betaFeedback

WorksMathematics

A Torsion-Free Group Algebra with Zero Divisors

Abstract

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

Introduction

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

Theorem 1.1. There exist a finitely presented torsion-free group GG and nonzero elements α,β∈F2[G]\alpha,\beta\in\mathbb{F}_2[G] such that αβ=0\alpha\beta= 0. Moreover, GG admits a finite two-dimensional classifying space.

The question goes back to Higman’s 1940 thesis [10]; its conjectural formulation is reproduced by Sandling [20], p. 112. It was also posed in Kaplansky’s 1956 conference contribution, published in 1957 [12], Problem 6; see the historical discussion in [4]. Finite-order elements give elementary zero divisors: if gg has order m>1m > 1, then (1−g)(1+g+⋯+gm−1)=0(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 Z\mathbb{Z} [11], Section 4, Theorems 12–13. Kropholler, Linnell, and Moody established it for torsion-free elementary amenable groups, even with division-ring coefficients [13], 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 [3], 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,QP,Q, some element of PQPQ has exactly one expression pqpq with p∈Pp \in P, q∈Qq \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 [19]; Steenbock supplied a graphical small-cancellation treatment of their construction [22]. Mian and Siddique report a machine-checked non-unique-product witness for Gardam’s A~2\widetilde{A}_2 lattice, taking torsion-freeness from Gardam rather than formalizing it [15], Sections 1 and 7. Failure of unique product alone does not produce a zero divisor: over F2\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 GG and a field KK, every unit of K[G]K[G] is a nonzero scalar multiple of a group element. Gardam disproved it over F2\mathbb{F}_2 [4] and subsequently over C\mathbb{C} [5]; 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 F2\mathbb{F}_2 [16], Theorem 27. Garg and Mineyev study these criteria through finite-support combinatorics and computation [6], 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 [21], 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 ΓA,ΓB\Gamma_A,\Gamma_B immersed into one rose FF, 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 xA,xBx_A,x_B, and let A′,B′A',B' be the full vertex sets of their connected components. Attach an abstract cone on each graph component along its labelled map to FF, obtaining a complex XX, and put G=π1(X)G=\pi_1(X). Coning kills the labels of all closed graph paths. Thus a path from xAx_A to x∈A′x\in A' has a well-defined label gx∈Gg_x\in G, independent of the chosen path; define hyh_y from xBx_B to y∈B′y\in B' in the same way. The proposed factors are

α=∑x∈A′gx,β=∑y∈B′hy−1in F2[G].(1.1)\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.1)}

Let SxS_x and SyS_y be the outgoing signed-label sets. We prescribe them so that ∣Sx∩Sy∣\lvert S_x\cap S_y\rvert is odd for every pair. Form a graph on A′×B′A'\times B' by simultaneous steps of a common label tt. Along each step the product is unchanged, since

(gxt)(hyt)−1=gxhy−1.(1.2)(g_xt)(h_yt)^{-1}=g_xh_y^{-1}. \tag*{(1.2)}

Every vertex of this finite graph has odd degree ∣Sx∩Sy∣\lvert S_x\cap S_y\rvert. 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 XX 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 [14] 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 [7]; Ollivier and Gruber develop precise graphical criteria for graph embeddings and asphericity [18, 8]. Distinguishing genuinely different graph lifts from coincident lifts is central to these arguments and to Bereznyuk’s spherical-diagram approach [1]. 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 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 TT has a fixed-point-free involution t↦tˉt \mapsto\bar{t}, with tˉ\bar{t} denoting the inverse letter. The rose FF has one vertex and one unoriented edge for each inverse pair. A labelled graph maps immersively to FF 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.

Sections 2 and 3 construct the random graphs and rule out bounded patterns. Section 4 extracts such a pattern from every reduced spherical arrangement. Section 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. Section 6 uses the resulting asphericity and root separation to complete the factor construction and prove Theorem 1.1. All logarithms are natural. Constants in asymptotic estimates are independent of the sampling size nn; 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 Section 3, exclude the path configurations that could defeat the geometric safeguards.

The finite geometry

Fix

q=128,v=q2+q+1=16513,p=q+1v.q = 128,\qquad v = q^2 + q + 1 = 16513,\qquad p = \frac{q+1}{v}.

The projective plane over Fq\mathbb{F}_q has vv points and vv lines. Each line has q+1q+1 points, each point lies on q+1q+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 Fq3\mathbb{F}_q^3.

Let TT consist of its vv 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 TT, since v−3v-3 is even. In particular, ∣T∣=16516|T|=16516, and the corresponding rose has 8258 edges.

Take disjoint vertex sets A,BA,B, each of size nn. For each vertex xx, prescribe a set Sx⊂TS_x\subset T of outgoing labels as follows:

  1. On either side the ordinary part of SxS_x is a line, with every line represented equally often.

  1. Within each line class on AA, the extra part is each of the three two-element subsets with proportion p/2p/2 apiece, and is otherwise empty.

  1. Within each line class on BB, the extra part is all three extras with proportion pp, and is otherwise empty.

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

Every letter has frequency pp on each side. Two ordinary line parts meet in either 1 or q+1=129q+1=129 points. An extra part on AA meets an extra part on BB in either 0 or 2 letters. Thus

∣Sx∩Sy∣ is odd for every x∈A, y∈B.(2.1)|S_x\cap S_y| \text{ is odd for every } x\in A,\ y\in B. \tag*{(2.1)}

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 xA∈Ax_A\in A and xB∈Bx_B\in B in advance. For Y=A,BY=A,B, write

Yt={x∈Y:t∈Sx},∣Yt∣=np.Y_t=\{x\in Y:t\in S_x\},\qquad|Y_t|=np.

For each inverse pair, choose a bijection Yt→YtˉY_t\to Y_{\bar{t}}, using its inverse for the opposite direction. A matched pair gives an edge labelled tt in one direction and tˉ\bar{t} in the other. Do this independently for all inverse pairs and both sides before any conditioning. The resulting graphs are denoted

ΓA,ΓB,Γ=ΓA⊔ΓB.\Gamma_A,\quad\Gamma_B,\quad\Gamma=\Gamma_A\sqcup\Gamma_B.

They immerse into FF, since every outgoing letter occurs once at each vertex that carries it. Their degrees lie between q+1q+1 and d∗=q+4=132d_* = 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,ut,u, let w(t,u)w(t,u) be the frequency of uu among the vertices of BB that contain tˉ\bar{t}. Put w(t,tˉ)=0w(t,\bar{t})=0. The corresponding conditional frequency on AA is at most w(t,u)w(t,u). Indeed, for distinct tˉ,u\bar{t},u, the weights on BB are

(tˉ,u)(\bar{t},u)ordinary, ordinaryordinary, extraextra, extra
w(t,u)w(t,u)1/(q+1)1/(q+1)pp11

Table 1.

The mixed entry is symmetric; the extra-extra frequency on AA is 1/21/2. In particular, every positive weight lies in [1/129,1][1/129,1].

