betaFeedback

WorksComputer Science

On Non-Deterministic Representation of Boolean Functions

Abstract

We study non-deterministic representation of Boolean functions by polynomials, introduced by (de Wolf, 2000). A polynomial p(x)p(x) is said to be a non-deterministic polynomial for a Boolean function ff if for all a∈{0,1}na\in\{0,1\}^n, p(a)≠0p(a)\neq 0 iff f(a)=1f(a)=1. The non-deterministic degree of ff, denoted ndeg(f)\mathsf{ndeg}(f), is the minimal degree of a non-deterministic polynomial for ff. In this work, we show the following main results: - Almost all Boolean functions on nn variables have non-deterministic degree at most n/2+O(nlog⁡n)n/2 + O(\sqrt{n\log n}). This confirms a conjecture of (Iyer et al., 2023). Together with the lower bound of (Iyer et al., 2023) it establishes a tight bound on the rational degree of a random Boolean function up to lower order terms. - We disprove a conjecture of (Kothari et al., 2026) about effective hypercube nullstellensatz for more than two polynomials. On the positive side, we also identify a constraint under which an effective hypercube nullstellensatz holds for many polynomials.

2012 ACM Subject Classification Computing methodologies →\to Representation of Boolean functions; Theory of computation →\to Quantum complexity theory

Keywords and phrases Random Functions, Non-Deterministic Degree, Rational Degree, Polynomials, Nullstellensatz

Funding Nitin Saurabh: Supported by ANRF ARG-MATRICS grant ANRF/ARGM/2025/003191/MTR. He also acknowledges funding support from the National Quantum Mission (NQM), an initiative of the Department of Science and Technology (DST), Govt. of India.

Acknowledgements We would like to thank anonymous reviewers whose careful reading and thoughtful comments greatly improved the presentation of this paper. We would also like to highlight that no AI tools were used in this work. Nitin Saurabh also acknowledge the support provided by the Foundation for QC Innovation (FQCI), DST-NQM T-Hub at IISc Bengaluru, in facilitating the NQM project.

Introduction

A Boolean function f:{0,1}n→{0,1}f : \{0,1\}^n \to\{0,1\} is said to be exactly represented by a polynomial p(x1,…,xn)p(x_1,\ldots,x_n) if for all a∈{0,1}na \in\{0,1\}^n, p(a)=f(a)p(a)=f(a). It is a well-known fact (see, e.g., [2]) that there exists a unique multilinear polynomial exactly representing a function ff. The degree deg⁡(f)\deg(f) of a Boolean function ff is defined to be the degree of this unique multilinear polynomial exactly representing ff. Polynomials are probably the ‘nicest’ object in mathematics which is attested not only by the existence of a mathematically rich theory but also by their ubiquitous presence in mathematics and sciences. It is no wonder then that since the seminal work of Minsky and Papert [11], a long line of work in theoretical computer science has used various notions of representations by polynomials, e.g., sign representations, pointwise approximations, rational representations, etc., to study different complexity measures associated with computing Boolean functions.

In this work we focus on non-deterministic representation of Boolean functions by polynomials. A polynomial p(x1,…,xn)p(x_1,\ldots,x_n) is said to be a non-deterministic polynomial for a function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\} if p(a)≠0p(a)\ne0 iff f(a)=1f(a)=1. The non-deterministic degree of ff, denoted ndeg⁡(f)\operatorname{ndeg}(f), is the minimum degree among all non-deterministic polynomials pp for ff. This notion was introduced by de Wolf [3] to study the non-deterministic quantum query complexity of ff. He showed that ndeg⁡(f)\operatorname{ndeg}(f) equals the non-deterministic quantum query complexity of ff up to a constant factor. The non-deterministic degree is also related to another natural complexity measure of Boolean functions called the rational degree.

The rational degree of ff, denoted rdeg⁡(f)\operatorname{rdeg}(f), is the minimum value of max⁡{deg⁡(p),deg⁡(q)}\max\{\deg(p),\deg(q)\} such that pp and qq are polynomials satisfying f(a)=p(a)/q(a)f(a)=p(a)/q(a) for all a∈{0,1}na\in\{0,1\}^n. It is a folklore result (credited to de Wolf; see [7, 9]) that rdeg⁡(f)=max⁡{ndeg⁡(f),ndeg⁡(¬f)}\operatorname{rdeg}(f)=\max\{\operatorname{ndeg}(f),\operatorname{ndeg}(\neg f)\}. Mahadev and de Wolf [10] showed an even tighter connection between rational degree and quantum query complexity by observing that rdeg⁡(f)\operatorname{rdeg}(f) exactly characterizes the exact postselected quantum query complexity (see also [9]).

Long before the quantum connections of rational degree came to fore, the motivation to study rational degree was rooted in the classical complexity theory. It was observed by [5] that if deg⁡(f)\deg(f) is polynomially bounded by rdeg⁡(f)\operatorname{rdeg}(f) then P=(C=P∩co⁡-C=P)\mathrm{P}=(\mathrm{C}_{=}\mathrm{P}\cap\operatorname{co}\text{-}\mathrm{C}_{=}\mathrm{P}) with respect to a generic oracle (see also [6]). Thus the question whether deg⁡(f)\deg(f) is polynomially related to rdeg⁡(f)\operatorname{rdeg}(f) was raised more than three decades ago in [12].

In a recent breakthrough result [9] resolved the deg vs. rdeg question by showing that D(f)=O~(ndeg⁡(f)1.5ndeg⁡(¬f)1.5)D(f)=\widetilde{O}(\operatorname{ndeg}(f)^{1.5}\operatorname{ndeg}(\neg f)^{1.5}) where D(f)D(f) is the deterministic query complexity of ff. They further observed that their main result gives an effective version of Hypercube Nullstellensatz.

Theorem 1 ([9 Theorem 10]). Let g1,g2∈R[x1,…,xn]g_1,g_2\in\mathbb{R}[x_1,\ldots,x_n] such that they do not share any common zeroes on the hypercube {0,1}n\{0,1\}^n. Further suppose g1(a)⋅g2(a)=0g_1(a)\cdot g_2(a)=0 for all a∈{0,1}na\in\{0,1\}^n. Then there exist h1,h2∈R[x1,…,xn]h_1,h_2\in\mathbb{R}[x_1,\ldots,x_n] such that

h1(a)g1(a)+h2(a)g2(a)=1for all a∈{0,1}n,h_1(a)g_1(a)+h_2(a)g_2(a)=1 \qquad\text{for all } a\in\{0,1\}^n,

and

max⁡{deg⁡(h1g1‾),deg⁡(h2g2‾)}=O(deg⁡(g1)1.5deg⁡(g2)1.5log⁡max⁡{deg⁡(g1),deg⁡(g2)}),\max\{\deg(\overline{h_1g_1}),\deg(\overline{h_2g_2})\}=O\left(\deg(g_1)^{1.5}\deg(g_2)^{1.5}\log\max\{\deg(g_1),\deg(g_2)\}\right),

where the overline denotes multilinearization using the (Boolean) relations xi2=xix_i^2=x_i for all i∈[n]i\in[n].

They conjectured, in view of well-known classical nullstellensatz results (see [8] and references therein), that the following natural generalization of Theorem 1 to any number of polynomial holds.

Conjecture 2 ([9 Conjecture 11]). For all integers m≥3m\ge3, the following holds. Let 0≠g1,…,gm∈R[x1,…,xn]0\ne g_1,\ldots,g_m\in\mathbb{R}[x_1,\ldots,x_n]. Suppose g1,…,gmg_1,\ldots,g_m do not share any common zeroes on the hypercube {0,1}n\{0,1\}^n. Further suppose g1(a)⋯gm(a)=0g_1(a)\cdots g_m(a)=0 for all a∈{0,1}na\in\{0,1\}^n. Then there exist h1,…,hm∈R[x1,…,xn]h_1,\ldots,h_m\in\mathbb{R}[x_1,\ldots,x_n] such that

h1(a)g1(a)+⋯+hm(a)gm(a)=1for all a∈{0,1}n,h_1(a)g_1(a)+\cdots+h_m(a)g_m(a)=1 \qquad\text{for all } a\in\{0,1\}^n,

and

max⁡i∈[m]{deg⁡(higi‾)}≤poly⁡(deg⁡(g1),…,deg⁡(gm)).\max_{i\in[m]}\{\deg(\overline{h_i g_i})\}\le\operatorname{poly}(\deg(g_1),\ldots,\deg(g_m)).

In this work, we disprove Conjecture 2 (Theorem 6) and prove a variant of it (Theorem 8). We also show that the counter-example in Theorem 6 is optimal (Theorem 7) with respect to the number of polynomials and their degrees. They are presented in § 4.

We also establish extremal bounds on the non-deterministic degree and rational degree of random Boolean functions. It was shown in [7] that all but a negligible fraction of Boolean functions have rational degree at least n/2−O(n)n/2 - O(\sqrt{n}). They conjectured [7 Conjecture 3] that an upper bound of n/2+o(n)n/2 + o(n) holds for a random Boolean function. We prove the conjecture (Theorem 3 and Corollary 5), in § 3, by showing that all but a negligible fraction of Boolean functions have rational degree at most n/2+O(nlog⁡n)n/2 + O(\sqrt{n\log n}) and thereby establishing tight bounds up to lower order terms.

