A Torsion-Free Group Algebra That Is Not Directly Finite

1 Introduction

A unital ring R is directly finite if ab=1 implies ba=1 for all a,b\in R. For a field K and a group G, the group algebra K[G] consists of finite formal sums of elements of G with coefficients in K, with multiplication extending the group operation bilinearly. Kaplansky’s direct finiteness conjecture asserts that every such group algebra is directly finite. We prove that the implication can fail even when the field is finite and the group is finitely presented and torsion-free. A classifying complex for G is a connected CW complex with fundamental group G and contractible universal cover.

The auxiliary element c certifies failure of the reverse identity: if ba=1, then c=(ba)c=b(ac)=0.

History and related work

Kaplansky’s formulation separates the characteristic-zero theorem from the positive-characteristic question [Kap72, Part II, Section 3, Problem 2, pp. 122–123]. In characteristic zero, group algebras are directly finite for every group. The operator-algebra argument also applies to matrix rings; Montgomery gave a concise C^*-algebra proof [Mon69]. A ring whose matrix rings of every finite size are directly finite is called stably finite.

In arbitrary characteristic, Ara, O’Meara, and Perera proved stable finiteness for group algebras of free-by-amenable groups over division rings [AOP02]. Elek and Szabó extended the conclusion to sofic groups [ES04, Corollary 4.7], a class defined by finite approximate permutation actions. Their theorem implies that the group in Theorem 1.1 is not sofic. A complementary approach studies the finite cancellation patterns forced by a one-sided inverse. Dykema, Heister, and Juschenko organized these patterns into universal groups and established direct finiteness for several small support pairs over \Ftwo [DHJ15].

Two companion manuscripts are especially relevant. A separate construction gives a scalar counterexample over a finite field of characteristic two for a finitely presented group with odd-order torsion [Ope26a, Theorem 1.1]. Theorem 1.1 uses the prime field \Ftwo and a torsion-free group. Its method develops the graph and cone construction of A Torsion-Free Group Algebra with Zero Divisors [Ope26b]. That manuscript supplies the parity mechanism for a zero product and the arrangement-exclusion strategy. We adapt those arguments to produce a one-sided inverse and reproduce the estimates and topology needed here.

Graphical presentations relate coincidences of labeled paths to geometric properties of quotient groups, as in Gromov’s random graphical constructions [Gro03] and Ollivier’s small-cancellation theorem [Oll06]. Bereznyuk’s spherical-diagram criterion for graphical asphericity distinguishes coincident graph lifts from genuinely different ones [Ber19]. The same distinction is essential here: pairings of two occurrences of the same graph edge are removed by cone surgeries. We prove the required asphericity and root protection directly in Section 6.

The construction and its main estimates

The group is obtained from a bouquet of circles by attaching cones on finite labeled graphs. A cone kills every closed path in its graph, so a vertex in a chosen component determines a group element by reading a path from a fixed root to that vertex. The desired algebra elements are finite sums of these path labels and their inverses.

Two graphs are used. A common outgoing label allows a simultaneous step in both coordinates of their vertex products. The group element contributed to the corresponding algebra product is constant along such a step. If every vertex of a simultaneous-step component has odd degree, the component has even cardinality and its contributions cancel over \Ftwo. A single even-degree exception instead leaves one surviving contribution. We prescribe the outgoing label sets so that the first graph paired with itself has exactly this exception, while the first graph paired with the second has none.

The change to the parity construction in [Ope26b] is to produce product 1 as well as product 0. Seven additional labels, organized by complements of lines in the Fano plane, create the required exception while keeping every inverse-label incidence count balanced. This changes the random model, and we establish its counting estimates directly.

The main difficulty is to make the cone attachments aspherical while ensuring that a path from a root to a different graph vertex has nontrivial image in the group. Both conclusions follow by excluding certain planar pairings of graph paths. The argument has two parts. First, a weighted estimate rules out bounded collections of paths with a small proportion of unpaired positions. Repeated traversal of a graph edge is the main counting obstacle: two compared path words need not impose two sets of random edge conditions. We organize the count by the number of times each edge is used, and choose subdivisions that nearly agree under all the comparisons. This makes the decay of word weights available despite repeated traversals. The permitted unpaired proportion is fixed before the bounds on the number and length of paths. Second, a planar separator extracts one of these bounded collections from any spherical arrangement, however large. The order of these parameter choices is what allows a local counting estimate to exclude all arrangements.

We give the graph criterion and the parity calculation in Section 2. Section 3 constructs the vertex types and proves the word, girth, and diameter estimates. Section 4 proves the bounded-path estimate, and Section 5 carries out the planar extraction. Section 6 proves the topological criterion by cone surgeries. Section 7 then assembles these conclusions.

2 Labeled graphs and the parity criterion

The algebraic part of the construction is a parity calculation on finite graphs. We first isolate this calculation from the geometric work needed to ensure that the resulting group is torsion-free and that a specified coefficient does not vanish. The use of immersed graphs and their cones follows the construction in [Ope26b, Proposition 5.1 and Section 6].

