Conjecture on Thue–Morse maximum order complexity along polynomial subsequences

From papers

Let TP\mathcal{T}_P denote the Thue–Morse sequence along a polynomial subsequence, where PP is a polynomial of degree dd. Write M(TP,N)M(\mathcal{T}_P,N) for its maximum order complexity up to length NN. Thue–Morse polynomial-subsequence conjecture. There are constants c,C>0c,C>0 such that, for all sufficiently large NN,

cN1/dM(TP,N)CN1/d.cN^{1/d}\leq M(\mathcal{T}_P,N)\leq CN^{1/d}.

Equivalently, M(TP,N)N1/dM(\mathcal{T}_P,N)\asymp N^{1/d}. A proof would show that the previously proved lower bound is optimal; the claim is supported by computations for squares and cubes.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Damien Jamet, Pierre Popoli and Thomas Stoll, “Maximum order complexity of the sum of digits function in Zeckendorf base and polynomial subsequences”, arXiv:2106.09959 (2021).

Solutions 0

No solutions have been posted yet.