betaFeedback

WorksMathematics

Random semigroups á la Gromov

Abstract

We introduce a model of random semigroups analogous to Gromov's density model for random groups. For a fixed number n≥2n\ge 2 of generators and a density parameter δ∈(0,1)δ\in (0,1), we impose a uniformly chosen set of ⌊n2δl⌋\lfloor n^{2δl}\rfloor relations of the form u=vu=v, where u,vu,v are distinct words of length at most ll, and study the resulting semigroup as l→∞l\to\infty. We prove that, with overwhelming probability, above density 1/21/2 the semigroup is trivial, while below density 1/21/2 it contains a free subsemigroup of rank two, has a Golod-Shafarevich semigroup algebra over every field, and has a homomorphic image which generates a non-elementary hyperbolic group. We also show that the small cancellation condition C(m)C(m) holds with overwhelming probability whenever δ<1/2mδ<1/2m. Finally, for n≥3n\ge 3, at critical density 1/21/2 we obtain a subsequential limiting distribution on finite semigroups, with positive mass at the trivial semigroup and unbounded support in size. This contrasts with random groups, which have order at most two with overwhelming probability at critical density.

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≥2n \ge2, and consider the free semigroup Fn=⟨x1,…,xn⟩\mathcal{F}_n = \langle x_1,\ldots,x_n\rangle. For each l≥1l \ge1, we denote by Bn,lB_{n,l} the set of words in Fn\mathcal{F}_n of length at most ll. This set can be thought of as the ball of radius ll in the (undirected) Cayley graph of Fn\mathcal{F}_n, and has size ∣Bn,l∣=n+⋯+nl=nl(nn−1+ol(1))|B_{n,l}| = n + \cdots+ n^l = n^l\left(\frac{n}{n-1} + o_l(1)\right).

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≥2n \ge2 and l≥1l \ge1. Given a density parameter δ∈(0,1)\delta\in(0,1), we pick a uniformly random set of ⌊n2δl⌋\lfloor n^{2\delta l}\rfloor unordered pairs {ui,vi}⊆Bn,l\{u_i,v_i\} \subseteq B_{n,l}, i∈I:={1,…,⌊n2δl⌋}i \in I := \{1,\ldots,\lfloor n^{2\delta l}\rfloor\} and consider the quotient semigroup Mn,δ,l:=Fn/⟨ui=vi∣i∈I⟩M_{n,\delta,l}:=F_n/\langle u_i=v_i\mid i\in I\rangle.

