A hyperbolic group with no geometric CAT(0) action

Proof. For a connected graph H and a map H\to X into a connected complex, attaching its cone changes \pi_1X by the normal closure of the image of \pi_1H. It introduces no extra generator. This follows from van Kampen, or by choosing a spanning tree of H and eliminating all but one of the new radial edges successively. The statement does not require distinct graph vertices to have distinct images.

It remains to check that the top macro graph imposes the required core relations after the fan relations. Each fan triangle replaces a fan edge by the two radial edges from its endpoints to the fan apex. A path in a fan can therefore be replaced, relative its endpoints, by the radial path through that apex. Apply these replacements to a closed core walk. Excursions through X_i or Y_i then cancel, leaving a closed walk in the mapped macro graph. At D, the only unreplaced edge is the loose edge; together with r_{b_D,X_D} it gives exactly the exceptional subdivided incidence. Conversely, every macro turn can be replaced by a path in its connected fan. The two sets of relations have the same normal closure modulo the fan relations. This proves the presentation assertion.

The graph \Gamma, and each fan, is bipartite, so every closed-walk word has even length. The decorations have lengths four and six. Sending each original generator to the nonidentity element of C_2 respects all the defining relations and is surjective.□

Proof. Fix the table types, the incidence of the fan slots, and a partition of the field positions into unsigned-value classes. There are only finitely many such choices for fixed M. Write J for the number of positions. Assigning letters to a pattern of rank R has at most C_M N^{J-R} possibilities: first choose one underlying generator per class, then choose the signs of the positions. The latter contributes only a factor bounded in terms of M.

We count only choices whose occurrences are distinct within their respective tables. For such choices all the required Bernoulli trials are independent. Their product contributes the power of N with exponent

Here a shared fan occurrence appears once in the second sum, not once per top using it. Since J=s+\sum_b k_b+\sum_e2h_e, the expected number of realizations of the chosen pattern is at most

If Equation (3.1) fails, this exponent is negative. There are finitely many exponents to consider for the fixed size bound, so summing these expectations proves the assertion.□

Proof. The disk assertion is the cellular van Kampen construction, applied to the finite cone and polygon complex. Here is also a description that applies to the sphere assertion. Since \widetilde P is simply connected, the Hurewicz map \pi_2(\widetilde P)\longrightarrow H_2(\widetilde P;\mathbb Z) is an isomorphism [10, Theorem 4.32]. There are no three-cells. Consequently a sphere map representing the class of c has cellular two-chain equal to c, not merely congruent to it modulo boundaries of three-cells.

Put this map in cellular general position. One way to do so is to choose an interior point in each two-cell, make its inverse image a finite set of regular points, and take small disks about those preimages. Each such disk maps, with a sign, across that two-cell. Retracting each punctured target cell to its boundary moves the complement of these disks into the one-skeleton. Inverse images of interior edge points now give strips pairing the corresponding cell sides; the remaining regions map to vertices. Circular strips not meeting cell sides may be cut and capped. A vertex region with several boundary components may likewise be replaced by a separate cap for each component. These operations are compressions along curves in an oriented sphere. They therefore produce a collection of oriented spheres, not surfaces of positive genus. They change none of the signed cell disks or their lifts. Components with no cell disks may be discarded. This gives the claimed spherical pictures and preserves the chain c exactly.

For a disk map, adjoin the distinguished outside polygon before the same construction. Keep that polygon as a single face throughout. The construction preserves its word and gives one picture containing it, possibly together with sphere components. All the required pictures are finite.□

Proof. The nonempty class of finite pictures in Lemma 3.3 has a lexicographic minimum for the stated pair of nonnegative integer costs. In the sphere case fix the chain c once and for all in taking this minimum.

Simple macro cycles. Consider a top polygon whose macro walk repeats a template vertex. Its two boundary points at that repetition have the same lifted value: both are joined to the same lifted top apex by the same indexed cone spoke. Split the polygon by a chord collapsed to that vertex. The two resulting macro walks have the same total perimeter and the same total cone chain. A free backtrack cancels two oppositely oriented copies of a single lifted cone triangle and reduces total perimeter by two. Delete any resulting empty polygons. Repeating splitting and removal of backtracks therefore gives simple macro cycles. Collapsed chords may be put in the picture form of Lemma 3.3; they carry no two-chain. This proves the first property.

Cancellation. Suppose two top polygons meet at the same macro side of one occurrence. The two elementary cone triangles incident to that side are copies of the same triangle with opposite orientations. Their lifts agree, because the common lifted macro side determines the lifted triangle and its apex. Cancel the pair and merge the remaining cone walks. This reduces total top perimeter by two. It is an ordinary diagram cancellation: one uses the two face interiors and a thin strip across the specified common side, so other contacts between their boundaries cause no obstruction. Any vertex regions produced by the cancellation are capped as above. A same-template contact cannot occur between two sides of a single simple top polygon, because a simple macro cycle uses each edge at most once. The identical cancellation of two fan triangles or two decoration disks along equally indexed sides reduces the second cost without increasing the first. These cancellations preserve the cellular chain, so they are forbidden by minimality in both problems.

