%Dear Dr. Spalinski,
%Please find enclosed the final version of my paper with Villegas and
%Zagier, "Constructions of plane curves with many points", ACTARITH 3850
%accepted for Acta Arithmetica. I made the corrections pointed out in your 
%letter and I fixed the AMSTeX file according to your specifications.
%Thank you. Yours, Felipe Voloch


\input amstex
\documentstyle{amsppt}
\magnification=\magstep1 \vsize=23 truecm
\hsize=30truecc
\baselineskip=16truept
%\normalbaselineskip=1.1\normalbaselineskip\normalbaselines
\TagsOnRight \NoRunningHeads \nologo 
\def\bs{\bigskip} \def\n{\smallskip\noindent} \def\nn#1{\n{\bf(#1)}}
\def\Res{\text{Res}} \def\={\;=\;} \def\+{\,+\,}
\def\a{\alpha} \def\b{\beta} \def\z{\zeta} \
\def\l{\lambda} \def\p{\partial} \def\e{\varepsilon}
\def\Z{\Bbb Z} \def\Q{\Bbb Q} \def\R{\Bbb R} \def\N{\Bbb N} \def\F{\Bbb F_p}

\topmatter\title Constructions of plane curves with many points\endtitle
\author F. Rodriguez Villegas, 
J. F. Voloch and D. Zagier\endauthor
\subjclass14G05,11G30\endsubjclass
\endtopmatter 

In this paper we investigate some plane curves with many points
over $\Q$, finite fields and cyclotomic fields.  

In a previous paper [4] the first two authors constructed a sequence
of absolutely irreducible polynomials $P_d(x,y)\in\Z[x,y]$ of degree
$d$ having low height and many integral solutions to $P_d(x,y)=0$.
(The definition of these polynomials will be recalled in \S4.)  Here
we construct further examples of polynomials of arbitrarily large
degree $d$ over $\Q$ with many rational zeros, improving the known
record for the maximal number of rational zeros of a smooth
polynomial in two variables over $\Q$ of given large degree. We also
construct examples of two variable polynomials having the maximal
theoretically possible number of zeros at roots of unity and over
finite fields.  Finally, we return to the polynomials $P_d$ and show
that for certain special values of $d$ they have a few more zeros than
were found there.

Here is a more precise statements of the results obtained, with a few
remarks about each one.

\proclaim{Theorem 1} For each natural number $m$, the plane projective
curve of degree $m$ defined by the vanishing of the polynomial
$$
G_m(x,y,z)\=\sum\Sb i,\,j,\,k\ge0\\i+j+k=m\endSb x^iy^jz^k\tag1$$
is non-singular in characteristic 0 or characteristic
$p\nmid(m+1)(m+2)$, and has zeros at $2m^2$ points where the
coordinates $x$, $y$ and $z$ are roots of unity.  \endproclaim 
The polynomials $G_m$, which are in some sense the simplest imaginable homogeneous
polynomials of degree $m$ (all coefficients are equal!), simultaneously
achieve the optimum for two different problems relating to the number of zeros
of a polynomial in two variables: On the one hand, a simple argument
(given in \S1) shows that no non-reciprocal plane curve of degree $m$
can vanish at more than $2m^2$ points whose coordinates are roots of
unity.  On the other hand, Theorem 0.1 of [6] tells us that an
absolutely irreducible plane curve of degree $1<d<p$ defined over $\F$
has at most $d(d+p-1)/2$ points over $\F$, and, as we will check in
\S1, Theorem~1 implies that the curve $G_m(x^k,y^k,z^k)=0$ with
$p-1=(m+2)k$ attains this bound.

\proclaim{Theorem 2} For any integer $d$ divisible by $6$ there exist
infinitely many polynomials $F(x,y) \in \Q[x,y]$ of degree $d$ of the
form $F_d(x,y)=(f(h(x))-f(h(y)))/(h(x)-h(y))$ such that the curve
$F_d(x,y) =0$ is smooth and contains at least $d^2+6d$ rational
points. \endproclaim These are, for large $d$, the smooth polynomials
in two variables with the largest number of points over $\Q$ known. We
refer the reader to the introduction of [4] for references to some
speculations as to whether there is a uniform bound on the number of
rational points on a curve of fixed genus (see also [2]). We note that
there are constructions, due to Brumer, Harris and Mestre (see [2] or
[3]) which lead to curves with many points over number fields. For
instance, Harris obtains plane curves of degree $d$ with $3d^2$
rational points over cyclotomic fields.  Brumer and Mestre construct
hyperelliptic curves of any genus $g$ with $16(g+1)$ rational points
over the field of $(g+1)$-st roots of unity and $8g+12$ points over
$\Q$.  The curves of Brumer and Mestre all have big automorphism
groups.  Silverman has suggested that one should measure the number of
points divided by the order of the automorphism group. From this point
of view the curves occurring in Theorem 2 are good, since they usually
have the involution $(x,y)\mapsto (y,x)$ as their only non-trivial
automorphism, and the curves constructed in [4] are still better,
since they probably have no non-trivial automorphisms at all.  Here we
will obtain:

