# Number of solutions of an equation over finite fields

Does anyone know of any result that deals with the following problem of counting the number of solutions of a certain algebraic equation over a finite field?

Let $p$ be an odd prime and $(a,b,c,d)\in\mathbb{F}_p^4$. How many solutions does the following equation have:

$$ab^2 + cd^2 = bc^2 + da^2.$$

And more generally, if $1\le m,n\le q-1$ are two integers, how many solutions does the equation $$a^mb^n + c^md^n = b^mc^n + d^ma^n$$ have?

-

The projectivization of your first equation is a cubic surface which (unless I made a mistake) is smooth for $p>5$. So the number of solutions of the projectivized equation is of the form $N=p^2+\alpha p + \beta$ where $\alpha, \beta$ range over a short finite list of single digit integers. The full list is, I think, in Manin's book "Cubic forms" or in Swinnerton-Dyer "The zeta function of a cubic surface over a finite field", Math Proc Cam Phil Soc 1967. Your first equation then has $pN+1$ solutions.

Whenever the projectivization of your second equation is smooth, you get $p^3+O(p^2)$ solutions by general facts but the answer may not be as clean as the first one.

-
$(p-1)N+1$ solutions, that is. And I think $\beta$ is always $1$ for a smooth cubic.  The general case is still a Delsarte (quadrinomial) surface, so the number of solutions can be expressed in terms of Gauss sums, but it won't be as clean as for $(m,n)=(1,2)$. – Noam D. Elkies Nov 27 '12 at 0:53
Yes, thanks, Noam. – Felipe Voloch Nov 27 '12 at 1:27
Can any of you point to an elementary source where this is described. I have zero exposure to algebraic geometry. – azazello Nov 27 '12 at 3:23
– Franz Lemmermeyer Nov 27 '12 at 13:03
When it's not smooth, you should still get $p^3+ O(p^{5/2})$ as long as it's irreducible. – Will Sawin Nov 27 '12 at 15:26

The first equation can be worked out in an elementary way. Counting the solutions where $b=0$ or $d=0$ is straightforward. So let's consider the case $bd\ne0$. The equation rewrites as$$d(a-\frac{b^2}{2d})^2+b(c-\frac{d^2}{2b})^2=\frac{b^5+d^5}{4bd}.$$ So, given given $b$ and $d$, and upon setting $a=\frac{x+b^2}{2d}$, $c=\frac{y+d^2}{2b}$, and replacing $d$ with $-d$, we have to count the $x,y\in\mathbb F_p$ with $$bx^2-dy^2=b^5-d^5.$$ If $b^5-d^5\ne0$, we have an ellipsis with $p-1$ points if $b/d$ is a square, and $p+1$ points otherwise. The former case happens $(p-1)(p-3)/2$ times, and the latter case $(p-1)^2/2$ times. In the remaining case $b^5-d^5=0$ we have solutions $x, y$ if and only if $b/d$ is a square, and the number of solutions is $2p-1$ for each such pair $b,d$.

Indeed, carying out the count we, we find that there are all together $(p^2 + 6p - 6)p$ solutions if $p\equiv1\pmod{10}$, and $(p^2 + 2p - 2)p$ solutions if $p\not\equiv1\pmod{10}$.

-

I have a somewhat different take from Peter Mueller's on an elementary way of solving

$$ab^2 + cd^2 = bc^2 + da^2.$$

To begin with, it's easy to see that there are $1+4(p-1)+2(p-1)^2+4(p-1)^2 = 6p^2-8p+3$ solutions with $abcd=0$. (There is 1 solution with four 0's, $4(p-1)$ solutions with three 0's, $2(p-1)^2$ solutions with two 0's, and $4(p-1)^2$ solutions with one 0.) So it remains to count the number of solutions with $abcd \not= 0$.

Apropos of nothing obvious for the moment, it's worth noting that the equation

$$A+B = C+D$$

(in the finite field) has $1+0+6(p-1)+4(p-1)(p-2) = 4p^2 - 6p +3$ solutions with $ABCD=0$ and hence $p^3-4p^2+6p-3$ solutions with $ABCD \not= 0$.

