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

Less than 1 year old · traced to

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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.