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 ${f(x_{1},\dots,x_{n})}$ is a polynomial of degree ${d}$ and ${p}$ is a prime. Then, the number of solutions of

$\displaystyle f(x_{1},\dots,x_{n}) \equiv 0 \bmod p$

is divisible by ${p}$ provided ${n > d}$.

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

$\displaystyle 8xyz + 3x^{2}yw^{2} - 17yz^{3}$

is ${5}$, since the term ${ 3x^{2}yw^{2}}$ has total degree ${5}$. More generally, the total degree of a term

$\displaystyle cx_{1}^{d_{1}}x_{2}^{d_{2}}\dots x_{n}^{d_{n}}$

is equal to ${d_{1} + d_{2} + \dots + d_{n}}$ provided ${c \neq 0}$. 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 ${f(x_{1},\dots,x_{n})}$ is a degree ${d}$ polynomial and ${p}$ is a prime. Then, the number of solutions of

$\displaystyle f(x_{1},\dots,x_{n}) \equiv 0 \bmod p$

is either ${0}$ or is at least ${p^{n-d}}$ provided ${n > d}$.

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 ${0}$${1}$ values. Thus, a natural question is what happens to the above theorems when we ask: how many boolean solutions are there to,

$\displaystyle f(x_{1},\dots,x_{n}) \equiv 0 \bmod p$

where by boolean we mean that each ${x_{i} \in \{0,1\}}$?

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

$\displaystyle f^{*}(x_{1},\dots,x_{n}) \equiv 0 \bmod p$

where ${ f^{*}(x_{1},\dots,x_{n}) = f(x_{1}^{p-1},\dots,x_{n}^{p-1})}$. Notice that the argument of ${f}$ is always boolean modulo ${p}$. Any solution of ${f^{*}}$ is a boolean solution to ${f}$. But multiple solutions of ${f^{*}}$ give rise to the same boolean solution of ${f}$. One can see that if ${f^{*}}$ has N solutions, then ${f }$ has at least ${N/(p-1)^n}$ boolean solutions. But this is a pretty weak result. The difficulty is that there is one pre-image of ${0}$ and ${p-1}$ pre-images of ${1}$. 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 ${0}$ and ${1}$ the same number of times. Then, there would be at least

$\displaystyle N/(p/2)^{n}$

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

Put simply ${p/2}$ 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 ${p}$ be a odd prime, and thus ${\dots}$

or

Since ${q}$ is an odd prime, it follows that ${\dots}$

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 ${2}$.”

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

Theorem: Suppose that ${f(x_{1},\dots,x_{n})}$ is a degree ${d}$ polynomial and ${p}$ is a prime. Also assume that ${n > d(p-1)}$. Then, the number of boolean solutions of

$\displaystyle f(x_{1},\dots,x_{n}) \equiv 0 \bmod p$

is either ${0}$ or is at least ${2^{n-d(p-1)\log p}}$.

Here is a simple application of this theorem to prove a well-known result. Suppose that ${f(x_{1},\dots,x_{n})}$ is a polynomial that computes the “and” function modulo ${3}$. That is

$\displaystyle f(x_{1},\dots,x_{n}) \equiv 0 \bmod 3$

if and only if the boolean vector ${x = (x_{1},\dots,x_{n})}$ is all ${1}$‘s. Then, the degree of ${f}$ must be ${\Omega(n)}$.

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 ${f(x_1,\ldots , x_n)}$ is the polynomial that we wish to show has many boolean solutions modulo ${p}$. Let ${S}$ be the set of all

$\displaystyle x = (x_1, \ldots , x_n)$

boolean vectors so that ${f(x) \equiv 0 \bmod p}$. Note, we can assume that ${S}$ is non-empty.

Define ${\psi(x_i, r_i) = r_i \cdot x_i^{p-1} + (1 - r_i) \cdot (1 - x_i^{p-1})}$. Also define ${g(x, r)}$ to be

$\displaystyle g(x,r) = f( \psi(x_1, r_1),\ldots , \psi(x_n, r_n))$

The degree of ${g}$ is ${d(p - 1)}$ in the variables ${x_{1},\dots,x_{n}}$.

