\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\DeclareMathOperator{\Nil}{Nil}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
Iterations of Integer Polynomial \\
\vskip .1in
Maps Modulo Primes
}
\vskip 1cm
\large
Alexander Borisov\footnote{The research of the author was supported in part by the NSA grants H98230-08-1-0129, H98230-06-1-0034 and H98230-11-1-0148.} \\
Department of Mathematics \\
University of Pittsburgh\\
301 Thackeray Hall\\
Pittsburgh, PA 15260\\
USA\\
\href{mailto:borisov@pitt.edu}{\tt borisov@pitt.edu} \\
\end{center}
\vskip .2 in
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\Tr}{\operatorname{Tr}}
\newcommand{\A}{{\rm A}}
\newcommand{\SL}{\hbox{SL}}
\newcommand{\GL}{\hbox{GL}}
\newcommand{\PGL}{\hbox{PGL}}
\newcommand{\Spec}{\operatorname{Spec}}
\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\phi}{\varphi}
\vskip .2 in
\begin{abstract}
In this elementary note we discuss some questions
related to the behavior of iterations of polynomial maps with integer
coefficients modulo primes. In particular, we introduce three examples
of such maps that have interesting dynamical properties. Several open
questions are stated and discussed.
\end{abstract}
\section{Introduction}
Polynomial maps with integer coefficients are among the simplest mathematical objects. If the number of polynomials equals the number of variables, then the map can be iterated. So for any ring \(R\) we get a discrete dynamical system on the set \(R^n,\) where \(n\) is the number of variables (polynomials). In spite of the simplicity of this setup, relatively little is known regarding the dynamical properties of these maps, in particular their periodic points. Generally, one expects that over a global field there are few periodic points. See the paper of Fakhruddin for some results and conjectures in this direction \cite{Fakhruddin}. On the other hand, over an algebraic closure of a finite field there are usually many periodic points. Indeed, if the reduction of the map is dominant, then the periodic points are Zariski dense, by a result of the author and Sapir \cite{BS}. The dynamics over the local fields received considerable attention, in particular by Silverman and his school \cite{CallSilverman, Silverman}. The primary object of investigation in that context is the recurrent points, i.e., the points that lie in the limit set of their iterated images. The one-dimensional case has been especially well studied, in particular by Benedetto \cite{Benedetto}. Independently, interesting results were obtained by Khrennikov and Nilsson \cite{KN}.
Modulo primes, some special cases, most notably monomial maps and quadratic maps in one variable, were studied in great detail. The early works include those of Chass{\'e} \cite{Chasse}, motivated by the Pollard's rho factorization algorithm. More recently, very precise results were obtained by Vasiga and Shallit \cite{VasigaShallit}, Chou and Shparlinski \cite{ChouShparlinski}, and Sha \cite{ Sha}. This list is very incomplete, and you should consult the above mentioned papers, especially the paper of Vasiga and Shallit, for more references.
This short note is devoted to comparison of the dynamical properties of the map at a generic point (i.e., over \(\mathbb Z\)) and its reductions modulo primes \(p\). The author and Sapir \cite{BS2} obtained some very general results of this kind and used them to prove that the mapping tori of free group endomorphisms are virtually residually (finite $p$)-groups for all but finitely many primes \(p\). Importantly, we used the maps over the extensions of of \({\mathbb Z}/{p\mathbb Z}\), and the corresponding extensions of the \(p\)-adic numbers. This note grew from an observation that there exist integer polynomial maps which are dominant over \(\mathbb Z\), but ``nilpotent" modulo all primes (see Example~\ref{1} below).
The paper is organized as follows. In Section 2 we introduce three particular polynomial maps and prove their properties. In Section 3 we discuss some natural open questions.
\section{Examples and Theorems}
The first map is the simplest. We discovered it while working with Mark Sapir \cite{BS}.
\begin{example}\label{1} (Additive Trap) Define \(F_{at}(x,y)=(u,v)\), where
\[(u,v)=(x^2y,x^2y+xy^2) .\]
\end{example}
\begin{theorem}
\begin{itemize}
\item[(a)] \(F_{at}\) and its reductions modulo \(p\) for all primes \(p\) are dominant.
\item[(b)] The only fixed point over the algebraic closure of the ground field of \(F_{at}\), and any reduction of it modulo \(p\), is \((0,0).\)
\item[(c)] For every \((x,y)\in {\mathbb F}_p^2\) some multiple of the reduction of \(F_{at}\) modulo \(p\) sends it to \((0,0).\)
\end{itemize}
\end{theorem}
\begin{proof} (a) We need to show that for a Zariski open subset of pairs \((u,v)\) there exists \((x,y)\) such that \(F(x,y)=(u.v).\) For \(u\neq 0\), \(u\neq v\), take \(x\) such that \(x^3=\frac{u^2}{v-u}\) and take \(y=\frac{u}{x^2}\).
(b) Suppose \(x^2y=x\) and \(x^2y+xy^2=y\). If \(x=0\), then from the second equation \(y=0.\) If \(x\neq 0,\) then from the first equation \(xy=1\). Plugging this into the second equation, we get \(x+y=y,\) so \(x=0.\)
(c) We will prove that modulo any prime \(p\) the \(p\)-th iteration of \(F_{at}\) sends everything to \((0,0)\). Indeed, if \(x\neq 0\), then \(\frac{v}{u}=\frac{y}{x}+1\). So after no more than \(p-1\) iterations, we get \(y=0,\) which forces \(x\) and \(y\) to become zero at the next step and forever afterwards.
\end{proof}
Note that these properties are in sharp contrast with the result of the author and Sapir that implies that periodic orbits of \(F_{at}\) over the algebraic closure of \({\mathbb F}_p\) are Zariski dense \cite{BS}.
\begin{example} (Multiplicative Trap) Suppose \(n\geq 2\) is a natural number. Define \(F_{mt(n)}(x,y)=(u,v)\), where
\[(u,v)=(x^2y(x-y),nxy^2(x-y)) .\]
\end{example}
\begin{theorem}
\begin{itemize}
\item[(a)] \(F_{mt(n)}\) and its reductions modulo \(p\) for all primes \(p \nmid n\) are dominant.
\item[(b)] The only fixed point over the algebraic closure of the ground field of \(F_{mt(n)}\), and its reductions modulo \(p\nmid n-1\), is \((0,0).\) For \(p|n-1\), the fixed points of the reduction of \(F_{mt(n)}\) are \((0,0)\) and such \((x,y)\) that \(xy(x-y)=1.\)
\item[(c)] The following two statements are equivalent:
\begin{enumerate}
\item Either \(p|n\) or \(n\) is a multiplicative generator modulo \(p\).
\item For every \((x,y)\in {\mathbb F}_p^2\), some multiple of the reduction of \(F_{mt(n)}\) modulo \(p\) sends it to \((0,0).\)
\end{enumerate}
\end{itemize}
\end{theorem}
\begin{proof} (a) For generic \(u\) and \(v\), take \(x\) so that \(x^4=\frac{n^2u^3}{v(nu-v)}\) and \(y=\frac{v}{nu}x.\) One can check that \(F_{mt(n)}(x,y)=(u,v).\)
(b) Suppose \(F_{mt(n)}(x,y)=(x,y).\) If \(x=0\), then \(y=0\) and vice versa. If \(x\) and \(y\) are non-zero, then from the first equation we get \(xy(x-y)=1\), after which from the second equation we get \(n=1\). If \(p\nmid n-1\), this is impossible; if \(p|n-1\), it is true, which implies the result.
(c) For \(p|n\) two iterations are enough to send everything to \((0,0)\). Modulo any prime \(p\nmid n\), if \(x\neq 0\) and \(\frac{y}{x}\neq 1\), then \(\frac{u}{v}=n\frac{y}{x}\). If \(n\) is a generator of \(({\mathbb Z}/{p\mathbb Z})^*\), then iterations of this map eventually send everything to \((0,0)\). Otherwise, if \(\frac{y}{x}\) is not a power of \(n\), then no iteration
will send $(x,y)$ to \((0,0)\).
\end{proof}
\begin{example} (Power Trap) Suppose \(n\geq 2\) is a natural number. Define \(F_{pt(n)}(x,y)=(u,v)\), where
\[(u,v)=(x^{n+1}y(x-y),xy^{n+1}(x-y)).\]
\end{example}
\begin{theorem}
\begin{itemize}
\item[(a)] \(F_{pt(n)}\) and its reductions modulo \(p\) for all primes \(p\) are dominant.
\item[(b)] For a prime \(p\) the following two statements are equivalent.
\begin{enumerate}
\item \((p-1)|n^k\) for some \(k\).
\item For every \((x,y)\in {\mathbb F}_p^2\), some multiple of the reduction of \(F_{pt(n)}\) modulo \(p\) sends it to \((0,0).\)
\end{enumerate}
\end{itemize}
\end{theorem}
\begin{proof} (a) For generic \(u\) and \(v\), take \(t\) such that \(t^n=\frac{v}{u}\). Then take \(x\) such that \(x^{n+3}=\frac{u}{t-t^2}\) and \(y=tx\). One can check that \(F_{pt(n)}(x,y)=(u,v).\)
(b) Modulo any prime \(p\) if \(x\neq 0\) and \(\frac{y}{x}\neq 1\), then \(\frac{u}{v}=(\frac{y}{x})^n\). If \((p-1)|n^k\) for some \(k,\) then \(k+1\) iterations of this map send everything to \((0,0)\). For general \(p\) a high enough iteration of \(F_{pt(n)}\) sends to \((0,0)\) all pairs \((x,y)\) such that at least one of the coordinates is zero or the order of \(\frac{y}{x}\) in \(({\mathbb Z}/{p\mathbb Z})^*\) divides \(n^k\) for some \(k\).
\end{proof}
These examples inspire the following definition.
\begin{definition} Suppose \(F\) is an integer polynomial map. Then its {\it nilpotency locus} \( \Nil(F)\) is the set of all primes \(p\) such that some iteration of \(F\) is constant on \({\mathbb Z}/p{\mathbb Z}\). We denote by \(\mathcal {NIL}\) the set of all subsets of the set of primes that can be realized as a nilpotency locus for some integer polynomial map \(F\).
\end{definition}
\begin{theorem} Suppose \(S_1\in \mathcal {NIL}\) and \( S_2\in \mathcal {NIL}\). Then \(S_1\cap S_2 \in \mathcal {NIL}.\)
\end{theorem}
\begin{proof} Suppose \(S_1=\Nil(F_1)\) and \(S_2=\Nil(F_2),\) where \(F_1\) has \(n\) variables and \(F_2\) has \(m\) variables. Consider the direct sum of \(F_1\) and \(F_2\), which is the polynomial map on \((n+m)\) variables defined as follows:
\[(F_1\oplus F_2) (x_1,...,x_n;x_{n+1},...,x_{n+m})=(F_1(x_1,...,x_n);F_2(x_{n+1},...,x_{n+m}))\]
Clearly, \(\Nil(F_1 \oplus F_2) =S_1 \cap S_2.\)
\end{proof}
The definition of the nilpotency locus admits an interesting variation.
\begin{definition} Suppose \(F\) is an integer polynomial map. Then its {\it zero nilpotency locus} \( \Nil_0(F)\) is the set of all primes \(p\) such that some iteration of \(F\) is the constant \(0\) on \({\mathbb Z}/p{\mathbb Z}\). We denote by \(\mathcal {NIL}_0\) the set of all subsets of the set of primes that can be realized as a nilpotency locus for some integer polynomial map \(F\).
\end{definition}
It is unclear if \(\mathcal {NIL}_0=\mathcal{NIL}\). In fact, it is possible that neither \(\mathcal {NIL}_0\subseteq \mathcal{NIL}\) nor \(\mathcal {NIL} \subseteq \mathcal{NIL}_0\). A construction similar to the theorem above shows that \(\mathcal{NIL}_0\) is also closed under finite intersections.
\section{Open Questions and Conjectures}
Obviously, with more variables one can create more complicated maps. However, it is unclear how much can be actually ``programmed" using integer polynomial maps. The following question is very natural in this regard.
\begin{question}
Does there exist an integer polynomial map with two different fixed points such that modulo every prime its sufficiently high iteration will send any initial point to one of the fixed points, depending on whether or not the initial first coordinate is zero?
\end{question}
Another interesting question is related to the notion of the nilpotency locus.
\begin{question}
Which subsets of the set of all primes can be realized as a nilpotency locus of some \(F\)?
\end{question}
Note that the nilpotency locus of \(F_{mt(n)}\) is the set of all primes \(p\) for which \(n\) is a generator modulo \(p\), which is a very tricky arithmetic condition. The nilpotency locus of \(F_{pt(2)}\) is the set of the Fermat primes, so we don't even know if it is finite or infinite. Definitely, not all subsets of the set of all primes are in \(\mathcal{NIL}\), because there are uncountably many of them and only countably many integer polynomial maps.
It would also be very interesting to study ``random" polynomial maps, and their dynamical properties on the finite sets of points over \(\mathbb F_p\). The following quantities are of particular interest: the size of the intersection of the images of all iterations, the length of the longest cycle, the length of the shortest cycle, the number of cycles, and the distribution of lengths of the cycles. At this time, it is absolutely unclear what to expect in general, so one should do some computer experiments to formulate any conjectures in this direction. Some results of this kind are contained in a very recent paper by Benedetto, Ghioca, Hutz, Kurlberg, Scanlon, and Tucker \cite{BGHKST}.
\section{Acknowledgments}
We thank Mark Sapir for helpful suggestions and encouragement. We thank Jeffrey Shallit for many references and comments that greatly improved the paper.
\begin{thebibliography}{99}
\bibitem{Benedetto} R. L. Benedetto, Components and periodic points in
non-Archimedean dynamics, {\it Proc. London Math. Soc. (3)} {\bf 84}
(2002), 231--256.
\bibitem{BGHKST} R. L. Benedetto, D. Ghioca, B. Hutz, P. Kurlberg, T.
Scanlon, and T. J. Tucker, Periods of rational maps modulo primes, {\it
Math. Ann.} {\bf 355} (2013), 637--660.
\bibitem{BS} A. Borisov and M. Sapir, Polynomial maps over finite
fields and residual finiteness of mapping tori of group endomorphisms,
{\it Invent. Math.} {\bf 160} (2005), 341--356.
\bibitem{BS2} A. Borisov and M. Sapir, Polynomial maps over $p$-adics
and residual properties of mapping tori of group endomorphisms, {\it
Int. Math. Res. Notices}, (2009), 3002--3015.
\bibitem{CallSilverman} G. Call and J. Silverman, Canonical heights on
varieties with morphisms, {\it Compositio Math.} {\bf 89} (1993), 163--205.
\bibitem{Chasse} G. Chass{\'e}, Combinatorial cycles of a polynomial
map over a commutative field, {\it Discrete Math.} {\bf 61} (1986),
21--26.
\bibitem{ChouShparlinski} W.-S. Chou and I. Shparlinski, On the cycle
structure of repeated exponentiation modulo a prime, {\it J. Number
Theory} {\bf 107} (2004), 345--356.
\bibitem{Fakhruddin} N. Fakhruddin, Questions on self maps of
algebraic varieties, {\it J. Ramanujan Math. Soc.} {\bf 18} (2003),
109--122.
\bibitem{KN} A. Khrennikov and M. Nilsson, On the number of cycles of
\(p\)-adic dynamical systems, {\it J. Number Theory} {\bf 90} (2001),
255--264.
\bibitem{Sha} M. Sha, On the cycle structure of repeated
exponentiation modulo a prime power, {\it Fibonacci Quart.} {\bf 49}
(2011), 340--347.
\bibitem{Silverman} J. Silverman, {\it The Arithmetic of Dynamical Systems},
Graduate Texts in Mathematics, vol.~241, Springer, 2007.
\bibitem{VasigaShallit} T. Vasiga and J. Shallit, On the iteration of
certain quadratic maps over GF($p$). {\it Discrete Math.} {\bf
277} (2004), 219--240.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 37P05; Secondary 37P25, 37P35, 11A07.
\noindent \emph{Keywords: }
polynomial map, reduction, iteration.
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received May 4 2013;
revised version received August 4 2013; September 1 2013.
Published in {\it Journal of Integer Sequences}, October 12 2013.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}