On Restricting No-Junta Boolean Function and Degree Lower Bounds by Polynomial Method

Abstract

Let ${\mathcal{F}}_n^{\ast }$ be the set of Boolean functions depending on all $n$ variables. We prove that for any $f\in {\mathcal{F}}_n^{\ast }$, $f{|}_{x_i=0}$ or $f{|}_{x_i=1}$ depends on the remaining $n-1$ variables, for some variable $x_i$. This existent result suggests a possible way to deal with general Boolean functions via its subfunctions of some restrictions. As an application, we consider the degree lower bound of representing polynomials over finite rings. Let $f\in {\mathcal{F}}_n^{\ast }$ and denote the exact representing degree over the ring ${\mathbb{Z}}_m$ (with the integer $m>2$) as $d_m(f)$. Let $m={\Pi }_{i=1}^r{p}_i^{e_i}$, where $p_i$'s are distinct primes, and $r$ and $e_i$'s are positive integers. If $f$ is symmetric, then $m\cdot d_{p_1^{e_1}}(f)...d_{p_r^{e_r}}(f)>n$. If $f$ is non-symmetric, by the second moment method we prove almost always $m\cdot d_{p_1^{e_1}}(f)...d_{p_r^{e_r}}(f)>\lg n-1$. In particular, as $m=pq$ where $p$ and $q$ are arbitrary distinct primes, we have $d_p(f)d_q(f)=\Omega (n)$ for symmetric $f$ and $d_p(f)d_q(f)=\Omega (\lg n-1)$ almost always for non-symmetric $f$. Hence any $n$-variate symmetric Boolean function can have exact representing degree $o(\sqrt{n})$ in at most one finite field, and for non-symmetric functions, with $o(\sqrt{\lg n})$-degree in at most one finite field.

5 pages, ISIT 2015. Simplified proof