Sing's generalized power-law conjecture for f-smooth-word complexity

From papers

Let \mathpzcA={a,b}\mathpzc{A}=\{a,b\} be a binary alphabet, let Cf\mathcal{C}_f^\infty be the set of finite f-smooth words over \mathpzcA\mathpzc{A}, and let pCf(n)p_{\mathcal{C}_f^\infty}(n) denote its factor complexity. Define

ρ=log(a+b)log(a+b2).\rho=\frac{\log(a+b)}{\log\left(\frac{a+b}{2}\right)}.

Sing's power-law conjecture. Over \mathpzcA={a,b}\mathpzc{A}=\{a,b\},

pCf(n)=Θ(nρ).p_{\mathcal{C}_f^\infty}(n)=\Theta(n^\rho).

The conjecture generalizes the original {1,2}\{1,2\} case; polynomial bounds and partial results are known, but the full asymptotic estimate is not established.

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

Julien Cassaigne and Raphaël Henry, “The complexity of smooth words over binary alphabets”, arXiv:2603.10733 (2026).

Solutions 0

No solutions have been posted yet.