We think of Mn,δ,lM_{n,\delta,l} as a generalized random variable Ω→{Semigroups}\Omega\to\{\text{Semigroups}\} where the probability space Ω\Omega is the collection of all sets of ⌊n2δl⌋\lfloor n^{2\delta l}\rfloor unordered pairs of elements from Bn,lB_{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 ll tends to infinity.

Definition 1.2. Let P\mathcal{P} be a semigroup property. We say that a random semigroup with nn generators and density δ\delta satisfies P\mathcal{P} with overwhelming probability if

lim⁡l→∞Pr⁡(Mn,δ,l satisfies P)=1.\lim_{l\to\infty}\Pr(M_{n,\delta,l}\text{ satisfies }\mathcal{P})=1.

In Gromov’s density model, density δ=12\delta=\frac{1}{2} marks a phase transition: with overwhelming probability, the random group is either trivial or isomorphic to Z/2Z\mathbb{Z}/2\mathbb{Z} when δ>12\delta>\frac{1}{2}, and non-elementary hyperbolic when δ<12\delta<\frac{1}{2} [4, 10]. Further model-theoretic evidence for the largeness of random groups when δ<12\delta<\frac{1}{2} is given in [6]. If one samples freely reduced relators, the group is also trivial or isomorphic to Z/2Z\mathbb{Z}/2\mathbb{Z} with overwhelming probability at the critical density δ=12\delta=\frac{1}{2} [2].

In this work we study the same phase transition for random semigroups. We show in Theorem 2.3 that for density δ>12\delta>\frac{1}{2}, the random semigroup Mn,δ,lM_{n,\delta,l} is trivial with overwhelming probability. Here we do not need to add an exceptional case as Z/2Z\mathbb{Z}/2\mathbb{Z}, which is the case since our relators do not have fixed length.

When δ<12\delta<\frac{1}{2}, we show that Mn,δ,lM_{n,\delta,l} is typically large by showing that the following properties hold with overwhelming probability:

  • Mn,δ,lM_{n,\delta,l} contains nonabelian free semigroups (Proposition 3.2), hence has exponential growth.

  • For any field K\mathbb{K}, the semigroup algebra K[Mn,δ,l]\mathbb{K}[M_{n,\delta,l}] is a filtered Golod-Shafarevich algebra (Proposition 3.5). It then follows that Mn,δ,lM_{n,\delta,l} has a periodic quotient of bounded index with exponential growth (Corollary 3.6).

  • We study small cancellation properties of Mn,δ,lM_{n,\delta,l}, which are defined in an analogous way to the standard small cancellation properties of groups. We show that if δ<12m\delta<\frac{1}{2m}, then Mn,δ,lM_{n,\delta,l} satisfies C(m)C(m) with overwhelming probability (Proposition 4.3).

This allows us to prove that when δ<16\delta< \frac{1}{6}, the semigroup Mn,δ,lM_{n,\delta,l} is residually finite (Corollary 4.6).

  • For any given N≥1N \ge1, the semigroup Mn,δ,lM_{n,\delta,l} has a finite homomorphic image of size NN (Proposition 4.7).

  • Mn,δ,lM_{n,\delta,l} is neither left amenable nor right amenable (Corollary 5.9). In fact, we show that there is a (random) group Gn,δ,lG_{n,\delta,l} and a homomorphism π:Mn,δ,l→Gn,δ,l\pi: M_{n,\delta,l} \to G_{n,\delta,l} such that π(Mn,δ,l)\pi(M_{n,\delta,l}) generates Gn,δ,lG_{n,\delta,l} (as a group), and GG is non-elementary hyperbolic (Theorem 5.7).

Finally, we study the critical case δ=12\delta= \frac{1}{2}. We show that for n≥3n \ge3, the semigroup Mn,1/2,lM_{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: Mn,1/2,lM_{n,1/2,l} is trivial with positive limiting probability (Corollary 6.5), but for every N≥1N \ge1 there is a positive limiting probability that Mn,1/2,lM_{n,1/2,l} has size at least NN (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 Fn=⟨x1,…,xn⟩\mathcal{F}_n = \langle x_1,\ldots,x_n\rangle for the nn-generated free semigroup. We refer to elements of Fn\mathcal{F}_n as words. For a word w∈Fnw \in\mathcal{F}_n, we write ∣w∣|w| for its length with respect to the standard generators of Fn\mathcal{F}_n, which is the homomorphism ∣⋅∣:Fn→N∪{0}|\cdot| : \mathcal{F}_n \to\mathbb{N} \cup\{0\} given by ∣xi∣=1|x_i| = 1 for all 1≤i≤n1 \le i \le 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 XX, we denote by (X2)\binom{X}{2} the set of (unordered) pairs of elements from XX. Given a set of relations R⊆(Fn2)\mathcal{R} \subseteq\binom{\mathcal{F}_n}{2}, we obtain a semigroup presentation ⟨x1,…,xn∣R⟩\langle x_1,\ldots,x_n \mid\mathcal{R}\rangle. Given a relation u=vu = v, we call u,vu,v ‘relation words’.

Let Bn,lB_{n,l} be the set of words in the nn-generated free semigroup, whose length is at most ll. Notice that

∣Bn,l∣=∑i=1lni=nl+1−nn−1=(nn−1+ol(1))⋅nl|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

and

pn,l:=∣(Bn,l2)∣=(n22(n−1)2+ol(1))⋅n2lp_{n,l}:=\left|\binom{B_{n,l}}{2}\right|=\left(\frac{n^2}{2(n-1)^2}+o_l(1)\right)\cdot n^{2l}

We recall the following fact.

Fact 2.1. Let π:Fn↠⟨x1,…,xn∣R⟩\pi:F_n\twoheadrightarrow\langle x_1,\ldots,x_n\mid\mathcal{R}\rangle be the natural projection. For two words w,w′∈⟨x1,…,xn⟩w,w'\in\langle x_1,\ldots,x_n\rangle we have π(w)=π(w′)\pi(w)=\pi(w') if and only if there is a sequence of words w=w0,w1,…,wm=w′w=w_0,w_1,\ldots,w_m=w' in the free semigroup such that each wi+1w_{i+1} is obtained from wiw_i by replacing a subword uu of it by vv, where u=vu=v is among the relation set R\mathcal{R}. In particular, π−1(π(w))={w}\pi^{-1}(\pi(w))=\{w\} if and only if ww contains no relation word as a subword.

References

  1. [1]A. Chorna, Some new properties of random groups in the density and few-relator models. Ph.D. dissertation, CUNY Graduate Center, 2024.
  2. [2]M. Duchin et al., A sharper threshold for random groups at density one-half. Groups Geom. Dyn. 10 (2016), no. 3, 985–1005arxiv.org/abs/1412.8741
  3. [3]R. D. Gray and M. Kambites, Amenability and geometry of semigroups, Trans. Amer. Math. Soc. 369 (2017), no. 11, 8087–8103.arxiv.org/abs/1505.06139
  4. [4]M. Gromov, Asymptotic invariants of infinite groups, in Geometric group theory, Vol. 2 (Sussex, 1991), 1–295, London Math. Soc. Lecture Note Ser., 182, Cambridge Univ. Press, Cambridge.
  5. [5]M. Kambites, Generic complexity of finitely presented monoids and semigroups, Comput. Complexity 20 (2011), no. 1, 21–50.DOI
  6. [6]O. Kharlampovich, A. Miasnikov, R. Sklinos, First-order sentences in random groups II, doi.org/10.48550/arXiv.2507.19740.arxiv.org/abs/2212.11780
  7. [7]M. A. Khrystik, Combinatorics on finite words and the length of a finite-dimensional associative algebra, European J. Combin. 136 (2026), Paper No. 104393, 10 pp.; MR5070045
  8. [8]G. Kozma and A. Lubotzky, Linear representations of random groups. Bull. Math. Sci. 9 (2019), no. 3, 1950016, 12 pp.arxiv.org/abs/1810.01529
  9. [9]S. W. Margolis, J. Meakin, and Z. unik, Distortion functions and the membership problem for submonoids of groups and monoids, Contemporary Mathematics 372 (2005), 109129.DOI
  10. [10]Y. Ollivier, Sharp phase transition theorems for hyperbolicity of random groups, Geom. Funct. Anal. 14, 595–679 (2004). doi.org/10.1007/s00039-004-0470-y
  11. [11]J. H. Remmers, Some algorithmic problems for semigroups: A geometric approach. Ph.D. dissertation, University of Michigan, 1971.DOI

Paper details

vlnc:W_f74t7hb8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 0

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

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents