Nonclassical polynomials and exact computation of Boolean functions

Thoughts 2018-04-25

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 $\mathbb {Z}/2^k\mathbb {Z}$ , 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 $16$ in $\mathbb {F}_2[x_1, \ldots , x_n]$ . (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),

$\begin{aligned}S_{16}(x_1, \ldots , x_n) = \left (\sum _{S\subseteq [n],|S| = 16} \prod _{i \in S}x_i\right )\textrm { mod 2} = {|x| \choose 16} \textrm { mod 2},\end{aligned}$

where $|x| = \sum _{i=1}^n x_i$ is the Hamming weight of $x$ . One can verify (using, for example, Lucas’s theorem) that $S_{16}(x_1, \ldots , x_n) = 1$ if and only if the $5^{th}$ least significant bit of $|x|$ is $1$ .

We use that no polynomial of degree less than or equal to $15$ can compute $S_{16}(x)$ correctly on more than half of the points in $\{0,1\}^n$ .

Theorem 1. Let $P$ be a polynomial of degree at most $15$ in $\mathbb {F}_2[x_1, \ldots , x_n]$ . Then

$\begin{aligned}\Pr _{x \sim \{0,1\}^n}[P(x) = S_{16}(x)] \le \frac {1}{2} + o(1).\end{aligned}$

[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 $0$ polynomials) can compute any Boolean function on half of the points in $\{0,1\}^n$ and this result shows that even polynomials of higher degree don’t do any better as far as $S_{16}(x_1, \ldots , x_n)$ is concerned. What we prove is that there is a nonclassical polynomial of degree $14$ that computes $S_{16}(x_1, \ldots , x_n)$ on $9/16 \ge 1/2 + \Omega (1)$ of the points in $\{0,1\}^n$ .

Theorem 2. There is a nonclassical polynomial $P$ of degree $14$ such that

$\begin{aligned}\Pr _{x \sim \{0,1\}^n}[P(x) = S_{16}(x)] = \frac {9}{16} - o(1).\end{aligned}$

A nonclassical polynomial takes values on the torus $\mathbb {T} = \mathbb {R}/\mathbb {Z}$ 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 $\{0,1/2\} \subset \mathbb {T}$ . So, for example, $S_{16}(x_1, \ldots , x_n) = \frac {1}{2}$ if $|x|_4 = 1$ , and $S_{16}(x_1, \ldots , x_n) = 0$ otherwise. Here $|x|_4$ denotes the $5^{th}$ least significant bit of $|x|$ .

We show that the nonclassical polynomial that computes $S_{16}(x)$ on $9/16$ of the points in $\{0,1\}^n$ is

$\begin{aligned}P(x_1, \ldots , x_n) = \frac {\sum _{S \subseteq [n], |S|=12} \prod _{i \in S}x_i}{8} \textrm { mod 1}= \frac {{|x| \choose 12}}{8} \textrm { mod 1} .\end{aligned}$

The degree of this nonclassical polynomial is $14$ 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 $P(x)$ behaves comes down to figuring out the largest power of two that divides $|x| \choose 12$ for a given $x$ : if the largest power of two that divides $|x| \choose 12$ is $2$ then $P(x) = 1/2$ , otherwise if the largest power is at least $3$ then $P(x) = 0$ . 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 $2$ dividing $a \choose b$ for $a,b \in \mathbb {N}$ , $a \ge b$ , is equal to the number of borrows required when subtracting $b$ from $a$ in base $2$ . Equipped with Kummer’s theorem, it doesn’t take much work to arrive at the following conclusion.

Lemma 4. $P(x) = S_{16}(x)$ if either $|x|_{2} = 0$ or $(|x|_2, |x|_3, |x|_4, |x|_5) = (1,0,0,0)$ , where $|x|_i$ denotes the $(i+1)^{th}$ least significant bit of $|x|$ .

If $x = (x_1, \ldots , x_n)$ is uniformly distributed in $\{0,1\}^n$ then it’s not hard to verify that the bits $|x|_0, \ldots , |x|_5$ are almost uniformly and independently distributed in $\{0,1\}$ , and so the above lemma proves that $P(x)$ computes $S_{16}(x)$ on $9/16$ of the points in $\{0,1\}^n$ . It turns out that one can easily generalize the above argument to show that $S_{2^\ell }(x)$ is a counterexample to Bhowmick and Lovett’s conjecture for every $\ell \ge 4$ .

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 $S_4(x_1, \ldots , x_n)$ is a counterexample but couldn’t. It would be interesting to check if it is one.

References

[AB01] N. Alon and R. Beigel. Lower bounds for approximations by low degree polynomials over z m. In Proceedings 16th Annual IEEE Conference on Computational Complexity, pages 184–187, 2001.

[BL15] Abhishek Bhowmick and Shachar Lovett. Nonclassical polynomials as a barrier to polynomial lower bounds. In Proceedings of the 30th Conference on Computational Complexity, pages 72–87, 2015.

[GT07] B. Green and T. Tao. The distribution of polynomials over finite fields, with applications to the Gowers norms. ArXiv e-prints, November 2007.

[LMS11] Shachar Lovett, Roy Meshulam, and Alex Samorodnitsky. Inverse conjecture for the gowers norm is false. Theory of Computing, 7(9):131–145, 2011.