A signed alphabet is a finite set T with a fixed-point-free involution t\mapsto\bar t. Let F be the rose with one vertex * and one geometric edge for each pair \{t,\bar t\}; its two orientations carry the labels t and \bar t. A T-labeled graph \Gamma has a label on every oriented edge, with opposite orientations carrying inverse labels. It therefore has a label map \Gamma\to F taking each edge homeomorphically onto the appropriate edge of the rose. The map is an immersion if the labels on the edges leaving any one vertex are distinct. Write S_x\subseteq T for these outgoing labels. For t\in S_x, denote by x\cdot t the endpoint of the unique edge leaving x with label t.

The length of an edge path is its number of edge traversals, counted with multiplicity. A path is immersed if it has no consecutive edge and reverse edge. A closed path is cyclically immersed if this also holds at the closing turn. For a graph immersed in F, these conditions say precisely that the label word is freely reduced, or cyclically reduced, respectively. We multiply labels in the order in which a path traverses its edges.

Let \Gamma_A and \Gamma_B be finite graphs immersed in F, with vertex sets A and B, and choose roots x_A\in A and x_B\in B. Put \Gamma=\Gamma_A\sqcup\Gamma_B. For each connected component \Lambda of \Gamma, let K_\Lambda be its abstract cone, and form

Here the base of each cone is attached by its label map. In particular, the cone need not embed in X. This is a finite CW complex of dimension at most two. Every closed path in \Gamma has trivial label in G, because it bounds in its cone.

Let A'\subseteq A and B'\subseteq B be the vertex sets of the components containing the respective roots. For x\in A', let g_x be the label in G of any path from x_A to x; define h_y for y\in B' in the same way. These elements are independent of the chosen paths: the concatenation of one such path with the reverse of another is a closed path in the same component. Thus

whenever the indicated step exists, where a letter also denotes its image in G.

Only protection of x_B is needed for the last coefficient calculation. We retain the symmetric condition (2.4) because the geometric argument will establish it for both roots. The remaining task is to construct finite immersed graphs satisfying (2.3) whose cone complex is aspherical and whose roots satisfy (2.4).

3 Types and random matchings

We construct the outgoing label sets first, so that every choice of edges has the parity properties needed for the algebraic argument. We then choose the edges by random matchings. The estimates in this section show that we may condition on logarithmic girth while retaining useful bounds for prescribed edges, and that the resulting components have logarithmic diameter. The construction and the use of conditioned matchings adapt the method of [Ope26b, Section “Prescribed types and random matchings”]; the label counts and estimates below are for the types used here.

3.1 Prescribing the outgoing labels

Fix

Let \mathcal P and \mathcal L be the points and lines of the projective plane over \mathbb F_q. Concretely, these are the one-dimensional and two-dimensional subspaces of \mathbb F_q^3, with incidence given by containment. Counting nonzero vectors gives v points, and duality gives v lines. Every line contains q+1 points, and every point lies on q+1 lines. Two distinct points span a unique line, and two distinct lines intersect in exactly one point.

Adjoin a set \mathcal E of seven extra letters to \mathcal P, and put T=\mathcal P\sqcup\mathcal E. Pair each extra letter with a distinct ordinary letter. Since v-7 is even, the remaining ordinary letters can be paired among themselves. These pairs define the fixed-point-free involution t\mapsto\bar t on T. As before, F is the rose with one edge for each inverse pair.

Identify \mathcal E with the seven points of the projective plane over \mathbb F_2, and let \mathcal D consist of the complements of its seven lines. Each D\in\mathcal D has four elements, and distinct members of \mathcal D intersect in two elements. Each extra letter belongs to four members of \mathcal D: three Fano lines contain the letter and four do not. Each pair of distinct extra letters belongs to two members of \mathcal D, since the number of Fano lines containing at least one of them is 3+3-1=5.

Let m tend to infinity through positive integers congruent to 1 modulo 4, and set n=vm. All asymptotic statements below use this sequence. Partition sets A and B into classes indexed by \mathcal L, with m vertices in each class of A and m-1 vertices in each class of B. Thus

The ordinary part of the outgoing label set S_x at a vertex x is its indexing line. Choose a distinguished vertex x_A\in A and give it all seven extra letters. For every D\in\mathcal D, prescribe extra part exactly D at

These are integers because q+1\equiv m\equiv1\pmod4. Every remaining vertex has empty extra part.

For each D, distribute its prescribed vertices among the v line classes with counts differing by at most one. These distributions can be realized simultaneously on disjoint vertices. Indeed, in each line class the total demand in A, including x_A if applicable, is at most 7\lceil a_m/v\rceil+1, and in B it is at most 7\lceil b_m/v\rceil. Both bounds are

whose coefficient of m is strictly less than one. For all sufficiently large m, each bound is smaller than m-1. Fix one such assignment of the sets S_x, and also fix any root x_B\in B, before choosing edges.