For a word W=t1⋯thW=t_1\cdots t_h, define

P(W)=∏i=1h−1w(ti,ti+1).(2.2)P(W)=\prod_{i=1}^{h-1}w(t_i,t_{i+1}). \tag*{(2.2)}

Write W−1=t‾h⋯t‾1W^{-1}=\overline{t}_h\cdots\overline{t}_1. Equal letter marginals and symmetry of joint incidence give

w(t,u)=w(u‾,t‾),P(W)=P(W−1).(2.3)w(t,u)=w(\overline{u},\overline{t}),\qquad P(W)=P(W^{-1}). \tag*{(2.3)}

For non-cancelling turns this follows by dividing the joint frequency of t‾,u\overline{t},u by pp; for cancelling turns both weights in the first equality are zero.

Lemma 2.1. There is a constant δ>0\delta>0 such that, for every sufficiently large hh,

∑W∈ThP(W)2≤e−2δh.(2.4)\sum_{W\in T^h}P(W)^2\le e^{-2\delta h}. \tag*{(2.4)}

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

If t‾\overline{t} is ordinary, the ordinary successors different from t‾\overline{t} contribute (v−1)/(q+1)2=q/(q+1)(v-1)/(q+1)^2=q/(q+1) before the weights ff are inserted. At most three such successors have their weight increased by four. The extra successors all have weight one. Hence

(Mf)(t)≤qq+1+3p2+12(q+1)2=500731261911504183783481<149150.(Mf)(t)\le\frac{q}{q+1}+3p^2+\frac{12}{(q+1)^2} =\frac{500731261911}{504183783481}<\frac{149}{150}.

If t‾\overline{t} is extra, the other two extras contribute two; the ordinary successors contribute at most vp2+12p2vp^2+12p^2. Thus

(Mf)(t)f(t)≤2+vp2+12p25=8203508631363395845<149150.\frac{(Mf)(t)}{f(t)}\le\frac{2+vp^2+12p^2}{5} =\frac{820350863}{1363395845}<\frac{149}{150}.

Consequently Mf≤(149/150)fMf\le(149/150)f. Since 1≤f1\le f and ∑tf(t)=16528<e10\sum_t f(t)=16528<e^{10},

∑W∈ThP(W)2=1TMh−11≤16528(149/150)h−1≤e−h/300(h≥3002).\sum_{W\in T^h}P(W)^2=\mathbf{1}^{\mathsf T}M^{h-1}\mathbf{1} \le16528(149/150)^{h-1}\le e^{-h/300}\qquad(h\ge3002).

For example, δ=1/600\delta=1/600 is admissible.

Girth conditioning and switching

Fix a sufficiently small positive constant cc, and put

L=⌊clog⁡n⌋.L=\lfloor c\log n\rfloor.

It is enough that

clog⁡(2∣T∣/p)<1,2clog⁡d∗<1;(2.5)c\log(2|T|/p)<1,\qquad2c\log d_*<1; \tag*{(2.5)}

one may take c=1/100c=1/100. We work with the uniform tuple of matchings conditioned on girth⁡(Γ)≥L\operatorname{girth}(\Gamma)\ge L. The next lemma both justifies this conditioning and gives a bound within the conditioned space.

Lemma 2.2. For all sufficiently large admissible nn, there is a tuple of matchings with girth⁡(Γ)≥L\operatorname{girth}(\Gamma)\ge L. In the uniform distribution on such tuples, condition further on any feasible set of ss prescribed matching pairs. The probability of an additional specified pair, not already prescribed in either direction, is at most

1np−s−rn,rn=O(d∗2L+2)=o(n),(2.6)\frac{1}{np-s-r_n},\qquad r_n=O(d_*^{2L+2})=o(n), \tag*{(2.6)}

whenever the denominator is positive. The error rnr_n can be chosen uniformly over all prescriptions.

Proof. Before girth conditioning, a feasible simple cycle of length k<Lk < L has at most 2nk∣T∣k2n^k|T|^k vertex-and-letter descriptions. Its distinct edges require kk distinct matching prescriptions, with probability at most (np−k)−k(np-k)^{-k}. Thus the expected number of edges lying on cycles shorter than LL is at most

2∑k<Lk nk∣T∣k(np−k)−k≤2∑k<Lk(2∣T∣/p)k=o(n)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 nn, by (2.5). Choose a tuple with o(n)o(n) such bad edges.

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

Transpose the two matches, replacing xy,uzxy,uz by xz,uyxz,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)(x,u),(y,z) or (x,y),(u,z)(x,y),(u,z). The first case again joins the distant sets. In the second, the uu-to-zz path together with uzuz is an old short cycle, contradicting the choice of uzuz. This includes x=yx=y, when the xx-to-yy 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 LL.

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

Given an output and the pair xyxy to restore, the inverse operation is unique: the current match of xx is zz, and the current preimage of yy is uu. Thus the map from a tuple containing xyxy, together with an admissible transposition, to its output tuple is injective. If Ωs\Omega_s is the conditioned set and Ωs,xy\Omega_{s,xy} is its subset containing xyxy, then

∣Ωs,xy∣(np−s−rn)≤∣Ωs∣.|\Omega_{s,xy}|(np-s-r_n)\leq|\Omega_s|.

This proves (2.6).

In particular, any feasible collection of E=O(L)E=O(L) distinct edge prescriptions has conditional probability at most

(np)−Eexp⁡(o(L)).(2.7)(np)^{-E}\exp(o(L)). \tag*{(2.7)}

This follows by applying Lemma 2.2 successively. Uniformity of its error is important; no independence after conditioning is asserted.

Lemma 2.3. With conditional probability tending to one, every connected component of Γ\Gamma has diameter at most D0LD_0L, for a fixed constant D0D_0.

Proof. Fix a small positive ρ\rho. On either side, require every vertex set of size 1≤k≤ρn1\leq k\leq\rho n to grow to at least 2k2k vertices on adjoining all its neighbors. A failure supplies a set of 2k2k vertices containing at least

r=⌈(q+1)k/2⌉r=\lceil(q+1)k/2\rceil

distinct edges: all edges incident to the failing kk-set lie in the larger set and are counted at most twice by its degree sum. There are at most (C1n/k)2k(C_1n/k)^{2k} choices for the larger set. Its possible typed edge prescriptions number O(k2)O(k^2); choosing an unordered rr-subset costs at most (C1k)r(C_1k)^r. Decrease ρ\rho so that r≤np/3r \le np/3 throughout the range. For sufficiently large nn, Lemma 2.2 then bounds the probability of all rr prescriptions by (2/(np))r(2/(np))^r. Hence the probability of a failure of size kk, on either side, is at most a fixed multiple of

(C1n/k)2k(C1k)r(2/(np))r≤(C2(k/n)62.5)k,(C_1n/k)^{2k}(C_1k)^r(2/(np))^r \le(C_2(k/n)^{62.5})^k,

