Cycle Counting and Character Expectations Using Alternating Structures

Noam Ta Shma

Source-linked AI summary

Cycle Counting and Character Expectations Using Alternating Structures

Noam Ta Shma

arXiv:2608.27593v1Aug 27, 2026math.GRcs.FL

TL;DR

The applicability of stronger w-cycle results depends on whether words admit alternating structures. This paper generalizes stackings and bislim structures, showing that generic words admit alternating structures and the strengthened results apply to them.

Problem
The applicability of stronger w-cycle results depends on whether words admit alternating partial stackings, whose existence was open.
Source: §1.4 · p. 8
Method
The paper generalizes stackings and bislim structures to alternating partial stackings and alternating bislim structures.
Source: §1.4 · p. 7
Results
Generic words admit (|Σ|−1)-alternating partial stackings and bislim structures, and the paper reports strengthened w-cycle results for words admitting such structures.
Source: §1 · p. 2, §1.4 · pp. 7–8
Takeaways & Limitations
Any word admitting a k-alternating partial stacking has stable primitivity rank at least k.
Source: §1.4 · p. 7
The probability bounds in Theorem 1.18 seem far from tight because many words directly admit an sπ(w)-alternating bislim structure.
Source: §6.3 · p. 53

Abstract

from arXiv · show

Recently, two related papers [arXiv:2412.13941, arXiv:2409.03626] found a connection between two subjects: the w-cycle theorem, which is a theorem about counting appearances of cycles reading out a word w in certain graphs, and character expectations on word measures. The w-cycle theorem was proven independently by [arXiv:1410.2540] using stackings and by [arXiv:1410.2579] using bislim structures. In the current work, we generalize stackings and bislim structures to alternating stackings and alternating bislim structures. We show how this significantly strengthens the w-cycle theorem for words admitting such alternating structures, and as a result, also strengthens the recent results of [arXiv:2412.13941] and [arXiv:2409.03626]. We show that generic words admit alternating bislim structures, and therefore, the strengthened results hold for generic words. Using our new machinery, we address conjectures of Wilton, of Hanany-Puder and of Puder-Shomroni. We prove that all three conjectures hold for generic words, but we also find counterexamples for the first two.

1 Introduction

This work extends stackings and bislim structures with alternating versions, strengthening the w-cycle theorem and related results for generic words.

1 Introduction

The w-cycle theorem was conjectured as part of a program to prove one-relator groups coherent, a goal recently achieved in.The theorem and its proof structures later proved useful beyond that original motivation.Source: §1 · p. 2
The paper generalizes stackings and bislim structures to alternating stackings and alternating bislim structures.These generalizations significantly strengthen the w-cycle theorem and the recent results of [Cas24] and.Source: §1 · p. 2
Almost all words admit alternating bislim structures, so the strengthened results apply to almost all words.Source: §1 · p. 2

1.1 The w-cycle theorem

The section introduces w-cycles in labeled core graphs and states the conditions under which the w-cycle theorem applies.

1.1 The w-cycle theorem

A core graph is a directed labeled graph without leaves or isolated vertices, with at most one incoming and outgoing edge of each label at each vertex.Source: §1.1 · p. 2
A w-cycle spells a positive power of a nontrivial cyclically reduced word and is not a repetition of a smaller w-cycle; its degree is that power.The count #w(Γ) weights w-cycles by their degrees.Source: §1.1 · p. 2
Wise conjectured a bound on w-cycle counts in terms of Euler characteristic for words that are not proper powers; and proved the conjecture.Source: §1.1 · p. 3
The stated theorem assumes a non-proper-power cyclically reduced word and that every edge is covered at least twice by w-cycles.Coverage twice includes two distinct cycles or two traversals by the same cycle.Source: §1.1 · p. 3

1.2 Stackings and bislim structures

Stackings encode a word cycle by heights or vertex orderings, while bislim structures provide a parallel framework for proving the w-cycle theorem.

1.2 Stackings and bislim structures

Stackings and bislim structures serve parallel roles in the independent proofs of the w-cycle theorem, and the authors focus on bislim structures in the main proof.The authors describe stackings as more intuitive and report that good partial stackings are equivalent to bislim structures in upcoming work.Source: §1.2 · pp. 3–4
A stacking embeds the word cycle in Ω × R by assigning heights so the combined map into Ω × R is injective.The word cycle maps to the bouquet Ω according to its letter labels.Source: §1.2 · p. 3
The height embedding has an equivalent combinatorial description using an ordering of the word cycle's vertices.For edges carrying the same label, the relative order of their initial vertices agrees with that of their terminal vertices.Source: §1.2 · pp. 3–4