For Y\in\{A,B\}, write Y_t=\{x\in Y:t\in S_x\}. For each inverse pair, choose a bijection Y_t\to Y_{\bar t}. A matched pair (x,y) gives one undirected edge, oriented from x to y with label t and in the reverse direction with label \bar t. Overlap between Y_t and Y_{\bar t} is allowed, so loops may occur at this stage. More precisely, a match joins the label slots (x,t) and (y,\bar t); these remain distinct when x=y. Denote the resulting graphs by \Gamma_A and \Gamma_B, and put \Gamma=\Gamma_A\sqcup\Gamma_B. Every outgoing label at a vertex occurs exactly once, so the maps to F are immersions. Degrees count half-edges, including both half-edges of a loop, and are bounded by

3.2 Turn frequencies and decay of word weights

At an interior vertex of a path with consecutive labels t,u, the outgoing labels used by the path are \bar t,u. For a reduced turn, meaning u\ne\bar t, define

For either Y=A or Y=B, uniformly over reduced turns,

Here and below constants in O(1) do not depend on m. To verify the formula, two distinct ordinary letters occur together on just one line, giving m or m-1 choices. An extra letter occurs in each line class 4a_m/v+O(1)=pm+O(1) times in A, including the possible distinguished vertex in the error, and 4b_m/v+O(1)=p(m-1)+O(1) times in B. Summing over the q+1 lines containing a specified ordinary letter gives np^2+O(1). Finally, two distinct extra letters occur together 2a_m+1=np/2+1/2 times in A and 2b_m=(n-v)p/2 times in B. These are precisely the three cases of (3.6).

For a word W=t_1\cdots t_h of positive length, put

with the empty product equal to one. This weight is positive exactly when the word is reduced. Since the rule in (3.5) is symmetric in \bar t,u, it also gives

Thus reversing the orientation of a path does not change its weight. The square of this weight has summable total mass in long word lengths, as the next estimate shows.

3.3 Conditioning on large girth

Initially choose all the bijections independently and uniformly, and write \mathbb P for this probability law. Fix c_0>0 so small that

Girth is the length of a shortest simple cycle; loops and pairs of parallel edges count as cycles of lengths one and two. Let \mathcal G_L be the event that \Gamma has girth at least L. We first prove that this event is nonempty for all sufficiently large n, so that the conditioned law

is defined.

A match prescription specifies one matched pair in one of the bijections, on a specified side A or B. The reverse orientation describes the same prescription. A collection is feasible if some tuple of bijections satisfies it. Every bijection on side Y has N_Y=|Y|p pairs. Before conditioning, a feasible collection of distinct prescriptions has probability \prod (N_Y)_{e}^{-1}, where the product runs over the bijections, e is their respective number of prescriptions, and (N)_e=N(N-1)\cdots(N-e+1).

There are at most 2n^k|T|^k choices of vertices and labels that can describe a cycle of length k. A feasible simple cycle uses k distinct prescriptions, even for k=1 or k=2, and therefore has probability at most (np-vp-k)^{-k}. If an edge is called bad when it lies on a cycle of length less than L, the expected number of bad edges is consequently at most

Here np-vp-k\ge np/2 for large n, uniformly for k<L, and the last assertion follows from (3.9).

We use the following elementary switch. Suppose that xy and uz are edges on the same side, both oriented with the same label t. Assume that uz is not bad and that the distance between \{x,y\} and \{u,z\} exceeds 2L. Distances between different components are understood to be infinite. Transpose the two targets in the bijection, replacing xy,uz by xz,uy. This preserves every outgoing label set and creates no cycle of length less than L.

For the last assertion, any new short cycle must contain a new edge. If it contains just one, deleting that edge gives an old path of length less than L between the two distant endpoint sets, a contradiction. If it contains both, deleting the new edges gives two old paths. Either one of these crosses between the endpoint sets, again contradicting their distance, or the paths join x to y and u to z. In the latter case the old u-to-z path together with uz is a cycle of length less than L, contrary to the choice of uz. This argument also applies when x=y; the corresponding residual path can have length zero.

Choose an initial tuple with o(n) bad edges, as supplied by (3.10). Given a bad edge xy, the number of edges having an endpoint within distance 2L of x or y is O(d_*^{2L+2})=o(n), by (3.9). The appropriate bijection contains at least np-vp edges, so it has an edge uz which is neither bad nor excluded by this distance condition. The switch removes the bad edge xy and creates no new bad edges. Repeating decreases the number of bad edges strictly at each step and eventually gives a tuple in \mathcal G_L. Since every tuple has positive probability, \mathbb P(\mathcal G_L)>0.

The purpose of switching is also quantitative. It permits an upper bound for an additional prescribed edge without any lower bound for \mathbb P(\mathcal G_L).

3.4 Expansion and component diameter

We now use (3.11) for collections with a small linear number of edges. The high minimum degree forces small vertex sets to expand, even under girth conditioning.

4 A bounded path estimate

