On the growth of algebras, semigroups, and hereditary languages

Efim Zelmanov; Jason Bell

arxiv: 1907.01777 · v1 · pith:I3RDVF4Tnew · submitted 2019-07-03 · 🧮 math.RA · math.GR

On the growth of algebras, semigroups, and hereditary languages

Jason Bell , Efim Zelmanov This is my paper

Pith reviewed 2026-05-25 10:02 UTC · model grok-4.3

classification 🧮 math.RA math.GR

keywords growth functionssemigroupsalgebrashereditary languagesasymptotic equivalencefinitely generatedgrowth rates

0 comments

The pith

Semigroups, algebras, and hereditary languages share exactly the same possible growth functions up to asymptotic equivalence.

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

The paper establishes that the functions arising as growth rates of finitely generated semigroups are precisely those that arise for finitely generated algebras and for hereditary languages over a finite alphabet. Growth is measured by counting distinct elements or words of length at most n with respect to a finite generating set, then comparing two such functions f and g when constants exist so that each is bounded by a scaled and stretched version of the other. A reader would care because this unifies the study of size and complexity across algebraic structures and combinatorial languages, allowing results proved in one setting to transfer directly to the others without separate case-by-case analysis.

Core claim

The possible functions that can occur, up to asymptotic equivalence, as growth functions of semigroups, hereditary languages, and algebras are the same set.

What carries the argument

The growth function of a finitely generated object, considered up to asymptotic equivalence.

If this is right

Any growth rate realized by a semigroup is realized by some algebra and some hereditary language.
Any growth rate realized by an algebra is realized by some semigroup and some hereditary language.
Classifications or constructions of growth rates in one category apply immediately to the other two.
The landscape of possible growth behaviors is identical across the three classes of objects.

Where Pith is reading between the lines

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

The result suggests growth rate is an invariant insensitive to whether one works with multiplicative, additive, or subword-closed structures.
Constructions that achieve unusual growth rates in one category can be imported to solve existence questions in the others.
The unification raises the question of whether similar coincidences hold for other combinatorial or algebraic objects such as groups or automata.

Load-bearing premise

Growth is measured with respect to finite generating sets in the standard way for each of the three classes.

What would settle it

An explicit function that is the growth function of a finitely generated semigroup but cannot be realized as the growth function of any finitely generated algebra or hereditary language.

read the original abstract

We determine the possible functions that can occur, up to asymptotic equivalence, as growth functions of semigroups, hereditary languages, and 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

Bell and Zelmanov classify the possible asymptotic growth functions for semigroups, algebras, and hereditary languages and show the three classes realize exactly the same set.

read the letter

The main thing to know is that this paper determines all functions that can arise as growth functions, up to the standard asymptotic equivalence, for finitely generated semigroups, algebras, and hereditary languages, and proves the three classes have identical realizable growth classes. That unification is the core result. The abstract states it cleanly and the stress-test finds no hidden inconsistency in the setup or the weakest assumption, which is just the usual definition of growth with respect to finite generating sets. The paper does well by making the equivalence across structures explicit; this kind of classification can tidy up work on enumeration questions in algebra and combinatorics on words. The constructions presumably move between the objects while preserving growth, which is a standard technique and appears to cover the cases without obvious gaps. Soft spots are limited. The claim is broad, so the details of how intermediate growth functions and edge cases are handled will need checking in the full proof, but nothing in the stated setup suggests a load-bearing flaw or circularity. The citation pattern is not visible from the abstract, but the result stands on its own terms if the embeddings work as described. This paper is for people working on growth invariants in semigroups, algebras, or formal languages who want a reference classification. A reader focused on classification theorems or enumeration problems would get direct value from it. It deserves a serious referee because the claim is sharp, the authors are established in the area, and the result is formally grounded enough to warrant review even if revisions are required on the proof details. Recommendation: send it to peer review.

Referee Report

1 major / 0 minor

Summary. The paper claims to determine all possible functions, up to the standard asymptotic equivalence f ≼ g (f(n) ≤ C g(Cn) for some C), that arise as growth functions of finitely generated semigroups, finitely generated algebras, and hereditary languages over a finite alphabet.

Significance. If the classification is correct, the result would equate the realizable growth classes across the three structures, which is consistent with standard embedding techniques that preserve growth and would provide a unified description of possible growth functions in this area of algebra and combinatorics on words.

major comments (1)

The provided text consists solely of the abstract; no definitions, theorems, proofs, or explicit classification of the growth functions are visible. Without these, the central claim cannot be verified for correctness or completeness.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their comments on our manuscript. We address the sole major comment below.

read point-by-point responses

Referee: The provided text consists solely of the abstract; no definitions, theorems, proofs, or explicit classification of the growth functions are visible. Without these, the central claim cannot be verified for correctness or completeness.

Authors: The complete manuscript includes all required elements beyond the abstract. Section 1 provides the necessary definitions for growth functions of semigroups, algebras, and hereditary languages, along with the notion of asymptotic equivalence. The explicit classification of all possible growth functions (up to equivalence) is stated as the main theorem in Section 3 and proved in full in Sections 4 and 5, with supporting lemmas and examples. We believe the referee may have reviewed only the abstract excerpt rather than the full document submitted for evaluation. revision: no

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's central result is a classification of realizable growth functions (up to the standard asymptotic equivalence) across three classes of objects. This rests on the weakest assumption being the ordinary definition of growth with respect to finite generating sets, which is external and not derived from the classification itself. No equations, self-citations, fitted parameters renamed as predictions, or self-definitional steps appear in the abstract or setup. The equivalence across semigroups, languages, and algebras is obtained via standard embeddings that preserve growth and does not reduce the claimed classification to its own inputs by construction. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no information on free parameters, axioms, or invented entities.

pith-pipeline@v0.9.0 · 5530 in / 884 out tokens · 24581 ms · 2026-05-25T10:02:10.375153+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.

Theorem 1.1: growth function ... constant, linear, or weakly increasing F with F'(n)≥n+1 and F'(m)≤F'(n)^2 for m∈{n,...,2n}
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

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

Proposition 2.1: f(m)≤f(n)^2 for m∈{n,...,2n} from monomial algebra and prefix/suffix counting

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.