« Young’s lattice
Newton’s sums, necklace congruences, and zeta functions II »

The cyclotomic identity and Lyndon words

November 3, 2009

In number theory there is a certain philosophy that \mathbb{F}_q[x] is a good toy model for the integers \mathbb{Z}. 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 \mathbb{F}_q[x] are much easier than their corresponding questions over \mathbb{Z}. One way to see this is to look at their zeta functions.

The usual zeta function \zeta(s) = \sum_{n \ge 1} \frac{1}{n^s} reflects the structure of prime factorization through its Euler product

\displaystyle \zeta(s) = \prod_p \frac{1}{1 - p^{-s}}

where the product runs over all primes; this is essentially equivalent to unique factorization. Since we know that monic polynomials over \mathbb{F}_q[x] 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 O_K in a finite extension of \mathbb{Z} can be written

\displaystyle \zeta_K(s) = \sum_I \frac{1}{N(I)^s} = \prod_P \frac{1}{1 - N(P)^{-s}}.

where the sum runs over all ideals of O_K, the product runs over all prime ideals of O_K, and N(P) is the norm of an ideal; this Euler product reflects prime factorization of ideals in O_K, 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 n, define its norm to be t^{-n}. (The choice of sign will make sense later.)

Since every ideal in \mathbb{F}_q[x] is principal, we may identify ideals with monic polynomials. There are q^n monic polynomials of degree n, so we are led to the zeta function

\displaystyle \zeta_{\mathbb{F}_q[x]}(t) = \sum_{n=0}^{\infty} q^n t^n = \frac{1}{1 - qt}.

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

\displaystyle \prod_P \frac{1}{1 - t^{\text{deg } P}} = \prod_{n \ge 1}\left( \frac{1}{1 - t^n} \right)^{M(q, n)}

where M(q, n) is the number of irreducible polynomials over \mathbb{F}_q of degree n. I claim that knowing only that this product is equal to \frac{1}{1 - qt} uniquely determines M(q, n) for all n. In fact, much more is true.

Proposition: The group of formal power series of the form 1 + t \mathbb{Z}[t] is isomorphic to the direct product of countable copies of \mathbb{Z} with generators g_n = \frac{1}{1 - t^n}.

Proof. Let G_n be the group of formal power series of the form 1 + t^n \mathbb{Z}[t]. It’s straightforward to verify that G_n \simeq \mathbb{Z} \times G_{n+1} where the element (k, g) is sent to g_n^k g (this is an internal direct product), and the conclusion follows from here. More generally we can replace g_n with any power series of the form 1 + t^n + a_{n+1} t^{n+1} + ....

We can now compute M(q, n) as follows. Taking t times the logarithmic derivative of the zeta function gives

\displaystyle \frac{qt}{1 - qt} = \sum_{n \ge 1} n M(q, n) \frac{t^n}{1 - t^n}

and the coefficient of t^n on both sides is q^n = \sum_{d | n} d M(q, d). How should we interpret this identity? Here’s one way: the polynomial x^{q^n} - x factors over \mathbb{F}_q as the product of all irreducible polynomials of degree d | n. In other words, every element of \mathbb{F}_{q^n} has a unique period d 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

\displaystyle M(q, n) = \frac{1}{n} \sum_{d | n} \mu \left( \frac{n}{d} \right) q^d.

Hence we have proven the cyclotomic identity

\displaystyle \frac{1}{1 - qt} = \prod_{n \ge 1} \left( \frac{1}{1 - t^n} \right)^{ \frac{1}{n} \sum_{d | n} \mu \left( \frac{n}{d} \right) q^d }

and our explicit formula for M(q, n) gives, rather easily, the asymptotic

\displaystyle M(q, n) \sim \frac{q^n}{n} = \frac{x}{\log_q x}

where x = q^n, by analogy with the usual prime number theorem.

Lyndon words

M(q, n) 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 x \mapsto x^q. One can think of the algebraic closure F = \overline{ \mathbb{F}_q }, which is the variety associated to the ring \mathbb{F}_q[x], as a dynamical system on which the Frobenius map f acts, and this dynamical system has the property that the fixed points of f^n are precisely a copy of \mathbb{F}_{q^n}; 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

