Mapped Exponent and Asymptotic Critical Exponent of Words

Aleksi Saarela; Aleksi Vanhatalo; Eva Foster

REVIEW 2 major objections 4 minor 17 references

Mapped Exponent and Asymptotic Critical Exponent of Words

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read An injective morphism cannot increase the asymptotic critical exponent of an infinite binary word by a full integer; the increase is zero when the exponent is integral or letter frequencies are uniform, and strictly below one otherwise.

desk verdict Genuinely new invariants and a strong binary dichotomy; the only clear error is a false equality in Thm 3.13's proof, and a terse diagonal step in Thm 3.16 that should be expanded. read the letter →

arxiv 2506.04091 v2 pith:KGCCGFH2 submitted 2025-06-04 math.CO cs.FL

Eva Foster , Aleksi Saarela , Aleksi Vanhatalo This is my paper

classification math.COcs.FL MSC 68R15

keywords combinatoricsonwordsinjectivemorphismsfractionalexponentasymptoticcriticalrepetitionsinsynchronizingbinarymapped

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies how much injective morphisms can amplify repetition in a word, measured by the fractional exponent of finite words and by the asymptotic critical exponent of infinite words. For finite words it gives a complete classification of the words whose mapped fractional exponent can be made arbitrarily large, with a simple form in the binary case, and bounds the mapped exponent by the word length when it is finite. For infinite words it proves that an injective morphism can multiply the asymptotic critical exponent by at most a constant depending only on the alphabet size, and it provides words where the increase is linear in the alphabet size. The central discovery is the binary theorem: if the asymptotic critical exponent of an infinite binary word is finite, an injective morphism can never raise it by a full integer; it stays equal when the exponent is an integer or letter frequencies are uniform, and otherwise stays strictly below the next integer. A consequence is that repetition-averse binary words with asymptotic critical exponent one exist and remain repetition-averse under every injective morphism.

What carries the argument

The machinery has two load-bearing parts. The first is the fractional exponent $\operatorname{E}(u)=\sup\{r\in\mathbb{Q}: u=v^r\text{ for some word }v\}$, together with the asymptotic critical exponent $\operatorname{ACE}(w)=\limsup_{n\to\infty}\{\operatorname{E}(u): u\in\operatorname{Fact}_n(w)\}$ and its mapped version $\operatorname{ACE}_I(w)=\sup_h\operatorname{ACE}(h(w))$ over injective morphisms $h$. The second is the notion of a synchronizing word of a morphism $h$: a factor $w=w_1w_2$ whose every occurrence inside a concatenation of the images $h(a)$ is forced to align with block boundaries, making $w_1$ a legal prefix and $w_2$ a legal suffix of the factored blocks. The proof splits on whether $h(w)$ has arbitrarily long non-synchronizing factors: if it does, a compactness argument with shifted sequences, $X$-factorizations, and the defect theorem for bi-infinite words produces a periodic limit and forces $\operatorname{ACE}(w)=\infty$; if it does not, synchronizing-word lemmas from earlier work bound $\operatorname{ACE}(h(w))$ by $\lceil\operatorname{ACE}(w)\rceil$, and in the binary case a uniform positive lower bound on letter frequencies inside the relevant factors yields the strict gap $\lambda_u$. For finite words, the classification is carried by a classical periodicity uniqueness theorem and a lemma showing that when one letter maps to a block at least as long as the period, the gaps between occurrences of that letter must be identical, yielding the factorization condition.

What would settle it

