In number theory there is a certain philosophy that is a good toy model for the integers . The two rings share an important property: they are basically the canonical examples of Euclidean domains, hence PIDs, hence UFDs. However, many number-theoretic questions involving prime factorization over are much easier than their corresponding questions over . One way to see this is to look at their zeta functions.

The usual zeta function reflects the structure of prime factorization through its **Euler product**

where the product runs over all primes; this is essentially equivalent to unique factorization. Since we know that monic polynomials over also enjoy unique factorization, it’s natural to ask whether there’s a sum over monic polynomials that would give a similar Euler product.

In fact, there is such a product, and investigating it leads naturally to a seemingly unrelated subject: the combinatorics of words.

**The cyclotomic identity**

To phrase the Euler product correctly, recall that the zeta function of a ring of integers in a finite extension of can be written

.

where the sum runs over all ideals of , the product runs over all prime ideals of , and is the norm of an ideal; this Euler product reflects prime factorization of ideals in , and to make it work it is crucial that the definition of norm be multiplicative. On the other hand, there is an obvious choice of multiplicative function on polynomials: if the degree of the polynomial is , define its norm to be . (The choice of sign will make sense later.)

Since every ideal in is principal, we may identify ideals with monic polynomials. There are monic polynomials of degree , so we are led to the zeta function

.

This is almost disappointing: it’s much easier to deal with than the Riemann zeta function. Analytic continuation and the functional equation are trivial, and we know all of its poles and zeroes! But let’s keep going. The Euler product of the above zeta function is given by

where is the number of irreducible polynomials over of degree . I claim that knowing only that this product is equal to uniquely determines for all . In fact, much more is true.

**Proposition:** The group of formal power series of the form is isomorphic to the direct product of countable copies of with generators .

*Proof.* Let be the group of formal power series of the form . It’s straightforward to verify that where the element is sent to (this is an internal direct product), and the conclusion follows from here. More generally we can replace with any power series of the form .

We can now compute as follows. Taking times the logarithmic derivative of the zeta function gives

and the coefficient of on both sides is . How should we interpret this identity? Here’s one way: the polynomial factors over as the product of all irreducible polynomials of degree . In other words, every element of has a unique period under the action of the Frobenius map, and irreducible polynomials are in natural bijection with orbits of the Frobenius map. This is a very important point to which I will return. Mobius inversion then gives

.

Hence we have proven the **cyclotomic identity**

and our explicit formula for gives, rather easily, the asymptotic

where , by analogy with the usual prime number theorem.

**Lyndon words**

revealed itself to be Moreau’s necklace-counting function, which also counts equivalence classes of aperiodic necklaces. I was curious if there was an explicit bijection here and asked MathOverflow. It turns out that the bijection has some interesting things to say about finite fields, as I described in a different question.

The key is the Frobenius map . One can think of the algebraic closure , which is the variety associated to the ring , as a dynamical system on which the Frobenius map acts, and this dynamical system has the property that the fixed points of are precisely a copy of ; this is a fundamental fact of Galois theory and implies that the dynamical zeta function (which we first encountered when talking about Newton’s sums) is equal to

.

In fact, this definition agrees with the definition using ideals. The connection, as I have said, is that irreducible polynomials can naturally be identified with orbits under the action of the Frobenius map. (This is a simple version of the ideal-variety correspondence over non-algebraically closed fields: maximal ideals of can naturally be identified with “closed points” in .)

For aperiodic necklaces, the relevant dynamical system is given instead by the set of **aperiodic words** over an alphabet of size , which are words of length which have no nontrivial stabilizer under cyclic rotation. These words are acted on by cyclic rotation , and the fixed points of can be identified with aperiodic words of period , which can in turn be identified with words of length (since any word has a unique decomposition into copies of an aperiodic word), of which there are . It follows that, again,

.

The connection between cyclic rotation and the Frobenius map is as follows. Fix an irreducible monic polynomial of degree . If one of its roots is , then the rest of its roots are , and has basis , so we can write any of its elements as

.

In this basis, the Frobenius map acts by cyclic rotation of the coordinates , which define a word of length on an alphabet of size , and the number of elements in the orbit is precisely the length of the unique aperiodic factor of this word. In particular, orbits of length are in bijection with the other irreducible polynomials of degree , which in turn are in bijection with equivalence classes of aperiodic words of length .

A concrete way to think about equivalence classes of aperiodic words is as follows. Fix a total ordering on the alphabet, and consider the lexicographical order on words, which is total. Of the cyclic rotations of an aperiodic word, a unique word is minimal in the lexicographic order, and such words are referred to as Lyndon words. Now, what all this zeta function stuff suggests is that, since the coefficient of is equal to , words should have a unique factorization of some sorts into Lyndon words with multiplicity.

This is in fact true. The more precise statement is as follows.

**Proposition:** Fix a totally ordered alphabet . Every word on has a unique factorization where is a Lyndon word and in the lexicographic order for all .

*Proof.* We proceed by induction. Define to be the minimal word such that . We claim that is a Lyndon word. is aperiodic since for any words . Moreover, if is not Lyndon then there would exist such that , and then , so is not minimal; contradiction.

By induction we obtain a factorization into Lyndon words such that for all , so we have shown existence. To show uniqueness, suppose that is some other factorization, and suppose WLOG that . The only way this could occur is if is a left factor of , since otherwise their letters would disagree, but this is impossible by the assumption that is minimal.

It therefore follows that a word is uniquely specified by the multiplicity with which each Lyndon word appears in it, and this statement is equivalent to the cyclotomic identity.

on November 9, 2010 at 5:25 pm |Zeta functions, statistical mechanics and Haar measure « Annoying Precision[…] where . The corresponding Euler product is described in this previous post. […]

on January 4, 2010 at 2:43 am |The arithmetic plane « Annoying Precision[…] Posts The connected components functorIMO 2009 and proof systemsTextbooksBibliographyAboutThe cyclotomic identity and Lyndon wordsThe "correct" definition of a homomorphismSome contextThe weak Nullstellensatz and affine […]

on November 4, 2009 at 6:56 am |Newton’s sums, necklace congruences, and zeta functions II « Annoying Precision[…] Comments Qiaochu Yuan on The cyclotomic identity and Ly…harrison on The cyclotomic identity and Ly…The cyclotomic ident… on Newton’s […]

on November 3, 2009 at 11:34 am |harrisonAbout the Frobenius map’s action on : You can recover the absolute Galois group of from the description of this map, right? So one way of thinking about why Gal( ) carries so much more information is that there’s no good choice of “Frobenius map” on the algebraic closure of Q.

on November 3, 2009 at 11:40 am |Qiaochu YuanYep. One way to think about is that every algebraic number over is a root of unity, so every extension is cyclotomic, in particular abelian. The maximal abelian extension of is well-understood, but it takes more work to describe, and then there’s all those horrible non-abelian ones.