# Polynomials with many rational preperiodic points

John R. Doyle  Dept. of Mathematics
Oklahoma State University
Stillwater, OK 74078<EMAIL_ADDRESS>and  Trevor Hyde  Dept. of
Mathematics
University of Chicago
Chicago, IL 60637<EMAIL_ADDRESS>
###### Abstract.

In this paper we study two questions related to exceptional behavior of
preperiodic points of polynomials in $\mathbb{Q}[x]$. We show that for all
sufficiently large integers $d$, there exists a polynomial
$f_{d}(x)\in\mathbb{Q}[x]$ with $2\leq\deg(f_{d})\leq d$ such that $f_{d}(x)$
has at least $d+\lfloor\log_{16}(d)\rfloor$ rational preperiodic points.
Furthermore, we show that for infinitely many $d\geq 2$, the polynomials
$f_{d}(x)$ and $f_{d}(x)+1$ have at least
$d^{2}+d\lfloor\log_{16}(d)\rfloor-2d+1$ common complex preperiodic points. To
prove the existence of such polynomials we introduce the technique of
dynamical compression.

##  1\. Introduction

The following two questions arise naturally in arithmetic and complex
dynamics:

######  Question 1.1.

How many rational preperiodic points can a degree-$d$ polynomial
$f(x)\in\mathbb{Q}[x]$ have?

######  Question 1.2.

How many complex preperiodic points can degree-$d$ polynomials
$f(x),g(x)\in\mathbb{C}[x]$ have in common?

Both questions are conjectured to have answers in the form of uniform upper
bounds depending only on $d$ (subject to some minor caveats described below).
In this paper, we consider lower bounds for these two conjectural uniform
upper bounds. That is, we prove the existence of degree-$d$ polynomials
$f(x)\in\mathbb{Q}[x]$ with a large number of rational preperiodic points
relative to $d$, and then use these polynomials to construct pairs of
polynomials $f(x)$ and $g(x)$ with many common complex preperiodic points.

###  1.1. Results

Let $K$ be a field and let $f(x)\in K[x]$ be a polynomial. We write $f^{n}(x)$
to denote the $n$-fold composition of $f$ with itself. A point
$\alpha\in\overline{K}$ is _preperiodic_ under $f(x)$ if $\alpha$ has a finite
forward orbit $\\{f^{n}(\alpha):n\geq 0\\}$ under $f$. Let
$\mathrm{PrePer}(f,K)$ denote the set of $K$-rational preperiodic points of
$f$,

$\mathrm{PrePer}(f,K):=\\{\alpha\in K:\alpha\text{ is preperiodic under
}f\\}.$

Now let $K$ be a number field. Northcott [15] proved that
$\mathrm{PrePer}(f,K)$ is finite when $\deg(f)\geq 2$. Given an integer $d\geq
2$, let

$B_{d}(K):=\sup_{f}|\mathrm{PrePer}(f,K)|\in[0,\infty],$

where the supremum is taken over all polynomials $f(x)\in K[x]$ with
$2\leq\deg(f)\leq d$. The Morton-Silverman Uniform Boundedness Conjecture [14]
asserts, in part, that $B_{d}(K)<\infty$ for any number field $K$. This
conjecture has motivated a substantial volume of work in arithmetic dynamics
(see Silverman [17, Sec. 3.3]). While it is widely believed to be true, it has
yet to be proved unconditionally in any degree. Looper [11] recently gave a
conditional proof that $B_{d}(K)<\infty$, assuming a generalization of the
$abc$ conjecture.

Our first main result establishes lower bounds for $B_{d}(\mathbb{Q})$. Note
that Lagrange interpolation gives the trivial lower bound of
$B_{d}(\mathbb{Q})\geq d+1$.

######  Theorem 1.3.

For all sufficiently large integers $d\geq 2$,

$B_{d}(\mathbb{Q})\geq d+\lfloor\log_{16}(d)\rfloor.$

One may compare Theorem 1.3 to known lower bounds on
$A_{g}(\mathbb{Q}):=\sup_{X}|X(\mathbb{Q})|$, where $X$ ranges over all smooth
irreducible genus-$g$ curves defined over $\mathbb{Q}$. In this setting, the
best known lower bound for $A_{g}(\mathbb{Q})$ that holds for all $g\geq 2$ is
linear in $g$ (see [5]), though it is unknown whether the correct upper bound
should also be linear. In that spirit, we pose the following question:

######  Question 1.4.

What is the order of growth of $B_{d}(\mathbb{Q})$ as $d\to\infty$? Is it true
that $B_{d}(\mathbb{Q})=d+O(\log d)$?

If $m\in\mathbb{Z}$ is a positive integer, let $[m]:=\\{1,2,3,\ldots,m\\}$. We
say a degree-$d$ polynomial $g(x)\in\mathbb{C}[x]$ exhibits _dynamical
compression_ if $g(x)$ is conjugate to some polynomial $f(x)$—that is,
$f=\ell\circ g\circ\ell^{-1}$ for some degree-$1$ polynomial
$\ell(x)\in\mathbb{C}[x]$—which satisfies

$f([m])\subseteq[n]$

for some $m\geq n>d+1$. In this case,
$[m]\subseteq\mathrm{PrePer}(f(x),\mathbb{Q})$ and Newton interpolation [4,
Sec. I.1] implies that $f(x)\in\mathbb{Q}[x]$ is an integer-valued polynomial.
Recall that a polynomial $f(x)\in\mathbb{Q}[x]$ is _integer-valued_ if
$f(\mathbb{Z})\subseteq\mathbb{Z}$. The polynomials we construct that achieve
the lower bounds in Theorem 1.3 all exhibit dynamical compression.

######  Example 1.5.

Let $f(x):=\frac{x^{2}-9x+22}{2}$. One may check that

$f([8])\subseteq[7].$ (1.1)

Therefore, both $f(x)$ and $f(x)+1$ exhibit dynamical compression and have at
least 8 rational preperiodic points, namely the elements of $[8]$. In fact, it
may be shown that $f(x)$ and $f(x)+1$ have exactly 8 rational preperiodic
points. Hence $B_{2}(\mathbb{Q})\geq 8$. Poonen [16] has conjectured that
$B_{2}(\mathbb{Q})=8$. The polynomials $f(x)$ and $f(x)+1$ are simultaneously
conjugate to $x^{2}-\frac{29}{16}$ and $x^{2}-\frac{21}{16}$, respectively.
These quadratic polynomials appear several times in the literature for their
exceptional properties, including DeMarco, Krieger, and Ye [7], Doyle, Faber
and Krumm [8], Hindes [10], Morton and Raianu [13], and Poonen [16].

######  Example 1.6.

The cubic polynomial $f(x):=\frac{x^{3}-18x^{2}+89x-66}{6}$ satisfies

$f([11])\subseteq[11].$

Thus both $f(x)$ and $12-f(x)$ exhibit dynamical compression and have at least
11 rational preperiodic points. These examples share the current record with 8
other cubics, found by computational search in Benedetto et al. [3, Table 2],
for the cubic polynomial with the most rational preperiodic points. Of the 10
record holding cubics found by Benedetto et al., only the two conjugate to
$f(x)$ and $12-f(x)$ exhibit dynamical compression.

Dynamical compression also has applications to constructing polynomials with
many common complex preperiodic points. Given an integer $d\geq 2$, let

$C_{d}:=\sup_{f,g}|\mathrm{PrePer}(f,\mathbb{C})\cap\mathrm{PrePer}(g,\mathbb{C})|,$

where the supremum is taken over all $f(x),g(x)\in\mathbb{C}[x]$ with
$2\leq\deg(f),\deg(g)\leq d$ such that
$\mathrm{PrePer}(f,\mathbb{C})\neq\mathrm{PrePer}(g,\mathbb{C})$. DeMarco,
Krieger, and Ye [7, Conj. 1.4] conjecture that $C_{d}<\infty$ for all $d\geq
2$; they prove this conjecture when $f$ and $g$ are restricted to the family
of quadratic polynomials of the form $x^{2}+c$ [7, Thm. 1.1]. This result was
recently strengthened to other 1-parameter families in
$\mathrm{Rat}_{d}\times\mathrm{Rat}_{d}$ by Mavraki and Schmidt [12].

Our second main result establishes a lower bound on $C_{d}$.

######  Theorem 1.7.

Let $d\geq 2$, and let $2\leq\ell\leq k:=\lfloor\log_{16}(d)\rfloor$. For all
sufficiently large $d$, there exists a polynomial $f(x)\in\mathbb{Q}[x]$ with
$2\leq\deg(f)\leq d$ such that

$\deg(f)(d+\ell-1)+1\leq\left|\bigcap_{i=0}^{k-\ell}\mathrm{PrePer}(f(x)+i,\mathbb{C})\right|<\infty.$