1.3 Word measures and character expectations

The section sets up word measures and stable characters, reviews asymptotic growth conjectures and prior partial results, and presents generic-word and finite-word conclusions.

1.3 Word measures and character expectations

A word measure comes from substituting independent uniform random elements of a compact group for free generators, then evaluating the word; the paper focuses on Sn and U(n).Source: §1.3 · p. 4

1.3.1 Stable characters

Stable characters are families whose members are essentially the same for all sufficiently large n; for Sn, irreducible stable characters are indexed by partitions.Their word-measure expectations are rational functions in n for sufficiently large n [HP23].Source: §1.3.1 · p. 5

1.3.2 Asymptotic growth conjectures

The paper proves that Conjectures 1.9, 1.10, and 1.11 hold for a generic word w.Puder and Shomroni [PS23] describe Conjecture 1.11 as more natural than Conjecture 1.9.Source: §1.3.2 · p. 6
All three conjectures hold for words in F4 of length at most 10, but the first counterexamples found disprove Conjectures 1.9 and 1.10.The authors still believe Conjecture 1.11 is true.Source: §1.3.2 · p. 6

1.3.3 Previous partial results

Recent results bound character expectations by reducing them to w-cycle theorem variants; generalizing that theorem yields new expectation bounds using the same representation-theoretic computations.The cited recent results are [Cas24, Theorem 1.6] and [MdS26, Corollary 11.3].Source: §1.3.3 · p. 6
Before this work, lower bounds for stable primitivity rank above 1 were rare, and its computation was described as intractable in practice even for relatively short words.The cited result makes it rational and computable but requires double-exponential running time.Source: §1.3.3 · p. 7

1.4 Alternating structures and new results

The section introduces alternating stackings and bislim structures to strengthen the w-cycle theorem and derive results for words with such structures. It also shows that generic words admit structures of optimal alternation degree.

1.4 Alternating structures and new results

A partial stacking is k-alternating when k high edges and k low edges occur in alternating order around the word cycle.High and low edges are determined by their positions relative to other edges with the same label.Source: §1.4 · p. 7
A word admitting a k-alternating partial stacking has sπ(w) ≥ k, extending the w-cycle theorem when each graph edge is covered at least twice by w-cycles.The theorem also permits k-alternating bislim structures; the example in the section attains equality.Source: §1.4 · p. 7
The section applies the strengthened w-cycle theorem to [Cas24] and, and Theorem 1.17 concerns irreducible stable characters of S(n) or U(n).Earlier knowledge of sπ(w) covered π(w) ≤ 2 or products of words with known values and disjoint letter sets.Source: §1.4 · p. 7
A generic word over Σ admits a (|Σ|−1)-alternating partial stacking and bislim structure, and this alternation degree is optimal.The stated upper bound has an exception when some letter occurs at most once in the word.Source: §1.4 · p. 8
Since generic words do not belong to a free basis, the stated sπ(w) bounds imply Theorem 1.12 for generic words.The cited bound is sπ(w) ≤ π(w)−1 ≤ |Σ|−1 outside the free-basis case.Source: §1.4 · p. 8

1.5 Organization

The paper develops alternating bislim structures and their applications across several sections, then describes an appendix equivalence for its bislim definition.

1.5 Organization

Section 2 develops k-alternating bislim structures and proves strengthened w-cycle results, while Section 3 establishes optimal alternation for random words with high probability.Source: §1.5 · p. 8
Section 4 bounds character expectations, and Section 5 applies alternating bislim structures to negative immersions, hyperbolicity, coherence, and a curvature invariant.Source: §1.5 · p. 8
Section 6 addresses efficient computation and certification, including an algorithmic proof of Theorem 1.13; Appendix A shows the paper's bislim definition is equivalent to the original.Source: §1.5 · p. 8

2 Alternating bislim structures

This section develops the framework of alternating bislim structures, including their definitions, criteria, and related combinatorial-map and disk-diagram terminology. It derives structural consequences such as cycle existence in specified subgraphs and extends the w-cycle theorem to multiple words and graph diagrams.

2.1 Combinatorial complexes and maps

A combinatorial 2-complex has a graph as its 1-skeleton and 2-cells attached along combinatorial boundary maps; the paper assumes complexes are non-degenerate and maps are branched combinatorial maps.A branched combinatorial map is locally injective in each 2-cell away from its center.Source: §2.1 · p. 9

2.1.1 Sides

