The run-structure conjecture for words of minimal subword entropy

About 2 years old · traced to

For k≥2k \geq 2, let ww be a binary word of length n≥1n \geq 1 achieving the minimal subword entropy min⁡Ssw(k)(n)\min S_{\mathrm{sw}}^{(k)}(n). A run is a maximal consecutive block of equal letters. Run-structure conjecture. Except for finitely many values of nn, the longest run in ww has length 33, and the average run length converges as n→+∞n \to +\infty.

The claim is motivated by computations showing that minimizers mostly contain runs of lengths 11, 22, and 33, while long runs appear to increase subword entropy. Its status is open.

References

Primary source

Wenjie Fang, “Maximal number of subword occurrences in a word”, arXiv:2406.02971 (2025).

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.