PaperlayerView exact revision on arXiv

Source-linked AI summary

Synchronization Strings over the Optimal Alphabet

Huibo Xu, Shi Fu, Youming Qiao, Dacheng Tao

arXiv:2609.04122v2cs.ITcs.DMcs.FLmath.IT

TL;DR

Whether three symbols could support a fixed synchronization gap remained open between four-symbol sufficiency and binary impossibility. The paper uses occurrence-wise branching in ternary square-free constructions to turn interval entropy into separation between adjacent intervals, proving a ternary synchronization string exists at every length.

  • Problem

    Whether three symbols can support a fixed synchronization gap remained open, despite four-symbol sufficiency and the impossibility of arbitrarily long binary synchronization strings.

    Source: §1 · p. 2

  • Method

    The construction branches occurrence-wise within ternary square-free families, using interval conditional entropy and deletion-ball bounds to suppress high-LCS matches between adjacent intervals.

    Source: From four symbols to three · p. 3, §1.4 · p. 7

  • Results

    Every length admits a ternary 2001/2002-synchronization string, making three the minimum constant alphabet size for synchronization strings of all lengths at some fixed ε < 1.

    Source: §1.3 · p. 3, §1.4 · p. 8

  • Takeaways & Limitations

    Occurrence-wise branching lets the construction combine ternary square-freeness with the long-range separation that the earlier four-symbol method carried in a separate marking symbol.

    Source: From four symbols to three · p. 3

    The optimal ternary synchronization gap remains open; the stronger explicit parameter uses a larger family and finite checks at short scales.

    Source: §7 · p. 21

Abstract

from arXiv · show

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.

1 Introduction

The introduction presents a construction of ternary synchronization strings using square-free words with local randomness, alongside a local-entropy transfer principle. It also outlines stronger parameter results and extensions to cyclic circles and related word families.

1.2 Pattern avoidance and the extremal alphabet question

  • Synchronization labels restore approximate positions after insertions and deletions, while square-freeness alone prevents exact repetitions but not adjacent blocks with near-complete common subsequences.Three symbols are the first alphabet size that avoids squares in arbitrarily long words; the paper shows this also supports the stronger linear separation required for synchronization.Source: §1.1 · p. 2, §1.2 · p. 3

1.3 Our results

  • Every length admits a ternary 2001/2002-synchronization string, making three the minimum constant alphabet size that works for all lengths.The binary obstruction establishes the lower bound on alphabet size.Source: §1 · p. 2, §1.3 · p. 3
  • Every square-free block-local source with fixed block size and positive interval conditional min-entropy rate contains a synchronization string for some fixed parameter ε < 1.Occurrence-wise Brinkhuis choices preserve ternary square-freeness and provide local randomness; for η = 1/1000, equal blocks have normalized edit distance at least 1/1000, while arbitrary adjacent intervals have at least 1/2001.Source: From four symbols to three · p. 4, Local entropy and further consequences · p. 5, §1.4 · pp. 7–8
  • For every n ≥ 2493, a ternary word can be both extremal square-free and a 200001/200002-synchronization string.Pairing occurrence-wise images of lengths 41 and 52 creates equal-length choice blocks that preserve extremality and provide local entropy.Source: Local entropy and further consequences · p. 5
  • For every ε > 215/216, ternary ε-synchronization strings exist at every length.The computer-assisted refinement uses a larger 54-uniform family.Source: Local entropy and further consequences · p. 5
  • Ternary synchronization circles exist at every length 18N for N ≥ 18, and three is the minimum alphabet size for circles of unbounded length.A computer-assisted argument further gives a ternary 5201/5202-synchronization circle for every n ≥ 10008.Source: Local entropy and further consequences · p. 6
  • For every n ≥ 504, at least exp(n/9) ternary words satisfy Equation (2), and a Las Vegas algorithm finds one in expected O(n^2 log^3(n + 2)) time.The algorithm also uses constraints on distant interval pairs to reduce longer violations to events on O(log n) symbols.Source: Local entropy and further consequences · p. 6

