The abelian complexity of infinite words and the Frobenius problem

Ian Kaye; Narad Rampersad

arxiv: 1907.08247 · v1 · pith:ZGIGLW72new · submitted 2019-07-18 · 🧮 math.CO

The abelian complexity of infinite words and the Frobenius problem

Ian Kaye , Narad Rampersad This is my paper

Pith reviewed 2026-05-24 19:38 UTC · model grok-4.3

classification 🧮 math.CO

keywords abelian complexityinfinite wordsFrobenius problemsemigroup homomorphismfactorscombinatorics on wordscovering properties

0 comments

The pith

Conditions on S and abelian complexity guarantee that factors of specific infinite words cover all but finitely many naturals.

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

The paper studies Dekking's problem of when the image under a semigroup homomorphism S of the factors of an infinite word x covers all sufficiently large natural numbers. It focuses on particular infinite words that possess different abelian complexity functions and derives conditions on S and the complexity that make the covering hold. The authors verify the property through direct analysis of the factors for the chosen words. This links the combinatorial repetition properties measured by abelian complexity to the classical Frobenius covering question in additive number theory. A reader cares because the work supplies concrete, checkable instances where the word's structure controls numerical coverage.

Core claim

Conditions on S and the abelian complexity of x guarantee that S(L_x) contains all but finitely many elements of N for some specific infinite words x having different abelian complexity functions.

What carries the argument

The semigroup homomorphism S from the free monoid on the alphabet to the natural numbers, whose action on the language L_x of factors of x produces a covering of N minus a finite set when the abelian complexity of x satisfies suitable conditions.

If this is right

For the examined words the covering property holds under the derived conditions on S.
Different abelian complexity functions supply distinct test cases for the general Dekking problem.
The covering can be confirmed or refuted by inspecting the possible abelian vectors of factors.

Where Pith is reading between the lines

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

The same direct-analysis approach might work for other words whose abelian complexity is eventually periodic or computable.
Results could connect to questions about numerical semigroups generated by automatic sequences.
One could test whether the same conditions suffice when abelian complexity is replaced by ordinary factor complexity.

Load-bearing premise

The specific infinite words chosen have abelian complexity functions that interact with the homomorphism S in a way that allows the covering property to be verified or disproved through direct analysis of their factors.

What would settle it

An explicit infinite word x together with a homomorphism S where the stated conditions on abelian complexity hold yet S(L_x) still omits infinitely many natural numbers.

read the original abstract

We study the following problem, first introduced by Dekking. Consider an infinite word x over an alphabet {0,1,...,k-1} and a semigroup homomorphism S:{0,1,...,k-1}* -> N. Let L_x denote the set of factors of x. What conditions on S and the abelian complexity of x guarantee that S(L_x) contains all but finitely many elements of N? We examine this question for some specific infinite words x having different abelian complexity functions.

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 checks Dekking's abelian complexity question via direct Parikh vector computation on a few specific infinite words but stays strictly case-by-case.

read the letter

The paper takes Dekking's question about when the image of the factors of an infinite word under a semigroup homomorphism covers all but finitely many naturals, and it works through this for some specific words that have different abelian complexity functions. They pick words with varying complexity behaviors and compute the occurring Parikh vectors from the factors, then check what linear combinations under S cover all large enough integers when the stated conditions hold. That direct translation from complexity data to the attainable sums is the part that holds up cleanly, with no visible gaps in the factor analysis according to the stress-test note. The computations give explicit examples of when the covering property succeeds or fails depending on S. The limitation is that the work never leaves the case-by-case level. No general criterion or first-principles condition appears that would apply to wider classes of words, and the choice of examples seems driven mainly by having distinct complexity functions rather than by any structural necessity. The advance therefore remains incremental on an existing open problem. This is for people already working on abelian properties of words and their links to additive semigroups. A reader looking for broad new theorems will find little, but someone collecting concrete checks for the Dekking question might use the examples. I would send it to peer review because the computations are checkable and the question is legitimate even if the results stay narrow.

Referee Report

0 major / 2 minor

Summary. The manuscript examines Dekking's problem: for an infinite word x over a finite alphabet and a semigroup homomorphism S from the free monoid to the naturals, find conditions on S and the abelian complexity function of x such that the image S(L_x) (with L_x the language of factors) is cofinite in N. The authors investigate the question by direct analysis of Parikh vectors for several concrete infinite words chosen to exhibit qualitatively different abelian complexity behaviors.

Significance. The concrete case-by-case verifications supply explicit examples where the cofiniteness property holds or fails under stated conditions on S, thereby furnishing test cases and partial positive results for the general question. The approach of translating abelian complexity data into attainable linear combinations <S, p> is appropriate to the combinatorial setting and yields falsifiable predictions for the chosen words.

minor comments (2)

The definition of the homomorphism S in the introduction would benefit from an explicit statement that S is extended multiplicatively from the letters; the current wording leaves the extension implicit until later sections.
Several figures displaying factor graphs or Parikh-vector sets lack axis labels or scale indications, making it harder to verify the claimed gaps at a glance.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript on Dekking's problem, the significance of the concrete examples, and the recommendation for minor revision. No specific major comments were listed in the report.

Circularity Check

0 steps flagged

No significant circularity; direct case analysis on external problem

full rationale

The paper studies a problem first posed by Dekking and verifies the cofiniteness of S(L_x) via explicit computation of factors, Parikh vectors, and linear combinations for a handful of concrete infinite words with given abelian complexity functions. No derivation step equates a claimed prediction to a fitted input, renames a known result, or relies on a load-bearing self-citation chain. The argument is self-contained against the external benchmark of direct enumeration and does not invoke any of the enumerated circularity patterns.

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 · 5598 in / 1003 out tokens · 16858 ms · 2026-05-24T19:38:51.381204+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