A side is an edge in a 2-cell’s boundary circle, and a branched near-immersion maps distinct sides of the same edge to distinct sides in the target.A disk diagram is reduced precisely when its map is a branched near-immersion.Source: §2.1.1 · p. 9, §2.1.2 · p. 10

2.2 Bislim structures and heightened complexes

The revised bislim definition allows multiple high and low sides, is symmetric under reversing heights, and supports alternating structures that give stronger w-cycle bounds than the original definition [HW16].For good complexes, admitting a good bislim structure under the revised definition is equivalent to admitting one under [HW16, Definition 2.1].Source: §2.2 · pp. 10, 13
A heightened complex is alternating when high and low sides alternate around each 2-cell boundary; its alternation degree counts the high sides, which equal the number of low sides.Good bislim structures and 1-alternating bislim structures are equivalent.Source: §2.2 · p. 14
For good heightened complexes, bislimness is equivalent to acyclicity of Γ(Y) for every simply connected branched near-immersion Y → X.This is equivalent to requiring acyclicity for every reduced disk diagram or for the universal cover.Source: §2.2 · p. 14
For possibly non-good heightened complexes, bislimness requires non-degeneracy and acyclicity for reduced disk diagrams without internal 2-cells, equivalently for simply connected branched near-immersions without internal 2-cells.For good heightened complexes, this definition agrees with the good-complex definition; for non-good ones, the definitions need not agree.Source: §2.2 · pp. 14–15

2.3 The w-cycle theorem

The section sets out to prove the w-cycle theorem for alternating bislim structures and variations; related claims and proofs in [HW16, Sections 3 and 4] use structures that are effectively only 1-alternating.Source: §2.3 · pp. 15, 17
Under the stated finiteness, internal-edge, and nontriviality assumptions, every component of Y(1) − H contains a cycle.This is Lemma 2.12 for a finite alternating bislim structure.Source: §2.3 · p. 17
A branched near-immersion Y → X inherits an alternating bislim structure from X, with altC′ = d · altC when C′ maps to C with branching degree d.Theorem 2.14 applies the preceding Euler-characteristic result, counting preimage 2-cells with multiplicity by branching degree.Source: §2.3 · p. 19
If a component of Y(1) − H is a tree, it contains or is adjacent to a non-internal edge; Theorem 2.16 accounts for non-internal edges with a term 2|∂Y|.Here ∂Y is the set of non-internal edges in Y.Source: §2.3 · p. 20
The extended w-cycle theorem treats multiple words w1, . . . , wk when their cycles cover each edge at least twice and the presentation complex admits an alternating bislim structure.Its stated hypotheses include alternation degrees altwi; the supplied passage does not show the theorem’s concluding bound.Source: §2.3 · p. 20
Theorem 2.18 recasts the branched-map result for graph diagrams, assuming W → Ω admits an alternating partial stacking and S → H covers each edge at least twice.For each component w of W, the map ψ−1(w) → w is a degree dw covering; the supplied passage truncates the conclusion.Source: §2.3 · p. 21

3 Existence of bislim structures for generic presentations

This section develops sufficient and relaxed criteria for bislimness, proving them through piece-counting arguments that control minimal counterexamples. It applies these criteria to show that random presentations admit alternating bislim structures with high probability.

3 Existence of bislim structures for generic presentations

If the nonnegative alternation degrees a_1, …, a_k sum to less than r, a generic r-generator, k-relator presentation admits a bislim structure with w_i a_i-alternating.The paper states that the bound on the sum is tight.Source: §3 · p. 22

3.1 A Simple criterion for bislim structures

For R ≥ 4, a heightened complex is bislim if it has no trivial cycles, pieces of length at most R/4, neutral neighborhoods within distance R − 2 of extremal sides, and extremal sides separated by at least 2R − 1.Source: §3.1 · p. 23
Generic presentation complexes satisfy three safeguards of the simple criterion but fail its neutral-neighborhood condition, and the criterion cannot reach the required r − 1 alternations.It requires at least two neutral edges, limiting it to r − 2 overall alternations; the relaxed criterion is needed for the full theorem.Source: §3.1 · pp. 23–24

3.1.1 Proof of Theorem 3.5

The proof rules out a minimal counterexample by bounding its piece count both below and above by twice the number of leaves in its internal tree.The lower bound comes from extremal sides and paths through neutral sides; together with the upper bound, it yields a contradiction.Source: §3.1.1 · pp. 24, 27

3.2 The relaxed criterion for bislim structures