To test the binary theorem, search for an infinite binary word $w$ with finite non-integer $\operatorname{ACE}(w)$ and an injective morphism $h$ with $\operatorname{ACE}(h(w))\ge\lceil\operatorname{ACE}(w)\rceil$; the theorem predicts none exists. A more targeted check is the unproved extraction in the proof of Theorem 3.16: build a binary word with finite non-integer $\operatorname{ACE}$ whose relevant factor sequences admit no uniform lower bounds $r,\delta_a,\delta_b$, and see whether the letter-frequency ratios of the extracted sequence tend to zero while exponents stay below ACE; if such a sequence exists, the gap $\lambda_u$ and the theorem fail. The words of Theorem 3.22, with ACE just above $n$ and mapped ACE almost $n+1$, are natural candidates for numerical experiment.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.19: for an infinite binary word $w$ with finite $\operatorname{ACE}(w)$, if $w$ has uniform letter frequencies or $\operatorname{ACE}(w)$ is an integer, then $\operatorname{ACE}_I(w)=\operatorname{ACE}(w)$; otherwise $\operatorname{ACE}_I(w)<\lceil\operatorname{ACE}(w)\rceil$. In words: no injective morphism can increase the asymptotic critical exponent of a binary word by one or more. The theorem is obtained by splitting the behaviour of $h(w)$ into two regimes: if $h(w)$ has arbitrarily long factors that are not synchronizing words of $h$, then $w$ itself has infinite asymptotic critical exponent, so the interesting case is when all long factors are synchronizing; there a structural lemma bounds $\operatorname{ACE}(h(w))$ by $\lceil\operatorname{ACE}(w)\rceil$, and in the binary non-integer case a uniform gap $\lambda_u>0$ separates $\operatorname{ACE}(h(w))$ from the next integer. The paper also establishes the finite-word classification ($\operatorname{E}_I(w)=\infty$ iff a certain factorization with comparable blocks exists, which for binary words reduces to the shape $b^{j_1}(ab^{j_2})^k ab^{j_3}$ up to exchanging letters) and the general-alphabet bound $\operatorname{ACE}_I(w)=O(|\Sigma|^2\operatorname{ACE}(w))$, together with examples showing the increase can be linear in the alphabet size.

Load-bearing premise

The load-bearing premise is that if the family of factor sequences produced in the proof has no uniform positive lower bounds on their lengths and letter frequencies, then one can extract a single sequence whose relevant letter-frequency ratios tend to zero; the paper asserts this extraction without proof, and the strict inequality $\operatorname{ACE}_I(w)<\lceil\operatorname{ACE}(w)\rceil$ for binary words with non-integer asymptotic critical exponent rests on it.

Editorial extensions

If this is right

For every infinite binary word, an injective morphism cannot increase the asymptotic critical exponent by one or more; if the exponent is an integer, it is left unchanged.
There are binary words with $\operatorname{ACE}_I(w)=1$, so some words are completely resistant to morphic inflation of their asymptotic repetition rate.
The forbidden full-integer jump can be approached arbitrarily closely: for every $n$ and every small $\lambda,\delta>0$ there is a binary word with $\operatorname{ACE}$ just above $n$ whose mapped asymptotic critical exponent reaches at least $n+1-\delta$.
For finite words, the mapped fractional exponent is either infinite or at most the word length, and the binary words with infinite mapped exponent are exactly those of the form $b^{j_1}(ab^{j_2})^k ab^{j_3}$ up to letter exchange.
Over alphabets of size $2n$, there are words with asymptotic critical exponent $1$ whose mapped asymptotic critical exponent is at least $n$, while the general upper bound is quadratic in the alphabet size, leaving a gap posed as an open problem.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If correct, the binary theorem makes $\lceil\operatorname{ACE}(w)\rceil$ a kind of morphic invariant: injective images cannot cross integer layers of asymptotic repetition, so the gap to the next integer becomes a stable characteristic of the word rather than a property of the morphism.
A natural testable extension is to compute $\operatorname{ACE}_I$ for the balanced binary sequences studied in the cited literature; since those words have uniform letter frequencies, the theorem predicts exact morphic invariance, which can be checked numerically for concrete morphisms.
The wider-alphabet question the paper leaves open is whether the maximal multiplicative increase $\operatorname{ACE}_I/\operatorname{ACE}$ grows linearly in the alphabet size; the $2n$-letter construction supplies the lower-bound direction of that conjecture, and the quadratic upper bound is likely loose.
For finite words the classification suggests a complexity question: checking whether a binary word has infinite mapped exponent is a simple pattern match, while the general-alphabet condition with comparability of mapped blocks might be computationally harder; the paper poses this as an open problem.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's my honest read. The paper introduces two genuinely new invariants, the mapped fractional exponent EI and the mapped asymptotic critical exponent ACEI, and proves real results about them: a complete characterization of finite words with unbounded EI (Thm 2.7), a general upper bound for ACEI (Thm 3.11), and a clean binary dichotomy (Thm 3.19) saying injective morphisms cannot raise ACE by one or more. The tightness constructions in Thms 2.6, 2.9, and 3.22 round it out. The proofs are mostly detailed and use standard tools appropriately, and the authors properly attribute the synchronizing-word machinery to Dvořáková–Ochem–Opočenská and the integer-exponent starting point to Saarela.