We now use the word estimate of Lemma 3.2 to rule out short systems of paths with extensive label comparisons. An edge of the image graph may occur many times in these paths. The proof keeps track of this repetition by counting subgraphs at successive multiplicity levels. Comparisons then recover the square of the word weight needed for Lemma 3.2. We develop the multiplicity and block argument of [Ope26b, Section “A bounded-pattern estimate”] for the types constructed here.

A position of a path means an edge traversal, so different positions may traverse the same edge of \Gamma. A comparison consists of two disjoint intervals of positions of equal length, together with one of the following requirements: their words agree in the given orders, or their words are t_1\cdots t_h and \bar t_h\cdots\bar t_1. The comparisons in a system use disjoint positions. We allow cyclic intervals on a closed path. Throughout this section comparisons must also satisfy

Write H for the sum of the path lengths and b_0 for the number of positions not used in a comparison.

Fix K_0,C,I for the proof. All constants described below as bounded may depend on these parameters and on the fixed alphabet. All o(L) estimates are uniform over the systems and patterns satisfying these bounds. We always work under the conditional law \mathbb P_L. Index each closed path by choosing a starting vertex. If a comparison crosses one of these indexing points, split both intervals of that comparison at the corresponding position. The number of resulting comparisons is still bounded in terms of I and K_0, and their union of paired positions has not changed.

4.1 The image graph and its multiplicity levels

Let \Delta\subseteq\Gamma be the image of a putative system. It has at most CL edges and girth at least L. We first show that it has bounded topological complexity. Here the cycle rank of a finite graph is |E|-|V|+ the number of connected components.

Mark every vertex of \Delta whose degree differs from two, and also every initial and terminal vertex of our indexed paths. There are no isolated vertices. A leaf can occur only as an endpoint of the possible interval path, because every other path turn is immersed. There are therefore at most two leaves. To see explicitly that the remaining marks are bounded, write \beta for the cycle rank and c for the number of components. The degree sum gives

Lemma 4.2 bounds both the number and the total degree of vertices of degree at least three. There are at most 2K_0 additional path-endpoint marks. Each component contains a path start. Consequently \Delta is the union of a bounded number of chains, that is, paths between marked vertices with disjoint, unmarked degree-two interiors. A chain may have the same marked vertex at both ends. Choose an orientation on every chain.

Every path traverses whole chains. Let m_e be the total number of traversals of the undirected edge e by the entire path system. This multiplicity is constant on the edges of each chain. Two successive uses of the same oriented edge by a single indexed path have starting positions separated by at least L: the intervening path from the initial vertex of that edge back to itself is a nonempty reduced closed walk and contains a cycle. For a path of length h, each orientation can therefore occur at most h/L+1 times. Summing over paths and the two orientations yields

An unlabelled pattern records the finite marked chain graph, its positive chain lengths, the side A or B of each component, the indexed paths as sequences of oriented chain traversals, and the endpoints and directions of the comparisons. It records whether there is an interval path and, if so, which root is its initial vertex. Only patterns having the structure just proved and satisfying (4.1) are retained. The underlying graph in a pattern is an image graph: a realization must map its vertices and edges injectively into the appropriate sides of \Gamma.

There are boundedly many chain traversals by (4.2). All lengths and comparison endpoints are integers between 0 and CL. Hence the number of unlabelled patterns is polynomial in L. This includes the finitely many choices of chain graph, traversal sequences, sides, and interval designation.

For a pattern, let m_*:=\max_e m_e\leq M. Its stage j graph \Delta_j consists of all edges with m_e\geq j and their endpoints, for 1\leq j\leq m_*. Write V_j and E_j for its numbers of vertices and edges. Let \iota be 1 if there is an interval path and 0 otherwise, and put

We will fix the prescribed root only when counting stage one. This loss of a factor n pays precisely for the two possible unpaired path endpoints in the following incidence estimate.

4.2 One grid for all comparisons

The role of (4.3) is visible in the embedding count. For fixed labels, choosing V_j vertices, prescribing E_j distinct edges, and fixing k_j roots leave a factor n^{V_j-E_j-k_j}. Apart from factors subexponential in L, the turn frequencies also supply one word weight for each chain. Thus (4.3) permits us to combine the stage estimates without a positive net power of n. It remains to sum over labels compatible with the comparisons; the precise embedding count appears in (4.11) below.

For orientation, suppose two edge-disjoint chain segments are required to carry the same word W. Their turn-weight contribution is P(W)^2, although only one word is free to vary. The same holds for inverse words because P(W^{-1})=P(W). Lemma 3.2 then supplies exponential decay. In the actual system, the comparison endpoints need not line up, and chains can be traversed repeatedly. We now subdivide the chains into long words whose boundaries nearly agree across comparisons; the multiplicity stages will account for the repeated traversals.

Fix an unlabelled pattern. Give each oriented chain coordinates from 0 to its length, putting edge positions at half-integers. Split a comparison whenever either of its path intervals crosses a chain end. The bounded number of chain traversals gives a bounded number of resulting subcomparisons. In chain coordinates each is a restriction of