Splitting each leaf path into a neutral blocker and a remainder relaxes the earlier criterion, while attributing pieces from the next blocker can ensure four pieces per leaf.The remainder may escape the boundary and contain too few internal pieces; the proof uses a further trick to force the next blocker to contain at least four pieces.Source: §3.2 · p. 28

3.2.1 Blockers

Blockers are sided paths of length ℓb beginning at an extremal side, and remainders are sided paths of length ℓr continuing from a blocker.The proof fixes both lengths as positive integer parameters.Source: §3.2.1 · p. 29
Theorem 3.19 gives bislimness when a heightened complex with no trivial cycles satisfies the blocker/remainder conditions for fixed ℓb, ℓr, and a directed neutral loop e*.The loop’s endpoints coincide.Source: §3.2.1 · p. 29
In ˜D, blockers cannot intersect unless they start on the same edge; each leaf has a blocker directed from it, and full blockers stay in T˜D without internal pieces longer than ℓb.Blockers also do not pass through another leaf of T˜D.Source: §3.2.1 · p. 29, §3.2.2 · pp. 32–34
To overcome the failure of local counting on a minimal counterexample, the proof augments Γ(D) to ˜Γ(D) and chooses a minimal diagram ˜D whose augmented graph has a cycle.The chosen diagram also retains the property that blockers do not intersect unless they start on the same edge.Source: §3.2.1 · p. 30, §3.2.2 · pp. 31–32

3.2.3 Proof of the relaxed criterion for bislim structures

Every leaf of the associated tree has at least four sided pieces attributed to it, and no piece is attributed to two leaves.These lemmas contradict the leaf bound when a structure satisfying the relaxed criterion is assumed not to be bislim, proving Theorem 3.19.Source: §3.2.3 · pp. 34–35

3.3 Generic words have alternating bislim structures

Random r-generator k-relator presentations with relator length ℓ admit an (a1, …, ak)-alternating bislim structure with probability at least 1 − e^−Ω(ℓ^c), when Σ_i a_i < r.Here c = 1/(2 + 20·Σ_i a_i); relators are chosen uniformly from cyclically reduced words.Source: §3.3 · p. 35
The proof uses spaced families of alternating position pairs: with high probability the global small-cancellation condition holds and some pair satisfies the remaining relaxed-criterion conditions.The construction makes the candidate events approximately independent, allowing the probability of finding a successful pair to be bounded.Source: §3.3 · pp. 36, 38, 39

4 Applications to word measures

This section applies alternating bislim structures to strengthen bounds for stable-character expectations on S_n and U(n), with consequences for generic words. It also extends the methods to multiple words when their presentation complex satisfies an alternating bislim condition.

4.1 Background

For words admitting a k-alternating bislim structure, the paper proves stronger bounds in the w-cycle theorem; these bounds apply to the methods of [Cas24] and prove Theorem 1.17.Generic words in Fr admit (r − 1)-alternating bislim structures, but their unbounded ssql(w) means this cannot prove Conjecture 1.8 for generic words [PS23, Section 7].Source: §4.1 · p. 40

4.2 Stable Fourier coefficients of word measures on S_n

For S_n, Theorem 4.3 strengthens the w-cycle bound for alternating bislim words, and its consequences establish Conjectures 1.9 and 1.11 for generic words.For non-power words, the result recovers [Cas24, Theorem 1.6].Source: §4.2 · p. 41

4.2.1 The graph Γ

The graph Γ(ρ, ⟨π⟩) is built by gluing vertices identified by partial bijections or the partition, then gluing same-label edges whose endpoints are partition-equivalent.This graph construction supplies the combinatorial object used to strengthen the S_n bound.Source: §4.2.1 · p. 42

4.2.2 Proof of Theorem 4.3

The S_n proof uses an auxiliary graph H so the covering graph meets the w-cycle theorem’s conditions, yielding the desired Euler-characteristic bound.The construction ensures edges are covered at least twice, while admissibility prevents certain same-position identifications.Source: §4.2.2 · pp. 43–44

4.3 Stable Fourier coefficients of word measures on U(n)

For U(n), Theorem 4.6 bounds χ(Σ) by −deg ψ · altw for surfaces satisfying [MdS26, Proposition 11.1].The proof converts each surface to a ribbon graph whose w-cycles cover every edge twice and satisfy the positional restriction; the graph and surface have the same Euler characteristic.Source: §4.3 · p. 45

4.4 Extension to multiple words

