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 , , and by , . The upper bound is known to be optimal if P is a symmetric polynomial .
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 .
Contact person: Vince Grolmusz (firstname.lastname@example.org)
Posted by: Vince Grolmusz (email@example.com)
Originated from: ,