Furthermore, there are infinitely many $d\geq 2$ such that

$C_{d}\geq d^{2}+d\lfloor\log_{16}(d)\rfloor-2d+1.$ (1.2)

In Section 5 we provide a table of explicit lower bounds on $C_{d}$ for $2\leq
d\leq 15$.

######  Remark.

The uniform boundedness conjectures stated above are actually believed to hold
more generally for rational functions on $\mathbb{P}^{1}$. However, the
methods of this paper appear to be constrained to polynomials, so we only
consider this case. Note that if $B_{d}^{\prime}(K)$ and $C_{d}^{\prime}$ are
the corresponding conjectured uniform upper bounds for rational functions,
then we have $B_{d}(K)<B_{d}^{\prime}(K)$ and $C_{d}^{\prime}<C_{d}$ for all
$d\geq 2$ and all number fields $K$. This inequality follows from the simple
observation that every polynomial is a rational function, plus the fact that
we are not counting $\infty$ as a preperiodic point, though it is a fixed
point for every polynomial map.

######  Remark.

Fu and Stoll [9] recently proved a result analogous to (1.2) giving lower
bounds on the maximal number of common torsion $x$-coordinates for pairs of
elliptic curves $E_{1},E_{2}$ such that $x(E_{1,\mathrm{tors}})\neq
x(E_{2,\mathrm{tors}})$. Their results have the following dynamical
interpretation: If $f_{i}(x)$ denotes the degree-4 flexible Lattès map
associated to multiplication by $2$ on the elliptic curve $E_{i}$, then
$x(E_{i,\mathrm{tors}})=\mathrm{PrePer}(f_{i}(x),\mathbb{C})$. Hence [9, Thm.
2] implies that there are infinitely many pairs of elliptic curves $E_{1}$,
$E_{2}$ for which

$22\leq|\mathrm{PrePer}(f_{1}(x),\mathbb{C})\cap\mathrm{PrePer}(f_{2}(x),\mathbb{C}))|<\infty,$

and [9, Thm. 3] implies that there exists an explicit pair of elliptic curves
$E_{1}$, $E_{2}$ such that

$|\mathrm{PrePer}(f_{1}(x),\mathbb{C})\cap\mathrm{PrePer}(f_{2}(x),\mathbb{C}))|=34.$
(1.3)

Using the notation of the previous remark, (1.3) implies that
$C_{4}^{\prime}\geq 34$. On the other hand, in Section 5 we provide an example
that shows $C_{4}\geq 36$, hence that $C_{4}^{\prime}\geq 37$.

The first part of Theorem 1.7 follows from Theorem 1.3 and the following
proposition.

######  Proposition 1.8.

Suppose that $f(x)\in\mathbb{C}[x]$ is a degree $d\geq 2$ polynomial such that

$f([m])\subseteq[n],$

for some integers $m>n\geq 1$. Then

$d(n-1)+1\leq\left|\bigcap_{i=0}^{m-n}\mathrm{PrePer}(f(x)+i,\mathbb{C})\right|<\infty.$

######  Example 1.9.

Returning to Example 1.5, let $f(x):=\frac{x^{2}-9x+22}{2}$. Then (1.1) and
Proposition 1.8 imply that

$|\mathrm{PrePer}(f(x),\mathbb{C})\cap\mathrm{PrePer}(f(x)+1,\mathbb{C})|\geq
13.$

However, by comparing the preperiodic points with small forward orbit for
$f(x)$ and $f(x)+1$ directly we find that
$\mathrm{PrePer}(f(x),\mathbb{C})\cap\mathrm{PrePer}(f(x)+1,\mathbb{C})$
actually contains at least 26 points. Hence $C_{2}\geq 26$. To the best of our
knowledge, this is the current record for a lower bound on $C_{2}$.

The proofs of Theorems 1.3 and 1.7 do not produce explicit examples. Thus it
remains an interesting problem to construct explicit polynomials which surpass
the trivial lower bounds on $B_{d}(\mathbb{Q})$ and $C_{d}$. Our last result
provides one such family $r_{d}(x)$. Formulas for $r_{d}(x)$ are given in
Section 4.

######  Theorem 1.10.

For all $d\geq 2$, there is an explicit degree-$d$, integer-valued polynomial
$r_{d}(x)$ such that if $d$ is even, then

$r_{d}([d+6])\subseteq[d+5],$

and if $d$ is odd, then

$r_{d}([d+6])\subseteq[d+4].$

Furthermore, $r_{d}(x)$ gives us

  1. (1)

$B_{d}(\mathbb{Q})\geq d+6$ for all $d\geq 2$, and

  2. (2)

$C_{d}\geq d^{2}+4d+1$ for all $d\geq 2$.

###  1.2. Outline

Theorem 1.3 is proved in Section 2. We show that polynomials exhibiting
dynamical compression for prescribed intervals correspond to integer lattice
points within certain convex regions depending on the lengths of those
intervals. Minkowski’s theorem from the geometry of numbers allows us to use
asymptotic lower bounds on the volumes of these regions to prove the existence
of the desired lattice points within them. Section 3 contains the proofs of
Proposition 1.8 and Theorem 1.7. In Section 4 we construct the family of
polynomials $r_{d}(x)$ and prove Theorem 1.10. We end the paper with some low-
degree records for $B_{d}(\mathbb{Q})$ and $C_{d}$ found by a computational
survey in Section 5.

###  1.3. Acknowledgements

We thank Laura DeMarco for a helpful correspondence which prompted this work
and the University of Chicago Research Computing Center for access to their
computational resources. We thank Hang Fu for pointing out that (1.3) follows
from [9, Thm. 3]. We also thank Joseph Silverman for several helpful comments
on an earlier draft, as well as for suggesting that we include the discussion
and question immediately following Theorem 1.3. John Doyle was partially
supported by NSF grant DMS-2112697. Trevor Hyde was partially supported by the
NSF Postdoctoral Research Fellowship DMS-2002176 and the Jump Trading Mathlab
Research Fund.

##  2\. Rational Preperiodic Points

The goal of this section is to prove Theorem 1.3, which is stated in a refined
form below as Theorem 2.5. Our strategy is to first construct a bijection
between polynomials exhibiting dynamical compression for exceptionally large
intervals and lattice points in a certain convex region of Euclidean space
(Lemma 2.2), and then use a geometry of numbers argument to reduce the
existence of such lattice points to volume estimates.

###  2.1. Matrix norms

Let $L:\mathbb{R}^{d}\rightarrow\mathbb{R}^{k}$ be a linear transformation and
suppose that $\mathbb{R}^{d}$ and $\mathbb{R}^{k}$ are endowed with the
standard Euclidean norms. The _spectral norm_ of $L$ is defined by

$||L||:=\sup\\{||L(v)||/||v||:v\in\mathbb{R}^{d}\text{ is non-zero}\\}.$

If $\sigma_{1}\geq\sigma_{2}\geq\cdots\geq\sigma_{k}$ are the singular values
of $L$, then $||L||=\sigma_{1}$. Let $(a_{i,j})$ be the matrix representation
of $L$ with respect to some basis. The _Frobenius norm_ of $L$ is

$||L||_{F}:=\Big{(}\sum_{i,j}|a_{i,j}|^{2}\Big{)}^{1/2}.$

The _max norm_ of $L$ is

$||L||_{\max}:=\max_{i,j}|a_{i,j}|.$

If $L_{1}:\mathbb{R}^{m}\rightarrow\mathbb{R}^{k}$ and
$L_{2}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{m}$, then the Frobenius norm is
submultiplicative,

$||L_{1}L_{2}||_{F}\leq||L_{1}||_{F}||L_{2}||_{F},$

and the max norm satisfies the weaker inequality

$||L_{1}L_{2}||_{\max}\leq m||L_{1}||_{\max}||L_{2}||_{\max}.$ (2.1)

Note that the Frobenius norm and the max norm both depend on a choice of
basis. Whenever we consider $||L||_{\max}$ or $||L||_{F}$ the corresponding
bases will be made explicit.

The following inequalities will be used several times in subsequent sections:

$||L||\leq||L||_{F}\leq\sqrt{mn}||L||_{\max}.$ (2.2)

###  2.2. Constructing $L_{d,k}$

Next we construct a linear transformation $L_{d,k}$ which interpolates a
polynomial based on several initial values and returns the evaluation at
subsequent values.

######  Lemma 2.1.

Let $d,k\geq 2$ be integers. There exists a linear map
$L_{d,k}:\mathbb{R}^{d+1}\rightarrow\mathbb{R}^{k-1}$ and, for each
$v\in\mathbb{R}^{d+1}$, there exists a polynomial $g_{v}(x)\in\mathbb{R}[x]$
of degree at most $d$ such that

  1. (1)

