**Budapest Problem Exchange in MathematicsProblem No. XXX**
**Area:** Theoretical Computer Science, Complexity Theory, Combinatorics, Algebra

**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].

**Contact person:** Vince Grolmusz (grolmusz@cs.elte.hu)

**Posted by:** Vince Grolmusz (grolmusz@cs.elte.hu)

Sat Mar 14 16:13:02 MET 1998