betaFeedback

WorksMathematics

A hyperbolic group with no geometric CAT(0) action

Abstract

We construct a hyperbolic group with a finite classifying space that admits no geometric action on a proper complete CAT(0) space. Consequently, a finite aspherical simplicial complex with a linear combinatorial disk-filling inequality need not have a finite locally CAT(0) homotopy model, and hence need not have a finite locally CAT(−1-1) model. Here metric models carry geodesic length metrics inducing the given complex topology.

Introduction

A linear isoperimetric inequality is a large-scale expression of negative curvature: for finitely presented groups, it characterizes word hyperbolicity. Local comparison geometry is more restrictive. The geometric realization question asks whether every hyperbolic group admits a geometric action on a proper CAT(0) space, or on a proper CAT(−1-1) space. We construct a group for which neither action exists.

Throughout the paper, a geometric action is a proper, cocompact action by isometries, and metric models of finite complexes carry geodesic length metrics inducing the given complex topology.

Theorem 1.1. There exist a finite connected two-dimensional aspherical simplicial complex KK and a constant C<∞C < \infty with the following properties.

(i) Every combinatorial edge loop of length ℓ\ell in the universal cover of KK bounds a disk diagram with at most CℓC\ell triangular faces.

(ii) The group π1K\pi_1 K admits no geometric action on a proper complete CAT(0) space.

In particular, π1K\pi_1 K is word-hyperbolic, and no finite simplicial complex homotopy equivalent to KK admits a locally CAT(0) geodesic length metric inducing its given topology. Consequently, no such model admits a compatible locally CAT(−1-1) geodesic length metric.

The proof is an existence argument and does not give an effective size for KK. The filling constant may depend on the selected finite presentation.

Context

The realization problem goes back to the development of hyperbolic groups. In his account of that development, Gromov recalls introducing linear isoperimetry as a group-theoretic form of negative curvature and then spending years seeking geometric realizations by negatively curved spaces [17] (p. 396). The equivalence between linear filling and word hyperbolicity became part of the foundational theory [8]; see also [5] (Theorem III.Γ.2.6 and Remark III.Γ.2.7(2)). The CAT(−1-1) realization question appears as Problem H11 in Baumslag–Myasnikov–Shpilrain’s 1999 problem list [3]. Both the CAT(−1-1) and CAT(0) questions appear as open problems in Stark’s 2025 survey [18] (Open Problem 2.15) and in the March 2026 preprint of Duchesne–Simon [6], Question W.

There are several successful ways to obtain such geometric actions. Finitely generated free groups act on trees and closed hyperbolic manifold groups act on hyperbolic space. More generally, a finite complex carrying a locally CAT(−1-1) or locally CAT(0) geodesic length metric inducing its topology has a universal cover with the corresponding global curvature bound; its deck action is geometric [5] (Theorem II.4.1). Cubulation provides another route to CAT(0) models. For example, Ollivier–Wise prove that random groups in the density model at density less than 1/61/6 act freely and cocompactly on CAT(0) cube complexes with probability tending to one as relator length grows, with the number of generators fixed [16] (Theorem 10.4.1). Thus random presentations can produce geometric CAT(0) actions as well as hyperbolicity; the relations used here must enforce an additional obstruction.

Dimension restrictions already yield obstructions. Brady–Crisp [4] (Theorem 2) construct infinitely many torsion-free hyperbolic groups of geometric dimension two which admit no proper isometric action on a proper two-dimensional CAT(0) space. Their Theorem 1 gives a hyperbolic group of CAT⁡(0)\operatorname{CAT}(0) dimension two and CAT⁡(−1)\operatorname{CAT}(-1) dimension three. These conclusions rely on constraints on translation lengths in two-dimensional targets. Theorem 1.1 excludes geometric CAT⁡(0)\operatorname{CAT}(0) actions in every dimension. Its finite-model consequence also allows the entire simplicial complex to change within its homotopy type: any compatible locally CAT⁡(0)\operatorname{CAT}(0) geodesic length metric on such a model would recover a geometric action by passing to the universal cover.

Random-presentation proofs of hyperbolicity combine counting for bounded diagrams with a local-to-global argument. Our treatment of repeated relator occurrences is related to the multiplicity and constraint methods in Ollivier [15], Section 2.2] and Antoniuk–Friedgut–Łuczak [1], Section 3]. Within each finite presentation we first sample small labelled graphs, then larger labelled graphs whose required small graphs have already been selected. The same prerequisite can support several larger graphs, so its probability cost must be charged only once. Section 3 proves the resulting estimate directly.

The obstruction to actions uses the harmonic-energy framework of Gromov [9], Sections 3.3 and 3.7] and Izeki–Nayatani [12]. In this framework, expansion in a finite graph can force a fixed point when the target satisfies a suitable nonlinear spectral inequality. The target hypothesis matters: Izeki–Kondo–Nayatani obtain random hyperbolic groups with fixed-point properties for target classes whose tangent-cone invariant is bounded by a prescribed constant strictly less than one [11], Corollary 3.8]. Toyoda [20], Theorem 1.4] supplies such spectral bounds for a prescribed finite family of geodesically complete CAT⁡(0)\operatorname{CAT}(0) spaces admitting proper cocompact actions, with constants depending on that family. Here a hypothetical target and its action can be chosen after the finite presentation is known. We obtain the required uniformity from bounds on every generator displacement and total-variation couplings of table matches. Sturm’s inductive means [19], Definition 4.6 and Theorem 4.7, proof (a)] then turn those couplings into the averaging estimate used in the energy argument.

Structure of the proof

The construction must satisfy two requirements: its relations must be sparse enough to preserve hyperbolicity and asphericity, yet impose enough metric constraints to exclude geometric actions on proper CAT⁡(0)\operatorname{CAT}(0) spaces. We organize the relations using a fixed modification of the incidence graph of the projective plane over F2\mathbb{F}_2. Four point vertices are doubled. At one of them we omit one incidence and keep its counterpart at the other representative separate. The remaining edges over each point form a small connected graph, called a fan. We call the resulting incidence graph the core. Edges receive signed generator labels, and every closed walk in a selected labelled graph gives a relation. Fans are selected first; a labelled copy of the whole graph is selected only when its seven fan restrictions have already been selected. We study copies for which further four-letter relations close every nonbacktracking two-edge core path to a square. An independent collection of six-letter relations will control individual generator displacements. A labelled core copy together with one chosen square completion for every nonbacktracking two-edge core path is a match.

We choose a sequence of such finite presentations, with progressively stronger finite counting requirements. At each stage, a finite list of statistical tests is fixed before choosing the sampling parameters; those parameters then remain fixed while the alphabet grows. If infinitely many of their groups admitted geometric actions on proper complete CAT⁡(0)\operatorname{CAT}(0) spaces, choose one action for each of those groups. The closed-walk relations realize the fixed graph by orbit points in every chosen action. After normalizing the average squared generator displacement, products of these configurations have a limiting configuration in a complete CAT⁡(0)\operatorname{CAT}(0) space. The counting requirements force exact metric identities in that limit, and a finite geometric contradiction excludes it. Thus every sufficiently late group in the chosen sequence admits no such action. The argument uses the following three ingredients.

  1. A positive deficit in diagram counting. A fan shared by several copies of the whole graph supplies only one random table entry, so its probability cost must be counted once. At the same time, a disk or sphere diagram may use the same relation many times. We reconcile these two counts by assigning multiplicity weights to distinct table entries. Local incidence estimates at vertices then leave a positive multiple of the diagram’s area to be paid by its boundary. This is first proved for bounded fragments. Planar separators extend it to all diagrams, yielding both a linear filling inequality and asphericity in Section 3.

  1. Sampling that is uniform over later actions. The metric argument compares a bounded function of one or two edge labels with a further edge label. The relevant tuples need not have dense projections in the sampled tables. Instead, we couple several matches so that the conditioning labels agree, each match is approximately uniform among all matches, and the further labels are approximately independent uniform generators. Section 4 obtains this coupling by gluing copies along an enlarged conditioning tuple and proving concentration of the numbers of extensions. The enlargement is chosen by counting exponents so that every further collection of label positions has a strictly positive margin. The conclusions concern total variation of finite probability laws. They therefore apply to bounded tests from any action chosen after the tables are revealed. The common conditioning tuple may still depend on the further labels; the averaging estimate allows this dependence. The six-letter relations supply the uniform displacement bound that makes these tests bounded.

  1. A rigid configuration and incompatible scalar products. Energy minimization and the coupling yield lower bounds for squared orbit distances along short paths. In the limit, the decoration squares force squared two-step distances to equal two. The six-cycles through three noncollinear point vertices then have a common center, and their central triangles are flat (Section 5). The doubled points give four unit vectors obtained by doubling certain midpoints in the tangent cone at that center. The line incidences force two of these vectors to have nonnegative scalar product. A three-field test involving the separated incidence edge forces the other two vectors to be antipodal. Splitting the parallel set of the resulting line exposes a flat square in the transverse factor, which makes the first pair antipodal as well. Their scalar product is consequently −1-1, the contradiction in Section 6.

Section 2 defines the finite graph and its random tables. Section 7 makes the finite-test selection precise and transfers one resulting finite classifying complex to the simplicial model in Theorem 1.1. Its filling constant may depend on that chosen presentation.

Conventions

A disk diagram may have boundary spurs or edges collapsed to the target’s 1-skeleton; such features have zero area and can be removed. Its area is the number of its noncollapsed 2-cells. Constants in filling estimates may depend on a fixed finite presentation. A statement holds with high probability if its probability tends to one as the alphabet size tends to infinity, with all parameters in that statement fixed. Finite-test limits and the final diagonal selection will always be distinguished.

We use completed tangent cones and completed spaces of directions. The latter are CAT⁡(1)\operatorname{CAT}(1) and the former are CAT⁡(0)\operatorname{CAT}(0) [5], Theorem II.3.19]. For the tangent-cone construction in this generality, see also Kleiner–Leeb [13], Section 2.1.3, who credit Nikolaev’s tangent-cone theorem. Subsequent products and limits need not be proper; properness is used only for the original geometric actions. Standard comparison, covering-space and topological results are cited with the hypotheses needed here. All estimates specific to the new construction are proved below.

The incidence template and the nested tables

We begin with the fixed finite combinatorics. All randomness will be in the labels, not in the template.

Points, lines, and fans

Definition 2.1 (The incidence template). Identify the points of the projective plane over F2\mathbb{F}_2 with the seven nonzero vectors of F23\mathbb{F}_2^3. A line consists of the three nonzero vectors in a two-dimensional subspace. Fix

A=e1,B=e2,C=e3,D=e1+e2+e3.A=e_1,\qquad B=e_2,\qquad C=e_3,\qquad D=e_1+e_2+e_3.

No three of these four points are collinear. For distinct points i,ji,j, write ijij for their line.

The bipartite graph Γ\Gamma has a vertex XiX_i for every point, an additional vertex YiY_i for i∈{A,B,C,D}i\in\{A,B,C,D\}, and a vertex for every line. Both representatives over a point are joined to each incident line, with one exception: the edge YDY_D–CDCD is omitted. The edge

e0=XD–CDe_0=X_D\text{--}CD

is called the loose edge. Every other edge belongs to the fan FiF_i at its point ii. At DD, the fan uses only the two lines other than CDCD, so CDCD is not a vertex of FDF_D.

Each FiF_i is connected. At A,B,CA,B,C it is K2,3K_{2,3}, at DD it is K2,2K_{2,2}, and at each of the other three points it is a three-edge star. Let g=7g=7 and ki=∣E(Fi)∣k_i=|E(F_i)|. Thus

(ki)i=(6,6,6,4,3,3,3),∑iki=31,∣E(Γ)∣=32.(k_i)_i=(6,6,6,4,3,3,3),\qquad\sum_i k_i=31,\qquad|E(\Gamma)|=32.

The graph has 18 vertices. Its cycle rank is 15; the sum of the cycle ranks of the fans is 7. We will first impose the cycles within the fans, then use a smaller graph of cycle rank 8 to impose the remaining core relations. The cone construction below makes this decomposition explicit.

Figures 1 and 2 show the incidence pattern and the exceptional fan.

Choose an orientation for each edge once and for all. A field is an edge position in a template or a position in a polygon word. An assignment gives one signed letter to each field. A walk reads that letter in the specified orientation and its inverse in the other orientation. The fields are bookkeeping coordinates; they all take values in the same alphabet.

A core hexagon is the six-cycle obtained from three noncollinear points, the three lines joining them, and one representative over each point for which all six incidences are present. In particular, the all-XX choice is always permitted. Any three successive edges of a core hexagon contain at most two fields from each fan; the loose field, if present, belongs to no fan.

The seven points and seven lines of the Fano plane

Figure 1. The seven points and seven lines of the Fano plane. The three sides, three medians, and dashed circle each represent one projective line; only marked dots represent projective points. The points AA, BB, CC, D=A+B+CD = A + B + C form a quadrangle: no three are collinear. The thick median is the line CD={C,D,A+B}CD = \{C, D, A + B\}, at which the incidence graph is modified.

A full fan and the exceptional fan

Figure 2. A full fan and the exceptional fan. The blue edges and their endpoints form the indicated fans. The loose edge e0=XDe_0 = X_D–CDCD belongs to Γ\Gamma but not to FDF_D; the crossed dashed segment YDY_D–CDCD is absent from Γ\Gamma. In particular, CDCD is not a vertex of FDF_D. The two occurrences of CDCD denote the same line vertex of Γ\Gamma.

The independent tables

For n≥1n \ge1, let

Sn={a1,a1−1,…,an,an−1},N=2n.S_n = \{a_1, a_1^{-1}, \ldots, a_n, a_n^{-1}\}, \qquad N = 2n.

These are formal signed letters; assignments are not required to use distinct letters or to produce freely reduced words. Let

f=2−α,p=3−β,0<α,δ<1,7α<β<1.f = 2-\alpha,\qquad p = 3-\beta,\qquad0 < \alpha,\delta< 1,\qquad7\alpha< \beta< 1.

Additional smallness requirements will be imposed when we choose finitely many sampling tests.

