A
D
V
E
R
T

I
S
E
M
E
N
T

LEVEL 1 OF 1 · A counterexample to Kaplansky's zero-divisor conjecture

A Torsion-Free Group Algebra with Zero Divisors

expertly designed by an internal OpenAI model · released 2026-09-23 · original PDF

Theorems: 1	Lemmas: 7	Proofs: 11
Formulas: 799	Words: 12,309	Play time: ~1 hour

>>> How to Play <<<

We disprove Kaplansky's zero-divisor conjecture by constructing a finitely presented torsion-free group G for which $\mathbb F_2[G]$ has nonzero zero divisors. The group admits a finite two-dimensional classifying space.

>>> Level Map <<<

Introduction

Kaplansky’s zero-divisor conjecture asserts that $K[G]$ has no nonzero zero divisors whenever $K$ is a field and $G$ is torsion-free. Here $K[G]$ is the algebra of finite formal sums of elements of $G$, with multiplication extended bilinearly from the group law. We prove the following negative resolution.

Theorem 1. There exist a finitely presented torsion-free group $G$ and nonzero elements $\alpha,\beta\in\mathbb F_2[G]$ such that $\alpha\beta=0$. Moreover, $G$ admits a finite two-dimensional classifying space.

History and related constructions

The question goes back to Higman’s 1940 thesis (Higman 1940b); its conjectural formulation is reproduced by Sandling (Sandling 1981, 112). It was also posed in Kaplansky’s 1956 conference contribution, published in 1957 (Kaplansky 1957, Problem 6); see the historical discussion in (Gardam 2021). Finite-order elements give elementary zero divisors: if $g$ has order $m>1$, then $(1-g)(1+g+\cdots+g^{m-1})=0$. The conjecture asks whether removing this obstruction suffices.

Substantial positive results explain why torsion-freeness is a natural dividing line. Higman proved the domain conclusion for groups in which every nontrivial subgroup maps onto $\mathbb Z$ (Higman 1940a, sec. 4, Theorems 12–13). Kropholler, Linnell, and Moody established it for torsion-free elementary amenable groups, even with division-ring coefficients (Kropholler et al. 1988, Theorem 1.4). More recently, Fisher and Sánchez-Peralta obtained division-ring embeddings for group algebras of torsion-free virtually compact special groups and torsion-free compact $3$-manifold groups, and the domain conclusion for torsion-free $3$-manifold groups without a finite-generation assumption (Fisher and Sánchez-Peralta 2026, Theorem 1.3 and Corollary 1.5). These results concern particular classes of groups; our construction uses a different geometric mechanism.

A group has the unique-product property if, for every pair of finite nonempty subsets $P,Q$, some element of $PQ$ has exactly one expression $pq$ with $p\in P$, $q\in Q$. Applying this property to the supports of two nonzero group-algebra elements gives a nonzero product coefficient. Rips and Segev constructed torsion-free groups without unique product (Rips and Segev 1987); Steenbock supplied a graphical small-cancellation treatment of their construction (Steenbock 2015). Mian and Siddique report a machine-checked non-unique-product witness for Gardam’s $\widetilde A_2$ lattice, taking torsion-freeness from Gardam rather than formalizing it (Mian and Siddique 2026, sec. 1 and 7). Failure of unique product alone does not produce a zero divisor: over $\mathbb F_2$, the relevant representation counts must be even, not merely greater than one.

The distinct unit conjecture asks whether, for a torsion-free group $G$ and a field $K$, every unit of $K[G]$ is a nonzero scalar multiple of a group element. Gardam disproved it over $\mathbb F_2$ (Gardam 2021) and subsequently over $\mathbb C$ (Gardam 2024); a nontrivial unit is not a zero divisor.

Mineyev developed product structures and sufficient geometric criteria for obtaining nontrivial zero divisors or units in torsion-free group algebras over $\mathbb F_2$ (Mineyev 2024, Theorem 27). Garg and Mineyev study these criteria through finite-support combinatorics and computation (Garg and Mineyev 2025, Theorems 1–3 and 16). Shin proves that the orientable no-fold, triple-girth route cannot succeed when both support sizes are at least two (Shin 2026, Theorem 1.1 and Corollary 1.2); this obstruction does not address the arrangement-exclusion argument here. Our construction supplies its own coefficient cancellation, root separation, and torsion-freeness proofs rather than applying those geometric criteria.

The cancellation mechanism and the two safeguards

We use two finite graphs $\Gamma_A,\Gamma_B$ immersed into one rose $F$, a graph with one vertex and one edge for each generator. Every edge is read with a signed label, reversed when its orientation is reversed. Choose roots $x_A,x_B$, and let $A',B'$ be the full vertex sets of their connected components. Attach an abstract cone on each graph component along its labelled map to $F$, obtaining a complex $X$, and put $G=\pi_1(X)$. Coning kills the labels of all closed graph paths. Thus a path from $x_A$ to $x\in A'$ has a well-defined label $g_x\in G$, independent of the chosen path; define $h_y$ from $x_B$ to $y\in B'$ in the same way. The proposed factors are \[ \alpha=\sum_{x\in A'}g_x,\qquad \beta=\sum_{y\in B'}h_y^{-1}\quad\text{in }\mathbb F_2[G]. \tag{1}\]

Let $S_x$ and $S_y$ be the outgoing signed-label sets. We prescribe them so that $|S_x\cap S_y|$ is odd for every pair. Form a graph on $A'\times B'$ by simultaneous steps of a common label $t$. Along each step the product is unchanged, since \[ (g_xt)(h_yt)^{-1}=g_xh_y^{-1}. \tag{2}\] Every vertex of this finite graph has odd degree $|S_x\cap S_y|$. Hence each connected component has even cardinality, by the degree-sum formula. Its vertices all contribute the same group element to $\alpha\beta$, so their contributions cancel in characteristic two.

This simple cancellation leaves two substantial safeguards. First, both factors must survive in the quotient: we prove that a path from either prescribed root to any different vertex in its component has nontrivial label. The root is then the only contributor to the identity coefficient in each factor, so both are nonzero. We do not need to distinguish labels of two non-root vertices. Second, the quotient group must be torsion-free: we prove that $X$ is aspherical, making it a finite two-dimensional classifying space and ruling out torsion. Both safeguards will follow by excluding certain planar configurations of paired path occurrences.

From random graphs to topological control

The outgoing-label types use lines in a finite projective plane together with three extra letters. Their cross-intersections force parity, while their turn frequencies satisfy an exponentially decaying squared-word estimate. We convert this estimate into an exclusion of bounded systems of almost completely paired paths. Paths may traverse the same edge repeatedly; multiplicity stages keep track of those repeated uses, while nearly aligned blocks control comparisons of arbitrary subpaths. Multiplying numerical expectation bounds selects one stage with a small expected count, without asserting independence between stages.

The remaining obstacle is that a sphere can involve arbitrarily many paths of arbitrarily large total length. Lipton–Tarjan planar separation (Lipton and Tarjan 1979) reduces each such configuration to a bounded system. Long boundaries are first split and closed at a controlled cost, and planar gap counting bounds the number of comparison intervals after localization. The proportion of unpaired positions allowed by the probabilistic estimate is fixed before the bounds on the number and lengths of paths. This order permits the same bounded class to detect every large spherical arrangement, rather than a union bound over all arrangement sizes.

Graphical small cancellation provides important antecedents for this strategy. Gromov’s random graphical presentations connect word-coincidence estimates with geometric control (Gromov 2003); Ollivier and Gruber develop precise graphical criteria for graph embeddings and asphericity (Ollivier 2006; Gruber 2015). Distinguishing genuinely different graph lifts from coincident lifts is central to these arguments and to Bereznyuk’s spherical-diagram approach (Bereznyuk 2019). Here the prescribed vertex types and repeated traversals require a separate probability estimate, and the needed topology is proved directly by cone-picture surgery. We do not invoke a small-cancellation or $\mathrm{CAT}(0)$ criterion for these graphs.

Conventions and proof structure

All graphs are finite unless stated otherwise. A graph may initially have loops or parallel edges; both are counted in its girth. A signed alphabet $T$ has a fixed-point-free involution $t\mapsto\bar t$, with $\bar t$ denoting the inverse letter. The rose $F$ has one vertex and one unoriented edge for each inverse pair. A labelled graph maps immersively to $F$ when each outgoing label occurs at most once at each vertex. An immersed path is an edge path with no immediate reversal; a closed path is cyclically immersed if this also holds at its last/first junction. Length always counts edge traversals, including repetitions.

[sec:types,sec:bounded-pattern] construct the random graphs and rule out bounded patterns. 4 extracts such a pattern from every reduced spherical arrangement. 5 explains why either an essential sphere or a trivial label on a path from a prescribed root to a different vertex would produce such an arrangement. 6 uses the resulting asphericity and root separation to complete the factor construction and prove 1. All logarithms are natural. Constants in asymptotic estimates are independent of the sampling size $n$; additional fixed parameters on which they depend will be indicated.

Prescribed types and random matchings

We construct the two immersed graphs so that their outgoing-label sets have odd cross-intersections, the condition needed for cancellation. The same vertex types also provide a squared-word decay estimate. Conditioning the matchings on large girth will preserve enough control to prove a diameter bound and, in 3, exclude the path configurations that could defeat the geometric safeguards.

The finite geometry

Fix \[q=128,\qquad v=q^2+q+1=16513,\qquad p=\frac{q+1}{v}.\] The projective plane over $\mathbb F_q$ has $v$ points and $v$ lines. Each line has $q+1$ points, each point lies on $q+1$ lines, two distinct points lie on one common line, and two distinct lines meet at one point. These facts follow by counting one- and two-dimensional subspaces of $\mathbb F_q^3$.

Let $T$ consist of its $v$ points, called ordinary letters, and three further extra letters. Pair the extras with three distinct ordinary letters, and pair the remaining ordinary letters arbitrarily in twos. This defines a fixed-point-free involution on $T$, since $v-3$ is even. In particular, $|T|=16516$, and the corresponding rose has $8258$ edges.