Fan-apex links. Fix a source vertex v mapping to a fan apex b. A step in its link is either a fan triangle or a corner of a top polygon. Suppose two different outgoing spokes at v have the same radial label. Each spoke is an edge from v to a vertex mapping to the letter-bouquet vertex. Cut the side pairings of these two edges and pair them crosswise, with the outgoing orientations at v agreeing. This preserves the orientation of every face and all face maps. In terms of vertex-link cycles, it splits the link cycle of v into two. At the far ends it either merges two distinct vertex cycles or splits one vertex cycle.

For completeness, this switch preserves the genus-zero condition. The numbers of faces and edges do not change. When the two far vertices were distinct, the total vertex count does not change, and the affected surface remains connected: both switched edges are incident to the merged far vertex. When the far vertices were the same, the total vertex count increases by two. There can be at most two affected components after either switch. To see this, cut the two corresponding edges of the connected dual graph before re-pairing their four exposed half-edges. Every component of the cut graph contains an exposed half-edge: otherwise it was already disconnected before the cut. After re-pairing, every component therefore contains one of the two switched edges. This argument includes loops and parallel edges in the dual graph. In the first case the connected oriented surface consequently has Euler characteristic two. In the second case the total Euler characteristic is four, which forces exactly two oriented spheres. All unaffected spheres are retained, and the outside polygon remains one unchanged face.

The switch is also valid for the fixed lifted chain. The repeated radial label and the lifted initial fan vertex determine the same lifted radial edge and far endpoint. Thus the new vertex identifications agree in \widetilde P, and every lifted face is unchanged. Each switch increases the number of fan-apex instances while keeping the finite set of polygon corners fixed. Repetition therefore terminates. The two minimized costs are unchanged, so a newly created forbidden adjacency would still contradict their minimality by the cancellation just described.

The resulting link uses each radial label at most once. There are at most five labels in any fan. A two-step link made only of fan triangles is the reverse traversal of one edge of the simple fan graph; the two triangles would cancel along an equally indexed radial side. Every other nonempty triangle-only link is a circuit in the simple bipartite fan graph and has length at least four. This proves the last property.□

Proof. Give each fan field of b weight w_b, each loose field of a weight t_a, and each field of a decoration e weight t_e. These are upper bounds for their side multiplicities in the fragment. Indeed a fan field is used at most once at a given normalized fan-apex link, so its multiplicity is at most r_b. A simple top polygon uses its loose field at most once, and a copy of a decoration uses each indexed field once.

For each integer j\ge1, apply Equation (3.1) to the positions of weight at least j. This is an eligible collection: t_a\ge j implies w_b\ge m_b\ge t_a\ge j for every slot a\to b. Its size is at most 8A, since there are at most T distinct tops, at most 7T+Q fans, and at most E decorations. Sum the resulting inequalities over j. Within an unsigned-value class, the sum of its ranks is its total weight minus its largest position weight. Thus, writing \mathcal C for the unsigned-value classes, we obtain

Every internal letter contact joins two different field positions. For fan triangles and decorations this follows from the cancellations in Lemma 3.4; for two loose top sides it follows from the same-occurrence top cancellation. A contact between different kinds of cells automatically has different positions. In each class C, choose one maximum-weight position. Charge each internal contact to one of its endpoints other than that position. Such an endpoint always exists. Different contacts use different actual side copies, so the charge to any position is at most its side multiplicity and hence at most its weight. This proves that I is bounded by the left side of Equation (3.4). Using Equation (3.2) on its right side gives Equation (3.3).□

Proof. First suppose w_b=r_b. A simple top polygon has at most one turn at this fan, so S_b\ge\sum_{z\mapsto b}d_z. Consequently the left side of Equation (3.5) is at most \sum_{z\mapsto b}(2-d_z). For a full link with d_z=0, at least four fan triangles give the required inequality. For a full link with d_z=1, the triangles form a path in the fan between the two distinct ports of that top turn. Ordinary ports are distinct line vertices, so this path has at least two edges. The only exception is a path incident to the port X_D; it may have one edge, in which case its top turn has the loose side counted by P_b^*. Thus in either case its triangle count plus its loose-side payment is at least two. For d_z\ge2 the expression 2-d_z is nonpositive. At a represented partial link with d_z=0 there is at least one selected fan triangle, so its deficit is at most 3/2. With d_z=1 its deficit is at most one, and with d_z\ge2 it is nonpositive. Thus the error 2J_b suffices in this case.

Now suppose w_b=m_b>r_b, and choose a top occurrence a_0 with t_{a_0}=m_b. Call its turns dominant. Let x and y be the total numbers of selected dominant and nondominant turns over b. Nondominant selected faces have at most one turn each at this fan, including when other selected faces omit the fan entirely; hence y\le S_b-m_b. It follows that

Consider a full link. In its cyclic list of turns the number of consecutive dominant-to-dominant interfaces is at least the number of dominant turns minus the number of other turns. To see this, assign to each dominant turn its following turn: at most as many dominant turns can be followed by a nondominant one as there are nondominant turns. A single turn is followed by itself. Between a counted pair of turns there is a path of fan triangles. This path cannot have length zero, because then the two top polygons use the same radial side of the same occurrence a_0, forbidden by Lemma 3.4. If the path has length one, it must have an exceptional port, since the other ports lie in the line part of the bipartite fan graph. That port has its loose-side payment. Thus the path length plus the available payments is at least two for each counted interface. The triangle paths are disjoint portions of the link. A port incidence is an endpoint of just one such intervening path, so no loose-side payment is used twice. The triangle counts and payments at full links therefore bound twice their total dominant-minus-nondominant count from below.

