#### [SOLVED] Order of Conway's "look and say" recurrence

Let $$L_n$$ be the length of the $$n$$th term of Conway's "look and say" sequence (https://oeis.org/A005341). The generating function $$F(x)= \sum_{n\geq 0}L_nx^n$$ is a rational function, say $$P(x)/Q(x)$$ in lowest terms, where $$Q(0)=1$$. The look and say sequence is built up from 92 "atoms" in a way that suggests $$\deg Q(x)=92$$. Actually, however, $$\deg Q(x)=72$$. Is there a theoretical reason for this?

For those who are interested, $$\begin{eqnarray*} P(x) & = & x+x^2-x^3-x^4-x^5-x^6-x^8+4x^9+6x^{10}-6x^{12}-8x^{13}\\ & & \ +x^{14}+5x^{15}+4x^{16}+x^{17}+4x^{18}+x^{19}-3x^{20}-6x^{21}-8x^{22}\\ & & \ -12x^{23}+6x^{24}+36x^{25}+20x^{26}+x^{27}-58x^{28}-34x^{29}+30x^{30}\\ & & \ +20x^{31}+23x^{32}-35x^{33}+9x^{34}+26x^{35}-8x^{36}-12x^{37}\\ & & \ -42x^{38}-7x^{39}+79x^{40}+13x^{41}-16x^{42}-14x^{43}-107x^{44}\\ & & \ +65x^{45}+33x^{46}+32x^{47}+39x^{48}-126x^{49}-38x^{50}+25x^{51}\\ & & \ +66x^{52}+64x^{53}-89x^{54}+8x^{55}-45x^{56}+15x^{57}+27x^{58}\\ & & -15x^{59}+44x^{60}+56x^{61}-54x^{62}-41x^{63}+11x^{64}+21x^{65}\\ & & \ +50x^{66}-62x^{67}+19x^{68}+4x^{69}+4x^{70}-15x^{71}-31x^{72}\\ & & \ +22x^{73}+20x^{74}-18x^{75}+18x^{76}-18x^{77}+18x^{78} -12x^{79}. \end{eqnarray*}$$ and $$\begin{eqnarray*} Q(x) & = & (1-x)(1-x^2-2x^3-x^4+2x^5+2x^6+x^7-x^8-x^9-x^{10}-x^{11}\\ & & \ -x^{12} +2x^{13}+5x^{14}+3x^{15}-2x^{16}-10x^{17}-3x^{18}-2x^{19}\\ & & \ +6x^{20}+6x^{21}+x^{22}+9x^{23}-3x^{24}-7x^{25}-8x^{26}\\ & & \ -8x^{27}+10x^{28}+6x^{29}+8x^{30}-5x^{31}-12x^{32}+7x^{33}\\ & & \ -7x^{34}+7x^{35}+x^{36}-3x^{37}+10x^{38}+x^{39}-6x^{40}\\ & & \ -2x^{41}-10x^{42}-3x^{43}+2x^{44}+9x^{45}-3x^{46}+14x^{47}\\ & & \ -8x^{48}-7x^{50}+9x^{51}+3x^{52}-4x^{53}-10x^{54}-7x^{55}\\ & & \ +12x^{56}+7x^{57}+2x^{58}-12x^{59}-4x^{60}-2x^{61}+5x^{62}\\ & & \ +x^{64}-7x^{65}+7x^{66}-5x^{67}+12x^{68}-6x^{69}+3x^{70} -6x^{71}). \end{eqnarray*}$$ #### @Guntram 2019-01-09 20:27:22

The characteristic polynomial of the transition matrix $$A$$ is given by $$f(x) = x^{18}(x-1)^2(x+1) Q(x)$$ with $$Q$$ as in the question, see the link given by Per Alexandersson.

With the notation in http://www.se16.info/js/lands2.htm, the relevant pieces recalled below, a computation for $$A$$ gives

• $$0$$-eigenvector: $$(2)-(4)-(73)+(75)$$ (in particular the kernel is 1-dimensional)

• $$1$$-eigenvectors: $$(1); (2)+(3)-(73)-(74)$$

• $$(-1)$$-eigenvector: $$(2)-(3)-(73)+(74)$$.

Interpreting this computation as a theoretical explanation, one might say:

• trivially, the block $$(1)$$ (given by $$22$$) is stable

• the successor of $$(2)+(75)$$ equals the successor of $$(4)+(73)$$ (up to a permutation of the blocks).

• the successor of $$(2)+(3)$$, S $$+ (2)+(3)$$ where S = $$\text{Hf Pa H C}$$, shares the same "prefix" S with the successor of $$(73)+(74)$$, S + $$(73) + (74)$$ (again, up to permutation of blocks)

• the successor of $$(2)+(74)$$ is given by T $$+ (3)+(73)$$, where T = $$\text{Hf Pa H Ca}$$, while the successor of $$(3)+(73)$$ is given by T$$+(2)+(74)$$.

These facts then force the degree to be smaller than the degree of the blocks.

Presumably the generalized eigenvectors for 0 correspond to combinations of blocks whose successors eventually become equal.

$$\begin{array}{|c|c|c|c|} \hline \text{Number} & \text{Element} & \text{Evolution} \\ \hline 1 & \text{H} & \text{H} \\ \hline 2 & \text{He} & \text{Hf Pa H Ca Li} \\ \hline 3 & \text{Li} & \text{He} \\ \hline 4 & \text{Be} & \text{Ge Ca Li} \\ \hline 73 & \text{Ta} & \text{Hf Pa H Ca W} \\ \hline 74 & \text{W} & \text{Ta} \\ \hline 75 & \text{Re} & \text{Ge Ca W}\\ \hline \end{array}$$