What conditions on S and the abelian complexity of x guarantee that S(L_x) contains all but finitely many elements of N?
IndisputableMonolith/Foundation/DimensionForcing.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Dekking studied the case where w is a Sturmian word... ρ_w(n)=2 for all n≥1

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

[1]

Allouche and F.M

J.-P . Allouche, M. Dekking. Generalized Beatty sequenc es and complementary triples. Preprint. https://arxiv.org/abs/1809.03424

work page arXiv
[2]

Ardal, T

H. Ardal, T . Brown, V . Jungi´c, and J. Sahasrabudhe. On abelian and additive complexity in inﬁnite words. Integers, 12:#A21, 2012

work page 2012
[3]

Balková, M

L. Balková, M. Bucci, A. De Luca, J. Hladký, S. Puzynina. A periodic pseudorandom number generators based on inﬁnite words. Theoret. Comput. Sci. 647:85–100, 2016

work page 2016
[4]

Blanchet-Sadri, N

F . Blanchet-Sadri, N. Fox, N. Rampersad. On the asymptot ic abelian complexity of mor- phic words. Adv . Appl. Math. 61:46–84, 2014

work page 2014
[5]

E. M. Coven and G. A. Hedlund. Sequences with minimal bloc k growth. Mathematical Systems Theory , 7:138–153, 1973

work page 1973
[6]

M. Dekking. The Frobenius problem for homomorphic embed dings of languages into the integers. Theoret. Comput. Sci. 732:73–79, 2018. 17

work page 2018
[7]

Dekking, M

M. Dekking, M. Mendès France, A. van der Poorten. Folds I– III. Math. Intelligencer 4:130–138,172–181,190–195, 1982

work page 1982
[8]

P . Hubert. Suites équilibrées. Theoret. Comput. Sci. 24 2:91–108, 2000

work page 2000
[9]

Madill, N

B. Madill, N. Rampersad. The abelian complexity of the pa perfolding word. Discrete Math. 313:831–838, 2013

work page 2013
[10]

Ramírez Alfonsín

J. Ramírez Alfonsín. The Diophantine Frobenius Proble m. Oxford Univ . Press (2005)

work page 2005
[11]

Steuding, P

J. Steuding, P . Stumpf. On the Frobenius problem for Bea tty sequences. Indag. Mathe- maticae 28:132–137, 2017

work page 2017
[12]

Sylvester

J. Sylvester . Mathematical questions with their solut ions. Educational Times 41:21, 1884

work page
[13]

L. Vuillon. Balanced words. Bull. Belg. Math. Soc. Simo n Stevin 10:787–805, 2003

work page 2003
[14]

Richomme, K

G. Richomme, K. Saari, and L. Q. Zamboni. Abelian comple xity of minimal subshifts. J. London Math Soc. 83:79–95, 2010. 18

work page 2010

[1] [1]

Allouche and F.M

J.-P . Allouche, M. Dekking. Generalized Beatty sequenc es and complementary triples. Preprint. https://arxiv.org/abs/1809.03424

work page arXiv

[2] [2]

Ardal, T

H. Ardal, T . Brown, V . Jungi´c, and J. Sahasrabudhe. On abelian and additive complexity in inﬁnite words. Integers, 12:#A21, 2012

work page 2012

[3] [3]

Balková, M

L. Balková, M. Bucci, A. De Luca, J. Hladký, S. Puzynina. A periodic pseudorandom number generators based on inﬁnite words. Theoret. Comput. Sci. 647:85–100, 2016

work page 2016

[4] [4]

Blanchet-Sadri, N

F . Blanchet-Sadri, N. Fox, N. Rampersad. On the asymptot ic abelian complexity of mor- phic words. Adv . Appl. Math. 61:46–84, 2014

work page 2014

[5] [5]

E. M. Coven and G. A. Hedlund. Sequences with minimal bloc k growth. Mathematical Systems Theory , 7:138–153, 1973

work page 1973

[6] [6]

M. Dekking. The Frobenius problem for homomorphic embed dings of languages into the integers. Theoret. Comput. Sci. 732:73–79, 2018. 17

work page 2018

[7] [7]

Dekking, M

M. Dekking, M. Mendès France, A. van der Poorten. Folds I– III. Math. Intelligencer 4:130–138,172–181,190–195, 1982

work page 1982

[8] [8]

P . Hubert. Suites équilibrées. Theoret. Comput. Sci. 24 2:91–108, 2000

work page 2000

[9] [9]

Madill, N

B. Madill, N. Rampersad. The abelian complexity of the pa perfolding word. Discrete Math. 313:831–838, 2013

work page 2013

[10] [10]

Ramírez Alfonsín

J. Ramírez Alfonsín. The Diophantine Frobenius Proble m. Oxford Univ . Press (2005)

work page 2005

[11] [11]

Steuding, P

J. Steuding, P . Stumpf. On the Frobenius problem for Bea tty sequences. Indag. Mathe- maticae 28:132–137, 2017

work page 2017

[12] [12]

Sylvester

J. Sylvester . Mathematical questions with their solut ions. Educational Times 41:21, 1884

work page

[13] [13]

L. Vuillon. Balanced words. Bull. Belg. Math. Soc. Simo n Stevin 10:787–805, 2003

work page 2003

[14] [14]

Richomme, K

G. Richomme, K. Saari, and L. Q. Zamboni. Abelian comple xity of minimal subshifts. J. London Math Soc. 83:79–95, 2010. 18

work page 2010