Two problems about bases and independent sets in free groups

arXiv:2609.00382 · math.GR, math.CO · Submitted 2026-08-31 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: We're looking at the paper: "Two problems about bases and independent sets in free groups".

Paper summary: Ada: So we're looking at this paper, "Two problems about bases and independent sets in free groups," which basically tackles two big questions from Dotsenko and Grigorchuk using Stallings foldings. It aims to find tight upper bounds on the rank of subgroups based on how long their generators are.

Emmy: Right, so they start by defining these terms—the set Sn and Bn, which are just words of length exactly n or at most n in a free group Fr—and then look at the growth function of any subset X in that group.

Kolya: That growth function definition, gX(n), is where they're setting up the exponential growth rate as this limit supremum over n to infinity, which is also equivalent to finding the infimum b such that gX(n) falls within big O of b times n.

Ada: Exactly. The main thrust here seems to be answering a specific problem about an independent set X in F2—whether one exists that isn't redundant and has an exponential growth rate of three—and they prove no such set exists, which leads them to a more general result about independent sets.

Emmy: And then they tie it all together by proving Theorem one point seven, which states that if you take an independent set S from the ball Bn, its size cannot exceed big O of the square root of two r minus one times n <ref:2609.00382#pg2>.

Kolya: That bound on the size of an independent set is interesting because it directly limits how fast a set can grow exponentially. It suggests that for any b smaller than the square root of two r minus one times n, there's actually an independent set that grows at least as fast as b times n.

Ada: And they show that this bound is achievable by constructing specific classes of bases, like Pr(k) and Qr(k), which meet certain Nielsen reduction conditions to hit the upper bound derived in Lemma three point one <ref:2609.00382#pg2>.

Emmy: That construction shows that you can build sets that actually reach the limit, meaning the maximum possible rank for a subgroup generated by elements of Sn is at least what those formulas give you based on whether n is even or odd.

Kolya: I wonder if those constructions are simple enough to be practical, though they seem to show the bound is tight, which means it's a very strong limitation on the structure of these subgroups.

Ada: Speaking of limitations, Theorem one point seven tells us that an independent set S from Bn has a size that grows at most big O of square root of two r minus one times n, which is a direct upper bound on the exponential growth rate <ref:2609.00382#pg2>.

Emmy: And Proposition four point three adds another layer by saying that for every b smaller than the square root of two r minus one times n, you can find an independent set S whose growth function gS(n) is bigger than big O of b times n.

Kolya: So, if you're trying to construct something with a certain exponential growth rate, say something that grows faster than some constant b times n, this theorem tells you it's impossible if b is too large.

Ada: And the authors point out some open questions at the end of the paper, Problem five point one asks if there exists an independent subset with an exponential growth rate exactly equal to square root of two r minus one times n.

Emmy: Problem five point two conjectures that no set S exists where every element is independent and the set grows exponentially, which is a very strong statement about the structure they just explored.

Kolya: And Problem five point three asks for a finer characterization of the largest independent subsets of Sn and Bn, suggesting the answer lies in something involving theta root two r minus one times n. That means they're trying to pinpoint exactly where that growth rate limit is reached.

Ada: Overall, this paper provides tools using Stallings foldings and simple graph theory to establish these rank bounds for subgroups generated by elements of Sn and Bn, which was the initial goal when they were addressing Dotsenko's problem.

Emmy: It really shows how the geometry of Stallings core graphs, where rank is just edges minus vertices plus one, provides a concrete way to translate these abstract group theory problems into graph theory constraints.

Kolya: The implication for us listening is that when you look at growth rates in free groups, these geometric properties translate directly into limits on how complex the underlying subgroup structure can be.

Ada: So the paper essentially says that exponential growth rate is constrained by this square root of two r minus one times n factor, and they've shown how to construct examples that approach that limit.

Emmy: It connects the algebraic structure of subgroups directly to graph properties, which is a powerful bridge for understanding these free group problems.

Conclusion: Ada: So we're wrapping up this look at "Two problems about bases and independent sets in free groups." This paper uses Stallings foldings to set some tight limits on how big these subgroups can be, especially when you have a maximum length for their generators.

Emmy: Right, it basically takes the abstract structure of these free groups and turns it into a graph problem where the rank of the subgroup just becomes counting edges minus vertices plus one in that core graph.

Kolya: And what they're showing is that this geometric approach gives us concrete upper bounds on those ranks based on whether you're dealing with an even or odd number of generators.

Ada: So, the big picture here is establishing a clear ceiling for how complex these subgroups can be, which was a question posed by Dotsenko years ago.