because 64.5≤r/k≤6564.5 \le r/k \le65. Choose ρ\rho still smaller so that C2ρ62.5<1/2C_2\rho^{62.5}<1/2. Summing over k≤nk \le\sqrt{n} gives o(1)o(1); the sum over larger k≤ρnk \le\rho n is at most n2−nn2^{-\sqrt{n}}.

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

A bounded-pattern estimate

All probabilities in this section refer to the distribution conditioned on girth(Γ\Gamma) ≥L\ge L. We retain the predetermined vertices xAx_A and xBx_B. The possible rooted interval will accommodate a null-homotopy of a root-to-vertex path in Section 5.

Consider finitely many positive-length paths in Γ\Gamma, all cyclically immersed and closed except possibly one immersed interval path whose initial vertex is xAx_A or xBx_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

paired occurrences traverse distinct underlying undirected edges of Γ.(3.1)\text{paired occurrences traverse distinct underlying undirected edges of }\Gamma. \tag*{(3.1)}

Positions outside the paired intervals are called unpaired.

Proposition 3.1 (Bounded-pattern estimate). There is a constant ε>0\varepsilon>0, depending only on the fixed types and turn weights, with the following property. For every fixed positive integer KK, fixed real C≥1C\ge1, and fixed nonnegative integer II, the conditional probability tends to zero that there exists a system as above having at most KK paths, total length HH with

L≤H≤CL,L \le H \le CL,

at most II interval pairs, and bb unpaired occurrences, where b≤εHb\le\varepsilon H. In particular, ε\varepsilon is chosen before KK, CC, II, and these three bounds are held fixed as nn 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,IK,C,I. Constants implicit in this proof may depend on these bounds, whereas the final choice of ε\varepsilon will not. Every o(L)o(L) or o(s)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 (2.3), 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 CLCL edges and girth at least LL. 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 CC, since each uses at least LL 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 CLCL. Suppose it has r>0r>0 edges. Start a non-backtracking walk uniformly on its 2r2r 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 zz has deg⁡(z)−1\operatorname{deg}(z)-1 allowed predecessors, each contributing 1/[2r(deg⁡(z)−1)]1/[2r(\operatorname{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 kk edges is therefore at most kCL/rkCL/r. At least half of the probability lies on walks of expanded length at most 2kCL/r2kCL/r. Each particular walk has probability at most (2r)−12−(k−1)(2r)^{-1}2^{-(k-1)}, so there are at least r2k−1r2^{k-1} such short walks. Choose k=O(log⁡(r+1))k=O(\log(r+1)) so that this number exceeds (2r)2(2r)^2. There are at most (2r)2(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/r4kCL/r. Girth at least LL implies r≤4Ckr\le4Ck, bounding rr in terms of CC 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Δc_{\Delta} the number of components, the degree-sum identity gives

∑deg⁡(z)≥3(deg⁡(z)−2)=2β−2cΔ+#{z:deg⁡(z)=1}.\sum_{\operatorname{deg}(z)\ge3}(\operatorname{deg}(z)-2)=2\beta-2c_{\Delta}+\#\{z:\operatorname{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 mem_e for the total number of traversals of an undirected edge ee 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 LL: the intervening segment is a nonempty reduced closed walk and hence contains a cycle. A path of length hh thus traverses any given oriented edge at most h/L+1h/L+1 times. Summing over paths and the two orientations yields

me≤2(H/L+K)≤2(C+K).(3.2)m_e\le2(H/L+K)\le2(C+K). \tag*{(3.2)}

Consequently, the total number of chain traversals is bounded as well.

There are only polynomially many unlabelled patterns in LL. To specify one, give the bounded marked multigraph, the positive integer length of each chain, the side AA or BB 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)O(L) choices and there are boundedly many of them. We retain only patterns satisfying (3.1). Vertex names in AA and BB, 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 [17], motivates the stage organization and selection below. The conditioned matching estimate for the dependent graph paths in this model is developed locally.

For 1≤j≤m∗:=max⁡eme1 \le j \le m_* := \max_e m_e, let Δj\Delta_j consist of all edges with me≥jm_e \ge j, together with their incident vertices. Denote its edge and vertex counts by EjE_j and VjV_j. Let ι\iota be one if the interval path is present and zero otherwise. Then

∑j=1m∗Ej=H,∑j=1m∗Vj=∑z∈Δ(0)max⁡e∋zme≤H+ι.(3.3)\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*{(3.3)}

For the inequality, let a(z)a(z) count interval-path endpoints at zz, 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)a(z) endpoints. Hence

2max⁡e∋zme≤∑half-edges at zme+a(z).2\max_{e \ni z} m_e \le\sum_{\text{half-edges at }z} m_e + a(z).

Summing this inequality proves (3.3), because the half-edge sum is 2H2H and ∑za(z)=2ι\sum_z a(z)=2\iota.

Set k1=ιk_1=\iota, and kj=0k_j=0 for j>1j>1. In stage one the initial vertex of the interval path has its prescribed image, saving one factor of nn. We claim no such saving at later stages. The exponent needed below satisfies

∑j=1m∗(Vj−Ej−kj)≤0.(3.4)\sum_{j=1}^{m_*}(V_j-E_j-k_j)\le0. \tag*{(3.4)}

In the later realization count, the exponent Vj−Ej−kjV_j-E_j-k_j will count vertex-image choices against edge-prescription costs. Equation (3.4) therefore controls the total power of nn 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,ℓ][0,\ell], and put its edge positions at half-integers. Splitting comparisons at chain-traversal boundaries gives boundedly many subcomparisons of the form

x⟼σx+a,σ∈{1,−1},a∈Z.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 σ=1\sigma=1 and inverse equality when σ=−1\sigma=-1.

Pad the list of integer offsets by zeros to a fixed length d≥1d \ge1. Put

N=⌊L1/(2(d+1))⌋,R=⌊N⌋.N=\left\lfloor L^{1/(2(d+1))}\right\rfloor,\qquad R=\left\lfloor\sqrt{N}\right\rfloor.

The simultaneous pigeonhole principle gives an integer 1≤u≤Nd1 \le u \le N^d such that dist⁡(ua/L,Z)≤1/N\operatorname{dist}(ua/L,\mathbb{Z}) \le1/N for every offset aa. For completeness, place the Nd+1N^d+1 vectors of fractional parts of k(a1/L,…,ad/L)k(a_1/L,\ldots,a_d/L), for 0≤k≤Nd0 \le k \le N^d, in the NdN^d cubes of side 1/N1/N. Subtracting two vectors in the same cube gives the required uu. Choose the least such uu, so all choices are determined by the unlabelled pattern, and set s=L/(uR)s=L/(uR). Uniformly in that pattern,

LNd+1/2≤s≤LR,max⁡adist⁡(a/s,Z)≤RN.(3.5)\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*{(3.5)}

In particular, ss tends to infinity at least as a fixed positive power of LL, while s/Ls/L and all the distances in (3.5) tend to zero.

On each chain use the full grid intervals [ks,(k+1)s)[ks,(k+1)s) contained in [0,ℓ][0,\ell], for integers k≥0k\ge0. The half-integer edge positions in such an interval form a full block. Index these blocks over all of Δ\Delta by ii. Their lengths and multiplicities satisfy

hi=s+O(1),mi=meon their chains.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)O(s+1) positions. Every traversal of the same chain uses this same subdivision, also when read backwards.

