Introduction
The theory of random groups, originating in the work of Gromov [4 ] , provides a framework for studying the properties of a “typical” finitely presented group. In Gromov’s density model, one chooses a random set of relators of a prescribed length at a fixed density and studies the resulting group as this length tends to infinity. In this paper, we introduce an analogous density model for random semigroups and study which properties of random groups persist in this broader setting.
Let us define the model of our random semigroups. Fix n ≥ 2 n \ge2 n ≥ 2 , and consider the free semigroup F n = ⟨ x 1 , … , x n ⟩ \mathcal{F}_n = \langle x_1,\ldots,x_n\rangle F n = ⟨ x 1 , … , x n ⟩ . For each l ≥ 1 l \ge1 l ≥ 1 , we denote by B n , l B_{n,l} B n , l the set of words in F n \mathcal{F}_n F n of length at most l l l . This set can be thought of as the ball of radius l l l in the (undirected) Cayley graph of F n \mathcal{F}_n F n , and has size ∣ B n , l ∣ = n + ⋯ + n l = n l ( n n − 1 + o l ( 1 ) ) |B_{n,l}| = n + \cdots+ n^l = n^l\left(\frac{n}{n-1} + o_l(1)\right) ∣ B n , l ∣ = n + ⋯ + n l = n l ( n − 1 n + o l ( 1 ) ) .
2020 Mathematics Subject Classification. Primary 20M05, 60B15; Secondary 20P05.
Key words and phrases. Random semigroups, random groups, Gromov’s density model.
Definition 1.1. Fix positive integers n ≥ 2 n \ge2 n ≥ 2 and l ≥ 1 l \ge1 l ≥ 1 . Given a density parameter δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , we pick a uniformly random set of ⌊ n 2 δ l ⌋ \lfloor n^{2\delta l}\rfloor ⌊ n 2 δ l ⌋ unordered pairs { u i , v i } ⊆ B n , l \{u_i,v_i\} \subseteq B_{n,l} { u i , v i } ⊆ B n , l , i ∈ I : = { 1 , … , ⌊ n 2 δ l ⌋ } i \in I := \{1,\ldots,\lfloor n^{2\delta l}\rfloor\} i ∈ I := { 1 , … , ⌊ n 2 δ l ⌋} and consider the quotient semigroup M n , δ , l : = F n / ⟨ u i = v i ∣ i ∈ I ⟩ M_{n,\delta,l}:=F_n/\langle u_i=v_i\mid i\in I\rangle M n , δ , l := F n / ⟨ u i = v i ∣ i ∈ I ⟩ .
We think of M n , δ , l M_{n,\delta,l} M n , δ , l as a generalized random variable Ω → { Semigroups } \Omega\to\{\text{Semigroups}\} Ω → { Semigroups } where the probability space Ω \Omega Ω is the collection of all sets of ⌊ n 2 δ l ⌋ \lfloor n^{2\delta l}\rfloor ⌊ n 2 δ l ⌋ unordered pairs of elements from B n , l B_{n,l} B n , l .
We are interested in properties of the random semigroup which hold when the number of generators and density are fixed, while the length l l l tends to infinity.
Definition 1.2. Let P \mathcal{P} P be a semigroup property. We say that a random semigroup with n n n generators and density δ \delta δ satisfies P \mathcal{P} P with overwhelming probability if
lim l → ∞ Pr ( M n , δ , l satisfies P ) = 1. \lim_{l\to\infty}\Pr(M_{n,\delta,l}\text{ satisfies }\mathcal{P})=1. l → ∞ lim Pr ( M n , δ , l satisfies P ) = 1. In Gromov’s density model, density δ = 1 2 \delta=\frac{1}{2} δ = 2 1 marks a phase transition: with overwhelming probability, the random group is either trivial or isomorphic to Z / 2 Z \mathbb{Z}/2\mathbb{Z} Z /2 Z when δ > 1 2 \delta>\frac{1}{2} δ > 2 1 , and non-elementary hyperbolic when δ < 1 2 \delta<\frac{1}{2} δ < 2 1 [4 , 10 ] . Further model-theoretic evidence for the largeness of random groups when δ < 1 2 \delta<\frac{1}{2} δ < 2 1 is given in [6 ] . If one samples freely reduced relators, the group is also trivial or isomorphic to Z / 2 Z \mathbb{Z}/2\mathbb{Z} Z /2 Z with overwhelming probability at the critical density δ = 1 2 \delta=\frac{1}{2} δ = 2 1 [2 ] .
In this work we study the same phase transition for random semigroups. We show in Theorem 2.3 that for density δ > 1 2 \delta>\frac{1}{2} δ > 2 1 , the random semigroup M n , δ , l M_{n,\delta,l} M n , δ , l is trivial with overwhelming probability. Here we do not need to add an exceptional case as Z / 2 Z \mathbb{Z}/2\mathbb{Z} Z /2 Z , which is the case since our relators do not have fixed length.
When δ < 1 2 \delta<\frac{1}{2} δ < 2 1 , we show that M n , δ , l M_{n,\delta,l} M n , δ , l is typically large by showing that the following properties hold with overwhelming probability:
M n , δ , l M_{n,\delta,l} M n , δ , l contains nonabelian free semigroups (Proposition 3.2 ), hence has exponential growth.
For any field K \mathbb{K} K , the semigroup algebra K [ M n , δ , l ] \mathbb{K}[M_{n,\delta,l}] K [ M n , δ , l ] is a filtered Golod-Shafarevich algebra (Proposition 3.5). It then follows that M n , δ , l M_{n,\delta,l} M n , δ , l has a periodic quotient of bounded index with exponential growth (Corollary 3.6 ).
We study small cancellation properties of M n , δ , l M_{n,\delta,l} M n , δ , l , which are defined in an analogous way to the standard small cancellation properties of groups. We show that if δ < 1 2 m \delta<\frac{1}{2m} δ < 2 m 1 , then M n , δ , l M_{n,\delta,l} M n , δ , l satisfies C ( m ) C(m) C ( m ) with overwhelming probability (Proposition 4.3 ).
This allows us to prove that when δ < 1 6 \delta< \frac{1}{6} δ < 6 1 , the semigroup M n , δ , l M_{n,\delta,l} M n , δ , l is residually finite (Corollary 4.6 ).
For any given N ≥ 1 N \ge1 N ≥ 1 , the semigroup M n , δ , l M_{n,\delta,l} M n , δ , l has a finite homomorphic image of size N N N (Proposition 4.7 ).
M n , δ , l M_{n,\delta,l} M n , δ , l is neither left amenable nor right amenable (Corollary 5.9 ). In fact, we show that there is a (random) group G n , δ , l G_{n,\delta,l} G n , δ , l and a homomorphism π : M n , δ , l → G n , δ , l \pi: M_{n,\delta,l} \to G_{n,\delta,l} π : M n , δ , l → G n , δ , l such that π ( M n , δ , l ) \pi(M_{n,\delta,l}) π ( M n , δ , l ) generates G n , δ , l G_{n,\delta,l} G n , δ , l (as a group), and G G G is non-elementary hyperbolic (Theorem 5.7 ).
Finally, we study the critical case δ = 1 2 \delta= \frac{1}{2} δ = 2 1 . We show that for n ≥ 3 n \ge3 n ≥ 3 , the semigroup M n , 1 / 2 , l M_{n,1/2,l} M n , 1/2 , l is finite with overwhelming probability (Theorem 6.2 ). However, in contrast to the case of random groups, here we get nontrivial limiting behaviour: M n , 1 / 2 , l M_{n,1/2,l} M n , 1/2 , l is trivial with positive limiting probability (Corollary 6.5 ), but for every N ≥ 1 N \ge1 N ≥ 1 there is a positive limiting probability that M n , 1 / 2 , l M_{n,1/2,l} M n , 1/2 , l has size at least N N N (Proposition 6.6 ).
Structure of the paper
We begin with some preliminary results of the random semigroup and its random presentation in § 2 , covering the large density case. The small density case is divided into several parts. We cover largeness properties in Section 3, small cancellation in § 4 , and hyperbolicity and non-amenability in § 5 . The final section (§ 6 ) is devoted to study the critical case.
Notations
We write F n = ⟨ x 1 , … , x n ⟩ \mathcal{F}_n = \langle x_1,\ldots,x_n\rangle F n = ⟨ x 1 , … , x n ⟩ for the n n n -generated free semigroup. We refer to elements of F n \mathcal{F}_n F n as words. For a word w ∈ F n w \in\mathcal{F}_n w ∈ F n , we write ∣ w ∣ |w| ∣ w ∣ for its length with respect to the standard generators of F n \mathcal{F}_n F n , which is the homomorphism ∣ ⋅ ∣ : F n → N ∪ { 0 } |\cdot| : \mathcal{F}_n \to\mathbb{N} \cup\{0\} ∣ ⋅ ∣ : F n → N ∪ { 0 } given by ∣ x i ∣ = 1 |x_i| = 1 ∣ x i ∣ = 1 for all 1 ≤ i ≤ n 1 \le i \le n 1 ≤ i ≤ n .
Acknowledgements
BG is supported by the Mary P. Dolciani Halloran Foundation, the Simons Foundation, and the PSC-CUNY Research Award Program. GB is supported by the ERC consolidator grant CUT-OFF (101123174). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency.
Preliminary results
For a set X X X , we denote by ( X 2 ) \binom{X}{2} ( 2 X ) the set of (unordered) pairs of elements from X X X . Given a set of relations R ⊆ ( F n 2 ) \mathcal{R} \subseteq\binom{\mathcal{F}_n}{2} R ⊆ ( 2 F n ) , we obtain a semigroup presentation ⟨ x 1 , … , x n ∣ R ⟩ \langle x_1,\ldots,x_n \mid\mathcal{R}\rangle ⟨ x 1 , … , x n ∣ R ⟩ . Given a relation u = v u = v u = v , we call u , v u,v u , v ‘relation words’.
Let B n , l B_{n,l} B n , l be the set of words in the n n n -generated free semigroup, whose length is at most l l l . Notice that
∣ B n , l ∣ = ∑ i = 1 l n i = n l + 1 − n n − 1 = ( n n − 1 + o l ( 1 ) ) ⋅ n l |B_{n,l}|=\sum_{i=1}^{l}n^i=\frac{n^{l+1}-n}{n-1}=\left(\frac{n}{n-1}+o_l(1)\right)\cdot n^l ∣ B n , l ∣ = i = 1 ∑ l n i = n − 1 n l + 1 − n = ( n − 1 n + o l ( 1 ) ) ⋅ n l
and
p n , l : = ∣ ( B n , l 2 ) ∣ = ( n 2 2 ( n − 1 ) 2 + o l ( 1 ) ) ⋅ n 2 l p_{n,l}:=\left|\binom{B_{n,l}}{2}\right|=\left(\frac{n^2}{2(n-1)^2}+o_l(1)\right)\cdot n^{2l} p n , l := ( 2 B n , l ) = ( 2 ( n − 1 ) 2 n 2 + o l ( 1 ) ) ⋅ n 2 l
We recall the following fact.
Fact 2.1. Let π : F n ↠ ⟨ x 1 , … , x n ∣ R ⟩ \pi:F_n\twoheadrightarrow\langle x_1,\ldots,x_n\mid\mathcal{R}\rangle π : F n ↠ ⟨ x 1 , … , x n ∣ R ⟩ be the natural projection. For two words w , w ′ ∈ ⟨ x 1 , … , x n ⟩ w,w'\in\langle x_1,\ldots,x_n\rangle w , w ′ ∈ ⟨ x 1 , … , x n ⟩ we have π ( w ) = π ( w ′ ) \pi(w)=\pi(w') π ( w ) = π ( w ′ ) if and only if there is a sequence of words w = w 0 , w 1 , … , w m = w ′ w=w_0,w_1,\ldots,w_m=w' w = w 0 , w 1 , … , w m = w ′ in the free semigroup such that each w i + 1 w_{i+1} w i + 1 is obtained from w i w_i w i by replacing a subword u u u of it by v v v , where u = v u=v u = v is among the relation set R \mathcal{R} R . In particular, π − 1 ( π ( w ) ) = { w } \pi^{-1}(\pi(w))=\{w\} π − 1 ( π ( w )) = { w } if and only if w w w contains no relation word as a subword.
Proposition 2.2. Suppose that 0 < δ < 1 2 0<\delta<\frac{1}{2} 0 < δ < 2 1 .
Let θ > 2 δ \theta>2\delta θ > 2 δ . Let R n , δ , l \mathcal{R}_{n,\delta,l} R n , δ , l denote a random set of ⌊ n 2 δ l ⌋ \lfloor n^{2\delta l}\rfloor ⌊ n 2 δ l ⌋ defining relations. Then, with overwhelming probability, all relation words are of length at least ( 1 − θ ) l (1-\theta)l ( 1 − θ ) l .
Let 0 < ε < 1 − 2 δ 0<\varepsilon<1-2\delta 0 < ε < 1 − 2 δ . For each 1 ≤ i ≤ l 1\leq i\leq l 1 ≤ i ≤ l , let a i a_i a i denote the number of relation words of length i i i (counted with multiplicity1 ^1 1 ). Then
Pr ( a i > n i − ε l ) ≤ 2 n ( 2 δ − 1 + ε ) l \Pr(a_i>n^{i-\varepsilon l})\leq2n^{(2\delta-1+\varepsilon)l} Pr ( a i > n i − εl ) ≤ 2 n ( 2 δ − 1 + ε ) l and
Pr ( ∃ 1 ≤ i ≤ l : a i > n i − ε l ) ≤ 2 l ⋅ n ( 2 δ − 1 + ε ) l . \Pr(\exists1\leq i\leq l:a_i>n^{i-\varepsilon l})\leq2l\cdot n^{(2\delta-1+\varepsilon)l}. Pr ( ∃1 ≤ i ≤ l : a i > n i − εl ) ≤ 2 l ⋅ n ( 2 δ − 1 + ε ) l .
Proof. (1) Recall that p n , l = ( n + ⋯ + n l 2 ) p_{n,l}=\binom{n+\cdots+n^l}{2} p n , l = ( 2 n + ⋯ + n l ) is the number of unordered pairs of elements from B n , l B_{n,l} B n , l . Denote by N : = ⌊ n 2 δ l ⌋ = ∣ R n , δ , l ∣ N:=\lfloor n^{2\delta l}\rfloor=|\mathcal{R}_{n,\delta,l}| N := ⌊ n 2 δ l ⌋ = ∣ R n , δ , l ∣ . Let k = ⌈ ( 1 − θ ) l ⌉ k=\lceil(1-\theta)l\rceil k = ⌈( 1 − θ ) l ⌉ . The number of unordered pairs of words in B n , l B_{n,l} B n , l both of which are of length at least k k k is
q n , k , l : = ( n k + n k + 1 + ⋯ + n l 2 ) . (1) q_{n,k,l}:=\binom{n^k+n^{k+1}+\cdots+n^l}{2}. \tag*{(1)} q n , k , l := ( 2 n k + n k + 1 + ⋯ + n l ) . (1)
We omit the subscripts of p , q p,q p , q for brevity. Denote by A A A the event that all words in R n , δ , l \mathcal{R}_{n,\delta,l} R n , δ , l are of length at least k k k . Then
Pr ( A ) = ( q N ) ( p N ) = q ( q − 1 ) ⋯ ( q − N + 1 ) p ( p − 1 ) ⋯ ( p − N + 1 ) ≥ ( q − N p − N ) N = ( 1 − p − q p − N ) N . (2) \Pr(A)=\frac{\binom{q}{N}}{\binom{p}{N}}=\frac{q(q-1)\cdots(q-N+1)}{p(p-1)\cdots(p-N+1)}
\geq\left(\frac{q-N}{p-N}\right)^N=\left(1-\frac{p-q}{p-N}\right)^N. \tag*{(2)} Pr ( A ) = ( N p ) ( N q ) = p ( p − 1 ) ⋯ ( p − N + 1 ) q ( q − 1 ) ⋯ ( q − N + 1 ) ≥ ( p − N q − N ) N = ( 1 − p − N p − q ) N . (2)
Now
p − q = ( n + ⋯ + n l 2 ) − ( n k + ⋯ + n l 2 ) = ( n l + 1 − n n − 1 2 ) − ( n l + 1 − n k n − 1 2 ) ≤ ( n l + 1 − n ) 2 2 ( n − 1 ) 2 − ( n l + 1 − n k − n + 1 ) 2 2 ( n − 1 ) 2 ≤ 1 2 ( n − 1 ) 2 ( ( n l + 1 − n ) 2 − ( n l + 1 − 2 n k ) 2 ) ≤ 1 2 ( n − 1 ) 2 ⋅ 4 n l + k + 1 = 2 n ( n − 1 ) 2 ⋅ n l + k . \begin{aligned}
p-q&=\binom{n+\cdots+n^l}{2}-\binom{n^k+\cdots+n^l}{2}\\
&=\binom{\frac{n^{l+1}-n}{n-1}}{2}-\binom{\frac{n^{l+1}-n^k}{n-1}}{2}\\
&\leq\frac{(n^{l+1}-n)^2}{2(n-1)^2}-\frac{(n^{l+1}-n^k-n+1)^2}{2(n-1)^2}\\
&\leq\frac{1}{2(n-1)^2}\left((n^{l+1}-n)^2-(n^{l+1}-2n^k)^2\right)\\
&\leq\frac{1}{2(n-1)^2}\cdot4n^{l+k+1}=\frac{2n}{(n-1)^2}\cdot n^{l+k}.
\end{aligned} p − q = ( 2 n + ⋯ + n l ) − ( 2 n k + ⋯ + n l ) = ( 2 n − 1 n l + 1 − n ) − ( 2 n − 1 n l + 1 − n k ) ≤ 2 ( n − 1 ) 2 ( n l + 1 − n ) 2 − 2 ( n − 1 ) 2 ( n l + 1 − n k − n + 1 ) 2 ≤ 2 ( n − 1 ) 2 1 ( ( n l + 1 − n ) 2 − ( n l + 1 − 2 n k ) 2 ) ≤ 2 ( n − 1 ) 2 1 ⋅ 4 n l + k + 1 = ( n − 1 ) 2 2 n ⋅ n l + k .
Recall that, for some c > 0 c>0 c > 0 we have p ≥ c ⋅ n 2 l p\geq c\cdot n^{2l} p ≥ c ⋅ n 2 l , so p − N ≥ c ⋅ n 2 l − n 2 δ l p-N\geq c\cdot n^{2l}-n^{2\delta l} p − N ≥ c ⋅ n 2 l − n 2 δ l and, since δ < 1 \delta<1 δ < 1 , we can write p − N ≥ d ⋅ n 2 l p-N\geq d\cdot n^{2l} p − N ≥ d ⋅ n 2 l for some d > 0 d>0 d > 0 . By the above computation, p − q ≤ e ⋅ n ( 2 − θ ) l p-q\leq e\cdot n^{(2-\theta)l} p − q ≤ e ⋅ n ( 2 − θ ) l for some e > 0 e>0 e > 0 . It follows from (2.1) that (for C = e d C=\frac{e}{d} C = d e )
Pr ( A ) ≥ ( 1 − e ⋅ n ( 2 − θ ) l d ⋅ n 2 l ) N ≥ ( 1 − C ⋅ n − θ l ) n 2 δ l ≥ 1 − C ⋅ n ( 2 δ − θ ) l ⟶ l → ∞ 1 \Pr(A)\geq\left(1-\frac{e\cdot n^{(2-\theta)l}}{d\cdot n^{2l}}\right)^N
\geq(1-C\cdot n^{-\theta l})^{n^{2\delta l}}
\geq1-C\cdot n^{(2\delta-\theta)l}\underset{l\to\infty}{\longrightarrow}1 Pr ( A ) ≥ ( 1 − d ⋅ n 2 l e ⋅ n ( 2 − θ ) l ) N ≥ ( 1 − C ⋅ n − θ l ) n 2 δ l ≥ 1 − C ⋅ n ( 2 δ − θ ) l l → ∞ ⟶ 1
since θ > 2 δ \theta>2\delta θ > 2 δ .
(2) Writing a i a_i a i as a sum of indicator variables,
E [ a i ] = E [ ∑ ∣ w ∣ = i ∑ v ∈ B n , l ∖ { w } I { w , v } ∈ R ] = n i ⋅ ( ∣ B n , l ∣ − 1 ) ⋅ N ( ∣ B n , l ∣ 2 ) = 2 N n i n + ⋯ + n l ≤ 2 n 2 δ l + i − l . \begin{aligned}
\mathbb{E}[a_i]
&=\mathbb{E}\left[\sum_{\lvert w\rvert=i}\sum_{v\in B_{n,l}\setminus\{w\}}\mathbb{I}_{\{w,v\}\in\mathcal{R}}\right]\\
&=n^i\cdot(\lvert B_{n,l}\rvert-1)\cdot\frac{N}{\binom{\lvert B_{n,l}\rvert}{2}}\\
&=\frac{2Nn^i}{n+\cdots+n^l}\\
&\leq2n^{2\delta l+i-l}.
\end{aligned} E [ a i ] = E ∣ w ∣ = i ∑ v ∈ B n , l ∖ { w } ∑ I { w , v } ∈ R = n i ⋅ (∣ B n , l ∣ − 1 ) ⋅ ( 2 ∣ B n , l ∣ ) N = n + ⋯ + n l 2 N n i ≤ 2 n 2 δ l + i − l .
By Markov’s inequality,
Pr ( a i > n i − ε l ) ≤ E [ a i ] n i − ε l ≤ 2 n ( 2 δ − 1 ) l + i n i − ε l = 2 n ( 2 δ − 1 + ε ) l , \begin{aligned}
\Pr(a_i > n^{i-\varepsilon l}) \le\frac{\mathbb{E}[a_i]}{n^{i-\varepsilon l}} \\
&\le\frac{2n^{(2\delta-1)l+i}}{n^{i-\varepsilon l}} = 2n^{(2\delta-1+\varepsilon)l},
\end{aligned} Pr ( a i > n i − εl ) ≤ n i − εl E [ a i ] ≤ n i − εl 2 n ( 2 δ − 1 ) l + i = 2 n ( 2 δ − 1 + ε ) l ,
as claimed. By the union bound,
Pr ( ∃ 1 ≤ i ≤ l : a i > n i − ε l ) ≤ 2 l ⋅ n ( 2 δ − 1 + ε ) l . \Pr(\exists1 \le i \le l : a_i > n^{i-\varepsilon l}) \le2l \cdot n^{(2\delta-1+\varepsilon)l}. Pr ( ∃1 ≤ i ≤ l : a i > n i − εl ) ≤ 2 l ⋅ n ( 2 δ − 1 + ε ) l .
We next show that for density δ > 1 2 \delta> \frac{1}{2} δ > 2 1 , a random semigroup is trivial with overwhelming probability. This echoes the situation for Gromov random groups, which are either trivial or cyclic of order 2 with overwhelming probability when δ > 1 2 \delta> \frac{1}{2} δ > 2 1 .
Theorem 2.3. Let n ≥ 2 n \ge2 n ≥ 2 . For every δ > 1 2 \delta> \frac{1}{2} δ > 2 1 , M n , δ , l M_{n,\delta,l} M n , δ , l is trivial with overwhelming probability.
Proof. Consider the random graph G \mathcal{G} G with vertex set B n , l B_{n,l} B n , l , where two vertices u u u and v v v are joined by an edge if the relation u = v u=v u = v appears among the set R n , δ , l \mathcal{R}_{n,\delta,l} R n , δ , l of defining relations of M n , δ , l M_{n,\delta,l} M n , δ , l . Then G \mathcal{G} G is an Erdős–Rényi graph with k : = ∣ B n , l ∣ k := |B_{n,l}| k := ∣ B n , l ∣ vertices and N : = ⌊ n 2 δ l ⌋ N := \lfloor n^{2\delta l}\rfloor N := ⌊ n 2 δ l ⌋ edges.
It is well known that an Erdős–Rényi graph G ( k , N ) \mathcal{G}(k,N) G ( k , N ) is connected with probability tending to 1 as k → ∞ k \to\infty k → ∞ whenever N ≫ k log k N \gg k \log k N ≫ k log k . In our setting, k ≍ n l k \asymp n^l k ≍ n l , so this condition holds for all sufficiently large l l l since δ > 1 2 \delta> \frac{1}{2} δ > 2 1 .
If G \mathcal{G} G is connected, then the elements of B n , l B_{n,l} B n , l are all congruent modulo the relations R n , δ , l \mathcal{R}_{n,\delta,l} R n , δ , l . In particular, with overwhelming probability, we have x 1 = ⋯ = x n x_1=\cdots=x_n x 1 = ⋯ = x n and x 1 2 = x 1 x_1^2=x_1 x 1 2 = x 1 in M n , δ , l M_{n,\delta,l} M n , δ , l . Thus, M n , δ , l M_{n,\delta,l} M n , δ , l is trivial with overwhelming probability.
Random semigroups with density δ < 1 2 \delta< \frac{1}{2} δ < 2 1 are large
Free subsemigroups
Lemma 3.1. Let M = ⟨ x 1 , … , x n ∣ u 1 = v 1 , … , u m = v m ⟩ M=\langle x_1,\ldots,x_n \mid u_1=v_1,\ldots,u_m=v_m\rangle M = ⟨ x 1 , … , x n ∣ u 1 = v 1 , … , u m = v m ⟩ be a finitely presented semigroup and let π : ⟨ x 1 , … , x n ⟩ ↠ M \pi:\langle x_1,\ldots,x_n\rangle\twoheadrightarrow M π : ⟨ x 1 , … , x n ⟩ ↠ M be the natural projection. Let w 1 , w 2 ∈ ⟨ x 1 … , x n ⟩ w_1,w_2 \in\langle x_1\ldots,x_n\rangle w 1 , w 2 ∈ ⟨ x 1 … , x n ⟩ be distinct words in the free semigroup such that
∣ w 1 ∣ = ∣ w 2 ∣ ≥ ∣ u 1 ∣ , … , ∣ u m ∣ , ∣ v 1 ∣ , … , ∣ v m ∣ . |w_1|=|w_2| \ge|u_1|,\ldots,|u_m|,|v_1|,\ldots,|v_m|. ∣ w 1 ∣ = ∣ w 2 ∣ ≥ ∣ u 1 ∣ , … , ∣ u m ∣ , ∣ v 1 ∣ , … , ∣ v m ∣. If none of u 1 , … , u m , v 1 , … , v m u_1,\ldots,u_m,v_1,\ldots,v_m u 1 , … , u m , v 1 , … , v m is a subword of any of w 1 2 , w 1 w 2 , w 2 w 1 , w 2 2 w_1^2,w_1w_2,w_2w_1,w_2^2 w 1 2 , w 1 w 2 , w 2 w 1 , w 2 2 , then π ( w 1 ) , π ( w 2 ) \pi(w_1),\pi(w_2) π ( w 1 ) , π ( w 2 ) generate a free subsemigroup of M M M .
Proof. Suppose that π ( w i 1 ⋯ w i k ) = π ( w j 1 ⋯ w j k ′ ) \pi(w_{i_1}\cdots w_{i_k})=\pi(w_{j_1}\cdots w_{j_{k'}}) π ( w i 1 ⋯ w i k ) = π ( w j 1 ⋯ w j k ′ ) where i l , j l ′ ∈ { 1 , 2 } i_l,j_{l'}\in\{1,2\} i l , j l ′ ∈ { 1 , 2 } for all 1 ≤ l ≤ k 1\leq l\leq k 1 ≤ l ≤ k and 1 ≤ l ′ ≤ k ′ 1\leq l'\leq k' 1 ≤ l ′ ≤ k ′ . Notice that w i 1 ⋯ w i k w_{i_1}\cdots w_{i_k} w i 1 ⋯ w i k and w j 1 ⋯ w j k ′ w_{j_1}\cdots w_{j_{k'}} w j 1 ⋯ w j k ′ do not contain any relation word as a subword; indeed, since ∣ w 1 ∣ = ∣ w 2 ∣ ≥ ∣ u 1 ∣ , … , ∣ u m ∣ , ∣ v 1 ∣ , … , ∣ v m ∣ |w_1|=|w_2|\geq|u_1|,\ldots,|u_m|,|v_1|,\ldots,|v_m| ∣ w 1 ∣ = ∣ w 2 ∣ ≥ ∣ u 1 ∣ , … , ∣ u m ∣ , ∣ v 1 ∣ , … , ∣ v m ∣ , any occurrence of a relation word would have to fall within w i t w i t + 1 w_{i_t}w_{i_{t+1}} w i t w i t + 1 or w j t w j t + 1 w_{j_t}w_{j_{t+1}} w j t w j t + 1 , which is impossible by assumption. Hence, by Fact 2.1 ,
{ w i 1 ⋯ w i k } = π − 1 ( π ( w i 1 ⋯ w i k ) ) = π − 1 ( π ( w j 1 ⋯ w j k ′ ) ) = { w j 1 ⋯ w j k ′ } . \{w_{i_1}\cdots w_{i_k}\}=\pi^{-1}\bigl(\pi(w_{i_1}\cdots w_{i_k})\bigr)
=\pi^{-1}\bigl(\pi(w_{j_1}\cdots w_{j_{k'}})\bigr)=\{w_{j_1}\cdots w_{j_{k'}}\}. { w i 1 ⋯ w i k } = π − 1 ( π ( w i 1 ⋯ w i k ) ) = π − 1 ( π ( w j 1 ⋯ w j k ′ ) ) = { w j 1 ⋯ w j k ′ } .
and since ∣ w 1 ∣ = ∣ w 2 ∣ |w_1|=|w_2| ∣ w 1 ∣ = ∣ w 2 ∣ and w 1 ≠ w 2 w_1\ne w_2 w 1 = w 2 , we obtain that k ′ = k k'=k k ′ = k and i 1 = j 1 , … , i k = j k i_1=j_1,\ldots,i_k=j_k i 1 = j 1 , … , i k = j k . It follows that ⟨ π ( w 1 ) , π ( w 2 ) ⟩ \langle\pi(w_1),\pi(w_2)\rangle ⟨ π ( w 1 ) , π ( w 2 )⟩ is a free subsemigroup of M M M .
:::
Proposition 3.2. Let n ≥ 2 n\geq2 n ≥ 2 . For every δ < 1 2 \delta<\frac{1}{2} δ < 2 1 , M n , δ , l M_{n,\delta,l} M n , δ , l contains a nonabelian free subsemigroup with overwhelming probability.
Proof. Let N = ⌊ n 2 δ l ⌋ N=\lfloor n^{2\delta l}\rfloor N = ⌊ n 2 δ l ⌋ and let M n , δ , l = ⟨ x 1 , … , x n ∣ R ⟩ M_{n,\delta,l}=\langle x_1,\ldots,x_n\mid\mathcal{R}\rangle M n , δ , l = ⟨ x 1 , … , x n ∣ R ⟩ where R \mathcal{R} R is u 1 = v 1 , … , u N = v N u_1=v_1,\ldots,u_N=v_N u 1 = v 1 , … , u N = v N .
Denote X = { x 1 , … , x n } X=\{x_1,\ldots,x_n\} X = { x 1 , … , x n } and choose a pair of words w 1 , w 2 ∈ X l w_1,w_2\in X^l w 1 , w 2 ∈ X l uniformly at random (with overwhelming probability, they are distinct). Let W 1 = w 1 2 W_1=w_1^2 W 1 = w 1 2 , W 2 = w 1 w 2 W_2=w_1w_2 W 2 = w 1 w 2 , W 3 = w 2 w 1 W_3=w_2w_1 W 3 = w 2 w 1 , and W 4 = w 2 2 W_4=w_2^2 W 4 = w 2 2 . For each one of them, the probability that it contains a given word P P P of length s s s (s ≤ l s\leq l s ≤ l ) as subword is at most 2 l ⋅ n − s 2l\cdot n^{-s} 2 l ⋅ n − s , since there are (at most) 2 l 2l 2 l possible starting positions, and the probability that a random sequence of s s s letters coincides with P P P is n − s n^{-s} n − s . Notice that since ∣ w 1 ∣ = ∣ w 2 ∣ = l |w_1|=|w_2|=l ∣ w 1 ∣ = ∣ w 2 ∣ = l and s ≤ l s\leq l s ≤ l , the induced distribution on each length-s s s window in each one of W 1 , … , W 4 W_1,\ldots,W_4 W 1 , … , W 4 is uniform (each position of w 1 , w 2 w_1,w_2 w 1 , w 2 appears only once within that window). Denote by E \mathcal{E} E the event that
∃ 1 ≤ i ≤ 4 : W i contains a relation word as a subword. \exists\,1\leq i\leq4:\ W_i\text{ contains a relation word as a subword.} ∃ 1 ≤ i ≤ 4 : W i contains a relation word as a subword. We have
Pr ( E ∣ a 1 , … , a l ) ≤ 4 ⋅ ∑ i = 1 l a i ⋅ 2 l ⋅ n − i = 8 l ∑ i = 1 l a i n − i . (3) \Pr(\mathcal{E}\mid a_1,\ldots,a_l)\leq4\cdot\sum_{i=1}^{l}a_i\cdot2l\cdot n^{-i}=8l\sum_{i=1}^{l}a_i n^{-i}. \tag*{(3)} Pr ( E ∣ a 1 , … , a l ) ≤ 4 ⋅ i = 1 ∑ l a i ⋅ 2 l ⋅ n − i = 8 l i = 1 ∑ l a i n − i . (3) where a i a_i a i denotes the number of length-i i i relation words in R \mathcal{R} R . Fix an arbitrary 0 < ε < 1 − 2 δ 0<\varepsilon<1-2\delta 0 < ε < 1 − 2 δ . By Proposition 2.2 ,
Pr ( ∃ 1 ≤ i ≤ l : a i > n i − ε l ) ≤ 2 l ⋅ n ( 2 δ − 1 + ε ) l \Pr(\exists\,1\leq i\leq l:\ a_i>n^{i-\varepsilon l})\leq2l\cdot n^{(2\delta-1+\varepsilon)l} Pr ( ∃ 1 ≤ i ≤ l : a i > n i − εl ) ≤ 2 l ⋅ n ( 2 δ − 1 + ε ) l
and so by (3.1),
Pr ( E ) ≤ Pr ( ∃ 1 ≤ i ≤ l : a i > n i − ε l ) + Pr ( E ∩ ∀ 1 ≤ i ≤ l : a i ≤ n i − ε l ) \Pr(\mathcal{E}) \leq\Pr(\exists1 \leq i \leq l : a_i > n^{i-\varepsilon l}) + \Pr(\mathcal{E} \cap\forall1 \leq i \leq l : a_i \leq n^{i-\varepsilon l}) Pr ( E ) ≤ Pr ( ∃1 ≤ i ≤ l : a i > n i − εl ) + Pr ( E ∩ ∀1 ≤ i ≤ l : a i ≤ n i − εl )
≤ 2 l ⋅ n ( 2 δ − 1 + ε ) l + 8 l ∑ i = 1 l n i − ε l ⋅ n − i = 2 l ⋅ n ( 2 δ − 1 + ε ) l + 8 l 2 ⋅ n − ε l → l → ∞ 0 \begin{aligned}
\leq2l \cdot n^{(2\delta-1+\varepsilon)l} + 8l \sum_{i=1}^{l} n^{i-\varepsilon l} \cdot n^{-i} \\
&= 2l \cdot n^{(2\delta-1+\varepsilon)l} + 8l^2 \cdot n^{-\varepsilon l} \xrightarrow[l\to\infty]{} 0
\end{aligned} ≤ 2 l ⋅ n ( 2 δ − 1 + ε ) l + 8 l i = 1 ∑ l n i − εl ⋅ n − i = 2 l ⋅ n ( 2 δ − 1 + ε ) l + 8 l 2 ⋅ n − εl l → ∞ 0
since ε > 0 \varepsilon> 0 ε > 0 and 2 δ − 1 + ε < 0 2\delta- 1 + \varepsilon< 0 2 δ − 1 + ε < 0 . Therefore, with overwhelming probability, there exist w 1 , w 2 w_1,w_2 w 1 , w 2 of length l l l such that none of w 1 2 , w 1 w 2 , w 2 w 1 , w 2 2 w_1^2,w_1w_2,w_2w_1,w_2^2 w 1 2 , w 1 w 2 , w 2 w 1 , w 2 2 contains a relation word as a subword, and by Lemma 3.1, the images of w 1 , w 2 w_1,w_2 w 1 , w 2 in M n , δ , l M_{n,\delta,l} M n , δ , l generate a free subsemigroup. □
Corollary 3.3. Let n ≥ 2 n \geq2 n ≥ 2 . For every δ < 1 2 \delta< \frac{1}{2} δ < 2 1 , M n , δ , l M_{n,\delta,l} M n , δ , l has exponential growth with overwhelming probability.
Random semigroups with δ < 1 2 \delta< \frac{1}{2} δ < 2 1 are Golod–Shafarevich.
Definition 3.4. Let K \mathbb{K} K be a field and let A = K ⟨ x 1 , … , x n ⟩ / ⟨ R ⟩ A = \mathbb{K}\langle x_1,\ldots,x_n\rangle/\langle\mathcal{R}\rangle A = K ⟨ x 1 , … , x n ⟩ / ⟨ R ⟩ be a finitely generated K \mathbb{K} K -algebra. Given f ∈ K ⟨ x 1 , … , x n ⟩ f \in\mathbb{K}\langle x_1,\ldots,x_n\rangle f ∈ K ⟨ x 1 , … , x n ⟩ with zero constant term, let ν ( f ) \nu(f) ν ( f ) denote the minimum length of a monomial on which f f f is supported. Let r i : = { f ∈ R ∣ ν ( f ) = i } r_i := \{f \in\mathcal{R} \mid\nu(f) = i\} r i := { f ∈ R ∣ ν ( f ) = i } . We say that A A A is a (filtered) Golod–Shafarevich algebra if, for some 0 < τ < 1 0 < \tau< 1 0 < τ < 1 , the following is convergent and has a negative value
1 − n τ + ∑ i = 0 ∞ r i τ i . 1 - n\tau+ \sum_{i=0}^{\infty} r_i\tau^i. 1 − n τ + i = 0 ∑ ∞ r i τ i .
Recall that Golod-Shafarevich algebras are of exponential growth and enjoy many additional ‘largeness’ properties (see an example in Corollary 3.6 below).
Proposition 3.5. Fix n ≥ 2 n \geq2 n ≥ 2 and 0 < δ < 1 2 0 < \delta< \frac{1}{2} 0 < δ < 2 1 . Then K [ M n , δ , l ] \mathbb{K}[M_{n,\delta,l}] K [ M n , δ , l ] is a filtered Golod-Shafarevich algebra with overwhelming probability.
Proof. Let M n , δ , l = ⟨ x 1 , … , x n ∣ R ⟩ M_{n,\delta,l} = \langle x_1,\ldots,x_n \mid\mathcal{R}\rangle M n , δ , l = ⟨ x 1 , … , x n ∣ R ⟩ where R ⊆ B n , l \mathcal{R} \subseteq B_{n,l} R ⊆ B n , l is a random subset of size N = ⌊ n 2 δ l ⌋ N = \lfloor n^{2\delta l}\rfloor N = ⌊ n 2 δ l ⌋ . The semigroup algebra K [ M n , δ , l ] \mathbb{K}[M_{n,\delta,l}] K [ M n , δ , l ] has a presentation K ⟨ x 1 , … , x n ⟩ / ⟨ u − v ∣ { u , v } ∈ R ⟩ \mathbb{K}\langle x_1,\ldots,x_n\rangle/\langle u-v \mid\{u,v\} \in\mathcal{R}\rangle K ⟨ x 1 , … , x n ⟩ / ⟨ u − v ∣ { u , v } ∈ R ⟩ . Given a relation u = v u=v u = v in R \mathcal{R} R , notice that ν ( u − v ) = min { ∣ u ∣ , ∣ v ∣ } \nu(u-v)=\min\{|u|,|v|\} ν ( u − v ) = min { ∣ u ∣ , ∣ v ∣ } . Let r i r_i r i be the number of relations u = v u=v u = v in R \mathcal{R} R for which min { ∣ u ∣ , ∣ v ∣ } = i \min\{|u|,|v|\}=i min { ∣ u ∣ , ∣ v ∣ } = i . Recall that in Proposition 2.2 , we defined a i a_i a i to be the number of relation words of length i i i (counted with multiplicity). Hence, r i ≤ a i r_i \leq a_i r i ≤ a i . Fix any 0 < ε < 1 − 2 δ 0 < \varepsilon< 1-2\delta 0 < ε < 1 − 2 δ . By Proposition 2.2 ,
Pr ( ∃ 1 ≤ i ≤ l : a i > n i − ε l ) ≤ 2 l ⋅ n ( 2 δ − 1 + ε ) l \Pr(\exists1 \leq i \leq l : a_i > n^{i-\varepsilon l}) \leq2l \cdot n^{(2\delta-1+\varepsilon)l} Pr ( ∃1 ≤ i ≤ l : a i > n i − εl ) ≤ 2 l ⋅ n ( 2 δ − 1 + ε ) l
and so with overwhelming probability we may assume that r i ≤ a i ≤ n i − ε l r_i \leq a_i \leq n^{i-\varepsilon l} r i ≤ a i ≤ n i − εl for all 1 ≤ i ≤ l 1 \leq i \leq l 1 ≤ i ≤ l . In this case, fix some 0 < α < ε 0 < \alpha< \varepsilon 0 < α < ε and take τ = n α − 1 \tau= n^{\alpha-1} τ = n α − 1 and
1 − n τ + ∑ i = 0 ∞ r i τ i ≤ 1 − n τ + ∑ i = 1 l n i − ε l τ i = 1 − n α + n − ε l ∑ i = 1 l n α i = 1 − n α + n − ε l ⋅ n α ( l + 1 ) − n α n α − 1 \begin{aligned}
1-n\tau+\sum_{i=0}^{\infty}r_i\tau^i \leq1-n\tau+\sum_{i=1}^{l}n^{i-\varepsilon l}\tau^i \\
&=1-n^\alpha+n^{-\varepsilon l}\sum_{i=1}^{l}n^{\alpha i} \\
&=1-n^\alpha+n^{-\varepsilon l}\cdot\frac{n^{\alpha(l+1)}-n^\alpha}{n^\alpha-1}
\end{aligned} 1 − n τ + i = 0 ∑ ∞ r i τ i ≤ 1 − n τ + i = 1 ∑ l n i − εl τ i = 1 − n α + n − εl i = 1 ∑ l n α i = 1 − n α + n − εl ⋅ n α − 1 n α ( l + 1 ) − n α
≤ 1 − n α + n ( α − ε ) l ⋅ n α n α − 1 \leq1-n^\alpha+n^{(\alpha-\varepsilon)l}\cdot\frac{n^\alpha}{n^\alpha-1} ≤ 1 − n α + n ( α − ε ) l ⋅ n α − 1 n α
which, when l ≫ 1 l \gg1 l ≫ 1 , is negative, as α − ε < 0 \alpha-\varepsilon<0 α − ε < 0 . It follows that K [ M n , δ , l ] \mathbb{K}[M_{n,\delta,l}] K [ M n , δ , l ] is Golod-Shafarevich with overwhelming probability.
A sample evidence of the largeness of M n , δ , l M_{n,\delta,l} M n , δ , l for δ < 1 2 \delta< \frac{1}{2} δ < 2 1 implied by Proposition 3.5 is the following (probably well-known) Burnside-type result (in the spirit of Wilson; see also Ershov):
Corollary 3.6. For every n ≥ 2 n \geq2 n ≥ 2 and δ < 1 2 \delta< \frac{1}{2} δ < 2 1 , the semigroup M n , δ , l M_{n,\delta,l} M n , δ , l has a periodic quotient of bounded index with exponential growth with overwhelming probability.
Proof. Let r i r_i r i denote the number of defining relations f f f of K [ M n , δ , l ] \mathbb{K}[M_{n,\delta,l}] K [ M n , δ , l ] with ν ( f ) = i \nu(f)=i ν ( f ) = i . By Proposition 3.5, there is some 0 < τ < 1 0<\tau<1 0 < τ < 1 such that h : = 1 − n τ + ∑ i = 0 ∞ r i τ i < 0 h:=1-n\tau+\sum_{i=0}^{\infty}r_i\tau^i<0 h := 1 − n τ + ∑ i = 0 ∞ r i τ i < 0 . Take k ≫ 1 k\gg1 k ≫ 1 such that
∑ i = 1 ∞ n i τ k i = n k 1 − n τ k < − h . \sum_{i=1}^{\infty}n^i\tau^{ki}=\frac{n^k}{1-n\tau^k}<-h. i = 1 ∑ ∞ n i τ k i = 1 − n τ k n k < − h .
Then, adding to K [ M n , δ , l ] \mathbb{K}[M_{n,\delta,l}] K [ M n , δ , l ] the relations of the form f w : = w k + 1 − w k f_w:=w^{k+1}-w^k f w := w k + 1 − w k for all w w w word in x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n , we add n i n^i n i relations f w f_w f w with ν ( f w ) = k i \nu(f_w)=ki ν ( f w ) = k i , and
1 − n τ + ∑ i = 0 ∞ r i τ i + ∑ i = 1 ∞ n i τ k i < 0 , 1-n\tau+\sum_{i=0}^{\infty}r_i\tau^i+\sum_{i=1}^{\infty}n^i\tau^{ki}<0, 1 − n τ + i = 0 ∑ ∞ r i τ i + i = 1 ∑ ∞ n i τ k i < 0 ,
hence K [ M n , δ , l ] / ⟨ w k + 1 − w k : w ∈ M n , δ , l ⟩ \mathbb{K}[M_{n,\delta,l}]/\langle w^{k+1}-w^k:w\in M_{n,\delta,l}\rangle K [ M n , δ , l ] / ⟨ w k + 1 − w k : w ∈ M n , δ , l ⟩ is again a (filtered) Golod-Shafarevich algebra.
Small cancellation and Finite quotients
Small Cancellation Properties
Let ⟨ x 1 , … , x n ⟩ \langle x_1,\ldots,x_n\rangle ⟨ x 1 , … , x n ⟩ be a free semigroup and let R \mathcal{R} R be a set of relations.
Definition 4.1. A nonempty word p p p is called a piece if it either appears as a subword in two distinct relation words, or within the same relation word in distinct positions.
Definition 4.2. Let m ∈ N m \in\mathbb{N} m ∈ N . We say that ⟨ x 1 , … , x n ∣ R ⟩ \langle x_1,\ldots,x_n \mid\mathcal{R}\rangle ⟨ x 1 , … , x n ∣ R ⟩ satisfies condition C ( m ) C(m) C ( m ) if no relation word can be expressed as a product of fewer than m m m pieces.
Every set of relations satisfies C ( 1 ) C(1) C ( 1 ) . A set of relations satisfies C ( 2 ) C(2) C ( 2 ) if and only if no relation word is a proper subword of any other relation word. For a thorough account of conditions C ( m ) C(m) C ( m ) , see [11 ] . Kambites [5 ] proved that in the few relation model, a random semigroup satisfies C ( m ) C(m) C ( m ) with overwhelming probability, for all m ∈ N m \in\mathbb{N} m ∈ N . Thinking of the few relation model as a ‘density zero’ model, we prove the following optimal behavior:
Proposition 4.3. Let n ≥ 2 n \ge2 n ≥ 2 and m ≥ 2 m \ge2 m ≥ 2 . For every 0 < δ < 1 2 m 0 < \delta< \frac{1}{2m} 0 < δ < 2 m 1 , M n , δ , l M_{n,\delta,l} M n , δ , l satisfies C ( m ) C(m) C ( m ) with overwhelming probability.
Proof. Let N = ⌊ n 2 δ l ⌋ N = \lfloor n^{2\delta l}\rfloor N = ⌊ n 2 δ l ⌋ and let M n , δ , l = ⟨ x 1 , … , x n ∣ R ⟩ M_{n,\delta,l} = \langle x_1,\ldots,x_n \mid\mathcal{R}\rangle M n , δ , l = ⟨ x 1 , … , x n ∣ R ⟩ where R \mathcal{R} R is u 1 = u − 1 , … , u N = u − N u_1 = u_{-1},\ldots,u_N = u_{-N} u 1 = u − 1 , … , u N = u − N .
Recall M n , δ , l M_{n,\delta,l} M n , δ , l satisfies C ( m ) C(m) C ( m ) if, for every 1 ≤ q ≤ m − 1 1 \le q \le m-1 1 ≤ q ≤ m − 1 and every partition of a relation word u = α 1 ⋯ α q u = \alpha_1 \cdots\alpha_q u = α 1 ⋯ α q into q q q non-empty subwords, at least one of the α k \alpha_k α k is not a piece. If, for some q < m − 1 q < m-1 q < m − 1 , u = α 1 ⋯ α q u = \alpha_1 \cdots\alpha_q u = α 1 ⋯ α q is a product of q q q pieces, this can be expressed as a product of m − 1 m-1 m − 1 pieces since subwords of pieces are also pieces2 ^2 2 . Thus, it suffices to only consider partitions into exactly m − 1 m-1 m − 1 non-empty subwords.
In particular, C ( m ) C(m) C ( m ) fails when there exists an m m m -tuple of relation words u i 0 , … , u i m − 1 u_{i_0},\ldots,u_{i_{m-1}} u i 0 , … , u i m − 1 , a partition u i 0 = α 1 ⋯ α m − 1 u_{i_0} = \alpha_1 \cdots\alpha_{m-1} u i 0 = α 1 ⋯ α m − 1 , and positions p 1 , … , p m − 1 p_1,\ldots,p_{m-1} p 1 , … , p m − 1 such that every k k k , α k \alpha_k α k occurs in u i k u_{i_k} u i k at position p k p_k p k , excluding the natural occurrence of α k \alpha_k α k in u i k u_{i_k} u i k when i k = i 0 i_k = i_0 i k = i 0 . Here, we use the convention that a subword α \alpha α occurs in a word w w w at position p p p if w = β α γ w = \beta\alpha\gamma w = β α γ and ∣ β ∣ = p |\beta| = p ∣ β ∣ = p .
Let S S S be the set of all ordered lists of the form
( i 0 , … , i m − 1 , α 1 , … , α m − 1 , p 1 , … , p m − 1 ) (i_0,\ldots,i_{m-1},\alpha_1,\ldots,\alpha_{m-1},p_1,\ldots,p_{m-1}) ( i 0 , … , i m − 1 , α 1 , … , α m − 1 , p 1 , … , p m − 1 )
such that i k ∈ { ± 1 , … , ± N } i_k \in\{\pm1,\ldots,\pm N\} i k ∈ { ± 1 , … , ± N } for 0 ≤ k ≤ m − 1 0 \le k \le m-1 0 ≤ k ≤ m − 1 ; u i 0 = α 1 ⋯ α m − 1 u_{i_0} = \alpha_1 \cdots\alpha_{m-1} u i 0 = α 1 ⋯ α m − 1 is a partition into m − 1 m-1 m − 1 non-empty subwords; and 0 ≤ p k ≤ ∣ u i k ∣ − ∣ α k ∣ 0 \le p_k \le|u_{i_k}| - |\alpha_k| 0 ≤ p k ≤ ∣ u i k ∣ − ∣ α k ∣ for every 1 ≤ k ≤ m − 1 1 \le k \le m-1 1 ≤ k ≤ m − 1 . We exclude from S S S any lists such that there exists 1 ≤ k ≤ m − 1 1 \le k \le m-1 1 ≤ k ≤ m − 1 for which i k = i 0 i_k = i_0 i k = i 0 and p k = ∣ α 1 ⋯ α k − 1 ∣ p_k = |\alpha_1 \cdots\alpha_{k-1}| p k = ∣ α 1 ⋯ α k − 1 ∣ (i.e., the p k p_k p k is the naturally occurring position of α k \alpha_k α k in u i 0 u_{i_0} u i 0 ).
For s ∈ S s \in S s ∈ S , let I s I_s I s denote the indicator of the event that, for every 1 ≤ k ≤ m − 1 1 \le k \le m-1 1 ≤ k ≤ m − 1 , α k \alpha_k α k occurs in u i k u_{i_k} u i k in position p k p_k p k . Let
X = ∑ s ∈ S I s . X = \sum_{s \in S} \mathbb{I}_s. X = s ∈ S ∑ I s .
Then, X ≥ 1 X \ge1 X ≥ 1 implies that M n , δ , l M_{n,\delta,l} M n , δ , l fails C ( m ) C(m) C ( m ) . By Markov’s inequality, Pr ( X ≥ 1 ) ≤ E ( X ) \Pr(X \ge1) \le\mathbb{E}(X) Pr ( X ≥ 1 ) ≤ E ( X ) . Thus, it suffices to show
E ( X ) = ∑ s ∈ S E ( I s ) → l → ∞ 0. \mathbb{E}(X) = \sum_{s \in S} \mathbb{E}(\mathbb{I}_s) \xrightarrow[l \to\infty]{} 0. E ( X ) = s ∈ S ∑ E ( I s ) l → ∞ 0.
Fix s = ( i 0 , … , i m − 1 , α 1 , … , α m − 1 , p 1 , … , p m − 1 ) ∈ S s=(i_0,\ldots,i_{m-1},\alpha_1,\ldots,\alpha_{m-1},p_1,\ldots,p_{m-1})\in S s = ( i 0 , … , i m − 1 , α 1 , … , α m − 1 , p 1 , … , p m − 1 ) ∈ S . To calculate E ( I s ) \mathbb{E}(\mathbb{I}_s) E ( I s ) , we consider the number of generator constraints imposed by the subwords α k \alpha_k α k sequentially. For each k k k , suppose that each α j \alpha_j α j occurs in u i j u_{i_j} u i j at position p j p_j p j for every j < k j<k j < k , and consider the number of new generator constraints imposed by the prescription of α k \alpha_k α k in u i k u_{i_k} u i k at position p k p_k p k . A position of α k \alpha_k α k does not impose a new generator constraint if it overlaps with a position of some α j \alpha_j α j for j < k j<k j < k or if it overlaps with the natural occurrence of α k \alpha_k α k in u i 0 u_{i_0} u i 0 . An overlapping position (of α k \alpha_k α k with some α j \alpha_j α j , j ≤ k j\le k j ≤ k ) is called compatible if the prescribed generators match. For each k k k , denote the number of overlapping positions by r k r_k r k . Then, sequentially, α k \alpha_k α k imposes ∣ α k ∣ − r k |\alpha_k|-r_k ∣ α k ∣ − r k new generator constraints.
Note that the new generator constraints from α 1 , … , α m − 1 \alpha_1,\ldots,\alpha_{m-1} α 1 , … , α m − 1 are independent. Thus, letting R ( s ) = ∑ k = 1 m − 1 r k R(s)=\sum_{k=1}^{m-1}r_k R ( s ) = ∑ k = 1 m − 1 r k ,
E ( I s ) = ∏ k = 1 m − 1 n − ( ∣ α k ∣ − r k ) = n − ∣ u i 0 ∣ + R ( s ) \mathbb{E}(\mathbb{I}_s)=\prod_{k=1}^{m-1}n^{-(|\alpha_k|-r_k)}=n^{-|u_{i_0}|+R(s)} E ( I s ) = k = 1 ∏ m − 1 n − ( ∣ α k ∣ − r k ) = n − ∣ u i 0 ∣ + R ( s )
provided that all overlapping constraints are compatible and 0 0 0 otherwise.
If R ( s ) = 0 R(s)=0 R ( s ) = 0 , then E ( I s ) = n − ∣ u i 0 ∣ \mathbb{E}(\mathbb{I}_s)=n^{-|u_{i_0}|} E ( I s ) = n − ∣ u i 0 ∣ . This, in particular occurs if i 0 , i 1 , … , i m − 1 i_0,i_1,\ldots,i_{m-1} i 0 , i 1 , … , i m − 1 are distinct. On the other hand, if R ( s ) > 0 R(s)>0 R ( s ) > 0 , then I s \mathbb{I}_s I s occurs with positive probability only if the partition u i 0 = α 1 ⋯ α m − 1 u_{i_0}=\alpha_1\cdots\alpha_{m-1} u i 0 = α 1 ⋯ α m − 1 satisfies certain compatibility conditions (i.e., there must be sufficient overlap between or within the subwords α k \alpha_k α k ).
We will use the following:
Fix 2 δ ( m − 1 ) < ε < 1 − 2 δ 2\delta(m-1)<\varepsilon<1-2\delta 2 δ ( m − 1 ) < ε < 1 − 2 δ and let a L a_L a L denote the number of length-L L L relation words in R \mathcal{R} R . By 2.2, with overwhelming probability a L ≤ n L − ε l : 1 ≤ L ≤ l a_L\le n^{L-\varepsilon l}:1\le L\le l a L ≤ n L − εl : 1 ≤ L ≤ l .
Fix 2 δ < θ < ε − 2 δ ( m − 2 ) 2\delta<\theta<\varepsilon-2\delta(m-2) 2 δ < θ < ε − 2 δ ( m − 2 ) . We claim that with overwhelming probability no relation word can satisfy more than θ l \theta l θ l overlapping constraints.
To see this, fix a relation word u i u_i u i and an overlap pattern for a partition u i = α 1 ⋯ α m − 1 u_i=\alpha_1\cdots\alpha_{m-1} u i = α 1 ⋯ α m − 1 in which there are at least θ l \theta l θ l overlapping constraints. Here, the overlap pattern specifies identifications between positions within or between the subwords α 1 , … , α m − 1 \alpha_1,\ldots,\alpha_{m-1} α 1 , … , α m − 1 . For a fixed such pattern with r ≥ θ l r\ge\theta l r ≥ θ l constraints, the probability that u i 0 u_{i_0} u i 0 can satisfy all overlapping constraints is n − r ≤ n − θ l n^{-r}\le n^{-\theta l} n − r ≤ n − θ l .
For a fixed relation word u i u_i u i , the number of possible partitions and overlap patterns is polynomial in l l l . Thus by the union bound, the probability that there exists a relation word satisfying an overlap pattern with more than θ l \theta l θ l constraints is at most
poly ( l ) N n − θ l = poly ( l ) n ( 2 δ − θ ) l → l → ∞ 0 \operatorname{poly}(l)Nn^{-\theta l}=\operatorname{poly}(l)n^{(2\delta-\theta)l}\xrightarrow[l\to\infty]{}0 poly ( l ) N n − θ l = poly ( l ) n ( 2 δ − θ ) l l → ∞ 0
as θ > 2 δ \theta>2\delta θ > 2 δ .
Thus, we will calculate E ( X ) \mathbb{E}(X) E ( X ) under the assumptions that the conditions in (1) and (2) hold. In particular, under these assumptions,
E ( I s ) ≤ { n − ∣ u i 0 ∣ if i 0 , … , i m − 1 pairwise distinct , n − ∣ u i 0 ∣ + θ l otherwise . \mathbb{E}(\mathbb{I}_s)\le
\begin{cases}
n^{-|u_{i_0}|} & \text{if }i_0,\ldots,i_{m-1}\text{ pairwise distinct},\\
n^{-|u_{i_0}|+\theta l} & \text{otherwise}.
\end{cases} E ( I s ) ≤ { n − ∣ u i 0 ∣ n − ∣ u i 0 ∣ + θ l if i 0 , … , i m − 1 pairwise distinct , otherwise .
Let 1 ≤ L ≤ l 1\le L\le l 1 ≤ L ≤ l . We now count the number of lists s ∈ S s\in S s ∈ S such that ∣ u i 0 ∣ = L |u_{i_0}|=L ∣ u i 0 ∣ = L . There are a L a_L a L choices for i 0 i_0 i 0 . For the remaining m − 1 m-1 m − 1 indices i 1 , … , i m − 1 i_1,\ldots,i_{m-1} i 1 , … , i m − 1 , there are at most
( 2 N − 1 ) ( 2 N − 2 ) ⋯ ( 2 N − m + 1 ) ≤ ( 2 N ) m − 1 (2N-1)(2N-2)\cdots(2N-m+1)\le(2N)^{m-1} ( 2 N − 1 ) ( 2 N − 2 ) ⋯ ( 2 N − m + 1 ) ≤ ( 2 N ) m − 1
choices such that i 0 , … , i m − 1 i_0,\ldots,i_{m-1} i 0 , … , i m − 1 are distinct; there are at most
( m 2 ) ( 2 N ) m − 2 \binom{m}{2}(2N)^{m-2} ( 2 m ) ( 2 N ) m − 2
choices where at least one index in i 0 , … , i m − 1 i_0,\ldots,i_{m-1} i 0 , … , i m − 1 is repeated. Note that these are upper bounds as we exclude lists for which there is at least one value 1 ≤ k ≤ m − 1 1\le k\le m-1 1 ≤ k ≤ m − 1 such that i k = i 0 i_k=i_0 i k = i 0 and p k = ∣ α 1 ⋯ α k − 1 ∣ p_k=|\alpha_1\cdots\alpha_{k-1}| p k = ∣ α 1 ⋯ α k − 1 ∣ .
For a given u i 0 u_{i_0} u i 0 , there are O ( l m − 2 ) O(l^{m-2}) O ( l m − 2 ) choices for a partition u i 0 = α 1 ⋯ α m − 1 u_{i_0}=\alpha_1\cdots\alpha_{m-1} u i 0 = α 1 ⋯ α m − 1 , and O ( l m − 1 ) O(l^{m-1}) O ( l m − 1 ) choices for the positions p 1 , … , p m − 1 p_1,\ldots,p_{m-1} p 1 , … , p m − 1 . Thus,
E ( X ) = ∑ s ∈ S Pr ( I s = 1 ) = ∑ s ∈ S distinct m -tuple Pr ( I s = 1 ) + ∑ s ∈ S non-distinct m -tuple Pr ( I s = 1 ) ≤ ∑ L = 1 l a L poly ( l ) ( 2 N ) m − 1 n − L + ∑ L = 1 l a L poly ( l ) ( 2 N ) m − 2 n − L + θ l \begin{aligned}
\mathbb{E}(X)=\sum_{s\in S}\Pr(\mathbb{I}_s=1) \\
&=\sum_{\substack{s\in S\\\text{distinct }m\text{-tuple}}}\Pr(\mathbb{I}_s=1)+\sum_{\substack{s\in S\\\text{non-distinct }m\text{-tuple}}}\Pr(\mathbb{I}_s=1) \\
&\le\sum_{L=1}^{l}a_L\operatorname{poly}(l)(2N)^{m-1}n^{-L}+\sum_{L=1}^{l}a_L\operatorname{poly}(l)(2N)^{m-2}n^{-L+\theta l}
\end{aligned} E ( X ) = s ∈ S ∑ Pr ( I s = 1 ) = s ∈ S distinct m -tuple ∑ Pr ( I s = 1 ) + s ∈ S non-distinct m -tuple ∑ Pr ( I s = 1 ) ≤ L = 1 ∑ l a L poly ( l ) ( 2 N ) m − 1 n − L + L = 1 ∑ l a L poly ( l ) ( 2 N ) m − 2 n − L + θ l
(*) ≤ ∑ L = 1 l a L poly ( l ) n 2 δ ( m − 1 ) l n − L + ∑ L = 1 l a L poly ( l ) n 2 δ ( m − 2 ) l n − L + θ l . \text{(*)}\quad\le\sum_{L=1}^{l}a_L\operatorname{poly}(l)n^{2\delta(m-1)l}n^{-L}+\sum_{L=1}^{l}a_L\operatorname{poly}(l)n^{2\delta(m-2)l}n^{-L+\theta l}. (*) ≤ L = 1 ∑ l a L poly ( l ) n 2 δ ( m − 1 ) l n − L + L = 1 ∑ l a L poly ( l ) n 2 δ ( m − 2 ) l n − L + θ l .
Under assumption (1), for all 1 ≤ L ≤ l 1 \le L \le l 1 ≤ L ≤ l , a L ≤ n L − ε l a_L \le n^{L-\varepsilon l} a L ≤ n L − εl , so
( ∗ ) ≤ ∑ L = 1 l poly ( l ) n 2 δ ( m − 1 ) l − L + L − ε l + ∑ L = 1 l poly ( l ) n 2 δ ( m − 2 ) l − L + θ l + L − ε l = poly ( l ) n ( 2 δ ( m − 1 ) − ε ) l + poly ( l ) n ( 2 δ ( m − 2 ) + θ − ε ) l . (*) \le\sum_{L=1}^{l} \operatorname{poly}(l)n^{2\delta(m-1)l-L+L-\varepsilon l}+\sum_{L=1}^{l} \operatorname{poly}(l)n^{2\delta(m-2)l-L+\theta l+L-\varepsilon l}
= \operatorname{poly}(l)n^{(2\delta(m-1)-\varepsilon)l}+\operatorname{poly}(l)n^{(2\delta(m-2)+\theta-\varepsilon)l}. ( ∗ ) ≤ L = 1 ∑ l poly ( l ) n 2 δ ( m − 1 ) l − L + L − εl + L = 1 ∑ l poly ( l ) n 2 δ ( m − 2 ) l − L + θ l + L − εl = poly ( l ) n ( 2 δ ( m − 1 ) − ε ) l + poly ( l ) n ( 2 δ ( m − 2 ) + θ − ε ) l .
Since 2 δ ( m − 1 ) < ε 2\delta(m-1)<\varepsilon 2 δ ( m − 1 ) < ε and 2 δ ( m − 2 ) + θ < ε 2\delta(m-2)+\theta<\varepsilon 2 δ ( m − 2 ) + θ < ε , this tends to 0 0 0 as l → ∞ l \to\infty l → ∞ .
Residual Finiteness
Definition 4.4. A finitely generated semigroup M M M is graded if there is a surjective homomorphism with finite fibers from a finitely generated free semigroup onto M M M .
See [9 ] for an analogous definition for monoids, where the following is proved for monoids M M M in which M ∖ { 1 } M \setminus\{1\} M ∖ { 1 } is a semigroup.
Lemma 4.5 ([9 Theorem 1.7] ). Every graded semigroup is residually finite.
Further, Remmers [11 Corollary 4.14] proved that C ( 3 ) C(3) C ( 3 ) semigroups are graded.
Corollary 4.6. For every δ < 1 6 \delta< \frac{1}{6} δ < 6 1 and n ≥ 2 n \ge2 n ≥ 2 , M n , δ , l M_{n,\delta,l} M n , δ , l is residually finite with overwhelming probability.
Proof. This follows from Proposition 4.3, Lemma 4.5, and Remmers’ theorem [11 ] .
We close this section with the following remark, demonstrating the difference between the behavior of random semigroups and random groups. For random groups with δ < 1 2 \delta< \frac{1}{2} δ < 2 1 , for every given N N N , a random group does not have a subgroup of index ≤ N \le N ≤ N , or even a complex representation of dimension ≤ N \le N ≤ N , with overwhelming probability (see [8 ] and [1 ] ).
Proposition 4.7. Let 0 < δ < 1 2 0 < \delta< \frac{1}{2} 0 < δ < 2 1 . For every N ≥ 2 N \ge2 N ≥ 2 , M n , δ , l M_{n,\delta,l} M n , δ , l has a finite homomorphic image of size N N N , with overwhelming probability.
Proof. Let 0 < δ < 1 2 0 < \delta< \frac{1}{2} 0 < δ < 2 1 be given. Fix N ≥ 2 N \ge2 N ≥ 2 . Let t t t be such that n + ⋯ + n t − 1 < N ≤ n + ⋯ + n t n+\cdots+n^{t-1}<N\le n+\cdots+n^t n + ⋯ + n t − 1 < N ≤ n + ⋯ + n t .
Fix some 2 δ < θ < 1 2\delta<\theta<1 2 δ < θ < 1 . By Proposition 2.2,
Pr ( All relation words in R n , δ , l are of length ≥ ( 1 − θ ) l ) → l → ∞ 1. \Pr(\text{All relation words in }\mathcal{R}_{n,\delta,l}\text{ are of length }\ge(1-\theta)l)\xrightarrow[l\to\infty]{}1. Pr ( All relation words in R n , δ , l are of length ≥ ( 1 − θ ) l ) l → ∞ 1.
We may assume that ( 1 − θ ) l > t (1-\theta)l > t ( 1 − θ ) l > t . In the event that all words in R n , δ , l \mathcal{R}_{n,\delta,l} R n , δ , l are of length ≥ ( 1 − θ ) l \ge(1-\theta)l ≥ ( 1 − θ ) l , the quotient semigroup M n , δ , l M_{n,\delta,l} M n , δ , l maps onto
M ~ : = ⟨ x 1 , … , x n ∣ u = v ∀ ∣ u ∣ , ∣ v ∣ ≥ t + 1 ⟩ (4) \widetilde{M} := \langle x_1,\ldots,x_n \mid u=v\ \forall|u|,|v|\ge t+1\rangle \tag*{(4)} M := ⟨ x 1 , … , x n ∣ u = v ∀∣ u ∣ , ∣ v ∣ ≥ t + 1 ⟩ (4)
which is a semigroup with zero (represented by any word of length ≥ t + 1 \ge t+1 ≥ t + 1 ) whose cardinality is n + ⋯ + n t n+\cdots+n^t n + ⋯ + n t . Let D : = n + ⋯ + n t − N ≥ 0 D:=n+\cdots+n^t-N\ge0 D := n + ⋯ + n t − N ≥ 0 and pick D D D arbitrary length-t t t words over the alphabet { x 1 , … , x n } \{x_1,\ldots,x_n\} { x 1 , … , x n } , say, u 1 , … , u D u_1,\ldots,u_D u 1 , … , u D . Consider the quotient of the semigroup of M ~ \widetilde{M} M modulo the further relations u 1 = ⋯ = u D = 0 u_1=\cdots=u_D=0 u 1 = ⋯ = u D = 0 . Now the non-zero words in this semigroup are precisely: all words of length ≤ t − 1 \le t-1 ≤ t − 1 ; and all words of length t t t except for u 1 , … , u D u_1,\ldots,u_D u 1 , … , u D . Hence the cardinality of this quotient is n + ⋯ + n t − 1 + ( n t − D ) = N n+\cdots+n^{t-1}+(n^t-D)=N n + ⋯ + n t − 1 + ( n t − D ) = N . □ \square □
Hyperbolicity and non-amenability
In this section, we will show that for every n ≥ 2 n\ge2 n ≥ 2 and 0 < δ < 1 / 2 0<\delta<1/2 0 < δ < 1/2 , the random semigroup M n , δ , l M_{n,\delta,l} M n , δ , l has a homomorphic image which generates a non-elementary hyperbolic group, and discuss applications to the (non)amenability of M n , δ , l M_{n,\delta,l} M n , δ , l .
Hyperbolicity
Given a semigroup M M M , let M → ι G ( M ) M\xrightarrow{\iota}G(M) M ι G ( M ) be its enveloping group: every homomorphism f : M → H f:M\to H f : M → H where H H H is a group factors uniquely through ι \iota ι . In particular, for any n , δ , l n,\delta,l n , δ , l , we define a random group G n , δ , l = G ( M n , δ , l ) G_{n,\delta,l}=G(M_{n,\delta,l}) G n , δ , l = G ( M n , δ , l ) , namely, G n , δ , l : = F n / ⟨ ⟨ u i v i − 1 ∣ i ∈ I ⟩ ⟩ G_{n,\delta,l}:=F_n/\langle\langle u_i v_i^{-1}\mid i\in I\rangle\rangle G n , δ , l := F n / ⟨⟨ u i v i − 1 ∣ i ∈ I ⟩⟩ . We will prove that G n , δ , l G_{n,\delta,l} G n , δ , l is non-elementary hyperbolic with overwhelming probability.
Notice that this notion differs from Gromov random groups. Indeed, for any word w w w in a free group, denote by cyc ( w ) \operatorname{cyc}(w) cyc ( w ) its cyclically reduced form. Then the relations of G n , δ , l G_{n,\delta,l} G n , δ , l are sampled independently according to the following measure μ l \mu_l μ l : Take a uniform unordered pair { u , v } ⊆ B n , l \{u,v\}\subseteq B_{n,l} { u , v } ⊆ B n , l , choose an orientation uniformly, and then let μ l \mu_l μ l be the measure of the random word cyc ( u v − 1 ) \operatorname{cyc}(uv^{-1}) cyc ( u v − 1 ) .
Our goal will be to use a theorem of Ollivier, which we state below. Throughout the statement, “a subword under μ l \mu_l μ l ” and “two disjoint subwords under μ l \mu_l μ l ” are understood in the sense of Ollivier's Definitions 6 and 7. In particular, the probability bounds are conditional on the total relator length and on specified portions revealed before the chosen subword. Furthermore, for two subwords, the definition separately covers two independent relators and two disjoint pieces of the same relator.
Theorem 5.1 ([10 Theorem 9] ). Let Γ \Gamma Γ be a non-elementary hyperbolic group with generating set { x 1 ± 1 , … , x 2 n ± 1 } \{x_1^{\pm1},\ldots,x_{2n}^{\pm1}\} { x 1 ± 1 , … , x 2 n ± 1 } and trivial virtual center. Let
μ l \mu_l μ l be a family of symmetric measures indexed by l l l , satisfying the following axioms:
(1) There is a constant κ 1 ≥ 1 \kappa_1 \ge1 κ 1 ≥ 1 such that μ l \mu_l μ l weights only words of length between l / κ 1 l/\kappa_1 l / κ 1 and κ 1 l \kappa_1l κ 1 l .
(2) There are constants κ 2 , β 2 > 0 \kappa_2, \beta_2 > 0 κ 2 , β 2 > 0 such that for every subword x x x under μ l \mu_l μ l , for every 0 ≤ t ≤ 1 0 \le t \le1 0 ≤ t ≤ 1 , we have
Pr ( ∥ x ∥ ≤ κ 2 ∣ x ∣ ( 1 − t ) ) ≤ e o ( l ) ( 2 n ) − β 2 t ∣ x ∣ . \Pr(\lVert x\rVert\le\kappa_2|x|(1-t)) \le e^{o(l)}(2n)^{-\beta_2t|x|}. Pr (∥ x ∥ ≤ κ 2 ∣ x ∣ ( 1 − t )) ≤ e o ( l ) ( 2 n ) − β 2 t ∣ x ∣ .
Here ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ stands for the word metric in the ambient group Γ \Gamma Γ .
(3) There are constants β 3 , γ 3 > 0 \beta_3, \gamma_3 > 0 β 3 , γ 3 > 0 such that for any two disjoint subwords under μ l \mu_l μ l , for any m = m ( l ) m=m(l) m = m ( l ) ,
Pr ( ∃ ξ , η ∈ F n : ∣ ξ ∣ , ∣ η ∣ ≤ m , x ξ y η = 1 ) ≤ e o ( l ) ⋅ ( 2 n ) γ 3 m ( 2 n ) − β 3 ( ∣ x ∣ + ∣ y ∣ ) . \Pr(\exists\xi,\eta\in F_n : |\xi|,|\eta| \le m,\ x\xi y\eta=1) \le e^{o(l)}\cdot(2n)^{\gamma_3m}(2n)^{-\beta_3(|x|+|y|)}. Pr ( ∃ ξ , η ∈ F n : ∣ ξ ∣ , ∣ η ∣ ≤ m , x ξ y η = 1 ) ≤ e o ( l ) ⋅ ( 2 n ) γ 3 m ( 2 n ) − β 3 ( ∣ x ∣ + ∣ y ∣ ) .
(4) There exist constants β 4 , γ 4 > 0 \beta_4, \gamma_4 > 0 β 4 , γ 4 > 0 such that, for any subword x x x under μ l \mu_l μ l , for any m = m ( l ) m=m(l) m = m ( l ) ,
Pr ( ∃ ξ , η ∈ F n ∖ { 1 } : ∣ ξ ∣ , ∣ η ∣ ≤ m , ξ x = x η ) ≤ e o ( l ) ⋅ ( 2 n ) γ 4 m ( 2 n ) − β 4 ∣ x ∣ . \Pr(\exists\xi,\eta\in F_n\setminus\{1\} : |\xi|,|\eta| \le m,\ \xi x=x\eta) \le e^{o(l)}\cdot(2n)^{\gamma_4m}(2n)^{-\beta_4|x|}. Pr ( ∃ ξ , η ∈ F n ∖ { 1 } : ∣ ξ ∣ , ∣ η ∣ ≤ m , ξ x = x η ) ≤ e o ( l ) ⋅ ( 2 n ) γ 4 m ( 2 n ) − β 4 ∣ x ∣ .
(We note that the equalities and inequalities of axioms (3) and (4) should hold in Γ \Gamma Γ , and that the e o ( l ) e^{o(l)} e o ( l ) factors should be uniform in the conditioning data.)
Let R R R be a set of independent random words of density at most d d d picked under μ l \mu_l μ l , i.e., for every length L L L there are at most ( 2 n ) d L (2n)^{dL} ( 2 n ) d L (independent) words in R R R of length L L L (each one sampled by μ l L = μ l ( ⋅ ∣ ∣ ⋅ ∣ = L \mu_l^L=\mu_l(\cdot\mid|\cdot|=L μ l L = μ l ( ⋅ ∣ ∣ ⋅ ∣ = L )).
If d < min { β 2 , β 3 , β 4 } d<\min\{\beta_2,\beta_3,\beta_4\} d < min { β 2 , β 3 , β 4 } , then with probability exponentially close to 1 1 1 as l → ∞ l\to\infty l → ∞ , the random quotient Γ / ⟨ ⟨ R ⟩ ⟩ \Gamma/\langle\langle R\rangle\rangle Γ/ ⟨⟨ R ⟩⟩ is non-elementary hyperbolic, as well as all intermediate quotients Γ / ⟨ ⟨ R ′ ⟩ ⟩ \Gamma/\langle\langle R'\rangle\rangle Γ/ ⟨⟨ R ′ ⟩⟩ with R ′ ⊆ R R'\subseteq R R ′ ⊆ R .
We want to apply Theorem 5.1 to the random group G n , δ , l G_{n,\delta,l} G n , δ , l . Here the ambient group is Γ = F n \Gamma=F_n Γ = F n , which is non-elementary hyperbolic and has trivial virtual center for n ≥ 2 n\ge2 n ≥ 2 . The measures μ l \mu_l μ l are those defined above, which are symmetric by definition. However, these measures do not satisfy Axiom 1: they give a positive weight to short words. To overcome this, we will replace the measures μ l \mu_l μ l by a truncated version of them. We fix 0 ≤ δ < 1 2 0\le\delta<\frac{1}{2} 0 ≤ δ < 2 1 and choose δ < θ < 1 2 \delta<\theta<\frac{1}{2} δ < θ < 2 1 .
We write f ≪ n g f\ll_n g f ≪ n g if there is a constant C > 0 C>0 C > 0 , depending only on n n n , such that f ≤ C g f\le Cg f ≤ C g .
Lemma 5.2. For u , v u,v u , v chosen uniformly as above,
Pr ( ∣ cyc ( u v − 1 ) ∣ = L ) ≪ n ( l − ⌈ L / 2 ⌉ + 1 ) n ⌊ L / 2 ⌋ − l \Pr(|\operatorname{cyc}(uv^{-1})|=L)\ll_n (l-\lceil L/2\rceil+1)n^{\lfloor L/2\rfloor-l} Pr ( ∣ cyc ( u v − 1 ) ∣ = L ) ≪ n ( l − ⌈ L /2 ⌉ + 1 ) n ⌊ L /2 ⌋ − l uniformly for $1\le L\le 2l.
Proof. To count the number of pairs ( u , v ) (u,v) ( u , v ) with ∣ cyc ( u v − 1 ) ∣ = L \lvert\operatorname{cyc}(uv^{-1})\rvert=L ∣ cyc ( u v − 1 )∣ = L , we write u = w p w ′ u=wpw' u = w p w ′ and v = w q w ′ v=wqw' v = w q w ′ where p , q p,q p , q do not begin with the same letter and do not end with the same letter. Then ∣ w ∣ + ∣ w ′ ∣ + max { ∣ p ∣ , ∣ q ∣ } ≤ l \lvert w\rvert+\lvert w'\rvert+\max\{\lvert p\rvert,\lvert q\rvert\}\le l ∣ w ∣ + ∣ w ′ ∣ + max {∣ p ∣ , ∣ q ∣} ≤ l , and cyc ( u v − 1 ) = p q − 1 \operatorname{cyc}(uv^{-1})=pq^{-1} cyc ( u v − 1 ) = p q − 1 , so ∣ cyc ( u v − 1 ) ∣ = ∣ p ∣ + ∣ q ∣ \lvert\operatorname{cyc}(uv^{-1})\rvert=\lvert p\rvert+\lvert q\rvert ∣ cyc ( u v − 1 )∣ = ∣ p ∣ + ∣ q ∣ . Therefore, the number of pairs ( u , v ) (u,v) ( u , v ) such that ∣ cyc ( u v − 1 ) ∣ = L \lvert\operatorname{cyc}(uv^{-1})\rvert=L ∣ cyc ( u v − 1 )∣ = L is bounded by the number of words ( w , w ′ , p , q ) (w,w',p,q) ( w , w ′ , p , q ) of lengths ( a , a ′ , i , L − i ) (a,a',i,L-i) ( a , a ′ , i , L − i ) such that a + a ′ + max { i , L − i } ≤ l a+a'+\max\{i,L-i\}\le l a + a ′ + max { i , L − i } ≤ l :
Pr ( ∣ cyc ( u v − 1 ) ∣ = L ) ≤ 1 ∣ B n , l ∣ ( ∣ B n , l ∣ − 1 ) ∑ i = max { 0 , L − l } min { L , l } ∑ a + a ′ ≤ l − max { i , L − i } n a + a ′ + i + ( L − i ) \operatorname{Pr}\left(\lvert\operatorname{cyc}(uv^{-1})\rvert=L\right)
\le\frac{1}{\lvert B_{n,l}\rvert(\lvert B_{n,l}\rvert-1)}
\sum_{i=\max\{0,L-l\}}^{\min\{L,l\}}
\sum_{a+a'\le l-\max\{i,L-i\}} n^{a+a'+i+(L-i)} Pr ( ∣ cyc ( u v − 1 )∣ = L ) ≤ ∣ B n , l ∣ (∣ B n , l ∣ − 1 ) 1 i = m a x { 0 , L − l } ∑ m i n { L , l } a + a ′ ≤ l − m a x { i , L − i } ∑ n a + a ′ + i + ( L − i )
≪ n n L n 2 l ∑ i = max { 0 , L − l } min { L , l } ∑ a + a ′ ≤ l − max { i , L − i } n a + a ′ . \ll_n \frac{n^L}{n^{2l}}
\sum_{i=\max\{0,L-l\}}^{\min\{L,l\}}
\sum_{a+a'\le l-\max\{i,L-i\}} n^{a+a'}. ≪ n n 2 l n L i = m a x { 0 , L − l } ∑ m i n { L , l } a + a ′ ≤ l − m a x { i , L − i } ∑ n a + a ′ .
We use the identity
∑ a + a ′ ≤ M n a + a ′ = ∑ j = 0 M ( j + 1 ) n j ≍ n ( M + 1 ) n M . \sum_{a+a'\le M} n^{a+a'}=\sum_{j=0}^{M}(j+1)n^j\asymp_n (M+1)n^M. a + a ′ ≤ M ∑ n a + a ′ = j = 0 ∑ M ( j + 1 ) n j ≍ n ( M + 1 ) n M .
and deduce
Pr ( ∣ cyc ( u v − 1 ) ∣ = L ) ≪ n n L n 2 l ∑ i = max { 0 , L − l } min { L , l } ( l − max { i , L − i } + 1 ) n l − max { i , L − i } ≤ l − ⌈ L / 2 ⌉ + 1 n l ∑ i = max { 0 , L − l } min { L , l } n min { i , L − i } ≪ n ( l − ⌈ L / 2 ⌉ + 1 ) n ⌊ L / 2 ⌋ − l . \begin{aligned}
\operatorname{Pr}\left(\lvert\operatorname{cyc}(uv^{-1})\rvert=L\right)
&\ll_n \frac{n^L}{n^{2l}}
\sum_{i=\max\{0,L-l\}}^{\min\{L,l\}}
\left(l-\max\{i,L-i\}+1\right)n^{l-\max\{i,L-i\}}\\
&\le\frac{l-\lceil L/2\rceil+1}{n^l}
\sum_{i=\max\{0,L-l\}}^{\min\{L,l\}}n^{\min\{i,L-i\}}\\
&\ll_n \left(l-\lceil L/2\rceil+1\right)n^{\lfloor L/2\rfloor-l}.
\end{aligned} Pr ( ∣ cyc ( u v − 1 )∣ = L ) ≪ n n 2 l n L i = m a x { 0 , L − l } ∑ m i n { L , l } ( l − max { i , L − i } + 1 ) n l − m a x { i , L − i } ≤ n l l − ⌈ L /2 ⌉ + 1 i = m a x { 0 , L − l } ∑ m i n { L , l } n m i n { i , L − i } ≪ n ( l − ⌈ L /2 ⌉ + 1 ) n ⌊ L /2 ⌋ − l .
A simple union bound shows that:
Corollary 5.3. For any L ≥ 1 L\ge1 L ≥ 1 ,
Pr ( ∣ cyc ( u v − 1 ) ∣ ≤ L ) ≪ n l n L / 2 − l . \operatorname{Pr}\left(\lvert\operatorname{cyc}(uv^{-1})\rvert\le L\right)\ll_n l\,n^{L/2-l}. Pr ( ∣ cyc ( u v − 1 )∣ ≤ L ) ≪ n l n L /2 − l .
By taking another union bound, we get:
Corollary 5.4. If u 1 = v 1 , … , u N = v N u_1=v_1,\ldots,u_N=v_N u 1 = v 1 , … , u N = v N are the relations of the random semigroup for N = ⌊ n 2 δ l ⌋ N=\lfloor n^{2\delta l}\rfloor N = ⌊ n 2 δ l ⌋ , then
Pr ( ∃ i : ∣ cyc ( u i v i − 1 ) ∣ ≤ 2 ( 1 − 2 θ ) l ) ≪ n l n 2 ( δ − θ ) l . \operatorname{Pr}\left(\exists i:\lvert\operatorname{cyc}(u_iv_i^{-1})\rvert\le2(1-2\theta)l\right)\ll_n l\,n^{2(\delta-\theta)l}. Pr ( ∃ i : ∣ cyc ( u i v i − 1 )∣ ≤ 2 ( 1 − 2 θ ) l ) ≪ n l n 2 ( δ − θ ) l .
We write μ ~ l \widetilde{\mu}_l μ l for the measure obtained from μ l \mu_l μ l by conditioning on the fact that the length of a μ ~ l \widetilde{\mu}_l μ l -random word is at least c l cl c l for c = 2 ( 1 − 2 θ ) > 0 c = 2(1-2\theta) > 0 c = 2 ( 1 − 2 θ ) > 0 . In other words, sampling according to μ ~ l \widetilde{\mu}_l μ l can be thought of as sampling according to μ l \mu_l μ l until the resulting word is long enough. We note that for any c l ≤ L ≤ 2 l cl \le L \le2l c l ≤ L ≤ 2 l ,
μ l ( ⋅ ∣ ∣ ⋅ ∣ = L ) = μ ~ l ( ⋅ ∣ ∣ ⋅ ∣ = L ) . \mu_l(\,\cdot\mid|\cdot|=L)=\widetilde{\mu}_l(\,\cdot\mid|\cdot|=L). μ l ( ⋅ ∣ ∣ ⋅ ∣ = L ) = μ l ( ⋅ ∣ ∣ ⋅ ∣ = L ) .
Therefore, the verification of Axioms 3 and 4 for the truncated law μ ~ l \widetilde{\mu}_l μ l uses exactly the same length-conditioned distributions as μ l \mu_l μ l .
Lemma 5.5. There is a constant C = C n C=C_n C = C n such that the following holds. Let r r r be a μ l \mu_l μ l -random word. Condition on ∣ r ∣ = L |r|=L ∣ r ∣ = L , fix a deterministic cyclic interval3 I ⊆ Z / L Z I\subseteq\mathbb{Z}/L\mathbb{Z} I ⊆ Z / L Z , and reveal all the letters outside I I I . Then, for every word z z z whose letters are indexed by I I I ,
Pr ( r ∣ I = z ∣ ∣ r ∣ = L , r ∣ I c ) ≤ C n − ∣ I ∣ . (5) \Pr\left(r|_I=z \mid|r|=L,\ r|_{I^c}\right)\le Cn^{-|I|}. \tag*{(5)} Pr ( r ∣ I = z ∣ ∣ r ∣ = L , r ∣ I c ) ≤ C n − ∣ I ∣ . (5)
Proof. Write r = cvc ( u v − 1 ) r=\operatorname{cvc}(uv^{-1}) r = cvc ( u v − 1 ) for u , v u,v u , v chosen uniformly from B n , l B_{n,l} B n , l . Write u = w p w ′ u=wpw' u = w p w ′ and v = w q w ′ v=wqw' v = w q w ′ , where w w w is the maximal common prefix of u , v u,v u , v , and w ′ w' w ′ is the maximal common suffix of u , v u,v u , v after removing w w w . Then r = p q − 1 r=pq^{-1} r = p q − 1 . Put a = ∣ p ∣ a=|p| a = ∣ p ∣ and b = ∣ q ∣ b=|q| b = ∣ q ∣ . Conditional on a , b a,b a , b , all pairs ( p , q ) (p,q) ( p , q ) with lengths ( a , b ) (a,b) ( a , b ) such that p , q p,q p , q do not start or end with the same letter, have the same probability: indeed, the number of possible choices of w , w ′ w,w' w , w ′ is ∑ h + k ≤ l − max { a , b } n h + k \sum_{h+k\le l-\max\{a,b\}}n^{h+k} ∑ h + k ≤ l − m a x { a , b } n h + k , which depends only on a , b a,b a , b . The cases a = 0 a=0 a = 0 or b = 0 b=0 b = 0 are the same, with fewer restrictions.
Take a cyclic interval I ⊆ Z / L Z I\subseteq\mathbb{Z}/L\mathbb{Z} I ⊆ Z / L Z and a word z z z . Fix a , b a,b a , b such that a + b = L a+b=L a + b = L , and fix a realization ρ \rho ρ of r ∣ I c r|_{I^c} r ∣ I c for which the conditioning event ∣ p ∣ = a , ∣ q ∣ = b , r ∣ I c = ρ |p|=a,|q|=b,r|_{I^c}=\rho ∣ p ∣ = a , ∣ q ∣ = b , r ∣ I c = ρ has positive probability. Let F a , b ( ρ ) \mathcal{F}_{a,b}(\rho) F a , b ( ρ ) be the set of all admissible fillings of the letters in I I I . Conditional on a , b a,b a , b and on r ∣ I c = ρ r|_{I^c}=\rho r ∣ I c = ρ , all elements of F a , b ( ρ ) \mathcal{F}_{a,b}(\rho) F a , b ( ρ ) have the same probability.
When a , b > 0 a,b>0 a , b > 0 , the only restrictions on p , q p,q p , q are p 1 ≠ q 1 p_1\ne q_1 p 1 = q 1 and p a ≠ q b p_a\ne q_b p a = q b . Since F a , b ( ρ ) \mathcal{F}_{a,b}(\rho) F a , b ( ρ ) is nonempty, fix one admissible assignment to the at most four positions involved in the endpoint restrictions. All remaining positions in I I I may be chosen freely, hence ∣ F a , b ( ρ ) ∣ ≥ n ∣ I ∣ − 4 |\mathcal{F}_{a,b}(\rho)|\ge n^{|I|-4} ∣ F a , b ( ρ ) ∣ ≥ n ∣ I ∣ − 4 . Therefore
Pr ( r ∣ I = z ∣ ∣ p ∣ = a , ∣ q ∣ = b , r ∣ I c = ρ ) ≤ 4 n − ∣ I ∣ . \Pr\left(r|_I=z\mid|p|=a,|q|=b,r|_{I^c}=\rho\right)\le4n^{-|I|}. Pr ( r ∣ I = z ∣ ∣ p ∣ = a , ∣ q ∣ = b , r ∣ I c = ρ ) ≤ 4 n − ∣ I ∣ .
The same bound holds also if a = 0 a=0 a = 0 or b = 0 b=0 b = 0 . Since the right hand side does not depend on a , b a,b a , b , we may average over them and deduce
Pr ( r ∣ I = z ∣ ∣ r ∣ = L , r ∣ I c = ρ ) ≤ 4 n − ∣ I ∣ , \Pr\left(r|_I=z\mid|r|=L,r|_{I^c}=\rho\right)\le4n^{-|I|}, Pr ( r ∣ I = z ∣ ∣ r ∣ = L , r ∣ I c = ρ ) ≤ 4 n − ∣ I ∣ ,
so the lemma holds with C = n 4 C=n^4 C = n 4 .
The lemma conditions on the whole complement of the chosen interval, and is therefore stronger than each of the conditional estimates required in Ollivier's theorem. Since the bound is uniform in the revealed letters, averaging over any information not prescribed by those definitions gives the required estimates.
Proposition 5.6. The measures μ ~ l \widetilde{\mu}_l μ l satisfy Ollivier's axioms with β 2 \beta_2 β 2 arbitrarily large, β 3 = 1 2 log 2 n n \beta_3 = \frac{1}{2}\log_{2n} n β 3 = 2 1 log 2 n n , and β 4 = log 2 n n \beta_4 = \log_{2n} n β 4 = log 2 n n .
Proof. We do this directly by verifying each axiom:
This is immediate by the definition of μ ~ l \widetilde{\mu}_l μ l ; indeed, we can take κ 1 = max { 2 , c − 1 } \kappa_1 = \max\{2,c^{-1}\} κ 1 = max { 2 , c − 1 } , since any word sampled by μ ~ l \widetilde{\mu}_l μ l has length between c l cl c l and 2 l 2l 2 l .
In Ollivier's setting, the ambient group Γ \Gamma Γ is allowed to be a non-elementary hyperbolic (not necessarily free) group. However, in our case Γ \Gamma Γ is free. Since the words sampled by μ ~ l \widetilde{\mu}_l μ l are cyclically reduced, any subword x x x of them is freely reduced, and so satisfies ∥ x ∥ = ∣ x ∣ \lVert x\rVert= |x| ∥ x ∥ = ∣ x ∣ . This proves Axiom 2 with κ 2 = 1 \kappa_2 = 1 κ 2 = 1 and arbitrarily large β 2 \beta_2 β 2 .
Let x , y x,y x , y be two disjoint subwords and let m = m ( l ) m=m(l) m = m ( l ) . Fix words ξ , η \xi,\eta ξ , η of lengths at most m m m . After revealing x x x , the equation x ξ y η = e x\xi y\eta=e x ξ y η = e determines y y y uniquely, if it has a solution. Hence, by (5.1), Pr ( x ξ y η = e ∣ ξ , η , x ) ≤ C n − ∣ y ∣ \Pr(x\xi y\eta=e\mid\xi,\eta,x)\le Cn^{-|y|} Pr ( x ξ y η = e ∣ ξ , η , x ) ≤ C n − ∣ y ∣ . If the equation holds, then ∣ x ∣ − ∣ y ∣ ≤ ∣ ξ ∣ + ∣ η ∣ ≤ 2 m |x|-|y|\le|\xi|+|\eta|\le2m ∣ x ∣ − ∣ y ∣ ≤ ∣ ξ ∣ + ∣ η ∣ ≤ 2 m , and therefore ∣ y ∣ ≥ ∣ x ∣ + ∣ y ∣ 2 − m |y|\ge\frac{|x|+|y|}{2}-m ∣ y ∣ ≥ 2 ∣ x ∣ + ∣ y ∣ − m . Summing over the at most C ′ ⋅ ( 2 n ) 2 m C'\cdot(2n)^{2m} C ′ ⋅ ( 2 n ) 2 m choices of ξ , η \xi,\eta ξ , η (for some C ′ > 0 C'>0 C ′ > 0 ), we obtain
Pr ( ∃ ξ , η : ∣ ξ ∣ , ∣ η ∣ ≤ m , x ξ y η = e ) ≤ C ′ ⋅ ( 2 n ) 2 m ⋅ C n − ∣ y ∣ ≤ C C ′ ( 2 n ) 3 m ( 2 n ) − 1 2 log 2 n ( n ) ( ∣ x ∣ + ∣ y ∣ ) . \begin{aligned}
\Pr(\exists\xi,\eta:|\xi|,|\eta|\le m,\ x\xi y\eta=e)\le C'\cdot(2n)^{2m}\cdot Cn^{-|y|} \\
&\le CC'(2n)^{3m}(2n)^{-\frac{1}{2}\log_{2n}(n)(|x|+|y|)}.
\end{aligned} Pr ( ∃ ξ , η : ∣ ξ ∣ , ∣ η ∣ ≤ m , x ξ y η = e ) ≤ C ′ ⋅ ( 2 n ) 2 m ⋅ C n − ∣ y ∣ ≤ C C ′ ( 2 n ) 3 m ( 2 n ) − 2 1 l o g 2 n ( n ) ( ∣ x ∣ + ∣ y ∣ ) .
We may therefore take β 3 = 1 2 log 2 n n \beta_3=\frac{1}{2}\log_{2n}n β 3 = 2 1 log 2 n n .
Fix nontrivial words ξ , η \xi,\eta ξ , η of length at most m m m . If ξ x = x η \xi x=x\eta ξ x = x η has one solution x 0 x_0 x 0 , then all solutions form the coset x 0 Cent F n ( η ) x_0\operatorname{Cent}_{F_n}(\eta) x 0 Cent F n ( η ) . The centralizer of a nontrivial element of a free group is cyclic, and one may choose ∣ x 0 ∣ ≤ 2 m |x_0|\le2m ∣ x 0 ∣ ≤ 2 m . If Cent F n ( η ) = ⟨ h ⟩ \operatorname{Cent}_{F_n}(\eta)=\langle h\rangle Cent F n ( η ) = ⟨ h ⟩ , then any solution of length s s s is of the form x 0 h j x_0h^j x 0 h j for ∣ j ∣ ∣ h ∣ ≤ ∣ x 0 ∣ + ∣ x 0 h j ∣ ≤ 2 m + s |j||h|\le|x_0|+|x_0h^j|\le2m+s ∣ j ∣∣ h ∣ ≤ ∣ x 0 ∣ + ∣ x 0 h j ∣ ≤ 2 m + s . It follows that the number of reduced solutions x x x of a prescribed length s s s is at most 4 m + 2 s + 1 4m+2s+1 4 m + 2 s + 1 . Using (5.1) and summing over ξ , η \xi,\eta ξ , η , we get
Pr ( ∃ ξ , η ≠ 1 : ∣ ξ ∣ , ∣ η ∣ ≤ m , ξ x = x η ) ≤ C ( m + s ) ( 2 n ) 2 m n − s ≤ e o ( l ) ( 2 n ) 3 m ( 2 n ) − log 2 n ( n ) s . \begin{aligned}
\Pr(\exists\xi,\eta\ne1:|\xi|,|\eta|\le m,\ \xi x=x\eta)\le C(m+s)(2n)^{2m}n^{-s} \\
&\le e^{o(l)}(2n)^{3m}(2n)^{-\log_{2n}(n)s}.
\end{aligned} Pr ( ∃ ξ , η = 1 : ∣ ξ ∣ , ∣ η ∣ ≤ m , ξ x = x η ) ≤ C ( m + s ) ( 2 n ) 2 m n − s ≤ e o ( l ) ( 2 n ) 3 m ( 2 n ) − l o g 2 n ( n ) s .
This proves the final axiom with β 4 = log 2 n n \beta_4=\log_{2n}n β 4 = log 2 n n .
We recall that a coupling of probability measures ν 1 , ν 2 \nu_1,\nu_2 ν 1 , ν 2 is a pair of random variables ( X 1 , X 2 ) (X_1,X_2) ( X 1 , X 2 ) , defined on a common probability space, with respective laws ν 1 , ν 2 \nu_1,\nu_2 ν 1 , ν 2 . For every property P \mathcal{P} P ,
∣ Pr ( X 1 ∈ P ) − Pr ( X 2 ∈ P ) ∣ ≤ Pr ( X 1 ≠ X 2 ) . \left|\Pr(X_1 \in\mathcal{P})-\Pr(X_2 \in\mathcal{P})\right| \leq\Pr(X_1 \neq X_2). ∣ Pr ( X 1 ∈ P ) − Pr ( X 2 ∈ P ) ∣ ≤ Pr ( X 1 = X 2 ) .
Thus a coupling for which Pr ( X 1 ≠ X 2 ) = o ( 1 ) \Pr(X_1 \neq X_2)=o(1) Pr ( X 1 = X 2 ) = o ( 1 ) allows one to transfer events holding with overwhelming probability from one model to the other.
Theorem 5.7. For any n ≥ 2 n \geq2 n ≥ 2 and 0 ≤ δ < 1 2 0 \leq\delta< \frac{1}{2} 0 ≤ δ < 2 1 , the group G n , δ , l G_{n,\delta,l} G n , δ , l is non-elementary hyperbolic with overwhelming probability.
Proof. Fix 0 ≤ δ < 1 2 0 \leq\delta< \frac{1}{2} 0 ≤ δ < 2 1 and n ≥ 2 n \geq2 n ≥ 2 . To apply Theorem 5.1, we need to make sure that the measures μ l \mu_l μ l satisfy the four axioms of the theorem, and to control the number of relations of G n , δ , l G_{n,\delta,l} G n , δ , l of each length. A priori, this does not hold for G n , δ , l G_{n,\delta,l} G n , δ , l : the measure μ l \mu_l μ l gives positive weight to short words as well as long ones, and the length of each relation is random. We fix this by using two couplings: The first one replaces μ l \mu_l μ l by μ ~ l \widetilde{\mu}_l μ l , which controls the lengths of the relations, and the second coupling controls the number of relations of each length, allowing us to get a good density for the set of relations.
For the proof, it will be easier for us to choose the relations of G n , δ , l G_{n,\delta,l} G n , δ , l as independent words rather than choose an independent set of relations. Since δ < 1 2 \delta< \frac{1}{2} δ < 2 1 , this is harmless: If Q = ( ∣ B n , l ∣ 2 ) Q = \binom{|B_{n,l}|}{2} Q = ( 2 ∣ B n , l ∣ ) is the total number of unordered pairs of words and N = ⌊ n 2 δ l ⌋ N = \lfloor n^{2\delta l}\rfloor N = ⌊ n 2 δ l ⌋ is the number of sampled relations, the probability that we choose the same relation twice when taking N N N independent pairs is bounded by
( N 2 ) Q = O n ( n ( 4 δ − 2 ) l ) = o l ( 1 ) , \frac{\binom{N}{2}}{Q}=O_n\left(n^{(4\delta-2)l}\right)=o_l(1), Q ( 2 N ) = O n ( n ( 4 δ − 2 ) l ) = o l ( 1 ) , so this event has probability tending to 0 0 0 as l l l tends to ∞ \infty ∞ .
For the first part, we let G ~ n , δ , l \widetilde{G}_{n,\delta,l} G n , δ , l denote a random group with N = ⌊ n 2 δ l ⌋ N=\lfloor n^{2\delta l}\rfloor N = ⌊ n 2 δ l ⌋ relations, such that the relations are independent and sampled by μ ~ l \widetilde{\mu}_l μ l . We claim that there is a coupling of G n , δ , l G_{n,\delta,l} G n , δ , l and G ~ n , δ , l \widetilde{G}_{n,\delta,l} G n , δ , l such that Pr ( G n , δ , l ≠ G ~ n , δ , l ) = o l ( 1 ) \Pr(G_{n,\delta,l}\neq\widetilde{G}_{n,\delta,l})=o_l(1) Pr ( G n , δ , l = G n , δ , l ) = o l ( 1 ) . Therefore, G n , δ , l G_{n,\delta,l} G n , δ , l is non-elementary hyperbolic if and only if G ~ n , δ , l \widetilde{G}_{n,\delta,l} G n , δ , l is.
Indeed, we define the coupling as follows. Sample N N N independent μ l \mu_l μ l -words W 1 , … , W N W_1,\ldots,W_N W 1 , … , W N . Then, for each 1 ≤ i ≤ N 1 \leq i \leq N 1 ≤ i ≤ N , define W ~ i \widetilde{W}_i W i as follows: If ∣ W i ∣ ≥ c l |W_i| \geq cl ∣ W i ∣ ≥ c l , we set W ~ i = W i \widetilde{W}_i=W_i W i = W i , and otherwise sample W ~ i \widetilde{W}_i W i from μ ~ l \widetilde{\mu}_l μ l . By Corollary 5.4,
Pr ( G n , δ , l ≠ G ~ n , δ , l ) ≤ Pr ( ∃ i : W i ≠ W ~ i ) \Pr(G_{n,\delta,l}\neq\widetilde{G}_{n,\delta,l})\leq\Pr(\exists i: W_i\neq\widetilde{W}_i) Pr ( G n , δ , l = G n , δ , l ) ≤ Pr ( ∃ i : W i = W i ) ≤ Pr ( ∃ i : ∣ W i ∣ ≤ c l ) ≪ n l n 2 ( δ − θ ) l = o l ( 1 ) . \leq\Pr(\exists i: |W_i|\leq cl)\ll_n ln^{2(\delta-\theta)l}=o_l(1). ≤ Pr ( ∃ i : ∣ W i ∣ ≤ c l ) ≪ n l n 2 ( δ − θ ) l = o l ( 1 ) .
We are left with computing the density of the relations of G ~ n , δ , l \widetilde{G}_{n,\delta,l} G n , δ , l . For each c l ≤ L ≤ 2 l cl \le L \le2l c l ≤ L ≤ 2 l , let M δ , L M_{\delta,L} M δ , L denote the number of relations of G ~ n , δ , l \widetilde{G}_{n,\delta,l} G n , δ , l of length L L L . Then
E [ M δ , L ] = N Pr w ∼ μ ~ l ( ∣ w ∣ = L ) = N Pr w ∼ μ ~ l ( ∣ w ∣ = L ∣ ∣ w ∣ ≥ c l ) = N Pr w ∼ μ l ( ∣ w ∣ = L ) Pr w ∼ μ l ( ∣ w ∣ ≥ c l ) ≪ n n 2 δ l n L / 2 − l ≤ l n ( 2 δ − 1 ) l + L / 2 ≤ l n δ L . \begin{aligned}
\mathbb{E}[M_{\delta,L}] &= N\operatorname{Pr}_{w\sim\widetilde{\mu}_l}(|w|=L) \\
&= N\operatorname{Pr}_{w\sim\widetilde{\mu}_l}(|w|=L\mid|w|\ge cl) \\
&= N\frac{\operatorname{Pr}_{w\sim\mu_l}(|w|=L)}{\operatorname{Pr}_{w\sim\mu_l}(|w|\ge cl)} \\
&\ll_n n^{2\delta l}n^{L/2-l} \\
&\le l n^{(2\delta-1)l+L/2}\le l n^{\delta L}.
\end{aligned} E [ M δ , L ] = N Pr w ∼ μ l ( ∣ w ∣ = L ) = N Pr w ∼ μ l ( ∣ w ∣ = L ∣ ∣ w ∣ ≥ c l ) = N Pr w ∼ μ l ( ∣ w ∣ ≥ c l ) Pr w ∼ μ l ( ∣ w ∣ = L ) ≪ n n 2 δ l n L /2 − l ≤ l n ( 2 δ − 1 ) l + L /2 ≤ l n δ L .
where the ≪ n \ll_n ≪ n inequality uses Lemma 5.2 and Pr w ∼ μ l ( ∣ w ∣ ≥ c l ) = 1 − o ( 1 ) \operatorname{Pr}_{w\sim\mu_l}(|w|\ge cl)=1-o(1) Pr w ∼ μ l ( ∣ w ∣ ≥ c l ) = 1 − o ( 1 ) , and the last inequality uses L ≤ 2 l L\le2l L ≤ 2 l . This gives the required exponential upper bound on the expected number of relators of each length. However, the number of relators at each length is random, and therefore need not satisfy Ollivier's deterministic length-by-length cap on every realization.
We solve this problem by considering a different set of relations R \mathcal{R} R , which will contain the relations of G ~ n , δ , l \widetilde{G}_{n,\delta,l} G n , δ , l with overwhelming probability. Take ε > 0 \varepsilon>0 ε > 0 such that δ + ε < 1 2 \delta+\varepsilon<\frac{1}{2} δ + ε < 2 1 . For each c l ≤ L ≤ 2 l cl\le L\le2l c l ≤ L ≤ 2 l , we let N L = ⌊ n ( δ + ε ) L ⌋ N_L=\lfloor n^{(\delta+\varepsilon)L}\rfloor N L = ⌊ n ( δ + ε ) L ⌋ . Moreover, for each c l ≤ L ≤ 2 l cl\le L\le2l c l ≤ L ≤ 2 l , let W L , 1 , W L , 2 , … W_{L,1},W_{L,2},\ldots W L , 1 , W L , 2 , … be i.i.d. μ ~ l \widetilde{\mu}_l μ l -random words, where W L , j W_{L,j} W L , j is conditioned to have length L L L . We sample G ~ n , δ , l \widetilde{G}_{n,\delta,l} G n , δ , l by first sampling for each 1 ≤ i ≤ N 1\le i\le N 1 ≤ i ≤ N the length L i L_i L i of the word W ~ i \widetilde{W}_i W i , according to the distribution of the lengths induced from μ ~ l \widetilde{\mu}_l μ l . We then take W ~ i \widetilde{W}_i W i to be the first variable from W L i , 1 , W L i , 2 , … W_{L_i,1},W_{L_i,2},\ldots W L i , 1 , W L i , 2 , … which has not been used yet. This defines G ~ n , δ , l \widetilde{G}_{n,\delta,l} G n , δ , l with set of relations R ~ n , δ , l \widetilde{R}_{n,\delta,l} R n , δ , l . We then define
R = { W L , j ∣ c l ≤ L ≤ 2 l , 1 ≤ j ≤ N L } . \mathcal{R}=\{W_{L,j}\mid cl\le L\le2l,\ 1\le j\le N_L\}. R = { W L , j ∣ c l ≤ L ≤ 2 l , 1 ≤ j ≤ N L } .
We note that, by Markov's inequality, for each c l ≤ L ≤ 2 l cl\le L\le2l c l ≤ L ≤ 2 l we have
Pr ( M δ , L ≥ N L ) ≪ n l n − ε L ≤ l n − ε c l , \operatorname{Pr}(M_{\delta,L}\ge N_L)\ll_n l n^{-\varepsilon L}\le l n^{-\varepsilon cl}, Pr ( M δ , L ≥ N L ) ≪ n l n − ε L ≤ l n − ε c l ,
so
Pr ( R ~ n , δ , l ⊈ R ) ≤ ∑ L = ⌈ c l ⌉ 2 l Pr ( M δ , L ≥ N L ) ≪ n l 2 n − ε c l = o l ( 1 ) . \operatorname{Pr}(\widetilde{R}_{n,\delta,l}\nsubseteq\mathcal{R})\le\sum_{L=\lceil cl\rceil}^{2l}\operatorname{Pr}(M_{\delta,L}\ge N_L)\ll_n l^2n^{-\varepsilon cl}=o_l(1). Pr ( R n , δ , l ⊈ R ) ≤ L = ⌈ c l ⌉ ∑ 2 l Pr ( M δ , L ≥ N L ) ≪ n l 2 n − ε c l = o l ( 1 ) .
For each L L L , the set R \mathcal{R} R contains at most N L ≤ n ( δ + ε ) L N_L\le n^{(\delta+\varepsilon)L} N L ≤ n ( δ + ε ) L relations of length L L L . Therefore R \mathcal{R} R satisfies the conditions of Theorem 5.1 with density at most ( δ + ε ) log 2 n n (\delta+ \varepsilon)\log_{2n} n ( δ + ε ) log 2 n n and min { β 2 , β 3 , β 4 } = 1 2 log 2 n n \min\{\beta_2,\beta_3,\beta_4\} = \frac{1}{2}\log_{2n} n min { β 2 , β 3 , β 4 } = 2 1 log 2 n n . Further, with probability 1 − o l ( 1 ) 1-o_l(1) 1 − o l ( 1 ) , the set of relations R ~ n , δ , l \widetilde{\mathcal{R}}_{n,\delta,l} R n , δ , l is a subset of R \mathcal{R} R . Olliviers theorem states simultaneously that all quotients obtained from subfamilies of R \mathcal{R} R are non-elementary hyperbolic. Hence G ~ n , δ , l \widetilde{G}_{n,\delta,l} G n , δ , l , and therefore G n , δ , l G_{n,\delta,l} G n , δ , l is non-elementary hyperbolic with overwhelming probability.
Non-amenability
We now discuss the (non)-amenability of the random semigroup M n , δ , l M_{n,\delta,l} M n , δ , l for any 0 < δ < 1 / 2 0 < \delta< 1/2 0 < δ < 1/2 . Theorem 5.7 shows that the enveloping group G n , δ , l G_{n,\delta,l} G n , δ , l is non-elementary hyperbolic with overwhelming probability, and is thus non-amenable. We use this to prove that M n , δ , l M_{n,\delta,l} M n , δ , l is neither left amenable nor right amenable with overwhelming probability.
To do so, we recall the relevant notions of semigroup amenability. Let M M M be a semigroup, and let ℓ ∞ ( M ) \ell^\infty(M) ℓ ∞ ( M ) denote the space of bounded real-valued functions on M M M . A mean on ℓ ∞ ( M ) \ell^\infty(M) ℓ ∞ ( M ) is a positive linear functional ϕ : ℓ ∞ ( M ) → R \phi:\ell^\infty(M) \to\mathbb{R} ϕ : ℓ ∞ ( M ) → R such that ϕ ( 1 ) = 1 \phi(1)=1 ϕ ( 1 ) = 1 , where 1 1 1 denotes the constant function.
For every a ∈ M a \in M a ∈ M , define the left translation operator L a L_a L a by ( L a f ) ( x ) = f ( a x ) (L_a f)(x)=f(ax) ( L a f ) ( x ) = f ( a x ) . We say that M M M is left amenable if there is a mean ϕ \phi ϕ on ℓ ∞ ( M ) \ell^\infty(M) ℓ ∞ ( M ) such that ϕ ( L a f ) = ϕ ( f ) \phi(L_a f)=\phi(f) ϕ ( L a f ) = ϕ ( f ) for every a ∈ M a \in M a ∈ M and f ∈ ℓ ∞ ( M ) f \in\ell^\infty(M) f ∈ ℓ ∞ ( M ) . Right amenability is defined similarly, using the right translation operators ( R a f ) ( x ) = f ( x a ) (R_a f)(x)=f(xa) ( R a f ) ( x ) = f ( x a ) .
Lemma 5.8. Let M M M be a semigroup, let G G G be a group, and let π : M → G \pi:M \to G π : M → G be a semigroup homomorphism such that π ( M ) \pi(M) π ( M ) generates G G G as a group. Suppose that M M M is left or right amenable. Then G G G is amenable.
Proof. Suppose that M M M is left amenable, and let ϕ \phi ϕ denote a mean on ℓ ∞ ( M ) \ell^\infty(M) ℓ ∞ ( M ) invariant under the left translation operators of M M M . Given f ∈ ℓ ∞ ( G ) f \in\ell^\infty(G) f ∈ ℓ ∞ ( G ) , define ϕ ~ : ℓ ∞ ( G ) → R \widetilde{\phi}:\ell^\infty(G) \to\mathbb{R} ϕ : ℓ ∞ ( G ) → R by ϕ ~ ( f ) = ϕ ( f ∘ π ) \widetilde{\phi}(f)=\phi(f\circ\pi) ϕ ( f ) = ϕ ( f ∘ π ) . Clearly, ϕ ~ \widetilde{\phi} ϕ is a mean on ℓ ∞ ( G ) \ell^\infty(G) ℓ ∞ ( G ) . It is invariant under translation by elements of π ( M ) \pi(M) π ( M ) by the choice of ϕ \phi ϕ . Next, for every g ∈ π ( M ) g \in\pi(M) g ∈ π ( M ) and f ∈ ℓ ∞ ( G ) f \in\ell^\infty(G) f ∈ ℓ ∞ ( G ) , we have
ϕ ~ ( L g − 1 f ) = ϕ ~ ( L g L g − 1 f ) = ϕ ~ ( f ) . \widetilde{\phi}(L_{g^{-1}}f)=\widetilde{\phi}(L_gL_{g^{-1}}f)=\widetilde{\phi}(f). ϕ ( L g − 1 f ) = ϕ ( L g L g − 1 f ) = ϕ ( f ) .
Thus ϕ ~ \widetilde{\phi} ϕ is also invariant under translation by inverses of elements of π ( M ) \pi(M) π ( M ) . Since π ( M ) \pi(M) π ( M ) generates G G G , it follows that ϕ ~ \widetilde{\phi} ϕ is invariant under translation by all elements of G G G . Therefore G G G is amenable. The proof for right amenability is similar.
Combining with the non-amenability of G n , δ , l G_{n,\delta,l} G n , δ , l , we conclude:
Corollary 5.9. For every n ≥ 2 n \ge2 n ≥ 2 and 0 < δ < 1 / 2 0 < \delta< 1/2 0 < δ < 1/2 , the semigroup M n , δ , l M_{n,\delta,l} M n , δ , l is neither left amenable nor right amenable with overwhelming probability.
We also recall the strong Følner conditions. A semigroup M M M satisfies the left strong Følner condition if, for every finite subset H ⊆ M H \subseteq M H ⊆ M and every ε > 0 \varepsilon> 0 ε > 0 , there is a finite nonempty subset F ⊆ M F \subseteq M F ⊆ M such that ∣ F ∖ a F ∣ ≤ ε ∣ F ∣ |F \setminus aF| \le\varepsilon|F| ∣ F ∖ a F ∣ ≤ ε ∣ F ∣ for every a ∈ H a \in H a ∈ H . The right strong Følner condition is defined similarly, using F a Fa F a in place of a F aF a F .
The left (respectively, right) strong Følner condition implies left (respectively, right) amenability (see for instance [3 ] ). Thus, by the preceding corollary, for every n ≥ 2 n \ge2 n ≥ 2 and 0 < δ < 1 / 2 0 < \delta< 1/2 0 < δ < 1/2 , the random semigroup M n , δ , l M_{n,\delta,l} M n , δ , l satisfies neither the left nor the right strong Følner condition with overwhelming probability.
The critical case
We now turn to the critical density case, i.e., δ = 1 2 \delta= \frac{1}{2} δ = 2 1 . We recall that the Erdős–Rényi graph G n , 1 / 2 , l \mathcal{G}_{n,1/2,l} G n , 1/2 , l associated to M n , 1 / 2 , l M_{n,1/2,l} M n , 1/2 , l is the graph with vertex set B n , l B_{n,l} B n , l , where we join two vertices u 1 u_1 u 1 and v 1 v_1 v 1 if u 1 = v 1 u_1 = v_1 u 1 = v 1 appears within the defining relations of M n , 1 / 2 , l M_{n,1/2,l} M n , 1/2 , l . We begin with the following facts:
Fact 6.1. G n , 1 / 2 , l \mathcal{G}_{n,1/2,l} G n , 1/2 , l is a random graph on ∣ B n , l ∣ = n l ( n n − 1 + o l ( 1 ) ) |B_{n,l}| = n^l\left(\frac{n}{n-1}+o_l(1)\right) ∣ B n , l ∣ = n l ( n − 1 n + o l ( 1 ) ) vertices, where we place n l n^l n l edges uniformly at random among all sets of n l n^l n l edges on B n , l B_{n,l} B n , l . The density parameter of G n , 1 / 2 , l \mathcal{G}_{n,1/2,l} G n , 1/2 , l (i.e., the ratio of the number of edges to the number of vertices) is n − 1 n + o l ( 1 ) \frac{n-1}{n}+o_l(1) n n − 1 + o l ( 1 ) .
If n ≥ 3 n \ge3 n ≥ 3 , we have lim l → ∞ ( n − 1 n + o l ( 1 ) ) > 1 2 \lim_{l\to\infty}\left(\frac{n-1}{n}+o_l(1)\right) > \frac{1}{2} lim l → ∞ ( n n − 1 + o l ( 1 ) ) > 2 1 , so there is a giant component in G n , 1 / 2 , l \mathcal{G}_{n,1/2,l} G n , 1/2 , l : There is some constant 0 < c n < 1 0 < c_n < 1 0 < c n < 1 such that G n , 1 / 2 , l \mathcal{G}_{n,1/2,l} G n , 1/2 , l contains a connected component with at least c n ∣ B n , l ∣ c_n|B_{n,l}| c n ∣ B n , l ∣ vertices with high probability as l l l tends to ∞ \infty ∞ . In fact, all other connected components will be substantially smaller, though we do not need this.
We will denote the giant component C n , 1 / 2 , l C_{n,1/2,l} C n , 1/2 , l (and, when it does not exist, take C n , 1 / 2 , l C_{n,1/2,l} C n , 1/2 , l to be the largest connected component of G n , 1 / 2 , l \mathcal{G}_{n,1/2,l} G n , 1/2 , l ). Writing H l = { ∣ C n , 1 / 2 , l ∣ ≥ c n ∣ B n , l ∣ } H_l = \{|C_{n,1/2,l}| \ge c_n|B_{n,l}|\} H l = { ∣ C n , 1/2 , l ∣ ≥ c n ∣ B n , l ∣ } , we have Pr ( H l c ) = o l ( 1 ) \Pr(H_l^c) = o_l(1) Pr ( H l c ) = o l ( 1 ) . By symmetry, Pr ( w ∈ C n , 1 / 2 , l ) ≥ c n Pr ( H l ) \Pr(w \in C_{n,1/2,l}) \ge c_n\Pr(H_l) Pr ( w ∈ C n , 1/2 , l ) ≥ c n Pr ( H l ) for every w ∈ B n , l w \in B_{n,l} w ∈ B n , l , and in fact
Pr ( w 1 , … , w k ∈ C n , 1 / 2 , l ) ≥ ( ⌊ c n ∣ B n , l ∣ ⌋ k ) ( ∣ B n , l ∣ k ) Pr ( H l ) (6) \Pr(w_1,\ldots,w_k \in C_{n,1/2,l}) \ge\frac{\binom{\lfloor c_n|B_{n,l}|\rfloor}{k}}{\binom{|B_{n,l}|}{k}}\Pr(H_l) \tag*{(6)} Pr ( w 1 , … , w k ∈ C n , 1/2 , l ) ≥ ( k ∣ B n , l ∣ ) ( k ⌊ c n ∣ B n , l ∣ ⌋ ) Pr ( H l ) (6) and
Pr ( { w 1 , … , w k ∉ C n , 1 / 2 , l } ∩ H l ) ≤ ( 1 − c n ) k (7) \Pr(\{w_1,\ldots,w_k \notin C_{n,1/2,l}\} \cap H_l) \le(1-c_n)^k \tag*{(7)} Pr ({ w 1 , … , w k ∈ / C n , 1/2 , l } ∩ H l ) ≤ ( 1 − c n ) k (7) for every distinct w 1 , … , w k ∈ B n , l w_1,\ldots,w_k \in B_{n,l} w 1 , … , w k ∈ B n , l .
We remark that when n = 2 n=2 n = 2 , there is no giant component in G 2 , 1 / 2 , l G_{2,1/2,l} G 2 , 1/2 , l . Instead, the largest connected component has size of order ∣ B 2 , l ∣ 2 / 3 |B_{2,l}|^{2/3} ∣ B 2 , l ∣ 2/3 in probability, so the probability that even two generators lie in the same connected component of G 2 , 1 / 2 , l G_{2,1/2,l} G 2 , 1/2 , l tends to 0. However, it is reasonable that one can use the congruence properties to increase G 2 , 1 / 2 , l G_{2,1/2,l} G 2 , 1/2 , l and get a giant component with positive probability.
Using this fact, we prove the following:
Theorem 6.2. For every n ≥ 3 n \ge3 n ≥ 3 , the semigroup M n , 1 / 2 , l M_{n,1/2,l} M n , 1/2 , l is nilpotent with overwhelming probability, and its size is asymptotically tight:
lim K → ∞ lim sup l → ∞ Pr ( ∣ M n , 1 / 2 , l ∣ > K ) = 0. \lim_{K\to\infty}\limsup_{l\to\infty}\Pr\left(\lvert M_{n,1/2,l}\rvert>K\right)=0. K → ∞ lim l → ∞ lim sup Pr ( ∣ M n , 1/2 , l ∣ > K ) = 0.
Proof. We first show that, with overwhelming probability, the element z z z of M n , 1 / 2 , l M_{n,1/2,l} M n , 1/2 , l corresponding to the giant component C n , 1 / 2 , l C_{n,1/2,l} C n , 1/2 , l is an absorbing zero. For each 1 ≤ i ≤ n 1 \le i \le n 1 ≤ i ≤ n , let A i A_i A i denote the event that there exists a word u u u of length l − 1 l-1 l − 1 such that u , x i u ∈ C n , 1 / 2 , l u,x_i u \in C_{n,1/2,l} u , x i u ∈ C n , 1/2 , l . Let X i X_i X i count such words u u u . Conditional on ∣ C n , 1 / 2 , l ∣ = s \lvert C_{n,1/2,l}\rvert=s ∣ C n , 1/2 , l ∣ = s , the vertex set of C n , 1 / 2 , l C_{n,1/2,l} C n , 1/2 , l is uniformly distributed among all subsets of B n , l B_{n,l} B n , l of size s s s , and hence
E [ X i ∣ ∣ C n , 1 / 2 , l ∣ = s ] = n l − 1 s ( s − 1 ) ∣ B n , l ∣ ( ∣ B n , l ∣ − 1 ) . \mathbb{E}\left[X_i \mid\lvert C_{n,1/2,l}\rvert=s\right]
=n^{l-1}\frac{s(s-1)}{\lvert B_{n,l}\rvert(\lvert B_{n,l}\rvert-1)}. E [ X i ∣ ∣ C n , 1/2 , l ∣ = s ] = n l − 1 ∣ B n , l ∣ (∣ B n , l ∣ − 1 ) s ( s − 1 ) .
The pairs { u , x i u } \{u,x_i u\} { u , x i u } are vertex-disjoint, so the indicators of u ∈ C n , 1 / 2 , l u\in C_{n,1/2,l} u ∈ C n , 1/2 , l and x i u ∈ C n , 1 / 2 , l x_i u\in C_{n,1/2,l} x i u ∈ C n , 1/2 , l have non-positive covariance under this conditioning. Therefore
Var ( X i ∣ ∣ C n , 1 / 2 , l ∣ = s ) ≤ E [ X i ∣ ∣ C n , 1 / 2 , l ∣ = s ] . \operatorname{Var}\left(X_i \mid\lvert C_{n,1/2,l}\rvert=s\right)
\le\mathbb{E}\left[X_i \mid\lvert C_{n,1/2,l}\rvert=s\right]. Var ( X i ∣ ∣ C n , 1/2 , l ∣ = s ) ≤ E [ X i ∣ ∣ C n , 1/2 , l ∣ = s ] .
For s ≥ c n ∣ B n , l ∣ s\ge c_n\lvert B_{n,l}\rvert s ≥ c n ∣ B n , l ∣ and sufficiently large l l l , the conditional expectation is at least c n 2 2 n l − 1 \frac{c_n^2}{2}n^{l-1} 2 c n 2 n l − 1 . By Chebyshev’s inequality,
Pr ( A i c ∩ H l ) ≤ 2 c n 2 n l − 1 . \Pr\left(A_i^c\cap H_l\right)\le\frac{2}{c_n^2n^{l-1}}. Pr ( A i c ∩ H l ) ≤ c n 2 n l − 1 2 .
Consequently,
Pr ( A 1 c ∪ ⋯ ∪ A n c ) ≤ Pr ( H l c ) + 2 n c n 2 n l − 1 ⟶ 0. \Pr\left(A_1^c\cup\cdots\cup A_n^c\right)
\le\Pr\left(H_l^c\right)+\frac{2n}{c_n^2n^{l-1}}\longrightarrow0. Pr ( A 1 c ∪ ⋯ ∪ A n c ) ≤ Pr ( H l c ) + c n 2 n l − 1 2 n ⟶ 0.
We therefore have z = x i z z=x_i z z = x i z for every 1 ≤ i ≤ n 1\le i\le n 1 ≤ i ≤ n with overwhelming probability. A similar reasoning shows that z = z x i z=zx_i z = z x i for every 1 ≤ i ≤ n 1\le i\le n 1 ≤ i ≤ n with overwhelming probability, so z z z is an absorbing zero in M n , 1 / 2 , l M_{n,1/2,l} M n , 1/2 , l . We denote this event by Z l Z_l Z l .
We next estimate the probability that every word of length r r r contains a subword which lies in C n , 1 / 2 , l C_{n,1/2,l} C n , 1/2 , l . Fix 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 , and let r ≤ l r\le l r ≤ l be sufficiently large. For each word w w w of length r r r , let B w B_w B w denote the event that w w w has a subword of length between r 2 \frac{r}{2} 2 r and 3 r 4 \frac{3r}{4} 4 3 r which lies in C n , 1 / 2 , l C_{n,1/2,l} C n , 1/2 , l .
Let S 1 S_1 S 1 denote the set of words of length r r r that have at least r 1 − ε r^{1-\varepsilon} r 1 − ε distinct subwords of length ⌊ r 2 ⌋ \lfloor\frac{r}{2}\rfloor ⌊ 2 r ⌋ , and S 2 S_2 S 2 the words of length r r r with fewer than r 1 − ε r^{1-\varepsilon} r 1 − ε such distinct subwords. If w ∈ S 1 w \in S_1 w ∈ S 1 , then w w w has at least 1 2 r 1 − ε \frac{1}{2}r^{1-\varepsilon} 2 1 r 1 − ε distinct subwords of length L L L for any integer r 2 ≤ L ≤ 3 r 4 \frac{r}{2} \leq L \leq\frac{3r}{4} 2 r ≤ L ≤ 4 3 r , since any distinct subword of length ⌊ r 2 ⌋ \lfloor\frac{r}{2}\rfloor ⌊ 2 r ⌋ appears either as a prefix or as a suffix of such a word. Therefore, for sufficiently large r r r , the word w w w has at least 1 16 r 2 − ε \frac{1}{16}r^{2-\varepsilon} 16 1 r 2 − ε distinct subwords of lengths between r 2 \frac{r}{2} 2 r and 3 r 4 \frac{3r}{4} 4 3 r .
By (6.2), for any w ∈ S 1 w \in S_1 w ∈ S 1 ,
Pr ( B w c ∩ H l ) ≤ ( 1 − c n ) r 2 − ε / 16 . \Pr(B_w^c \cap H_l) \leq(1-c_n)^{r^{2-\varepsilon}/16}. Pr ( B w c ∩ H l ) ≤ ( 1 − c n ) r 2 − ε /16 .
If w ∈ S 2 w \in S_2 w ∈ S 2 , then it has at least ⌊ r 4 ⌋ \lfloor\frac{r}{4}\rfloor ⌊ 4 r ⌋ prefixes of lengths between r 2 \frac{r}{2} 2 r and 3 r 4 \frac{3r}{4} 4 3 r , so
Pr ( B w c ∩ H l ) ≤ ( 1 − c n ) ⌊ r / 4 ⌋ . \Pr(B_w^c \cap H_l) \leq(1-c_n)^{\lfloor r/4\rfloor}. Pr ( B w c ∩ H l ) ≤ ( 1 − c n ) ⌊ r /4 ⌋ .
However, by [7 Theorem 4.2] , ∣ S 2 ∣ ≤ exp ( O n ( r 1 − ε ) ) |S_2| \leq\exp(O_n(r^{1-\varepsilon})) ∣ S 2 ∣ ≤ exp ( O n ( r 1 − ε )) . Together we get
Pr ( ⋃ w : ∣ w ∣ = r B w c ) ≤ Pr ( H l c ) + ∣ S 1 ∣ ( 1 − c n ) r 2 − ε / 16 + ∣ S 2 ∣ ( 1 − c n ) ⌊ r / 4 ⌋ ≤ Pr ( H l c ) + n r ( 1 − c n ) r 2 − ε / 16 + exp ( O n ( r 1 − ε ) ) ( 1 − c n ) ⌊ r / 4 ⌋ . \begin{aligned}
\Pr\left(\bigcup_{w:|w|=r} B_w^c\right) \leq\Pr(H_l^c) + |S_1|(1-c_n)^{r^{2-\varepsilon}/16} + |S_2|(1-c_n)^{\lfloor r/4\rfloor} \\
&\leq\Pr(H_l^c) + n^r(1-c_n)^{r^{2-\varepsilon}/16} + \exp(O_n(r^{1-\varepsilon}))(1-c_n)^{\lfloor r/4\rfloor}.
\end{aligned} Pr w : ∣ w ∣ = r ⋃ B w c ≤ Pr ( H l c ) + ∣ S 1 ∣ ( 1 − c n ) r 2 − ε /16 + ∣ S 2 ∣ ( 1 − c n ) ⌊ r /4 ⌋ ≤ Pr ( H l c ) + n r ( 1 − c n ) r 2 − ε /16 + exp ( O n ( r 1 − ε )) ( 1 − c n ) ⌊ r /4 ⌋ .
Taking r = l r=l r = l in the preceding estimate and using Pr ( Z l ) → 1 \Pr(Z_l) \to1 Pr ( Z l ) → 1 , we see that, with overwhelming probability, every word of length l l l equals z z z . Combining this with Pr ( Z l ) → 1 \Pr(Z_l) \to1 Pr ( Z l ) → 1 , we see that, with overwhelming probability, every word of length l l l equals z z z . Since z z z is absorbing, every longer word also equals z z z , so M n , 1 / 2 , l M_{n,1/2,l} M n , 1/2 , l is nilpotent with overwhelming probability.
More generally, on the event Z l ∩ ⋂ w : ∣ w ∣ = r B w Z_l \cap\bigcap_{w:|w|=r} B_w Z l ∩ ⋂ w : ∣ w ∣ = r B w , every word of length at least r r r equals z z z . Therefore ∣ M n , 1 / 2 , l ∣ ≤ 1 + n + ⋯ + n r − 1 |M_{n,1/2,l}| \leq1+n+\cdots+n^{r-1} ∣ M n , 1/2 , l ∣ ≤ 1 + n + ⋯ + n r − 1 . Consequently, for every sufficiently large fixed r r r ,
lim sup l → ∞ Pr ( ∣ M n , 1 / 2 , l ∣ > 1 + n + ⋯ + n r − 1 ) ≤ n r ( 1 − c n ) r 2 − ε / 16 + exp ( O n ( r 1 − ε ) ) ( 1 − c n ) ⌊ r / 4 ⌋ . \begin{aligned}
\limsup_{l\to\infty} \Pr\left(|M_{n,1/2,l}| > 1+n+\cdots+n^{r-1}\right) \\
&\leq n^r(1-c_n)^{r^{2-\varepsilon}/16}+\exp(O_n(r^{1-\varepsilon}))(1-c_n)^{\lfloor r/4\rfloor}.
\end{aligned} l → ∞ lim sup Pr ( ∣ M n , 1/2 , l ∣ > 1 + n + ⋯ + n r − 1 ) ≤ n r ( 1 − c n ) r 2 − ε /16 + exp ( O n ( r 1 − ε )) ( 1 − c n ) ⌊ r /4 ⌋ .
The right-hand side tends to 0 0 0 as r → ∞ r \to\infty r → ∞ , proving that the size of M n , 1 / 2 , l M_{n,1/2,l} M n , 1/2 , l is asymptotically tight. □
Corollary 6.3. With overwhelming probability, the semigroup M n , 1 / 2 , l M_{n,1/2,l} M n , 1/2 , l is finite.
Corollary 6.4. Consider the sequence of distributions of M n , 1 / 2 , l M_{n,1/2,l} M n , 1/2 , l on the set of finitely presented semigroups. Then this sequence has a subsequence of these measures that converges pointwise to a probability measure on finite nilpotent semigroups.
The probability of obtaining the trivial semigroup remains bounded away from zero, as follows directly from the above fact:
Corollary 6.5. For every n ≥ 3 n \ge3 n ≥ 3 ,
lim inf l → ∞ Pr ( M n , 1 / 2 , l is trivial ) > 0. \liminf_{l \to\infty} \Pr(M_{n,1/2,l}\text{ is trivial}) > 0. l → ∞ lim inf Pr ( M n , 1/2 , l is trivial ) > 0. Proof. By (6.1),
lim inf l → ∞ Pr ( x 1 , … , x n , x 1 2 ∈ C n , 1 / 2 , l ) ≥ c n + 1 n n . \liminf_{l \to\infty} \Pr(x_1,\ldots,x_n,x_1^2 \in\mathcal{C}_{n,1/2,l}) \ge\frac{c^{n+1}}{n^n}. l → ∞ lim inf Pr ( x 1 , … , x n , x 1 2 ∈ C n , 1/2 , l ) ≥ n n c n + 1 . This proves the corollary since, if x 1 , … , x n , x 1 2 x_1,\ldots,x_n,x_1^2 x 1 , … , x n , x 1 2 all lie in the same connected component of G n , 1 / 2 , l \mathcal{G}_{n,1/2,l} G n , 1/2 , l , then they are all equal in M n , 1 / 2 , l M_{n,1/2,l} M n , 1/2 , l and so M n , 1 / 2 , l M_{n,1/2,l} M n , 1/2 , l is trivial. □
On the other hand, arbitrarily large finite quotients occur with probabilities bounded away from zero:
Proposition 6.6. For every N ≥ 1 N \ge1 N ≥ 1 ,
lim inf l → ∞ Pr ( M n , 1 / 2 , l has a homomorphic image of size N ) > 0. \liminf_{l \to\infty} \Pr(M_{n,1/2,l}\text{ has a homomorphic image of size }N) > 0. l → ∞ lim inf Pr ( M n , 1/2 , l has a homomorphic image of size N ) > 0. Proof. Fix N ≥ 2 N \ge2 N ≥ 2 , and let t ≥ 2 t \ge2 t ≥ 2 be such that 1 + n + ⋯ + n t − 2 < N ≤ 1 + n + ⋯ + n t − 1 1+n+\cdots+n^{t-2}<N\le1+n+\cdots+n^{t-1} 1 + n + ⋯ + n t − 2 < N ≤ 1 + n + ⋯ + n t − 1 . We claim that
lim inf l → ∞ Pr ( all relation words of M n , 1 / 2 , l are of length at least t ) > 0. (8) \liminf_{l \to\infty} \Pr(\text{all relation words of }M_{n,1/2,l}\text{ are of length at least }t)>0. \tag*{(8)} l → ∞ lim inf Pr ( all relation words of M n , 1/2 , l are of length at least t ) > 0. (8) Once (6.3) is established, the proposition will follow as in the proof of Proposition 4.7.
To prove (6.3), we follow the proof of Proposition 2.2. The number of unordered pairs of elements from B n , l B_{n,l} B n , l is
p = p n , l = ( n + ⋯ + n l 2 ) , p=p_{n,l}=\binom{n+\cdots+n^l}{2}, p = p n , l = ( 2 n + ⋯ + n l ) , whereas the number of unordered pairs of words in B n , l B_{n,l} B n , l of length at least t t t is
q = q n , t , l = ( n t + ⋯ + n l 2 ) . q=q_{n,t,l}=\binom{n^t+\cdots+n^l}{2}. q = q n , t , l = ( 2 n t + ⋯ + n l ) . If A l A_l A l is the event that all words in R n , 1 / 2 , l \mathcal{R}_{n,1/2,l} R n , 1/2 , l have length at least t t t , then
Pr ( A l ) = ( q n l ) ( p n l ) ≥ ( 1 − p − q p − n l ) n l . \Pr(A_l)=\frac{\binom{q}{n^l}}{\binom{p}{n^l}}\ge\left(1-\frac{p-q}{p-n^l}\right)^{n^l}. Pr ( A l ) = ( n l p ) ( n l q ) ≥ ( 1 − p − n l p − q ) n l .
We have
p − q ≤ 2 n 1 + l + t ( n − 1 ) 2 ≤ 8 n l + t − 1 p-q \le\frac{2n^{1+l+t}}{(n-1)^2} \le8n^{l+t-1} p − q ≤ ( n − 1 ) 2 2 n 1 + l + t ≤ 8 n l + t − 1
for all n ≥ 2 n \ge2 n ≥ 2 , and p − n l ≥ d n 2 l p-n^l \ge dn^{2l} p − n l ≥ d n 2 l for some constant d > 0 d>0 d > 0 , hence
Pr ( A l ) ≥ ( 1 − 8 n l + t − 1 d n 2 l ) n l = ( 1 − 8 n t − 1 d n l ) n l → l → ∞ exp ( − 8 d n t − 1 ) . \Pr(A_l) \ge\left(1-\frac{8n^{l+t-1}}{dn^{2l}}\right)^{n^l} = \left(1-\frac{8n^{t-1}}{dn^l}\right)^{n^l} \xrightarrow{l\to\infty} \exp\left(-\frac{8}{d}n^{t-1}\right). Pr ( A l ) ≥ ( 1 − d n 2 l 8 n l + t − 1 ) n l = ( 1 − d n l 8 n t − 1 ) n l l → ∞ exp ( − d 8 n t − 1 ) .
This proves (6.3), and the proposition follows. □
Question 6.7. Corollary 6.4 shows that, after passing to a subsequence, the measures of M n , 1 / 2 , l M_{n,1/2,l} M n , 1/2 , l converge to a probability measure on finite nilpotent semigroups. Corollary 6.5 shows that this limiting measure gives positive mass to the trivial semigroup, while Proposition 6.6 shows that it gives positive mass to semigroups of arbitrarily large sizes. It is therefore natural to ask:
Do the measures of M n , 1 / 2 , l M_{n,1/2,l} M n , 1/2 , l converge pointwise (or in any other sense), without moving to a subsequence?
Which finite semigroups occur in the support of the limiting measure?