1.4 Proof overview

  • The length-54 family with 952 choices per outer-letter occurrence yields normalized edit-distance lower bound 1/216, hence ternary ε-synchronization strings for every ε > 215/216, including 216/217.The refinement checks the remaining one- and two-deletion obstructions and analyzes unequal adjacent intervals directly.Source: §1.4 · p. 8
  • A circularly square-free outer word gives 18N-length synchronization circles; deleting a short factor then yields every sufficiently large length after checking seam-local squares and boundary cases.For the circle result, the same conditioning and scale-sensitive local lemma apply to cyclic arcs.Source: §1.4 · p. 8
  • The product-form local lemma gives exponentially many ternary words, while LCS-detected bad events and macroblock resampling yield a Las Vegas polynomial-time construction.Injectivity turns the lower bound on successful choice vectors into the word count; the charge calculation bounds expected resamplings.Source: §1.4 · p. 8

1.5 Related work

  • Prior work established that four symbols suffice for some fixed ε < 1, two do not, and ternary remained open; a separate quaternary result reached 0.999606 [CHL+19, Section 1.3.2 and Theorem 6.4; BDG+26, Corollary 1.10].The 0.999606 value comes from a Hamming-to-edit embedding construction.Source: §1.5 · pp. 8–9
  • The paper repurposes corrected occurrence-wise Brinkhuis families as conditional anti-concentration sources and occurrence-wise choices from an extremal-word substitution as a block-local source.Prior work also studied LCS similarity avoidance and computational bounds beginning at three symbols [CR16, Theorem 1 and Tables 1–2].Source: §1.5 · p. 9
  • Unlike Cheng et al.’s small-alphabet construction [CHL+19, Sections 3–4], bounded-range independent variables retain interval conditional min-entropy while every outcome remains square-free, keeping the local lemma within square-free support.The paper uses the asymmetric local lemma and Moser–Tardos resampling theorem in their standard forms.Source: §1.5 · p. 9

2 Preliminaries

The preliminaries connect insertion–deletion distance and longest common subsequences to synchronization, then reduce the condition to equal-length adjacent blocks. They also state the local-lemma tools used later.

2 Preliminaries

  • Words are indexed by half-open intervals, and all logarithms are natural.Intervals are nonempty unless stated otherwise.Source: §2 · p. 9

2.1 Edit distance, common subsequences, and synchronization

  • Insertion–deletion distance counts the minimum insertions and deletions needed to transform one word into another, while LCS length measures their longest shared subsequence.The section also defines square-free words and notes that synchronization strings with ε < 1 must be square-free; both square-freeness and fixed synchronization inequalities pass to factors.Source: §2.1 · pp. 9–10
  • A uniform LCS deficit for every adjacent equal-length pair implies a synchronization string whenever 1 − ε < η/(2 + η), including synchronization gap η/3.The proof extends the equal-length guarantee to unequal adjacent intervals using their length difference.Source: §2.1 · p. 10

2.2 Local-lemma tools

  • The asymmetric Lovász Local Lemma gives a criterion for avoiding dependent bad events, and Moser–Tardos provides a resampling algorithm that terminates almost surely under the same hypotheses.The expected resamplings of an event E are at most x(E)/(1 − x(E)).Source: §2.2 · p. 10

3 The square-free source: Brinkhuis substitutions

The construction uses occurrence-wise choices from a Brinkhuis family so that outputs remain ternary and square-free while retaining randomness inside intervals. This conditional variation is later used to control long common subsequences.

3 The square-free source: Brinkhuis substitutions

  • A uniform Brinkhuis K-triple requires each independent choice of images for every ternary square-free three-letter word to preserve square-freeness, including when the first and third letters match.Different occurrences of the same source letter may choose different images.Source: §3 · p. 11
  • The six length-18 words form an 18-Brinkhuis 2-triple, and applying the choices to any ternary square-free outer word yields a square-free output with an injective choice-to-word map.The length-three condition corrects the original insufficient two-block formulation.Source: §3 · p. 11
  • Choosing independently and uniformly between the two images at each occurrence makes every output square-free while leaving linearly many independent choices inside each long interval after outside choices are fixed.The choices are used to bound the probability of a long common subsequence, rather than only to count square-free words.Source: §3 · p. 11

4 Ternary synchronization strings

The six-codeword construction gives ternary synchronization strings at every length by combining square-freeness at short scales with conditional entropy and a local-lemma argument at long scales. Its equal-length interval guarantee yields the stated synchronization gap and establishes ternary alphabet optimality.

