For a prime p and a field $\mathbb{Z}_p$, is there support to find polynomials in $\mathbb{Z}_p[x]$ that can be iterated to generate all of $\mathbb{Z}_p$?

As an example that such exist, let p = 251 and consider $f(x) = 3x^3 + 3x^2+x+39 \in \mathbb{Z}_p[x]$. You can iterate this polynomial with any $x_0 \in \mathbb{Z}_p$, i.e., $x_{n+1} = f(x_n)$, and generate all of $\mathbb{Z}_p$.

I would appreciate any help identifying the theory about how such polynomials can be selected. Or even a topic / reference that gets me in the ballpark.

  • 2
    $\begingroup$ You know that any function $f:\Bbb{Z}_p \to \Bbb{Z}_p$ is realized with the polynomial $f = \sum_{a=0}^{p-1}f(a) \prod_{b \ne a} \frac{x-b}{a-b}$ and that as functions $g =f$ iff as polynomials $x^p-x |g-f$ ? From there we can contruct all the polynomials satisfying your problem for a given $p$. In general $f$ will be of degree $\le p-1$, that you found one of degree $3$ for $p = 251$ is probably quite exceptional. Asking for the polynomial of least degree given $p$ would be fun. $\endgroup$ – reuns Aug 22 at 1:08
  • $\begingroup$ I'm not following. Might you have a reference that I could locate and examine? $\endgroup$ – mgeile Aug 22 at 3:41
  • 1
    $\begingroup$ Unless I am missing something, $x+1$ works well. $\endgroup$ – user58697 Aug 22 at 3:45
  • $\begingroup$ What is unclear to you ? Given any permutation $\sigma : \Bbb{Z}_p \to \Bbb{Z}_p$ there is a polynomial such that $f(\sigma(a)) = \sigma(a+1)$ which satisfies $\Bbb{Z}_p=\{ x_0,f(x_0),f(f(x_0)),\ldots \}$. Of course when I mentioned $\deg(f)$ I meant excluding those of degree $1$. $\endgroup$ – reuns Aug 22 at 3:46
  • $\begingroup$ Or, to any $p$-cycle in $Sym(\Bbb{Z}_p)$ there exists a polynomial $f$ such that $f(a)=\sigma(a)$ for all $a$. As $a\mapsto\sigma(a)\mapsto\sigma^2(a)\cdots\mapsto\sigma^p(a)=a$ cycles through all the elements for any $a$, so do iterates of $f$. $\endgroup$ – Jyrki Lahtonen Aug 22 at 6:11

Your Answer

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

Browse other questions tagged or ask your own question.