The real soft spot is Theorem 3.13. The displayed equality h(u_{1,j}...u_{n,j}) = (h(u_{1,j})c)^{n-1/j} fails a length check: for n=2, j=1 the left side has length 4 and the right side length 3. So the proof of ACEI(w_n) ≥ n, as written, is not correct. This is isolated to that lower-bound construction and does not appear to touch the binary results, but it would need a fix before publication.

The other concern is the binary case of Theorem 3.16. The proof needs common positive lower bounds r, δa, δb for all factor sequences in F, and it asserts that if no such bounds exist, one can pick elements from the sequences to produce a sequence where one of the quantities goes to zero. That is a diagonal selection that should be written out; as it stands it is too terse. The stress-test's additional claim that low letter frequency does not force a long run is not valid, however: if b-runs in u were bounded by C, then any factor's a-frequency would be bounded below by roughly 1/(C+1), so limsup |s_n|_a/|s_n|=0 really would force arbitrarily long b-runs. So the uniform-gap argument is likely repairable, but the exposition needs to be explicit.

Who is this for: combinatorics on words researchers, especially those working on morphisms and repetition phenomena. The invariants are natural and likely to be cited. The main theorems (2.7 and 3.19) look solid to me, and the flaws are not load-bearing for those results, as far as I can see. This deserves a serious referee; I would send it to review with a request to fix Thm 3.13 and expand the compactness argument in Thm 3.16.

Referee Report

2 major / 4 minor

Summary. The paper studies how injective morphisms can increase the repetitiveness of a word, measuring finite words by fractional exponent and infinite words by asymptotic critical exponent. For finite words, Theorem 2.7 characterizes the words with infinite mapped fractional exponent via a factorization-and-comparability condition, with a simple binary corollary, and Theorems 2.6 and 2.9 supply extremal examples. For infinite words, Theorem 3.11 proves a general upper bound ACEI(w) <= (|Sigma|+1)+|Sigma|(|Sigma|+1)(floor(ACE(w))+1), Theorem 3.13 gives a linear lower-bound example, and Theorems 3.16 and 3.19 give a binary result stating that an injective morphism cannot increase the asymptotic critical exponent by a full integer, with an extremal example of a gap arbitrarily close to one in Theorem 3.22.

Significance. The paper contains several elegant and potentially lasting contributions. The classification of finite words with infinite mapped exponent is clean and likely to be useful, the finite bound EI(w) <= |w| is tight up to constants, and the binary infinite-word theorem is a strong dichotomy with a surprising strict-inequality conclusion. The authors also make careful attributions to the synchronizing-word proof of Dvorakova, Ochem, and Opocenska and to prior work of Saarela and Cassaigne, and they provide explicit extremal constructions. If the two proof issues noted below are repaired, the paper would be a solid contribution to combinatorics on words.

major comments (2)

