arxiv: 2605.14955 · v1 · submitted 2026-05-14 · 🧮 math.CO

Recognition: 2 theorem links

· Lean Theorem

On the Number of Rational Power Factors in a Finite Word

Shuo Li , Yuan Song

Authors on Pith no claims yet

Pith reviewed 2026-05-15 03:16 UTC · model grok-4.3

classification 🧮 math.CO

keywords rational powerfinite wordupper boundcombinatorics on wordsgraph representationword equationspattern counting

0 comments

The pith

A finite word of length n contains at most one-eighth n squared plus lower-order terms distinct rational power factors.

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

This paper proves an upper bound on the total number of distinct rational power factors that can appear in any finite word. Rational powers generalize the usual k-powers by allowing fractional exponents through prefix repetitions. The proof transforms the problem into a constrained extremal question using a graph model of the word and some equations on its factors. A sympathetic reader would care because such bounds help understand the repetitive structure possible in strings, with applications in text processing and combinatorics.

Core claim

We prove that for any finite word w of length n the number RP(w) of distinct rational power factors satisfies RP(w) ≤ (1/8)n² + O(n). This is achieved by representing the word as a graph and using word equations to reduce the counting to an extremal problem on that graph.

What carries the argument

A graph-theoretic representation of the finite word together with associated word equations that model the occurrences of rational powers.

If this is right

The bound is quadratic in n, unlike the linear bounds known for fixed integer exponents.
Every rational power, defined as p^k p' with k>1 integer and p' prefix of p, is accounted for in the count.
The method converts pattern counting into an extremal graph problem.
Previous work on k-powers is generalized to all rational exponents at once.

Where Pith is reading between the lines

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

The graph method could extend to counting other types of factors or patterns in words.
The constant 1/8 might be improvable or achieved by some specific word constructions.
Such bounds could influence the design of algorithms that detect or avoid repetitions in strings.

Load-bearing premise

The graph representation and word equations capture all possible rational power factors in every finite word without missing any or double-counting.

What would settle it

Constructing a specific word of length n that contains strictly more than n²/8 + c n distinct rational power factors for a sufficiently large constant c would disprove the bound.

read the original abstract

Let $w$ be a finite word of length $n$. In this paper, we study the maximum possible number of distinct rational power factors in a finite word. A rational power is a word of the form $u=p^kp'$, where $p$ is a nonempty finite word, $k$ is an integer larger than $1$, $p^k$ is a concatenation of $k$ copies of $p$ and $p'$ is a prefix of $p$. The rational powers can be recognized as a generalization of $k$-powers, and it is proved in [Li,Pachocki,Radoszewski 24] that, the number $C_k(w)$ of distinct $k$-powers in $w$ satisfies $C_k(w) \leq \frac{n-1}{k-1}$. However, the number of rational powers has not been studied in the literature. In this article, we prove that the number $\mathrm{RP}(w)$ of distinct rational power factors of $w$ satisfies $\mathrm{RP}(w)\le\frac18n^2+O(n)$. We also illustrate a novel approach to study pattern-counting problems: using a graph-theoretic representation of words and a few word equations, we transform the traditional pattern-counting problems into a constrained extremal problem.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper introduces rational powers and claims a quadratic upper bound on their distinct count via a graph model, but the model's coverage of all cases needs close checking.

read the letter

