# Boolean Solutions to Polynomials Modulo a Prime

* Chevalley-Warning-Ax type theorems for the number of boolean solutions of a polynomial modulo a prime *

Carl Pomerance is a famous computational number theorist. He has done many wonderful things, including inventing the quadratic sieve factoring algorithm (QS), and playing an important role in factoring methods of all kinds. As you may know from previous posts, I believe that there is a chance that factoring is in polynomial time. But the best algorithms known today are based on the work of Pomerance and his colleagues, and have super-polynomial but sub-exponential running times. In particular, the currently fastest known general method is the number field sieve (NFS).

I do not plan to go into details on this today, but rather relate a story of the role theory played in the discovery of NFS. Then, I will switch gears and discuss technology from another part of number theory that is used to count the number of solutions to polynomial equations. Today is number theory day.

Carl and I were at the first ANTS conference which was held at Cornell in 1994: this is now a biennial conference on algorithmic number theory. The first night, at the cocktail party, Carl grabbed me and insisted that he get me a drink to thank me. I accepted the drink, in those days I still “drank adult beverages,” and I asked what did he need to thank me for? Well it was nothing that I had done. Nothing. But it was the general field of theory, and in particular the concept of *asymptotic analysis* that he was excited about. He had to thank some theorist and since I was one of the few at the meeting, he picked me. He then proceeded to explain what this was all about.

He had recently been on a long airplane flight on the way to give an invited address on the state-of-the-art of factoring. Since it was a long flight, he had plenty of time to review his planned talk. One thing he started to ponder was a recent–at the time–algorithm due to John Pollard. He had not planned to say anything about John’s new algorithm, because it could only factor numbers that were in a very special form. Carl’s talk was on factoring arbitrary numbers, so it would be natural to skip this new development.

However, Pomerance said he started to imagine what if Pollard’s technology could be made to work for any number? Not just special ones. He wondered what would the running time be of such an algorithm? Most factoring experts are “from Missouri” they need to see results, actual computations, to believe in them. The puzzle that Carl faced, sitting on the plane, was that he had no way to run a general purpose Pollard algorithm. Not because of a lack of computer, but because there were missing steps, lemmas, tricks, that were needed to make a real factoring algorithm. You cannot try an algorithm that is not an algorithm–computers cannot execute ideas.

But wait, he thought. What if these missing pieces could all be found, how well would the hypothetical new algorithm perform? This he could solve using asymptotic analysis. A quick estimate of the running time, showed Carl that if all the pieces could be found, the resulting factoring algorithm would be a huge improvement over the QS method. Huge. He was excited by this “discovery.”

As soon as Carl left the plane he ran to a pay phone, this was before cell phones were everywhere, and called Arjen Lenstra. He explained to Lenstra what he had worked out, and they agreed then and there that they would start immediately to try to extend Pollard’s method to all numbers. Eventually, this happened and the method is now called the NFS. See this for Carl’s comments on history of the NFS.

This story of discovery is a pretty good argument for O-notation and asymptotic analysis. I enjoyed my drink, and I thanked Carl on behalf of all theorists. Now on to another aspect of number theory.

** Polynomial Equations **

One of the coolest theorems about polynomial equations is the Chevalley-Warning Theorem:

Theorem:Suppose that is a polynomial of degree and is a prime. Then, the number of solutions of

is divisible by provided .

Note, the degree of a polynomial in many variables is the *total degree*. Thus, the degree of

is , since the term has total degree . More generally, the total degree of a term

is equal to provided . And the total degree of a polynomial is the maximum of the degree of all its non-zero terms.

This is a wonderful theorem with many applications throughout theory. There is a related theorem that is also quite useful: sometimes it is called the Chevalley-Warning-Ax Theorem,

Theorem:Suppose that is a degree polynomial and is a prime. Then, the number of solutions of

is either or is at least provided .

Both of these can be extended to systems of equations.

** Boolean Case **

While these theorems are quite useful, as computer scientists, we often are interested in the number of solutions of a polynomial equation that are restricted to – values. Thus, a natural question is what happens to the above theorems when we ask: how many *boolean* solutions are there to,

where by boolean we mean that each ?

There is a simple idea that almost works. Look at the equation

where . Notice that the argument of is always boolean modulo . Any solution of is a boolean solution to . But multiple solutions of give rise to the same boolean solution of . One can see that if has N solutions, then has at least boolean solutions. But this is a pretty weak result. The difficulty is that there is one pre-image of and pre-images of . Thus, this method yields a poor estimation on the number of boolean solutions.

To get a really good estimation we need a function that takes on and the same number of times. Then, there would be at least

boolean solutions. This is a much better estimation. The trouble is, of course, that if is an odd prime, there is no such function.

Put simply is not an integer for any odd prime–how inconvenient. It reminds me of what happen to a good friend (G), who is not a theorist. He once attended a talk by a famous number theorist (T). I will use initials to protect the guilty and the innocent, both. You get to decide, however, which is which. Note T is *not* equal to “Pomerance.” All throughout the talk there were statements by T like,