[Section 3.2, proof of Theorem 3.13] The displayed equality h(u_{1,j}u_{2,j}...u_{n,j}) = (h(u_{1,j})c)^(n-1/j) fails a length check. For n=2 and j=1, the left side has length 4, while the right side, being a fractional power of a word of length 3, has non-integral total length and in particular cannot equal the left side. The correct exponent appears to be n^2 j/(n j+1) = n - n/(n j+1), since h(u_{1,j})...h(u_{n,j}) has length n^2 j and (h(u_{1,j})c) has length n j+1. Because this equality is the entire justification for the lower bound ACEI(w_n) >= n, the display must be corrected and the argument checked with the corrected exponent.
[Section 3.3, proof of Theorem 3.16, final paragraph] The passage asserting the existence of uniform lower bounds r, delta_a, delta_b for all sequences in the family F is too compressed. The sentence 'If no such r, delta_a or delta_b exists, then we could construct a sequence belonging to F...' is a diagonal-selection argument, but the text does not verify that the selected elements can be chosen so that the defining conditions of F are preserved, in particular liminf |p_n|/|t_n| > 0 and l_n -> floor(ACE(u)). This step is load-bearing for the strict inequality ACEI(w) < ceil(ACE(w)) in Theorem 3.19, so it should be expanded into a complete argument. A standard diagonalization can likely supply the missing details, but as written the step is asserted rather than proved; I do not dispute the companion claim that delta_a tending to zero forces arbitrarily long b-runs in a fixed binary word.

minor comments (4)

[Section 3.2, proof of Theorem 3.13] In the proof, the text says 'a sequence of factors of wl' and later writes 'lim_{l->infty} E(x_n)'; these should be 'w_n' and 'x_l', respectively.
[Section 3.4, proof of Corollary 3.20] The reference 'Theorem 3.12 and Corollary 3.19' should read 'Theorem 3.12 and Theorem 3.19', since the statement quoted is Theorem 3.19.
[Section 3.3, proof of Theorem 3.16] The proof uses the letter F both for the family of factor sequences and for the set of factors in the surrounding discussion; a different symbol or a one-line clarification would avoid ambiguity.
[Section 3.2, proof of Theorem 3.9] The sentence 'we can also assume that ACE_I(u) is finite as we clearly have ACE_I(u) <= ACE_I(w)' should be rephrased, since if ACE_I(u) is infinite the desired equality is immediate and the subsequent contradiction argument only concerns the finite case.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: all load-bearing claims are proved from external lemmas, attributed borrowings, or direct construction; the flagged binary-case extraction is a proof gap, not circularity.

full rationale

The paper contains no fitted parameters, no normalization that forces the stated bound, and no dependence on the authors' own prior results for the new theorems. The finite-word classification (Thm 2.7) is proved by an implication chain using Fine–Wilf and injectivity; [14] is cited only as the origin of the question and for a primitive-word observation, with the needed lemma (2.5) actually reproved in the text. The infinite-word results rest on external theorems: Beck and Cassaigne for words of ACE 1, Morse–Hedlund for periodicity, Karhumäki–Maňuch–Plandowski for the defect theorem, Lothaire for degree bounds, and Dvořáková–Ochem–Opočenská's synchronizing-word theorem, which is explicitly borrowed with permission and marked in bold. The binary strict bound ACEI(w) < ⌈ACE(w)⌉ in Thm 3.19 depends on the uniform-gap argument in the final paragraph of Sec. 3.3. There, the assertion that if no uniform lower bounds r, δa, δb exist then one can construct a sequence in F with a zero limit by 'picking elements from sequences' is not fully proved, and the claim that limsup |s_n|_a/|s_n| = 0 forces a long monochromatic run is questionable. But these are proof gaps, not circularity: the quantities r, δa, δb, and λu are extracted from u, not from the conclusion ACEI(w) < ⌈ACE(w)⌉, and the theorem is not obtained by renaming a fitted value or by invoking the authors' own earlier claim as the load-bearing premise. Under the strict standard that a circular step must be exhibited as an equation, reduction, or self-citation chain equivalent to its own input, no such step is present.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters or invented entities. The paper's contribution is new definitions and proofs; all external inputs are standard, cited theorems.

assumptions (5)