At a partial link, the selected steps form a nonempty proper subset of a cyclic list of at most five steps. Split this subset into maximal consecutive selected runs. Each run and each intervening unselected gap contains a step, so there are at most two runs. In a run containing turns, let k and l be the numbers of dominant and nondominant turns. Their linear turn list has at most l+1 blocks of dominant turns. Consequently, if H counts its consecutive dominant-to-dominant interfaces, then

The fan-triangle path at each of these interfaces is entirely selected. The same indexed-side cancellation and exceptional-port argument used for a full link shows that its length plus its available loose-side payments is at least two. Different interfaces, including those in different runs, use disjoint triangle paths and distinct port incidences, so no payment is used twice. A run without turns contributes zero to the dominant-minus-nondominant count. Summing over the at most two runs therefore bounds that count by half the selected triangle count and loose-side payments, plus two.

Choose the dominant occurrence a_0 once for the entire fan occurrence b, and apply these estimates separately at all its apex instances. They do not require the fragment to be connected, or every selected polygon of a_0 to visit this fan. Summing the partial- and full-link estimates, and then using Equation (3.7), proves Equation (3.5) also in the second case.

Finally, a represented partial cyclic link has at least two transitions between selected and unselected steps. Each transition is a radial edge with exactly one selected incident face, and hence is a radial fragment boundary side. A radial side belongs to only one fan-apex instance. This proves Equation (3.6).□

Proof. Write W=\sum_b w_b and P^*=\sum_bP_b^*. Every simple top polygon has at least three turns. Summing Equation (3.5), and using Equation (3.2), gives

The right side of Equation (3.3) can be written as

There are at most five selected triangles at a represented fan-apex instance, so Q\le5\sum_b r_b\le5W. Therefore

The total number of raw side copies in the fragment is

Equations (3.3) and (3.10) imply

Since B_{\rm raw}=R_{\rm raw}-2I, Equations (3.6) and (3.11) give

This is Equation (3.9).□

Proof. Ignore loops and apply the planar separator theorem to the underlying simple graph. In a graph with q vertices it gives a set of at most c\sqrt q vertices whose removal leaves two sets, with no edges between them, each of size at most 2q/3; one may take c=2\sqrt2 [14, Corollary 2]. Repeat inside every set larger than K, and make every removed separator vertex a singleton part.

Charge c/\sqrt q to every vertex present in a recursive set of size q. These charges pay for all removed separator vertices. For any fixed original vertex, the successive set sizes containing it decrease by a factor at most 2/3 while they exceed K. Reading that sequence backward shows that its total charge is at most

If the original graph has A vertices, the number of removed separator vertices is at most C A/\sqrt K, where C=c/(1-\sqrt{2/3}). Every edge crossing between final parts has a removed separator vertex as an endpoint. The degree bound therefore limits their number, counting multiplicity, to DC A/\sqrt K. Choose K so large that DC/\sqrt K\le\eta. Disconnected graphs are treated component by component.□

Proof of Theorem 3.1. Fix the parameters, so that \kappa and C_0 in Lemma 3.7 are positive constants. Choose \eta>0 with 2C_0\eta\le1/2, and apply Lemma 3.8 with D=15. This gives a fixed finite threshold K. By Lemma 3.2, with probability tending to one Equation (3.1) holds for all collections of at most 8K occurrences. Work with any realization having that property. The remainder of the proof is deterministic and applies simultaneously to every picture for this realization.

For a normal picture, the dual graph of its interior faces and their contacts is planar of degree at most fifteen. Fan triangles have three sides, decorations have at most six, and simple top polygons have at most fifteen. Parallel contacts and self-contacts cause no problem in Lemma 3.8. Partition its A interior faces into fragments of size at most K, cutting at most \eta A contacts. Let B_0 count contacts with the outside polygon; in the sphere problem set B_0=0. The sum of fragment boundary lengths is at most B_0+2\eta A. Lemma 3.7 applies to every fragment, and summing it gives

In a disk picture whose outside word has length \ell, one has B_0\le\ell; outside-to-outside pairings represent free boundary cancellations and do not add an interior contact. Thus the normal picture uses at most 2C_0\ell interior faces.

If a nonzero cellular two-cycle c existed in \widetilde P, use its normal spherical picture supplied by Lemmas 3.3 and 3.4. For it B_0=0, forcing A=0. Its cellular chain would then be zero, contrary to its construction. Therefore H_2(\widetilde P;\mathbb Z)=0. The universal cover is a simply connected two-dimensional CW complex, so all its reduced homology groups vanish. If it had a first nonzero homotopy group, the Hurewicz theorem would identify it with a nonzero homology group [10, Theorem 4.32]. It is consequently weakly contractible, and the Whitehead theorem makes it contractible [10, Theorem 4.5]. This proves asphericity.

We finish by making explicit the claimed filling inequality over letters. Choose a vertex of every fan template and, for each of its vertices, a fixed path from the chosen vertex to that vertex. These paths have length at most two. Send every fan-apex vertex of a normal picture to the bouquet vertex, and replace its indexed radial edge by the label word of the corresponding fixed fan path, with the appropriate orientation. A fan triangle boundary becomes a closed walk in that fan of length at most five. A top polygon boundary becomes a closed walk in its copy of \Gamma: at an ordinary point, its two radial paths concatenate to a fan path between the two ports; at the exceptional point the path to X_D is followed by the loose edge. Its expanded length is at most thirty. A decoration boundary is unchanged.