4.3 All scales and all adjacent intervals

  • Every length admits a ternary 2001/2002-synchronization string, and three is the minimum constant alphabet size supporting synchronization strings of all lengths for some fixed ε < 1.The proof obtains normalized edit distance at least 1/2001, while the binary impossibility result establishes optimality.Source: §4 · p. 11, §4.3 · p. 14

4.1 Conditional entropy and high-LCS events

  • Conditioning on choices outside a long interval fixes the other adjacent interval while leaving at least ℓ/18 − 2 independent bits; each exact value of the first interval then has conditional probability at most 2^−s.A ternary deletion-ball bound limits the number of near-complete common-subsequence competitors, and the resulting event probability is exponentially small.Source: §4.1 · pp. 12–13

4.2 Eliminating every long bad event

  • The variable-dependency graph joins events whose length-18 macroblock choices overlap, and a scale-sensitive asymmetric local-lemma calculation produces an outcome avoiding every long bad event.For a fixed event of length ℓ, the number of neighbors of length r is at most 3(ℓ + r).Source: §4.2 · pp. 13–14

4.3 All scales and all adjacent intervals

  • A ternary word can be chosen so every adjacent equal-length pair has LCS at most (1 − η)ℓ; square-freeness handles ℓ ≤ 1000, and the long-event argument handles larger intervals.Taking a length-n prefix preserves the interval guarantee, which Lemma 2.2 converts to synchronization gap 1/2002.Source: §4 · p. 11, §4.3 · p. 14

5 From local entropy to synchronization

A local-entropy transfer theorem turns square-free sources with conditional entropy in long intervals into synchronization strings. Its applications include extremal square-free words, synchronization circles, and a stronger explicit ternary parameter.

5 From local entropy to synchronization

  • A square-free block-local source with positive interval conditional min-entropy supports an output with a fixed LCS deficit at every available adjacent interval pair.The theorem’s entropy, deletion-ball, boundary-loss, and dependency conditions are numerical and independent of source length.Source: §5 · pp. 14–15
  • Every square-free occurrence-wise substitution with K ≥2 and an outer language containing words of every positive length yields Q-ary synchronization strings for some fixed ε < 1.For sufficiently small δ, each requested length has an output factor satisfying the interval bound.Source: §5 · p. 15
  • The 18-uniform Brinkhuis source yields ternary 2001/2002-synchronization strings through a normalized edit-distance gap of 1/2001.The argument uses δ = 1/1000 and a = 1/80.Source: §5 · p. 16

5.1 An extremal square-free consequence

  • For every n ≥2493, a ternary word can be both extremal square-free and a 200001/200002-synchronization string.The Mol–Rampersad construction obtains interval entropy by choosing between two distinct length-93 blocks for each paired occurrence.Source: §5.1 · p. 16

5.2 A cyclic consequence

  • Every circularly square-free outer word of length at least two has an occurrence-wise output that is a synchronization circle; ternary examples of length 18N exist for every N ≥18.The circular preservation lemma keeps outputs circularly square-free, and the cyclic local-lemma argument controls long arcs.Source: §5.2 · p. 17

5.3 A stronger explicit parameter

  • A 54-uniform Brinkhuis family gives ternary synchronization strings of every finite length and one infinite string for every ε > 215/216.The refinement uses 952 choices per outer letter, finite deletion-shell checks, phase-sensitive matching-run bounds, and unequal-interval constraints.Source: §5.3 · p. 18

6 Abundance and randomized construction

The paper establishes exponential abundance of synchronized words and gives Las Vegas construction algorithms. A long-distance extension yields a ternary construction with expected O(n^2 log^3(n+2)) time and O(n^2) machine-word space.

6.1 Exponential abundance

  • The 54-uniform construction retains enough occurrence-wise choice entropy to produce exponentially many valid prefixes as well as full outputs.The proof counts good choice vectors and bounds the number of full outputs that share a length-n prefix.Source: §6.1 · p. 19
  • For every n ≥504, at least exp(n/9) ternary words satisfy the synchronization inequality.The general theorem gives at least exp((log K)n/(3m)) words for sufficiently large n under the substitution criterion.Source: §6.1 · pp. 18–19