$v=(g_{v}(0),g_{v}(1),\ldots,g_{v}(d))$ and
$L_{d,k}(v)=(g_{v}(d+1),\ldots,g_{v}(d+k-1))$,

  2. (2)

if $v\in\mathbb{Z}^{d+1}$, then $g_{v}(x)$ is integer-valued, and

  3. (3)

for each $\beta>0$, there exists a constant $\beta^{\prime}>0$ depending only
on $\beta$ (in particular, not on $d$ or $k$) such that if
$k\leq\beta\log(d)$, then

$\log||L_{d,k}||_{F}\leq\log(4)d+\beta^{\prime}\log(d).$

###### Proof.

(1) Let $\mathrm{Poly}_{d}$ denote the real vector space of degree-at-most-$d$
polynomials in $\mathbb{R}[x]$. Given $v\in\mathbb{R}^{d+1}$, Lagrange
interpolation implies that there exists a unique degree-at-most-$d$ polynomial
$g_{v}(x)\in\mathrm{Poly}_{d}$ such that
$v=(g_{v}(0),g_{v}(1),\ldots,g_{v}(d))$. An explicit formula for $g_{v}(x)$ is
given by

$g_{v}(x):=\sum_{i=0}^{d}\Delta^{i}g_{v}(0)\binom{x}{i},$

where $\Delta g(x):=g(x+1)-g(x)$. If $\sigma$ is the forward shift operator
$\sigma g(x):=g(x+1)$, then $\Delta=\sigma-1$ and

$\Delta^{i}g_{v}(0)=(\sigma-1)^{i}g_{v}(0)=\sum_{j=0}^{i}\binom{i}{j}(-1)^{i-j}(\sigma^{j}g_{v})(0)=\sum_{j=0}^{i}\binom{i}{j}(-1)^{i-j}g_{v}(j).$
(2.3)

Hence $B_{d}:\mathbb{R}^{d+1}\rightarrow\mathrm{Poly}_{d}$ defined by
$B_{d}(v):=g_{v}(x)$ is a linear map. Let
$A_{d,k}:\mathrm{Poly}_{d}\rightarrow\mathbb{R}^{k-1}$ be the linear map
defined by

$A_{d,k}(g(x)):=(g(d+1),g(d+2),\ldots,g(d+k-1)).$

Then we define $L_{d,k}:\mathbb{R}^{d+1}\rightarrow\mathbb{R}^{k-1}$ by
$L_{d,k}:=A_{d,k}\circ B_{d}$. Therefore, by construction,

$L_{d,k}(v)=(g_{v}(d+1),g_{v}(d+2),\ldots,g_{v}(d+k-1)).$

(2) The polynomials $\binom{x}{n}$ are integer-valued. If
$v\in\mathbb{Z}^{d+1}$, then (2.3) implies that
$\Delta^{i}g_{v}(0)\in\mathbb{Z}$, hence $g_{v}(x)$ is an integer-valued
polynomial.

(3) Now fix $\beta>0$ and suppose that $k\leq\beta\log(d)$. Since the
Frobenius norm is submultiplicative,

$\log||L_{d,k}||_{F}\leq\log||A_{d,k}||_{F}+\log||B_{d}||_{F}.$

With respect to the basis of polynomials $\binom{x}{n}$ with $0\leq n\leq d$,
the matrix entries of $A_{d,k}$ have absolute value $\binom{m}{n}$ with
$d+1\leq m\leq d+k-1$ and $0\leq n\leq d$. Therefore by (2.2),

$\log||A_{d,k}||_{F}\leq\log\Big{(}\sqrt{(d+1)(k-1)}\binom{d+k-1}{\lfloor(d+k-1)/2\rfloor}\Big{)}\leq\log\binom{d+k-1}{\lfloor(d+k-1)/2\rfloor}+\beta_{1}\log(d),$

for some positive constant $\beta_{1}$ depending only on $\beta$.

Similarly, (2.3) implies that the matrix entries of $B_{d}$ have absolute
value $\binom{m}{n}$ with $0\leq n\leq m\leq d$. Hence

$\log||B_{d}||_{F}\leq\log\Big{(}(d+1)\binom{d}{\lfloor
d/2\rfloor}\Big{)}\leq\log\binom{d}{\lfloor d/2\rfloor}+\beta_{2}\log(d)$

for some absolute positive constant $\beta_{2}$. Note that $\binom{m}{n}\leq
2^{m}$ for all $m,n\geq 0$. Therefore, by the submultiplicativity of the
Frobenius norm, there is some positive constant $\beta^{\prime}$ depending
only on $\beta$ such that

$\displaystyle\log||L_{d,k}||_{F}$
$\displaystyle\leq\log||A_{d,k}||_{F}+\log||B_{d}||_{F}$
$\displaystyle\leq\log(2)(d+k-1)+\log(2)d+(\beta_{1}+\beta_{2})\log(d)$
$\displaystyle\leq\log(4)d+\beta^{\prime}\log(d).\qed$

###  2.3. Reduction to lattice points in an ellipsoid

Let $d,k,\ell\geq 2$ be integers, let $\sigma_{i}\geq 0$ with $0\leq i\leq d$
be the singular values of $L_{d,k}$, and let $0\leq n\leq d$ be such that
$\sigma_{i}>0$ if and only if $0\leq i\leq n$. The existence of singular value
decompositions implies there is an orthonormal basis
$u_{0},u_{1},\ldots,u_{d}$ of $\mathbb{R}^{d+1}$ such that
$||L_{d,k}(u_{i})||=\sigma_{i}$. For $m\geq 1$ an integer and $r>0$ a real
number, let $\bar{B}^{m}(r)\subseteq\mathbb{R}^{m}$ denote the closed ball of
radius $r$ centered at the origin. The pre-image
$L_{d,k}^{-1}(\bar{B}^{k-1}((d+\ell-1)/2))\subseteq\mathbb{R}^{d+1}$ factors
in the $u$-basis as $\widetilde{E}\times\mathbb{R}^{d-n}$, where
$\widetilde{E}$ is a solid ellipsoid with elliptic radii
$\frac{d+\ell-1}{2\sigma_{i}}$ for $0\leq i\leq n$.

Finally, we denote by $E_{d,k,\ell}\subseteq\mathbb{R}^{d+1}$ the solid
ellipsoid with axes $u_{0},u_{1},\ldots,u_{d}$ and respective elliptic radii
$\frac{d+\ell-1}{2\max(\sigma_{i},1)}$ for $0\leq i\leq d$.

######  Lemma 2.2.

Let $d\geq 2$ and $2\leq\ell\leq k$ be integers, and let
$g_{v}(x)\in\mathrm{Poly}_{d}$ be the degree-at-most-$d$ polynomial
constructed in Lemma 2.1 associated to $v\in\mathbb{R}^{d+1}$. If
$v\in\mathbb{Z}^{d+1}$ is a lattice point contained in $E_{d,k,\ell}$, then
$f_{v}(x):=g_{v}(x-1)+\lfloor(d+\ell-1)/2\rfloor+1\in\mathbb{Q}[x]$ is a
degree-at-most-$d$, integer-valued polynomial such that

$f_{v}([d+k])\subseteq[d+\ell].$

In particular, $f_{v}(x)$ has at least $d+k$ rational preperiodic points.

###### Proof.

If $v\in\mathbb{Z}^{d+1}$, then Lemma 2.1 implies that $g_{v}(x)$ has degree
at most $d$ and is integer-valued, thus the same holds for $f_{v}(x)$. By
construction we have $E_{d,k,\ell}\subseteq\bar{B}^{d+1}((d+\ell-1)/2)$ and
$L_{d,k}(E_{d,k,\ell})\subseteq\bar{B}^{k-1}((d+\ell-1)/2)$. Hence if
$v=(v_{0},v_{1},\ldots,v_{d})$ and $L_{d,k}(v)=(v_{d+1},\ldots,v_{d+k-1})$,
then $v\in E_{d,k,\ell}$ implies that

$|v_{i}|\leq(d+\ell-1)/2$

for all $0\leq i\leq d+k-1$. Note that for all $v\in\mathbb{Z}^{d+1}$ and all
$0\leq i\leq d+k-1$, we have $g_{v}(i)=v_{i}$; thus, for $v\in E_{d,k,\ell}$
and $0\leq i\leq d+k-1$ we have
$f_{v}(i+1)=v_{i}+\lfloor(d+\ell-1)/2\rfloor+1\in\mathbb{Z}$ and

$1\leq v_{i}+\lfloor(d+\ell-1)/2\rfloor+1\leq d+\ell.$

Therefore $f_{v}([d+k])\subseteq[d+\ell]$. ∎

In Lemma 2.3 we establish lower bounds on the growth rate of the volume of
$E_{d,k,\ell}$.

