Pith. sign in

REVIEW 6 minor 13 references

Words of linear subword complexity have only boundedly many distinct upper (or lower) frequencies among their factors of any fixed length.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-31 12:34 UTC pith:EYBJJN73

load-bearing objection Clean extension of the three-gap/Boshernitzan frequency bound to arbitrary words via upper/lower frequencies, with a matching superlinear counterexample that shows linear complexity is the right threshold.

arxiv 2607.28273 v1 pith:EYBJJN73 submitted 2026-07-30 cs.FL

Frequencies of subwords in words of linear subword complexity

Jason Bell , Laindon Burnett , Chris Schulz This is my paper
classification cs.FL MSC 68R1511B85
keywords subword frequencyinfinite wordsRauzy graphscombinatorics on wordsSturmian wordssubword complexitylinear complexity
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper proves that in any right-infinite word that is not eventually periodic, the number of distinct upper frequencies of length-(N+1) factors is at most three times the complexity jump p(N+1)-p(N), plus one (and the same bound holds for lower frequencies, and for ordinary frequencies when they exist). When the complexity function itself grows at most linearly, the jumps stay bounded, so a single constant caps the number of distinct frequencies at every length. The authors show the bound is sharp in spirit: once complexity is allowed to grow even slightly faster than linear—O(n f(n)) for any f tending to infinity—one can construct words whose number of distinct upper frequencies becomes unbounded. The result therefore pins a clean combinatorial threshold between “uniformly few frequencies” and “arbitrarily many frequencies.”

Core claim

For a non-eventually-periodic right-infinite word w, the sets of upper frequencies and of lower frequencies of its length-(N+1) factors each have cardinality at most 3(p_w(N+1)-p_w(N))+1. Consequently, linear complexity forces a uniform bound independent of N. The same counting also shows that ordinary frequencies, when they exist, obey the identical bound.

What carries the argument

The reduced Rauzy graph whose vertices are the infinitely occurring left- or right-special factors of length N; simple paths between them carry constant upper (or lower) frequency, so the number of distinct frequencies is controlled by the number of edges, which is at most 3Δp^0(N).

Load-bearing premise

The edge count of the reduced Rauzy graph is bounded by three times the complexity jump, using only the separate inequalities that there are at most Δp left-special and at most Δp right-special vertices.

What would settle it

Exhibit a single infinite word of linear complexity whose number of distinct upper frequencies of length-N factors grows unboundedly with N, or compute an explicit word family whose reduced-Rauzy edge count exceeds 3Δp+1 for some N.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Any infinite word of linear complexity admits only boundedly many distinct Banach or logarithmic frequencies of factors of each length.
  • Sturmian words and other low-complexity aperiodic words automatically satisfy a uniform three-gap-type bound on factor frequencies without needing unique ergodicity.
  • Once complexity exceeds every linear multiple, the uniform frequency bound can fail, so linear growth is the precise threshold for the phenomenon.
  • The same reduced-graph counting applies verbatim to any notion of density that is constant along simple paths of the ordinary Rauzy graph.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The +1 term (the zero frequency of finite-occurrence factors) suggests that refinements excluding transient factors might tighten the constant from 3 to something closer to 2.
  • The construction that realises O(n f(n)) complexity with unbounded frequency counts can probably be adapted to produce words whose ordinary frequencies exist yet still become arbitrarily numerous.
  • A matching lower-bound example achieving roughly 3Δp distinct frequencies would show that the Rauzy-graph estimate is essentially optimal rather than merely convenient.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 6 minor

Summary. The paper proves that for any right-infinite word w that is not eventually periodic, the number of distinct upper (resp. lower) frequencies of length-(N+1) factors is at most 3(p_w(N+1)-p_w(N))+1. The argument adapts the Balková–Pelantová reduced-Rauzy-graph method: after restricting to factors that occur infinitely often, upper frequencies are constant on interiors of simple paths, and the number of edges of the reduced graph is at most 3Δp^0_w(N). When p_w is linearly bounded, Cassaigne’s bound on Δp_w therefore yields a uniform constant independent of N. Complementary constructions show the linear regime is essentially sharp: there exist words with p_w(n)=O(n f(n)) for any weakly increasing f→∞ whose number of distinct upper frequencies is unbounded in N, and words realizing exponentially many distinct frequencies of length-d factors.

Significance. The result cleanly extends the classical three-frequency phenomenon for Sturmian words and Boshernitzan’s bound for uniformly recurrent linear-complexity words to arbitrary (not necessarily recurrent) infinite words, by working with upper and lower frequencies. The counting argument is elementary, self-contained, and correctly tracks the contribution of left- and right-special vertices. The matching super-linear examples—especially the hierarchical substitution construction of Example 3.2—are technically substantial and show that the “in particular” clause cannot be pushed beyond linear complexity. Together the positive theorem and the sharpness examples form a complete, publishable contribution to the combinatorial theory of factor frequencies.

