5
$\begingroup$

If $f(x)$ is defined as :

$f(x)=i$ ,if $x\equiv i$ (mod n), $0\leq i< n$

How can I prove whether the following recursive sequences are periodic or not?

$$x_{i+1}=f(k_0+k_1x_{i}+k_2x_{i-1}+...+k_{m+1}x_{i-m})$$

and $$x_i=1,0\leq i< m$$

And for instance, how can I find period of an special case:($k_0=k_1=k_2=1$)

$$x_{i+1}=f(1+x_{i}+x_{i-1}) $$ $$x_0=x_1=1$$

$\endgroup$
  • $\begingroup$ What do you mean by periodic, for example $1,2,3,4,3,4,3,4,3,4,3,4,\cdots$ is it periodic for you or do you need it to be fully periodic from the first point? $\endgroup$ – Elaqqad Jul 21 '15 at 19:12
  • $\begingroup$ Yes, I consider it as a periodic function. $\endgroup$ – SMA.D Jul 22 '15 at 7:34
2
$\begingroup$

1)All sequences are periodic after a certain point

The first sequences are periodic after a certain integer,and there period is less than $$(m+1)^n $$ In order to prove this you can consider the sequence $$y_k=(x_k,x_{k+1},\cdots,x_{k+m}) $$ and observe that if there exists two integers $i< N$ such that $y_i=y_N$ then $x_i$ is periodic and it's period is less than $N$, the second observation is the fact that $y_k$ can take it's values in the set $[0,n-1]^{m+1}$ which is finite ant it's cardinal is $(m+1)^{n}$ and this means that $N,i$ (in the first observation) must exist.

2)Is all sequences fully periodic from the first point,

This is equivalent to asking whither there exists an integer such $N$ such that: $$y_N=y_1 $$ This is not true in general take for example the sequence (there are simpler examples but this example shows why this could hold): $$n=4\quad f(n)= (n\mod 4)$$ and consider the sequence: $$x_{n+1}=f(4x_{n-4}) $$

3)advanced study of the problem

The sequence as stated is very known and their periodicity is well studied,as you defined the function $f$ to be the identity in $K=\mathbb{Z}_n$ the set of sequences could be defined in the ring $\mathbb{Z}_n$ by : $$x_{i+1}=k_0+k_1x_{i}+k_2x_{i-1}+...+k_{m+1}x_{i-m}$$ and from here, this type of sequences is called : linear recurrence sequences, when $K$ is a field they are related to the roots of their corresponding polynomial $P$ having $k_i$ as coefficients and we can even find a closed form for the sequence $a_k$. In particular when $K=\mathbb{Z}_n$ with $n$ is a power of a prime, we know a theorem due to Peterson linking the period of the sequence to the smallest integer $r$ such that corresponding polynomial $P$ divides $x^r-1$. See for example this paper for a revue.

The periodicity is studied here in general, but there are no more powerful results than what we proved in $(1)$

4) The second question

For the following sequence: $$x_{i+1}=1+x_i+x_{i-1} \quad \quad x_0=x_1=1$$ we consider $y_i=(x_i+1)/2$ we have: $$y_{i+1}=y_i+y_{i-1}\quad \quad y_0=y_1=1 $$ which is a shifted Fibonacci sequence and its period is called the $n$th Pisano period, written $\pi(n)$, and I don't know a closed form for this number but it's also well studied and you can prove a lot of relations between these numbers.

$\endgroup$
  • $\begingroup$ Thank you a lot, your answer is quite complete. But Is the statistical properties of the resulting sequences, also well-studied? $\endgroup$ – SMA.D Jul 22 '15 at 7:32
  • 1
    $\begingroup$ If fact these sequences are well studied because they have a very interesting application in cryptography, and specifically because their statistical properties are used as ciphers, look for Linear FeedBack Registers (LFBRs) for more details. $\endgroup$ – Elaqqad Jul 22 '15 at 8:31
  • 1
    $\begingroup$ Their values modulo an integer $M$ very large are a source of "random" numbers (satisfy some conditions of randomness) so they can be also considered as random number generators (not truly random, see Broadcasting, GBS). For the ciphers we don't consider the sequence as it is defined in your question, because the numbers will be predictable easily, we actually consider a function $f$ which is equally distributed modulo $M$ but not linear to make good ciphers but there are some of attacks in all cases $\endgroup$ – Elaqqad Jul 22 '15 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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