######  Lemma 2.3.

Let $d,\ell\geq 2$ be integers, and assume that $2\leq\ell\leq
k:=\lfloor\log_{16}(d)\rfloor$. Let $E_{d,k,\ell}$ be the ellipsoid
constructed immediately preceding Lemma 2.2. Then there is a constant $\gamma$
such that for all sufficiently large $d$,

$\log\mathrm{Vol}(E_{d,k,\ell})\geq\log\Big{(}\frac{\sqrt{2\pi
e}}{2}\Big{)}d+\gamma\log(d)^{2}.$

###### Proof.

The volume of an ellipsoid $E$ with elliptic radii $r_{0},r_{1},\ldots,r_{d}$
is

$\mathrm{Vol}(E)=\frac{\sqrt{\pi}^{d+1}}{\Gamma(\frac{d+1}{2}+1)}r_{0}r_{1}\cdots
r_{d},$

where $\Gamma(x)$ is the standard Gamma function. Therefore, by construction,

$\mathrm{Vol}(E_{d,k,\ell})\geq\frac{(\sqrt{\pi}d/2)^{d+1}}{\Gamma(\frac{d+1}{2}+1)\prod_{i=0}^{n}\max(\sigma_{i},1)},$

where $\sigma_{i}$ for $0\leq i\leq n$ are the non-zero singular values of
$L_{d,k}$. Note that $n<k$. Since $L_{d,k}$ is defined over $\mathbb{Z}$,
$\max(\sigma_{i},1)\leq||L_{d,k}||_{F}$. Thus

$\log\mathrm{Vol}(E_{d,k,\ell})\geq(d+1)\log(d)+\log(\sqrt{\pi}/2)(d+1)-\log\Gamma\Big{(}\frac{d+1}{2}+1\Big{)}-k\log||L_{d,k}||_{F}.$

Stirling’s formula $\log\Gamma(x+1)=x\log x-x+O(\log(x))$ implies that

$\displaystyle\log\Gamma\Big{(}\frac{d+1}{2}+1\Big{)}$
$\displaystyle=\Big{(}\frac{d+1}{2}\Big{)}\log\Big{(}\frac{d+1}{2}\Big{)}-\frac{d+1}{2}+O(\log(d))$
$\displaystyle=\frac{d}{2}\log(d)-\frac{d}{2}\log(2)-\frac{d}{2}+O(\log(d))$
$\displaystyle=\frac{d}{2}\log(d)-\log(\sqrt{2e})d+O(\log(d)).$

Since $k\leq\frac{\log(d)}{\log(16)}$ by assumption, Lemma 2.1(3) gives us a
positive constant $\beta^{\prime}$ such that

$\log||L_{d,k}||_{F}\leq\log(4)d+\beta^{\prime}\log(d).$

Again using the inequality $k\leq\frac{\log(d)}{\log(16)}$, we conclude that
there is some constant $\gamma^{\prime}$ such that

$k\log||L_{d,k}||_{F}\leq\frac{d}{2}\log(d)+\gamma^{\prime}\log(d)^{2}.$

Combining these estimates, there is some constant $\gamma$ such that

$\log\mathrm{Vol}(E_{d,k,\ell})\geq\log\Big{(}\frac{\sqrt{2\pi
e}}{2}\Big{)}d+\gamma\log(d)^{2}.\qed$

###  2.4. Main Result

The final input we require is the following classic theorem of Minkowski. See,
for example, Cassels [6, Chp. III, Thm. II].

######  Theorem 2.4 (Minkowski).

Let $E\subseteq\mathbb{R}^{n}$ be a compact, convex set such that $E=-E$. If

$\mathrm{Vol}(E)\geq m2^{n},$

then $E$ contains at least $m$ pairs $\pm v$ of nonzero vectors with integer
coordinates.

We now prove the first main result. Recall that for $d\geq 2$,

$B_{d}(\mathbb{Q}):=\sup_{f}|\mathrm{PrePer}(f,\mathbb{Q})|\in[0,\infty],$

where the supremum is taken over all $f(x)\in\mathbb{Q}[x]$ with
$2\leq\deg(f)\leq d$.

######  Theorem 2.5.

Let $d\geq 2$, and let $2\leq\ell\leq k:=\lfloor\log_{16}(d)\rfloor$. For all
sufficiently large integers $d$ there exists an integer-valued polynomial
$f_{d,\ell}(x)\in\mathbb{Q}[x]$ with $2\leq\deg(f_{d,\ell})\leq d$ such that

$f_{d,\ell}([d+k])\subseteq[d+\ell].$

In particular, for all sufficiently large $d$,

$B_{d}(\mathbb{Q})\geq d+\lfloor\log_{16}(d)\rfloor.$

###### Proof.

By Lemma 2.2 it suffices to show that there exists a non-zero lattice point
$v\in E_{d,k,\ell}$ such that the degree-at-most-$d$ polynomial $f_{v}(x)$
constructed in Lemma 2.2 has degree at least 2. If $v\in E_{d,k,\ell}$ and
$\deg(f_{v})\leq 1$, then either $f_{v}(x)=c\in[d+\ell]$ is constant, or
$f_{v}(x)=ax+b$ is a linear integer-valued polynomial. A linear polynomial
$ax+b$ with at least 2 finite preperiodic points is finite order; in that
case, $a$ is a root of unity. Thus $a=\pm 1$ and, since
$f_{v}([d+k])\subseteq[d+\ell]$, $b$ is uniquely determined by $a$. Therefore
there are at most $d+\ell+2$ lattice points $v\in E_{d,k,\ell}$ for which
$f_{v}(x)$ has degree less than 2.

It therefore suffices by Lemma 2.2 to show that for all sufficiently large
$d$, the ellipsoid $E_{d,k,\ell}$ contains more than $(d+\ell+2)/2$ pairs $\pm
v$ of non-zero lattice points. Since $E_{d,k,\ell}$ is clearly compact,
convex, and centrally symmetric, Theorem 2.4 reduces this to showing that

$\mathrm{Vol}(E_{d,k,\ell})\geq(d+\ell+4)2^{d}\text{ for all sufficiently
large $d$.}$

Lemma 2.3 implies there is a constant $\gamma$ such that

$\log\mathrm{Vol}(E_{d,k,\ell})\geq\log\big{(}\tfrac{\sqrt{2\pi
e}}{2}\big{)}d+\gamma\log(d)^{2}.$

Since $\tfrac{\sqrt{2\pi e}}{2}>2$, it follows that for all sufficiently large
$d$,

$\log\mathrm{Vol}(E_{d,k,\ell})\geq\log\big{(}\tfrac{\sqrt{2\pi
e}}{2}\big{)}d+\gamma\log(d)^{2}\geq\log(2)d+\log(d+\ell+4)=\log((d+\ell+4)2^{d}).\qed$

##  3\. Common preperiodic points

In this section we prove Proposition 1.8 and Theorem 1.7, restated as
Proposition 3.2 and Theorem 3.4 below.

######  Lemma 3.1.

If $f(x)\in\mathbb{C}[x]$ is a degree-$d$ polynomial and
$S\subseteq\mathbb{C}$ is a set with $n$ elements, then

$|f^{-1}(S)|\geq dn-d+1.$

###### Proof.

Let $e_{p}$ denote the ramification index of $f(x)$ at $p\in\mathbb{C}$. Then
for all $q\in\mathbb{C}$,

$d=\sum_{p\in f^{-1}(q)}e_{p}=|f^{-1}(q)|+\sum_{p\in f^{-1}(q)}(e_{p}-1).$

A point $p\in\mathbb{C}$ has $e_{p}>1$ if and only if $p$ is a root of
$f^{\prime}(x)$ with multiplicity $e_{p}-1$, hence

$d-1=\sum_{p\in\mathbb{C}}(e_{p}-1).$

Thus,

$|f^{-1}(S)|=\sum_{q\in S}|f^{-1}(q)|=dn-\sum_{p\in f^{-1}(S)}(e_{p}-1)\geq
dn-d+1.\qed$

######  Proposition 3.2.

Suppose that $f(x)\in\mathbb{Q}[x]$ is a degree $d\geq 2$ polynomial such that

$f([m])\subseteq[n],$

for some integers $m>n\geq 0$. Then

  1. (1)

$f^{-1}([n])\subseteq\bigcap_{i=0}^{m-n}\mathrm{PrePer}(f(x)+i,\mathbb{C})$,

  2. (2)

$|f^{-1}([n])|\geq dn-d+1$, and

  3. (3)

$\mathrm{PrePer}(f(x)+i,\mathbb{C})\neq\mathrm{PrePer}(f(x)+j,\mathbb{C})$ for
all $0\leq i<j\leq m-n$.

Hence

