Let $\mathcal{ F}_{ n}^*$ be the set of Boolean functions depending on all $n$ variables. We prove that for any $f\in \mathcal{ F}_{ n}^*$, $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}^*$ 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.

Categories: cs.CC

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