UC Berkeley

Polynomial representations of Boolean functions over various rings such as Z and Zm have been studied since Minsky and Papert (1969). From then on, they have been employed in a large variety of areas including communication complexity, circuit complexity, learning theory, coding theory and so on. For any integer m ≥ 2, each Boolean function has a unique multilinear polynomial representation over ring Zm. The degree of such polynomial is called modulo-m degree, denoted as degm(·). In this paper, we investigate the lower bound of modulo-m degree of Boolean functions. When m = pk (k ≥ 1) for some prime p, we give a tight lower bound degm(f) ≥ k(p − 1) for any nondegenerate function f : {0, 1}n → {0, 1}, provided that n is sufficient large. When m contains two different prime factors p and q, we give a nearly optimal lower bound for any symmetric function f : {0, 1}n → {0, 1} that degm(f) ≥ 2+ p−1 1 + q−1 n . 1.