For example, how to solve the equation $\sum^{p-1}_{i}x_{i}^{2}=0$ in $F_{p}$? This is not a homework problem. I think it should have a definite answer, so not an open problem. I just don't know how to solve it.
$\begingroup$
$\endgroup$
7
-
$\begingroup$ Thanks for the answers! I want to ask is there any good bound for the number of solutions(sorry forgot to post in first place)? $\endgroup$– KerryCommented Apr 6, 2010 at 21:57
-
1$\begingroup$ The number of solutions up to simultaneous scaling by a non-zero element of $\mathbb{F}_p$ (if p>3) should be $\frac{p^{p-2}-1}{p-1}$ if $p=1 \pmod{4}$ and $\frac{p^{p-2}-1}{p-1}+p^{\frac{p-3}{2}}$ if $p=3 \pmod{4}$. $\endgroup$– damianoCommented Apr 6, 2010 at 22:15
-
$\begingroup$ damiano, how can you show that? I did some numerical work and conjectured it but I have no idea how such things are proven. $\endgroup$– Michael LugoCommented Apr 6, 2010 at 22:22
-
2$\begingroup$ The way I computed it, was by using the Weil conjectures. In this case you can argue your way through using the fact that as soon as you have a solution you can find all the remaining ones by projection away from it (like in Bjorn's answer). What remains to show is what happens when the projection never contains a line (case 1) or when it does contain at least one (and hence two) (case 2). $\endgroup$– damianoCommented Apr 6, 2010 at 22:28
-
2$\begingroup$ The number of solutions was first worked out by Victor Amande Lebesgue (the number theorist, not the Lebesgue famous for his integration theory) in 1838 and was used for proving the quadratic reciprocity law. A simplified version of his proof was recently published by W. Castryck, A shortened classical proof of the quadratic reciprocity law, Amer. Math. Monthly (2007). $\endgroup$– Franz LemmermeyerCommented Apr 7, 2010 at 9:14
|
Show 2 more comments
3 Answers
$\begingroup$
$\endgroup$
6
There is a deterministic polynomial-time algorithm for finding solutions to diagonal equations of degree less than or equal to the number of variables over finite fields. See Christiaan van de Woestijne's thesis.
(A solution of your example equation can be found much more simply, however: try small integers, not necessarily distinct... . And for quadratic forms, the other solutions can be found by drawing lines through the point and intersecting with the quadric hypersurface: there will either be one more intersection point, or a whole line of points.)
answered Apr 6, 2010 at 21:45
-
1$\begingroup$ Hi! I really thanks for the link of the paper. I will read it. $\endgroup$– KerryCommented Apr 6, 2010 at 22:03
-
3$\begingroup$ Sorry for the impertinent remark, but a deterministic algorithm for finding all solutions to an equation in the variables $x_1,\ldots,x_n$ over $\mathbb{F}_q$ is obtained by plugging in all $q^n$ possible values and counting how many give solutions. I can well believe the van de Woestijne's algorithm is better than this, but can you say exactly how? $\endgroup$ Commented Apr 6, 2010 at 23:07
-
$\begingroup$ I don't really understand the part "the other solutions can be found by drawing lines through the point and intersecting with the quadric hypersurface: there will either be one more intersection point, or a whole line of points", I will read the paper. $\endgroup$– KerryCommented Apr 6, 2010 at 23:35
-
$\begingroup$ @Pete: Good point! I forgot to write the words "polynomial time" (not to mention "over finite fields"!) It's fixed now. $\endgroup$ Commented Apr 7, 2010 at 0:00
-
1$\begingroup$ To amplify on what Bjorn said -- if you have one solution you can use it to rationally parametrize all others via pencils of line. So the real problem is there a fast (i.e. polynomial time algorithm in log of the size of the finite field) algorithm to find one point. It turns out that if you are given a quadratic non-residue (generator of the 2-sylow subgroup of $F^*$) then there is a deterministic poly time algorithm to find a solution. This is still an open problem but van de Woestijne found a clever way around this for diagonal forms. $\endgroup$ Commented Apr 7, 2010 at 1:08
$\begingroup$
$\endgroup$
1
You want to know if the sum of $p-1$ squares can be equal to 0 mod $p$. I'll assume that you don't want to allow the trivial (all-zeroes) solution.
If $k$ is a quadratic residue mod $p$, not equal to $1$, then this is simple; take $x_1$ such that $x_1^2 = k$, take $x_2 = \ldots = x_{p-k+1} = 1$, and take $x_{p-k+2} = \ldots = x_{p-1} = 0$.
So the equation $x_1^2 + \cdots + x_{p-1}^2 = 0$ has solutions mod $p$ as long as there exists a quadratic residue mod $p$ which is not equal to $1$. The number of quadratic residues mod $p$ is $\phi(p)/2$, where $\phi$ is Euler's totient function; if $\phi(p)/2 \ge 2$, or $\phi(p) \ge 4$, then there is at least one non-$1$ quadratic residue mod p. Now for a prime, $\phi(p) = p-1$, so that means your equation has solutions when $p-1 \ge 4$, i. e. when $p \ge 5$. We can check by brute force that $x_1^2 = 0 \mod 2$ and $x_1^2 + x_2^2 = 0 \mod 3$ have only the trivial solutions. So the equation $x_1^2 + \cdots + x_{p-1}^2 = 0 \mod p$ has nontrivial solutions for all primes $p \ge 5$.
(Basically, this is a more explicit version of the second paragraph of Bjorn Poonen's answer.)
answered Apr 6, 2010 at 21:46
-
1$\begingroup$ In fact, what I was trying to hint at by "small integers" was your solution with k=4 (for p at least 5); i.e., 2^2 + 1^2 + 1^2 + ... + 1^2 + 0^2 + 0^2 = p. (No need to count quadratic residues!) $\endgroup$ Commented Apr 6, 2010 at 22:56
$\begingroup$
$\endgroup$
1
This answer is tangential in the sense that it is speaking of the existence of solutions rather than counting them all. But I rather suspect that you would find this interesting.
Suppose you have a quadratic form in at least thee variables over $\mathbb F_p$. Then the Chevalley-Warning Theorem would tell you that it has a nontrivial solution.
If you want to check out more, I refer you to the first chapter of J.-P. Serre's "A Course in Arithmetic", rather than the wikipedia page linked above.
-
$\begingroup$ Hi! I am reading the book "A course in arithmetic". I finished about 4 chapters by now. Thanks! $\endgroup$– KerryCommented Jul 21, 2010 at 3:23