standard math Fine-Wilf theorem (Theorem 2.1)
Used to force a common period when two powers overlap; standard external theorem.
standard math Karhumäki-Maňuch-Plandowski defect theorem (Theorem 3.5)
Used in Corollary 3.6 to show a bi-infinite word with two factorizations over two image words is periodic.
standard math X-degree bound (Theorem 3.7, from Lothaire)
Used in Theorem 3.11 to bound the number of disjoint interpretations of long factors.
domain assumption Existence of binary infinite word with ACE = 1 (Beck; Cassaigne, Theorem 3.12)
External existence result needed for the constructions in Theorems 3.13 and 3.20. It is cited, not proved.
standard math Dvořáková-Ochem-Opočenská Theorem 3.15 on synchronizing words preserving ACE
Used directly in Theorem 3.19 for the uniform-letter-frequency case.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Mapped Exponent and Asymptotic Critical Exponent of Words." pith.science (2026). https://pith.science/paper/KGCCGFH2

@misc{pith2026250604091,
  author       = {Pith},
  title        = {Pith review of: Mapped Exponent and Asymptotic Critical Exponent of Words},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KGCCGFH2}},
  note         = {Machine review of arXiv:2506.04091}
}

read the original abstract

We study how much injective morphisms can increase the repetitiveness of a given word. This question has a few possible variations depending on the meaning of ``repetitiveness''. We concentrate on fractional exponents of finite words and asymptotic critical exponents of infinite words. We characterize finite words that, when mapped by injective morphisms, can have arbitrarily high fractional exponent. For infinite words, alongside other results, we show that the asymptotic critical exponent grows at most by a constant factor (depending on the size of the alphabet) when mapped by an injective morphism. For both finite and infinite words, the binary case is better understood than the general case.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[1]

J. Beck. An application of Lov´ asz local lemma: there exists an infinite 01-sequence containing no near identical intervals. In Finite and infinite sets, Vol. I, II (Eger, 1981), volume 37 of Colloq. Math. Soc. J´ anos Bolyai, pages 103–107. North-Holland, Amsterdam, 1984

work page 1981
[2]

On extremal properties of the Fibonacci word

Julien Cassaigne. On extremal properties of the Fibonacci word. RAIRO-Theoretical Informatics and Applications , 42(4):701–715, 2008

work page 2008
[3]

For each α > 2 there is an infinite binary word with critical exponent α

James Currie and Narad Rampersad. For each α > 2 there is an infinite binary word with critical exponent α. The Electronic Journal of Combinatorics , 15, 2008

work page 2008
[4]

On balanced se- quences and their asymptotic critical exponent

Francesco Dolce, L’ubom ´ ıra Dvoˇ r´ akov´ a, and Edita Pelantov´ a. On balanced se- quences and their asymptotic critical exponent. In International Conference on Language and Automata Theory and Applications , pages 293–304. Springer, 2021

work page 2021
[5]

Critical exponent of binary words with few distinct palindromes

L’ubom ´ ıra Dvoˇ r´ akov´ a, Pascal Ochem, and Daniela Opoˇ censk´ a. Critical exponent of binary words with few distinct palindromes. The Electronic Journal of Combi- natorics, 31(2), 2024. 25

work page 2024
[6]

On nonrepetitive sequences

Roger Entringer, Douglas Jackson, and Joseph Schatz. On nonrepetitive sequences. Journal of Combinatorial Theory, Series A , 16(2):159–164, 1974

work page 1974
[7]

Uniqueness theorems for periodic functions

Nathan Fine and Herbert Wilf. Uniqueness theorems for periodic functions. Pro- ceedings of the American Mathematical Society , 16(1):109–114, 1965

work page 1965
[8]

Binary words with few squares

Tero Harju and Dirk Nowotka. Binary words with few squares. Bulletin of the EATCS, 89:164–166, 2006

work page 2006

Show all 17 references

[9]

On cube-freeω-words generated by binary morphisms

