The 6n complexity conjecture for binary generalized pseudostandard words

Let u\mathbf u be a binary generalized pseudostandard word, and let Cu(n)\mathcal C_{\mathbf u}(n) denote its complexity, namely the number of factors of length nn in u\mathbf u. The 6n complexity conjecture.

Cu(n)<6n\mathcal C_{\mathbf u}(n)<6n

for every nNn\in\mathbb N. The conjecture is motivated by computer experiments and proposes a new upper bound after the previously stated 4n4n bound was disproved. Determining such upper bounds is presented as an open problem, and no resolution of this conjecture is given in the source.

Sources & referencesView supporting material

Primary source

Lubomira Dvorakova and Josef Florian, “A new estimate on complexity of binary generalized pseudostandard words”, arXiv:1611.05482 (2016).

Additional references

2 papers in this index state this conjecture (2014–2016). The statement above is taken from the most recent of them; the others are arXiv:1408.5210.

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.