The methods extend to multiple words: Theorem 4.8 applies to stable irreducible character expectations when the presentation complex of the words admits an alternating bislim structure.The theorem considers either S_n or U(n).Source: §4.4 · pp. 45–46
The authors leave the relevant parts of [Cas24] and without a formal proof because their algebraic details are too involved to present here.Source: §4.4 · p. 46

5 Nonpositive and negative immersions

This section returns the w-cycle theorem’s geometric-group-theory motivation to generic presentations, deriving results on immersions, hyperbolicity, curvature, and coherence. It establishes nonpositive immersions for generic presentations with one fewer relator than generators and negative immersions when the generator count is at least two greater than the relator count.

5 Nonpositive and negative immersions

Generic presentations have negative immersions when r ≥ k+2 and nonpositive immersions when r ≥ k+1.The section also derives results on maximal irreducible curvature.Source: §5 · p. 46, §5.1 · p. 46, §5.2 · p. 47

5.1 Nonpositive immersions

A generic r-generator (r−1)-relator presentation has nonpositive immersions.The proof removes adjacent 2-cells at non-internal edges until only internal edges remain or the complex becomes a graph.Source: §5.1 · p. 46

5.2 Negative immersions

A generic r-generator k-relator presentation has negative immersions when r ≥ k+2.Negative immersions imply coherence, yielding a new proof of coherence for generic r-generator (r−2)-relator presentations.Source: §5.2 · p. 47

5.3 Hyperbolicity and Negative immersions

The methods that establish negative immersions also establish hyperbolicity of the fundamental group.The section presents this as corroborating the conjecture that negative immersions imply hyperbolicity.Source: §5.3 · p. 48

5.4 Wilton’s curvature invariant

For generic r-generator k-relator presentation complexes, the paper proves Wilton’s conjecture on maximal irreducible curvature.The theorem states an exact value for this invariant, though the supplied passage does not preserve the formula legibly.Source: §5.4 · p. 50

5.5 Coherence

A generic r-generator (r−1)-relator presentation is coherent.The proof uses nonpositive immersions, homological coherence, hyperbolicity, and asphericity.Source: §5.5 · p. 50

6 Algorithms

The section develops algorithms for finding alternating bislim structures and using them to certify hyperbolicity and negative immersions. Computational searches verify the alternating-structure condition for nearly all tested word classes, while identifying counterexamples to two conjectures.

6.1 Finding bislim structures

The search algorithm tests alternating bislim structures, while automorphic replacement can succeed even when the original word has no such structure.Automorphic words induce the same word measures, so results about the conjectures transfer between them.Source: §6.1 · p. 51

6.2 Checking for hyperbolicity and negative immersions

The certification algorithms search for alternating bislim structures and remove qualifying 2-cells recursively; acceptance certifies both negative immersions and hyperbolicity.If no suitable structure is found, the lightweight algorithm reports that it cannot determine either property; the more general algorithm tests candidates against an expanded Euler characteristic polyhedron.Source: §6.2 · p. 52

6.3 Computational results

For every word in F4 of length at most 10, an automorphic representative admits a (π(w)−1)-alternating bislim structure; this holds through length 11 except six equivalence classes.The first four exceptional words have π(w) = 3 and sπ(w) = 1.5, counterexample character expectations refute Conjectures 1.9 and 1.10, while a combinatorial argument establishes Conjecture 1.11 for them.Source: §6.3 · p. 53
The probability bounds of Theorem 1.18 appear far from tight, since many words directly admit an sπ(w)-alternating bislim structure.Source: §6.3 · p. 53

6.3.1 An Algorithm

The exhaustive search checks PCI±-equivalence representatives and returns only classes not yet verified to contain a word with an optimal alternating bislim structure.For fixed ambient free-group rank, alt_w and primitivity rank can be computed in polynomial time; the search over words is capped for unresolved infinite equivalence classes.Source: §6.3.1 · pp. 54–55

A Equivalence to the original definition of bislim structures

The appendix proves that the paper’s good bislim structures are equivalent to the original definition. It relates the two formulations through their order data on cells and edges in the universal cover.

A Equivalence to the original definition of bislim structures

The original definition uses the multiset boundary of a 2-cell, recording adjacent edges with multiplicity rather than the cyclic boundary path of sides.Source: A Equivalence to the original… · p. 57
The proof relates the cell preorder in the good-structure formulation to an invariant preorder on edges of the universal cover.The construction selects high and low sides for cells and uses the induced order data to establish the correspondence.Source: A Equivalence to the original… · pp. 57–58
A connected complex admits a good bislim structure exactly when it is bislim under the original definition.Source: A Equivalence to the original… · p. 58