A Torsion-Free Group Algebra with Zero Divisors

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

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

If \bar t is extra, the other two extras contribute two; the ordinary successors contribute at most vp^2+12p^2. Thus

Consequently Mf\le(149/150)f. Since \mathbf1\le f and \sum_t f(t)=16528<e^{10},

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

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

for sufficiently large n, by (2.5). Choose a tuple with o(n) such bad edges.

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

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

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

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

This proves (2.6).□

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

distinct edges: all edges incident to the failing k-set lie in the larger set and are counted at most twice by its degree sum.

There are at most (C_1n/k)^{2k} choices for the larger set. Its possible typed edge prescriptions number O(k^2); choosing an unordered r-subset costs at most (C_1k)^r. Decrease \rho so that r\le np/3 throughout the range. For sufficiently large n, Remark 2.2 then bounds the probability of all r prescriptions by (2/(np))^r. Hence the probability of a failure of size k, on either side, is at most a fixed multiple of

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

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

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

By (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 CL edges and girth at least L. Mark every path start and end, and every vertex whose degree in \Delta differs from two. We first show that \Delta consists of a bounded number of chains between marks, with disjoint unmarked degree-two interiors. A chain is allowed to return to its initial mark.

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

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

The graph \Delta has no isolated vertices and has at most two leaves. Indeed, a cyclically immersed path cannot visit a leaf, and an immersed interval path can visit one only at an endpoint. If \beta is the cycle rank and c_\Delta the number of components, the degree-sum identity gives

It follows that the number and total degrees of branching vertices are bounded. There are also only boundedly many path-start and path-end marks. Every component contains a path start. Suppressing all remaining unmarked degree-two vertices now proves the asserted bound on the number of marked chains, including circle components.

Every path traverses whole marked chains. Write m_e for the total number of traversals of an undirected edge e by all the paths; it is constant on each chain. If one immersed path traverses the same oriented edge twice, the gap between the two starting positions is at least L: the intervening segment is a nonempty reduced closed walk and hence contains a cycle. A path of length h thus traverses any given oriented edge at most h/L+1 times. Summing over paths and the two orientations yields

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

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

Multiplicity stages and vertex exponents. The density-counting viewpoint of organizing constraints by multiplicity, discussed by Ollivier [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\le j\le m_*:=\max_e m_e, let \Delta_j consist of all edges with m_e\ge j, together with their incident vertices. Denote its edge and vertex counts by E_j and V_j. Let \iota be one if the interval path is present and zero otherwise. Then

For the inequality, let a(z) count interval-path endpoints at z, with multiplicity. At a vertex, all traversal incidences except these endpoints are coupled into passages between distinct half-edges, by immersion and cyclic immersion. Thus the incidences on a half-edge of maximum multiplicity must be coupled to incidences on other half-edges, except for at most a(z) endpoints. Hence

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

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

In the later realization count, the exponent V_j-E_j-k_j will count vertex-image choices against edge-prescription costs. Equation (3.4) therefore controls the total power of n across the multiplicity stages. The remaining task is to obtain exponential decay from the label constraints; counting only distinct edges would lose the incidence balance that makes these two estimates compatible.

Word constraints on aligned blocks

The aim is a common subdivision for which each comparison carries almost all positions of a block into a single partner block. Orient each marked chain of length \ell, identify it with [0,\ell], and put its edge positions at half-integers. Splitting comparisons at chain-traversal boundaries gives boundedly many subcomparisons of the form

These maps compare particular occurrences of subchains. Relative to the chosen chain orientations, their label relations are equality when \sigma=1 and inverse equality when \sigma=-1.

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

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

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

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

The remaining end fragment of a chain has O(s+1) positions. Every traversal of the same chain uses this same subdivision, also when read backwards.

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

Because a is integral, the isometry preserves the half-integer lattice. In either case its image overlaps the indicated partner grid block in a contiguous string of at least s-|r|-2=s-o(s) positions. The reversed endpoint convention in the reflection costs only a bounded number of positions.

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

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

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

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

Additional links and immersion constraints can only reduce this number.

If \mathcal U has a self-link, choose a self-linked block as the root. Its word has only \exp(o(s)) possibilities, or the pattern is infeasible. To prove this, first consider a translation self-link. Its constraints have the form

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

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

For any link component put

If \mathcal U has no self-link, then

Indeed, take a block of multiplicity z_{\mathcal U}. At least z_{\mathcal U}-b_{\mathcal U} of its occurrences are matched, and their partners are distinct occurrences of other blocks in the same component. There are only S_{\mathcal U}-z_{\mathcal U} such other occurrences. This proves (3.8), also for isolated blocks and in the presence of multiple links.

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

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

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

using h_i=s+O(1). This also explains why the bin estimate uses the squared, rather than the unsquared, word weights.

Enlarge each unlabelled pattern by its bin integers. There are O(L/s) blocks and O(s) possible bin values per block, so the number of choices is at most

Together with the earlier polynomial count, the number of enlarged patterns is \exp(o(L)), uniformly for the fixed bounds.

Expected counts and stage selection

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

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

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

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

on the number of vertex assignments. We apply probability estimates only to the feasible injective choices among these assignments.

Such a choice requires E_j distinct matching prescriptions. Two distinct edges cannot prescribe the same matching pair in either direction, because injectivity and the immersion condition would then identify their outgoing letters at an endpoint. By Lemma 2.2, the probability of all these prescriptions is at most

uniformly since E_j=O(L). Multiplication leaves the bounded factor p^{-Q_j}, the power n^{V_j-E_j-k_j}, and the product of internal turn weights. Discard turn weights outside full blocks, since they are at most one. The retained product is \prod_{i:m_i\ge j}P(W_i)\le\exp(-\sum_{i:m_i\ge j}d_i). The bounded factor and the prescription errors are absorbed in \exp(o(L)), proving (3.10).

The number of permitted stage label assignments is at most

To see this carefully, consider a link component with at least one active block, equivalently z_{\mathcal U}\ge j. The allowed labels on its active blocks are projections of full feasible word assignments on that component. Their number cannot exceed the number of full assignments. If the component has no self-link, choose a root attaining \min_{i\in\mathcal U}d_i, count its words by (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), since the total number of blocks is O(L/s). Arbitrary letters in the end fragments contribute at most \exp(O(s)) per marked chain, again \exp(o(L)). Ignoring any further constraints between components gives (3.11).

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

If 2z_{\mathcal U}\le S_{\mathcal U}, then (3.9) gives

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

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

Bounded multiplicities and boundedly many chains imply

where the second inequality is (3.6). There are only boundedly many stages by (3.2), so all their error terms remain o(L). We have proved

Choose, once and for all,

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

Put M=\max\{1,\lceil2(C+K)\rceil\}, so m_*\le M. Some stage therefore has B_j\le e^{-\delta H/(4M)}. Since a realization of the entire enlarged pattern requires X_j\ge1 at every stage, Markov’s inequality gives

This uses no independence between stages. We multiplied numerical bounds solely to find one stage with a small expectation.

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

Proof. Appending a geodesic return may cancel the ends of the given segment. We prevent this by inserting short based loops with prescribed first and last edge exclusions. To construct such a loop at a vertex z, delete at most two specified incident undirected edges from its side of \Gamma. For sufficiently large n, girth at least L\ge3 excludes graph loops and parallel edges; after the deletion every vertex still has degree at least (q+1)-2\ge3. Put

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

Let S be the given segment, running from a to b, and let R be a geodesic from b to a, of length at most dL. If R is nonempty, choose a based loop J_b at b by excluding the last edge of S and the first edge of R. Choose J_a at a by excluding the last edge of R and the first edge of S. Then

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

For large n we have L\ge(c/2)\log n and L\ge1, whence

Thus any integer

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

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

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

The neighborhood retracts to the multigraph, so \chi(R)=N-E. Gluing the complementary surfaces to it along boundary circles gives

Consequently

This calculation uses neither connectedness of the multigraph nor simple connectivity of its complementary regions.

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

• •

  A disk monogon has one gap between occurrences paired by its single arc. Those consecutive letters are inverse, so immersion forbids the gap unless it is the exceptional break. Thus there are at most M\le1 monogons, contributing -M to Equation 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 N such faces, and hence at most 2N gaps of this type. This deliberately allows a coarse bound, including isolated single-edge components.

• •

  Every connected non-disk complementary surface is planar with Euler characteristic at most zero. Its length is therefore at most its contribution l_Q-2\chi(Q). For a disk region of length l_Q\ge3, we instead have l_Q\le3(l_Q-2).

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

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

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

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

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 s vertices, at most 2\sqrt{2s} vertices whose deletion leaves components with at most 2s/3 vertices. Apply this theorem recursively to each component with more than K vertices.

For a recursive call on s>K vertices, charge 2\sqrt2/\sqrt s to each of those vertices. The total charge at this call is 2\sqrt{2s} and bounds the number deleted. Fix one original vertex and list the successive component sizes containing it before it is deleted or recursion stops. Consecutive sizes decrease by a factor at most 2/3. Reading the list backwards from its last size greater than K, its total charge is at most

This also covers vertices that are themselves deleted at a separator. Summing over the original vertices proves the bound. Components already of size at most K incur no charge.□

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

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

For reference, the dependency order is

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

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

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

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

Every resulting path has at least L original occurrences, except possibly the single exceptional path when it was kept intact: ordinary intact paths have that length by girth, and split segments have length at least UL/3\ge L. It follows that

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' interval pairs, each contained in the designated pieces. On a newly closed path, index its original segment first and its closure afterwards; this keeps those intervals within the linear indexing as well.

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

By Lemma 4.4 and the choice of K, delete at most \eta N' vertices so that each remaining component, called a cluster, has at most K pieces. The number M of deleted original positions is at most

Retain just those occurrence pairs whose two pieces survive. Each surviving original position has at most one deleted partner, so the number of newly unpaired surviving original positions is at most M. Each comparison interval lies in one piece on either side; thus an interval pair is retained or discarded in its entirety. No retained pair joins different clusters.

For a cluster Z, let H_Z be its total path length including closures, b_Z the number of its unpaired positions, and I_Z its number of retained interval pairs. Equations 4.6, 4.7, and 4.8 give

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

A positive amount of admissible length survives. The retained total length is at least 15H_0/16 by Equation 4.4. Clusters with b_Z>\varepsilon H_Z have total length at most

Clusters with I_Z>C_2H_Z/L likewise have total length at most

After excluding both classes, at least 13H_0/16 of cluster length remains.

A cluster of length less than L can contain no positive-length cyclically immersed path. Thus it can consist only of the one intact short exceptional path, and there is at most one such cluster. If its length is h<L, the original arrangement also contained an ordinary cyclic path of length at least L, so H_0\ge h+L>2h. Removing that cluster therefore costs less than H_0/2. The clusters left after all three exclusions have total length at least

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

and inherits Equation 3.1. All paths are cyclically immersed except possibly the entire short exceptional interval, whose initial vertex is still x_A or x_B. Added closures may traverse old edges repeatedly; all their occurrences are unpaired, as permitted by Proposition 3.1. The cluster is therefore one of the bounded patterns excluded by Remark 3.1.

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

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

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

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

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

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

Proof. The simply connected two-dimensional cover \widetilde X has H_2=0 by Remark 5.1 and Hurewicz, has H_1=0, and has no cellular homology above dimension two. It is therefore contractible by the homological form of Whitehead’s theorem [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 \widetilde X give an exact free \mathbb ZG-resolution of \mathbb Z of length two. If G had a nontrivial finite-order element, a power would generate a cyclic subgroup H=\langle g\rangle of prime order \ell. Restricting the resolution to \mathbb ZH preserves freeness, since \mathbb ZG is free as a left \mathbb ZH-module on coset representatives.

The cyclic group has the exact periodic resolution

Exactness follows by comparing the coefficients of 1,g,\ldots,g^{\ell-1}: the kernel of g-1 consists of the multiples of N, and the kernel of N is the augmentation ideal generated by g-1. With trivial coefficients \mathbb F_\ell, all differentials in the corresponding cochain complex vanish. Hence H^k(H;\mathbb F_\ell)\cong\mathbb F_\ell in every degree. The comparison theorem for projective resolutions makes this cohomology independent of the chosen resolution [2, Chapter I, Theorem 7.5, p. 24]. This contradicts the vanishing above degree two forced by the restricted finite-length free resolution.□

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

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

Set

Both sums are finite. The root contributes the identity to each. By Remark 5.1, no other vertex contributes identity, so its coefficient is one in each factor. Thus \alpha\ne0 and \beta\ne0. No assertion about equality between two non-root labels is needed.

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

sends g_x to g_xt and h_y to h_yt, and therefore preserves

The reverse step has label \bar t. Since full components are used, the degree at (x,y) is the entire number |S_x\cap S_y|, which is odd by (2.1). The girth condition excludes loops for the chosen large n; parallel edges would not affect the degree-sum argument.

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