Here is the alignment consequence of (3.5), including reflections. Write a=νs+ra=\nu s+r, with ν∈Z\nu\in\mathbb{Z} and ∣r∣=o(s)|r|=o(s). A translation sends the kk-th real grid interval to the (k+ν)(k+\nu)-th interval shifted by rr. A reflection sends it to

((ν−k−1)s+r,(ν−k)s+r].((\nu-k-1)s+r,(\nu-k)s+r].

Because aa 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)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.

Figure 1. Approximate alignment under a translation, shown schematically with 0<r=o(s)0 < r = o(s). A source block is translated by a=νs+ra = \nu s + r; its image overlaps the indicated target block in real length s−rs - r. Restricting to half-integer edge positions loses at most a bounded number of positions, giving s−o(s)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−κ)s(1-\kappa)s, where κ=o(1)\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∗b_* be the number of unmatched full-block occurrences. Only boundedly many blocks lie within 3s+O(1)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)O(L/s) block occurrences in total, so rounding their lengths and charging the exceptional blocks gives

sb∗≤b+O(s+L/s)=b+o(L).(3.6)sb_* \le b+O(s+L/s)=b+o(L). \tag*{(3.6)}

Links between underlying blocks. Forget occurrence indices in this matching, obtaining a multigraph whose vertices are the full blocks ii. 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 U\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)o(s) letters. Indeed, the recorded comparison specifies s−o(s)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 U\mathcal{U} is at most

exp⁡(o(s)∣U∣).(3.7)\exp(o(s)|\mathcal{U}|). \tag*{(3.7)}

Additional links and immersion constraints can only reduce this number.

If U\mathcal{U} has a self-link, choose a self-linked block as the root. Its word has only exp⁡(o(s))\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)(x∈D),W(x) = W(x+t) \qquad(x \in D),

where DD and D+tD+t are contiguous subsets of the same block and ∣D∣=s−o(s)|D| = s - o(s). The integral shift tt is nonzero by (3.1); a zero shift would compare the same underlying edge with itself. On the hih_i positions of the block, the ∣D∣|D| distinct constraint edges form a forest of arithmetic chains with step ∣t∣|t|. Thus this forest has hi−∣D∣=o(s)h_i - |D| = o(s) components, leaving at most ∣T∣hi−∣D∣=exp⁡(o(s))|T|^{h_i-|D|} = \exp(o(s)) root words.

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

For any link component put

SU=∑i∈Umi,zU=max⁡i∈Umi,bU=#{unmatched block occurrences in U}.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 U\mathcal{U} has no self-link, then

2zU≤SU+bU.(3.8)2z_{\mathcal{U}} \le S_{\mathcal{U}}+b_{\mathcal{U}}. \tag*{(3.8)}

Indeed, take a block of multiplicity zUz_{\mathcal{U}}. At least zU−bUz_{\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 SU−zUS_{\mathcal{U}}-z_{\mathcal{U}} such other occurrences. This proves (3.8), also for isolated blocks and in the presence of multiple links.

Binning the word weights. For each full-block word WiW_i, read in its chain orientation, specify the integer

di=⌊−log⁡P(Wi)⌋.d_i=\lfloor-\log P(W_i)\rfloor.

We need only consider positive weights, since feasible block words are immersed. By Lemma 2.1, every such word of length hh has P(W)≤e−δhP(W)\le e^{-\delta h} for all sufficiently large hh. The smallest positive turn weight is a fixed positive number. Hence there is a constant a0>0a_0>0, depending only on the turn weights, such that for all large LL,

δs2≤di≤a0s,#{Wi:⌊−log⁡P(Wi)⌋=di}≤exp⁡(2di−δs).(3.9)\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*{(3.9)}

For the counting assertion, every word in the indicated bin contributes more than e−2di−2e^{-2d_i-2} to the sum of squared weights. The same lemma therefore bounds the number of these words by

exp⁡(2di+2−2δhi)≤exp⁡(2di−δs),\exp(2d_i+2-2\delta h_i)\le\exp(2d_i-\delta s),

using hi=s+O(1)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)O(L/s) blocks and O(s)O(s) possible bin values per block, so the number of choices is at most

exp⁡(O((L/s)log⁡(s+1)))=exp⁡(o(L)).\exp(O((L/s)\log(s+1)))=\exp(o(L)).

Together with the earlier polynomial count, the number of enlarged patterns is exp⁡(o(L))\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 Δj\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 XjX_j count injective realizations of Δj\Delta_j, with these permitted labels and prescribed sides, and with the prescribed initial vertex in stage one if ι=1\iota=1. A realization of the entire path system gives Xj≥1X_j\ge1 at every stage.

For one fixed permitted stage label assignment, its expected number of vertex realizations is at most

nVj−Ej−kjexp⁡(−∑i:mi≥jdi+o(L)).(3.10)n^{V_j-E_j-k_j}\exp\left(-\sum_{i:m_i\ge j}d_i+o(L)\right). \tag*{(3.10)}

Here are the vertex and edge counts giving this bound. A chain is either entirely present or absent at stage jj, because its multiplicity is constant. Let QjQ_j be the number of active chains. There are Ej−QjE_j-Q_j internal chain vertices. If such a vertex has incoming letter tt and outgoing letter uu, then on its prescribed side it has at most np w(t,u)np\,w(t,u) possible images. All other unfixed vertices have at most nn choices. The fixed initial vertex, when imposed, is a marked vertex. Ignoring injectivity gives the upper bound

nVj−kjpEj−Qj∏internal chain turnsw(t,u)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 EjE_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 2.2, the probability of all these prescriptions is at most

(1+o(1)np)Ej,\left(\frac{1+o(1)}{np}\right)^{E_j},

uniformly since Ej=O(L)E_j=O(L). Multiplication leaves the bounded factor p−Qjp^{-Q_j}, the power nVj−Ej−kjn^{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 ∏i:mi≥jP(Wi)≤exp⁡(−∑i:mi≥jdi)\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))\exp(o(L)), proving (3.10).

The number of permitted stage label assignments is at most

exp⁡(o(L)+∑U without a self-linkzU≥j(2min⁡i∈Udi−δs)).(3.11)\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*{(3.11)}

To see this carefully, consider a link component with at least one active block, equivalently zU≥jz_{\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∈Udi\min_{i\in\mathcal{U}}d_i, count its words by (3.9), and extend along a spanning tree by (3.7). 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)o(L), since the total number of blocks is O(L/s)O(L/s). Arbitrary letters in the end fragments contribute at most exp⁡(O(s))\exp(O(s)) per marked chain, again exp⁡(o(L))\exp(o(L)). Ignoring any further constraints between components gives (3.11).

