\input amstex \documentstyle{amsppt} %\NoPageNumbers %\Monograph %\NoRunningHeads %\TagsOnLeft %\TagsOnRight \catcode `\@=11 \def\logo@{} \catcode `@=12 %\Hoffset=.05in %\voffset=0.02in %\pagewidth{5.3in} %\pageheight{7.25in} %\pageno=-2 \topmatter \title {On certain plane curves with many integral points}\endtitle \author F. Rodr\'iguez Villegas and J. F. Voloch\endauthor \address{Department of Mathematics\newline University of Texas at Austin\newline Austin, TX 78712 USA}\endaddress \date{November 1997}\enddate \email villegas@math.utexas.edu, voloch@math.utexas.edu \endemail %\keywords{} %\subclass{} %\abstract{TO COME}\endabstract \endtopmatter %%\pagewidth{4.6in} %%\pageheight{6.0in} %\def\SumPrime{\sideset} \NoBlackBoxes \def\Z{\Bbb Z} \def\C{\Bbb C} \def\Q{\Bbb Q} \def\R{\Bbb R} \def\N{\Bbb N} \def\H{\Cal H} \def\F{\Cal F} \def\K{\Cal K} \def\I{\Cal I} \def\T{\widetilde{T}} \def\disc{\operatorname{disc}} \def\Res{\operatorname{Res}} \def\no{$\text{n}^{\text{o\,}}$} \def\RE{\text{Re}\,} \def\IM{\text{Im}\,} \def\half{\tfrac12} \def\sgn{\text{sgn\,}} \def\Kl{\text{Kl\,}} \document \magnification=\magstep1 \baselineskip=14pt {\bf 0.} \ In the course of another investigation we came across a sequence of polynomials $P_d \in \Z[x,y]$, such that $P_d$ is absolutely irreducible, of degree $d$, has low height and at least $d^2+2d+3$ integral solutions to $P_d(x,y)=0$. We know of no other family of polynomials of increasing degree with as many integral (or even rational) solutions in terms of their degree, except of course those with infinitely many rational points. It is a consequence of Siegel's theorem [Si] that these polynomials have finitely many integral zeros, since their homogeneous part of highest degree has distinct roots. Siegel [Si, \S 7] speculated whether there is a bound for the number of integral zeros of a polynomial as a function of the number of non-zero coefficients, provided it has only finitely many zeros. This is still very much of an open problem but Caporaso et al. [CHM] have shown that a similar statement for rational points on curves (with the genus replacing the number of coefficients) would follow from a conjecture of Lang. Abramovich [$\aleph$] proved an analogue of the result of [CHM] for integral points on elliptic curves. See also [$\aleph$V]. A polynomial in two variables and degree $d$ has $N={d+2 \choose 2}$ coefficients, so, given points $(x_1,y_1),\ldots,(x_{N-1},y_{N-1})$, one can find a non-zero polynomial that vanishes on these points. If these points have integer coordinates of absolute value at most $H$, then such a polynomial can be chosen with integer coefficients of absolute value at most $(NH^d)^N$, by a straightforward application of Siegel's lemma. We can choose $H = N/2$, for instance, and it will turn out that our polynomials $P_d$ have slightly lower height and twice as many points as this construction gives. Moreover, this construction does not ensure that the polynomial obtained is absolutely irreducible. A slightly better construction, suggested by Ed Schaffer is to take a polynomial of the shape $(x-x_1)\cdots(x-x_d)+\alpha(y-y_1)\cdots(y-y_d)$, which will vanish on the $d^2$ points $(x_i,y_j),i,j=1,\ldots,d$, is irreducible for most chioces of $\alpha$ and has height at most $|\alpha|H^d$. Our polynomials $P_d$ have larger height but more points. We have checked that $P_d=0$ defines a smooth curve for $d=1,2, \cdots, 25$. We do not know whether this is true in general, though it is very likely. Also, we can prove the existence of certain points on the curve, but numerical experimentation shows that they may contain a few more. We present the data in \no 7. {\bf 1.} \ Let $T_k \in \Z[x,y]$ be defined recursively by $$ \aligned &T_0=1, \qquad T_1=y, \\ &T_{k+1}=yT_k+k(x+k-1)T_{k-1}, \qquad k \in \N. \endaligned \tag{\bf T0} $$ The first few polynomials are $$ \aligned T_2&=x + y^2\\ T_3&=3yx + y^3 + 2y\\ T_4&=3x^2 + 6y^2x + 6x + y^4 + 8y^2\\ T_5&=15yx^2 + 10y^3x + 50yx + y^5 + 20y^3 + 24y\\ T_6&=15x^3 + 45y^2x^2 + 90x^2 + 15y^4x + 210y^2x + 120x + y^6 + 40y^4 + 184y^2 . \endaligned $$ {}From the recursion it follows easily that $$ T_k(x,-y)=(-1)^kT_k(x,y), \qquad k \in \N . \tag{\bf T1} $$ Hence for $k=2d$ with $d \in \N$, $T_k(x,y)=P_d(-x,y^2)$ with $P_d \in \Z[x,y]$. We will use the following notation: given a polynomial $$ H= \sum_{m,n}a_{m,n}x^my^n \quad\in \C[x,y], $$ we let $$ ||H||_1=\sum_{m,n}|a_{m,n}|. $$ We will prove the following. \proclaim{Theorem} \ Let $d \in \N$ and $P_d$ be the polynomial defined above. Then a) $P_d$ has degree $d$; b) $P_d$ is absolutely irreducible; c) the coefficients of $P_d(-x,y)$ are relatively prime non-negative integers; d) $||P_d||_1=(2d)!$\;; and e) $P_d$ vanishes at the $d^2+2d+3$ integral points: $$ \aligned I:&\qquad(n,0), \;(n, 2^2), \;(n, 4^2), \cdots ,\; (n, n^2), \qquad 0\leq n\leq 2d-1, \qquad \text{ $n$ even} \\ II:&\qquad (n, 1^2), \; (n, 3^2), \; (n, 5^2), \cdots ,\; (n, n^2), \qquad 0\leq n\leq 2d-1, \qquad \text{ $n$ odd} \\ III:& \qquad (4d, 2^2), \; (4d, 6^2), \; (4d, 10^2), \cdots ,\; (4d, 4(2d-1)^2)\\ IV:& \qquad (8d+1, 3^2), \; (2d-4,-6d+4), \; (2d-3, -2d+1) \endaligned $$ \endproclaim Note that $P_d,P_{d+1}$ intersect in exactly $d(d+1)$ of the above points. \vskip .5cm {\bf 2.} \ Fix $x,y$ and consider the generating function $$ F(\lambda)=\sum_{k=0}^\infty \frac{T_k}{(x)_k}\;\frac{\lambda^k}{k!}, $$ where $$ (z)_0=1, \qquad (z)_k=z(z+1) \cdots (z+k-1), \qquad k\in \N. $$ It is not hard to see that the recursion defining $T_k$ implies that $F$ satisfies the differential equation $$ \lambda\frac{d^2 F}{d \lambda^2}+x \frac{d F}{d \lambda} - (\lambda+y)F=0. $$ In order to get a formula for $T_k$ we consider $G(\lambda)=e^\lambda F(\lambda)$. A calculation shows that $G$ satisfies the differential equation $$ \lambda\frac{d^2 G}{d \lambda^2}+(x-2\lambda) \frac{d G}{d \lambda} -(x+y)G=0. $$ It follows that $$ G(\lambda)=\Phi(\tfrac12(x+y),x,2\lambda), $$ where $\Phi$ is the confluent hypergeometric function (see for example, [Le \S 9.9]). If we write $$ G(\lambda)=\sum_{k=0}^\infty \frac{S_k}{(x)_k}\;\frac{\lambda^k}{k!}, $$ the differential equation implies that $$ S_{k+1}=(y+x+2k)S_k, \qquad k \in \N. $$ Therefore, $$ S_k=(y+x)(y+x+2)\cdots (y+x+2k-2), $$ from which we obtain $$ \multline T_k=\sum_{j=0}^k(-1)^{k-j}\binom kj(x+y)(x+y+2)\cdots(x+y+2j-2)\\ (x+j)(x+j+1)\cdots (x+k-1). \endmultline \tag{\bf T2} $$ We now may see why $P_d$ vanishes at the points $I$ and $II$ of the theorem. The principle is based on the following self-proving lemma; we leave the details to the reader. \proclaim{Lemma} Let $x_1, \cdots, x_n$ and $y_1, \cdots, y_n$ be two sets of $n$ elements of a field $K$. Let $$ \aligned &\phi_0=1, \qquad \phi_\nu(x)=(x-x_1)(x-x_2) \cdots (x-x_\nu), \in K[x] \qquad 1\leq \nu \leq n \\ &\psi_0=1, \qquad \psi_\nu(y)=(y-y_1)(y-y_2) \cdots (y-y_\nu), \in K[y] \qquad 1\leq \nu \leq n, \endaligned $$ with $x,y$ indeterminates. Then any linear combination $$ \sum_{\nu=0}^n\alpha_\nu \; \phi_\nu(x) \; \psi_{n-\nu}(y) \in K[x,y], \qquad \alpha_\nu \in K, $$ has degree at most $n$ and vanishes at the points $(x_\mu,y_\nu)$ for all $1\leq \mu\leq \nu\leq n.$ \endproclaim \vskip .5cm {\bf 3.} \ It is clear from the recursion {\bf T0} that $T_k$ has degree $k$, that the coefficients of $T_k$ are non-negative integers and that the coefficient of $y^k$ is $1$. This proves parts a) and c) of the theorem. To prove part d), let $c_k=T_k(1,1)$. Note that $c_k=||T_k||_1$ since the coefficients of $T_k$ are non-negative. {}From the recursion $$ \aligned &c_0=1, \qquad c_1=1, \\ &c_{k+1}=c_k+k^2c_{k-1}, \qquad k \in \N. \endaligned $$ It follows easily that $c_k=k!$ hence $$ ||T_k||_1=k!\;, \qquad k \in \N. \tag{\bf T3} $$ Let us also remark that {\bf T2} implies the following $$ \frac{T_k(m,n)}{k!} \in \Z, \qquad \text{for all $m,n \in \Z$}. \tag{\bf T4} $$ \vskip .5cm {\bf 4.} \ Let $\T_k=z^kT_k(x/z^2,y/z)$. Then $\T_k$ is isobaric of weight $k$, if we assign $x$ weight $2$, $y$ weight $1$, and $z$ weight $1$. These polynomials satisfy the recursion $$ \aligned &\T_0=1, \qquad \T_1=y, \\ &\T_{k+1}=y\T_k+k(x+z^2(x-1))\T_{k-1}, \qquad k \in \N. \endaligned $$ Set now $R_k=\T_k(1,t,0)$, the leading terms of $\T_k$ at infinity. Then $$ \aligned &R_0=1, \qquad R_1=t, \\ &R_{k+1}=tR_k-kR_{k-1}, \qquad k \in \N. \endaligned $$ It follows that $R_k(t)=2^{-k/2}H_k(t/\sqrt{2})$, where $H_k$ is the classical Hermite polynomial (see for example [Le \S 4.9]). More precisely, $$ R_k(t)=\left . z^kT(1/z^2,t/z)\right |_{z=0}=k!\sum_{j=0}^{[k/2]}\frac{(-1)^j}{j!\;(k-2j)!\;2^j}\; t^{k-2j} \tag{\bf T5} $$ It is interesting that the discriminant can be computed explicitly $$ \disc (R_k)=\prod_{j=1}^kj^j, $$ but we only need to know that it is non-zero. \proclaim{Lemma} Let $K$ be a perfect field and $\overline{K}$ an algebraic closure of $K$. Let $P \in K[x,y,z]$ be a homogeneous polynomial of degree $d$. Suppose that $P(t,1,0) \in K[t]$ also has degree $d$, is irreducible over $K$ and $P(x,y,z)=0$ has more than $d^2/4$ projective solutions over $K$. Then $P$ is irreducible over $\overline{K}$. \endproclaim \demo{Proof} Since $P(t,1,0)$ has degree $d$ and is irreducible over $K$ it follows that $P(x,y,z)$ is also irreducible over $K$. Suppose $P$ is not absolutely irreducible. Then, $P=\prod_\sigma Q^\sigma$, where $Q$ is an irreducible factor of $P$ over $\overline{K}$ of degree $e \le d/2$ and $\sigma$ runs through the embeddings of the field of definition of $Q$ into $\overline{K}$. Any $K$-rational point of $P=0$ is a rational point of $Q^\sigma=0$ for every $\sigma$. Since the $Q^\sigma$'s are all distinct, Bezout's theorem implies that the number of $K$-rational points of $P=0$ is bounded by $e^2\leq d^2/4$, a contradiction. $\square$ \enddemo According to Schur [Sc] the polynomials $R_k$ for $k$ even and $R_k/t$ for $k$ odd are irreducible over $\Q$. Hence, the above lemma applies and we deduce part b) of the theorem. \vskip .5cm {\bf 5.} \ For $p>2$ a prime number let us consider the recursion defining $T_k$ modulo $p$. It turns out to have a very simple structure. First, from {\bf T2} it follows that $$ T_p \equiv y^p-y \bmod{p}, \qquad p>2, \qquad \text{$p$ prime}. $$ Also, $$ \aligned T_{p+k}&\equiv (y^p-y)T_k \bmod{p} \\ T_{p+k+1}&\equiv yT_{p+k}+k(x+k-1)T_{p+k-1} \bmod{p} \endaligned $$ and we conclude that $$ T_k\equiv T_{a_0}(y^p-y)^{a_1}(y^{p^2}-y^p)^{a_2}\cdots \bmod{p}, \qquad k=a_0+a_1p+a_2p^2 \cdots \in \N. \tag{\bf T6} $$ \vskip .5cm {\bf 6.} \ We now prove that $P_d$ vanishes on the points $III$ of the theorem. First we need the following. For each $k \in \N$ consider the polynomials $$ U_k(z,w)=T_k(x,y), \qquad z=\tfrac12(x-y), \qquad w=x-k+1. $$ Let $\lambda$ be an indeterminate and $z,w$ two fixed integers. Then using {\bf T2} we obtain $$ \sum_{k=0}^\infty U_k(z,w)\frac{\lambda^k}{k!}=\frac{(1+2\lambda)^z}{(1+\lambda)^w}, \qquad z, w \in \Z. \tag{\bf T7} $$ {}From this identity it is not hard to see that $$ \frac{U_k(z,w)}{k!}=\sum_{j=0}^{w-1}(-2)^j\binom{z}{j} \binom{k+w-j-1}{w-j-1}, \qquad 0\leq z\leq w. \tag{\bf T8} $$ Note that the right hand side is a polynomial of degree $w-1$ in $k$. Without the hypothesis $z\leq w$ {\bf T8} holds for all $k$ sufficiently large. In particular, given integers $z,w$ there is only finitely many polynomials $U_k$ that vanish at the point $(z,w)$, for $w \ge 0$. It follows that $P_d$ vanishes at the points III if $$ \sum_{j=0}^m(-2)^j\binom{m}{k}\binom{2k-j}{k}=0, \qquad 0\leq m\leq k, \quad \text{$m$ odd}, \tag{*} $$ where $k=2d$. To prove this identity we start with $$ \binom{a+b}{k}=\sum_{r=0}^a\binom{a}{r}\binom{b}{k-r}, \qquad a,b\in \Z_{\geq0}, $$ which follows from the binomial theorem by comparing the $k$-th coefficients on both sides of $$ (1+\lambda)^{a+b}=(1+\lambda)^a(1+\lambda)^b. $$ Applying this to $a=m-j,b=2k-m$ we obtain $$ \binom{2k-j}{k}=\sum_{r=0}^{m-j}\binom{m-j}{r}\binom{2k-m}{k-r} $$ and hence (*) is equivalent to $$ \sum_{j=0}^m\sum_{r=0}^{m-j} (-2)^j\binom{m}{j}\binom{m-j}{r}\binom{2k-m}{k-r}=0. $$ This in turn follows from the stronger fact $$ \sum_{j=0}^{m-r}(-2)^j\binom{m}{j}\binom{m-j}{r}= (-1)^m\sum_{j=0}^r(-2)^j\binom{m}{j}\binom{m-j}{m-r}, $$ since $\binom{2k-m}{k-r}=\binom{2k-m}{k-m+r}$, obtained by expanding $$ (\lambda-1)^m=(\lambda+1-2)^m $$ and comparing the coefficients of $\lambda^r$ and $\lambda^{m-r}$ respectively. The fact that the points listed in $IV$ are in $P_d=0$ will be left to the reader. \vskip .5cm {\bf 7.} \ We now present the experimental data. We first discuss the cases $d=3,4$ in more detail, where the equations $P_d(x,y)=0$ determine smooth projective curves of genus $1,3$ respectively. For $d=3$ we have $$ P_3=-15x^3 + 45yx^2 + 90x^2 - 15y^2x - 210yx - 120x + y^3 + 40y^2+ 184y. $$ The equation $P_3=0$ defines an elliptic curve and a Weierstrass equation for it (courtesy of F. Hajir) is given by: $$y^2 = x^3 + 230940/23*x^2 + 9286041600/529*x + 90438421708800/12167.$$ A computer search yielded the following $25$ integral solutions $(x,y)$ to $P_3(x,y)=0$. \vskip .2cm $$ \matrix \format \r&\quad\r&\quad\r&\quad\r&\quad\r&\quad\r&\quad\r&\quad\r\\ (0,0)& (1, 1)& (2, -14)& (2, 0)& (2, 4)& (3, -5)& (3, 1)& (3, 9)\\ (4, 0)& (4, 4)& (4, 16)& (5, 1)& (5, 9)& (5, 25)& (9, 25)& (12, 4)\\ (12, 36)& (12, 100)& (16, 144)& (25, 9)& (67, 25)& (345, 1225)& (-1,-9)& (-4,-20)\\ (-14,-56) \endmatrix $$ \vskip .5cm For $d=4$ $$ \multline P_4= 105x^4 - 420x^3y - 1260x^3 + 210x^2y^2 + 4200x^2y + 4620x^2 \\ - 28xy^3 -1540xy^2 - 11872xy - 5040x + y^4 + 112y^3 + 2464y^2 + 8448y \endmultline $$ A computer search yielded the following $31$ integral solutions $(x,y)$ to $P_4(x,y)=0$. \vskip .2cm $$ \matrix \format \r&\quad\r&\quad\r&\quad\r&\quad\r&\quad\r&\quad\r&\quad\r\\ (0,0)& (2,0)& (4,0)& (6,0)& (1, 1)& (3, 1)& (5, 1)& (7, 1)\\ (3, -3)& (2, 4)& (4, 4)& (6, 4)& (16, 4)& (5,-7)& (3, 9)& (5, 9)\\ (7, 9)& (33, 9)& (4, 16)& (6, 16)& (4, -20)& (0,- 24)& (5, 25)& (7, 25)\\ (3, -35)& %???(11, 35)& (6, 36)& (16, 36)& (7, 49)& (16, 10)& (16, 196)& (-11,-35) \endmatrix $$ For higher $d$ we have the following data, where we only present those points not given by the Theorem. We searched exhaustively for points with $|x| \le 1000$. We haven't found any patterns in the extra points; perhaps a more attentive reader will. \vskip .2cm $$ \matrix \format \r&\quad\r&\quad\r&\quad\r&\quad\r&\quad\r&\quad\r&\quad\r\\ {\tenrm d}& {\tenrm new\ points}\hfill& {\tenrm total\ number\ of\ points}\\ 5& (16,144),(17,81),(25,441),(99,589)\hfill& 42\hfill\\ 6& (1,-11),(17,121),(34,784)\hfill& 54\hfill\\ 7& (16,16),(17,49),(25,169),(36,676),(98,16)\hfill& 71\hfill\\ 8& {\tenrm none}\hfill& 85\hfill\\ 9& (9,-35),(33,289)\hfill& 104\hfill\\ 10& {\tenrm none}\hfill& 123\hfill\\ 11& (34,784),(36,676),(41,441),(57,2601),(67,3249)\hfill& 160\hfill\\ 12& {\tenrm none}\hfill& 171\hfill \endmatrix $$ \bigskip To verify that $P_d=0$ defines a smooth curve is enough to check that it has no affine singularities as the Hermite polynomial is separable. For this we computed, using the recursion modulo $p$, the quantity $$ \Res_y(\Res_x(P_d,\frac{\partial P_d}{\partial x}), \Res_x(P_d,\frac{\partial P_d}{\partial y})) \bmod p, $$ for various primes $p$, where $\Res_t$ stands for resultant in the variable $t$, and confirmed it is not zero for $d=2, 3, \ldots, 25 $. Acknowledgements: We would like to thank R. Coleman, A. Granville, F. Hajir and B. Poonen for suggestions, and the NSF (FRV) and NSA (JFV) for financial support. We also acknowledge the use of the software PARI for the numerical calculations. The routines we used are available at the URL:\break {\tt http://www.ma.utexas.edu/users/voloch/polynomial.html}. \frenchspacing \widestnumber\key{999999999} \Refs \ref \key{$\aleph$} \by D. Abramovich \paper Uniformity of stably integral points on elliptic curves \vol 127 \pages 307-317 \yr 1997 \jour Invent. Math. \endref \ref \key{$\aleph$V} \by D. Abramovich, J. F. Voloch \paper Lang's conjectures, fibered powers, and uniformity \vol 2 \pages 20-34 \yr 1996 \jour New York J. Math. \endref \ref \key{CHM} \by L. Caporaso, J. Harris, B. Mazur \paper Uniformity of rational points \jour J. Amer. Math. Soc. \vol 10 \yr 1997 \pages 1-35 \endref \vskip .3cm \ref \key{Le} \by N. N. Lebedev \book Special functions and their applications \yr 1972 \publ Dover Publications \endref \vskip .3cm \ref \key{Si} \by C. L. Siegel \pages 209-266 \paper Uber einige Anwendungen Diophantischer Approximationen \yr 1966 \inbook Gesammelte Abhandlungen I \publ Springer Verlag \endref \vskip.3cm \ref \key{Sc} \paper Affektlose Gleichungen in der Theorie der Laguerreschen und Hermiteschen Polynome \by I. Schur \vol 165 \pages 52-58 \jour J. Reine Angew. Math. \yr 1931 \endref \endRefs \enddocument