\proclaim{Theorem 3} For infinitely many values of $d$, the equation
$P_d(x,y)=0$ of degree $d$ has at least $d^2+2d+8$ integral solutions.
\endproclaim 
This improves (for some $d$) the result of [4], where it was shown 
that $P_d=0$ has at least $d^2+2d+3$ integral solutions for every $d$. 
We will also show that the number ``$d^2+2d+8$" in Theorem~3 can be increased 
by~1 if we allow rational zeros, and will give numerical evidence suggesting 
that in general there are very few, if any, further rational zeros. 

% The definition of $P_d$ will be recalled in \S4.

\heading\S1. Variations of a construction of Schaefer \endheading 

A very simple construction of two-variable polynomials with many
integral zeros was suggested by Ed Schaefer: if $f(x)\in\Z[x]$ has
distinct integer roots, say $\a_1,\ldots,\a_n$, then the polynomial
$f(x)+\l f(y)$, which is irreducible for generic $\l$, has degree
$d=n$ and $n^2$ integral roots at $(x,y)=(\a_i,\a_j)$.  To improve
this, we take $\l=-1$.  The polynomial $f(x)-f(y)$ now has the linear
factor $x-y$. If we remove it, then the quotient is usually
irreducible, has degree $d=n-1$, and has $n^2-n=d^2+d$ roots
$(x,y)=(\a_i,\a_j)$, $\a_i\ne\a_j$, which is slightly better in terms
of the degree.  If $f$ is also assumed to be even, then $f(x)-f(y)$ is
divisible by $x^2-y^2$ and the quotient has degree $d=n-2$ and
$n(n-2)=d^2+2d$ roots, very nearly as good as the number $d^2+2d+3$
found in [4] for the polyomials $P_d$, and this can be improved still
further in some cases, as we will see below.

