# Chaos in finite field

Let's think about some finite field $\mathbb{F}$. Is it possible to construct a map

$x[n+1] = \mathcal{P}(x[n], x[n-1],...,x[n-k]), \ \ \ \forall x\in\mathbb{F}$

where $\mathcal{P}$ - polynomial with coeffs $\in\mathbb{F}$, so it's behavior be non-periodic, but chaotic,
so x[n] be "jumping" randomly over $\mathbb{F}$?
(As $x[n+1] =1-2\cdot x[n]^2$ on [-1,1])

-
Polynomials can only have a fixed number of variables, so perhaps you mean $\mathcal P(x[n],x[n-1],\dots,x[n-k])$? (Any reason you are not using subscsripts? $x[n]$ is programming notation, not a math notation.) – Thomas Andrews May 23 '13 at 15:45
@Thomas Andrews Sorry... My mind immersed in Mathematica – lesobrod May 23 '13 at 15:48

If $x[n+1]$ depends on $d$ of the previous values in the sequence (i.e. $x[n+1]=P(x[n],x[n-1],\ldots,x[n-d+1])$, the answer is negative. There are only $|\mathbb{F}|^d$ possible $d$-tuples of the values, so once any of them repeats (Dirichlet's principle), the subsequent values will start repeating too, making the function eventually-periodic.

-
Yes, now I see clearly. – lesobrod May 23 '13 at 15:54
Hmm Are there other ways to make simple chaotic finite state system? – lesobrod May 23 '13 at 15:55
@lesobrod no, because of the exact same reasonning... – Glougloubarbaki May 23 '13 at 16:01
So what about nonconservative system: $x[n+1]=P(n,x[n-1],...)$ ? Any chance for finite chaos... – lesobrod May 23 '13 at 16:04

Let $f:F^k \to F$ be a function on any finite set $F$, then the sequence defined recursively by $x_{n}=f(x_{n-1},x_{n-2},...,x_{n-k})$ can only take a finite number of values. So it must be periodic, maybe only after a certain rank.

But your question is not trivial, though. Assuming the field $F$ to be infinite but of finite characteristic, for example the p-adic numbers, can you define chaotic in such a topology?

-
Thank you, I'll try to play with $p$-adic monsters... – lesobrod May 23 '13 at 16:25