Guest post by Abhishek Bhrushundi.
I would like to thank Emanuele for giving me the opportunity to write a guest post here. I recently stumbled upon an old post on this blog which discussed two papers: Nonclassical polynomials as a barrier to polynomial lower bounds by Bhowmick and Lovett, and Anti-concentration for random polynomials by Nguyen and Vu. Towards the end of the post, Emanuele writes:
“Having discussed these two papers in a sequence, a natural question is whether non-classical polynomials help for exact computation as considered in the second paper. In fact, this question is asked in the paper by Bhowmick and Lovett, who conjecture that the answer is negative: for exact computation, non-classical polynomials should not do better than classical.”
In a joint work with Prahladh Harsha and Srikanth Srinivasan from last year, On polynomial approximations over , we study exact computation of Boolean functions by nonclassical polynomials. In particular, one of our results disproves the aforementioned conjecture of Bhowmick and Lovett by giving an example of a Boolean function for which low degree nonclassical polynomials end up doing better than classical polynomials of the same degree in the case of exact computation.
The counterexample we propose is the elementary symmetric polynomial of degree in . (Such elementary symmetric polynomials also serve as counterexamples to the inverse conjecture for the Gowers norm [LMS11, GT07], and this was indeed the reason why we picked these functions as candidate counterexamples),
where is the Hamming weight of . One can verify (using, for example, Lucas’s theorem) that if and only if the least significant bit of is .
Theorem 1. Let be a polynomial of degree at most in . Then
[Emanuele’s note. Let me take advantage of this for a historical remark. Green and Tao first claimed this fact and sent me and several others a complicated proof. Then I pointed out the paper by Alon and Beigel [AB01]. Soon after they and I independently discovered the short proof reported in [GT07].]
The constant functions (degree polynomials) can compute any Boolean function on half of the points in and this result shows that even polynomials of higher degree don’t do any better as far as is concerned. What we prove is that there is a nonclassical polynomial of degree that computes on of the points in .
Theorem 2. There is a nonclassical polynomial of degree such that
A nonclassical polynomial takes values on the torus and in order to compare the output of a Boolean function (i.e., a classical polynomial) to that of a nonclassical polynomial it is convenient to think of the range of Boolean functions to be . So, for example, if , and otherwise. Here denotes the least significant bit of .
We show that the nonclassical polynomial that computes on of the points in is
The degree of this nonclassical polynomial is but I wouldn’t get into much detail as to why this is case (See [BL15] for a primer on the notion of degree in the nonclassical world).
Understanding how behaves comes down to figuring out the largest power of two that divides for a given : if the largest power of two that divides is then , otherwise if the largest power is at least then . Fortunately, there is a generalization of Lucas’s theorem, known as Kummer’s theorem, that helps characterize this:
Theorem 3.[Kummer’s theorem] The largest power of dividing for , , is equal to the number of borrows required when subtracting from in base .
Equipped with Kummer’s theorem, it doesn’t take much work to arrive at the following conclusion.
Lemma 4. if either or , where denotes the least significant bit of .
If is uniformly distributed in then it’s not hard to verify that the bits are almost uniformly and independently distributed in , and so the above lemma proves that computes on of the points in . It turns out that one can easily generalize the above argument to show that is a counterexample to Bhowmick and Lovett’s conjecture for every .
We also show in our paper that it is not the case that nonclassical polynomials always do better than classical polynomials in the case of exact computation — for the majority function, nonclassical polynomials do as badly as their classical counterparts (this was also conjectured by Bhowmick and Lovett in the same work), and the Razborov-Smolensky bound for classical polynomials extends to nonclassical polynomials.
We started out trying to prove that is a counterexample but couldn’t. It would be interesting to check if it is one.