Emmy: It's about showing that you can build specific types of bases that actually hit those upper bounds they calculated in Lemma three point one, meaning the limits aren't just theoretical lines on a graph; they are reachable with real constructions.

Kolya: From my side, it means for someone studying the growth rate of these sets, there’s a hard wall up—an exponential growth rate cannot exceed this specific square root of two r minus one times n limit.

Ada: That's the core finding, showing that exponential growth is capped by this factor. It also touches on whether you can actually reach that exact limit with an independent set.

Emmy: They leave some open questions about whether a set can grow at exactly that square root of two r minus one times n, suggesting the precise characterization of the largest sets is still being worked out.

Kolya: So while they found a strong restriction on growth, the next step for researchers is figuring out if that exact boundary point is achievable or what kind of structure creates it.

LUCY KOCH-HYDE, EAMONN OLIVE

math.GR, math.CO

Submitted: 2026-08-31

Updated: 2026-11-17

Comments: 10 pages, 2 figures

License: http://creativecommons.org/licenses/by-sa/4.0/

Importance score: 75/100

The gist: The paper addresses problems concerning bases and independent sets in free groups by using Stallings foldings and simple graph theory to establish bounds on subgroup rank and growth rates Problem…

Key concepts

Stallings folding
This technique connects free groups to fundamental groups of graphs. By constructing a specific graph called the 'rose graph,' authors create a core graph where the rank of a subgroup can be calculated simply by counting its edges and vertices.
Core Graph Core(G)
The core graph is a triplet (Q, p, L) representing the structure derived from Stallings folding. The edge coloring L uses generators from the free group Fr to define the image of a homomorphism related to subgroup G.
Rank Bound Formula
Lemma 2.2 provides a crucial formula relating the rank of a subgroup G to its core graph Core(G). This formula shows that rank(G) is determined by E - V + 1, where E and V are the number of edges and vertices in the core graph.
Exponential Growth Rate
This refers to how quickly the size of a set grows when repeatedly applying group operations. The paper uses this concept to show that for certain independent sets in F2, this growth rate is strictly limited by a specific bound derived from the structure of the free group.

Terminology

Summary

The paper addresses problems concerning bases and independent sets in free groups by using Stallings foldings and simple graph theory to establish bounds on subgroup rank and growth rates

Problem Context

The work aims to answer a problem posed by Dotsenko regarding the tight upper bound on the rank of subgroups given a maximum length for its generators, and then use similar tools to solve a longstanding problem of Grigorchuk in the Kourovka notebook The paper introduces elementary definitions related to freely reduced words and growth functions for subsets of free groups Problem 1.5 asks whether a set X in F2 exists such that no part of X is redundant, and X has an exponential growth rate of 3 The authors show that the answer to Problem 1. p. 0

Where the paper says it

For the group presentation ⟨F2 | X⟩ (giving the group F2/ ⟪X⟫), (1) imposes the restriction that no part of X is redundant, which is a desirable property. 5 then asks a question about how “big” a non-redundant relator set can be in terms of its asymptotic growth.

5 is No such X exists by proving a more general result about independent sets

Stallings Core Graph Construction

The approach utilizes Stallings foldings, which connect free groups to fundamental groups of graphs For a free group Fr, the authors choose the rose graph Rr as a representation They define the Stallings core graph Core(G) as a triplet (Q, p, L) where L is an edge coloring by generators in Fr such that its induced homomorphism has an image exactly equal to G A crucial property of these graphs is that the rank of a subgroup G can be determined by the number of edges and vertices in Core(G) via Lemma 2.2, which states rank(G) = E − V + 1

Rank Bounds for Bases

The paper derives upper bounds for the rank of subgroups generated by elements of Sn and Bn using the properties of the core graph Lemma 3.1 establishes an upper bound for the rank based on whether n is even or odd, providing formulas involving √2r − 1 The authors demonstrate that these bounds are attainable by constructing specific classes of bases, such as Pr(k) and Qr(k), which satisfy Nielsen reduction conditions This construction shows that the maximum possible rank for a subgroup generated by elements of Sn is at least the bound derived in Lemma 3. p. 5

Where the paper says it

