Repetition thresholds along arithmetic progressions: overlap-free binary words and their decimations

Abstract

For an infinite word w=w₀w₁w₂… over a k-letter alphabet and an integer p ≥ 1, let su(w, p)=w₀wₚw₂ₚ… be the decimation of w modulo p, and let RT(k,p) be the infimum of the rationals α for which some infinite k-ary word w has both w and su(w, p) free of factors of exponent exceeding α. At p=1 this is Dejean's repetition threshold RT(k). Our main theorem is that for every p with 1 ≤ p ≤ 40 there is an infinite binary overlap-free word whose decimation modulo p is again overlap-free if and only if p is a power of two. The statement quantifies over all infinite binary overlap-free words, an uncountable set. Brown, Rampersad, Shallit and Vasiga proved the corresponding statement for the single word t: the linear subsequence (tᵢₙ₊ₐ)_(n ≥ 0) is overlap-free exactly when i is a power of two. Our negative half is instead an exhaustion of the whole binary overlap-free language at each of the 34 non-powers of two p ≤ 40, and it delivers for each such p the exact length of the longest binary overlap-free word whose decimation modulo p is overlap-free — 34 values, from 18 at p=3 to 766 at p=38 — which no statement about t alone can produce. The positive half is uniform: su(t, 2ʲ)=t for every j, with no bound on j. We further prove RT(2,3) ≥ 5/2; RT(2,p) ≥ 7/3 for each of the seven moduli p ∈ {5,6,7,9,10,11,12}; and RT(3,4) ≥ 11/6. Each of these bounds on an infimum over a continuum of exponents comes from a single exhaustive search, through a monotonicity lever that converts one search at a non-strict threshold into a bound valid on a whole half-line of exponents. Finally we record the exact sense in which Harju's theorem is sharp: RT(3,2)=2, the infimum being attained just above 2 and not at 2. Every theorem, proposition and lemma stated below is machine-checked in Lean 4.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-08-30 15:34 UTC

   File fingerprint

   69c1563236e4cbb92087cae742b57546cc60920da96de4ce10568506fd4ff874