The cyclotomic identity and Lyndon words

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

The cyclotomic identity and Lyndon words

November 3, 2009 by Qiaochu Yuan

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+1} \simeq \mathbb{Z} \times G_n$ 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.

Posted in math.CO, math.NT | Tagged finite fields, MaBloWriMo, zeta functions | 5 Comments

5 Responses

on November 9, 2010 at 5:25 pm | Reply 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 | Reply 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 | Reply 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 | Reply harrison

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.
- on November 3, 2009 at 11:40 am | Reply Qiaochu Yuan
  
  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.

Comments RSS

	ZW on The double commutant theo…
	auto on More about the Schrödinger equ…
	Jaromir Kuben on Meditation on the Sylow theore…
	Qiaochu Yuan on Meditation on the Sylow theore…
	Qiaochu Yuan on Some remarks on the infinitude…

Annoying Precision

"A good stock of examples, as large as possible, is indispensable for a thorough understanding of any concept, and when I want to learn something new, I make it my first job to build one." – Paul Halmos