Strange asymptotic

Revision ru1, by piru-piru-piru, 2025-12-14 20:37:30

Let

$$$ P(x) = \sum_{i=0}^n a_i x^i $$$

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

For an integer p >= 1, consider

$$$ x^p - 1 $$$

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

$$$ x^p - 1 \nmid P(x). $$$

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian piru-piru-piru 2025-12-14 20:37:30 535 Первая редакция (опубликовано)