6.2 A Las Vegas construction

  • A fixed occurrence-wise square-free substitution and polynomial-time outer-word generator suffice for a Las Vegas construction in expected polynomial time.The general procedure scans equal-block events and resamples precisely the macroblock variables in a violated event’s support.Source: §6.2 · p. 19
  • For every n ≥1, a ternary word satisfying the synchronization inequality can be generated by a Las Vegas algorithm in expected O(n^2 log^3(n+2)) time and O(n^2) machine words of space.The output also satisfies the stated distant-interval inequalities when the combined interval lengths are at least 30000 log n.Source: §6.2 · p. 20
  • With H = min{B, M}, the implementation caches entries for ordered pairs of starts; initialization costs O(M^2H^2), and each resampling recomputes affected entries in O(MH^3) time.The cache, pointers, marks, and temporary list use O(M^2) words.Source: §6.2 · p. 20

7 Consequences and open directions

The paper establishes the exact minimum constant alphabet size for synchronization strings and separates the ternary construction from the earlier four-symbol marking approach. It leaves the optimal ternary gap and faster, more locally accessible constructions open.

7 Consequences and open directions

  • Three symbols are the exact constant-alphabet threshold: ternary synchronization strings exist at every length for a fixed parameter below one, while binary strings have an unbounded-length obstruction.Occurrence-wise Brinkhuis choices provide long-range information while preserving ternary square-freeness, instead of adding a separate fourth-symbol marking layer.Source: §7 · pp. 20–21
  • The transfer theorem links long-range synchronization to interval conditional entropy exceeding the deletion-ball entropy rate, subject to bounded-scale and dependency conditions.The paper also applies the framework to make extremal square-freeness and a fixed synchronization gap hold simultaneously.Source: §7 · p. 21
  • The optimal ternary gap remains open, and the current long-distance construction still has a quadratic collection of start pairs as a bottleneck.Near-linear-time and locally accessible ternary constructions remain goals.Source: §7 · p. 21

A Proof of the local-entropy transfer theorem

The proof fixes a block-local square-free source and the theorem’s parameters, then derives geometric-series expressions from its hypotheses.

A Proof of the local-entropy transfer theorem

A.1 The probability of a bad interval

The section bounds the probability that adjacent intervals share an overly long common subsequence. It combines conditional entropy of one interval with a count of the values that can satisfy the bad-event condition.

A.1 The probability of a bad interval

  • For each available start t and integer ℓ > L, the bad event is that adjacent length-ℓ intervals have LCS greater than (1 − δ)ℓ.The entropy and counting bounds yield an exponentially small probability for every such event.Source: §A.1 · p. 22
  • Conditioning on all block variables outside the first interval’s contained blocks fixes the second interval, leaving a conditional point-mass bound for the first.The point-mass bound follows by applying the interval conditional-entropy bound to the first interval.Source: §A.1 · p. 22
  • The deletion-ball count and conditional entropy give Pr[Et,ℓ] ≤ e^(−γℓ) for every bad event.The count is at most e^(Φq(δ)ℓ); each counted value has conditional probability at most e^(−hℓ+b), and ℓ > L absorbs the boundary term b.Source: §A.1 · pp. 22–23

A.2 Dependencies across all scales

The argument controls dependencies among bad events across interval lengths, then applies the asymmetric Lovasz Local Lemma to avoid all long-scale events. Square-freeness handles the remaining short scales, yielding a synchronization gap.

A.2 Dependencies across all scales

  • For each event, at most 2ℓ + 2r + 2m + 1 events of length r can be neighbors; when L ≥ 2m + 1, this is at most 3(ℓ + r).The dependency graph joins events whose declared block-variable sets intersect.Source: §A.2 · p. 23
  • Under Equation (23), every long-interval bad event satisfies the asymmetric local-lemma criterion.The proof bounds neighboring charges using the dependency tail and the exponential bad-event estimate.Source: §A.2 · p. 23
  • The local-lemma argument produces an outcome avoiding every bad event with ℓ > L, while square-freeness excludes violations at 1 ≤ ℓ ≤ L.At short scales, adjacent intervals cannot be equal, so their LCS is at most ℓ − 1.Source: §A.2 · pp. 23–24
  • Every adjacent interval pair then has normalized insertion–deletion distance at least δ/(2 + δ), giving synchronization for each ε with 1 − δ/(2 + δ) < ε < 1.Factors inherit the equal-block inequalities and the same conclusion.Source: §A.2 · p. 24

