next up previous
Next: References

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 tex2html_wrap_inline65, which is 0 modulo 6 if tex2html_wrap_inline69, and non-zero modulo 6, if tex2html_wrap_inline71.

How large is d(n)?

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

By [1], tex2html_wrap_inline77, and by [4], tex2html_wrap_inline79. 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 tex2html_wrap_inline85, then it would yield a larger Ramsey-graph construction than is currently known [3].

Contact person: Vince Grolmusz (

Posted by: Vince Grolmusz (

Originated from: [2], [1]

Vince Grolmusz
Sat Mar 14 16:13:02 MET 1998