Periodic orbits and polynomials

Question

There are two simple and classic enumerations that still I'm puzzled about. Let's start with a simple counting problem from a well-known dynamical system.

fact 1 Consider the "tent map" f:[0,1]→[0,1] with parameter 2, that is

f(x):=2min(x,1-x).

Clearly, it has 2 fixed points, and more generally, for any positive integer n, there are 2ⁿ periodic points of period n (it's easy to count them as they are fixed points of the n-fold iteration of f, which is a piecewise linear function oscillating up and down between 0 and 1 the proper number of times). To count the number of periodic orbits of minimal period n, a plain and standard application of the Moebius inversion formula gives

Number of n-orbits of (I,f) = $\frac{1}{n}\sum_{d|n} \mu(d)2^{n/d}.$

(rmk: any function with similar behaviour would give the same result, e.g. f(x)=4x(1-x),...&c.)

Now let's leave for a moment dynamical systems and consider the following enumeration in the theory of finite fields.

fact 2 Clearly, there are 2ⁿ polynomials of degree n in $\mathbb{F}_2[x]$. With a bit of field algebra it is not hard to compute the number I(n) of the irreducible ones. One can even make a completely combinatorial computation, just exploiting the unique factorization, expressed in the form:

$\frac{1}{1-2x}=\prod_{n=1}^\infty (1-x^n)^{-I(n)}.$

One finds:

Number of irreducible polynomials of degree n in $\mathbb{F} _ 2[x]$ = $\frac{1}{n}\sum_{d|n} \mu(d)2^{n/d}.$

Question: it's obvious by now: is there a natural and structured bijection between periodic orbits of f and irreducible polinomials in $\mathbb{F}_2[x]$? How is interpreted the structure of one context when transported ni the other?

(rmk: of course, analogous identities hold for any p > 2)

Answer 1

How I see it is every fixed point comes from an equation $T^nx=x$. Denoting $f(x)=2x$ and $g(x)=2(1-x)$ we see that this corresponds to solving equations $$h_1\circ h_2\circ\cdots \circ h_n (x)=x$$ where $h_i\in \{f,g\}$. This is geometrically the intersection of two lines and thus gives a unique solution, and therefore a correspondence between periodic points of period $n$ and binary strings of length $n$. Now since concatenating a binary string $L$ with itself clearly gives the same $x$ with $x=L(x)=L\circ L(x)$ and you have a shift operator $L\circ h(x)=x \implies h\circ L(y)=y$ where $y=h(x)$ you get a bijection between periodic orbits and aperiodic cyclic sequences of zeros and ones, which are well known to be in bijection with the irreducible polynomials of $\mathbb F_2 [x]$.

Answer 2

In the paper, review of which is cited below, the bijection between irreducible polynomials and periodic sequences is established. Periodic points of this map $f$ are less or more in obvious less or more bijection:) with periodic sequences of 0,1: just use symbolic version of $f$ (binary representation).

Golomb, Solomon W. Irreducible polynomials, synchronization codes, primitive necklaces, and the cyclotomic algebra. 1969 Combinatorial Mathematics and its Applications (Proc. Conf., Univ. North Carolina, Chapel Hill, N.C., 1967) pp. 358--370

Let $\alpha$ be a primitive root of $\text{GF}(q^n)$. The author observes that if $m=m_1q^{n-1}+m_2q^{n-2}+\cdots+m_n$ is the $q$-ary representation of the integer $m$, then the cyclic sequence (``necklace'') $m_1m_2\cdots m_n$ has no subperiod if and only if the minimal polynomial of $\alpha^m$ has degree $n$. Since a cyclic shift of the necklace corresponds to conjugation of $\alpha^m$, this exhibits an explicit one-to-one correspondence between the irreducible polynomials of degree $n$ over $\text{GF}(q)$ and the aperiodic necklaces with $n$ beads in $q$ colors. In Section 5, we learn that the integers $15^i (\text{mod}\,31)$, $i=0,1,\cdots,5$, when written in binary form, a maximal binary comma free dictionary. In Sections 6 and 7, the author restricts himself to $q=2$, and presents an algorithm for obtaining the minimal polynomial of $\alpha^p$ from that of $\alpha$, if $p$ is a prime $>2$. This algorithm is very simple for $p=3$, requiring $O(n^3)$ operations for a polynomial of degree $n$, but the work involved grows exponentially with $p$.

Reviewed by R. J. McEliece

Answer 3

The irreducible polynomials of degree $n$ over $\mathbb{F}_2[x]$ can be identified with the periodic orbits of minimal period $n$ of the Frobenius map $x \mapsto x^2$ acting on $\overline{ \mathbb{F}_2 }$. I think one can't do better than this canonically.

Let me mention a third related enumeration that might help you out. For fixed $n$, let $\alpha$ be a primitive element for $\mathbb{F}_{2^n}$ as an extension of $\mathbb{F}_2$. Then orbits of the Frobenius map of minimal period $n$ can be identified with aperiodic words $\sum a_i \alpha^{p^i}$ of length $n$ on the alphabet $\{ 0, 1 \}$ up to cyclic permutation, i.e. Lyndon words. It might be easier to give an explicit bijection to Lyndon words; for one thing, Lyndon words on alphabets of any size make sense whereas irreducible polynomials only make sense over prime power fields.