Title: MOD 6 polynomial representation of the OR function

Problem Description: Let d=d(n) denote the
smallest integer, such that there exists a degree-d polynomial ,
which is 0 modulo 6 if ,
and non-zero modulo 6, if .

How large is d(n)?

Background: It is easy to prove, that for prime moduli, instead
of modulus 6, .

By [1], ,
and by [4], .
The upper bound is known to be optimal if P is a symmetric polynomial
[1].

If we were able to construct a P with degree less than ,
then it would yield a larger Ramsey-graph construction than is currently
known [3].

D. A. M. Barrington, R. Beigel, and S. Rudich. Representing Boolean
functions as polynomials modulo composite numbers. Comput. Complexity,
4:367-382, 1994. Appeared also in Proc. 24th Ann. ACM Symp. Theor.\
Comput., 1992.

2

D. A. M. Barrington, H. Straubing, and D. Thérien. Non-uniform
automata over groups. Information and Computation, 89:109-132, 1990.

G. Tardos and D. A. M. Barrington. A lower bound on the MOD 6 degree
of the OR function. In Proceedings of the Third Israel Symosium on the
Theory of Computing and Systems (ISTCS'95), pages 52-56, 1995.