Take disjoint vertex sets $A,B$, each of size $n$. For each vertex $x$, prescribe a set $S_x\subset T$ of outgoing labels as follows:

On either side the ordinary part of $S_x$ is a line, with every line represented equally often.
Within each line class on $A$, the extra part is each of the three two-element subsets with proportion $p/2$ apiece, and is otherwise empty.
Within each line class on $B$, the extra part is all three extras with proportion $p$, and is otherwise empty.

These are exact empirical proportions. We take $n\to\infty$ through multiples of $2v^2$, so all counts are integral. For example, at $n=2v^2$, each line class on $A$ has $129$ vertices of each double-extra type and $32639$ of the empty type; on $B$ it has $258$ of the triple-extra type and $32768$ of the empty type.

Every letter has frequency $p$ on each side. Two ordinary line parts meet in either $1$ or $q+1=129$ points. An extra part on $A$ meets an extra part on $B$ in either $0$ or $2$ letters. Thus \[ |S_x\cap S_y|\ \text{is odd for every }x\in A,\ y\in B. \tag{3}\] Thus the parity condition is built into the types, independently of how their edges will be matched. The random choice can now be used entirely to control the geometry without risking this condition.

Choose two vertices $x_A\in A$ and $x_B\in B$ in advance. For $Y=A,B$, write \[Y_t=\{x\in Y:t\in S_x\},\qquad |Y_t|=np.\] For each inverse pair, choose a bijection $Y_t\to Y_{\bar t}$, using its inverse for the opposite direction. A matched pair gives an edge labelled $t$ in one direction and $\bar t$ in the other. Do this independently for all inverse pairs and both sides before any conditioning. The resulting graphs are denoted \[\Gamma_A,\quad\Gamma_B,\qquad \Gamma=\Gamma_A\sqcup\Gamma_B.\] They immerse into $F$, since every outgoing letter occurs once at each vertex that carries it. Their degrees lie between $q+1$ and $d_*=q+4=132$. A prescription for one matching edge can be described using either orientation. Whenever prescriptions are counted, an edge and its reverse describe a single prescription.

Turn weights

For a non-cancelling turn $t,u$, let $w(t,u)$ be the frequency of $u$ among the vertices of $B$ that contain $\bar t$. Put $w(t,\bar t)=0$. The corresponding conditional frequency on $A$ is at most $w(t,u)$. Indeed, for distinct $\bar t,u$, the weights on $B$ are \[\begin{array}{c|ccc} (\bar t,u)&\text{ordinary, ordinary}& \text{ordinary, extra}&\text{extra, extra}\\ \hline w(t,u)&1/(q+1)&p&1. \end{array}\] The mixed entry is symmetric; the extra-extra frequency on $A$ is $1/2$. In particular, every positive weight lies in $[1/129,1]$.

For a word $W=t_1\cdots t_h$, define \[ P(W)=\prod_{i=1}^{h-1}w(t_i,t_{i+1}). \tag{4}\] Write $W^{-1}=\bar t_h\cdots\bar t_1$. Equal letter marginals and symmetry of joint incidence give \[ w(t,u)=w(\bar u,\bar t),\qquad P(W)=P(W^{-1}). \tag{5}\] For non-cancelling turns this follows by dividing the joint frequency of $\bar t,u$ by $p$; for cancelling turns both weights in the first equality are zero.

Lemma 2. There is a constant $\delta>0$ such that, for every sufficiently large $h$, \[ \sum_{W\in T^h}P(W)^2\le e^{-2\delta h}. \tag{6}\]

Proof. Let $M_{t,u}=w(t,u)^2$, and set $f(t)=5$ if $\bar t$ is extra and $f(t)=1$ otherwise. There are precisely three states of weight five.

If $\bar t$ is ordinary, the ordinary successors different from $\bar t$ contribute $(v-1)/(q+1)^2=q/(q+1)$ before the weights $f$ are inserted. At most three such successors have their weight increased by four. The extra successors all have weight one. Hence \[(Mf)(t)\le\frac{q}{q+1}+3p^2+\frac{12}{(q+1)^2} =\frac{500731261911}{504183783481}<\frac{149}{150}.\] If $\bar t$ is extra, the other two extras contribute two; the ordinary successors contribute at most $vp^2+12p^2$. Thus \[\frac{(Mf)(t)}{f(t)} \le\frac{2+vp^2+12p^2}{5} =\frac{820350863}{1363395845}<\frac{149}{150}.\] Consequently $Mf\le(149/150)f$. Since $\mathbf1\le f$ and $\sum_t f(t)=16528<e^{10}$, \[\sum_{W\in T^h}P(W)^2 =\mathbf1^{\mathsf T}M^{h-1}\mathbf1 \le16528(149/150)^{h-1} \le e^{-h/300}\qquad(h\ge3002).\] For example, $\delta=1/600$ is admissible. ◻

Girth conditioning and switching

Fix a sufficiently small positive constant $c$, and put \[L=\lfloor c\log n\rfloor.\] It is enough that \[ c\log(2|T|/p)<1,\qquad 2c\log d_*<1; \tag{7}\] one may take $c=1/100$. We work with the uniform tuple of matchings conditioned on $\mathop{\mathrm{girth}}(\Gamma)\ge L$. The next lemma both justifies this conditioning and gives a bound within the conditioned space.

Lemma 3. For all sufficiently large admissible $n$, there is a tuple of matchings with $\mathop{\mathrm{girth}}(\Gamma)\ge L$. In the uniform distribution on such tuples, condition further on any feasible set of $s$ prescribed matching pairs. The probability of an additional specified pair, not already prescribed in either direction, is at most \[ \frac{1}{np-s-r_n}, \qquad r_n=O(d_*^{2L+2})=o(n), \tag{8}\] whenever the denominator is positive. The error $r_n$ can be chosen uniformly over all prescriptions.

Proof. Before girth conditioning, a feasible simple cycle of length $k<L$ has at most $2n^k|T|^k$ vertex-and-letter descriptions. Its distinct edges require $k$ distinct matching prescriptions, with probability at most $(np-k)^{-k}$. Thus the expected number of edges lying on cycles shorter than $L$ is at most \[2\sum_{k<L}k\,n^k|T|^k(np-k)^{-k} \le2\sum_{k<L}k(2|T|/p)^k=o(n)\] for sufficiently large $n$, by (7). Choose a tuple with $o(n)$ such bad edges.

Let $xy$ be a bad edge, oriented with label $t$. Among the $np$ edges for this inverse pair on the same side, choose an edge $uz$, also oriented with label $t$, that is not bad and whose endpoint set is at distance greater than $2L$ from $\{x,y\}$. This is possible: bad edges exclude $o(n)$ choices, and the maximum-degree ball bound excludes another $O(d_*^{2L+2})=o(n)$.

Transpose the two matches, replacing $xy,uz$ by $xz,uy$. A short cycle using only one new edge would give an old path between the distant endpoint sets. If a short cycle uses both, deleting them leaves old paths pairing the endpoints as either $(x,u),(y,z)$ or $(x,y),(u,z)$. The first case again joins the distant sets. In the second, the $u$-to-$z$ path together with $uz$ is an old short cycle, contradicting the choice of $uz$. This includes $x=y$, when the $x$-to-$y$ path may have length zero. No short cycle is created. The chosen bad edge disappears, and the other removed edge was not bad, so the number of bad edges strictly decreases. Repetition produces a tuple of girth at least $L$.

Now restrict to any feasible girth-conditioned set with $s$ previous prescriptions, and consider an additional compatible pair $xy$. If it is incompatible, its probability is zero. From every tuple containing $xy$, perform the same transposition with any sufficiently distant edge $uz$ of the same inverse pair and side that is not previously prescribed. All edges are now nonbad. At least $np-s-r_n$ choices are available, with one uniform ball-size error $r_n$. Each output preserves girth and all prior prescriptions.

Given an output and the pair $xy$ to restore, the inverse operation is unique: the current match of $x$ is $z$, and the current preimage of $y$ is $u$. Thus the map from a tuple containing $xy$, together with an admissible transposition, to its output tuple is injective. If $\Omega_s$ is the conditioned set and $\Omega_{s,xy}$ is its subset containing $xy$, then \[|\Omega_{s,xy}|(np-s-r_n)\le|\Omega_s|.\] This proves (8). ◻

In particular, any feasible collection of $E=O(L)$ distinct edge prescriptions has conditional probability at most \[ (np)^{-E}\exp(o(L)). \tag{9}\] This follows by applying 3 successively. Uniformity of its error is important; no independence after conditioning is asserted.

Lemma 4. With conditional probability tending to one, every connected component of $\Gamma$ has diameter at most $D_0L$, for a fixed constant $D_0$.

Proof. Fix a small positive $\rho$. On either side, require every vertex set of size $1\le k\le\rho n$ to grow to at least $2k$ vertices on adjoining all its neighbors. A failure supplies a set of $2k$ vertices containing at least \[r=\lceil(q+1)k/2\rceil\] distinct edges: all edges incident to the failing $k$-set lie in the larger set and are counted at most twice by its degree sum.

There are at most $(C_1n/k)^{2k}$ choices for the larger set. Its possible typed edge prescriptions number $O(k^2)$; choosing an unordered $r$-subset costs at most $(C_1k)^r$. Decrease $\rho$ so that $r\le np/3$ throughout the range. For sufficiently large $n$, 3 then bounds the probability of all $r$ prescriptions by $(2/(np))^r$. Hence the probability of a failure of size $k$, on either side, is at most a fixed multiple of \[(C_1n/k)^{2k}(C_1k)^r(2/(np))^r \le \bigl(C_2(k/n)^{62.5}\bigr)^k,\] because $64.5\le r/k\le65$. Choose $\rho$ still smaller so that $C_2\rho^{62.5}<1/2$. Summing over $k\le\sqrt n$ gives $o(1)$; the sum over larger $k\le\rho n$ is at most $n2^{-\sqrt n}$.