Use as a finite letter presentation all simple cycle relators in each included fan and top graph, together with the decoration rows. This presents the same group by the cone construction in Section 2. Any closed graph walk of length at most thirty splits at repeated vertices into at most thirty simple cycles, after free backtracks are erased. Each expanded face above thus has a filling with at most thirty relator disks in this presentation. Replacing the faces of the normal picture by these fillings leaves the outside letter word unchanged and produces a disk diagram, with free folds allowed, of area at most 60C_0\ell. Sphere components can be discarded. Any other fixed finite choice of defining cycle relators gives the same linear inequality after bounded relator substitutions. This proves the theorem.□

Proof. First consider only the core part of W. Let a_i be its number of fields in F_i, and let \ell\in\{0,1\} indicate the loose field. Before charging the top mark, the exponent is

The top-mark cost is charged only for the complete core. For that set the exponent is 32-17-12=3. Consequently every core subset has exponent at least the size of any admissible core subset it contains, and at least the smaller of two and its own cardinality.

Now add the fresh fields of the four-letter entries. Adding one fresh field of an entry adds one to the exponent. Adding both adds two and can charge the cost two only if that entry’s two core fields are also present. The net contribution of each pair of fresh fields is therefore nonnegative. This proves Equation (4.5) when S consists of core fields, and proves Equation (4.4) when W has at least two core fields. If W has fewer than two core fields, no four-letter entry is charged, and no fan or top entry is charged either. In that case h(W)=|W|. This proves Equation (4.4) in all cases. Finally, an admissible subset of one four-letter entry has size at most two, so its required bound follows from Equation (4.4).□

Proof. For the first assertion, condition only on the Bernoulli trials used by \sigma. All other trials retain their original independent laws. Entries supported in U have thereby been fixed present, as have the other entries of the specified branch. Every other branch uses new entries distinct from those conditioned trials. For each field outside U, its other t-1 values are distinct and avoid the value in \sigma, giving (N-1)_{t-1} choices. Each extra branch requires all the entries not supported in U, giving exactly Equation (4.12).

Consider an overlap of the unconditioned entries of two such extensions. In extra branch j of the first extension let V_j consist of the outside-U fields involved in its shared entries. The assignment penalty in Equation (4.8) is \sum_j|V_j|: all U-values are fixed, whereas every involved outside-U variable is free and, by injectivity, cannot match a value in the pinned branch. Charge each shared entry to its branch in the first extension. The recovered critical cost there is at most

Thus the critical excess of assignment penalty over recovered cost is at least

for every nonempty overlap, by Equation (4.7). The finitely many bounds remain strict for small actual parameters. Equations (4.8) and (4.9) prove the conditional relative variance claim, uniformly in the values of \sigma. If t=1, the extension count is identically one and there is no variance to estimate.

For the second assertion, no Bernoulli trials are conditioned on; only letter values are pinned. Since e\notin U, its t pinned values satisfy precisely its field-injectivity constraint. The other fields have N^{|U|}(N)_t^{d-1} choices, proving Equation (4.13).

For an overlap let W be the set of variables in the first star belonging to shared entries. Write A=W\cap U, and let V_j be its outside-U fields in branch j. Let m(W) be the number of its e-variables. In a realizable overlap an e-variable can only match the variable with the same pinned value; those equalities impose no further assignment penalty. All other involved variables do impose one. Thus q=|W|-m(W) in Equation (4.8).

Define h_\star(W) using the critical entry costs in the star, counting entries entirely in U once and the other entries separately in each branch. The recovered cost is at most the cost of all star entries supported in W. Therefore the critical excess is at least

If A\ne\varnothing, separating entries entirely in U from the entries in each branch gives

Indeed the exact contribution of branch j is |V_j| minus the costs of entries supported in A\cup V_j but not entirely in U; replacing A by U can only increase those costs. This proves the displayed inequality directly. Its first term is at least one by Lemma 4.2, and each nonempty summand is at least one by Equation (4.7). Each such branch contains at most one pinned e-variable. Hence the excess in Equation (4.14) is at least one.

If A=\varnothing, no shared entry meets U, and entries in different branches use disjoint variables. Consequently h_\star(W)=\sum_j h(V_j). An active branch contains the full support of at least one shared entry. Every entry support has at least three fields, so |V_j|\geq3 in such a branch and Lemma 4.2 gives h(V_j)\geq2. Subtracting at most one pinned leaf per branch again leaves a positive excess. This argument is applied to supports of shared entries, not to arbitrary nonempty field subsets.

All nonempty overlap types thus have critical excess at least one. Perturbing to sufficiently small actual parameters preserves a positive excess for every type. Equation (4.9), summed over those types, proves the second relative variance assertion. The bounds are uniform in the pinned letters because all assignment counts and Bernoulli probabilities used above are independent of their particular values.□

Proof. Use the uniform law on present injective stars. We verify that its normalization is nonzero and has the stated properties.

Put L_N=|\Omega_n| and \lambda_N=\E L_N. For a specified branch let