$dn-d+1\leq\left|\bigcap_{i=0}^{m-n}\mathrm{PrePer}(f(x)+i,\mathbb{C})\right|<\infty.$

###### Proof.

Let $0\leq i\leq m-n$. If $f([m])\subseteq[n]$, then

$f(f^{-1}([n]))+i\subseteq[n+i]\subseteq[m]\subseteq f^{-1}([n]).$

Hence $f^{-1}([n])\subseteq\mathrm{PrePer}(f(x)+i,\mathbb{C})$, proving (1).
The lower bound $|f^{-1}([n])|\geq dn-d+1$ follows immediately from Lemma 3.1
since $[n]$ contains $n$ points.

For (3) it suffices to prove that for any polynomial $f(x)$ and any positive
integer $i$,
$\mathrm{PrePer}(f(x),\mathbb{C})\neq\mathrm{PrePer}(f(x)+i,\mathbb{C})$.
Since $f(x)$ is a polynomial, $\infty$ is a super attracting fixed point and
thus the set $\mathrm{PrePer}(f(x),\mathbb{C})$ of finite complex preperiodic
points of $f(x)$ is bounded. Therefore there exists some
$q\in\mathrm{PrePer}(f(x),\mathbb{C})$ such that
$q+i\not\in\mathrm{PrePer}(f(x),\mathbb{C})$. Let $p\in f^{-1}(q)$. Then
$p\in\mathrm{PrePer}(f(x),\mathbb{C})$ by construction. If
$p\in\mathrm{PrePer}(f(x)+i,\mathbb{C})$, then
$f(p)+i=q+i\in\mathrm{PrePer}(f(x)+i,\mathbb{C})\setminus\mathrm{PrePer}(f(x),\mathbb{C})$.
Otherwise,
$p\in\mathrm{PrePer}(f(x),\mathbb{C})\setminus\mathrm{PrePer}(f(x)+i,\mathbb{C})$.
Therefore in either case,
$\mathrm{PrePer}(f(x),\mathbb{C})\neq\mathrm{PrePer}(f(x)+i,\mathbb{C})$.

Finally, Baker and DeMarco [1, Thm. 1.2] proved that if
$f(x),g(x)\in\mathbb{C}(x)$ are rational functions of degree at least 2, then
$\mathrm{PrePer}(f(x),\mathbb{C})\neq\mathrm{PrePer}(g(x),\mathbb{C})$ implies
$\mathrm{PrePer}(f(x),\mathbb{C})\cap\mathrm{PrePer}(g(x),\mathbb{C})$ is
finite. Therefore,

$dn-d+1\leq\left|\bigcap_{i=0}^{m-n}\mathrm{PrePer}(f(x)+i,\mathbb{C})\right|<\infty.\qed$

######  Example 3.3.

Consider the degree-6 polynomial

$f(x)=\frac{x^{6}-45x^{5}+775x^{4}-6375x^{3}+25504x^{2}-45060x+30960}{720}.$

One may check that

$f([14])\subseteq[10].$

Therefore Proposition 3.2 implies that
$\bigcap_{i=0}^{4}\mathrm{PrePer}(f(x)+i,\mathbb{C})$ is finite and contains
at least 55 points.

Recall that $C_{d}$ for $d\geq 2$ is defined by

$C_{d}:=\sup_{f,g}|\mathrm{PrePer}(f,\mathbb{C})\cap\mathrm{PrePer}(g,\mathbb{C})|,$

where the supremum is taken over all $f(x),g(x)\in\mathbb{C}[x]$ with
$2\leq\deg(f),\deg(g)\leq d$ such that
$\mathrm{PrePer}(f,\mathbb{C})\neq\mathrm{PrePer}(g,\mathbb{C})$.

######  Theorem 3.4.

For all sufficiently large $d$ and all integers $\ell$ with $2\leq\ell\leq
k:=\lfloor\log_{16}(d)\rfloor$, there exists a polynomial
$f(x)\in\mathbb{Q}[x]$ with $2\leq\deg(f)\leq d$ such that

$\deg(f)(d+\ell-1)+1\leq\left|\bigcap_{i=0}^{k-\ell}\mathrm{PrePer}(f(x)+i,\mathbb{C})\right|<\infty.$
(3.1)

Furthermore, there exist infinitely many $d\geq 2$ such that

$C_{d}\geq d^{2}+d\lfloor\log_{16}(d)\rfloor-2d+1.$ (3.2)

###### Proof.

Theorem 2.5 implies that for $d$ sufficiently large and integers
$2\leq\ell\leq k:=\lfloor\log_{16}(d)\rfloor$, there exists a polynomial
$f_{d,\ell}(x)\in\mathbb{Q}[x]$ with $2\leq\deg(f_{d,\ell})\leq d$ such that

$f_{d,\ell}([d+k])\subseteq[d+\ell].$

Hence (3.1) follows from Proposition 3.2.

Now we set $\ell:=k-1$ and write $f_{d}(x):=f_{d,k-1}(x)$ so that $f_{d}(x)$
is an integer-valued polynomial with $2\leq\deg(f_{d})\leq d$ such that

$f_{d}([d+k])\subseteq[d+k-1].$

Thus (3.1) specializes to

$\deg(f_{d})(d+k-2)+1\leq|\mathrm{PrePer}(f_{d}(x),\mathbb{C})\cap\mathrm{PrePer}(f_{d}(x)+1,\mathbb{C})|<\infty.$

We claim that for all $d_{0}\geq 2$, there exists an integer $d_{1}\geq d_{0}$
such that $d:=\deg f_{d_{1}}\geq d_{0}$. In that case,

$\begin{split}C_{d}\geq
d(d_{1}+k-2)+1&=d(d_{1}+\lfloor\log_{16}(d_{1})\rfloor-2)+1\\\ &\geq
d^{2}+d\lfloor\log_{16}(d)\rfloor-2d+1.\end{split}$ (3.3)

Note that we are using the fact that $d\leq d_{1}$ by construction of
$f_{d_{1}}$. Since $d\geq d_{0}$ and $d_{0}$ was arbitrary, the set of
integers $d\geq 2$ satisfying (3.3)—and hence (3.2)—is infinite. Thus, it
suffices to prove the claim.

Suppose there is some $d_{0}\geq 2$ such that $\deg(f_{d})\leq d_{0}$ for all
$d$. Since $f_{d}(x)$ is integer-valued, there are integers $a_{d,i}$ such
that $f_{d}(x)=\sum_{i=0}^{j_{d}}a_{d,i}\binom{x}{i}$ with $j_{d}\leq d_{0}$
and $a_{d,j_{d}}\neq 0$. Recall that a prime $p$ is said to be of _bad
reduction_ for a polynomial $f(x)\in\mathbb{Q}[x]$ if $p$ divides either the
leading coefficient of $f(x)$ or the denominator of some coefficient of
$f(x)$. Therefore the primes of bad reduction for $f_{d}(x)$ either divide
$a_{d,j_{d}}$ or are at most $j_{d}\leq d_{0}$. Benedetto [2, Main Thm.]
proved that $|\mathrm{PrePer}(f_{d},\mathbb{Q})|$ is bounded solely in terms
of the number of primes of bad reduction of $f_{d}(x)$. Since
$|\mathrm{PrePer}(f_{d},\mathbb{Q})|\geq d$ by construction, the number of
primes dividing $a_{d,j_{d}}$ must grow with $d$. In particular,
$|a_{d,j_{d}}|$ is unbounded as a function of $d$. We arrive at a
contradiction by arguing that $|a_{d,j_{d}}|$ must be bounded.

If $f(x):=\sum_{i=0}^{d_{0}}a_{i}\binom{x}{i}$, then the function

$c:=(a_{0},a_{1},\ldots,a_{d_{0}})\longmapsto(f(1),f(2),\ldots,f(d_{0}+1))$

is linear and invertible; let $M$ denote its matrix representation. Let
$c_{d}:=(a_{d,0},a_{d,1},\ldots,a_{d,d_{0}})$. Then $||Mc_{d}||_{\max}\leq
R_{d}:=d+k$ by construction. Hence the inequality (2.1) implies

$||c_{d}||_{\max}=||M^{-1}Mc_{d}||_{\max}\leq(d_{0}+1)||M^{-1}||_{\max}R_{d}.$

That is, $|a_{d,i}|\leq b_{0}R_{d}$ for some $b_{0}$ independent of $d$ and
each $0\leq i\leq d_{0}$. From $|f_{d}(R_{d})|\leq R_{d}$ we have

$R_{d}\geq|f_{d}(R_{d})|\geq|a_{d,j_{d}}|\binom{R_{d}}{j_{d}}-\left|\sum_{i=0}^{j_{d}-1}a_{d,i}\binom{R_{d}}{i}\right|,$

hence

