The run-structure conjecture for words of minimal subword entropy

For k2k \geq 2, let ww be a binary word of length n1n \geq 1 achieving the minimal subword entropy minSsw(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.

Sources & referencesView supporting material

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.