Selecting a stage and summing over patterns. Let BjB_j be the product of the right-hand sides of (3.10) and (3.11). Thus EXj≤Bj\mathbb{E}X_j\le B_j. Multiply these numerical upper bounds over 1≤j≤m∗1\le j\le m_*. The total exponent of nn is nonpositive by (3.4). For a link component without a self-link, put dmin⁡=min⁡i∈Udid_{\min}=\min_{i\in\mathcal{U}}d_i. Its remaining contribution to the logarithm of the product is

FU=−∑i∈Umidi+2zUdmin⁡−δszU.F_{\mathcal{U}}=-\sum_{i\in\mathcal{U}}m_i d_i+2z_{\mathcal{U}}d_{\min}-\delta s z_{\mathcal{U}}.

If 2zU≤SU2z_{\mathcal{U}}\le S_{\mathcal{U}}, then (3.9) gives

FU≤−(SU−2zU)δs2−δszU=−δ2sSU.F_{\mathcal{U}}\le-(S_{\mathcal{U}}-2z_{\mathcal{U}})\frac{\delta s}{2}-\delta s z_{\mathcal{U}}=-\frac{\delta}{2}s S_{\mathcal{U}}.

If 2zU>SU2z_{\mathcal{U}}>S_{\mathcal{U}}, use (3.8), the upper bin bound, and zU>SU/2z_{\mathcal{U}}>S_{\mathcal{U}}/2 to obtain

FU≤(2zU−SU)a0s−δszU≤a0sbU−δ2sSU.F_{\mathcal{U}}\le(2z_{\mathcal{U}}-S_{\mathcal{U}})a_0s-\delta sz_{\mathcal{U}}\le a_0sb_{\mathcal{U}}-\frac{\delta}{2}sS_{\mathcal{U}}.

For a self-linked component the negative cost −∑imidi-\sum_i m_i d_i alone is at most −δsSU/2-\delta sS_{\mathcal{U}}/2.

Bounded multiplicities and boundedly many chains imply

∑UsSU=H+O(L/s+s)=H+o(L),s∑UbU≤b+o(L),\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 (3.6). There are only boundedly many stages by (3.2), so all their error terms remain o(L)o(L). We have proved

log⁡∏j=1m∗Bj≤−δ2H+a0b+o(L).(3.12)\log\prod_{j=1}^{m_*}B_j\le-\frac{\delta}{2}H+a_0b+o(L). \tag*{(3.12)}

Choose, once and for all,

ε=min⁡{14,δ16(1+a0)}>0.\varepsilon=\min\left\{\frac{1}{4},\frac{\delta}{16(1+a_0)}\right\}>0.

This depends only on the fixed turn weights. For b≤εHb\le\varepsilon H and all sufficiently large LL, uniformly over the fixed pattern bounds, (3.12) gives

∏j=1m∗Bj≤e−δH/4.\prod_{j=1}^{m_*}B_j\le e^{-\delta H/4}.

Put M=max⁡{1,⌈2(C+K)⌉}M=\max\{1,\lceil2(C+K)\rceil\}, so m∗≤Mm_*\le M. Some stage therefore has Bj≤e−δH/(4M)B_j\le e^{-\delta H/(4M)}. Since a realization of the entire enlarged pattern requires Xj≥1X_j\ge1 at every stage, Markov’s inequality gives

Pr⁡(this enlarged pattern is realized)≤min⁡jEXj≤min⁡jBj≤e−δH/(4M).\Pr(\text{this enlarged pattern is realized})\le\min_j\mathbb{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))\exp(o(L)) enlarged patterns and H≥LH\ge L. The union bound is at most exp⁡(o(L)−δL/(4M))\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 (3.1) 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 LL.

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

  1. 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 xAx_A or xBx_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.

  1. 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.

  1. Paired occurrences have inverse signed letters in these boundary orientations, and their underlying undirected edges of Γ\Gamma are distinct, as required by (3.1).

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 dd such that the event

diam⁡(Λ)≤dLfor every connected component Λ of Γ\operatorname{diam}(\Lambda) \le dL \quad\text{for every connected component } \Lambda\text{ of } \Gamma

(diameter event) has probability 1−o(1)1-o(1), as supplied by Lemma 2.3. We first work on this event.

Lemma 4.2 (Closing a segment without cancellation). There is a fixed integer DD, independent of nn and of the segment, such that every positive-length immersed segment in Γ\Gamma extends to a cyclically immersed closed path by appending at most DLDL 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 zz, delete at most two specified incident undirected edges from its side of Γ\Gamma. For sufficiently large nn, girth at least L≥3L \ge3 excludes graph loops and parallel edges; after the deletion every vertex still has degree at least (q+1)−2≥3(q+1)-2 \ge3. Put

k=⌈log⁡2n⌉+1.k=\lceil\log_2 n\rceil+1.

From zz in the remaining graph there are at least 3⋅2k−1>n3\cdot2^{k-1}>n non-backtracking walks of length kk. That graph has at most nn vertices, so two distinct such walks P,QP,Q end at the same vertex. Reduce PQ−1PQ^{-1} as a linear edge path. This removes just their common terminal segment. Since PP and QQ have equal length and are distinct, neither walk is entirely removed. The result is a nonempty reduced based loop of length at most 2k2k, whose first and last edges avoid both deleted edges. The loop need not be cyclically immersed at zz; only its linear reduction will be used.

Let SS be the given segment, running from aa to bb, and let RR be a geodesic from bb to aa, of length at most dLdL. If RR is nonempty, choose a based loop JbJ_b at bb by excluding the last edge of SS and the first edge of RR. Choose JaJ_a at aa by excluding the last edge of RR and the first edge of SS. Then

SJbRJaSJ_bRJ_a

has no backtracking at any join, including its cyclic last/first join. If RR is empty, so that a=ba=b, use just one based loop JaJ_a, excluding the last and first edges of SS; the path SJaSJ_a is cyclically immersed. The immersion Γ→F\Gamma\to F also makes every one of these joins reduced in signed letters.

For large nn we have L≥(c/2)log⁡nL \ge(c/2)\log n and L≥1L \ge1, whence

k≤(2clog⁡2+2)L.k \le\left(\frac{2}{c\log2}+2\right)L.

Thus any integer

D≥d+8clog⁡2+8D \ge d+\frac{8}{c\log2}+8

bounds the added length ∣R∣+4k|R|+4k in units of LL, and covers the empty-return case as well. □\square

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 4.3 (A linear bound on comparison intervals). Suppose an arrangement with NN disk boundaries is divided into N′≥NN' \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′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 RR of their planar multigraph. Let EE 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 QQ, let lQl_Q be the number of band sides in its boundary. Equivalently, lQl_Q counts the intervening vertex gaps, with incidences counted separately. Every vertex has positive degree, so every boundary component of RR meets a band side, and lQ≥1l_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,fe,f and their partners are e′,f′e',f', the opposite corner has coherent order f′,e′f',e'. Thus (e,f)↔(f′,e′)(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 χ(R)=N−E\chi(R)=N-E. Gluing the complementary surfaces to it along boundary circles gives