We now present a brief overview of our results and techniques.

Our Results and Techniques

In this paper, we first prove an extremal bound on non-deterministic degree of Boolean functions.

Theorem 3. All but a negligible fraction of Boolean functions on nn variables have non-deterministic degree at most n/2+O(nlog⁡n)n/2 + O(\sqrt{n\log n}).

To establish the upper bound in the theorem, we prove the following technical lemma (Lemma 4) that characterizes functions with ndeg⁡(f)≤d−1\operatorname{ndeg}(f) \le d - 1. Let HH be the 2n×2n2^n \times2^n Hadamard matrix where the (x,y)(x,y)-entry is given by (−1)⟨x,y⟩(-1)^{\langle x,y\rangle} (Definition 10). Let HdH_d denote the submatrix of HH obtained by keeping the rows indexed by strings of Hamming weight at least dd, and further let Hd(f)H_d(f) denote the submatrix of HdH_d obtained by keeping columns indexed by strings in f−1(1)f^{-1}(1).

Lemma 4. Let f:{0,1}n→{0,1}f:\{0,1\}^n \to\{0,1\} be a Boolean function with k:=∣f−1(1)∣k := |f^{-1}(1)|. Then, ndeg⁡(f)≤d−1\operatorname{ndeg}(f) \le d - 1 if and only if there exists a coordinate-wise non-zero v∈Rkv \in\mathbb{R}^k such that Hd(f)v=0H_d(f)v = 0.

To be able to fruitfully use the above lemma we further establish a linear algebraic characterization of matrices having a ‘coordinate-wise non-zero vector in the nullspace’ (Lemma 24). It shows that for a coordinate-wise non-zero vector to exists in the nullspace, it is sufficient (and necessary) for the rowspace to have none of the standard {0,1}\{0,1\}-unit vectors ejte_j^t. This in turn requires that rows remain independent even after removing a column jj. That is, the matrix remains full rank even after removing a column.

Observe that Hd(f)H_d(f) is random submatrix of HdH_d obtained by keeping each column with probability 1/21/2. We need to show that rank⁡(Hd,−j(f))\operatorname{rank}(H_{d,-j}(f)) is full with high probability, where Hd,−j(f)H_{d,-j}(f) denote the submatrix of Hd(f)H_d(f) obtained by removing its jj-th column. Now using the random Gram matrix Hd(f)Hd(f)tH_d(f)H_d(f)^t and the matrix Chernoff inequalities (Lemma 20) we show that Hd(f)H_d(f) satisfies the characterization of Lemma 24 with very high probability.

As a corollary to Theorem 3, we also obtain the following extremal bound on rational degree proving a conjecture of [7].

Corollary 5. All but a negligible fraction of Boolean functions on nn variables have rational degree at most n/2+O(nlog⁡n)n/2 + O(\sqrt{n\log n}).

Our second result is a counterexample to Conjecture 2 about effective hypercube nullstellensatz for many polynomials (made in [9]).

Theorem 6. There exist three non-zero polynomials g1,g2,g3∈R[x1,…,xn,y1,…,yn]g_1,g_2,g_3 \in\mathbb{R}[x_1,\ldots,x_n,y_1,\ldots,y_n] with the following properties:

(i) each of degree two, (ii) do not share any common zeroes in {0,1}n×{0,1}n\{0,1\}^{n} \times\{0,1\}^{n}, and (iii) g1(a,b)⋅g2(a,b)⋅g3(a,b)=0g_{1}(a,b) \cdot g_{2}(a,b) \cdot g_{3}(a,b) = 0 for all (a,b)∈{0,1}n×{0,1}n(a,b) \in\{0,1\}^{n} \times\{0,1\}^{n}.

Let p1,p2,p3∈R[x1,…,xn,y1,…,yn]p_{1},p_{2},p_{3} \in\mathbb{R}[x_{1},\ldots,x_{n},y_{1},\ldots,y_{n}] be any (multilinear) polynomials satisfying

gi(a,b)=0⇒pi(a,b)=0g_{i}(a,b) = 0 \Rightarrow p_{i}(a,b) = 0 for all i∈{1,2,3}i \in\{1,2,3\} and (a,b)∈{0,1}n×{0,1}n(a,b) \in\{0,1\}^{n} \times\{0,1\}^{n}, and

p1(a,b)+p2(a,b)+p3(a,b)=1p_{1}(a,b) + p_{2}(a,b) + p_{3}(a,b) = 1 for all (a,b)∈{0,1}n×{0,1}n(a,b) \in\{0,1\}^{n} \times\{0,1\}^{n}.

Then,

max⁡{deg⁡(p1),deg⁡(p2),deg⁡(p3)}≥n.\max\{\deg(p_{1}),\deg(p_{2}),\deg(p_{3})\} \ge n.

This counterexample is optimal with respect to number of polynomials and their degrees as we state below.

Theorem 7. There exists no set of 3 degree-1 polynomials that is a counterexample to Conjecture 2.

In other words, let g1,g2,g3∈R[x1,…,xn]g_{1},g_{2},g_{3} \in\mathbb{R}[x_{1},\ldots,x_{n}] be three non-zero affine-linear forms such that they do not share any common zeroes on the hypercube {0,1}n\{0,1\}^{n}. Further, suppose g1(a)g2(a)g3(a)=0g_{1}(a)g_{2}(a)g_{3}(a) = 0 for all a∈{0,1}na \in\{0,1\}^{n}. Then, there exist h1,h2,h3∈R[x1,…,xn]h_{1},h_{2},h_{3} \in\mathbb{R}[x_{1},\ldots,x_{n}] such that

h1(a)g1(a)+h2(a)g2(a)+h3(a)g3(a)=1for all a∈{0,1}n,h_{1}(a)g_{1}(a) + h_{2}(a)g_{2}(a) + h_{3}(a)g_{3}(a) = 1 \quad\text{for all } a \in\{0,1\}^{n},

and

max⁡{deg⁡(h1),deg⁡(h2),deg⁡(h3)}=O(1).\max\{\deg(h_{1}),\deg(h_{2}),\deg(h_{3})\} = O(1).

We also give a counterexample comprising of 5 linear polynomials (Proposition 26). These counterexamples build on a similar example (Proposition 25) from [9]. Finally, we identify an extra constraint on the zero set of polynomials that allows us to prove an effective version of hypercube nullstellensatz for many polynomials.

Theorem 8. Let m≥3m \ge3 be an integer and g1,…,gm∈R[x1,…,xn]g_{1},\ldots,g_{m} \in\mathbb{R}[x_{1},\ldots,x_{n}] be non-zero polynomials satisfying the following:

(i) they do not share any common zeroes in {0,1}n\{0,1\}^{n},

(ii) g1(a)⋯gm(a)=0g_{1}(a)\cdots g_{m}(a) = 0 for all a∈{0,1}na \in\{0,1\}^{n}, and

(iii) there exists a non-empty S⊂[m]S \subset[m] such that (⋃i∈SVi)∩(⋃i∉SVi)=∅(\bigcup_{i \in S} V_{i}) \cap(\bigcup_{i \notin S} V_{i}) = \varnothing, where Vi:=gi−1(0)⊆{0,1}nV_{i} := g_{i}^{-1}(0) \subseteq\{0,1\}^{n} for i∈[m]i \in[m].

Then, there exist (multilinear) polynomials p1,…,pm∈R[x1,…,xn]p_{1},\ldots,p_{m} \in\mathbb{R}[x_{1},\ldots,x_{n}] such that the following holds:

(a) gi(a)=0⇒pi(a)=0g_{i}(a) = 0 \Rightarrow p_{i}(a) = 0 for all i∈[m]i \in[m] and a∈{0,1}na \in\{0,1\}^{n},

(b) p1(a)+⋯+pm(a)=1p_{1}(a) + \cdots+ p_{m}(a) = 1 for all a∈{0,1}na \in\{0,1\}^{n}, and

(c) max⁡i∈[m]{deg⁡(pi)}≤poly⁡(deg⁡(g1),…,deg⁡(gm))\max_{i \in[m]}\{\deg(p_{i})\} \le\operatorname{poly}(\deg(g_{1}),\ldots,\deg(g_{m})).

Preliminaries

For a positive integer nn, we denote the set {1,…,n}\{1,\ldots,n\} by [n][n]. We use ⊔\sqcup to denote the disjoint union of sets. A polynomial p(x1,…,xn)∈R[x1,…,xn]p(x_{1},\ldots,x_{n}) \in\mathbb{R}[x_{1},\ldots,x_{n}] is said to be multilinear if it is of the form ∑S⊆[n]cS⋅∏i∈Sxi\sum_{S \subseteq[n]} c_{S} \cdot\prod_{i \in S} x_{i} with cS∈Rc_{S} \in\mathbb{R}. It is a well-known fact (see, e.g., [2]) that every f:{0,1}n→Rf : \{0,1\}^{n} \to\mathbb{R} is exactly represented by a unique multilinear polynomial p(x1,…,xn)p(x_{1},\ldots,x_{n}).

