Periodic orbits and polynomials

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]$.

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

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.