Algebraic codes that achieve list decoding capacity were recently
constructed by a careful ``folding'' of the Reed-Solomon code. The
``low-degree'' nature of this folding operation was crucial to the list
decoding algorithm. We show how such folding schemes conducive to list
decoding arise out of the Artin-Frobenius automorphism at primes in
Galois extensions. Using this approach, we construct new folded
algebraic-geometric codes for list decoding based on cyclotomic
function fields with a cyclic Galois group. Such function fields are
obtained by adjoining torsion points of the Carlitz action of an
irreducible $M \in \F_q[T]$. The Reed-Solomon case corresponds to the
simplest such extension (corresponding to the case $M=T$). In the
general case, we need to descend to the fixed field of a suitable
Galois subgroup in order to ensure the existence of many degree one
places that can be used for encoding.

Our methods shed new light on algebraic codes and their list decoding,
and lead to new codes achieving list decoding capacity.
Quantitatively, these codes provide list decoding (and list
recovery/soft decoding) guarantees similar to folded Reed-Solomon
codes but with an alphabet size that is only polylogarithmic in the
block length. In comparison, for folded RS codes, the alphabet size is
a large polynomial in the block length. This has applications to
fully explicit (with no brute-force search) binary concatenated codes
for list decoding up to the Zyablov radius.