minor comments (6)
  1. [Section 2, Proof of Theorem 1.1] Proof of Theorem 1.1, edge-count display: the identity E=Δp^0+|RS∪LS| is correct, but a one-sentence remark that simultaneous left-and-right-special vertices only loosen the subsequent inequality |RS∪LS|≤|RS|+|LS| would help the reader see that the factor 3 is worst-case rather than typical.
  2. [Section 2, end of proof] The +1 that accounts for frequency 0 is an upper-bound convenience; if every length-(N+1) factor occurs infinitely often the zero class is empty. A brief parenthetical noting that the bound remains valid (and may be improved by 1) in that case would avoid a possible pedantic objection.
  3. [Example 3.1] Example 3.1: the passage from the floor-function count to the claimed asymptotic for the number of occurrences of w_i is asserted with “one can show.” A short expansion (or a reference to the standard Cesàro argument for such weighted sums) would make the frequency formula fully rigorous without lengthening the text appreciably.
  4. [Example 3.2] Example 3.2, display (3.1) and the subsequent frequency computation for the unique factors beginning 01^{n-i}0: the constant 2^{i-n-2} is derived under |v_N|∼2N; it would be clearer to record the precise error term O((log N)/N) so that the later 0.95/1.05 windows in Lemma 3.6 are visibly justified for large n.
  5. [Throughout] Typographical: several accented names (Balková, Pelantová, Sós, Surányi, Świerczkowski) appear with inconsistent TeX accents across the abstract, introduction and bibliography; a single pass with the correct UTF-8/TeX macros would improve appearance.
  6. [Section 1] Notation: the paper uses both freq_u(w) and the under/over-lined variants; a single displayed definition block at the beginning of §1 would make the three notions easier to reference later.

Circularity Check

0 steps flagged

No circularity: self-contained combinatorial counting on Rauzy graphs with external citations only

full rationale

Theorem 1.1 is proved by a direct counting argument on the reduced Rauzy graph of infinitely often factors: handshaking gives |RS| ≤ Δp⁰ and |LS| ≤ Δp⁰, hence E = Δp⁰ + |RS ∪ LS| ≤ 3Δp⁰, plus the zero-frequency class. Frequency invariance along simple-path interiors and the map Φ are established inside the proof, not assumed. The argument adapts Balková–Pelantová and invokes Cassaigne, Morse–Hedlund, and Boshernitzan as external lemmas; none are authored by Bell–Burnett–Schulz in a load-bearing way. Section 3 constructions are independent explicit words showing the linear-complexity clause is sharp, not fitted predictions. No step reduces the claimed bound to its own input by definition or self-citation.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

The paper is pure combinatorics on words. It rests on standard external theorems (Morse–Hedlund, Cassaigne’s bound on Δp for linear complexity, the classical Rauzy-graph formalism, and the Balková–Pelantová reduced-graph idea) plus ordinary limsup/liminf definitions. No free parameters are fitted; no new physical or algebraic entities are postulated.

axioms (4)
  • standard math Morse–Hedlund theorem: a right-infinite word is eventually periodic iff p_w(n) is bounded (equivalently Δp_w(n)=0 for large n); used to guarantee Δp≥1 and non-emptiness of special vertices.
    Invoked at the start of the proof of Theorem 1.1 and to ensure every path reaches a special vertex.
  • standard math Cassaigne’s theorem: linearly bounded p_w implies Δp_w(n) is uniformly bounded (cited [6, Théorème 7.2]).
    Used only for the ‘in particular’ clause that produces a uniform C under linear complexity.
  • domain assumption Balková–Pelantová reduced-Rauzy-graph method: frequencies are constant on interiors of simple paths between left/right-special vertices.
    The paper explicitly adapts this method (cited [2]) from ordinary frequencies under recurrence to upper/lower frequencies in general; the adaptation is the technical core.
  • standard math Standard definitions of subword complexity, Rauzy graphs, left/right-special factors, and upper/lower frequency via limsup/liminf.
    Background of combinatorics on words; used throughout §§1–2.

pith-pipeline@v1.2.0-daily-grok45 · 16531 in / 2870 out tokens · 52127 ms · 2026-07-31T12:34:07.427126+00:00 · methodology

0 comments
read the original abstract