Definition 2.2 (The tables). Use the following mutually independent Bernoulli arrays.

  • (i) For each point ii, an array indexed by SnE(Fi)S_n^{E(F_i)} includes every tuple with probability Nf−kiN^{f-k_i}. An included tuple, together with its type ii, is a fan occurrence bb.

  • (ii) An array indexed by SnE(Γ)S_n^{E(\Gamma)} marks every full core tuple with probability Np−gf−1N^{p-gf-1}. A top occurrence aa is a marked tuple whose restriction to every FiF_i is an included fan occurrence. We write a→ba \to b when bb is the fan in one of the seven slots of aa.

  • (iii) For each unoriented nonbacktracking two-edge path τ\tau in Γ\Gamma, choose one order and direction. Give τ\tau a separate four-field array: its first two coordinates are the two core fields on τ\tau, and its last two are new coordinates. Include each row with probability N−2−δN^{-2-\delta}. Its relator reads τ\tau, with the required orientation signs, followed by the two new letters around a closing path.

  • (iv) A separate six-field array includes each word in Sn6S_n^6 with probability N−3−δN^{-3-\delta}. Its word is a relator.

All included rows in (iii) and (iv) are imposed, not only rows matching some top occurrence. We call them decorations; their lengths are 2h2h, with h∈{2,3}h \in\{2,3\}.

There is no ambiguity from opposite path directions: reversing one chosen convention simply inverts or reorders the corresponding coordinates, preserving the Bernoulli law. There are 90 tables in Definition 2.2(iii). Indeed, the eleven point-representative vertices contribute 10(32)+(22)=3110\binom{3}{2}+\binom{2}{2}=31 two-edge paths; the line degrees are 5,5,4,5,5,5,35,5,4,5,5,5,3, contributing 59 more.

The exponents in Definition 2.2 are negative. In particular,

p−gf−1=−12−(β−7α)<0.p-gf-1=-12-(\beta-7\alpha)<0.

Each is therefore a valid probability. Distinct numerical tuples of a fixed table are independent. Top occurrences are correlated because they may share fan slots; top marks remain independent.

The expected counts explain the normalization of these probabilities. For each fan type there are NkiN^{k_i} candidate tuples, so the expected number of included fans is NfN^f. A fixed core tuple requires its mark and seven independent fan entries. Since the fans contain 31 fields in total, the expected number of top occurrences is

N32Np−7f−1∏iNf−ki=Np.N^{32}N^{p-7f-1}\prod_i N^{f-k_i}=N^p.

Each square table has expected size N2−δN^{2-\delta}, and the six-letter table has expected size N3−δN^{3-\delta}. Thus the expected exponents are just below 2 for fans and squares, and just below 3 for tops and hexagons. Section 3 explains how these deficits, together with β>7α\beta>7\alpha, leave a positive margin in the diagram estimates. The correlation between top occurrences is the reason that their shared fan costs must be counted only once.

The group and its two-complex

The letter presentation has the generators a1,…,ana_1,\ldots,a_n. For each included fan and each top occurrence, impose the labels of all closed walks in its graph. Impose also the decoration words. This is a finite presentation: in each connected graph a fixed spanning tree supplies a finite basis of closed walks that suffices.

For the diagram arguments we use a specific finite two-dimensional CW complex PP. Start with the letter bouquet, with vertex oo. For each fan occurrence bb of type ii, attach the cone on FiF_i along its labelled map to the bouquet. The cone apex is a new vertex, also denoted bb. For each vertex vv of FiF_i, its radial edge rb,vr_{b,v} joins bb to the image oo of vv. Every fan edge gives one triangle with one letter side and two radial sides. Different radial edges can have the same endpoints; they retain their distinct labels vv.

The fan cones already fill all fan cycles. To impose the remaining relations of a top occurrence aa, take the ordinary Fano incidence graph and subdivide the edge DD–CDCD once. Call the resulting graph BB. It has 15 vertices and 22 edges, hence cycle rank 8, matching the difference 15−715-7 computed above. Map a point vertex ii to the apex of the fan in slot ii of aa, and map all line vertices and the subdivision vertex to oo. An ordinary incidence at ii maps to the radial edge indexed by its line. The subdivided exceptional incidence maps to

rbD,XDr_{b_D,X_D} followed by the loose letter edge,

with the orientation giving the path from XDX_D to CDCD. Attach the cone on this mapped graph, with its own new apex. We call its radial triangles top triangles. Finally attach every decoration polygon. All these attachments are finite, and PP has dimension two.

Lemma 2.3 (Presentation equivalence). The complex PP has the fundamental group of the letter presentation above. In particular, it has a quotient isomorphic to C2C_2.

