Synchronization Strings over the Optimal Alphabet
Abstract
Synchronization strings provide deterministic position labels for recovering coordinates after insertions and deletions. Haeupler and Shahrasbi introduced these objects, and subsequent work proved that four symbols suffice for some fixed parameter epsilon < 1, whereas two symbols cannot support arbitrarily long synchronization strings. We resolve the remaining ternary case: every length admits a ternary 2001/2002-synchronization string. Thus three is the exact minimum constant alphabet size. A computer-assisted refinement based on a larger 54-uniform family yields ternary epsilon-synchronization strings for every epsilon > 215/216. The previous four-symbol construction uses a ternary square-free backbone to exclude short repetitions and a fourth symbol to carry long-range synchronization marks. Our main technical contribution is a local-entropy transfer theorem: every square-free block-local source with a positive interval conditional min-entropy rate supports synchronization strings with a fixed gap. We instantiate this theorem using occurrence-wise branching in a Brinkhuis family. Every outcome remains ternary and square-free, while every long interval retains linear conditional min-entropy after all choices outside it are exposed. A deletion-ball estimate converts this entropy into an exponentially small probability of a near-complete common subsequence between adjacent intervals, and an asymmetric Lovasz Local Lemma enforces all interval constraints simultaneously. The same framework also yields exponentially many valid words, synchronization circles, and synchronization within a class of extremal square-free words. Adding constraints on distant intervals gives a Las Vegas construction in expected O(n^2 log^3(n+2)) time.
Related
- Efficient construction of subspace design codes over constant alphabet
- Distributed Optimization over Simplicial Complexes via Topological Dirac Synchronization
- Control Laguerre Tessellation: Semi-discrete Optimal Transport Over Control Systems
- Latency-Optimal Geo-Distributed Storage over Structured Networks
- Near-Optimal Decentralized Stochastic Convex Optimization over Networks
BibTeX
@misc{xu2026synchronization,
title = {{Synchronization Strings over the Optimal Alphabet}},
author = {Huibo Xu and Shi Fu and Youming Qiao and Dacheng Tao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.04122},
eprint = {2609.04122},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.04122},
}
RIS
TY - UNPB
TI - Synchronization Strings over the Optimal Alphabet
AU - Huibo Xu
AU - Shi Fu
AU - Youming Qiao
AU - Dacheng Tao
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.04122
UR - https://arxiv.org/abs/2609.04122
AB - Synchronization strings provide deterministic position labels for recovering coordinates after insertions and deletions. Haeupler and Shahrasbi introduced these objects, and subsequent work proved that four symbols suffice for some fixed parameter epsilon < 1, whereas two symbols cannot support arbitrarily long synchronization strings. We resolve the remaining ternary case: every length admits a ternary 2001/2002-synchronization string. Thus three is the exact minimum constant alphabet size. A computer-assisted refinement based on a larger 54-uniform family yields ternary epsilon-synchronization strings for every epsilon > 215/216. The previous four-symbol construction uses a ternary square-free backbone to exclude short repetitions and a fourth symbol to carry long-range synchronization marks. Our main technical contribution is a local-entropy transfer theorem: every square-free block-local source with a positive interval conditional min-entropy rate supports synchronization strings with a fixed gap. We instantiate this theorem using occurrence-wise branching in a Brinkhuis family. Every outcome remains ternary and square-free, while every long interval retains linear conditional min-entropy after all choices outside it are exposed. A deletion-ball estimate converts this entropy into an exponentially small probability of a near-complete common subsequence between adjacent intervals, and an asymmetric Lovasz Local Lemma enforces all interval constraints simultaneously. The same framework also yields exponentially many valid words, synchronization circles, and synchronization within a class of extremal square-free words. Adding constraints on distant intervals gives a Las Vegas construction in expected O(n^2 log^3(n+2)) time.
ER -