Iterations of quadratic polynomials over finite fields

DOI10.2140/INVOLVE.2013.6.99MaRDI QIDQ365960zbMATH OpenOpenAlexFDO

Authors William Worden

Publication date 10 September 2013

Published in Involve (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.4528

zbMATH Keywords

arithmetic dynamicsbirthday problemforward orbit modulo \(p\)random maps

Mathematics Subject Classification ID

Recurrences (11B37) Arithmetic and non-Archimedean dynamical systems involving polynomial and rational maps (37P05)

Abstract: Given a map f:Z-->Z and an initial argument alpha, we can iterate the map to get a finite set of iterates modulo a prime p. In particular, for a quadratic map f(z)=z^2 +c, c constant, work by Pollard suggests that this set should have length on the order of p^(1/2). We give a heuristic argument that suggests that the statistical properties of this set might be very similar to the Birthday Problem random variable X_n, for an n=p day year, and offer considerable experimental evidence that the limiting distribution of these set lengths, divided by p^(1/2), for pleq x as x goes to infinity, converges to the limiting distribution of X_n/n^(1/2), as n goes to infinity.

Review text

Polynomial maps over finite fields are believed to behave like random maps, even though there are very few rigorous results in this direction. The normalised length of an orbit of a random map obeys a limiting smooth distribution function. The author computes the length of the forward orbit of a quadratic polynomial \(f(z)=z^2+c\) over the field of \(p\) elements, for fixed parameter \(c\) and fixed integer initial condition \(\alpha\).NEWLINENEWLINEThe data collected from approximately two million primes provide convincing evidence that the normalised length of polynomial orbits is asymptotically (large \(p\)) distributed according to the aforementioned distribution. A related problem -- the density of the set of primes for which the orbit through \(\alpha\) passes through the origin -- is also considered and analysed using similar methods. These findings lead to the formulation of two conjectures.

Recommendations

• Iteration of quadratic polynomials over finite fields
• A refined conjecture for factorizations of iterates of quadratic polynomials over finite fields
• Settled polynomials over finite fields
• On the length of critical orbits of stable quadratic polynomials
• A survey on iterations of mappings over finite fields

Cited in

(11)

• Iteration of polynomials \(AX^d + C\) over finite fields
• Irreducibility of iterates of post-critically finite quadratic polynomials over \(\mathbb{Q}\)
• A refined conjecture for factorizations of iterates of quadratic polynomials over finite fields
• Expansions of quadratic maps in prime fields
• Settled polynomials over finite fields
• scientific article; zbMATH DE number 5003329 (Why is no real title available?)
• On the length of critical orbits of stable quadratic polynomials
• On Repeated Squarings in Binary Fields
• scientific article; zbMATH DE number 4027619 (Why is no real title available?)
• Irreducibility of the iterates of a quadratic polynomial over a field
• Iteration of quadratic polynomials over finite fields

This page was built for publication: Iterations of quadratic polynomials over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q365960)