Getting back to the lowercase equation, if $abcd\not=0$, then each variable is a power of a generator, say $g$, of the finite field: $a=g^\alpha$, $b=g^\beta$, $c=g^\gamma$, and $d=g^\delta$. If we write the equation in these terms and divide everything by $g^{\alpha+\beta+\gamma+\delta}$, we have

$$g^r + g^s = g^t + g^u,$$

where

$$r=\beta-\gamma-\delta$$ $$s=\delta-\alpha-\beta$$ $$t=\gamma-\delta-\alpha$$ $$u=\alpha-\beta-\gamma$$

This last batch of equations is really a linear system of congruences $\mod(p-1)$. The linear transformation turns out to have determinant with absolute value 5. Consequently, if 5 does not divide $p-1$, i.e, if $p\not\equiv1 \mod5$, then there's a one-to-one correspondence between points $(\alpha,\beta,\gamma,\delta)$ and $(r,s,t,u)$. But in that case, we may as well think of the equation $g^r + g^s = g^t + g^u$ as the equation

$$A+B=C+D$$ with $ABCD\not=0$. As we casually noted earlier, there are $p^3-4p^2+6p-3$ such solutions. Combining this with the $6p^2-8p+3$ solutions with $abcd=0$, we get a total count of

$$(p^3-4p^2+6p-3)+(6p^2-8p+3) = (p^2+2p-2)p$$

solutions when $p\not\equiv1\mod5$, in agreement with what Peter Mueller found. (A small confession: I was initially perplexed by the difference between his mod 10 and my mod 5. A larger confession: Peter's results were a huge help in catching and correcting mistakes I made in my own calculations.)

I'm a bit mired at this point in how to deal with the case $p\equiv1\mod5$, so I'm going to leave things unfinished for now. I'll try to come back to it if I can find more time. Alternatively, if someone sees a slick way to finish and/or streamline things, please post it, either in comments or as a separate answer.

Added 11/30/12: I haven't had any luck making this approach work when $p\equiv1\mod5$, but Peter Mueller's comment has prompted me to go back and look more closely at the determinant of the linear transformation I used. As Peter noted, in the general case ($a^mb^n + c^md^n = b^mc^n + d^ma^n$), the determinant is $n^4-m^4$. That's actually for the linear transformation that turns $g^{m\alpha+n\beta}+g^{m\gamma+n\delta}=g^{m\beta+n\gamma}+g^{m\delta+n\alpha}$ into $g^r+g^s=g^t+g^u$. Note that when $m=1$, $n=2$, $n^4-m^4=15$, which suggests there's a problem not just when $p\equiv1\mod5$, but also when $p\equiv1\mod3$. That is, in fact, what I initially did. But given the results in Peter's answer, I suspected there ought to be a way of getting rid of the 3. I intuited that dividing by $g^{\alpha+\beta+\gamma+\delta}$ would help, and indeed it did, but I didn't really think about why.

Here's what's really going on. In general, you can divide by $g^{h\alpha+j\beta+k\gamma+\ell\delta}$ for any choice of $h,j,k,\ell$. Doing so gives a determinant (up to sign) of

$$n^4-m^4 -(h+j+k+\ell)(n-m)(n^2+m^2) = (n-m)(n^2+m^2)(n+m-h-j-k-\ell).$$

It's clear that one can choose $h,j,k,$ and $\ell$ to make the last factor $\pm1$; there's no particular need to make them all equal, but when $m+n$ is odd it's an appealing option.

The upshot is that the approach falters only for primes $p$ for which $p-1$ has a factor in common with $(n-m)(n^2+m^2)$. Whether it can be coaxed into saying something useful in the cases where it falters, I still don't know.

-
I don't see right now how to deal with $5$ dividing $p-1$. But what is probably interesting is that your approach can handle some cases for general $m$ and $n$: The determinant in this case is $n^4-m^4$. So if $m+n$ is odd, then there are infinitely many primes $p$ such that $p-1$ is prime to $n^4-m^4$, so the number of $\mathbb F_p$-points can be determined. – Peter Mueller Nov 28 '12 at 10:20