B Extremal square-free synchronization strings

The paper applies the local-entropy transfer theorem to sources built from square-free words, including extremal square-free words. It also gives sufficiently long ternary synchronization circles and a phase-recognition property for the circular construction.

B Extremal square-free synchronization strings

  • For every n ≥ 2493, the construction yields an extremal square-free synchronization string with parameter 200001/200002.Occurrence-wise choices in paired length-93 macroblocks provide interval entropy while every outcome remains extremal square-free.Source: B Extremal square-free synchronization… · pp. 24–26

C All sufficiently large synchronization-circle lengths

  • For every n ≥ 10008, there is a ternary 5201/5202-synchronization circle.The construction deletes a short factor from an 18-uniform output to obtain circle lengths not divisible by 18.Source: C All sufficiently large… · p. 26

C.1 Circular Dejean words and phase recognition

  • Every length-14 factor of an occurrence-wise output determines its starting-position phase modulo 18, and the six codewords are pairwise distinct.At length 13, factors can occur at two phases, so the stated factor length cannot be shortened to 13.Source: §C.1 · pp. 26–27

C.2 A bounded defect

The bounded-defect construction deletes a gap and joins its endpoints, creating a seam where macroblock phases shift. Phase recognition excludes interior seam crossings, while a finite argument handles the remaining possible squares.

C.2 A bounded defect

  • Deleting a cyclic factor of length g shifts the inherited macroblock phases by g modulo 18 at the new defect seam.When g is not divisible by 18, a square crossing the seam cannot place it at least 14 symbols from its start, midpoint, and end.Source: §C.2 · p. 27
  • Any remaining square crossing the seam has root length at most 288 when the deleted gap has length 1 to 35.For roots of length at least 27, seam-free equal segments and phase recognition reduce the bound to a comparison of outer factors in a 7/4+-free circle.Source: §C.2 · pp. 27–28
  • For every N > 555 and nonzero residue r modulo 18, a partially fixed occurrence-wise source becomes circularly square-free after deleting gr characters.The finite boundary lemma chooses periodic Brinkhuis choices and a gap position to eliminate roots up to 288; the verification covers 306 template–context cases.Source: §C.2 · pp. 28–29

C.3 The local lemma with a bounded defect

The bounded-defect argument uses a local lemma to avoid long synchronization violations, while square-freeness handles short scales. A larger 54-uniform Brinkhuis family supplies conditional entropy and deletion-ball bounds for a stronger ternary construction.

C.3 The local lemma with a bounded defect

  • Long cyclic adjacent-arc violations have probability below e^-ℓ/135, and the asymmetric local lemma yields an assignment avoiding every event with ℓ > 2600.Square-freeness supplies the complementary short-scale bound.Source: §C.3 · pp. 29–30
  • The circular output has normalized edit distance at least 1/5201 in every rotation, and every length n ≥ 10008 is realized, yielding strict parameter 5201/5202.Lengths divisible by 18 use the construction with strict gap 1/2002; other lengths are realized by adjusting the macroblock count.Source: §C.3 · p. 30

D Quantitative strengthening from the 54-uniform family

  • The 54-Brinkhuis 952-triple preserves ternary square-freeness under occurrence-wise substitution and maps distinct choice vectors to distinct outputs.Its three codebooks are related by cyclic alphabet permutations, and the first codebook is closed under reversal.Source: D Quantitative strengthening from the… · p. 31
  • For intervals of length at least 54, occurrence choices can be exposed to fix the right interval while bounding the conditional mass of each exact left-interval value.The bound accounts for a partial macroblock at the left endpoint through suffix multiplicities and offset-dependent probabilities.Source: D Quantitative strengthening from the… · p. 31

D.1 Deletion balls within the source support

  • Counting deletion fillings within the source support reduces deletion-ball volume because neighboring letters must differ, while block phases rule out some matching-run patterns.For a fixed deletion pattern, the undeleted letters determine the remaining word up to at most q − 1 choices per deleted position.Source: §D.1 · p. 32
  • Phase-dependent bounds on uninterrupted matching runs feed a recurrence that upper-bounds the common-subsequence length for adjacent factors after specified deletions.At total length 227, a one-deletion alignment permits at most 92 matches, below the 113 required.Source: §D.1 · pp. 32–33