First, however, we look at a generalization of this construction,
replacing ``even" by ``invariant under multiplying $x$ or $y$ by $\z$,
where $\z$ is a $k$th root of unity." This of course requires working
over a field $K$ which contains the $k$th roots of unity, so no longer
applies to $\Q$, but will be of interest in the cases of cyclotomic
and of finite fields.  Let $K$ be such a field and set $f(x)=\prod
(x^k-\a_i^k)$, where $\a_1,\ldots,\a_r$ are elements of $K^\times$
whose $k$th powers are distinct. Then the polynomial $P(x,y)=
(f(x)-f(y))/(x^k-y^k)$ has degree $d=k(r-1)$ and vanishes on the
$k^2r(r-1)$ points $(\z\a_i,\z'\a_j)$, where $\z,\,\z'$ are $k$-th
roots of unity and $i\ne j$.  Thus we get polynomials of degree $d$
with $d^2+kd$ points over any number field containing the $k$-th roots of
unity, though it is unclear how good these examples really are.

More interesting is what the construction gives in the case of finite
fields. Let $p$ be a prime and $k$ a divisor of $p-1$, $k<(p-1)/2$.
Let $r+1=(p-1)/k$. We then get polynomials of degree $d=p-1-2k$ with
$d^2+kd = d(d+p-1)/2$ points over $\F$, and this achieves the upper
bound from [6] mentioned in the introduction, provided we know that
our polynomials are absolutely irreducible.  This information is given
by Theorem~1 in the case of the polynomial
$f(x)=(x^{(m+2)k}-1)/(x^k-1)$, since then $P(x,y)=G_m(x^k,y^k,1)$,
with $G_m(x,y,z)$ as in equation~(1), so that in this case we indeed
achieve the theoretical upper bound (with $d=mk$ and zeros at all
$x,\,y,\,z\in\F^\times$ with $x^k$, $y^k$ and $z^k$ distinct).


As was also mentioned in the introduction, the same polynomials $G_m$
also achieve the maximum for the number of zeros at roots of unity of
a non-reciprocal polynomial of degree $m$ over $\Q$, or indeed even over
$\R$. To see this, let $h(x,y)=0$ be such a polynomial.  If we have a
solution of $h(\z,\,\z')=0$ with $\z$ and $\z'$ roots of unity, then
taking complex congugates we get
$0=h(\bar\z,\,\bar{\z'})=h(\z^{-1},\,{\z'}^{-1})$.  Thus $(\z, \z')$ is
also a point on the curve $(xy)^mh(x^{-1},y^{-1})$, of degree $2m$.
If those two curves have no component in common, there can be only
$2m^2$ points in their intersection; we call such polynomials $h$ or
the curves that they define {\it non-reciprocal}. For example, if $h$
is smooth and does not go through the origin then $h$ is
non-reciprocal.  (For bounds for general curves see [5]).

\heading\S2. Construction of curves with many points over $\Q$ \endheading


Returning to the case of $\Q$ and to $P(x,y)$ of the form
$(f(x)-f(y))/(x^2-y^2)$ where $f$ is an even polynomial of degree
$d+2$ with distinct integral roots, we can try to improve our lower
bound $d^2+2d$ on the number of zeros of $P$ by looking for solutions
of the equation $f(x)=f(y)\ne0$.  We list only some first attempts in
that direction; looking for better examples is an amusing game and the
reader may want to play.

The idea is that if $f(x)$ has one or several blocks of zeros in
arithmetic progression, then for certain small values of $\delta$ the
difference $f(x)-f(x+\delta)$ already has so many known zeros
(corresponding to $x$ where $f(x)=f(x+\delta)=0$) that the remaining
ones are the roots of a polynomial of small degree which may then
split completely over $\Q$. There are many possible variants. For
instance, if we take $f$ to have its positive roots at
$a,\,a+1,\ldots,a+n-1$ for some $a$ and~$n$, then $f(x+1)=f(x)$ has
only the obvious roots but
$$
\frac{f(x+1)}{f(x-1)}\=
1\+4nx\,\frac{x^2-a^2-(n-1)(a-\frac12)}{(x+a)(x+a-1)(x-a-n)(x-a-n+1)}\,,$$
so if we arrange for $\kappa:=a^2+(n-1)(a-\frac12)$ to be a perfect
square, which is easy to do, then we get eight additional roots
$(\pm\sqrt\kappa-1,\pm\sqrt\kappa+1)$,
$(\pm\sqrt\kappa+1,\pm\sqrt\kappa-1)$ of the polynomial
$(f(x)-f(y))/(x^2-y^2)$. (Here $a$ can even be a rational number,
since we can always rescale $x$ and $y$ to get integral roots.)  If we
take instead $f$ with its positive roots at $1,\,3,\ldots,2k-1$ and
$2b+1,\,2b+3,\ldots,2b+2l-1$ for some positive integers $k$, $l$ and
some integer or rational number $b$, then we find
$$
\frac{f(2x+1)}{f(2x-1)}\=
1\+2\,\frac{(k+l)x^2-kb(b+l)}{(x-k)(x-b-l)(x+b)}\,,$$
so whenever
$kb(b+l)/(k+l)$ is a perfect square we again get 8 extra roots.
Finally, if we choose $f$ with its positive roots at
$1,\,3,\ldots,\widehat{2r-1},\ldots,2n-1$ for some $0<r<n$, then the
non-trivial roots of $f(x+1)=f(x-1)$ and of $f(x+2)=f(x-2)$ are given
by $(n-1)x^2=4nr(r-1)$ and $(n-1)x^2=4n^2+(4r^2-4r-3)n-1$,
respectively, and there are many pairs $(n,r)$ for which one of these
two equations has rational solutions, although unfortunately (at least
up to $n=1000$) none where they both do.

Summarizing, we have the following result. For each degree $d$ there are
infinitely many two-variable polynomials of degree~$d$ of the form
$(f(x)-f(y))/(x^2-y^2)$ having at least $d^2+2d+8$ integral
zeros.

It is easy to check that for
generic even polynomials  $f$  which split completely over  $\Q$, the curve
defined by  $(f(x)-f(y))/(x^2-y^2)=0$  is smooth. Thus we can guarantee that
polynomials in the above result are smooth at the expense of reducing
the number of points to $d^2+2d$.

We can construct polynomials with at least $d^2+3d$ integral
zeros, for all $d$ divisible by $3$, as follows.
Let $h(x)=x^3-x^2$. It can easily be shown that there exist infinitely
many rational numbers $\a$ such that $h(x)+\a$ splits completely in $\Q$.
Let $\a_1,\ldots,\a_n$ be distinct rational numbers such that $h(x)+\a_i$ splits
into three distinct linear factors in $\Q$. Let $f(x)=\prod (h(x)+\a_i)$ and
$F(x,y) = (f(x)-f(y))/(h(x)-h(y)), d=3n-3$. If $\b_{ij},j=1,2,3$ are the roots
of $h(x)+\a_i=0, i=1,\ldots,n$, then $F(x,y) =0$ contains the rational points
$(\b_{ij},\b_{i'j'}),i,i'=1,\ldots,n,i'\ne i,j,j'=1,2,3$. These points number
$9n(n-1)= d^2+3d$, as claimed.

A slight modification of the same idea gives Theorem 2, 
 which we now proceed to prove.

\demo{Proof of Theorem 2} Set $h(x)=x^6-2x^4+x^2$ and
$$C(\l)=\dfrac{(\l(\l-1)(\l+1)(2\l-1)(\l-2))^2}{(\l^2-\l+1)^6}.$$ 
Then the polynomial $h(x)-C(\l)$ splits as $\prod_{\a\in S(\l)}(x-\a)$ with
$$S(\l)\;=\;\biggl\{\pm\dfrac{\l^2-1}{\l^2-\l+1}\;,\;\,
\pm\dfrac{\l^2-2\l}{\l^2-\l+1}\;,\;\,\pm\dfrac{2\l-1}{\l^2-\l+1}\biggl\}\;.$$
Now let $\l_1,\ldots,\l_n$ be rational numbers such that the numbers
$C(\l_i)$ are all distinct and set $f(X)=\prod_i (X-C(\l_i))$ and
$F(x,y)=(f(h(x))-f(h(y)))/(h(x)-h(y))$. This polynomial has degree $d=6n-6$
and vanishes for $x\in S(\l_i)$, $y\in S(\l_j)$ with $1\le i\ne j\le n$,
i.e., at $36n(n-1)=d^2+6d$ rational points.  Finally, the curve defined by 
$F(x,y)=0$ is smooth for almost all $(\l_1,\ldots,\l_n) \in\Q^n$ because, as is
easily seen, the set of (complex) $n$-tuples $(\l_1,\ldots,\l_n)$ for which this curve
is smooth is Zariski open.
\enddemo



\heading\S3. Proof of Theorem 1\endheading

Let $m$ be a natural number and consider the homogeneous polynomial
$G_m(x,y,z)$ defined in the introduction. By summing a geometric
series, we can write it in the form
$$
G_m(x,y,z)\=\frac{1}{x-y}\left(\frac{x^{m+2}-z^{m+2}}{x-z}\,
-\,\frac{y^{m+2}-z^{m+2}}{y-z}\right)\,,\tag2$$
which is the form which was
used in \S1.  Writing it this way makes it clear that we have not
merely the $m^2+m$ roots of $G_m(\z,\z',1)=0$ given by taking $\z$ and
$\z'$ to be distinct $(m+2)$nd roots of unity different from~1, but
also the $m^2-m$ roots of $G_m(\z,\z',1)=0$ given by taking $\z$ and
$\z'$ to be distinct $(m+1)$st roots of unity different from~1.
   %  since in this case both fractions $(x^{m+2}-z^{m+2})(x-z)$ and $(y^{m+2}-y^{m+2})(x-y)$ are equal to~1. 
This proves the second assertion of the theorem.

To prove the first, we note that (2) can be rewritten as
$G_m=D_{m+2}/D_2$, where
$$D_n\=D_n(x,y,z)\=\left|\matrix 1&1&1\\1
  &x&y\\1&x^n&y^n\endmatrix\right|\;.\tag3$$
{}From now on we fix $m$
and write simply $G$ for $G_m(x,y,1)$ and $D$ for $D_{m+2}(x,y,1)$.
Our first claim is that
$$
\Res_x(G,\frac{\p G}{\p y})=g(y)^{m-1}\,,\tag4$$
where $\Res_x$
denotes the resultant as polynomials in $x$ and
$g(y)=G(y,y)=\sum_{j=0}^m(j+1)y^j\,$.  To prove this, we have to look
at the simultaneous zeros of $G$ and $G_y= \p G/\p y$.  It is easy to
deal with the points where $D_2=0$. Ignoring them, we have that the
equations $G=G_y=0$ are equivalent to $D=D_y=0$.  The polynomial $D$
is the determinant of the matrix with columns $v(1)$, $v(x)$ and
$v(y)$, where $v(x):=(1,x,x^{m+2})^t$, and similarly $D_y$ is the
determinant of the matrix with columns $v(1)$, $v(x)$, and
$v'(y)=(0,1,(m+2)y^{m+1})^t$.  If both vanish, then all four vectors
$v(1)$, $v(x)$, $v(y)$ and $v'(y)$ must lie in the same
two-dimensional space.  (It cannot be one-dimensional since $v(y)$ is
never proportional to $v(1)$ for $y\ne1$.) In particular this holds
for $v(1)$, $v(y)$ and $v'(y)$, so the determinant they define is
zero, and this determinant is simply $g(y)$.  Hence any zero of
$G=G_y=0$ has $y$-coordinate equal to one of the roots
$y_1,\ldots,y_m$ of $g(y)=0$, and conversely each of these roots
occurs as the $y$-coordinate of precisely $m-1$ zeros of $G=G_y=0$.
(Up to a scalar, the unique vector orthogonal to $v(1)$, $v(y_i)$ and
$v'(y_i)$ is $w(y_i)=((m+1)y_i^{m+2},\,-(m+2)y_i^{m+1},\,1)$, so the
roots of $G(x,y_i)=G_y(x,y_i)=0$ are the roots of the polynomial
$(x^{m+2}-(m+2)y_i^{m+1}x+(m+1)y_i^{m+2})/(x-1)(x-y_i)^2$ of degree
$m-1$.)  This proves equation (4) up to a constant, which can then be
shown to be $1$ by looking at the terms of highest degree.

Now to find the possible singular points of the projective curve $C$,
we must look for the common zeros of $G$, $G_x$, and $G_y$ and hence,
by (4), of $G_x$ and $g$. Again we can ignore the zeros of $D_2$ and
the points at infinity, which are easily dealt with. Then
$G=G_x=G_y=0$ is equivalent to $D=D_x=D_y=0$. At a simultaneous zero
of $G$, $G_x$, and $G_y$, all five vectors $v(1)$, $v(x)$, $v'(x)$,
$v(y)$ and $v'(y)$ must be in the same 2-dimensional space.  By the
argument already given, the orthogonal complement of this space is
spanned by the vector $w(y)$, and by symmetry it is also spanned by
$w(x)$, so these two vectors must be equal.  Subtracting them, we find
that $(m+1)(x^{m+2}-y^{m+2})$ and $(m+2)(x^{m+1}-y^{m+1})$ both
vanish, and this is clearly impossible if $m+1$ and $m+2$ are
non-zero.  Therefore singularities can only occur in characteristics
dividing $(m+1)(m+2)$, as claimed.

\n{\bf Remarks. 1.} We have observed numerically the following
identity, which would also imply the statement about non-singularity
in Theorem 1, but were unable to prove it:
$$
\Res_y(\Res_x(G,{\p G \over \p
  x}),g)\=2^{-m}(m+1)^{m^2-2m+2}(m+2)^{m^2-m}\,.$$
\n{\bf 2.} In our
previous example over finite fields we only considered the points on
$G(x^k,y^k)=0$ above the $(m+2)$nd roots of unity, but we can also
consider the $(m+1)$st by, for example taking $p-1=k(m+1)$.
Incidentally, $G(0,\zeta,1)=0$ if $\zeta \ne 1$ is an $(m+1)$st root
of unity and there are similar points also on the lines $y=0$ and
$z=0$. So $G(x^k,y^k)=0$ in this case has $k^2m(m-1)+3km$ rational
points over $\F$. This again attains the bound of Thm.~0.1 of [5] if
$k=2$, and comes fairly close for other small $k$.  It also has the
feature that we can obtain curves of odd degree, which we could not
do in the previous example. One can also try to use simultaneously at
least some of the $(m+1)$st and $(m+2)$nd roots of unity, but we did
not obtain interesting examples this way.

\heading\S4. Integral points on the curve $P_d(x,y)=0$ \endheading 

In [4], certain polynomials $P_d(x,y)\in\Z[x,y]$ of degree $d$ were
constructed and it was shown that $P_d$ for every $d$ is absolutely
irreducible and has at least $d^2+2d+3$ integral solutions to
$P_d(x,y)=0$.  In his review [1] of [4] for Math\. Reviews, A\.
Bremner pointed out that in fact one family of integral solutions had
been missed and that in fact the equation $P_d(x,y)=0$ has at least
$d^2+2d+4$ integral solutions when $d$ is odd.  This prompted us to
look again for patterns in the extra points we found experimentally
which might occur for infinitely many, but not all, $d$.  This section
reports our findings.

The polynomials $P_d$ can be defined by the formula
$P_d(-X,Y^2)=T_{2d}(X,Y)$, where the $T_k[X,Y]\in\Z[X,Y]$
($k=0,\,1,\,\ldots$) are given by the generating function
$$ H(t):=(1-t)^r(1+t)^s\=\sum_{k=0}^\infty 
T_k(-r-s,-r+s)\;\frac{t^k}{k!}\tag5$$
or---expanding by the binomial theorem---more explicitly by
$$
T_k(-r-s,-r+s)\=k!\;\sum_{n=0}^k(-1)^n\binom rn\binom s{k-n}\,.\tag
6$$
We now describe ten constructions of infinite families of integer
solutions of the equation $P_d(x,y)=0$. The first four are the ones
already given in [4], but we re-prove them here for completeness and
also because the proofs here, based on the generating function (5),
are in some cases shorter than those in [4].  The fifth family gives
the extra solution for odd $d$ observed by Bremner, and the first
seven together give (for suitable $d$) the conclusion of Theorem~2.

\nn{I} $r$ and $s$ small \n If $r$ and $s$ are nonnegative integers,
then $H(t)$ is a polynomial of degree $r+s$, so $T_k(-r-s,-r+s)$
vanishes for $k>r+s$.  This gives us the $d(d+1)$ integral zeros
$(x,y)=(n,m^2)$ of $P_d(x,y)=0$, where $0\le m\le n\le 2d-1$, $m\equiv
n\pmod2$.  \nn{II} $x=4d$ \n If $r$ and $s$ are positive odd integers
with sum $2k$, then the coefficients of the polynomial $H(t)$ are
anti-symmetric (i.e. $t^{2k}H(1/t)=-H(t)$), so its middle coefficient
vanishes.  For $P_d$ this gives the $d$ additional zeros
$P_d(4d,4n^2)=0$ for $0<n<2d$, $n$ odd.
\nn{III} $y=9$ \n A further zero
$P_d(8d+1,3^2)=0$ can be seen as follows. Take $r=4d-1$, $s=4d+2$
in~(5).  Then $H(t)=(1+t)^3(1-t^2)^{4d-1}$, and the coefficient of
$t^{2d}$ in this is, up to sign, equal to
$\;\binom{4d-1}d-3\binom{4d-1}{d-1}$, which indeed vanishes.  \nn{IV}
$x=2d-3$ or $2d-4$ \n The generating function identity (5) and the
obvious differential equation
$$\frac{H'(t)}{H(t)}\=-\,\frac r{1-t}\+\frac s{1+t}$$
imply the
recursion $T_{k+1}=YT_k$ $+k(X+k-1)T_{k-1}$ for the polynomials
$T_k(X,Y)$.  (This recursion, with suitable initial conditions, was in
fact taken as the definition of $T_k$ in [4].) For the subfamily
$P_d(x,y)=T_{2d}(-x,\sqrt y)$ this leads to the recursion
$$P_{d+1}\=[y-(4d+1)x+8d^2]\,P_d-[2d(2d-1)(x-2d+1)(x-2d+2)]\,P_{d-1}\;.$$ 
The two coefficients in square brackets vanish if $x$ equals $2d-1$ 
or $2d-2$ and $y=(4d+1)x-8d^2$, giving two additional integer zeros.
%
% $$P_{d+1}\=[y-(4d+1)x+8d^2]\,P_d-[2d(2d-1)(x-2d+1)(x-2d+2)]\,P_{d-1}$$
% for the subfamily $P_d$ corresponding to even $k$.  Both expressions in
% square brackets vanish for $(x,y)=(2d-2,-6d-2)$ or $(x,y)=(2d-1,-2d-1)$,
% giving two additional integer zeros.
%
\nn{V} $x=4d-3$ \n For $d$ odd we have a further solution
$P_d(4d-3,\,(2d-1)^2)=0$. (These are the points noticed by Bremner.)
To prove this we must show that the coefficient of $t^{2d}$ in $H(t)$
is zero when $r=d-1$, $s=3d-2$. For these values of $r$ and $s$,
$H(t)= (1-t^2)^{d-1}(1+t)^{2d-1}$, so the coefficient in question is
$\sum_{n=1}^{d-1}(-1)^{d-n}\,\binom{d-1}{d-n}\binom{2d-1}{2n}\,,$
which vanishes if $d$ is odd because the terms for $n$ and $d-n$
cancel.

\nn{VI} $r=2$ \n
For $r=2$ the function $H(t)$ in (5) equals $(1+t)^{s+2}-4t(1+t)^s$, so
$$\align T_k(&-s-2,s-2)\=k!\biggl[\binom{s+2}k-4\binom s{k-1}\biggr]\\
&\=\frac14s(s-1)\cdots(s-k+3)\,\bigl[(2s-4k+3)^2\,-\,(8k+1)\bigr]\,.\endalign
$$
The zeros at $s=0,\,1,\ldots,k-3$ correspond to construction (I),
but if $k=2d$ and $16d+1=a^2$ for some integer $a$ then we get a new
integral point $x=\bigl(\frac{a+1}2\bigr)^2$,
$y=\bigl(\frac{a+5}2\bigr)^2\bigl(\frac{a-3}2\bigr)^2$ on
$P_d(x,y)=0$.  In fact we get {\it two} new solutions, since we can
replace $a$ by its negative.


\nn{VII} $r=3,\,4,\,5$ \n More generally, if $r$ is a fixed positive
integer then for $k\ge r$ the sum in (6) terminates at $n=r$ and can
be rewritten as $\binom kr^{-1}\binom s{k-r}\,Q_r(k,s)$ with
$$
Q_r(k,s)\=r!\,\sum_{n=0}^r(-1)^n \binom
kn\binom{r+s-k}{r-n}\;\in\,\Z[k,s]\,,$$
a polynomial of degree $r$.
For $r$ odd, we set $\tilde Q_r(k,s)=Q_r(k,s)/(r+s-2k)$ to remove the
factor corresponding to (II) above. Then for $r=3$ we find
$$ 4\,\tilde Q_3(k,s)\=(2s-4k+3)^2\,-\,(24k+1) $$
and hence two further integral solutions of $P_d=0$ whenever $48d+1$ is a
square.  (This case is very similar to (VI), but has been listed separately
for convenience in counting solutions below.) For $r=4$ or 5, we find
$$
\align Q_4(k,t+2k-4)&\=3\,(2k-t^2+t-1)^2\,-\,(2t^4-2t^2+3)\,,\\
3\,\tilde
Q_5(k,t+2k-5)&\=5\,(6k-t^2+3t-5)^2\,-\,(2t^4-10t^2+53)\,,\endalign$$
each giving only a finite number of further solutions corresponding to
the integral points on an elliptic curve of positive rank over $\Q$.

\nn{VIII} $x=2d+2$ \n 
  % Going back to case (I), we note that for $r$ and $s$ non-negative integers the polynomial
  % $(-1)^rH(t)$ begins $t^{r+s}+(s-r)t^{r+s-1}+\frac12((s-r)^2-r-s)t^{r+s-2}$.  The vanishing
  % of the second coefficient for $r=s$ does not help us (the degree of this term is then odd),
  % but the vanishing of the third coefficient produces another infinite family of integral 
  % zeros of $P_d(x,y)=0$ for special $d$, given by $d=c^2-1$, $x=y=4c^2$ with $c\in\N$. 
Another infinite family of integral zeros of $P_d(x,y)=0$ for special
$d$ is given by $d=2c^2-1$, $x=y=4c^2$ with $c\in\N$. This solution is
found by going back to the argument for construction (I) and
considering the coefficient of $t^{r+s-2}$ in $H(t)$.

\nn{IX} $x=2d+3$ \n Similarly, if we look at the coefficient
of $t^{r+s-3}$ in $H(t)$, then after removing from it the factor $r-s$
we find a quadratic equation,
giving the further integral point $P_d(2d+3,\,6d+7)=0$ if $6d+7$ is a
square.  Looking at the coefficients of $t^{r+s-\nu}$ for larger
values of $\nu$ leads to curves of higher degree (in fact, because of a
hidden symmetry of $H(t)$, to the same ones as in (VII) above) and
therefore to no new infinite families.

\nn{X} $x=2d-5$ or $2d-6$ \n We could also have obtained the solutions
(IV) by observing that for $x=2d-2\nu-1$ and $x=2d-2\nu-2$
construction (I) gives all but
$\nu$ of the roots of $P_d(x,\cdot)=0$.  The case $\nu=1$ corresponds
to (IV), while for $\nu=2$ we are left with a quadratic polynomial and
find
$$\align 6d^2-9d+4=e^2\quad&\Rightarrow\quad P_d(2d-5,\,5-6d\pm2e)=0\\
10d^2-15d+9=f^2\quad&\Rightarrow\quad
P_d(2d-6,\,10-10d\pm2f)=0\endalign$$
The conditions on $d$ are in each
case Pell-type equations having infinitely many solutions, the first
being $d=4,\,33,\,320,\,3161,\ldots$ and
$d=8,\,33,\,144,\,637,\ldots$, respectively. Here again, larger $\nu$
no longer give infinite families of solutions.

\bs We summarize the above constructions (excluding (X) and the
elliptic curves in (VII)) and the numbers of solutions they yield by
the table
$$\vbox {\hbox {\phantom{---------------}}
  \halign{\hfil\;#\;\hfil&\hfil\;#\;\hfil& \hfil\;#\;\hfil&
    \hfil\;#\;\hfil& \hfil\;#\;\hfil& \hfil\;#\;\hfil&
    \hfil\;#\;\hfil& \hfil\;#\;\hfil& \hfil\;#\;\hfil\cr
    (I)&\;(II)\;&\;(III)\;&(IV)&(V)&(VI)&(VII)&(VIII)&(IX)\cr
    \noalign{\vskip-.5 \baselineskip}\multispan9\hrulefill\cr
    $d^2+d$&$d$&1&2&\,[odd]\,
    &$\,2\e_{16d+1}\,$&$2\e_{48d+1}$&$\e_{2d+2}$&$\e_{6d+7}$\cr}}$$
where ``[odd]" means 1 if $d$ is odd and 0 otherwise and $\e_n$
denotes~1 if $n$ is a square and 0 otherwise.  To get the
constructions (VI) and (VII) to work simultaneously we need
$16d+1=a^2$ and $48d+1=b^2$ for some integers $a$ and $b$, so
$3a^2-b^2=2$. This is a Pell-type equation whose positive solutions
are given by $(b+a\sqrt3)^n=(1+\sqrt3)(2+\sqrt3)^n$ with $n\ge0$. The
common value of $(a^2-1)/16$ and $(b^2-1)/48$ is then integral if $n$
is congruent to 0 or 3 (mod 4) and odd if $n$ is congruent to 3 or 4
(mod 8), so for $n$ satisfying the latter congruence all seven
constructions (I)--(VII) apply and we get $d^2+2d+8$ integral
solutions of $P_d(x,y)=0$.  The set of values of $d$ obtained in this
way is not very dense (its only elements less than $10^{20}$ are
$d=105$, 1463, 148772396955, and 2072132179845), but it is still
infinite, proving Theorem 2.  We can also combine either (V) or (VII)
with (VIII) or (IX) instead of with each other to produce other
infinite Pell-like families, but this gives (for $d$ odd) only
$d^2+2d+7$ rather than $d^2+2d+8$ solutions, and we cannot combine
three of these constructions because this corresponds to finding
integral points on an elliptic curve over $\Q$ and there are only
finitely many.

\n{\bf Remarks.}
\subheading{1} It is very striking that in all of the above
constructions except for (IV) and (X) the values of $y$ are perfect
squares, and that the same holds for most (all but 3) of the
``sporadic" solutions listed in [4].  From a Diophantine point of
view, replacing the equation $P_d(x,y)=0$ by $P_d(x,y^2)=0$ makes the
problem incomparably harder to solve (for instance, already for $d=2$
the original equation is easy and has infinitely many solutions, while
the latter has only finitely many and the problem of finding them is
difficult), so that it is downright perverse to throw away the extra
information and list the solutions found merely as solutions of the
easier problem. The reason that this was nevertheless done in [4] and
here is not so much in order to capture the two extra zeros in (IV),
but because we are looking for examples of polynomials with many zeros
relative to their degree, and replacing $y$ by $y^2$ in $P_d(x,y)$
doubles the degree.  In other words, in general there are fewer and
fewer rational or integral points on curves as the degree (or genus)
goes up, but for these special polynomials the opposite is happening
and it is therefore advantageous to forget that $y$ is usually a
square.  Nevertheless, it seemed reasonable to supplement the search
described in [4] (which found all solutions with $d\le12$,
$|x|\le1000$) by a systematic search for integral zeros of
$P_d(x,y^2)=0$.  A search for all zeros in the range $d\le50$, $0\le
y\le 1000$ led to the discoveries of some of the above families and
produced the following zeros which do not belong to any of the
families (I)--(IX):
$$\align \quad(d,\sqrt y,x)\=&
(2,6,66),\;(2,91,1521),\;(2,91,15043),\;(3,5,67),\\
&(3,35,345),\; (7,4,98),\;(17,6,514),\;(18,21,67),\\
&(18,55,67),\;(22,5,67),\;(22,5,465),\; (31,6,66),\\ 
&(31,6,932),\; (31,11,67),\; (31,23,67),\;(31,94,132),\\ 
&(35,94,132),\; (42,4,98),\; (42,4,576),\;  (43,55,177)
\endalign$$
with no further discernible patterns.


\subheading{2} Both in [4] and in the introduction to this paper, the
emphasis has been on integral solutions of $P_d(x,y)=0$ or other
polynomial equations in two variables.  Actually, there is no real
distinction in this context between rational and integral solutions,
if we not quantify things by putting some restriction on the heights
of the polynomials, because if an equation $P(x,y)=0$ of degree $d$
has $\ge C$ rational solutions, then the rescaled equation
$N^dP(x/N,y/N)=0$, where $N$ is any common denominator of these
solutions, clearly has $\ge C$ integral solutions. For the particular
family of polynomials $P_d$, the large number of integral solutions
was so striking that it seemed a pity to throw away this information
by replacing ``integral" by ``rational" in the statement of the
theorems, especially as these polynomials have relatively small height
and this property would be destroyed by too vigorous a rescaling.
Nevertheless, for the sake of completeness and to have a clear
conscience we should also look for rational solutions.  A small
computer search (specifically, a search for all solutions of
$P_d(x,\,a/b)=0$ or $P_d(x,\,a^2/b^2)=0$ with $3<d\le12$, $2\le
b\le20$, and $|a|\le1000$, the equations $P_2=0$ and $P_3=0$ with
infinitely many solutions being omitted) yielded only one additional
family, \nn{X} $P_d\bigl(d-\frac34,\,\frac14\bigr)=0\;$ for $d$ odd \n
(whose proof by residue calculus we omit), together with the handful
of sporadic solutions:
$$
\align d=4:&\quad(x,y)\=\bigl(\tfrac53,\,-\tfrac13\bigr),\;
\bigl(-\tfrac{10}{11},\,-\tfrac{76}{11}\bigr),\;
\bigl(\tfrac{71}{11},\,\tfrac{71}{11}\bigr),\;
\bigl(\tfrac{505}{121},\,\tfrac{25}{121}\bigr),\;\\
d=5:&\quad(x,y)\=\bigl(\tfrac7{17},\,-\tfrac{43}{17}\bigr),\;
\bigl(-\tfrac5{19},\,-\tfrac{81}{19}\bigr),\;
\bigl(\tfrac{124}{19},\,\tfrac{124}{19}\bigr).\endalign$$
Two of these
are easy to explain and do not generalize (the polynomial $P_d(x,x)$
vanishes at $x=0,\,1,\,4,\ldots,\,[\sqrt{2d-1}]^2$, and for $d=4$ or 5
this leaves room for only one further root, which must then be
rational) and all of them have $d\le5$, so this data suggests that the
special equations $P_d(x,y)=0$ indeed have almost no non-integral
rational solutions. Nevertheless, by using the new family~(X) we can
present the following minuscule improvement of the previous results:
\proclaim{Theorem 4} The equation $P_d(x/4,\,y/4)=0$ has at least
$d^2+2d+5$ integral solutions for any odd $d$ and at least $d^2+2d+9$
integral solutions for infinitely many values of $d$. \endproclaim



\heading\S5. Acknowledgements\endheading

We would like to thank A. Bremner for spotting the extra points (V)
discussed in~\S4. The first author would  like to
thank the NSF, TARP and the Alfred P.~Sloan
Foundation for financial
support. The  second  author would like to thank the NSA for financial 
support.

\heading References\endheading
\noindent
[1] Bremner, A. Math Reviews, 2000b:14025, AMS.\medskip \noindent
[2] Caporaso, L.{\it Counting rational points on algebraic curves},
Number theory, I (Rome, 1995). 
Rend. Sem. Mat. Univ. Politec. Torino {\bf 53} (1995), 223--229. 
\medskip \noindent
[3] Elkies, N. {\it Curves with many points}, preprint available at
\newline
{\tt http://www.math.harvard.edu/~elkies/misc.html}
\medskip \noindent
[4] F. Rodr\'{\i}guez Villegas and J. F. Voloch,
{\it On certain plane curves with many integral points},
 Experimental Math.~{\bf 8} (1999), 57--62.
\medskip \noindent
[5] Ruppert, W., {\it Solving algebraic equations in roots of unity},
J. Reine Angew. Math. {\bf 435} (1993), 119--156. 
\medskip \noindent
[6]  St\"ohr, K-O. and Voloch, J.F.,
{\it Weierstrass Points and Curves over Finite Fields},
 Proc. London Math. Soc.(3) {\bf 52} (1986), 1--19 

\medskip\n   Dept. of Mathematics, Univ. of Texas, Austin, TX 78712, USA
\newline\noindent  e-mail: villegas\@math.utexas.edu, voloch\@math.utexas.edu
\n Max-Planck-Institut f\"ur Mathematik, D-53111 Bonn, Germany
\newline\noindent e-mail: zagier\@mpim-bonn.mpg.de 

\end