Let be a odd prime, and thus

or

Since is an odd prime, it follows that

My friend G finally raised his hand and asked, “what is an *odd* prime?” The number theorist T said, in a not very nice manner, “not .”

However, we can overcome the fact that primes are usually odd, and still prove the following theorem:

Theorem:Suppose that is a degree polynomial and is a prime. Also assume that . Then, the number of boolean solutions of

is either or is at least .

Here is a simple application of this theorem to prove a well-known result. Suppose that is a polynomial that computes the “and” function modulo . That is

if and only if the boolean vector is all ‘s. Then, the degree of must be .

** Proof **

For completeness I will include a sketch of the proof of this bound on the number of boolean solutions. The result, and more, is in the very pretty paper by Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlak, and Denis Therien.

The proof is an application of the Erdös probabilistic method.

*Proof:* Suppose that is the polynomial that we wish to show has many boolean solutions modulo . Let be the set of all

boolean vectors so that . Note, we can assume that is non-empty.

Define . Also define to be

The degree of is in the variables .

For a boolean vector , notice that the argument to the function is boolean modulo p. For a fixed , let be the number of solutions to

We want to be the number of solutions which are unique modulo . One can think of as the number of solutions from the set .

is at least one, because of our assumption. By using the Chevalley-Warning-Ax theorem on , it follows that . We next compute the value of , and use this to bound the size of . The expectation is over all the -length boolean vectors .

For a fixed boolean vector , define . The value of is equal to

where is a boolean solution to and is the number of so that .

But notice that, every vector maps to any given boolean vector with probability . Since there are allowed ‘s, by taking expectation over , we get that is equal to

Thus, by probabilistic method,

which implies that

Finally, this yields the claimed estimation, and finishes the proof of the theorem.

** Open Problems **

As powerful as the Chevalley-Warning-Ax family of theorems are, they say nothing about composite moduli. To make progress on some of the really vexing problems in theory we need to understand the number of boolean solutions to polynomial equations modulo a composite number. This is completely unknown territory. Can anyone shed some light on this problem?

Christos Papadimitrious defined a nice complexity problem related to this theorem which he called “CHEVALLEY MOD p”. Given a system Q of polynomial equations mod p (explicitly as lists of monomials) with degree < # of variables, and a root of Q mod p, find another toot. This must exist by the theorem. The theorem has some strictly graph-theoretic consequences. The problem for p=2 is in PPA, the undirected version of PPAD, but is not known to be complete. The paper is the same one where he asked about the PPAD-completeness of the Nash equilibrium problem..

How can we find solutions to a quadratic equation

ax^2 + bx + c = 0 mod P

P is a prime, and a,b,c < 0 a not equal to 0.

Also all roots must be less than P (maybe sometimes infinite solutions are possible if not for this restriction e.g x^2 = 0 mod 2 )

Thanks.

There are fast methods for solving equations modulo a

prime.Rabin is one source. Here is a link to a paper.The key insight is that because you are working over a finite field, you can use Fermat Little Theorem and randomness to solve any low degree equation.

I hope this helps.

Thanks for the reply. I couldn’t access that paper, as I dont have a link. Can you elaborate about that method in details.

Here is the central idea. Suppose that we have a polynomial

and we wish to find a root, if one exists, modulo a prime . The cool idea is this suppose that has a solution, then it will have two solutions: call them and . Thus, , where means congruent modulo from now on.

The question is how to find and . Clearly, if we find one, then we have the other. So how do we find one?

Suppose for the moment that and where different in the following sense: was a quadratic residue modulo and was not. Recall a quadratic residue means that . This “difference” allows us to find .

The key idea is to note that the following is true by Fermat’s Little Theorem:

for any in . But, is odd–otherwise the problem is trivial–so it follows that the quadratic residues satisfy

and the non-quadratic residues do not.

The next step is to take the polynomial and the polynomial and form their greatest common divisor (gcd). This can be done efficient even if is large: use repeated squaring to get modulo . Finally, the gcd can only be , , , or . But, since is a quadratic residue and is not, it can be shown that the only case possible is .

Thus, we have found a factor of in polynomial time. Cool. You might ask what if both and are quadratic residues? Then, the gcd will be useless, it will be . The trick now is to use an idea of Rabin. We randomly form a new polynomial where is a random residue modulo . It is not hard to prove that this new polynomial is likely to have one root a quadratic residue and one not. In this was we can get the roots of a quadratic polynomial.

I hope this helps.

Err, i meant a,b,c < p and a not equal to zero.

Thank you very much for your time.

This question about a Composite Number N. Out of town I watch Leonardo s ‘bunnies'(great history was indian few centuries ago);got the impression that his function gets an invariant

crunch and is corrupted formally for a while. Factor 8 helps deduce an holding number.

Have to call myself William the Conquerer a while…..funny day all round so far….