In this paper
AbstractIntroductionContextStructure of the proofConventionsThe incidence template and the nested tablesPoints, lines, and fansThe independent tablesThe group and its two-complexThe master pattern and admissible testsDiagrams and linear fillingCoincidence ranksSpherical pictures and their reductionsWeights on a bounded fragmentFrom bounded fragments to all picturesConditional sampling from the nested tablesThe master pattern and its critical exponentsStars and their overlap estimatesNormalization to probability couplingsFinite tests, parameter choices, and the six-letter tableEnergy and a limiting configurationA minimizing basepoint and uniform displacement boundsConditional tests in tangent conesProducts of orbit configurationsQuadrilateral equality and hexagon centersThe ternary midpoint testThe resulting finite configurationThe geometric obstructionCone notation and square rigidityThe sums at the four doubled pointsThe identity at the exceptional incidenceA semicircle in the space of directionsSplitting the axis and obtaining a flat squareSelection and the finite-model conclusionPassing to a finite simplicial modelReferencesWorksMathematics
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() 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() 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 and a constant with the following properties.
(i) Every combinatorial edge loop of length in the universal cover of bounds a disk diagram with at most triangular faces.
(ii) The group admits no geometric action on a proper complete CAT(0) space.
In particular, is word-hyperbolic, and no finite simplicial complex homotopy equivalent to admits a locally CAT(0) geodesic length metric inducing its given topology. Consequently, no such model admits a compatible locally CAT() geodesic length metric.
The proof is an existence argument and does not give an effective size for . 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() realization question appears as Problem H11 in Baumslag–Myasnikov–Shpilrain’s 1999 problem list [3]. Both the CAT() 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() 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 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 dimension two and dimension three. These conclusions rely on constraints on translation lengths in two-dimensional targets. Theorem 1.1 excludes geometric actions in every dimension. Its finite-model consequence also allows the entire simplicial complex to change within its homotopy type: any compatible locally 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 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 spaces. We organize the relations using a fixed modification of the incidence graph of the projective plane over . 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 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 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.
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.
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.
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 , 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 and the former are [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 with the seven nonzero vectors of . A line consists of the three nonzero vectors in a two-dimensional subspace. Fix
No three of these four points are collinear. For distinct points , write for their line.
The bipartite graph has a vertex for every point, an additional vertex for , and a vertex for every line. Both representatives over a point are joined to each incident line, with one exception: the edge – is omitted. The edge
is called the loose edge. Every other edge belongs to the fan at its point . At , the fan uses only the two lines other than , so is not a vertex of .
Each is connected. At it is , at it is , and at each of the other three points it is a three-edge star. Let and . Thus
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- 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.

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 , , , form a quadrangle: no three are collinear. The thick median is the line , at which the incidence graph is modified.

Figure 2. A full fan and the exceptional fan. The blue edges and their endpoints form the indicated fans. The loose edge – belongs to but not to ; the crossed dashed segment – is absent from . In particular, is not a vertex of . The two occurrences of denote the same line vertex of .
The independent tables
For , let
These are formal signed letters; assignments are not required to use distinct letters or to produce freely reduced words. Let
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 , an array indexed by includes every tuple with probability . An included tuple, together with its type , is a fan occurrence .
(ii) An array indexed by marks every full core tuple with probability . A top occurrence is a marked tuple whose restriction to every is an included fan occurrence. We write when is the fan in one of the seven slots of .
(iii) For each unoriented nonbacktracking two-edge path in , choose one order and direction. Give a separate four-field array: its first two coordinates are the two core fields on , and its last two are new coordinates. Include each row with probability . Its relator reads , 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 with probability . 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 , with .
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 two-edge paths; the line degrees are , contributing 59 more.
The exponents in Definition 2.2 are negative. In particular,
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 candidate tuples, so the expected number of included fans is . 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
Each square table has expected size , and the six-letter table has expected size . 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 , 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 . 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 . Start with the letter bouquet, with vertex . For each fan occurrence of type , attach the cone on along its labelled map to the bouquet. The cone apex is a new vertex, also denoted . For each vertex of , its radial edge joins to the image of . 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 .
The fan cones already fill all fan cycles. To impose the remaining relations of a top occurrence , take the ordinary Fano incidence graph and subdivide the edge – once. Call the resulting graph . It has 15 vertices and 22 edges, hence cycle rank 8, matching the difference computed above. Map a point vertex to the apex of the fan in slot of , and map all line vertices and the subdivision vertex to . An ordinary incidence at maps to the radial edge indexed by its line. The subdivided exceptional incidence maps to
followed by the loose letter edge,
with the orientation giving the path from to . 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 has dimension two.
Lemma 2.3 (Presentation equivalence). The complex has the fundamental group of the letter presentation above. In particular, it has a quotient isomorphic to .
Proof. For a connected graph and a map into a connected complex, attaching its cone changes by the normal closure of the image of . It introduces no extra generator. This follows from van Kampen, or by choosing a spanning tree of 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 or then cancel, leaving a closed walk in the mapped macro graph. At , the only unreplaced edge is the loose edge; together with 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 , 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 respects all the defining relations and is surjective.
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 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 .
A match is an assignment to the fields of for which every required table entry is present, including the top mark. We denote the set of matches by . When it is nonempty, it carries its uniform probability measure. Its 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 .
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 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 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 .
Theorem 3.1. Fix sufficiently small positive with , and put and . As , the probability tends to one that 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 , , and for fans, tops, and decorations of length . The local incidence geometry compares these with the values , , and . After shared fan costs have been accounted for, the differences , , and 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 fields of each fan occurrence of type , 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 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 , with probability tending to one the following holds simultaneously for every collection of at most distinct occurrences that contains all fan slots of its tops. If the collection has tops and fans, then
where the sum is over its decorations and is the length of decoration .
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 . Write for the number of positions. Assigning letters to a pattern of rank has at most 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 .
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 with exponent
Here a shared fan occurrence appears once in the second sum, not once per top using it. Since , the expected number of realizations of the chosen pattern is at most
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 , 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 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 , including the index of each of its sides. Equal edge labels alone do not identify two side indices. For a picture mapped to , 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 is a cellular two-cycle of , there is a finite collection of spherical pictures with total cellular chain exactly .
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 is simply connected, the Hurewicz map is an isomorphism [10]. There are no three-cells. Consequently a sphere map representing the class of has cellular two-chain equal to , 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 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 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 is .
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 , minimizing among finite collections of sphere pictures whose total lifted cellular chain is exactly .
Every top polygon is a simple macro cycle.
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.
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 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 mapping to a fan apex . A step in its link is either a fan triangle or a corner of a top polygon. Suppose two different outgoing spokes at have the same radial label. Each spoke is an edge from 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 agreeing. This preserves the orientation of every face and all face maps. In terms of vertex-link cycles, it splits the link cycle of 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 , 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 be the numbers of selected top polygons, fan triangles, and decoration disks, respectively, and put .
For a top occurrence let be its number of selected top polygons, and for a decoration occurrence let be its selected multiplicity. At a fan-apex instance represented in the fragment, let count selected top turns and count selected fan triangles. It is partial if not every step of its full cyclic link is selected.
For a fan occurrence , 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
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
Write for the number of partial instances over , and let count the selected loose top sides belonging to turns at this fan. This number is zero unless has type . Each such loose side records one incidence with the exceptional radial port .
Let count internal contacts between two letter sides of the fragment. Radial side contacts are not counted in . Denote the numbers of letter and radial fragment boundary sides by and , and put .
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
Proof. Give each fan field of weight , each loose field of weight , and each field of a decoration weight . 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 . 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 , apply Equation (3.1) to the positions of weight at least . This is an eligible collection: implies for every slot . Its size is at most , since there are at most distinct tops, at most fans, and at most decorations. Sum the resulting inequalities over . Within an unsigned-value class, the sum of its ranks is its total weight minus its largest position weight. Thus, writing for the unsigned-value classes, we obtain
Every internal letter contact joins two different field positions. For fan triangles and decorations this follows from the cancellations in Lemma 3.4; for two loose top sides it follows from the same-occurrence top cancellation. A contact between different kinds of cells automatically has different positions. In each class , 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 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 in a fragment,
Moreover
Proof. First suppose . A simple top polygon has at most one turn at this fan, so . Consequently the left side of Equation (2) is at most . For a full link with , at least four fan triangles give the required inequality. For a full link with , 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 ; it may have one edge, in which case its top turn has the loose side counted by . Thus in either case its triangle count plus its loose-side payment is at least two. For the expression is nonpositive. At a represented partial link with there is at least one selected fan triangle, so its deficit is at most . With its deficit is at most one, and with it is nonpositive. Thus the error suffices in this case.
Now suppose , and choose a top occurrence with . Call its turns dominant. Let and be the total numbers of selected dominant and nondominant turns over . Nondominant selected faces have at most one turn each at this fan, including when other selected faces omit the fan entirely; hence . It follows that
Consider a full link. In its cyclic list of turns the number of consecutive dominant-to-dominant interfaces is at least the number of dominant turns minus the number of other turns. To see this, assign to each dominant turn its following turn: at most as many dominant turns can be followed by a nondominant one as there are nondominant turns. A single turn is followed by itself. Between a counted pair of turns there is a path of fan triangles. This path cannot have length zero, because then the two top polygons use the same radial side of the same occurrence , 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 and be the numbers of dominant and nondominant turns. Their linear turn list has at most blocks of dominant turns. Consequently, if counts its consecutive dominant-to-dominant interfaces, then
The fan-triangle path at each of these interfaces is entirely selected. The same indexed-side cancellation and exceptional-port argument used for a full link shows that its length plus its available loose-side payments is at least two. Different interfaces, including those in different runs, use disjoint triangle paths and distinct port incidences, so no payment is used twice. A run without turns contributes zero to the dominant-minus-nondominant count. Summing over the at most two runs therefore bounds that count by half the selected triangle count and loose-side payments, plus two.
Choose the dominant occurrence once for the entire fan occurrence , and apply these estimates separately at all its apex instances. They do not require the fragment to be connected, or every selected polygon of 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
If (3.1) holds for collections of at most 8A occurrences, then every fragment of area satisfies
Proof. Write and . Every simple top polygon has at least three turns. Summing (2), and using (3.2), gives
The right side of (3.3) can be written as
There are at most five selected triangles at a represented fan-apex instance, so . Therefore
The total number of raw side copies in the fragment is
Equations (3.3) and (3.10) imply
Since , Equations (3) and (3.11) give
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 and there is an integer such that the vertices of any finite planar multigraph of maximum degree at most can be partitioned into sets of size at most , with at most 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 vertices it gives a set of at most vertices whose removal leaves two sets, with no edges between them, each of size at most ; one may take [14] (Corollary 2). Repeat inside every set larger than , and make every removed separator vertex a singleton part.
Charge to every vertex present in a recursive set of size . 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 while they exceed . Reading that sequence backward shows that its total charge is at most
If the original graph has vertices, the number of removed separator vertices is at most , where . Every edge crossing between final parts has a removed separator vertex as an endpoint. The degree bound therefore limits their number, counting multiplicity, to . Choose so large that . Disconnected graphs are treated component by component.
Proof of Theorem 3.1. Fix the parameters, so that and in Lemma 3.7 are positive constants. Choose with , and apply Lemma 3.8 with . This gives a fixed finite threshold . By Lemma 3.2, with probability tending to one Equation (3.1) holds for all collections of at most 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 interior faces into fragments of size at most , cutting at most contacts. Let count contacts with the outside polygon; in the sphere problem set . The sum of fragment boundary lengths is at most . Lemma 3.7 applies to every fragment, and summing it gives
In a disk picture whose outside word has length , one has ; outside-to-outside pairings represent free boundary cancellations and do not add an interior contact. Thus the normal picture uses at most interior faces.
If a nonzero cellular two-cycle existed in , use its normal spherical picture supplied by Lemmas 3.3 and 3.4. For , forcing . Its cellular chain would then be zero, contrary to its construction. Therefore . 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 : at an ordinary point, its two radial paths concatenate to a fan path between the two ports; at the exceptional point the path to 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 . 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 tends to infinity. No uniform bound as 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 from Section 2, and let 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 . Thus . Write for the set of its 98 array entries and for the field support of . Each belongs to a different Bernoulli array. The order of its coordinates is fixed throughout.
A match is a map for which every required array entry is present. No injectivity is required of a single match. We write for the random set of matches and, when it is nonempty, write 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 with , , admissible, and a positive integer.
For define so that the inclusion probability of entry is . Its value and its critical value are
For a set of fields put
Thus is the expected number of assignments to for which all required entries supported in are present. The function is submodular. Indeed, for each fixed , the indicator of is supermodular, and all are nonnegative. Notice also that
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 ,
If is admissible and , then
Proof. First consider only the core part of . Let be its number of fields in , and let indicate the loose field. Before charging the top mark, the exponent is
The top-mark cost is charged only for the complete core. For that set the exponent is . 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 consists of core fields, and proves (6) when has at least two core fields. If has fewer than two core fields, no four-letter entry is charged, and no fan or top entry is charged either. In that case . 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).
Fix a conditional test . To couple matches agreeing on , we will require them to agree on a possibly larger set . The purpose of this enlargement is to make every further extension increase the critical exponent. For example, if consists of two fields in one fan , then completing that fan leaves the exponent unchanged:
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 must absorb.
In general, , and every entry support has at least three fields, so . Choose an inclusion-maximal set such that
Such a set exists because the field set is finite. The next two properties are the reason for this choice:
The first follows from Equation (7) applied to . For the second, every superset of has exponent at least by the same lemma applied to . Maximality rules out equality for a strict superset, and all critical exponents are integers.
Stars and their overlap estimates
Form a star from ordered copies of by identifying all copies of each field in . Entries supported entirely in 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 , its branch values must be pairwise distinct. Values in different fields may coincide. All fields continue to take values in the same alphabet .
This injectivity has two consequences. First, copies of an entry not supported in are distinct tuples in their array, since some one of their coordinates lies outside . Second, when one branch is fixed, an entry in another branch that is not supported in 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 . Each equality of array entries equates corresponding coordinates. For a given field , injectivity implies that these equalities give a partial matching between the 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 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 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 of them has probability at most ; the number of remaining choices is at most , whereas the number of unrestricted choices is a falling factorial , with and . Multiplying over the finitely many fields gives
Incompatible specifications simply contribute zero. If the coincident, unconditioned entries have total actual cost , their joint inclusion probability divided by the product of the two individual inclusion probabilities is . All other trials are independent. Consequently this overlap type contributes at most
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 . If is the set of fields belonging to its shared entries, then and the recovered cost is at most the sum of the costs of all entries supported in . Its critical excess is therefore at least . For sufficiently small actual parameters, every one of these finitely many positive excesses stays positive. It follows that
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
Let be the number of present injective stars. With ,
Lemma 4.3. For each fixed conditional test, sufficiently small actual parameters have the following properties as .
Fix any assignment , place it in a specified branch, and condition on it being a match. Let count its extensions to a present injective star. Its conditional mean is independent of and equals
Uniformly in , its conditional relative variance is .
Fix any ordered list of distinct letters as the values of field in the branches. Let count the present injective stars having those values. Its mean is independent of and equals
Uniformly in , its relative variance is $o(1).
Proof. For the first assertion, condition only on the Bernoulli trials used by . All other trials retain their original independent laws. Entries supported in 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 , its other values are distinct and avoid the value in , giving choices. Each extra branch requires all the entries not supported in , giving exactly Equation (4.12).
Consider an overlap of the unconditioned entries of two such extensions. In extra branch of the first extension let consist of the outside- fields involved in its shared entries. The assignment penalty in Equation (9) is : all -values are fixed, whereas every involved outside- variable is free and, by injectivity, cannot match a value in the pinned branch. Charge each shared entry to its branch in the first extension. The recovered critical cost there is at most
Thus the critical excess of assignment penalty over recovered cost is at least
for every nonempty overlap, by Equation (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 . If , 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 , its pinned values satisfy precisely its field-injectivity constraint. The other fields have choices, proving Equation (4.13).
For an overlap let be the set of variables in the first star belonging to shared entries. Write , and let be its outside- fields in branch . Let be the number of its -variables. In a realizable overlap an -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 in Equation (9).
Define using the critical entry costs in the star, counting entries entirely in once and the other entries separately in each branch. The recovered cost is at most the cost of all star entries supported in . Therefore the critical excess is at least
If , separating entries entirely in from the entries in each branch gives
Indeed the exact contribution of branch is minus the costs of entries supported in but not entirely in ; replacing by 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 -variable. Hence the excess in Equation (4.14) is at least one.
If , no shared entry meets , and entries in different branches use disjoint variables. Consequently . An active branch contains the full support of at least one shared entry. Every entry support has at least three fields, so in such a branch and Lemma 4.2 gives . 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 on a finite set we use
All convergence statements about the random tables below are in probability as ; 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 matches such that:
their restrictions to agree identically;
every branch marginal has total-variation distance from ;
the law of has total-variation distance from the uniform product law on .
Proof. Use the uniform law on present injective stars. We verify that its normalization is nonzero and has the stated properties.
Put and . For a specified branch let
The conditional variance bound of Lemma 4.3, followed by the Cauchy–Schwarz inequality, gives uniformly in each possible assignment
Multiplying by the probability that is present and summing over all assignments shows . Markov’s inequality yields in probability. By Equation (4.10), in probability. Since
we have in probability, and in particular with probability tending to one. Moreover,
The same argument applies to each of the finitely many branches. This proves the marginal assertion. Agreement on is exact because the branches agree on .
For the leaves, let be the set of ordered distinct letter lists of length , so . By the second part of Lemma 4.3,
Markov’s inequality and imply that the total variation between the leaf distribution and the uniform distribution on tends to zero, by the same displayed normalization estimate with in place of . Finally, an iid uniform list in has a repeated value with probability at most . Its distribution conditioned on distinctness is uniform on . 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 branches by a function of the -labels alone; the common -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 -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 copies of each array entry. Since , all cost increments are positive. Replacing critical costs by actual costs therefore increases any recovered-cost sum by at most
Conditioning removes trials and can only decrease this bound; a single master match is covered by . For a finite family of tests, let be the largest requested value of , or one if the family is empty. Choosing preserves every overlap margin at a value at least , including the singleton tests used below. This is compatible with : take and then take sufficiently small. The parameters are held fixed while tends to infinity. In particular, none of the variance arguments asserts uniformity for unbounded at a single fixed choice of parameters.
Let be the separate six-letter table. For positions and letters , write
Each such count is a sum of independent Bernoulli variables of parameter , and so has mean . For fixed , put . The binomial Chernoff bound gives
A union bound over the choices of positions and letters therefore proves
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 of conditional tests, there is a neighborhood of the critical parameters such that every sufficiently small fixed positive in that neighborhood with has the following properties as . With probability tending to one, the master pattern has a nonempty set of matches, its count is
every single-field marginal of its uniform law is in total variation from the uniform law on , and every test in 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 the finitely many tests , one for each field . For such a test (6) forces , 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, , and . (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 . 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 . Its completed tangent cone at is denoted by , with vertex . For , the vector has length and the direction of the geodesic from to . In a Euclidean metric cone set
Thus , where the angle is truncated at . 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
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 act properly and cocompactly by isometries on a proper complete CAT(0) space . For a finite symmetric generating alphabet , counted with its given multiplicities, the function
has a minimizer and its minimum is positive. At any minimizing basepoint, the vectors satisfy
Equivalently, is their barycenter, and
Proof. Choose a minimizing sequence and a compact set with . There are such that . Bounded energy bounds each individual displacement , since is finite. It therefore bounds
The closed neighborhood of of any fixed finite radius is compact, by properness of . Properness of the action implies that only finitely many group elements can carry a point of into that neighborhood. For each there are consequently only finitely many possibilities for . Passing to a subsequence, the entire conjugated generating tuple is constant and converges to a point . Its energy for that tuple is the original infimum. Fixing one element in the subsequence, the point attains the infimum for the original tuple. An energy of zero would make all generators, and hence , fix a point. A proper action has finite point stabilizers, so the minimum is positive.
Fix a minimizing point . First let be a tangent vector represented by a geodesic issuing from , parameterized with initial speed . For sufficiently small , convexity at the midpoints of the crossed geodesics gives
After averaging over the symmetric alphabet, the two terms on the right have the same average: apply to the second distance and replace by . Minimality and first variation now imply
Represented vectors are dense in the completed tangent cone, so continuity gives (15) for every . The cone cosine formula immediately gives (16); in particular minimizes the mean squared distance to the .
For each aspherical instance of Theorem 3.1, its group is infinite. Indeed, the parity quotient in Lemma 2.3 makes nontrivial. If were finite, the universal cover would be a finite contractible complex and
which forces . Thus Lemma 5.1 applies to any geometric action considered here. Rescale its metric so that at the minimizing basepoint
Rescaling preserves completeness, properness, and the CAT(0) condition.
Lemma 5.2. Suppose the six-letter table has pointwise relative error at most in the counts for positions 1 and , for every . Then every action normalized as in Equation (17) satisfies
The bound is independent of the action.
Proof. Write for the number of included rows whose first coordinate is and whose th coordinate is . The asserted relative estimate is
Summing over shows that rows beginning with any fixed are nonempty and that their conditional th-coordinate distribution is bounded above, pointwise, by
The relation attached to a row gives . Since , the triangle inequality and Cauchy–Schwarz give
Average over the rows beginning with and use the preceding pointwise bound and Equation (17). Each of the five conditional averages is at most , 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 to in a CAT(0) Euclidean cone, write for its point at parameter . Its squared radial norm satisfies the exact identity
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 . When their angular distance is at least , it passes through the cone vertex, and 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, is concave along every geodesic, for fixed . Suppose a finite probability distribution of vectors has barycenter and . If are independent samples and
then
For any deterministic list one also has
Proof. Subtract strong convexity of from Equation (19) in the identity . The quadratic terms cancel, proving concavity. Induction gives Equation (21).
For the independent samples, condition on . The barycenter variance inequality gives . Strong convexity of squared distance from the cone vertex therefore gives, with ,
Starting with , induction yields .
Consider now a sequence of table instances indexed by for which the conclusions of Proposition (7) hold with errors tending to zero, for every fixed test and every fixed positive integer . Suppose their groups have geometric actions as above, and choose the normalized minimizing basepoints . Write for the nonempty finite set of master matches and for its uniform distribution. Lemma 5.2 gives an absolute constant such that
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 and be disjoint sets of fields with admissible union. For each , let be a function of the labels on with values in , and suppose for a constant independent of and the match. For either fixed choice or ,
Here in a subscript denotes the letter occupying that field.
Proof. Fix . Use the coupling in Proposition 4.5: it gives matches agreeing on , each branch marginal at total variation distance at most from , and their -labels at distance at most from independent uniform letters, where . Increasing the error if necessary allows one bound for all these comparisons. Applying the fixed inversion preserves this assertion.
The vector has the same value in every branch. Form the inductive mean of the branch vectors . (21) gives, for every coupled tuple,
The last step uses only the norm bound; it does not assume that is independent of the leaves. Under independent uniform leaves, Equation (5.7) applies by Equations (5.3) and (5.4). Under the coupling, , by convexity of the ball of radius . Consequently the total variation comparison changes the expected squared norm by at most . The branch comparisons change the expectation of each scalar-product test by at most . It follows that
First take the upper limit in with fixed, and then let . All error bounds used only and , so the conclusion is uniform over the action-dependent functions in the statement.
Products of orbit configurations
Enlarge 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 ; its additional midpoint vertices are distinct abstract vertices. A master match gives a consistent orbit realization of this graph in : choose one anchor at , and send a vertex reached by the successive letters to . 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 from , where depends only on .
Take the finite product over the matches with metric
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 and take the pointed metric ultralimit . 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 indexed by the vertices of . Midpoints and fixed-fraction points on segments in the products are formed coordinatewise, and their ultralimits are the corresponding points in by uniqueness of geodesics. We identify the abstract vertex names with the resulting points. Neither properness nor a dimension bound for is needed.
Lemma 5.5. Every edge in has length one in . Every two-step path using two distinct fields of one decoration square has squared endpoint distance at least two. More generally, a path of distinct core fields whose field set is admissible has squared endpoint distance at least .
Proof. For an edge with letter , translation at its initial orbit vertex identifies its squared length with , or with the same quantity for . 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 , translate its penultimate orbit vertex to . Its earlier endpoint then becomes , and its next endpoint becomes . Set
This is a function of precisely the preceding labels, and . Equation (14) gives
in every factor. Average, apply Lemma 5.4, and take the ultralimit. Induction adds at least one at each step. Every prefix of the field sets in the statement is admissible, so the conditional test is available at each step. Distinct fields here need not carry distinct numerical letter values.
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 in a CAT(0) space, let and . Then
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 and using the segment , and then to using . 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,
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 , their joining lines, and a choice of or an available representative at each of the three points, with all six required edges present. The squared distances of its vertices 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 . The side-square sum is , whereas each diagonal-square is at least three. Both are therefore three and their midpoints coincide. Applying the same argument to identifies the third opposite-pair midpoint with the first two. Denote the resulting center of this hexagon by . Every vertex has distance
from .
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
Proof. The opposite pairs are geodesic segments through , so their directions in are antipodal and their radial lengths are . If and are any such opposite vectors, the angular triangle inequality implies
Indeed, the two angles from to their directions have sum at least , and the sum of their cosines is nonpositive.
Set , , and , with indices modulo six. Log comparison gives
The two prescribed squared distances sum to , so the lower bounds sum to zero. Equation (28) forces equality in each bound. Thus the angle at 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 . Every core vertex lies in a core hexagon, and hence is at distance from .
Proof. First use only representatives. A noncollinear ordered triple of Fano points is a basis of . Reordering a basis does not change its hexagon, and replacing one basis vector by preserves the line and the third point . The old and new hexagons therefore share the opposite pair , and their centers are its common midpoint. Permutations and elementary additions generate all changes of basis over , so the centers of all hexagons agree.
Replace one representative in a core hexagon by its representative. The new hexagon is a core hexagon, since every corresponding 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 representatives.
Every lies in a hexagon obtained by extending to a basis. Every line lies in one by choosing two points spanning that line and a third point outside it. Each has two distinct incident lines available. Choose a point other than on each of them; these two points together with are noncollinear and yield a core hexagon containing . This includes , 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 between the segment to the midpoint of and the loose edge to .
Put
in . The following argument gives an angle statement in without any assumption that angles commute with ultralimits.
Choose another line through . The core four-cycle has unit sides and both diagonals of squared length two, by Equation (5.13). Its diagonal midpoints coincide by Lemma 5.6, so
In each orbit factor let be the midpoint of the realizations of and . Translate the realization of to . The realizations of are then given by the two letters on the adjacent edges, with their fixed orientation signs. Therefore the translated vector toward is a function of just those two fields, with norm at most . The translated vector toward is , where 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 . In each factor take the points at fractions along the segments from to . 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 , respectively, gives
Thus every such comparison angle at is at least . Letting both fractions decrease to zero in proves
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 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 . If every has a proper cocompact isometric action on a proper complete CAT(0) space, then there are a complete CAT(0) space , a configuration indexed by the core vertices of , and a point with the following properties.
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.
Every core hexagon has its three opposite-pair midpoints equal to . All core vertices have distance from . For any two vertices occurring in one core hexagon, their central triangle with is flat and their tangent scalar product is given by (27).
With and , one has
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 with vertex , let denote radial dilation by . Write and
For nonzero vectors this last expression is , where the angular distance is truncated at . Define
This operation is commutative, but no associativity or cancellation law will be used. If the directions of are joined by a geodesic of length less than , its cone is a Euclidean sector, and 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
Indeed, apply concavity at the midpoint of 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 be points of a CAT(0) space, with indices taken modulo four. Suppose
Their convex hull is a unit Euclidean square, in the indicated cyclic order. In particular, the two diagonals have the same midpoint. Proof. Let be the midpoint of . Squared-distance convexity gives
Since
both inequalities are equalities and is also the midpoint of . The equality for is an interior comparison equality in the triangle , 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 . The flat quadrilateral theorem [5] applies: the sum of these four angles is . Its Euclidean quadrilateral has the prescribed sides and diagonals, and hence is a unit square.
The sums at the four doubled points
Suppose that is a complete CAT(0) space containing the configuration from Proposition 5.9. Use the graph vertex names for the corresponding points of . Let be the common hexagon center and put
The completed tangent cone is CAT(0), and its completed space of directions is CAT(1) by [5, Theorem II.3.19]. Write
for the named radial vectors, and abbreviate when . All these vectors have norm . Any two distinct line vertices occur together in a core hexagon: take their intersection point , choose a point on and a point on , and use the representatives of the noncollinear triple . Their central triangle is flat by Proposition 5.9, and their distance is . Consequently
A line through a doubled point is called full at if it is adjacent to both and . All lines through are full; the full lines at are .
Lemma 6.2 (Fan identities). For there is a unit vector such that
Each sum displayed here is computed in a nondegenerate Euclidean sector. Moreover,
Proof. The four-cycle has unit sides and diagonals of length , by the two-step assertions of Proposition 5.9. Lemma 6.1 makes it a flat square. Let be its center, which is the midpoint of and also of . The triangle is flat. Its median therefore gives
On the other hand, squared-distance convexity in the triangle has right-hand side
Thus this is also an equality, and is a flat triangle. Taking its midpoint in the tangent cone proves
Define ; it has norm one. The left-hand side makes it independent of the full-line pair chosen. The cosine law gives . The pair has angular separation , and in its Euclidean sector
The same computation applies to .
We will obtain a contradiction by evaluating the scalar product of the unit vectors in two ways. One bound is already available. At , the fan identities give
Apply (31) in both entries. The three lines are distinct, so (32) yields
The remaining argument will force to be antipodal, with scalar product . We first use the exceptional incidence to show that are antipodal. Their axis will let us place in a product , where the CAT(0) factor contains a flat square formed by their second coordinates. The opposite side midpoints of that square will then force to be antipodal through the fan identities at .
The identity at the exceptional incidence
Set
and let be the midpoint of . The missing edge from to is responsible for the asymmetry used in the next lemma.
Lemma 6.3 (Exceptional-incidence identity). The vectors lie in a Euclidean sector in , and
Within this sector,
Proof. Apply the square construction in Lemma 6.2 at , using and any other line through . Since is its center,
Also , , and the two paths and give
The ternary midpoint conclusion of Proposition 5.9 states that the angle at between the segments to is at least . Angle comparison and Equation (37) therefore imply
The reverse inequality follows from the fact that is the midpoint of :
The angle and distance comparisons are consequently equalities. The triangle is flat, with a right angle at .
Let be the point of at parameter from . Calculating in this right triangle gives
Squared-distance convexity toward gives
The triangle inequality now reads
Hence every inequality is an equality. In particular, lies on , in that order, and the triangle is flat by its interior comparison equality. Put . In the Euclidean sector containing , the vector to is . The collinearity just proved and the distances therefore imply
Here the two ordinary additions take place in that Euclidean sector, and by Lemma 6.2. The norm identity in this sector gives
so . 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 are antipodal in :
Proof. Take either full line at . The path uses two fields of and the loose field, so it is one of the admissible three-step paths. Thus
Equality follows from the triangle inequality. The segment from to passes through , and the directions of are antipodal.
Let be the completed space of directions of at , and use a hat for the direction of a nonzero vector. Define
Both lie strictly between zero and , and . Equation (36) gives
The two arcs occur consecutively in the Euclidean sector of Lemma 6.3; their concatenation is its geodesic direction arc. By Equation (34),
The direction of bisects this last arc, because its two summands have equal length. Consequently .
The concatenation has length and antipodal endpoints. It is therefore minimizing, so its two arcs continue geodesically through . It follows that
is a local geodesic in : continuation at holds inside the first sector, and continuation at holds inside the minimizing semicircle just described. Its length is . The space is CAT(1), so [5] makes this local geodesic globally minimizing, including the endpoint case of length exactly . 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 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), . We will contradict this bound by splitting the axis supplied by Lemma 6.4. Use the fan identities
The four lines in these expressions are pairwise distinct. Therefore Equation (31) implies
Lemma 6.4 forces equality in the chain
Interchanging the roles of the two sums gives the symmetric equalities. Combining these with Equation (34), we obtain
The opposite rays form a complete geodesic line through the cone vertex. Put . For each vector in the four columns of Equation (38), the angles to the two ends of are and , 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 and containing the vector. In particular, that vector lies on a complete line parallel to .
The parallel-set product decomposition [5] now applies in ; it requires no properness. Write its convex parallel set as
The factor is a CAT(0) space. Within each of the flat half-planes above, projection onto shows that the axial coordinate is the scalar product with the unit vector . Thus Equation (38) gives
for points . Their distances to are all , since each original vector has squared norm .
Distinct line vectors have squared cone distance two, by Equation (32). The product metric in Equation (6.11) therefore gives
and
Furthermore, means that the midpoint of these two line vectors is : the midpoint is the half-dilation of on the axis. Product midpoints consequently give . The identity at likewise gives .
In cyclic order , these points satisfy Lemma 6.1. They therefore span a unit flat square in , centered at . Let
They are the midpoints of opposite sides of that square, and hence
This square lies in the transverse factor only; no planar realization of the original incidence configuration has been assumed. Figure 3 records the square and the axis that has been split off.

Figure 3. The final contradiction takes place in the transverse factor after splitting off the axis. The cyclically ordered points form a flat unit square in , with common diagonal midpoint . The opposite-side midpoints are distance from and distance apart. Dilation in the original tangent cone therefore makes and antipodal unit vectors. The panels display the two distinct factors of the parallel set.
Finally, the full-line choices at and at give
Here is dilation in the original cone ; no cone structure on is needed. It doubles all distances. By (39),
so . 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 and positive parameters , such that
(i) the associated complexes 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 and every fixed integer , the common- 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 are infinite.
Proof. At stage , request all the admissible tests in the fixed master pattern with . This is a finite list. Choose small enough for Proposition 4.5 for this list and for Theorem 3.1, with , and set
These parameters satisfy , and the exponent of the master count is positive. Moreover,
so the explicit bound in Section 4 preserves every overlap margin required for the finite list.
Fix these parameters. The proof of Theorem 3.1 selects a finite fragment threshold, possibly depending on . Its coincidence inequalities hold with probability tending to one as . For the same fixed parameters, Proposition 4.5 gives the requested finite collection of sampling properties with probability tending to one. Choose so large that there is positive probability that all these events hold and all requested sampling errors are at most . Select one realization in their intersection. No comparison between the fragment threshold and is needed before fixing the parameters and threshold. This proves (i)–(iv).
Each has a quotient by Lemma 2.3. If it were finite, its universal cover would be a finite contractible CW complex, and multiplicativity of Euler characteristic would give
Since is an integer, this forces , contrary to the quotient. Hence is infinite.
Proposition 7.2. For all sufficiently large , the group in Lemma 7.1 admits no geometric action on any proper complete CAT(0) space.
Proof. Suppose, more generally, that infinitely many 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 be a finite connected CW complex with contractible universal cover. Suppose a finite presentation of has a linear disk-filling inequality. Then has a finite connected simplicial homotopy model , 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 be the resulting finite simplicial model. A homotopy equivalence lifts to a homotopy equivalence of universal covers, so is contractible.
For completeness, the linear estimate is independent of the chosen finite presentation. Choose substitutions from new generators to old words and from old generators to new words, inducing inverse group identifications. Let bound the lengths of the words , let bound the new-presentation filling areas of the finitely many substituted old relators , and let bound the filling areas of the words . The latter two lists consist of null words, and all three lists are finite, so these bounds exist. A new null word of length substitutes to an old word of length at most . If the old filling constant is , filling that word and replacing its relator cells costs at most new cells. The boundary substitutions cost at most more. Thus the new filling constant is at most .
Apply this to the maximal-tree presentation of the finite complex . Its generators correspond to the non-tree edges, and its relators to its triangular faces. A null-homotopic combinatorial edge loop in of length gives a null word of length at most 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 with at most triangular faces for a fixed finite .
An edge loop in projects to a null loop in . 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 supplied by Proposition 7.2. Its finite letter presentation has a linear disk bound by Theorem 3.1. Apply Lemma 7.3 to obtain . Since has dimension two, the same-dimension construction gives a two-dimensional . This proves the asserted asphericity and linear filling estimate. Its fundamental group is , 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 homotopy equivalent to admitted a compatible locally geodesic length metric. The metric space 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 [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 therefore gives a geometric action of on a proper complete space, a contradiction. This also excludes compatible locally geodesic length metrics, since a space is [5], Theorem II.1.12(1)]. □
Remark 7.4. The argument makes no curvature assumption on the random complexes . 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]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]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]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]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]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]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]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]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]Mikhail Gromov. Random walk in random groups. Geometric and Functional Analysis, 13(1):73–146, 2003. DOI.DOI
- [10]Allen Hatcher. Algebraic Topology. Cambridge University Press, 2002. Author PDF.
- [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]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]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]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]Yann Ollivier. Sharp phase transition theorems for hyperbolicity of random groups. Geometric and Functional Analysis, 14(3):595–679, 2004. DOI.
- [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]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]Emily Stark. Visual metrics on boundaries of hyperbolic spaces, 2025. arXiv:2506.10108v1.arxiv.org/abs/2506.10108
- [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]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