The following observation makes me quite confused when I am trying to count the number of solutions of the equation:


$$\sum\_{k=0}^{M}{M \choose k}^2x^k=0$$


on finite fields $\mathbb{F}\_p$ with the prime number $p>3$ and $M=(p-1)/2$.


**Observation:** I tried the count the number of solutions with Mathematica. To my surprise, the number of solutions coincides with three times the sequence [in OEIS](https://oeis.org/A165951).


**Question:** I think what I observed is true for the first 100 primes. Is it true for all prime numbers $p>3$?



Congruence equation and quadratic residue
When $p \equiv 1 \bmod 4$, both expressions are $0$ and I understand why. For $p \equiv 1 \bmod 4$, the number $k$ is a QR iff $p-k$ is. Pairing off $k$ and $p-k$, the OEIS expression is
$$\frac{1}{p} \left( \frac{p\cdot \# \mbox{QRs}}{2} - \frac{p \cdot \# \mbox{non-QRs}}{2} \right) = 0.$$


Meanwhile, values of $x$ in $\mathbb{F}\_p$ are in bijection with elliptic curves $E$ over $\mathbb{F}\_p$ and a chosen bijection between the $\mathbb{F}\_p$-points of the $2$-torsion $E[2]$ and $(\mathbb{Z}/2)^2$. As js21 explains, we have $\sum \binom{(p-1)/2}{k}^2 x^k = 0$ if and only if $E$ is supersingular. So we need to show that (when $p \equiv 1 \bmod 4$) there are no supersingular elliptic curves $E$ whose $2$-torsion is entirely defined over $\mathbb{F}\_p$.


An supersingular elliptic curve always has $p+1$ points over $\mathbb{F}\_p$, so if $p \equiv 1 \bmod 4$ then $\#E(\mathbb{F}\_p) \equiv 2 \bmod 4$ and cannot have $(\mathbb{Z}/2 \mathbb{Z})^2$ as a subgroup.




---


I found the key fact for treating $p \equiv 3 \bmod 4$ in [Theorem 2.7 of a paper by Delfs and Galbraith](http://arxiv.org/abs/1310.7789). (See also [Galbraith's slides](http://iml.univ-mrs.fr/ati/geocrypt2013/slides/galbraith.pdf).) If $E$ is a supersingular curve defined over $\mathbb{F}\_p$, then Frobenius obeys $\mathrm{Frob}^2 = -p$ and $\mathrm{End}(E) \cap \mathbb{Q}[\mathrm{Frob}]$ is either $\mathbb{Q}\left( \tfrac{1-\sqrt{-p}}{2} \right)$ or $\mathbb{Q}(\sqrt{-p})$. In the former case, Delfs and Galbraith say that the curve is "on the surface", otherwise it is "on the floor". (The metaphor is subterranean, so the floor is below the surface.) 


As Theorem 2.7 says, curves on the surface always have three $2$-isogenies from them which are defined over $\mathbb{F}\_p$, so their $2$-torsion is entirely defined over $\mathbb{F}\_p$, while curves on the floor always have one $2$-isogeny, so their $2$-torsion is not entirely defined over $\mathbb{F}\_p$. 
One can see this directly: $\mathrm{End}(E) \cap \mathbb{Q}[\mathrm{Frob}]$ is 
$\mathbb{Q}\left( \tfrac{1-\sqrt{-p}}{2} \right)$ iff $[2]$ divides $1-\mathrm{Frob}$, if and only if the kernel of $[2]$ (namely $E(2)$) is contained in the kernel of $1-\mathrm{Frob}$ (namely $E(\mathbb{F}\_p)$).


So roots of your polynomial come from curves on the surface -- generally, $6$ roots per curve, but fewer for $j=0$ or $1728$. By a theorem of Deuring, the number of curves on the surface is the same as the number of ideal classes in $\mathbb{Q}\left( \tfrac{1-\sqrt{-p}}{2} \right)$, namely, $h(-p)$. 


Combine all of this with Dirichlet's class number formula, and get all the details right, and you should have a proof.




---


Examples: $p=83$. The class number is $3$ (see [here](http://www.numbertheory.org/classnos/)) as is the OEIS sequence. Since $p \equiv 3 \bmod 8$, there are $2 \cdot 3 = 6$ $j$-invariants of supersingular curves defined over $\mathbb{F}\_{83}$: $0$, $17$, $28$, $50$, $67$, $68\! \equiv\! 1728$. Each of them has two non-isomorphic twists over $\mathbb{F}\_{83}$, so $12$ curves over $\mathbb{F}\_{83}$ in all. The $2$-isogenies between them are shown on [Galbraith's slide 27](http://iml.univ-mrs.fr/ati/geocrypt2013/slides/galbraith.pdf). Both of the twists of $j=50$, and one of the twists of $j=1728$, have three $2$-isogenies from them, so $E[2]$ defined over $\mathbb{F}\_{83}$. 


The roots of your equation over $\mathbb{F}\_{83}$ are $2$, $18$, $24$, $39$, $42$, $45$, $60$, $66$, $82$. Of these roots, $2$, $42$ and $82$ correspond to $j=1728$. The other six correspond to one of the two twists with $j=50$; the other twist is $-y^2 = X(X-1)(X-x)$ where $x$ takes one of these six values.


$p=103$: This time, the class number is $5$ and $p \equiv 7 \bmod 8$ so there are $5$ supersingular $j$-invariants in $\mathbb{F}\_{103}$: $23$, $24$, $34$, $69$ and $80 \! \equiv \! 1728$. Each of them has two twists. You can see the $2$-isogenies on Slide 33. In particular, the full $2$-torsion is defined over $\mathbb{F}\_{103}$ for both twists of $j=23$ and $j=69$, and for one of the twists of $j=1728$.


The roots of your polynomial are $2$, $12$, $25$, $28$, $30$, $33$, $43$, $52$, $61$, $71$, $74$, $76$, $79$, $92$, $102$. As $x$ ranges over these values, $y^2 = X(X-1)(X-x)$ covers $j=1728$ and one of each of the twists of $j=23$ and $j=69$, and $-y^2 = X(X-1)(X-x)$ covers the other twist of the latter cases.