For a boolean vector ${r}$, notice that the argument to the function ${f}$ is boolean modulo p. For a fixed ${r}$, let ${N_r}$ be the number of solutions ${x}$ to

$\displaystyle g(x, r) \equiv 0 \bmod p.$

We want ${N_r}$ to be the number of solutions which are unique modulo ${p}$. One can think of ${N_r}$ as the number of solutions from the set ${\{0, 1, 2, \ldots, p-1\}^n}$.

${N_r}$ is at least one, because of our assumption. By using the Chevalley-Warning-Ax theorem on ${g(x,r)}$, it follows that ${N_r \geq p^{n-d(p-1)}}$. We next compute the value of ${E[N_r]}$, and use this to bound the size of ${S}$. The expectation is over all the ${n}$-length boolean vectors ${r}$.

For a fixed boolean vector ${r}$, define $\Psi_{r}(x) = ((x_1, r_1), \ldots , (x_n, r_n))$. The value of ${N_r}$ is equal to

$\displaystyle \sum_{s\in S} |\Psi_r^{-1}(s)|$

where ${s\in S}$ is a boolean solution to $f \equiv 0 \bmod p$ and $|\Psi_r^{-1}(s)|$ is the number of ${x}$ so that $\Psi_r(x) = s$.

But notice that, every vector ${x \in \{0, 1, 2, \ldots, p-1\}^n}$ maps to any given boolean vector with probability ${1/2^n}$. Since there are ${p^n}$ allowed ${x}$‘s, by taking expectation over ${r}$, we get that ${E[N_r]}$ is equal to

$\displaystyle E[N_r] = \sum_{s\in S}(p/2)^n = |S| (p/2)^n$

Thus, by probabilistic method,

$\displaystyle |S| (p/2)^n \geq p^{n-d(p-1)}$

which implies that

$\displaystyle |S| \geq 2^n / p^{d(p-1)}$

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

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?

May 19, 2009 2:41 am

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

July 1, 2009 1:48 pm

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.

July 1, 2009 3:11 pm

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.

July 2, 2009 5:31 am

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

July 2, 2009 7:02 am

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

$\displaystyle f(x) = x^{2} + ax + b$
and we wish to find a root, if one exists, modulo a prime ${p}$. The cool idea is this suppose that ${f(x) \equiv 0 \bmod p}$ has a solution, then it will have two solutions: call them ${r}$ and ${s}$. Thus, ${f(x) = (x-r)(x-s)}$, where ${=}$ means congruent modulo ${p}$ from now on.

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

Suppose for the moment that ${r}$ and ${s}$ where different in the following sense: ${r}$ was a quadratic residue modulo ${p}$ and ${s}$ was not. Recall a quadratic residue means that ${r \equiv (r')^{2} \bmod p}$. This “difference” allows us to find ${r}$.

The key idea is to note that the following is true by Fermat’s Little Theorem: $\displaystyle w^{p-1} \equiv 1 \bmod p$
for any ${w}$ in ${\{1,\dots,p-1\}}$. But, ${p}$ is odd–otherwise the problem is trivial–so it follows that the quadratic residues satisfy $\displaystyle w^{\frac{p-1}{2}} \equiv 1 \bmod p$
and the non-quadratic residues do not.

The next step is to take the polynomial ${f(x)}$ and the polynomial ${g(x)=x^{\frac{p-1}{2}}-1}$ and form their greatest common divisor (gcd). This can be done efficient even if ${p}$ is large: use repeated squaring to get ${g(x)}$ modulo ${f(x)}$. Finally, the gcd can only be ${1}$, ${f(x)}$, ${x-r}$, or ${x-s}$. But, since ${r}$ is a quadratic residue and ${s}$ is not, it can be shown that the only case possible is ${x-r}$.

Thus, we have found a factor of ${f(x)}$ in polynomial time. Cool. You might ask what if both ${r}$ and ${s}$ are quadratic residues? Then, the gcd will be useless, it will be ${f(x)}$. The trick now is to use an idea of Rabin. We randomly form a new polynomial ${f(x+\delta)}$ where ${\delta}$ is a random residue modulo ${p}$. 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.

July 1, 2009 1:49 pm

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