The main thing to know is that this work defines rational powers as a generalization of k-powers and proves that any word of length n has at most n²/8 plus linear terms distinct such factors. It extends the earlier linear bound for fixed k from Li-Pachocki-Radoszewski by allowing variable rational exponents and supplies the first explicit quadratic estimate for the total count. The graph-plus-equation technique is the clearest new element: they encode possible overlaps and periods as vertices and edges, then turn the counting task into a constrained extremal problem on that graph. If the construction is complete, it gives a systematic route for similar pattern-counting questions. The bound is stated cleanly and the abstract sketches how the equations constrain the feasible configurations, which is more concrete than many purely existential arguments in the area. The soft spot is the completeness of the model. The stress-test note flags that certain boundary cases, such as when the prefix length is close to the period length or when periods cross block boundaries oddly, might not map to any path or configuration in their graph. If even one family of rational powers is omitted, the derived maximum would not be a true upper bound on the actual RP(w). The abstract does not include enough of the derivation to rule this out, and there are no tightness examples or explicit constructions that reach the quadratic term. The citation pattern is reasonable, building directly on the cited k-power result without obvious omissions. This paper is aimed at people working on repetitions and pattern avoidance in words who need concrete bounds for algorithmic purposes. A combinatorics-on-words reader would get value from the bound and the modeling idea even if the proof needs tightening. It deserves a serious referee because the problem is well-posed, the claimed result is new, and the approach is reproducible in principle once the graph details are verified.

Referee Report

2 major / 2 minor

