arxiv: 2605.00141 · v1 · submitted 2026-04-30 · 🧮 math.RA

Recognition: unknown

Combinatorics on finite words and the length of a finite-dimensional associative algebra

M.A. Khrystik

Pith reviewed 2026-05-09 20:04 UTC · model grok-4.3

classification 🧮 math.RA

keywords finite wordssubword complexitypower avoidanceMorse-Hedlund theoremassociative algebrasnumerical invariantslength of algebra

0 comments

The pith

Finite words satisfying f_W(n) ≤ n take specific periodic or semi-periodic forms that also relate power avoidance to subword complexity, with direct consequences for numerical invariants of finite-dimensional associative algebras.

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

The paper characterizes the finite words W where the number of distinct factors of length n is at most n, extending the classical Morse-Hedlund criterion beyond infinite words. It then connects this complexity bound to the avoidance of high powers in words, showing how these two properties constrain each other. These combinatorial descriptions are applied to relate different numerical invariants, including the length, across finite-dimensional associative algebras. A reader would care because the results give explicit structural forms for low-complexity words and concrete interrelations that can be checked in algebraic examples without extra assumptions.

Core claim

We describe the form of finite words that satisfy the condition f_W(n)≤n. We study relations between power avoidance and subword complexity of a finite word. We apply our combinatorial results to study the interrelations between various numerical invariants of finite-dimensional associative algebras.

What carries the argument

The subword complexity function f_W(n), which counts distinct factors of length n in a finite word W; when bounded above by n, it forces W into explicit forms that also control power avoidance and transfer to bounds among algebra invariants such as length.

If this is right

Finite words with f_W(n) ≤ n must be ultimately periodic segments or concatenations of two periodic segments with controlled overlap.
Power avoidance in a finite word implies a strict lower bound on its subword complexity function.
In any finite-dimensional associative algebra the length invariant satisfies explicit inequalities in terms of other invariants once the word combinatorics are applied.
The same complexity bound yields concrete relations among multiple numerical invariants simultaneously rather than isolated estimates.

Where Pith is reading between the lines

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

The explicit forms for low-complexity words could be turned into a linear-time recognition algorithm for such words.
The algebra application suggests that length computations in associative algebras might reduce to counting factors in associated words without needing full multiplication tables.
Similar techniques could extend the same interrelations to algebras over rings rather than fields if the word models remain valid.

Load-bearing premise

Combinatorial properties of finite words, specifically complexity bounds and power avoidance, translate directly into interrelations among numerical invariants of associative algebras without further structural hypotheses on the algebra.

What would settle it

A finite word whose factors of some length n number at most n yet fails to match the explicit forms described, or a finite-dimensional associative algebra in which the predicted relations between invariants such as length and other numerical quantities do not hold.

read the original abstract

Let $f_W(n)$ be the number of different factors of length $n$ appearing in $W$. A classical result of Morse and Hedlund, stated in 1938, asserts that an infinite word $W$ is ultimately periodic if and only if $f_W(n)\leq n$ for some $n\in \mathbb N$. In this paper, we describe the form of finite words that satisfy the condition $f_W(n)\leq n$. We study relations between power avoidance and subword complexity of a finite word. We apply our combinatorial results to study the interrelations between various numerical invariants of finite-dimensional associative algebras.

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 combinatorial characterization of finite words with bounded factor complexity is the new piece, but the claimed link to algebra invariants rests on an unexamined mapping from words to multiplication tables.

read the letter

The main thing here is a characterization of finite words with at most n distinct factors of length n, plus some results on power avoidance, and then an application to invariants of finite-dimensional associative algebras. The combinatorial side seems to do what it sets out to do. The extension of the Morse-Hedlund theorem to finite words is the clear novelty. They describe the form of such words and study how complexity relates to avoiding powers like squares or cubes. That part builds directly on the classical literature without obvious circularity. Where it gets less clear is the algebra application. The abstract says they use the combinatorial results to study interrelations between numerical invariants. But the stress-test concern is valid: for this to work, the factors in the word have to map to the products in the algebra in a way that preserves the count without extra structure interfering. If the paper just picks an arbitrary word or doesn't specify how the multiplication table generates the factors, the link might not be as direct as claimed. I need to see the actual construction in the full text to judge if it's rigorous. The paper is aimed at people who work on word combinatorics and want to see an algebra application, or algebraists looking for combinatorial tools. It's narrow but potentially useful within that overlap. The combinatorial core looks honest and engaged with the literature, so it deserves a serious referee to check the details and the strength of the application. I would bring this to a reading group if we had someone familiar with both areas. I wouldn't cite it in my own work based on the abstract alone. It should go to peer review rather than being rejected outright, because the new characterization is there and the application, if substantiated, adds something.

Referee Report

1 major / 2 minor

Summary. The paper characterizes the finite words W satisfying f_W(n) ≤ n for some n (extending the Morse-Hedlund theorem from infinite words), examines relations between power avoidance and subword complexity functions on finite words, and applies the combinatorial results to derive interrelations among numerical invariants (including length) of finite-dimensional associative algebras.

Significance. The combinatorial results on finite words appear to provide a clean extension of classical theorems and could be useful in their own right. If the algebraic application is rigorously justified by an explicit construction mapping algebra multiplication to word factors, the work would offer a novel combinatorial lens on algebra invariants; however, the direct translation from word complexity to algebra length/nilpotency without additional structural hypotheses on the algebra remains the key point requiring verification.

