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.
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.
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
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 .
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.
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?