Restrictions of Nondegenerate Boolean Functions and Degree Lower Bounds over Different Rings

Abstract

A Boolean function f : {0; 1}(n) -> {0, 1} is called nondegenerate if f depends on all its n variables. We show that, for any nondegenerate function f, there exists a variable x(i) such that at least one of the restrictions f vertical bar(xi) = 0 or f vertical bar(xi) = 1 must depend on all the remaining n - 1 variables. We also consider lower bounds on the degrees of polynomials representing a Boolean function over different rings. Let d (q)(f) be the degree of the unique) polynomial over the ring Z(q) exactly representing f. For distinct primes p(i) let m = Pi(r)(i=1) p(i)(ei). Then, we show that any nondegenerate symmetric Boolean function f must have m . d(p1)(e1) (f)...d(pr)(er)(f) > n. We use the existence of nondegenerate subfunctions to prove degree lower bounds on random functions. Specifically, we show that m .d(p)(e1) (f)...d(pr)(er) (f) > l g n - 1 holds for almost all f when f is chosen uniformly at random from all n - variate Boolean functions. Our proof uses the second moment method to show that a random f must almost always contain a nondegenerate symmetric subfunction on at least l g n - 1 variables. It follows that an n-variate nondegenerate symmetric Boolean function can have degree o(root n) over at most one finite field and that almost all f can have degree o(root lg n) over at most one finite field.