$|a_{d,j_{d}}|\leq\frac{R_{d}+\left|\sum_{i=0}^{j_{d}-1}a_{d,i}\binom{R_{d}}{i}\right|}{\binom{R_{d}}{j_{d}}}\leq\frac{R_{d}+\sum_{i=0}^{j_{d}-1}b_{0}R_{d}\binom{R_{d}}{i}}{\binom{R_{d}}{j_{d}}}\leq
g(R_{d}),$

where $g(x)$ is a rational function independent of $d$ such that

$\lim_{x\rightarrow\infty}g(x)<\infty.$

Since $R_{d}=d+k\rightarrow\infty$ as $d\rightarrow\infty$, it follows that
$|a_{d,j_{d}}|$ is bounded as a function of $d$. This contradiction proves our
claim. ∎

##  4\. Examples of exceptional preperiodic behavior in every degree

In Theorem 2.5 we showed that for all sufficiently large degrees $d$, there
exists a degree-at-most-$d$ polynomial with at least
$d+\lfloor\log_{16}(d)\rfloor$ rational preperiodic points. However, the proof
is not constructive, in the sense that it does not allow us to provide an
explicit formula for such a polynomial. In this section we construct a family
of polynomials $r_{d}(x)\in\mathbb{Q}[x]$ such that, for all $d\geq 2$,
$r_{d}$ is a degree-$d$ polynomial with at least $d+6$ rational preperiodic
points.

First we introduce a doubly periodic sequence $\rho(m,d)$ and use its values
to interpolate an auxiliary sequence of polynomials $s_{d}(x)$.

######  Lemma 4.1.

There is a unique function $\rho:\mathbb{Z}^{2}\to\mathbb{Z}$ satisfying the
following properties:

  1. (i)

$\rho(m+3,d)=-\rho(m,d)$ for all $(m,d)\in\mathbb{Z}^{2}$,

  2. (ii)

$\rho(m,d+1)=-\rho(m+1,d)$ for all $(m,d)\in\mathbb{Z}^{2}$, and

  3. (iii)

$\rho(0,0)=\rho(1,0)=1$, and $\rho(2,0)=0$.

Furthermore, for all $(m,d)\in\mathbb{Z}^{2}$,

  1. (1)

$\rho(m,d+3)=\rho(m,d)$,

  2. (2)

$\rho(m+1,d+1)=\rho(m,d)+\rho(m,d+1)$,

  3. (3)

$\rho(m,d)=(-1)^{d}\rho(d+1-m,d)$.

###### Proof.

The initial values together with (i) imply that $\rho(m,0)$ is well-defined
for all $m\in\mathbb{Z}$. Then (ii) implies that
$\rho(m,d)=(-1)^{d}\rho(m+d,0)$. Hence these three properties uniquely
determine $\rho(m,d)$ for all $(m,d)\in\mathbb{Z}^{2}$.

$m$ | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---
$\rho(m,0)$ | 1 | 1 | 0 | $-1$ | $-1$ | 0
Table 1. Initial values that determine $\rho(m,n)$

(1) Properties (i) and (ii) imply that

$\rho(m,d+3)=(-1)^{3}\rho(m+3,d)=-\rho(m+3,d)=\rho(m,d).$

(2) Since $\rho(m+6,d)=\rho(m,d)$, we can check the following identity by
inspection:

$\rho(m+2,0)=\rho(m+1,0)-\rho(m,0).$

Replacing $m$ by $m+d$ yields

$\rho((m+1)+(d+1),0)=\rho(m+(d+1),0)-\rho(m+d,0),$

and repeatedly applying (ii) gives

$(-1)^{d+1}\rho(m+1,d+1)=(-1)^{d+1}\rho(m,d+1)+(-1)^{d+1}\rho(m,d);$

dividing by $(-1)^{d+1}$ yields (2).

(3) Using $\rho(m+6,d)=\rho(m,d)$ we may verify that for all $m\in\mathbb{Z}$,

$\rho(m,0)=\rho(1-m,0).$ (4.1)

Thus, if $d=2n$ is even, then

$\rho(m,2n)=\rho(m+2n,0)=\rho(m-4n,0)=\rho(4n+1-m,0)=\rho(2n+1-m,2n).$

Similarly, if $d=2n+1$ is odd, then (4.1) implies that

$\rho(m,2n+1)=-\rho(m+2n+1,0)=-\rho(m-4n+1,0)=-\rho(4n-m,0)=\rho(2n-1-m,2n+1).$

Finally, (i) implies

$\rho(2n-1-m,2n+1)=-\rho(2n+2-m,2n+1).$

Hence in either case,

$\rho(m,d)=(-1)^{d}\rho(d+1-m,d).\qed$

Let $s_{d}(x)\in\mathbb{Q}[x]$ be the unique degree-at-most-$d$ polynomial
such that

$s_{d}(m-\tfrac{d+1}{2})=\rho(m,d),$

for $0\leq m\leq d$. Lemma 4.2 establishes some basic properties of
$s_{d}(x)$. Let $\delta$ denote the _centered difference operator_ defined by

$\delta f(x):=f(x+\tfrac{1}{2})-f(x-\tfrac{1}{2}).$

######  Lemma 4.2.

Let $d\geq 0$.

  1. (1)

$s_{d}(-x)=(-1)^{d}s_{d}(x)$,

  2. (2)

$\delta s_{d+1}(x)=s_{d}(x)$,

  3. (3)

$\deg(s_{d})=d$,

  4. (4)

$s_{d}(d+1-\tfrac{d+1}{2})=\rho(d+1,d)$,

  5. (5)

$s_{d}(d+2-\tfrac{d+1}{2})=\rho(d+2,d)+1$,

  6. (6)

$s_{d}(d+3-\tfrac{d+1}{2})=\rho(d+3,d)+d+2$.

###### Proof.

(1) Suppose $f(x)\in\mathbb{R}[x]$ is a degree-at-most-$d$ polynomial. Then
$f(x)-(-1)^{d}f(-x)$ has degree at most $d-1$. Hence if there are at least
$\lfloor\tfrac{d+1}{2}\rfloor$ distinct pairs $\pm a$ of real numbers for
which $f(a)=(-1)^{d}f(-a)$, then it follows that the identity
$f(x)=(-1)^{d}f(-x)$ holds in $\mathbb{R}[x]$.

Lemma 4.1(3) implies that for $1\leq m\leq d$,

$s_{d}(m-\tfrac{d+1}{2})=\rho(m,d)=(-1)^{d}\rho(d+1-m,d)=(-1)^{d}s_{d}(d+1-m-\tfrac{d+1}{2})=(-1)^{d}s_{d}(\tfrac{d+1}{2}-m),$

since $1\leq m\leq d$ is equivalent to $1\leq d+1-m\leq d$. The set
$\\{m-\tfrac{d+1}{2}:1\leq m\leq d\\}$ contains at least
$\lfloor\tfrac{d+1}{2}\rfloor$ pairs $\pm a$, hence it follows that
$s_{d}(x)=(-1)^{d}s_{d}(-x)$ for all $d\geq 0$.

(2) Let $f(x)$ be the degree-at-most-$d$ polynomial

$f(x):=\delta s_{d+1}(x)=s_{d+1}(x+\tfrac{1}{2})-s_{d+1}(x-\tfrac{1}{2}).$

If $0\leq m\leq d$, then by Lemma 4.1(2),

$\displaystyle f(m-\tfrac{d+1}{2})$
$\displaystyle=s_{d+1}(m+1-\tfrac{d+2}{2})-s_{d+1}(m-\tfrac{d+2}{2})$
$\displaystyle=\rho(m+1,d+1)-\rho(m,d+1)$ $\displaystyle=\rho(m,d)$
$\displaystyle=s_{d}(m-\tfrac{d+1}{2}).$

Hence $f(x)=s_{d}(x)$.

(3) If $f(x)$ has degree $d\geq 1$, then $\delta f(x)$ has degree $d-1$. Since
$s_{0}(x)=1$ has degree 0 by construction, it follows from (2) that
$\deg(s_{d})=d$ for all $d\geq 0$.

(4) By (1) and Lemma 4.1(3),

$s_{d}(d+1-\tfrac{d+1}{2})=(-1)^{d}s_{d}(0-\tfrac{d+1}{2})=(-1)^{d}\rho(0,d)=\rho(d+1,d).$

(5) We prove this identity by induction on $d$. Since $s_{0}(x)=1$ is
constant,

$s_{0}(0+2-\tfrac{0+1}{2})=1=\rho(2,0)+1.$

Now let $d\geq 1$ and suppose that the identity (5) holds for $d-1$. By (2),
(4), and Lemma 4.1(2),