The conditional variance bound of Lemma 4.3, followed by the Cauchy–Schwarz inequality, gives uniformly in each possible assignment \sigma

Multiplying by the probability that \sigma is present and summing over all assignments shows \E D_N=o(\lambda_Na_N). Markov’s inequality yields D_N=o(\lambda_Na_N) in probability. By Equation (4.10), L_N/\lambda_N\to1 in probability. Since

we have Z_N/(L_Na_N)\to1 in probability, and in particular Z_N>0 with probability tending to one. Moreover,

The same argument applies to each of the finitely many branches. This proves the marginal assertion. Agreement on I is exact because the branches agree on U\supseteq I.

For the leaves, let \mathcal B_N be the set of ordered distinct letter lists of length t, so |\mathcal B_N|=(N)_t. By the second part of Lemma 4.3,

Markov’s inequality and \sum_bB_b=Z_N imply that the total variation between the leaf distribution B_b/Z_N and the uniform distribution on \mathcal B_N tends to zero, by the same displayed normalization estimate with (N)_t,b_N in place of L_N,a_N. Finally, an iid uniform list in S_n^t has a repeated value with probability at most \binom t2/N. Its distribution conditioned on distinctness is uniform on \mathcal B_N. This proves the final assertion.□

Proof. Adjoin to \mathcal T the finitely many tests (\varnothing,e,1), one for each field e. For such a test Equation (4.4) forces U=\varnothing, and its one-branch star is exactly a master match. The leaf assertion in Lemma 4.4 therefore gives single-field uniformity. Choose parameters satisfying all the finite overlap margins just described, \beta+90\delta<3, and \delta<1. Equation (4.10), Lemma 4.4, and Equation (4.16), combined over this finite set of events, prove the proposition.□

Proof. Choose a minimizing sequence x_j and a compact set C with GC=X. There are g_j\in G such that y_j=g_jx_j\in C. Bounded energy bounds each individual displacement d(x_j,sx_j), since S is finite. It therefore bounds

The closed neighborhood of C of any fixed finite radius is compact, by properness of X. Properness of the action implies that only finitely many group elements can carry a point of C into that neighborhood. For each s there are consequently only finitely many possibilities for g_jsg_j^{-1}. Passing to a subsequence, the entire conjugated generating tuple is constant and y_j converges to a point y\in C. Its energy for that tuple is the original infimum. Fixing one element g_{j_0} in the subsequence, the point g_{j_0}^{-1}y attains the infimum for the original tuple. An energy of zero would make all generators, and hence G, fix a point. A proper action has finite point stabilizers, so the minimum is positive.

Fix a minimizing point x. First let h be a tangent vector represented by a geodesic x_t issuing from x, parameterized with initial speed \norm h. For sufficiently small t>0, convexity at the midpoints of the crossed geodesics gives

After averaging over the symmetric alphabet, the two terms on the right have the same average: apply s^{-1} to the second distance and replace s by s^{-1}. Minimality and first variation now imply

Represented vectors are dense in the completed tangent cone, so continuity gives Equation (5.2) for every h. The cone cosine formula immediately gives Equation (5.3); in particular 0 minimizes the mean squared distance to the v_s.□

Proof. Write Q_{1k}(a,b) for the number of included rows whose first coordinate is a and whose kth coordinate is b. The asserted relative estimate is

Summing over b shows that rows beginning with any fixed a are nonempty and that their conditional kth-coordinate distribution is bounded above, pointwise, by

The relation attached to a row (a,s_2,\ldots,s_6) gives a^{-1}=s_2\cdots s_6. Since d(x,a^{-1}x)=d(x,ax), the triangle inequality and Cauchy–Schwarz give

Average over the rows beginning with a and use the preceding pointwise bound and Equation (5.4). Each of the five conditional averages is at most (1+\varepsilon)/(1-\varepsilon), proving the assertion. This uses only nonnegative weights, and therefore holds even when the weights were chosen from an action after the table was revealed.□

Proof. Subtract strong convexity of d(h,\cdot)^2 from Equation (5.6) in the identity 2\ip{h}{u}=\norm h^2+\norm u^2-d(h,u)^2. The quadratic terms cancel, proving concavity. Induction gives Equation (5.8).

For the independent samples, condition on m_{j-1}=u. The barycenter variance inequality gives \mathbb E[d(u,V_j)^2\mid u]\ge\norm u^2+1. Strong convexity of squared distance from the cone vertex therefore gives, with a_j=\mathbb E\norm{m_j}^2,

Starting with a_1=1, induction yields a_j\le1/j.□

Proof. Fix t. Use the coupling in Proposition 4.5: it gives t matches agreeing on I, each branch marginal at total variation distance at most \eta_{\nu,t} from \mu_\nu, and their e-labels at distance at most \eta_{\nu,t} from independent uniform letters, where \eta_{\nu,t}\to0. Increasing the error if necessary allows one bound for all these comparisons. Applying the fixed inversion \sigma preserves this assertion.

The vector h_I has the same value in every branch. Form the inductive mean m_t of the branch vectors v_{\sigma(e_j)}. Equation (5.8) gives, for every coupled tuple,

The last step uses only the norm bound; it does not assume that h_I is independent of the leaves.

