First-order sentences in random groups III

Olga Kharlampovich, Alexei Miasnikov, Rizos Sklinos · 2025

Read First-order sentences in random groups III by Olga Kharlampovich, Alexei Miasnikov, Rizos Sklinos (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-19740.txt.

Introduction

Olga Kharlampovich, Alexei Miasnikov, and Rizos Sklinos present a group theory paper, published in 2025, on logical statements in randomly built groups. A random group is assembled from generators plus a tangle of imposed relations, whose density can be tuned. Whenever that density stays below one half, the authors prove, a first order sentence is almost surely true in the random group exactly when it is true in a free group.

Catalog record

CREATOROlga Kharlampovich, Alexei Miasnikov, Rizos Sklinos
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-19740

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

First-order sentences in random groups III Olga Kharlampovich, Alexei Miasnikov, Rizos Sklinos Abstract We show that a first-order sentence is almost surely true in a random group of density d < 1 / 2 d<1/2 if and only if it is true in a non-abelian free group. 1 Introduction It was proved in [ 19 ] , [ 3 ] that every formula in the theory of a free group F is equivalent to a boolean combination of \exists\forall -formulas. In [ 3 ] it is also proved that the elementary theory of a free group is decidable (there is an algorithm given a sentence to decide whether this sentence belongs to Th(F) ). If the language of the free group F contains its generators as constants, then it was shown in [ 6 ] that every definable subset of F is defined by some boolean combination of formulas \exists x\forall y(\Sigma(a,p,x)=1\wedge\Psi(a,p,x,y)\neq 1), (1) where a are constants, x,y,p are tuples of variables. Let F_{n} be a free group with generators e_{1},\ldots,e_{n} , and \Gamma be a random group in Gromov’s density model for d<1/2 (for each \ell , \Gamma_{\ell} is a quotient of F_{n} over a random set of relations of density d ). We proved in [ 9 ] that a universal sentence is true in \Gamma (for density d<1/16 ) if and only if it is true in a non-abelian free group. In [ 10 ] we extended this result to boolean combinations of \forall\exists sentences. It was noticed in [ 12 ] that using the method of [ 9 ] one can prove the statement about universal sentences for d<1/2 , see the appendix at the end of this paper. This and [ 10 ] imply that a boolean combinations of \forall\exists sentences holds in a random group \Gamma at d<1/2 if and only if it holds in a non-abelian free group. In [ 13 ] it was proved that a first-order sentence of minimal rank is true in \Gamma if and only if it is true in a non-abelian free group. Here we will present the proof of the following results. Theorem 1 . A first-order formula is equivalent to a boolean combination of \exists\forall -formulas in F_{n} if and only if it is almost surely equivalent to this boolean combination in \Gamma . The idea of the proof is to follow the quantifier elimination procedure used in the proof of the Tarski conjecture - that the theories of non-abelian free groups of different ranks coincide - and to observe that at each step, the result concerning universal sentences guarantees that the procedure proceeds identically for F_{n} and \Gamma . This theorem and [ 10 ] imply Theorem 2 . A first-order sentence is almost surely true in a random group of density d<1/2 if and only if it is true in a non-abelian free group. We will use the machinery developed for answering Tarski’s question and in particular formal solutions, towers, closures of towers (see [ 7 ] , [ 15 ] ) and the process of validating a \forall\exists -sentence (see [ 17 ] , [ 3 ] ). The reader should be familiar with [ 10 , Section 2] where necessary definitions are given. 2 Preliminary results We say that a property P holds in a random group \Gamma if the probability that \Gamma_{\ell} has P approaches 1, as \ell approaches infinity. An ascending sequence of groups in density d is a sequence of groups \{\Gamma_{\ell_{n}}\} such that \ell_{n}\rightarrow\infty and \Gamma_{\ell_{n}} is a random group with relations of length \ell_{n} and density d . Let \{h_{\ell_{n}}:F_{m}\to\Gamma_{\ell_{n}}\} be a sequence of homomorphisms over an ascending sequence of groups at d<1/2 . Assume that the stretching factors \mu_{n}=\min_{f_{n}\in\Gamma_{\ell_{n}}}\max_{1\leq u\leq m}d_{\Gamma_{\ell_{n}}}(1,\tau_{f_{n}}\circ h_{ln}(x_{u})), satisfy that \mu_{n}\geq\ell_{n}^{2} for all n , where X_{n} is the Cayley graph of \Gamma_{\ell_{n}} with respect to the generating set a . Then, the sequence \tau_{f_{n}}\circ h_{\ell_{n}}, where \tau_{f_{n}} is the corresponding inner automorphism of \Gamma_{n} (see [ 12 , Section 9] ), subconverges to an isometric non-trivial action of F_{m} on a pointed real tree (Y,y_{0}) . Theorem 3 . 1. Solution set of a system of equations over F_{n} and \Gamma is encoded in the same M-R diagram. 2. Every system of equations U(x)=1 over \Gamma is equivalent to the same finite subsystem V(x)=1 as for F_{n} . Namely, every solution of V(x)=1 in \Gamma is a solution of U(x)=1 with overwelming probability (w.o.p). 3. For every convergent sequence of homomorphisms h_{\ell}:G=\langle x|V(x)\rangle\rightarrow\Gamma_{\ell} the limit of this sequence is a limit group (over F_{n} ). 4. Let K be a solid limit group over H\leq K . Let N be the bound on the number of strictly solid homomorphisms K\rightarrow F_{n} . Then N is the bound on the number of strictly solid homomorphisms K\rightarrow\Gamma_{\ell} w.o.p. Moreover, for large \ell , for any fixed homomorphism H\rightarrow\Gamma_{\ell} the pre-images of representatives of distinct strictly solid families K\rightarrow\Gamma_{\ell} w.o.p.are strictly solid homomorphisms from distinct families. 5. A complete system of reducing (=flexible) quotients of a solid limit group modulo a subgroup is the same for F_{n} and \Gamma . Proof. 1. The solution set of a system of equations over a free group F_{n} is encoded by a M-R diagram. Since for a given system of equations the solution over \Gamma is almost surely the same as over F_{n} (we say that it can be lifted into F_{n} ), it is encoded by the same M-R diagram. 2. Let U(x)=1 be an infinite system equations and V(x) a finite subsystem equivalent to it in F_{n} . Every solution \bar{b} of V(x) in \Gamma almost surely has a pre-image in F_{n} that is a solution of V(x) and, therefore, a solution of U(x) . Therefore \bar{b} is a solution of U(x) in \Gamma . 3. We can order the sets of all finite systems of equations W_{1}\subset W_{2}\subset\ldots . Let p_{\ell} be the probability that \Gamma_{\ell} every solution of every system in W_{\ell} is a free solution (can be lifted to F_{n} ). Then p_{\ell}\rightarrow 1 as \ell\rightarrow\infty . A consequence of this is our statement. 4. The property to have at most N strictly solid families for a solid limit group can be described by a boolean combination of \forall\exists -sentences. Now the statement follows from the main result of [ 10 ] . One can also give a direct proof. Assume, by contradiction, that there exist more than N pairwise distinct \Gamma -strictly solid families. Let h_{j} be strictly solid representatives for these families. For each j , we lift the homomorphism h_{j} into a homomorphism \tilde{h}_{j}:K\rightarrow F_{k}. Then, since the homomorphisms h_{j} represent pairwise distinct \Gamma -strictly solid families, the homomorphisms \tilde{h}_{j} must represent pairwise distinct strictly solid families. This gives a contradiction. 5. This follows from the fact that homomorphisms factoring through the reducing quotients can be described by a disjunction of systems of equations. ∎ We will call strictly solid (and rigid) solutions algebraic solutions (similarly to the fields terminology). If the obtained limit of \{h_{\ell_{n}}:F_{m}\to\Gamma_{\ell_{n}}\} (that is, by the theorem above, is a limit group), is freely indecomposable, then the homomorphisms h_{\ell_{n}} can be eventually shortened by

Read the complete text