D.2 Direct control of unequal intervals

Directly including unequal adjacent intervals in the local lemma avoids relying only on an equal-length reduction. Finite short-shell exclusions and probability bounds for retained events yield a ternary word with the stated edit-distance guarantee.

D.2 Direct control of unequal intervals

  • For odd total lengths 229 through 463, adjacent factors whose lengths differ by one cannot have edit distance one.Parity makes edit distance one the only possible violation of the target bound in these cases.Source: §D.2 · pp. 33, 36
  • At total lengths 456, 462, and 464, adjacent factors with length difference at most two cannot have edit distance two.Square-freeness excludes equal factors at edit distance zero; the finite codebook checks exclude the remaining two-deletion cases.Source: §D.2 · p. 34
  • For admissible unequal interval pairs, the direct bad-event probability is bounded using conditional point mass and supported deletion-volume estimates, then an asymmetric local lemma avoids retained events.Pairs with zero probability are discarded; omitted short or imbalanced cases are checked separately.Source: §D.2 · pp. 34–36
  • Every length admits a ternary word whose adjacent nonempty intervals satisfy the non-strict normalized edit-distance bound 1/216, giving strict synchronization for every ε > 215/216.The proof handles shorter lengths by taking a prefix of a constructed word.Source: §D.2 · pp. 35–36

E Exact calculations for the ternary parameters

The appendix supplies exact finite checks for short deletion shells and rational bounds for the unequal-event calculations. Together, these calculations verify the quantitative margins used by the ternary construction.

E Exact calculations for the ternary parameters

  • Finite mask-graph classification and consistency checks exclude every one-deletion shell in the stated range for the 54-uniform family.The classification leaves 344 residual contexts, all of which are ruled out by inconsistent relation cores.Source: E Exact calculations for the ternary… · pp. 37–38
  • Exact relation and coloring checks exclude every edit-distance-two pair in the specified shells at total lengths 456, 462, and 464.The checks combine empty-relation tests with square-free outer-coloring tests.Source: E Exact calculations for the ternary… · pp. 38–39
  • The exact unequal-event charge calculation establishes the finite bounds and a uniform analytic tail used to control retained events.The calculation combines conditional-mass bounds, deletion-volume estimates, and the capacity recurrence.Source: E Exact calculations for the ternary… · pp. 39–40
  • The parameter margins verify 9/500 > 1/80 + 1/245 and η/(2 + η) = 1/2001 > 1/2002 for η = 1/1000.The logarithmic bounds include 137/20 < log 952 < 7.Source: E Exact calculations for the ternary… · pp. 37, 42

F Distant intervals and bounded event lengths

The paper adds bounded-length events for distant intervals and uses a matching-path reduction to extend the guarantee beyond those events. The resulting finite words satisfy long-distance constraints, while the infinite-word conclusion is limited to adjacent intervals.

F Distant intervals and bounded event lengths

  • Distant bad events of total length s have probability below e^-s/50 for s ≥ 2800.When the length imbalance is below the target threshold, exposing choices outside one interval fixes the other and bounds conditional point mass.Source: F Distant intervals and bounded event… · p. 42
  • Adding distant events preserves the variable local-lemma condition, and Moser–Tardos resampling uses an expected O(M) resamplings.The bounded adjacent and distant event system is the one covered by the combined local lemma.Source: F Distant intervals and bounded event… · p. 43
  • For finite length n, the construction ensures normalized edit distance at least 1/216 for adjacent intervals and ordered disjoint intervals of total length at least R, with R = O(log n).The stated threshold is R < 30000 log n; the infinite-word conclusion in the paper concerns adjacent inequalities only.Source: F Distant intervals and bounded event… · pp. 43–44
  • A violating alignment can be split into shorter violating subpairs until an included bounded event is reached, extending the guarantee to longer disjoint pairs.The reduced intervals remain ordered and disjoint, though they need not remain adjacent.Source: F Distant intervals and bounded event… · pp. 43–44

Related papers

Loading 2609.04122v2…