If \sigma=1, the labels in chain orientation agree; if \sigma=-1, they are inverse. This follows by incorporating into the comparison the orientation of each of its two chain traversals.

We need blocks whose grids agree approximately under every map in (4.4). Choose a fixed integer d_1\geq1 bounding the number of offsets, padding their list with zeros when necessary. Put

Partition [0,1)^{d_1} into N^{d_1} boxes of side 1/N. Among the N^{d_1}+1 vectors with coordinates \{\ell a/L\}, 0\leq\ell\leq N^{d_1}, two lie in the same box. Subtracting their indices gives 1\leq u\leq N^{d_1} such that

Choose one such u deterministically from the pattern and set

Uniformly over patterns,

In particular, s\to\infty, s=o(L), and all the distances in the last display tend to zero. The lower bound even gives s\geq L^{(d_1+3/2)/(2(d_1+1))} for large L, so all estimates involving L/s are uniform.

On each chain take the edge positions lying in grid intervals [ks,(k+1)s) contained in its coordinate interval. These sets are the full blocks. The final fragment has fewer than s+1 positions. Index underlying full blocks by i, and write h_i for their lengths and m_i for their chain multiplicities. Thus h_i=s+O(1) and 1\leq m_i\leq M. Every traversal of a chain uses the same subdivision; a block i therefore has m_i separate occurrences in the path system.

Choose \kappa=\kappa_L>0 tending to zero, large enough to dominate the grid displacement R/N and the rounding error 10/s. For each subcomparison, match two full-block occurrences if it compares contiguous portions of these occurrences of length at least (1-\kappa)s. Record the entire substring constraint on that overlap. For large L this gives a partial matching of occurrences. Indeed, the matched portion occupies more than half of each block. Two different proposed matches incident to the same occurrence would therefore overlap, contrary to the disjointness of all compared positions. The match is recorded only once, irrespective of which of its two occurrences is considered first.

We next bound the full-block occurrences left unmatched. Exclude the boundedly many block occurrences within distance 3s+O(1) of a subcomparison endpoint or a chain end, measuring distance along the corresponding traversal. A remaining block occurrence either has every position unpaired, or lies wholly inside one subcomparison. In the latter case its grid interval maps under (4.4) to an interval displaced by at most (R/N)s from a grid interval on the partner chain. Reflection may exchange open and closed endpoints, changing the number of half-integer positions by at most two. The partner interval is full, because the source block is also far from the corresponding subcomparison ends. The two blocks consequently overlap in at least (1-\kappa)s compared positions, and are matched.

Let b_* be the number of unmatched full-block occurrences. There are O(L/s) occurrences altogether. Each unmatched occurrence outside the bounded exceptional collection contributes at least s-1 unpaired positions. It follows that

The constants here count subcomparison ends and chain traversals, not individual edges.

Now forget the occurrence indices while retaining all matches and their substring constraints. This gives a multigraph on the underlying blocks; call its edges links. A link whose two occurrences belong to the same underlying block is a self-link. Isolated blocks are included as components. For a component \mathcal U, put

In particular, \sum_{\mathcal U}b_{\mathcal U}=b_*. Figure 1 illustrates the nearly aligned grids and the distinction between occurrences and underlying blocks.

4.3 Word bins and stage expectations

The link constraints make the number of free words small. To combine this fact with the probability of embedding a labelled graph, we must also retain each block’s word weight. For its word W_i, in the chosen chain orientation, record the integer

All these words are reduced. Since the fixed collection of positive turn weights has a positive minimum, there is a constant a_0>0 depending only on those weights such that, for large L,

Here and below only positive-weight words are counted. For completeness, Lemma 3.2 implies P(W)^2\leq e^{-2\delta h_i} for each word, so d_i\geq\delta h_i-1\geq\delta s/2 for large s. The minimum turn weight gives the upper bound. Every word in the bin has P(W)>e^{-d_i-1}, and therefore the number in the bin is at most

These estimates are uniform because h_i=s+O(1) and s\to\infty.

Enlarge the pattern by recording all d_i. There are O(L/s) full blocks, each with O(s) possible bins. Thus the logarithm of the number of bin choices is O((L/s)\log(s+2))=o(L). Together with the earlier polynomial count, the total number of enlarged patterns is

The grid, occurrence matching, and link multigraph are determined by the unlabelled pattern, and introduce no further choices.

Fix one enlarged pattern. A full label assignment means labels on all edges of its abstract image graph, read inversely on reverse edges, giving an immersion into F and satisfying the comparisons and bins. This is a condition on strings on the abstract graph; it does not require an embedding in the random graph. At stage j, consider the restrictions of all such full label assignments to \Delta_j. Let Z_j count their injective realizations in \Gamma, with the component sides prescribed by the pattern, and with the root fixed if k_j=1. Every realization of the original enlarged pattern gives Z_j\geq1 at every stage.

For a fixed one of these stage label assignments, the expected number of its realizations is at most