Thus, the maximum possible rank of a subgroup generated by elements of Sn is at least ( √ 2r − 1 n n is even r √ 2r − 1 n−1 n is odd Because Sn ⊆ Bn, Lemma 3. 1 shows that this is precisely the maximum possible rank in the Sn case.

1

Growth Rate Limitations

Theorem 1.7 provides an upper bound on the size of an independent set S, stating that S ∈ O √2r − 1 n This theorem is applied to Problem 1. p. 0

Where the paper says it

TWO PROBLEMS ABOUT BASES AND INDEPENDENT SETS IN FREE GROUPS LUCY KOCH-HYDE AND EAMONN OLIVE ´ Abstract. We will answer a problem of Dotsenko that asks for a tight upper bound on the rank of subgroups given a maximum length for its generators.

5, showing that the exponential growth rate of any independent set S cannot exceed this bound Proposition 4. p. 8
Where the paper says it

We’ve shown a reasonably tight bound on the worst-case growth rate of an independent set (Theorem 1. 7 and Proposition 4.

3 further shows that for every b < √2r − 1, there exists an independent set S such that gS(n) ∈ omega (b n), suggesting the bound can be approached closely

Future Directions

The paper concludes by posing three open questions related to the findings Problem 5.1 asks if there exists an independent subset with an exponential growth rate exactly √2r − 1 Problem 5. p. 8

Where the paper says it

3), but it leaves a loose end: Problem 5. In a finitely generated free group Fr, does there exist some independent subset with exponential growth rate exactly √ 2r − 1?

2 conjectures that no set S exists where every element is independent and the set grows exponentially Problem 5. p. 7
Where the paper says it

Let Fr be a finitely generated non-Abelian free group. For every b < √ 2r − 1, there exists an independent set S ⊂ Fr such that gS(n) ∈ Ω (b n ) Proof.

3 asks for a finer characterization of the largest independent subsets of Sn and Bn, noting that the answer lies in Θ √2r − 1 n The authors suggest an upper bound involving ρ(r, n) and v(r, n) for this problem

References

[1] Matt Clay, Free groups and folding, Office hours with a geometric group theorist, 2017, pp. 66–84

[2] Ilya Kapovich and Alexei Myasnikov, Stallings foldings and the subgroup structure of free groups, Journal of Algebra 248 (2002), no. 2, 608–668

[3] Ilya Kapovich, Alexei Myasnikov, and Vladimir Shpilrain, Combinatorial group theory: Open problems on infinite groups, De Gruyter, 2026

[4] E. I. Khukhro and V. p. 8

Where the paper says it

[3] Ilya Kapovich, Alexei Myasnikov, and Vladimir Shpilrain, Combinatorial group theory: Open problems on infinite groups, De Gruyter, 2026. Khukhro and V.

D. Mazurov, Unsolved problems in group theory. p. 8
Where the paper says it

Khukhro and V. Mazurov, Unsolved problems in group theory.

The Kourovka notebook, 10th ed. p. 0
Where the paper says it

We will answer a problem of Dotsenko that asks for a tight upper bound on the rank of subgroups given a maximum length for its generators. Then, we will use the same tools to answer a longstanding problem of Grigorchuk in the 10th edition of the Kourovka notebook.

, 1986

[5] Wilhelm Magnus, Abraham Karrass, and Donald Solitar, Combinatorial group theory; presentations of groups in terms of generators and relations, Pure and applied mathematics, v. 13, Interscience Publishers, New York 1966 (eng) p. 8

Where the paper says it

[5] Wilhelm Magnus, Abraham Karrass, and Donald Solitar, Combinatorial group theory; presentations of groups in terms of generators and relations, Pure and applied mathematics, v. 13, Interscience Publishers, New York, 1966 (eng).

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improve algorithms for checking independence in free groups by utilizing Stallings foldings and core graphs to establish a structural bound on independent sets. This allows AI systems to quickly determine if a given set of group elements forms an independent set by analyzing the complexity of its core graph structure.

  2. Develop tools for calculating the growth rate of subsets of free groups more accurately by applying Theorem 1.7, which provides an upper bound on the size of any independent set S, stating that S in O sqrt(2r - 1)n when S is a subset of Bn. This improves the accuracy when estimating asymptotic growth rates for generated subgroups.

  3. Create solvers for Problem 10.13 by implementing checks based on Lemma 4.1, which states that if the number of vertices in Core(S union w) is greater than or equal to the number of vertices in Core(S), then K union w is a basis. This allows AI to iteratively test potential generating sets and efficiently identify minimal bases for subgroups generated by specific sets like Sn or Bn.

  4. Enhance knowledge representation for Problem 18 by using the explicit constructions Pr(k) and Qr(k) given in Theorem 1.9 as guaranteed bases with rank equal to the upper bound derived in Lemma 3.1. This enables AI systems to generate known maximal bases for subgroups of Sn and Bn, rather than relying solely on theoretical upper bounds for rank determination.

Abstract

We will answer a problem of Dotsenko that asks for a tight upper bound on the rank of subgroups given a maximum length for its generators. Then, we will use the same tools to answer a longstanding problem of Grigorchuk in the 10th edition of the Kourovka notebook. We accomplish this using Stallings foldings and simple graph theory.

Related papers