∑Qχ(Q)=2−N+E,∑QlQ=2E.\sum_Q \chi(Q)=2-N+E,\qquad\sum_Q l_Q=2E.

Consequently

∑Q(lQ−2χ(Q))=2N−4.(4.1)\sum_Q\left(l_Q-2\chi(Q)\right)=2N-4. \tag*{(4.1)}

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≤1M \le1 monogons, contributing −M-M to (4.1).

  • 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 NN such faces, and hence at most 2N2N 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 lQ−2χ(Q)l_Q-2\chi(Q). For a disk region of length lQ≥3l_Q \ge3, we instead have lQ≤3(lQ−2)l_Q \le3(l_Q-2).

All contributions except those of monogons and digons are positive. Their total is 2N−4+M2N - 4 + M, by (4.1). If BgapB_{\mathrm{gap}} is the number of non-good gaps, these observations give

Bgap≤M+2N+3(2N−4+M)≤8N.(4.2)B_{\mathrm{gap}} \le M + 2N + 3(2N - 4 + M) \le8N. \tag*{(4.2)}

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′N + N' additional marked gaps: a split cyclic boundary into mm pieces needs at most mm 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 JJ satisfying

J≤Bgap+2(N+N′)≤12N′.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 JJ runs, since each original boundary is a circle with a nonempty cut set. They pair in distinct twos, giving at most J/2≤6N′J/2 \le6N' interval pairs. Inverse letters and reversed order are exactly the signed comparison convention of Proposition 3.1.

Separating a planar graph into bounded components

Lemma 4.4 (Recursive planar separation). Put

Csep=221−2/3.C_{\mathrm{sep}} = \frac{2\sqrt{2}}{1-\sqrt{2/3}}.

For every integer K≥1K \ge1, a planar multigraph with mm vertices has a set of at most Csepm/KC_{\mathrm{sep}}m/\sqrt{K} vertices whose deletion leaves components of size at most KK.

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 [14], Corollary 2, p. 183 supplies, in any simple planar graph with ss vertices, at most 22s2\sqrt{2s} vertices whose deletion leaves components with at most 2s/32s/3 vertices. Apply this theorem recursively to each component with more than KK vertices.

For a recursive call on s>Ks > K vertices, charge 22/s2\sqrt{2}/\sqrt{s} to each of those vertices. The total charge at this call is 22s2\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/32/3. Reading the list backwards from its last size greater than KK, its total charge is at most