Summary. The paper claims that for any finite word w of length n, the number RP(w) of distinct rational power factors (substrings of the form p^k p' with k ≥ 2) satisfies RP(w) ≤ (1/8)n² + O(n). The proof converts the counting problem into a constrained extremal problem on a graph whose vertices and edges are defined via a fixed collection of word equations that encode possible overlaps and periods.

Significance. If the central bound holds, it supplies the first quadratic upper bound on the total number of rational powers (generalizing the linear bounds C_k(w) ≤ (n-1)/(k-1) for fixed k from Li-Pachocki-Radoszewski 2024). The graph-plus-equation technique is presented as a reusable method for other pattern-counting questions in combinatorics on words.

major comments (2)

[§3] §3 (Graph-theoretic representation): The argument that every rational power u = p^k p' appears as a feasible path or configuration in the constructed graph G_w is not verified by exhaustive case analysis or by showing that the chosen word equations are complete. Without this, the extremal count on G_w need not upper-bound the true RP(w) for all words, which is load-bearing for the claimed inequality.
[§5] §5 (Extremal analysis): The coefficient 1/8 in the leading quadratic term is obtained by maximizing a certain quadratic form subject to the graph constraints, but the optimization steps (including how boundary cases with |p'| close to |p| are handled) are not exhibited in sufficient detail to confirm that the maximum is attained only by configurations that actually correspond to realizable words.

minor comments (2)

The O(n) term is stated without an explicit constant or leading coefficient; providing the precise form of the linear term would improve readability.
Notation for the graph G_w and the set of feasible paths should be introduced with a single consolidated definition rather than piecemeal across paragraphs.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address the two major points below and will revise the manuscript accordingly to strengthen the arguments.

read point-by-point responses

Referee: [§3] §3 (Graph-theoretic representation): The argument that every rational power u = p^k p' appears as a feasible path or configuration in the constructed graph G_w is not verified by exhaustive case analysis or by showing that the chosen word equations are complete. Without this, the extremal count on G_w need not upper-bound the true RP(w) for all words, which is load-bearing for the claimed inequality.

Authors: We agree that an explicit verification is needed to confirm completeness. In the revised manuscript we will insert a new lemma in §3 that performs an exhaustive case analysis on the possible periods and overlaps, showing that every rational power factor u = p^k p' corresponds to a feasible path in G_w under the chosen word equations. This will establish that the extremal count on G_w is indeed an upper bound for RP(w). revision: yes
Referee: [§5] §5 (Extremal analysis): The coefficient 1/8 in the leading quadratic term is obtained by maximizing a certain quadratic form subject to the graph constraints, but the optimization steps (including how boundary cases with |p'| close to |p| are handled) are not exhibited in sufficient detail to confirm that the maximum is attained only by configurations that actually correspond to realizable words.

Authors: We acknowledge that the optimization details are insufficiently explicit. In the revision we will expand §5 with the complete sequence of steps for maximizing the quadratic form under the graph constraints, including explicit treatment of the boundary cases where |p'| is close to |p|. We will also add a short argument verifying that the maximizing configurations are realizable by concrete words, thereby confirming that the leading coefficient is indeed 1/8. revision: yes

Circularity Check

0 steps flagged

No significant circularity in the derivation

full rationale

The paper derives the bound on RP(w) by constructing a graph whose vertices and edges are defined via a fixed collection of word equations that encode the structure of finite words and their factors. The maximum number of rational-power configurations is then obtained as the solution to an extremal path-counting problem on this graph. Because the graph is assembled from the syntactic definition of words rather than from any presupposed count of rational powers, the resulting inequality is not forced by construction. The citation to the earlier k-powers bound supplies background only and is not invoked to justify the new extremal argument. No self-definitional steps, fitted-input predictions, or load-bearing self-citations appear in the described method.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof rests on the assumption that every word and every rational power factor can be faithfully encoded by paths in a graph whose edges satisfy a small set of word equations; no free parameters or new entities are introduced in the abstract.

axioms (1)

domain assumption The graph-theoretic representation of words accurately models all possible finite words and their factors.
Invoked to convert the pattern-counting task into a constrained extremal graph problem.

pith-pipeline@v0.9.0 · 5530 in / 1096 out tokens · 44320 ms · 2026-05-15T03:16:04.714835+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

171 extracted references · 171 canonical work pages

[1]

Bidimensional Sturmian Sequences and Substitutions , Url =

Thomas Fernique , Bibsource =. Bidimensional Sturmian Sequences and Substitutions , Url =. Developments in Language Theory, 9th International Conference,. 2005 , Bdsk-Url-1 =. doi:10.1007/11505877\_21 , Pages =

work page doi:10.1007/11505877 2005
[2]

Suites de m

Ali Aberkane and Sre. Suites de m. Actes des Journ

work page
[3]

Reversals and palindromes in continued fractions , Volume =

Boris Adamczewski and Jean-Paul Allouche , Journal =. Reversals and palindromes in continued fractions , Volume =

work page
[4]

Palindromic continued fractions , Volume =

Boris Adamczewski and Yann Bugeaud , Journal =. Palindromic continued fractions , Volume =

work page
[5]

On Repeated Factors in

Arturo Carpi , Journal =. On Repeated Factors in

work page
[6]

Axel Thue's papers on repetitions in words : a translation , Volume =

work page
[7]

Currie and Narad Rampersad , Journal =

James D. Currie and Narad Rampersad , Journal =. Cubefree words with many squares , Volume =

work page
[8]

Currie and Narad Rampersad , Bibsource =

James D. Currie and Narad Rampersad , Bibsource =. Growth rate of binary words avoiding xxx\(. 2016 , Bdsk-Url-1 =. doi:10.1016/j.tcs.2015.11.004 , Journal =

work page doi:10.1016/j.tcs.2015.11.004 2016
[9]

A d -step approach for distinct squares in strings , Volume =

Antoine Deza and Frantisek Franek and Mei Jiang , Booktitle =. A d -step approach for distinct squares in strings , Volume =

work page
[10]

How many double squares can a string contain? , Volume =

Antoine Deza and Frantisek Franek and Adrien Thierry , Journal =. How many double squares can a string contain? , Volume =

work page
[11]

A d -step approach to the maximum number of distinct squares and run in strings , Volume =

Antoine Deza and Frantisek Franek , Journal =. A d -step approach to the maximum number of distinct squares and run in strings , Volume =

work page
[12]

Bannai et al

Antoine Deza and Frantisek Franek , Journal =. Bannai et al. method proves the d -step conjecture for strings. , Volume =

work page
[13]

Fraenkel and Jamie Simpson , Journal =

Aviezri S. Fraenkel and Jamie Simpson , Journal =. How Many Squares Can a String Contain? , Volume =

work page
[14]

Fraenkel and Jamie Simpson , Journal =

Aviezri S. Fraenkel and Jamie Simpson , Journal =. The Exact Number of Squares in Fibonacci Words , Volume =

work page
[15]

Lucian Ilie , Title =. Theor. Comput. Sci. , Volume =

work page
[16]

A Stronger Square Conjecture on Binary Words , Year =

Natasa Jonoska and Florin Manea and Shinnosuke Seki , Booktitle =. A Stronger Square Conjecture on Binary Words , Year =

work page
[17]

Proof of the

Lubom. Proof of the. Theor. Comput. Sci. , Pages =

work page
[18]

Braquelaire and A

J.-P. Braquelaire and A. Vialard , Issue =. Euclidean Paths: A New Representation of Boundary of Discrete Regions , Volume =. Graphical Models and Image Processing , Pages =

work page
[19]

Journal of Mathematical Physics , Month = apr, Pages =

work page
[20]

Palindrome complexity , Volume =

Jean-Paul Allouche and Michael Baake and Julien Cassaigne and David Damanik , Journal =. Palindrome complexity , Volume =

work page
[21]

Sums of Digits, Overlaps, and Palindromes , Volume =

Jean-Paul Allouche and Jeffrey Shallit , Journal =. Sums of Digits, Overlaps, and Palindromes , Volume =

work page
[22]

A Note on Palindromicity , Volume =

Baake, Michael , Doi =. A Note on Palindromicity , Volume =. Letters in Mathematical Physics , Language =. 1999 , Bdsk-Url-1 =

work page 1999
[23]

Weakly directed self-avoiding walks , Url =

Axel Bacher and Mireille Bousquet-M. Weakly directed self-avoiding walks , Url =. Journal of Combinatorial Theory, Series A , Keywords =. 2011 , Bdsk-Url-1 =. doi:http://dx.doi.org/10.1016/j.jcta.2011.06.001 , Issn =

work page doi:10.1016/j.jcta.2011.06.001 2011
[24]

Families of prudent self-avoiding walks , Url =

Mireille Bousquet-M. Families of prudent self-avoiding walks , Url =. Journal of Combinatorial Theory, Series A , Number =. 2010 , Bdsk-Url-1 =. doi:http://dx.doi.org/10.1016/j.jcta.2009.10.001 , Issn =

work page doi:10.1016/j.jcta.2009.10.001 2010
[25]

On Translating one Polyomino to Tile the Plane , Volume =

Dani. On Translating one Polyomino to Tile the Plane , Volume =. Discrete Computational Geometry , Pages =

work page
[26]

Berger , Journal =

R. Berger , Journal =. The undecidability of the domino problem , Volume =

work page
[27]

Combinatorial properties of double square tiles , Volume =

Alexandre. Combinatorial properties of double square tiles , Volume =. Theoretical Computer Science , Pages =

work page
[28]

Combinatorial properties of f -palindromes in the Thue-Morse sequence , Volume =

Alexandre. Combinatorial properties of f -palindromes in the Thue-Morse sequence , Volume =. Pure Mathematics and Applications , Number =

work page
[29]

Equations on palindromes and circular words , Volume =

Alexandre Blondin Mass. Equations on palindromes and circular words , Volume =. Theor. Comput. Sci. , Number =

work page
[30]

Palindromic lacunas of the

Alexandre. Palindromic lacunas of the. Proc. GASCom 2008 (16-20 June 2008, Bibbiena, Arezzo-Italia) , Pages =

work page 2008
[31]

Complexity of the

Alexandre. Complexity of the. Fractals , Number =

work page
[32]

Enumeration of factors in the

Sre. Enumeration of factors in the. Discrete Applied Mathematics , Number =

work page
[33]

TBA , Year =

Sre. TBA , Year =. Words, Codes and Algebraic Combinatorics: A conference in honor of

work page
[34]

On The Palindromic Complexity Of Infinite Words , Volume =

Sre. On The Palindromic Complexity Of Infinite Words , Volume =. International Journal on Foundation of Computer Science , Number =

work page
[35]

Smooth words on 2-letter alphabets having same parity , Volume =

Sre. Smooth words on 2-letter alphabets having same parity , Volume =. Theoretical Computer Science , Number =

work page
[36]

Reconstructing words from a

Brlek, Sre. Reconstructing words from a. Fund. Inform. , Mrclass =

work page
[37]

Reconstructing words from a fixed palindromic length sequence , Volume =

Alexandre. Reconstructing words from a fixed palindromic length sequence , Volume =. 5th IFIP International Conference On Theoretical Computer Science - TCS 2008, IFIP 20th World Computer Congress, TC 1, Foundations of Computer Science, September 7-10, 2008, Milano, Italy , Editor =

work page 2008
[38]

A Linear Time and Space Algorithm for Detecting Path Intersection , Volume =

Brlek, Sre. A Linear Time and Space Algorithm for Detecting Path Intersection , Volume =. Discrete Geometry for Computer Imagery , Editor =

work page
[39]

A linear time and space algorithm for detecting path intersection in

Sre. A linear time and space algorithm for detecting path intersection in. Theoretical Computer Science , Number =

work page
[40]

Brlek and G

S. Brlek and G. Labelle and A. Lacasse , Booktitle =. A note on a result of

work page
[41]

Brlek and G

S. Brlek and G. Labelle and A. Lacasse , Journal =. Properties of the Contour Path of Discrete Sets , Volume =

work page
[42]

Combinatorial view of digital convexity

Sre. Combinatorial view of digital convexity. , Volume =. Discrete Geometry for Computer Imagery, 14th International Conference, DGCI 2008, Lyon, France, April 16-18, 2008, Proceedings , Editor =

work page 2008
[43]

Sre. Lyndon+. Pattern Recognition , Pages =

work page
[44]

A note on differentiable palindromes , Volume =

Sre. A note on differentiable palindromes , Volume =. Theoretical Computer Science , Number =

work page
[45]

Ladouceur and Laurent Vuillon , Journal =

Srecko Brlek and Serge Dulucq and A. Ladouceur and Laurent Vuillon , Journal =. Combinatorial properties of smooth infinite words , Volume =

work page
[46]

Proceedings of the Prague Stringology Conference '06 , Editor =

Sre. Proceedings of the Prague Stringology Conference '06 , Editor =

work page
[47]

An Optimal Algorithm for Detecting Pseudo-squares , Volume =

Sre. An Optimal Algorithm for Detecting Pseudo-squares , Volume =. Discrete Geometry for Computer Imagery, 13th International Conference, DGCI 2006, Szeged, Hungary, October 25-27, 2006, Proceedings , Editor =

work page 2006
[48]

On the Tiling by Translation Problem , Volume =

Sre. On the Tiling by Translation Problem , Volume =. Discr. Appl. Math. , Pages =

work page
[49]

Complexity and palindromic defect of infinite words , Volume =

Sre. Complexity and palindromic defect of infinite words , Volume =. Theoretical Computer Science , Number =

work page
[50]

Periodic-like words, periodicity, and boxes , Volume =

Arturo Carpi and Aldo de Luca , Journal =. Periodic-like words, periodicity, and boxes , Volume =

work page
[51]

Daurat and M

A. Daurat and M. Nivat , Booktitle =

work page
[52]

Sturmian Words: Structure, Combinatorics, and Their Arithmetics , Volume =

Aldo de Luca , Journal =. Sturmian Words: Structure, Combinatorics, and Their Arithmetics , Volume =

work page
[53]

Pseudopalindrome closure operators in free monoids , Volume =

Aldo. Pseudopalindrome closure operators in free monoids , Volume =. Theoretical Computer Science , Number =

work page
[54]

Some Combinatorial Properties of the Thue-Morse Sequence and a Problem in Semigroups , Volume =

Aldo de Luca and Stefano Varricchio , Journal =. Some Combinatorial Properties of the Thue-Morse Sequence and a Problem in Semigroups , Volume =

work page
[55]

Detection of the discrete convexity of polyominoes , Volume =

Debled-Rennesson, Isabelle and R. Detection of the discrete convexity of polyominoes , Volume =. Discrete Appl. Math. , Mrclass =

work page
[56]

Episturmian words and some constructions of de

Xavier Droubay and Jacques Justin and Giuseppe Pirillo , Journal =. Episturmian words and some constructions of de

work page
[57]

Boltzmann Samplers for the Random Generation of Combinatorial Structures , Volume =

Philippe Duchon and Philippe Flajolet and Guy Louchard and Gilles Schaeffer , Journal =. Boltzmann Samplers for the Random Generation of Combinatorial Structures , Volume =

work page
[58]

Bentley , Journal =

Raphael Finkel and J.L. Bentley , Journal =. Quad Trees: A Data Structure for Retrieval on Composite Keys , Volume =

work page
[59]

Freeman , Journal =

H. Freeman , Journal =. On the Encoding of Arbitrary Geometric Configurations , Volume =

work page
[60]

Freeman , Booktitle =

H. Freeman , Booktitle =

work page
[61]

Gardner , Journal =

M. Gardner , Journal =

work page
[62]

Zamboni , Journal =

Amy Glen and Jacques Justin and Steve Widmer and Luca Q. Zamboni , Journal =. Palindromic richness , Volume =

work page
[63]

Powers Powers in a class of

Amy Glen , Journal =. Powers Powers in a class of

work page
[64]

S. W. Golomb , Publisher =

work page
[65]

S. W. Golomb , Issue =. Checker boards and polyominoes , Volume =. Amer. Math. Monthly , Pages =

work page
[66]

Gurevich and I

Y. Gurevich and I. Koriakov , Journal =. A remark on

work page
[67]

Finding all maximal palindromes in linear time , Year =

Dan Gusfield , Booktitle =. Finding all maximal palindromes in linear time , Year =

work page
[68]

Gusfield , Publisher =

D. Gusfield , Publisher =

work page
[69]

Gusfield and J

D. Gusfield and J. Stoye , Journal =. Linear time algorithms for finding and representing all the tandem repeats in a string , Volume =

work page
[70]

and Conway, Andrew R

Guttmann, Anthony J. and Conway, Andrew R. , Doi =. Square Lattice Self-Avoiding Walks and Polygons , Volume =. Annals of Combinatorics , Keywords =. 2001 , Bdsk-Url-1 =

work page 2001
[71]

Singular continuous spectrum for palindromic

Hof, Albert and Knill, Oliver and Simon, Barry , Journal =. Singular continuous spectrum for palindromic

work page
[72]

Watson-Crick palindromes in

Lila Kari and Kalpana Mahalingam , Journal =. Watson-Crick palindromes in

work page
[73]

Coding properties of

Salah Hussini and Lila Kari and Stavros Konstantinidis , Journal =. Coding properties of

work page
[74]

Coding Properties of

Salah Hussini and Lila Kari and Stavros Konstantinidis , Booktitle =. Coding Properties of

work page
[75]

Codes, Involutions, and

Lila Kari and Rob Kitto and Gabriel Thierrin , Booktitle =. Codes, Involutions, and

work page
[76]

A Hierarchical Data Base Management Algorithm , Volume =

Michel Koskas , Journal =. A Hierarchical Data Base Management Algorithm , Volume =

work page
[77]

Shortest Paths un Unweighted Graphs , Volume =

Michel Koskas , Journal =. Shortest Paths un Unweighted Graphs , Volume =

work page
[78]

D. E. Knuth , Isbn =

work page
[79]

S\'ebastien Labb\'e , Title =

work page
[80]

Complexit

Nadia Lafreni\`ere , School =. Complexit

work page

Showing first 80 references.