On the resulting expansion event, every ball reaches more than $\rho n$ vertices in $R=O(\log n)$ steps. Along a geodesic, centers separated by $2R+1$ have disjoint radius-$R$ balls. At most $1/\rho$ such balls fit in one side. This bounds each component diameter by $O(\log n)=O(L)$, with a fixed constant. ◻

A bounded-pattern estimate

All probabilities in this section refer to the distribution conditioned on $\operatorname{girth}(\Gamma)\ge L$. We retain the predetermined vertices $x_A$ and $x_B$. The possible rooted interval will accommodate a null-homotopy of a root-to-vertex path in 5.

Consider finitely many positive-length paths in $\Gamma$, all cyclically immersed and closed except possibly one immersed interval path whose initial vertex is $x_A$ or $x_B$. An occurrence means a position on one of these paths; different occurrences may traverse the same edge. A pairing by interval pairs consists of disjoint occurrence intervals, paired in twos by length-preserving interval isometries. Even when the two intervals lie on the same path, they are distinct and disjoint as occurrence intervals. An order-preserving comparison requires equal signed letters, and an order-reversing comparison requires inverse letters in opposite orders. We impose the additional reduction condition \[ \text{paired occurrences traverse distinct underlying undirected edges of }\Gamma. \tag{10}\] Positions outside the paired intervals are called unpaired.

Proposition 5 (Bounded-pattern estimate). There is a constant $\varepsilon>0$, depending only on the fixed types and turn weights, with the following property. For every fixed positive integer $K$, fixed real $C\ge1$, and fixed nonnegative integer $I$, the conditional probability tends to zero that there exists a system as above having at most $K$ paths, total length $H$ with \[L\le H\le CL,\] at most $I$ interval pairs, and $b$ unpaired occurrences, where $b\le\varepsilon H$. In particular, $\varepsilon$ is chosen before $K,C,I$, and these three bounds are held fixed as $n$ tends to infinity through its admissible values.

We first describe the actual image of a candidate system by boundedly many chains. Sorting its edges by traversal multiplicity gives stages whose total vertex exponent is nonpositive. Nearly aligned blocks turn the path pairings into word constraints controlled by the squared-word estimate. Together, these bounds make the product of the stage expectation bounds exponentially small. Every realization must occur at every stage, so one small expectation bound suffices for the union bound.

Proof. Fix $K,C,I$. Constants implicit in this proof may depend on these bounds, whereas the final choice of $\varepsilon$ will not. Every $o(L)$ or $o(s)$ estimate below is uniform over the patterns with these fixed bounds. Cutting comparison intervals at the chosen indexing starts of closed paths changes only a fixed bound on the number of interval pairs, so we make these cuts at the outset.

By (5), reversing a chain does not change its word weight.

The image graph and multiplicity stages

Let $\Delta$ be the actual image subgraph of a proposed system. It has at most $CL$ edges and girth at least $L$. Mark every path start and end, and every vertex whose degree in $\Delta$ differs from two. We first show that $\Delta$ consists of a bounded number of chains between marks, with disjoint unmarked degree-two interiors. A chain is allowed to return to its initial mark.

Repeatedly delete leaves and their incident edges, and discard any edgeless remnants. This preserves cycle rank. Set aside the components of the resulting core that are circles; there are at most $C$, since each uses at least $L$ edges. Suppress all degree-two vertices in the remaining core. The resulting multigraph has minimum degree at least three; its edges have positive integer lengths, whose sum is at most $CL$. Suppose it has $r>0$ edges. Start a non-backtracking walk uniformly on its $2r$ directed edges, and at every subsequent step choose uniformly among the allowed continuations. Uniform measure on directed edges is stationary: a given directed edge with origin $z$ has $\deg(z)-1$ allowed predecessors, each contributing $1/[2r(\deg(z)-1)]$. This calculation also applies to loops and parallel edges, with degrees counted by half-edges.

The expected expanded length of a walk of $k$ edges is therefore at most $kCL/r$. At least half of the probability lies on walks of expanded length at most $2kCL/r$. Each particular walk has probability at most $(2r)^{-1}2^{-(k-1)}$, so there are at least $r2^{k-1}$ such short walks. Choose $k=O(\log(r+1))$ so that this number exceeds $(2r)^2$. There are at most $(2r)^2$ ordered pairs of endpoint vertices. Two distinct short walks consequently have the same endpoints. Their expansions are distinct reduced paths. Their union contains a cycle, since in a tree there is only one reduced path between two specified vertices. That cycle has length at most $4kCL/r$. Girth at least $L$ implies $r\le4Ck$, bounding $r$ in terms of $C$ alone. Thus the cycle rank of $\Delta$ is bounded.

