Iteration of Quadratic Polynomials Over Finite Fields - new research from Professor Roger Heath-Brown

As part of our series of research articles deliberately focusing on the rigour and intricacies of mathematics and its problems, Eminent Oxford Mathematician and number theorist Roger Heath-Brown discusses his latest work.

"Since retiring last September I've had plenty of time for research. Here is something I've been looking into.

Suppose $p$ is prime and consider the map $x\mapsto x^2+1$ on the ring $\mathbb{Z}_p$. For example, if $p=5$ then $0\to 0^2+1=1$, $1\to 2$, $2\to 5=0$, $3\to 10=0$ and $4\to 17=2$. If we iterate the map we get sequences, such as $0\to 1\to 2\to 0\to 1\ldots$ and $4\to 2\to 0\to 1\to 2\to 0\ldots$. Clearly any such sequence must eventually repeat and enter a cycle. The process produces a directed graph, with vertices labeled $0,1,\ldots, p-1$.

The questions I am interested in include - How far must one go before entering a cycle? How long are the cycles? And how many distinct cycles are there? For example, for $p=31$, if one starts at 13 there are 6 steps before one gets a repetition; and there are 3 cycles, of lengths 1, 1 and 3.

What I have shown is the following. Firstly, any path repeats after $O(p/\log\log p)$ steps; and secondly the sum of the lengths of all the cycles is $O(p/\log\log p)$. (The notation means that there is a numerical constant $C$, which I've not bothered to compute, so that the number of steps is at most $Cp/\log\log p$.) Of course $\log\log p$ tends to infinity extremely slowly, but the results do show that eventually $p$ is sufficiently large that one always gets a repetition within $p/1000$ steps, for example.

Other people (including Fernando Shao, at the Mathematical Institute here in Oxford) have looked at this and related questions, but mine are the first quantitative results of this type. There is some interesting Galois theory of relevance, but my approach is more geometric.

You can read my paper which will be published in due course in a memorial volume for Klaus Roth, the first British Fields Medalist."