Definition 9. The degree of f:{0,1}n→{0,1}f : \{0,1\}^{n} \to\{0,1\}, denoted deg⁡(f)\deg(f), is the degree of the unique multilinear polynomial p(x)p(x) exactly representing ff, i.e., p(a)=f(a)p(a) = f(a) for all a∈{0,1}na \in\{0,1\}^{n}.

We will use Fourier representation of Boolean functions. In particular, consider the space of all functions from {0,1}n\{0,1\}^{n} to R\mathbb{R} with the following inner-product

⟨f,g⟩:=Ex∈{0,1}n[f(x)g(x)],\langle f,g\rangle:= \mathbb{E}_{x\in\{0,1\}^{n}}[f(x)g(x)],

where the expectation is with respect to the uniform distribution on {0,1}n\{0,1\}^{n}. For S⊆[n]S \subseteq[n], define the character functions χS:{0,1}n→{−1,1}\chi_{S} : \{0,1\}^{n} \to\{-1,1\} as χS(x)=(−1)∑i∈Sxi\chi_{S}(x) = (-1)^{\sum_{i\in S}x_{i}}. Then the set of character functions {χS}S⊆[n]\{\chi_{S}\}_{S\subseteq[n]} forms an orthonormal basis for the space of all real-valued functions on {0,1}n\{0,1\}^{n}. Hence, every real-valued function f:{0,1}n→Rf : \{0,1\}^{n} \to\mathbb{R} has a unique Fourier expansion

f(x)=∑S⊆[n]f^(S)χS(x),f(x) = \sum_{S\subseteq[n]} \widehat{f}(S)\chi_{S}(x),

where the Fourier coefficients f^(S)∈R\widehat{f}(S) \in\mathbb{R}.

It is easily seen that the Fourier-degree max⁡{∣S∣∣f^(S)≠0}\max\{|S| \mid\widehat{f}(S) \ne0\} equals deg⁡(f)\deg(f). From the orthonormality, it follows that f^(S)=Ex∈{0,1}n[f(x)χS(x)]\widehat{f}(S) = \mathbb{E}_{x\in\{0,1\}^{n}}[f(x)\chi_{S}(x)]. Fourier representation is intimately tied with the Hadamard matrices.

Definition 10. Let nn be an integer. Then, the Hadamard matrix HH of dimension 2n×2n2^{n} \times2^{n} is defined such that the rows and columns are indexed by Boolean strings in {0,1}n\{0,1\}^{n} and (x,y)(x,y)-th entry of HH equals (−1)∑i=1nxiyi(-1)^{\sum_{i=1}^{n}x_{i}y_{i}}.

It is then easily seen that for a function f∈R2nf \in\mathbb{R}^{2^{n}}, f^=12nHf\widehat{f} = \frac{1}{2^{n}}Hf, where the vector of Fourier coefficients f^∈R2n\widehat{f} \in\mathbb{R}^{2^{n}}. Furthermore, f=Hf^f = H\widehat{f}.

Definition 11. A polynomial p(x)p(x) is said to be a non-deterministic polynomial for f:{0,1}n→{0,1}f : \{0,1\}^{n} \to\{0,1\} if for all a∈{0,1}na \in\{0,1\}^{n}, p(a)≠0p(a) \ne0 if and only if f(a)=1f(a) = 1. The non-deterministic degree of ff, denoted ndeg⁡(f)\operatorname{ndeg}(f), is the minimum degree among all non-deterministic polynomials for ff.

Definition 12. Polynomials p(x)p(x) and q(x)q(x) are said to be a rational polynomial for f:{0,1}n→{0,1}f : \{0,1\}^{n} \to\{0,1\} if for all a∈{0,1}na \in\{0,1\}^{n}, q(a)≠0q(a) \ne0 and p(a)/q(a)=f(a)p(a)/q(a) = f(a). The rational degree of ff, denoted rdeg⁡(f)\operatorname{rdeg}(f), is the minimum of max⁡{deg⁡(p),deg⁡(q)}\max\{\deg(p),\deg(q)\} among all rational polynomials for ff.

We note the following (folklore) fact about rational degree and non-deterministic degree. For a proof see [9].

Fact 13. For every Boolean function ff, rdeg⁡(f)=max⁡{ndeg⁡(f),ndeg⁡(¬f)}\operatorname{rdeg}(f) = \max\{\operatorname{ndeg}(f), \operatorname{ndeg}(\neg f)\}.

We note the following facts from linear algebra.

Fact 14. Let p(x1,…,xn)∈R[x1,…,xn]p(x_{1},\ldots,x_{n}) \in\mathbb{R}[x_{1},\ldots,x_{n}]. Then p=0p = 0 in R[x1,…,xn]\mathbb{R}[x_{1},\ldots,x_{n}] if and only if p:Rn→Rp:\mathbb{R}^{n} \to\mathbb{R} is the zero function.

We need the following fact about the non-zeroness of a multilinear polynomial. For a proof see, e.g., [12].

Lemma 15 (Ore-Schwartz-Zippel-DeMillo-Lipton Lemma). Let p(x1,…,xn)∈R[x1,…,xn]p(x_{1},\ldots,x_{n}) \in\mathbb{R}[x_{1},\ldots,x_{n}] be a non-zero multilinear polynomial of degree dd. Then, Pr⁡x[p(x)≠0]≥2−d\Pr_{x}[p(x) \ne0] \ge2^{-d}, where xx is chosen uniformly at random from {0,1}n\{0,1\}^{n}.

We also note the following anti-concentration result about linear forms [4].

Lemma 16 ([4]). Let a1,…,ana_1,\ldots,a_n be nn real numbers with ∣ai∣≥1|a_i| \ge1. Further let ϵi∈{−1,1}\epsilon_i \in\{-1,1\} for each i∈[n]i \in[n]. Then the number of sums ∑i=1nϵiai\sum_{i=1}^{n}\epsilon_i a_i which fall in the interior of an arbitrary interval II of length 2 is at most (n⌊n/2⌋)\binom{n}{\lfloor n/2\rfloor}.

Let ej∈Rne_j \in\mathbb{R}^n denote the {0,1}\{0,1\}-unit-vector with 1 at the jj-th location and 0 everywhere else. For a vector v∈Rnv \in\mathbb{R}^n, let vTv^{\mathsf{T}} denote its transpose.

Definition 17. Let AA be a m×nm \times n matrix over R\mathbb{R}. Then, the nullspace of AA is defined to be the set of all vectors v∈Rnv \in\mathbb{R}^n such that Av=0Av = 0. It is a subspace of Rn\mathbb{R}^n.

Further, the rowspace of AA is defined to be the subspace in Rn\mathbb{R}^n generated by the rows of AA. That is, it is the set of all vectors vTAv^{\mathsf{T}}A where v∈Rmv \in\mathbb{R}^m.

Fact 18. Let AA be a m×nm \times n matrix over R\mathbb{R}. Then, the rowspace of AA is the orthogonal complement of the nullspace of AA. That is, (rowspace of A)=(nullspace of A)⊥(\text{rowspace of } A) = (\text{nullspace of } A)^\perp.

We need the following version of Chernoff-Hoeffding concentration inequality.

Lemma 19 (Chernoff-Hoeffding). Let Y1,…,YnY_1,\ldots,Y_n be independent and identically distributed {0,1}\{0,1\}-random variables with Pr⁡(Yi=1)=Pr⁡(Yi=0)=1/2\Pr(Y_i=1)=\Pr(Y_i=0)=1/2. Let Y=∑i=1nYiY=\sum_{i=1}^{n}Y_i. Then, for any t>0t>0,

Pr⁡(Y≥E[Y]+t)≤e−2t2/n.\Pr(Y \ge\mathbb{E}[Y]+t) \le e^{-2t^2/n}.

We also need the following matrix Chernoff inequalities from [13, 14]. See [13 Corollary 5.2] or [14 Theorem 5.1.1] for the version stated here. See also Remark 5.3 in [13].

Lemma 20 (Matrix Chernoff Lower Tail Inequality [13, 14]). Consider a finite sequence {Yk}\{Y_k\} of independent, random, self-adjoint matrices with common dimension dd that satisfy

Yk⪰0Y_k \succeq0 and λmax⁡(Yk)≤L\lambda_{\max}(Y_k) \le L for each index kk.

Define Y:=∑kYkY := \sum_k Y_k and the minimum eigenvalue μmin⁡\mu_{\min} of the expectation E[Y]\mathbb{E}[Y] as μmin⁡:=λmin⁡(E[Y])\mu_{\min} := \lambda_{\min}(\mathbb{E}[Y]). Then, for δ∈[0,1]\delta\in[0,1],

Pr⁡(λmin⁡(Y)≤(1−δ)μmin⁡)≤d⋅[e−δ(1−δ)1−δ]μmin⁡/L≤d⋅e−δ2μmin⁡/2L.\Pr\left(\lambda_{\min}(Y) \le(1-\delta)\mu_{\min}\right) \le d \cdot\left[\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\right]^{\mu_{\min}/L} \le d \cdot e^{-\delta^2\mu_{\min}/2L}.

Extremal properties of non-deterministic polynomials

In this section we give extremal bounds on non-deterministic polynomial representations of Boolean functions. We begin with a simple characterization of functions having full non-deterministic degree. It is well-known that non-deterministic degree of ANDn\mathrm{AND}_n is nn [1, 3]. (In fact, in combinatorics it is known as the Alon-Füredi theorem.) We observe that only ANDn\mathrm{AND}_n have non-deterministic degree nn.