$\displaystyle s_{d}(d+2-\tfrac{d+1}{2})$
$\displaystyle=s_{d}(d+1-\tfrac{d+1}{2})+s_{d-1}(d+1-\tfrac{d}{2})$
$\displaystyle=\rho(d+1,d)+\rho(d+1,d-1)+1$ $\displaystyle=\rho(d+2,d)+1.$

(6) Following the induction in (5) we first observe that

$s_{0}(0+3-\tfrac{0+1}{2})=1=\rho(3,0)+0+2.$

If $d\geq 1$ and we suppose that (6) holds for $d-1$, then by (2), (5), and
Lemma 4.1(2),

$\displaystyle s_{d}(d+3-\tfrac{d+1}{2})$
$\displaystyle=s_{d}(d+2-\tfrac{d+1}{2})+s_{d-1}(d+2-\tfrac{d}{2})$
$\displaystyle=\rho(d+2,d)+1+\rho(d+2,d-1)+d-1+2$
$\displaystyle=\rho(d+3,d)+d+2.\qed$

###  4.1. Constructing $r_{d}(x)$

For $d\geq 0$, let $r_{d}(x)\in\mathbb{Q}[x]$ be the polynomial sequence
defined by

$r_{d}(x):=\begin{cases}s_{d}(x-3-\tfrac{d+1}{2})+2&\text{if $d$ is even,}\\\
s_{d}(x-3-\tfrac{d+1}{2})-x+d+6&\text{if $d$ is odd.}\end{cases}$

######  Theorem 4.3.

For all $d\geq 2$, $r_{d}(x)$ is a degree-$d$, integer-valued polynomial such
that if $d$ is even, then

$r_{d}([d+6])\subseteq[d+5],$

and if $d$ is odd, then

$r_{d}([d+6])\subseteq[d+4].$

Thus,

  1. (1)

$B_{d}(\mathbb{Q})\geq d+6$ for all $d\geq 2$, and

  2. (2)

$C_{d}\geq d^{2}+4d+1$ for all $d\geq 2$.

###### Proof.

Lemma 4.2(3) implies that $r_{d}(x)$ has degree $d$, and the fact that
$s_{d}(y-\frac{d+1}{2})$ is an integer for all $0\leq y\leq d$, and therefore
$r_{d}(x)$ is an integer for all $3\leq x\leq d+3$, implies that $r_{d}$ is
integer-valued for all $d\geq 0$.

Suppose that $d\geq 2$ is even. If $3\leq k\leq d+4$, then the definition of
$s_{d}(x)$ and Lemma 4.2(4) gives us,

$r_{d}(k)=s_{d}(k-3-\tfrac{d+1}{2})+2=\rho(k-3,d)+2\in[1,3].$

From $s_{d}(x)$ even we find that

$r_{d}(d+7-x)=s_{d}(\tfrac{d+7}{2}-x)+2=s_{d}(x-\tfrac{d+7}{2})+2=r_{d}(x).$

Hence by Lemma 4.2(5) and (6),

$\displaystyle r_{d}(1)$
$\displaystyle=r_{d}(d+6)=s_{d}(d+3-\tfrac{d+1}{2})+2=\rho(d+3,d)+d+4\in[d+3,d+5],$
$\displaystyle r_{d}(2)$
$\displaystyle=r_{d}(d+5)=s_{d}(d+2-\tfrac{d+1}{2})+2=\rho(d+2,d)+3\in[2,4].$

Thus if $d$ is even,

$r_{d}([d+6])\subseteq[d+5],$

from which it follows that
$B_{d}(\mathbb{Q})\geq|\mathrm{PrePer}(r_{d}(x),\mathbb{Q})|\geq d+6$.

Next suppose that $d\geq 2$ is odd. If $3\leq k\leq d+4$, then as above we
have

$r_{d}(k)=s_{d}(k-3-\tfrac{d+1}{2})-k+d+6=\rho(k-3,d)-k+d+6\in[1,d+4].$

Lemma 4.2(5) and (6) gives us

$\displaystyle r_{d}(d+5)$
$\displaystyle=s_{d}(d+2-\tfrac{d+1}{2})+1=\rho(d+2,d)+2\in[1,3],$
$\displaystyle r_{d}(d+6)$
$\displaystyle=s_{d}(d+3-\tfrac{d+1}{2})=\rho(d+3,d)+d+2\in[d+1,d+3].$

Since $s_{d}(x)$ is odd,

$\displaystyle d+5-r_{d}(d+7-x)$
$\displaystyle=d+5-s_{d}((d+7-x)-3-\tfrac{d+1}{2})+(d+7-x)-d-6$
$\displaystyle=-s_{d}(-x+3+\tfrac{d+1}{2})-x+d+6$
$\displaystyle=s_{d}(x-3-\tfrac{d+1}{2})-x+d+6$ $\displaystyle=r_{d}(x).$

Thus,

$\displaystyle r_{d}(1)$ $\displaystyle=d+5-r_{d}(d+6)\in[2,4]$ $\displaystyle
r_{d}(2)$ $\displaystyle=d+5-r_{d}(d+5)\in[d+2,d+4].$

Therefore,

$r_{d}([d+6])\subseteq[d+4],$

and it follows that $B_{d}(\mathbb{Q})\geq d+6$ for all $d\geq 2$. Since for
either parity of $d$ we have

$r_{d}([d+6])\subseteq[d+5],$

Proposition 3.2 implies that for all $d\geq 2$,

$|\mathrm{PrePer}(r_{d}(x),\mathbb{C})\cap\mathrm{PrePer}(r_{d}(x)+1,\mathbb{C})|\geq
d(d+4)+1=d^{2}+4d+1.$

Hence $C_{d}\geq d^{2}+4d+1$ for all $d\geq 2$. ∎

Figure 1 illustrates the typical behavior of the polynomials $r_{d}(x)$ in the
interval $[1,d+6]$.

Figure 1. The graphs of $r_{12}(x)$ and $r_{13}(x)$

###  4.2. Explicit formulas for $s_{d}(x)$

We suspect there is more of interest to say about the dynamical properties of
the sequence of polynomials $r_{d}(x)$. Thus to facilitate their future study
we end this section by deriving explicit formulas for the polynomials
$s_{d}(x)$, which then allow for direct calculation of $r_{d}(x)$.

For $d\geq 0$, let $c_{d}(x)\in\mathbb{Q}[x]$ be the polynomial sequence
defined by

$c_{2k}(x):=\frac{1}{(2k)!}\prod_{j=1}^{k}\left(x^{2}-\tfrac{(2j-1)^{2}}{4}\right)\hskip
54.2025ptc_{2k+1}(x):=\frac{1}{(2k+1)!}x\prod_{j=1}^{k}(x^{2}-j^{2}).$

Note that, by construction, $c_{d}(x)$ is even when $d$ is even and $c_{d}(x)$
is odd when $d$ is odd. A straightforward comparison of roots and leading
coefficients implies that

$\delta c_{d+1}(x)=c_{d}(x)$

for $d\geq 0$, and $\delta c_{0}(x)=\delta\,1=0$. Furthermore, $c_{2k}(x)$ is
integer-valued on $\mathbb{Z}+\tfrac{1}{2}$ and $c_{2k+1}(x)$ is integer-
valued on $\mathbb{Z}$.

######  Proposition 4.4.

For all $k\geq 0$,

$s_{2k}(x):=\sum_{j=0}^{k}(-1)^{k-j}c_{2j}(x)\qquad\text{and}\qquad
s_{2k+1}(x):=\sum_{j=0}^{k}(-1)^{k-j}c_{2j+1}(x).$

###### Proof.

First observe that $\\{c_{2k}:k\geq 0\\}$ forms a basis for the vector space
of even polynomials in $\mathbb{Q}[x]$. Therefore there are rational numbers
$\alpha_{j}$ such that

$s_{2k}(x):=\sum_{j=0}^{k}\alpha_{j}c_{2j}(x).$

Since

$c_{2k}(\tfrac{1}{2})=\begin{cases}1&\text{if $k=0$,}\\\
0&\text{otherwise,}\end{cases}$

it follows from Lemma 4.1 and Lemma 4.2 that

$\alpha_{j}=\delta^{2j}s_{2k}(\tfrac{1}{2})=s_{2(k-j)}(\tfrac{1}{2})=\rho(k-j,2(k-j))=\rho(3(k-j),0)=(-1)^{k-j}\rho(0,0)=(-1)^{k-j}.$

The expansion for $s_{2k+1}(x)$ follows by applying $\delta$ to the expansion
of $s_{2k+2}(x)$. ∎

##  5\. Low degree examples

In this final section we provide lower bounds for $B_{d}(\mathbb{Q})$ and
$C_{d}$ in low degrees found by computation. Table 2 gives examples of
polynomials $f(x)$ and integers $m,n$ such that

$f([m])\subseteq[n].$ (5.1)