\displaystyle \zeta_X(t) = \exp \left( \sum_{n \ge 1} \frac{q^n}{n} t^n \right) = \frac{1}{1 - qt}.

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 \mathbb{F}_q[x] can naturally be identified with “closed points” in \overline{ \mathbb{F}_q }.)

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

\displaystyle \zeta_W(t) = \exp \left( \sum_{n \ge 1} \frac{q^n}{n} t^n \right) = \frac{1}{1 - qt}.

The connection between cyclic rotation and the Frobenius map is as follows. Fix an irreducible monic polynomial p(x) \in \mathbb{F}_q[x] of degree n. If one of its roots is \alpha, then the rest of its roots are \alpha, \alpha^q, \alpha^{q^2}, ..., and \mathbb{F}_q[x]/(p(x)) \simeq \mathbb{F}_{q^n} has basis \alpha, \alpha^q, \alpha^{q^2}, ..., so we can write any of its elements as

a_0 \alpha + a_1 \alpha^2 + ... + a_{n-1} \alpha^{q^{n-1}}.

In this basis, the Frobenius map acts by cyclic rotation of the coordinates (a_0, ... a_{n-1}), which define a word of length n on an alphabet of size q, 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 n are in bijection with the other irreducible polynomials of degree n, which in turn are in bijection with equivalence classes of aperiodic words of length n.

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 \frac{1}{1 - qt} is equal to q^n, 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 A. Every word w on A has a unique factorization w = L_1 L_2 ... L_m where L_i is a Lyndon word and L_i \ge L_{i+1} in the lexicographic order for all i.

Proof. We proceed by induction. Define L_1 to be the minimal word w_1 ... w_k such that w_1 ... w_k \ge w_{k+1} ... w_n. We claim that L_1 is a Lyndon word. L_1 is aperiodic since a < ab for any words a, b. Moreover, if L_1 is not Lyndon then there would exist i such that w_1 ... w_k > w_i ... w_k, and then w_1 ... w_k \ge w_i ... w_n, so L_1 is not minimal; contradiction.

By induction we obtain a factorization w = L_1 L_2 ... L_m into Lyndon words such that L_i \ge L_{i+1} ... L_m \ge L_{i+1} for all i, so we have shown existence. To show uniqueness, suppose that w = L_1' ... L_r' is some other factorization, and suppose WLOG that L_1 > L_1'. The only way this could occur is if L_1' is a left factor of L_1, since otherwise their letters would disagree, but this is impossible by the assumption that L_1 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.

Possibly related posts: (automatically generated)

This entry was posted on November 3, 2009 at 11:11 am and is filed under algebraic combinatorics, number theory.

Tags: , , , ,

3 Responses to “The cyclotomic identity and Lyndon words”

  1. harrison Says:

    November 3, 2009 at 11:34 am

    About the Frobenius map’s action on \overline{ \mathbb{F}_q }: You can recover the absolute Galois group of \mathbb{F}_q from the description of this map, right? So one way of thinking about why Gal( \overline{ \mathbb{Q}}/ \mathbb{Q}) carries so much more information is that there’s no good choice of “Frobenius map” on the algebraic closure of Q.

    Reply
    • Qiaochu Yuan Says:

      November 3, 2009 at 11:40 am

      Yep. One way to think about \mathbb{F}_q is that every algebraic number over \mathbb{F}_q is a root of unity, so every extension is cyclotomic, in particular abelian. The maximal abelian extension of \mathbb{Q} is well-understood, but it takes more work to describe, and then there’s all those horrible non-abelian ones.

      Reply
  2. Newton’s sums, necklace congruences, and zeta functions II « Annoying Precision Says:

    November 4, 2009 at 6:56 am

    [...] Comments Qiaochu Yuan on The cyclotomic identity and Ly…harrison on The cyclotomic identity and Ly…The cyclotomic ident… on Newton’s [...]

    Reply

Leave a Reply