The authors developed this work with AI models from more than one developer and take responsibility for every claim. How the work was done, and what the machine checks cover, is described at the end of the paper.
Introduction
The question. Do Kaplansky’s conjectures hold for torsion-free word-hyperbolic groups? For a field K K K and a group G G G , Higman and Kaplansky asked whether, when G G G is torsion-free, the group algebra K [ G ] K[G] K [ G ] has only the trivial units λ g \lambda g λ g (λ ∈ K × \lambda\in K^{\times} λ ∈ K × , g ∈ G g \in G g ∈ G ) (U), no zero divisors (Z), and no idempotents other than 0 and 1 (I); and whether, for every group G G G , K [ G ] K[G] K [ G ] is directly finite : a b = 1 ab = 1 ab = 1 implies b a = 1 ba = 1 ba = 1 (D). Higman’s 1940 thesis contains (U) and (Z) [104 p. 112] , [50 , 51 ] ; Fox asked (Z) for integral group rings [36 p. 557] ; and Kaplansky posed (Z) for every field [56 Problem 6] and returned to the problems in [57 ] and [58 pp. 122–123] . For torsion-free G G G , (U)⇒ \Rightarrow ⇒ (Z)⇒ \Rightarrow ⇒ (I), and a failure of (D) is a failure of all three (§ 2 ). Gardam disproved (U) over F 2 \mathbb{F}_2 F 2 [38 ] , Murray extended this to every positive characteristic [78 ] and Gardam to C \mathbb{C} C [39 ] ; in 2026 OpenAI disproved (Z) [82 ] and (D) [84 , 85 , 83 ] , and Ivanov extended the failure of (Z) to every odd characteristic [53 ] . Torsion-free word-hyperbolic groups [44 ] are a central class in geometric group theory, and for them the conjectures looked robust: (D) and (I) hold in characteristic zero [58 , 75 , 101 , 16 ] . (Z) holds over every field for those that are cubulated, that is, act properly and cocompactly on a CAT(0) cube complex [3 Thm. 1.1] , [37 Thm. 1.3(1)] , and under Delzant’s large-displacement condition [29 , 2 ] . To our knowledge, no torsion-free hyperbolic group was previously known to violate any of the four.
The answer. In positive characteristic, all four fail.
Main Theorem. For every prime p p p there are a finitely presented, torsion-free, word-hyperbolic group G G G with a finite two-dimensional classifying space and elements a , b ∈ F p [ G ] a,b \in\mathbb{F}_p[G] a , b ∈ F p [ G ] with a b = 1 ≠ b a ab = 1 \ne ba ab = 1 = ba . Consequently, for every field K K K of characteristic p p p , the group algebra K [ G ] K[G] K [ G ] is not directly finite, and it contains an idempotent other than 0 and 1, a zero divisor, and a unit of order p p p that is not of the form λ g \lambda g λ g .
For every prime p p p , a single group fails all four. For p = 2 p = 2 p = 2 the group and the elements come from OpenAI’s random construction [83 ] , and what is new is that the group is hyperbolic for every outcome in an event of probability 1 − o ( 1 ) 1 - o(1) 1 − o ( 1 ) (Theorem A and Corollary 5.2 ). For odd p p p the groups are new (Theorem C). Table 1 summarizes what is known.
Table 1. Kaplansky’s conjectures for torsion-free word-hyperbolic groups, by the characteristic of the field. “Fails”: some finitely presented torsion-free hyperbolic group is a counterexample over every field of this characteristic. “Holds”: the conjecture is known for every torsion-free hyperbolic group (§ 12 ).
Three takeaways.
In positive characteristic, hyperbolicity does not protect Kaplansky’s conjectures. All four fail, for aspherical groups with a finite two-dimensional classifying space. In characteristic zero, (I) and (D) hold for torsion-free hyperbolic groups, and (Z) and (U) remain open.
The estimate that gives asphericity also gives hyperbolicity. OpenAI prove asphericity with a counting estimate that excludes spheres. A van Kampen diagram is a sphere with one extra
face, and the same estimate forces that face to be long: this is a linear isoperimetric inequality. OpenAI used this accounting for a different random complex [88 Thm. 3.1] ; here it applies to their cone complexes. We package it as a deterministic criterion on the labelled graph (Theorem B), which every random model in this paper satisfies.
(3) Direct finiteness needs one controlled failure of the cancellation. OpenAI’s certificates are parity counts. Signed on a bipartite model, they cancel modulo p p p [53 ] , because two lines of a projective plane over a field of characteristic p p p meet in 1 1 1 or q + 1 ≡ 1 q+1 \equiv1 q + 1 ≡ 1 points. A one-sided inverse needs the congruence to fail at the root, and this cannot be avoided (§ 9.2 ); we absorb the failure in the two-colour model by an exact integer-lattice solution. In characteristic zero, the decay estimate that makes the groups torsion-free rules out every cancellation built into the vertex types (§ 10 ).
Formal verification. N. Mghirbi has formalized the Main Theorem in Lean 4, for every prime p p p and with its consequences over every field of characteristic p p p [Mgh26]. The formal proof includes the random-graph estimates that the Main Theorem uses, for OpenAI’s direct-finiteness model [83 ] and for the model of § 9 , in the form it needs: for all large sizes, some outcome satisfies them. It builds on OpenAI’s Lean development for their zero-divisor model [OAI-Lean], its statements use definitions copied from OpenAI’s public formal challenges, and its main theorems use only the standard axioms (§ 13 , Appendix § 16 ). The remaining point of trust is that these definitions mean what the paper means.
Characteristic two. OpenAI note that their group whose group algebra over F 2 \mathbb{F}_2 F 2 is not directly finite is not sofic [83 §1] , and Bradford and Fournier-Facio that elements with a b = 1 ≠ b a ab=1 \ne ba ab = 1 = ba in the group algebra of a torsion-free group also disprove (I), (Z) and (U) [13 §1] . What is new for p = 2 p=2 p = 2 is hyperbolicity, for both of OpenAI’s models; Corollary 5.2 assembles the case p = 2 p=2 p = 2 .
Theorem A. Let ε > 0 \varepsilon> 0 ε > 0 be the constant of OpenAI’s bounded-pattern estimate [82 Prop. 3.1] , [83 Thm. 4.1] . For the random graphs of [82 ] and of [83 ] and all large admissible n n n , on an event E n E_n E n of probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) (Lemma 3.5 ), the group G = π 1 ( X ) G=\pi_1(X) G = π 1 ( X ) satisfies
Area ( w ) ≤ 16 13 ε ∣ w ∣ for every word w that is trivial in G , \operatorname{Area}(w) \le\frac{16}{13\varepsilon}|w| \quad\text{for every word } w \text{ that is trivial in } G, Area ( w ) ≤ 13 ε 16 ∣ w ∣ for every word w that is trivial in G , where area is taken with respect to the finite presentation (1). In particular, G G G is word-hyperbolic.
For OpenAI’s zero-divisor model, whose estimates OpenAI formalized in Lean with an explicit ε \varepsilon ε , the constant is explicit: Area ( w ) ≤ 3,036,554 ∣ w ∣ \operatorname{Area}(w) \le3{,}036{,}554\,|w| Area ( w ) ≤ 3 , 036 , 554 ∣ w ∣ (Corollary 5.4 ).
The idea. OpenAI’s group G G G is the fundamental group of a 2-complex X X X obtained by coning off the components of a random labelled graph Γ \Gamma Γ (§ 3 ). OpenAI prove that X X X is aspherical by excluding reduced spherical arrangements : spheres carrying cone disks, each bounded by a closed path γ i \gamma_i γ i in Γ \Gamma Γ , whose letters are all paired, by disjoint arcs, with inverse letters (Figure 1 (a)); discs bounded by a path from a root are excluded in the same way, which protects the roots (Figure 1 (b)). A probabilistic estimate shows that, with high probability, no bounded family of closed paths of total length H H H admits such a pairing of all but ε H \varepsilon H ε H of its letters by boundedly many intervals, never matching an edge with itself [82 Prop. 3.1] ; Euler-characteristic counting and planar separation cut any arrangement, however large, into bounded clusters of this kind [82 §4] . Now a van Kampen diagram for a word w w w is a sphere with one extra face D ∞ D_\infty D ∞ reading w w w (Figure 1 (c)). In a minimal diagram every cone letter is paired with another cone letter or with one of the ∣ w ∣ |w| ∣ w ∣ letters of D ∞ D_\infty D ∞ . Counting the latter as unpaired, OpenAI’s reduction still produces a forbidden cluster unless ∣ w ∣ ≥ 13 16 ε ∑ i ∣ γ i ∣ |w| \ge\frac{13}{16}\varepsilon\sum_i |\gamma_i| ∣ w ∣ ≥ 16 13 ε ∑ i ∣ γ i ∣ . As a cone disk bounded by a path of length h h h has area at most h h h , this is a linear isoperimetric inequality. One proposition (Proposition 4.4 ) handles all three pictures.
Figure 1. One estimate, three pictures. Cone disks are bounded by closed paths γ i \gamma_i γ i in Γ \Gamma Γ ; arcs pair inverse letters. (a) A reduced sphere: every cone letter is paired with a cone letter. (b) A disc bounded by a path u u u in Γ \Gamma Γ from a root: u u u is one more path in Γ \Gamma Γ , and its letters are counted like the others. (c) A van Kampen disc for a word w w w : the letters of w w w are discarded, so at most ∣ w ∣ |w| ∣ w ∣ cone letters (red) become unpaired. Proposition 4.4 excludes (a) and (b) and, for a minimal (c), gives ∣ w ∣ ≥ 13 16 ε ∑ i ∣ γ i ∣ ≥ 13 16 ε Area ( w ) |w| \ge\frac{13}{16}\varepsilon\sum_i |\gamma_i| \ge\frac{13}{16}\varepsilon\operatorname{Area}(w) ∣ w ∣ ≥ 16 13 ε ∑ i ∣ γ i ∣ ≥ 16 13 ε Area ( w ) .
Where a a a comes from. OpenAI’s certificate [83 Prop. 2.1] is a parity count (Proposition 5.1 ). Write Γ = Γ A ⊔ Γ B \Gamma= \Gamma_A \sqcup\Gamma_B Γ = Γ A ⊔ Γ B , fix roots x A ∈ Γ A x_A \in\Gamma_A x A ∈ Γ A and x B ∈ Γ B x_B \in\Gamma_B x B ∈ Γ B , and let A ′ A' A ′ and B ′ B' B ′ be the vertex sets of their components. For x ∈ A ′ x \in A' x ∈ A ′ let g x ∈ G g_x \in G g x ∈ G be the label of any path from x A x_A x A to x x x , and for y ∈ B ′ y \in B' y ∈ B ′ let h y h_y h y be the label of any path from x B x_B x B to y y y ; these are well defined because the cones kill all closed paths. Put
a = ∑ x ∈ A ′ g x , a ∗ = ∑ x ∈ A ′ g x − 1 , c = ∑ y ∈ B ′ h y − 1 . a = \sum_{x \in A'} g_x,\qquad a^* = \sum_{x \in A'} g_x^{-1},\qquad c = \sum_{y \in B'} h_y^{-1}. a = x ∈ A ′ ∑ g x , a ∗ = x ∈ A ′ ∑ g x − 1 , c = y ∈ B ′ ∑ h y − 1 .
The coefficient of g g g in a a ∗ aa^* a a ∗ is the parity of the number of pairs ( x , x ′ ) (x,x') ( x , x ′ ) with g x g x ′ − 1 = g g_xg_{x'}^{-1}=g g x g x ′ − 1 = g . If x x x and x ′ x' x ′ both have an outgoing edge labelled t t t , the simultaneous step ( x , x ′ ) ↦ ( x ⋅ t , x ′ ⋅ t ) (x,x') \mapsto(x \cdot t,x' \cdot t) ( x , x ′ ) ↦ ( x ⋅ t , x ′ ⋅ t ) does not change g x g x ′ − 1 g_xg_{x'}^{-1} g x g x ′ − 1 . OpenAI choose the sets S x S_x S x of outgoing labels so that ∣ S x ∩ S x ′ ∣ |S_x \cap S_{x'}| ∣ S x ∩ S x ′ ∣ is odd for all ( x , x ′ ) ≠ ( x A , x A ) (x,x') \ne(x_A,x_A) ( x , x ′ ) = ( x A , x A ) , ∣ S x A ∣ |S_{x_A}| ∣ S x A ∣ is even, and ∣ S x ∩ S y ∣ |S_x \cap S_y| ∣ S x ∩ S y ∣ is odd for x ∈ A ′ x \in A' x ∈ A ′ , y ∈ B ′ y \in B' y ∈ B ′ . By the handshake lemma, every component of the graph of simultaneous steps on A ′ × A ′ A' \times A' A ′ × A ′ has an even number of vertices, except the one containing ( x A , x A ) (x_A,x_A) ( x A , x A ) ; over F 2 \mathbb{F}_2 F 2 this gives a a ∗ = 1 aa^* = 1 a a ∗ = 1 , and the same argument on A ′ × B ′ A' \times B' A ′ × B ′ gives a c = 0 ac = 0 a c = 0 . The hard part is to show that c ≠ 0 c \ne0 c = 0 , which holds if no path from x B x_B x B to another vertex has trivial label, and that G G G is torsion-free. Both follow from the exclusions of Figure 1 (a),(Figure 1 b). Then a ∗ a ≠ 1 a^*a \ne1 a ∗ a = 1 , since otherwise c = a ∗ ( a c ) = 0 c = a^*(ac) = 0 c = a ∗ ( a c ) = 0 .
A deterministic criterion. Randomness enters the topology only through one deterministic property of Γ \Gamma Γ . Call a finite immersed labelled graph with distinguished roots pattern-free (Definition 3.3) if its vertices have degree at least 5, its girth is at least L ≥ 3 L \ge3 L ≥ 3 , its components have diameter at most d L dL d L , it has at most 2 λ L 2^{\lambda L} 2 λ L vertices, and it carries no bounded nearly-paired path system: none with at most K 0 K_0 K 0 paths of total length H ∈ [ L , C L ] H \in[L,CL] H ∈ [ L , C L ] , paired by at most I I I interval pairs with at most ε H \varepsilon H ε H letters unpaired, where K 0 , C , I K_0,C,I K 0 , C , I are explicit functions (2) of ε , d , λ \varepsilon,d,\lambda ε , d , λ .
Theorem B. If Γ \Gamma Γ is ( ε , d , λ ) (\varepsilon,d,\lambda) ( ε , d , λ ) -pattern-free at some scale L L L , then the complex X X X is aspherical, no path in Γ \Gamma Γ from a root to a different vertex has trivial label in G = π 1 ( X ) G = \pi_1(X) G = π 1 ( X ) , and every word w w w that is trivial in G G G satisfies Area ( w ) ≤ 16 13 ∣ w ∣ \operatorname{Area}(w) \le\frac{16}{13}|w| Area ( w ) ≤ 13 16 ∣ w ∣ .
The first two conclusions are OpenAI’s argument [82 Prop. 4.5 and §5] , [83 Thm. 5.2 and §6] , run for a fixed graph; the isoperimetric inequality is new. OpenAI’s random graphs are pattern-free with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) (Lemma 3.5), and so are the two random graphs we build for odd p p p (Corollaries 6.8 and 7.10). An explicit pattern-free graph with suitable types would give an explicit example (§ 12 ).
Odd characteristic. By Theorem B, building counterexamples reduces to building pattern-free graphs with suitable vertex types. OpenAI’s certificates need characteristic two. For odd p p p , finitely presented torsion-free groups with a finite two-dimensional classifying space whose group algebras over F p \mathbb{F}_p F p have zero divisors were found first by S. V. Ivanov [53 Thm. 1.1] , and independently by us, by the same signed mechanism; Ivanov has precedence. The mechanism signs OpenAI’s parity count on a bipartite random model [53 Lemma 2.2, Construction 4.1] . If Γ A \Gamma_A Γ A is bipartite, σ \sigma σ is the bipartition sign, α = ∑ x ∈ A ′ σ ( x ) g x \alpha= \sum_{x \in A'} \sigma(x)g_x α = ∑ x ∈ A ′ σ ( x ) g x and β = ∑ y ∈ B ′ h y − 1 \beta= \sum_{y \in B'} h_y^{-1} β = ∑ y ∈ B ′ h y − 1 , then a simultaneous step reverses the sign while keeping g x h y − 1 g_xh_y^{-1} g x h y − 1 fixed. Pairing each step with its reverse therefore cancels ∑ x , y ∣ S x ∩ S y ∣ σ ( x ) g x h y − 1 \sum_{x,y} |S_x \cap S_y|\sigma(x)g_xh_y^{-1} ∑ x , y ∣ S x ∩ S y ∣ σ ( x ) g x h y − 1 over Z \mathbb{Z} Z , and this sum is α β \alpha\beta α β in F p [ G ] \mathbb{F}_p[G] F p [ G ] when every such ∣ S x ∩ S y ∣ |S_x \cap S_y| ∣ S x ∩ S y ∣ is 1 modulo p p p (Lemma 6.1). Lines of the projective plane PG ( 2 , q ) \operatorname{PG}(2,q) PG ( 2 , q ) over F q \mathbb{F}_q F q , q = p k q = p^k q = p k , do this, since two of them meet in 1 or q + 1 ≡ 1 q+1 \equiv1 q + 1 ≡ 1 points; Ivanov takes q = p 3 q = p^3 q = p 3 with p p p extra letters, the same design on both sides [53 Constructions 3.1 and 3.2] . The same sign rule appears earlier, for product structures, as Mineyev’s signature condition [72 §2.2] (§ 12 ). In hyperbolic groups, zero divisors in odd characteristic are subsumed by Theorem C below, since a failure of direct finiteness gives idempotents, then zero divisors, then units (§ 2 ). The model of § 6 , whose types follow OpenAI’s asymmetric design (lines of PG ( 2 , q ) \operatorname{PG}(2,q) PG ( 2 , q ) and 2 p − 1 2p-1 2 p − 1 extra letters), adds only that groups built with the signed zero-divisor mechanism are hyperbolic (Proposition 6.9); Theorem B applies in the same way to Ivanov’s own model, given his estimates (Remark 6.10). § 9 builds on that section.
Direct finiteness, the centre of the odd-characteristic part, needs more. OpenAI’s witnesses come from one graph paired with itself and with a second graph, with a single exception at a root [83 Prop. 2.1] . We use the signed cancellation and the two-colour matchings, and pair the root component with itself. In the signed version, a = ∑ x σ ( x ) g x a = \sum_x \sigma(x)g_x a = ∑ x σ ( x ) g x and b = − ∑ x g x − 1 b = -\sum_x g_x^{-1} b = − ∑ x g x − 1 , and the types make ∣ S x ∩ S x ′ ∣ ≡ 1 ( m o d p ) |S_x \cap S_{x'}| \equiv1 \pmod p ∣ S x ∩ S x ′ ∣ ≡ 1 ( mod p ) for all x , x ′ x,x' x , x ′ in the root component, except that ∣ S r ∣ ≡ 2 |S_r| \equiv2 ∣ S r ∣ ≡ 2 at the root r r r . A type is a line of PG ( 2 , p 5 ) \operatorname{PG}(2,p^5) PG ( 2 , p 5 ) with the complement of a line of PG ( 2 , p ) \operatorname{PG}(2,p) PG ( 2 , p ) , or nothing, as its extra part, and the root carries all of PG ( 2 , p ) \operatorname{PG}(2,p) PG ( 2 , p ) ; for p = 2 p=2 p = 2 these extra parts are OpenAI’s. The exception at the root cannot be avoided, and it creates the new difficulty. The bipartite matchings need, for every letter t t t , as many vertices of one colour carrying t t t as vertices of the other colour carrying t ˉ \bar{t} t ˉ . We solve this colour-balance condition exactly, by an integer-lattice argument in which the pairing t ↦ t ˉ t \mapsto\bar{t} t ↦ t ˉ is chosen to satisfy a residue condition modulo p 5 p^5 p 5 , and we certify the decay estimate with an explicit rational Perron vector.
Theorem C. For every odd prime p p p there are a finitely presented, torsion-free, word-hyperbolic group H p H_p H p with a finite two-dimensional classifying space and elements a , b , c ∈ F p [ H p ] a,b,c \in\mathbb{F}_p[H_p] a , b , c ∈ F p [ H p ] with a b = 1 ab=1 ab = 1 , a c = 0 ac=0 a c = 0 and c ≠ 0 c \ne0 c = 0 . Hence b a ≠ 1 ba \ne1 ba = 1 , and for every field K K K of characteristic p p p the group algebra K [ H p ] K[H_p] K [ H p ] is not directly finite and contains an idempotent other than 0 and 1, a zero divisor and a unit of order p p p that is not of the form λ g \lambda g λ g . Moreover, H p H_p H p is neither sofic nor surjunctive.
Corollary 5.2 for p = 2 p=2 p = 2 and Theorem C for odd p p p give the Main Theorem. As far as we know, the groups H p H_p H p are the first torsion-free groups whose group algebras over a field of odd characteristic are not directly finite. By the implication noted by Bradford and Fournier-Facio [13 §1] , they are also counterexamples to the idempotent conjecture, and, as far as we know, the first torsion-free ones in odd characteristic: the earlier torsion-free counterexamples in odd characteristic, Ivanov’s zero divisors and Murray’s units [78 ] , do not by themselves give idempotents. OpenAI’s odd-characteristic counterexample to (D) uses a finitely generated group with torsion, over a field of order p 4 p^4 p 4 , for one specified prime p p p [85 Thm. 1.1] . Ivanov’s odd-characteristic groups have zero divisors, and nothing is claimed there about direct finiteness or idempotents. Independently, Bunina, Lee, Miasnikov and Muliarchyk gave, for every odd prime p p p , a finitely presented group whose group algebra over F p \mathbb{F}_p F p is not directly finite, by signed bipartite cancellation with a different exceptional type at the root; their proof does not use torsion-freeness, and torsion-freeness and hyperbolicity are not claimed [15 Thm. 1] . Building on the first version of this paper, Miah [71 ] gives explicit finite incidence data for one-sided inverses in odd characteristic, realized in finitely presented torsion-free hyperbolic groups. The signed form of OpenAI’s self-pairing of the root component, with its exception at the root, the exact solution of the colour-balance problem and the Perron certificate are new here.
Consequences. Since their group algebras over a finite field are not directly finite, the groups of Corollary 5.2 and Theorem C are not sofic [33 Cor. 4.7] , as OpenAI note for the group of Corollary 5.2 [83 §1] , and not surjunctive, by the standard transfer [33 §1] , [84 Prop. 7.2] (Lemma 2.4). Gottschalk’s surjunctivity conjecture {citep}[42 ] was disproved in {citep}[84 ] , see also {citep}[85 ] , with groups that have torsion. To our knowledge, the groups of {citet}Corollary 5.2 and {citet}Theorem C are the first word-hyperbolic groups known not to be surjunctive. Non-sofic hyperbolic groups were obtained in October 2026 in our note {citep}[32 ] and, independently, by Sandhu and Thom {citep}[108 ] , both building on OpenAI’s non-residually-finite hyperbolic group {citep}[87 ] ; {citet}Corollary 5.2 and {citet}Theorem C` give such groups by a different, purely algebraic certificate.
Characteristic zero. Over Z \mathbb{Z} Z the signed count of a component need not vanish. Ivanov observed that the obvious designs with constant cross-intersections destroy the decay estimate that makes the groups torsion-free, and wrote that he knew no design combining exact constancy with that estimate [53 §8.2] . § 10 proves that none exists: no variant with the cancellation built into the vertex types can work under that estimate. Such cancellation requires the incidence matrices X A , X B X_A, X_B X A , X B of the types to satisfy X A X B T = λ J X_A X_B^{\mathsf{T}} = \lambda J X A X B T = λ J , so the sum of their ranks is at most the number N N N of letters plus one. Over F p \mathbb{F}_p F p this is possible because the point–line incidence matrix of a projective plane over a field of characteristic p p p satisfies X X T = q I + J ≡ J XX^{\mathsf{T}} = qI + J \equiv J X X T = q I + J ≡ J . Over R \mathbb{R} R , the decay estimate forces each rank above N / 2 N/2 N /2 (Theorem 8.1 ).
The example with torsion. OpenAI’s first counterexample to (D) [84 ] uses a group with elements of odd prime order ℓ \ell ℓ , built by gluing copies of F ℓ 2 \mathbb{F}_\ell^2 F ℓ 2 along their lines according to an incidence structure of girth at least 12, followed by an HNN extension over finite subgroups and a direct product with a finite group. A link computation, which OpenAI’s reasoning trace for [84 ] records together with the possibility of a hyperbolic example at girth 14 [92 §§12, 17 and 21] , shows (§ 11 ):
Theorem D. The group of [84 Thm. 1.1] , whose group algebra over a finite field of characteristic two is not directly finite, acts properly and cocompactly by isometries on a CAT(0) space. If the incidence structure used to build it has girth at least 14, the group is word-hyperbolic.
What rests on OpenAI’s preprints. Corollary 5.2 , Theorems A and C, and Proposition 6.9 use four inputs about random graphs: the vertex types, the girth, the component diameter and a bounded-pattern estimate (Theorem 3.4 , Table 2 ). Everything else is proved here or classical. In the existence form that the Main Theorem uses, the inputs are formalized for both models it uses, so the Main Theorem does not rest on any unformalized OpenAI text. The probability statement of Theorem A , and Proposition 6.9, use the inputs in their probabilistic form. For OpenAI’s zerodivisor model [82 ] , OpenAI formalized them in the existence form used in Corollary 5.4 , and Ivanov reports a line-by-line check of OpenAI’s proofs of them and of the exclusion of reduced spheres [53 §1.4 and Appendix A] . For OpenAI’s direct-finiteness model [83 ] we have checked their proofs independently (§ 13 ). For our two odd-characteristic models we prove them in § 6 and § 9 : the types directly, and the other three inputs by rerunning OpenAI’s proofs with the model-dependent counts replaced, as Ivanov did for his two-colour model [53 §§4–6] ; the parts of those proofs that do not depend on the model are used as stated. Theorem D assumes [84 ] .
Table 2. The only inputs from [82 , 83 ] , and where this paper proves the corresponding inputs for its own models; everything else is proved here. For the models of § 6 and § 9 , (a) is the degree bound together with the congruences used by the signed certificates, and (b)–(d) are proved by rerunning OpenAI’s proofs. The Lean declarations listed are those of OpenAI’s development [OAI-Lean]. *Existence form, with (b) and (c) included and ε = 1 / 2467200 \varepsilon= 1/2467200 ε = 1/2467200 : for every fixed triple, some outcome satisfying (4) has the diameter bound and carries no such path system (Corollary 5.4 ). For the model of [83 ] and the model of § 9 , the formalization [Mgh26] proves (a) and, in the same existence form with explicit constants, (b)–(d) (Appendix § 16 ). The model of § 6 is not formalized.
What is due to whom. OpenAI’s [82 , 83 ] : the groups and elements of Corollaries 5.2 and 5.3 and Theorem A ; the parity certificates; the random models, the vertex types built from a projective plane and extra letters, and the girth, diameter and bounded-pattern estimates, whose proofs § 6 and § 9 rerun; the closure, interval and separation lemmas; and the cone pictures, the surgeries and the exclusion of reduced spheres and rooted discs. Also OpenAI’s are the accounting that turns such an exclusion into a linear isoperimetric inequality, for a different random complex [88 Thm. 3.1] , and the developability route through the link computation behind Theorem D, with the possibility of a hyperbolic example at girth 14, in their reasoning trace [92 §§12, 17 and 21] . In priority, Ivanov’s [53 ] : the first torsion-free zero divisors in odd characteristic, the signed cancellation, the two-colour model, the transfer of OpenAI’s estimates to that model with the colour data in the pattern count, and a decay estimate for an odd-characteristic projective-plane design certified by an explicit test vector; the same sign rule appears earlier as Mineyev’s signature condition [72 §2.2] . New here: hyperbolicity throughout (the free case of Proposition 4.4 , Theorems A and B and their consequences); the direct-finiteness construction in odd characteristic, Theorem C; the characteristic-zero obstruction, Theorem 8.1 ; and a written proof of Theorem D. The Lean formalization of the Main Theorem is N. Mghirbi’s [Mgh26]. § 13 gives a sentence-level account, including formal verification and how the work was done.
Organization. § 2 proves the algebra. § 3 defines pattern-free graphs, states the four inputs (Table 2 ) and proves the deterministic tools. § 4 proves Proposition 4.4 and Theorems A and B, and § 5 treats characteristic two (Corollaries 5.2 to 5.4 ). § 6 sets up the two-colour model and proves Proposition 6.9, § 9 proves Theorem C, and § 10 explains why the mechanism stops short of characteristic zero. § 11 proves Theorem D, § 12 discusses related work and questions, and § 13 records contributions and how the work was done. Appendix § 14 proves the interval lemma, Appendix § 15 lists the verification scripts, and Appendix § 16 lists what the Lean formalization proves.
The algebra of Kaplansky’s conjectures
Everything in this section is classical; we include the short proofs because they make the consequences stated in the Main Theorem self-evident. Rings are associative and unital, not necessarily commutative.
Lemma 2.1 (one-sided inverses). Let a , b a,b a , b be elements of a ring with a b = 1 ≠ b a ab=1\ne ba ab = 1 = ba , and put e = b a e=ba e = ba and ν = b ( 1 − e ) \nu=b(1-e) ν = b ( 1 − e ) . Then e 2 = e ∉ { 0 , 1 } e^2=e\notin\{0,1\} e 2 = e ∈ / { 0 , 1 } , e ( 1 − e ) = 0 = ( 1 − e ) e e(1-e)=0=(1-e)e e ( 1 − e ) = 0 = ( 1 − e ) e , and ν ≠ 0 = ν 2 \nu\ne0=\nu^2 ν = 0 = ν 2 ; hence ( 1 + ν ) ( 1 − ν ) = 1 = ( 1 − ν ) ( 1 + ν ) (1+\nu)(1-\nu)=1=(1-\nu)(1+\nu) ( 1 + ν ) ( 1 − ν ) = 1 = ( 1 − ν ) ( 1 + ν ) .
Proof. We have e 2 = b ( a b ) a = e e^2=b(ab)a=e e 2 = b ( ab ) a = e and ( 1 − e ) b = b − b ( a b ) = 0 (1-e)b=b-b(ab)=0 ( 1 − e ) b = b − b ( ab ) = 0 . Hence e ( 1 − e ) = 0 = ( 1 − e ) e e(1-e)=0=(1-e)e e ( 1 − e ) = 0 = ( 1 − e ) e , ν 2 = b [ ( 1 − e ) b ] ( 1 − e ) = 0 \nu^2=b[(1-e)b](1-e)=0 ν 2 = b [( 1 − e ) b ] ( 1 − e ) = 0 , and ( 1 ± ν ) ( 1 ∓ ν ) = 1 − ν 2 = 1 (1\pm\nu)(1\mp\nu)=1-\nu^2=1 ( 1 ± ν ) ( 1 ∓ ν ) = 1 − ν 2 = 1 . Finally, e ≠ 1 e\ne1 e = 1 by hypothesis, a e b = ( a b ) 2 = 1 aeb=(ab)^2=1 a e b = ( ab ) 2 = 1 gives e ≠ 0 e\ne0 e = 0 , and a ν = 1 − e ≠ 0 a\nu=1-e\ne0 a ν = 1 − e = 0 gives ν ≠ 0 \nu\ne0 ν = 0 .
Lemma 2.2 (square-zero elements give non-trivial units). Let G G G be torsion-free, K K K a field, and ν ∈ K [ G ] \nu\in K[G] ν ∈ K [ G ] with ν ≠ 0 = ν 2 \nu\ne0=\nu^2 ν = 0 = ν 2 . Then 1 + ν 1+\nu 1 + ν is a unit of K [ G ] K[G] K [ G ] that is not of the form λ g \lambda g λ g .
Proof. Its inverse is 1 − ν 1-\nu 1 − ν . Suppose that 1 + ν = λ g 1+\nu=\lambda g 1 + ν = λ g . If g = 1 g=1 g = 1 , then ν \nu ν is a scalar with ν 2 = 0 \nu^2=0 ν 2 = 0 , so ν = 0 \nu=0 ν = 0 . If g ≠ 1 g\ne1 g = 1 , then 1 , g , g 2 1,g,g^2 1 , g , g 2 are distinct because G G G is torsion-free, so ν 2 = λ 2 g 2 − 2 λ g + 1 \nu^2=\lambda^2g^2-2\lambda g+1 ν 2 = λ 2 g 2 − 2 λ g + 1 has coefficient 1 1 1 at the identity (also in characteristic two), and ν 2 ≠ 0 \nu^2\ne0 ν 2 = 0 .
In characteristic p > 0 p>0 p > 0 , moreover, ( 1 + ν ) k = 1 + k ν (1+\nu)^k=1+k\nu ( 1 + ν ) k = 1 + k ν for all k ≥ 1 k\ge1 k ≥ 1 , so the unit 1 + ν 1+\nu 1 + ν has order exactly p p p .
Lemma 2.3 (zero divisors give square-zero elements). Let G G G be torsion-free, K K K a field, and α , β ∈ K [ G ] ∖ { 0 } \alpha,\beta\in K[G]\setminus\{0\} α , β ∈ K [ G ] ∖ { 0 } with α β = 0 \alpha\beta=0 α β = 0 . Then ν = β g α \nu=\beta g\alpha ν = β g α satisfies ν ≠ 0 = ν 2 \nu\ne0=\nu^2 ν = 0 = ν 2 for some g ∈ G g\in G g ∈ G .
Proof. By Connell’s theorem, K [ G ] K[G] K [ G ] is a prime ring if and only if G G G has no non-trivial finite normal subgroup [24 , 97 Thm. 4.2.101] . So K [ G ] K[G] K [ G ] is prime, hence β K [ G ] α ≠ 0 \beta K[G]\alpha\ne0 β K [ G ] α = 0 , and since K [ G ] K[G] K [ G ] is spanned by G G G some ν = β g α \nu=\beta g\alpha ν = β g α is non-zero. Then ν 2 = β g ( α β ) g α = 0 \nu^2=\beta g(\alpha\beta)g\alpha=0 ν 2 = β g ( α β ) g α = 0 .
For torsion-free G G G , these lemmas give ( U ) ⇒ ( Z ) ⇒ ( I ) (\mathrm{U})\Rightarrow(\mathrm{Z})\Rightarrow(\mathrm{I}) ( U ) ⇒ ( Z ) ⇒ ( I ) (an idempotent e ≠ 0 , 1 e\ne0,1 e = 0 , 1 satisfies e ( 1 − e ) = 0 e(1-e)=0 e ( 1 − e ) = 0 ), and show that a counterexample to (D) is a counterexample to (I), and hence to (Z) and (U); compare [97 Ch. 13] , the introduction of [38 ] , and [13 §1] .
Lemma 2.4 (direct finiteness, surjunctivity and soficity). Let K K K be a finite field and a , b ∈ K [ G ] a,b \in K[G] a , b ∈ K [ G ] with a b = 1 ≠ b a ab=1 \ne ba ab = 1 = ba . Then the map τ : K G → K G \tau:K^{G}\to K^{G} τ : K G → K G , τ ( x ) = x ∗ a \tau(x)=x * a τ ( x ) = x ∗ a , where ( x ∗ a ) ( g ) = ∑ h x ( g h − 1 ) a ( h ) (x * a)(g)=\sum_h x(gh^{-1})a(h) ( x ∗ a ) ( g ) = ∑ h x ( g h − 1 ) a ( h ) , is a cellular automaton over the finite alphabet K K K that is injective but not surjective. Hence G G G is neither surjunctive nor sofic.
Proof. The sum is finite and τ \tau τ commutes with the left shift, so τ \tau τ is a cellular automaton with memory set ( supp a ) − 1 (\operatorname{supp}a)^{-1} ( supp a ) − 1 . Convolution is associative when the right-hand factors are finitely supported, so τ ( x ) ∗ b = x ∗ ( a b ) = x \tau(x) * b=x * (ab)=x τ ( x ) ∗ b = x ∗ ( ab ) = x , and τ \tau τ is injective. If δ 1 = τ ( y ) \delta_1=\tau(y) δ 1 = τ ( y ) , then b a = δ 1 ∗ ( b a ) = ( y ∗ a ) ∗ ( b a ) = y ∗ ( a b ) ∗ a = y ∗ a = δ 1 ba=\delta_1 * (ba)=(y * a) * (ba)=y * (ab) * a=y * a=\delta_1 ba = δ 1 ∗ ( ba ) = ( y ∗ a ) ∗ ( ba ) = y ∗ ( ab ) ∗ a = y ∗ a = δ 1 , a contradiction; so τ \tau τ is not surjective, and G G G is not surjunctive [42 ] . Since sofic groups are surjunctive [46 , 112 ] (and satisfy (D) over every field [33 Cor. 4.7] ), G G G is not sofic.
The link between direct finiteness and injective linear cellular automata is classical [27 , 98 ] ; for the stronger implication from surjunctivity to stable finiteness over every field, see also [28 ] . The finite-field scalar argument above suffices for the consequence used here. That a surjunctive group satisfies (D) over finite fields, by exactly this argument, is Elek and Szabó’s observation [33 §1] ; OpenAI give a detailed proof of the step from one-sided inverses to cellular automata [84 Prop. 7.2] .
Finally, base change : for a field extension K ⊆ L K \subseteq L K ⊆ L , the natural map K [ G ] → L [ G ] K[G]\to L[G] K [ G ] → L [ G ] is an injective unital ring homomorphism, since L [ G ] = L ⊗ K K [ G ] L[G]=L\otimes_K K[G] L [ G ] = L ⊗ K K [ G ] is a free L L L -module with basis G G G . So every identity and every non-identity above that holds over F p \mathbb{F}_p F p also holds over every field of characteristic p p p .
Cone complexes, pattern-free graphs and OpenAI’s inputs
Labelled graphs, cones and a presentation
A signed alphabet is a finite set T T T with a fixed-point-free involution t ↦ t ˉ t\mapsto\bar{t} t ↦ t ˉ ; the rose F F F has one vertex and one edge for each pair { t , t ˉ } \{t,\bar{t}\} { t , t ˉ } , and π 1 ( F ) \pi_1(F) π 1 ( F ) is the free group on T T T with t ˉ = t − 1 \bar{t}=t^{-1} t ˉ = t − 1 . In a T T T -labelled graph Γ \Gamma Γ each oriented edge carries a label, and reversed edges carry inverse labels; Γ \Gamma Γ is immersed if the labels of the edges leaving any vertex are distinct, i.e. if the label map Γ → F \Gamma\to F Γ → F is an immersion. A path is immersed if it has no backtracking, and a closed path is cyclically immersed if this also holds at its closing turn; in an immersed graph this says exactly that the label is freely, respectively cyclically, reduced. Lengths count edge traversals with multiplicity. The girth of Γ \Gamma Γ is the least length of a non-empty cyclically immersed closed path; loops and pairs of parallel edges are cycles of lengths one and two.
For each component Λ \Lambda Λ of Γ \Gamma Γ attach the cone K Λ K_\Lambda K Λ on Λ \Lambda Λ to F F F along the label map, obtaining a finite 2-complex X X X , and put G = π 1 ( X ) G=\pi_1(X) G = π 1 ( X ) . Choose a spanning tree in each component, and let R R R be the set of labels of the fundamental cycles of the non-tree edges. Attaching K Λ K_\Lambda K Λ is homotopy equivalent, relative to F F F , to attaching one 2-cell along each fundamental cycle [82 proof of Lemma 5.2] , so
G = ⟨ T ∣ R ⟩ (1) G=\langle T\mid R\rangle \tag*{(1)} G = ⟨ T ∣ R ⟩ (1)
is a finite presentation. For a word w w w that is trivial in G G G , Area ( w ) \operatorname{Area}(w) Area ( w ) is the least number of conjugates of elements of R ± 1 R^{\pm1} R ± 1 whose product is freely equal to w w w [65 Ch. V] .
Lemma 3.1. The label of a closed path of length h h h in a component Λ \Lambda Λ is freely equal to a product of at most h h h conjugates of elements of R ± 1 R^{\pm1} R ± 1 .
Proof. Up to conjugation by the label of a tree path, the closed path is equal, in the fundamental groupoid of Λ \Lambda Λ , to the product of the fundamental cycles of the non-tree edges it traverses, in order and with signs; there are at most h h h of them. Labelling is compatible with free reduction.
Path systems and pattern-free graphs
Let Γ \Gamma Γ be a finite immersed T T T -labelled graph with a finite set of distinguished vertices, the roots .
Definition 3.2 (path systems [82 §3] ). A path system is a finite family of positive-length paths in Γ \Gamma Γ , all closed and cyclically immersed except possibly one immersed interval path that starts at a root. Its occurrences are the positions on these paths; distinct occurrences may traverse the same edge. A pairing by interval pairs is a family of pairwise disjoint intervals of consecutive occurrences, matched in pairs by order-reversing bijections that match inverse letters, or by order-preserving bijections that match equal letters, subject to the reduction condition : matched occurrences traverse distinct undirected edges of Γ \Gamma Γ . Occurrences outside the paired intervals are unpaired .
Given ε ∈ ( 0 , 1 ] \varepsilon\in(0,1] ε ∈ ( 0 , 1 ] and d , λ ≥ 1 d,\lambda\ge1 d , λ ≥ 1 , put C s e p = 2 2 / ( 1 − 2 / 3 ) C_{\mathrm{sep}} = 2\sqrt{2}/(1-\sqrt{2/3}) C sep = 2 2 / ( 1 − 2/3 ) and, following OpenAI’s choices [82 Lemma 4.2 and (4.3)] , [83 Lemma 5.3 and (5.3)] ,
D 0 = ⌈ d + 4 λ + 8 ⌉ , U = max { 3 , ⌈ 96 D 0 ε ⌉ } , η = min { 1 32 U , ε 64 U } , D_0=\left\lceil d+4\lambda+8\right\rceil,\qquad U=\max\left\{3,\left\lceil\frac{96D_0}{\varepsilon}\right\rceil\right\},\qquad\eta=\min\left\{\frac{1}{32U},\frac{\varepsilon}{64U}\right\}, D 0 = ⌈ d + 4 λ + 8 ⌉ , U = max { 3 , ⌈ ε 96 D 0 ⌉ } , η = min { 32 U 1 , 64 U ε } ,
K 0 = max { 1 , ⌈ ( C s e p η ) 2 ⌉ } , C = K 0 ( U + D 0 ) , I = ⌈ 192 C ⌉ . (2) K_0=\max\left\{1,\left\lceil\left(\frac{C_{\mathrm{sep}}}{\eta}\right)^2\right\rceil\right\},\qquad C=K_0(U+D_0),\qquad I=\left\lceil192C\right\rceil. \tag*{(2)} K 0 = max { 1 , ⌈ ( η C sep ) 2 ⌉ } , C = K 0 ( U + D 0 ) , I = ⌈ 192 C ⌉ . (2)
They satisfy
3 D 0 U ≤ ε 32 , 2 η U ≤ 1 16 , 2 η U ≤ ε 32 , C s e p K 0 ≤ η . (3) \frac{3D_0}{U}\le\frac{\varepsilon}{32},\qquad2\eta U\le\frac{1}{16},\qquad2\eta U\le\frac{\varepsilon}{32},\qquad\frac{C_{\mathrm{sep}}}{\sqrt{K_0}}\le\eta. \tag*{(3)} U 3 D 0 ≤ 32 ε , 2 η U ≤ 16 1 , 2 η U ≤ 32 ε , K 0 C sep ≤ η . (3)
Definition 3.3 (pattern-free graphs). Let L ≥ 3 L\ge3 L ≥ 3 be an integer. The rooted graph Γ \Gamma Γ is ( ε , d , λ ) (\varepsilon,d,\lambda) ( ε , d , λ ) -pattern-free at scale L L L if
(P1) every vertex has degree at least 5, and girth ( Γ ) ≥ L \operatorname{girth}(\Gamma)\ge L girth ( Γ ) ≥ L ;
(P2) every component of Γ \Gamma Γ has diameter at most d L dL d L , and log 2 ∣ V ( Γ ) ∣ ≤ λ L \log_2|V(\Gamma)|\le\lambda L log 2 ∣ V ( Γ ) ∣ ≤ λ L ;
(P3) Γ \Gamma Γ carries no path system with at most K 0 K_0 K 0 paths and total length H ∈ [ L , C L ] H\in[L,CL] H ∈ [ L , C L ] with a pairing by at most I I I interval pairs leaving at most ε H \varepsilon H ε H occurrences unpaired, where K 0 , C , I K_0,C,I K 0 , C , I are given by (2) .
OpenAI’s random graphs
OpenAI choose Γ = Γ A ⊔ Γ B \Gamma=\Gamma_A\sqcup\Gamma_B Γ = Γ A ⊔ Γ B at random [82 §2] , [83 §3] : vertex sets A A A and B B B of sizes n , n n,n n , n [82 ] or n , n − v n,n-v n , n − v [83 ] , prescribed sets S x S_x S x of outgoing labels (“types”) built from the projective plane of order 128, which has v = 16513 v=16513 v = 16513 points [82 §2.1] , and in [83 §3.1] also from the Fano plane, and independent uniform matchings, conditioned on
girth ( Γ ) ≥ L = ⌊ c 0 log n ⌋ (4) \operatorname{girth}(\Gamma)\ge L=\left\lfloor c_0\log n\right\rfloor \tag*{(4)} girth ( Γ ) ≥ L = ⌊ c 0 log n ⌋ (4)
for a fixed small c 0 > 0 c_0>0 c 0 > 0 . Here n n n runs through the admissible values: multiples of 2 v 2 2v^2 2 v 2 in [82 ] , and n = v m n=vm n = v m with m ≡ 1 ( m o d 4 ) m\equiv1\pmod{4} m ≡ 1 ( mod 4 ) in [83 ] . Two roots x A ∈ A x_A\in A x A ∈ A and x B ∈ B x_B\in B x B ∈ B are fixed in advance, and A ′ , B ′ A',B' A ′ , B ′ denote the vertex sets of their components. For x ∈ A ′ x\in A' x ∈ A ′ let g x ∈ G g_x\in G g x ∈ G be the label of any path from x A x_A x A to x x x , and for y ∈ B ′ y\in B' y ∈ B ′ let h y ∈ G h_y\in G h y ∈ G be the label of any path from x B x_B x B to y y y ; these are well defined because the cones kill the labels of closed paths.
Theorem 3.4 (OpenAI’s inputs [82 , 83 ] ). In each of the two models there are constants ε > 0 \varepsilon> 0 ε > 0 and d ≥ 1 d \ge1 d ≥ 1 , depending only on the fixed data of the model, such that:
(a) every vertex has degree at least 129, and the types satisfy the parity hypotheses of Proposition 5.1(a) in the model of [82 ] , respectively of Proposition 5.1(b) in the model of [83 ] ;
(b) for all large admissible n n n some matching satisfies (4) ;
(c) with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , every component of Γ \Gamma Γ has diameter at most d L dL d L ;
(d) (bounded-pattern estimate) for every integer K 0 ≥ 1 K_0 \ge1 K 0 ≥ 1 , real C ≥ 1 C \ge1 C ≥ 1 and integer I ≥ 0 I \ge0 I ≥ 0 , with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , Γ \Gamma Γ carries no path system with roots x A , x B x_A, x_B x A , x B , at most K 0 K_0 K 0 paths and total length H ∈ [ L , C L ] H \in[L,CL] H ∈ [ L , C L ] with a pairing by at most I I I interval pairs leaving at most ε H \varepsilon H ε H occurrences unpaired.
Probabilities refer to the girth-conditioned model. Table 2 gives the sources.
The order of quantifiers in (d) is the crux: ε \varepsilon ε is fixed before K 0 , C , I K_0,C,I K 0 , C , I .
Lemma 3.5. In either model, let ε , d \varepsilon,d ε , d be as in Theorem 3.4 , λ = 1 + 2 / ( c 0 log 2 ) \lambda= 1 + 2/(c_0 \log2) λ = 1 + 2/ ( c 0 log 2 ) , and let E n E_n E n be the event that Γ \Gamma Γ , with roots x A , x B x_A, x_B x A , x B , is ( ε , d , λ ) (\varepsilon,d,\lambda) ( ε , d , λ ) -pattern-free at scale L L L . Then E n E_n E n has probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) .
Proof. (P1) holds by Theorem 3.4 (a) and (4) once L ≥ 3 L \ge3 L ≥ 3 . For large n n n we have L ≥ c 0 2 log n L \ge\frac{c_0}{2}\log n L ≥ 2 c 0 log n , so log 2 ∣ V ( Γ ) ∣ ≤ 1 + log 2 n ≤ L + 2 c 0 log 2 L = λ L \log_2 |\mathrm{V}(\Gamma)| \le1+\log_2 n \le L+\frac{2}{c_0\log2}L = \lambda L log 2 ∣ V ( Γ ) ∣ ≤ 1 + log 2 n ≤ L + c 0 l o g 2 2 L = λ L ; with Theorem 3.4 (c) this gives (P2) with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) . (P3) holds with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) by Theorem 3.4 (d) applied to the triple ( K 0 , C , I ) (K_0,C,I) ( K 0 , C , I ) of (2) .
Three deterministic tools
The next three lemmas are OpenAI’s [82 Lemmas 4.2–4.4] , [83 Lemmas 5.3–5.5] ; we include their short proofs.
Lemma 3.6 (short closures). Let Γ \Gamma Γ satisfy (P1) and (P2). Every positive-length immersed path extends to a cyclically immersed closed path by appending at most D 0 L D_0L D 0 L edges, without cancelling any of its edges.
Proof. First, for a vertex z z z and at most two undirected edges at z z z , we find a non-empty immersed closed path at z z z of length at most 2 k 2k 2 k , where k = ⌈ log 2 ∣ V ( Γ ) ∣ ⌉ + 1 k = \lceil\log_2 |V(\Gamma)|\rceil+ 1 k = ⌈ log 2 ∣ V ( Γ ) ∣ ⌉ + 1 , whose first and last edges avoid the given edges. Delete these edges; since girth ( Γ ) ≥ 3 \operatorname{girth}(\Gamma) \ge3 girth ( Γ ) ≥ 3 , every vertex keeps degree at least 3. There are at least 3 ⋅ 2 k − 1 > ∣ V ( Γ ) ∣ 3 \cdot2^{k-1} > |V(\Gamma)| 3 ⋅ 2 k − 1 > ∣ V ( Γ ) ∣ non-backtracking walks of length k k k from z z z , so two distinct ones, P P P and Q Q Q , end at the same vertex. Freely reducing P Q − 1 PQ^{-1} P Q − 1 removes only their common terminal segment; as P ≠ Q P \ne Q P = Q have the same length, what remains is the required path.
Let S S S run from a a a to b b b , and let R R R be a geodesic from b b b to a a a , of length at most d L dL d L . Choose such a closed path J b J_b J b at b b b avoiding the last edge of S S S and the first edge of R R R , and J a J_a J a at a a a avoiding the last edge of R R R and the first edge of S S S . Then S J b R J a SJ_bRJ_a S J b R J a has no backtracking at any join, including the closing one; if R R R is empty, use S J a SJ_a S J a with J a J_a J a avoiding the first and last edges of S S S . The added length is at most d L + 4 k ≤ d L + 4 ( λ L + 2 ) ≤ D 0 L dL + 4k \le dL + 4(\lambda L + 2) \le D_0L d L + 4 k ≤ d L + 4 ( λ L + 2 ) ≤ D 0 L .
Lemma 3.7 (recursive planar separation). For every integer K 0 ≥ 1 K_0 \ge1 K 0 ≥ 1 , every planar multigraph with m m m vertices has a set of at most C s e p m / K 0 C_{\mathrm{sep}}m/\sqrt{K_0} C sep m / K 0 vertices whose removal leaves components with at most K 0 K_0 K 0 vertices.
Proof. Removing loops and multiple edges changes no components. By Lipton and Tarjan [66 Cor. 2] , a simple planar graph with s s s vertices has at most 2 2 s 2\sqrt{2}\sqrt{s} 2 2 s vertices whose removal leaves components with at most 2 s / 3 2s/3 2 s /3 vertices. Apply this recursively to every component with more than K 0 K_0 K 0 vertices, charging 2 2 / s 2\sqrt{2}/\sqrt{s} 2 2 / s to each of its s s s vertices; the charges at that step total 2 2 s 2\sqrt{2}\sqrt{s} 2 2 s , which bounds the number of vertices removed. Along the recursion, the components containing a given vertex shrink by factors of at least 3 / 2 3/2 3/2 and have more than K 0 K_0 K 0 vertices, so its total charge is at most
2 2 K 0 ∑ j ≥ 0 ( 2 / 3 ) j / 2 = C s e p K 0 . {2\sqrt{2}\over\sqrt{K_0}}\sum_{j\geq0}(2/3)^{j/2}= {C_{\mathrm{sep}}\over\sqrt{K_0}}. K 0 2 2 j ≥ 0 ∑ ( 2/3 ) j /2 = K 0 C sep .
Lemma 3.8 (interval lemma). Let S S S be an oriented sphere containing disjoint closed disks D 1 , … , D N 0 D_1,\ldots,D_{N_0} D 1 , … , D N 0 . Suppose that each ∂ D i \partial D_i ∂ D i , oriented as the boundary of D i D_i D i , carries a non-empty cyclic word, and that these words are cyclically reduced except that one circle may contain a marked gap between consecutive letters, the break, where the two letters may be inverse. Suppose that disjoint arcs in S ∖ ⋃ i int D i S \setminus\bigcup_i \operatorname{int} D_i S ∖ ⋃ i int D i join the letter occurrences in pairs, each occurrence lying on exactly one arc and joined occurrences carrying inverse letters. Cut the circles into N ′ ≥ N 0 N' \ge N_0 N ′ ≥ N 0 pieces of consecutive occurrences, cutting at the break. Then the arcs are described by at most 6 N ′ 6N' 6 N ′ pairs of intervals, each interval consisting of consecutive occurrences in a single piece and each pair matched in reversed order.
The proof (Appendix § 14 ) uses only planarity and the absence of inverse adjacent letters, never that the boundaries are paths in Γ \Gamma Γ ; this is what allows a boundary reading an arbitrary word.
One estimate, three consequences
Throughout this section Γ \Gamma Γ is ( ε , d , λ ) (\varepsilon,d,\lambda) ( ε , d , λ ) -pattern-free at scale L L L , and X X X , G G G are its cone complex and group.
Cone pictures
We use pictures, the dual form of van Kampen diagrams [111 , 102 , 22 , 99 , 18 ] , in the cone version of [82 §5.1] .
Definition 4.1 (cone pictures). A cone picture consists of an oriented 2-sphere S S S , disjoint closed disks D 1 , … , D k D_1,\ldots,D_k D 1 , … , D k (k ≥ 0 k \ge0 k ≥ 0 ), the cone disks , at most one further disjoint closed disk D ∞ D_\infty D ∞ , the outer disk , and disjoint arcs in the complement of the disks, such that, reading each boundary circle as the boundary of its own disk, each ∂ D i \partial D_i ∂ D i reads the label of a closed path γ i \gamma_i γ i in Γ \Gamma Γ , every letter occurrence on the circles is an endpoint of exactly one arc, and the two occurrences joined by an arc carry inverse letters. The picture is
spherical if there is no outer disk;
free if ∂ D ∞ \partial D_\infty ∂ D ∞ reads a word; it is a capped picture for w w w if this word is w − 1 w^{-1} w − 1 ;
rooted if ∂ D ∞ \partial D_\infty ∂ D ∞ carries a marked point, the break , and read from the break reads the label of a path u u u in Γ \Gamma Γ that starts at a root.
The graph boundaries are the ∂ D i \partial D_i ∂ D i and, in the rooted case, ∂ D ∞ \partial D_\infty ∂ D ∞ ; their occurrences traverse edges of Γ \Gamma Γ . The cone length is H 0 = ∑ i ∣ γ i ∣ H_0 = \sum_i |\gamma_i| H 0 = ∑ i ∣ γ i ∣ . The picture is reduced if
(R1) k ≥ 1 k \ge1 k ≥ 1 , every γ i \gamma_i γ i is non-empty and cyclically immersed, in the free case the outer word is non-empty and cyclically reduced, and in the rooted case u u u is non-empty and immersed;
(R2) no arc joins two occurrences on graph boundaries that traverse the same undirected edge of Γ \Gamma Γ .
Lemma 4.2. (a) A non-empty word w w w is trivial in G G G if and only if it admits a capped picture, and then Area ( w ) \operatorname{Area}(w) Area ( w ) is at most the cone length of any capped picture for w w w . (b) A spherical cone picture P P P defines a map f P : S → X f_P:S\to X f P : S → X , well defined up to homotopy, and if π 2 ( X ) ≠ 0 \pi_2(X)\ne0 π 2 ( X ) = 0 , then f P f_P f P is essential for some spherical cone picture P P P .
Proof. (a) Regard the labels of all closed paths in Γ \Gamma Γ as (infinitely many) relators; their normal closure is the kernel of π 1 ( F ) → G \pi_1(F)\to G π 1 ( F ) → G , and a capped picture is a picture over this presentation in which the boundary reads w w w . If w w w is trivial, a van Kampen diagram for w w w over (1) [65 Ch. V] , placed on a sphere whose complementary face becomes D ∞ D_\infty D ∞ , is dual to such a picture: each 2-cell becomes a cone disk bounded by a fundamental cycle, and each edge is crossed by one arc [102 , 99 ] . Conversely, a picture with cone disks D 1 , … , D k D_1,\ldots,D_k D 1 , … , D k exhibits w w w as freely equal to a product of conjugates of the labels of γ 1 ± 1 , … , γ k ± 1 \gamma_1^{\pm1},\ldots,\gamma_k^{\pm1} γ 1 ± 1 , … , γ k ± 1 [99 §1] , [18 ] ; by Lemma 3.1 each of these is a product of at most ∣ γ i ∣ |\gamma_i| ∣ γ i ∣ conjugates of elements of R ± 1 R^{\pm1} R ± 1 , so Area ( w ) ≤ ∑ i ∣ γ i ∣ \operatorname{Area}(w)\le\sum_i|\gamma_i| Area ( w ) ≤ ∑ i ∣ γ i ∣ .
(b) Send the complement of the disks and of a neighbourhood of the arcs to the vertex of F F F , a neighbourhood of each arc across the corresponding edge of F F F , and D i D_i D i to the cone on γ i \gamma_i γ i in K Λ K_\Lambda K Λ . By the cone version [82 Lemma 5.2] of the classical fact for presentation complexes [102 ] , [99 §1] , [18 ] , transported along the homotopy equivalence of (1), an essential map S → X S\to X S → X is homotopic to a map that agrees with f P f_P f P for some spherical cone picture P P P , except that the preimages of the midpoints of the edges of F F F may also contain closed curves. A closed curve c c c maps to one point, so collapsing c c c writes the class as a sum of translates of the classes of the two spheres obtained from the disks bounded by c c c ; one of them is essential, and each has fewer closed curves. Induction on the number of closed curves gives an essential f P f_P f P . □
Minimal pictures are reduced
We consider three minimization problems.
(S) Spherical cone pictures P P P with f P f_P f P essential. (F) Capped pictures for a fixed non-empty cyclically reduced word w w w that is trivial in G G G .
(R) Pairs ( u , P ) (u,P) ( u , P ) , where u u u is a path from a fixed root r r r to a fixed vertex y ≠ r y \ne r y = r and P P P is a rooted cone picture whose outer disk reads u u u from the break.
In each, the complexity is H 0 H_0 H 0 , respectively H 0 H_0 H 0 , respectively ∣ u ∣ + H 0 |u|+H_0 ∣ u ∣ + H 0 , followed by the number k k k of cone disks, ordered lexicographically.
Lemma 4.3. In each of the problems (S), (F), (R), a solution of least complexity is reduced.
Proof. We list moves that apply whenever (R1) or (R2) fails. Each produces a solution of the same problem of smaller complexity, except that in (S) the last move may produce two spherical pictures, one of which is then a solution of smaller complexity. Since each cone K Λ K_\Lambda K Λ is contractible, two maps of a disc into K Λ K_\Lambda K Λ that agree on the boundary are homotopic relative to it; this is why the moves other than splitting do not change the class of f P f_P f P in (S). Moves in (F) never touch D ∞ D_\infty D ∞ .
Empty disks. A cone disk with ∣ γ i ∣ = 0 |\gamma_i|=0 ∣ γ i ∣ = 0 carries no arcs and is deleted.
Tightening. Suppose that two consecutive occurrences on a graph boundary read σ σ − 1 \sigma\sigma^{-1} σ σ − 1 for an edge σ \sigma σ (on ∂ D ∞ \partial D_\infty ∂ D ∞ , not across the break). If they are joined to each other, apply splitting below, with p p p , respectively u 2 u_2 u 2 , empty. Otherwise shrink the disk to exclude them and join their two arcs, through the excised region, into one arc, which again joins inverse letters. A cone path loses two edges, and in (R) the path u u u loses two edges and keeps its endpoints.
Merging. Suppose an arc θ \theta θ joins occurrences on two different graph boundaries that traverse the same undirected edge. Joined occurrences carry inverse letters and t ↦ t ‾ t\mapsto\overline{t} t ↦ t has no fixed points, so they traverse the edge in opposite directions, as σ \sigma σ and σ − 1 \sigma^{-1} σ − 1 . Thicken θ \theta θ to a band. The two disks and the band form one disk, whose boundary reads the path obtained by replacing σ \sigma σ in one boundary path by the rest of the other: if γ i = σ p \gamma_i=\sigma p γ i = σ p and γ j = σ − 1 q \gamma_j=\sigma^{-1}q γ j = σ − 1 q cyclically, it reads p q pq pq ; in (R), if u = u 1 σ u 2 u=u_1\sigma u_2 u = u 1 σ u 2 and γ i = σ − 1 q \gamma_i=\sigma^{-1}q γ i = σ − 1 q , it reads u 1 q u 2 u_1qu_2 u 1 q u 2 , with the same endpoints and break. The band lifts to the edge σ \sigma σ of Λ \Lambda Λ , so in (S) the new disk still maps into K Λ K_\Lambda K Λ .
Splitting. Suppose θ \theta θ joins two occurrences of σ \sigma σ and σ − 1 \sigma^{-1} σ − 1 on the same graph boundary. The disk and the band form an annulus A A A , crossed by no arc. For a cone disk, write γ i = σ p σ − 1 q \gamma_i=\sigma p\sigma^{-1}q γ i = σ p σ − 1 q , so the circles of A A A read the closed paths p p p and q q q , bounding complementary components U p U_p U p and U q U_q U q . In (F) and (R), delete everything in the component not containing D ∞ D_\infty D ∞ , and fill it together with A A A by one cone disk bounded by the other circle. In (S), let P ′ P' P ′ be obtained by filling A ∪ U p A\cup U_p A ∪ U p by a cone disk bounded by q q q , and P ′ ′ P'' P ′′ by filling A ∪ U q A\cup U_q A ∪ U q by a cone disk bounded by p p p . Capping the circles of A A A by cones in K Λ K_\Lambda K Λ splits f P f_P f P as a sum of translates of f P ′ f_{P'} f P ′ , f P ′ ′ f_{P''} f P ′′ and a map into K Λ K_\Lambda K Λ ; so one of f P ′ f_{P'} f P ′ , f P ′ ′ f_{P''} f P ′′ is essential, and both have smaller cone length. For the outer disk in (R), write u = u 1 σ u 2 σ − 1 u 3 u=u_1\sigma u_2\sigma^{-1}u_3 u = u 1 σ u 2 σ − 1 u 3 : the circles of A A A read the closed path u 2 u_2 u 2 and, from the break, u 1 u 3 u_1u_3 u 1 u 3 ; delete everything in the component bounded by the u 2 u_2 u 2 -circle and let it, with A A A , be the new outer disk.
In every case the complexity drops, by at least two in the length or by one in k k k . So a solution of least complexity admits none of these moves: its cone paths are non-empty and cyclically immersed, in (R) the path u u u is immersed, and (R2) holds. It remains to show that k ≥ 1 k\ge1 k ≥ 1 . If k = 0 k=0 k = 0 , the arcs form a non-crossing matching of inverse letters on the outer circle, so the outer word is trivial in the free group. In (F) this contradicts cyclic reducedness, and in (R) the label of the non-empty immersed path u u u is freely reduced, a contradiction. In (S), f P f_P f P maps into the graph F F F and is inessential. ∎
The key estimate
Proposition 4.4. Let P P P be a reduced cone picture. Then P P P is not rooted, and
H 0 ≤ 16 13 ε ℓ ∞ , H_0 \le\frac{16}{13\varepsilon}\ell_\infty, H 0 ≤ 13 ε 16 ℓ ∞ , where ℓ ∞ \ell_\infty ℓ ∞ is the length of the outer word (ℓ ∞ = 0 \ell_\infty= 0 ℓ ∞ = 0 if P P P is spherical). In particular, there is no reduced spherical picture.
Proof. Let H H H be the total length of the graph boundaries: H = H 0 H = H_0 H = H 0 , plus ∣ u ∣ |u| ∣ u ∣ in the rooted case. Since k ≥ 1 k \ge1 k ≥ 1 , the girth gives H ≥ H 0 ≥ L H \ge H_0 \ge L H ≥ H 0 ≥ L . Suppose that P P P is rooted, or that ℓ ∞ < 13 16 ε H 0 \ell_\infty< \frac{13}{16}\varepsilon H_0 ℓ ∞ < 16 13 ε H 0 ; we derive a contradiction. We follow the proof of [82 Prop. 4.5] (equivalently [83 Thm. 5.2] ), with a free outer disk as an extra boundary all of whose arcs are discarded.
Split and close. Keep each graph boundary path of length at most U L UL U L . Split a longer one, of length h h h , into m = ⌈ h / U L ⌉ m = \lceil h/UL\rceil m = ⌈ h / U L ⌉ consecutive segments whose lengths differ by at most one, cutting u u u along its order from the root; since U L ≥ 6 UL \ge6 U L ≥ 6 , these lengths lie between U L / 3 UL/3 U L /3 and U L UL U L . Close each segment to a cyclically immersed closed path by Lemma 3.6 , and declare the added occurrences unpaired. This gives k ′ k' k ′ pieces: closed cyclically immersed paths with between L L L and U L UL U L original occurrences and of length at most ( U + D 0 ) L (U + D_0)L ( U + D 0 ) L , and possibly the intact rooted path u u u , if ∣ u ∣ ≤ U L |u| \le UL ∣ u ∣ ≤ U L . Since m ≤ 2 h / U L m \le2h/UL m ≤ 2 h / U L , the total added length and the number of pieces satisfy
H a d d ≤ 2 D 0 U H , k ′ L ≤ H + L ≤ 2 H . (5) H_{\mathrm{add}} \le\frac{2D_0}{U}H,\qquad k'L \le H + L \le2H. \tag*{(5)} H add ≤ U 2 D 0 H , k ′ L ≤ H + L ≤ 2 H . (5)
Intervals. Apply Lemma 3.8 to P P P , with the graph boundaries cut into the k ′ k' k ′ pieces (the break being a cut) and a free outer circle as one more piece. In the rooted case there are k ′ k' k ′ pieces; otherwise every piece has at least L L L occurrences, so k ′ L ≤ H k'L \le H k ′ L ≤ H , and there is at most one more piece. Either way the arcs are described by at most 12 H / L 12H/L 12 H / L interval pairs, each interval lying in one piece. Keep only the pairs both of whose intervals lie on graph pieces; by (R2) they satisfy the reduction condition.
Separate. The multigraph whose vertices are the k ′ k' k ′ graph pieces and whose edges are the arcs between them is planar [82 proof of Prop. 4.5] : draw one vertex per piece inside its disk, and omit arcs ending on a free outer disk. By Lemma 3.7 and (3) , deleting at most η k ′ \eta k' η k ′ pieces leaves components, the clusters, of at most K 0 K_0 K 0 pieces each. The deleted pieces contain at most M d e l ≤ η k ′ U L ≤ 2 η U H M_{\mathrm{del}} \le\eta k'UL \le2\eta UH M del ≤ η k ′ U L ≤ 2 η U H original occurrences, so at most M d e l M_{\mathrm{del}} M del surviving occurrences lose their partner. An interval pair is retained if both of its intervals survive; its two pieces are then adjacent, hence in the same cluster.
Count. For a cluster Z Z Z let H Z H_Z H Z be its total length (closures included), b Z b_Z b Z its number of unpaired occurrences, and I Z I_Z I Z its number of retained interval pairs. An occurrence of Z Z Z is unpaired only if it was added by a closure, its partner was deleted, or its arc ends on a free outer disk; there are at most ℓ ∞ \ell_\infty ℓ ∞ of the last kind. By (5) and (3) ,
∑ Z H Z ≥ ( 1 − 2 η / U ) H ≥ 15 16 H , ∑ Z b Z ≤ ( 2 D 0 U + 2 η / U ) H + ℓ ∞ ≤ ε 16 H + ℓ ∞ , \sum_Z H_Z \ge(1 - 2\eta/U)H \ge\frac{15}{16}H,\qquad
\sum_Z b_Z \le\left(\frac{2D_0}{U} + 2\eta/U\right)H + \ell_\infty\le\frac{\varepsilon}{16}H + \ell_\infty, Z ∑ H Z ≥ ( 1 − 2 η / U ) H ≥ 16 15 H , Z ∑ b Z ≤ ( U 2 D 0 + 2 η / U ) H + ℓ ∞ ≤ 16 ε H + ℓ ∞ ,
and ∑ Z I Z ≤ 12 H / L \sum_Z I_Z \le12H/L ∑ Z I Z ≤ 12 H / L . Call Z Z Z good if b Z ≤ ε H Z b_Z \le\varepsilon H_Z b Z ≤ ε H Z and I Z ≤ 192 H Z / L I_Z \le192H_Z/L I Z ≤ 192 H Z / L . Clusters violating the first condition have total length at most ε − 1 ∑ Z b Z \varepsilon^{-1}\sum_Z b_Z ε − 1 ∑ Z b Z , and clusters violating the second have total length at most L 192 ∑ Z I Z \frac{L}{192}\sum_Z I_Z 192 L ∑ Z I Z . Therefore
15 16 H ≤ ∑ Z H Z ≤ 1 ε ∑ Z b Z + L 192 ∑ Z I Z + ∑ Z g o o d H Z (6) \frac{15}{16}H \le\sum_Z H_Z \le\frac{1}{\varepsilon}\sum_Z b_Z + \frac{L}{192}\sum_Z I_Z + \sum_{Z\ \mathrm{good}} H_Z \tag*{(6)} 16 15 H ≤ Z ∑ H Z ≤ ε 1 Z ∑ b Z + 192 L Z ∑ I Z + Z good ∑ H Z (6)
so the good clusters have total length at least 13 16 H − ℓ ∞ / ε \frac{13}{16}H-\ell_\infty/\varepsilon 16 13 H − ℓ ∞ / ε .
Contradiction. If P P P is not rooted, then H = H 0 H=H_0 H = H 0 , this is positive by assumption, and every cluster has length at least L L L . If P P P is rooted, then ℓ ∞ = 0 \ell_\infty=0 ℓ ∞ = 0 ; a cluster shorter than L L L consists of the intact path u u u alone, of length h < L h<L h < L , and since some cone disk is disjoint from it, H ≥ h + L > 2 h H\ge h+L>2h H ≥ h + L > 2 h . Discarding that cluster leaves good clusters of total length at least ( 13 16 − 1 2 ) H > 0 (\frac{13}{16}-\frac{1}{2})H>0 ( 16 13 − 2 1 ) H > 0 . In both cases there is a good cluster Z Z Z with H Z ≥ L H_Z\ge L H Z ≥ L . It consists of at most K 0 K_0 K 0 paths, closed and cyclically immersed except possibly the rooted path u u u , so L ≤ H Z ≤ K 0 ( U + D 0 ) L = C L L\le H_Z\le K_0(U+D_0)L=CL L ≤ H Z ≤ K 0 ( U + D 0 ) L = C L ; it has b Z ≤ ε H Z b_Z\le\varepsilon H_Z b Z ≤ ε H Z and I Z ≤ 192 H Z / L ≤ 192 C ≤ I I_Z\le192H_Z/L\le192C\le I I Z ≤ 192 H Z / L ≤ 192 C ≤ I ; and its retained pairs form a pairing by interval pairs satisfying the reduction condition. This contradicts (P3).
Remark 4.5. Proposition 4.4 is OpenAI’s exclusion argument [82 Prop. 4.5] , [83 Thm. 5.2] with one new case. A free outer disk differs from OpenAI’s boundaries in three ways: it is not a path in Γ \Gamma Γ , which is harmless because its arcs are discarded and the interval lemma needs only cyclic reducedness; its at most ℓ ∞ \ell_\infty ℓ ∞ arcs add at most ℓ ∞ \ell_\infty ℓ ∞ unpaired occurrences, the source of the term ℓ ∞ / ε \ell_\infty/\varepsilon ℓ ∞ / ε in (6) ; and no surgery touches it. No union bound over the size of the picture is used: the same fixed triple ( K 0 , C , I ) (K_0,C,I) ( K 0 , C , I ) handles every sphere, every rooted disc and every word. The same accounting, with contacts on the outer boundary paid for by its length, gives a linear isoperimetric inequality for a different random complex in [88 Thm. 3.1 and Lemma 3.8] .
Asphericity, root protection and hyperbolicity
Proof of Theorem B. Asphericity. If π 2 ( X ) ≠ 0 \pi_2(X)\ne0 π 2 ( X ) = 0 , Lemma 4.2 (b) gives a spherical cone picture P P P with f P f_P f P essential; by Lemma 4.3 one of least complexity is reduced, contradicting Proposition 4.4 . So π 2 ( X ) = 0 \pi_2(X)=0 π 2 ( X ) = 0 . The universal cover of X X X is a simply connected 2-complex with H 2 ≅ π 2 ( X ) = 0 H_2\cong\pi_2(X)=0 H 2 ≅ π 2 ( X ) = 0 , hence contractible [49 Thm. 4.32, Cor. 4.33] . Thus X X X is a finite two-dimensional K ( G , 1 ) K(G,1) K ( G , 1 ) , and G G G , having a finite-dimensional classifying space, is torsion-free [20 §VIII.2] .
Roots. Suppose that a path u u u from a root r r r to a vertex y ≠ r y\ne r y = r has trivial label; u u u is non-empty. By Lemma 4.2 (a), the word w w w with w − 1 = label ( u ) w^{-1}=\operatorname{label}(u) w − 1 = label ( u ) has a capped picture; marking a break between the last and first letters of ∂ D ∞ \partial D_\infty ∂ D ∞ makes it a rooted picture for u u u . By Lemma 4.3 , a pair of least complexity in problem (R) is reduced, contradicting Proposition 4.4 .
Isoperimetry. Free reduction and cyclic permutation do not increase length, and conjugation does not change area, so it suffices to take w w w non-empty and cyclically reduced. By Lemma 4.2 (a) and Lemma 4.3 , a capped picture for w w w of least complexity is reduced, and by Lemma 4.2 (a) and Proposition 4.4 , Area ( w ) ≤ H 0 ≤ 16 13 ε ∣ w ∣ \operatorname{Area}(w)\le H_0\le\frac{16}{13\varepsilon}|w| Area ( w ) ≤ H 0 ≤ 13 ε 16 ∣ w ∣ .
Proof of Theorem A . On the event E n E_n E n of Lemma 3.5 , Γ \Gamma Γ is pattern-free, so Theorem B gives the isoperimetric inequality. A finitely presented group with a linear Dehn function is word-hyperbolic. This is Gromov’s theorem [44 2.3.D, proved in 6.8] ; complete proofs are given in [1 Thm. 2.5] , [93 ] and [14 Thm. III.H.2.9] , and see [19 Thm. 6.1.5] .
Characteristic two
Proposition 5.1. (OpenAI’s parity certificates [82 §6] , [83 Prop. 2.1] ). Let Γ = Γ A ⊔ Γ B \Gamma=\Gamma_A\sqcup\Gamma_B Γ = Γ A ⊔ Γ B be a finite immersed labelled graph without loops, with roots x A , x B x_A,x_B x A , x B , notation as in § 3.3 , and let S x S_x S x be the set of labels of the edges leaving x x x . Put a = ∑ x ∈ A ′ g x a=\sum_{x\in A'}g_x a = ∑ x ∈ A ′ g x and c = ∑ y ∈ B ′ h y − 1 c=\sum_{y\in B'}h_y^{-1} c = ∑ y ∈ B ′ h y − 1 in F 2 [ G ] \mathbb{F}_2[G] F 2 [ G ] .
(a) If ∣ S x ∩ S y ∣ |S_x\cap S_y| ∣ S x ∩ S y ∣ is odd for all x ∈ A ′ x\in A' x ∈ A ′ and y ∈ B ′ y\in B' y ∈ B ′ , then a c = 0 ac=0 a c = 0 .
(b) If moreover ∣ S x ∩ S x ′ ∣ |S_x \cap S_{x'}| ∣ S x ∩ S x ′ ∣ is odd for all ( x , x ′ ) ∈ A ′ × A ′ (x,x') \in A' \times A' ( x , x ′ ) ∈ A ′ × A ′ other than ( x A , x A ) (x_A,x_A) ( x A , x A ) , and ∣ S x A ∣ |S_{x_A}| ∣ S x A ∣ is even, then a a ∗ = 1 aa^* = 1 a a ∗ = 1 .
(c) If no path from x A x_A x A , respectively x B x_B x B , to a different vertex has trivial label, then a ≠ 0 a \ne0 a = 0 , respectively c ≠ 0 c \ne0 c = 0 ; in case (b) then a ∗ a ≠ 1 a^*a \ne1 a ∗ a = 1 .
Proof. For x ∈ A ′ x \in A' x ∈ A ′ and t ∈ S x t \in S_x t ∈ S x let x ⋅ t x \mathbin{\cdot} t x ⋅ t be the end of the edge labelled t t t at x x x , so that g x ⋅ t = g x t g_{x\mathbin{\cdot}t}=g_xt g x ⋅ t = g x t . On A ′ × B ′ A' \times B' A ′ × B ′ , join ( x , y ) (x,y) ( x , y ) to ( x ⋅ t , y ⋅ t ) (x\mathbin{\cdot}t,y\mathbin{\cdot}t) ( x ⋅ t , y ⋅ t ) for every t ∈ S x ∩ S y t \in S_x \cap S_y t ∈ S x ∩ S y ; the step labelled t ˉ \bar{t} t ˉ at the endpoint is the same edge reversed. This multigraph has no loops, the vertex ( x , y ) (x,y) ( x , y ) has degree ∣ S x ∩ S y ∣ |S_x \cap S_y| ∣ S x ∩ S y ∣ , and g x h y − 1 g_xh_y^{-1} g x h y − 1 is constant on each component, since ( g x t ) ( h y t ) − 1 = g x h y − 1 (g_xt)(h_yt)^{-1}=g_xh_y^{-1} ( g x t ) ( h y t ) − 1 = g x h y − 1 . By the handshake lemma, a component in which every degree is odd has an even number of vertices. The coefficient of g g g in a c = ∑ x , y g x h y − 1 ac=\sum_{x,y}g_xh_y^{-1} a c = ∑ x , y g x h y − 1 is the number of vertices with value g g g , a sum of sizes of components, hence even: (a). In (b), the same multigraph on A ′ × A ′ A' \times A' A ′ × A ′ , with values g x g x ′ − 1 g_xg_{x'}^{-1} g x g x ′ − 1 , has odd degrees except at ( x A , x A ) (x_A,x_A) ( x A , x A ) , whose component therefore has odd size and value 1 1 1 ; all other components have even size, so a a ∗ = ∑ x , x ′ g x g x ′ − 1 = 1 aa^*=\sum_{x,x'}g_xg_{x'}^{-1}=1 a a ∗ = ∑ x , x ′ g x g x ′ − 1 = 1 . In (c), only x A x_A x A contributes 1 1 1 to a a a , and only x B x_B x B to c c c , so their coefficients of 1 1 1 are 1 1 1 . Finally, if a ∗ a = 1 a^*a=1 a ∗ a = 1 then c = a ∗ ( a c ) = 0 c=a^*(ac)=0 c = a ∗ ( a c ) = 0 .
Corollary 5.2. (the case p = 2 p=2 p = 2 ; G G G and a a a from [83 Thm. 1.1 and Prop. 2.1] ). There are a finitely presented, torsion-free, word-hyperbolic group G G G with a finite two-dimensional classifying space and an element a ∈ F 2 [ G ] a \in\mathbb{F}_2[G] a ∈ F 2 [ G ] with a a ∗ = 1 ≠ a ∗ a aa^*=1 \ne a^*a a a ∗ = 1 = a ∗ a . Consequently, with e = a ∗ a e=a^*a e = a ∗ a and ν = a ∗ ( 1 − e ) \nu=a^*(1-e) ν = a ∗ ( 1 − e ) : (i) e e e is an idempotent different from 0 0 0 and 1 1 1 , so (I) and (D) fail; (ii) e ( 1 − e ) = 0 e(1-e)=0 e ( 1 − e ) = 0 with e ≠ 0 ≠ 1 − e e\ne0\ne1-e e = 0 = 1 − e , so (Z) fails; (iii) ν ≠ 0 = ν 2 \nu\ne0=\nu^2 ν = 0 = ν 2 , so 1 + ν 1+\nu 1 + ν is a unit of order two that is not of the form λ g \lambda g λ g , so (U) fails. Moreover, G G G is neither sofic nor surjunctive.
Proof of Corollary 5.2 . Work in the model of [83 ] , choose n n n large and Γ ∈ E n \Gamma\in E_n Γ ∈ E n (Lemma 3.5 ), and let G = π 1 ( X ) G=\pi_1(X) G = π 1 ( X ) . By Theorem B, X X X is a finite aspherical 2-complex, so G G G is finitely presented, torsion-free and has a finite two-dimensional classifying space; its roots are protected; and G G G is word-hyperbolic. Γ \Gamma Γ has no loops, and by Theorem 3.4 (a) its types satisfy the hypotheses of Proposition 5.1 (b), so a a ∗ = 1 ≠ a ∗ a aa^*=1\ne a^*a a a ∗ = 1 = a ∗ a . Items (i)–(iii) follow from Lemma 2.1 with b = a ∗ b=a^* b = a ∗ and Lemma 2.2 , and ( 1 + ν ) 2 = 1 + ν 2 = 1 (1+\nu)^2=1+\nu^2=1 ( 1 + ν ) 2 = 1 + ν 2 = 1 in characteristic two. Lemma 2.4 shows that G G G is neither sofic nor surjunctive.
Corollary 5.3. In the model of [82 ] , for every large admissible n n n and every Γ ∈ E n \Gamma\in E_n Γ ∈ E n , the group G G G is finitely presented, torsion-free and word-hyperbolic, with a finite two-dimensional classifying space, and α = ∑ x ∈ A ′ g x \alpha=\sum_{x\in A'}g_x α = ∑ x ∈ A ′ g x and β = ∑ y ∈ B ′ h y − 1 \beta=\sum_{y\in B'}h_y^{-1} β = ∑ y ∈ B ′ h y − 1 are non-zero elements of F 2 [ G ] \mathbb{F}_2[G] F 2 [ G ] with α β = 0 \alpha\beta=0 α β = 0 . Hence F 2 [ G ] \mathbb{F}_2[G] F 2 [ G ] contains a non-trivial unit.
Proof. As for Corollary 5.2 , using Proposition 5.1 (a),(c), whose hypothesis holds by Theorem 3.4 (a), and then Lemmas 2.2 and 2.3 .
Corollary 5.4. In the model of [82 ] as formalized by OpenAI [OAI-Lean], for all large n n n there is an outcome Γ \Gamma Γ satisfying the conclusions of Corollary 5.3 for which, with respect to (1),
Area ( w ) ≤ 3,036,554 ∣ w ∣ for every word w that is trivial in G . \operatorname{Area}(w) \le3{,}036{,}554\,|w| \qquad\text{for every word } w \text{ that is trivial in } G. Area ( w ) ≤ 3 , 036 , 554 ∣ w ∣ for every word w that is trivial in G . The only inputs from OpenAI used in the proof, Theorem 3.4 (a)–(d) in the existence form below, are formalized in Lean.
Proof. OpenAI’s Lean development proves the following existence form of Theorem 3.4 (b)–(d), as SampleGraph.exists_avoiding: there are explicit constants ε ∗ = 1 / 2467200 \varepsilon_* = 1/2467200 ε ∗ = 1/2467200 and d ∗ d_* d ∗ such that for all natural numbers C C C , K 0 K_0 K 0 , I ′ ≥ 1 I' \ge1 I ′ ≥ 1 , all large n n n and all roots x A x_A x A , x B x_B x B , some matching satisfies (4) , has all component diameters at most d ∗ L d_*L d ∗ L , and carries no path system with at most K 0 K_0 K 0 paths and total length in [ L , C L ] [L,CL] [ L , C L ] with at most I ′ I' I ′ interval sides, that is ⌊ I ′ / 2 ⌋ \lfloor I'/2\rfloor ⌊ I ′ /2 ⌋ interval pairs, leaving at most ε ∗ H \varepsilon_*H ε ∗ H occurrences unpaired. There n = 2 v 2 m n = 2^{v^2m} n = 2 v 2 m and L = ⌊ ( log n ) / 100 ⌋ L = \lfloor(\log n)/100\rfloor L = ⌊( log n ) /100 ⌋ , intervals are linear in a fixed indexing of each path (we index each closed piece from one of its cuts), degreeA_bounds and degreeB_bounds give degrees in [ 129 , 132 ] [129,132] [ 129 , 132 ] , and odd_cross_intersections gives the parity hypothesis of Proposition 5.1 (a). Take ε = ε ∗ \varepsilon= \varepsilon_* ε = ε ∗ , d = d ∗ d = d_* d = d ∗ and λ = 1 + 200 / log 2 \lambda= 1 + 200/\log2 λ = 1 + 200/ log 2 , compute K 0 K_0 K 0 , C C C , I I I by (2) , and apply this with I ′ = 2 I I' = 2I I ′ = 2 I . The resulting Γ \Gamma Γ is pattern-free, as in the proof of Lemma 3.5 . Theorem B and Proposition 5.1 give the conclusions, with 16 13 ε ∗ = 39475200 13 < 3 , 036 , 554 \frac{16}{13\varepsilon_*} = \frac{39475200}{13} < 3,036,554 13 ε ∗ 16 = 13 39475200 < 3 , 036 , 554 . □
Corollary 5.4 adds an explicit constant to Corollary 5.3. The formalization [Mgh26] proves, for an outcome of OpenAI’s formalized model, that G G G is finitely presented, torsion-free and word-hyperbolic, with a finite two-dimensional classifying space, and that α , β ≠ 0 \alpha,\beta\ne0 α , β = 0 and α β = 0 \alpha\beta= 0 α β = 0 (Appendix § 16 ). Its statement asserts one such example, not one for every large n n n ; the explicit constant is not part of it, nor is the unit, which needs Connell’s theorem.
The two-colour model: zero divisors in odd characteristic
Fix an odd prime p p p . In hyperbolic groups, zero divisors over F p \mathbb{F}_p F p are subsumed by Theorem C: a failure of direct finiteness gives idempotents, then zero divisors, then units (§ 2 ). Without hyperbolicity, torsion-free zero divisors in odd characteristic are Ivanov’s theorem [53 Thm. 1.1] . This section sets up what § 9 and § 10 build on: the signed cancellation, a type design that follows OpenAI’s asymmetric types, the two-colour model, its squared-word decay and the colour data in the pattern count. Its only further content is Proposition 6.9: groups built with the signed zero-divisor mechanism are hyperbolic.
Signed cancellation
We use the notation of § 3 and Proposition 5.1 : S x S_x S x is the set of labels of the edges leaving a vertex x x x , and x ⋅ t x \mathbin{\cdot} t x ⋅ t is the end of the edge labelled t t t at x x x .
Lemma 6.1 (signed cancellation [53 Lemma 2.2] ). Let A ′ A' A ′ and B ′ B' B ′ be the vertex sets of components, possibly the same one, of finite immersed graphs labelled over the same signed alphabet, with path labels g x g_x g x (x ∈ A ′ x \in A' x ∈ A ′ ) and h y h_y h y (y ∈ B ′ y \in B' y ∈ B ′ ) in a group G G G , so that g x ⋅ t = g x t g_{x\mathbin{\cdot}t}=g_xt g x ⋅ t = g x t and h y ⋅ t = h y t h_{y\mathbin{\cdot}t}=h_yt h y ⋅ t = h y t . Let σ : A ′ → { ± 1 } \sigma\colon A' \to\{\pm1\} σ : A ′ → { ± 1 } satisfy σ ( x ⋅ t ) = − σ ( x ) \sigma(x\mathbin{\cdot}t)=-\sigma(x) σ ( x ⋅ t ) = − σ ( x ) for all x ∈ A ′ x \in A' x ∈ A ′ and t ∈ S x t \in S_x t ∈ S x .
(a) In Z [ G ] \mathbb{Z}[G] Z [ G ] ,
∑ x ∈ A ′ , y ∈ B ′ ∣ S x ∩ S y ∣ σ ( x ) g x h y − 1 = 0. (7) \sum_{x\in A',\,y\in B'} |S_x\cap S_y|\,\sigma(x)\,g_xh_y^{-1}=0. \tag*{(7)} x ∈ A ′ , y ∈ B ′ ∑ ∣ S x ∩ S y ∣ σ ( x ) g x h y − 1 = 0. (7) (b) If R R R is a commutative ring in which ∣ S x ∩ S y ∣ ⋅ 1 R = 1 R |S_x\cap S_y|\cdot1_R=1_R ∣ S x ∩ S y ∣ ⋅ 1 R = 1 R for all x ∈ A ′ x\in A' x ∈ A ′ and y ∈ B ′ y\in B' y ∈ B ′ , then
( ∑ x ∈ A ′ σ ( x ) g x ) ( ∑ y ∈ B ′ h y − 1 ) = 0 in R [ G ] . \left(\sum_{x\in A'}\sigma(x)g_x\right)\left(\sum_{y\in B'}h_y^{-1}\right)=0 \quad\text{in }R[G]. ( x ∈ A ′ ∑ σ ( x ) g x ) y ∈ B ′ ∑ h y − 1 = 0 in R [ G ] .
(c) For any map σ : A ′ → { ± 1 } \sigma:A'\to\{\pm1\} σ : A ′ → { ± 1 } , alternating or not: if no path from a vertex x A ∈ A ′ x_A\in A' x A ∈ A ′ to a different vertex has trivial label, then the coefficient of 1 1 1 in ∑ x ∈ A ′ σ ( x ) g x \sum_{x\in A'}\sigma(x)g_x ∑ x ∈ A ′ σ ( x ) g x is σ ( x A ) \sigma(x_A) σ ( x A ) ; in particular this sum is non-zero.
Proof. (a) Let Φ = { ( x , y , t ) : x ∈ A ′ , y ∈ B ′ , t ∈ S x ∩ S y } \Phi=\{(x,y,t):x\in A',\ y\in B',\ t\in S_x\cap S_y\} Φ = {( x , y , t ) : x ∈ A ′ , y ∈ B ′ , t ∈ S x ∩ S y } and ι ( x , y , t ) = ( x ⋅ t , y ⋅ t , t ˉ ) \iota(x,y,t)=(x\cdot t,y\cdot t,\bar{t}) ι ( x , y , t ) = ( x ⋅ t , y ⋅ t , t ˉ ) . Since t ˉ ∈ S x ⋅ t ∩ S y ⋅ t \bar{t}\in S_{x\cdot t}\cap S_{y\cdot t} t ˉ ∈ S x ⋅ t ∩ S y ⋅ t and ( x ⋅ t ) ⋅ t ˉ = x (x\cdot t)\cdot\bar{t}=x ( x ⋅ t ) ⋅ t ˉ = x , the map ι \iota ι is an involution of Φ \Phi Φ , and it has no fixed points because t ˉ ≠ t \bar{t}\ne t t ˉ = t . Put ω ( x , y , t ) = σ ( x ) g x h y − 1 \omega(x,y,t)=\sigma(x)g_xh_y^{-1} ω ( x , y , t ) = σ ( x ) g x h y − 1 . Then
ω ( ι ( x , y , t ) ) = σ ( x ⋅ t ) g x ⋅ t ( h y ⋅ t ) − 1 = − ω ( x , y , t ) , \omega(\iota(x,y,t))=\sigma(x\cdot t)g_{x\cdot t}(h_{y\cdot t})^{-1}=-\omega(x,y,t), ω ( ι ( x , y , t )) = σ ( x ⋅ t ) g x ⋅ t ( h y ⋅ t ) − 1 = − ω ( x , y , t ) ,
so the ι \iota ι -orbits cancel in pairs and ∑ Φ ω = 0 \sum_{\Phi}\omega=0 ∑ Φ ω = 0 . Grouping Φ \Phi Φ by ( x , y ) (x,y) ( x , y ) gives the left side of (7) . (b) Map (7) to R [ G ] R[G] R [ G ] ; by the hypothesis on R R R its left side becomes the product. (c) The only vertex with g x = 1 g_x=1 g x = 1 is x A x_A x A .
Parts (a) and (b) are [53 Lemma 2.2] , which allows any common residue d ≠ 0 d\ne0 d = 0 in place of 1 1 1 ; part (a) is the identity over Z \mathbb{Z} Z of Step 3 of his proof, stated here for possibly equal components, which § 9 needs. Part (c) is noted there too. The lemma is OpenAI’s parity argument (Proposition 5.1) with a sign. The same sign rule appears earlier as Mineyev’s signature condition [72 §2.2] , with σ ≡ 1 \sigma\equiv1 σ ≡ 1 on B ′ B' B ′ , for the pairs { ( x , y , t ) , ι ( x , y , t ) } \{(x,y,t),\iota(x,y,t)\} {( x , y , t ) , ι ( x , y , t )} ; § 12 explains how the two differ. In characteristic two the sign is invisible, and the hypothesis of (b) reads “every ∣ S x ∩ S y ∣ |S_x\cap S_y| ∣ S x ∩ S y ∣ is odd”. Two features are essential. First, bipartiteness: without the sign reversal the orbit sums do not cancel. Second, the hypothesis is only a congruence. Over Z \mathbb{Z} Z the signed vertex count of a single component of the simultaneous-step graph need not vanish, and § 10 shows that this cannot be repaired by cancellation built into the vertex types under the same decay estimate.
Vertex types in characteristic p p p
Put e = 2 p − 1 e=2p-1 e = 2 p − 1 and choose a power q = p k q=p^k q = p k with q ≥ 2 e ( e + 2 ) q\ge2e(e+2) q ≥ 2 e ( e + 2 ) ; for p = 3 p=3 p = 3 we take q = 81 q=81 q = 81 . Let v = q 2 + q + 1 v=q^2+q+1 v = q 2 + q + 1 and λ = ( q + 1 ) / v \lambda=(q+1)/v λ = ( q + 1 ) / v , the proportion of lines of PG ( 2 , q ) \operatorname{PG}(2,q) PG ( 2 , q ) through a given point. (OpenAI denote this proportion by p p p ; we reserve p p p for the characteristic.) Note that λ < 1 / q \lambda<1/q λ < 1/ q .
Definition 6.2. The letters are the v v v points of PG ( 2 , q ) \operatorname{PG}(2,q) PG ( 2 , q ) , called ordinary, and e e e extra letters E 1 , … , E e E_1,\ldots,E_e E 1 , … , E e . Choose distinct ordinary points P 1 , … , P e P_1,\ldots,P_e P 1 , … , P e , set E ˉ i = P i \bar{E}_i=P_i E ˉ i = P i , and pair the remaining v − e v-e v − e ordinary points arbitrarily; v − e v-e v − e is even, so this is a fixed-point-free involution of the N = v + e N=v+e N = v + e letters. The vertex sets are A = A + ⊔ A − A=A_+\sqcup A_- A = A + ⊔ A − with ∣ A ± ∣ = n / 2 |A_\pm|=n/2 ∣ A ± ∣ = n /2 , and B B B with ∣ B ∣ = n |B|=n ∣ B ∣ = n , where n n n runs through the multiples of n 0 = 2 ( e − 1 p − 1 ) v 2 n_0=2\binom{e-1}{p-1}v^2 n 0 = 2 ( p − 1 e − 1 ) v 2 . Each vertex x x x receives an outgoing set S x S_x S x as follows.
(i) On each of A + A_+ A + , A − A_- A − and B B B , the ordinary part of S x S_x S x is a line, and every line occurs equally often.
(ii) Within each line class on A + A_+ A + , and within each line class on A − A_- A − , the extra part is each p p p -element subset of the extras with proportion λ / ( e − 1 p − 1 ) \lambda/\binom{e-1}{p-1} λ / ( p − 1 e − 1 ) , and is empty otherwise.
(iii) Within each line class on B B B , the extra part is the set of all e e e extras with proportion λ \lambda λ , and is empty otherwise.
The definition follows OpenAI’s design [82 §2.1] : run with p = 2 p=2 p = 2 , e = 3 e=3 e = 3 and q = 128 q=128 q = 128 , it gives their type proportions, with pairs of extras on A A A and all three extras on B B B . Ivanov’s design is symmetric instead: lines of PG ( 2 , p 3 ) \operatorname{PG}(2,p^3) PG ( 2 , p 3 ) with all or none of p p p extra letters, on both sides [53 Constructions 3.1 and 3.2] . The words within each line class matter, they do for OpenAI’s types and for Ivanov’s [53 Construction 3.2(ii)] . If on B B B all extras sat exactly on the vertices whose line passes through E ‾ 1 \overline{E}_1 E 1 , every stated frequency would be unchanged, but B E 1 = B E ‾ BE_1 = B\overline{E} B E 1 = B E : the cones would make E 1 E_1 E 1 a torsion element or trivial, so torsion-freeness and root protection could not both hold, and the word E 1 E 1 ⋯ E 1 E_1E_1\cdots E_1 E 1 E 1 ⋯ E 1 would violate the squared-word decay of Lemma 6.4 .
Lemma 6.3. (a) All type counts are integers, and the proportion of A ± A_{\pm} A ± -vertices with non-empty extra part is ( e / p ) λ < 1 (e/p)\lambda< 1 ( e / p ) λ < 1 .
(b) Every letter occurs with frequency λ \lambda λ on each of A + A_+ A + , A − A_- A − and B B B .
(c) For x ∈ A x \in A x ∈ A and y ∈ B y \in B y ∈ B , ∣ S x ∩ S y ∣ ∈ { 1 , 1 + p , q + 1 , q + 1 + p } |S_x \cap S_y| \in\{1, 1+p, q+1, q+1+p\} ∣ S x ∩ S y ∣ ∈ { 1 , 1 + p , q + 1 , q + 1 + p } ; in particular ∣ S x ∩ S y ∣ ≡ 1 ( m o d p ) |S_x \cap S_y| \equiv1 \pmod{p} ∣ S x ∩ S y ∣ ≡ 1 ( mod p ) .
(d) Every vertex has degree between q + 1 q+1 q + 1 and q + 1 + e q+1+e q + 1 + e ; in particular at least 5.
Proof. (a) With n = m n 0 n=mn_0 n = m n 0 , a line class on A ± A_{\pm} A ± has n / ( 2 v ) = ( e − 1 p − 1 ) v m n/(2v)=\binom{e-1}{p-1}vm n / ( 2 v ) = ( p − 1 e − 1 ) v m vertices, so each p p p -subset type has ( q + 1 ) m (q+1)m ( q + 1 ) m vertices; a line class on B B B has n / v n/v n / v vertices, of which 2 ( e − 1 p − 1 ) ( q + 1 ) m 2\binom{e-1}{p-1}(q+1)m 2 ( p − 1 e − 1 ) ( q + 1 ) m carry all extras. There are ( e p ) \binom{e}{p} ( p e ) subsets of size p p p , and ( e p ) / ( e − 1 p − 1 ) = e / p < 2 < q \binom{e}{p}/\binom{e-1}{p-1}=e/p<2<q ( p e ) / ( p − 1 e − 1 ) = e / p < 2 < q . (b) An ordinary point lies on q + 1 q+1 q + 1 of the v v v lines, and an extra lies in ( e − 1 p − 1 ) \binom{e-1}{p-1} ( p − 1 e − 1 ) of the p p p -subsets. (c) Distinct lines meet in one point and equal lines in q + 1 q+1 q + 1 ; an A A A -extra part meets a B B B -extra part in p p p or 0 letters; and q ≡ 0 ( m o d p ) q \equiv0 \pmod{p} q ≡ 0 ( mod p ) . (d) is immediate, since q ≥ 2 e ( e + 2 ) ≥ 70 q \ge2e(e+2) \ge70 q ≥ 2 e ( e + 2 ) ≥ 70 .
For p = 3 p=3 p = 3 the data are q = 81 q=81 q = 81 , v = 6643 v=6643 v = 6643 , N = 6648 N=6648 N = 6648 , λ = 82 / 6643 \lambda=82/6643 λ = 82/6643 and n 0 = 12 v 2 = 529 , 553 , 388 n_0=12v^2=529,553,388 n 0 = 12 v 2 = 529 , 553 , 388 . At n = n 0 n=n_0 n = n 0 each line class on A ± A_{\pm} A ± has 82 vertices of each of the ten 3-subset types and 39,038 with no extras, and each line class on B B B has 984 vertices carrying all five extras and 78,732 with none. The cross-intersections are 1, 4, 82, 85.
The random model
Write Y t = { x ∈ Y : t ∈ S x } Y_t=\{x\in Y:t\in S_x\} Y t = { x ∈ Y : t ∈ S x } . For each inverse pair { t , t ‾ } \{t,\overline{t}\} { t , t } choose, independently and uniformly, three bijections
A + , t → A − , t ‾ , A − , t → A + , t ‾ , B t → B t ‾ . A_{+,t} \to A_{-,\overline{t}}, \qquad A_{-,t} \to A_{+,\overline{t}}, \qquad B_t \to B_{\overline{t}}. A + , t → A − , t , A − , t → A + , t , B t → B t .
A matched pair x ↦ y x\mapsto y x ↦ y is an edge labelled t t t from x x x to y y y and t ‾ \overline{t} t from y y y to x x x . The two A A A -pools have size n λ / 2 n\lambda/2 nλ /2 and the B B B -pool has size n λ n\lambda nλ (Lemma 6.3 (b)). Every vertex receives exactly one edge for each of its outgoing letters, so the resulting graphs Γ A \Gamma_A Γ A and Γ B \Gamma_B Γ B are immersed. Every edge of Γ A \Gamma_A Γ A joins A + A_+ A + to A − A_- A − , so Γ A \Gamma_A Γ A is bipartite, with sign σ = ± 1 \sigma=\pm1 σ = ± 1 on A ± A_{\pm} A ± . This is the two-colour model of [53 Construction 4.1] , here with our types; it is not the bipartite double cover of OpenAI’s graph, whose edges come in coupled pairs.
Fix a constant c > 0 c>0 c > 0 with
c log ( 4 N / λ ) < 1 , 2 c log d ∗ < 1 , d ∗ = q + 1 + e , (8) c\log(4N/\lambda)<1,\qquad2c\log d_*<1,\qquad d_*=q+1+e, \tag*{(8)} c log ( 4 N / λ ) < 1 , 2 c log d ∗ < 1 , d ∗ = q + 1 + e , (8)
and put L = ⌊ c log n ⌋ L=\lfloor c\log n\rfloor L = ⌊ c log n ⌋ . For p = 3 p=3 p = 3 , c = 1 / 100 c=1/100 c = 1/100 works: the two left sides are about 0.146 and 0.089. Fix roots x A ∈ A + x_A\in A_+ x A ∈ A + and x B ∈ B x_B\in B x B ∈ B before the matchings are drawn, as OpenAI do [82 §2.1] ; the bounded-pattern estimate uses the prescribed initial vertex of an interval path, so the roots may not depend on the outcome. Condition the matchings on girth( Γ ) ≥ L (\Gamma)\ge L ( Γ ) ≥ L , where Γ = Γ A ⊔ Γ B \Gamma=\Gamma_A\sqcup\Gamma_B Γ = Γ A ⊔ Γ B . Let A ′ A' A ′ and B ′ B' B ′ be the vertex sets of the components of x A x_A x A and x B x_B x B , cone off every component of Γ \Gamma Γ as in § 3 , and let X p X_p X p be the resulting finite two-complex and G p = π 1 ( X p ) G_p=\pi_1(X_p) G p = π 1 ( X p ) . Put
α = ∑ x ∈ A ′ σ ( x ) g x , β = ∑ y ∈ B ′ h y − 1 . \alpha=\sum_{x\in A'}\sigma(x)\,g_x,\qquad\beta=\sum_{y\in B'}h_y^{-1}. α = x ∈ A ′ ∑ σ ( x ) g x , β = y ∈ B ′ ∑ h y − 1 .
By Lemma 6.1 (b) and Lemma 6.3 (c), α β = 0 \alpha\beta= 0 α β = 0 in F p [ G p ] \mathbb{F}_p[G_p] F p [ G p ] for every outcome.
The bipartite model is pattern-free
It remains to show that Γ \Gamma Γ , with roots x A x_A x A and x B x_B x B , satisfies (P1)–(P3) of Definition 3.3 with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) . For OpenAI’s model these are inputs (b)–(d) of Theorem 3.4, proved in [82 Lemmas 2.2, 2.3 and Prop. 3.1] from the decay estimate [82 Lemma 2.1] . We rerun these four proofs for the bipartite model, as Ivanov does for his types [53 Lemmas 4.2 and 4.4, Props. 5.3 and 6.1] . Only the model-dependent counts change; the rest of OpenAI’s proofs concerns words and abstract graphs and is used as stated.
Turn weights and squared-word decay. For letters t , u t,u t , u with u ≠ t ˉ u \ne\bar{t} u = t ˉ , let w ( t , u ) w(t,u) w ( t , u ) be the frequency of u u u among the B B B -vertices containing t ˉ \bar{t} t ˉ , and put w ( t , t ˉ ) = 0 w(t,\bar{t})=0 w ( t , t ˉ ) = 0 . By Definition 6.2 , w ( t , u ) w(t,u) w ( t , u ) equals 1 / ( q + 1 ) 1/(q+1) 1/ ( q + 1 ) when t ˉ , u \bar{t},u t ˉ , u are distinct ordinary letters, λ \lambda λ when exactly one of them is extra, and 1 1 1 when both are extra. On A + A_+ A + and on A − A_- A − the conditional frequencies are the same, except that two distinct extras give ( p − 1 ) / ( e − 1 ) = 1 / 2 (p-1)/(e-1)=1/2 ( p − 1 ) / ( e − 1 ) = 1/2 ; so w w w dominates the turn frequencies on every side. Since all letter frequencies equal λ \lambda λ , we have w ( t , u ) = w ( u ˉ , t ˉ ) w(t,u)=w(\bar{u},\bar{t}) w ( t , u ) = w ( u ˉ , t ˉ ) . Put P ( t 1 ⋯ t h ) = ∏ i < h w ( t i , t i + 1 ) P(t_1\cdots t_h)=\prod_{i<h}w(t_i,t_{i+1}) P ( t 1 ⋯ t h ) = ∏ i < h w ( t i , t i + 1 ) .
Lemma 6.4 (cf. [82 Lemma 2.1] and [53 Prop. 5.3] ). There is δ > 0 \delta>0 δ > 0 such that
∑ W ∈ T h P ( W ) 2 ≤ e − 2 δ h \sum_{W\in T^h} P(W)^2 \le e^{-2\delta h} W ∈ T h ∑ P ( W ) 2 ≤ e − 2 δ h for all sufficiently large h h h , where T T T is the set of letters.
Proof. Let M t , u = w ( t , u ) 2 M_{t,u}=w(t,u)^2 M t , u = w ( t , u ) 2 , and let f ( t ) = e + 2 f(t)=e+2 f ( t ) = e + 2 if t ˉ \bar{t} t ˉ is extra and f ( t ) = 1 f(t)=1 f ( t ) = 1 otherwise. Suppose that t ˉ \bar{t} t ˉ is ordinary. Its v − 1 v-1 v − 1 ordinary successors have weight 1 / ( q + 1 ) 1/(q+1) 1/ ( q + 1 ) , and at most e e e of them, the points P i P_i P i , have f = e + 2 f=e+2 f = e + 2 ; its e e e extra successors have weight λ \lambda λ and f = 1 f=1 f = 1 . Hence
( M f ) ( t ) ≤ q q + 1 + e ( e + 1 ) ( q + 1 ) 2 + e λ 2 < 1 − 1 q + 1 + e ( e + 2 ) q 2 ≤ 1 − 1 q + 1 + 1 2 q < 1 , (Mf)(t)\le\frac{q}{q+1}+\frac{e(e+1)}{(q+1)^2}+e\lambda^2<1-\frac{1}{q+1}+\frac{e(e+2)}{q^2}\le1-\frac{1}{q+1}+\frac{1}{2q}<1, ( M f ) ( t ) ≤ q + 1 q + ( q + 1 ) 2 e ( e + 1 ) + e λ 2 < 1 − q + 1 1 + q 2 e ( e + 2 ) ≤ 1 − q + 1 1 + 2 q 1 < 1 ,
using λ < 1 / q \lambda<1/q λ < 1/ q and q ≥ 2 e ( e + 2 ) q\ge2e(e+2) q ≥ 2 e ( e + 2 ) . Suppose that t ˉ \bar{t} t ˉ is extra. Its other e − 1 e-1 e − 1 extras have weight 1 1 1 and f = 1 f=1 f = 1 , and its v v v ordinary successors have weight λ \lambda λ , of which e e e have f = e + 2 f=e+2 f = e + 2 . Since
v λ 2 = 1 + q / v < 1 + 1 / q , v\lambda^2=1+q/v<1+1/q, v λ 2 = 1 + q / v < 1 + 1/ q ,
( M f ) ( t ) f ( t ) ≤ e − 1 + ( v + e ( e + 1 ) ) λ 2 e + 2 < e + 1 / q + e ( e + 1 ) / q 2 e + 2 < 1. \frac{(Mf)(t)}{f(t)}\le\frac{e-1+(v+e(e+1))\lambda^2}{e+2}<\frac{e+1/q+e(e+1)/q^2}{e+2}<1. f ( t ) ( M f ) ( t ) ≤ e + 2 e − 1 + ( v + e ( e + 1 )) λ 2 < e + 2 e + 1/ q + e ( e + 1 ) / q 2 < 1.
So M f ≤ ρ 0 f Mf\le\rho_0f M f ≤ ρ 0 f for a constant ρ 0 < 1 \rho_0<1 ρ 0 < 1 . Since 1 ≤ f 1\le f 1 ≤ f , we get ∑ W P ( W ) 2 = 1 T M h − 1 1 ≤ ( ∑ t f ( t ) ) ρ 0 h − 1 \sum_{W}P(W)^2=\mathbf{1}^{\mathsf T}M^{h-1}\mathbf{1}\le(\sum_t f(t))\rho_0^{h-1} ∑ W P ( W ) 2 = 1 T M h − 1 1 ≤ ( ∑ t f ( t )) ρ 0 h − 1 .
For p = 3 p=3 p = 3 the two row bounds are 73664436152 / 74181603769 73664436152/74181603769 73664436152/74181603769 and 221387048 / 308906143 221387048/308906143 221387048/308906143 , both below 199 / 200 199/200 199/200 , and ∑ t f ( t ) = 6678 \sum_t f(t)=6678 ∑ t f ( t ) = 6678 . So ∑ W P ( W ) 2 ≤ e − h / 400 \sum_W P(W)^2\le e^{-h/400} ∑ W P ( W ) 2 ≤ e − h /400 for h ≥ 3508 h\ge3508 h ≥ 3508 , and δ = 1 / 800 \delta=1/800 δ = 1/800 is admissible. The spectral radius of M M M for p = 3 p=3 p = 3 is 0.99158188503 … 0.99158188503\ldots 0.99158188503 … (Appendix § 15 ); the same computation for OpenAI’s design gives 0.99279703 … 0.99279703\ldots 0.99279703 … , and OpenAI state the row bound 149 / 150 149/150 149/150 .
Girth and prescriptions.
Lemma 6.5 (cf. [82 Lemma 2.2] ). For all sufficiently large admissible n n n some tuple of bijections has girth at least L L L . In the uniform distribution on such tuples, condition on any feasible set of s s s prescribed matched pairs. The probability of a further specified pair in a pool of size m m m is at most 1 / ( m − s − r n ) 1/(m-s-r_n) 1/ ( m − s − r n ) ,
where r n = O ( d 2 L + 2 ) = o ( n ) r_n = O(d^{2L+2}) = o(n) r n = O ( d 2 L + 2 ) = o ( n ) uniformly over prescriptions. Consequently a feasible set of E = O ( L ) E = O(L) E = O ( L ) distinct prescriptions, E A E_A E A of them on the A A A -side, has conditional probability at most
( n λ ) − E 2 E A exp ( o ( L ) ) . (9) (n\lambda)^{-E}2^{E_A}\exp(o(L)). \tag*{(9)} ( nλ ) − E 2 E A exp ( o ( L )) . (9)
Proof. This is OpenAI’s switching argument, an instance of McKay’s switching method [69 , 79 ] . Their switch already stays inside the bijection of one inverse pair on one side; here the A A A -side has two bijections for each inverse pair, and we switch only inside one of them. A simple k k k -cycle has at most 2 n k N k 2n^kN^k 2 n k N k descriptions and needs k k k distinct prescriptions, each in a pool of size at least n λ / 2 n\lambda/2 nλ /2 . So the expected number of edges on cycles shorter than L L L is at most 2 ∑ k < L k ( 4 N / λ ) k = o ( n ) 2\sum_{k<L} k(4N/\lambda)^k = o(n) 2 ∑ k < L k ( 4 N / λ ) k = o ( n ) , by (8) . A bad edge x y xy x y , oriented with label t t t , lies in one of the three bijections. Transpose it with a non-bad edge u z uz u z of the same bijection whose endpoints are at distance more than 2 L 2L 2 L ; that is, u u u lies on the same side and in the same colour class as x x x . The transposition replaces x y , u z xy, uz x y , u z by x z , u y xz, uy x z , u y . It preserves the colour classes, and OpenAI’s argument shows that it creates no cycle shorter than L L L . The excluded set has size o ( n ) + O ( d 2 L + 2 ) o(n) + O(d^{2L+2}) o ( n ) + O ( d 2 L + 2 ) , which is o ( n ) o(n) o ( n ) by the second condition in (8) . The conditional bound follows from the same injectivity count: from a tuple containing the pair, at least m − s − r n m-s-r_n m − s − r n transpositions are available, and the output determines the inverse transposition, since the current match of x x x is z z z and the current preimage of y y y is u u u . Applying the bound successively, with m = n λ / 2 m=n\lambda/2 m = nλ /2 on A A A and m = n λ m=n\lambda m = nλ on B B B , gives (9) .
Diameter
Lemma 6.6 (cf. [82 Lemma 2.3] ). There is a constant d ≥ 1 d \ge1 d ≥ 1 such that, with conditional probability tending to one, every component of Γ \Gamma Γ has diameter at most d L dL d L .
Proof. OpenAI’s proof applies with the new pool sizes. If a vertex set of size k ≤ ρ n k \le\rho n k ≤ ρ n fails to reach 2 k 2k 2 k vertices on adjoining its neighbours, some set of 2 k 2k 2 k vertices contains at least r k = ⌈ ( q + 1 ) k / 2 ⌉ r_k=\lceil(q+1)k/2\rceil r k = ⌈( q + 1 ) k /2 ⌉ distinct edges. Choose ρ \rho ρ so small that r k + r n ≤ n λ / 4 r_k+r_n \le n\lambda/4 r k + r n ≤ nλ /4 throughout the range (for p = 3 p=3 p = 3 , ρ ≤ λ / 328 \rho\le\lambda/328 ρ ≤ λ /328 suffices for large n n n ). Each prescription then costs at most 4 / ( n λ ) 4/(n\lambda) 4/ ( nλ ) , and the failure probability is at most ( C ′ ( k / n ) ( q + 1 ) / 2 − 2 ) k (C'(k/n)^{(q+1)/2-2})^k ( C ′ ( k / n ) ( q + 1 ) /2 − 2 ) k for a constant C ′ C' C ′ . Summing separately over k ≤ n k \le\sqrt n k ≤ n and n < k ≤ ρ n \sqrt n<k\le\rho n n < k ≤ ρ n , as OpenAI do, gives o ( 1 ) o(1) o ( 1 ) . Expansion then bounds every component diameter by O ( log n ) = O ( L ) O(\log n)=O(L) O ( log n ) = O ( L ) , as in [82 Lemma 2.3] .
Bounded patterns
Proposition 6.7 (cf. [82 Prop. 3.1] ). There is ε ∈ ( 0 , 1 ] \varepsilon\in(0,1] ε ∈ ( 0 , 1 ] , depending only on the types and turn weights, such that for every integer K 0 ≥ 1 K_0\ge1 K 0 ≥ 1 , real C ≥ 1 C\ge1 C ≥ 1 and integer I ≥ 0 I\ge0 I ≥ 0 , with conditional probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , Γ \Gamma Γ carries no path system (Definition 3.2) with roots x A , x B x_A,x_B x A , x B , at most K 0 K_0 K 0 paths and total length H ∈ [ L , C L ] H\in[L,CL] H ∈ [ L , C L ] with a pairing by at most I I I interval pairs leaving at most ε H \varepsilon H ε H occurrences unpaired.
Proof. The path systems of Definition 3.2, with roots x A x_A x A and x B x_B x B , are exactly those of [82 §3] , and the statement is [82 Prop. 3.1] for the bipartite model, with the same order of quantifiers. OpenAI’s proof uses the random model at one point: the bound on the expected number of injective realizations of a multiplicity stage Δ j \Delta_j Δ j with fixed labels [82 (3.10)] . Its two ingredients are a count of vertex assignments, n V j − κ j λ E j − Q j ∏ w ( t , u ) n^{V_j-\kappa_j}\lambda^{E_j-Q_j}\prod w(t,u) n V j − κ j λ E j − Q j ∏ w ( t , u ) over internal chain turns, and the prescription bound ( ( 1 + o ( 1 ) ) / ( n λ ) ) E j ((1+o(1))/(n\lambda))^{E_j} (( 1 + o ( 1 )) / ( nλ ) ) E j . All other steps concern words and abstract immersed paths and are unchanged: the chain decomposition, the multiplicity stages (whose organization OpenAI trace to Ollivier’s treatment of multiplicities [95 ] with ∑ j ( V j − E j − k j ) ≤ 0 \sum_j(V_j-E_j-k_j)\le0 ∑ j ( V j − E j − k j ) ≤ 0 , the alignment into long blocks, the word bins, and the count of permitted label assignments.
As Ivanov does [53 §6.1] , we add one piece of data to each enlarged pattern: a proper two-colouring of the A A A -part of its image graph Δ \Delta Δ , with the colour of x A x_A x A fixed to + + + . Patterns whose A A A -part is not bipartite have no realization. The number of colourings is at most 2 2 2 to the number of components of Δ \Delta Δ , which is bounded in terms of K 0 K_0 K 0 and C C C ; so the number of enlarged patterns is still exp ( o ( L ) ) \exp(o(L)) exp ( o ( L )) . Now realize a stage with its colours prescribed. An internal chain vertex on the A A A -side with incoming letter t t t and outgoing letter u u u lies in a prescribed class A ± A_{\pm} A ± , where it has at most ( n / 2 ) λ w ( t , u ) (n/2)\lambda w(t,u) ( n /2 ) λ w ( t , u ) possible images. On the B B B -side the bound is n λ w ( t , u ) n\lambda w(t,u) nλ w ( t , u ) , and other unfixed vertices have at most n n n choices. There are E A − Q A E_A-Q_A E A − Q A internal A A A -chain vertices and E B − Q B E_B-Q_B E B − Q B internal B B B -chain vertices, where Q A , Q B Q_A,Q_B Q A , Q B count the active chains on each side. Multiplying by (9) gives the expected count
n V j − E j − k j λ − Q j 2 E A 2 − ( E A − Q A ) ∏ w ( t , u ) exp ( o ( L ) ) = n V j − E j − k j λ − Q j 2 Q A ∏ w ( t , u ) exp ( o ( L ) ) . n^{V_j-E_j-k_j}\lambda^{-Q_j}2^{E_A}2^{-(E_A-Q_A)}\prod w(t,u)\exp(o(L))=n^{V_j-E_j-k_j}\lambda^{-Q_j}2^{Q_A}\prod w(t,u)\exp(o(L)). n V j − E j − k j λ − Q j 2 E A 2 − ( E A − Q A ) ∏ w ( t , u ) exp ( o ( L )) = n V j − E j − k j λ − Q j 2 Q A ∏ w ( t , u ) exp ( o ( L )) .
The factor λ − Q j 2 Q A ≤ ( 2 / λ ) Q j \lambda^{-Q_j}2^{Q_A}\le(2/\lambda)^{Q_j} λ − Q j 2 Q A ≤ ( 2/ λ ) Q j is bounded in terms of K 0 K_0 K 0 and C C C and is absorbed into exp ( o ( L ) ) \exp(o(L)) exp ( o ( L )) , exactly as OpenAI’s factor p − Q j p^{-Q_j} p − Q j is (their p p p is our λ \lambda λ ). This is [82 (3.10)] for the bipartite model. The rest of OpenAI’s proof, with Lemma 6.4 in place of [82 Lemma 2.1] , gives the proposition, with ε \varepsilon ε chosen before K 0 , C , I K_0,C,I K 0 , C , I ; we may take ε ≤ 1 \varepsilon\le1 ε ≤ 1 .
Without the colouring the count would range over all of A A A on the vertex side while paying 2 / ( n λ ) 2/(n\lambda) 2/ ( nλ ) per A A A -edge, and would lose a factor 2 E A − Q A = 2 Θ ( L ) 2^{E_A-Q_A}=2^{\Theta(L)} 2 E A − Q A = 2 Θ ( L ) , which no fixed δ \delta δ can absorb.
Corollary 6.8. Let ε \varepsilon ε be as in Proposition 6.7, d d d as in Lemma 6.6, and λ ∗ = 1 + 2 / ( c log 2 ) \lambda_* = 1+2/(c\log2) λ ∗ = 1 + 2/ ( c log 2 ) ; we write λ ∗ \lambda_* λ ∗ for the parameter λ \lambda λ of Definition 3.3, since λ \lambda λ denotes the line proportion here. For all large admissible n n n , the girth-conditioned law is defined, and with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) the graph Γ \Gamma Γ , with roots x A , x B x_A,x_B x A , x B , is ( ε , d , λ ∗ ) (\varepsilon,d,\lambda_*) ( ε , d , λ ∗ ) -pattern-free at scale L L L .
Proof. The law is defined by Lemma 6.5 . (P1): every degree is at least q + 1 ≥ 5 q+1\ge5 q + 1 ≥ 5 by Lemma 6.3 (d), and the girth is at least L ≥ 3 L\ge3 L ≥ 3 for large n n n . (P2): the diameter bound holds with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) by Lemma 6.6, and ∣ V ( Γ ) ∣ = 2 n |V(\Gamma)|=2n ∣ V ( Γ ) ∣ = 2 n , so log 2 ∣ V ( Γ ) ∣ ≤ λ ∗ L \log_2|V(\Gamma)|\le\lambda_*L log 2 ∣ V ( Γ ) ∣ ≤ λ ∗ L as in the proof of Lemma 3.5 . (P3): apply Proposition 6.7 to the triple ( K 0 , C , I ) (K_0,C,I) ( K 0 , C , I ) that (2) assigns to ( ε , d , λ ∗ ) (\varepsilon,d,\lambda_*) ( ε , d , λ ∗ ) .
Proposition 6.9. For every odd prime p p p there are a finitely presented, torsion-free, word-hyperbolic group G p G_p G p with a finite two-dimensional classifying space and non-zero elements α , β ∈ F p [ G p ] \alpha,\beta\in\mathbb{F}_p[G_p] α , β ∈ F p [ G p ] with α β = 0 \alpha\beta=0 α β = 0 . Hence F p [ G p ] \mathbb{F}_p[G_p] F p [ G p ] contains a unit of order p p p that is not of the form λ g \lambda g λ g .
Proof. Choose a large admissible n n n and an outcome Γ \Gamma Γ in the event of Corollary 6.8. By Theorem B, X p X_p X p is a finite aspherical two-complex, so G p G_p G p is finitely presented and torsion-free and has a finite two-dimensional classifying space; no path from x A x_A x A or x B x_B x B to a different vertex has trivial label; and Area ( w ) ≤ 16 13 ε ∣ w ∣ \operatorname{Area}(w)\le\frac{16}{13\varepsilon}|w| Area ( w ) ≤ 13 ε 16 ∣ w ∣ for every word w w w that is trivial in G p G_p G p , so G p G_p G p is word-hyperbolic. We have α β = 0 \alpha\beta=0 α β = 0 by § 6.3 , and α , β ≠ 0 \alpha,\beta\ne0 α , β = 0 by root protection and Lemma 6.1 (c), applied to Γ A \Gamma_A Γ A and to Γ B \Gamma_B Γ B with σ = 1 \sigma=1 σ = 1 . Lemmas 2.2 and 2.3 give a non-trivial unit 1 + ν 1+\nu 1 + ν , of order p p p by the remark after Lemma 2.2 .
Remark 6.10. Theorem B should apply in the same way to Ivanov’s random graphs [53 Construction 4.1] . His switching, diameter and bounded-pattern estimates [53 Lemmas 4.2 and 4.4, Prop. 6.1] appear to have the form of Theorem 3.4 (b)–(d), with the roots fixed in advance and ε \varepsilon ε fixed before K 0 , C , I K_0,C,I K 0 , C , I , and his degrees are at least p 3 + 1 p^3+1 p 3 + 1 . If so, (P1)–(P3) hold with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , as in the proof of Corollary 6.8, and his groups are word-hyperbolic as well. We have not checked his estimates in the detail needed to state this as a theorem.
Direct finiteness in odd characteristic
Fix an odd prime p p p . We follow OpenAI’s direct-finiteness construction [83 ] (§ 3.3 ) with three changes: new vertex types; the two-colour matchings of § 6.3 on the A A A -side; and the signed cancellation identity (7) , applied to the root component paired with itself, with one exception at the root, in place of OpenAI’s parity certificate (Proposition 5.1(b)). Throughout this section
q = p 5 , v = q 2 + q + 1 , s = p 2 + p + 1 , λ = q + 1 v < 1 q ; (10) q=p^{5},\qquad v=q^{2}+q+1,\qquad s=p^{2}+p+1,\qquad\lambda=\frac{q+1}{v}<\frac{1}{q}; \tag*{(10)} q = p 5 , v = q 2 + q + 1 , s = p 2 + p + 1 , λ = v q + 1 < q 1 ; (10)
these replace the parameters of § 6 .
Types
Definition 7.1. The ordinary letters are the v v v points of PG ( 2 , q ) \operatorname{PG}(2,q) PG ( 2 , q ) ; they form the set O O O . The extra letters are the s s s points of PG ( 2 , p ) \operatorname{PG}(2,p) PG ( 2 , p ) , taken disjoint from O O O ; they form the set E E E . Put T = O ⊔ E T=O\sqcup E T = O ⊔ E ; since v v v and s s s are odd, ∣ T ∣ |T| ∣ T ∣ is even. A block is the complement E ∖ ℓ 0 E\setminus\ell_{0} E ∖ ℓ 0 of a line ℓ 0 \ell_{0} ℓ 0 of PG ( 2 , p ) \operatorname{PG}(2,p) PG ( 2 , p ) , and D \mathcal{D} D is the set of the s s s blocks. The non-root types are the sets ℓ \ell ℓ and ℓ ∪ D \ell\cup D ℓ ∪ D , for a line ℓ \ell ℓ of PG ( 2 , q ) \operatorname{PG}(2,q) PG ( 2 , q ) and D ∈ D D\in\mathcal{D} D ∈ D . The root type is S r = ℓ r ∪ E S_{r}=\ell_{r}\cup E S r = ℓ r ∪ E , for a fixed line ℓ r \ell_{r} ℓ r of PG ( 2 , q ) \operatorname{PG}(2,q) PG ( 2 , q ) .
A line of PG ( 2 , p ) \operatorname{PG}(2,p) PG ( 2 , p ) has p + 1 p+1 p + 1 points, and two lines meet in one point. So a block has p 2 p^{2} p 2 points, two distinct blocks meet in p 2 − p p^{2}-p p 2 − p points, every extra letter lies in p 2 p^{2} p 2 blocks, and two distinct extra letters lie together in p 2 − p p^{2}-p p 2 − p blocks. For p = 2 p=2 p = 2 these are the numbers 4, 2, 4 and 2 of OpenAI’s design, which uses the complements of the lines of the Fano plane [83 §3.1] . The fixed-point-free involution t ↦ t ˉ t\mapsto\bar{t} t ↦ t ˉ of T T T is not arbitrary; it is chosen in Lemma 7.5 .
Lemma 7.2. For types τ , τ ′ \tau,\tau' τ , τ ′ as in Definition 7.1 , ∣ τ ∩ τ ′ ∣ ≡ 1 ( m o d p ) |\tau\cap\tau'|\equiv1\pmod p ∣ τ ∩ τ ′ ∣ ≡ 1 ( mod p ) , unless τ = τ ′ = S r \tau=\tau'=S_{r} τ = τ ′ = S r ; and ∣ S r ∣ = q + 1 + s ≡ 2 ( m o d p ) |S_{r}|=q+1+s\equiv2\pmod p ∣ S r ∣ = q + 1 + s ≡ 2 ( mod p ) . A non-root type has q + 1 q+1 q + 1 or q + 1 + p 2 q+1+p^{2} q + 1 + p 2 letters.
Proof. Two lines of PG ( 2 , q ) \operatorname{PG}(2,q) PG ( 2 , q ) meet in 1 or q + 1 q+1 q + 1 points, and q + 1 ≡ 1 ( m o d p ) q+1\equiv1\pmod p q + 1 ≡ 1 ( mod p ) . The extra parts are empty, blocks, or E E E . Two blocks meet in p 2 p^{2} p 2 or p 2 − p p^{2}-p p 2 − p letters, the root type meets a block in ∣ E ∩ D ∣ = p 2 |E\cap D|=p^{2} ∣ E ∩ D ∣ = p 2 letters, and ∣ E ∩ E ∣ = s = p 2 + p + 1 |E\cap E|=s=p^{2}+p+1 ∣ E ∩ E ∣ = s = p 2 + p + 1 . All of these numbers are 0 modulo p p p , except s ≡ 1 s\equiv1 s ≡ 1 .
Colour balance
The A A A -side has two colour classes A + A_{+} A + and A − A_{-} A − , with the root r r r in A + A_{+} A + , and every edge of Γ A \Gamma_{A} Γ A will join a vertex of A + A_{+} A + carrying a letter t t t to a vertex of A − A_{-} A − carrying t ˉ \bar{t} t ˉ (§ 9.4 ). Write μ ± ( t ) \mu_{\pm}(t) μ ± ( t ) for the number of vertices of A ± A_{\pm} A ± carrying t t t . The matchings exist only if
μ + ( t ) = μ − ( t ˉ ) for every t ∈ T . (11) \mu_{+}(t)=\mu_{-}(\bar{t})\qquad\text{for every }t\in T. \tag*{(11)} μ + ( t ) = μ − ( t ˉ ) for every t ∈ T . (11)
The exception at the root cannot be dropped. If every vertex of the root component A ′ A' A ′ had degree congruent to 1 modulo p p p , then counting the edges between A ′ ∩ A + A'\cap A_{+} A ′ ∩ A + and A ′ ∩ A − A'\cap A_{-} A ′ ∩ A − would give ∣ A ′ ∩ A + ∣ ≡ ∣ A ′ ∩ A − ∣ ( m o d p ) |A'\cap A_{+}|\equiv|A'\cap A_{-}|\pmod p ∣ A ′ ∩ A + ∣ ≡ ∣ A ′ ∩ A − ∣ ( mod p ) . The element a = ∑ x ∈ A ′ σ ( x ) g x a=\sum_{x\in A'}\sigma(x)g_{x} a = ∑ x ∈ A ′ σ ( x ) g x of Proposition 7.11 would then have augmentation 0 in F p \mathbb{F}_{p} F p , and no right inverse. So (11) has to absorb the extra letters of the root.
For w ∈ Z T w\in\mathbb{Z}^{T} w ∈ Z T let w ˉ ∈ Z T \bar{w}\in\mathbb{Z}^{T} w ˉ ∈ Z T be given by w ˉ ( t ) = w ( t ˉ ) \bar{w}(t)=w(\bar{t}) w ˉ ( t ) = w ( t ˉ ) . Write 1 S ∈ Z T \mathbf{1}_{S}\in\mathbb{Z}^{T} 1 S ∈ Z T for the indicator vector of S ⊆ T S\subseteq T S ⊆ T , and 1 t = 1 { t } \mathbf{1}_{t}=\mathbf{1}_{\{t\}} 1 t = 1 { t } . Let L ⊆ Z T \mathcal{L}\subseteq\mathbb{Z}^{T} L ⊆ Z T be the subgroup spanned by the indicators of the non-root types, and put L ‾ = { w ˉ : w ∈ L } \overline{\mathcal{L}}=\{\bar{w}:w\in\mathcal{L}\} L = { w ˉ : w ∈ L } . Since 1 ℓ ∪ D − 1 ℓ = 1 D \mathbf{1}_{\ell\cup D}-\mathbf{1}_{\ell}=\mathbf{1}_{D} 1 ℓ ∪ D − 1 ℓ = 1 D , the group L \mathcal{L} L is spanned by the 1 ℓ \mathbf{1}_{\ell} 1 ℓ and the 1 D \mathbf{1}_{D} 1 D .
Lemma 7.3. (a) For e ∈ E e \in E e ∈ E , p 2 1 e = ∑ D ∈ D 1 D − p ∑ D ∌ e 1 D p^{2}1_{e}=\sum_{D\in\mathcal{D}}1_{D}-p\sum_{D\not\ni e}1_{D} p 2 1 e = ∑ D ∈ D 1 D − p ∑ D ∋ e 1 D . In particular q 1 e ∈ L q1_{e}\in\mathcal{L} q 1 e ∈ L .
(b) For t , t ′ ∈ O t,t' \in O t , t ′ ∈ O , q ( 1 t − 1 t ′ ) = ∑ ℓ ∋ t 1 ℓ − ∑ ℓ ∋ t ′ 1 ℓ q(1_{t}-1_{t'})=\sum_{\ell\ni t}1_{\ell}-\sum_{\ell\ni t'}1_{\ell} q ( 1 t − 1 t ′ ) = ∑ ℓ ∋ t 1 ℓ − ∑ ℓ ∋ t ′ 1 ℓ , which lies in L \mathcal{L} L .
(c) If e ˉ ∈ O \bar{e}\in O e ˉ ∈ O for some e ∈ E e\in E e ∈ E , then q Z T ⊆ L + L ˉ q\mathbb{Z}^{T}\subseteq\mathcal{L}+\bar{\mathcal{L}} q Z T ⊆ L + L ˉ and 1 O ∈ L + L ˉ 1_{O}\in\mathcal{L}+\bar{\mathcal{L}} 1 O ∈ L + L ˉ .
Proof. (a) Every extra letter lies in p 2 p^{2} p 2 blocks, so ∑ D 1 D = p 2 1 E \sum_{D}1_{D}=p^{2}1_{E} ∑ D 1 D = p 2 1 E . The blocks not containing e e e are the complements of the p + 1 p+1 p + 1 lines through e e e , and every other point lies on exactly one of these lines. So ∑ D ∌ e 1 D = ( p + 1 ) 1 E − ( p 1 e + 1 E ) = p 1 E − p 1 e \sum_{D\not\ni e}1_{D}=(p+1)1_{E}-(p1_{e}+1_{E})=p1_{E}-p1_{e} ∑ D ∋ e 1 D = ( p + 1 ) 1 E − ( p 1 e + 1 E ) = p 1 E − p 1 e , and the formula follows. Since p 2 p^{2} p 2 divides q q q , also q 1 e ∈ L q1_{e}\in\mathcal{L} q 1 e ∈ L . (b) The q + 1 q+1 q + 1 lines through t t t cover t t t exactly q + 1 q+1 q + 1 times and every other point of O O O once, so ∑ ℓ ∋ t 1 ℓ = q 1 t + 1 O \sum_{\ell\ni t}1_{\ell}=q1_{t}+1_{O} ∑ ℓ ∋ t 1 ℓ = q 1 t + 1 O . (c) Choose e ∈ E e\in E e ∈ E with e ˉ ∈ O \bar{e}\in O e ˉ ∈ O . By (a), q 1 e ∈ L q1_{e}\in\mathcal{L} q 1 e ∈ L , so q 1 e ˉ = q 1 e ‾ ∈ L ˉ q1_{\bar{e}}=\overline{q1_{e}}\in\bar{\mathcal{L}} q 1 e ˉ = q 1 e ∈ L ˉ . By (b), q 1 t ∈ L + L ˉ q1_{t}\in\mathcal{L}+\bar{\mathcal{L}} q 1 t ∈ L + L ˉ for every t ∈ O t\in O t ∈ O , and by (a) also for every t ∈ E t\in E t ∈ E . Finally ∑ ℓ 1 ℓ = ( q + 1 ) 1 O \sum_{\ell}1_{\ell}=(q+1)1_{O} ∑ ℓ 1 ℓ = ( q + 1 ) 1 O lies in L \mathcal{L} L , and subtracting q 1 O q1_{O} q 1 O gives 1 O ∈ L + L ˉ 1_{O}\in\mathcal{L}+\bar{\mathcal{L}} 1 O ∈ L + L ˉ .
By (a), the s s s block indicators span Q E \mathbb{Q}^{E} Q E , so they are linearly independent. This shows why OpenAI’s choice, the same frequency φ \varphi φ for every letter, cannot work on both colours here: on E E E it would force exactly ( φ − 1 ) / p 2 (\varphi-1)/p^{2} ( φ − 1 ) / p 2 vertices of each block type in A + A_{+} A + , where the root carries all of E E E , and exactly φ / p 2 \varphi/p^{2} φ / p 2 in A − A_{-} A − , and these cannot both be integers.
We therefore solve (11) with unequal frequencies. Since 1 S r = 1 ℓ r + 1 T − 1 O 1_{S_{r}}=1_{\ell_{r}}+1_{T}-1_{O} 1 S r = 1 ℓ r + 1 T − 1 O , Lemma 7.3 (c) gives 1 S r ∈ L + L ˉ 1_{S_{r}}\in\mathcal{L}+\bar{\mathcal{L}} 1 S r ∈ L + L ˉ as soon as 1 T ∈ L + L ˉ 1_{T}\in\mathcal{L}+\bar{\mathcal{L}} 1 T ∈ L + L ˉ . This holds if some ξ ∈ L \xi\in\mathcal{L} ξ ∈ L satisfies
ξ ˉ ( t ) + ξ ˉ ( t ˉ ) ≡ 1 ( m o d q ) for every t ∈ T , (12) \bar{\xi}(t)+\bar{\xi}(\bar{t})\equiv1 \pmod q \qquad\text{for every }t\in T, \tag*{(12)} ξ ˉ ( t ) + ξ ˉ ( t ˉ ) ≡ 1 ( mod q ) for every t ∈ T , (12)
since then 1 T = ξ + ξ ˉ − q d 1_{T}=\xi+\bar{\xi}-qd 1 T = ξ + ξ ˉ − q d for some d ∈ Z T d\in\mathbb{Z}^{T} d ∈ Z T . We construct an explicit ξ ∈ L \xi\in\mathcal{L} ξ ∈ L , and then choose the involution to pair its values.
Write the points of PG ( 2 , p ) \operatorname{PG}(2,p) PG ( 2 , p ) as [ i : j : 1 ] [i:j:1] [ i : j : 1 ] with i , j ∈ F p i,j\in\mathbb{F}_{p} i , j ∈ F p , [ k : 1 : 0 ] [k:1:0] [ k : 1 : 0 ] with k ∈ F p k\in\mathbb{F}_{p} k ∈ F p , and [ 1 : 0 : 0 ] [1:0:0] [ 1 : 0 : 0 ] . Put u = ( p − 1 ) / 2 u=(p-1)/2 u = ( p − 1 ) /2 , h = ( p + 1 ) / 2 h=(p+1)/2 h = ( p + 1 ) /2 and κ = p u = p ( p − 1 ) / 2 \kappa=pu=p(p-1)/2 κ = p u = p ( p − 1 ) /2 . For i ∈ F p i\in\mathbb{F}_{p} i ∈ F p let ⟨ i ⟩ ∈ { − u , … , u } \langle i\rangle\in\{-u,\ldots,u\} ⟨ i ⟩ ∈ { − u , … , u } be its centred representative, and let [ j = 0 ] [j=0] [ j = 0 ] be 1 if j = 0 j=0 j = 0 and 0 otherwise.
Lemma 7.4. Define z ∈ Z E z\in\mathbb{Z}^{E} z ∈ Z E by
z ( [ i : j : 1 ] ) = ⟨ i − h [ j = 0 ] ⟩ , z ( [ k : 1 : 0 ] ) = h , z ( [ 1 : 0 : 0 ] ) = κ . z([i:j:1])=\langle i-h[j=0]\rangle,\qquad z([k:1:0])=h,\qquad z([1:0:0])=\kappa. z ([ i : j : 1 ]) = ⟨ i − h [ j = 0 ]⟩ , z ([ k : 1 : 0 ]) = h , z ([ 1 : 0 : 0 ]) = κ . (a) Every line ℓ 0 \ell_{0} ℓ 0 of PG ( 2 , p ) \operatorname{PG}(2,p) PG ( 2 , p ) has ∑ e ∈ ℓ 0 z ( e ) ≡ 0 ( m o d p ) \sum_{e\in\ell_{0}}z(e)\equiv0\pmod p ∑ e ∈ ℓ 0 z ( e ) ≡ 0 ( mod p ) , and ∑ e ∈ E z ( e ) = p 2 \sum_{e\in E}z(e)=p^{2} ∑ e ∈ E z ( e ) = p 2 .
(b) The numbers β ( ℓ 0 ) = 1 − 1 p ∑ e ∈ ℓ 0 z ( e ) \beta(\ell_{0})=1-\frac{1}{p}\sum_{e\in\ell_{0}}z(e) β ( ℓ 0 ) = 1 − p 1 ∑ e ∈ ℓ 0 z ( e ) are integers, and z = ∑ ℓ 0 β ( ℓ 0 ) 1 E ∖ ℓ 0 z=\sum_{\ell_{0}}\beta(\ell_{0})1_{E\setminus\ell_{0}} z = ∑ ℓ 0 β ( ℓ 0 ) 1 E ∖ ℓ 0 . In particular z ∈ L z\in\mathcal{L} z ∈ L .
(c) The values of z z z are p p p copies of each integer in { − u , … , h } \{-u,\ldots,h\} { − u , … , h } and one copy of κ \kappa κ . Together with one further value 1 − κ 1-\kappa 1 − κ , they split into pairs whose sums are exactly 1.
Proof. For each j ∈ F p j\in\mathbb{F}_{p} j ∈ F p , as i i i runs through F p \mathbb{F}_{p} F p so does i − h [ j = 0 ] i-h[j=0] i − h [ j = 0 ] . So the points [ i : j : 1 ] [i:j:1] [ i : j : 1 ] with fixed j j j carry the values − u , … , u -u,\ldots,u − u , … , u once each, with sum 0. (a) The line Y = j Z Y=jZ Y = j Z consists of such a row and the point [ 1 : 0 : 0 ] [1:0:0] [ 1 : 0 : 0 ] , so its sum is κ ≡ 0 \kappa\equiv0 κ ≡ 0 . The line X = k Y + c Z X=kY+cZ X = k Y + c Z consists of the points [ k j + c : j : 1 ] [kj+c:j:1] [ k j + c : j : 1 ] and [ k : 1 : 0 ] [k:1:0] [ k : 1 : 0 ] ; modulo p p p its sum is ∑ j ( k j + c ) − h + h ≡ 0 \sum_{j}(kj+c)-h+h\equiv0 ∑ j ( k j + c ) − h + h ≡ 0 , since p p p is odd. The line Z = 0 Z=0 Z = 0 has sum p h + κ = p 2 ph+\kappa=p^{2} p h + κ = p 2 , and the total is 0 + p h + κ = p 2 0+ph+\kappa=p^{2} 0 + p h + κ = p 2 . (b) Integrality is (a). Evaluate the right side at e ∈ E e\in E e ∈ E : the p 2 p^{2} p 2 lines ℓ 0 \ell_{0} ℓ 0 not through e e e contribute ∑ ℓ 0 ∌ e β ( ℓ 0 ) = p 2 − 1 p ∑ ℓ 0 ∌ e ∑ e ′ ∈ ℓ 0 z ( e ′ ) \sum_{\ell_{0}\not\ni e}\beta(\ell_{0})=p^{2}-\frac{1}{p}\sum_{\ell_{0}\not\ni e}\sum_{e'\in\ell_{0}}z(e') ∑ ℓ 0 ∋ e β ( ℓ 0 ) = p 2 − p 1 ∑ ℓ 0 ∋ e ∑ e ′ ∈ ℓ 0 z ( e ′ ) . A point e ′ ≠ e e'\ne e e ′ = e lies on exactly p p p lines not through e e e , so the double sum is p ( p 2 − z ( e ) ) p(p^{2}-z(e)) p ( p 2 − z ( e )) , and the value is z ( e ) z(e) z ( e ) . (c) The rows give p p p copies of each of − u , … , u -u,\ldots,u − u , … , u , the points [ k : 1 : 0 ] [k:1:0] [ k : 1 : 0 ] give p p p copies of h h h , and [ 1 : 0 : 0 ] [1:0:0] [ 1 : 0 : 0 ] gives κ \kappa κ . The map y ↦ 1 − y y\mapsto1-y y ↦ 1 − y maps { − u , … , h } \{-u,\ldots,h\} { − u , … , h } to itself without fixed points, since h = u + 1 h=u+1 h = u + 1 , and κ + ( 1 − κ ) = 1 \kappa+(1-\kappa)=1 κ + ( 1 − κ ) = 1 .
:::
For p = 3 p=3 p = 3 the values of z z z are three copies each of − 1 , 0 , 1 , 2 -1,0,1,2 − 1 , 0 , 1 , 2 and one 3 3 3 , and 1 − κ = − 2 1-\kappa=-2 1 − κ = − 2 . Now write the points of PG ( 2 , q ) \operatorname{PG}(2,q) PG ( 2 , q ) as [ i : j : 1 ] [i:j:1] [ i : j : 1 ] , [ k : 1 : 0 ] [k:1:0] [ k : 1 : 0 ] and [ 1 : 0 : 0 ] [1:0:0] [ 1 : 0 : 0 ] , with i , j , k ∈ F q i,j,k\in\mathbb{F}_q i , j , k ∈ F q . Put h q = ( q + 1 ) / 2 h_q=(q+1)/2 h q = ( q + 1 ) /2 , and fix a bijection θ : F q → { 0 , 1 , … , q − 1 } \theta:\mathbb{F}_q\to\{0,1,\ldots,q-1\} θ : F q → { 0 , 1 , … , q − 1 } . Let ξ O ∈ Z O \xi_O\in\mathbb{Z}^O ξ O ∈ Z O be the combination of line indicators with coefficient θ ( k ) \theta(k) θ ( k ) on the line X = k Z X=kZ X = k Z , for each k ∈ F q k\in\mathbb{F}_q k ∈ F q , coefficient 1 − κ − h q 1-\kappa-h_q 1 − κ − h q on the line Y = 0 Y=0 Y = 0 , and coefficient h q h_q h q on the line Z = 0 Z=0 Z = 0 . Let ξ ∈ Z T \xi\in\mathbb{Z}^T ξ ∈ Z T be ξ O \xi_O ξ O on O O O and z z z on E E E . Then ξ ∈ L \xi\in\mathcal{L} ξ ∈ L , by Lemma 7.4(b).
Lemma 7.5. There is a fixed-point-free involution t ↦ t ˉ t\mapsto\bar{t} t ↦ t ˉ of T T T with E ˉ ⊆ O \bar{E}\subseteq O E ˉ ⊆ O that satisfies (12) .
Proof. The point [ i : j : 1 ] [i:j:1] [ i : j : 1 ] lies on X = i Z X=iZ X = i Z , and on Y = 0 Y=0 Y = 0 when j = 0 j=0 j = 0 . The point [ 0 : 1 : 0 ] [0:1:0] [ 0 : 1 : 0 ] lies on all q q q lines X = k Z X=kZ X = k Z and on Z = 0 Z=0 Z = 0 ; a point [ k : 1 : 0 ] [k:1:0] [ k : 1 : 0 ] with k ≠ 0 k\ne0 k = 0 lies only on Z = 0 Z=0 Z = 0 among these lines; and [ 1 : 0 : 0 ] [1:0:0] [ 1 : 0 : 0 ] lies on Y = 0 Y=0 Y = 0 and Z = 0 Z=0 Z = 0 . Hence
ξ ( [ i : j : 1 ] ) = θ ( i ) + ( 1 − κ − h q ) [ j = 0 ] , ξ ( [ 1 : 0 : 0 ] ) = 1 − κ , \xi([i:j:1])=\theta(i)+(1-\kappa-h_q)[j=0],\qquad\xi([1:0:0])=1-\kappa, ξ ([ i : j : 1 ]) = θ ( i ) + ( 1 − κ − h q ) [ j = 0 ] , ξ ([ 1 : 0 : 0 ]) = 1 − κ ,
ξ ( [ 0 : 1 : 0 ] ) = q ( q − 1 ) 2 + h q , ξ ( [ k : 1 : 0 ] ) = h q ( k ≠ 0 ) . \xi([0:1:0])=\frac{q(q-1)}{2}+h_q,\qquad\xi([k:1:0])=h_q\quad(k\ne0). ξ ([ 0 : 1 : 0 ]) = 2 q ( q − 1 ) + h q , ξ ([ k : 1 : 0 ]) = h q ( k = 0 ) .
Modulo q q q , each row of points [ i : j : 1 ] [i:j:1] [ i : j : 1 ] with fixed j j j carries every residue once; the q q q points [ k : 1 : 0 ] [k:1:0] [ k : 1 : 0 ] carry h q h_q h q , since q q q is odd; the point [ 1 : 0 : 0 ] [1:0:0] [ 1 : 0 : 0 ] carries 1 − κ 1-\kappa 1 − κ ; and the extra letters carry the values of z z z . The map y ↦ 1 − y y\mapsto1-y y ↦ 1 − y on Z / q \mathbb{Z}/q Z / q fixes only h q h_q h q , since 2 h q = q + 1 2h_q=q+1 2 h q = q + 1 . By Lemma 7.4(c), the values of z z z together with 1 − κ 1-\kappa 1 − κ pair off under this map, so the multiset of residues of ξ \xi ξ is invariant under it. The residue h q h_q h q occurs exactly 2 q 2q 2 q times: q q q times in the rows and q q q times at infinity, and never on E E E or at [ 1 : 0 : 0 ] [1:0:0] [ 1 : 0 : 0 ] . Indeed, every value y y y of z z z , and y = 1 − κ y=1-\kappa y = 1 − κ , has 2 y − 1 2y-1 2 y − 1 odd and ∣ 2 y − 1 ∣ ≤ p 2 − p − 1 < q |2y-1|\le p^2-p-1<q ∣2 y − 1∣ ≤ p 2 − p − 1 < q , so q ∤ 2 y − 1 q\nmid2y-1 q ∤ 2 y − 1 .
First pair each extra letter e e e with a point [ i : j : 1 ] [i:j:1] [ i : j : 1 ] whose residue is 1 − z ( e ) 1-z(e) 1 − z ( e ) , using distinct points; this is possible because every residue occurs at q > s q>s q > s such points. The residues removed in this step, z ( e ) z(e) z ( e ) and 1 − z ( e ) 1-z(e) 1 − z ( e ) for e ∈ E e\in E e ∈ E , form an invariant multiset that avoids h q h_q h q . So the residues of the remaining ordinary letters are still invariant, and h q h_q h q still occurs 2 q 2q 2 q times among them. Pair the remaining letters with residue y ≠ h q y\ne h_q y = h q with those with residue 1 − y 1-y 1 − y , and the 2 q 2q 2 q letters with residue h q h_q h q among themselves. □
For p = 3 p=3 p = 3 we have q = 243 q=243 q = 243 , h q = 122 h_q=122 h q = 122 and 1 − κ = − 2 1-\kappa=-2 1 − κ = − 2 , so ξ O \xi_O ξ O has coefficient − 124 -124 − 124 on Y = 0 Y=0 Y = 0 and 122 122 122 on Z = 0 Z=0 Z = 0 .
Proposition 7.6. With the involution of Lemma 7.5, 1 S r = U + V ˉ 1_{S_r}=U+\bar{V} 1 S r = U + V ˉ for some U , V ∈ L U,V\in\mathcal{L} U , V ∈ L . Fix expansions U = ∑ τ u τ 1 τ U=\sum_\tau u_\tau1_\tau U = ∑ τ u τ 1 τ and V = ∑ τ v τ 1 τ V=\sum_\tau v_\tau1_\tau V = ∑ τ v τ 1 τ with integer coefficients, over the non-root types τ \tau τ . The uniform family has, for each line ℓ \ell ℓ of PG ( 2 , q ) \operatorname{PG}(2,q) PG ( 2 , q ) , q + 1 q+1 q + 1 vertices of type ℓ ∪ D \ell\cup D ℓ ∪ D for each D ∈ D D\in\mathcal{D} D ∈ D , and
p 2 v − s ( q + 1 ) = p 2 q 2 − ( p + 1 ) ( q + 1 ) p^2v-s(q+1)=p^2q^2-(p+1)(q+1) p 2 v − s ( q + 1 ) = p 2 q 2 − ( p + 1 ) ( q + 1 ) vertices of type ℓ \ell ℓ ; write k τ > 0 k_\tau>0 k τ > 0 for its multiplicities. For an integer m ≥ 1 m\ge1 m ≥ 1 , let
A + A_+ A + consist of m k τ − u τ mk_\tau-u_\tau m k τ − u τ vertices of each type τ \tau τ , and one vertex r r r of type S r S_r S r ;
A − A_- A − consist of m k τ + v τ mk_\tau+v_\tau m k τ + v τ vertices of each type τ \tau τ ;
B B B consist of m k τ mk_\tau m k τ vertices of each type τ \tau τ .
For all sufficiently large m m m these numbers are positive and (11) holds. Moreover, ∣ B ∣ = n : = p 2 v 2 m |B|=n:=p^2v^2m ∣ B ∣ = n := p 2 v 2 m and ∣ A ± ∣ = n + O ( 1 ) |A_\pm|=n+O(1) ∣ A ± ∣ = n + O ( 1 ) ; every letter is carried by n λ n\lambda nλ vertices of B B B and by n λ + O ( 1 ) n\lambda+O(1) nλ + O ( 1 ) vertices of each of A + A_+ A + and A − A_- A − ; and as many vertices of B B B carry t t t as carry t ˉ \bar{t} t ˉ . Here and below O ( 1 ) O(1) O ( 1 ) depends on p p p and on the fixed expansions, but not on m m m .
Proof. By Lemma 7.4 (b) and Lemma 7.5 , ξ ∈ L \xi\in L ξ ∈ L satisfies (12) , and E ˉ ⊆ O \bar{E} \subseteq O E ˉ ⊆ O . So 1 T = ξ + ξ ˉ − q d \mathbf{1}_T=\xi+\bar{\xi}-qd 1 T = ξ + ξ ˉ − q d with d ∈ Z T d\in\mathbb{Z}^T d ∈ Z T , and Lemma 7.3 (c) gives 1 T , 1 O ∈ L + L ˉ \mathbf{1}_T,\mathbf{1}_O\in L+\bar{L} 1 T , 1 O ∈ L + L ˉ , hence 1 S r = 1 ℓ r + 1 T − 1 O ∈ L + L ˉ \mathbf{1}_{S_r}=\mathbf{1}_{\ell_r}+\mathbf{1}_T-\mathbf{1}_O\in L+\bar{L} 1 S r = 1 ℓ r + 1 T − 1 O ∈ L + L ˉ .
The uniform family has p 2 v p^2v p 2 v vertices in each line class, so p 2 v 2 p^2v^2 p 2 v 2 in all. An ordinary letter lies on q + 1 q+1 q + 1 lines, so it is carried by ( q + 1 ) p 2 v (q+1)p^2v ( q + 1 ) p 2 v vertices. An extra letter lies in p 2 p^2 p 2 blocks, so it is carried by v ⋅ p 2 ⋅ ( q + 1 ) v\cdot p^2\cdot(q+1) v ⋅ p 2 ⋅ ( q + 1 ) vertices. So the uniform family carries every letter p 2 v ( q + 1 ) p^2v(q+1) p 2 v ( q + 1 ) times, a λ \lambda λ -fraction of its vertices. Hence
μ + = m p 2 v ( q + 1 ) 1 T − U + 1 S r , μ − = m p 2 v ( q + 1 ) 1 T + V , \mu_+=mp^2v(q+1)\mathbf{1}_T-U+\mathbf{1}_{S_r},\qquad
\mu_-=mp^2v(q+1)\mathbf{1}_T+V, μ + = m p 2 v ( q + 1 ) 1 T − U + 1 S r , μ − = m p 2 v ( q + 1 ) 1 T + V ,
and μ ˉ − = m p 2 v ( q + 1 ) 1 T + V ˉ = μ + \bar{\mu}_-=mp^2v(q+1)\mathbf{1}_T+\bar{V}=\mu_+ μ ˉ − = m p 2 v ( q + 1 ) 1 T + V ˉ = μ + , which is (11) . The statements about B B B and the sizes follow in the same way. Since every k τ k_\tau k τ is positive and the corrections u τ u_\tau u τ , v τ v_\tau v τ and the root do not depend on m m m , all multiplicities are positive for large m m m .
The proof of Lemma 7.3 is constructive, so U U U and V V V , and hence all multiplicities, are given by integer formulas; no search is involved. For p = 3 p=3 p = 3 the uniform family has, in each line class, 244 vertices of each of the 13 block types and 530,465 vertices with no extra letters.
Turn weights and a Perron certificate
For letters t , u t,u t , u with u ≠ t ˉ u\ne\bar{t} u = t ˉ put
w ( t , u ) = { 1 / ( q + 1 ) , t ˉ , u ∈ O , λ , one of t ˉ , u is in O and the other in E , γ = ( p − 1 ) / p , t ˉ , u ∈ E , (13) w(t,u)=
\begin{cases}
1/(q+1), & \bar{t},u\in O,\\
\lambda, & \text{one of }\bar{t},u\text{ is in }O\text{ and the other in }E,\\
\gamma=(p-1)/p, & \bar{t},u\in E,
\end{cases} \tag*{(13)} w ( t , u ) = ⎩ ⎨ ⎧ 1/ ( q + 1 ) , λ , γ = ( p − 1 ) / p , t ˉ , u ∈ O , one of t ˉ , u is in O and the other in E , t ˉ , u ∈ E , (13)
and put w ( t , t ˉ ) = 0 w(t,\bar{t})=0 w ( t , t ˉ ) = 0 . The weights are at most 1, they satisfy w ( t , u ) = w ( u ˉ , t ˉ ) w(t,u)=w(\bar{u},\bar{t}) w ( t , u ) = w ( u ˉ , t ˉ ) , and their smallest positive value is 1 / ( q + 1 ) 1/(q+1) 1/ ( q + 1 ) . As in § 6.4 , P ( t 1 ⋯ t h ) = ∏ i < h w ( t i , t i + 1 ) P(t_1\cdots t_h)=\prod_{i<h}w(t_i,t_{i+1}) P ( t 1 ⋯ t h ) = ∏ i < h w ( t i , t i + 1 ) .
Lemma 7.7 (cf. [83 (3.6)] ). For Y ∈ { A + , A − , B } Y\in\{A_+,A_-,B\} Y ∈ { A + , A − , B } and letters t , u t,u t , u with u ≠ t ˉ u\ne\bar{t} u = t ˉ ,
∣ { x ∈ Y : t ˉ , u ∈ S x } ∣ = n λ w ( t , u ) + O ( 1 ) . \left|\{x\in Y:\bar{t},u\in S_x\}\right|=n\lambda w(t,u)+O(1). ∣ { x ∈ Y : t ˉ , u ∈ S x } ∣ = nλ w ( t , u ) + O ( 1 ) . Proof. Count in m m m copies of the uniform family. Two distinct ordinary letters lie on one common line, whose class has p 2 v m = n λ / ( q + 1 ) p^2vm=n\lambda/(q+1) p 2 v m = nλ / ( q + 1 ) vertices. An ordinary and an extra letter occur together on the q + 1 q+1 q + 1 lines through the first, in p 2 p^2 p 2 block types with ( q + 1 ) m (q+1)m ( q + 1 ) m vertices each, which gives p 2 ( q + 1 ) 2 m = n λ 2 p^2(q+1)^2m=n\lambda^2 p 2 ( q + 1 ) 2 m = n λ 2 . Two distinct extra letters lie together in p 2 − p p^2-p p 2 − p blocks, which gives v ( p 2 − p ) ( q + 1 ) m = n λ γ v(p^2-p)(q+1)m=n\lambda\gamma v ( p 2 − p ) ( q + 1 ) m = nλγ . The remaining vertices of Y Y Y , the corrections of Proposition 7.6 and the root, number O ( 1 ) O(1) O ( 1 ) .
Lemma 7.8 (Perron certificate; cf. [83 Lemma 3.2] ). Let M t , u = w ( t , u ) 2 M_{t,u}=w(t,u)^2 M t , u = w ( t , u ) 2 , and let f ( t ) = p 2 f(t)=p^2 f ( t ) = p 2 if t ˉ ∈ E \bar{t}\in E t ˉ ∈ E and f ( t ) = 1 f(t)=1 f ( t ) = 1 otherwise. Then
M f ≤ ρ f , ρ = 1 − 1 2 ( q + 1 ) . (14) Mf\le\rho f,\qquad\rho=1-\frac{1}{2(q+1)}. \tag*{(14)} M f ≤ ρ f , ρ = 1 − 2 ( q + 1 ) 1 . (14) Consequently ∑ W ∈ T h P ( W ) 2 ≤ p 2 ∣ T ∣ ρ h − 1 \sum_{W\in T^h}P(W)^2\le p^2|T|\rho^{h-1} ∑ W ∈ T h P ( W ) 2 ≤ p 2 ∣ T ∣ ρ h − 1 , and δ = − 1 4 log ρ \delta=-\frac{1}{4}\log\rho δ = − 4 1 log ρ satisfies ∑ W ∈ T h P ( W ) 2 ≤ e − 2 δ h \sum_{W\in T^h}P(W)^2\le e^{-2\delta h} ∑ W ∈ T h P ( W ) 2 ≤ e − 2 δ h for all sufficiently large h h h .
Proof. Since E ˉ ⊆ O \bar{E} \subseteq O E ˉ ⊆ O , the letters with f = p 2 f=p^2 f = p 2 are the s s s ordinary letters in E ˉ \bar{E} E ˉ , and f = 1 f=1 f = 1 on E E E . We use
2 s p 2 ( q + 1 ) q 2 = 2 ( 1 p + 1 p 2 + 1 p 3 ) ( 1 + 1 p 5 ) ≤ 6344 6561 < 1 , (15) \frac{2sp^2(q+1)}{q^2}=2\left(\frac{1}{p}+\frac{1}{p^2}+\frac{1}{p^3}\right)\left(1+\frac{1}{p^5}\right)\leq\frac{6344}{6561}<1, \tag*{(15)} q 2 2 s p 2 ( q + 1 ) = 2 ( p 1 + p 2 1 + p 3 1 ) ( 1 + p 5 1 ) ≤ 6561 6344 < 1 , (15)
where the bound is the value at p = 3 p=3 p = 3 . Suppose that t ˉ ∈ O \bar{t}\in O t ˉ ∈ O , so f ( t ) = 1 f(t)=1 f ( t ) = 1 . The successors u ≠ t ˉ u\neq\bar{t} u = t ˉ of t t t are q ( q + 1 ) q(q+1) q ( q + 1 ) ordinary letters of weight 1 / ( q + 1 ) 1/(q+1) 1/ ( q + 1 ) , at most s s s of them with f ( u ) = p 2 f(u)=p^2 f ( u ) = p 2 , and s s s extra letters of weight λ \lambda λ . Using λ < 1 / q \lambda<1/q λ < 1/ q and (15) ,
( M f ) ( t ) ≤ q q + 1 + s λ 2 + s ( p 2 − 1 ) ( q + 1 ) 2 < q q + 1 + s p 2 q 2 < q q + 1 + 1 2 ( q + 1 ) = ρ . (Mf)(t)\leq\frac{q}{q+1}+s\lambda^2+\frac{s(p^2-1)}{(q+1)^2}<\frac{q}{q+1}+\frac{sp^2}{q^2}<\frac{q}{q+1}+\frac{1}{2(q+1)}=\rho. ( M f ) ( t ) ≤ q + 1 q + s λ 2 + ( q + 1 ) 2 s ( p 2 − 1 ) < q + 1 q + q 2 s p 2 < q + 1 q + 2 ( q + 1 ) 1 = ρ .
Suppose that t ˉ ∈ E \bar{t}\in E t ˉ ∈ E , so f ( t ) = p 2 f(t)=p^2 f ( t ) = p 2 . The successors are s − 1 s-1 s − 1 extra letters of weight γ \gamma γ and v v v ordinary letters of weight λ \lambda λ , whose f f f -values add up to v + s ( p 2 − 1 ) v+s(p^2-1) v + s ( p 2 − 1 ) . Here ( s − 1 ) γ 2 = p 2 − p − 1 + 1 / p (s-1)\gamma^2=p^2-p-1+1/p ( s − 1 ) γ 2 = p 2 − p − 1 + 1/ p , v λ 2 = ( q + 1 ) 2 / v < 1 + 1 / q v\lambda^2=(q+1)^2/v<1+1/q v λ 2 = ( q + 1 ) 2 / v < 1 + 1/ q , and s ( p 2 − 1 ) λ 2 < s p 2 / q 2 < 1 / ( 2 q ) s(p^2-1)\lambda^2<sp^2/q^2<1/(2q) s ( p 2 − 1 ) λ 2 < s p 2 / q 2 < 1/ ( 2 q ) by (15) . So
( M f ) ( t ) ≤ ( s − 1 ) γ 2 + ( v + s ( p 2 − 1 ) ) λ 2 < p 2 − p + 1 p + 3 2 q < p 2 − 2 < ρ p 2 , (Mf)(t)\leq(s-1)\gamma^2+(v+s(p^2-1))\lambda^2<p^2-p+\frac{1}{p}+\frac{3}{2q}<p^2-2<\rho p^2, ( M f ) ( t ) ≤ ( s − 1 ) γ 2 + ( v + s ( p 2 − 1 )) λ 2 < p 2 − p + p 1 + 2 q 3 < p 2 − 2 < ρ p 2 ,
since p ≥ 3 p\geq3 p ≥ 3 and p 2 < 4 ( q + 1 ) p^2<4(q+1) p 2 < 4 ( q + 1 ) . Finally 1 ≤ f ≤ p 2 1 \mathbf{1}\leq f\leq p^2\mathbf{1} 1 ≤ f ≤ p 2 1 gives ∑ W P ( W ) 2 = 1 T M h − 1 1 ≤ 1 T M h − 1 f ≤ p 2 ∣ T ∣ ρ h − 1 \sum_W P(W)^2=\mathbf{1}^{\mathsf T}M h^{-1}\mathbf{1}\leq\mathbf{1}^{\mathsf T}M h^{-1}f\leq p^2|T|\rho^{h-1} ∑ W P ( W ) 2 = 1 T M h − 1 1 ≤ 1 T M h − 1 f ≤ p 2 ∣ T ∣ ρ h − 1 .
This is where the choice q = p 5 q=p^5 q = p 5 enters: for q = p 4 q=p^4 q = p 4 the left side of (15) exceeds 1 1 1 . For p = 3 p=3 p = 3 , ρ = 487 / 488 \rho=487/488 ρ = 487/488 and δ ≈ 5.13 ⋅ 10 − 4 \delta\approx5.13\cdot10^{-4} δ ≈ 5.13 ⋅ 1 0 − 4 .
The random model is pattern-free
Fix the involution of Lemma 7.5 , the vertex sets of Proposition 7.6 , and the roots r ∈ A + r\in A_+ r ∈ A + and x B ∈ B x_B\in B x B ∈ B , before any edges are drawn, as OpenAI do [83 §3.1] ; their bounded path estimate concerns interval paths starting at these fixed vertices [83 Thm. 4.1] , so the roots may not depend on the outcome. The matchings are those of § 6.3 : for every letter t t t , a uniform bijection from the vertices of A + A_+ A + carrying t t t to the vertices of A − A_- A − carrying t ˉ \bar{t} t ˉ , and for every inverse pair { t , t ˉ } \{t,\bar{t}\} { t , t ˉ } , a uniform bijection between the vertices of B B B carrying t t t and those carrying t ˉ \bar{t} t ˉ . Their sizes agree by Proposition 7.6 . Every vertex receives exactly one edge for each letter of its type, so Γ A \Gamma_A Γ A and Γ B \Gamma_B Γ B are immersed; every edge of Γ A \Gamma_A Γ A joins A + A_+ A + to A − A_- A − ; and by Lemma 7.2 the degrees lie between q + 1 q+1 q + 1 and d max = q + 1 + s d_{\max}=q+1+s d m a x = q + 1 + s . Fix c 0 > 0 c_0>0 c 0 > 0 with
c 0 log ( 4 ∣ T ∣ / λ ) < 1 , 2 c 0 log d max < 1 , (16) c_0\log(4|T|/\lambda)<1,\qquad2c_0\log d_{\max}<1, \tag*{(16)} c 0 log ( 4∣ T ∣/ λ ) < 1 , 2 c 0 log d m a x < 1 , (16)
put L = ⌊ c 0 log n ⌋ L=\lfloor c_0\log n\rfloor L = ⌊ c 0 log n ⌋ , and let P L \mathbb{P}_L P L be the uniform law on the outcomes with girth ( Γ ) ≥ L \operatorname{girth}(\Gamma)\geq L girth ( Γ ) ≥ L , where Γ = Γ A ⊔ Γ B \Gamma=\Gamma_A\sqcup\Gamma_B Γ = Γ A ⊔ Γ B . These are the conditions (8) with N = ∣ T ∣ N=|T| N = ∣ T ∣ and d ∗ = d max d_*=d_{\max} d ∗ = d m a x , and they replace [83 (3.9)] : the A A A -side has 2 n + O ( 1 ) 2n+O(1) 2 n + O ( 1 ) vertices, which doubles OpenAI’s factor 2 ∣ T ∣ / p 2|T|/p 2∣ T ∣/ p . For p = 3 p=3 p = 3 , c 0 = 1 / 20 c_0=1/20 c 0 = 1/20 works; the left sides are about 0.89 0.89 0.89 and 0.55 0.55 0.55 . Cone off every component of Γ \Gamma Γ as in § 3 , giving a finite two-complex X X X and a group H = π 1 ( X ) H=\pi_1(X) H = π 1 ( X ) .
Proposition 7.9 (OpenAI’s estimates for the two-colour model). As m → ∞ m\to\infty m → ∞ , the following hold.
(a) The girth event is non-empty for all sufficiently large m m m , and the conclusion of [83 Lemma 3.3] holds with n p np n p replaced by n λ n\lambda nλ and with r n = O ( 1 ) + O ( d max 2 L + 2 ) = o ( n ) r_n=O(1)+O(d_{\max}^{2L+2})=o(n) r n = O ( 1 ) + O ( d m a x 2 L + 2 ) = o ( n ) . (b) There is a constant d ≥ 1 d \ge1 d ≥ 1 such that, with P L \mathbb{P}_L P L -probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , every component of Γ \Gamma Γ has diameter at most d L dL d L .
(c) Let δ \delta δ be as in Lemma 7.8 , a 0 = 2 log ( q + 1 ) + 1 a_0=2\log(q+1)+1 a 0 = 2 log ( q + 1 ) + 1 and
ε = min { 1 4 , δ 16 ( 1 + a 0 ) } . \varepsilon=\min\left\{\frac{1}{4},\frac{\delta}{16(1+a_0)}\right\}. ε = min { 4 1 , 16 ( 1 + a 0 ) δ } .
For every integer K 0 ≥ 1 K_0\ge1 K 0 ≥ 1 , real C ≥ 1 C\ge1 C ≥ 1 and integer I ≥ 0 I\ge0 I ≥ 0 , with P L \mathbb{P}_L P L -probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , Γ \Gamma Γ carries no path system (Definition 3.2) with roots r , x B r,x_B r , x B , at most K 0 K_0 K 0 paths and total length H ∈ [ L , C L ] H\in[L,CL] H ∈ [ L , C L ] with a pairing by at most I I I interval pairs leaving at most ε H \varepsilon H ε H occurrences unpaired.
Proof. This is § 6.4 run with the proofs of [83 ] in place of those of [82 ] . We list the inputs that change. Everything else in those proofs concerns words, abstract graphs or planar pictures, and is used as stated.
(a) Non-emptiness is the bad-edge switching argument of [83 §3.3] . A cycle of length k k k has at most 2 ( 2 n + O ( 1 ) ) k ∣ T ∣ k 2(2n+O(1))^k|T|^k 2 ( 2 n + O ( 1 ) ) k ∣ T ∣ k descriptions, because the A A A -side has 2 n + O ( 1 ) 2n+O(1) 2 n + O ( 1 ) vertices, and probability at most ( 2 / ( n λ ) ) k (2/(n\lambda))^k ( 2/ ( nλ ) ) k , because pools have n λ + O ( 1 ) n\lambda+O(1) nλ + O ( 1 ) elements. So the expected number of edges on cycles shorter than L L L is at most 2 ∑ k < L k ( 4 ∣ T ∣ / λ ) k ( 1 + o ( 1 ) ) = o ( n ) 2\sum_{k<L}k(4|T|/\lambda)^k(1+o(1))=o(n) 2 ∑ k < L k ( 4∣ T ∣/ λ ) k ( 1 + o ( 1 )) = o ( n ) , by the first condition in (16) . The switch transposes two edges of the same bijection, so, as in Lemma 6.5 , it preserves the colour classes and the types; OpenAI’s argument that it creates no cycle shorter than L L L is graph-theoretic. The edges near a bad edge that must be avoided number O ( d max 2 L + 2 ) = o ( n ) O(d_{\max}^{2L+2})=o(n) O ( d m a x 2 L + 2 ) = o ( n ) , by the second condition in (16) . The prescription bound is OpenAI’s injectivity count [83 Lemma 3.3] , for pools of size n λ + O ( 1 ) n\lambda+O(1) nλ + O ( 1 ) .
(b) OpenAI’s expansion argument [83 Prop. 3.4] applies with three changes. The minimum degree is q + 1 q+1 q + 1 , so a set of 2 k 2k 2 k vertices containing the closed neighbourhood of k k k vertices contains at least ⌈ ( q + 1 ) k / 2 ⌉ \lceil(q+1)k/2\rceil ⌈( q + 1 ) k /2 ⌉ distinct edges, and the union bound becomes ( C ′ ( k / n ) ( q − 3 ) / 2 ) k (C'(k/n)^{(q-3)/2})^k ( C ′ ( k / n ) ( q − 3 ) /2 ) k , whose sum over 1 ≤ k ≤ ρ 1 n 1\le k\le\rho_1n 1 ≤ k ≤ ρ 1 n tends to zero for a small ρ 1 > 0 \rho_1>0 ρ 1 > 0 depending on p p p . Each exposed prescription costs at most 2 / ( n λ ) 2/(n\lambda) 2/ ( nλ ) , by (a). A side has at most 2 n + O ( 1 ) 2n+O(1) 2 n + O ( 1 ) vertices, which changes only the constant in the ball-packing bound O ( log n ) = O ( L ) O(\log n)=O(L) O ( log n ) = O ( L ) on the diameter.
(c) The path systems of Definition 3.2 with roots r , x B r,x_B r , x B are the systems of [83 Thm. 4.1] : an interval pair is a comparison, and the reduction condition is [83 (4.1)] . So (c) is the conclusion of [83 Thm. 4.1] for the two-colour model, with its order of quantifiers. The model enters OpenAI’s proof only through the fixed-stage expectation [83 (4.11)] , whose inputs are the turn counts [83 (3.6)] and the prescription bound [83 (3.12)] . As in the proof of Proposition 6.7, and as in [53 §6.1] , add to each enlarged pattern a proper two-colouring of the A A A -part of its image graph, with r r r coloured + + + ; patterns whose A A A -part is not bipartite have no realization. By [83 Lemma 4.2] and the paragraph after it, the image graph is a union of boundedly many chains, and each of its components contains a path start, so it has at most K 0 K_0 K 0 components. There are therefore at most 2 K 0 2^{K_0} 2 K 0 colourings, and the number of enlarged patterns is still exp ( o ( L ) ) \exp(o(L)) exp ( o ( L )) . Now count realizations with the colours prescribed. An internal chain vertex with turn ( t , u ) (t,u) ( t , u ) has at most n λ w ( t , u ) + O ( 1 ) n\lambda\,w(t,u)+O(1) nλ w ( t , u ) + O ( 1 ) images, by Lemma 7.7 ; another unfixed vertex has at most n + O ( 1 ) n+O(1) n + O ( 1 ) images in its colour class or in B B B ; a fixed root has one; and the E j E_j E j prescriptions cost ( n λ ) − E j exp ( o ( L ) ) (n\lambda)^{-E_j}\exp(o(L)) ( nλ ) − E j exp ( o ( L )) , by (a). This is [83 (4.11)] with p p p replaced by λ \lambda λ , and the bounded factor λ − Q j \lambda^{-Q_j} λ − Q j is absorbed into exp ( o ( L ) ) \exp(o(L)) exp ( o ( L )) as there. The rest of OpenAI’s proof uses the model only through the word-bin bounds [83 (4.9)] , which follow from Lemma 7.8 and from − log P ( W ) ≤ ( ∣ W ∣ − 1 ) log ( q + 1 ) -\log P(W)\le(|W|-1)\log(q+1) − log P ( W ) ≤ ( ∣ W ∣ − 1 ) log ( q + 1 ) . So the choice [83 (4.15)] gives the stated ε \varepsilon ε , which depends only on p p p . Without the colours, the count would lose a factor two at every internal vertex on the A A A -side, which no fixed δ \delta δ can absorb (compare the end of the proof of Proposition 6.7). □
Corollary 7.10. Let ε \varepsilon ε and d d d be as in Proposition 7.9, and λ ∗ = 1 + 2 / ( c 0 log 2 ) \lambda_* = 1 + 2/(c_0 \log2) λ ∗ = 1 + 2/ ( c 0 log 2 ) . For all large m m m the law P L \mathbb{P}_{L} P L is defined, and with P L \mathbb{P}_{L} P L -probability 1 − o ( 1 ) 1 - o(1) 1 − o ( 1 ) the graph Γ \Gamma Γ , with roots r , x B r, x_B r , x B , is ( ε , d , λ ∗ ) (\varepsilon, d, \lambda_*) ( ε , d , λ ∗ ) -pattern-free at scale L L L .
Proof. The law is defined by Proposition 7.9(a). (P1): every degree is at least q + 1 ≥ 5 q + 1 \ge5 q + 1 ≥ 5 , and the girth is at least L ≥ 3 L \ge3 L ≥ 3 for large m m m . (P2): the diameter bound holds with probability 1 − o ( 1 ) 1 - o(1) 1 − o ( 1 ) by Proposition 7.9(b); and ∣ V ( Γ ) ∣ = 3 n + O ( 1 ) ≤ 4 n |V(\Gamma)| = 3n + O(1) \le4n ∣ V ( Γ ) ∣ = 3 n + O ( 1 ) ≤ 4 n , so for large m m m , when L ≥ 2 L \ge2 L ≥ 2 and L ≥ c 0 2 log n L \ge\frac{c_0}{2}\log n L ≥ 2 c 0 log n , we get log 2 ∣ V ( Γ ) ∣ ≤ 2 + log 2 n ≤ L + 2 c 0 log 2 L = λ ∗ L \log_2 |V(\Gamma)| \le2 + \log_2 n \le L + \frac{2}{c_0 \log2}L = \lambda_*L log 2 ∣ V ( Γ ) ∣ ≤ 2 + log 2 n ≤ L + c 0 l o g 2 2 L = λ ∗ L . (P3): apply Proposition 7.9(c) to the triple ( K 0 , C , I ) (K_0,C,I) ( K 0 , C , I ) that (2) assigns to ( ε , d , λ ∗ ) (\varepsilon,d,\lambda_*) ( ε , d , λ ∗ ) .
The witnesses
Let A ′ A' A ′ and B ′ B' B ′ be the vertex sets of the components of r r r and x B x_B x B , with path labels g x g_x g x and h y h_y h y as in § 3.3 , and let σ = ± 1 \sigma= \pm1 σ = ± 1 on A ± A_\pm A ± . Every edge of Γ A \Gamma_A Γ A joins A + A_+ A + to A − A_- A − , so σ ( x ⋅ t ) = − σ ( x ) \sigma(x \cdot t) = -\sigma(x) σ ( x ⋅ t ) = − σ ( x ) .
Proposition 7.11. Put
a = ∑ x ∈ A ′ σ ( x ) g x , b = − ∑ x ∈ A ′ g x − 1 , c = ∑ y ∈ B ′ h y − 1 in F p [ H ] . a = \sum_{x\in A'} \sigma(x)g_x,\qquad b = -\sum_{x\in A'} g_x^{-1},\qquad c = \sum_{y\in B'} h_y^{-1}\qquad\text{in }\mathbb{F}_p[H]. a = x ∈ A ′ ∑ σ ( x ) g x , b = − x ∈ A ′ ∑ g x − 1 , c = y ∈ B ′ ∑ h y − 1 in F p [ H ] . Then a b = 1 ab = 1 ab = 1 and a c = 0 ac = 0 a c = 0 . If no path in Γ B \Gamma_B Γ B from x B x_B x B to a different vertex has trivial label in H H H , then c ≠ 0 c \ne0 c = 0 , and hence b a ≠ 1 ba \ne1 ba = 1 .
Proof. Apply (7) with B ′ = A ′ B' = A' B ′ = A ′ and h x = g x h_x = g_x h x = g x . By Lemma 7.2 , ∣ S x ∩ S x ′ ∣ ≡ 1 + [ x = x ′ = r ] ( m o d p ) |S_x \cap S_{x'}| \equiv1 + [x = x' = r] \pmod p ∣ S x ∩ S x ′ ∣ ≡ 1 + [ x = x ′ = r ] ( mod p ) for x , x ′ ∈ A ′ x,x' \in A' x , x ′ ∈ A ′ , because r r r is the only vertex of type S r S_r S r . Since g r = 1 g_r = 1 g r = 1 and σ ( r ) = 1 \sigma(r) = 1 σ ( r ) = 1 , reducing (7) modulo p p p gives
0 = ∑ x , x ′ ∈ A ′ σ ( x ) g x g x ′ − 1 + 1 = − a b + 1 in F p [ H ] . 0 = \sum_{x,x'\in A'} \sigma(x)g_xg_{x'}^{-1} + 1 = -ab + 1 \qquad\text{in }\mathbb{F}_p[H]. 0 = x , x ′ ∈ A ′ ∑ σ ( x ) g x g x ′ − 1 + 1 = − ab + 1 in F p [ H ] .
No vertex of B B B has type S r S_r S r , so ∣ S x ∩ S y ∣ ≡ 1 ( m o d p ) |S_x \cap S_y| \equiv1 \pmod p ∣ S x ∩ S y ∣ ≡ 1 ( mod p ) for x ∈ A ′ x \in A' x ∈ A ′ and y ∈ B ′ y \in B' y ∈ B ′ , and Lemma 6.1 (b) with R = F p R = \mathbb{F}_p R = F p gives a c = 0 ac = 0 a c = 0 . If x B x_B x B is protected as stated, Lemma 6.1 (c), with σ ≡ 1 \sigma\equiv1 σ ≡ 1 on B ′ B' B ′ , gives c ≠ 0 c \ne0 c = 0 . Then b a ≠ 1 ba \ne1 ba = 1 , since otherwise c = ( b a ) c = b ( a c ) = 0 c = (ba)c = b(ac) = 0 c = ( ba ) c = b ( a c ) = 0 .
Proof of Theorem C. Fix the constants in this order: the types, the involution and the vertex sets; then c 0 c_0 c 0 and δ \delta δ ; then ε \varepsilon ε and d d d (Proposition 7.9); then λ ∗ \lambda_* λ ∗ and the constants (2) . Choose a large m m m and an outcome Γ \Gamma Γ in the event of Corollary 7.10 . We choose it in this event, and not merely among the outcomes without reduced spherical arrangements, because the isoperimetric inequality uses (P3) itself, which the absence of such arrangements does not provide.
By Theorem B, X X X is a finite aspherical two-complex, so H H H is finitely presented and torsion-free and has a finite two-dimensional classifying space; both roots are protected; and Area ( w ) ≤ 16 13 ∣ w ∣ \operatorname{Area}(w) \le\frac{16}{13}|w| Area ( w ) ≤ 13 16 ∣ w ∣ for every word w w w trivial in H H H , so H H H is word-hyperbolic. Proposition 7.11 gives a , b , c ∈ F p [ H ] a,b,c \in\mathbb{F}_p[H] a , b , c ∈ F p [ H ] with a b = 1 ab = 1 ab = 1 , a c = 0 ac = 0 a c = 0 and c ≠ 0 c \ne0 c = 0 , hence b a ≠ 1 ba \ne1 ba = 1 . Put H p = H H_p = H H p = H . By base change (§ 2 ), the same identities hold in K [ H p ] K[H_p] K [ H p ] for every field K K K of characteristic p p p . Lemmas 2.1 and 2.2 and the remark after Lemma 2.2 give the idempotent, the zero divisor and the unit of order p p p , and Lemma 2.4 with the finite field F p \mathbb{F}_p F p shows that H p H_p H p is neither sofic nor surjunctive.
For p = 3 p = 3 p = 3 , with c 0 = 1 / 20 c_0 = 1/20 c 0 = 1/20 : a 0 ≈ 12.0 a_0 \approx12.0 a 0 ≈ 12.0 and ε ≈ 2.47 ⋅ 10 − 6 \varepsilon\approx2.47 \cdot10^{-6} ε ≈ 2.47 ⋅ 1 0 − 6 , so Area ( w ) ≤ 5.0 ⋅ 10 5 ∣ w ∣ \operatorname{Area}(w) \le5.0 \cdot10^5 |w| Area ( w ) ≤ 5.0 ⋅ 1 0 5 ∣ w ∣ .
Further consequences
Arzhantseva and Păunescu define linear soficity over C \mathbb{C} C [6 Def. 4.1] . Their Theorem 7.4 holds over every field, and its hypothesis is the following.
Definition 7.12. Let F F F be a field. A countable group is linearly sofic over F F F if, for some non-principal ultrafilter ω \omega ω and some sequence n k → ∞ n_k \to\infty n k → ∞ , it admits an injective group morphism into the metric ultraproduct ∏ k → ω G L n k ( F ) / d \prod_{k\to\omega} \mathrm{GL}_{n_k}(F)/d ∏ k → ω GL n k ( F ) / d of general linear groups with the normalized rank distance [6 Defs. 2.3 and 2.5] .
Corollary 7.13. Let p p p be a prime, and let G G G be the group of Corollary 5.2 if p = 2 p=2 p = 2 and the group H p H_p H p of Theorem C if p p p is odd.
(a) G G G is not residually finite.
(b) G G G admits no proper cocompact action on a CAT ( 0 ) \operatorname{CAT}(0) CAT ( 0 ) cube complex.
(c) G G G is not linearly sofic over any field of characteristic p p p .
Proof. Let a , b ∈ F p [ G ] a,b \in\mathbb{F}_p[G] a , b ∈ F p [ G ] with a b = 1 ≠ b a ab=1 \ne ba ab = 1 = ba . (a) Residually finite groups are sofic [33 Prop. 4.6] , and G G G is not (Lemma 2.4 ).
(b) Suppose that G G G acts properly and cocompactly on a CAT ( 0 ) \operatorname{CAT}(0) CAT ( 0 ) cube complex Y Y Y . Point stabilizers are finite, hence trivial since G G G is torsion-free, so the action is free. By Agol’s theorem [3 Thm. 1.1] , a finite-index subgroup G ′ G' G ′ acts specially on Y Y Y , so Y / G ′ Y/G' Y / G ′ is a special cube complex. It is compact, and its fundamental group is G ′ G' G ′ , since G ′ G' G ′ acts freely on Y Y Y , which is contractible [14 Cor. II.1.5] . So G G G is virtually compact special, and since it is torsion-free, F p [ G ] \mathbb{F}_p[G] F p [ G ] embeds in a division ring [37 Thm. 1.3(1)] . In a division ring x y = 1 xy=1 x y = 1 implies y x = 1 yx=1 y x = 1 , and the embedding is injective, so b a = 1 ba=1 ba = 1 , a contradiction. Alternatively, Agol’s theorem and work of Haglund and Wise make such a hyperbolic group residually finite, as Sandhu and Thom observe [108 §1] ; this contradicts (a).
(c) Let F F F be a field of characteristic p p p , and suppose that θ : G → ∏ k → ω G L n k ( F ) / d \theta:G \to\prod_{k\to\omega} \mathrm{GL}_{n_k}(F)/d θ : G → ∏ k → ω GL n k ( F ) / d is injective. By [6 Thm. 7.4] there is an injective algebra morphism Θ \Theta Θ from F [ G ] F[G] F [ G ] to an ultraproduct ∏ k → ω M m k ( F ) / Ker \prod_{k\to\omega} M_{m_k}(F)/\operatorname{Ker} ∏ k → ω M m k ( F ) / Ker of matrix algebras [6 Def. 2.3] . It is unital: in the proof of that theorem, Θ \Theta Θ extends a group morphism, which sends 1 1 1 to the identity. This ultraproduct is stably finite [6 Prop. 2.8] . Since F p ⊆ F \mathbb{F}_p \subseteq F F p ⊆ F , we have a b = 1 ab=1 ab = 1 in F [ G ] F[G] F [ G ] . So Θ ( a ) Θ ( b ) = 1 \Theta(a)\Theta(b)=1 Θ ( a ) Θ ( b ) = 1 , hence Θ ( b ) Θ ( a ) = 1 \Theta(b)\Theta(a)=1 Θ ( b ) Θ ( a ) = 1 , and injectivity gives b a = 1 ba=1 ba = 1 , a contradiction.
For p = 2 p=2 p = 2 , parts (a) and (c) follow from [83 ] alone, since they use only a b = 1 ≠ b a ab=1 \ne ba ab = 1 = ba . Part (b) is a formal consequence of zero divisors in a group algebra of a torsion-free hyperbolic group, so it also holds for the groups of Corollary 5.3 and Proposition 6.9 (§ 12 ). The argument for (c) applies equally to OpenAI’s counterexample with torsion, over the finite field of that construction [84 ] . Over C \mathbb{C} C it gives nothing. If G G G is linearly sofic in the sense of [6 Def. 4.1] , then it answers in the negative their question whether linearly sofic groups satisfy the direct-finiteness conjecture [6 Question 7.9] , and, by (c) with F = F p F=\mathbb{F}_p F = F p , also their question whether every linearly sofic group embeds in ∏ k → ω G L n k ( F ) / d \prod_{k\to\omega} \mathrm{GL}_{n_k}(F)/d ∏ k → ω GL n k ( F ) / d for every finite field F F F [6 Question 8.6] .
Remark 7.14. Surveying results of others, Bartels, Lück and Reich attribute to Formanek [35 ] (see also [21 Lemma 4.1 and Prop. 4.2] ) the statement that all idempotents of F G FG F G are trivial if F F F is a field of prime characteristic p p p , G G G has no p p p -torsion and no g ≠ 1 g \ne1 g = 1 is conjugate to some g p k g^{p^k} g p k ; they note that torsion-free word-hyperbolic groups satisfy these conditions, and conclude [BLR08, §0.6, p. 9]: “Hence Formanek’s results imply that all idempotents in F G FG F G are trivial if G G G is torsionfree word-hyperbolic and F F F is a field.” The triviality results of Formanek that they cite are stated over fields of characteristic zero [35 Thms. 1 and 9] , as is Burger and Valette’s version for torsionfree hyperbolic groups [21 Prop. 4.2 and Remark 4.3] . In characteristic p p p , Formanek’s argument, in Burger and Valette’s form, shows only that the coefficient of 1 1 1 in such an idempotent is 0 0 0 or 1 1 1 [21 Lemma 4.1] ; in characteristic zero, Kaplansky’s theorem that a non-trivial idempotent has this coefficient strictly between 0 0 0 and 1 1 1 [35 Thm. 2] then gives triviality. The idempotents b a ba ba and 1 − b a 1-ba 1 − ba of Corollary 5.2 and Theorem C have coefficients 1 1 1 and 0 0 0 at the identity, since the coefficient of 1 1 1 in b a ba ba equals the one in a b = 1 ab=1 ab = 1 ; this is consistent with that lemma. They show that the characteristic-p p p statement, and with it the quoted one, fails over every field of positive characteristic. The theorems of [16 ] are not affected, and they explain what happens. Hyperbolic groups satisfy the K K K -theoretic Farrell–Jones conjecture [16 Thm. 0.1(i)] , so for G G G as in Corollary 5.2 and Theorem C the map K 0 ( F p ) → K 0 ( F p [ G ] ) K_0(\mathbb{F}_p) \to K_0(\mathbb{F}_p[G]) K 0 ( F p ) → K 0 ( F p [ G ]) is bijective [16 Thm. 0.2] ; their Kaplansky theorem [16 Thm. 0.12] deduces trivial idempotents from this when the group ring is stably finite, the coefficients have characteristic zero, or the group is sofic. None of these holds here, and indeed ( 1 − b a ) F p [ G ] (1-ba)\mathbb{F}_p[G] ( 1 − ba ) F p [ G ] is a non-zero projective module with trivial class in K 0 ( F p [ G ] ) K_0(\mathbb{F}_p[G]) K 0 ( F p [ G ]) , since b a F p [ G ] ≅ F p [ G ] ba\mathbb{F}_p[G] \cong\mathbb{F}_p[G] ba F p [ G ] ≅ F p [ G ] . So in positive characteristic the stable-finiteness hypothesis of [16 Thm. 0.12] cannot be dropped, even for groups satisfying the Farrell–Jones conjecture.
Why characteristic zero is different
The signed handshake needs ∣ S x ∩ S y ∣ ⋅ 1 = 1 |S_x \cap S_y| \cdot1 = 1 ∣ S x ∩ S y ∣ ⋅ 1 = 1 in the coefficient ring for all cross pairs. In characteristic p p p the projective plane does this for us: its point-line incidence matrix X X X satisfies
X X T = q I + J , XX^{\mathsf T}=qI+J, X X T = q I + J ,
since a line has q + 1 q+1 q + 1 points and distinct lines meet in one point, and q = p k q=p^k q = p k vanishes in characteristic p p p . (Its p p p -rank is ( p + 1 2 ) k + 1 \binom{p+1}{2}^k+1 ( 2 p + 1 ) k + 1 [73 , 107 ] .) Over the reals q I + J qI+J q I + J is positive definite, X X X has full rank, and equal and distinct lines give cross-intersections q + 1 q+1 q + 1 and 1 1 1 ; Ivanov points to q I + J qI+J q I + J , of rank one modulo p p p but full rank over Q \mathbb{Q} Q , as the structural reason his construction lives in characteristic p p p [53 §§1.5 and 3] . The direct characteristic-zero analogue of the construction needs types whose cross-intersections are all equal; the step components would then be regular bipartite graphs, and the signed count would vanish over Z \mathbb{Z} Z . This section shows that no such types, and no letter-weighted version of them, are compatible with the squared-word decay of Lemma 6.4 .
Consider one side with a finite family of types S a ⊆ T S_a \subseteq T S a ⊆ T and positive probabilities μ ( a ) \mu(a) μ ( a ) . Let X X X be the type-by-letter incidence matrix, π ( t ) = ∑ a μ ( a ) [ t ∈ S a ] \pi(t)=\sum_a\mu(a)[t\in S_a] π ( t ) = ∑ a μ ( a ) [ t ∈ S a ] and j ( s , t ) = ∑ a μ ( a ) [ s , t ∈ S a ] j(s,t)=\sum_a\mu(a)[s,t\in S_a] j ( s , t ) = ∑ a μ ( a ) [ s , t ∈ S a ] . Assume π ( t ) > 0 \pi(t)>0 π ( t ) > 0 and π ( t ) = π ( t ˉ ) \pi(t)=\pi(\bar{t}) π ( t ) = π ( t ˉ ) ; the latter is needed to match occurrences of t t t with occurrences of t ˉ \bar{t} t ˉ . The turn frequencies are θ ( t , u ) = j ( t ˉ , u ) / π ( t ˉ ) \theta(t,u)=j(\bar{t},u)/\pi(\bar{t}) θ ( t , u ) = j ( t ˉ , u ) / π ( t ˉ ) for u ≠ t ˉ u\ne\bar{t} u = t ˉ and θ ( t , t ˉ ) = 0 \theta(t,\bar{t})=0 θ ( t , t ˉ ) = 0 , and the squared-turn matrix is M ( t , u ) = θ ( t , u ) 2 M(t,u)=\theta(t,u)^2 M ( t , u ) = θ ( t , u ) 2 . In the construction of § 6.3 the hypothesis of the next theorem holds on each side: w w w dominates the turn frequencies and ∑ W P ( W ) 2 = 1 T M W h − 1 1 \sum_W P(W)^2=1^{\mathsf T}M_W^{h-1}1 ∑ W P ( W ) 2 = 1 T M W h − 1 1 with M w = ( w 2 ) M_w=(w^2) M w = ( w 2 ) , so Lemma 6.4 and monotonicity of the spectral radius on nonnegative matrices give ρ ( M ) ≤ ρ ( M w ) < 1 \rho(M)\le\rho(M_w)<1 ρ ( M ) ≤ ρ ( M w ) < 1 . On the bipartite side one takes all A A A -types together, with the weights of A + A_+ A + and A − A_- A − ; the matchings A + , t ˉ → A − , t ˉ A_{+,\bar{t}}\to A_{-,\bar{t}} A + , t ˉ → A − , t ˉ give π ( t ) = π ( t ˉ ) \pi(t)=\pi(\bar{t}) π ( t ) = π ( t ˉ ) , and the combined turn frequencies are weighted averages of those on A ± A_\pm A ± , hence also dominated by w w w .
Theorem 8.1. If M M M has spectral radius less than one, then rank R X ≥ N / 2 + 1 \operatorname{rank}_{\mathbb{R}} X \ge N/2+1 rank R X ≥ N /2 + 1 .
Proof. Let D = diag ( π ) D = \operatorname{diag}(\pi) D = diag ( π ) and C = D − 1 / 2 J ( s , t ) D − 1 / 2 C = D^{-1/2}J(s,t)D^{-1/2} C = D − 1/2 J ( s , t ) D − 1/2 , a positive semidefinite matrix with unit diagonal and rank C = rank X \operatorname{rank} C = \operatorname{rank} X rank C = rank X . Let S = C ∘ 2 − I S = C^{\circ2} - I S = C ∘ 2 − I (entrywise square) and let R R R be the permutation matrix of t ↦ t ˉ t \mapsto\bar{t} t ↦ t ˉ . Using π ( t ) = π ( t ˉ ) \pi(t) = \pi(\bar{t}) π ( t ) = π ( t ˉ ) one checks entrywise that M = D − 1 R S D M = D^{-1}RSD M = D − 1 R S D , so R S RS R S has spectral radius less than one. Then f = ( I − R S ) − 1 1 = ∑ k ( R S ) k 1 f = (I - RS)^{-1}\mathbf{1} = \sum_k (RS)^k\mathbf{1} f = ( I − R S ) − 1 1 = ∑ k ( R S ) k 1 is entrywise positive and S f = R f − 1 < R f Sf = Rf - \mathbf{1} < Rf S f = R f − 1 < R f , that is, ( S f ) t < f t ˉ (Sf)_t < f_{\bar{t}} ( S f ) t < f t ˉ .
Let H = F 1 / 2 C F 1 / 2 H = F^{1/2}CF^{1/2} H = F 1/2 C F 1/2 with F = diag ( f ) F = \operatorname{diag}(f) F = diag ( f ) , and let Q Q Q be the orthogonal projection onto the range of H H H . For each coordinate vector e t e_t e t , H t t = ⟨ Q e t , H e t ⟩ H_{tt} = \langle Qe_t, He_t\rangle H tt = ⟨ Q e t , H e t ⟩ , so by Cauchy–Schwarz H t t 2 ≤ Q t t ( H 2 ) t t H_{tt}^2 \le Q_{tt}(H^2)_{tt} H tt 2 ≤ Q tt ( H 2 ) tt . Here H t t = f t H_{tt} = f_t H tt = f t and ( H 2 ) t t = f t ∑ s C t s 2 f s = f t ( f t + ( S f ) t ) (H^2)_{tt} = f_t\sum_s C_{ts}^2f_s = f_t(f_t + (Sf)_t) ( H 2 ) tt = f t ∑ s C t s 2 f s = f t ( f t + ( S f ) t ) . Hence
Q t t ≥ f t f t + ( S f ) t > f t f t + f t ˉ . Q_{tt} \ge\frac{f_t}{f_t + (Sf)_t} > \frac{f_t}{f_t + f_{\bar{t}}}. Q tt ≥ f t + ( S f ) t f t > f t + f t ˉ f t .
Summing over each inverse pair gives more than one, so rank X = rank H = tr Q > N / 2 \operatorname{rank} X = \operatorname{rank} H = \operatorname{tr} Q > N/2 rank X = rank H = tr Q > N /2 . Since N N N is even, rank X ≥ N / 2 + 1 \operatorname{rank} X \ge N/2 + 1 rank X ≥ N /2 + 1 .
The argument is a weighted, coordinatewise form of the trace bound rank A ≥ ( tr A ) 2 / tr ( A 2 ) \operatorname{rank} A \ge(\operatorname{tr} A)^2/\operatorname{tr}(A^2) rank A ≥ ( tr A ) 2 / tr ( A 2 ) for real symmetric A A A . That bound shows that a unit-diagonal symmetric N × N N \times N N × N matrix with off-diagonal entries at most N − 1 / 2 N^{-1/2} N − 1/2 in absolute value has rank greater than N / 2 N/2 N /2 [4 Lemma 2.2] ; compare the Welch bound [113 ] .
Corollary 8.2. Suppose both sides satisfy the hypotheses of Theorem 8.1 . Then
rank C ( X A diag ( c ) X B T ) ≥ 2 \operatorname{rank}_{\mathbb{C}}\left(X_A\operatorname{diag}(c)X_B^{\mathsf{T}}\right) \ge2 rank C ( X A diag ( c ) X B T ) ≥ 2 for every c ∈ C T c \in\mathbb{C}^{T} c ∈ C T whose support is nonempty and closed under t ↦ t ˉ t \mapsto\bar{t} t ↦ t ˉ . In particular no cross-intersection matrix X A X B T X_AX_B^{\mathsf{T}} X A X B T is a nonzero multiple of J J J , and no such weighting c c c makes the weighted cross-intersections factor as u a v b u_av_b u a v b .
Proof. Restricting both type families to the support U U U of c c c keeps the letter and joint frequencies on U U U , and the squared-turn matrix becomes the principal submatrix M [ U , U ] M[U,U] M [ U , U ] , whose spectral radius is at most ρ ( M ) < 1 \rho(M) < 1 ρ ( M ) < 1 by Perron–Frobenius monotonicity. Theorem 8.1 gives ranks at least ∣ U ∣ / 2 + 1 |U|/2 + 1 ∣ U ∣/2 + 1 on each side, and Sylvester’s inequality gives rank at least 2 for the product through the invertible diagonal matrix.
Weightings whose support is not closed under t ↦ t ˉ t \mapsto\bar{t} t ↦ t ˉ are not usable: the pairing ι \iota ι of Lemma 6.1 cancels c c c -weighted terms only when c ( t ˉ ) = c ( t ) c(\bar{t}) = c(t) c ( t ˉ ) = c ( t ) .
So in characteristic zero no cancellation design built into the types, weighted or not, survives the squared-word decay safeguard. Ivanov observed that the obvious designs with constant cross-intersections destroy the decay estimate and wrote that he knew no design combining exact constancy with squared-word decay [53 §8.2] ; Corollary 8.2 shows that none exists. In characteristic p p p the same corollary forces some cross-intersection to be at least p + 1 p + 1 p + 1 (the entries of X A X B T X_AX_B^{\mathsf{T}} X A X B T are nonnegative integers congruent to 1 modulo p p p , and they are not all equal to 1), so these designs need at least p + 1 p + 1 p + 1 letters, and a bounded alphabet cannot serve infinitely many primes. The corollary does not exclude cancellation that depends on the matchings themselves, balanced components that are not regular, or a different safeguard. There is also a route through bounded supports.
Proposition 8.3. Suppose that for infinitely many primes p p p there are a torsion-free group G p G_p G p and nonzero zero divisors α p β p = 0 \alpha_p\beta_p = 0 α p β p = 0 in K p [ G p ] K_p[G_p] K p [ G p ] , for a field K p K_p K p of characteristic p p p , whose supports have sizes bounded independently of p p p . Then, for infinitely many of these p p p , the group G p G_p G p has nonzero zero divisors in C [ G p ] \mathbb{C}[G_p] C [ G p ] , with algebraic coefficients.
Proof. This is a form of the Lefschetz principle (see, e.g., [68 Corollary 2.2.10] ). Passing to infinitely many p p p , we may fix the support sizes a , b a,b a , b and the partition of [ a ] × [ b ] [a] \times[b] [ a ] × [ b ] according to equality of the products x i y j x_i y_j x i y j of support elements. The vanishing of α p β p \alpha_p\beta_p α p β p and the nonvanishing of all coefficients form a fixed system of polynomial equations over Z \mathbb{Z} Z : one equation ∑ ( i , j ) ∈ C X i Y j = 0 \sum_{(i,j)\in C} X_iY_j=0 ∑ ( i , j ) ∈ C X i Y j = 0 for each block C C C , and Z ∏ i X i ∏ j Y j = 1 Z\prod_i X_i\prod_j Y_j=1 Z ∏ i X i ∏ j Y j = 1 . It has solutions over F p \mathbb{F}_p F p for infinitely many p p p . If it had no complex solution, the weak Nullstellensatz would place 1 1 1 in its ideal over C \mathbb{C} C , hence over Q \mathbb{Q} Q , since the generators have rational coefficients and a linear system over Q \mathbb{Q} Q that is solvable over C \mathbb{C} C is solvable over Q \mathbb{Q} Q ; clearing denominators would then place a nonzero integer in its ideal over Z \mathbb{Z} Z . The system would then be inconsistent in all but finitely many characteristics. A complex solution, which may be taken algebraic, used in any of the groups realizing the partition (the support elements there are distinct), gives the zero divisors. Torsion-freeness is not used in the argument; it only makes the conclusion a counterexample.
Ivanov notes the same transfer for one fixed group with fixed supports [53 §8.3] ; Proposition 8.3 allows the group to vary with a fixed coincidence pattern. The converse transfer, from characteristic zero to all but finitely many characteristics, is noted by Gardam [39 Section 1] ; it is the Nullstellensatz reduction of the Kaplansky conjectures to finite fields, see [13 Section 1] and [67 Section 3.4.3] .
The constructions of Proposition 6.9 and Theorem C do not provide supports bounded independently of p p p : the witnesses are sums over root components of graphs with at least n 0 n_0 n 0 , respectively p 2 v 2 p^2v^2 p 2 v 2 , vertices, and these numbers grow with p p p . So the proposition does not apply to them.
The torsion example of [OAI-197b] is CAT(0)
The glued group. Let ℓ \ell ℓ be an odd prime and ( V , F ) (V,\mathcal{F}) ( V , F ) a finite incidence structure in which every point lies on exactly ℓ + 1 \ell+1 ℓ + 1 members and every member has at least two points; let g 0 g_0 g 0 be the girth of its bipartite incidence graph I \mathcal{I} I . (In [84 ] the members are affine lines with at least four points.) For v ∈ V v\in V v ∈ V let K v ≅ ( Z / ℓ ) 2 K_v\cong(\mathbb{Z}/\ell)^2 K v ≅ ( Z / ℓ ) 2 , for f ∈ F f\in\mathcal{F} f ∈ F let L f ≅ Z / ℓ L_f\cong\mathbb{Z}/\ell L f ≅ Z / ℓ , and for v ∈ f v\in f v ∈ f choose injections ι v f : L f → K v \iota_{vf}:L_f\to K_v ι v f : L f → K v such that, for each v v v , the ℓ + 1 \ell+1 ℓ + 1 images are the ℓ + 1 \ell+1 ℓ + 1 distinct subgroups of order ℓ \ell ℓ of K v K_v K v . The glued group N N N is the free product of all K v K_v K v and L f L_f L f modulo the relations ι v f ( x ) = x \iota_{vf}(x)=x ι v f ( x ) = x . This is the group of [84 §3.1] : copies of F ℓ 2 F_\ell^2 F ℓ 2 glued along their lines according to the incidence structure.
Theorem 9.1. If g 0 ≥ 12 g_0\ge12 g 0 ≥ 12 , then N N N acts properly and cocompactly by isometries on a CAT(0) piecewise Euclidean 2-complex. If g 0 ≥ 14 g_0\ge14 g 0 ≥ 14 , it acts properly and cocompactly on a CAT(− 1 -1 − 1 ) piecewise hyperbolic 2-complex, so N N N is word-hyperbolic.
Proof. Let K \mathcal{K} K be the cone on I \mathcal{I} I : its vertices are the apex O O O , the members f ∈ F f\in\mathcal{F} f ∈ F and the points v ∈ V v\in V v ∈ V , and it has one triangle ( O , f , v ) (O,f,v) ( O , f , v ) for each incidence v ∈ f v\in f v ∈ f . Define a simple complex of groups over K \mathcal{K} K with local group K v K_v K v at v v v , local group L f L_f L f at f f f and on the edge { f , v } \{f,v\} { f , v } (mapping to K v K_v K v by ι v f \iota_{vf} ι v f ), and trivial local groups elsewhere [14 §II.12] . Its direct limit is N N N .
The links of the local developments [14 §§II.12, III.C.4] are as follows. At v v v , the vertices are the cosets of the trivial group in K v K_v K v (towards O O O ) and the cosets of the subgroups ι v f ( L f ) \iota_{vf}(L_f) ι v f ( L f ) (towards the members f ⊃ v f\supset v f ⊃ v ), and x x x is joined to x + ι v f ( L f ) x+\iota_{vf}(L_f) x + ι v f ( L f ) ; this is the point-line incidence graph of the affine plane AG ( 2 , ℓ ) \operatorname{AG}(2,\ell) AG ( 2 , ℓ ) , of girth 6. At f f f , the link is the complete bipartite graph K ℓ , ℓ K_{\ell,\ell} K ℓ , ℓ , of girth 4. At O O O , the link is I \mathcal{I} I , of girth g 0 g_0 g 0 .
Give every triangle the angles ( α O , π / 2 , π / 3 ) (\alpha_O, \pi/2, \pi/3) ( α O , π /2 , π /3 ) at ( O , f , v ) (O, f, v) ( O , f , v ) , with α O = π / 6 \alpha_O = \pi/6 α O = π /6 (a Euclidean triangle) if g 0 ≥ 12 g_0 \ge12 g 0 ≥ 12 , and α O = π / 7 \alpha_O = \pi/7 α O = π /7 (a hyperbolic triangle of curvature − 1 -1 − 1 ) if g 0 ≥ 14 g_0 \ge14 g 0 ≥ 14 . In each link every injective loop then has length at least min { 6 ⋅ π 3 , 4 ⋅ π 2 , g 0 α O } ≥ 2 π \min\{6 \cdot\frac{\pi}{3}, 4 \cdot\frac{\pi}{2}, g_0\alpha_O\} \ge2\pi min { 6 ⋅ 3 π , 4 ⋅ 2 π , g 0 α O } ≥ 2 π , so the links are CAT(1) [14 II.5.6] and the complex of groups is non-positively, respectively negatively, curved [14 II.5.2] . It is therefore developable [14 Thm. III.C.4.17] : the local groups inject into N N N , which is its fundamental group, and N N N acts with finite stabilizers and compact quotient K \mathcal{K} K on the development, a simply connected locally CAT(0), respectively CAT(− 1 -1 − 1 ), complex with finitely many shapes, hence CAT(0), respectively CAT(− 1 -1 − 1 ); see also [109 Hae91] . A group acting properly and cocompactly on a CAT(− 1 -1 − 1 ) space is hyperbolic [14 Prop. III.H.1.2, Prop. I.8.19] .
Proof of Theorem D. The group G G G of [84 Thm. 1.1] is built from the glued group N N N of incidence data of girth at least 12 [84 §§3–5] in three steps [84 §§4.2, 4.5, 4.6] : the direct product H = N × ⟨ z ⟩ H = N \times\langle z\rangle H = N × ⟨ z ⟩ with a cyclic group of order ℓ \ell ℓ ; a multiple HNN extension M M M of H H H with stable letters τ v \tau_v τ v (v ∈ V v \in V v ∈ V ) conjugating K v × ⟨ z ⟩ K_v \times\langle z\rangle K v × ⟨ z ⟩ onto K ∗ × ⟨ z ⟩ K_* \times\langle z\rangle K ∗ × ⟨ z ⟩ , finite subgroups of order ℓ \ell ℓ ; and the direct product G = M × Q G = M \times Q G = M × Q with a finite group Q Q Q (M M M and Q Q Q are called L L L and F F F in [84 ] ). By Theorem 9.1 , N N N acts properly and cocompactly on a CAT(0) space Y Y Y , and so does H H H , through H → N H \to N H → N . Each finite subgroup of H H H fixes a point of Y Y Y [14 Cor. II.2.8] . Over the Bass–Serre tree of M M M , take one copy of Y Y Y for each vertex and, for each edge, join the fixed points of its (finite) edge group in the two adjacent copies by a segment of length one, equivariantly. Gluing CAT(0) spaces along points yields CAT(0) spaces [14 II.11.1] , and any two points of this tree of spaces lie in the union of finitely many pieces; so it is CAT(0), and M M M acts on it properly and cocompactly. The finite factor Q Q Q acts trivially. If g 0 ≥ 14 g_0 \ge14 g 0 ≥ 14 , the same construction starting from the CAT(− 1 -1 − 1 ) space of Theorem 9.1 is CAT(− 1 -1 − 1 ), and G G G is hyperbolic; alternatively, an HNN extension of a hyperbolic group over finite subgroups is hyperbolic [12 ] .
Remark 9.2. (1) With g 0 = 12 g_0 = 12 g 0 = 12 , the link condition forces α O ≥ π / 6 \alpha_O \ge\pi/6 α O ≥ π /6 , α f ≥ π / 2 \alpha_f \ge\pi/2 α f ≥ π /2 and α v ≥ π / 3 \alpha_v \ge\pi/3 α v ≥ π /3 , whose sum is π \pi π ; so for no metric on K \mathcal{K} K in which all triangles are congruent is the complex of groups negatively curved, and the development is never CAT(− 1 -1 − 1 ) for such a metric. (The cone K \mathcal{K} K itself can be CAT(− 1 -1 − 1 ): its links at f f f and v v v are trees.) (2) Theorem 9.1 recovers the injectivity of the local groups, which [84 Lemma 3.2] proves by an Euler-characteristic argument; OpenAI’s reasoning trace records the same link computation as an alternative route to these embeddings [92 §12] . (3) We expect that the probabilistic construction of [84 §5] can be run with girth at least 14, but we have not written a proof, and nothing here depends on it; Corollary 5.2 and Theorem C already provide torsion-free hyperbolic examples. OpenAI’s reasoning trace for that construction raises the “speculative possibility of a hyperbolic example” and leaves it exploratory [92 §§17 and 21] .
Related work, remarks and questions
Context. Beyond the results recalled in the introduction, (Z) holds for locally indicable groups [51 ] , torsion-free elementary amenable groups [60 ] and groups with the unique-product property [23 ] , [97 Ch. 13] , and, over every field, for torsion-free virtually compact special groups and torsion-free three-manifold groups [37 Thm. 1.3(1) and Cor. 1.5] ; for three-manifold groups over C \mathbb{C} C see also [59 ] . Over C \mathbb{C} C , (Z) follows from the strong Atiyah conjecture, which is known for torsion-free groups in Linnell’s class C \mathcal{C} C [64 ] , locally indicable groups [55 ] and virtually compact special groups [105 ] . (D) holds in every characteristic for free-by-amenable groups [AOP02] and sofic groups [33 Cor. 4.7] . Dykema, Heister and Juschenko reduced (D) to finitely presented groups that are universal for one-sided inverses with supports of given sizes, and showed by computation that (D) holds over F 2 \mathbb{F}_2 F 2 for supports of sizes ( 3 , n ) (3,n) ( 3 , n ) with n ≤ 11 n \le11 n ≤ 11 and ( 5 , 5 ) (5,5) ( 5 , 5 ) [30 ] . Gardam’s counterexample to (U) lives in Promislow’s torsion-free virtually abelian group [100 , 38 ] ; Murray extended it to every positive characteristic [78 ] , and Gardam to characteristic zero, also giving a unit over F 2 \mathbb{F}_2 F 2 for a virtually nilpotent group of Soelberg [39 Thms. A and B] . These groups are virtually nilpotent, so they satisfy (Z) [60 ] , and they contain Z 2 \mathbb{Z}^2 Z 2 , so no hyperbolic group contains them. Bartholdi showed that Gardam’s units are twisted unitary, and noted that all units then known have non-trivial symmetry [10 ] . To our knowledge, all counterexamples known before 2026 were counterexamples to (U) in virtually nilpotent groups. By the classical step of Lemmas 2.2 and 2.3 (Connell’s theorem; [97 Lemma 13.1.2] ), the zero divisors of Corollaries 5.2 and 5.3 , Proposition 6.9, and Theorem C give non-trivial units in group algebras of torsion-free hyperbolic groups, in every positive characteristic; we know of no earlier example in a hyperbolic group. The same step gives non-trivial units for every outcome of the random constructions of [82 ] and [53 ] for which their conclusions hold, that is, the group is torsion-free and the two factors are non-zero. Neither paper states hyperbolicity; for the model of [82 ] it holds on the event of probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) in Corollary 5.3 , and the same criterion applies to Ivanov’s model, given his estimates (Remark 6.10).
Characteristic zero. Over every field of characteristic zero, (D) holds for all groups [58 , 75 ] , and (I) holds for torsion-free hyperbolic groups [101 ] : the coefficients of an idempotent lie in a finitely generated subfield, which embeds in C \mathbb{C} C . Over C \mathbb{C} C this also follows from Formanek’s theorem [35 Thm. 9] with [21 Remark 4.3] , and from the Baum–Connes conjecture for hyperbolic groups [80 , 63 ] . Hyperbolicity matters for this analytic route: OpenAI’s unrefereed preprint [89 Thm. 1.1] constructs a finitely generated torsion-free group whose reduced C ∗ C^* C ∗ -algebra contains a projection other than 0 and 1, disproving the Kadison–Kaplansky projection conjecture; by [86 Cor. 1.2(ii)] , as OpenAI note there, this projection does not lie in the group algebra. Over every field of characteristic zero, (I) for torsion-free hyperbolic groups also follows, without embedding in C \mathbb{C} C , from the K K K -theoretic Farrell–Jones conjecture, which holds for hyperbolic groups [16 Thms. 0.1, 0.2 and 0.12(ii)] . OpenAI’s unrefereed preprint [86 Cor. 1.2(ii)] proves (I) for every torsion-free group over every commutative domain of characteristic zero, and this statement is formalized in their Lean development as a Comparator target [OAI-Lean]. Remark 7.14 compares this with a statement over arbitrary fields. Over C \mathbb{C} C , (Z) for torsion-free hyperbolic groups is known only for special classes [29 , 105 , 2 , 37 ] , and § 10 shows that our mechanism needs a new ingredient to get there.
Why hyperbolicity is natural. Gromov’s density model [45 ] and Ollivier’s sharp phase transition [94 ] show that random presentations are hyperbolic below density 1 / 2 1/2 1/2 ; see [95 ] . Proving hyperbolicity by counting bounded diagrams is the standard route for random groups, where a local-to-global principle passes from bounded diagrams to all diagrams [45 9.B] , [94 ] ; here recursive planar separation (Lemma 3.7 ) takes the place of the local-to-global step, as in OpenAI’s hyperbolic group without a geometric CAT(0) action [88 Thm. 3.1] . Gromov’s graphical random groups [43 ] and graphical small cancellation theory [96 , 47 ] relate labelled graphs to hyperbolicity and asphericity, and [11 ] studies asphericity of groups defined by graphs. OpenAI explicitly do not invoke a small-cancellation or CAT(0) criterion for their groups [82 §1] : their bounded-pattern estimate replaces it. Theorem B shows that this estimate, combined with their planar reduction, is already a linear isoperimetric inequality; in the language of small cancellation theory, pattern-freeness is a local isoperimetric condition and Proposition 4.4 a local-to-global principle.
Gromov’s graphical small cancellation theorem [43 ] , in the form proved by Ollivier Ollivier [96 Thm. 1] , does not apply to these graphs. Consider immersed graphs over an alphabet of size s s s with minimum degree d ≥ 3 d \ge3 d ≥ 3 , and suppose that ( d − 1 ) 4 > s − 1 (d-1)^4 > s-1 ( d − 1 ) 4 > s − 1 . If the girth g g g tends to infinity, the hypothesis of [96 Thm. 1] , that every piece (a word with two different immersions in the graph) is shorter than g / 6 g/6 g /6 , must eventually fail. Indeed, a component has at least ( d − 1 ) ⌊ ( g − 1 ) / 2 ⌋ (d-1)^{\lfloor(g-1)/2\rfloor} ( d − 1 ) ⌊( g − 1 ) /2 ⌋ vertices, while the condition forces distinct non-backtracking paths of length ⌈ g / 6 ⌉ \lceil g/6\rceil ⌈ g /6 ⌉ to read distinct reduced words; comparing the two counts gives ( d − 1 ) 4 ≤ s − 1 (d-1)^4 \le s-1 ( d − 1 ) 4 ≤ s − 1 asymptotically. OpenAI’s zero-divisor design, with ( d , s ) = ( 129 , 16516 ) (d,s)=(129,16516) ( d , s ) = ( 129 , 16516 ) , and ours for p = 3 p=3 p = 3 , with ( 82 , 6648 ) (82,6648) ( 82 , 6648 ) , violate this. The count concerns only this metric condition. It does not decide Ollivier’s weaker condition, which compares a piece only with the cycles on which it lies [96 Remark 2] , the graphical G r ′ ( 1 / 6 ) Gr'(1/6) G r ′ ( 1/6 ) condition with pieces taken up to label-preserving automorphisms [41 ] , or Gruber’s non-metric conditions: a G r ( 7 ) Gr(7) G r ( 7 ) -labelled graph gives a linear isoperimetric inequality, and a C ( 6 ) C(6) C ( 6 ) -labelled graph an aspherical presentation [47 Thms. 2.16 and 2.18] . We have not checked these conditions for our graphs; Theorem B needs none of them.
Unique products, cubulation and Delzant’s theorem. Since their group algebras have zero divisors, the groups of Corollaries 5.2 and 5.3 , Proposition 6.9, and Theorem C do not have the unique-product property, as OpenAI note for their group [82 §6] . Torsion-free groups without unique products go back to Rips and Segev [103 ] , answering a question of Passman [97 ] . Promislow gave a virtually abelian example [100 ] , and Mian and Siddique give a formal proof that Gardam’s A 2 A_2 A 2 lattice lacks unique products [MS26]. Steenbock completed the proof that the Rips–Segev groups are torsion-free and showed that they and their generalizations are hyperbolic, which gave the first torsion-free hyperbolic groups without unique products [110 ] . Further hyperbolic examples are given by Arzhantseva and Steenbock, including ones with Kazhdan’s property (T) [AS23], and by Gruber, Martin and Steenbock, with every subgroup up to a given index also without unique products [41 ] . To our knowledge, the groups of Corollaries 5.2 and 5.3 , Proposition 6.9, and Theorem C are the first torsion-free hyperbolic groups for which (Z) is known to fail. They are constructed differently from the Rips–Segev groups, and nothing here decides Arzhantseva and Steenbock’s question whether those satisfy (Z) [AS23, Open problem 6.1], which remains open; Steenbock expects a positive answer [110 Introduction] .
Remark 10.1 (Delzant’s theorem). Delzant proved that a group acting by isometries on a geodesic δ \delta δ -hyperbolic space with injectivity radius inf g ≠ 1 inf x ∣ g x − x ∣ \inf_{g\ne1}\inf_x |gx-x| inf g = 1 inf x ∣ g x − x ∣ greater than 4 δ 4\delta 4 δ has the strong unique-product property, and that its group ring over any domain has no zero divisors and only trivial units [29 Théorème and Proposition, p. 382] ; it follows, as Arzhantseva and Steenbock note [AS23, §6], that every residually finite hyperbolic group has a finite-index subgroup with unique products. So no group whose group algebra over a field has zero divisors admits such an action. For our groups this needs only the zero divisors, not hyperbolicity; compare [82 §6] , where OpenAI note that their group lacks unique products. Delzant noted that his displacement hypothesis is restrictive and does not reach general hyperbolic groups [29 Remarques, p. 382] . Because the groups of Corollary 5.2 , Proposition 6.9, and Theorem C are hyperbolic, it cannot be dropped from his zero-divisor and unit conclusions within torsion-free hyperbolic groups; for the unique-product conclusion this was known from the Rips–Segev groups [103 , 110 ] . The absence of zero divisors says that principal ideals are free; Avramidi [9 ] shows, by a division algorithm in the hyperbolic plane, that submodules generated by two elements, in particular two-generator ideals, are free in group algebras of surface groups of large genus, and Avramidi and Delzant [2 ] show, for groups acting on a hyperbolic space, that ideals generated by n n n elements are free when the minimal displacement is large in terms of n n n .
By [37 Thm. 1.3(1)] , a torsion-free group whose group algebra over some field has zero divisors is not virtually compact special. A proper action of a torsion-free group is free, so Agol’s theorem [3 ] , which builds on [52 ] , shows that such a hyperbolic group is not cubulated, as in Corollary 7.13 (b). Arzhantseva and Steenbock made the same observation over C \mathbb{C} C , and gave torsion-free hyperbolic groups without unique products that are not cubulable because they have property (T) [AS23, §6]. This contrasts with cubulation results for small cancellation groups [114 , 76 ] .
Division rings and orderability. A division ring has no zero divisors, so for G G G as in Corollaries 5.2 and 5.3 , Proposition 6.9, and Theorem C and every field K K K of the corresponding characteristic p p p , K [ G ] K[G] K [ G ] embeds in no division ring. The pair ( K , G ) (K,G) ( K , G ) is therefore a counterexample to the conjecture that the group algebra of a torsion-free group over a field embeds in a division ring [37 Conj. 1.1] , to the existence part of Jaikin-Zapirain and Linton’s conjecture that K [ G ] K[G] K [ G ] has a Linnell division ring, unique up to K [ G ] K[G] K [ G ] -isomorphism [54 Conj. 1] , and to its extension to crossed products over division rings [37 Conj. 1.2] . These consequences already follow from the zero divisors of [82 ] in characteristic two and of [53 ] in odd characteristic; what our groups add is hyperbolicity. For the same reason these groups are neither left-orderable nor locally indicable [51 ] .
Signed schemes. Signed cancellation has been proposed before. Mineyev’s product structures pair the terms of a product into cells of equal group elements. Mineyev gives combinatorial conditions under which an associated two-complex is non-positively curved and the associated elements are counterexamples over F 2 \mathbb{F}_2 F 2 , or, when the structure admits a signature (signs that are opposite on the two members of every cell), over every ring with unity [72 §§2.2, 3.5, 3.6 and Thm. 27] , [40 Thm. 16] . Garg and Mineyev prove that the middle link of every orientable product structure has half-girth at most 4, and that no product structure with a support of size at most 5 satisfies Mineyev’s conditions T 1 \mathrm{T}_1 T 1 –T 4 \mathrm{T}_4 T 4 ; a computer-assisted search extends this to all pairs of support sizes up to 13 [40 Thms. 1–3] . Shin shows that these conditions fail whenever both supports have size at least two [106 ] . Rips constructed a series of groups with potential zero divisors; Bardakov and Petukhova classify its simplest groups and show that all of them have 2-torsion [17 ] , and Mineyev observes that the construction is a special case of product structures with signature [72 §1] . A signed candidate over Z [ G ] \mathbb{Z}[G] Z [ G ] was discussed recently in [74 ] ; Rüping showed there that its cancellation pattern forces an element t t t with t 3 = 1 t^3=1 t 3 = 1 , and that the product factors through ( t − 1 ) ( 1 + t + t 2 ) (t-1)(1+t+t^2) ( t − 1 ) ( 1 + t + t 2 ) . None of these schemes has a known torsion-free instance. Ivanov’s construction [53 ] , which signs OpenAI’s parity count modulo an odd prime, realizes a signed cancellation in torsion-free groups, but it is not an instance of these schemes, as we now explain.
The sign rule of Lemma 6.1 is Mineyev’s signature condition; the difference is what is paired. In a product structure each term of the product lies in exactly one cell, so a signature cancels the product over every ring at once, and a torsion-free instance would give zero divisors over Z \mathbb{Z} Z . Here the pairs partition the multiset Φ \Phi Φ , in which the term g x h y − 1 g_xh_y^{-1} g x h y − 1 occurs ∣ S x ∩ S y ∣ |S_x\cap S_y| ∣ S x ∩ S y ∣ times. pairing cancels Φ \Phi Φ exactly, but the product vanishes only because every multiplicity is 1 modulo p p p . Mineyev’s framework also covers a b = 1 ab = 1 ab = 1 , through odd product structures with exactly one 1-cell [72 §§2.1 and 2.3] ; the exception at the root in Proposition 7.11 plays the role of that 1-cell.
Soficity. Non-sofic groups were first constructed in August 2026 [OAI-Ten, FF26, KT26], and Chapman and Peled had earlier given a conditional construction of a non-sofic hyperbolic group [26 ] . OpenAI constructed a torsion-free hyperbolic group that is not residually finite [87 ] . In [32 ] we proved that this group is not sofic, and Sandhu and Thom gave an explicit non-sofic hyperbolic group and a torsion-free hyperbolic group without non-trivial sofic quotients [108 ] , using [62 ] . For the relation between residual finiteness and soficity of hyperbolic groups, see [7 Conj. 2.8] . Being non-sofic, the groups of Corollary 5.2 and Theorem C are not residually finite. Quantitatively, some finite subset of each of them has infinite sofic profile in the sense of Cornulier [25 ] ; in amenable groups all profiles are finite, but they can be nearly exponential [31 ] .
Questions 10.2. (1) Is C [ G ] \mathbb{C}[G] C [ G ] a domain for every torsion-free hyperbolic group G G G ? Is there any torsion-free group with zero divisors over C \mathbb{C} C ? (2) Can one write down, in a form that can be inspected directly, a torsion-free hyperbolic group whose group algebra over a field of positive characteristic has zero divisors, or is not directly finite, in the spirit of the explicit non-sofic hyperbolic group of [108 ] ? Miah’s finite incidence data are explicit, but his graph is the first matching found by a search that terminates because a suitable matching is known to exist [71 §§1 and 8] . By Theorem B, a pattern-free graph specified without such a search, with types satisfying the congruences of Proposition 5.1 , Lemma 6.3 or Lemma 7.2 , would give one. (3) Are the groups of Corollary 5.2 , Proposition 6.9, and Theorem C hyperlinear? Do they act properly and cocompactly on a CAT(0) space? They are not cubulated, and OpenAI have shown that a hyperbolic group need not act geometrically on any proper complete CAT(0) space [88 Thm. 1.1] ; Mineyev’s program looks for counterexamples among CAT(0) groups built from product structures [72 , 40 ] .
Contributions, attribution and how this work was done
Due to OpenAI. The groups of Corollaries 5.2 to 5.4 and of Theorems A and D; the parity certificates (Proposition 5.1 ); the random models, their girth and diameter estimates and the bounded-pattern estimates (Theorem 3.4 ); the closure, separation and interval lemmas, whose proofs we reproduce (Lemmas 3.6 to 3.8 , Appendix § 14 ); the constants (2); the cone pictures [82 Lemma 5.2] and the surgeries of Lemma 4.3 ; the splitting, separation and counting scheme of Proposition 4.4 ; and the exclusion of reduced spheres and rooted discs, hence asphericity, root protection and torsion-freeness [82 , 83 , 84 ] . Our proofs of the last three follow theirs, reorganized around Proposition 4.4 . Also OpenAI’s: the vertex types built from the lines of a projective plane and extra letters [82 §2.1] , and the Fano-complement template [83 §3.1] , which § 6 and § 9 adapt; the switching, expansion and bounded-pattern arguments that those sections rerun for new models; and, for a different random complex, the scheme that turns a bounded counting estimate into asphericity and a linear isoperimetric inequality by planar separators, with contacts on the outer boundary paid for by its length [88 Thm. 3.1 and Lemma 3.8] . OpenAI’s reasoning trace for [84 ] records the route of Theorem 9.1 through Haefliger’s developability theorem for non-positively curved complexes of groups, with its link computation (links of girths 6, 4 and 12, angles π / 3 \pi/3 π /3 , π / 2 \pi/2 π /2 and π / 6 \pi/6 π /6 ), as an alternative route to the local-group embeddings, and the possibility of a hyperbolic example at girth 14 with angles π / 7 \pi/7 π /7 , π / 3 \pi/3 π /3 and π / 2 \pi/2 π /2 , which it left exploratory [92 §§12, 17 and 21] .
Due to Ivanov and others. In priority (§ 1 ), the following are Ivanov’s: for odd p p p , torsion-free groups with a finite two-dimensional classifying space and zero divisors over F p \mathbb{F}_p F p [Iva26, Thm. 1.1]; the signed cancellation (Lemma 6.1; [Iva26, Lemma 2.2]); the two-colour model (§ 6.3 ; [Iva26, Construction 4.1]); and the transfer of OpenAI’s switching, diameter and bounded-pattern estimates to that model [53 Lemmas 4.2 and 4.4, Prop. 6.1] , with the colour data in the pattern count [53 §6.1] , which § 6 and § 9 also use. Ivanov also proved the decay estimate for his design with an explicit test vector [53 Prop. 5.3] ; checked {citep}[82 §§3–5] , with the lemmas of its Section 2 that they use, line by line {citep}[53 Appendix A] , and two of his points there, the injectivity of the switching map and the domination of the $A$-side turn frequencies by the weights $w$, appear in the same form in {xref}Lemma 6.5 and {xref}Section 6.4 {citep}[53 Remarks A.1 and A.3] ; identified the matrix q I + J qI+J q I + J , of rank one modulo p p p but full rank over Q \mathbb{Q} Q , as the structural reason the construction lives in characteristic p p p [53 §§1.5 and 3] ; observed that the obvious constant-intersection designs destroy the decay estimate, writing that he knew no design combining exact constancy with it {citep}[53 §8.2] , which {xref}Theorem 8.1 and {xref}Corollary 8.2 settle in the negative; and noted the Nullstellensatz transfer of {xref}Proposition 8.3 for one fixed group {citep}[53 §8.3] . The same sign rule appears earlier as Mineyev’s signature condition {citep}[72 §2.2] . Presentations by labelled graphs go back to Rips and Segev {citep}[103 ] and to Gromov {citep}[43 ] . That a torsion-free counterexample to (D) also disproves (I), (Z) and (U) is noted by Bradford and Fournier-Facio {citep}[13 §1] . The switching method is McKay’s {citep}[69 , 79 ] `.
Classical. Lemmas 2.1 to 2.4 ; the correspondence between pictures and van Kampen diagrams, and between spherical pictures and π 2 \pi_2 π 2 ; Lipton–Tarjan separation; the Hurewicz and Whitehead theorems; the criteria for hyperbolicity, developability and CAT(0) used in § 4 and § 11 ; and the Lefschetz principle and the weak Nullstellensatz used in Proposition 8.3 , with the references given there.
New here. (i) The free case of Proposition 4.4 : OpenAI’s exclusion for these cone complexes survives when the boundary letters of a van Kampen diagram are counted as unpaired, at the cost of a term ℓ ∞ / ε \ell_\infty/\varepsilon ℓ ∞ / ε . Capping a diagram to a sphere is standard, and the accounting is that of [88 Thm. 3.1] ; what is new is its application to the cone complexes of {citep}[82 , 83 ] . (ii) The organization of OpenAI’s arguments into one proposition with three consequences, and the resulting deterministic criterion, {xref}Theorem B, through which the paper depends on {citep}[82 , 83 ] only via {xref}Table 2; this is a new formulation, not a new mechanism. (iii) Hyperbolicity: {xref}Theorem A, hence the hyperbolic groups of {xref}Corollaries 5.2 to 5.4 (the last with an explicit constant) and {xref}Proposition 6.9. (iv) The direct-finiteness construction in odd characteristic: the signed form of OpenAI’s self-pairing of the root component, with its exception at the root; the types of {xref}Definition 7.1; the exact solution of the colour-balance problem and the residue and Perron certificates ({xref}Sections 7.2 and 7.3); and the proofs of inputs (a)–(d) for that model, (b)–(d) by rerunning {citep}[83 ] with the colour data of {xref}Proposition 6.7 ({xref}Proposition 7.9); hence {xref}Theorem C and {xref}Corollary 7.13. Also the type design of {xref}Definition 6.2, which differs from Ivanov’s, and its decay estimate ({xref}Lemma 6.4`); the other inputs for it are rerun as Ivanov does for his design (§ 6.4 ). (v) The characteristic-zero obstruction as a theorem (Theorem 8.1 , Corollary 8.2 ), and Proposition 8.3 for groups that vary with a fixed coincidence pattern. (vi) A written proof of the link computation (Theorem 9.1 ), and the passage from the glued group to OpenAI’s full group (Theorem D). (vii) The Lean formalization of the Main Theorem, by N. Mghirbi [Mgh26], described next.
Formal verification. N. Mghirbi has formalized the Main Theorem in Lean 4 [Mgh26], with Lean v4.34.1 and Mathlib commit d13f23b, the versions OpenAI use. The statements are in one file, Kaplansky/Challenge.lean, which contains only definitions and statements. Its definitions of torsion-freeness, of a finite two-dimensional classifying space and of word-hyperbolicity are copied verbatim from OpenAI’s public Comparator challenges [OAI-Lean], specialised from arbitrary universes to Type. In them, a group is word-hyperbolic if the geodesic triangles of its Cayley graph for some finite generating set are uniformly thin, and it has a finite two-dimensional classifying space if it is the fundamental group of a finite connected two-dimensional CW complex with a contractible covering space. Fields K K K in MainTheoremConsequences likewise range over Type. Finite presentation and group algebras are Mathlib’s Group.IsFinitelyPresented and MonoidAlgebra. The theorem Kaplansky.Final.mainTheorem_proof states that for every prime p p p there are a finitely presented, torsion-free, word-hyperbolic group G G G with a finite two-dimensional classifying space and a , b ∈ F p [ G ] a,b \in\mathbb{F}_p[G] a , b ∈ F p [ G ] with a b = 1 ≠ b a ab=1 \ne ba ab = 1 = ba . The theorem Kaplansky.Final.mainTheoremConsequences_proof states that, for the same groups and every field K K K of characteristic p p p , K [ G ] K[G] K [ G ] is not directly finite and contains an idempotent other than 0 and 1, a zero divisor, and a unit u u u with u p = 1 u^p=1 u p = 1 that is not of the form λ g \lambda g λ g . The development contains no sorry outside the statement file. It builds with lake build Kaplansky.Final.Main, and #print axioms reports only the standard axioms propext, Classical.choice and Quot.sound for both theorems (build record of 25 October 2026). It includes OpenAI’s Lean modules for [82 ] and parts of their developments for [87 ] and [85 ] . These retain the upstream source except for the import adaptations and the excerpt of CayleyMetric.lean as GraphMetric.lean, each modified file carrying a notice, as documented in OAI/VENDOR.md; they are redistributed under OpenAI’s Apache License 2.0. From them it takes the random-graph estimates for the model of [82 ] , the cone complexes, pictures and exclusion lemmas, and the criterion that a linear cochain bound gives thin triangles. Its own parts formalize Theorem B for arbitrary pattern-free graphs of degree at least 7, through the free case of Proposition 4.4 ; the parity and signed certificates; the design and certificates of § 9 for every odd prime; and inputs (a)–(d), with (b)–(d) in existence form, for the model of [83 ] and for the model of § 9 . For (b)–(d) it makes OpenAI’s formal estimates for [82 ] depend on the model, adding the colour data of Proposition 6.7 for the two-colour model. Appendix § 16 lists the statements of this paper with the declarations that prove them, and what is not formalized. The remaining point of trust is whether the definitions in the statement file mean what the paper means.
Independent checks of OpenAI’s estimates. The main theorems of [82 , 84 , 85 , 87 , 88 ] are proved in OpenAI’s Lean development [OAI-Lean], whose proof library contains no sorry, no native_decide and no added axioms. For the model of [82 ] it also contains inputs (a)–(c) of Table 2 and input (d) in the existence form used in Corollary 5.4 . In the probabilistic form used in Theorem A , input (d) is not formalized for either of OpenAI’s models, and input (c) is formalized only for the model of [82 ] . For [83 ] we have checked OpenAI’s proofs independently. We re-derived Lemma 3.3, the switching argument of Section 3.3, Proposition 3.4, Theorem 4.1 with Lemmas 4.2–4.4, and Lemma 5.3 of [83 ] step by step, and confirmed the model-specific constants (types, turn counts, squared-word decay) by exact computation. We found no gap. The proofs of § 6 and § 9 rerun these arguments, and those of [82 ] , for our models.
How this work was done. This paper is the work of its two authors together with AI models from more than one developer. The authors set the direction of the research throughout: they posed the questions, proposed the designs and recipes, set the verification, decided which lines to pursue and which to drop, judged and selected the results, and take full responsibility for every claim. The models did most of the exploration, derivation, computation and drafting. The disc argument behind Theorem A was found in a cross-reading of OpenAI’s release [81 ] against recent preprints; separately, a model given the authors’ brief describing that argument found its extension to the group of [83 ] . The direct-finiteness construction in odd characteristic (§ 9 ) started from the authors’ proposal to replace OpenAI’s Fano-plane template [83 §3.1] by its analogue over PG ( 2 , p ) \operatorname{PG}(2,p) PG ( 2 , p ) : complements of the lines of PG ( 2 , p ) \operatorname{PG}(2,p) PG ( 2 , p ) as extra parts, with the root carrying all of PG ( 2 , p ) \operatorname{PG}(2,p) PG ( 2 , p ) . The authors also supplied the signed form of OpenAI’s self-pairing certificate [83 Prop. 2.1] , with its exception at the root and the signed cancellation of Lemma 6.1, and the disc argument, whose accounting is that of [88 Thm. 3.1] . The models produced the exact solution of the colour-balance problem, the residue and Perron certificates, and the transfer of OpenAI’s estimates, first for p = 3 p = 3 p = 3 and then for every odd prime. N. Mghirbi built the Lean development with AI coding agents, under fixed rules: no sorry, no new axioms, no change to the statement file, and #print axioms for every main result.
Every load-bearing claim went through independent derivations, refutation-first reviews and exact computation. Before a result was kept, model instances that had not seen its proof, usually from a different developer, first tried to refute the statement and then audited the proof line by line, with exact computation wherever possible. For the arguments of § 3 to § 5 and § 11 , independent instances checked them against the texts of [82 , 83 , 84 ] , including attempts to construct counterexample diagrams, read OpenAI’s Lean development to determine exactly what it formalizes, and audited every reference. For § 6 and § 9 this meant replications by instances that had seen only the statement or the construction, separate refutation-first reviews of the probabilistic and of the algebraic and topological arguments, a separate review of the extension to every odd prime, and priority searches; § 10 had its own refutation-first review, with exact and random numerical tests. These checks found gaps in earlier drafts of this paper, not in the arguments of [82 , 83 ] , which the text now closes, among them the independence of the extras from the line (§ 6 ), the colour data in the stage counts (Propositions 6.7 and 7.9), two gaps in our combinatorial reformulation of the asphericity argument (closed curves in pictures, and tightening of a self-joined pair), and, for Theorem C, the choice of the outcome in an event that includes (P3), the roots fixed before the matchings, and the girth-scale conditions (16). The finite arithmetic of § 6 and § 9 was reproduced exactly on independent engines: for p = 3 p = 3 p = 3 on three independently written constructions of PG ( 2 , 81 ) \operatorname{PG}(2,81) PG ( 2 , 81 ) and an exact quotient computation, and, for the certificates of § 9 , for p = 3 , 5 , 7 , 11 , 13 p = 3,5,7,11,13 p = 3 , 5 , 7 , 11 , 13 , and for every odd p ≤ 199 p \le199 p ≤ 199 in the case of the residue and Perron certificates. The scripts of Appendix § 15 check constants, the interval lemma, the closure lemma, link girths, ring identities, the designs and the certificates. The Main Theorem, with the arguments and OpenAI estimates it uses, is also formally verified, as described above. For the other results the proofs are given in full, and the checks support them but do not replace them. The inputs [82 , 83 , 84 , 87 , 88 ] are AI-generated and unrefereed, and our earlier note [32 ] and the note [108 ] are AI-assisted, as each states.
Priority search. Searches on 14 October 2026 of arXiv (the math.GR, math.RA and math.OA submissions of 7–14 October, and newest-first keyword queries), Zenodo, ResearchGate, OSF, HAL, Preprints.org, Research Square, MathOverflow (questions since 1 September 2026), OpenAI’s catalogue [81 ] and the history of its repository (no commits after 12 October) found no prior statement of Theorems A , B and D or Corollaries 5.2 to 5.4 ; for Theorem D, the developability route through the link computation, for the glued group, is recorded in OpenAI’s reasoning trace [92 §§12, 17 and 21] . The survey arXiv:2610.17090, read in full, summarizes [82 , 84 ] without any statement about hyperbolicity; SSRN, INSPIRE-HEP, OpenAlex and Semantic Scholar were not searched systematically. Searches on 13 and 14 October 2026 found no earlier torsion-free group without direct finiteness over a field of odd characteristic, no earlier statement that any of the groups of [82 , 83 ] is hyperbolic, and no earlier non-trivial unit in the group algebra of a torsion-free hyperbolic group. They found Ivanov’s preprint [53 ] , dated 7 October and posted on 13 October 2026, which gives zero divisors in every odd characteristic without hyperbolicity and is credited throughout. A further search on 26 October 2026, of the arXiv submissions since 1 October on these conjectures, of Zenodo and of OpenAI’s repository, found the preprint [15 ] , discussed after Theorem C, and the arXiv version of [108 ] ; Ivanov’s preprint is unchanged, and OpenAI’s repository has no commits after 12 October.
Earlier work by the authors. Non-sofic hyperbolic groups were obtained independently in our earlier note [32 ] and by Sandhu and Thom [108 ] . In [32 ] the group and every input to the argument are OpenAI’s [87 ] ; our contribution there was a robust form of OpenAI’s rank argument and a Lean formalization of the headline statement. Sandhu and Thom’s note is based on an AI-generated construction obtained by H. Sandhu on 7 October 2026, which A. Thom worked through and wrote up [108 Acknowledgments] .
The interval lemma
This is [82 Lemma 4.3] , [83 Lemma 5.4] , rewritten for words.
Proof of Lemma 3.8 . A gap is the segment of a boundary circle between two cyclically consecutive occurrences; if there are E E E arcs, there are 2 E 2E 2 E occurrences and 2 E 2E 2 E gaps. Let N \mathcal{N} N be a regular neighbourhood of the disks and arcs, so that χ ( N ) = N 0 − E \chi(\mathcal{N})=N_0-E χ ( N ) = N 0 − E , and let Q Q Q range over the components of the closure of S ∖ N S \setminus\mathcal{N} S ∖ N . Every boundary circle of Q Q Q alternates between gaps and sides of arcs (each disk carries an occurrence); let l Q l_Q l Q be its number of arc sides, which equals its number of gaps. Then ∑ Q l Q = 2 E \sum_Q l_Q=2E ∑ Q l Q = 2 E and 2 = χ ( S ) = χ ( N ) + ∑ Q χ ( Q ) 2=\chi(S)=\chi(\mathcal{N})+\sum_Q\chi(Q) 2 = χ ( S ) = χ ( N ) + ∑ Q χ ( Q ) , hence
∑ Q ( l Q − 2 χ ( Q ) ) = 2 N 0 − 4. (17) \sum_Q (l_Q-2\chi(Q))=2N_0-4. \tag*{(17)} Q ∑ ( l Q − 2 χ ( Q )) = 2 N 0 − 4. (17)
Call a gap good if it lies on a region Q Q Q that is a disc with l Q = 2 l_Q=2 l Q = 2 whose two arc sides belong to different arcs. Across such a digon, two consecutive occurrences o 1 , o 2 o_1,o_2 o 1 , o 2 are joined to two consecutive occurrences o 2 ′ , o 1 ′ o'_2,o'_1 o 2 ′ , o 1 ′ in reversed order; the two gaps of the digon are both good, and we call each the partner of the other.
We bound the other gaps. A disc region with l Q = 1 l_Q = 1 l Q = 1 has a single gap between two consecutive occurrences joined by one arc, hence inverse adjacent letters; this happens at most at the break, so there are M ≤ 1 M \le1 M ≤ 1 such regions, each contributing − 1 -1 − 1 to (17) . A disc region with l Q = 2 l_Q = 2 l Q = 2 whose two sides belong to the same arc has both gaps on circles carrying a single occurrence; there are at most N 0 N_0 N 0 such gaps. Every region that is not a disc with l Q ≤ 2 l_Q \le2 l Q ≤ 2 has l Q − 2 χ ( Q ) > 0 l_Q - 2\chi(Q) > 0 l Q − 2 χ ( Q ) > 0 and l Q ≤ 3 ( l Q − 2 χ ( Q ) ) l_Q \le3(l_Q - 2\chi(Q)) l Q ≤ 3 ( l Q − 2 χ ( Q )) : for discs l Q ≥ 3 l_Q \ge3 l Q ≥ 3 gives l Q ≤ 3 ( l Q − 2 ) l_Q \le3(l_Q - 2) l Q ≤ 3 ( l Q − 2 ) , and otherwise χ ( Q ) ≤ 0 \chi(Q) \le0 χ ( Q ) ≤ 0 . By (17) , at most M + N 0 + 3 ( 2 N 0 − 4 + M ) < 7 N 0 M + N_0 + 3(2N_0 - 4 + M) < 7N_0 M + N 0 + 3 ( 2 N 0 − 4 + M ) < 7 N 0 gaps are not good.
Now cut every gap that is not good, one gap between any two consecutive pieces (one gap on each circle that is a single piece, and always the break), and the partner of every good gap cut so far. The cut set is invariant under the partner involution, has at most 7 N 0 + 2 N ′ ≤ 9 N ′ 7N_0 + 2N' \le9N' 7 N 0 + 2 N ′ ≤ 9 N ′ elements, and meets every circle. A run is a maximal sequence of consecutive occurrences with no cut gap between them; there are at most 9 N ′ 9N' 9 N ′ runs, and each lies in one piece. All gaps inside a run are good, so the arcs carry the run onto a sequence of consecutive occurrences in reversed order, and by the invariance of the cut set this sequence is again a run. A run is not carried onto itself: otherwise its middle occurrence would be joined to itself, or its two middle occurrences, which are consecutive and not separated by the break, would carry inverse letters. Hence the runs are matched in at most 9 2 N ′ ≤ 6 N ′ \frac{9}{2}N' \le6N' 2 9 N ′ ≤ 6 N ′ pairs.
The verification package
The repository accompanying this paper, https://github.com/Apsiape/kaplansky-conjectures-hyperbolic-groups , contains the following scripts in verify/, each with its recorded output, and verify/run_all.sh, which reruns them all. They check finite arithmetic and sample instances; they do not replace the proofs.
bicyclic_algebra_check.py: every identity of Lemma 2.1 , in the monoid ring of the bicyclic monoid over Z \mathbb{Z} Z and over F 2 \mathbb{F}_2 F 2 , which is universal for rings with a b = 1 ab = 1 ab = 1 ; and the computations behind Lemmas 2.2 and 2.3 .
constants_check.py: the inequalities (3) for the constants (2) on many pairs ( ε , D 0 ) (\varepsilon, D_0) ( ε , D 0 ) ; the bookkeeping of Proposition 4.4 ; the arithmetic of Lemmas 3.5 and 3.6 ; and the constant of Corollary 5.4 .
closure_lemma_check.py: the construction of Lemma 3.6 , run on random immersed paths in random 5- and 6-regular graphs.
interval_lemma_check.py: Lemma 3.8 on random planar pictures with bundles of parallel arcs, with and without a break.
cat0_links_check.py: the vertex links of Theorem 9.1 for ℓ = 3 , 5 , 7 \ell= 3,5,7 ℓ = 3 , 5 , 7 , their girths and the angle sums.
design_p3_explicit.py: builds F 81 F_{81} F 81 and PG ( 2 , 81 ) \operatorname{PG}(2,81) PG ( 2 , 81 ) and the exact type tables of Definition 6.2 for p = 3 p = 3 p = 3 at n = 12 ν 2 n = 12\nu^2 n = 12 ν 2 ; checks the letter frequencies, the cross-intersections { 1 , 4 , 82 , 85 } \{1,4,82,85\} { 1 , 4 , 82 , 85 } and the domination of the A A A -side turn frequencies by w w w ; and computes the spectral radius of the full 6648 × 6648 6648 \times6648 6648 × 6648 matrix M M M of Lemma 6.4 .
pg281_kernel.py and pg2_81_kernel_r2.py: two further, independently written constructions of PG ( 2 , 81 ) \operatorname{PG}(2,81) PG ( 2 , 81 ) and the turn kernel for p = 3 p = 3 p = 3 .
decay_quotient.py: the exact 3 × 3 3 \times3 3 × 3 equitable quotient of M M M , with OpenAI’s design as a control, and its spectral radius for p = 3 , 5 , 7 , 11 , 13 p = 3,5,7,11,13 p = 3 , 5 , 7 , 11 , 13 at the smallest admissible q q q .
exact_rows_r2.py: the row bounds in the proof of Lemma 6.4 , exactly, for p = 3 , 5 , 7 , 11 , 13 p = 3,5,7,11,13 p = 3 , 5 , 7 , 11 , 13 at the smallest admissible q q q , and the constants stated after that proof for p = 3 p = 3 p = 3 .
decay_constants_check.py: an alternative Perron certificate for the matrix M M M of Lemma 6.4 , with weight 2 e − 1 2e - 1 2 e − 1 in place of e + 2 e + 2 e + 2 , exactly, for every odd p ≤ 23 p \le23 p ≤ 23 and four powers q q q of each; and the conditions (8) for p = 3 p = 3 p = 3 .
signed_cancellation_test.py: random bipartite models of the design for p = 3 , 5 , 7 p = 3,5,7 p = 3 , 5 , 7 ; every component of the simultaneous-step graph has signed vertex count divisible by p p p , some have non-zero signed counts over Z \mathbb{Z} Z , and with a non-bipartite first graph the congruence fails.
certificates_odd_p.py: for p = 3 , 5 , 7 , 11 , 13 p = 3,5,7,11,13 p = 3 , 5 , 7 , 11 , 13 and q = p 5 q = p^5 q = p 5 , in exact arithmetic, the certificate of Lemma 7.4 , the block counts and the positivity of the uniform family of Proposition 7.6 , the two row bounds of Lemma 7.8 , and the constant for p = 3 p = 3 p = 3 at the end of § 9 .
certificates_odd_p_extended.py: Lemma 7.4 and the block counts for every odd p ≤ 43 p \le43 p ≤ 43 ; the residue bookkeeping of Lemma 7.5 at q = p 5 q = p^5 q = p 5 for every odd p ≤ 199 p \le199 p ≤ 199 ; and, for every odd p ≤ 199 p \le199 p ≤ 199 , the inequalities in the proof of Lemma 7.8 , the smallest turn weight and the congruences of Lemma 7.2 .
The Lean formalization
The formalization [Mgh26] is described in § 13 . Table 3 lists the statements of this paper that it proves, with the Lean declarations that prove them. Names are relative to the namespace Kaplansky. “Existence form” means that for all large sizes some outcome of the random model has the stated properties.
Table 3. Statements of this paper proved in the Lean formalization [Mgh26]. The consequences in Corollary 5.2 and Theorem C come from Algebra.mainTheoremConsequences_of_mainTheorem. The model of [83 ] is formalized with one of the type assignments that [83 §3.1] allows, along the admissible sizes n = v ( 4 v ( m + 1 ) + 1 ) n = v(4v(m + 1) + 1) n = v ( 4 v ( m + 1 ) + 1 ) .
Theorem B is formalized in the following form: the group is finitely presented, torsion-free and word-hyperbolic and has a finite two-dimensional classifying space, the roots are protected, and every non-empty cyclically reduced word w w w that is trivial in G G G bounds a reduced capped picture of cone length at most 16 13 ∣ w ∣ \frac{16}{13}|w| 13 16 ∣ w ∣ . Hyperbolicity is derived from this cone-length bound directly, so Lemma 4.2 (a), which bounds Area ( w ) \operatorname{Area}(w) Area ( w ) by the cone length, is not needed and not formalized. In (P1) the formal definition asks for degree at least 7 instead of 5, as OpenAI’s closure lemma does; every random graph used in this paper has larger degree.
Not formalized are the probability statement of Theorem A ; Lemma 2.4 , and with it the clauses “neither sofic nor surjunctive” of Corollary 5.2 and Theorem C; Connell’s theorem, used in Lemma 2.3 for the units of Corollaries 5.3 and 5.4 and Proposition 6.9; the explicit constants of Theorem A and Corollary 5.4 , and the quantifier over all large n n n in Corollary 5.4 ; § 6 apart from Lemma 6.1 ; Corollary 7.13 and Remark 7.14; § 10 ; and Theorem 9.1 and Theorem D. The units in the Main Theorem come from Lemmas 2.1 and 2.2 and are formalized.
Acknowledgements
We thank OpenAI for releasing their manuscripts and Lean development openly, which made this work possible, and Harjas Sandhu and Andreas Thom for making their note publicly available.