Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I ran across a math puzzle that went like this:

Consider the list $1,9,9,3, \cdots$ where the next entry is equal to the sum mod 10 of the prior 4. So the list begins $1,9,9,3,2,3,7,\cdots$. Will the sequence $7,3,6,7$ ever occur?

(Feel free to pause here and solve this problem for your own amusement if you desire. Spoiler below.)

So the answer is "yes", and we can solve this by noticing that the function to derive the next digit is invertible so we can derive digits going to the left as well. Going left, we find $7,3,6,7$ pretty quickly.

I wrote a program and found that the period (equivalently the length of the permutation's cycle) is 1560. But surprisingly (to me) altering the starting sequence from 1,9,9,3 to most any other sequence left the period at 1560. There are a few cases where it changes; for example, starting with 4,4,4,4 we get a period of length only 312.

So, my question: what's special about 1560 here?

Note: This feels a lot like LFSRs, but I don't know much about them.

share|improve this question
3  
I don't even know what a LFSR is... –  Mariano Suárez-Alvarez Jun 2 '11 at 22:16
    
Linear feedback shift register. –  Gerry Myerson Jun 2 '11 at 22:47

2 Answers 2

up vote 7 down vote accepted

This is a linear homogeneous recurrence relation with characteristic polynomial $p(x) = x^4 - x^3 - x^2 - x - 1$. To compute its period $\bmod 10$ it suffices to compute its period $\bmod 2, 5$ by the Chinese Remainder Theorem.

Over any field, a recurrence $a_n$ with characteristic polynomial $p(x)$ has closed form

$$a_n = \sum c_i(n) r_i^n$$

where $r_i$ is a root of $p$ and $c_i(n)$ is a polynomial of degree at most one less than the multiplicity of $r_i$ (with coefficients in a splitting field of $p$). Now $\bmod 2$ we see that $p(x)$ has no roots, so it's either irreducible or the product of two irreducible quadratics. $\bmod 2$ the only irreducible quadratic is $x^2 + x + 1$, which doesn't divide $p(x)$, so $p(x)$ is irreducible $\bmod 2$. It follows from basic facts about finite fields that $p(x)$ divides $x^{2^4} - x$, so the roots of $p(x) \bmod 2$ are $15^{th}$ roots of unity and the period of $a_n \bmod 2$ divides $15$.

Similarly, $\bmod 5$ we see that $p(x)$ has no roots, so it's either irreducible or the product of two irreducible quadratics. Casework rules out the latter. Again, it follows that $p(x)$ divides $x^{5^4} - x$, so the roots of $p(x) \bmod 5$ are $624^{th}$ roots of unity and the period of $a_n \bmod 5$ divides $624$.

Putting it together we see that the period of $a_n \bmod 10$ divides $\text{lcm}(15, 624) = 2 \cdot 1560$. The fact that you often get $1560$ means that the period of $a_n \bmod 2$ is often either $5$ or $15$ and the period of $a_n \bmod 5$ is often either $312$ or $104$ (and at least one of these is the one divisible by $3$) which just means that the roots of $p(x) \bmod 2, p(x) \bmod 5$ are generators or close to generators of the multiplicative groups of the splitting fields $\mathbb{F}_{2^4}, \mathbb{F}_{5^4}$.

share|improve this answer
    
For some reason (which follows from Ross's answer) we never get a period of $624$. Is there a nice way to explain this using your style of reasoning? –  Eric Naslund Jun 2 '11 at 22:35
    
@Eric: not really. Note that I didn't use any specific properties of $p$ other than that it was irreducible $\bmod 2$ and $\bmod 5$, so the above argument can't distinguish $p$ from any other irreducible quartic with the same property, and the maximal period will differ between them. At some point you have to do some kind of specific calculation to figure out the exact maximal period for a particular $p$. –  Qiaochu Yuan Jun 2 '11 at 23:01
3  
There is a better answer than that, if you're willing to cite something advanced. What you want to show is that $x^{312} \equiv 1 \mod p(x)$. This is equivalent to asking that $x$ be a square in $\mathbb{F}_5[x]/p(x)$ (since the unit group of $\mathbb{F}_5[x]/p(x)$ is cyclic of order 624). Using quadratic reciprocity for polynomials over finite fields math.uconn.edu/~kconrad/blurbs/ugradnumthy/QRcharp.pdf this turns into the question of whether $p(x)$ is a square modulo $x$. We have $p(x) \equiv -1 \mod x$, and $-1$ is a square mod $5$. –  David Speyer Jun 2 '11 at 23:11
    
Now, seeing that the order is not 104, that I don't see how to do without a brute force computation. –  David Speyer Jun 2 '11 at 23:12
    
Ah, nice observation. –  Qiaochu Yuan Jun 2 '11 at 23:17

Your recurrence is linear in that you can add two series together term by term and still have it a series. The period of (0,0,0,1) is 1560, so all periods will be a divisor of that. To get 1560 you just have to avoid shorter cycles.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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