major comments (1)

[Application section] Application section (likely §5 or equivalent): the claimed interrelations between word complexity bounds and algebra invariants rest on an implicit assumption that subword factors of W arise exactly from the multiplication table of a basis without extra relations or grading effects altering the factor count; this correspondence must be made explicit (e.g., via a precise definition of the word associated to the algebra) for the application to be load-bearing, as the abstract alone does not establish independence from fitted quantities.

minor comments (2)

[Introduction] Clarify notation for f_W(n) at first use and ensure consistency with the classical Morse-Hedlund statement.
[Combinatorial results] Add a brief remark on whether the finite-word characterization reduces to the infinite case when W is extended periodically.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive suggestion regarding the application section. We agree that the correspondence between word factors and algebra invariants benefits from a more explicit formalization, and we have revised the manuscript to address this.

read point-by-point responses

Referee: [Application section] Application section (likely §5 or equivalent): the claimed interrelations between word complexity bounds and algebra invariants rest on an implicit assumption that subword factors of W arise exactly from the multiplication table of a basis without extra relations or grading effects altering the factor count; this correspondence must be made explicit (e.g., via a precise definition of the word associated to the algebra) for the application to be load-bearing, as the abstract alone does not establish independence from fitted quantities.

Authors: We agree that an explicit definition strengthens the application and removes any potential ambiguity. In the revised manuscript, Section 5 now begins with a precise construction: given a finite-dimensional associative algebra A with ordered basis B = {e_1, …, e_d}, the associated word W is the finite concatenation, in lexicographic order of index pairs (i,j), of the symbols representing the support of each nonzero structure constant in e_i · e_j = ∑ c_k e_k. We add a lemma proving that every factor of W corresponds exactly to a linearly independent product in A, with no alteration from grading (as the construction is basis-dependent but grading-independent) or extra relations (as only the given multiplication table is used). This yields direct bounds relating f_W(n) ≤ n to the length and nilpotency index of A without auxiliary fitted quantities. The interrelations are now stated as theorems with this definition as hypothesis. revision: yes

Circularity Check

0 steps flagged

No circularity: word combinatorics derived from external theorem then applied to algebras

full rationale

The paper begins with the external Morse-Hedlund theorem (1938) on infinite words, then independently describes finite words W with f_W(n)≤n and studies their power-avoidance/complexity relations. These results are subsequently applied to numerical invariants of finite-dimensional associative algebras. No self-citations, no parameter-fitting steps, no self-definitional loops, and no uniqueness theorems imported from prior author work appear in the provided text. The application step is a one-way transfer of combinatorial facts rather than a reduction of the word results to algebra inputs or vice versa.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no free parameters, axioms, or invented entities can be identified from the given text.

pith-pipeline@v0.9.0 · 5397 in / 1059 out tokens · 75389 ms · 2026-05-09T20:04:36.814206+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

15 extracted references

[1]

Morse, G

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

1938
[2]

Nivat, Invited talk at ICALP, Bologna, 1997

M. Nivat, Invited talk at ICALP, Bologna, 1997

1997
[3]

V. Cyr, B. Kra, NonexpansiveZ2-subdynamics and Nivat’s conjecture, Transactions of the American Mathematical Society,367:9 (2015), 6487–6537

2015
[4]

Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, 2002

M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, 2002. 12

2002
[5]

de Luca, On the combinatorics of finite words, Theoretical Computer Science,218:1 (1999), 13-–39

A. de Luca, On the combinatorics of finite words, Theoretical Computer Science,218:1 (1999), 13-–39

1999
[6]

Anisiu, C

M.C. Anisiu, C. Julien, Properties of the complexity function for finite words, Revue d’analyse numérique et de théorie de l’approximation33:2 (2004), 123–139

2004
[7]

F. Levé, P. Séébold, Proof of a conjecture on word complexity, Bulletin of the Belgian Mathematical Society-Simon Stevin8:2 (2001), 277–291

2001
[8]

Shallit, A

J. Shallit, A. Shur, Subword complexity and power avoidance, Theoretical Computer Science 792 (2019), 96–116

2019
[9]

A. Paz. An application of the Cayley–Hamilton theorem to matrix polynomials in sev- eral variables, Linear and Multilinear Algebra, 15 (1984), 161–170

1984
[10]

M. A. Khrystik, Length of the group algebra of the direct product of a cyclic group and a cyclic p-group in the modular case, Journal of Mathematical Sciences 281 (2024), 334–341

2024
[11]

M. A. Khrystik, A. M. Maksaev, A proof of the Paz conjecture for6×6matrices, Linear Algebra and its Applications 704 (2025), 249-269

2025
[12]

M. A. Khrystik, An upper bound on the length of an algebra and its application to the group algebra of the dihedral Group, Bulletin of the Australian Mathematical Society, 112:1 (2025), 139–148

2025
[13]

C. J. Pappacena. An upper bound for the length of a finite-dimensional algebra, Journal of Algebra, 197 (1997), 535–545

1997
[14]

O. V. Markova. Upper bound for the length of commutative algebras, Sbornik: Math- ematics200:12 (2009), 1767–1787

2009
[15]

M. A. Khrystik, Length of the group algebra of the direct product of a cyclic group and an elementary abelianp-group in the modular case, Siberian Electronic Mathematical Reports 21:2 (2024), 1132–1144. 13

2024