22K∑j≥0(2/3)j/2=CsepK.\frac{2\sqrt{2}}{\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 KK incur no charge.

Extracting a forbidden bounded pattern

Proposition 4.5 (Absence of reduced spherical arrangements). With probability 1−o(1)1-o(1), Γ\Gamma admits no reduced spherical arrangement. In particular, for all sufficiently large admissible nn there exist graphs of the prescribed types, with girth at least LL and the diameter bound of Lemma 2.3, admitting no such arrangement.

Proof. Let ε>0\varepsilon>0 be supplied by Proposition 3.1; it is independent of the fixed pattern bounds. Fix dd for the diameter event and then the integer DD from Lemma 4.2. Splitting at length about ULUL will make each closure cost of at most DLDL a small proportion of the original length. We choose UU to control that cost, η\eta to control the original positions discarded by planar separation, and C2C_2 as a cutoff for the number of comparison intervals relative to path length. Choose, in the indicated order,

U≥max⁡{3,⌈96D/ε⌉},U an integer,η=min⁡{132U,ε64U},K=max⁡{1,⌈(Csep/η)2⌉},a=6,C2=32a,C=K(U+D),I=⌈C2C⌉.(4.3)\begin{aligned} U &\ge\max\{3,\lceil96D/\varepsilon\rceil\}, && U\text{ an integer},\\ \eta&= \min\left\{\frac{1}{32U},\frac{\varepsilon}{64U}\right\}, && K=\max\left\{1,\left\lceil(C_{\mathrm{sep}}/\eta)^2\right\rceil\right\},\\ a&=6, && C_2=32a,\\ C&=K(U+D), && I=\lceil C_2C\rceil. \tag*{(4.3)} \end{aligned}

Here CsepC_{\mathrm{sep}} is the constant in Lemma 4.4. These choices imply

3DU≤ε32,2ηU≤116,2ηU≤ε32.(4.4)\frac{3D}{U}\le\frac{\varepsilon}{32},\qquad2\eta U\le\frac{1}{16},\qquad2\eta U\le\frac{\varepsilon}{32}. \tag*{(4.4)}

For reference, the dependency order is

types, c, δ ;ε, d ;D ;U ;η ;K ;C,I ;n.(4.5)\text{types},\,c,\,\delta\ ;\quad\varepsilon,\,d\ ;\quad D\ ;\quad U\ ;\quad\eta\ ;\quad K\ ;\quad C,I\ ;\quad n. \tag*{(4.5)}

All constants preceding nn are fixed before nn tends to infinity through multiples of 2v22v^2, with L=⌊clog⁡n⌋L=\lfloor c\log n\rfloor. In particular, the bounded-pattern estimate is applied to one fixed triple (K,C,I)(K,C,I), not to bounds growing with nn.

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

Splitting and closing long paths. Keep every path of length at most ULUL intact. A longer path of length hh is split into m=⌈h/(UL)⌉m=\lceil h/(UL)\rceil consecutive integer-length segments whose lengths differ by at most one. For large LL, these lengths lie between UL/3UL/3 and ULUL: indeed h/m>UL/2h/m>UL/2, and ⌊h/m⌋≥UL/3\lfloor h/m\rfloor\ge UL/3 once UL≥6UL\ge6, while ⌈h/m⌉≤UL\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 4.2, and leave every added occurrence unpaired.

Denote the number of resulting paths by N′N'. Each has length at most (U+D)L(U+D)L and contains at most ULUL original occurrences. Since m≤3h/(UL)m\le3h/(UL), the total added length HaddH_{\mathrm{add}} satisfies

Hadd≤3DUH0.(4.6)H_{\mathrm{add}}\le\frac{3D}{U}H_0. \tag*{(4.6)}

Every resulting path has at least LL 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≥LUL/3\ge L. It follows that

N≤N′,N′L≤H0+L≤2H0.(4.7)N\le N',\qquad N'L\le H_0+L\le2H_0. \tag*{(4.7)}

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 4.3 to the original positions in these pieces. It represents their pairing by at most aN′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′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 4.4 and the choice of KK, delete at most ηN′\eta N' vertices so that each remaining component, called a cluster, has at most KK pieces. The number MM of deleted original positions is at most

M≤ηN′UL≤2ηUH0.(4.8)M \le\eta N'UL \le2\eta UH_0. \tag*{(4.8)}

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 MM. 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 ZZ, let HZH_Z be its total path length including closures, bZb_Z the number of its unpaired positions, and IZI_Z its number of retained interval pairs. Equations (4.6), (4.7), and (4.8) give

∑ZHZ≥(1−2ηU)H0,∑ZbZ≤(2ηU+3D/U)H0,∑ZIZ≤aN′≤2aH0/L.(4.9)\begin{aligned} \sum_Z H_Z &\ge(1-2\eta U)H_0,\\ \sum_Z b_Z &\le(2\eta U+3D/U)H_0,\\ \sum_Z I_Z &\le aN' \le2aH_0/L. \tag*{(4.9)} \end{aligned}

Also every cluster satisfies HZ≤K(U+D)L=CLH_Z \le K(U+D)L=CL.

A positive amount of admissible length survives. The retained total length is at least 15H0/1615H_0/16 by Equation (4.4). Clusters with bZ>εHZb_Z>\varepsilon H_Z have total length at most

1ε∑ZbZ≤H016.\frac{1}{\varepsilon}\sum_Z b_Z \le\frac{H_0}{16}.

Clusters with IZ>C2HZ/LI_Z>C_2H_Z/L likewise have total length at most

LC2∑ZIZ≤2aC2H0=H016.\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 13H0/1613H_0/16 of cluster length remains.

A cluster of length less than LL 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<Lh<L, the original arrangement also contained an ordinary cyclic path of length at least LL, so H0≥h+L>2hH_0 \ge h + L > 2h. Removing that cluster therefore costs less than H0/2H_0/2. The clusters left after all three exclusions have total length at least

(1516−116−116−12)H0=516H0>0.\left(\frac{15}{16}-\frac{1}{16}-\frac{1}{16}-\frac{1}{2}\right)H_0=\frac{5}{16}H_0>0.

Choose one such cluster. It contains at most KK positive-length paths, has

L≤HZ≤CL,bZ≤εHZ,IZ≤C2HZ/L≤C2C≤I,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 (3.1). All paths are cyclically immersed except possibly the entire short exceptional interval, whose initial vertex is still xAx_A or xBx_B. Added closures may traverse old edges repeatedly; all their occurrences are unpaired, as permitted by Proposition 3.1. The cluster is therefore one of the bounded patterns excluded by Proposition 3.1.

The constants in (4.3) were chosen using the single ε\varepsilon independent of K,C,IK,C,I. The probability of such a bounded pattern is o(1)o(1), and the probability of failure of the diameter event is o(1)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 Proposition 4.5. Attach to the rose FF, for each connected component Λ\Lambda of Γ\Gamma, its abstract cone KΛK_\Lambda along the labelled map Λ→F\Lambda\to F. Denote the resulting finite two-dimensional CW complex by XX, and put G=π1(X)G=\pi_1(X), based at the rose vertex. In particular, labels of all closed walks in Γ\Gamma are trivial in GG.

Proposition 5.1. The complex XX satisfies π2(X)=0\pi_2(X)=0. Moreover, if a path in Γ\Gamma starts at xAx_A or xBx_B and ends at a different vertex, its label is nontrivial in GG.

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 [8, 1]. Their hypotheses are not imported here: we give the cone-picture reduction needed for Proposition 4.5 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ΛK_\Lambda, and the complement of the disk interiors maps to FF. 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 5.2. Every essential sphere map to XX 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 π1(Λ)\pi_1(\Lambda). Temporarily replace KΛK_\Lambda by the space YΛY_\Lambda obtained by attaching one disk to Λ\Lambda along each basis loop. The space YΛY_\Lambda is simply connected. The classes of its attaching loops form a basis of H1(Λ;Z)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 [9 Theorem 4.32 and Corollary 4.33].

Both YΛY_{\Lambda} and KΛ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 FF. This works even though Λ→F\Lambda\to F is not injective. We obtain an ordinary rose-with-relator-disks model homotopy equivalent to XX relative to FF.

That finite model can be triangulated. Take collars inside the relator disks, view their attachments to FF 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 FF.

After composition, the complement of the preimage disks maps to FF, and each preimage disk reads an attaching loop, with one of its two orientations. Return to XX 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 Proposition 5.1 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 xAx_A or xBx_B, and allow the interval path between them to vary. By Lemma 5.2, 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 π1(F)\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 XX 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 FF, 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 (3.1). 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→ve:u\to v. The two matched occurrences are ee and e−1e^{-1}. The local possibilities are:

Incident disksOld lifted pathsNew lifted paths
Two inner diskseaea, e−1be^{-1}babab
Exterior and inneraec:x→yaec:x\to y, e−1be^{-1}babc:x→yabc:x\to y
One inner disk twiceeae−1beae^{-1}baa, bb
Exterior twiceaebe−1c:x→yaebe^{-1}c:x\to yac:x→yac:x\to y

Table 2 (PDF p. 22).

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

Geometrically, each band side joins two residual edge fragments that go from one endpoint of ee 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.

  1. 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.

  1. 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.

  1. 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.

  1. 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.

For the essentiality assertion in the third case, illustrated in Figure 2, lift the original sphere map to the universal cover X~\widetilde{X}. The map KΛ→XK_{\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ΛK_{\Lambda} and use this same lift.

An inner disk joined to itself by a band forms an annulus, which is removed and capped to produce two spheres

Figure 2. 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 aa, bb indicate the shortened boundary paths; the picture is schematic.

With compatible orientations, the original spherical class in H2(X~;Z)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 X~\widetilde{X} is simply connected, the Hurewicz map sending a sphere to its fundamental homology class identifies π2(X~)\pi_{2}(\widetilde{X}) with H2(X~;Z)H_{2}(\widetilde{X};\mathbb{Z}) [9 Theorem 4.37]. A nonzero original class therefore leaves a nonzero capped class. This uses no prior vanishing of π2(X)\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 Definition 4.1: 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. Proposition 4.5 excludes it. This proves Proposition 5.1.

A finite-dimensional obstruction to torsion

Corollary 5.3. The universal cover of XX is contractible, and GG is torsion-free.

Proof. The simply connected two-dimensional cover X~\widetilde{X} has H2=0H_{2}=0 by Proposition 5.1 and Hurewicz, has H1=0H_{1}=0, and has no cellular homology above dimension two. It is therefore contractible by the homological form of Whitehead’s theorem [9 Corollary 4.33].

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

The cyclic group has the exact periodic resolution

⋯⟶ZH→NZH→g−1ZH→NZH→g−1ZH⟶Z⟶0,N=1+g+⋯+gℓ−1.\cdots\longrightarrow\mathbb{Z}H \xrightarrow{N} \mathbb{Z}H \xrightarrow{g-1} \mathbb{Z}H \xrightarrow{N} \mathbb{Z}H \xrightarrow{g-1} \mathbb{Z}H \longrightarrow\mathbb{Z} \longrightarrow0,\qquad N=1+g+\cdots+g^{\ell-1}.

Exactness follows by comparing the coefficients of 1,g,…,gℓ−11,g,\ldots,g^{\ell-1}: the kernel of g−1g-1 consists of the multiples of NN, and the kernel of NN is the augmentation ideal generated by g−1g-1. With trivial coefficients Fℓ\mathbb{F}_{\ell}, all differentials in the corresponding cochain complex vanish. Hence Hk(H;Fℓ)≅Fℓ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 [2 Chapter I, Theorem 7.5, p. 24]. This contradicts the vanishing above degree two forced by the restricted finite-length free resolution. □\square

The zero divisors

Proof of Theorem 1.1. Use the graphs of Proposition 4.5 and the complex XX constructed in Section 5. It is finite and two-dimensional. By Corollary 5.3, it is a classifying space for the torsion-free group G=π1(X)G=\pi_1(X), which is finitely presented.

Let A′A' be the full vertex set of the component of xAx_A and B′B' that of the component of xBx_B. For x∈A′x\in A', let gx∈Gg_x\in G be the label of a path from xAx_A to xx; for y∈B′y\in B', define hyh_y using paths from xBx_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.

α=∑x∈A′gx,β=∑y∈B′hy−1in F2[G].\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 Proposition 5.1, no other vertex contributes identity, so its coefficient is one in each factor. Thus α≠0\alpha\ne0 and β≠0\beta\ne0. No assertion about equality between two non-root labels is needed.

On A′×B′A'\times B', form the graph of simultaneous steps of a common signed label. A step

x→tx′,y→ty′x\xrightarrow{t}x',\qquad y\xrightarrow{t}y'

sends gxg_x to gxtg_xt and hyh_y to hyth_yt, and therefore preserves

gx′hy′−1=(gxt)(hyt)−1=gxhy−1.g_{x'}h_{y'}^{-1}=(g_xt)(h_yt)^{-1}=g_xh_y^{-1}.

The reverse step has label tˉ\bar{t}. Since full components are used, the degree at (x,y)(x,y) is the entire number ∣Sx∩Sy∣|S_x\cap S_y|, which is odd by (2.1). The girth condition excludes loops for the chosen large nn; 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 gxhy−1g_xh_y^{-1} is constant on that component, so the component contributes zero to the expansion of αβ\alpha\beta over F2\mathbb{F}_2. Summing over all components gives αβ=0\alpha\beta=0. This proves Theorem 1.1 and disproves the universal zero-divisor assertion. □\square

In particular, GG 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.

References

  1. [1]Vadim Bereznyuk. Asphericity of groups defined by graphs. Mathematical Notes, 105:316–328, 2019. Author version: https://arxiv.org/pdf/1711.05293v2.
  2. [2]Kenneth S. Brown. Cohomology of Groups, volume 87 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1982. https://doi.org/10.1007/978-1-4684-9327-6.
  3. [3]Sam P. Fisher and Pablo Sánchez-Peralta. Division rings for group algebras of virtually compact special groups and 3-manifold groups. Journal of Combinatorial Algebra, 10(1/2):153–193, 2026. https://doi.org/10.4171/JCA/89.
  4. [4]Giles Gardam. A counterexample to the unit conjecture for group rings. Annals of Mathematics, 194(3):967–979, 2021. https://doi.org/10.4007/annals.2021.194.3.9.
  5. [5]Giles Gardam. Non-trivial units of complex group rings. arXiv:2312.05240v2, 2024. Version 2, 29 October 2024. https://arxiv.org/abs/2312.05240v2.
  6. [6]Manisha Garg and Igor Mineyev. On zero-divisors and units in group rings of torsion-free CAT(0) groups. arXiv:2501.07646v2, September 2025. Version 2, 8 September 2025. https://arxiv.org/abs/2501.07646v2.
  7. [7]M. Gromov. Random walk in random groups. Geometric and Functional Analysis, 13(1):73–146, 2003. https://doi.org/10.1007/s000390300002.
  8. [8]Dominik Gruber. Groups with graphical C(6) and C(7) small cancellation presentations. Transactions of the American Mathematical Society, 367(3):2051–2078, 2015. Author version: https://arxiv.org/pdf/1210.0178v2.
  9. [9]Allen Hatcher. Algebraic Topology. Cambridge University Press, Cambridge, 2002. https://pi.math.cornell.edu/~hatcher/AT/AT.pdf.
  10. [10]Graham Higman. Units in group rings. D.phil. thesis, University of Oxford, 1940.
  11. [11]Graham Higman. The units of group-rings. Proceedings of the London Mathematical Society, 46:231–248, 1940. https://doi.org/10.1112/plms/s2-46.1.231.
  12. [12]Irving Kaplansky. Problems in the theory of rings. In Report of a Conference on Linear Algebras, June 6–8, 1956, number 502 in National Academy of Sciences–National Research Council Publication, pages 1–3. National Research Council, Washington, DC, 1957.
  13. [13]P. H. Kropholler, P. A. Linnell, and J. A. Moody. Applications of a new K-theoretic theorem to soluble group rings. Proceedings of the American Mathematical Society, 104(3):675–684, 1988. https://doi.org/10.2307/2046771.
  14. [14]Richard J. Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177–189, 1979. https://doi.org/10.1137/0136016.
  15. [15]Ibrahim Mian and Shayaan Siddique. A machine-checked proof that Gardam’s Ã₂ lattice does not have unique products. arXiv:2609.22380v1, 2026. Version 1, 17 September 2026. https://arxiv.org/abs/2609.22380v1.
  16. [16]Igor Mineyev. The topology and geometry of units and zero-divisors: Origami. Author preprint, 2024. Dated 1 April 2024; revised 12 August 2026. https://mineyev.web.illinois.edu/art/top-geom-uzd-origami.pdf.
  17. [17]Yann Ollivier. A January 2005 invitation to random groups, volume 10 of Ensaios Matemáticos. Sociedade Brasileira de Matemática, Rio de Janeiro, 2005.DOI
  18. [18]Yann Ollivier. On a small cancellation theorem of Gromov. Bulletin of the Belgian Mathematical Society – Simon Stevin, 13(1):75–89, 2006. Corrected author version, 25 September 2024: https://arxiv.org/pdf/math/0310022v2.
  19. [19]E. Rips and Y. S. Segev. Torsion-free group without unique product property. Journal of Algebra, 108(1):116–126, 1987. https://doi.org/10.1016/0021-8693(87)90125-6.
  20. [20]Robert Sandling. Graham Higman’s thesis “units in group rings”. In Integral Representations and Applications (Oberwolfach, 1980), volume 882 of Lecture Notes in Mathematics, pages 93–116. Springer, 1981.DOI
  21. [21]Henry Shin. A global girth obstruction for Garg–Mineyev taiko product structures. arXiv:2607.01716v1, 2026. Version 1, 2 July 2026. https://arxiv.org/abs/2607.01716v1.
  22. [22]Markus Steenbock. Rips–Segev torsion-free groups without the unique product property. Journal of Algebra, 438:337–378, 2015. https://doi.org/10.1016/j.jalgebra.2015.05.004.

Paper details

vlnc:W_8hv99232
Version
v1 · latest
Published
License
LicenseRef-OpenAI-public
Usage

views · 67

downloads · 4

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

unreleased internal OpenAI model

View statement
Looking for related papers…
Contents