Under independent uniform leaves, Equation (5.7) applies by Equations (5.3) and (5.4). Under the coupling, \norm{m_t}\le M, by convexity of the ball of radius M. Consequently the total variation comparison changes the expected squared norm by at most 2M^2\eta_{\nu,t}. The branch comparisons change the expectation of each scalar-product test by at most 2BM\eta_{\nu,t}. It follows that

First take the upper limit in \nu with t fixed, and then let t\to\infty. All error bounds used only B and M, so the conclusion is uniform over the action-dependent functions in the statement.□

Proof. For an edge with letter s, translation at its initial orbit vertex identifies its squared length with \norm{v_s}^2, or with the same quantity for s^{-1}. Single-field total variation convergence, Equation (5.9), and the normalization show that its squared product length tends to one.

For a path with oriented readings a_1,\ldots,a_k, translate its penultimate orbit vertex to x_\nu. Its earlier endpoint then becomes a_{k-1}^{-1}\cdots a_1^{-1}x_\nu, and its next endpoint becomes a_kx_\nu. Set

This is a function of precisely the preceding labels, and \norm{h_I}\le(k-1)M. Equation (5.1) gives

in every factor. Average, apply Lemma 5.4, and take the ultralimit. Induction adds at least one at each step. Every prefix of the field sets in the statement is admissible, so the conditional test is available at each step. Distinct fields here need not carry distinct numerical letter values.□

Proof. Apply midpoint convexity to d(m,z_2)^2 and d(m,z_4)^2 using the segment z_1z_3, and then to d(m,n)^2 using z_2z_4. Substituting the first two inequalities into the third and multiplying by four gives Equation (5.12).□

Proof. The opposite pairs are geodesic segments through c, so their directions in T_cZ are antipodal and their radial lengths are r. If v^+ and v^- are any such opposite vectors, the angular triangle inequality implies

Indeed, the two angles from u to their directions have sum at least \pi, and the sum of their cosines is nonpositive.

Set u=\log_c z_i, v^+=\log_c z_j, and v^-=\log_c z_{j+3}, with indices modulo six. Log comparison gives

The two prescribed squared distances sum to 3=4r^2, so the lower bounds sum to zero. Equation (5.16) forces equality in each bound. Thus the angle at c equals its Euclidean comparison angle. For a nondegenerate triangle the flat-triangle equality theorem gives a flat triangle; for an opposite or repeated pair the statement is a segment or a point.□

Proof. First use only X representatives. A noncollinear ordered triple of Fano points is a basis of \mathbb F_2^3. Reordering a basis does not change its hexagon, and replacing one basis vector i by i+j preserves the line ij and the third point k. The old and new hexagons therefore share the opposite pair (X_k,ij), and their centers are its common midpoint. Permutations and elementary additions generate all changes of basis over \mathbb F_2, so the centers of all X hexagons agree.

Replace one Y representative in a core hexagon by its X representative. The new hexagon is a core hexagon, since every corresponding X edge exists. Either of the unchanged point representatives, together with its opposite line, is an opposite pair shared by the two hexagons. Their centers agree. Repeating this replacement connects every core hexagon to one using only X representatives.

Every X_i lies in a hexagon obtained by extending i to a basis. Every line lies in one by choosing two points spanning that line and a third point outside it. Each Y_i has two distinct incident lines available. Choose a point other than i on each of them; these two points together with i are noncollinear and yield a core hexagon containing Y_i. This includes Y_D, using its two full lines. The radius assertion follows.□

Proof. Use the normalized minimizing actions of Lemma 5.1 and the uniform bound of Lemma 5.2. The product construction, Lemma 5.5, and the decoration-square argument give the first assertion. Lemmas 5.7 and 5.8 give the second. The fixed-fraction argument above gives the third.□

Proof. Let o be the midpoint of p_0,p_2. Squared-distance convexity gives

Since

both inequalities are equalities and o is also the midpoint of p_1,p_3. The equality for d(o,p_1) is an interior comparison equality in the triangle p_1,p_0,p_2, so that triangle is flat. The same argument, with each of the four vertices as the vertex opposite a diagonal midpoint, makes each triangle on three consecutive vertices flat. The angle at each corner of the quadrilateral is therefore \pi/2. The flat quadrilateral theorem [5, Theorem II.2.11] applies: the sum of these four angles is 2\pi. Its Euclidean quadrilateral has the prescribed sides and diagonals, and hence is a unit square.□

Proof. The four-cycle X_i,H,Y_i,H' has unit sides and diagonals of length \sqrt2, by the two-step assertions of Proposition 5.9. Lemma 6.1 makes it a flat square. Let J_i be its center, which is the midpoint of X_i,Y_i and also of H,H'.

The triangle c,H,H' is flat. Its median therefore gives

On the other hand, squared-distance convexity in the triangle c,X_i,Y_i has right-hand side

Thus this is also an equality, and c,X_i,Y_i is a flat triangle. Taking its midpoint in the tangent cone proves