These are the polynomials with the largest $m$ for each degree $d$ that we
found by computer search. Thus the entries in the column labeled $m$ also
provide the best known lower bounds on $B_{d}(\mathbb{Q})$ for $2\leq d\leq
9$.

$d$ | $m$ | $n$ | $f(x)$
---|---|---|---
2 | 8 | 7 | ${\scriptstyle\frac{x^{2}-9x+22}{2}}$
3 | 11 | 11 | ${\scriptstyle\frac{x^{3}-18x^{2}+89x-66}{6}}$
4 | 10 | 8 | ${\scriptstyle\frac{x^{4}-22x^{3}+167x^{2}-506x+552}{24}}$
5 | 13 | 9 | ${\scriptstyle\frac{x^{5}-35x^{4}+445x^{3}-2485x^{2}+5794x-3600}{120}}$
6 | 14 | 10 | ${\scriptstyle\frac{x^{6}-45x^{5}+775x^{4}-6375x^{3}+25504x^{2}-45060x+30960}{720}}$
7 | 15 | 15 | ${\scriptstyle\frac{x^{7}-56x^{6}+1246x^{5}-14000x^{4}+83629x^{3}-258104x^{2}+373764x-151200}{5040}}$
8 | 16 | 16 | ${\scriptstyle\frac{x^{8}-68x^{7}+1918x^{6}-29036x^{5}+254989x^{4}-1309952x^{3}+3765012x^{2}-5343984x+2862720}{20160}}$
8 | 16 | 15 | ${\scriptstyle\frac{x^{8}-68x^{7}+1946x^{6}-30464x^{5}+282569x^{4}-1559852x^{3}+4836124x^{2}-7320336x+4273920}{40320}}$
9 | 19 | 17 | ${\scriptstyle\frac{x^{9}-90x^{8}+3426x^{7}-71820x^{6}+904449x^{5}-7002450x^{4}+32752124x^{3}-87183720x^{2}+116300160x-55520640}{181440}}$
Table 2.

One fast method to find these examples in low degree is to use the LLL basis
reduction algorithm: Given a degree $d$ and an integer $k>0$, let
$\Lambda_{d,k}$ be the lattice generated by the vectors

$u_{i}:=\left(\binom{1}{i},\binom{2}{i},\ldots,\binom{d+k}{i}\right)$

for $0\leq i\leq d$. If $f(x)=\sum_{i=0}^{d}a_{i}\binom{x}{i}$ for
$a_{i}\in\mathbb{Z}$, then the lattice point
$u=\sum_{j=0}^{d}a_{j}u_{j}\in\Lambda_{d,k}$ has coordinates

$u=(f(1),f(2),\ldots,f(d+k)).$

Thus we are looking for vectors $v\in\Lambda_{d,k}$ for which all the
coordinates $v_{i}$ satisfy $1\leq v_{i}\leq d+k$. The condition on the
coordinates implies that these are relatively short vectors in
$\Lambda_{d,k}$. Hence an effective (but not guaranteed) way to find such
vectors is to use the LLL basis reduction algorithm to find a basis of short,
nearly orthogonal vectors in $\Lambda_{d,k}$. Finally we check each basis
vector to see if the coordinates fall within the desired interval and if the
corresponding polynomial has degree at least 2. Note that there are at most
two basis vectors for $\Lambda_{d,k}$ corresponding to polynomials of degree
less than 2. Using this method we surveyed up to degree $d=400$ and found
examples giving $B_{d}(\mathbb{Q})\geq d+8$ for all $11\leq d\leq 283$ except
for

$d\in\\{21,219,221,235,237,241,244,\ldots,247,249,251,255,\ldots,266,268,269,271\\}.$

For all other degrees $11\leq d\leq 400$ the examples showed that
$B_{d}(\mathbb{Q})\geq d+6$, which we already knew by Theorem 4.3.

When $n<m$ in Table 2, Proposition 3.2 applied to $f([m])\subseteq[m-1]$
allows us to extract lower bounds on $C_{d}$. Note that the lower bound on
$C_{2}$ in Table 3 comes from Example 1.9.

In Table 3 we collect the best lower bounds on $C_{d}$ for small $d$ that we
found through computational experiment. All of our examples came from common
preperiodic points of $f(x)$ and $f(x)+1$ for some polynomial $f(x)$
exhibiting dynamical compression.

$d$ | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$C_{d}\geq$ | 26 | 24 | 36 | 60 | 78 | 84 | 120 | 162 | 190 | 198 | 228 | 260 | 294 | 330
Table 3.

For degrees $d=2,4,5,6,8,9$, the polynomials giving the lower bound on $C_{d}$
come from Table 2. For degrees $d=3,7$, the polynomials $r_{d}(x)$ constructed
in Section 4.1 give the lower bound. For $10\leq d\leq 15$, the polynomials
$f_{d}(x)$ giving the lower bounds on $C_{d}$ are too large to print
explicitly. Instead, Table 4 lists $d+1$ interpolating values
$(f_{d}(1),f_{d}(2),\ldots,f_{d}(d+1))$ which uniquely determine the
polynomial $f_{d}(x)$.

$d$ | $(f_{d}(1),f_{d}(2),\ldots,f_{d}(d+1))$
---|---
10 | (14, 6, 14, 6, 1, 6, 14, 17, 14, 10, 10)
11 | (17, 1, 15, 3, 4, 14, 17, 12, 8, 9, 10, 6)
12 | (17, 1, 17, 3, 4, 14, 17, 12, 6, 3, 3, 6, 12)
13 | (17, 1, 17, 1, 3, 13, 16, 13, 10, 9, 9, 9, 8, 5)
14 | (20, 4, 20, 4, 20, 14, 1, 8, 21, 18, 6, 6, 18, 21, 8)
15 | (21, 1, 2, 20, 4, 1, 9, 10, 5, 3, 6, 11, 16, 19, 17, 12)
Table 4.

## References

  * [1] M. Baker, L. DeMarco, Preperiodic points and unlikely intersections, _Duke Math. J._ , 159, no. 11 (2011), DOI: 10.1215/00127094-1384773.
  * [2] R. L. Benedetto, Preperiodic points of polynomials over global fields, _J. reine angew. Math._ 608 (2007), 123–153.
  * [3] R. L. Benedetto, B. Dickman, S. Joseph, B. Krause, D. Rubin, X. Zhou, Computing points of small height for cubic polynomials, _Involve_ , 2, no. 1 (2009), 37–64.
  * [4] P. Cahen, J. Chabert, _Integer-Valued Polynomials_ , Mathematical Surveys and Monographs, 48, American Mathematical Society (1997).
  * [5] L. Caporaso, J. Harris, B. Mazur, _How many rational points can a curve have?_ , The Moduli Space of Curves, Progress in Mathematics, 129, Birkhäuser Boston (1995).
  * [6] J. W. S. Cassels, _An introduction to the geometry of numbers_ , Classics in Mathematics, 99, Springer Science & Business Media (1971).
  * [7] L. DeMarco, H. Krieger, H. Ye, Common preperiodic points for quadratic polynomials, _preprint_ (2019), arXiv: 1911.02458.
  * [8] J. R. Doyle, X. Faber, D. Krumm, Preperiodic points for quadratic polynomials over quadratic fields, _New York J. Math._ , 20 (2014), 507–605.
  * [9] H. Fu, M. Stoll, Elliptic curves with common torsion $x$-coordinates and hyperelliptic torsion packets, _preprint_ (2021), arXiv: 1912.09766.
  * [10] W. Hindes, Finite orbit points for sets of quadratic polynomials, _Int. J. Number Theory_ 15, no. 8 (2019), 1693–1719.
  * [11] N. Looper, The uniform boundedness and dynamical Lang conjectures for polynomials, _preprint_ (2021), arXiv: 2105.05240v2.
  * [12] N. M. Mavraki, H. Schmidt, On the dynamical Bogomolov conjecture for families of split rational maps, _preprint_ (2022), arXiv: 2201.10455.
  * [13] P. Morton, S. Raianu, Arithmetic properties of $3$-cycles of quadratic maps over $\mathbb{Q}$, _preprint_ (2021), arXiv: 2105.07435.
  * [14] P. Morton, J. H. Silverman, Rational periodic points of rational functions, _Int. Math. Res. Not._ , no. 2 (1994), 97–110.
  * [15] D. G. Northcott, Periodic points on an algebraic variety, _Ann. of Math. (2)_ , 51 (1950), 167–177.
  * [16] B. Poonen, The classification of rational preperiodic points of quadratic polynomials over $\mathbf{Q}$: a refined conjecture, _Math. Z._ , 228, no. 1 (1998), 11–29.
  * [17] J. H. Silverman, The arithmetic of dynamical systems, _Springer Science & Business Media_, 241 (2007).