To prove this, let Q_j be the number of active chains, that is, chains whose edges belong to \Delta_j. They have exactly E_j-Q_j unmarked internal vertices. At such a vertex the incoming and outgoing chain labels form a reduced turn t,u, and (3.6) bounds its possible images on its prescribed side by

At each remaining unfixed vertex use the upper bound n; a fixed root is marked and has only one choice. This bounds the number of possible vertex assignments by

Restrict to the assignments that are injective and compatible with all vertex types. Each requires E_j distinct edge prescriptions. Lemma 3.3 bounds their joint probability by (np)^{-E_j}\exp(o(L)). Multiplication leaves n^{V_j-E_j-k_j}p^{-Q_j} times the displayed turn product. The bounded factor p^{-Q_j} is \exp(o(L)). Every turn weight is at most one, so discarding all factors except internal turns of full blocks increases the product. The remaining product is

which proves (4.11). This count uses injective realizations of the image graph; it does not replace distinct edge prescriptions by repeated traversals.

The number of stage label assignments has the bound

Indeed, a link component is represented at stage j exactly when z_{\mathcal U}\geq j. The possible words on its represented blocks are projections of assignments on the entire link component. A projection has cardinality no larger than the set being projected. If the component has no self-link, choose a block attaining the minimum bin, even when that block is absent from stage j. Equation (4.9) gives at most \exp(2\min_i d_i-\delta s) choices on this block, and Lemma 4.4 bounds the extensions by \exp(\rho_Ls|\mathcal U|). If the component has a self-link, the second assertion of that lemma gives this last factor without any initial word choice. Constraints between different words, or at chain junctions, can only reduce these counts.

Summed over components, the propagation error is \rho_Ls\,O(L/s)=o(L). There are only boundedly many chain end fragments, containing O(s) positions in total; assigning their letters freely costs at most |T|^{O(s)}=\exp(o(L)). These observations prove (4.12). Requiring stage labels to extend as strings was essential: it permits the minimum-bin block to be used even at stages where it is absent.

Let B_j be the product of the right sides of (4.11) and (4.12), choosing their uniform error bounds. Then

The second inequality is Markov’s inequality at each individual stage. We will now bound the minimum by multiplying the deterministic numbers B_j.

4.4 Combining the stages

5 From spherical arrangements to bounded path systems

Theorem 4.1 excludes path systems whose number of paths, total length in units of L, and number of comparison intervals are bounded. The topological argument will produce a planar pairing of paths with none of those bounds. We show that every such pairing yields a system covered by the theorem. Planarity has two roles: an Euler characteristic count organizes the pairing into few intervals, and a separator reduces the number of paths while losing few paired positions. This is the spherical-arrangement method of [Ope26b, Section “From bounded patterns to spherical arrangements”]; we include the geometric and quantitative details needed here.

The distinction between occurrences and graph edges is essential: different occurrences may traverse the same edge, but the two ends of any one pairing arc may not. The graph obtained by collapsing each disk to a vertex may be disconnected and may have loops or parallel edges.

Proposition 6.1 will show that the absence of these arrangements makes the cone complex aspherical and protects the two roots. The present section proves that the random graphs can be chosen to have this absence property.

We first establish the three deterministic tools used in the proof. The first closes path segments without changing any original occurrences. The other two depend only on planarity.

5.1 Closing immersed segments

Fix the constant d of Proposition 3.4, and work for now with an outcome in which every component of \Gamma has diameter at most dL. Each side of \Gamma has at most n vertices and minimum degree at least 129.

5.2 Organizing the pairing into intervals

We next count how often a planar pairing can change its consecutive partner interval. A pair of neighboring arc ends usually has another neighboring pair opposite it across a digon. Only the other gaps, and the places where we choose to split a path, require interval cuts. This is the linear comparison-interval argument of [Ope26b, Lemma 4.3].

5.3 A recursive separator bound

Once a long boundary has been divided into pieces of controlled length, deleting a small fraction of the pieces loses only a small fraction of all occurrences. The following consequence of the planar separator theorem, also used in [Ope26b, Lemma 4.4], makes the remaining groups of pieces bounded in size.

5.4 Extracting one bounded path system

We now combine these tools. The original paths will first be divided and closed, then separated into clusters. We retain a cluster whose proportion of unpaired occurrences and number of interval pairs are both small. Controlling the total losses, rather than those of every cluster, is enough to find one such cluster.

6 Cone pictures, asphericity, and protected roots

The probabilistic argument has produced finite immersed graphs for which no reduced spherical arrangement exists. We now turn that exclusion into the two geometric properties needed in Section 2: asphericity of the cone complex and protection of the roots. We give the cone-picture argument of [Ope26b, Proposition 5.1 and Corollary 5.3] in full, including the surgeries that preserve a rooted boundary.

The main issue is to pass from a sphere or a null-homotopy to a reduced arrangement. Its disks will record fillings through cones, and its arcs will record inverse letters in the intervening map to the rose. When a pair of inverse letters traverses the same edge of \Gamma, a band surgery removes that pair. Minimizing the total boundary length makes all such pairs impossible.

