18
$\begingroup$

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*}

$\endgroup$
  • 1
    $\begingroup$ In $P$ a sign is missing for the coefficient of $x^{52}$. $\endgroup$ – Jules Lamers Jan 9 at 4:24
  • 4
    $\begingroup$ An overview of the proof is given here I believe: njohnston.ca/2010/10/… $\endgroup$ – Per Alexandersson Jan 9 at 6:09
  • 3
    $\begingroup$ After having a look at the link above, it seems like a big part of the question is whether there's a conceptual reason that the 92x92 transition matrix for the atoms has a kernel of dimension 18. $\endgroup$ – j.c. Jan 9 at 16:42
  • 3
    $\begingroup$ @j.c. Conceivably the kernel could have smaller dimension. The initial conditions might cause the numerator to have factors in common with the denominator. For instance, the recurrence $f_{n+1}=5f_n-6f_{n-1}$ has general solution $a2^n+b3^n$, but the initial conditions $f_0=1, f_1=2$ cause $b=0$. $\endgroup$ – Richard Stanley Jan 9 at 19:56
5
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.