Two problems about bases and independent sets in free groups
summary
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…
In short
The paper investigates bases and independent sets in free groups using Stallings foldings and graph theory to bound subgroup rank and growth rates. It proves that no independent set in F2 can have an exponential growth rate of 3, establishing a general limitation on the size of such sets.
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 used across episodes
This episode discusses
The paper
Two problems about bases and independent sets in free groups · Read on arXiv
LUCY KOCH-HYDE, EAMONN OLIVE
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.
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.
More episodes
- 2509.05860-Concentration Inequalities for Branching Random Walks
- 2509.19309-Small Prime Primitive Roots in Arithmetic Progressions
- 2509.21830-Noncollapsing for Curvature Flows with Inhomogeneous Speeds
- 2510.08346-Separability and Submetrizability in Locally Convex Spaces
- 2510.27290-Borel Combinatorics of Schreier Graphs of Z-actions
- 2511.13500-Sampling Density for Gabor Phase Retrieval
- 2511.19161-Linear dynamics of random products of weighted shifts
- 2511.21548-Metastability of diffusion processes in narrow tubes
- 2512.01536-Abelian approximations for bicrossed products
- 2601.02524-Lagrangian slice disks with symplectomorphic exteriors