Using a method of Balkov\'a--Pelantov\'a, we show that if ${\bf w}$ is a right-infinite word over a finite alphabet, then for each nonnegative integer $N$ there are at most $3(p_{\bf w}(N+1)-p_{\bf w}(N))+1$ distinct upper (and likewise lower and ordinary when they exist) frequencies for length-$(N+1)$ subwords of ${\bf w}$, where $p_{\bf w}(n)$ is the subword complexity function of $n$. In particular, this gives a uniform upper bound when ${\bf w}$ has linearly bounded subword complexity. We provide examples showing that whenever $f(n)$ is a weakly increasing function tending to infinity, there is a word ${\bf w}$ such that the number of subwords of length $n$ is $O(nf(n))$ and for which the limit supremum of the number of distinct upper frequencies of length-$N$ subwords of ${\bf w}$ as $N\to\infty$ is infinite.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references

  1. [1]

    Allouche and J

    J.-P. Allouche and J. Shallit,Automatic sequences, Cambridge University Press, Cambridge, 2003

    2003

  2. [2]

    Balkov´ a and E

    ˇL. Balkov´ a and E. Pelantov´ a, A note on symmetries in the Rauzy graph and factor frequencies,Theoret. Comput. Sci.410(2009), no. 27–29, 2779–2783

    2009

  3. [3]

    J. P. Bell, The upper density of an automatic set is rational,J. Th´ eor. Nombres Bordeaux32(2020), no. 2, 585–604

    2020

  4. [4]

    Borel, Les probabilit´ es d´ enombrables et leurs applications arithm´ etiques,Supplemento di rend

    ´E. Borel, Les probabilit´ es d´ enombrables et leurs applications arithm´ etiques,Supplemento di rend. circ. Mat. Palermo,27(1909), 247–271

    1909

  5. [5]

    Boshernitzan, A condition for unique ergodicity of minimal symbolic flows,Ergodic Theory Dynam

    M. Boshernitzan, A condition for unique ergodicity of minimal symbolic flows,Ergodic Theory Dynam. Systems12(1992), 425–428

    1992

  6. [6]

    Cassaigne, Complexit´ e et facteurs sp´ eciaux,Bull

    J. Cassaigne, Complexit´ e et facteurs sp´ eciaux,Bull. Belg. Math. Soc. Simon Stevin,4(1997), no. 1, 67–88

    1997

  7. [7]

    Cobham, Uniform tag sequences,Math

    A. Cobham, Uniform tag sequences,Math. Systems Theory,6(1972), 164–192

    1972

  8. [8]

    Lothaire,Algebraic combinatorics on words, Encyclopedia Math

    M. Lothaire,Algebraic combinatorics on words, Encyclopedia Math. Appl.,90, Cambridge University Press, Cambridge, 2002

    2002

  9. [9]

    Rauzy, Suites ` a termes dans un alphabet fini, Seminar on number theory, 1982–1983 (Talence, 1982/1983), Exp

    G. Rauzy, Suites ` a termes dans un alphabet fini, Seminar on number theory, 1982–1983 (Talence, 1982/1983), Exp. No. 25, 16 pp. Universit´ e de Bordeaux I, U.E.R. de Math´ ematiques et d’Informatique, Laboratoire de Th´ eorie des Nombres, Talence, 1983

    1982

  10. [10]

    V. T. S´ os, On the theory of diophantine approximations I,Acta Math. Acad. Sci. Hungar.,8(1957), 461–472

    1957

  11. [11]

    Sur´ anyi,¨Uber die Anordnung der Vielfachen einer reellen Zahl mod 1,Ann

    J. Sur´ anyi,¨Uber die Anordnung der Vielfachen einer reellen Zahl mod 1,Ann. Univ. Sci. Budapest E¨ otv¨ os Sect. Math.,1(1958), 107–111

    1958

  12. [12]

    ´Swierczkowski, On successive settings of an arc on the circumference of a circle,Fund

    S. ´Swierczkowski, On successive settings of an arc on the circumference of a circle,Fund. Math.,46(1959), 187–189. FREQUENCIES OF SUBWORDS IN WORDS OF LINEAR SUBWORD COMPLEXITY 11

    1959

  13. [13]

    Vishne, Primitive algebras with arbitrary Gelfand-Kirillov dimension,J

    U. Vishne, Primitive algebras with arbitrary Gelfand-Kirillov dimension,J. Algebra211(1999), no. 1, 150–158. University of W aterloo, Department of Pure Mathematics, W aterloo, Ontario, N2L 3G1, Canada Email address:jpbell@uwaterloo.ca University of W aterloo, Department of Pure Mathematics, W aterloo, Ontario, N2L 3G1, Canada Email address:lcburnett@uwat...

    1999