Definition 21. A Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n \to\{0,1\} is called an indicator function if ∣f−1(1)∣=1|f^{-1}(1)|=1.

Proposition 22. Let f:{0,1}n→{0,1}f:\{0,1\}^n \to\{0,1\} be a Boolean function. Then, ndeg⁡(f)=n\operatorname{ndeg}(f)=n if and only if ff is an indicator function.

Proof. As mentioned before, the Alon-Füredi theorem [1] proves that the non-deterministic degree of an indicator function is nn (see also [3]). What remains to be shown is that if ndeg⁡(f)=n\operatorname{ndeg}(f)=n then ff must be an indicator function. To establish this, we prove the contrapositive. That is, if ff is not an indicator function then ndeg⁡(f)≤n−1\operatorname{ndeg}(f)\le n-1.

Let ff be a Boolean function such that ∣f−1(1)∣:=k≥2\lvert f^{-1}(1)\rvert:= k\ge2, and a1,…,aka_1,\ldots,a_k be the kk-elements of f−1(1)f^{-1}(1). For i∈[k]i\in[k], define IiI_i to be the indicator function of the input aia_i, i.e., Ii(x)=1I_i(x)=1 iff x=aix=a_i. Recall, deg⁡(Ii)=n\deg(I_i)=n. Let cic_i be the non-zero coefficient of the degree nn monomial ∏j=1nxj\prod_{j=1}^{n}x_j in IiI_i. Define λ:=−∑i=1k−1ci2/ck\lambda:=-\sum_{i=1}^{k-1}c_i^2/c_k. Clearly λ\lambda is well-defined and ≠0\ne0. Now consider the polynomial

p(x)=∑i=1k−1ciIi(x)+λIk(x).p(x)=\sum_{i=1}^{k-1}c_iI_i(x)+\lambda I_k(x).

We now claim that p(x)p(x) is a non-deterministic polynomial for ff of degree at most n−1n-1. It is easily seen from construction that p(x)p(x) evaluates to non-zero iff x∈{a1,…,ak}x\in\{a_1,\ldots,a_k\}. Moreover, the coefficient of the degree nn monomial equals ∑i=1k−1ci2+λck\sum_{i=1}^{k-1}c_i^2+\lambda c_k which equals 00 by the choice of λ\lambda.

The proof, in Proposition 22, showing that non-indicator functions have non-deterministic degree at most n−1n-1 is simple, and yet instructive enough to allow us to obtain a characterization of non-deterministic degree of arbitrary Boolean functions. This characterization in turn will help us bound the non-deterministic degree of random Boolean functions. Before we proceed further we recall the definition of Hadamard matrices (Definition 10). We need the following submatrices of them.

Definition 23. For 0≤d≤n0\le d\le n and S⊆{0,1}nS\subseteq\{0,1\}^n, let Hd(S)H_d(S) denote the submatrix of HH obtained by keeping columns indexed by SS and rows indexed by strings of Hamming weight ≥d\ge d. When S=f−1(1)S=f^{-1}(1) for a Boolean function ff, then we will use the shorthand Hd(f)H_d(f) to denote the submatrix Hd(f−1(1))H_d(f^{-1}(1)). When S={0,1}nS=\{0,1\}^n, we denote the submatrix by HdH_d.

We are now ready to state the characterization.

Lemma 4. Let f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\} be a Boolean function with k:=∣f−1(1)∣k:=\lvert f^{-1}(1)\rvert. Then, ndeg⁡(f)≤d−1\operatorname{ndeg}(f)\le d-1 if and only if there exists a coordinate-wise non-zero v∈Rkv\in\mathbb{R}^k such that Hd(f)v=0H_d(f)v=0.

Proof. Let f−1(1)={a1,…,ak}⊆{0,1}nf^{-1}(1)=\{a_1,\ldots,a_k\}\subseteq\{0,1\}^n and assume, without loss of generality, the columns of Hd(f)H_d(f) are indexed from left to right by a1,…,aka_1,\ldots,a_k.

(⇒)(\Rightarrow) Let ndeg⁡(f)≤d−1\operatorname{ndeg}(f)\le d-1 and p(x)p(x) be a non-deterministic polynomial for ff with degree at most d−1d-1. Then define v=(v1,…,vk)t∈Rkv=(v_1,\ldots,v_k)^t\in\mathbb{R}^k as follows: vi=p(ai)v_i=p(a_i) for all i∈[k]i\in[k]. Clearly vv is coordinate-wise non-zero. Further we claim Hd(f)v=0H_d(f)v=0. To see this first recall that p^=12nHp\hat{p}=\frac{1}{2^n}Hp. Secondly observe that HdH_d is the restriction of HH to Fourier characters of degree at least dd. Now since deg⁡(p)≤d−1\deg(p)\le d-1, we must have 0=Hdp=Hd(f)v0=H_dp=H_d(f)v.

(⇐)(\Leftarrow) Let v∈Rkv\in\mathbb{R}^k be coordinate-wise non-zero such that Hd(f)v=0H_d(f)v=0. Define the function p:{0,1}n→Rp:\{0,1\}^n\to\mathbb{R} as follows:

p(x)={vj,if x=aj∈f−1(1),0,otherwise.p(x)= \begin{cases} v_j, & \text{if }x=a_j\in f^{-1}(1),\\ 0, & \text{otherwise.} \end{cases}

Clearly pp is a non-deterministic polynomial for ff, i.e., p(x)≠0⟺x∈f−1(1)p(x)\ne0\Longleftrightarrow x\in f^{-1}(1). Therefore, ndeg⁡(f)≤deg⁡(p)\operatorname{ndeg}(f)\le\deg(p). We now claim that deg⁡(p)≤d−1\deg(p)\le d-1; thereby completing the proof.

To see that deg⁡(p)≤d−1\deg(p)\le d-1, consider the Fourier expansion p^=12nHp\hat{p}=\frac{1}{2^n}Hp. Further consider the restriction p^d\hat{p}_d of p^\hat{p} to Fourier characters of degree at least dd. We have p^d=12nHdp=12nHd(f)v=0\hat{p}_d=\frac{1}{2^n}H_dp=\frac{1}{2^n}H_d(f)v=0. Thus deg⁡(p)≤d−1\deg(p)\le d-1.

We now prove a linear algebraic lemma that helps utilize the characterization in Lemma 4.

Lemma 24. Let AA be a real matrix with kk columns. Then, there exists a coordinate-wise non-zero v∈Rk\mathbf{v} \in\mathbb{R}^{k} in the nullspace of AA (i.e., Av=0A\mathbf{v}=0) if and only if for all j∈[k]j \in[k], ejt\mathbf{e}_{j}^{t} is not in the rowspace of AA.

Proof. It is a well-known fact in linear algebra that the rowspace of AA is the orthogonal complement of the nullspace of AA (Fact 18).

(⇒)(\Rightarrow) Let v\mathbf{v} be a coordinate-wise non-zero vector in the nullspace of AA. Then, since rowspace of AA is the orthogonal complement of the nullspace and ejtv=vj≠0\mathbf{e}_{j}^{t}\mathbf{v}=v_{j}\ne0, we must have ejt∉\mathbf{e}_{j}^{t}\notin rowspace of AA for all j∈[k]j \in[k].

(⇐)(\Leftarrow) Let ejt\mathbf{e}_{j}^{t} is not in the rowspace of AA for all j∈[k]j \in[k]. By Fact 18, for each j∈[k]j \in[k], there must exist vectors v(j)\mathbf{v}^{(j)} in the nullspace of AA such that its jj-th coordinate vj(j)≠0v_{j}^{(j)}\ne0. We now claim that there is a linear combination of v(j)\mathbf{v}^{(j)}’s that is coordinate-wise non-zero.

Let v=∑j=1kxjv(j)\mathbf{v}=\sum_{j=1}^{k}x_{j}\mathbf{v}^{(j)} be an arbitrary linear combination of v(j)\mathbf{v}^{(j)}’s. We need to show that there exist a choice of xjx_{j}’s such that v\mathbf{v} is coordinate-wise non-zero. Let us consider each coordinate vi(x)=∑j=1kxjvi(j)v_{i}(\mathbf{x})=\sum_{j=1}^{k}x_{j}v_{i}^{(j)} as a polynomial in x\mathbf{x}. Note that, since vi(i)≠0v_{i}^{(i)}\ne0, each vi(x)v_{i}(\mathbf{x}) is a non-zero polynomial. Now consider the product polynomial p(x)=∏i=1kvi(x)p(\mathbf{x})=\prod_{i=1}^{k}v_{i}(\mathbf{x}). Since each vi(x)v_{i}(\mathbf{x}) is a non-zero polynomial, the product polynomial is also a non-zero polynomial (of degree kk). Therefore, since R\mathbb{R} is an infinite field, there exists a point c∈Rk\mathbf{c}\in\mathbb{R}^{k} such that p(c)≠0p(\mathbf{c})\ne0, which in turn implies that each vi(c)≠0v_{i}(\mathbf{c})\ne0, thereby proving the existence of a coordinate-wise non-zero v\mathbf{v} in the nullspace of AA.

We are now ready to prove that almost all Boolean functions have degree at most n/2+O(nlog⁡n)n/2+O(\sqrt{n\log n}).

Theorem 3. All but a negligible fraction of Boolean functions on nn variables have non-deterministic degree at most n/2+O(nlog⁡n)n/2+O(\sqrt{n\log n}).

Proof. Let us fix d=n/2+cnln⁡nd=n/2+\sqrt{cn\ln n}, for an appropriate choice of the constant cc to be made later. Consider Hd(f)H_{d}(f) for a random Boolean function ff. By Lemma 4, it suffices to show that with probability 1−o(1)1-o(1) there exists a coordinate-wise non-zero vector v\mathbf{v} such that Hd(f)v=0H_{d}(f)\mathbf{v}=0. Which in turn, by Lemma 24, is equivalent to showing that for a uniformly at random ff, with probability 1−o(1)1-o(1), no standard basis vectors ejt\mathbf{e}_{j}^{t} are in the rowspace of Hd(f)H_{d}(f). We now prove this.

Recall HdH_{d} denote the submatrix of HH obtained by keeping those rows indexed by Boolean strings of Hamming weight ≥d\ge d. Let RR denote the number of rows in HdH_{d}. Then, R=∑j=dn(nj)≤2n⋅e−2cln⁡n=2n⋅n−2cR=\sum_{j=d}^{n}\binom{n}{j}\le2^{n}\cdot e^{-2c\ln n}=2^{n}\cdot n^{-2c}, where the inequality follows from the choice of dd and the Chernoff-Hoeffding inequality (Lemma 19).

Let us fix a Boolean function ff. Suppose that a standard basis vector ejt\mathbf{e}_{j}^{t} is in the row span of Hd(f)H_{d}(f). Then there exists a non-zero vector u∈RR\mathbf{u}\in\mathbb{R}^{R} such that utHd(f)=ejt\mathbf{u}^{t}H_{d}(f)=\mathbf{e}_{j}^{t}. Let Hd,−j(f)H_{d,-j}(f) denote the submatrix of Hd(f)H_{d}(f) obtained by removing its jj-th column. Then, utHd,−j(f)=0\mathbf{u}^{t}H_{d,-j}(f)=0. That is, the rows of Hd,−j(f)H_{d,-j}(f) are linearly dependent. Therefore, if a standard basis vector ejt\mathbf{e}_{j}^{t} is in the row span of Hd(f)H_{d}(f) then the rows of Hd,−j(f)H_{d,-j}(f) are linearly dependent, and therefore rank⁡(Hd,−j(f))<R\operatorname{rank}(H_{d,-j}(f))<R. Consider the R×RR\times R Gram matrix Gjf:=Hd,−j(f)Hd,−j(f)tG_{j}^{f}:=H_{d,-j}(f)H_{d,-j}(f)^{t}. Since rank⁡(Gjf)=rank⁡(Hd,−j(f))\operatorname{rank}(G_{j}^{f})=\operatorname{rank}(H_{d,-j}(f)), we must therefore have rank⁡(Gjf)<R\operatorname{rank}(G_{j}^{f})<R.

Hence, for a random ff,

Pr⁡(ejt is in the rowspace of Hd(f))≤Pr⁡(rank⁡(Hd,−j(f))<R)=Pr⁡(rank⁡(Gjf)<R).(1)\Pr\left(\mathbf{e}_{j}^{t}\text{ is in the rowspace of }H_{d}(f)\right)\le\Pr\left(\operatorname{rank}(H_{d,-j}(f))<R\right)=\Pr\left(\operatorname{rank}(G_{j}^{f})<R\right). \tag*{(1)}

We now estimate the probability that rank⁡(Gjf)<R\operatorname{rank}(G_j^f) < R. Consider the matrix-valued function

Gj(δi)=∑i=1i≠j2nδivivit,(2)G_j(\delta_i)=\sum_{\substack{i=1\\i\ne j}}^{2^n}\delta_i v_i v_i^t, \tag*{(2)}

where vi∈RRv_i \in\mathbb{R}^R are the columns of HdH_d and δi\delta_i's are independent {0,1}\{0,1\}-indicator variables. For a random ff, δi∼Bernoulli⁡(1/2)\delta_i \sim\operatorname{Bernoulli}(1/2). Therefore,

Pr⁡f(rank⁡(Gjf)<R)=Pr⁡f(λmin⁡(Gj(f))≤0).(3)\Pr_f(\operatorname{rank}(G_j^f)<R)=\Pr_f(\lambda_{\min}(G_j(f))\le0). \tag*{(3)}

We now bound the probability that minimum eigenvalue of the random Gram matrix Gj(f)G_j(f) equals zero using the matrix Chernoff inequality (Lemma 20). We note that the maximum eigenvalue λmax⁡(vivit)\lambda_{\max}(v_i v_i^t) of the rank-1 matrix vivitv_i v_i^t is RR, since viv_i is a {1,−1}\{1,-1\}-vector of dimension RR. We also compute the expected Gram matrix

Ef[Gj(f)]=12Hd,−jHd,−jt=12(HdHdt−vjvjt)=12(2nIR−vjvjt),(4)\mathbb{E}_f[G_j(f)]=\frac{1}{2}H_{d,-j}H_{d,-j}^t=\frac{1}{2}\left(H_dH_d^t-v_jv_j^t\right)=\frac{1}{2}\left(2^nI_R-v_jv_j^t\right), \tag*{(4)}

where IRI_R is the R×RR\times R identity matrix and, recall Hd,−jH_{d,-j} is the submatrix of HdH_d obtained by removing its jj-th column. The first equality in Equation (4) follows from the linearity of expectation and writing the sum of outer products as matrix multiplication, the second follows from adding and subtracting the term vjvjtv_jv_j^t, and finally the third follows from the fact that the rows of HdH_d (Hadamard matrices) are mutually orthogonal.

It then follows from Equation (4) that the minimum eigenvalue of the expected Gram matrix μmin⁡(E[Gj])=(2n−R)/2\mu_{\min}(\mathbb{E}[G_j])=(2^n-R)/2. Therefore, using the lower tail of matrix Chernoff inequality (Lemma 20) we have

Pr⁡f(rank⁡(Gjf)<R)=Pr⁡f(λmin⁡(Gj(f))≤0)≤R⋅e−μmin⁡/2R=R⋅e−(2n−R)/4R.(5)\Pr_f(\operatorname{rank}(G_j^f)<R)=\Pr_f(\lambda_{\min}(G_j(f))\le0)\le R\cdot e^{-\mu_{\min}/2R}=R\cdot e^{-(2^n-R)/4R}. \tag*{(5)}

We can then bound the probability that any standard basis vector ejte_j^t is in the row span of Hd(f)H_d(f) by the union bound

Pr⁡(∃j such that ejt in the row span of Hd(f))≤2n⋅R⋅e−(2n−R)/4R,≤22nn2c⋅e−(n2c−1)/4.(6)\begin{aligned} \Pr\left(\exists j\text{ such that }e_j^t\text{ in the row span of }H_d(f)\right)\le2^n\cdot R\cdot e^{-(2^n-R)/4R}, \\ &\le\frac{2^{2n}}{n^{2c}}\cdot e^{-(n^{2c-1})/4}. \tag*{(6)} \end{aligned}

Choosing c>1/2c>1/2 we can see that the failure probability in Equation (6) is o(1)o(1), thus completing the proof of the theorem. ◀

An interesting special case of Theorem 3 occurs when we consider ndeg⁡(f)\operatorname{ndeg}(f) and ndeg⁡(¬f)\operatorname{ndeg}(\neg f) for a random ff. By Theorem 3, the probability that, for a random ff, both ndeg⁡(f)\operatorname{ndeg}(f) and ndeg⁡(¬f)\operatorname{ndeg}(\neg f) are not at most n/2+O(nlog⁡n)n/2+O(\sqrt{n\log n}) is o(1)o(1). We thus obtain the following corollary proving a conjecture of [7].

Corollary 5. All but a negligible fraction of Boolean functions on nn variables have rational degree at most n/2+O(nlog⁡n)n/2+O(\sqrt{n\log n}).

Together with a result of [7] it establishes a tight bound on the rational degree of random Boolean functions up to lower order terms.

Effective hypercube nullstellensatz for many polynomials

A recent breakthrough work [9] proved an effective version of nullstellensatz on Boolean hypercube.

Theorem 1 ([9 Theorem 10]). Let g1,g2∈R[x1,…,xn]g_1,g_2 \in\mathbb{R}[x_1,\ldots,x_n] such that they do not share any common zeroes on the hypercube {0,1}n\{0,1\}^n. Further suppose g1(a)⋅g2(a)=0g_1(a)\cdot g_2(a)=0 for all a∈{0,1}na\in\{0,1\}^n. Then there exist h1,h2∈R[x1,…,xn]h_1,h_2\in\mathbb{R}[x_1,\ldots,x_n] such that

h1(a)g1(a)+h2(a)g2(a)=1for all a∈{0,1}n,h_1(a)g_1(a)+h_2(a)g_2(a)=1 \qquad\text{for all }a\in\{0,1\}^n,

and

max⁡{deg⁡(h1g1‾),deg⁡(h2g2‾)}=O(deg⁡(g1)1.5deg⁡(g2)1.5log⁡max⁡{deg⁡(g1),deg⁡(g2)}).\max\{\deg(\overline{h_1g_1}),\deg(\overline{h_2g_2})\}=O\left(\deg(g_1)^{1.5}\deg(g_2)^{1.5}\log\max\{\deg(g_1),\deg(g_2)\}\right).

where the overline denotes multilinearization using the (Boolean) relations xi2=xix_i^2=x_i for all i∈[n]i\in[n].

They conjectured, in view of well-known classical nullstellensatz results (see [8] and references therein), that the following natural generalization of Theorem 1 to any number of polynomial holds.

Conjecture 2 ([9 Conjecture 1]). For all integers m≥3m\geq3, the following holds. Let 0≠g1,…,gm∈R[x1,…,xn]0\neq g_1,\ldots,g_m\in\mathbb{R}[x_1,\ldots,x_n]. Suppose g1,…,gmg_1,\ldots,g_m do not share any common zeroes on the hypercube {0,1}n\{0,1\}^n. Further suppose g1(a)⋯gm(a)=0g_1(a)\cdots g_m(a)=0 for all a∈{0,1}na\in\{0,1\}^n. Then there exist h1,…,hm∈R[x1,…,xn]h_1,\ldots,h_m\in\mathbb{R}[x_1,\ldots,x_n] such that

h1(a)g1(a)+⋯+hm(a)gm(a)=1for all a∈{0,1}n,h_1(a)g_1(a)+\cdots+h_m(a)g_m(a)=1 \qquad\text{for all }a\in\{0,1\}^n,

and

max⁡i∈[m]{deg⁡(higi‾)}≤poly⁡(deg⁡(g1),…,deg⁡(gm)).\max_{i\in[m]}\{\deg(\overline{h_i g_i})\}\leq\operatorname{poly}(\deg(g_1),\ldots,\deg(g_m)).

In the following we disprove the conjecture even when m=3m=3. Note that when m=2m=2 we have Theorem 1. We will need the following proposition from [9].

Proposition 25 ([9]). Let f1(x1,…,xn,y1,…,yn):=∑i=1nxif_1(x_1,\ldots,x_n,y_1,\ldots,y_n):=\sum_{i=1}^{n}x_i and Z1:={(a,b)∈{0,1}n×{0,1}n∣f1(a,b)=0}Z_1:=\{(a,b)\in\{0,1\}^n\times\{0,1\}^n\mid f_1(a,b)=0\}. Let f2(x1,…,xn,y1,…,yn):=∑i=1nxi+∑j=1nyj−(n+1)f_2(x_1,\ldots,x_n,y_1,\ldots,y_n):=\sum_{i=1}^{n}x_i+\sum_{j=1}^{n}y_j-(n+1) and Z2:={(a,b)∈{0,1}n×{0,1}n∣f2(a,b)=0}Z_2:=\{(a,b)\in\{0,1\}^n\times\{0,1\}^n\mid f_2(a,b)=0\}. Further, define f:Z1⊔Z2→{0,1}f:Z_1\sqcup Z_2\to\{0,1\} by f(a,b)=0f(a,b)=0 if and only if (a,b)∈Z1(a,b)\in Z_1. Then, any polynomial p(x1,…,xn,y1,…,yn)p(x_1,\ldots,x_n,y_1,\ldots,y_n) satisfying p(a,b)=f(a,b)p(a,b)=f(a,b) for all (a,b)∈Z1⊔Z2(a,b)\in Z_1\sqcup Z_2 must have deg⁡(p)≥n\deg(p)\geq n.

We are now ready to present a counterexample to Conjecture 2.

Theorem 6. There exist three non-zero polynomials g1,g2,g3∈R[x1,…,xn,y1,…,yn]g_1,g_2,g_3\in\mathbb{R}[x_1,\ldots,x_n,y_1,\ldots,y_n] with the following properties:

  • (i) each of degree two,

  • (ii) do not share any common zeroes in {0,1}n×{0,1}n\{0,1\}^n\times\{0,1\}^n, and

  • (iii) g1(a,b)⋅g2(a,b)⋅g3(a,b)=0g_1(a,b)\cdot g_2(a,b)\cdot g_3(a,b)=0 for all (a,b)∈{0,1}n×{0,1}n(a,b)\in\{0,1\}^n\times\{0,1\}^n.

Let p1,p2,p3∈R[x1,…,xn,y1,…,yn]p_1,p_2,p_3\in\mathbb{R}[x_1,\ldots,x_n,y_1,\ldots,y_n] be any (multilinear) polynomials satisfying

  • gi(a,b)=0⇒pi(a,b)=0g_i(a,b)=0\Rightarrow p_i(a,b)=0 for all i∈{1,2,3}i\in\{1,2,3\} and (a,b)∈{0,1}n×{0,1}n(a,b)\in\{0,1\}^n\times\{0,1\}^n, and

  • p1(a,b)+p2(a,b)+p3(a,b)=1p_1(a,b)+p_2(a,b)+p_3(a,b)=1 for all (a,b)∈{0,1}n×{0,1}n(a,b)\in\{0,1\}^n\times\{0,1\}^n.

Then,

max⁡{deg⁡(p1),deg⁡(p2),deg⁡(p3)}≥n.\max\{\deg(p_1), \deg(p_2), \deg(p_3)\} \ge n.

Proof. Let g1:=f1(x,y)⋅(x1+x2)g_1 := f_1(x,y)\cdot(x_1+x_2), g2:=f1(x,y)⋅(x1+x2−1)g_2 := f_1(x,y)\cdot(x_1+x_2-1), and g3:=f2(x,y)⋅(x1+x2−2)g_3 := f_2(x,y)\cdot(x_1+x_2-2), where f1f_1 and f2f_2 are as defined in Proposition 25. Clearly they are non-zero polynomials of degree 2. Furthermore, it is easily seen that a common zero of g1g_1, g2g_2 and g3g_3 will also be a common zero of f1f_1 and f2f_2. But we know from Proposition 25 that f1f_1 and f2f_2 do not share any common zero, and therefore, g1g_1, g2g_2, and g3g_3 do not share any common zero over the Boolean hypercube. Finally, g1(a,b)g2(a,b)g3(a,b)=0g_1(a,b)g_2(a,b)g_3(a,b)=0 for all (a,b)∈{0,1}n×{0,1}n(a,b)\in\{0,1\}^n\times\{0,1\}^n since (x1+x2)(x1+x2−1)(x1+x2−2)≡0(x_1+x_2)(x_1+x_2-1)(x_1+x_2-2)\equiv0 over the Boolean hypercube.

Let p1p_1, p2p_2, and p3p_3 be any polynomials as given in the statement of Theorem 6. Further, let Z1Z_1 and Z2Z_2 be the zero set of f1f_1 and f2f_2, respectively. By definition, p3p_3 evaluates to 0 on Z2Z_2 and since p1p_1 and p2p_2 evaluates to 0 on Z1Z_1, p3p_3 must evaluate to 1 on Z1Z_1. Thus, by Proposition 25, deg⁡(p3)≥n\deg(p_3)\ge n.

We also present a counterexample with linear polynomials but the number of polynomials increases to 5. In fact, Theorem 6 is optimal with respect to the number of polynomials and their degrees, as we show in Theorem 7.

Proposition 26. Consider the following non-zero polynomials: g1(x,y):=x1g_1(x,y):=x_1, g2(x,y):=x2g_2(x,y):=x_2, g3(x,y):=x1−x2g_3(x,y):=x_1-x_2, g4(x,y):=f1(x,y)g_4(x,y):=f_1(x,y), and g5(x,y):=f2(x,y)g_5(x,y):=f_2(x,y), where f1f_1 and f2f_2 are as defined in Proposition 25. Clearly, they do not share any common zeroes and ∏igi≡0\prod_i g_i\equiv0 on the Boolean hypercube. Let p1,p2,p3,p4,p5∈R[x1,…,xn,y1,…,yn]p_1,p_2,p_3,p_4,p_5\in\mathbb{R}[x_1,\ldots,x_n,y_1,\ldots,y_n] be any (multilinear) polynomials satisfying

  • gi(a,b)=0⟹pi(a,b)=0g_i(a,b)=0\Longrightarrow p_i(a,b)=0 for all i∈[5]i\in[5] and (a,b)∈{0,1}n×{0,1}n(a,b)\in\{0,1\}^n\times\{0,1\}^n, and

  • p1(a,b)+p2(a,b)+p3(a,b)+p4(a,b)+p5(a,b)=1p_1(a,b)+p_2(a,b)+p_3(a,b)+p_4(a,b)+p_5(a,b)=1 for all (a,b)∈{0,1}n×{0,1}n(a,b)\in\{0,1\}^n\times\{0,1\}^n.

Then,

max⁡{deg⁡(p1),deg⁡(p2),deg⁡(p3),deg⁡(p4),deg⁡(p5)}≥n.\max\{\deg(p_1),\deg(p_2),\deg(p_3),\deg(p_4),\deg(p_5)\}\ge n.

Proof. Let Z1Z_1 and Z2Z_2 be the zero set of f1f_1 and f2f_2, respectively. Note that p1p_1, p2p_2, p3p_3, and p4p_4 all evaluate to 0 on Z1Z_1, and thus p5p_5 must evaluate to 1 on Z1Z_1, while it evaluates to 0 on Z2Z_2 by definition. Hence, by Proposition 25, deg⁡(p5)≥n\deg(p_5)\ge n.

Note that an important requirement in nullstellensatz is that polynomials do not share any common zeroes. However, this does not forbid some of them from sharing a common zero. In the following we identify a constraint on the zero sets of polynomials that allows to prove an effective version for many polynomials.

Theorem 8. Let m≥3m\ge3 be an integer and g1,…,gm∈R[x1,…,xn]g_1,\ldots,g_m\in\mathbb{R}[x_1,\ldots,x_n] be non-zero polynomials satisfying the following:

(i) they do not share any common zeroes in {0,1}n\{0,1\}^n,

(ii) g1(a)⋯gm(a)=0g_1(a)\cdots g_m(a)=0 for all a∈{0,1}na\in\{0,1\}^n, and

(iii) there exists a non-empty S⊆[m]S\subseteq[m] such that (⋃i∈SVi)∩(⋃i∉SVi)=∅(\bigcup_{i\in S}V_i)\cap(\bigcup_{i\notin S}V_i)=\varnothing, where Vi:=gi−1(0)⊆{0,1}nV_i:=g_i^{-1}(0)\subseteq\{0,1\}^n for i∈[m]i\in[m].

Then, there exist (multilinear) polynomials p1,…,pm∈R[x1,…,xn]p_1,\ldots,p_m\in\mathbb{R}[x_1,\ldots,x_n] such that the following holds:

(a) gi(a)=0⟹pi(a)=0g_i(a)=0\Longrightarrow p_i(a)=0 for all i∈[m]i\in[m] and a∈{0,1}na\in\{0,1\}^n,

(b) p1(a)+⋯+pm(a)=1p_1(a)+\cdots+p_m(a)=1 for all a∈{0,1}na\in\{0,1\}^n, and

(c) $\max_{i\in[m]}{\deg(p_i)}\le\operatorname{poly}(\deg(g_1),\ldots,\deg(g_m)).

Proof. Since SS and [m]∖S[m] \setminus S are non-empty, define the following polynomials:

g1∗=∏i∈Sgiandg2∗=∏i∉Sgi.g_1^* = \prod_{i \in S} g_i \quad\text{and}\quad g_2^* = \prod_{i \notin S} g_i.

Then, by property (iii), we have that g1∗g_1^* and g2∗g_2^* do not share any common zeroes. Furthermore, g1∗(a)⋅g2∗(a)=∏i=1mgi(a)=0g_1^*(a) \cdot g_2^*(a) = \prod_{i=1}^{m} g_i(a) = 0 for all a∈{0,1}na \in\{0,1\}^n. Therefore, by Theorem 1, there exist p1∗p_1^* and p2∗p_2^* such that

(a) gi∗(a)=0  ⟹  pi∗(a)=0g_i^*(a) = 0 \implies p_i^*(a) = 0 for all i∈{1,2}i \in\{1,2\} and a∈{0,1}na \in\{0,1\}^n,

(b) p1∗(a)+p2∗(a)=1p_1^*(a) + p_2^*(a) = 1 for all a∈{0,1}na \in\{0,1\}^n, and

(c) max⁡{deg⁡(p1∗),deg⁡(p2∗)}≤poly⁡(deg⁡(g1∗),deg⁡(g2∗))\max\{\deg(p_1^*), \deg(p_2^*)\} \leq\operatorname{poly}(\deg(g_1^*), \deg(g_2^*)).

Now fix a k∈Sk \in S and j∉Sj \notin S. Define pi:=0p_i := 0 for all i∈[m]∖{k,j}i \in[m] \setminus\{k,j\}, pk:=p1∗p_k := p_1^*, and pj:=p2∗p_j := p_2^*. These polynomials satisfy the conclusion of the theorem statement.

Optimality of the example in Theorem 6

In this subsection, we show that a counterexample to Conjecture 2 with 3 polynomials, say g1g_1, g2g_2 and g3g_3 must satisfy max⁡{deg⁡(g1),deg⁡(g2),deg⁡(g3)}\max\{\deg(g_1),\deg(g_2),\deg(g_3)\} at least 2.

Theorem 7. There exists no set of 3 degree-1 polynomials that is a counterexample to Conjecture 2.

In other words, let g1,g2,g3∈R[x1,…,xn]g_1,g_2,g_3 \in\mathbb{R}[x_1,\ldots,x_n] be three non-zero affine-linear forms such that they do not share any common zeroes on the hypercube {0,1}n\{0,1\}^n. Further, suppose g1(a)g2(a)g3(a)=0g_1(a)g_2(a)g_3(a)=0 for all a∈{0,1}na \in\{0,1\}^n. Then, there exist h1,h2,h3∈R[x1,…,xn]h_1,h_2,h_3 \in\mathbb{R}[x_1,\ldots,x_n] such that

h1(a)g1(a)+h2(a)g2(a)+h3(a)g3(a)=1for all a∈{0,1}n,h_1(a)g_1(a) + h_2(a)g_2(a) + h_3(a)g_3(a) = 1 \quad\text{for all } a \in\{0,1\}^n,

and

max⁡{deg⁡(h1),deg⁡(h2),deg⁡(h3)}=O(1).\max\{\deg(h_1),\deg(h_2),\deg(h_3)\} = O(1).

Proof. Let g1,g2,g3:{0,1}n→Rg_1,g_2,g_3 : \{0,1\}^n \to\mathbb{R} be non-zero affine-linear forms such that

(i) g1(a)g2(a)g3(a)=0g_1(a)g_2(a)g_3(a)=0 for all a∈{0,1}na \in\{0,1\}^n, and

(ii) they share no common zeroes in {0,1}n\{0,1\}^n.

For i∈{1,2,3}i \in\{1,2,3\}, define Zi:={a∈{0,1}n∣gi(a)=0}Z_i := \{a \in\{0,1\}^n \mid g_i(a)=0\} and ηi:=∣Zi∣/2n\eta_i := |Z_i|/2^n. Thus, by property (i), we have η1+η2+η3≥1\eta_1+\eta_2+\eta_3 \geq1. We now have two cases based on g1,g2,g3g_1,g_2,g_3.

Case 1: Two of the hyperplanes, say Z1Z_1 and Z2Z_2, cover the full hypercube {0,1}n\{0,1\}^n on their own. That is, {0,1}n=Z1∪Z2\{0,1\}^n = Z_1 \cup Z_2. Then, by Lemma 27, we have exactly one of the following subcases.

(a) For some ii, g1=xig_1=x_i and g2=1−xig_2=1-x_i. In this case, it suffices to take h1=1h_1=1, h2=1h_2=1 and h3=0h_3=0 to obtain the conclusion in the theorem.

(b) For some distinct i,ji,j, g1=xi−xjg_1=x_i-x_j and g2=xi+xj−1g_2=x_i+x_j-1. In such a case, let h1=g1h_1=g_1, h2=g2h_2=g_2 and h3=0h_3=0.

In both cases we have max⁡{deg⁡(h1),deg⁡(h2),deg⁡(h3)}≤1\max\{\deg(h_1),\deg(h_2),\deg(h_3)\} \leq1.

Case 2: No two hyperplanes can cover the full hypercube {0,1}n\{0,1\}^n. That is, for distinct i,j∈{1,2,3}i,j \in\{1,2,3\}, Zi∪Zj⊂{0,1}nZ_i \cup Z_j \subset\{0,1\}^n. Then, we claim that for each i∈{1,2,3}i \in\{1,2,3\}, ηi≥1/4\eta_i \geq1/4.

Let us complete the proof of theorem assuming the claim. For i∈{1,2,3}i \in\{1,2,3\}, let kik_i be the number of variables with non-zero coefficients in the affine-linear form gig_i. Then by the Littlewood-Offord inequality (Lemma 16), we have ηi≤2πki\eta_i \leq\sqrt{\frac{2}{\pi k_i}}, which in turn implies ki≤2πηi2≤32π<11k_i \leq\frac{2}{\pi\eta_i^2} \leq\frac{32}{\pi} < 11. Therefore, together gig_i's depend on k1+k2+k3=O(1)k_1+k_2+k_3=O(1) variables. Hence the solutions hih_i's have degree at most O(1)O(1).

We are now left to prove the claim that ηi≥1/4\eta_i \ge1/4 for all ii. We show it for η1\eta_1. The argument is analogous for others. Consider the function g′(x):=g2(x)g3(x)g'(x) := g_2(x)g_3(x) for all x∈{0,1}nx \in\{0,1\}^n. Since Z2∪Z3⊂{0,1}nZ_2 \cup Z_3 \subset\{0,1\}^n, g′g' is a non-zero multilinear polynomial of degree at most 22. Therefore, by Lemma 15, Pr⁡[g′(x)≠0]≥1/4\Pr[g'(x) \ne0] \ge1/4. It is then implied by property (i) that η1=Pr⁡[g1(x)=0]≥1/4\eta_1 = \Pr[g_1(x) = 0] \ge1/4.

We are now ready to characterize a pair of affine-linear forms that together covers the Boolean hypercube.

Lemma 27. Let A(x)=a0+∑i=1naixiA(x) = a_0+\sum_{i=1}^n a_i x_i and B(x)=b0+∑i=1nbixiB(x) = b_0+\sum_{i=1}^n b_i x_i be non-zero affine-linear forms over R\mathbb{R}. Further, suppose {0,1}n⊆{A=0}∪{B=0}\{0,1\}^n \subseteq\{A = 0\} \cup\{B = 0\}. Then, up to multiplication by non-zero constants, and up to relabelling, exactly one of the following holds:

(a) For some i∈[n]i \in[n], A(x)=xiA(x) = x_i and B(x)=1−xiB(x) = 1-x_i.

(b) For some distinct i,j∈[n]i,j \in[n], A(x)=xi−xjA(x) = x_i-x_j and B(x)=xi+xj−1B(x) = x_i+x_j-1.

Proof. We need the following two technical claims, which we prove afterwards.

Claim 28. For a non-zero affine-linear form L(x)L(x) on nn variables, #L:=∣{z∈{0,1}n∣L(z)=0}∣≤2n−1\#L := |\{z \in\{0,1\}^n \mid L(z) = 0\}| \le2^{n-1}.

Claim 29. If a non-zero affine-linear form L(x)L(x) on nn variables is such that #L=2n−1\#L = 2^{n-1}, then, up to multiplication by a non-zero constant, L(x)∈{xi,1−xi,xi−xj,xi+xj−1}L(x) \in\{x_i,1-x_i,x_i-x_j,x_i+x_j-1\}, for distinct i,j∈[n]i,j \in[n].

Assuming the claims we complete the proof now. By Claim 28 and the assumption {0,1}n⊆{A=0}∪{B=0}\{0,1\}^n \subseteq\{A = 0\} \cup\{B = 0\}, we must have #A=#B=2n−1\#A = \#B = 2^{n-1} and A∩B=∅A \cap B = \varnothing. By Claim 29, A,B∈{xi,1−xi,xi−xj,xi+xj−1}A,B \in\{x_i,1-x_i,x_i-x_j,x_i+x_j-1\} and moreover they should be complementary. Therefore, either A=xiA = x_i and B=1−xiB = 1-x_i, or A=xi−xjA = x_i-x_j and B=xi+xj−1B = x_i+x_j-1. ◀

We now prove the two claims.

Proof of Claim 28. Let L(x)=a0+∑i=1naixiL(x) = a_0+\sum_{i=1}^n a_i x_i. Since LL is non-zero either there exists a variable xkx_k with the non-zero coefficient aka_k, or LL is a non-zero constant function. If LL is a non-zero constant function, then clearly #L=0≤2n−1\#L = 0 \le2^{n-1}, for all n≥0n \ge0. Henceforth, we assume, without loss of generality, that the variable xnx_n has non-zero coefficient. Thus, for some affine-linear form AA on n−1n-1 variables, we have

L(x)=anxn+A(x1,…,xn−1).L(x) = a_nx_n + A(x_1,\ldots,x_{n-1}).

Now observe that for every setting y=(x1,…,xn−1)∈{0,1}n−1y = (x_1,\ldots,x_{n-1}) \in\{0,1\}^{n-1}, there is at most one solution to xnx_n that satisfies L(x)=anxn+A(y)=0L(x) = a_nx_n + A(y) = 0. Therefore, the number of solutions to LL is at most 2n−12^{n-1}. ◁

Proof of Claim 29. Since L(x)L(x) is a non-zero affine-linear form, we assume, without loss of generality, up to multiplication by a non-zero constant,

L(x)=xi−g(x1,…,xi−1,xi+1,…,xn),L(x) = x_i-g(x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_n),

for some affine-linear form gg in the remaining n−1n-1 variables. For every assignment z∈{0,1}n−1z \in\{0,1\}^{n-1} to the variables of gg, at most one value of xix_i can satisfy L(x)=0L(x)=0. Since #L=2n−1\#L=2^{n-1}, there must be exactly one such zero for each zz. Therefore, g(z)∈{0,1}g(z) \in\{0,1\} for all z∈{0,1}n−1z \in\{0,1\}^{n-1}. Thus, gg is a Boolean function of degree at most 11. That is, g∈{0,1,xj,1−xj}g \in\{0,1,x_j,1-x_j\} for j≠ij \ne i. This completes the proof of the claim. ◁

Conclusion

In this paper, we studied non-deterministic polynomial representation of Boolean functions. We showed that almost all Boolean functions have non-deterministic degree as well as rational degree at most n/2+O(nlog⁡n)n/2 + O(\sqrt{n\log n}). This confirms a conjecture of [7] and together with their lower bound establishes tight extremal bounds for random Boolean functions up to lower order terms.

We also studied effective versions of hypercube nullstellensatz and disproved Conjecture 2 of [9]. On the positive side, we proved a variant of Conjecture 2. We also show the optimality of our counterexample to Conjecture 2.

For the future work, one of the most interesting question that remains open is to close the gap between deg⁡/D\operatorname{deg}/D and ndeg⁡/rdeg⁡\operatorname{ndeg}/\operatorname{rdeg}. In particular, de Wolf [3] conjectured that D(f)=O(ndeg⁡(f)ndeg⁡(¬f))D(f) = O(\operatorname{ndeg}(f)\operatorname{ndeg}(\neg f)). The current best known separation is quadratic (see [9]). Even the weaker versions of this conjecture, namely QE(f)=O(ndeg⁡(f)ndeg⁡(¬f))QE(f) = O(\operatorname{ndeg}(f)\operatorname{ndeg}(\neg f)) and deg⁡(f)=O(ndeg⁡(f)ndeg⁡(¬f))\operatorname{deg}(f) = O(\operatorname{ndeg}(f)\operatorname{ndeg}(\neg f)), remains open.

The deg⁡(f)=?O(ndeg⁡(f)ndeg⁡(¬f))\operatorname{deg}(f) \overset{?}{=} O(\operatorname{ndeg}(f)\operatorname{ndeg}(\neg f)) question is also interesting from the perspective of effective hypercube nullstellensatz. If true it would match the well-known effective version of classical nullstellensatz [8].

References

  1. [1]Noga Alon and Zoltán Füredi. Covering the cube by affine hyperplanes. Eur. J. Comb., 14(2):79–83, 1993. URL: https://doi.org/10.1006/eujc.1993.1011, doi:10.1006/EJC.1993.1011.
  2. [2]Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci., 288(1):21–43, 2002. doi:10.1016/S0304-3975(01)00144-X.DOI
  3. [3]Ronald de Wolf. Characterization of non-deterministic quantum query and quantum communication complexity. In Proceedings of the 15th Annual IEEE Conference on Computational Complexity, pages 271–278. IEEE Computer Society, 2000. doi:10.1109/CCC.2000.856758.
  4. [4]P. Erdős. On a lemma of Littlewood and Offord. Bulletin of the American Mathematical Society, 51(12):898 – 902, 1945.DOI
  5. [5]Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, and Lide Li. An oracle builder’s toolkit. Inf. Comput., 182(2):95–136, 2003. doi:10.1016/S0890-5401(03)00018-X.DOI
  6. [6]Lance Fortnow. Computational complexity blog - rational functions and decision-tree complexity, 2003. URL: https://blog.computationalcomplexity.org/2003/11/rational-functions-and-decision-tree.html.
  7. [7]Vishnu Iyer, Siddhartha Jain, Robin Kothari, Matt Kovacs-Deak, Vinayak M. Kumar, Luke Schaeffer, Daochen Wang, and Michael Whitmeyer. On the rational degree of boolean functions and applications. CoRR, abs/2310.08004, 2023. URL: https://doi.org/10.48550/arXiv.2310.08004, doi:10.48550/ARXIV.2310.08004.
  8. [8]Zbigniew Jelonek. On the effective Nullstellensatz. Inventiones mathematicae, 162:1–17, 2005. doi:10.1007/s00222-004-0434-8.
  9. [9]Robin Kothari, Matt Kovacs-Deak, Daochen Wang, and Rain Zimin Yang. Rational degree is polynomially related to degree. CoRR, abs/2601.08727, 2026. URL: https://doi.org/10.48550/arXiv.2601.08727, doi:10.48550/ARXIV.2601.08727.
  10. [10]Urmila Mahadev and Ronald de Wolf. Rational approximations and quantum algorithms with postselection. Quantum Inf. Comput., 15(3&4):295–307, 2015. doi:10.26421/QIC15.3-4-5.DOI
  11. [11]Marvin Minsky and Seymour Papert. Perceptrons. MIT Press, Cambridge, MA, 1969.
  12. [12]Noam Nisan and Mario Szegedy. On the degree of boolean functions as real polynomials. Comput. Complex., 4:301–313, 1994. doi:10.1007/BF01263419.DOI
  13. [13]Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Found. Comput. Math., 12(4):389–434, 2012. URL: https://doi.org/10.1007/s10208-011-9099-z, doi:10.1007/S10208-011-9099-Z.
  14. [14]Joel A. Tropp. An introduction to matrix concentration inequalities. Found. Trends Mach. Learn., 8(1-2):1–230, 2015. doi:10.1561/2200000048.DOI

Paper details

vlnc:W_u3f7dzjt
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

None listed by the authors

View statement
Looking for related papers…
Contents