摘要：Polynomial representations of Boolean functions over various rings such as â"¤ and â"¤_m 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 â"¤_m. The degree of such polynomial is called modulo-m degree, denoted as deg_m(â<.). In this paper, we investigate the lower bound of modulo-m degree of Boolean functions. When m = p^k (k ⥠1) for some prime p, we give a tight lower bound deg_m(f) ⥠k(p-1) for any non-degenerate function f:{0,1}â¿ â' {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}â¿ â' {0,1} that deg_m(f) ⥠n/{2+1/(p-1)+1/(q-1)}.
关键词：Boolean function; polynomial; modular degree; Ramsey theory