Juhani Karhum¨ aki. On cube-freeω-words generated by binary morphisms. Discrete Applied Mathematics, 5(3):279–297, 1983

1983
[10]

A defect theorem for bi-infinite words

Juhani Karhum¨ aki, J´ an Maˇ nuch, and Wojciech Plandowski. A defect theorem for bi-infinite words. Theoretical computer science, 292(1):237–243, 2003

2003
[11]

Lothaire

M. Lothaire. Combinatorics on words . Encyclopedia of mathematics and its appli- cations ; 17. Cambridge University Press, Cambridge, 1997

1997
[12]

Lothaire

M. Lothaire. Algebraic combinatorics on words . Encyclopedia of mathematics and its applications ; 90. Cambridge University Press, Cambridge, 2002

2002
[13]

Marston Morse and Gustav A. Hedlund. Symbolic dynamics. American Journal of Mathematics, 60(4):815–866, 1938

1938
[14]

Mapping words to powers by morphisms, 2025

Aleksi Saarela. Mapping words to powers by morphisms, 2025. Preprint. arXiv: 2503.00960

2025 arXiv
[15]

Codes ` a longueur variable

Marcel-Paul Sch¨ utzenberger. Codes ` a longueur variable. Cours l’´ ecole d’´ et´ e de l’OTAN sur les m´ ethodes combinatoires en th´ eorie de l’information et du codage, Royan, France, 1965

1965
[16]

¨Uber unendliche Zeichenreihen

Axel Thue. ¨Uber unendliche Zeichenreihen. Norske Vid Selsk. Skr. I Mat-Nat Kl.(Christiana), 7:1–22, 1906

1906
[17]

Sturmian words and words with a critical exponent

Drew Vandeth. Sturmian words and words with a critical exponent. Theoretical computer science, 242(1-2):283–300, 2000. 26

2000

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

J. Beck. An application of Lov´ asz local lemma: there exists an infinite 01-sequence containing no near identical intervals. In Finite and infinite sets, Vol. I, II (Eger, 1981), volume 37 of Colloq. Math. Soc. J´ anos Bolyai, pages 103–107. North-Holland, Amsterdam, 1984

work page 1981

[2] [2]

On extremal properties of the Fibonacci word

Julien Cassaigne. On extremal properties of the Fibonacci word. RAIRO-Theoretical Informatics and Applications , 42(4):701–715, 2008

work page 2008

[3] [3]

For each α > 2 there is an infinite binary word with critical exponent α

James Currie and Narad Rampersad. For each α > 2 there is an infinite binary word with critical exponent α. The Electronic Journal of Combinatorics , 15, 2008

work page 2008

[4] [4]

On balanced se- quences and their asymptotic critical exponent

Francesco Dolce, L’ubom ´ ıra Dvoˇ r´ akov´ a, and Edita Pelantov´ a. On balanced se- quences and their asymptotic critical exponent. In International Conference on Language and Automata Theory and Applications , pages 293–304. Springer, 2021

work page 2021

[5] [5]

Critical exponent of binary words with few distinct palindromes

L’ubom ´ ıra Dvoˇ r´ akov´ a, Pascal Ochem, and Daniela Opoˇ censk´ a. Critical exponent of binary words with few distinct palindromes. The Electronic Journal of Combi- natorics, 31(2), 2024. 25

work page 2024

[6] [6]

On nonrepetitive sequences

Roger Entringer, Douglas Jackson, and Joseph Schatz. On nonrepetitive sequences. Journal of Combinatorial Theory, Series A , 16(2):159–164, 1974

work page 1974

[7] [7]

Uniqueness theorems for periodic functions

Nathan Fine and Herbert Wilf. Uniqueness theorems for periodic functions. Pro- ceedings of the American Mathematical Society , 16(1):109–114, 1965

work page 1965

[8] [8]

Binary words with few squares

Tero Harju and Dirk Nowotka. Binary words with few squares. Bulletin of the EATCS, 89:164–166, 2006

work page 2006