Let

be a nonzero polynomial of degree n, where a_i \in {-1,0,1}.

For an integer p >= 1, consider

Define p(n) as the minimal p such that for every polynomial P of degree n with coefficients in {-1,0,1},

Question: what is the asymptotic growth of p(n)? Remark. Without coefficient restrictions, the maximal possible p is Θ(sqrt(n)). The question is whether the constraint a_i in {-1,0,1} changes this bound.