Period of a binary sequence

Question

Given the first $5$ elements of a binary sequence $x_1 = 0, x_2 = 1, x_3 = 0, x_4 = 0, x_5 = 0$, the subsequent ones are determined as follows:

$$x_{n + 5} = x_{n} + x_{n + 2}$$

(this is an example of Linear Feedback Shift Register).

So,

$$01000010010110 \ldots$$

This sequence is periodic after $31$ elements. How is it possible to prove this?

---

$31 = 2^5 - 1$ and it can be related to the number of the first assigned elements $x_1, \ldots, x_5$.

I tried to expand the single items $x_i$ as a combination of the first $5$ items till no. $18$, with nothing relevant, except the fact that each $x_i$ can always be expressed as

$$x_i = a_1 x_1 + a_2 x_2 + a_3 x_3 + a_4 x_4 + a_5 x_5$$

where $a_i$ are integer coefficients.

Is this the right appoach to determine the periodicity of the sequence, or other ones are preferable?

Answer 1

The simple way to prove it is to compute the first $36$ terms and show that $01000$ recurs starting at position $32$ and not before. As the length of the recurrence is $5$ the behavior is determined by five successive terms and you are done. You can do the computation in a spreadsheet computing one term, then copy down for all the rest of the terms.

Answer 2

Any five subsequent elements determine the rest of the sequence, by the recursive formula. There are only $2^5 = 32$ such combinations of five elements possible, which means two things:

• The cycle, which inevitably occurs, will be at most of length $32$;
• The cycle will start occurring within $32$ steps.

The actual length of the cycle, and the point at which the cycle starts occurring, depends on the initial conditions: $x_i=0$ for all $i\in\{1\ldots 5\}$ gives a trivial sequence $00000\ldots$), for example. I don't know if there is any proper way, besides trial and error, to find the cycle length based on the initial conditions and the formula alone.

Answer 3

Your system can be described by the following matrix:

$$\left(\matrix{0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\\1&0&1&0&0\\}\right)\left(\matrix{x_n\\x_{n+1}\\x_{n+2}\\x_{n+3}\\x_{n+4}}\right)=\left(\matrix{\matrix{x_{n+1}\\x_{n+2}\\x_{n+3}\\x_{n+4}\\x_{n+5}}}\right)$$

Therefore all you need is to prove that the $31$st power of this matrix is the identity over $\mathbb{Z}_2$ (which is true, btw!).

Answer 4

Your sequence of bits comes together with a matching generating function $$ X(t)=x_0+x_1t+x_2t^2+\cdots=\sum_{i=0}^\infty x_it^i\in\Bbb{F}_2[[t]]. $$ Because all the arithmetic is done modulo two, the recurrency relation can be written to read $x_n+x_{n+2}+x_{n+5}=0$ for all $n\ge0$. The sum $x_n+x_{n+2}+x_{n+5}$ appears as the coefficient of $t^{n+5}$ the product $ (1+t^3+t^5)X(t). $ Check this yourself if you have never seen it, but this is really bread&butter in the theory LFSR-sequences. Consult e.g. Solomon Golomb's book.

Anyway, this means that all the terms of degree $5$ or higher in the product $X(t)(1+t^3+t^5)$ vanish. We therefore have the equation $$ X(t)=\frac{A(t)}{1+t^3+t^5}\tag{1} $$ for some polynomial $A(t)\in\Bbb{F}_2[t]$ of degree $\le4$.

Let's continue. Next I claim that the feedback polynomial $P(t)=1+t^3+t^5$ is irreducible in $\Bbb{F}_2[t]$. It is of degree five, so if it were reducible, then it would necessarily have a factor of degree at most two. But, $P(0)=P(1)=1$, so it has no zeros (and hence no linear factors). Nor is it divisible by the only irreducible quadratic polynomial $Q(t)=t^2+t+1$. This is because $Q(t)(t+1)=t^3+1$, so if $P(t)$ were divisible by $Q(t)$ so would be the monomial $t^5$, but that is absurd (by the uniqueness of factorization).

The basic properties of finite fields then tell us that

• the zeros of $P(t)$ are in the field $\Bbb{F}_{32}$ (aka $GF(32)$) and,
• therefore the zeros of $P(t)$ have multiplicative order that is a factor of $32-1=31$, and
• because $31$ is a prime (and $1$ is not a zero of $P(t)$), those zeros have order $31$ exactly.

Consequently $P(t)$ is a factor of the polynomial $t^{31}-1$. In many sources this fact is phrased as follows: the order of $P(t)$ is $31$. The argument outlined in the above sequence of bullets can be written using the concept of the order alone. I did it this way, because I think that on this site less people are familiat with that language.

Anyway, $P(t)R(t)=1-t^{31}$ for some polynomial $R(t)\in\Bbb{F}_2[t]$ of degree $31-5=26$. This allows us to rewrite $(*)$ as $$ X(t)=\frac{A(t)R(t)}{1-t^{31}},\tag{2} $$ where $$ Q(t)R(t)=b_0+b_1tb_2t^2+\cdots b_{30}t^{30}\tag{3} $$ is a polynomial of degree $\le30$.

By the familiar sum formula for the geometric series $$ \frac1{1-t^{31}}=1+t^{32}+t^{2\cdot31}+t^{3\cdot31}+\cdots=\sum_{k=0}^\infty t^{k\cdot31}.\tag{4} $$

Putting $(2),(3)$, and $(4)$ together we see that the coefficients of $X(t)$ follow a repeating period of length 31. A single period can be read from the coefficients of the product $A(t)R(t)$.

A final remark. A user of a linear feedback shift register with this feedback polynomial $P(t)$ can adjust the coefficients of the polynomial $A(t)$ be initializing the LFSR with those coefficients. Some other readers would think of doing the same by declaring another initial segment $x_0,x_1,x_2,x_3,x_4$. All according to which sequence you want to produce. Actually, in this case all the $31$ non-zero initializations simply produce the $31$ cyclic shifts of the same $m$-sequence, but let's leave that for the specialists.