A lower bound on the MOD 6 degree of the or function

We examine the computational power of modular counting, where the modulus m is not a prime power, in the setting of polynomials in Boolean variables o ver Z(m). In particular, we say that a polynomial P weakly represents a Boo lean function f (both have n variables) if for any inputs x and y in {0, 1} (n), we have P(x) not equal P(y) whenever f(x) not equal f(y). Barrington e t al. (1994) investigated the minimal degree of a polynomial representing t he OR function in this way, proving an upper bound of O(n(1/r)) (where r is the number of distinct primes dividing m) and a lower bound of omega(1). H ere, we show a lower bound of Omega(log n) when m is a product of two prime s and Omega((log n)(1/(r-1))) in general. While many lower bounds are known for a much stronger form of representation of a function by a polynomial ( Barrington et al. 1994, Tsai 1996), very little is known using this liberal land, we argue, more natural) definition. While the degree is known to be Omega(log n) for the generalized inner product because of its high communic ation complexity (Grolmusz 1995), our bound is the best known for any funct ion of low communication complexity and any modulus not a prime power.