The graph $\Delta$ has no isolated vertices and has at most two leaves. Indeed, a cyclically immersed path cannot visit a leaf, and an immersed interval path can visit one only at an endpoint. If $\beta$ is the cycle rank and $c_\Delta$ the number of components, the degree-sum identity gives \[\sum_{\deg(z)\ge3}(\deg(z)-2) =2\beta-2c_\Delta+\#\{z:\deg(z)=1\}.\] It follows that the number and total degrees of branching vertices are bounded. There are also only boundedly many path-start and path-end marks. Every component contains a path start. Suppressing all remaining unmarked degree-two vertices now proves the asserted bound on the number of marked chains, including circle components.

Every path traverses whole marked chains. Write $m_e$ for the total number of traversals of an undirected edge $e$ by all the paths; it is constant on each chain. If one immersed path traverses the same oriented edge twice, the gap between the two starting positions is at least $L$: the intervening segment is a nonempty reduced closed walk and hence contains a cycle. A path of length $h$ thus traverses any given oriented edge at most $h/L+1$ times. Summing over paths and the two orientations yields \[ m_e\le 2(H/L+K)\le2(C+K). \tag{11}\] Consequently the total number of chain traversals is bounded as well.

There are only polynomially many unlabelled patterns in $L$. To specify one, give the bounded marked multigraph, the positive integer length of each chain, the side $A$ or $B$ of each component, the oriented chain sequence of each path, the designation and starting side of the possible interval path, and the comparison endpoints and their orientation data. Each integer endpoint has $O(L)$ choices and there are boundedly many of them. We retain only patterns satisfying (10). Vertex names in $A$ and $B$, and signed edge labels, are not included in this description. Crucially, the abstract graph so described is the actual image graph: its subsequent realizations must be injective on vertices and edges.

Multiplicity stages and vertex exponents.

The density-counting viewpoint of organizing constraints by multiplicity, discussed by Ollivier (Ollivier 2005), motivates the stage organization and selection below. The conditioned matching estimate for the dependent graph paths in this model is developed locally.

For $1\le j\le m_*:=\max_e m_e$, let $\Delta_j$ consist of all edges with $m_e\ge j$, together with their incident vertices. Denote its edge and vertex counts by $E_j$ and $V_j$. Let $\iota$ be one if the interval path is present and zero otherwise. Then \[ \sum_{j=1}^{m_*}E_j=H,\qquad \sum_{j=1}^{m_*}V_j =\sum_{z\in\Delta^{(0)}}\max_{e\ni z}m_e \le H+\iota. \tag{12}\] For the inequality, let $a(z)$ count interval-path endpoints at $z$, with multiplicity. At a vertex, all traversal incidences except these endpoints are coupled into passages between distinct half-edges, by immersion and cyclic immersion. Thus the incidences on a half-edge of maximum multiplicity must be coupled to incidences on other half-edges, except for at most $a(z)$ endpoints. Hence \[2\max_{e\ni z}m_e \le \sum_{\text{half-edges at }z}m_e+a(z).\] Summing this inequality proves (12), because the half-edge sum is $2H$ and $\sum_z a(z)=2\iota$.

Set $k_1=\iota$, and $k_j=0$ for $j>1$. In stage one the initial vertex of the interval path has its prescribed image, saving one factor of $n$. We claim no such saving at later stages. The exponent needed below satisfies \[ \sum_{j=1}^{m_*}(V_j-E_j-k_j)\le0. \tag{13}\] In the later realization count, the exponent $V_j-E_j-k_j$ will count vertex-image choices against edge-prescription costs. Equation (13) therefore controls the total power of $n$ across the multiplicity stages. The remaining task is to obtain exponential decay from the label constraints; counting only distinct edges would lose the incidence balance that makes these two estimates compatible.

Word constraints on aligned blocks

The aim is a common subdivision for which each comparison carries almost all positions of a block into a single partner block. Orient each marked chain of length $\ell$, identify it with $[0,\ell]$, and put its edge positions at half-integers. Splitting comparisons at chain-traversal boundaries gives boundedly many subcomparisons of the form \[x\longmapsto\sigma x+a,\qquad \sigma\in\{1,-1\},\quad a\in\mathbb Z.\] These maps compare particular occurrences of subchains. Relative to the chosen chain orientations, their label relations are equality when $\sigma=1$ and inverse equality when $\sigma=-1$.

Pad the list of integer offsets by zeros to a fixed length $d\ge1$. Put \[N=\left\lfloor L^{1/(2(d+1))}\right\rfloor, \qquad R=\lfloor\sqrt N\rfloor.\] The simultaneous pigeonhole principle gives an integer $1\le u\le N^d$ such that $\operatorname{dist}(ua/L,\mathbb Z)\le1/N$ for every offset $a$. For completeness, place the $N^d+1$ vectors of fractional parts of $k(a_1/L,\ldots,a_d/L)$, for $0\le k\le N^d$, in the $N^d$ cubes of side $1/N$. Subtracting two vectors in the same cube gives the required $u$. Choose the least such $u$, so all choices are determined by the unlabelled pattern, and set $s=L/(uR)$. Uniformly in that pattern, \[ \frac{L}{N^{d+1/2}}\le s\le\frac{L}{R},\qquad \max_a\operatorname{dist}(a/s,\mathbb Z)\le\frac{R}{N}. \tag{14}\] In particular, $s$ tends to infinity at least as a fixed positive power of $L$, while $s/L$ and all the distances in (14) tend to zero.

On each chain use the full grid intervals $[ks,(k+1)s)$ contained in $[0,\ell]$, for integers $k\ge0$. The half-integer edge positions in such an interval form a full block. Index these blocks over all of $\Delta$ by $i$. Their lengths and multiplicities satisfy \[h_i=s+O(1),\qquad m_i=m_e\quad\text{on their chains}.\] The remaining end fragment of a chain has $O(s+1)$ positions. Every traversal of the same chain uses this same subdivision, also when read backwards.

Here is the alignment consequence of (14), including reflections. Write $a=\nu s+r$, with $\nu\in\mathbb Z$ and $|r|=o(s)$. A translation sends the $k$-th real grid interval to the $(k+\nu)$-th interval shifted by $r$. A reflection sends it to \[((\nu-k-1)s+r,(\nu-k)s+r].\] Because $a$ is integral, the isometry preserves the half-integer lattice. In either case its image overlaps the indicated partner grid block in a contiguous string of at least $s-|r|-2=s-o(s)$ positions. The reversed endpoint convention in the reflection costs only a bounded number of positions.

Figure 1 illustrates the translation case. The grid belongs to the underlying chain, not to an individual path traversal: repeated traversals use the same blocks but give distinct block occurrences. This distinction will matter when occurrence pairings are projected to links between underlying blocks.

Approximate alignment under a translation, shown schematically with $0<r=o(s)$. A source block is translated by $a=\nu s+r$; its image overlaps the indicated target block in real length $s-r$. Restricting to half-integer edge positions loses at most a bounded number of positions, giving $s-o(s)$ compared letters. The shift is exaggerated for visibility. The proof also treats negative shifts and reflections.

Join two full-block occurrences whenever one of the subcomparisons identifies contiguous subwords in them of length at least $(1-\kappa)s$, where $\kappa=o(1)$ is chosen uniformly large enough to absorb the alignment and rounding errors. Record one such substring comparison with each join. These joins form a partial matching of block occurrences: each compared substring occupies more than half its block, whereas the original comparison domains are disjoint as occurrence intervals. Thus a block occurrence cannot participate in two joins.

Let $b_*$ be the number of unmatched full-block occurrences. Only boundedly many blocks lie within $3s+O(1)$ of a subcomparison cut or a chain endpoint. Away from these cuts, a full block in a comparison domain has its partner full block and hence is matched. Every remaining unmatched block away from the cuts consists entirely of unpaired positions. There are $O(L/s)$ block occurrences in total, so rounding their lengths and charging the exceptional blocks gives \[ sb_*\le b+O(s+L/s)=b+o(L). \tag{15}\]

Links between underlying blocks.

Forget occurrence indices in this matching, obtaining a multigraph whose vertices are the full blocks $i$. We call its edges links and include isolated blocks. The substring positions and directions attached to every link are already fixed by the unlabelled pattern. In a component $\mathcal U$ of this link graph, a word on any one block determines the word on each next block along a spanning tree except for $o(s)$ letters. Indeed, the recorded comparison specifies $s-o(s)$ letters of the next word, possibly with reversal and inversion. Since the alphabet is fixed, the number of extensions of a root word to all blocks in $\mathcal U$ is at most \[ \exp\bigl(o(s)|\mathcal U|\bigr). \tag{16}\] Additional links and immersion constraints can only reduce this number.

If $\mathcal U$ has a self-link, choose a self-linked block as the root. Its word has only $\exp(o(s))$ possibilities, or the pattern is infeasible. To prove this, first consider a translation self-link. Its constraints have the form \[W(x)=W(x+t)\quad(x\in D),\] where $D$ and $D+t$ are contiguous subsets of the same block and $|D|=s-o(s)$. The integral shift $t$ is nonzero by (10); a zero shift would compare the same underlying edge with itself. On the $h_i$ positions of the block, the $|D|$ distinct constraint edges form a forest of arithmetic chains with step $|t|$. Thus this forest has $h_i-|D|=o(s)$ components, leaving at most $|T|^{h_i-|D|}=\exp(o(s))$ root words.

For a reflection self-link, write its map as $\phi(x)=a-x$. The intersection $J=D\cap\phi(D)$ of its nearly full domain and image is a contiguous reflection-invariant set with $|J|\ge2|D|-h_i>0$. If $a$ is odd, its center is a half-integer position in $J$, forcing that letter to equal its inverse. If $a$ is even, the two half-integer positions on either side of its center are adjacent positions in $J$ and their letters must be inverse. The first alternative contradicts the fixed-point-free involution on $T$, and the second contradicts immersion. Thus reflection self-links are infeasible. Combining the translation bound with (16), a component with a self-link has at most $\exp(o(s)|\mathcal U|)$ full word assignments altogether.

For any link component put \[S_{\mathcal U}=\sum_{i\in\mathcal U}m_i,\qquad z_{\mathcal U}=\max_{i\in\mathcal U}m_i,\qquad b_{\mathcal U}=\#\{\text{unmatched block occurrences in }\mathcal U\}.\] If $\mathcal U$ has no self-link, then \[ 2z_{\mathcal U}\le S_{\mathcal U}+b_{\mathcal U}. \tag{17}\] Indeed, take a block of multiplicity $z_{\mathcal U}$. At least $z_{\mathcal U}-b_{\mathcal U}$ of its occurrences are matched, and their partners are distinct occurrences of other blocks in the same component. There are only $S_{\mathcal U}-z_{\mathcal U}$ such other occurrences. This proves (17), also for isolated blocks and in the presence of multiple links.

Binning the word weights.

For each full-block word $W_i$, read in its chain orientation, specify the integer \[d_i=\lfloor-\log P(W_i)\rfloor.\] We need only consider positive weights, since feasible block words are immersed. By Lemma 2, every such word of length $h$ has $P(W)\le e^{-\delta h}$ for all sufficiently large $h$. The smallest positive turn weight is a fixed positive number. Hence there is a constant $a_0>0$, depending only on the turn weights, such that for all large $L$, \[ \frac{\delta s}{2}\le d_i\le a_0s, \qquad \#\{W_i:\lfloor-\log P(W_i)\rfloor=d_i\} \le\exp(2d_i-\delta s). \tag{18}\] For the counting assertion, every word in the indicated bin contributes more than $e^{-2d_i-2}$ to the sum of squared weights. The same lemma therefore bounds the number of these words by \[\exp(2d_i+2-2\delta h_i)\le\exp(2d_i-\delta s),\] using $h_i=s+O(1)$. This also explains why the bin estimate uses the squared, rather than the unsquared, word weights.

Enlarge each unlabelled pattern by its bin integers. There are $O(L/s)$ blocks and $O(s)$ possible bin values per block, so the number of choices is at most \[\exp\bigl(O((L/s)\log(s+1))\bigr)=\exp(o(L)).\] Together with the earlier polynomial count, the number of enlarged patterns is $\exp(o(L))$, uniformly for the fixed bounds.

Expected counts and stage selection

The block estimates now control feasible strings. We combine them with the matching-prescription estimate to count injective realizations of each multiplicity stage, keeping string extension distinct from graph embedding extension.

Fix an enlarged pattern. A permitted label assignment on $\Delta_j$ is the restriction of some label assignment on all of $\Delta$ satisfying the bins, the immersion condition into the rose, and all original comparisons. This is a condition on strings: no embedding of the inactive part of $\Delta$ in the sampled graph is required. Let $X_j$ count injective realizations of $\Delta_j$, with these permitted labels and prescribed sides, and with the prescribed initial vertex in stage one if $\iota=1$. A realization of the entire path system gives $X_j\ge1$ at every stage.

For one fixed permitted stage label assignment, its expected number of vertex realizations is at most \[ n^{V_j-E_j-k_j} \exp\left(-\sum_{i:m_i\ge j}d_i+o(L)\right). \tag{19}\] Here are the vertex and edge counts giving this bound. A chain is either entirely present or absent at stage $j$, because its multiplicity is constant. Let $Q_j$ be the number of active chains. There are $E_j-Q_j$ internal chain vertices. If such a vertex has incoming letter $t$ and outgoing letter $u$, then on its prescribed side it has at most $np\,w(t,u)$ possible images. All other unfixed vertices have at most $n$ choices. The fixed initial vertex, when imposed, is a marked vertex. Ignoring injectivity gives the upper bound \[n^{V_j-k_j}p^{E_j-Q_j} \prod_{\text{internal chain turns}}w(t,u)\] on the number of vertex assignments. We apply probability estimates only to the feasible injective choices among these assignments.

Such a choice requires $E_j$ distinct matching prescriptions. Two distinct edges cannot prescribe the same matching pair in either direction, because injectivity and the immersion condition would then identify their outgoing letters at an endpoint. By Lemma 3, the probability of all these prescriptions is at most \[\left(\frac{1+o(1)}{np}\right)^{E_j},\] uniformly since $E_j=O(L)$. Multiplication leaves the bounded factor $p^{-Q_j}$, the power $n^{V_j-E_j-k_j}$, and the product of internal turn weights. Discard turn weights outside full blocks, since they are at most one. The retained product is $\prod_{i:m_i\ge j}P(W_i)\le\exp(-\sum_{i:m_i\ge j}d_i)$. The bounded factor and the prescription errors are absorbed in $\exp(o(L))$, proving (19).

The number of permitted stage label assignments is at most \[ \exp\left(o(L)+ \sum_{\substack{\mathcal U\text{ without a self-link}\\ z_{\mathcal U}\ge j}} \left(2\min_{i\in\mathcal U}d_i-\delta s\right)\right). \tag{20}\] To see this carefully, consider a link component with at least one active block, equivalently $z_{\mathcal U}\ge j$. The allowed labels on its active blocks are projections of full feasible word assignments on that component. Their number cannot exceed the number of full assignments. If the component has no self-link, choose a root attaining $\min_{i\in\mathcal U}d_i$, count its words by (18), and extend along a spanning tree by (16). This argument is valid even if the chosen root is inactive at this stage: it counts full word assignments before projecting, and asserts no extension of an embedded graph. A self-linked component has only its propagation error, as proved above. Components with no active block contribute nothing. The sum of propagation errors is $o(L)$, since the total number of blocks is $O(L/s)$. Arbitrary letters in the end fragments contribute at most $\exp(O(s))$ per marked chain, again $\exp(o(L))$. Ignoring any further constraints between components gives (20).

Selecting a stage and summing over patterns.

Let $B_j$ be the product of the right-hand sides of (19) and (20). Thus $\operatorname{E}X_j\le B_j$. Multiply these numerical upper bounds over $1\le j\le m_*$. The total exponent of $n$ is nonpositive by (13). For a link component without a self-link, put $d_{\min}=\min_{i\in\mathcal U}d_i$. Its remaining contribution to the logarithm of the product is \[F_{\mathcal U} =-\sum_{i\in\mathcal U}m_i d_i +2z_{\mathcal U}d_{\min}-\delta s z_{\mathcal U}.\] If $2z_{\mathcal U}\le S_{\mathcal U}$, then (18) gives \[F_{\mathcal U} \le-(S_{\mathcal U}-2z_{\mathcal U})\frac{\delta s}{2} -\delta s z_{\mathcal U} =-\frac{\delta}{2}sS_{\mathcal U}.\] If $2z_{\mathcal U}>S_{\mathcal U}$, use (17), the upper bin bound, and $z_{\mathcal U}>S_{\mathcal U}/2$ to obtain \[F_{\mathcal U} \le(2z_{\mathcal U}-S_{\mathcal U})a_0s -\delta s z_{\mathcal U} \le a_0s b_{\mathcal U}-\frac{\delta}{2}sS_{\mathcal U}.\] For a self-linked component the negative cost $-\sum_i m_i d_i$ alone is at most $-\delta sS_{\mathcal U}/2$.

Bounded multiplicities and boundedly many chains imply \[\sum_{\mathcal U}sS_{\mathcal U}=H+O(L/s+s)=H+o(L), \qquad s\sum_{\mathcal U}b_{\mathcal U}\le b+o(L),\] where the second inequality is (15). There are only boundedly many stages by (11), so all their error terms remain $o(L)$. We have proved \[ \log\prod_{j=1}^{m_*}B_j \le-\frac{\delta}{2}H+a_0b+o(L). \tag{21}\]

Choose, once and for all, \[\varepsilon=\min\left\{\frac14, \frac{\delta}{16(1+a_0)}\right\}>0.\] This depends only on the fixed turn weights. For $b\le\varepsilon H$ and all sufficiently large $L$, uniformly over the fixed pattern bounds, (21) gives \[\prod_{j=1}^{m_*}B_j\le e^{-\delta H/4}.\] Put $M=\max\{1,\lceil2(C+K)\rceil\}$, so $m_*\le M$. Some stage therefore has $B_j\le e^{-\delta H/(4M)}$. Since a realization of the entire enlarged pattern requires $X_j\ge1$ at every stage, Markov’s inequality gives \[\operatorname{Pr}(\text{this enlarged pattern is realized}) \le\min_j\operatorname{E}X_j \le\min_j B_j \le e^{-\delta H/(4M)}.\] This uses no independence between stages. We multiplied numerical bounds solely to find one stage with a small expectation.

Finally there are $\exp(o(L))$ enlarged patterns and $H\ge L$. The union bound is at most $\exp(o(L)-\delta L/(4M))$, which tends to zero. This proves the proposition with the asserted order of quantifiers. ◻

From bounded patterns to spherical arrangements

Proposition 5 controls systems of bounded size. We now show that any spherical arrangement of the kind needed for the topological argument contains such a system. The number of disks in the arrangement is unrestricted. Throughout this section, probability is taken in the distribution conditioned on girth at least $L$.

Definition 6 (Reduced spherical arrangement). A reduced spherical arrangement over $\Gamma$ consists of the following data on an oriented sphere.

There are finitely many pairwise disjoint piecewise linear closed disks. Each disk boundary carries a positive-length cyclically immersed closed path in $\Gamma$, with the possible exception of one boundary. That exceptional boundary carries a positive-length immersed interval path starting at $x_A$ or $x_B$: its two endpoints are represented at one marked boundary point, called the break. No immersion condition is imposed across that break. At least one ordinary cyclically immersed boundary is present.
The paths are read in the boundary orientations induced by the oriented disks. Their edge occurrences are paired in distinct twos by piecewise linear arcs whose interiors lie outside the disks. The arcs are mutually disjoint, and each occurrence contains exactly one arc end in its interior.
Paired occurrences have inverse signed letters in these boundary orientations, and their underlying undirected edges of $\Gamma$ are distinct, as required by Equation 10.

Occurrences remain distinct even when the paths revisit the same graph edge. The arc graph may have loops, parallel edges, or several connected components.

Short closures

Fix a deterministic constant $d$ such that the event \[\operatorname{diam}(\Lambda)\le dL \quad\text{for every connected component $\Lambda$ of $\Gamma$} \tag*{\textnormal{(diameter event)}}\] has probability $1-o(1)$, as supplied by Lemma 4. We first work on this event.

Lemma 7 (Closing a segment without cancellation). There is a fixed integer $D$, independent of $n$ and of the segment, such that every positive-length immersed segment in $\Gamma$ extends to a cyclically immersed closed path by appending at most $DL$ edges. The original segment is retained without cancellation.

Proof. Appending a geodesic return may cancel the ends of the given segment. We prevent this by inserting short based loops with prescribed first and last edge exclusions. To construct such a loop at a vertex $z$, delete at most two specified incident undirected edges from its side of $\Gamma$. For sufficiently large $n$, girth at least $L\ge3$ excludes graph loops and parallel edges; after the deletion every vertex still has degree at least $(q+1)-2\ge3$. Put \[k=\lceil\log_2 n\rceil+1.\] From $z$ in the remaining graph there are at least $3\cdot2^{k-1}>n$ non-backtracking walks of length $k$. That graph has at most $n$ vertices, so two distinct such walks $P,Q$ end at the same vertex. Reduce $PQ^{-1}$ as a linear edge path. This removes just their common terminal segment. Since $P$ and $Q$ have equal length and are distinct, neither walk is entirely removed. The result is a nonempty reduced based loop of length at most $2k$, whose first and last edges avoid both deleted edges. The loop need not be cyclically immersed at $z$; only its linear reduction will be used.

Let $S$ be the given segment, running from $a$ to $b$, and let $R$ be a geodesic from $b$ to $a$, of length at most $dL$. If $R$ is nonempty, choose a based loop $J_b$ at $b$ by excluding the last edge of $S$ and the first edge of $R$. Choose $J_a$ at $a$ by excluding the last edge of $R$ and the first edge of $S$. Then \[S J_b R J_a\] has no backtracking at any join, including its cyclic last/first join. If $R$ is empty, so that $a=b$, use just one based loop $J_a$, excluding the last and first edges of $S$; the path $SJ_a$ is cyclically immersed. The immersion $\Gamma\to F$ also makes every one of these joins reduced in signed letters.

For large $n$ we have $L\ge(c/2)\log n$ and $L\ge1$, whence \[k\le \left(\frac{2}{c\log2}+2\right)L.\] Thus any integer \[D\ge d+\frac{8}{c\log2}+8\] bounds the added length $|R|+4k$ in units of $L$, and covers the empty-return case as well. ◻

Turning planar pairings into intervals

The next bound concerns only the original paired occurrences; edges added to close segments will always be left unpaired.

Lemma 8 (A linear bound on comparison intervals). Suppose an arrangement with $N$ disk boundaries is divided into $N'\ge N$ pieces by cutting each original path into consecutive segments, without crossing an exceptional break. A path left intact counts as one piece. Then its occurrence pairing can be specified by at most $6N'$ pairs of intervals. Both intervals in every pair lie wholly in their designated pieces, are distinct as occurrence intervals, and compare inverse strings in reversed boundary order.

Proof. Thicken the disks and pairing arcs to a regular disk-and-band neighborhood $R$ of their planar multigraph. Let $E$ denote its number of arcs. A vertex gap is the boundary arc between consecutive pairing-arc ends in the cyclic order around one disk. For each connected complementary compact surface $Q$, let $l_Q$ be the number of band sides in its boundary. Equivalently, $l_Q$ counts the intervening vertex gaps, with incidences counted separately. Every vertex has positive degree, so every boundary component of $R$ meets a band side, and $l_Q\ge1$.

Call a vertex gap good if it belongs to a complementary disk digon whose two sides come from two distinct arcs. The two gaps across such a digon are both good. If consecutive occurrences at one corner are $e,f$ and their partners are $e',f'$, the opposite corner has coherent order $f',e'$. Thus $(e,f)\leftrightarrow(f',e')$ is an involution on good gaps. Here the symbols denote occurrences, not underlying graph edges. Good gaps therefore continue an inverse-word comparison. We first bound the remaining gaps, where this continuation can fail, before making the required indexing and splitting cuts.

The neighborhood retracts to the multigraph, so $\chi(R)=N-E$. Gluing the complementary surfaces to it along boundary circles gives \[\sum_Q\chi(Q)=2-N+E, \qquad \sum_Q l_Q=2E.\] Consequently \[ \sum_Q\bigl(l_Q-2\chi(Q)\bigr)=2N-4. \tag{22}\] This calculation uses neither connectedness of the multigraph nor simple connectivity of its complementary regions.

We bound the non-good gaps, including the possible degenerate faces, as follows.

A disk monogon has one gap between occurrences paired by its single arc. Those consecutive letters are inverse, so immersion forbids the gap unless it is the exceptional break. Thus there are at most $M\le1$ monogons, contributing $-M$ to Equation 22.
A disk digon traversing the same arc twice must turn immediately back along that arc at an endpoint. No other arc end can intervene in the cyclic order there, so that endpoint has degree one. Different such faces use different degree-one gaps. There are at most $N$ such faces, and hence at most $2N$ gaps of this type. This deliberately allows a coarse bound, including isolated single-edge components.
Every connected non-disk complementary surface is planar with Euler characteristic at most zero. Its length is therefore at most its contribution $l_Q-2\chi(Q)$. For a disk region of length $l_Q\ge3$, we instead have $l_Q\le3(l_Q-2)$.

All contributions except those of monogons and digons are positive. Their total is $2N-4+M$, by Equation 22. If $B_{\mathrm{gap}}$ is the number of non-good gaps, these observations give \[ B_{\mathrm{gap}}\le M+2N+3(2N-4+M)\le8N. \tag{23}\]

Cut at every non-good gap. Mark also one indexing gap for each original path, using the exceptional break when present, and all gaps used in the prescribed splitting. There are at most $N+N'$ additional marked gaps: a split cyclic boundary into $m$ pieces needs at most $m$ splitting gaps, and a split interval needs no more. Whenever a marked gap is good, cut both it and its opposite good gap. The resulting cut set is stable under the good-gap involution and has cardinality $J$ satisfying \[J\le B_{\mathrm{gap}}+2(N+N')\le12N'.\]

Every original boundary now has at least one cut. Its remaining occurrence-adjacency components are therefore linear runs, all lying inside their prescribed pieces. The occurrence pairing reverses every uncut adjacency. Stability of the cut set implies that it maps each whole maximal run onto another whole maximal run in reverse order. A run cannot map to itself: an odd-length run would have a fixed occurrence, while an even-length run would pair its two central consecutive occurrences and give inverse adjacent letters. The latter contradicts internal immersion; the exceptional break was cut and cannot occur at the center of such a run.

There are exactly $J$ runs, since each original boundary is a circle with a nonempty cut set. They pair in distinct twos, giving at most $J/2\le6N'$ interval pairs. Inverse letters and reversed order are exactly the signed comparison convention of Proposition 5. ◻

Separating a planar graph into bounded components

Lemma 9 (Recursive planar separation). Put \[C_{\mathrm{sep}}=\frac{2\sqrt2}{1-\sqrt{2/3}}.\] For every integer $K\ge1$, a planar multigraph with $m$ vertices has a set of at most $C_{\mathrm{sep}}m/\sqrt K$ vertices whose deletion leaves components of size at most $K$.

Proof. Remove loops and merge parallel copies of edges. These operations preserve connected components, including after any vertex deletion. The planar separator theorem of Lipton and Tarjan (Lipton and Tarjan 1979, Corollary 2, p. 183) supplies, in any simple planar graph with $s$ vertices, at most $2\sqrt{2s}$ vertices whose deletion leaves components with at most $2s/3$ vertices. Apply this theorem recursively to each component with more than $K$ vertices.

For a recursive call on $s>K$ vertices, charge $2\sqrt2/\sqrt s$ to each of those vertices. The total charge at this call is $2\sqrt{2s}$ and bounds the number deleted. Fix one original vertex and list the successive component sizes containing it before it is deleted or recursion stops. Consecutive sizes decrease by a factor at most $2/3$. Reading the list backwards from its last size greater than $K$, its total charge is at most \[\frac{2\sqrt2}{\sqrt K} \sum_{j\ge0}(2/3)^{j/2} =\frac{C_{\mathrm{sep}}}{\sqrt K}.\] This also covers vertices that are themselves deleted at a separator. Summing over the original vertices proves the bound. Components already of size at most $K$ incur no charge. ◻

Extracting a forbidden bounded pattern

Proposition 10 (Absence of reduced spherical arrangements). With probability $1-o(1)$, $\Gamma$ admits no reduced spherical arrangement. In particular, for all sufficiently large admissible $n$ there exist graphs of the prescribed types, with girth at least $L$ and the diameter bound of Lemma 4, admitting no such arrangement.

Proof. Let $\varepsilon>0$ be supplied by Proposition 5; it is independent of the fixed pattern bounds. Fix $d$ for the diameter event and then the integer $D$ from Lemma 7. Splitting at length about $UL$ will make each closure cost of at most $DL$ a small proportion of the original length. We choose $U$ to control that cost, $\eta$ to control the original positions discarded by planar separation, and $C_2$ as a cutoff for the number of comparison intervals relative to path length. Choose, in the indicated order, \[\begin{align*} U&\ge\max\{3,\lceil96D/\varepsilon\rceil\}, &&\text{$U$ an integer}, \\ \eta&=\min\left\{\frac1{32U},\frac{\varepsilon}{64U}\right\}, &K&=\max\left\{1,\left\lceil(C_{\mathrm{sep}}/\eta)^2\right\rceil\right\}, \tag{24}\\ a&=6,\qquad C_2=32a, &C&=K(U+D),\qquad I=\lceil C_2C\rceil. \end{align*}\] Here $C_{\mathrm{sep}}$ is the constant in Lemma 9. These choices imply \[ \frac{3D}{U}\le\frac{\varepsilon}{32},\qquad 2\eta U\le\frac1{16},\qquad 2\eta U\le\frac{\varepsilon}{32}. \tag{25}\] For reference, the dependency order is \[ \text{types},c,\delta\ ;\quad \varepsilon,d\ ;\quad D\ ;\quad U\ ;\quad\eta\ ;\quad K\ ;\quad C,I\ ;\quad n. \tag{26}\] All constants preceding $n$ are fixed before $n$ tends to infinity through multiples of $2v^2$, with $L=\lfloor c\log n\rfloor$. In particular, the bounded-pattern estimate is applied to one fixed triple $(K,C,I)$, not to bounds growing with $n$.

Suppose, on the diameter event, that a reduced spherical arrangement exists. Write $N$ for its number of boundaries and $H_0$ for their total length. There is an ordinary cyclically immersed boundary, so girth gives $H_0\ge L$.

Splitting and closing long paths.

Keep every path of length at most $UL$ intact. A longer path of length $h$ is split into $m=\lceil h/(UL)\rceil$ consecutive integer-length segments whose lengths differ by at most one. For large $L$, these lengths lie between $UL/3$ and $UL$: indeed $h/m>UL/2$, and $\lfloor h/m\rfloor\ge UL/3$ once $UL\ge6$, while $\lceil h/m\rceil\le UL$. For an exceptional path use its linear order from the prescribed initial vertex, so no segment spans the break. Close each segment by Lemma 7, and leave every added occurrence unpaired.

Denote the number of resulting paths by $N'$. Each has length at most $(U+D)L$ and contains at most $UL$ original occurrences. Since $m\le3h/(UL)$, the total added length $H_{\mathrm{add}}$ satisfies \[ H_{\mathrm{add}}\le\frac{3D}{U}H_0. \tag{27}\] Every resulting path has at least $L$ original occurrences, except possibly the single exceptional path when it was kept intact: ordinary intact paths have that length by girth, and split segments have length at least $UL/3\ge L$. It follows that \[ N\le N',\qquad N'L\le H_0+L\le2H_0. \tag{28}\] If the exceptional path was long, all its pieces have been closed and there is no remaining interval path. Otherwise the entire exceptional path remains, with its original prescribed initial vertex.

Apply Lemma 8 to the original positions in these pieces. It represents their pairing by at most $aN'$ interval pairs, each contained in the designated pieces. On a newly closed path, index its original segment first and its closure afterwards; this keeps those intervals within the linear indexing as well.

Deleting a small set of pieces.

Make a multigraph whose vertices are the $N'$ pieces and whose edges are the original pairing arcs. This graph is planar. To see this locally, replace each old disk vertex by a separate vertex for each consecutive block of its incident arc ends. Place those vertices inside disjoint sectors of the old disk and join each to its own block of ends within its sector. These connections have no crossings, including when an original arc had both ends at the old vertex. Closures have no incident pairing arcs and need no additional edges.

By Lemma 9 and the choice of $K$, delete at most $\eta N'$ vertices so that each remaining component, called a cluster, has at most $K$ pieces. The number $M$ of deleted original positions is at most \[ M\le\eta N'UL\le2\eta U H_0. \tag{29}\] Retain just those occurrence pairs whose two pieces survive. Each surviving original position has at most one deleted partner, so the number of newly unpaired surviving original positions is at most $M$. Each comparison interval lies in one piece on either side; thus an interval pair is retained or discarded in its entirety. No retained pair joins different clusters.

For a cluster $Z$, let $H_Z$ be its total path length including closures, $b_Z$ the number of its unpaired positions, and $I_Z$ its number of retained interval pairs. Equations 27, 28, and 29 give \[\begin{align*} \sum_Z H_Z&\ge(1-2\eta U)H_0, \\ \sum_Z b_Z&\le(2\eta U+3D/U)H_0, \tag{30}\\ \sum_Z I_Z&\le aN'\le 2aH_0/L. \end{align*}\] Also every cluster satisfies $H_Z\le K(U+D)L=CL$.

A positive amount of admissible length survives.

The retained total length is at least $15H_0/16$ by Equation 25. Clusters with $b_Z>\varepsilon H_Z$ have total length at most \[\frac1\varepsilon\sum_Z b_Z\le\frac{H_0}{16}.\] Clusters with $I_Z>C_2H_Z/L$ likewise have total length at most \[\frac{L}{C_2}\sum_Z I_Z \le\frac{2a}{C_2}H_0=\frac{H_0}{16}.\] After excluding both classes, at least $13H_0/16$ of cluster length remains.

A cluster of length less than $L$ can contain no positive-length cyclically immersed path. Thus it can consist only of the one intact short exceptional path, and there is at most one such cluster. If its length is $h<L$, the original arrangement also contained an ordinary cyclic path of length at least $L$, so $H_0\ge h+L>2h$. Removing that cluster therefore costs less than $H_0/2$. The clusters left after all three exclusions have total length at least \[\left(\frac{15}{16}-\frac1{16}-\frac1{16}-\frac12\right)H_0 =\frac5{16}H_0>0.\] Choose one such cluster. It contains at most $K$ positive-length paths, has \[L\le H_Z\le CL,\qquad b_Z\le\varepsilon H_Z,\qquad I_Z\le C_2H_Z/L\le C_2C\le I,\] and inherits Equation 10. All paths are cyclically immersed except possibly the entire short exceptional interval, whose initial vertex is still $x_A$ or $x_B$. Added closures may traverse old edges repeatedly; all their occurrences are unpaired, as permitted by Proposition 5. The cluster is therefore one of the bounded patterns excluded by 5.

The constants in Equation 24 were chosen using the single $\varepsilon$ independent of $K,C,I$. The probability of such a bounded pattern is $o(1)$, and the probability of failure of the diameter event is $o(1)$. Every finite reduced spherical arrangement, regardless of size, deterministically yields a pattern for these same fixed bounds. This proves the claimed probability estimate and hence the existence assertion. ◻

Cone pictures and torsion-freeness

Fix graphs supplied by 10. Attach to the rose $F$, for each connected component $\Lambda$ of $\Gamma$, its abstract cone $K_\Lambda$ along the labelled map $\Lambda\to F$. Denote the resulting finite two-dimensional CW complex by $X$, and put $G=\pi_1(X)$, based at the rose vertex. In particular, labels of all closed walks in $\Gamma$ are trivial in $G$.

Proposition 11. The complex $X$ satisfies $\pi_2(X)=0$. Moreover, if a path in $\Gamma$ starts at $x_A$ or $x_B$ and ends at a different vertex, its label is nontrivial in $G$.

We prove the two conclusions together, using minimal surface pictures. The proof keeps track of the actual boundary lifts in $\Gamma$. Removing overlaps with coincident graph lifts is also central to the graphical-diagram arguments of Gruber and Bereznyuk (Gruber 2015; Bereznyuk 2019). Their hypotheses are not imported here: we give the cone-picture reduction needed for 10 directly, without a graphical small-cancellation condition.

Representing maps by pictures

A cone picture on a sphere or disk consists of finitely many disjoint tame disks in the surface interior, called inner disks, with the following mapping data. Each inner disk has a specified boundary lift to a graph component $\Lambda$, its filling factors through $K_\Lambda$, and the complement of the disk interiors maps to $F$. The boundary lifts are combinatorial closed paths. For a disk domain the outer boundary additionally reads the label of a specified interval path in $\Gamma$.

Lemma 12. Every essential sphere map to $X$ can be replaced by an essential sphere map admitting a cone picture. Every null-homotopy of a graph-path label can be represented by a disk cone picture with that boundary label.

Proof. For each component $\Lambda$, choose based edge loops representing a free basis of $\pi_1(\Lambda)$. Temporarily replace $K_\Lambda$ by the space $Y_\Lambda$ obtained by attaching one disk to $\Lambda$ along each basis loop. The space $Y_\Lambda$ is simply connected. The classes of its attaching loops form a basis of $H_1(\Lambda;\mathbb Z)$, so its cellular chains show that its positive-dimensional homology vanishes. A simply connected acyclic CW complex is contractible, by the Hurewicz and Whitehead theorems; see (Hatcher 2002, Theorem 4.32 and Corollary 4.33).

Both $Y_\Lambda$ and $K_\Lambda$ contain $\Lambda$ as a subcomplex. Their contractibility gives maps between them restricting to the identity on $\Lambda$, and homotopies of the composites to the identities relative to $\Lambda$: extend the prescribed maps and homotopies over relative cells, using the vanishing of the homotopy groups of the targets. These relative maps and homotopies glue with the identity on $F$. This works even though $\Lambda\to F$ is not injective. We obtain an ordinary rose-with-relator-disks model homotopy equivalent to $X$ relative to $F$.

That finite model can be triangulated. Take collars inside the relator disks, view their attachments to $F$ as mapping cylinders, subdivide the collar rectangles so that their bottom edges map injectively to small rose edges, and triangulate. A surface map can be approximated piecewise linearly, preserving its boundary in the graph. If needed, a graph collar homotopy restores the original boundary word in the disk case.

Choose a point in the interior of each relator disk outside the images of degenerate or lower-dimensional simplices. It has finitely many preimages, with disjoint disk neighborhoods that map homeomorphically onto a small disk around the chosen point. Choose these target disks small enough that there are no other preimages. A radial map of each relator disk expands the small target disk to the whole relator disk and sends the remaining annulus to its attaching boundary. This map is homotopic to the identity relative to $F$.

After composition, the complement of the preimage disks maps to $F$, and each preimage disk reads an attaching loop, with one of its two orientations. Return to $X$ using the relative equivalences of the individual cone substitutes. Each disk then factors through its specified abstract cone. Essentiality of a sphere, or the prescribed disk-boundary word, is preserved. ◻

Minimizing a failure picture

Suppose that one conclusion of 11 fails. In the sphere case, consider all essential sphere pictures; the homotopy class is allowed to vary. In the disk case, fix two distinct vertices witnessing a failure, with the first one equal to $x_A$ or $x_B$, and allow the interval path between them to vary. By 12, the appropriate class of pictures is nonempty.

Choose a picture of least total boundary length, counting all inner boundaries and, in the disk case, the outer path. This length is a nonnegative integer. Cyclically tighten every inner loop in its own graph component. The tightening can be performed on a collar, with the smaller disk filled through the same cone. The old filling and this replacement are homotopic relative to the old boundary, since both factor through that contractible cone. A constant boundary disk can be removed. Thus every inner boundary is nonempty and cyclically immersed.

Tighten the outer interval relative to its actual graph endpoints. It remains nonempty because those endpoints are distinct. There must be at least one inner disk: a graph has no essential sphere, and a nonempty immersed graph path has a nonempty freely reduced word under the immersion to the rose, so its label cannot be trivial in $\pi_1(F)$.

For a disk-domain picture, cap the exterior conceptually by an extra disk. Its boundary carries the interval path, with a single marked break from the endpoint back to the initial vertex. No map of that extra disk into $X$ is required. Orient the sphere so that the coherent exterior-disk boundary orientation reads this path from its prescribed root to its endpoint. We now have an oriented sphere with ordinary inner disks and at most one exceptional exterior disk.

In the surface region mapping to $F$, take transverse preimages of one interior point in each rose edge. This can again be arranged by PL approximation relative to the boundary words, using collars to straighten their parametrizations. The preimages are disjoint circles and arcs. Ignore the circles. Every letter occurrence has exactly one arc endpoint, giving a complete pairing. Transverse orientation over a rose edge gives opposite crossing signs at the two ends of an arc along the oriented boundary of the complement. Switching to coherent disk-boundary orientations reverses both signs. Consequently the paired letters are inverse in those orientations.

It remains to establish the reduction condition (10). The following surgery is the reason for minimizing over boundary length and, for spheres, over all nonzero classes.

Cancelling a band over the same lifted edge

Suppose an arc joins occurrences of the same underlying unoriented edge in $\Gamma$. A sufficiently narrow band around that arc maps into the corresponding open rose edge. It lifts to the specified common open graph edge, because the map of that open edge to the rose is a homeomorphism. The lift agrees with the specified lifts at both attachment intervals. In particular, any incident inner disks and the band together factor through one common abstract cone.

Join the incident disks along the band. If it returns to one disk, the result is an annulus in the sphere. Boundary paths follow the original paths cut at the two occurrences and spliced along the band. They lift to the same graph component, except for the one retained marked break when the exterior is involved.

Both spliced joins contract along the common graph edge. To check this concretely, orient it as $e:u\to v$. The two matched occurrences are $e$ and $e^{-1}$. The local possibilities are:

Incident disks	Old lifted paths	New lifted paths
Two inner disks	$ea,\ e^{-1}b$	$ab$
Exterior and inner	$aec:x\to y,\ e^{-1}b$	$abc:x\to y$
One inner disk twice	$eae^{-1}b$	$a,\ b$
Exterior twice	$aebe^{-1}c:x\to y$	$ac:x\to y$

The symbols denote graph paths with the endpoints forced by the displayed concatenations. For example, in the last row $a:x\to u$, $b:v\to v$, and $c:u\to y$. The other new boundary is $b$, up to orientation. Thus the break-containing path $ac$ has exactly the original distinct endpoints $x,y$.

Geometrically, each band side joins two residual edge fragments that go from one endpoint of $e$ back to that same endpoint through its interior. These fragments contract relative to their endpoints. Taken together, the two contractions remove the two complete edge occurrences and add no letters. Neither contraction passes through the marked break. Total new boundary length is smaller by two before any further tightening.

Here are the resulting modifications of the entire picture.

If the band joins two distinct inner disks, replace their disk-and-band union by one cone disk. The replacement is homotopic relative to its boundary because the entire map there factors through the common contractible cone. Then tighten its boundary.
If the band joins an inner disk to the exterior disk, replace the exterior by their joined disk. Keep the map on its complement and tighten the new outer path relative to the same endpoints.
If both ends meet one inner disk, remove its annulus with the band and cap the boundaries on the two complementary parts using that same cone. For a disk-domain failure, retain the part containing the exterior. For a sphere failure, at least one capped sphere remains essential, as proved below.
If both ends meet the exterior disk, the resulting annulus has the marked break on one boundary component. Retain as the new domain the complementary disk adjacent to that boundary. The last row of the table shows that its outer path has the same graph endpoints.

An inner disk joined to itself by a band forms an annulus. Cutting away the annulus leaves two complementary disks. Capping their new boundaries through the same abstract cone gives two spheres whose homology classes sum to the original class in the universal cover. The labels $a,b$ indicate the shortened boundary paths; the picture is schematic.

For the essentiality assertion in the third case, illustrated in 2, lift the original sphere map to the universal cover $\widetilde X$. The map $K_\Lambda\to X$ has a lift because the cone is simply connected. Choose this lift to agree with the lifted sphere at one point of the annulus. Since the annulus is connected, uniqueness of lifts gives agreement throughout it. Fill both new caps in $K_\Lambda$ and use this same lift.

With compatible orientations, the original spherical class in $H_2(\widetilde X;\mathbb Z)$ is the sum of the two capped classes. The difference between the original class and this sum is represented by the annulus together with the reverse caps, all mapping through the contractible cone, so it is zero in homology. Since $\widetilde X$ is simply connected, the Hurewicz map sending a sphere to its fundamental homology class identifies $\pi_2(\widetilde X)$ with $H_2(\widetilde X;\mathbb Z)$ (Hatcher 2002, Theorem 4.37). A nonzero original class therefore leaves a nonzero capped class. This uses no prior vanishing of $\pi_2(X)$.

In every case the retained surface still witnesses the chosen kind of failure, and its total boundary length has strictly decreased. For the split sphere this follows because the total new length over both parts is already smaller; keeping just one part cannot increase it. Collar homotopies restore combinatorial boundaries after the contractions, and further tightening only decreases length. In the exterior cases, the new graph path has the same fixed distinct endpoints. This contradicts the chosen minimum.

Thus every paired occurrence uses a different underlying graph edge from its partner. The minimized picture is now an arrangement of 6: it has at least one ordinary cyclic boundary, at most one rooted exceptional interval with one break, a full planar inverse-letter pairing, and the reduction condition. 10 excludes it. This proves 11.

A finite-dimensional obstruction to torsion

Corollary 13. The universal cover of $X$ is contractible, and $G$ is torsion-free.

Proof. The simply connected two-dimensional cover $\widetilde X$ has $H_2=0$ by 11 and Hurewicz, has $H_1=0$, and has no cellular homology above dimension two. It is therefore contractible by the homological form of Whitehead’s theorem (Hatcher 2002, Corollary 4.33).

For completeness, the torsion obstruction can be seen directly from resolutions; compare (Brown 1982, VIII, Section 2). The augmented cellular chains of $\widetilde X$ give an exact free $\mathbb ZG$-resolution of $\mathbb Z$ of length two. If $G$ had a nontrivial finite-order element, a power would generate a cyclic subgroup $H=\langle g\rangle$ of prime order $\ell$. Restricting the resolution to $\mathbb ZH$ preserves freeness, since $\mathbb ZG$ is free as a left $\mathbb ZH$-module on coset representatives.

The cyclic group has the exact periodic resolution \[\cdots\longrightarrow\mathbb ZH \xrightarrow{\,N\,}\mathbb ZH \xrightarrow{\,g-1\,}\mathbb ZH \xrightarrow{\,N\,}\mathbb ZH \xrightarrow{\,g-1\,}\mathbb ZH \longrightarrow\mathbb Z\longrightarrow0, \qquad N=1+g+\cdots+g^{\ell-1}.\] Exactness follows by comparing the coefficients of $1,g,\ldots,g^{\ell-1}$: the kernel of $g-1$ consists of the multiples of $N$, and the kernel of $N$ is the augmentation ideal generated by $g-1$. With trivial coefficients $\mathbb F_\ell$, all differentials in the corresponding cochain complex vanish. Hence $H^k(H;\mathbb F_\ell)\cong\mathbb F_\ell$ in every degree. The comparison theorem for projective resolutions makes this cohomology independent of the chosen resolution (Brown 1982, I, Theorem 7.5, p. 24). This contradicts the vanishing above degree two forced by the restricted finite-length free resolution. ◻

The zero divisors

Proof of 1. Use the graphs of 10 and the complex $X$ constructed in 5. It is finite and two-dimensional. By 13, it is a classifying space for the torsion-free group $G=\pi_1(X)$, which is finitely presented.

Let $A'$ be the full vertex set of the component of $x_A$ and $B'$ that of the component of $x_B$. For $x\in A'$, let $g_x\in G$ be the label of a path from $x_A$ to $x$; for $y\in B'$, define $h_y$ using paths from $x_B$. These labels do not depend on the path, because labels of all closed walks in each component are killed by its cone. We multiply in path order.

Set \[\alpha=\sum_{x\in A'}g_x,\qquad \beta=\sum_{y\in B'}h_y^{-1} \quad\text{in }\mathbb F_2[G].\] Both sums are finite. The root contributes the identity to each. By 11, no other vertex contributes identity, so its coefficient is one in each factor. Thus $\alpha\ne0$ and $\beta\ne0$. No assertion about equality between two non-root labels is needed.

On $A'\times B'$, form the graph of simultaneous steps of a common signed label. A step \[x\xrightarrow{t}x',\qquad y\xrightarrow{t}y'\] sends $g_x$ to $g_xt$ and $h_y$ to $h_yt$, and therefore preserves \[g_{x'}h_{y'}^{-1} =(g_xt)(h_yt)^{-1} =g_xh_y^{-1}.\] The reverse step has label $\bar t$. Since full components are used, the degree at $(x,y)$ is the entire number $|S_x\cap S_y|$, which is odd by (3). The girth condition excludes loops for the chosen large $n$; parallel edges would not affect the degree-sum argument.

Every finite connected component of the simultaneous-step graph has an even number of vertices, since the sum of its odd degrees is twice its number of edges. The value $g_xh_y^{-1}$ is constant on that component, so the component contributes zero to the expansion of $\alpha\beta$ over $\mathbb F_2$. Summing over all components gives $\alpha\beta=0$. This proves 1 and disproves the universal zero-divisor assertion. ◻

In particular, $G$ does not have the unique-product property. The construction is probabilistic: it proves that suitable finite matchings exist, without specifying matchings from which a concrete presentation and zero-divisor factors can be read off.

Bereznyuk, Vadim. 2019. “Asphericity of Groups Defined by Graphs.” Mathematical Notes 105: 316–28. https://doi.org/10.1134/S0001434619030027.

Brown, Kenneth S. 1982. Cohomology of Groups. Vol. 87. Graduate Texts in Mathematics. Springer-Verlag. https://doi.org/10.1007/978-1-4684-9327-6.

Fisher, Sam P., and Pablo Sánchez-Peralta. 2026. “Division Rings for Group Algebras of Virtually Compact Special Groups and $3$-Manifold Groups.” Journal of Combinatorial Algebra 10 (1/2): 153–93. https://doi.org/10.4171/JCA/89.

Gardam, Giles. 2021. “A Counterexample to the Unit Conjecture for Group Rings.” Annals of Mathematics, 2nd series, vol. 194 (3): 967–79. https://doi.org/10.4007/annals.2021.194.3.9.

Gardam, Giles. 2024. Non-Trivial Units of Complex Group Rings. arXiv:2312.05240v2.

Garg, Manisha, and Igor Mineyev. 2025. On Zero-Divisors and Units in Group Rings of Torsion-Free CAT(0) Groups. arXiv:2501.07646v2. https://arxiv.org/html/2501.07646v2.

Gromov, M. 2003. “Random Walk in Random Groups.” Geometric and Functional Analysis 13 (1): 73–146. https://doi.org/10.1007/s000390300002.

Gruber, Dominik. 2015. “Groups with Graphical $C(6)$ and $C(7)$ Small Cancellation Presentations.” Transactions of the American Mathematical Society 367 (3): 2051–78. https://doi.org/10.1090/S0002-9947-2014-06198-9.

Hatcher, Allen. 2002. Algebraic Topology. Cambridge University Press. https://pi.math.cornell.edu/~hatcher/AT/AT.pdf.

Higman, Graham. 1940a. “The Units of Group-Rings.” Proceedings of the London Mathematical Society, 2nd series, vol. 46: 231–48. https://doi.org/10.1112/plms/s2-46.1.231.

Higman, Graham. 1940b. “Units in Group Rings.” D.Phil. thesis, University of Oxford.

Kaplansky, Irving. 1957. “Problems in the Theory of Rings.” In Report of a Conference on Linear Algebras, June 6–8, 1956. National Academy of Sciences–National Research Council Publication 502. National Research Council.

Kropholler, P. H., P. A. Linnell, and J. A. Moody. 1988. “Applications of a New $K$-Theoretic Theorem to Soluble Group Rings.” Proceedings of the American Mathematical Society 104 (3): 675–84. https://doi.org/10.2307/2046771.

Lipton, Richard J., and Robert Endre Tarjan. 1979. “A Separator Theorem for Planar Graphs.” SIAM Journal on Applied Mathematics 36 (2): 177–89. https://doi.org/10.1137/0136016.

Mian, Ibrahim, and Shayaan Siddique. 2026. A Machine-Checked Proof That Gardam’s $\widetilde A_2$ Lattice Does Not Have Unique Products. arXiv:2609.22380v1.

Mineyev, Igor. 2024. The Topology and Geometry of Units and Zero-Divisors: Origami. Author preprint. https://mineyev.web.illinois.edu/art/top-geom-uzd-origami.pdf.

Ollivier, Yann. 2005. A January 2005 Invitation to Random Groups. Vol. 10. Ensaios Matemáticos. Sociedade Brasileira de Matemática.

Ollivier, Yann. 2006. “On a Small Cancellation Theorem of Gromov.” Bulletin of the Belgian Mathematical Society – Simon Stevin 13 (1): 75–89. https://doi.org/10.36045/bbms/1148059334.

Rips, E., and Y. S. Segev. 1987. “Torsion-Free Group Without Unique Product Property.” Journal of Algebra 108 (1): 116–26. https://doi.org/10.1016/0021-8693(87)90125-6.

Sandling, Robert. 1981. “Graham Higman’s Thesis ‘Units in Group Rings’.” In Integral Representations and Applications (Oberwolfach, 1980), vol. 882. Lecture Notes in Mathematics. Springer.

Shin, Henry. 2026. A Global Girth Obstruction for Garg–Mineyev Taiko Product Structures. arXiv:2607.01716v1.

Steenbock, Markus. 2015. “Rips–Segev Torsion-Free Groups Without the Unique Product Property.” Journal of Algebra 438: 337–78. https://doi.org/10.1016/j.jalgebra.2015.05.004.

LEVEL 1 COMPLETE!

You read 12,309 words and 799 formulas. Your math teacher would be proud.
Converted from the LaTeX source. Something look off? The original PDF is the real thing.

Back to game page

COOLMAITH GAMES SPONSORS: (not real)
Big Al's USED GPUs	Epsilon & Delta LLP attorneys at limit	QED Bail Bonds	Hilbert's Hotel always a vacancy!

Cool Links: openai/math Lean Mathlib arXiv the real Coolmath Games

You are visitor number 000719

Thanks for visiting CoolmAIth Games
© 1997-2026 CoolmAIth Games. A parody. Not affiliated with Coolmath.com LLC or OpenAI.
Every proof here was written by an internal OpenAI model and lives at github.com/openai/math.
Best viewed in Netscape Navigator 4.0 at 800x600