Define M_i=2\log_c J_i; it has norm one. The left-hand side makes it independent of the full-line pair chosen. The cosine law gives \ip{x_i}{y_i}=-1/4. The pair h_H,h_{H'} has angular separation \arccos(-1/3)<\pi, and in its Euclidean sector

The same computation applies to h_{H'}.□

Proof. Apply the square construction in Lemma 6.2 at C, using H_0 and any other line through C. Since J is its center,

Also d(H_0,z)=1, d(c,z)=d(c,H_0)=r, and the two paths p,H_0,z and q,H_0,z give

The ternary midpoint conclusion of Proposition 5.9 states that the angle at H_0 between the segments to J,z is at least \pi/2. Angle comparison and Equation (6.9) therefore imply

The reverse inequality follows from the fact that J is the midpoint of p,q:

The angle and distance comparisons are consequently equalities. The triangle H_0,J,z is flat, with a right angle at H_0.

Let B_0 be the point of [J,z] at parameter 1/3 from J. Calculating in this right triangle gives

Squared-distance convexity toward c gives

The triangle inequality now reads

Hence every inequality is an equality. In particular, B_0 lies on [H_0,c], in that order, and the triangle c,J,z is flat by its interior comparison equality. Put j=\log_c J. In the Euclidean sector containing j,x_D, the vector to B_0 is (2/3)j+(1/3)x_D. The collinearity just proved and the distances d(c,H_0)=3d(c,B_0) therefore imply

Here the two ordinary additions take place in that Euclidean sector, and M_C=2j by Lemma 6.2.

The norm identity in this sector gives

so \ip{M_C}{x_D}=-1/2. Pairing the sector identity with either summand yields the remaining two products in Equation (6.8).□

Proof. Take either full line H at D. The path Y_D,H,X_D,H_0 uses two fields of F_D and the loose field, so it is one of the admissible three-step paths. Thus

Equality follows from the triangle inequality. The segment from Y_D to H_0 passes through c, and the directions of y_D,h_0 are antipodal.

Let \Sigma be the completed space of directions of Z at c, and use a hat for the direction of a nonzero vector. Define

Both lie strictly between zero and \pi/2, and 2a+b=\pi. Equation (6.8) gives

The two arcs occur consecutively in the Euclidean sector of Lemma 6.3; their concatenation is its geodesic direction arc. By Equation (6.5),

The direction of M_D=x_D\oplus y_D bisects this last arc, because its two summands have equal length. Consequently d_\Sigma(\widehat x_D,\widehat M_D)=a.

The concatenation \widehat h_0,\widehat x_D,\widehat y_D has length \pi and antipodal endpoints. It is therefore minimizing, so its two arcs continue geodesically through \widehat x_D. It follows that

is a local geodesic in \Sigma: continuation at \widehat h_0 holds inside the first sector, and continuation at \widehat x_D holds inside the minimizing semicircle just described. Its length is a+b+a=\pi. The space \Sigma is \CAT(1), so [5, Proposition II.1.4(2)] makes this local geodesic globally minimizing, including the endpoint case of length exactly \pi. Equivalently, apply the short local-geodesic assertion to every strict initial subarc and pass to the endpoint by continuity of distance. Its endpoints are antipodal. Since M_C,M_D have norm one, the cone distance and scalar product have the stated values.□

Proof. Suppose otherwise and retain the notation above. By Equation (6.6), \ip{M_A}{M_B}\geq0. We will contradict this bound by splitting the axis supplied by Lemma 6.4. Use the fan identities

The four lines in these expressions are pairwise distinct. Therefore Equation (6.2) implies

Lemma 6.4 forces equality in the chain

Interchanging the roles of the two sums gives the symmetric equalities. Combining these with Equation (6.5), we obtain

The opposite rays M_C,M_D form a complete geodesic line \ell\subset T through the cone vertex. Put a=\arccos(1/\sqrt3). For each vector in the four columns of Equation (6.10), the angles to the two ends of \ell are a and \pi-a, in one order or the other. The two corresponding direction arcs concatenate to a minimizing semicircle. Its Euclidean cone is an isometric flat half-plane with boundary \ell and containing the vector. In particular, that vector lies on a complete line parallel to \ell.

The parallel-set product decomposition [5, Theorem II.2.14] now applies in T; it requires no properness. Write its convex parallel set as

The factor Q is a \CAT(0) space. Within each of the flat half-planes above, projection onto \ell shows that the axial coordinate is the scalar product with the unit vector M_C. Thus Equation (6.10) gives

for points u,u',v,v'\in Q. Their distances to q_0 are all 1/\sqrt2, since each original vector has squared norm 3/4.

Distinct line vectors have squared cone distance two, by Equation (6.3). The product metric in Equation (6.11) therefore gives

and

Furthermore, h_{AC}\oplus h_{BC}=M_C means that the midpoint of these two line vectors is (1/2,q_0): the midpoint is the half-dilation of M_C on the axis. Product midpoints consequently give q_0=\operatorname{mid}(u,u'). The identity at D likewise gives q_0=\operatorname{mid}(v,v').

In cyclic order u,v,u',v', these points satisfy Lemma 6.1. They therefore span a unit flat square in Q, centered at q_0. Let

They are the midpoints of opposite sides of that square, and hence

This square lies in the transverse factor only; no planar realization of the original incidence configuration has been assumed. Figure 3 records the square and the axis that has been split off.

Finally, the full-line choices AC,AD at A and BC,BD at B give

Here \delta_2 is dilation in the original cone T; no cone structure on Q is needed. It doubles all distances. By Equation (6.12),

so \ip{M_A}{M_B}=-1. This contradicts Equation (6.6) and proves the proposition.□

Proof. At stage j, request all the admissible tests in the fixed master pattern with 1\le t\le j. This is a finite list. Choose \varepsilon_j>0 small enough for Proposition 4.5 for this list and for Theorem 3.1, with \varepsilon_j<1/(400j), and set

These parameters satisfy \beta_j>7\alpha_j, and the exponent 3-\beta_j-90\delta_j of the master count is positive. Moreover,

so the explicit bound in Section 4 preserves every overlap margin required for the finite list.

Fix these parameters. The proof of Theorem 3.1 selects a finite fragment threshold, possibly depending on j. Its coincidence inequalities hold with probability tending to one as n\to\infty. For the same fixed parameters, Proposition 4.5 gives the requested finite collection of sampling properties with probability tending to one. Choose n_j>n_{j-1} so large that there is positive probability that all these events hold and all requested sampling errors are at most 1/j. Select one realization in their intersection. No comparison between the fragment threshold and n is needed before fixing the parameters and threshold. This proves (i)–(iv).

Each G_j has a quotient C_2 by Lemma 2.3. If it were finite, its universal cover would be a finite contractible CW complex, and multiplicativity of Euler characteristic would give

Since \chi(P_j) is an integer, this forces |G_j|=1, contrary to the quotient. Hence G_j is infinite.□

Proof. Suppose, more generally, that infinitely many G_j admitted such actions. Restrict to that subsequence and choose one action for each of its groups. All fixed-test limits in Lemma 7.1 remain valid. The action spaces, their dimensions, and their local geometries are allowed to vary.

Normalize the minimizing generator energy for each action as in Equation (5.4). The infinitude just proved makes this energy positive. The displacement estimate and Lemma 5.4 hold uniformly for these choices of actions. Proposition 5.9 therefore supplies the limiting configuration. Proposition 6.5 excludes it. Thus only finitely many of the selected groups can admit such actions; in particular, an instance with no action exists.□

Proof. A finite CW complex has a finite simplicial homotopy model of the same dimension [10, Theorem 2C.5]. One construction proceeds over its finitely many cells: approximate attaching maps by simplicial maps after finite subdivisions, and use simplicial analogues of their mapping cylinders for the attachments. Let K be the resulting finite simplicial model. A homotopy equivalence lifts to a homotopy equivalence of universal covers, so \widetilde K is contractible.

For completeness, the linear estimate is independent of the chosen finite presentation. Choose substitutions \phi from new generators to old words and \psi from old generators to new words, inducing inverse group identifications. Let L bound the lengths of the words \phi(b), let M bound the new-presentation filling areas of the finitely many substituted old relators \psi(r), and let D bound the filling areas of the words b\psi(\phi(b))^{-1}. The latter two lists consist of null words, and all three lists are finite, so these bounds exist. A new null word of length \ell substitutes to an old word of length at most L\ell. If the old filling constant is C_{\rm old}, filling that word and replacing its relator cells costs at most MC_{\rm old}L\ell new cells. The boundary substitutions cost at most D\ell more. Thus the new filling constant is at most MC_{\rm old}L+D.

Apply this to the maximal-tree presentation of the finite complex K. Its generators correspond to the non-tree edges, and its relators to its triangular faces. A null-homotopic combinatorial edge loop in K of length \ell gives a null word of length at most \ell in these generators after inserting paths in the fixed maximal tree. The tree has finitely many edges, so the inserted paths have uniformly bounded lengths. Fill the word linearly in the maximal-tree presentation; each relator cell is replaced by the corresponding triangular face and tree-path cancellations. The boundary collar likewise cancels the inserted tree paths with linear overhead. Thus the original loop bounds a diagram over K with at most C\ell triangular faces for a fixed finite C.

An edge loop in \widetilde K projects to a null loop in K. Its disk diagram lifts with the chosen boundary lift, giving the required estimate in the universal cover.□

Proof of Theorem 1.1. Choose an instance P_j supplied by Proposition 7.2. Its finite letter presentation has a linear disk bound by Theorem 3.1. Apply Lemma 7.3 to obtain K. Since P_j has dimension two, the same-dimension construction gives a two-dimensional K. This proves the asserted asphericity and linear filling estimate. Its fundamental group is G_j, so it has the no-action property. The equivalence between a linear Dehn function and word hyperbolicity gives the final group-theoretic assertion [5, Exercise III.H.2.5(5), Proposition III.H.2.7, and Theorem III.H.2.9].

Suppose that a finite simplicial complex L homotopy equivalent to K admitted a compatible locally \CAT(0) geodesic length metric. The metric space L is compact, hence complete and locally compact. Give its universal cover the induced length metric, for which the covering map is a local isometry [5, Proposition I.3.25]. This cover is complete: a Cauchy sequence upstairs projects to a convergent sequence downstairs; sufficiently short connecting paths force a tail into one sheet over an evenly covered neighborhood of the limit, where it converges. The Cartan–Hadamard theorem makes the cover globally \CAT(0) [5, Theorem II.4.1(2)]. It is locally compact, and the length-space Hopf–Rinow theorem makes it proper [5, Proposition I.3.7]. Its deck transformations act freely, properly and cocompactly by isometries.

The isomorphism \pi_1L\cong\pi_1K=G_j therefore gives a geometric action of G_j on a proper complete \CAT(0) space, a contradiction. This also excludes compatible locally \CAT(-1) geodesic length metrics, since a \CAT(-1) space is \CAT(0) [5, Theorem II.1.12(1)].□