Proof. For a connected graph HH and a map H→XH \to X into a connected complex, attaching its cone changes π1X\pi_1X by the normal closure of the image of π1H\pi_1H. It introduces no extra generator. This follows from van Kampen, or by choosing a spanning tree of HH 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 XiX_i or YiY_i then cancel, leaving a closed walk in the mapped macro graph. At DD, the only unreplaced edge is the loose edge; together with rbD,XDr_{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 C2C_2 respects all the defining relations and is surjective. □\square

Remark 2.4. The cone description records occurrences, not just relator words. If the same fan occurs in several tops, its cone is attached only once. A top occurrence has its own cone, and a decoration occurrence has its own disk. These distinctions are essential in the multiplicity count of Section 3.

The master pattern and admissible tests

Define the finite master pattern M\mathcal{M} by taking one top occurrence with its seven fan slots and, for each of the 90 two-edge paths, one matching row of its square table. The two core coordinates of that row are identified with their core fields; its two closing coordinates are new. The separate six-letter array is not part of M\mathcal{M}.

A match is an assignment to the fields of M\mathcal{M} for which every required table entry is present, including the top mark. We denote the set of matches by Ωn\Omega_n. When it is nonempty, it carries its uniform probability measure. Its 32+2⋅9032 + 2 \cdot90 fields include the shared core fields only once.

Definition 2.5 (Admissible fields). A set of fields is admissible if it is either

(i) a set of at most three distinct core fields containing at most two fields of each fan, or

(ii) a set of at most two fields of a single square decoration in M\mathcal{M}.

The loose core field does not count against any fan quota.

The first case includes all three-edge half-paths of core hexagons. It also includes two FCF_C fields together with the loose field, the combination that will produce the decisive midpoint identity. The second case includes every two-edge half-path in a decoration square.

Every match has a labelled realization of the core graph and the closing paths of its square decorations in the group: fix an anchor, and label a vertex by the word read along any path from the anchor. All closed-path labels are trivial by Lemma 2.3 and the square relators. Consequently this group-valued vertex assignment is independent of the chosen path. For any action and basepoint, it gives a corresponding configuration of orbit points.

Diagrams and linear filling

This section proves the combinatorial properties of the random complex PP of Section 2. An occurrence means an included tuple, together with its table type; copies of a cell in a diagram need not be distinct occurrences. All constants in this section may depend on the fixed incidence template and on the fixed parameters, but not on nn.

Theorem 3.1. Fix sufficiently small positive α,β,δ\alpha,\beta,\delta with β>7α\beta> 7\alpha, and put f=2−αf = 2 - \alpha and p=3−βp = 3 - \beta. As n⟶∞n \longrightarrow\infty, the probability tends to one that PP is aspherical and its letter presentation satisfies a linear disk isoperimetric inequality.

The central estimate will bound the number of faces in a bounded piece of a normalized diagram by the number of its exposed sides. The expected occurrence counts in Section 2 have exponents 2−α2 - \alpha, 3−β3 - \beta, and h−δh - \delta for fans, tops, and decorations of length 2h2h. The local incidence geometry compares these with the values 22, 33, and hh. After shared fan costs have been accounted for, the differences α\alpha, β−7α\beta- 7\alpha, and δ\delta supply the strictly positive margin in the boundary estimate.

We first obtain a probability bound for every bounded collection of distinct occurrences. We then normalize disk and sphere pictures so that this bound also controls repeated copies of their cells. The resulting estimate applies to arbitrary sets of faces, which lets us partition a large picture by planar separators and sum the bounds on its pieces. The same estimate proves linear filling for disks and rules out nonzero two-cycles in the universal cover.

We retain every fan slot of a top occurrence when making a collection of occurrences, even if a diagram uses only some of those slots. This convention is essential to the counting argument.

Coincidence ranks

Counting constraints while retaining repeated relator occurrences is standard in random-group diagram arguments; see Ollivier [15], Section 2 and Antoniuk–Friedgut–Łuczak [1], Section 3. We count the shared fan entries explicitly in the estimate below.

For a finite collection of top, fan, and decoration occurrences, its field positions are the following: the loose field of each top, the kik_i fields of each fan occurrence of type ii, and all fields of each decoration occurrence. A fan field is included only once when the same fan occurrence occupies slots in several tops. The unsigned coincidence rank RR is the number of positions minus the number of distinct underlying generators represented at those positions. Thus a letter and its inverse have the same unsigned value.

Lemma 3.2. For each fixed integer MM, with probability tending to one the following holds simultaneously for every collection of at most MM distinct occurrences that contains all fan slots of its tops. If the collection has ss tops and uu fans, then

R≤(p−7f)s+fu+∑e(he−δ),R \le(p-7f)s+fu+\sum_e(h_e-\delta),

where the sum is over its decorations and 2he∈{4,6}2h_e\in\{4,6\} is the length of decoration ee.

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 MM. Write JJ for the number of positions. Assigning letters to a pattern of rank RR has at most CMNJ−RC_MN^{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 MM.

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 NN with exponent

(p−7f−1)s+∑b(f−kb)+∑e(he−δ−2he).(p-7f-1)s+\sum_b(f-k_b)+\sum_e(h_e-\delta-2h_e).

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

CMN(p−7f)s+fu+∑e(he−δ)−R.C_MN^{(p-7f)s+fu+\sum_e(h_e-\delta)-R}.

If (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.

Spherical pictures and their reductions

[3] counts distinct occurrences, whereas a filling diagram may use the same occurrence many times. We normalize the diagram in two ways: the triangles incident to each top apex will be grouped into polygons tracing simple macro cycles, and the cyclic link at a fan apex will have no repeated radial label. These properties will bound how often a field can appear near each apex. For the asphericity argument, the normalization must also preserve a prescribed lifted two-cycle.

An elementary picture is a finite collection of oriented polygons with orientation-reversing pairings of their sides, such that the resulting closed oriented surfaces are spheres. Vertex links are taken to be circles, with a separate source vertex for each link circle. An interior face maps to a fan triangle, a triangle of a top cone, or a decoration disk of PP, with either orientation. In the disk problem there is one distinguished outside polygon whose boundary reads the prescribed letter word; no extension of its interior to PP is required. In the sphere problem there is no outside polygon. Collapsed regions mapping to vertices and free cancellations of edge paths have zero face cost. They can equivalently be recorded by thickening the paired sides to strips and capping the boundary circles of the resulting vertex regions.

Every cell has a specified map to PP, including the index of each of its sides. Equal edge labels alone do not identify two side indices. For a picture mapped to P~\widetilde{P}, its cellular chain is the sum of its signed lifted two-cells; the outside polygon is omitted.

Lemma 3.3. Every null letter word has a disk picture. If c≠0c \ne0 is a cellular two-cycle of P~\widetilde{P}, there is a finite collection of spherical pictures with total cellular chain exactly cc.

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 P~\widetilde{P} is simply connected, the Hurewicz map π2(P~)⟶H2(P~;Z)\pi_2(\widetilde{P}) \longrightarrow H_2(\widetilde{P};\mathbb{Z}) is an isomorphism [10]. There are no three-cells. Consequently a sphere map representing the class of cc has cellular two-chain equal to cc, 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 cc 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.

At a vertex mapping to the apex of a top cone, every incident face is a triangle of that cone. Grouping its incident triangles gives a polygon whose boundary is a closed walk in the macro graph of that top occurrence. We call it a top polygon; its filling in PP is always the indicated radial cone filling. Its perimeter is the number of these cone triangles. The other interior faces remain fan triangles and decoration disks.

The macro graph is the Fano incidence graph with one subdivided edge. It has fifteen vertices. A simple macro cycle has at most fifteen sides, visits each point at most once, and visits at least three points. At a point it turns between two distinct ports, namely the radial labels of the fan there. The ports are the incident line vertices, except that the exceptional port at DD is XDX_D.

Lemma 3.4. A null letter word has a picture of minimum total top perimeter and, subject to this, minimum number of remaining interior faces, with the following properties. The same assertion holds for a fixed nonzero cellular two-cycle cc, minimizing among finite collections of sphere pictures whose total lifted cellular chain is exactly cc.

  1. Every top polygon is a simple macro cycle.

  1. Adjacent top polygons do not use the same side of the same top occurrence. Two copies of one fan triangle cannot be adjacent along equally indexed sides, and two copies of one decoration cannot be adjacent along the same position of that decoration.

  1. At each fan-apex instance, the cyclic list of radial labels has no repetition. A circuit with two distinct parallel steps is permitted. Each such circuit has at most five steps. If it contains no top turn, it has at least four fan triangles.

The modifications establishing these properties preserve the outside word and, in the sphere problem, the exact lifted cellular chain.

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 cc 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 vv mapping to a fan apex bb. A step in its link is either a fan triangle or a corner of a top polygon. Suppose two different outgoing spokes at vv have the same radial label. Each spoke is an edge from vv 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 vv agreeing. This preserves the orientation of every face and all face maps. In terms of vertex-link cycles, it splits the link cycle of vv 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 Pˉ\bar{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.

The outside word uses only letter edges, so an outside polygon never meets a fan-apex instance. In particular each full link considered in Lemma 3.4 is a cyclic link of interior faces.

Weights on a bounded fragment

Fix a normal picture. A fragment is any selection of its interior faces; the selection need not be connected or simply connected. Keep a pairing of sides precisely when both incident faces are selected. All other selected sides are fragment boundary sides. Let T,Q,ET,Q,E be the numbers of selected top polygons, fan triangles, and decoration disks, respectively, and put A=T+Q+EA=T+Q+E.

For a top occurrence aa let tat_a be its number of selected top polygons, and for a decoration occurrence ee let tet_e be its selected multiplicity. At a fan-apex instance zz represented in the fragment, let dzd_z count selected top turns and qzq_z count selected fan triangles. It is partial if not every step of its full cyclic link is selected.

For a fan occurrence bb, two multiplicities must be distinguished. The number of represented apex instances bounds the actual use of each fan field. We must also retain this fan whenever we retain a top of sufficiently large multiplicity that requires it. The fan weight must therefore dominate the largest such top multiplicity. Write

rb=#{z:z is represented over b},mb=max⁡a→bta,Sb=∑a→bta,wb=max⁡{rb,mb}.r_b=\#\{z:z\text{ is represented over }b\},\qquad m_b=\max_{a\to b}t_a,\qquad S_b=\sum_{a\to b}t_a,\qquad w_b=\max\{r_b,m_b\}.

Empty maxima are zero. All fan slots of every selected top are included in these definitions, whether or not a polygon of that top visits the fan. In particular

∑bSb=7T.\sum_b S_b=7T.

Write IbI_b for the number of partial instances over bb, and let Pb∗P_b^* count the selected loose top sides belonging to turns at this fan. This number is zero unless bb has type DD. Each such loose side records one incidence with the exceptional radial port XDX_D.

Let II count internal contacts between two letter sides of the fragment. Radial side contacts are not counted in II. Denote the numbers of letter and radial fragment boundary sides by BrawB_{\mathrm{raw}} and BradB_{\mathrm{rad}}, and put B=Braw+BradB=B_{\mathrm{raw}}+B_{\mathrm{rad}}.

We first use the coincidence bound to control internal letter contacts. The remaining estimate is local at fan apices: full links contribute no error, while partial links contribute an error paid by radial boundary sides. Combining the two estimates will bound the fragment’s area by its total boundary length.

Lemma 3.5. Suppose Equation (3.1) holds for collections of at most 8A occurrences. Then

I≤pT+f∑b(wb−Sb)+∑e(he−δ)te.I \le pT + f\sum_b (w_b-S_b) + \sum_e (h_e-\delta)t_e.

Proof. Give each fan field of bb weight wbw_b, each loose field of aa weight tat_a, and each field of a decoration ee weight tet_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 rbr_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≥1j \ge1, apply Equation (3.1) to the positions of weight at least jj. This is an eligible collection: ta≥jt_a \ge j implies wb≥mb≥ta≥jw_b \ge m_b \ge t_a \ge j for every slot a→ba \to b. Its size is at most 8A8A, since there are at most TT distinct tops, at most 7T+Q7T+Q fans, and at most EE decorations. Sum the resulting inequalities over jj. Within an unsigned-value class, the sum of its ranks is its total weight minus its largest position weight. Thus, writing CC for the unsigned-value classes, we obtain

∑C∈C(∑v∈Cwt⁡(v)−max⁡v∈Cwt⁡(v))≤(p−7f)T+f∑bwb+∑e(he−δ)te.(1)\sum_{C\in\mathcal{C}}\left(\sum_{v\in C}\operatorname{wt}(v)-\max_{v\in C}\operatorname{wt}(v)\right) \le(p-7f)T+f\sum_b w_b+\sum_e(h_e-\delta)t_e. \tag*{(1)}

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 CC, 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 II is bounded by the left side of Equation (1). Using Equation (3.2) on its right side gives Equation (3.3).

This argument allows arbitrary cycles and repetitions in the contact graph. It charges side copies, and does not require the contacts to form a forest.

Lemma 3.6. For every fan occurrence bb in a fragment,

∑z↦bdz+2(wb−Sb)≤12(∑z↦bqz+Pb∗)+2Jb.(2)\sum_{z\mapsto b} d_z + 2(w_b-S_b) \le\frac{1}{2}\left(\sum_{z\mapsto b}q_z+P_b^*\right)+2J_b. \tag*{(2)}

Moreover

2∑bJb≤Brad.(3)2\sum_b J_b \le B_{\mathrm{rad}}. \tag*{(3)}

Proof. First suppose wb=rbw_b=r_b. A simple top polygon has at most one turn at this fan, so Sb≥∑z↦bdzS_b \ge\sum_{z\mapsto b}d_z. Consequently the left side of Equation (2) is at most ∑z↦b(2−dz)\sum_{z\mapsto b}(2-d_z). For a full link with dz=0d_z=0, at least four fan triangles give the required inequality. For a full link with dz=1d_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 XDX_D; it may have one edge, in which case its top turn has the loose side counted by Pb∗P_b^*. Thus in either case its triangle count plus its loose-side payment is at least two. For dz≥2d_z \ge2 the expression 2−dz2-d_z is nonpositive. At a represented partial link with dz=0d_z = 0 there is at least one selected fan triangle, so its deficit is at most 3/23/2. With dz=1d_z = 1 its deficit is at most one, and with dz≥2d_z \ge2 it is nonpositive. Thus the error 2Jb2J_b suffices in this case.

Now suppose wb=mb>rbw_b = m_b > r_b, and choose a top occurrence a0a_0 with ta0=mbt_{a_0} = m_b. Call its turns dominant. Let xx and yy be the total numbers of selected dominant and nondominant turns over bb. Nondominant selected faces have at most one turn each at this fan, including when other selected faces omit the fan entirely; hence y≤Sb−mby \le S_b - m_b. It follows that

∑z↦bdz+2(mb−Sb)=x+y−2(Sb−mb)≤x−y.\sum_{z \mapsto b} d_z + 2(m_b-S_b) = x+y-2(S_b-m_b) \le x-y.

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 a0a_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 kk and ll be the numbers of dominant and nondominant turns. Their linear turn list has at most l+1l+1 blocks of dominant turns. Consequently, if HH counts its consecutive dominant-to-dominant interfaces, then

H≥k−l−1,k−l≤H+1.H \ge k-l-1,\qquad k-l \le H+1.

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 a0a_0 once for the entire fan occurrence bb, and apply these estimates separately at all its apex instances. They do not require the fragment to be connected, or every selected polygon of a0a_0 to visit this fan. Summing the partial- and full-link estimates, and then using Equation (3.7), proves Equation (2) 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).

Lemma 3.7. Put

κ=min⁡{β−7α,α/5,δ}>0.\kappa= \min\{\beta- 7\alpha, \alpha/5, \delta\} > 0.

If (3.1) holds for collections of at most 8A occurrences, then every fragment of area AA satisfies

A≤C0B,C0=1κ.A \le C_0B,\qquad C_0 = \frac{1}{\kappa}.

Proof. Write W=∑bwbW = \sum_b w_b and P∗=∑bPb∗P^* = \sum_b P_b^*. Every simple top polygon has at least three turns. Summing (2), and using (3.2), gives

3T+2(W−7T)≤Q+P∗2+2∑bJb.3T + 2(W - 7T) \le\frac{Q + P^*}{2} + 2\sum_b J_b.

The right side of (3.3) can be written as

3T+2(W−7T)+∑ehete−Δ,Δ=(β−7α)T+αW+δE.3T + 2(W - 7T) + \sum_e h_e t_e - \Delta,\qquad\Delta= (\beta- 7\alpha)T + \alpha W + \delta E.

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

Δ≥κ(T+Q+E)=κA.\Delta\ge\kappa(T + Q + E) = \kappa A.

The total number of raw side copies in the fragment is

Rraw=Q+P∗+∑e2hete.R_{\mathrm{raw}} = Q + P^* + \sum_e 2h_e t_e.

Equations (3.3) and (3.10) imply

I≤Rraw2−Δ+2∑bJb.I \le\frac{R_{\mathrm{raw}}}{2} - \Delta+ 2\sum_b J_b.

Since Braw=Rraw−2IB_{\mathrm{raw}} = R_{\mathrm{raw}} - 2I, Equations (3) and (3.11) give

2κA≤2Δ≤Braw+4∑bJb≤Braw+2Brad≤2B.2\kappa A \le2\Delta\le B_{\mathrm{raw}} + 4\sum_b J_b \le B_{\mathrm{raw}} + 2B_{\mathrm{rad}} \le2B.

This is (3.9).

From bounded fragments to all pictures

The probability estimate controls only bounded collections of occurrences. To use it for an arbitrarily large picture, we partition the faces into bounded sets while cutting few contacts. A fragment was allowed to be disconnected and to have holes, so any partition of the dual graph gives eligible fragments. The following separator estimate makes their total new boundary small enough to absorb into the area bound.

Lemma 3.8. For every D<∞D < \infty and η>0\eta> 0 there is an integer K=K(D,η)K = K(D,\eta) such that the vertices of any finite planar multigraph of maximum degree at most DD can be partitioned into sets of size at most KK, with at most η\eta times the total number of vertices edges crossing between sets.

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

Charge c/qc/\sqrt{q} to every vertex present in a recursive set of size qq. 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/32/3 while they exceed KK. Reading that sequence backward shows that its total charge is at most

cK∑j≥0(23)j=c(1−2/3)K.\frac{c}{\sqrt{K}}\sum_{j\geq0}\left(\sqrt{\frac{2}{3}}\right)^j=\frac{c}{\left(1-\sqrt{2/3}\right)\sqrt{K}}.

If the original graph has AA vertices, the number of removed separator vertices is at most CA/KCA/\sqrt{K}, where C=c/(1−2/3)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 DCA/KDCA/\sqrt{K}. Choose KK so large that DC/K≤ηDC/\sqrt{K}\leq\eta. Disconnected graphs are treated component by component.

Proof of Theorem 3.1. Fix the parameters, so that κ\kappa and C0C_0 in Lemma 3.7 are positive constants. Choose η>0\eta>0 with 2C0η≤1/22C_0\eta\leq1/2, and apply Lemma 3.8 with D=15D=15. This gives a fixed finite threshold KK. By Lemma 3.2, with probability tending to one Equation (3.1) holds for all collections of at most 8K8K 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 AA interior faces into fragments of size at most KK, cutting at most ηA\eta A contacts. Let B0B_0 count contacts with the outside polygon; in the sphere problem set B0=0B_0=0. The sum of fragment boundary lengths is at most B0+2ηAB_0+2\eta A. Lemma 3.7 applies to every fragment, and summing it gives

A≤C0(B0+2ηA),henceA≤2C0B0.A\leq C_0(B_0+2\eta A),\qquad\text{hence}\qquad A\leq2C_0B_0.

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

If a nonzero cellular two-cycle cc existed in P~\widetilde{P}, use its normal spherical picture supplied by Lemmas 3.3 and 3.4. For B0=0B_0=0, forcing A=0A=0. Its cellular chain would then be zero, contrary to its construction. Therefore H2(P~;Z)=0H_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 XDX_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 60C0ℓ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.

Remark 3.9. The separator threshold is chosen after the positive parameters are fixed and before nn tends to infinity. No uniform bound as α,β,δ⟶0\alpha,\beta,\delta\longrightarrow0 is asserted or required. For each fixed parameter choice, the single finite-collection event in Lemma [3] controls all disk words and all cellular two-cycles simultaneously.

Conditional sampling from the nested tables

The relations will be tested against an action chosen after all the tables have been sampled. We therefore prove statements about total variation of finite distributions on table matches. These statements do not refer to a target metric space. In particular, they will apply simultaneously to all uniformly bounded functions on the relevant assignments, including functions obtained from a subsequently chosen action.

The master pattern and its critical exponents

Recall the master pattern M\mathcal{M} from Section 2, and let F\mathcal{F} be its field set. Its required entries are the seven fan entries, the top-mark entry, and one entry from each of the 90 four-letter tables. In each four-letter entry its first two fields are identified with the corresponding core fields; its other two fields are new and are used in no other entry. The six-letter table is not part of M\mathcal{M}. Thus ∣F∣=212|\mathcal{F}| = 212. Write RR for the set of its 98 array entries and Eρ⊆FE_\rho\subseteq\mathcal{F} for the field support of ρ∈R\rho\in R. Each ρ\rho belongs to a different Bernoulli array. The order of its coordinates is fixed throughout.

A match is a map σ:F→Sn\sigma: \mathcal{F} \to S_n for which every required array entry is present. No injectivity is required of a single match. We write Ωn\Omega_n for the random set of matches and, when it is nonempty, write μN\mu_N for its uniform probability measure.

Recall from Definition 2.5 that a set of fields is admissible if it consists either of at most three core fields, at most two in each fan, or of at most two fields of one square decoration. The loose field belongs to no fan.

Definition 4.1. A conditional test is a triple (I,e,t)(I,e,t) with I⊆FI \subseteq\mathcal{F}, e∈F∖Ie \in\mathcal{F} \setminus I, I∪{e}I \cup\{e\} admissible, and tt a positive integer.

For θ=(α,β,δ)\theta= (\alpha,\beta,\delta) define cρ(θ)c_\rho(\theta) so that the inclusion probability of entry ρ\rho is N−cρ(θ)N^{-c_\rho(\theta)}. Its value and its critical value cρ=cρ(0)c_\rho=c_\rho(0) are

entrycρ(θ)cρfan iki−2+αki−2top mark12+β−7α12four-letter entry2+δ2(4)\begin{array}{c|c|c} \text{entry} & c_\rho(\theta) & c_\rho\\ \text{fan }i & k_i-2+\alpha& k_i-2 \\ \text{top mark} & 12+\beta-7\alpha& 12 \\ \text{four-letter entry} & 2+\delta& 2 \tag*{(4)} \end{array}

For a set of fields WW put

hθ(W)=∣W∣−∑ρ:Eρ⊆Wcρ(θ),h(W)=h0(W).h_\theta(W)=|W|-\sum_{\rho:E_\rho\subseteq W}c_\rho(\theta),\qquad h(W)=h_0(W).

Thus Nhθ(W)N^{h_\theta(W)} is the expected number of assignments to WW for which all required entries supported in WW are present. The function hh is submodular. Indeed, for each fixed EρE_\rho, the indicator of Eρ⊆WE_\rho\subseteq W is supermodular, and all cρc_\rho are nonnegative. Notice also that

h(F)=212−(17+12+180)=3,E∣Ωn∣=Nhθ(F)=N3−β−90δ.(5)h(\mathcal{F})=212-(17+12+180)=3,\qquad\mathbb{E}|\Omega_n|=N^{h_\theta(\mathcal{F})}=N^{3-\beta-90\delta}. \tag*{(5)}

The expectation is exact: each assignment uses one entry from each of the distinct arrays, so all of its inclusion requirements are independent.

Lemma 4.2. For every W⊆FW\subseteq\mathcal{F},

h(W)≥min⁡{2,∣W∣}.(6)h(W)\ge\min\{2,|W|\}. \tag*{(6)}

If SS is admissible and S⊆WS\subseteq W, then

h(W)≥∣S∣.(7)h(W)\ge|S|. \tag*{(7)}

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

∑i(ai−(ki−2)1{ai=ki})+ℓ≥∑imin⁡{ai,2}+ℓ.\sum_i\left(a_i-(k_i-2)1_{\{a_i=k_i\}}\right)+\ell\ge\sum_i\min\{a_i,2\}+\ell.

The top-mark cost is charged only for the complete core. For that set the exponent is 32−17−12=332-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 (7) when SS consists of core fields, and proves (6) when WW has at least two core fields. If WW 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∣h(W)=|W|. This proves (6) in all cases. Finally, an admissible subset of one four-letter entry has size at most two, so its required bound follows from (6). □\square

Fix a conditional test (I,e,t)(I,e,t). To couple tt matches agreeing on II, we will require them to agree on a possibly larger set UU. The purpose of this enlargement is to make every further extension increase the critical exponent. For example, if II consists of two fields in one fan FiF_i, then completing that fan leaves the exponent unchanged:

h(I)=2=h(E(Fi)).h(I)=2=h(E(F_i)).

Once the fan fields have been included, adjoining both fresh fields of any square whose two core fields lie in that fan also leaves the exponent unchanged. These are examples of the enlargements that the choice of UU must absorb.

In general, ∣I∣≤2|I| \le2, and every entry support has at least three fields, so h(I)=∣I∣h(I) = |I|. Choose an inclusion-maximal set U⊇IU \supseteq I such that

h(U)=∣I∣.h(U) = |I|.

Such a set exists because the field set is finite. The next two properties are the reason for this choice:

e∉U,h(U∪V)−h(U)≥1for every nonempty V⊆F∖U.(8)e \notin U,\qquad h(U \cup V) - h(U) \ge1 \quad\text{for every nonempty } V \subseteq\mathcal{F} \setminus U. \tag*{(8)}

The first follows from Equation (7) applied to I∪{e}I \cup\{e\}. For the second, every superset of UU has exponent at least ∣I∣|I| by the same lemma applied to II. Maximality rules out equality for a strict superset, and all critical exponents are integers.

Stars and their overlap estimates

Form a star MU(t)\mathcal{M}_{U}^{(t)} from tt ordered copies of M\mathcal{M} by identifying all copies of each field in UU. Entries supported entirely in UU are also identified. Each other entry retains one copy in each branch. We require assignments to this star to be injective in each field: for each s∈F∖Us \in\mathcal{F} \setminus U, its tt branch values must be pairwise distinct. Values in different fields may coincide. All fields continue to take values in the same alphabet SnS_n.

This injectivity has two consequences. First, copies of an entry not supported in UU are distinct tuples in their array, since some one of their coordinates lies outside UU. Second, when one branch is fixed, an entry in another branch that is not supported in UU cannot equal the corresponding entry of the fixed branch. Thus all random variables counted below are products of distinct Bernoulli trials, after explicitly removing any trials on which we have conditioned.

We give the overlap count in detail because the coordinates are not disjoint letter domains. An overlap type between two star assignments specifies precisely which entries of each array coincide across the two stars. There are finitely many such types for fixed tt. Each equality of array entries equates corresponding coordinates. For a given field s∉Us \notin U, injectivity implies that these equalities give a partial matching between the tt branch variables of the first star and those of the second. Different arrays may use different partial matchings; their union must still be a partial matching whenever the overlap type is realizable. Otherwise two different branch values of the same field would be forced equal. For s∈Us \in U there is just one variable in each star. In particular, an equality never compares two different coordinate fields, even if their numerical letter values happen to be equal.

Here is the resulting counting rule. Reveal the first assignment. Suppose the equalities of an overlap type prescribe the values of qq distinct, previously unpinned variables in the second assignment. For each field with unpinned variables, there are a bounded number of those variables, and they are chosen uniformly without replacement, possibly avoiding one already pinned value. A field whose variables are all pinned contributes a factor one. Prescribing qsq_s of them has probability at most CtN−qsC_tN^{-q_s}; the number of remaining choices is at most Nr−qsN^{r-q_s}, whereas the number of unrestricted choices is a falling factorial (N−a)r(N-a)_r, with r≤tr \le t and a∈{0,1}a \in\{0,1\}. Multiplying over the finitely many fields gives

fraction of pairs having the specified overlap≤CtN−q.(9)\text{fraction of pairs having the specified overlap} \le C_t N^{-q}. \tag*{(9)}

Incompatible specifications simply contribute zero. If the coincident, unconditioned entries have total actual cost CC, their joint inclusion probability divided by the product of the two individual inclusion probabilities is NCN^C. All other trials are independent. Consequently this overlap type contributes at most

CtN−q+CC_tN^{-q+C}

to the relative variance of the count in question. Pairs with no coincident unconditioned entry have covariance zero, including when they have coincident values that do not complete any common entry. To justify the relative-variance normalization directly, all candidate assignments in any one of our counting problems have the same probability of inclusion, and (9) bounds the fraction of pairs of such candidates. Summing their covariances and dividing by the square of the expectation gives (4.9), summed over the finitely many nonempty overlap types.

We first apply this rule to a single copy of M\mathcal{M}. If WW is the set of fields belonging to its shared entries, then q=∣W∣q = |W| and the recovered cost is at most the sum of the costs of all entries supported in WW. Its critical excess is therefore at least h(W)>0h(W) > 0. For sufficiently small actual parameters, every one of these finitely many positive excesses stays positive. It follows that

Var⁡∣Ωn∣(E∣Ωn∣)2=o(1).(10)\frac{\operatorname{Var}|\Omega_n|}{(\mathbb{E}|\Omega_n|)^2}=o(1). \tag*{(10)}

In particular the master count is asymptotic to its expectation in probability. We always choose the parameters small enough that the exponent in (5) is positive.

For the two star counts, write

CU(θ)=∑ρ:Eρ⊆Ucρ(θ),Cout(θ)=∑ρ:Eρ⊈Ucρ(θ),d=∣F∖U∣.C_U(\theta)=\sum_{\rho:E_\rho\subseteq U}c_\rho(\theta),\qquad C_{\mathrm{out}}(\theta)=\sum_{\rho:E_\rho\not\subseteq U}c_\rho(\theta),\qquad d=|\mathcal{F}\setminus U|.

Let ZNZ_N be the number of present injective stars. With (N)t=N(N−1)⋯(N−t+1)(N)_t=N(N-1)\cdots(N-t+1),

EZN=N∣U∣(N)tdN−CU(θ)−tCout(θ).(11)\mathbb{E}Z_N=N^{|U|}(N)_t^dN^{-C_U(\theta)-tC_{\mathrm{out}}(\theta)}. \tag*{(11)}

Lemma 4.3. For each fixed conditional test, sufficiently small actual parameters have the following properties as N→∞N\to\infty.

  1. Fix any assignment σ:F→Sn\sigma:\mathcal{F}\to S_n, place it in a specified branch, and condition on it being a match. Let AσA_\sigma count its extensions to a present injective star. Its conditional mean is independent of σ\sigma and equals

aN=((N−1)t−1)dN−(t−1)Cout(θ).a_N=((N-1)_{t-1})^dN^{-(t-1)C_{\mathrm{out}}(\theta)}.

Uniformly in σ\sigma, its conditional relative variance is o(1)o(1).

  1. Fix any ordered list b=(b1,…,bt)b=(b_1,\ldots,b_t) of distinct letters as the values of field ee in the branches. Let BbB_b count the present injective stars having those values. Its mean is independent of bb and equals

bN=N∣U∣(N)td−1N−CU(θ)−tCout(θ).b_N=N^{|U|}(N)_t^{d-1}N^{-C_U(\theta)-tC_{\mathrm{out}}(\theta)}.

Uniformly in bb, its relative variance is $o(1).

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 UU 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 UU, its other t−1t-1 values are distinct and avoid the value in σ\sigma, giving (N−1)t−1(N-1)_{t-1} choices. Each extra branch requires all the entries not supported in UU, giving exactly Equation (4.12).

Consider an overlap of the unconditioned entries of two such extensions. In extra branch jj of the first extension let VjV_j consist of the outside-UU fields involved in its shared entries. The assignment penalty in Equation (9) is ∑j∣Vj∣\sum_j |V_j|: all UU-values are fixed, whereas every involved outside-UU 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

∑ρ:Eρ⊆U∪Vj, Eρ⊈Ucρ.\sum_{\rho:E_\rho\subseteq U\cup V_j,\ E_\rho\not\subseteq U} c_\rho.

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

∑j:Vj≠∅[h(U∪Vj)−h(U)]≥1.\sum_{j:V_j\ne\varnothing}\left[h(U\cup V_j)-h(U)\right]\ge1.

for every nonempty overlap, by Equation (8). The finitely many bounds remain strict for small actual parameters. Equations (9) and (4.9) prove the conditional relative variance claim, uniformly in the values of σ\sigma. If t=1t=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∉Ue\notin U, its tt pinned values satisfy precisely its field-injectivity constraint. The other fields have N∣U∣(N)t−1d−1N^{|U|}(N)_{t-1}^{d-1} choices, proving Equation (4.13).

For an overlap let WW be the set of variables in the first star belonging to shared entries. Write A=W∩UA=W\cap U, and let VjV_j be its outside-UU fields in branch jj. Let m(W)m(W) be the number of its ee-variables. In a realizable overlap an ee-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)q=|W|-m(W) in Equation (9).

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

h⋆(W)−m(W).h_\star(W)-m(W).

If A≠∅A\ne\varnothing, separating entries entirely in UU from the entries in each branch gives

h⋆(W)≥h(A)+∑j:Vj≠∅[h(U∪Vj)−h(U)].(12)h_\star(W)\ge h(A)+\sum_{j:V_j\ne\varnothing}\left[h(U\cup V_j)-h(U)\right]. \tag*{(12)}

Indeed the exact contribution of branch jj is ∣Vj∣|V_j| minus the costs of entries supported in A∪VjA\cup V_j but not entirely in UU; replacing AA by UU 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 (8). Each such branch contains at most one pinned ee-variable. Hence the excess in Equation (4.14) is at least one.

If A=∅A=\varnothing, no shared entry meets UU, and entries in different branches use disjoint variables. Consequently h⋆(W)=∑jh(Vj)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 ∣Vj∣≥3|V_j| \ge3 in such a branch and Lemma 4.2 gives h(Vj)≥2h(V_j) \ge2. 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. (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.

Normalization to probability couplings

For probability measures λ,λ′\lambda,\lambda' on a finite set we use

dTV(λ,λ′)=12∑z∣λ(z)−λ′(z)∣.d_{\mathrm{TV}}(\lambda,\lambda') = \frac{1}{2}\sum_z |\lambda(z)-\lambda'(z)|.

All convergence statements about the random tables below are in probability as N→∞N \to\infty; equivalently one can choose deterministic error bounds tending to zero for which the corresponding assertions hold with probability tending to one.

Lemma 4.4. For each fixed conditional test and sufficiently small actual parameters, with probability tending to one there is a probability law on tt matches (σ1,…,σt)(\sigma_1,\ldots,\sigma_t) such that:

  1. their restrictions to II agree identically;

  2. every branch marginal has total-variation distance o(1)o(1) from μN\mu_N;

  3. the law of (σ1(e),…,σt(e))(\sigma_1(e),\ldots,\sigma_t(e)) has total-variation distance o(1)o(1) from the uniform product law on SntS_n^t.

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

Put LN=∣Ωn∣L_N = |\Omega_n| and λN=ELN\lambda_N = \mathbb{E}L_N. For a specified branch let

DN=∑σ∈Ωn∣Aσ−aN∣.D_N = \sum_{\sigma\in\Omega_n} |A_\sigma-a_N|.

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

E[∣Aσ−aN∣∣σ∈Ωn]=o(aN).\mathbb{E}\bigl[|A_\sigma-a_N| \mid\sigma\in\Omega_n\bigr] = o(a_N).

Multiplying by the probability that σ\sigma is present and summing over all assignments shows EDN=o(λNaN)\mathbb{E}D_N = o(\lambda_Na_N). Markov’s inequality yields DN=o(λNaN)D_N = o(\lambda_Na_N) in probability. By Equation (4.10), LN/λN→1L_N/\lambda_N \to1 in probability. Since

ZN=∑σ∈ΩnAσ,∣ZN−LNaN∣≤DN,Z_N = \sum_{\sigma\in\Omega_n} A_\sigma,\qquad|Z_N-L_Na_N| \le D_N,

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

∑σ∈Ωn∣AσZN−1LN∣≤DNZN+∣LNaNZN−1∣⟶0.\sum_{\sigma\in\Omega_n}\left|\frac{A_\sigma}{Z_N}-\frac{1}{L_N}\right| \le\frac{D_N}{Z_N}+\left|\frac{L_Na_N}{Z_N}-1\right| \longrightarrow0.

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

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

E∑b∈BN∣Bb−bN∣=o((N)tbN).\mathbb{E}\sum_{b\in B_N}|B_b-b_N|=o((N)_t b_N).

Markov’s inequality and ∑bBb=ZN\sum_b B_b=Z_N imply that the total variation between the leaf distribution Bb/ZNB_b/Z_N and the uniform distribution on BNB_N tends to zero, by the same displayed normalization estimate with (N)t,bN(N)_t,b_N in place of LN,aNL_N,a_N. Finally, an iid uniform list in SntS_n^t has a repeated value with probability at most (t2)/N\binom{t}{2}/N. Its distribution conditioned on distinctness is uniform on BNB_N. This proves the final assertion.

Finite tests, parameter choices, and the six-letter table

The two marginal conclusions of the coupling serve different purposes. The branch comparison transfers averages of bounded tests between the coupled branches and a uniform match. In Lemma 5.4, a pointwise norm estimate bounds the average over the tt branches by a function of the ee-labels alone; the common II-labels enter only through a uniform bound. The comparison with independent uniform letters then controls that function of the leaves. Thus the argument needs no independence between the common II-tuple and the test labels.

All critical overlap margins above are at least one. Each shared trial is charged once to its occurrence in the first star, which has at most tt copies of each array entry. Since β>7α\beta>7\alpha, all cost increments are positive. Replacing critical costs by actual costs therefore increases any recovered-cost sum by at most

t[7α+(β−7α)+90δ]=t(β+90δ).t[7\alpha+(\beta-7\alpha)+90\delta]=t(\beta+90\delta).

Conditioning removes trials and can only decrease this bound; a single master match is covered by t=1t=1. For a finite family of tests, let tmax⁡t_{\max} be the largest requested value of tt, or one if the family is empty. Choosing tmax⁡(β+90δ)<1/2t_{\max}(\beta+90\delta)<1/2 preserves every overlap margin at a value at least 1/21/2, including the singleton tests used below. This is compatible with β>7α>0\beta>7\alpha>0: take β=8α\beta=8\alpha and then take α,δ\alpha,\delta sufficiently small. The parameters are held fixed while NN tends to infinity. In particular, none of the variance arguments asserts uniformity for unbounded tt at a single fixed choice of parameters.

Let DN⊆Sn6D_N\subseteq S_n^6 be the separate six-letter table. For positions 1≤r<q≤61\le r<q\le6 and letters u,vu,v, write

Qrq(u,v)=#{(s1,…,s6)∈DN:sr=u,sq=v}.Q_{rq}(u,v)=\#\{(s_1,\ldots,s_6)\in D_N:s_r=u,s_q=v\}.

Each such count is a sum of N4N^4 independent Bernoulli variables of parameter N−3−δN^{-3-\delta}, and so has mean N1−δN^{1-\delta}. For fixed 0<δ<10<\delta<1, put εN=N−(1−δ)/4\varepsilon_N=N^{-(1-\delta)/4}. The binomial Chernoff bound gives

P(∣Qrq(u,v)−N1−δ∣>εNN1−δ)≤2exp⁡(−εN2N1−δ/3).\mathbb{P}\left(\left|Q_{rq}(u,v)-N^{1-\delta}\right|>\varepsilon_NN^{1-\delta}\right)\le2\exp\left(-\varepsilon_N^2N^{1-\delta}/3\right).

A union bound over the 15N215N^2 choices of positions and letters therefore proves

max⁡r<q,u,v∈Sn∣Qrq(u,v)N1−δ−1∣=o(1)(13)\max_{r<q,u,v\in S_n}\left|\frac{Q_{rq}(u,v)}{N^{1-\delta}}-1\right|=o(1) \tag*{(13)}

with probability tending to one. No independence between these different counts is needed. We collect the conclusions in the form used below.

Proposition 4.5. For any finite family T\mathcal{T} of conditional tests, there is a neighborhood of the critical parameters such that every sufficiently small fixed positive (α,β,δ)(\alpha,\beta,\delta) in that neighborhood with β>7α\beta> 7\alpha has the following properties as N→∞N \to\infty. With probability tending to one, the master pattern has a nonempty set of matches, its count is

∣Ωn∣=(1+o(1))N3−β−90δ,|\Omega_n| = (1+o(1))N^{3-\beta-90\delta},

every single-field marginal of its uniform law μN\mu_N is o(1)o(1) in total variation from the uniform law on SnS_n, and every test in T\mathcal{T} has the coupling of Lemma 4.4. The six-letter counts also satisfy (13). All these properties concern only the tables and are independent of any choice of action or metric space.

Proof. Adjoin to T\mathcal{T} the finitely many tests (∅,e,1)(\varnothing,e,1), one for each field ee. For such a test (6) forces U=∅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, β+90δ<3\beta+90\delta<3, and δ<1\delta<1. (10), Lemma 4.4, and (13), combined over this finite set of events, prove the proposition.

Remark 4.6. Proposition 4.5 is compatible with Theorem 3.1: for each finite family of tests, choose positive parameters sufficiently small for that family and the theorem, then the diagram fragment threshold, and finally NN. The diagram and sampling events then hold simultaneously with probability tending to one. Lemma 7.1 constructs the deterministic diagonal sequence used below, with parameters tending to zero and every fixed test valid in the limit.

Energy and a limiting configuration

The sampling statements in Proposition 4.5 concern finite tables alone. In this section they will be applied to functions obtained from an isometric action chosen after those tables are known. The order is important: we first obtain a bound on every generator displacement using the pointwise relative counts in the six-letter table. Only then do we use total variation estimates for action-dependent functions.

We use the following standard notation for a complete CAT(0) space XX. Its completed tangent cone at xx is denoted by TxXT_xX, with vertex 00. For y∈Xy\in X, the vector log⁡xy\log_x y has length d(x,y)d(x,y) and the direction of the geodesic from xx to yy. In a Euclidean metric cone set

⟨u,v⟩=∥u∥2+∥v∥2−d(u,v)22.\langle u,v\rangle=\frac{\lVert u\rVert^2+\lVert v\rVert^2-d(u,v)^2}{2}.

Thus ⟨u,v⟩=∥u∥∥v∥cos⁡∠(u,v)\langle u,v\rangle=\lVert u\rVert\lVert v\rVert\cos\angle(u,v), where the angle is truncated at π\pi. Multiplication of a vector by a nonnegative real number always means radial dilation. No additive vector-space structure on a cone is assumed.

We will use strong convexity of squared distance, first variation, the flat-triangle equality theorem, and the tangent-cone theorem for CAT(0) spaces; see [5], Chapters II.1–II.3, in particular II.2.9–II.2.10, II.3.6, and II.3.19. These results do not require properness. In particular, comparison of angles with comparison angles gives

d(y,z)2≥d(x,y)2+d(x,z)2−2⟨log⁡xy,log⁡xz⟩.(14)d(y,z)^2\ge d(x,y)^2+d(x,z)^2-2\langle\log_x y,\log_x z\rangle. \tag*{(14)}

All the tangent cones below are completed cones.

A minimizing basepoint and uniform displacement bounds

The first-variation characterization of an energy minimizer in a tangent cone is part of the harmonic-map framework of Gromov [9] (Sections 3.3 and 3.7) and Izeki–Nayatani [12]. We give the argument together with the existence of a minimizing basepoint under the action hypotheses used here.

Lemma 5.1. Let an infinite finitely generated group GG act properly and cocompactly by isometries on a proper complete CAT(0) space XX. For a finite symmetric generating alphabet SS, counted with its given multiplicities, the function

E(x)=1∣S∣∑s∈Sd(x,sx)2E(x) = \frac{1}{|S|}\sum_{s\in S}d(x,sx)^2

has a minimizer and its minimum is positive. At any minimizing basepoint, the vectors vs=log⁡x(sx)v_s=\log_x(sx) satisfy

1∣S∣∑s∈S⟨h,vs⟩≤0(h∈TxX).(15)\frac{1}{|S|}\sum_{s\in S}\langle h,v_s\rangle\leq0 \qquad(h\in T_xX). \tag*{(15)}

Equivalently, 00 is their barycenter, and

1∣S∣∑s∈Sd(h,vs)2≥∥h∥2+1∣S∣∑s∈S∥vs∥2.(16)\frac{1}{|S|}\sum_{s\in S}d(h,v_s)^2\geq\lVert h\rVert^2+\frac{1}{|S|}\sum_{s\in S}\lVert v_s\rVert^2. \tag*{(16)}

Proof. Choose a minimizing sequence xjx_j and a compact set CC with GC=XGC=X. There are gj∈Gg_j\in G such that yj=gjxj∈Cy_j=g_jx_j\in C. Bounded energy bounds each individual displacement d(xj,sxj)d(x_j,sx_j), since SS is finite. It therefore bounds

d(yj,(gjsgj−1)yj).d(y_j,(g_jsg_j^{-1})y_j).

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

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

d(xt,sxt)2≤12d(x2t,sx)2+12d(x,sx2t)2.d(x_t,sx_t)^2\leq\frac{1}{2}d(x_{2t},sx)^2+\frac{1}{2}d(x,sx_{2t})^2.

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

0≤ddt∣0+1∣S∣∑sd(x2t,sx)2=−4∣S∣∑s⟨h,vs⟩.0\leq\left.\frac{d}{dt}\right|_{0+}\frac{1}{|S|}\sum_s d(x_{2t},sx)^2=-\frac{4}{|S|}\sum_s\langle h,v_s\rangle.

Represented vectors are dense in the completed tangent cone, so continuity gives (15) for every hh. The cone cosine formula immediately gives (16); in particular 00 minimizes the mean squared distance to the vsv_s.

For each aspherical instance PP of Theorem 3.1, its group GG is infinite. Indeed, the parity quotient in Lemma 2.3 makes GG nontrivial. If GG were finite, the universal cover would be a finite contractible complex and

1=χ(P~)=∣G∣χ(P),1 = \chi(\widetilde{P}) = |G|\chi(P),

which forces ∣G∣=1|G| = 1. Thus Lemma 5.1 applies to any geometric action considered here. Rescale its metric so that at the minimizing basepoint

1N∑s∈Sn∥vs∥2=1.(17)\frac{1}{N}\sum_{s\in S_n}\lVert v_s\rVert^2 = 1. \tag*{(17)}

Rescaling preserves completeness, properness, and the CAT(0) condition.

Lemma 5.2. Suppose the six-letter table has pointwise relative error at most ε<1\varepsilon< 1 in the counts for positions 1 and kk, for every 2≤k≤62 \leq k \leq6. Then every action normalized as in Equation (17) satisfies

max⁡s∈Sn∥vs∥2≤251+ε1−ε.(18)\max_{s\in S_n}\lVert v_s\rVert^2 \leq25\frac{1+\varepsilon}{1-\varepsilon}. \tag*{(18)}

The bound is independent of the action.

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

(1−ε)N1−δ≤Q1k(a,b)≤(1+ε)N1−δ.(1-\varepsilon)N^{1-\delta} \leq Q_{1k}(a,b) \leq(1+\varepsilon)N^{1-\delta}.

Summing over bb shows that rows beginning with any fixed aa are nonempty and that their conditional kkth-coordinate distribution is bounded above, pointwise, by

1+ε1−ε1N.\frac{1+\varepsilon}{1-\varepsilon}\frac{1}{N}.

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

∥va∥2≤5∑k=26∥vsk∥2.\lVert v_a\rVert^2 \leq5\sum_{k=2}^{6}\lVert v_{s_k}\rVert^2.

Average over the rows beginning with aa and use the preceding pointwise bound and Equation (17). Each of the five conditional averages is at most (1+ε)/(1−ε)(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.

Conditional tests in tangent cones

For a geodesic from uu to vv in a CAT(0) Euclidean cone, write [u,v]t[u,v]_t for its point at parameter tt. Its squared radial norm satisfies the exact identity

∥[u,v]t∥2=(1−t)∥u∥2+t∥v∥2−t(1−t)d(u,v)2.(19)\lVert[u,v]_t\rVert^2 = (1-t)\lVert u\rVert^2 + t\lVert v\rVert^2 - t(1-t)d(u,v)^2. \tag*{(19)}

If either endpoint is the cone vertex, the identity is immediate. Otherwise the segment is a Euclidean segment in the sector between its two rays when their angular distance is less than π\pi. When their angular distance is at least π\pi, it passes through the cone vertex, and ∥[u,v]t∥=∣(1−t)∥u∥−t∥v∥∣\lVert[u,v]_t\rVert= \lvert(1-t)\lVert u\rVert-t\lVert v\rVert\rvert gives the same identity. These two cases follow directly from the Euclidean-cone metric; see [5].

The scalar-product concavity used next is recorded by Gigli–Nobili [7]. The inductive-mean estimate is the unit-variance case of Sturm’s bound [19]. We include the short proofs in the present normalization.

Lemma 5.3. In a complete CAT(0) metric cone, u↦⟨h,u⟩u \mapsto\langle h,u\rangle is concave along every geodesic, for fixed hh. Suppose a finite probability distribution of vectors VV has barycenter 00 and E∥V∥2=1\mathbb{E}\lVert V\rVert^2=1. If V1,…,VtV_1,\ldots,V_t are independent samples and

m1=V1,mj=[mj−1,Vj]1/j,m_1=V_1,\qquad m_j=[m_{j-1},V_j]_{1/j},

then

E∥mt∥2≤1t.(20)\mathbb{E}\lVert m_t\rVert^2\leq\frac{1}{t}. \tag*{(20)}

For any deterministic list V1,…,VtV_1,\ldots,V_t one also has

1t∑j=1t⟨h,Vj⟩≤⟨h,mt⟩.(21)\frac{1}{t}\sum_{j=1}^{t}\langle h,V_j\rangle\leq\langle h,m_t\rangle. \tag*{(21)}

Proof. Subtract strong convexity of d(h,⋅)2d(h,\mathord\cdot)^2 from Equation (19) in the identity 2⟨h,u⟩=∥h∥2+∥u∥2−d(h,u)22\langle h,u\rangle=\lVert h\rVert^2+\lVert u\rVert^2-d(h,u)^2. The quadratic terms cancel, proving concavity. Induction gives Equation (21).

For the independent samples, condition on mj−1=um_{j-1}=u. The barycenter variance inequality gives E[d(u,Vj)2∣u]≥∥u∥2+1\mathbb{E}[d(u,V_j)^2\mid u]\geq\lVert u\rVert^2+1. Strong convexity of squared distance from the cone vertex therefore gives, with aj=E∥mj∥2a_j=\mathbb{E}\lVert m_j\rVert^2,

aj≤(1−1/j)aj−1+1/j2.a_j\leq(1-1/j)a_{j-1}+1/j^2.

Starting with a1=1a_1=1, induction yields aj≤1/ja_j\leq1/j.

Consider now a sequence of table instances indexed by ν\nu for which the conclusions of Proposition (7) hold with errors tending to zero, for every fixed test and every fixed positive integer tt. Suppose their groups have geometric actions as above, and choose the normalized minimizing basepoints xνx_\nu. Write Ων=Ωnν\Omega_\nu=\Omega_{n_\nu} for the nonempty finite set of master matches and μν=μNν\mu_\nu=\mu_{N_\nu} for its uniform distribution. Lemma 5.2 gives an absolute constant MM such that

∥vs∥≤Mfor all letters in all sufficiently large instances.(22)\lVert v_s\rVert\leq M\qquad\text{for all letters in all sufficiently large instances.} \tag*{(22)}

All statements about the limit are unchanged by discarding finitely many instances. The actions, their spaces, and the functions in the next lemma may depend on the complete table instances.

Lemma 5.4 (Uniform conditional test). Let II and {e}\{e\} be disjoint sets of fields with admissible union. For each ν\nu, let hIh_I be a function of the labels on II with values in TxνXνT_{x_\nu}X_\nu, and suppose ∥hI∥≤B\lVert h_I\rVert\le B for a constant independent of ν\nu and the match. For either fixed choice σ(s)=s\sigma(s)=s or σ(s)=s−1\sigma(s)=s^{-1},

lim sup⁡ν→∞Eμν⟨hI,vσ(e)⟩≤0.(23)\limsup_{\nu\to\infty}\mathbb{E}_{\mu_\nu}\langle h_I,v_{\sigma(e)}\rangle\le0. \tag*{(23)}

Here ee in a subscript denotes the letter occupying that field.

Proof. Fix tt. Use the coupling in Proposition 4.5: it gives tt matches agreeing on II, each branch marginal at total variation distance at most ην,t\eta_{\nu,t} from μν\mu_\nu, and their ee-labels at distance at most ην,t\eta_{\nu,t} from independent uniform letters, where ην,t→0\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 hIh_I has the same value in every branch. Form the inductive mean mtm_t of the branch vectors vσ(ej)v_{\sigma(e_j)}. (21) gives, for every coupled tuple,

1t∑j=1t⟨hI,vσ(ej)⟩≤⟨hI,mt⟩≤B∥mt∥.\frac{1}{t}\sum_{j=1}^{t}\langle h_I,v_{\sigma(e_j)}\rangle\le\langle h_I,m_t\rangle\le B\lVert m_t\rVert.

The last step uses only the norm bound; it does not assume that hIh_I is independent of the leaves. Under independent uniform leaves, Equation (5.7) applies by Equations (5.3) and (5.4). Under the coupling, ∥mt∥≤M\lVert m_t\rVert\le M, by convexity of the ball of radius MM. Consequently the total variation comparison changes the expected squared norm by at most 2M2ην,t2M^2\eta_{\nu,t}. The branch comparisons change the expectation of each scalar-product test by at most 2BMην,t2BM\eta_{\nu,t}. It follows that

Eμν⟨hI,vσ(e)⟩≤B1/t+2M2ην,t+2BMην,t.\mathbb{E}_{\mu_\nu}\langle h_I,v_{\sigma(e)}\rangle\le B\sqrt{1/t+2M^2\eta_{\nu,t}+2BM\eta_{\nu,t}}.

First take the upper limit in ν\nu with tt fixed, and then let t→∞t\to\infty. All error bounds used only BB and MM, so the conclusion is uniform over the action-dependent functions in the statement.

Products of orbit configurations

Enlarge Γ\Gamma by adding, for each of its prescribed two-edge paths, the complementary two-edge path of its decoration square. Denote this fixed finite graph by Γ^\widehat{\Gamma}; its additional midpoint vertices are distinct abstract vertices. A master match gives a consistent orbit realization of this graph in XνX_\nu: choose one anchor at xνx_\nu, and send a vertex reached by the successive letters s1,…,sks_1,\ldots,s_k to s1⋯skxνs_1\cdots s_kx_\nu. All core closed walks are relations, and the decoration square relations guarantee consistency on the added paths. Fixing one path for each vertex shows that these orbit points are at distance at most LMLM from xνx_\nu, where LL depends only on Γ^\widehat{\Gamma}.

Take the finite product over the matches with metric

dν((ym),(zm))2=1∣Ων∣∑m∈Ωνd(ym,zm)2.(24)d_\nu((y_m),(z_m))^2=\frac{1}{\lvert\Omega_\nu\rvert}\sum_{m\in\Omega_\nu}d(y_m,z_m)^2. \tag*{(24)}

based at the tuple of minimizing basepoints. It is a complete CAT(0) space. The vertex tuples have bounded distance from this basepoint. Fix a nonprincipal ultrafilter on the sequence index set N\mathbb{N} and take the pointed metric ultralimit ZZ. This space is complete by [5], Lemma I.5.53, and it is CAT(0) by [5], Corollary II.3.10(2). The bounded vertex tuples give a configuration in ZZ indexed by the vertices of Γ^\widehat{\Gamma}. Midpoints and fixed-fraction points on segments in the products are formed coordinatewise, and their ultralimits are the corresponding points in ZZ by uniqueness of geodesics. We identify the abstract vertex names with the resulting points. Neither properness nor a dimension bound for ZZ is needed.

Lemma 5.5. Every edge in Γ^\widehat{\Gamma} has length one in ZZ. Every two-step path using two distinct fields of one decoration square has squared endpoint distance at least two. More generally, a path of k≤3k \le3 distinct core fields whose field set is admissible has squared endpoint distance at least kk.

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

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

hI=log⁡xν(ak−1−1⋯a1−1xν).h_I=\log_{x_\nu}(a_{k-1}^{-1}\cdots a_1^{-1}x_\nu).

This is a function of precisely the preceding labels, and ∥hI∥≤(k−1)M\lVert h_I\rVert\le(k-1)M. Equation (14) gives

d(u0,uk)2≥d(u0,uk−1)2+∥vak∥2−2⟨hI,vak⟩d(u_0,u_k)^2 \ge d(u_0,u_{k-1})^2+\lVert v_{a_k}\rVert^2-2\langle h_I,v_{a_k}\rangle

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.

Quadrilateral equality and hexagon centers

The path estimates give lower bounds on squared distances. We now compare them with a CAT(0) upper bound on the sum of the two diagonal squares of a quadrilateral. Equality will first determine the diagonals of every decoration square, and then force the three opposite pairs in each core hexagon to share a midpoint.

Lemma 5.6. For four points z1,z2,z3,z4z_1,z_2,z_3,z_4 in a CAT(0) space, let m=mid⁡(z1,z3)m=\operatorname{mid}(z_1,z_3) and n=mid⁡(z2,z4)n=\operatorname{mid}(z_2,z_4). Then

d(z1,z3)2+d(z2,z4)2+4d(m,n)2≤∑i=14d(zi,zi+1)2,z5=z1.(25)d(z_1,z_3)^2+d(z_2,z_4)^2+4d(m,n)^2\le\sum_{i=1}^{4}d(z_i,z_{i+1})^2,\qquad z_5=z_1. \tag*{(25)}

In particular, equality between the two diagonal-square sum and the side-square sum forces the diagonal midpoints to coincide.

Proof. Apply midpoint convexity to d(m,z2)2d(m,z_2)^2 and d(m,z4)2d(m,z_4)^2 using the segment z1z3z_1z_3, and then to d(m,n)2d(m,n)^2 using z2z4z_2z_4. Substituting the first two inequalities into the third and multiplying by four gives Equation (25).

Each decoration square has unit sides. Both of its diagonals have squared length at least two by Lemma 5.5. Lemma 5.6 forces both squared lengths to equal two. In particular,

d(u,w)2=2for every nonbacktracking two-edge core path u,v,w.d(u,w)^2=2\quad\text{for every nonbacktracking two-edge core path }u,v,w.

Every such path was assigned a decoration table, including paths whose two fields lie in the same fan.

Recall that a core hexagon is obtained from three noncollinear Fano points i,j,ki,j,k, their joining lines, and a choice of XX or an available YY representative at each of the three points, with all six required edges present. The squared distances of its vertices z0,…,z5z_0,\ldots,z_5 at cyclic separation one and two are, respectively, one and two. Each three-edge half-path uses at most two fields of any one fan, so its opposite endpoints have squared distance at least three.

Apply Lemma 5.6 to (z0,z1,z3,z4)(z_0,z_1,z_3,z_4). The side-square sum is 1+2+1+2=61+2+1+2=6, whereas each diagonal-square is at least three. Both are therefore three and their midpoints coincide. Applying the same argument to (z1,z2,z4,z5)(z_1,z_2,z_4,z_5) identifies the third opposite-pair midpoint with the first two. Denote the resulting center of this hexagon by cc. Every vertex has distance

r=32(26)r=\frac{\sqrt{3}}{2} \tag*{(26)}

from cc.

Lemma 5.7. For a core hexagon, every triangle formed by its center and two of its vertices is Euclidean flat, including the degenerate case of opposite vertices. The corresponding tangent vectors satisfy

⟨log⁡czi,log⁡czj⟩=r2−12d(zi,zj)2.(27)\left\langle\log_c z_i,\log_c z_j\right\rangle=r^2-\frac{1}{2}d(z_i,z_j)^2. \tag*{(27)}

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

⟨u,v+⟩+⟨u,v−⟩≤0(u∈TcZ).(28)\left\langle u,v^+\right\rangle+\left\langle u,v^-\right\rangle\le0\qquad(u\in T_cZ). \tag*{(28)}

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

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

⟨u,v+⟩≥r2−12d(zi,zj)2,⟨u,v−⟩≥r2−12d(zi,zj+3)2.\left\langle u,v^+\right\rangle\ge r^2-\frac{1}{2}d(z_i,z_j)^2,\qquad \left\langle u,v^-\right\rangle\ge r^2-\frac{1}{2}d(z_i,z_{j+3})^2.

The two prescribed squared distances sum to 3=4r23=4r^2, so the lower bounds sum to zero. Equation (28) forces equality in each bound. Thus the angle at cc 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. □

Lemma 5.8. All core hexagons have the same center cc. Every core vertex lies in a core hexagon, and hence is at distance rr from cc.

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

Replace one YY representative in a core hexagon by its XX representative. The new hexagon is a core hexagon, since every corresponding XX 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 XX representatives.

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

The ternary midpoint test

The square and hexagon comparisons have supplied a common center. We now use three admissible core fields to control one further angle: the angle at CDCD between the segment to the midpoint of XC,YCX_C,Y_C and the loose edge to XDX_D.

Put

H0=CD,p=XC,q=YC,z=XD,J=mid⁡(p,q)H_0=CD,\qquad p=X_C,\qquad q=Y_C,\qquad z=X_D,\qquad J=\operatorname{mid}(p,q)

in ZZ. The following argument gives an angle statement in ZZ without any assumption that angles commute with ultralimits.

Choose another line H≠H0H\ne H_0 through CC. The core four-cycle (p,H0,q,H)(p,H_0,q,H) has unit sides and both diagonals of squared length two, by Equation (5.13). Its diagonal midpoints coincide by Lemma 5.6, so

J=mid⁡(H0,H),d(H0,J)2=12,d(H0,z)=1.(29)J=\operatorname{mid}(H_0,H),\qquad d(H_0,J)^2=\frac{1}{2},\qquad d(H_0,z)=1. \tag*{(29)}

In each orbit factor let JmJ_m be the midpoint of the realizations of pp and qq. Translate the realization of H0H_0 to xνx_\nu. The realizations of p,qp,q are then given by the two letters on the adjacent FCF_C edges, with their fixed orientation signs. Therefore the translated vector toward JmJ_m is a function hIh_I of just those two fields, with norm at most MM. The translated vector toward zz is vσ(e0)v_\sigma(e_0), where e0e_0 is the loose field. These three fields are admissible. Lemma 5.4 shows that the upper limit of the averaged scalar product of these two vectors is at most zero.

Fix a,b∈(0,1]a,b\in(0,1]. In each factor take the points at fractions a,ba,b along the segments from H0H_0 to Jm,zJ_m,z. Their tangent vectors are the corresponding scalar multiples of the two vectors just considered. Apply (14), average over factors, and take the ultralimit. Denoting the limiting fractional points by Ja,zbJ_a,z_b, respectively, gives

d(Ja,zb)2≥a2d(H0,J)2+b2d(H0,z)2=a22+b2.d(J_a,z_b)^2\ge a^2d(H_0,J)^2+b^2d(H_0,z)^2=\frac{a^2}{2}+b^2.

Thus every such comparison angle at H0H_0 is at least π/2\pi/2. Letting both fractions decrease to zero in ZZ proves

∠H0(J,z)≥π2.(30)\angle_{H_0}(J,z)\ge\frac{\pi}{2}. \tag*{(30)}

Only distances of fixed-fraction points passed through the ultralimit; the angle was computed afterwards in the limiting space.

The resulting finite configuration

We collect the conclusions in the form needed in Section 6.

Proposition 5.9. Let PνP_\nu be a sequence of aspherical instances whose master-match statistics and six-letter relative counts satisfy the conclusions of Proposition 4.5, with errors tending to zero for every fixed test and every fixed tt. If every π1(Pν)\pi_1(P_\nu) has a proper cocompact isometric action on a proper complete CAT(0) space, then there are a complete CAT(0) space ZZ, a configuration indexed by the core vertices of Γ\Gamma, and a point c∈Zc\in Z with the following properties.

  1. Every core edge has length one. Every nonbacktracking two-edge core path has squared endpoint distance two. Every three-edge core path with distinct admissible fields has squared endpoint distance at least three.

  1. Every core hexagon has its three opposite-pair midpoints equal to cc. All core vertices have distance r=3/2r=\sqrt{3}/2 from cc. For any two vertices occurring in one core hexagon, their central triangle with cc is flat and their tangent scalar product is given by (27).

  1. With H0=CDH_0=CD and J=mid⁡(XC,YC)J=\operatorname{mid}(X_C,Y_C), one has

d(H0,J)2=12,d(H0,XD)=1,∠H0(J,XD)≥π2.d(H_0,J)^2=\frac{1}{2},\qquad d(H_0,X_D)=1,\qquad\angle_{H_0}(J,X_D)\ge\frac{\pi}{2}.

More precisely, all the fractional-point inequalities in (5.18) hold.

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.

The geometric obstruction

We now show that the configuration obtained in Proposition 5.9 cannot occur in a complete CAT(0) space. The argument takes place first in that space and then in its completed tangent cone at the common hexagon center. The tangent cone is not assumed to be a vector space, so we specify the meaning of its sums and use concavity whenever an additive inequality is required.

Cone notation and square rigidity

For a CAT(0) Euclidean cone TT with vertex 00, let δa\delta_a denote radial dilation by a≥0a\ge0. Write au=δa(u)au=\delta_a(u) and

∥u∥=dT(0,u),⟨u,v⟩=∥u∥2+∥v∥2−dT(u,v)22.\lVert u\rVert=d_T(0,u),\qquad\langle u,v\rangle=\frac{\lVert u\rVert^2+\lVert v\rVert^2-d_T(u,v)^2}{2}.

For nonzero vectors this last expression is ∥u∥∥v∥cos⁡∠(u,v)\lVert u\rVert\lVert v\rVert\cos\angle(u,v), where the angular distance is truncated at π\pi. Define

u⊕v=2mid⁡(u,v).u\oplus v=2\operatorname{mid}(u,v).

This operation is commutative, but no associativity or cancellation law will be used. If the directions of u,vu,v are joined by a geodesic of length less than π\pi, its cone is a Euclidean sector, and u⊕vu\oplus v is the ordinary vector sum in that sector. More generally, all two-vector calculations below are either made in such a sector or follow from the metric definition in (6.1).

The scalar-product concavity established in Lemma 5.3 implies

⟨w,u⊕v⟩≥⟨w,u⟩+⟨w,v⟩.(31)\langle w,u\oplus v\rangle\ge\langle w,u\rangle+\langle w,v\rangle. \tag*{(31)}

Indeed, apply concavity at the midpoint of u,vu,v and use homogeneity under radial dilation. This is an inequality in a general cone; we will not replace it by an equality without establishing rigidity.

We use two established equality principles for CAT(0) spaces. A triangle is flat if one vertex angle equals its Euclidean comparison angle, or if a nontrivial interior comparison inequality is an equality; see [5] and [2]. Here and below, flat means that the convex hull is isometric to the corresponding Euclidean triangle.

Lemma 6.1 (Square rigidity). Let p0,p1,p2,p3p_0,p_1,p_2,p_3 be points of a CAT(0) space, with indices taken modulo four. Suppose

d(pi,pi+1)=1,d(p0,p2)=d(p1,p3)=2.d(p_i,p_{i+1})=1,\qquad d(p_0,p_2)=d(p_1,p_3)=\sqrt{2}.

Their convex hull is a unit Euclidean square, in the indicated cyclic order. In particular, the two diagonals have the same midpoint. Proof. Let oo be the midpoint of p0,p2p_0,p_2. Squared-distance convexity gives

d(o,p1)2≤12,d(o,p3)2≤12.d(o,p_1)^2 \le\frac{1}{2}, \qquad d(o,p_3)^2 \le\frac{1}{2}.

Since

2=d(p1,p3)≤d(p1,o)+d(o,p3)≤2,\sqrt{2}=d(p_1,p_3)\le d(p_1,o)+d(o,p_3)\le\sqrt{2},

both inequalities are equalities and oo is also the midpoint of p1,p3p_1,p_3. The equality for d(o,p1)d(o,p_1) is an interior comparison equality in the triangle p1,p0,p2p_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 π/2\pi/2. The flat quadrilateral theorem [5] applies: the sum of these four angles is 2π2\pi. Its Euclidean quadrilateral has the prescribed sides and diagonals, and hence is a unit square.

The sums at the four doubled points

Suppose that ZZ is a complete CAT(0) space containing the configuration from Proposition 5.9. Use the graph vertex names for the corresponding points of ZZ. Let cc be the common hexagon center and put

r=32,T=TcZ.r=\frac{\sqrt{3}}{2}, \qquad T=T_cZ.

The completed tangent cone TT is CAT(0), and its completed space of directions is CAT(1) by [5, Theorem II.3.19]. Write

xi=log⁡cXi,yi=log⁡cYi,hH=log⁡cHx_i=\log_c X_i,\qquad y_i=\log_c Y_i,\qquad h_H=\log_c H

for the named radial vectors, and abbreviate hij=hHh_{ij}=h_H when H=ijH=ij. All these vectors have norm rr. Any two distinct line vertices H,H′H,H' occur together in a core hexagon: take their intersection point ii, choose a point j≠ij\ne i on HH and a point k≠ik\ne i on H′H', and use the XX representatives of the noncollinear triple i,j,ki,j,k. Their central triangle is flat by Proposition 5.9, and their distance is 2\sqrt{2}. Consequently

⟨hH,hH′⟩=−14for distinct lines H,H′.(32)\langle h_H,h_{H'}\rangle=-\frac{1}{4}\qquad\text{for distinct lines }H,H'. \tag*{(32)}

A line through a doubled point i∈{A,B,C,D}i\in\{A,B,C,D\} is called full at ii if it is adjacent to both XiX_i and YiY_i. All lines through A,B,CA,B,C are full; the full lines at DD are AD,BDAD,BD.

Lemma 6.2 (Fan identities). For i∈{A,B,C,D}i\in\{A,B,C,D\} there is a unit vector Mi∈TM_i\in T such that

Mi=xi⊕yi=hH⊕hH′whenever H,H′ are distinct full lines at i.(33)M_i=x_i\mathbin{\oplus}y_i=h_H\mathbin{\oplus}h_{H'} \qquad\text{whenever }H,H'\text{ are distinct full lines at }i. \tag*{(33)}

Each sum displayed here is computed in a nondegenerate Euclidean sector. Moreover,

⟨xi,yi⟩=−14,⟨Mi,hH⟩=⟨Mi,hH′⟩=12.(34)\langle x_i,y_i\rangle=-\frac{1}{4},\qquad \langle M_i,h_H\rangle=\langle M_i,h_{H'}\rangle=\frac{1}{2}. \tag*{(34)}

Proof. The four-cycle Xi,H,Yi,H′X_i,H,Y_i,H' has unit sides and diagonals of length 2\sqrt{2}, by the two-step assertions of Proposition 5.9. Lemma 6.1 makes it a flat square. Let JiJ_i be its center, which is the midpoint of Xi,YiX_i,Y_i and also of H,H′H,H'. The triangle c,H,H′c,H,H' is flat. Its median therefore gives

d(c,Ji)2=r2−14d(H,H′)2=14.d(c,J_i)^2=r^2-\frac{1}{4}d(H,H')^2=\frac{1}{4}.

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

12d(c,Xi)2+12d(c,Yi)2−14d(Xi,Yi)2=14.\frac{1}{2}d(c,X_i)^2+\frac{1}{2}d(c,Y_i)^2-\frac{1}{4}d(X_i,Y_i)^2=\frac{1}{4}.

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

xi⊕yi=2log⁡cJi=hH⊕hH′.x_i\oplus y_i=2\log_c J_i=h_H\oplus h_{H'}.

Define Mi=2log⁡cJiM_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 ⟨xi,yi⟩=−1/4\langle x_i,y_i\rangle=-1/4. The pair hH,hH′h_H,h_{H'} has angular separation arccos⁡(−1/3)<π\arccos(-1/3)<\pi, and in its Euclidean sector

⟨hH⊕hH′,hH⟩=∥hH∥2+⟨hH′,hH⟩=34−14=12.\langle h_H\oplus h_{H'},h_H\rangle=\lVert h_H\rVert^2+\langle h_{H'},h_H\rangle=\frac{3}{4}-\frac{1}{4}=\frac{1}{2}.

The same computation applies to hH′h_{H'}.

We will obtain a contradiction by evaluating the scalar product of the unit vectors MA,MBM_A,M_B in two ways. One bound is already available. At A,BA,B, the fan identities give

MA=hAB⊕hAC,MB=hAB⊕hBC.M_A=h_{AB}\oplus h_{AC},\qquad M_B=h_{AB}\oplus h_{BC}.

Apply (31) in both entries. The three lines AB,AC,BCAB,AC,BC are distinct, so (32) yields

⟨MA,MB⟩≥∥hAB∥2+⟨hAB,hBC⟩+⟨hAC,hAB⟩+⟨hAC,hBC⟩=0.(35)\langle M_A,M_B\rangle\geq\lVert h_{AB}\rVert^2+\langle h_{AB},h_{BC}\rangle+\langle h_{AC},h_{AB}\rangle+\langle h_{AC},h_{BC}\rangle=0. \tag*{(35)}

The remaining argument will force MA,MBM_A,M_B to be antipodal, with scalar product −1-1. We first use the exceptional incidence to show that MC,MDM_C,M_D are antipodal. Their axis will let us place hAC,hBC,hAD,hBDh_{AC},h_{BC},h_{AD},h_{BD} in a product R×Q\mathbb{R}\times Q, where the CAT(0) factor QQ contains a flat square formed by their second coordinates. The opposite side midpoints of that square will then force MA,MBM_A,M_B to be antipodal through the fan identities at A,BA,B.

The identity at the exceptional incidence

Set

H0=CD,h0=hCD,p=XC,q=YC,z=XD.H_0=CD,\qquad h_0=h_{CD},\qquad p=X_C,\qquad q=Y_C,\qquad z=X_D.

and let JJ be the midpoint of p,qp,q. The missing edge from YDY_D to H0H_0 is responsible for the asymmetry used in the next lemma.

Lemma 6.3 (Exceptional-incidence identity). The vectors MC,xDM_C,x_D lie in a Euclidean sector in TT, and

h0=MC⊕xD.h_0=M_C\oplus x_D.

Within this sector,

⟨MC,xD⟩=−12,⟨MC,h0⟩=12,⟨h0,xD⟩=14.(36)\langle M_C,x_D\rangle=-\frac{1}{2},\qquad\langle M_C,h_0\rangle=\frac{1}{2},\qquad\langle h_0,x_D\rangle=\frac{1}{4}. \tag*{(36)}

Proof. Apply the square construction in Lemma 6.2 at CC, using H0H_0 and any other line through CC. Since JJ is its center,

d(H0,J)2=12,d(c,J)2=14.(37)d(H_0,J)^2=\frac{1}{2},\qquad d(c,J)^2=\frac{1}{4}. \tag*{(37)}

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

d(p,z)2=d(q,z)2=2.d(p,z)^2=d(q,z)^2=2.

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

d(J,z)2≥d(H0,J)2+d(H0,z)2=32.d(J,z)^2\ge d(H_0,J)^2+d(H_0,z)^2=\frac{3}{2}.

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

d(J,z)2≤12d(p,z)2+12d(q,z)2−14d(p,q)2=32.d(J,z)^2\le\frac{1}{2}d(p,z)^2+\frac{1}{2}d(q,z)^2-\frac{1}{4}d(p,q)^2=\frac{3}{2}.

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

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

d(H0,B0)2=(23)212+(13)2=13.d(H_0,B_0)^2=\left(\frac{2}{3}\right)^2\frac{1}{2}+\left(\frac{1}{3}\right)^2=\frac{1}{3}.

Squared-distance convexity toward cc gives

d(c,B0)2≤23d(c,J)2+13d(c,z)2−29d(J,z)2=2314+1334−2932=112.\begin{aligned} d(c,B_0)^2&\le\frac{2}{3}d(c,J)^2+\frac{1}{3}d(c,z)^2-\frac{2}{9}d(J,z)^2\\ &=\frac{2}{3}\frac{1}{4}+\frac{1}{3}\frac{3}{4}-\frac{2}{9}\frac{3}{2}=\frac{1}{12}. \end{aligned}

The triangle inequality now reads

32=d(H0,c)≤d(H0,B0)+d(B0,c)≤13+123=32.\frac{\sqrt{3}}{2}=d(H_0,c)\le d(H_0,B_0)+d(B_0,c)\le\frac{1}{\sqrt{3}}+\frac{1}{2\sqrt{3}}=\frac{\sqrt{3}}{2}.

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

h0=3log⁡cB0=2j+xD=MC⊕xD.h_0=3\log_c B_0=2j+x_D=M_C\oplus x_D.

Here the two ordinary additions take place in that Euclidean sector, and MC=2jM_C=2j by Lemma 6.2. The norm identity in this sector gives

34=∥h0∥2=1+34+2⟨MC,xD⟩,\frac{3}{4}=\lVert h_0\rVert^2=1+\frac{3}{4}+2\langle M_C,x_D\rangle,

so ⟨MC,xD⟩=−1/2\langle M_C,x_D\rangle=-1/2. Pairing the sector identity with either summand yields the remaining two products in Equation (36). ∎

A semicircle in the space of directions

Lemma 6.4. The unit vectors MC,MDM_C,M_D are antipodal in TT:

dT(MC,MD)=2,⟨MC,MD⟩=−1.d_T(M_C,M_D)=2,\qquad\langle M_C,M_D\rangle=-1.

Proof. Take either full line HH at DD. The path YD,H,XD,H0Y_D,H,X_D,H_0 uses two fields of FDF_D and the loose field, so it is one of the admissible three-step paths. Thus

d(YD,H0)≥3=d(YD,c)+d(c,H0).d(Y_D,H_0)\ge\sqrt{3}=d(Y_D,c)+d(c,H_0).

Equality follows from the triangle inequality. The segment from YDY_D to H0H_0 passes through cc, and the directions of yD,h0y_D,h_0 are antipodal.

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

a=arccos⁡(1/3),b=arccos⁡(1/3).a=\arccos(1/\sqrt{3}),\qquad b=\arccos(1/3).

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

dΣ(MC^,h0^)=a,dΣ(h0^,xD^)=b.d_\Sigma(\widehat{M_C},\widehat{h_0})=a,\qquad d_\Sigma(\widehat{h_0},\widehat{x_D})=b.

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

dΣ(xD^,yD^)=arccos⁡(−1/3)=π−b.d_\Sigma(\widehat{x_D},\widehat{y_D})=\arccos(-1/3)=\pi-b.

The direction of MD=xD⊕yDM_D=x_D\oplus y_D bisects this last arc, because its two summands have equal length. Consequently dΣ(xD^,MD^)=ad_\Sigma(\widehat{x_D},\widehat{M_D})=a.

The concatenation h0^,xD^,yD^\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 xD^\widehat{x_D}. It follows that

MC^,h0^,xD^,MD^\widehat{M_C},\quad\widehat{h_0},\quad\widehat{x_D},\quad\widehat{M_D}

is a local geodesic in Σ\Sigma: continuation at h0^\widehat{h_0} holds inside the first sector, and continuation at xD^\widehat{x_D} holds inside the minimizing semicircle just described. Its length is a+b+a=πa+b+a=\pi. The space Σ\Sigma is CAT(1), so [5] 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 MC,MDM_C,M_D have norm one, the cone distance and scalar product have the stated values. □

Splitting the axis and obtaining a flat square

Proposition 6.5. No complete CAT(0) space contains the configuration asserted in Proposition 5.9.

Proof. Suppose otherwise and retain the notation above. By Equation (35), ⟨MA,MB⟩≥0\langle M_A,M_B\rangle\ge0. We will contradict this bound by splitting the axis supplied by Lemma 6.4. Use the fan identities

MC=hAC⊕hBC,MD=hAD⊕hBD.M_C=h_{AC}\oplus h_{BC},\qquad M_D=h_{AD}\oplus h_{BD}.

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

⟨MC,hAD⟩≥−12,⟨MC,hBD⟩≥−12.\langle M_C,h_{AD}\rangle\ge-\frac{1}{2},\qquad\langle M_C,h_{BD}\rangle\ge-\frac{1}{2}.

Lemma 6.4 forces equality in the chain

−1=⟨MC,MD⟩≥⟨MC,hAD⟩+⟨MC,hBD⟩≥−1.-1 = \langle M_C,M_D\rangle\ge\langle M_C,h_{AD}\rangle+ \langle M_C,h_{BD}\rangle\ge-1.

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

hAChBChADhBD⟨MC,⋅⟩1/21/2−1/2−1/2⟨MD,⋅⟩−1/2−1/21/21/2(38)\begin{array}{c|cccc} & h_{AC} & h_{BC} & h_{AD} & h_{BD} \\ \langle M_C,\cdot\rangle& 1/2 & 1/2 & -1/2 & -1/2 \\ \langle M_D,\cdot\rangle& -1/2 & -1/2 & 1/2 & 1/2 \tag*{(38)} \end{array}

The opposite rays MC,MDM_C,M_D form a complete geodesic line ℓ⊂T\ell\subset T through the cone vertex. Put a=arccos⁡(1/3)a=\arccos(1/\sqrt{3}). For each vector in the four columns of Equation (38), the angles to the two ends of ℓ\ell are aa and π−a\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] now applies in TT; it requires no properness. Write its convex parallel set as

P(ℓ)=R×Q,ℓ=R×{q0},0=(0,q0),MC=(1,q0),MD=(−1,q0).P(\ell)=\mathbb{R}\times Q,\qquad\ell=\mathbb{R}\times\{q_0\},\qquad0=(0,q_0),\qquad M_C=(1,q_0),\qquad M_D=(-1,q_0).

The factor QQ 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 MCM_C. Thus Equation (38) gives

hAC=(1/2,u),hBC=(1/2,u′),hAD=(−1/2,v),hBD=(−1/2,v′)h_{AC}=(1/2,u),\qquad h_{BC}=(1/2,u'),\qquad h_{AD}=(-1/2,v),\qquad h_{BD}=(-1/2,v')

for points u,u′,v,v′∈Qu,u',v,v'\in Q. Their distances to q0q_0 are all 1/21/\sqrt{2}, since each original vector has squared norm 3/43/4.

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

dQ(u,u′)=dQ(v,v′)=2,d_Q(u,u')=d_Q(v,v')=\sqrt{2},

and

dQ(u,v)=dQ(u,v′)=dQ(u′,v)=dQ(u′,v′)=1.d_Q(u,v)=d_Q(u,v')=d_Q(u',v)=d_Q(u',v')=1.

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

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

m=mid⁡(u,v),m′=mid⁡(u′,v′).m=\operatorname{mid}(u,v),\qquad m'=\operatorname{mid}(u',v').

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

dQ(q0,m)=dQ(q0,m′)=12,dQ(m,m′)=1.(39)d_Q(q_0,m)=d_Q(q_0,m')=\frac{1}{2},\qquad d_Q(m,m')=1. \tag*{(39)}

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.

The transverse factor $Q$ and axis $\ell = \mathbb{R} \times \{q_0\}$

Figure 3. The final contradiction takes place in the transverse factor after splitting off the MC,MDM_C,M_D axis. The cyclically ordered points u,v,u′,v′u,v,u',v' form a flat unit square in QQ, with common diagonal midpoint q0q_0. The opposite-side midpoints m,m′m,m' are distance 1/21/2 from q0q_0 and distance 11 apart. Dilation in the original tangent cone TT therefore makes MA=2(0,m)M_A=2(0,m) and MB=2(0,m′)M_B=2(0,m') antipodal unit vectors. The panels display the two distinct factors of the parallel set.

Finally, the full-line choices AC,ADAC,AD at AA and BC,BDBC,BD at BB give

MA=hAC⊕hAD=δ2(0,m),MB=hBC⊕hBD=δ2(0,m′).M_A=h_{AC}\oplus h_{AD}=\delta_2(0,m),\qquad M_B=h_{BC}\oplus h_{BD}=\delta_2(0,m').

Here δ2\delta_2 is dilation in the original cone TT; no cone structure on QQ is needed. It doubles all distances. By (39),

∥MA∥=∥MB∥=1,dT(MA,MB)=2,\lVert M_A\rVert=\lVert M_B\rVert=1,\qquad d_T(M_A,M_B)=2,

so ⟨MA,MB⟩=−1\langle M_A,M_B\rangle=-1. This contradicts (35) and proves the proposition.

Selection and the finite-model conclusion

We now assemble the arguments, keeping the order of all choices explicit.

Lemma 7.1 (A deterministic diagonal sequence). There is a sequence of realizations of the tables, with nj→∞n_j\to\infty and positive parameters αj,βj,δj→0\alpha_j,\beta_j,\delta_j\to0, such that

(i) the associated complexes PjP_j are aspherical and have a linear letter disk-filling inequality;

(ii) the master match sets are nonempty and their single-field marginals tend to uniformity in total variation;

(iii) for every admissible pair I,{e}I,\{e\} and every fixed integer tt, the common-II coupling in Proposition 4.5 has both of its total variation errors tending to zero along the sequence;

(iv) the six-letter table pair counts have uniformly vanishing relative error.

The groups Gj=π1PjG_j=\pi_1P_j are infinite.

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

αj=δj=εj,βj=8εj.\alpha_j=\delta_j=\varepsilon_j,\qquad\beta_j=8\varepsilon_j.

These parameters satisfy βj>7αj\beta_j > 7\alpha_j, and the exponent 3−βj−90δj3-\beta_j-90\delta_j of the master count is positive. Moreover,

j(βj+90δj)=98jεj<98400<12,j(\beta_j+90\delta_j)=98j\varepsilon_j<\frac{98}{400}<\frac{1}{2},

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 jj. Its coincidence inequalities hold with probability tending to one as n→∞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 nj>nj−1n_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/j1/j. Select one realization in their intersection. No comparison between the fragment threshold and nn is needed before fixing the parameters and threshold. This proves (i)–(iv).

Each GjG_j has a quotient C2C_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

1=χ(P~j)=∣Gj∣χ(Pj).1=\chi(\widetilde{P}_j)=|G_j|\chi(P_j).

Since χ(Pj)\chi(P_j) is an integer, this forces ∣Gj∣=1|G_j|=1, contrary to the quotient. Hence GjG_j is infinite.

Proposition 7.2. For all sufficiently large jj, the group GjG_j in Lemma 7.1 admits no geometric action on any proper complete CAT(0) space.

Proof. Suppose, more generally, that infinitely many GjG_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 (17). 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.

Passing to a finite simplicial model

We record the filling transfer because the conclusion is about edge loops in a finite simplicial complex, rather than just words in a presentation.

Lemma 7.3 (Finite-model filling transfer). Let PP be a finite connected CW complex with contractible universal cover. Suppose a finite presentation of π1P\pi_1P has a linear disk-filling inequality. Then PP has a finite connected simplicial homotopy model KK, whose universal cover is contractible and satisfies a linear combinatorial disk-filling inequality.

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 KK be the resulting finite simplicial model. A homotopy equivalence lifts to a homotopy equivalence of universal covers, so K~\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 LL bound the lengths of the words ϕ(b)\phi(b), let MM bound the new-presentation filling areas of the finitely many substituted old relators ψ(r)\psi(r), and let DD bound the filling areas of the words bψ(φ(b))−1b\psi(\varphi(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ℓL\ell. If the old filling constant is ColdC_{\mathrm{old}}, filling that word and replacing its relator cells costs at most MColdLℓMC_{\mathrm{old}}L\ell new cells. The boundary substitutions cost at most DℓD\ell more. Thus the new filling constant is at most MColdL+DMC_{\mathrm{old}}L+D.

Apply this to the maximal-tree presentation of the finite complex KK. Its generators correspond to the non-tree edges, and its relators to its triangular faces. A null-homotopic combinatorial edge loop in KK 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 KK with at most CℓC\ell triangular faces for a fixed finite CC.

An edge loop in K~\widetilde{K} projects to a null loop in KK. 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 PjP_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 KK. Since PjP_j has dimension two, the same-dimension construction gives a two-dimensional KK. This proves the asserted asphericity and linear filling estimate. Its fundamental group is GjG_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 LL homotopy equivalent to KK admitted a compatible locally CAT⁡(0)\operatorname{CAT}(0) geodesic length metric. The metric space LL 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]. 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)\operatorname{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 π1L≅π1K=Gj\pi_1L \cong\pi_1K = G_j therefore gives a geometric action of GjG_j on a proper complete CAT⁡(0)\operatorname{CAT}(0) space, a contradiction. This also excludes compatible locally CAT⁡(−1)\operatorname{CAT}(-1) geodesic length metrics, since a CAT⁡(−1)\operatorname{CAT}(-1) space is CAT⁡(0)\operatorname{CAT}(0) [5], Theorem II.1.12(1)]. □

Remark 7.4. The argument makes no curvature assumption on the random complexes PjP_j. Curvature comparison is used only in a hypothetical action space, after the combinatorial filling and asphericity statements have been established. Nor is a common filling constant needed for the diagonal sequence: only the constant for the single chosen finite complex appears in Theorem 1.1.

References

  1. [1]Sylwia Antoniuk, Ehud Friedgut, and Tomasz Łuczak. A sharp threshold for collapse of the random triangular group. Groups, Geometry, and Dynamics, 11(3):879–890, 2017. DOI.arxiv.org/abs/1403.3516
  2. [2]Werner Ballmann. Lectures on Spaces of Nonpositive Curvature, volume 25 of DMV Seminar. Birkhäuser, Basel, 1995. With an appendix by Misha Brin.DOI
  3. [3]Gilbert Baumslag, Alexei G. Myasnikov, and Vladimir Shpilrain. Open problems in combinatorial group theory. In Groups, Languages and Geometry, volume 250 of Contemporary Mathematics, pages 1–27. American Mathematical Society, Providence, RI, 1999. Author manuscript.DOI
  4. [4]Noel Brady and John Crisp. CAT(0) and CAT(-1) dimensions of torsion free hyperbolic groups. Commentarii Mathematici Helvetici, 82(1):61–85, 2007. DOI.DOI
  5. [5]Martin R. Bridson and André Haefliger. Metric Spaces of Non-Positive Curvature, volume 319 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, Berlin, 1999. DOI.DOI
  6. [6]Bruno Duchesne and Christopher-Lloyd Simon. The variety of group actions on all algebraic real hyperbolic spaces, 2026. Version submitted March 4, 2026; arXiv:2603.03863v1.arxiv.org/abs/2603.03863
  7. [7]Nicola Gigli and Francesco Nobili. A differential perspective on gradient flows on CAT(k)-spaces and applications. Journal of Geometric Analysis, 31:11780–11818, 2021. DOI.
  8. [8]Mikhail Gromov. Hyperbolic groups. In S. M. Gersten, editor, Essays in Group Theory, volume 8 of Mathematical Sciences Research Institute Publications, pages 75–263. Springer-Verlag, New York, 1987. DOI.DOI
  9. [9]Mikhail Gromov. Random walk in random groups. Geometric and Functional Analysis, 13(1):73–146, 2003. DOI.DOI
  10. [10]Allen Hatcher. Algebraic Topology. Cambridge University Press, 2002. Author PDF.
  11. [11]Hiroyasu Izeki, Takefumi Kondo, and Shin Nayatani. N-step energy of maps and the fixed-point property of random groups. Groups, Geometry, and Dynamics, 6(4):701–736, 2012. DOI.
  12. [12]Hiroyasu Izeki and Shin Nayatani. Combinatorial harmonic maps and discrete-group actions on Hadamard spaces. Geometriae Dedicata, 114:147–188, 2005. DOI.arxiv.org/abs/math/0410019
  13. [13]Bruce Kleiner and Bernhard Leeb. Rigidity of quasi-isometries for symmetric spaces and Euclidean buildings. Publications Mathématiques de l’IHÉS, 86:115–197, 1997. DOI.
  14. [14]Richard J. Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177–189, 1979. DOI.
  15. [15]Yann Ollivier. Sharp phase transition theorems for hyperbolicity of random groups. Geometric and Functional Analysis, 14(3):595–679, 2004. DOI.
  16. [16]Yann Ollivier and Daniel T. Wise. Cubulating random groups at density less than 1/6. Transactions of the American Mathematical Society, 363(9):4701–4733, 2011. DOI.
  17. [17]Martin Raussen and Christian Skau. Interview with Mikhail Gromov. Notices of the American Mathematical Society, 57(3):391–403, 2010. Interview of May 18, 2009; Author-hosted PDF.
  18. [18]Emily Stark. Visual metrics on boundaries of hyperbolic spaces, 2025. arXiv:2506.10108v1.arxiv.org/abs/2506.10108
  19. [19]Karl-Theodor Sturm. Probability measures on metric spaces of nonpositive curvature. In Heat Kernels and Analysis on Manifolds, Graphs, and Metric Spaces, volume 338 of Contemporary Mathematics, pages 357–390. American Mathematical Society, Providence, RI, 2003. DOI.DOI
  20. [20]Tetsu Toyoda. Fixed point property for a CAT(0) space which admits a proper cocompact group action. Kodai Mathematical Journal, 39(1):129–153, 2016. DOI.arxiv.org/abs/1102.0729

Paper details

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

views · 16

downloads · 2

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

  • Mathematics

unreleased internal OpenAI model

View statement
Looking for related papers…
Contents