6.1 Maps represented by cone pictures

For \Sigma=S^2 or D^2, a cone picture is a map f\colon\Sigma\to X together with finitely many pairwise disjoint piecewise linear closed disks D_i in the interior of \Sigma with the following properties. On the complement of their interiors, f takes values in F. For each i there is a component \Lambda_i of \Gamma and a factorization

whose restriction to \partial D_i is a specified closed edge path in \Lambda_i. In the disk case we also specify an edge path in \Gamma whose label is read on \partial\Sigma. That path may have distinct endpoints, since all graph vertices map to *.

We shall also use two elementary changes to a picture. A homotopy of one inner boundary path in its graph can be made on a collar of that boundary. Fill the resulting boundary in the same cone. The new and old fillings, with the collar included, are homotopic relative to the original boundary because the abstract cone is contractible. Thus inner paths can be tightened cyclically. If the result is constant, the inner disk can be removed, filling it by that constant map into F. An outer path can likewise be tightened with its graph endpoints fixed; the corresponding homotopy of its label is accommodated by a boundary collar.

6.2 Length reduction by band surgery

Suppose first that \pi_2(X)\ne0. Among cone pictures representing non-null-homotopic spheres, choose one minimizing the sum of the lengths of its inner boundary paths. Alternatively, suppose root protection fails. Fix a root r\in\{x_A,x_B\} and a distinct vertex z joined to it by a path with trivial label in G. Among all cone pictures of null-homotopies of labels of paths from r to this fixed z, choose one minimizing the sum of all inner boundary lengths and the outer path length. These minima exist because lengths are nonnegative integers and Lemma 6.2 provides the required pictures. Among pictures attaining the minimum, remove all constant inner boundaries.

The preceding collar changes show that every remaining inner boundary is nonempty and cyclically immersed. In the disk case the outer path is immersed and nonempty, since its endpoints are distinct. There is at least one inner disk. For the sphere case, a map with no such disk would factor through F, whose universal cover is a tree and whose second homotopy group is zero. For the disk case, a nonempty immersed path in \Gamma has a nonempty freely reduced label word, which cannot bound a disk in F.

Complete a disk picture to a sphere by adjoining a formal exterior disk D_\infty. Its interior carries no map into X. Mark its boundary at the initial point of the specified outer path; this is the exceptional break, representing the two endpoints of that path. Choose the orientation of the sphere so that the boundary of D_\infty, starting at the break, reads the path from r to z. This choice may reverse all ordinary boundary words, which preserves cyclic immersion. In the sphere case simply orient the sphere and give all disks their induced orientations.

On the complement of these disks, the map takes values in the rose. Put it in piecewise linear general position with respect to one point in the interior of each rose edge, keeping the boundary words fixed. The preimages of these points are disjoint embedded arcs and circles. Every letter occurrence has exactly one arc endpoint. Discard the circles. The arcs pair all occurrences, and paired letters are inverse when read in the oriented disk boundaries: the two ends of a transverse arc have opposite crossing signs, and disk-boundary orientations are opposite to those of the complementary surface.

It remains to show that paired occurrences use distinct underlying edges of \Gamma. Suppose an arc pairs two traversals of the same edge e. Choose a thin rectangular band around the arc. It maps into a small open interval in the corresponding rose edge and lifts to the interior of the abstract graph edge e. The lift agrees with both specified boundary lifts at the band ends. Whenever an inner disk meets the band, its cone must therefore be the cone on the component containing e.

The local shortening is particularly simple in graph paths. Splice the disk boundaries along the two sides of the band and then contract the residual portions of the two paired traversals within e. This removes two full edge occurrences in total. For ordinary boundaries the changes, with suitable cyclic starting points, are

Here e^{-1} denotes the reverse oriented graph edge, rather than merely a letter with the same label. Consequently all concatenations in (6.1) are paths in the same graph, and the new boundaries are closed. For a rooted exterior boundary the corresponding changes are

In the second formula Q is closed at the terminal vertex of e; in both formulas the resulting exterior path has exactly the original graph endpoints r,z. The contractions along e are realized by boundary-collar homotopies.

We now specify the resulting surface maps in all four cases. This also explains why the operation retains the failure that was minimized.

If the band joins two distinct inner disks, their union with the band is a disk. The maps on all three pieces factor together through the same abstract cone, since their lifts agree on the attaching intervals. Replace them by this single cone disk and shorten its boundary as in the first formula of (6.1). The replacement is homotopic to the old map relative to the rest of the surface, and the total boundary length decreases by two. Further tightening can only decrease it. An essential sphere remains essential, and a disk still fills the same exterior word.

If the band joins an inner disk to D_\infty, their union is again a disk, now an enlarged exterior disk. Retain its complementary disk and restrict the old map to that complement. Its new boundary is PQR as in the first formula of (6.2). The resulting picture is a null-homotopy of a path from r to z; the old inner boundary and exterior boundary have been replaced by a boundary shorter than their combined length by two.

