Let an varepsilon-synchronization string of length n over an alphabet Sigma be a word S∈Sigma^n such that, for every 0≤ i (1-varepsilon)(k-i). Determine the minimum alphabet cardinality q for which there exists a constant varepsilon<1 such that, for every n≥ 1, an varepsilon-synchronization string of length n over an alphabet of size q exists. Earlier results show that q≤ 4 and that q≥ 3; equivalently, the unresolved case was whether arbitrarily long ternary synchronization strings exist.

Optimal alphabet size for synchronization strings

Let an $\varepsilon$ -synchronization string of length $n$ over an alphabet $\Sigma$ be a word $S\in\Sigma^n$ such that, for every $0\le i<j<k\le n$ , the insertion-deletion edit distance satisfies $\operatorname{ED}(S[i:j],S[j:k])>(1-\varepsilon)(k-i)$ . Determine the minimum alphabet cardinality $q$ for which there exists a constant $\varepsilon<1$ such that, for every $n\ge 1$ , an $\varepsilon$ -synchronization string of length $n$ over an alphabet of size $q$ exists. Earlier results show that $q\le 4$ and that $q\ge 3$ ; equivalently, the unresolved case was whether arbitrarily long ternary synchronization strings exist.

References

Primary source

arXiv

Additional references

Synchronization Strings over the Optimal Alphabet — arXiv

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

An unrefereed preprint claims to settle the minimum alphabet question, but its new construction has not been independently verified.

The problem asks for the smallest alphabet supporting arbitrarily long synchronization strings. Earlier work established four-symbol constructions and ruled out arbitrarily long binary strings, leaving the ternary case unresolved.

Known results

The 2017 STOC work gave general bounds of $O(\varepsilon^{-4})$ and $\Omega(\varepsilon^{-1})$ .
The 2018 work improved the general bounds to $O(\varepsilon^{-2})$ and $\Omega(\varepsilon^{-3/2})$ .
Arbitrarily long strings were constructed over alphabets of size four, while binary alphabets were shown insufficient.
Whether ternary alphabets suffice was explicitly left open.

September 3, 2026 claimed ternary resolution

On September 3, 2026, Synchronization Strings over the Optimal Alphabet claimed a ternary construction at every length using $2001/2002$ -synchronization strings, together with a computer-assisted refinement for every $\varepsilon>226/227$ . If correct, this settles the alphabet-size gap; the claim is currently unverified.

Current status (as of September 2026): Binary impossibility and four-symbol constructions are established, while the ternary resolution and claimed optimality remain unverified.

Sources

No solutions have been posted yet.