If both ends of the band lie on D_\infty, their union is an annulus in the completed sphere. Its complement consists of two disks. Retain the one whose boundary contains the marked break, as shown in Figure 3. The restricted map on that disk, after the edge-collar contraction, fills the word PR in the second formula of (6.2). Thus this operation uses only a restriction of the existing map; it does not require a separate filling of Q. It preserves the fixed endpoints and decreases the total length by at least two. The path PR cannot tighten to the empty path, because r\ne z.

Finally suppose both band ends lie on one inner disk. The union N of the disk and band is an annulus, and its map factors through the same abstract cone K_\Lambda. The complement of N in the sphere consists of two disks Q_1,Q_2. Cap each new boundary by a disk mapping through K_\Lambda, using the boundary lifts inherited from N, and shorten these boundary paths to P and Q in the second formula of (6.1). In the rooted case one of Q_1,Q_2 contains D_\infty. Retain that component with its new cap and remove the formal exterior disk. This is another disk picture with the same exterior path. Its total inner boundary length is at most the old total minus two, because the two possible new cap boundaries together have length two less than the old boundary and all other retained disks already belonged to the old picture.

In the sphere case, the same operation gives two capped spheres; at least one must still be essential. To verify this without an ambiguity from choices of caps, lift the original sphere map to the universal cover \widetilde X. The factorization N\to K_\Lambda\to X lifts through a single lift K_\Lambda\to\widetilde X, chosen to agree with the lifted sphere on N. Use that very same lift for both new caps. Write \widetilde f_1,\widetilde f_2 for the resulting lifted capped spheres, with the orientations induced from Q_1,Q_2. Their fundamental homology classes satisfy

Compute this identity before the boundary-collar shortenings, which are homotopies and do not change these homology classes. The difference of the cycles on the two sides consists of the old annulus and the two caps, with their boundary orientations canceling. This cycle factors through the contractible abstract cone K_\Lambda, so its homology class is zero. No assertion that the image of this cone is an embedded contractible subspace is needed. Since \widetilde X is simply connected, the Hurewicz map \pi_2(\widetilde X)\to H_2(\widetilde X;\mathbb Z) is an isomorphism. The left side of (6.3) is nonzero, and hence one capped sphere is essential. Its total boundary length is smaller than the original one by at least two.

Figure 4 shows this splitting into two capped spheres and the homology identity that preserves essentiality.

Each case contradicts minimality. The chosen pairing therefore uses distinct underlying graph edges. All the other requirements of Definition 5.1 have already been verified: the ordinary boundaries are positive and cyclically immersed, there is at least one such boundary, and the only possible exceptional boundary is a positive immersed path starting at a designated root. Thus either failure would give a reduced spherical arrangement. Its assumed absence proves both \pi_2(X)=0 and root protection.

6.3 The finite aspherical complex and torsion

For completeness, we finish the two standard consequences needed in Proposition 6.1. The universal cover \widetilde X is simply connected, and the vanishing of \pi_2(X) gives H_2(\widetilde X;\mathbb Z)=0 by Hurewicz. Its higher cellular homology groups vanish because its dimension is at most two. Thus it is simply connected and acyclic. If it had a nonzero homotopy group, the first such group would, by Hurewicz, give a nonzero homology group. All homotopy groups therefore vanish, and Whitehead’s theorem makes \widetilde X contractible. Hence X is aspherical. Its finite two-dimensional CW structure gives a finite presentation for G.

The cellular chains of this contractible universal cover give a free resolution over \mathbb ZG,

If G had a nonidentity element of finite order, a power of that element would generate a cyclic subgroup C_\ell of prime order \ell. Restricting this resolution to \mathbb ZC_\ell still gives a free resolution of length at most two: \mathbb ZG is a free left \mathbb ZC_\ell-module, with basis given by representatives for the cosets C_\ell g in G. It would follow that H^k(C_\ell;\mathbb F_\ell)=0 for every k>2.

To see the contradiction directly, write u for a generator of C_\ell and N=1+u+\cdots+u^{\ell-1}. The periodic free resolution

is exact: the augmentation ideal is the image of multiplication by u-1, the kernel of that multiplication is \mathbb ZN, and the kernel of multiplication by N is the augmentation ideal. Applying \operatorname{Hom}_{\mathbb ZC_\ell}(-,\mathbb F_\ell) with trivial coefficients makes every differential zero, since u-1 acts as zero and N acts as \ell=0. Therefore H^k(C_\ell;\mathbb F_\ell)\cong\mathbb F_\ell for all k\ge0, the standard cohomological obstruction to torsion in a group of finite cohomological dimension [Bro82, Chapter VIII]. This contradiction proves that G is torsion-free and completes the proof of Proposition 6.1.

7 Completion of the construction

We now choose one finite pair of graphs and apply the deterministic results.

The argument selects a finite matching outcome rather than listing its edges. Once selected, its cones give a finite presentation, and the sums in Proposition 2.1 give finite scalar witnesses.