Introduction
Let p p p be a prime and let F p n \mathbb{F}_p^n F p n be the n n n -dimensional vector space over the finite field F p \mathbb{F}_p F p . An [ n , k , d ] p [n,k,d]_p [ n , k , d ] p linear code is a linear subspace C C C of F p n \mathbb{F}_p^n F p n of dimension k k k and distance d d d ; that is, the Hamming weight of every nonzero vector v ∈ C v \in C v ∈ C is at least d d d . A family of [ n i , k i , d i ] p [n_i,k_i,d_i]_p [ n i , k i , d i ] p codes C i ≤ F p n i C_i \leq\mathbb{F}_p^{n_i} C i ≤ F p n i , where n i ⟶ ∞ n_i \longrightarrow\infty n i ⟶ ∞ , is called (asymptotically) good if there exist δ , ρ > 0 \delta,\rho> 0 δ , ρ > 0 such that d i / n i ≥ δ d_i/n_i \geq\delta d i / n i ≥ δ and k i / n i ≥ ρ k_i/n_i \geq\rho k i / n i ≥ ρ . We call ρ ( C i ) : = k i / n i \rho(C_i) := k_i/n_i ρ ( C i ) := k i / n i the rate of the code and δ ( C i ) : = d i / n i \delta(C_i) := d_i/n_i δ ( C i ) := d i / n i its normalized distance. The basic result of Shannon asserts:
Theorem 1.1 (Shannon). [6 Theorem 11] . There exist good codes.
The second basic result of the theory of error-correcting codes is the Gilbert–Varshamov inequality.
Theorem 1.2 (Gilbert–Varshamov bound). [Gil52, Theorem 1, p. 507] and [8 condition (3), pp. 739–741] . Let 0 < δ < 1 − 1 / p 0 < \delta< 1 - 1/p 0 < δ < 1 − 1/ p and 0 < ρ < 1 − H p ( δ ) 0 < \rho< 1 - H_p(\delta) 0 < ρ < 1 − H p ( δ ) . Then a random linear code in F p n \mathbb{F}_p^n F p n of rate ρ \rho ρ has normalized distance at least δ \delta δ with high probability.
Here, for a real number s > 1 s > 1 s > 1 , we denote the s s s -ary entropy by H s ( δ ) H_s(\delta) H s ( δ ) for 0 < δ < 1 0 < \delta< 1 0 < δ < 1 , where
H s ( δ ) = δ log s ( s − 1 ) − δ log s δ − ( 1 − δ ) log s ( 1 − δ ) . (1) H_s(\delta)=\delta\log_s(s-1)-\delta\log_s\delta-(1-\delta)\log_s(1-\delta). \tag*{(1)} H s ( δ ) = δ log s ( s − 1 ) − δ log s δ − ( 1 − δ ) log s ( 1 − δ ) . (1)
By a random code C C C of rate ρ \rho ρ , we mean that k = ⌊ ρ n ⌋ k=\lfloor\rho n\rfloor k = ⌊ ρ n ⌋ vectors in F p n \mathbb{F}_p^n F p n are chosen independently and uniformly at random and that C C C is the subspace they span. The condition δ < 1 − 1 / p \delta< 1 - 1/p δ < 1 − 1/ p is necessary because of the Plotkin bound.
Theorem 1.3 (Plotkin bound). [5 Theorems 1–2, pp. 446–447] and [GRS25, Theorem 4.4.1]. If C i ≤ F p n i C_i \leq\mathbb{F}_p^{n_i} C i ≤ F p n i , n i ⟶ ∞ n_i \longrightarrow\infty n i ⟶ ∞ , and δ ( C i ) ≥ 1 − 1 / p \delta(C_i) \geq1 - 1/p δ ( C i ) ≥ 1 − 1/ p , then ρ ( C i ) ⟶ 0 \rho(C_i) \longrightarrow0 ρ ( C i ) ⟶ 0 .
In [CDL24], Chapman, Dinur, and the second author established a far-reaching extension of Theorem 1.1. To state it, we first need the following definition.
Definition 1.4. Let G G G be any finitely generated group, let 0 < δ < 1 0 < \delta< 1 0 < δ < 1 , and let A \mathcal{A} A be a finite tuple in G G G , viewed as a multiset. We say that A \mathcal{A} A is δ \delta δ -robust if every submultiset containing more than ( 1 − δ ) ∣ A ∣ (1-\delta)|\mathcal{A}| ( 1 − δ ) ∣ A ∣ of its entries generates G G G . All cardinalities and intersections involving sampled tuples are understood to count multiplicity.
For a finite tuple A \mathcal{A} A in G G G , its detection probability is
δ ( A ; G ) : = inf { 1 − ∣ A ∩ H ∣ ∣ A ∣ : H ≤ G } . \delta(\mathcal{A};G):=\inf\left\{1-\frac{|\mathcal{A}\cap H|}{|\mathcal{A}|}:H\leq G\right\}. δ ( A ; G ) := inf { 1 − ∣ A ∣ ∣ A ∩ H ∣ : H ≤ G } .
Thus A A A is δ \delta δ -robust if and only if δ ( A ; G ) ≥ δ \delta(A;G) \ge\delta δ ( A ; G ) ≥ δ . We write rk ( G ) \operatorname{rk}(G) rk ( G ) for the minimal number of generators of G G G . Chapman, Dinur, and the second author established the following non-commutative analogue of Shannon’s theorem.
Theorem 1.5. [CDL24, Theorem 1.8]. There are absolute constants δ > 0 \delta> 0 δ > 0 and C > 1 C > 1 C > 1 such that every finitely generated group G G G has a δ \delta δ -robust subset of size at most C rk ( G ) C\operatorname{rk}(G) C rk ( G ) .
Theorem 1.1 is a special case of Theorem 1.5. Indeed, apply Theorem 1.5 to G = F p k G = \mathbb{F}_p^k G = F p k to obtain a robust subset A = { α 1 , … , α n } ⊆ F p k A = \{\alpha_1,\ldots,\alpha_n\} \subseteq\mathbb{F}_p^k A = { α 1 , … , α n } ⊆ F p k . Let C C C be the image of the linear map
T : F p k ⟶ F p n , T ( β ) = ( ⟨ β , α 1 ⟩ , … , ⟨ β , α n ⟩ ) . T:\mathbb{F}_p^k \longrightarrow\mathbb{F}_p^n,\qquad T(\beta) = (\langle\beta,\alpha_1\rangle,\ldots,\langle\beta,\alpha_n\rangle). T : F p k ⟶ F p n , T ( β ) = (⟨ β , α 1 ⟩ , … , ⟨ β , α n ⟩) .
Here, for α = ( a 1 , … , a k ) \alpha= (a_1,\ldots,a_k) α = ( a 1 , … , a k ) and β = ( b 1 , … , b k ) \beta= (b_1,\ldots,b_k) β = ( b 1 , … , b k ) , we put ⟨ β , α ⟩ = ∑ j = 1 k a j b j \langle\beta,\alpha\rangle= \sum_{j=1}^{k} a_jb_j ⟨ β , α ⟩ = ∑ j = 1 k a j b j . One easily checks that C = T ( F p k ) ≤ F p n C = T(\mathbb{F}_p^k) \leq\mathbb{F}_p^n C = T ( F p k ) ≤ F p n has dimension k k k and normalized distance at least δ \delta δ . Since n ≤ C k n \leq Ck n ≤ C k , its rate is at least 1 / C 1/C 1/ C .
Every k k k -generated group is a quotient of the free group F k F_k F k of rank k k k , and robustness is preserved under quotients. It therefore suffices to construct robust subsets in F k F_k F k ; such subsets are called universal codes. The goal of this paper is to study random non-commutative codes systematically, and in particular to determine the extent to which an analogue of Theorem 1.2 holds for general groups.
Recall that a random linear code may be obtained from a random k × n k \times n k × n generator matrix, considered in the binary case in [BF02, Section II-C]. Viewing the matrix by columns gives a random n n n -tuple in F p k \mathbb{F}_p^k F p k . This suggests our general model: we ask when a random tuple in a group G G G is robust.
To formalize this model, let G = ( G i ) i ≥ 1 \mathcal{G} = (G_i)_{i\geq1} G = ( G i ) i ≥ 1 be a family of nontrivial finitely generated groups, where each G i G_i G i is equipped with a probability measure P i \mathbb{P}_i P i . For 0 < ρ < 1 0 < \rho< 1 0 < ρ < 1 , put N i ( ρ ) : = ⌈ rk ( G i ) / ρ ⌉ N_i(\rho) := \lceil\operatorname{rk}(G_i)/\rho\rceil N i ( ρ ) := ⌈ rk ( G i ) / ρ ⌉ and let A i ( ρ ) A_i(\rho) A i ( ρ ) be a tuple of N i ( ρ ) N_i(\rho) N i ( ρ ) independent P i \mathbb{P}_i P i -distributed elements of G i G_i G i . We use the same notation P i \mathbb{P}_i P i for the corresponding product measure on such tuples.
Definition 1.6 ((δ , ρ \delta,\rho δ , ρ )-GV family). The family G \mathcal{G} G is a ( δ , ρ ) (\delta,\rho) ( δ , ρ ) -Gilbert–Varshamov family, or a ( δ , ρ ) (\delta,\rho) ( δ , ρ ) -GV family, if
P G ( δ , ρ ) : = lim inf i → ∞ P i [ δ ( A i ( ρ ) ; G i ) ≥ δ ] > 0. \mathbb{P}_{\mathcal{G}}(\delta,\rho) := \liminf_{i\to\infty} \mathbb{P}_i[\delta(A_i(\rho);G_i) \geq\delta] > 0. P G ( δ , ρ ) := i → ∞ lim inf P i [ δ ( A i ( ρ ) ; G i ) ≥ δ ] > 0.
We call G \mathcal{G} G a GV family if this holds for some 0 < δ , ρ < 1 0 < \delta,\rho< 1 0 < δ , ρ < 1 . We call G \mathcal{G} G strong GV if, for every 0 < δ < 1 0 < \delta< 1 0 < δ < 1 , there is some 0 < ρ < 1 0 < \rho< 1 0 < ρ < 1 for which G \mathcal{G} G is ( δ , ρ ) (\delta,\rho) ( δ , ρ ) -GV.
In other words, a GV family admits random robust tuples whose size is proportional to the generating rank, with a success probability bounded away from zero along the family. Being strong GV means that this remains possible for every target normalized distance below 1 1 1 , although the rate may depend on the target distance.
There are two rather different settings. For free groups one must first choose a probability model, and the natural models considered here give a negative answer. For finite groups there is a canonical uniform measure, and the answer is governed by maximal-subgroup growth. These are the two main results of the paper.
Random universal codes
The first result concerns a question suggested in [CDL24, Problem 7.1]. For F k = ⟨ x 1 , … , x k ⟩ F_k = \langle x_1,\ldots,x_k\rangle F k = ⟨ x 1 , … , x k ⟩ and S = { i 1 < ⋯ < i r } ⊆ [ k ] S = \{i_1 < \cdots< i_r\} \subseteq[k] S = { i 1 < ⋯ < i r } ⊆ [ k ] , put x S = x i 1 ⋯ x i r x_S = x_{i_1}\cdots x_{i_r} x S = x i 1 ⋯ x i r and H k : = { x S : S ⊆ [ k ] } \mathcal{H}_k := \{x_S : S \subseteq[k]\} H k := { x S : S ⊆ [ k ]} . As shown in [CDL24, Theorem 3.3 and its proof], this universal Hadamard code has 2 k 2^k 2 k elements and detection probability at least 1 / 2 1/2 1/2 . Thus its normalized distance is bounded away from zero, but its rate k / 2 k k/2^k k / 2 k tends to zero. In the classical abelian Hadamard setting, taking a random linear-size sample produces a good code. It was natural to ask whether the same procedure works for H k \mathcal{H}_k H k .
Theorem 1.7. Let P k \mathbb{P}_k P k be the uniform probability measure on H k \mathcal{H}_k H k . For C > 1 C > 1 C > 1 , let A k ( C ) A_k(C) A k ( C ) be a tuple of ⌈ C k ⌉ \lceil Ck\rceil ⌈ C k ⌉ independent P k \mathbb{P}_k P k -distributed elements of F k F_k F k . Then
P k [ δ ( A k ( C ) ; F k ) = 0 ] → k → ∞ 1. \mathbb{P}_k[\delta(A_k(C);F_k) = 0] \xrightarrow[k\to\infty]{} 1. P k [ δ ( A k ( C ) ; F k ) = 0 ] k → ∞ 1.
In particular, the family ( F k , P k ) k ≥ 1 (F_k,\mathbb{P}_k)_{k\geq1} ( F k , P k ) k ≥ 1 is not GV.
Thus a random linear-size sample from the universal Hadamard code is not a good universal code. This gives a negative answer to the question above, despite the positive normalized distance of the ambient Hadamard code. We obtain the same negative result for a linear-size random sample from word-metric balls; see § 4 .
Random codes in finite groups
For the remainder of this subsection, and throughout § 5 , the groups G i G_i G i are finite and, unless specified otherwise, Π i \Pi_i Π i is the uniform probability measure on G i G_i G i .
To state our results for GV families of finite groups, write q ( G ) q(G) q ( G ) for the smallest index of a proper subgroup of G G G , and put q G : = lim inf i → ∞ q ( G i ) q_{\mathcal{G}} := \liminf_{i\to\infty} q(G_i) q G := lim inf i → ∞ q ( G i ) .
We say that G \mathcal{G} G has uniform polynomial maximal-subgroup growth , or uniform PMSG , if there is a constant A ≥ 0 A \ge0 A ≥ 0 such that, for all sufficiently large i i i and every s ≥ 2 s \ge2 s ≥ 2 , the number of maximal subgroups of index s s s in G i G_i G i is at most s A rk ( G i ) s^{A\operatorname{rk}(G_i)} s A rk ( G i ) . Thus the polynomial exponent is controlled uniformly by the generating rank.
Theorem 1.8 (GV characterization). Let G = ( G i ) i ≥ 1 \mathcal{G}=(G_i)_{i\ge1} G = ( G i ) i ≥ 1 be a family of nontrivial finite groups, and adopt the convention that 1 / q G = 0 1/q_{\mathcal{G}}=0 1/ q G = 0 if q G = ∞ q_{\mathcal{G}}=\infty q G = ∞ . Then the following are equivalent:
The family G \mathcal{G} G is ( δ , ρ ) (\delta,\rho) ( δ , ρ ) -GV for some δ > 0 \delta>0 δ > 0 and 0 < ρ < 1 0<\rho<1 0 < ρ < 1 .
The family G \mathcal{G} G has uniform PMSG.
For every 0 < δ < 1 − 1 / q G 0<\delta<1-1/q_{\mathcal{G}} 0 < δ < 1 − 1/ q G , there exists 0 < ρ < 1 0<\rho<1 0 < ρ < 1 such that G \mathcal{G} G is ( δ , ρ ) (\delta,\rho) ( δ , ρ ) -GV.
This gives a complete group-theoretic characterization, rather than only a sufficient construction. The connection between maximal-subgroup growth and random generation was first observed by Lubotzky [1 ] and studied systematically by Mann [2 ] , who developed the theory of positively finitely generated profinite groups. Mann and Shalev [3 ] proved that positive finite generation is equivalent to polynomial maximal-subgroup growth for profinite groups. Lucchini and Moscatiello [LM20] provide the quantitative input used here.
To state our quantitative results, we record the rate and range of a family and introduce the technical parameters used here. We recall their precise maximal-subgroup definitions in § 5 .
Definition 1.9 (GV rate, range, and family parameters). For 0 < δ < 1 0<\delta<1 0 < δ < 1 , define
R G ( δ ) : = sup { ρ ∈ ( 0 , 1 ) : G is ( δ , ρ ) -GV } , Range ( G ) : = sup { δ ∈ ( 0 , 1 ) : R G ( δ ) > 0 } . R_{\mathcal{G}}(\delta):=\sup\{\rho\in(0,1):\mathcal{G}\text{ is }(\delta,\rho)\text{-GV}\},\qquad\operatorname{Range}(\mathcal{G}):=\sup\{\delta\in(0,1):R_{\mathcal{G}}(\delta)>0\}. R G ( δ ) := sup { ρ ∈ ( 0 , 1 ) : G is ( δ , ρ ) -GV } , Range ( G ) := sup { δ ∈ ( 0 , 1 ) : R G ( δ ) > 0 } .
The supremum of the empty set is understood to be zero. For a nontrivial finite group Γ \Gamma Γ , define, for each s ≥ 2 s\ge2 s ≥ 2 ,
m s ( Γ ) : = # { M < max Γ : [ Γ : M ] = s } , and set M ( Γ ) : = max s ≥ 2 m s ( Γ ) > 0 log m s ( Γ ) log s . m_s(\Gamma):=\#\{M<_{\max}\Gamma:[\Gamma:M]=s\},\text{ and set }\mathcal{M}(\Gamma):=\max_{\substack{s\ge2\\m_s(\Gamma)>0}}\frac{\log m_s(\Gamma)}{\log s}. m s ( Γ ) := # { M < m a x Γ : [ Γ : M ] = s } , and set M ( Γ ) := s ≥ 2 m s ( Γ ) > 0 max log s log m s ( Γ ) .
Put r i : = rk ( G i ) r_i:=\operatorname{rk}(G_i) r i := rk ( G i ) and define
μ G : = max { 1 , lim sup i → ∞ M ( G i ) r i } , rk G : = lim inf i → ∞ r i ∈ N ∪ { ∞ } . \mu_{\mathcal{G}}:=\max\left\{1,\limsup_{i\to\infty}\frac{\mathcal{M}(G_i)}{r_i}\right\},\qquad\operatorname{rk}_{\mathcal{G}}:=\liminf_{i\to\infty}r_i\in\mathbb{N}\cup\{\infty\}. μ G := max { 1 , i → ∞ lim sup r i M ( G i ) } , rk G := i → ∞ lim inf r i ∈ N ∪ { ∞ } .
The parameter μ G \mu_{\mathcal{G}} μ G is the optimal exponent in the uniform PMSG bound: it is the infimum of admissible exponents A ≥ 1 A\ge1 A ≥ 1 for which m s ( G i ) ≤ s A r i m_s(G_i)\le s^{Ar_i} m s ( G i ) ≤ s A r i for every s ≥ 2 s\ge2 s ≥ 2 and all sufficiently large i i i , with μ G = ∞ \mu_{\mathcal{G}}=\infty μ G = ∞ if no such exponent exists. In other words, μ G \mu_{\mathcal{G}} μ G measures the optimal polynomial growth rate of maximal subgroups relative to the generating rank. Thus G \mathcal{G} G has uniform PMSG if and only if μ G < ∞ \mu_{\mathcal{G}}<\infty μ G < ∞ .
For a fixed prime p p p , Theorem 1.2 says that G p : = ( F p k ) k ≥ 1 \mathcal{G}_p:=(\mathbb{F}_p^k)_{k\ge1} G p := ( F p k ) k ≥ 1 is a GV family, while Theorem 1.3 shows that it is not strong GV. In fact,
R G p ( δ ) = { 1 − H p ( δ ) , 0 < δ < 1 − 1 p , 0 , 1 − 1 p ≤ δ < 1 , Range ( G p ) = 1 − 1 p . R_{\mathcal{G}_p}(\delta)=
\begin{cases}
1-H_p(\delta), & 0<\delta<1-\frac{1}{p},\\
0, & 1-\frac{1}{p}\le\delta<1,
\end{cases}
\qquad\operatorname{Range}(\mathcal{G}_p)=1-\frac{1}{p}. R G p ( δ ) = { 1 − H p ( δ ) , 0 , 0 < δ < 1 − p 1 , 1 − p 1 ≤ δ < 1 , Range ( G p ) = 1 − p 1 .
This classical family is the prototype for the finite-group theory developed below.
We also characterize the strong GV property; see Proposition 4.9 . Beyond these qualitative characterizations, we obtain quantitative bounds on the GV rate and determine the optimal distance range in the relevant regimes. The formal parameters and precise statements are given in § 5 , and Table 1 summarizes the resulting characterization, distance ranges, and rate bounds.
Table 1. The GV characterization, distance range, and rate bounds in terms of the family parameters.
Two applications illustrate the characterization. First, every family of nontrivial finite solvable groups has uniform polynomial maximal-subgroup growth and is therefore a GV family. Using [LMM06], we also obtain explicit bounds on the GV rate; See Section 5 for details.
Second, the threshold can be computed exactly for direct powers of a fixed finite simple group H H H . This example includes the classical case. Indeed, if H H H is abelian, then H ≅ C p ≅ ( F p , + ) H\cong C_p\cong(\mathbb{F}_p,+) H ≅ C p ≅ ( F p , + ) for some prime p p p , so H m ≅ F p m H^m\cong\mathbb{F}_p^m H m ≅ F p m and random tuples in H m H^m H m correspond to random generator matrices for p p p -ary linear codes. If H H H is nonabelian, then rk ( H m ) = log ∣ H ∣ m + O ( 1 ) \operatorname{rk}(H^m)=\log_{\lvert H\rvert}m+O(1) rk ( H m ) = log ∣ H ∣ m + O ( 1 ) as m → ∞ m\to\infty m → ∞ ; see [Thé97, Proposition 3.4] and [Wie78, Lemma 2]. Moreover, the smallest index of a proper subgroup of H H H is less than ∣ H ∣ \sqrt{\lvert H\rvert} ∣ H ∣ . Despite these differences, the probabilistic GV rate in both cases is given by the same formula.
Theorem 1.10 (Direct powers of a finite simple group). Let H H H be a fixed finite simple group and let G H = ( H m ) m ≥ 1 \mathcal{G}_H=(H^m)_{m\ge1} G H = ( H m ) m ≥ 1 . For every 0 < δ < 1 0<\delta<1 0 < δ < 1 ,
R G H ( δ ) = { log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ ) ) , 0 < δ < 1 − 1 q ( H ) , 0 , 1 − 1 q ( H ) ≤ δ < 1. Range ( G H ) = 1 − 1 q ( H ) . R_{\mathcal{G}_H}(\delta)=
\begin{cases}
\log_{\lvert H\rvert}q(H)\left(1-H_{q(H)}(\delta)\right), & 0<\delta<1-\frac{1}{q(H)},\\
0, & 1-\frac{1}{q(H)}\le\delta<1.
\end{cases}
\qquad
\operatorname{Range}(\mathcal{G}_H)=1-\frac{1}{q(H)}. R G H ( δ ) = { log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ ) ) , 0 , 0 < δ < 1 − q ( H ) 1 , 1 − q ( H ) 1 ≤ δ < 1. Range ( G H ) = 1 − q ( H ) 1 . For every 0 < δ < 1 − 1 / q ( H ) 0<\delta<1-1/q(H) 0 < δ < 1 − 1/ q ( H ) and every 0 < ρ < 1 0<\rho<1 0 < ρ < 1 ,
P G H ( δ , ρ ) = { 1 , ρ ≤ R G H ( δ ) , 0 , ρ > R G H ( δ ) . P_{\mathcal{G}_H}(\delta,\rho)=
\begin{cases}
1, & \rho\le R_{\mathcal{G}_H}(\delta),\\
0, & \rho>R_{\mathcal{G}_H}(\delta).
\end{cases} P G H ( δ , ρ ) = { 1 , 0 , ρ ≤ R G H ( δ ) , ρ > R G H ( δ ) . Thus direct powers of every finite simple group satisfy the same entropy-based threshold formula as in the abelian case.
The paper is organized as follows. § 3 collects the entropy estimates used throughout. In § 4 we prove the negative results for the universal Hadamard code and word-metric balls in free groups. In § 5 we prove the finite-group characterization and its quantitative refinements. Finally, Section 5 treats direct powers, finite solvable groups, and a family that fails the characterization.
Acknowledgments
The authors thank Michael Chapman for his useful comments on this work. The second author was partially supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 882751, TeStAbility).
The authors acknowledge the use of OpenAI’s ChatGPT to assist with reviewing and refining proofs, editing and proofreading this work, and identifying relevant references. The authors take full responsibility for the mathematical content.
Preliminaries
Lemma 2.1 (Binomial entropy tail). Let s ≥ 2 s \ge2 s ≥ 2 , let 0 < δ ≤ 1 − 1 / s 0 < \delta\le1-1/s 0 < δ ≤ 1 − 1/ s , and, for N ≥ 1 N \ge1 N ≥ 1 , put t N : = ⌈ ( 1 − δ ) N ⌉ + 1 t_N := \lceil(1-\delta)N\rceil+1 t N := ⌈( 1 − δ ) N ⌉ + 1 . If X N ∼ Bin ( N , 1 / s ) X_N \sim\operatorname{Bin}(N,1/s) X N ∼ Bin ( N , 1/ s ) , then
Pr ( X N ≥ t N ) = V s ( N , N − t N ) s N , (2) \Pr(X_N \ge t_N)=\frac{V_s(N,N-t_N)}{s^N}, \tag*{(2)} Pr ( X N ≥ t N ) = s N V s ( N , N − t N ) , (2) where V s ( N , r ) : = ∑ k = 0 r ( N k ) ( s − 1 ) k V_s(N,r):=\sum_{k=0}^{r}\binom{N}{k}(s-1)^k V s ( N , r ) := ∑ k = 0 r ( k N ) ( s − 1 ) k . So,
Pr ( X N ≥ t N ) ≤ s − N ( 1 − H s ( δ ) ) . (3) \Pr(X_N \ge t_N)\le s^{-N(1-H_s(\delta))}. \tag*{(3)} Pr ( X N ≥ t N ) ≤ s − N ( 1 − H s ( δ )) . (3) For fixed s s s and δ \delta δ , the Hamming-ball volume estimate also gives
Pr ( X N ≥ t N ) = s − N ( 1 − H s ( δ ) ) + o ( N ) . (4) \Pr(X_N \ge t_N)=s^{-N(1-H_s(\delta))+o(N)}. \tag*{(4)} Pr ( X N ≥ t N ) = s − N ( 1 − H s ( δ )) + o ( N ) . (4) For fixed s s s and 0 < δ < 1 − 1 / s 0<\delta<1-1/s 0 < δ < 1 − 1/ s , there is a constant C s , δ > 0 C_{s,\delta}>0 C s , δ > 0 such that, for all sufficiently large N N N ,
Pr ( X N ≥ t N ) ≤ C s , δ N − 1 / 2 s − N ( 1 − H s ( δ ) ) . (5) \Pr(X_N \ge t_N)\le C_{s,\delta}N^{-1/2}s^{-N(1-H_s(\delta))}. \tag*{(5)} Pr ( X N ≥ t N ) ≤ C s , δ N − 1/2 s − N ( 1 − H s ( δ )) . (5)
Proof. Using the change of variables k = N − j k=N-j k = N − j , we obtain
Pr ( X N ≥ t N ) = ∑ j = t N N ( N j ) ( 1 s ) j ( 1 − 1 s ) N − j = 1 s N ∑ k = 0 N − t N ( N k ) ( s − 1 ) k = V s ( N , N − t N ) s N . \Pr(X_N\ge t_N)=\sum_{j=t_N}^{N}\binom{N}{j}\left(\frac{1}{s}\right)^j\left(1-\frac{1}{s}\right)^{N-j}
=\frac{1}{s^N}\sum_{k=0}^{N-t_N}\binom{N}{k}(s-1)^k
=\frac{V_s(N,N-t_N)}{s^N}. Pr ( X N ≥ t N ) = j = t N ∑ N ( j N ) ( s 1 ) j ( 1 − s 1 ) N − j = s N 1 k = 0 ∑ N − t N ( k N ) ( s − 1 ) k = s N V s ( N , N − t N ) .
Since N − t N = N − ⌈ ( 1 − δ ) N ⌉ − 1 = ⌊ δ N ⌋ − 1 N-t_N=N-\lceil(1-\delta)N\rceil-1=\lfloor\delta N\rfloor-1 N − t N = N − ⌈( 1 − δ ) N ⌉ − 1 = ⌊ δ N ⌋ − 1 , the standard estimates for the volume of a Hamming ball [GRS25, Proposition 3.3.3] give V s ( N , N − t N ) ≤ s N H s ( δ ) V_s(N,N-t_N)\le s^{NH_s(\delta)} V s ( N , N − t N ) ≤ s N H s ( δ ) and, for fixed s s s and 0 < δ ≤ 1 − 1 / s 0<\delta\le1-1/s 0 < δ ≤ 1 − 1/ s , V s ( N , N − t N ) = s N H s ( δ ) + o ( N ) V_s(N,N-t_N)=s^{NH_s(\delta)+o(N)} V s ( N , N − t N ) = s N H s ( δ ) + o ( N ) . Substitution into (2) proves (3) and (4) .
For (5) , set Y N : = N − X N ∼ Bin ( N , 1 − 1 / s ) Y_N:=N-X_N\sim\operatorname{Bin}(N,1-1/s) Y N := N − X N ∼ Bin ( N , 1 − 1/ s ) and k N : = N − t N = ⌊ δ N ⌋ − 1 k_N:=N-t_N=\lfloor\delta N\rfloor-1 k N := N − t N = ⌊ δ N ⌋ − 1 , and put f N : = k N / N f_N:=k_N/N f N := k N / N and p : = 1 − 1 / s p:=1-1/s p := 1 − 1/ s . Proposition 5.5, Eq. (113) of [ZLH22] gives
Pr ( Y N ≤ k N ) < ( 1 − f N ) p 2 π N f N ( 1 − f N ) ( p − f N ) exp ( − N D ( f N ∥ p ) ) , \Pr(Y_N\le k_N)<\frac{(1-f_N)p}{\sqrt{2\pi Nf_N(1-f_N)(p-f_N)}}\exp(-ND(f_N\mathbin{\|}p)), Pr ( Y N ≤ k N ) < 2 π N f N ( 1 − f N ) ( p − f N ) ( 1 − f N ) p exp ( − N D ( f N ∥ p )) ,
where D ( f ∥ p ) = f ln ( f / p ) + ( 1 − f ) ln ( ( 1 − f ) / ( 1 − p ) ) D(f\mathbin{\|}p)=f\ln(f/p)+(1-f)\ln((1-f)/(1-p)) D ( f ∥ p ) = f ln ( f / p ) + ( 1 − f ) ln (( 1 − f ) / ( 1 − p )) is the binary relative entropy used in that paper. For all sufficiently large N N N , 0 < f N ≤ δ < p 0<f_N\le\delta<p 0 < f N ≤ δ < p , so we have D ( f N ∥ p ) ≥ D ( δ ∥ p ) D(f_N\mathbin{\|}p)\ge D(\delta\mathbin{\|}p) D ( f N ∥ p ) ≥ D ( δ ∥ p ) : indeed, d d f D ( f ∥ p ) = ln f ( 1 − p ) p ( 1 − f ) < 0 \frac{d}{df}D(f\mathbin{\|}p)=\ln\frac{f(1-p)}{p(1-f)}<0 df d D ( f ∥ p ) = ln p ( 1 − f ) f ( 1 − p ) < 0 for f < p f<p f < p . Also, since f N → δ f_N\to\delta f N → δ , the coefficient apart from N − 1 / 2 N^{-1/2} N − 1/2 is bounded. To rewrite the exponent, the definition of D D D gives
D ( δ ∥ 1 − 1 / s ) = ln s + δ ln δ − δ ln ( s − 1 ) + ( 1 − δ ) ln ( 1 − δ ) = ln s ( 1 − H s ( δ ) ) , D(\delta\mathbin{\|}1-1/s)=\ln s+\delta\ln\delta-\delta\ln(s-1)+(1-\delta)\ln(1-\delta)=\ln s\left(1-H_s(\delta)\right), D ( δ ∥ 1 − 1/ s ) = ln s + δ ln δ − δ ln ( s − 1 ) + ( 1 − δ ) ln ( 1 − δ ) = ln s ( 1 − H s ( δ ) ) ,
where the last equality follows from (1) . Therefore exp ( − N D ( f N ∥ p ) ) ≤ s − N ( 1 − H s ( δ ) ) \exp(-ND(f_N\mathbin{\|}p))\le s^{-N(1-H_s(\delta))} exp ( − N D ( f N ∥ p )) ≤ s − N ( 1 − H s ( δ )) . Together with the bounded prefactor above, this proves (5) . □
The next observation allows us to replace the entropy associated with an arbitrary subgroup index by the entropy at the smallest possible index. This will be used repeatedly in the later union bounds.
Lemma 2.2 (Entropy monotonicity). Let q ≥ 2 q\ge2 q ≥ 2 and 0 < δ ≤ 1 − 1 / q 0<\delta\le1-1/q 0 < δ ≤ 1 − 1/ q . Then H s ( δ ) ≤ H q ( δ ) H_s(\delta)\le H_q(\delta) H s ( δ ) ≤ H q ( δ ) for every real s ≥ q s\ge q s ≥ q ; for integer s s s , this inequality is also stated in [GRS25, Exercise 3.6].
Proof. Write h ( x ) = − x ln x − ( 1 − x ) ln ( 1 − x ) h(x)=-x\ln x-(1-x)\ln(1-x) h ( x ) = − x ln x − ( 1 − x ) ln ( 1 − x ) . For real u ≥ q u\ge q u ≥ q , set
F ( u ) : = H u ( δ ) = h ( δ ) + δ ln ( u − 1 ) ln u . F(u):=H_u(\delta)=\frac{h(\delta)+\delta\ln(u-1)}{\ln u}. F ( u ) := H u ( δ ) = ln u h ( δ ) + δ ln ( u − 1 ) .
Differentiation gives
F ′ ( u ) = δ u ( ln u ) 2 ( h ( 1 − 1 / u ) 1 − 1 / u − h ( δ ) δ ) . F'(u)=\frac{\delta}{u(\ln u)^2}\left(\frac{h(1-1/u)}{1-1/u}-\frac{h(\delta)}{\delta}\right). F ′ ( u ) = u ( ln u ) 2 δ ( 1 − 1/ u h ( 1 − 1/ u ) − δ h ( δ ) ) .
Since ( h ( x ) / x ) ′ = ln ( 1 − x ) / x 2 < 0 (h(x)/x)'=\ln(1-x)/x^2<0 ( h ( x ) / x ) ′ = ln ( 1 − x ) / x 2 < 0 on ( 0 , 1 ) (0,1) ( 0 , 1 ) and δ ≤ 1 − 1 / q ≤ 1 − 1 / u \delta\le1-1/q\le1-1/u δ ≤ 1 − 1/ q ≤ 1 − 1/ u , the term in parentheses is nonpositive. Thus F F F is nonincreasing for u ≥ q u\ge q u ≥ q , proving the claim. □
Random Universal Codes
We begin by proving Theorem 1.7, which says that choosing a linear number of random elements from the Hadamard code does not give rise to a good code.
Theorem 3.1. For each k k k , let P k \mathbb{P}_k P k be the uniform probability measure on H k \mathcal{H}_k H k (the universal Hadamard code as defined in § 1.1 ). For C > 1 C > 1 C > 1 , put N k ( C ) : = ⌈ C k ⌉ N_k(C) := \lceil Ck\rceil N k ( C ) := ⌈ C k ⌉ , and let A k ( C ) A_k(C) A k ( C ) consist of N k ( C ) N_k(C) N k ( C ) independent P k \mathbb{P}_k P k -distributed elements of F k F_k F k . Then
P [ A k ( C ) freely generates a free subgroup of rank N k ( C ) ] → k → ∞ 1. \mathbb{P}\left[A_k(C)\text{ freely generates a free subgroup of rank }N_k(C)\right] \xrightarrow[k\to\infty]{} 1. P [ A k ( C ) freely generates a free subgroup of rank N k ( C ) ] k → ∞ 1. Consequently, in the terminology of Definition 1.6, for G = ( F k , P k ) k ≥ 1 \mathcal{G} = (F_k,\mathbb{P}_k)_{k\geq1} G = ( F k , P k ) k ≥ 1 , P G ( δ , 1 / C ) = 0 \mathbb{P}_{\mathcal{G}}(\delta,1/C) = 0 P G ( δ , 1/ C ) = 0 for every 0 < δ < 1 0 < \delta< 1 0 < δ < 1 . In particular, G \mathcal{G} G is not a ( δ , ρ ) (\delta,\rho) ( δ , ρ ) -GV family for any 0 < δ , ρ < 1 0 < \delta,\rho< 1 0 < δ , ρ < 1 .
The mechanism behind this negative result is that a typical tuple freely generates the subgroup it spans. We isolate the combinatorial condition used to prove this freeness.
Definition 3.2 (Central tree property). Let u = ( u 1 , … , u N ) \mathbf{u} = (u_1,\ldots,u_N) u = ( u 1 , … , u N ) be a tuple of nontrivial reduced words, and write u ± 1 : = ( u 1 , u 1 − 1 , … , u N , u N − 1 ) \mathbf{u}^{\pm1} := (u_1,u_1^{-1},\ldots,u_N,u_N^{-1}) u ± 1 := ( u 1 , u 1 − 1 , … , u N , u N − 1 ) . Let lcp ( u ± 1 ) \operatorname{lcp}(\mathbf{u}^{\pm1}) lcp ( u ± 1 ) be the maximum length of a common prefix of two distinct words in u ± 1 \mathbf{u}^{\pm1} u ± 1 , and set min ( u ) : = min 1 ≤ i ≤ N ∣ u i ∣ \min(\mathbf{u}) := \min_{1\leq i\leq N}|u_i| min ( u ) := min 1 ≤ i ≤ N ∣ u i ∣ . We say that u \mathbf{u} u has the central tree property if
2 lcp ( u ± 1 ) < min ( u ) . 2\operatorname{lcp}(\mathbf{u}^{\pm1}) < \min(\mathbf{u}). 2 lcp ( u ± 1 ) < min ( u ) .
The relevance of the central tree property is that it prevents excessive cancellation between consecutive words, and therefore forces freeness.
Lemma 3.3 (Central tree property). If a tuple u = ( u 1 , … , u N ) \mathbf{u} = (u_1,\ldots,u_N) u = ( u 1 , … , u N ) has the central tree property, then it is a free basis of the subgroup ⟨ u 1 , … , u N ⟩ \langle u_1,\ldots,u_N\rangle ⟨ u 1 , … , u N ⟩ .
Proof. Set L : = lcp ( u ± 1 ) L := \operatorname{lcp}(\mathbf{u}^{\pm1}) L := lcp ( u ± 1 ) and m : = min ( u ) m := \min(\mathbf{u}) m := min ( u ) . Let v , w ∈ u ± 1 v,w \in\mathbf{u}^{\pm1} v , w ∈ u ± 1 with v w ≠ 1 vw \ne1 v w = 1 . The cancellation in v w vw v w is the length of the common prefix of v − 1 v^{-1} v − 1 and w w w , and is therefore at most L L L . Hence
∣ v w ∣ ≥ ∣ v ∣ + ∣ w ∣ − 2 L > max { ∣ v ∣ , ∣ w ∣ } , |vw| \geq|v| + |w| - 2L > \max\{|v|,|w|\}, ∣ v w ∣ ≥ ∣ v ∣ + ∣ w ∣ − 2 L > max { ∣ v ∣ , ∣ w ∣ } ,
where the strict inequality follows from 2 L < m ≤ min { ∣ v ∣ , ∣ w ∣ } 2L < m \leq\min\{|v|,|w|\} 2 L < m ≤ min { ∣ v ∣ , ∣ w ∣ } .
Similarly, let v , w , z ∈ u ± 1 v,w,z \in\mathbf{u}^{\pm1} v , w , z ∈ u ± 1 with v w ≠ 1 vw \ne1 v w = 1 and w z ≠ 1 wz \ne1 w z = 1 . At most L L L letters cancel at each of the two junctions. Since ∣ w ∣ ≥ m > 2 L |w| \geq m > 2L ∣ w ∣ ≥ m > 2 L , these cancellations cannot remove the entire middle word, and therefore
∣ v w z ∣ ≥ ∣ v ∣ + ∣ w ∣ + ∣ z ∣ − 4 L > ∣ v ∣ − ∣ w ∣ + ∣ z ∣ . |vwz| \geq|v| + |w| + |z| - 4L > |v| - |w| + |z|. ∣ v w z ∣ ≥ ∣ v ∣ + ∣ w ∣ + ∣ z ∣ − 4 L > ∣ v ∣ − ∣ w ∣ + ∣ z ∣.
Together with the assumption that the u i u_i u i are nontrivial, these are precisely the Nielsen reduction conditions. Thus u \mathbf{u} u is Nielsen reduced, and a Nielsen-reduced tuple is a free basis of the subgroup it generates; see [LS77, Chapter I, Section 2]. The conclusion also follows directly from [BNW16, Proposition 1.2]. □
For a random Hadamard tuple, it therefore remains to control the individual word lengths and the overlaps between pairs of signed words. The following estimate supplies the required overlap bound.
Lemma 3.4 (Common prefixes and suffixes). Let S , T ⊆ [ k ] S,T\subseteq[k] S , T ⊆ [ k ] be independent and uniformly distributed. Then, for every L ≥ 1 L\geq1 L ≥ 1 and every ε , η ∈ { ± 1 } \varepsilon,\eta\in\{\pm1\} ε , η ∈ { ± 1 } ,
P [ lcp ( x S ε , x T η ) ≥ L ] ≤ 3 − L . \mathbb{P}\left[\operatorname{lcp}(x_S^\varepsilon,x_T^\eta)\geq L\right]\leq3^{-L}. P [ lcp ( x S ε , x T η ) ≥ L ] ≤ 3 − L .
Proof. Let S , T ⊆ [ k ] S,T\subseteq[k] S , T ⊆ [ k ] be independent and uniformly distributed random subsets, and fix A = { a 1 < ⋯ < a r } ⊆ [ k ] A=\{a_1<\cdots<a_r\}\subseteq[k] A = { a 1 < ⋯ < a r } ⊆ [ k ] . Fix a ℓ ∈ A a_\ell\in A a ℓ ∈ A . Write
E ℓ : = ⋂ x ∈ A ∖ { a ℓ } { x ∈ S ∪ T } ∩ ⋂ x ∈ [ k ] ∖ A { x ∉ S ∪ T } . E_\ell:= \bigcap_{x\in A\setminus\{a_\ell\}}\{x\in S\cup T\}\cap\bigcap_{x\in[k]\setminus A}\{x\notin S\cup T\}. E ℓ := x ∈ A ∖ { a ℓ } ⋂ { x ∈ S ∪ T } ∩ x ∈ [ k ] ∖ A ⋂ { x ∈ / S ∪ T } .
Then
{ S ∪ T = A } = { a ℓ ∈ S ∪ T } ∩ E ℓ . \{S\cup T=A\}=\{a_\ell\in S\cup T\}\cap E_\ell. { S ∪ T = A } = { a ℓ ∈ S ∪ T } ∩ E ℓ .
The event E ℓ E_\ell E ℓ depends only on the membership choices at elements x ≠ a ℓ x\ne a_\ell x = a ℓ , and is therefore independent of the membership choices at a ℓ a_\ell a ℓ . Consequently,
P [ a ℓ ∈ S ∩ T ∣ S ∪ T = A ] = P [ a ℓ ∈ S ∩ T , E ℓ ] P [ a ℓ ∈ S ∪ T , E ℓ ] = P [ a ℓ ∈ S ∩ T ] P [ E ℓ ] P [ a ℓ ∈ S ∪ T ] P [ E ℓ ] = P [ a ℓ ∈ S ∩ T ] P [ a ℓ ∈ S ∪ T ] . \mathbb{P}[a_\ell\in S\cap T\mid S\cup T=A]
=\frac{\mathbb{P}[a_\ell\in S\cap T,E_\ell]}{\mathbb{P}[a_\ell\in S\cup T,E_\ell]}
=\frac{\mathbb{P}[a_\ell\in S\cap T]\mathbb{P}[E_\ell]}{\mathbb{P}[a_\ell\in S\cup T]\mathbb{P}[E_\ell]}
=\frac{\mathbb{P}[a_\ell\in S\cap T]}{\mathbb{P}[a_\ell\in S\cup T]}. P [ a ℓ ∈ S ∩ T ∣ S ∪ T = A ] = P [ a ℓ ∈ S ∪ T , E ℓ ] P [ a ℓ ∈ S ∩ T , E ℓ ] = P [ a ℓ ∈ S ∪ T ] P [ E ℓ ] P [ a ℓ ∈ S ∩ T ] P [ E ℓ ] = P [ a ℓ ∈ S ∪ T ] P [ a ℓ ∈ S ∩ T ] .
Since P [ a ℓ ∈ S ∩ T ] = 1 / 4 \mathbb{P}[a_\ell\in S \cap T] = 1/4 P [ a ℓ ∈ S ∩ T ] = 1/4 and P [ a ℓ ∈ S ∪ T ] = 3 / 4 \mathbb{P}[a_\ell\in S \cup T] = 3/4 P [ a ℓ ∈ S ∪ T ] = 3/4 , we obtain P [ a ℓ ∈ S ∩ T ∣ S ∪ T = A ] = 1 / 3 \mathbb{P}[a_\ell\in S \cap T \mid S \cup T = A] = 1/3 P [ a ℓ ∈ S ∩ T ∣ S ∪ T = A ] = 1/3 . If r ≥ L r \ge L r ≥ L , then lcp ( x S , x T ) ≥ L \operatorname{lcp}(x_S,x_T) \ge L lcp ( x S , x T ) ≥ L precisely when a 1 , … , a L ∈ S ∩ T a_1,\ldots,a_L \in S \cap T a 1 , … , a L ∈ S ∩ T , while if r < L r < L r < L this event is impossible. Conditioned on S ∪ T = A S \cup T = A S ∪ T = A , these membership choices are independent for the different elements of A A A . Hence, for every A ⊆ [ k ] A \subseteq[k] A ⊆ [ k ] ,
P [ lcp ( x S , x T ) ≥ L ∣ S ∪ T = A ] ≤ 3 − L . \mathbb{P}[\operatorname{lcp}(x_S,x_T) \ge L \mid S \cup T = A] \le3^{-L}. P [ lcp ( x S , x T ) ≥ L ∣ S ∪ T = A ] ≤ 3 − L .
Therefore
P [ lcp ( x S , x T ) ≥ L ] = ∑ A P [ S ∪ T = A ] P [ lcp ( x S , x T ) ≥ L ∣ S ∪ T = A ] ≤ 3 − L ∑ A P [ S ∪ T = A ] = 3 − L . \mathbb{P}[\operatorname{lcp}(x_S,x_T) \ge L] = \sum_A \mathbb{P}[S \cup T = A]\mathbb{P}[\operatorname{lcp}(x_S,x_T) \ge L \mid S \cup T = A] \le3^{-L}\sum_A \mathbb{P}[S \cup T = A] = 3^{-L}. P [ lcp ( x S , x T ) ≥ L ] = A ∑ P [ S ∪ T = A ] P [ lcp ( x S , x T ) ≥ L ∣ S ∪ T = A ] ≤ 3 − L A ∑ P [ S ∪ T = A ] = 3 − L .
The same argument applied to the last L L L elements of S ∪ T S \cup T S ∪ T gives P [ lcp ( x S − 1 , x T − 1 ) ≥ L ] ≤ 3 − L \mathbb{P}[\operatorname{lcp}(x_{S}^{-1},x_{T}^{-1}) \ge L] \le3^{-L} P [ lcp ( x S − 1 , x T − 1 ) ≥ L ] ≤ 3 − L . Moreover, for every B ⊆ [ k ] B \subseteq[k] B ⊆ [ k ] , the words x B x_B x B and x B ∓ 1 x_{B}^{\mp1} x B ∓ 1 contain letters with opposite signs, and hence P [ lcp ( x B ± 1 , x T ∓ 1 ) ≥ L ] = 0 ≤ 3 − L \mathbb{P}[\operatorname{lcp}(x_{B}^{\pm1},x_{T}^{\mp1}) \ge L] = 0 \le3^{-L} P [ lcp ( x B ± 1 , x T ∓ 1 ) ≥ L ] = 0 ≤ 3 − L .
Proof of Theorem 3.1 . Put N : = N k ( C ) N := N_k(C) N := N k ( C ) , write A k : = A k ( C ) = ( u 1 , … , u N ) A_k := A_k(C) = (u_1,\ldots,u_N) A k := A k ( C ) = ( u 1 , … , u N ) , and set L : = ⌈ 4 log 3 k ⌉ L := \lceil4\log_3 k\rceil L := ⌈ 4 log 3 k ⌉ . Since ∣ u j ∣ ∼ Bin ( k , 1 / 2 ) |u_j| \sim\operatorname{Bin}(k,1/2) ∣ u j ∣ ∼ Bin ( k , 1/2 ) and E [ ∣ u j ∣ ] = k / 2 \mathbb{E}[|u_j|] = k/2 E [ ∣ u j ∣ ] = k /2 , the lower-tail Chernoff bound [4 Theorem 4.5(2)] , followed by a union bound, gives
P [ min 1 ≤ j ≤ N ∣ u j ∣ < k 3 ] ≤ ∑ j = 1 N P [ ∣ u j ∣ < ( 1 − 1 3 ) k 2 ] ≤ N exp ( − ( 1 / 3 ) 2 ( k / 2 ) 2 ) = N e − k / 36 . \mathbb{P}\left[\min_{1\le j\le N}|u_j| < \frac{k}{3}\right] \le\sum_{j=1}^{N}\mathbb{P}\left[|u_j| < \left(1-\frac{1}{3}\right)\frac{k}{2}\right] \le N\exp\left(-\frac{(1/3)^2(k/2)}{2}\right) = Ne^{-k/36}. P [ 1 ≤ j ≤ N min ∣ u j ∣ < 3 k ] ≤ j = 1 ∑ N P [ ∣ u j ∣ < ( 1 − 3 1 ) 2 k ] ≤ N exp ( − 2 ( 1/3 ) 2 ( k /2 ) ) = N e − k /36 .
Moreover, by Lemma 3.4 ,
P [ lcp ( A k ± 1 ) ≥ L ] = P [ ∃ 1 ≤ i < j ≤ N , ε , η ∈ { ± 1 } : lcp ( u i ε , u j η ) ≥ L ] ≤ ∑ 1 ≤ i < j ≤ N ∑ ε , η ∈ { ± 1 } P [ lcp ( u i ε , u j η ) ≥ L ] ≤ 2 ( N 2 ) 3 − L ≤ 2 ( N 2 ) k − 4 . \begin{aligned}
\mathbb{P}[\operatorname{lcp}(A_k^{\pm1}) \ge L] = \mathbb{P}\left[\exists\,1\le i<j\le N,\ \varepsilon,\eta\in\{\pm1\}:\operatorname{lcp}(u_i^\varepsilon,u_j^\eta)\ge L\right] \\
&\le\sum_{1\le i<j\le N}\sum_{\varepsilon,\eta\in\{\pm1\}}\mathbb{P}[\operatorname{lcp}(u_i^\varepsilon,u_j^\eta)\ge L] \le2\binom{N}{2}3^{-L}\le2\binom{N}{2}k^{-4}.
\end{aligned} P [ lcp ( A k ± 1 ) ≥ L ] = P [ ∃ 1 ≤ i < j ≤ N , ε , η ∈ { ± 1 } : lcp ( u i ε , u j η ) ≥ L ] ≤ 1 ≤ i < j ≤ N ∑ ε , η ∈ { ± 1 } ∑ P [ lcp ( u i ε , u j η ) ≥ L ] ≤ 2 ( 2 N ) 3 − L ≤ 2 ( 2 N ) k − 4 .
Therefore, with probability at least 1 − N e − k / 36 − 2 ( N 2 ) k − 4 1-Ne^{-k/36}-2\binom{N}{2}k^{-4} 1 − N e − k /36 − 2 ( 2 N ) k − 4 , every u j u_j u j has length at least k / 3 k/3 k /3 , while all common prefixes of distinct words in { u 1 ± 1 , … , u N ± 1 } \{u_1^{\pm1},\ldots,u_N^{\pm1}\} { u 1 ± 1 , … , u N ± 1 } have length less than L L L . Indeed, overlaps are controlled by lcp \operatorname{lcp} lcp , and opposite-sign words have no common prefix.
For sufficiently large k k k , we have k / 3 > 2 L k/3 > 2L k /3 > 2 L . Hence ( u 1 , … , u N ) (u_1,\ldots,u_N) ( u 1 , … , u N ) satisfies the central tree property and therefore, by Lemma 3.3 , freely generates a free subgroup of rank N N N . Since N = ⌈ C k ⌉ > k N=\lceil Ck\rceil> k N = ⌈ C k ⌉ > k , this subgroup cannot equal F k F_k F k . Thus ⟨ A k ⟩ ≠ F k \langle A_k\rangle\ne F_k ⟨ A k ⟩ = F k and δ ( A k ; F k ) = 0 \delta(A_k;F_k)=0 δ ( A k ; F k ) = 0 . Finally, since N ≤ ( C + 1 ) k N\le(C+1)k N ≤ ( C + 1 ) k ,
P [ δ ( A k ; F k ) = 0 ] ≥ 1 − ( C + 1 ) k e − k / 36 − ( C + 1 ) 2 k 2 → k → ∞ 1. \mathbb{P}[\delta(A_k;F_k)=0]\ge1-(C+1)ke^{-k/36}-\frac{(C+1)^2}{k^2}\xrightarrow{k\to\infty}1. P [ δ ( A k ; F k ) = 0 ] ≥ 1 − ( C + 1 ) k e − k /36 − k 2 ( C + 1 ) 2 k → ∞ 1.
Similarly, sampling a linear number of elements uniformly from word-metric balls of radius at least 7 in F k F_k F k does not produce good codes. Here and below, B F k ( R ) B_{F_k}(R) B F k ( R ) denotes the radius-R R R ball in the word metric associated with the standard free generating set { x 1 , … , x k } \{x_1,\ldots,x_k\} { x 1 , … , x k } .
Theorem 3.5. Let ( R k ) k ≥ 1 (R_k)_{k\ge1} ( R k ) k ≥ 1 be a sequence of nonnegative integers such that R k ≥ 7 R_k\ge7 R k ≥ 7 for all sufficiently large k k k , and let P k \mathbb{P}_k P k be the uniform probability measure on B F k ( R k ) B_{F_k}(R_k) B F k ( R k ) . For C > 1 C>1 C > 1 , put N k ( C ) : = ⌈ C k ⌉ N_k(C):=\lceil Ck\rceil N k ( C ) := ⌈ C k ⌉ , and let A k ( C ) A_k(C) A k ( C ) consist of N k ( C ) N_k(C) N k ( C ) independent P k \mathbb{P}_k P k -distributed elements of F k F_k F k . Then
P [ A k ( C ) freely generates a free subgroup of rank N k ( C ) ] → k → ∞ 1. \mathbb{P}[A_k(C)\text{ freely generates a free subgroup of rank }N_k(C)]\xrightarrow{k\to\infty}1. P [ A k ( C ) freely generates a free subgroup of rank N k ( C )] k → ∞ 1.
Consequently, in the terminology of Definition 1.6, for G = ( F k , P k ) k ≥ 1 \mathcal{G}=(F_k,\mathbb{P}_k)_{k\ge1} G = ( F k , P k ) k ≥ 1 , P G ( δ , 1 / C ) = 0 P_{\mathcal{G}}(\delta,1/C)=0 P G ( δ , 1/ C ) = 0 for every 0 < δ < 1 0<\delta<1 0 < δ < 1 . In particular, G \mathcal{G} G is not a ( δ , ρ ) (\delta,\rho) ( δ , ρ ) -GV family for any 0 < δ , ρ < 1 0<\delta,\rho<1 0 < δ , ρ < 1 .
Proof. Put N : = N k ( C ) N:=N_k(C) N := N k ( C ) , write u : = A k ( C ) = ( u 1 , … , u N ) \mathbf{u}:=A_k(C)=(u_1,\ldots,u_N) u := A k ( C ) = ( u 1 , … , u N ) , and set q k : = 2 k − 1 q_k:=2k-1 q k := 2 k − 1 . Since there are 2 k q k ℓ − 1 2kq_k^{\ell-1} 2 k q k ℓ − 1 reduced words of length ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 , we have
∣ B F k ( r ) ∣ = 1 + ∑ ℓ = 1 r 2 k q k ℓ − 1 = k q k r − 1 k − 1 . |B_{F_k}(r)|=1+\sum_{\ell=1}^{r}2kq_k^{\ell-1}=\frac{kq_k^r-1}{k-1}. ∣ B F k ( r ) ∣ = 1 + ℓ = 1 ∑ r 2 k q k ℓ − 1 = k − 1 k q k r − 1 .
Since R k ≥ 7 R_k\ge7 R k ≥ 7 eventually,
P [ ∣ u i ∣ < 6 ] = ∣ B F k ( 5 ) ∣ ∣ B F k ( R k ) ∣ ≤ q k 5 − R k , \mathbb{P}[|u_i|<6]=\frac{|B_{F_k}(5)|}{|B_{F_k}(R_k)|}\le q_k^{5-R_k}, P [ ∣ u i ∣ < 6 ] = ∣ B F k ( R k ) ∣ ∣ B F k ( 5 ) ∣ ≤ q k 5 − R k ,
and therefore
P [ min 1 ≤ i ≤ N ∣ u i ∣ < 6 ] ≤ N q k 5 − R k . \mathbb{P}\left[\min_{1\leq i\leq N}|u_i|<6\right]\leq Nq_k^{5-R_k}. P [ 1 ≤ i ≤ N min ∣ u i ∣ < 6 ] ≤ N q k 5 − R k .
Conditioned on min i ∣ u i ∣ ≥ 6 \min_i |u_i|\geq6 min i ∣ u i ∣ ≥ 6 , two signed words arising from distinct u i u_i u i have the same length-3 prefix with probability ( 2 k q k 2 ) − 1 ≤ q k − 3 (2kq_k^2)^{-1}\leq q_k^{-3} ( 2 k q k 2 ) − 1 ≤ q k − 3 . For the pair u i , u i − 1 u_i,u_i^{-1} u i , u i − 1 , conditioned on ∣ u i ∣ = m ≥ 6 |u_i|=m\geq6 ∣ u i ∣ = m ≥ 6 , fixing the first m − 3 m-3 m − 3 letters leaves q k 3 q_k^3 q k 3 possible extensions, at most one of which satisfies lcp ( u i , u i − 1 ) ≥ 3 \operatorname{lcp}(u_i,u_i^{-1})\geq3 lcp ( u i , u i − 1 ) ≥ 3 . Hence
P [ lcp ( u ± 1 ) ≥ 3 ∣ min i ∣ u i ∣ ≥ 6 ] ≤ 4 ( N 2 ) 1 2 k q k 2 + N q k − 3 ≤ ( 2 N 2 ) q k − 3 . \mathbb{P}\left[\operatorname{lcp}(u^{\pm1})\geq3\mathrel{\big|}\min_i |u_i|\geq6\right]\leq4\binom{N}{2}\frac{1}{2kq_k^2}+Nq_k^{-3}\leq\binom{2N}{2}q_k^{-3}. P [ lcp ( u ± 1 ) ≥ 3 i min ∣ u i ∣ ≥ 6 ] ≤ 4 ( 2 N ) 2 k q k 2 1 + N q k − 3 ≤ ( 2 2 N ) q k − 3 .
It follows that
P [ 2 lcp ( u ± 1 ) ≥ min 1 ≤ i ≤ N ∣ u i ∣ ] ≤ N q k 5 − R k + ( 2 N 2 ) q k − 3 ≤ ( C + 1 ) k ( 2 k − 1 ) − 2 + 2 ( C + 1 ) 2 k 2 ( 2 k − 1 ) − 3 = O ( k − 1 ) . \begin{aligned}
\mathbb{P}\left[2\operatorname{lcp}(u^{\pm1})\geq\min_{1\leq i\leq N}|u_i|\right]\leq Nq_k^{5-R_k}+\binom{2N}{2}q_k^{-3} \\
&\leq(C+1)k(2k-1)^{-2}+2(C+1)^2k^2(2k-1)^{-3}=O(k^{-1}).
\end{aligned} P [ 2 lcp ( u ± 1 ) ≥ 1 ≤ i ≤ N min ∣ u i ∣ ] ≤ N q k 5 − R k + ( 2 2 N ) q k − 3 ≤ ( C + 1 ) k ( 2 k − 1 ) − 2 + 2 ( C + 1 ) 2 k 2 ( 2 k − 1 ) − 3 = O ( k − 1 ) .
Thus A k ( C ) A_k(C) A k ( C ) has the central tree property with probability tending to 1. By Lemma 3.3 , it therefore freely generates a free subgroup of rank N k ( C ) N_k(C) N k ( C ) with probability tending to 1.
Since C > 1 C>1 C > 1 , we have N k ( C ) > k N_k(C)>k N k ( C ) > k , so this subgroup cannot equal F k F_k F k . Hence A k ( C ) A_k(C) A k ( C ) does not generate F k F_k F k , and [CDL24, Fact 2.1] gives δ ( A k ( C ) ; F k ) = 0 \delta(A_k(C);F_k)=0 δ ( A k ( C ) ; F k ) = 0 . This also proves the final assertion of the theorem. □
Random Codes in Finite Groups
Throughout, let G = ( G i ) i ≥ 1 \mathcal{G}=(G_i)_{i\geq1} G = ( G i ) i ≥ 1 be a family of nontrivial finite groups. When no sampling measures are specified, we take P i P_i P i to be the uniform probability measure on G i G_i G i . The notions of GV and strong GV are those of Definition 1.6; the GV rate, range, and family parameters are defined in Definition 1.9. We record the maximal-subgroup parameters used below:
Definition 4.1 (Maximal-subgroup parameters). Let Γ \Gamma Γ be a nontrivial finite group. For s ≥ 2 s\geq2 s ≥ 2 , define
m s ( Γ ) : = # { M < max Γ : [ Γ : M ] = s } , m_s(\Gamma):=\#\{M<_{\max}\Gamma:[\Gamma:M]=s\}, m s ( Γ ) := # { M < m a x Γ : [ Γ : M ] = s } ,
the number of maximal subgroups of Γ \Gamma Γ of index s s s . Define also
q ( Γ ) : = min { s ≥ 2 : m s ( Γ ) > 0 } , M ( Γ ) : = max s ≥ 2 m s ( Γ ) > 0 log m s ( Γ ) log s . q(\Gamma):=\min\{s\geq2:m_s(\Gamma)>0\},\qquad\mathcal{M}(\Gamma):=\max_{\substack{s\geq2\\m_s(\Gamma)>0}}\frac{\log m_s(\Gamma)}{\log s}. q ( Γ ) := min { s ≥ 2 : m s ( Γ ) > 0 } , M ( Γ ) := s ≥ 2 m s ( Γ ) > 0 max log s log m s ( Γ ) .
Thus q ( Γ ) q(\Gamma) q ( Γ ) is the smallest index of a proper subgroup, while M ( Γ ) \mathcal{M}(\Gamma) M ( Γ ) is its maximal-subgroup growth exponent.
We introduced some of these family parameters in the introduction; we now recall them using the precise maximal-subgroup notation above.
Definition 4.2 (Parameters of a family). Recall the parameters of G = ( G i ) i ≥ 1 \mathcal{G}=(G_i)_{i\geq1} G = ( G i ) i ≥ 1 . Put r i : = rk ( G i ) r_i:=\operatorname{rk}(G_i) r i := rk ( G i ) and define
q G : = lim inf i → ∞ q ( G i ) ∈ { 2 , 3 , … } ∪ { ∞ } , μ G : = max { 1 , lim sup i → ∞ M ( G i ) r i } , rk G : = lim inf i → ∞ r i ∈ N ∪ { ∞ } . q_{\mathcal{G}}:=\liminf_{i\to\infty}q(G_i)\in\{2,3,\ldots\}\cup\{\infty\},\qquad
\mu_{\mathcal{G}}:=\max\left\{1,\limsup_{i\to\infty}\frac{\mathcal{M}(G_i)}{r_i}\right\},\qquad
\operatorname{rk}_{\mathcal{G}}:=\liminf_{i\to\infty}r_i\in\mathbb{N}\cup\{\infty\}. q G := i → ∞ lim inf q ( G i ) ∈ { 2 , 3 , … } ∪ { ∞ } , μ G := max { 1 , i → ∞ lim sup r i M ( G i ) } , rk G := i → ∞ lim inf r i ∈ N ∪ { ∞ } .
Definition 4.3 (Uniform polynomial maximal-subgroup growth). We say that G \mathcal{G} G has uniform polynomial maximal-subgroup growth , or uniform PMSG , if there is a constant A ≥ 0 A\geq0 A ≥ 0 such that, for all sufficiently large i i i and every s ≥ 2 s\geq2 s ≥ 2 ,
m s ( G i ) ≤ s A rk ( G i ) . m_s(G_i)\leq s^{A\operatorname{rk}(G_i)}. m s ( G i ) ≤ s A rk ( G i ) .
We also require a standard parameter measuring random generation.
Definition 4.4. For k ≥ 1 k\geq1 k ≥ 1 , define P Γ ( k ) : = P [ ⟨ g 1 , … , g k ⟩ = Γ ] P_\Gamma(k):=\mathbb{P}[\langle g_1,\ldots,g_k\rangle=\Gamma] P Γ ( k ) := P [⟨ g 1 , … , g k ⟩ = Γ ] , where g 1 , … , g k g_1,\ldots,g_k g 1 , … , g k are independent and uniform in Γ \Gamma Γ . For η > 1 \eta>1 η > 1 , put
ν η ( Γ ) : = min { k ≥ 1 : P Γ ( k ) ≥ 1 η } , ν ( Γ ) : = ν e ( Γ ) . \nu_\eta(\Gamma):=\min\left\{k\geq1:P_\Gamma(k)\geq\frac{1}{\eta}\right\},\qquad\nu(\Gamma):=\nu_e(\Gamma). ν η ( Γ ) := min { k ≥ 1 : P Γ ( k ) ≥ η 1 } , ν ( Γ ) := ν e ( Γ ) .
Thus ν ( Γ ) \nu(\Gamma) ν ( Γ ) is the least k k k for which k k k independent uniform elements generate Γ \Gamma Γ with probability at least 1 / e 1/e 1/ e .
The following lemma gives the basic estimate for the probability that a uniformly random tuple fails to have detection probability at least δ \delta δ , in terms of the maximal-subgroup growth.
Lemma 4.5. Let Γ \Gamma Γ be a nontrivial finite group, put r = rk ( Γ ) r=\operatorname{rk}(\Gamma) r = rk ( Γ ) and q = q ( Γ ) q=q(\Gamma) q = q ( Γ ) , and let 0 < ρ < 1 0<\rho<1 0 < ρ < 1 and 0 < δ < 1 − 1 / q 0<\delta<1-1/q 0 < δ < 1 − 1/ q . Set C : = 1 / ρ C:=1/\rho C := 1/ ρ , N ( C ) : = ⌈ C r ⌉ N(C):=\lceil Cr\rceil N ( C ) := ⌈ C r ⌉ , and let A Γ ( C ) ∈ Γ N ( C ) A_{\Gamma}(C)\in\Gamma^{N(C)} A Γ ( C ) ∈ Γ N ( C ) be a uniformly random tuple. Then
P [ δ ( A Γ ( C ) ; Γ ) < δ ] ≤ ∑ s = q ∣ Γ ∣ m s ( Γ ) s − C r ( 1 − H q ( δ ) ) . \mathbb{P}[\delta(A_{\Gamma}(C);\Gamma)<\delta]\le\sum_{s=q}^{|\Gamma|}m_s(\Gamma)s^{-Cr(1-H_q(\delta))}. P [ δ ( A Γ ( C ) ; Γ ) < δ ] ≤ s = q ∑ ∣Γ∣ m s ( Γ ) s − C r ( 1 − H q ( δ )) . Proof. Write A Γ ( C ) = ( X 1 , … , X N ( C ) ) A_{\Gamma}(C)=(X_1,\ldots,X_{N(C)}) A Γ ( C ) = ( X 1 , … , X N ( C ) ) and put t : = ⌈ ( 1 − δ ) N ( C ) ⌉ t:=\lceil(1-\delta)N(C)\rceil t := ⌈( 1 − δ ) N ( C )⌉ . If M < max Γ M<_{\max}\Gamma M < m a x Γ has index s s s , then
P [ X i ∈ M ] = 1 s , ∣ A Γ ( C ) ∩ M ∣ ∼ Bin ( N ( C ) , 1 s ) . \mathbb{P}[X_i\in M]=\frac{1}{s},\qquad|A_{\Gamma}(C)\cap M|\sim\operatorname{Bin}\left(N(C),\frac{1}{s}\right). P [ X i ∈ M ] = s 1 , ∣ A Γ ( C ) ∩ M ∣ ∼ Bin ( N ( C ) , s 1 ) . Hence, by Lemma 2.1 ,
P [ ∣ A Γ ( C ) ∩ M ∣ ≥ t ] ≤ s − N ( C ) ( 1 − H s ( δ ) ) . \mathbb{P}[|A_{\Gamma}(C)\cap M|\ge t]\le s^{-N(C)(1-H_s(\delta))}. P [ ∣ A Γ ( C ) ∩ M ∣ ≥ t ] ≤ s − N ( C ) ( 1 − H s ( δ )) . If δ ( A Γ ( C ) ; Γ ) < δ \delta(A_{\Gamma}(C);\Gamma)<\delta δ ( A Γ ( C ) ; Γ ) < δ , then some maximal subgroup contains at least t t t sampled elements. Therefore,
P [ δ ( A Γ ( C ) ; Γ ) < δ ] ≤ P [ ∃ M < max Γ : ∣ A Γ ( C ) ∩ M ∣ ≥ t ] . \mathbb{P}[\delta(A_{\Gamma}(C);\Gamma)<\delta]\le\mathbb{P}\left[\exists M<_{\max}\Gamma:|A_{\Gamma}(C)\cap M|\ge t\right]. P [ δ ( A Γ ( C ) ; Γ ) < δ ] ≤ P [ ∃ M < m a x Γ : ∣ A Γ ( C ) ∩ M ∣ ≥ t ] . Therefore, a union bound gives
P [ δ ( A Γ ( C ) ; Γ ) < δ ] ≤ ∑ s = q ∣ Γ ∣ m s ( Γ ) s − N ( C ) ( 1 − H s ( δ ) ) ≤ ∑ s = q ∣ Γ ∣ m s ( Γ ) s − C r ( 1 − H q ( δ ) ) . \mathbb{P}[\delta(A_{\Gamma}(C);\Gamma)<\delta]\le\sum_{s=q}^{|\Gamma|}m_s(\Gamma)s^{-N(C)(1-H_s(\delta))}\le\sum_{s=q}^{|\Gamma|}m_s(\Gamma)s^{-Cr(1-H_q(\delta))}. P [ δ ( A Γ ( C ) ; Γ ) < δ ] ≤ s = q ∑ ∣Γ∣ m s ( Γ ) s − N ( C ) ( 1 − H s ( δ )) ≤ s = q ∑ ∣Γ∣ m s ( Γ ) s − C r ( 1 − H q ( δ )) . Indeed, the last inequality follows from N ( C ) ≥ C r N(C)\ge Cr N ( C ) ≥ C r and H s ( δ ) ≤ H q ( δ ) H_s(\delta)\le H_q(\delta) H s ( δ ) ≤ H q ( δ ) for s ≥ q s\ge q s ≥ q by Lemma 2.2 . □
We now combine this failure-probability estimate with bounds on maximal-subgroup growth. This yields the qualitative characterization of GV families.
Theorem 4.6 (GV characterization). Let G = ( G i ) i ≥ 1 \mathcal{G}=(G_i)_{i\ge1} G = ( G i ) i ≥ 1 be a family of nontrivial finite groups, with q G q_{\mathcal{G}} q G as in Definition 1.9, and adopt the convention that 1 / q G = 0 1/q_{\mathcal{G}}=0 1/ q G = 0 if q G = ∞ q_{\mathcal{G}}=\infty q G = ∞ . Then the following are equivalent:
The family G \mathcal{G} G is ( δ , ρ ) (\delta,\rho) ( δ , ρ ) -GV for some 0 < δ , ρ < 1 0<\delta,\rho<1 0 < δ , ρ < 1 .
The family G \mathcal{G} G has uniform PMSG.
For every 0 < δ < 1 − 1 / q G 0<\delta<1-1/q_{\mathcal{G}} 0 < δ < 1 − 1/ q G , there exists 0 < ρ < 1 0<\rho<1 0 < ρ < 1 such that G \mathcal{G} G is ( δ , ρ ) (\delta,\rho) ( δ , ρ ) -GV.
Proof. Suppose first that G \mathcal{G} G is ( δ , ρ ) (\delta,\rho) ( δ , ρ ) -GV. Let N i : = ⌈ r i / ρ ⌉ N_i:=\lceil r_i/\rho\rceil N i := ⌈ r i / ρ ⌉ , let A i = ( X i , 1 , … , X i , N i ) A_i=(X_{i,1},\ldots,X_{i,N_i}) A i = ( X i , 1 , … , X i , N i ) consist of independent uniform elements of G i G_i G i , and put $K_i:=\lfloor(1-\delta)N_i\rfloor+1.
On the event δ ( A i ; G i ) ≥ δ \delta(A_i;G_i)\ge\delta δ ( A i ; G i ) ≥ δ , every proper subgroup of G i G_i G i contains fewer than K i K_i K i elements of A i A_i A i . Consequently,
⟨ X i , 1 , … , X i , K i ⟩ = G i , P G i ( K i ) ≥ P [ δ ( A i ; G i ) ≥ δ ] . \langle X_{i,1},\ldots,X_{i,K_i}\rangle=G_i,\qquad P_{G_i}(K_i)\ge\mathbb{P}[\delta(A_i;G_i)\ge\delta]. ⟨ X i , 1 , … , X i , K i ⟩ = G i , P G i ( K i ) ≥ P [ δ ( A i ; G i ) ≥ δ ] . Set λ : = P G ( δ , ρ ) > 0 \lambda:=P_{\mathcal{G}}(\delta,\rho)>0 λ := P G ( δ , ρ ) > 0 and choose η > 1 / λ \eta>1/\lambda η > 1/ λ . For all sufficiently large i i i , P G i ( K i ) > 1 / η P_{G_i}(K_i)>1/\eta P G i ( K i ) > 1/ η , so ν η ( G i ) ≤ K i \nu_\eta(G_i)\le K_i ν η ( G i ) ≤ K i . By [LM20, Lemma 2.1],
M ( G i ) ≤ ν η ( G i ) + 2 + log 2 η ≤ K i + 2 + log 2 η . \mathcal{M}(G_i)\le\nu_\eta(G_i)+2+\log_2\eta\le K_i+2+\log_2\eta. M ( G i ) ≤ ν η ( G i ) + 2 + log 2 η ≤ K i + 2 + log 2 η . Moreover,
K i ≤ ( 1 − δ ) ⌈ r i / ρ ⌉ + 1 ≤ 1 − δ ρ r i + 2 , K_i\le(1-\delta)\lceil r_i/\rho\rceil+1\le\frac{1-\delta}{\rho}r_i+2, K i ≤ ( 1 − δ ) ⌈ r i / ρ ⌉ + 1 ≤ ρ 1 − δ r i + 2 , and therefore
M ( G i ) ≤ 1 − δ ρ r i + 4 + log 2 η . \mathcal{M}(G_i)\le\frac{1-\delta}{\rho}r_i+4+\log_2\eta. M ( G i ) ≤ ρ 1 − δ r i + 4 + log 2 η . Since m s ( G i ) ≤ s M ( G i ) m_s(G_i)\le s^{\mathcal{M}(G_i)} m s ( G i ) ≤ s M ( G i ) for every s ≥ 2 s\ge2 s ≥ 2 , and r i ≥ 1 r_i\ge1 r i ≥ 1 , it follows that
m s ( G i ) ≤ s ( 1 − δ ρ + 4 + log 2 η ) r i . m_s(G_i)\le s^{\left(\frac{1-\delta}{\rho}+4+\log_2\eta\right)r_i}. m s ( G i ) ≤ s ( ρ 1 − δ + 4 + l o g 2 η ) r i . Hence the family G \mathcal{G} G has uniform PMSG. Thus (1) ⇒ \Rightarrow ⇒ (2).
Suppose now that (2) holds. Thus there exists A ≥ 0 A\ge0 A ≥ 0 such that m s ( G i ) ≤ s A ⋅ r i m_s(G_i)\le s^{A\cdot r_i} m s ( G i ) ≤ s A ⋅ r i for all sufficiently large i i i and every s ≥ 2 s\ge2 s ≥ 2 . Fix 0 < δ < 1 − 1 / q G 0<\delta<1-1/q_{\mathcal{G}} 0 < δ < 1 − 1/ q G . If q G < ∞ q_{\mathcal{G}}<\infty q G < ∞ , put q = q G q=q_{\mathcal{G}} q = q G . If q G = ∞ q_{\mathcal{G}}=\infty q G = ∞ , choose any sufficiently large integer q ≥ 2 q\ge2 q ≥ 2 for which δ < 1 − 1 / q \delta<1-1/q δ < 1 − 1/ q .
Put L : = 1 − H q ( δ ) > 0 L:=1-H_q(\delta)>0 L := 1 − H q ( δ ) > 0 and choose 0 < ρ < 1 0<\rho<1 0 < ρ < 1 such that L / ρ ≥ A + 2 L/\rho\ge A+2 L / ρ ≥ A + 2 . Let A i A_i A i and N i N_i N i be defined as before. By Lemma 4.5,
P [ δ ( A i ; G i ) < δ ] ≤ ∑ s = q ∞ s A ⋅ r i − N i L . \mathbb{P}[\delta(A_i;G_i)<\delta]\le\sum_{s=q}^{\infty}s^{A\cdot r_i-N_iL}. P [ δ ( A i ; G i ) < δ ] ≤ s = q ∑ ∞ s A ⋅ r i − N i L . @page 9/18 starts_mid=0 ends_mid=1
Lemma 4.5. Let Γ \Gamma Γ be a nontrivial finite group, put r = rk ( Γ ) r=\operatorname{rk}(\Gamma) r = rk ( Γ ) and q = q ( Γ ) q=q(\Gamma) q = q ( Γ ) , and let 0 < ρ < 1 0<\rho<1 0 < ρ < 1 and 0 < δ < 1 − 1 / q 0<\delta<1-1/q 0 < δ < 1 − 1/ q . Set C : = 1 / ρ C:=1/\rho C := 1/ ρ , N ( C ) : = ⌈ C r ⌉ N(C):=\lceil Cr\rceil N ( C ) := ⌈ C r ⌉ , and let A Γ ( C ) ∈ Γ N ( C ) A_{\Gamma}(C)\in\Gamma^{N(C)} A Γ ( C ) ∈ Γ N ( C ) be a uniformly random tuple. Then
P [ δ ( A Γ ( C ) ; Γ ) < δ ] ≤ ∑ s = q ∣ Γ ∣ m s ( Γ ) s − C r ( 1 − H q ( δ ) ) . \mathbb{P}[\delta(A_{\Gamma}(C);\Gamma)<\delta]\le\sum_{s=q}^{|\Gamma|}m_s(\Gamma)s^{-Cr(1-H_q(\delta))}. P [ δ ( A Γ ( C ) ; Γ ) < δ ] ≤ s = q ∑ ∣Γ∣ m s ( Γ ) s − C r ( 1 − H q ( δ )) . Proof. Write A Γ ( C ) = ( X 1 , … , X N ( C ) ) A_{\Gamma}(C)=(X_1,\ldots,X_{N(C)}) A Γ ( C ) = ( X 1 , … , X N ( C ) ) and put t : = ⌈ ( 1 − δ ) N ( C ) ⌉ t:=\lceil(1-\delta)N(C)\rceil t := ⌈( 1 − δ ) N ( C )⌉ . If M < max Γ M<_{\max}\Gamma M < m a x Γ has index s s s , then
P [ X i ∈ M ] = 1 s , ∣ A Γ ( C ) ∩ M ∣ ∼ Bin ( N ( C ) , 1 s ) . \mathbb{P}[X_i\in M]=\frac{1}{s},\qquad|A_{\Gamma}(C)\cap M|\sim\operatorname{Bin}\left(N(C),\frac{1}{s}\right). P [ X i ∈ M ] = s 1 , ∣ A Γ ( C ) ∩ M ∣ ∼ Bin ( N ( C ) , s 1 ) . Hence, by Lemma 2.1,
P [ ∣ A Γ ( C ) ∩ M ∣ ≥ t ] ≤ s − N ( C ) ( 1 − H s ( δ ) ) . \mathbb{P}[|A_{\Gamma}(C)\cap M|\ge t]\le s^{-N(C)(1-H_s(\delta))}. P [ ∣ A Γ ( C ) ∩ M ∣ ≥ t ] ≤ s − N ( C ) ( 1 − H s ( δ )) . If δ ( A Γ ( C ) ; Γ ) < δ \delta(A_{\Gamma}(C);\Gamma)<\delta δ ( A Γ ( C ) ; Γ ) < δ , then some maximal subgroup contains at least t t t sampled elements. Therefore,
P [ δ ( A Γ ( C ) ; Γ ) < δ ] ≤ P [ ∃ M < max Γ : ∣ A Γ ( C ) ∩ M ∣ ≥ t ] . \mathbb{P}[\delta(A_{\Gamma}(C);\Gamma)<\delta]\le\mathbb{P}\left[\exists M<_{\max}\Gamma:|A_{\Gamma}(C)\cap M|\ge t\right]. P [ δ ( A Γ ( C ) ; Γ ) < δ ] ≤ P [ ∃ M < m a x Γ : ∣ A Γ ( C ) ∩ M ∣ ≥ t ] . Therefore, a union bound gives
P [ δ ( A Γ ( C ) ; Γ ) < δ ] ≤ ∑ s = q ∣ Γ ∣ m s ( Γ ) s − N ( C ) ( 1 − H s ( δ ) ) ≤ ∑ s = q ∣ Γ ∣ m s ( Γ ) s − C r ( 1 − H q ( δ ) ) . \mathbb{P}[\delta(A_{\Gamma}(C);\Gamma)<\delta]\le\sum_{s=q}^{|\Gamma|}m_s(\Gamma)s^{-N(C)(1-H_s(\delta))}\le\sum_{s=q}^{|\Gamma|}m_s(\Gamma)s^{-Cr(1-H_q(\delta))}. P [ δ ( A Γ ( C ) ; Γ ) < δ ] ≤ s = q ∑ ∣Γ∣ m s ( Γ ) s − N ( C ) ( 1 − H s ( δ )) ≤ s = q ∑ ∣Γ∣ m s ( Γ ) s − C r ( 1 − H q ( δ )) . Indeed, the last inequality follows from N ( C ) ≥ C r N(C)\ge Cr N ( C ) ≥ C r and H s ( δ ) ≤ H q ( δ ) H_s(\delta)\le H_q(\delta) H s ( δ ) ≤ H q ( δ ) for s ≥ q s\ge q s ≥ q by Lemma 2.2 . □
We now combine this failure-probability estimate with bounds on maximal-subgroup growth. This yields the qualitative characterization of GV families.
Theorem 4.6 (GV characterization). Let G = ( G i ) i ≥ 1 \mathcal{G}=(G_i)_{i\ge1} G = ( G i ) i ≥ 1 be a family of nontrivial finite groups, with q G q_{\mathcal{G}} q G as in Definition 1.9, and adopt the convention that 1 / q G = 0 1/q_{\mathcal{G}}=0 1/ q G = 0 if q G = ∞ q_{\mathcal{G}}=\infty q G = ∞ . Then the following are equivalent:
The family G \mathcal{G} G is ( δ , ρ ) (\delta,\rho) ( δ , ρ ) -GV for some 0 < δ , ρ < 1 0<\delta,\rho<1 0 < δ , ρ < 1 .
The family G \mathcal{G} G has uniform PMSG.
For every 0 < δ < 1 − 1 / q G 0<\delta<1-1/q_{\mathcal{G}} 0 < δ < 1 − 1/ q G , there exists 0 < ρ < 1 0<\rho<1 0 < ρ < 1 such that G \mathcal{G} G is ( δ , ρ ) (\delta,\rho) ( δ , ρ ) -GV.
Proof. Suppose first that G \mathcal{G} G is ( δ , ρ ) (\delta,\rho) ( δ , ρ ) -GV. Let N i : = ⌈ r i / ρ ⌉ N_i:=\lceil r_i/\rho\rceil N i := ⌈ r i / ρ ⌉ , let A i = ( X i , 1 , … , X i , N i ) A_i=(X_{i,1},\ldots,X_{i,N_i}) A i = ( X i , 1 , … , X i , N i ) consist of independent uniform elements of G i G_i G i , and put $K_i:=\lfloor(1-\delta)N_i\rfloor+1.
On the event δ ( A i ; G i ) ≥ δ \delta(A_i;G_i)\ge\delta δ ( A i ; G i ) ≥ δ , every proper subgroup of G i G_i G i contains fewer than K i K_i K i elements of A i A_i A i . Consequently,
⟨ X i , 1 , … , X i , K i ⟩ = G i , P G i ( K i ) ≥ P [ δ ( A i ; G i ) ≥ δ ] . \langle X_{i,1},\ldots,X_{i,K_i}\rangle=G_i,\qquad P_{G_i}(K_i)\ge\mathbb{P}[\delta(A_i;G_i)\ge\delta]. ⟨ X i , 1 , … , X i , K i ⟩ = G i , P G i ( K i ) ≥ P [ δ ( A i ; G i ) ≥ δ ] . Set λ : = P G ( δ , ρ ) > 0 \lambda:=P_{\mathcal{G}}(\delta,\rho)>0 λ := P G ( δ , ρ ) > 0 and choose η > 1 / λ \eta>1/\lambda η > 1/ λ . For all sufficiently large i i i , P G i ( K i ) > 1 / η P_{G_i}(K_i)>1/\eta P G i ( K i ) > 1/ η , so ν η ( G i ) ≤ K i \nu_\eta(G_i)\le K_i ν η ( G i ) ≤ K i . By [LM20, Lemma 2.1],
M ( G i ) ≤ ν η ( G i ) + 2 + log 2 η ≤ K i + 2 + log 2 η . \mathcal{M}(G_i)\le\nu_\eta(G_i)+2+\log_2\eta\le K_i+2+\log_2\eta. M ( G i ) ≤ ν η ( G i ) + 2 + log 2 η ≤ K i + 2 + log 2 η . Moreover,
K i ≤ ( 1 − δ ) ⌈ r i / ρ ⌉ + 1 ≤ 1 − δ ρ r i + 2 , K_i\le(1-\delta)\lceil r_i/\rho\rceil+1\le\frac{1-\delta}{\rho}r_i+2, K i ≤ ( 1 − δ ) ⌈ r i / ρ ⌉ + 1 ≤ ρ 1 − δ r i + 2 , and therefore
M ( G i ) ≤ 1 − δ ρ r i + 4 + log 2 η . \mathcal{M}(G_i)\le\frac{1-\delta}{\rho}r_i+4+\log_2\eta. M ( G i ) ≤ ρ 1 − δ r i + 4 + log 2 η . Since m s ( G i ) ≤ s M ( G i ) m_s(G_i)\le s^{\mathcal{M}(G_i)} m s ( G i ) ≤ s M ( G i ) for every s ≥ 2 s\ge2 s ≥ 2 , and r i ≥ 1 r_i\ge1 r i ≥ 1 , it follows that
m s ( G i ) ≤ s ( 1 − δ ρ + 4 + log 2 η ) r i . m_s(G_i)\le s^{\left(\frac{1-\delta}{\rho}+4+\log_2\eta\right)r_i}. m s ( G i ) ≤ s ( ρ 1 − δ + 4 + l o g 2 η ) r i . Hence the family G \mathcal{G} G has uniform PMSG. Thus (1) ⇒ \Rightarrow ⇒ (2).
Suppose now that (2) holds. Thus there exists A ≥ 0 A\ge0 A ≥ 0 such that m s ( G i ) ≤ s A ⋅ r i m_s(G_i)\le s^{A\cdot r_i} m s ( G i ) ≤ s A ⋅ r i for all sufficiently large i i i and every s ≥ 2 s\ge2 s ≥ 2 . Fix 0 < δ < 1 − 1 / q G 0<\delta<1-1/q_{\mathcal{G}} 0 < δ < 1 − 1/ q G . If q G < ∞ q_{\mathcal{G}}<\infty q G < ∞ , put q = q G q=q_{\mathcal{G}} q = q G . If q G = ∞ q_{\mathcal{G}}=\infty q G = ∞ , choose any sufficiently large integer q ≥ 2 q\ge2 q ≥ 2 for which δ < 1 − 1 / q \delta<1-1/q δ < 1 − 1/ q .
Put L : = 1 − H q ( δ ) > 0 L:=1-H_q(\delta)>0 L := 1 − H q ( δ ) > 0 and choose 0 < ρ < 1 0<\rho<1 0 < ρ < 1 such that L / ρ ≥ A + 2 L/\rho\ge A+2 L / ρ ≥ A + 2 . Let A i A_i A i and N i N_i N i be defined as before. By Lemma 4.5,
P [ δ ( A i ; G i ) < δ ] ≤ ∑ s = q ∞ s A ⋅ r i − N i L . \mathbb{P}[\delta(A_i;G_i)<\delta]\le\sum_{s=q}^{\infty}s^{A\cdot r_i-N_iL}. P [ δ ( A i ; G i ) < δ ] ≤ s = q ∑ ∞ s A ⋅ r i − N i L .
Since N i ≥ r i / ρ N_i \ge r_i/\rho N i ≥ r i / ρ and r i ≥ 1 r_i \ge1 r i ≥ 1 ,
A r i − N i L ≤ ( A − L / ρ ) r i ≤ − 2 r i ≤ − 2. Ar_i-N_iL \le(A-L/\rho)r_i \le-2r_i \le-2. A r i − N i L ≤ ( A − L / ρ ) r i ≤ − 2 r i ≤ − 2.
Consequently,
P [ δ ( A i ; G i ) < δ ] ≤ ∑ s = q ∞ s − 2 ≤ ∑ s = 2 ∞ s − 2 = π 2 6 − 1 < 1. \mathbb{P}[\delta(A_i;G_i)<\delta]\le\sum_{s=q}^{\infty}s^{-2}\le\sum_{s=2}^{\infty}s^{-2}=\frac{\pi^2}{6}-1<1. P [ δ ( A i ; G i ) < δ ] ≤ s = q ∑ ∞ s − 2 ≤ s = 2 ∑ ∞ s − 2 = 6 π 2 − 1 < 1.
Thus
P [ δ ( A i ; G i ) ≥ δ ] ≥ 2 − π 2 6 > 0 \mathbb{P}[\delta(A_i;G_i)\ge\delta]\ge2-\frac{\pi^2}{6}>0 P [ δ ( A i ; G i ) ≥ δ ] ≥ 2 − 6 π 2 > 0
for all sufficiently large i i i . Hence G G G is ( δ , ρ ) (\delta,\rho) ( δ , ρ ) -GV, proving (2) ⇒ \Rightarrow ⇒ (3). Since the interval 0 < δ < 1 − 1 / q G 0<\delta<1-1/q_G 0 < δ < 1 − 1/ q G is nonempty, (3) ⇒ \Rightarrow ⇒ (1) is immediate. □
The next two theorems refine the preceding qualitative characterization by giving explicit bounds on the GV rate, treating separately the cases rk G < ∞ \operatorname{rk}_G<\infty rk G < ∞ and rk G = ∞ \operatorname{rk}_G=\infty rk G = ∞ .
Theorem 4.7 (Quantitative bounds and optimal GV range for rk G = ∞ \operatorname{rk}_G=\infty rk G = ∞ ). Let G = ( G i ) i ≥ 1 G=(G_i)_{i\ge1} G = ( G i ) i ≥ 1 be a family of nontrivial finite groups with uniform PMSG such that rk G = ∞ \operatorname{rk}_G=\infty rk G = ∞ . We adopt the conventions 1 / q G = 0 1/q_G=0 1/ q G = 0 and H q G ( δ ) = δ H_{q_G}(\delta)=\delta H q G ( δ ) = δ if q G = ∞ q_G=\infty q G = ∞ . Then:
(1) For every 0 < δ < 1 − 1 / q G 0<\delta<1-1/q_G 0 < δ < 1 − 1/ q G ,
1 − H q G ( δ ) μ G ≤ R G ( δ ) ≤ 1 − δ μ G . \frac{1-H_{q_G}(\delta)}{\mu_G}\le R_G(\delta)\le\frac{1-\delta}{\mu_G}. μ G 1 − H q G ( δ ) ≤ R G ( δ ) ≤ μ G 1 − δ . Moreover, if 0 < ρ < 1 − H q G ( δ ) μ G 0<\rho<\frac{1-H_{q_G}(\delta)}{\mu_G} 0 < ρ < μ G 1 − H q G ( δ ) then P G ( δ , ρ ) = 1 P_G(\delta,\rho)=1 P G ( δ , ρ ) = 1 .
(2) If q G = ∞ q_G=\infty q G = ∞ , then, for every 0 < δ < 1 0<\delta<1 0 < δ < 1 , R G ( δ ) = 1 − δ μ G R_G(\delta)=\frac{1-\delta}{\mu_G} R G ( δ ) = μ G 1 − δ .
(3) If q G < ∞ q_G<\infty q G < ∞ , then, for every 1 − 1 / q G < δ < 1 1-1/q_G<\delta<1 1 − 1/ q G < δ < 1 , R G ( δ ) = 0 R_G(\delta)=0 R G ( δ ) = 0 .
Theorem 4.8 (Quantitative GV bounds for rk G < ∞ \operatorname{rk}_G<\infty rk G < ∞ ). Let G = ( G i ) i ≥ 1 G=(G_i)_{i\ge1} G = ( G i ) i ≥ 1 be a family of nontrivial finite groups with uniform PMSG and rk G < ∞ \operatorname{rk}_G<\infty rk G < ∞ . Then:
(1) If q G < ∞ q_G<\infty q G < ∞ , then, for every 0 < δ < 1 − 1 / q G 0<\delta<1-1/q_G 0 < δ < 1 − 1/ q G , we have R G ( δ ) ≥ 1 − H q G ( δ ) μ G + 2 / rk G R_G(\delta)\ge\frac{1-H_{q_G}(\delta)}{\mu_G+2/\operatorname{rk}_G} R G ( δ ) ≥ μ G + 2/ rk G 1 − H q G ( δ ) .
(2) If q G = ∞ q_G=\infty q G = ∞ , then, for every 0 < δ < 1 0<\delta<1 0 < δ < 1 , we have R G ( δ ) ≥ 1 − δ μ G + 1 / rk G R_G(\delta)\ge\frac{1-\delta}{\mu_G+1/\operatorname{rk}_G} R G ( δ ) ≥ μ G + 1/ rk G 1 − δ .
Moreover, if 0 < ρ < 1 − δ μ G + 1 / rk G 0<\rho<\frac{1-\delta}{\mu_G+1/\operatorname{rk}_G} 0 < ρ < μ G + 1/ rk G 1 − δ then P G ( δ , ρ ) = 1 P_G(\delta,\rho)=1 P G ( δ , ρ ) = 1 .
The proofs of the two preceding theorems rely on the same probability estimate, so we prove them together.
Proof of Theorems 4.7 and 4.8 . Put q i : = q ( G i ) q_i:=q(G_i) q i := q ( G i ) and q G = lim inf i → ∞ q i q_G=\liminf_{i\to\infty}q_i q G = lim inf i → ∞ q i . Since G G G has uniform PMSG, μ G < ∞ \mu_G<\infty μ G < ∞ , and, for every ε > 0 \varepsilon>0 ε > 0 , M ( G i ) ≤ ( μ G + ε ) r i M(G_i)\le(\mu_G+\varepsilon)r_i M ( G i ) ≤ ( μ G + ε ) r i for all sufficiently large i i i .
Throughout the proof, whenever 0 < ρ < 1 0<\rho<1 0 < ρ < 1 is fixed, we write N i : = ⌈ r i / ρ ⌉ N_i:=\lceil r_i/\rho\rceil N i := ⌈ r i / ρ ⌉ and let A i A_i A i consist of N i N_i N i independent uniform elements of G i G_i G i . For δ < 1 − 1 / q i \delta<1-1/q_i δ < 1 − 1/ q i , put L i : = 1 − H q i ( δ ) L_i:=1-H_{q_i}(\delta) L i := 1 − H q i ( δ ) . Since m s ( G i ) ≤ s M ( G i ) m_s(G_i)\le s^{M(G_i)} m s ( G i ) ≤ s M ( G i ) for every s ≥ 2 s\ge2 s ≥ 2 , Lemma 4.5 gives
P i [ δ ( A i ; G i ) < δ ] ≤ ∑ s = q i ∣ G i ∣ m s ( G i ) s − r i L i / ρ ≤ ∑ s = q i ∞ s M ( G i ) − r i L i / ρ . (6) \mathbb{P}_i[\delta(A_i;G_i)<\delta]\le\sum_{s=q_i}^{|G_i|}m_s(G_i)s^{-r_iL_i/\rho}\le\sum_{s=q_i}^{\infty}s^{M(G_i)-r_iL_i/\rho}. \tag*{(6)} P i [ δ ( A i ; G i ) < δ ] ≤ s = q i ∑ ∣ G i ∣ m s ( G i ) s − r i L i / ρ ≤ s = q i ∑ ∞ s M ( G i ) − r i L i / ρ . (6)
For the lower-bound arguments below, fix 0 < δ < 1 − 1 / q G 0<\delta<1-1/q_G 0 < δ < 1 − 1/ q G and put L : = 1 − H q G ( δ ) > 0 L:=1-H_{q_G}(\delta)>0 L := 1 − H q G ( δ ) > 0 , with H ∞ ( δ ) = δ H_{\infty}(\delta)=\delta H ∞ ( δ ) = δ .
Proof of Theorem 4.8 . Suppose that rk G < ∞ \operatorname{rk}_G<\infty rk G < ∞ . Since the r i r_i r i are integers, r i ≥ rk G r_i\ge\operatorname{rk}_G r i ≥ rk G for all sufficiently large i i i . For part (1), suppose that q G < ∞ q_G<\infty q G < ∞ and choose 0 < ρ < L μ G + 2 / rk G 0<\rho<\frac{L}{\mu_G+2/\operatorname{rk}_G} 0 < ρ < μ G + 2/ rk G L . Choose ε > 0 \varepsilon>0 ε > 0 such that L / ρ ≥ μ G + 2 / rk G + 2 ε L/\rho\ge\mu_G+2/\operatorname{rk}_G+2\varepsilon L / ρ ≥ μ G + 2/ rk G + 2 ε . Since q i ≥ q G q_i\ge q_G q i ≥ q G eventually, we have L i ≥ L L_i\ge L L i ≥ L by Lemma 2.2 . Therefore, for all sufficiently large i i i ,
M ( G i ) − r i ρ L i ≤ ( μ G + ε ) r i − r i ρ L = ( μ G + ε − L ρ ) r i ≤ − ( 2 rk G + ε ) r i ≤ − 2. M(G_i)-\frac{r_i}{\rho}L_i\le(\mu_G+\varepsilon)r_i-\frac{r_i}{\rho}L=\left(\mu_G+\varepsilon-\frac{L}{\rho}\right)r_i\le-\left(\frac{2}{\operatorname{rk}_G}+\varepsilon\right)r_i\le-2. M ( G i ) − ρ r i L i ≤ ( μ G + ε ) r i − ρ r i L = ( μ G + ε − ρ L ) r i ≤ − ( rk G 2 + ε ) r i ≤ − 2.
Hence, by (6),
P i [ δ ( A i ; G i ) < δ ] ≤ ∑ s = q i ∞ s − 2 ≤ ∑ s = 2 ∞ s − 2 = π 2 6 − 1. \mathbb{P}_i[\delta(A_i;G_i)<\delta]\le\sum_{s=q_i}^{\infty}s^{-2}\le\sum_{s=2}^{\infty}s^{-2}=\frac{\pi^2}{6}-1. P i [ δ ( A i ; G i ) < δ ] ≤ s = q i ∑ ∞ s − 2 ≤ s = 2 ∑ ∞ s − 2 = 6 π 2 − 1.
Consequently, P G ( δ , ρ ) ≥ 2 − π 2 / 6 > 0 \mathbb{P}_{\mathcal{G}}(\delta,\rho) \ge2-\pi^2/6>0 P G ( δ , ρ ) ≥ 2 − π 2 /6 > 0 . Thus G \mathcal{G} G is ( δ , ρ ) (\delta,\rho) ( δ , ρ ) -GV for every 0 < ρ < L / ( μ G + 2 / rk G ) 0<\rho<L/(\mu_{\mathcal{G}}+2/\operatorname{rk}_{\mathcal{G}}) 0 < ρ < L / ( μ G + 2/ rk G ) , and hence
R G ( δ ) ≥ 1 − H q G ( δ ) μ G + 2 / rk G . R_{\mathcal{G}}(\delta)\ge\frac{1-H_{q_{\mathcal{G}}}(\delta)}{\mu_{\mathcal{G}}+2/\operatorname{rk}_{\mathcal{G}}}. R G ( δ ) ≥ μ G + 2/ rk G 1 − H q G ( δ ) .
For part (2), suppose that q G = ∞ q_{\mathcal{G}}=\infty q G = ∞ . Then L = 1 − δ L=1-\delta L = 1 − δ . Choose 0 < ρ < L / ( μ G + 1 / rk G ) 0<\rho<L/(\mu_{\mathcal{G}}+1/\operatorname{rk}_{\mathcal{G}}) 0 < ρ < L / ( μ G + 1/ rk G ) . Since H q i ( δ ) → δ H_{q_i}(\delta)\to\delta H q i ( δ ) → δ , we have L i / ρ → L / ρ > μ G + 1 / rk G L_i/\rho\to L/\rho>\mu_{\mathcal{G}}+1/\operatorname{rk}_{\mathcal{G}} L i / ρ → L / ρ > μ G + 1/ rk G . Thus there exists ε > 0 \varepsilon>0 ε > 0 such that, for all sufficiently large i i i ,
L i ρ ≥ μ G + 1 rk G + 2 ε and M ( G i ) ≤ ( μ G + ε ) r i . \frac{L_i}{\rho}\ge\mu_{\mathcal{G}}+\frac{1}{\operatorname{rk}_{\mathcal{G}}}+2\varepsilon
\qquad\text{and}\qquad
\mathcal{M}(G_i)\le(\mu_{\mathcal{G}}+\varepsilon)r_i. ρ L i ≥ μ G + rk G 1 + 2 ε and M ( G i ) ≤ ( μ G + ε ) r i .
It follows that
M ( G i ) − r i ρ L i ≤ ( μ G + ε − L i ρ ) r i ≤ − ( 1 rk G + ε ) r i ≤ − 1 − ε rk G . \mathcal{M}(G_i)-\frac{r_i}{\rho}L_i
\le\left(\mu_{\mathcal{G}}+\varepsilon-\frac{L_i}{\rho}\right)r_i
\le-\left(\frac{1}{\operatorname{rk}_{\mathcal{G}}}+\varepsilon\right)r_i
\le-1-\varepsilon\operatorname{rk}_{\mathcal{G}}. M ( G i ) − ρ r i L i ≤ ( μ G + ε − ρ L i ) r i ≤ − ( rk G 1 + ε ) r i ≤ − 1 − ε rk G .
Hence, by (6) ,
P i [ δ ( A i ; G i ) < δ ] ≤ ∑ s = q i ∞ s − 1 − ε rk G ≤ ∫ q i − 1 ∞ x − 1 − ε rk G d x = ( q i − 1 ) − ε rk G ε rk G → i → ∞ 0. \mathbb{P}_i[\delta(A_i;G_i)<\delta]
\le\sum_{s=q_i}^{\infty}s^{-1-\varepsilon\operatorname{rk}_{\mathcal{G}}}
\le\int_{q_i-1}^{\infty}x^{-1-\varepsilon\operatorname{rk}_{\mathcal{G}}}\,dx
=\frac{(q_i-1)^{-\varepsilon\operatorname{rk}_{\mathcal{G}}}}{\varepsilon\operatorname{rk}_{\mathcal{G}}}
\xrightarrow[i\to\infty]{}0. P i [ δ ( A i ; G i ) < δ ] ≤ s = q i ∑ ∞ s − 1 − ε rk G ≤ ∫ q i − 1 ∞ x − 1 − ε rk G d x = ε rk G ( q i − 1 ) − ε rk G i → ∞ 0.
Thus P G ( δ , ρ ) = 1 \mathbb{P}_{\mathcal{G}}(\delta,\rho)=1 P G ( δ , ρ ) = 1 , and hence
R G ( δ ) ≥ 1 − δ μ G + 1 / rk G . R_{\mathcal{G}}(\delta)\ge\frac{1-\delta}{\mu_{\mathcal{G}}+1/\operatorname{rk}_{\mathcal{G}}}. R G ( δ ) ≥ μ G + 1/ rk G 1 − δ .
Proof of Theorem 4.7 . Suppose that rk G = ∞ \operatorname{rk}_{\mathcal{G}}=\infty rk G = ∞ . For part (1), let δ \delta δ and L L L be as above, and choose 0 < ρ < L / μ G 0<\rho<L/\mu_{\mathcal{G}} 0 < ρ < L / μ G . Choose ε > 0 \varepsilon>0 ε > 0 such that L / ρ ≥ μ G + 3 ε L/\rho\ge\mu_{\mathcal{G}}+3\varepsilon L / ρ ≥ μ G + 3 ε . If q G < ∞ q_{\mathcal{G}}<\infty q G < ∞ , then q i ≥ q G q_i\ge q_{\mathcal{G}} q i ≥ q G eventually, so L i ≥ L L_i\ge L L i ≥ L by Lemma 2.2 . If q G = ∞ q_{\mathcal{G}}=\infty q G = ∞ , then q i → ∞ q_i\to\infty q i → ∞ and L i → L L_i\to L L i → L . Thus, in either case, L i / ρ ≥ μ G + 2 ε L_i/\rho\ge\mu_{\mathcal{G}}+2\varepsilon L i / ρ ≥ μ G + 2 ε for all sufficiently large i i i . Together with M ( G i ) ≤ ( μ G + ε ) r i \mathcal{M}(G_i)\le(\mu_{\mathcal{G}}+\varepsilon)r_i M ( G i ) ≤ ( μ G + ε ) r i , this gives M ( G i ) − r i L i / ρ ≤ − ε r i \mathcal{M}(G_i)-r_iL_i/\rho\le-\varepsilon r_i M ( G i ) − r i L i / ρ ≤ − ε r i . Since ε r i ≥ 2 \varepsilon r_i\ge2 ε r i ≥ 2 eventually, (6) gives
P i [ δ ( A i ; G i ) < δ ] ≤ ∑ s = q i ∞ s − ε r i ≤ 2 − ( ε r i − 2 ) ∑ s = 2 ∞ s − 2 → i → ∞ 0. \mathbb{P}_i[\delta(A_i;G_i)<\delta]
\le\sum_{s=q_i}^{\infty}s^{-\varepsilon r_i}
\le2^{-(\varepsilon r_i-2)}\sum_{s=2}^{\infty}s^{-2}
\xrightarrow[i\to\infty]{}0. P i [ δ ( A i ; G i ) < δ ] ≤ s = q i ∑ ∞ s − ε r i ≤ 2 − ( ε r i − 2 ) s = 2 ∑ ∞ s − 2 i → ∞ 0.
This proves both the lower bound and the convergence assertion in part (1).
We next prove the upper bound in part (1). Suppose that G \mathcal{G} G is ( δ , ρ ) (\delta,\rho) ( δ , ρ ) -GV. The proof of Theorem 4.6 gives
M ( G i ) ≤ 1 − δ ρ r i + O ( 1 ) . \mathcal{M}(G_i)\le\frac{1-\delta}{\rho}r_i+O(1). M ( G i ) ≤ ρ 1 − δ r i + O ( 1 ) .
Moreover, putting K i : = ⌊ ( 1 − δ ) ⌈ r i / ρ ⌉ ⌋ + 1 K_i:=\left\lfloor(1-\delta)\left\lceil r_i/\rho\right\rceil\right\rfloor+1 K i := ⌊ ( 1 − δ ) ⌈ r i / ρ ⌉ ⌋ + 1 , the same proof gives P G i ( K i ) ≥ P i [ δ ( A i ; G i ) ≥ δ ] \mathbb{P}_{G_i}(K_i)\ge\mathbb{P}_i[\delta(A_i;G_i)\ge\delta] P G i ( K i ) ≥ P i [ δ ( A i ; G i ) ≥ δ ] . The right-hand side is positive for all sufficiently large i i i , and hence P G i ( K i ) > 0 \mathbb{P}_{G_i}(K_i)>0 P G i ( K i ) > 0 . Thus G i G_i G i admits a generating K i K_i K i -tuple, so r i ≤ K i r_i\le K_i r i ≤ K i . Consequently,
r i ≤ ⌊ ( 1 − δ ) ⌈ r i ρ ⌉ ⌋ + 1 ≤ 1 − δ ρ r i + 2. r_i\le\left\lfloor(1-\delta)\left\lceil\frac{r_i}{\rho}\right\rceil\right\rfloor+1
\le\frac{1-\delta}{\rho}r_i+2. r i ≤ ⌊ ( 1 − δ ) ⌈ ρ r i ⌉ ⌋ + 1 ≤ ρ 1 − δ r i + 2.
Since r i → ∞ r_i\to\infty r i → ∞ , dividing by r i r_i r i and passing to the limit yields 1 ≤ ( 1 − δ ) / ρ 1\le(1-\delta)/\rho 1 ≤ ( 1 − δ ) / ρ . Dividing the preceding bound by r i r_i r i and taking the limsup yields μ G ≤ ( 1 − δ ) / ρ \mu_{\mathcal{G}}\le(1-\delta)/\rho μ G ≤ ( 1 − δ ) / ρ , and hence ρ ≤ ( 1 − δ ) / μ G \rho\le(1-\delta)/\mu_{\mathcal{G}} ρ ≤ ( 1 − δ ) / μ G . Therefore
R G ( δ ) ≤ 1 − δ μ G . R_{\mathcal{G}}(\delta)\le\frac{1-\delta}{\mu_{\mathcal{G}}}. R G ( δ ) ≤ μ G 1 − δ .
For part (2), suppose that q G = ∞ q_{\mathcal{G}}=\infty q G = ∞ . Then H q G ( δ ) = δ H_{q_{\mathcal{G}}}(\delta)=\delta H q G ( δ ) = δ , so the lower and upper bounds in part (1) coincide. Hence, for every 0 < δ < 1 0<\delta<1 0 < δ < 1 ,
R G ( δ ) = 1 − δ μ G . R_{\mathcal{G}}(\delta)=\frac{1-\delta}{\mu_{\mathcal{G}}}. R G ( δ ) = μ G 1 − δ .
Finally, we prove part (3). Suppose that q G < ∞ q_{\mathcal{G}}<\infty q G < ∞ . There is a subsequence along which q i = q G q_i=q_{\mathcal{G}} q i = q G . For each i i i in this subsequence, choose a maximal subgroup M i < G i M_i<G_i M i < G i of index q G q_{\mathcal{G}} q G . Fix 1 − 1 / q G < δ < 1 1-1/q_{\mathcal{G}}<\delta<1 1 − 1/ q G < δ < 1 and 0 < ρ < 1 0<\rho<1 0 < ρ < 1 , and let N i N_i N i and A i A_i A i be as above. Put X i : = ∣ A i ∖ M i ∣ X_i:=|A_i\setminus M_i| X i := ∣ A i ∖ M i ∣ and p : = 1 − 1 / q G p:=1-1/q_{\mathcal{G}} p := 1 − 1/ q G . Then
X i ∼ Bin ( N i , p ) , δ ( A i ; G i ) ≤ X i N i , X_i\sim\operatorname{Bin}(N_i,p),
\qquad
\delta(A_i;G_i)\le\frac{X_i}{N_i}, X i ∼ Bin ( N i , p ) , δ ( A i ; G i ) ≤ N i X i ,
and
E [ X i N i ] = p , Var ( X i N i ) = p ( 1 − p ) N i . \mathbb{E}\left[\frac{X_i}{N_i}\right]=p,
\qquad
\operatorname{Var}\left(\frac{X_i}{N_i}\right)=\frac{p(1-p)}{N_i}. E [ N i X i ] = p , Var ( N i X i ) = N i p ( 1 − p ) .
Put ε : = δ − p > 0 \varepsilon:= \delta- p > 0 ε := δ − p > 0 . Since δ ( A i ; G i ) ≤ X i / N i \delta(A_i;G_i) \le X_i/N_i δ ( A i ; G i ) ≤ X i / N i , we have { δ ( A i ; G i ) ≥ δ } ⊆ { X i N i ≥ p + ε } \{\delta(A_i;G_i) \ge\delta\} \subseteq\left\{\frac{X_i}{N_i} \ge p + \varepsilon\right\} { δ ( A i ; G i ) ≥ δ } ⊆ { N i X i ≥ p + ε } . Therefore, by Chebyshev’s inequality,
P i [ δ ( A i ; G i ) ≥ δ ] ≤ P i [ X i N i − p ≥ ε ] ≤ P i [ ∣ X i N i − p ∣ ≥ ε ] ≤ p ( 1 − p ) N i ε 2 ⟶ 0 , i → ∞ \mathbb{P}_i[\delta(A_i;G_i) \ge\delta] \le\mathbb{P}_i\left[\frac{X_i}{N_i} - p \ge\varepsilon\right] \le\mathbb{P}_i\left[\left|\frac{X_i}{N_i} - p\right| \ge\varepsilon\right] \le\frac{p(1-p)}{N_i\varepsilon^2} \longrightarrow0,\quad i\to\infty P i [ δ ( A i ; G i ) ≥ δ ] ≤ P i [ N i X i − p ≥ ε ] ≤ P i [ N i X i − p ≥ ε ] ≤ N i ε 2 p ( 1 − p ) ⟶ 0 , i → ∞
since N i ≥ r i / ρ → ∞ N_i \ge r_i/\rho\to\infty N i ≥ r i / ρ → ∞ . Thus the success probability tends to zero along a subsequence, so P G ( δ , ρ ) = 0 \mathbb{P}_{\mathcal{G}}(\delta,\rho)=0 P G ( δ , ρ ) = 0 and G \mathcal{G} G is not ( δ , ρ ) (\delta,\rho) ( δ , ρ ) -GV for any 0 < ρ < 1 0<\rho<1 0 < ρ < 1 . Therefore R G ( δ ) = 0 R_{\mathcal{G}}(\delta)=0 R G ( δ ) = 0 .
The GV characterization in Theorem 4.6 determines when some nontrivial GV parameters exist. We next determine when the entire distance range 0 < δ < 1 0<\delta<1 0 < δ < 1 is attainable, that is, when G \mathcal{G} G is strong GV in the sense of Definition 1.6.
Proposition 4.9 (Characterization of strong GV). Let G = ( G i ) i ∈ N \mathcal{G}=(G_i)_{i\in\mathbb{N}} G = ( G i ) i ∈ N be a family of nontrivial finite groups, and let q G q_{\mathcal{G}} q G be as in Definition 4.2. Then:
(1) If q G = ∞ q_{\mathcal{G}}=\infty q G = ∞ and G \mathcal{G} G has uniform PMSG, then G \mathcal{G} G is strong GV.
(2) If rk G = ∞ \operatorname{rk}_{\mathcal{G}}=\infty rk G = ∞ , then
G is strong GV ⟺ { q G = ∞ , G has uniform PMSG . \mathcal{G}\text{ is strong GV}\quad\Longleftrightarrow\quad
\begin{cases}
q_{\mathcal{G}}=\infty,\\
\mathcal{G}\text{ has uniform PMSG}.
\end{cases} G is strong GV ⟺ { q G = ∞ , G has uniform PMSG .
Proof. The first assertion follows immediately from Theorem 4.6, since q G = ∞ q_{\mathcal{G}}=\infty q G = ∞ means that the range appearing there is 0 < δ < 1 0<\delta<1 0 < δ < 1 .
For the second assertion, the reverse implication follows from the first. Conversely, suppose that G \mathcal{G} G is strong GV. In particular, it is ( δ , ρ ) (\delta,\rho) ( δ , ρ ) -GV for some 0 < δ < 1 0<\delta<1 0 < δ < 1 and 0 < ρ < 1 0<\rho<1 0 < ρ < 1 , so Theorem 4.6 implies that G \mathcal{G} G has uniform PMSG.
It remains to show that q G = ∞ q_{\mathcal{G}}=\infty q G = ∞ . Otherwise, q G < ∞ q_{\mathcal{G}}<\infty q G < ∞ , and we may choose 1 − 1 / q G < δ < 1 1-1/q_{\mathcal{G}}<\delta<1 1 − 1/ q G < δ < 1 . Since rk ( G i ) → ∞ \operatorname{rk}(G_i)\to\infty rk ( G i ) → ∞ , Theorem 4.7 gives R G ( δ ) = 0 R_{\mathcal{G}}(\delta)=0 R G ( δ ) = 0 , contradicting the assumption that G \mathcal{G} G is strong GV. Therefore q G = ∞ q_{\mathcal{G}}=\infty q G = ∞ .
The assumption rk G = ∞ \operatorname{rk}_{\mathcal{G}}=\infty rk G = ∞ in the converse direction is essential. The following examples illustrate the two different behaviors that can occur when rk G < ∞ \operatorname{rk}_{\mathcal{G}}<\infty rk G < ∞ .
Lemma 5.1. Let H H H be a nonabelian finite simple group and let m ≥ 1 m \ge1 m ≥ 1 . Every maximal subgroup of H m H^m H m is of exactly one of the following types:
(i) a product-type subgroup H j − 1 × M × H m − j H^{j-1} \times M \times H^{m-j} H j − 1 × M × H m − j , where j ∈ [ m ] j \in[m] j ∈ [ m ] and M M M is a maximal subgroup of H H H ;
(ii) a diagonal-type subgroup D j , k , α = { ( h 1 , … , h m ) ∈ H m : h k = α ( h j ) } D_{j,k,\alpha} = \{(h_1,\ldots,h_m) \in H^m : h_k = \alpha(h_j)\} D j , k , α = {( h 1 , … , h m ) ∈ H m : h k = α ( h j )} , where $1 \le j < k \le m$ and α ∈ Aut ( H ) \alpha\in\operatorname{Aut}(H) α ∈ Aut ( H ) .
Consequently, for every s ≥ 2 s \ge2 s ≥ 2 ,
m s ( H m ) = m ⋅ m s ( H ) + 1 { s = ∣ H ∣ } ( m 2 ) ∣ Aut ( H ) ∣ . m_s(H^m) = m \cdot m_s(H) + \mathbf{1}_{\{s=|H|\}} \binom{m}{2} \lvert\operatorname{Aut}(H)\rvert. m s ( H m ) = m ⋅ m s ( H ) + 1 { s = ∣ H ∣ } ( 2 m ) ∣ Aut ( H )∣ .
Proof. By [Thé97, Lemma 1.3], the maximal subgroups of H × H H \times H H × H are precisely M × H M \times H M × H , H × M H \times M H × M , where M < max H M <_{\max} H M < m a x H , and { ( h , α ( h ) ) : h ∈ H } \{(h,\alpha(h)) : h \in H\} {( h , α ( h )) : h ∈ H } , where α ∈ Aut ( H ) \alpha\in\operatorname{Aut}(H) α ∈ Aut ( H ) .
Since H H H is nonabelian simple, it is perfect, and hence so is H m H^m H m . In particular, H m H^m H m has no normal subgroup of prime index. Therefore, [Thé97, Proposition 1.6] shows that every maximal subgroup of H m H^m H m is the inverse image of one of the above subgroups under a coordinate projection. These give precisely the product-type and diagonal-type subgroups in the statement.
There are m ⋅ m s ( H ) m \cdot m_s(H) m ⋅ m s ( H ) product-type maximal subgroups of index s s s . The diagonal-type subgroups all have index ∣ H ∣ \lvert H\rvert ∣ H ∣ , and there is one for each pair $1 \le j < k \le m$ and each α ∈ Aut ( H ) \alpha\in\operatorname{Aut}(H) α ∈ Aut ( H ) . Hence
m s ( H m ) = m ⋅ m s ( H ) + 1 { s = ∣ H ∣ } ( m 2 ) ∣ Aut ( H ) ∣ . m_s(H^m) = m \cdot m_s(H) + \mathbf{1}_{\{s=|H|\}} \binom{m}{2} \lvert\operatorname{Aut}(H)\rvert. m s ( H m ) = m ⋅ m s ( H ) + 1 { s = ∣ H ∣ } ( 2 m ) ∣ Aut ( H )∣ .
□
The next theorem extends the sharp GV threshold for random p p p -ary linear codes, corresponding to H = C p H = C_p H = C p , to direct powers of an arbitrary finite simple group.
Theorem 5.2. Let H H H be a fixed finite simple group and consider the family G = G H : = ( H m ) m ∈ N \mathcal{G} = \mathcal{G}_H := (H^m)_{m \in\mathbb{N}} G = G H := ( H m ) m ∈ N . For every 0 < δ < 1 0 < \delta< 1 0 < δ < 1 ,
R G ( δ ) = { log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ ) ) , 0 < δ < 1 − 1 q ( H ) , 0 , 1 − 1 q ( H ) ≤ δ < 1 , Range ( G ) = 1 − 1 q ( H ) . R_{\mathcal{G}}(\delta) =
\begin{cases}
\log_{|H|} q(H)(1-H_{q(H)}(\delta)), & 0 < \delta< 1-\dfrac{1}{q(H)},\\
0, & 1-\dfrac{1}{q(H)} \le\delta< 1,
\end{cases}
\qquad
\operatorname{Range}(\mathcal{G}) = 1-\dfrac{1}{q(H)}. R G ( δ ) = ⎩ ⎨ ⎧ log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ )) , 0 , 0 < δ < 1 − q ( H ) 1 , 1 − q ( H ) 1 ≤ δ < 1 , Range ( G ) = 1 − q ( H ) 1 . For every 0 < δ < 1 − 1 / q ( H ) 0 < \delta< 1-1/q(H) 0 < δ < 1 − 1/ q ( H ) and every 0 < ρ < 1 0 < \rho< 1 0 < ρ < 1 ,
P G ( δ , ρ ) = { 1 , ρ ≤ R G ( δ ) , 0 , ρ > R G ( δ ) . P_{\mathcal{G}}(\delta,\rho) =
\begin{cases}
1, & \rho\le R_{\mathcal{G}}(\delta),\\
0, & \rho> R_{\mathcal{G}}(\delta).
\end{cases} P G ( δ , ρ ) = { 1 , 0 , ρ ≤ R G ( δ ) , ρ > R G ( δ ) .
Proof. Fix 0 < ρ < 1 0 < \rho< 1 0 < ρ < 1 , put C : = 1 / ρ C := 1/\rho C := 1/ ρ , and set N m ( C ) : = ⌈ C rk ( H m ) ⌉ N_m(C) := \lceil C\,\operatorname{rk}(H^m)\rceil N m ( C ) := ⌈ C rk ( H m )⌉ . Let A m ( C ) A_m(C) A m ( C ) be a tuple of N m ( C ) N_m(C) N m ( C ) independent uniformly distributed elements of H m H^m H m . If H H H is abelian, then H ≅ C p H \cong C_p H ≅ C p for some prime p p p . Identifying H m H^m H m with F p m \mathbb{F}_p^m F p m and writing the elements of A m ( C ) A_m(C) A m ( C ) as the rows of a random matrix X ∈ F p N m ( C ) × m X \in\mathbb{F}_p^{N_m(C) \times m} X ∈ F p N m ( C ) × m , we have
δ ( A m ( C ) ; H m ) = 1 N m ( C ) min a ≠ 0 wt ( X a ) , \delta(A_m(C);H^m) = \frac{1}{N_m(C)} \min_{a \ne0} \operatorname{wt}(Xa), δ ( A m ( C ) ; H m ) = N m ( C ) 1 a = 0 min wt ( X a ) ,
since the maximal subgroups of F p m \mathbb{F}_p^m F p m are its hyperplanes. This is the normalized minimum distance of the associated random p p p -ary linear code. For 0 < δ < 1 − 1 / p 0 < \delta< 1-1/p 0 < δ < 1 − 1/ p , by [Fan+12, Corollary 3.2, Remark 3.3, and Lemma 2.1], R G ( δ ) = 1 − H p ( δ ) R_{\mathcal{G}}(\delta) = 1-H_p(\delta) R G ( δ ) = 1 − H p ( δ ) , and
P G ( δ , ρ ) = { 1 , ρ ≤ R G ( δ ) , 0 , ρ > R G ( δ ) . P_{\mathcal{G}}(\delta,\rho) =
\begin{cases}
1, & \rho\le R_{\mathcal{G}}(\delta),\\
0, & \rho> R_{\mathcal{G}}(\delta).
\end{cases} P G ( δ , ρ ) = { 1 , 0 , ρ ≤ R G ( δ ) , ρ > R G ( δ ) .
Since q ( H ) = ∣ H ∣ = p q(H) = |H| = p q ( H ) = ∣ H ∣ = p , in this range we obtain
R G ( δ ) = log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ ) ) . R_{\mathcal{G}}(\delta) = \log_{|H|} q(H)(1-H_{q(H)}(\delta)). R G ( δ ) = log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ )) .
In this case, q G = p q_{\mathcal{G}} = p q G = p , rk G = ∞ \operatorname{rk}_{\mathcal{G}} = \infty rk G = ∞ , and G \mathcal{G} G has uniform PMSG. The quantitative characterization gives R G ( δ ) = 0 R_{\mathcal{G}}(\delta) = 0 R G ( δ ) = 0 for δ > 1 − 1 / p \delta> 1-1/p δ > 1 − 1/ p and Range ( G ) = 1 − 1 / p \operatorname{Range}(\mathcal{G}) = 1-1/p Range ( G ) = 1 − 1/ p . At δ ∗ = 1 − 1 / p \delta_* = 1-1/p δ ∗ = 1 − 1/ p , the corresponding random matrix defines a p p p -ary linear code of length N m ( C ) N_m(C) N m ( C ) and dimension m m m whenever δ ( A m ( C ) ; H m ) ≥ δ ∗ \delta(A_m(C);H^m) \ge\delta_* δ ( A m ( C ) ; H m ) ≥ δ ∗ . If this event occurred for infinitely many m m m , these codes would have relative distance at least δ ∗ \delta_{*} δ ∗ and rates m / N m ( C ) → ρ > 0 m/N_m(C) \to\rho> 0 m / N m ( C ) → ρ > 0 , contradicting Theorem 1.3 . Hence P G ( δ ∗ , ρ ) = 0 P_{\mathcal{G}}(\delta_{*},\rho)=0 P G ( δ ∗ , ρ ) = 0 for every 0 < ρ < 1 0<\rho<1 0 < ρ < 1 , and R G ( δ ∗ ) = 0 R_{\mathcal{G}}(\delta_{*})=0 R G ( δ ∗ ) = 0 . We may therefore assume that H H H is nonabelian. Put r m : = rk ( H m ) r_m:=\operatorname{rk}(H^m) r m := rk ( H m ) and t m : = ⌊ ( 1 − δ ) N m ( C ) ⌋ + 1 t_m:=\lfloor(1-\delta)N_m(C)\rfloor+1 t m := ⌊( 1 − δ ) N m ( C )⌋ + 1 . By [Thé97, Proposition 3.4], r m = log ∣ H ∣ m + O ( 1 ) r_m=\log_{\lvert H\rvert}m+O(1) r m = log ∣ H ∣ m + O ( 1 ) . Therefore, log ∣ H ∣ m / N m ( C ) → 1 / C = ρ \log_{\lvert H\rvert}m/N_m(C)\to1/C=\rho log ∣ H ∣ m / N m ( C ) → 1/ C = ρ . By Lemma 5.1 ,
m s ( H m ) = m ⋅ m s ( H ) + 1 { s = ∣ H ∣ } ( m 2 ) ∣ Aut ( H ) ∣ . m_s(H^m)=m\cdot m_s(H)+\mathbf{1}_{\{s=\lvert H\rvert\}}\binom{m}{2}\lvert\operatorname{Aut}(H)\rvert. m s ( H m ) = m ⋅ m s ( H ) + 1 { s = ∣ H ∣} ( 2 m ) ∣ Aut ( H )∣ .
It follows that
M ( H m ) = max s ≥ 2 m s ( H m ) > 0 log ( m m s ( H ) + 1 { s = ∣ H ∣ } ( m 2 ) ∣ Aut ( H ) ∣ ) log s = max { max s ≥ 2 m s ( H ) > 0 log ( m m s ( H ) ) log s , log ( ( m 2 ) ∣ Aut ( H ) ∣ ) log ∣ H ∣ } + O ( 1 ) = max { log q ( H ) m , 2 log ∣ H ∣ m } + O ( 1 ) . \begin{aligned}
\mathcal{M}(H^m)=\max_{\substack{s\geq2\\m_s(H^m)>0}}\frac{\log\left(mm_s(H)+\mathbf{1}_{\{s=\lvert H\rvert\}}\binom{m}{2}\lvert\operatorname{Aut}(H)\rvert\right)}{\log s} \\
&=\max\left\{\max_{\substack{s\geq2\\m_s(H)>0}}\frac{\log(mm_s(H))}{\log s},\frac{\log\left(\binom{m}{2}\lvert\operatorname{Aut}(H)\rvert\right)}{\log\lvert H\rvert}\right\}+O(1) \\
&=\max\left\{\log_{q(H)}m,2\log_{\lvert H\rvert}m\right\}+O(1).
\end{aligned} M ( H m ) = s ≥ 2 m s ( H m ) > 0 max log s log ( m m s ( H ) + 1 { s = ∣ H ∣} ( 2 m ) ∣ Aut ( H )∣ ) = max ⎩ ⎨ ⎧ s ≥ 2 m s ( H ) > 0 max log s log ( m m s ( H )) , log ∣ H ∣ log ( ( 2 m ) ∣ Aut ( H )∣ ) ⎭ ⎬ ⎫ + O ( 1 ) = max { log q ( H ) m , 2 log ∣ H ∣ m } + O ( 1 ) .
Consequently,
μ G = lim sup m → ∞ M ( H m ) rk ( H m ) = max { log q ( H ) ∣ H ∣ , 2 } . \mu_{\mathcal{G}}=\limsup_{m\to\infty}\frac{\mathcal{M}(H^m)}{\operatorname{rk}(H^m)}
=\max\left\{\log_{q(H)}\lvert H\rvert,2\right\}. μ G = m → ∞ lim sup rk ( H m ) M ( H m ) = max { log q ( H ) ∣ H ∣ , 2 } .
We also have q ( H m ) = q ( H ) q(H^m)=q(H) q ( H m ) = q ( H ) . Indeed, placing a subgroup of index q ( H ) q(H) q ( H ) in one coordinate gives q ( H m ) ≤ q ( H ) q(H^m)\leq q(H) q ( H m ) ≤ q ( H ) . Conversely, let K < H m K<H^m K < H m . Since the direct factors generate H m H^m H m , some direct factor H j H_j H j is not contained in K K K . Hence H j ∩ K < H j H_j\cap K<H_j H j ∩ K < H j , and [ H m : K ] ≥ [ H j : H j ∩ K ] ≥ q ( H ) [H^m:K]\geq[H_j:H_j\cap K]\geq q(H) [ H m : K ] ≥ [ H j : H j ∩ K ] ≥ q ( H ) . Therefore q ( H m ) ≥ q ( H ) q(H^m)\geq q(H) q ( H m ) ≥ q ( H ) , proving the equality. For 1 − 1 / q ( H ) < δ < 1 1-1/q(H)<\delta<1 1 − 1/ q ( H ) < δ < 1 , Theorem 4.7 gives R G ( δ ) = 0 R_{\mathcal{G}}(\delta)=0 R G ( δ ) = 0 . We may therefore assume 0 < δ ≤ 1 − 1 / q ( H ) 0<\delta\leq1-1/q(H) 0 < δ ≤ 1 − 1/ q ( H ) . In this range, for 0 < δ < 1 − 1 / q ( H ) 0<\delta<1-1/q(H) 0 < δ < 1 − 1/ q ( H ) , Theorem 4.7 gives
R G ( δ ) ≥ 1 − H q ( H ) ( δ ) μ G = min { log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ ) ) , 1 − H q ( H ) ( δ ) 2 } . R_{\mathcal{G}}(\delta)\geq\frac{1-H_{q(H)}(\delta)}{\mu_{\mathcal{G}}}
=\min\left\{\log_{\lvert H\rvert}q(H)(1-H_{q(H)}(\delta)),\frac{1-H_{q(H)}(\delta)}{2}\right\}. R G ( δ ) ≥ μ G 1 − H q ( H ) ( δ ) = min { log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ )) , 2 1 − H q ( H ) ( δ ) } .
By [BEJ22, Theorem A(4)], q ( H ) 2 < ∣ H ∣ q(H)^2<\lvert H\rvert q ( H ) 2 < ∣ H ∣ , and hence log ∣ H ∣ q ( H ) < 1 / 2 \log_{\lvert H\rvert}q(H)<1/2 log ∣ H ∣ q ( H ) < 1/2 . Therefore,
log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ ) ) < 1 − H q ( H ) ( δ ) 2 . \log_{\lvert H\rvert}q(H)(1-H_{q(H)}(\delta))<\frac{1-H_{q(H)}(\delta)}{2}. log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ )) < 2 1 − H q ( H ) ( δ ) .
Hence, for 0 < δ < 1 − 1 / q ( H ) 0<\delta<1-1/q(H) 0 < δ < 1 − 1/ q ( H ) ,
R G ( δ ) ≥ log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ ) ) . R_{\mathcal{G}}(\delta)\geq\log_{\lvert H\rvert}q(H)(1-H_{q(H)}(\delta)). R G ( δ ) ≥ log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ )) .
At δ = 1 − 1 / q ( H ) \delta=1-1/q(H) δ = 1 − 1/ q ( H ) , we have 1 − H q ( H ) ( δ ) = 0 1-H_{q(H)}(\delta)=0 1 − H q ( H ) ( δ ) = 0 , and the trivial bound R G ( δ ) ≥ 0 R_{\mathcal{G}}(\delta)\geq0 R G ( δ ) ≥ 0 supplies the lower bound. We now prove the reverse inequality for 0 < δ ≤ 1 − 1 / q ( H ) 0<\delta\leq1-1/q(H) 0 < δ ≤ 1 − 1/ q ( H ) . Represent the elements of A m ( C ) A_m(C) A m ( C ) as the rows of a random matrix
X = ( x i j ) ∈ H N m ( C ) × m . X=(x_{ij})\in H^{N_m(C)\times m}. X = ( x ij ) ∈ H N m ( C ) × m .
Suppose that
ρ > log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ ) ) . \rho>\log_{\lvert H\rvert}q(H)(1-H_{q(H)}(\delta)). ρ > log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ )) .
Fix M < max H M<_{\max}H M < m a x H of index q ( H ) q(H) q ( H ) and, for each j ∈ [ m ] j\in[m] j ∈ [ m ] , put
Y m , j : = # { i ∈ [ N m ( C ) ] : x i j ∈ M } , E j : = { Y m , j ≥ t m } . Y_{m,j}:=\#\{i\in[N_m(C)]:x_{ij}\in M\},\qquad E_j:=\{Y_{m,j}\geq t_m\}. Y m , j := # { i ∈ [ N m ( C )] : x ij ∈ M } , E j := { Y m , j ≥ t m } .
Since P [ x i j ∈ M ] = 1 / q ( H ) \mathbb{P}[x_{ij}\in M]=1/q(H) P [ x ij ∈ M ] = 1/ q ( H ) , we have Y m , j ∼ Bin ( N m ( C ) , 1 q ( H ) ) Y_{m,j}\sim\operatorname{Bin}\left(N_m(C),\frac{1}{q(H)}\right) Y m , j ∼ Bin ( N m ( C ) , q ( H ) 1 ) . Moreover, the columns of X X X are independent, so the events E 1 , … , E m E_1,\ldots,E_m E 1 , … , E m are independent. Hence, by Equation (4) ,
p m : = P ( E j ) = q ( H ) − N m ( C ) ( 1 − H q ( H ) ( δ ) ) + o ( N m ( C ) ) . p_m:=\mathbb{P}(E_j)=q(H)^{-N_m(C)(1-H_{q(H)}(\delta))+o(N_m(C))}. p m := P ( E j ) = q ( H ) − N m ( C ) ( 1 − H q ( H ) ( δ )) + o ( N m ( C )) .
Since log ∣ H ∣ m / N m ( C ) → m → ∞ ρ \log_{\lvert H\rvert}m/N_m(C)\xrightarrow[m\to\infty]{}\rho log ∣ H ∣ m / N m ( C ) m → ∞ ρ , we have
1 N m ( C ) log ∣ H ∣ ( m p m ) → m → ∞ ρ − log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ ) ) > 0. \frac{1}{N_m(C)}\log_{\lvert H\rvert}(mp_m)\xrightarrow[m\to\infty]{}\rho-\log_{\lvert H\rvert}q(H)(1-H_{q(H)}(\delta))>0. N m ( C ) 1 log ∣ H ∣ ( m p m ) m → ∞ ρ − log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ )) > 0.
Thus p m p m → m → ∞ ∞ p_m p_m \xrightarrow[m\to\infty]{} \infty p m p m m → ∞ ∞ , and hence
P [ ⋃ j = 1 m E j ] = 1 − ( 1 − p m ) m ≥ 1 − e − m p m → m → ∞ 1. \mathbb{P}\left[\bigcup_{j=1}^{m} E_j\right] = 1-(1-p_m)^m \ge1-e^{-mp_m} \xrightarrow[m\to\infty]{} 1. P [ j = 1 ⋃ m E j ] = 1 − ( 1 − p m ) m ≥ 1 − e − m p m m → ∞ 1.
Whenever some E j E_j E j occurs, at least t m > ( 1 − δ ) N m ( C ) t_m>(1-\delta)N_m(C) t m > ( 1 − δ ) N m ( C ) rows of X X X belong to the maximal subgroup H j − 1 × M × H m − j < H m H^{j-1}\times M\times H^{m-j}<H^m H j − 1 × M × H m − j < H m . Consequently, P G ( δ , ρ ) = 0 P_{\mathcal{G}}(\delta,\rho)=0 P G ( δ , ρ ) = 0 . It follows that
R G ( δ ) ≤ log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ ) ) . R_{\mathcal{G}}(\delta)\le\log_{|H|}q(H)(1-H_{q(H)}(\delta)). R G ( δ ) ≤ log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ )) .
For 0 < δ < 1 − 1 / q ( H ) 0<\delta<1-1/q(H) 0 < δ < 1 − 1/ q ( H ) , combining the two inequalities proves the rate formula. At δ = 1 − 1 / q ( H ) \delta=1-1/q(H) δ = 1 − 1/ q ( H ) , the right-hand side is zero, so this same reverse inequality proves R G ( δ ) = 0 R_{\mathcal{G}}(\delta)=0 R G ( δ ) = 0 . We may therefore assume 0 < δ < 1 − 1 / q ( H ) 0<\delta<1-1/q(H) 0 < δ < 1 − 1/ q ( H ) in the following threshold case, so that ρ 0 > 0 \rho_0>0 ρ 0 > 0 .
We now treat the threshold value ρ 0 : = log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ ) ) \rho_0:=\log_{|H|}q(H)(1-H_{q(H)}(\delta)) ρ 0 := log ∣ H ∣ q ( H ) ( 1 − H q ( H ) ( δ )) . For brevity, put N m : = N m ( 1 / ρ 0 ) N_m:=N_m(1/\rho_0) N m := N m ( 1/ ρ 0 ) . Since rk ( H m ) = log ∣ H ∣ m + O ( 1 ) \operatorname{rk}(H^m)=\log_{|H|}m+O(1) rk ( H m ) = log ∣ H ∣ m + O ( 1 ) and N m = ⌈ rk ( H m ) / ρ 0 ⌉ N_m=\lceil\operatorname{rk}(H^m)/\rho_0\rceil N m = ⌈ rk ( H m ) / ρ 0 ⌉ , we have
log ∣ H ∣ m = N m ρ 0 + O ( 1 ) . \log_{|H|}m=N_m\rho_0+O(1). log ∣ H ∣ m = N m ρ 0 + O ( 1 ) .
Since every maximal subgroup of H m H^m H m has index at most ∣ H ∣ |H| ∣ H ∣ , the possible indices s s s lie in the fixed finite set { q ( H ) , … , ∣ H ∣ } \{q(H),\ldots,|H|\} { q ( H ) , … , ∣ H ∣ } . If δ ( A m ( 1 / ρ 0 ) ; H m ) < δ \delta(A_m(1/\rho_0);H^m)<\delta δ ( A m ( 1/ ρ 0 ) ; H m ) < δ , then some maximal subgroup contains at least ⌊ ( 1 − δ ) N m ⌋ + 1 \lfloor(1-\delta)N_m\rfloor+1 ⌊( 1 − δ ) N m ⌋ + 1 rows. For each maximal subgroup of index s s s , the binomial estimate Equation (5) gives a failure probability at most K ∣ H ∣ , δ N m − 1 / 2 s − N m ( 1 − H s ( δ ) ) K_{|H|,\delta}N_m^{-1/2}s^{-N_m(1-H_s(\delta))} K ∣ H ∣ , δ N m − 1/2 s − N m ( 1 − H s ( δ )) , where the constant is uniform over this finite set of indices. A union bound, followed by substitution of the formula for m s ( H m ) m_s(H^m) m s ( H m ) , gives
P [ δ ( A m ( 1 / ρ 0 ) ; H m ) < δ ] ≤ K ∣ H ∣ , δ N m − 1 / 2 ∑ s = q ( H ) ∣ H ∣ ( m m s ( H ) + 1 { s = ∣ H ∣ } ( m 2 ) ∣ Aut ( H ) ∣ ) s − N m ( 1 − H s ( δ ) ) = K ∣ H ∣ , δ N m − 1 / 2 ( ∑ s = q ( H ) ∣ H ∣ m m s ( H ) s − N m ( 1 − H s ( δ ) ) + ( m 2 ) ∣ Aut ( H ) ∣ ∣ H ∣ − N m ( 1 − H ∣ H ∣ ( δ ) ) ) = : K ∣ H ∣ , δ N m − 1 / 2 B m . \begin{aligned}
\mathbb{P}\left[\delta(A_m(1/\rho_0);H^m)<\delta\right] \\
&\le K_{|H|,\delta}N_m^{-1/2}\sum_{s=q(H)}^{|H|}\left(mm_s(H)+\mathbf{1}_{\{s=|H|\}}\binom{m}{2}|\operatorname{Aut}(H)|\right)s^{-N_m(1-H_s(\delta))} \\
&=K_{|H|,\delta}N_m^{-1/2}\left(\sum_{s=q(H)}^{|H|}mm_s(H)s^{-N_m(1-H_s(\delta))}+\binom{m}{2}|\operatorname{Aut}(H)||H|^{-N_m(1-H_{|H|}(\delta))}\right)=:K_{|H|,\delta}N_m^{-1/2}B_m.
\end{aligned} P [ δ ( A m ( 1/ ρ 0 ) ; H m ) < δ ] ≤ K ∣ H ∣ , δ N m − 1/2 s = q ( H ) ∑ ∣ H ∣ ( m m s ( H ) + 1 { s = ∣ H ∣ } ( 2 m ) ∣ Aut ( H ) ∣ ) s − N m ( 1 − H s ( δ )) = K ∣ H ∣ , δ N m − 1/2 s = q ( H ) ∑ ∣ H ∣ m m s ( H ) s − N m ( 1 − H s ( δ )) + ( 2 m ) ∣ Aut ( H ) ∣∣ H ∣ − N m ( 1 − H ∣ H ∣ ( δ )) =: K ∣ H ∣ , δ N m − 1/2 B m .
For s = q ( H ) s=q(H) s = q ( H ) , the corresponding summand is bounded because
m q ( H ) − N m ( 1 − H q ( H ) ( δ ) ) = ∣ H ∣ log ∣ H ∣ m − N m ρ 0 = O ( 1 ) . mq(H)^{-N_m(1-H_{q(H)}(\delta))}=|H|^{\log_{|H|}m-N_m\rho_0}=O(1). m q ( H ) − N m ( 1 − H q ( H ) ( δ )) = ∣ H ∣ l o g ∣ H ∣ m − N m ρ 0 = O ( 1 ) .
Put
ϕ ( s ) : = log ∣ H ∣ s ( 1 − H s ( δ ) ) . \phi(s):=\log_{|H|}s(1-H_s(\delta)). ϕ ( s ) := log ∣ H ∣ s ( 1 − H s ( δ )) .
By Lemma 2.2 and positivity of 1 − H s ( δ ) 1-H_s(\delta) 1 − H s ( δ ) , ϕ \phi ϕ is strictly increasing in s s s . In particular, for each s > q ( H ) s>q(H) s > q ( H ) we have ϕ ( s ) > ϕ ( q ( H ) ) = ρ 0 \phi(s)>\phi(q(H))=\rho_0 ϕ ( s ) > ϕ ( q ( H )) = ρ 0 . Hence
m s − N m ( 1 − H s ( δ ) ) = ∣ H ∣ log ∣ H ∣ m − N m ϕ ( s ) = ∣ H ∣ N m ( ρ 0 − ϕ ( s ) ) + O ( 1 ) ⟶ 0. ms^{-N_m(1-H_s(\delta))}=|H|^{\log_{|H|}m-N_m\phi(s)}=|H|^{N_m(\rho_0-\phi(s))+O(1)}\longrightarrow0. m s − N m ( 1 − H s ( δ )) = ∣ H ∣ l o g ∣ H ∣ m − N m ϕ ( s ) = ∣ H ∣ N m ( ρ 0 − ϕ ( s )) + O ( 1 ) ⟶ 0.
The convergence is exponential since ϕ ( s ) > ρ 0 \phi(s)>\rho_0 ϕ ( s ) > ρ 0 . Finally,
( m 2 ) ∣ H ∣ − N m ( 1 − H ∣ H ∣ ( δ ) ) = O ( ∣ H ∣ N m ( 2 ρ 0 − ( 1 − H ∣ H ∣ ( δ ) ) ) ) ⟶ 0 , \binom{m}{2}|H|^{-N_m(1-H_{|H|}(\delta))}=O\left(|H|^{N_m(2\rho_0-(1-H_{|H|}(\delta)))}\right)\longrightarrow0, ( 2 m ) ∣ H ∣ − N m ( 1 − H ∣ H ∣ ( δ )) = O ( ∣ H ∣ N m ( 2 ρ 0 − ( 1 − H ∣ H ∣ ( δ ))) ) ⟶ 0 ,
because q ( H ) 2 < ∣ H ∣ q(H)^2<|H| q ( H ) 2 < ∣ H ∣ and, by the strict increase of ϕ \phi ϕ ,
1 − H ∣ H ∣ ( δ ) = ϕ ( ∣ H ∣ ) > ϕ ( q ( H ) 2 ) ≥ log ∣ H ∣ ( q ( H ) 2 ) ( 1 − H q ( H ) ( δ ) ) = 2 ρ 0 . 1-H_{|H|}(\delta)=\phi(|H|)>\phi(q(H)^2)\ge\log_{|H|}(q(H)^2)(1-H_{q(H)}(\delta))=2\rho_0. 1 − H ∣ H ∣ ( δ ) = ϕ ( ∣ H ∣ ) > ϕ ( q ( H ) 2 ) ≥ log ∣ H ∣ ( q ( H ) 2 ) ( 1 − H q ( H ) ( δ )) = 2 ρ 0 .
The estimates above show that B m = O ( 1 ) B_m=O(1) B m = O ( 1 ) . Hence the factor N m − 1 / 2 N_m^{-1/2} N m − 1/2 forces the failure probability to zero. Therefore P G ( δ , ρ 0 ) = 1 P_{\mathcal{G}}(\delta,\rho_0)=1 P G ( δ , ρ 0 ) = 1 . For nonabelian H H H , the preceding computation gives q G = q ( H ) q_{\mathcal{G}}=q(H) q G = q ( H ) and μ G < ∞ \mu_{\mathcal{G}}<\infty μ G < ∞ , while rk G = ∞ \operatorname{rk}_{\mathcal{G}}=\infty rk G = ∞ . Thus Theorem 4.7 gives R G ( δ ) = 0 R_{\mathcal{G}}(\delta)=0 R G ( δ ) = 0 for 1 − 1 / q ( H ) < δ < 1 1-1/q(H)<\delta<1 1 − 1/ q ( H ) < δ < 1 . The exact rate formula is positive for 0 < δ < 1 − 1 / q ( H ) 0<\delta<1-1/q(H) 0 < δ < 1 − 1/ q ( H ) . Therefore
Range ( G ) = 1 − 1 q ( H ) . \operatorname{Range}(\mathcal{G})=1-\frac{1}{q(H)}. Range ( G ) = 1 − q ( H ) 1 .
The preceding computation is exact for powers of a fixed simple group. The general rate bound also gives useful conclusions for families whose orders grow moderately relative to their generating ranks.
Corollary 5.3. Let G = ( G i ) i ≥ 1 \mathcal{G}=(G_i)_{i\ge1} G = ( G i ) i ≥ 1 be a family of nontrivial finite groups. Put r i = rk ( G i ) r_i=\operatorname{rk}(G_i) r i = rk ( G i ) and assume that rk G = ∞ \operatorname{rk}\mathcal{G}=\infty rk G = ∞ and log log ∣ G i ∣ = o ( r i ) \log\log|G_i|=o(r_i) log log ∣ G i ∣ = o ( r i ) . Suppose that q G < ∞ q_{\mathcal{G}}<\infty q G < ∞ . Then, for every 0 < δ < 1 − 1 / q G 0<\delta<1-1/q_{\mathcal{G}} 0 < δ < 1 − 1/ q G ,
R G ( δ ) ≥ 1 − H q G ( δ ) . R_{\mathcal{G}}(\delta)\ge1-H_{q_{\mathcal{G}}}(\delta). R G ( δ ) ≥ 1 − H q G ( δ ) . Moreover, P G ( δ , ρ ) = 1 P_{\mathcal{G}}(\delta,\rho)=1 P G ( δ , ρ ) = 1 for every 0 < ρ < 1 − H q G ( δ ) 0<\rho<1-H_{q_{\mathcal{G}}}(\delta) 0 < ρ < 1 − H q G ( δ ) .
Proof. By [Lub02, Theorem 2.1], M ( G i ) ≤ r i + 2 log log ∣ G i ∣ + 2 \mathcal{M}(G_i)\le r_i+2\log\log|G_i|+2 M ( G i ) ≤ r i + 2 log log ∣ G i ∣ + 2 . Hence μ G = 1 \mu_{\mathcal{G}}=1 μ G = 1 . Therefore, Theorem 4.7 gives
R G ( δ ) ≥ 1 − H q G ( δ ) μ G = 1 − H q G ( δ ) . R_{\mathcal{G}}(\delta)\ge\frac{1-H_{q_{\mathcal{G}}}(\delta)}{\mu_{\mathcal{G}}}=1-H_{q_{\mathcal{G}}}(\delta). R G ( δ ) ≥ μ G 1 − H q G ( δ ) = 1 − H q G ( δ ) . The assertion about P G P_{\mathcal{G}} P G follows from the convergence statement in Theorem 4.7 . □
Direct powers of a fixed nonperfect group satisfy these growth hypotheses automatically, giving the following concrete application.
Corollary 5.4 (Direct powers of nonperfect groups). Let H H H be a fixed finite nonperfect group, and let G : = G H = ( H m ) m ≥ 1 \mathcal{G}:=\mathcal{G}_H=(H^m)_{m\ge1} G := G H = ( H m ) m ≥ 1 . Then q G = q ( H ) q_{\mathcal{G}}=q(H) q G = q ( H ) and, for every 0 < δ < 1 − 1 / q G 0<\delta<1-1/q_{\mathcal{G}} 0 < δ < 1 − 1/ q G ,
R G ( δ ) ≥ 1 − H q G ( δ ) . R_{\mathcal{G}}(\delta)\ge1-H_{q_{\mathcal{G}}}(\delta). R G ( δ ) ≥ 1 − H q G ( δ ) . Moreover, P G ( δ , ρ ) = 1 P_{\mathcal{G}}(\delta,\rho)=1 P G ( δ , ρ ) = 1 for every 0 < ρ < 1 − H q G ( δ ) 0<\rho<1-H_{q_{\mathcal{G}}}(\delta) 0 < ρ < 1 − H q G ( δ ) .
Proof. Since H H H is nonperfect, it admits a quotient H ↠ C p H\twoheadrightarrow C_p H ↠ C p for some prime p p p . Hence H m ↠ C p m H^m\twoheadrightarrow C_p^m H m ↠ C p m , and therefore m ≤ rk ( H m ) ≤ m rk ( H ) m\le\operatorname{rk}(H^m)\le m\operatorname{rk}(H) m ≤ rk ( H m ) ≤ m rk ( H ) . Thus rk ( H m ) → ∞ \operatorname{rk}(H^m)\to\infty rk ( H m ) → ∞ and log 2 log 2 ∣ H m ∣ = log 2 m + O ( 1 ) = o ( rk ( H m ) ) \log_2\log_2|H^m|=\log_2m+O(1)=o(\operatorname{rk}(H^m)) log 2 log 2 ∣ H m ∣ = log 2 m + O ( 1 ) = o ( rk ( H m )) . As in the proof of Theorem 5.2 , q ( H m ) = q ( H ) q(H^m)=q(H) q ( H m ) = q ( H ) . In particular, q G = q ( H ) q_{\mathcal{G}}=q(H) q G = q ( H ) . The result now follows from Corollary 5.3 . □
Finite solvable groups give a broader application of the characterization in Theorem 4.6. Mann proved that every finite solvable group G G G satisfies M ( G ) ≤ 13 rk ( G ) / 4 + 2 \mathcal{M}(G)\le13\operatorname{rk}(G)/4+2 M ( G ) ≤ 13 rk ( G ) /4 + 2 [2 proof of Theorem 10, p. 437] . Lucchini, Menegazzo, and Morigi obtained the sharp leading constant as follows. Let F ^ r s o l \widehat{F}^{\mathrm{sol}}_r F r sol be the free prosolvable group of rank r r r . For a finitely generated profinite group Γ \Gamma Γ , let
m s ( Γ ) : = # { M < max Γ : M is open and [ Γ : M ] = s } , m_s(\Gamma):=\#\{M<_{\max}\Gamma:M\text{ is open and }[\Gamma:M]=s\}, m s ( Γ ) := # { M < m a x Γ : M is open and [ Γ : M ] = s } ,
and M ( Γ ) : = sup s ≥ 2 m s ( Γ ) > 0 log m s ( Γ ) log s \mathcal{M}(\Gamma):=\sup_{\substack{s\ge2\\m_s(\Gamma)>0}}\frac{\log m_s(\Gamma)}{\log s} M ( Γ ) := sup s ≥ 2 m s ( Γ ) > 0 l o g s l o g m s ( Γ ) . Their theorem states that, for r ≥ 3 r\ge3 r ≥ 3 ,
c 3 ( r − 1 ) + 1 ≤ M ( F ^ r s o l ) ≤ max { c 3 ( r − 1 ) + 1 , c 2 r } , c_3(r-1)+1\le\mathcal{M}(\widehat{F}^{\mathrm{sol}}_r)\le\max\{c_3(r-1)+1,c_2r\}, c 3 ( r − 1 ) + 1 ≤ M ( F r sol ) ≤ max { c 3 ( r − 1 ) + 1 , c 2 r } ,
where c 3 : = 1 + log 9 48 + 1 3 log 9 24 = 3.243991 … c_3:=1+\log_9 48+\frac{1}{3}\log_9 24=3.243991\ldots c 3 := 1 + log 9 48 + 3 1 log 9 24 = 3.243991 … and c 2 : = 1 + log 4 6 + 1 3 log 4 24 = 3.056 … c_2:=1+\log_4 6+\frac{1}{3}\log_4 24=3.056\ldots c 2 := 1 + log 4 6 + 3 1 log 4 24 = 3.056 … [LMM06, Theorem 4]. The upper-bound argument leading to this theorem gives, for every s ≥ 2 s\ge2 s ≥ 2 , m s ( F ^ r s o l ) ≤ s c 3 r + 2 m_s(\widehat{F}^{\mathrm{sol}}_r)\le s^{c_3r+2} m s ( F r sol ) ≤ s c 3 r + 2 [LMM06, proof of Theorem 4].
Now let G G G be a finite solvable group with rk ( G ) = r \operatorname{rk}(G)=r rk ( G ) = r . By the universal property, G G G is a quotient of F ^ r s o l \widehat{F}^{\mathrm{sol}}_r F r sol . Taking preimages sends distinct maximal subgroups of G G G of index s s s to distinct maximal open subgroups of F ^ r s o l \widehat{F}^{\mathrm{sol}}_r F r sol of the same index. Consequently, m s ( G ) ≤ m s ( F ^ r s o l ) m_s(G)\le m_s(\widehat{F}^{\mathrm{sol}}_r) m s ( G ) ≤ m s ( F r sol ) , and hence
M ( G ) ≤ c 3 rk ( G ) + 2. (7) \mathcal{M}(G)\le c_3\operatorname{rk}(G)+2. \tag*{(7)} M ( G ) ≤ c 3 rk ( G ) + 2. (7)
Thus every family of nontrivial finite solvable groups has uniform PMSG and hence is a GV family by Theorem 4.6. When the generating ranks tend to infinity, (7) gives μ G ≤ c 3 \mu_{\mathcal{G}}\le c_3 μ G ≤ c 3 , and Theorem 4.7 gives the following explicit rate.
Corollary 5.5 (Finite solvable groups). Let G = ( G i ) i ≥ 1 \mathcal{G}=(G_i)_{i\ge1} G = ( G i ) i ≥ 1 be a family of nontrivial finite solvable groups such that rk G = ∞ \operatorname{rk}\mathcal{G}=\infty rk G = ∞ . Then, for every 0 < δ < 1 − 1 / q G 0<\delta<1-1/q_{\mathcal{G}} 0 < δ < 1 − 1/ q G ,
R G ( δ ) ≥ 1 c 3 ( 1 − H q G ( δ ) ) , R_{\mathcal{G}}(\delta)\ge\frac{1}{c_3}(1-H_{q_{\mathcal{G}}}(\delta)), R G ( δ ) ≥ c 3 1 ( 1 − H q G ( δ )) , where, as usual, H q G ( δ ) = δ H_{q_{\mathcal{G}}}(\delta)=\delta H q G ( δ ) = δ if q G = ∞ q_{\mathcal{G}}=\infty q G = ∞ .
The lower bound in the quoted theorem also shows that the coefficient c 3 c_3 c 3 is sharp. Indeed, with the analogous definition of μ \mu μ for profinite families using maximal open-subgroup growth, the family F ^ s o l = ( F ^ r s o l ) r ≥ 3 \widehat{\mathcal{F}}^{\mathrm{sol}} = (\widehat{F}^{\mathrm{sol}}_r)_{r\ge3} F sol = ( F r sol ) r ≥ 3 satisfies μ F ^ s o l = c 3 \mu_{\widehat{\mathcal{F}}^{\mathrm{sol}}}=c_3 μ F sol = c 3 .
Using (7) in Lemma 4.5 also shows that every nontrivial finite solvable group G G G with rk ( G ) ≥ 8 \operatorname{rk}(G) \ge8 rk ( G ) ≥ 8 has a generating multiset A A A with ∣ A ∣ ≤ 7 rk ( G ) |A| \le7\operatorname{rk}(G) ∣ A ∣ ≤ 7 rk ( G ) and δ ( A ; G ) ≥ 1 / 10 \delta(A;G) \ge1/10 δ ( A ; G ) ≥ 1/10 . Thus, the constant 85 in [CDL24, Theorem 1.13] can be replaced by 7.
After showing that many families are GV, we conclude with a family that is not GV.
Example 5.6. Let G ℓ = A ℓ ℓ ! G_\ell=A_\ell^{\ell!} G ℓ = A ℓ ℓ ! for ℓ ≥ 7 \ell\ge7 ℓ ≥ 7 . By Dix69, Theorem 1 and KL90, Corollary 7, we have rk ( G ℓ ) = 3 \operatorname{rk}(G_\ell)=3 rk ( G ℓ ) = 3 for all sufficiently large ℓ \ell ℓ .
For each j ∈ [ ℓ ! ] j\in[\ell!] j ∈ [ ℓ !] , the subgroup
M ℓ , j = A ℓ j − 1 × Stab A ℓ ( 1 ) × A ℓ ℓ ! − j M_{\ell,j}=A_\ell^{j-1}\times\operatorname{Stab}_{A_\ell}(1)\times A_\ell^{\ell!-j} M ℓ , j = A ℓ j − 1 × Stab A ℓ ( 1 ) × A ℓ ℓ ! − j is maximal in G ℓ G_\ell G ℓ and has index ℓ \ell ℓ . Hence G ℓ G_\ell G ℓ has at least ℓ ! \ell! ℓ ! maximal subgroups of index ℓ \ell ℓ . For every fixed C > 0 C>0 C > 0 ,
ℓ ! ℓ C rk ( G ℓ ) = ℓ ! ℓ 3 C ⟶ ∞ . \frac{\ell!}{\ell^{C\operatorname{rk}(G_\ell)}}=\frac{\ell!}{\ell^{3C}}\longrightarrow\infty. ℓ C rk ( G ℓ ) ℓ ! = ℓ 3 C ℓ ! ⟶ ∞. Thus ( G ℓ ) ℓ ≥ 7 (G_\ell)_{\ell\ge7} ( G ℓ ) ℓ ≥ 7 does not have uniform PMSG and, by Theorem 4.6, is not GV.
Michael Best
Weizmann institute of Science
Rehovot, Israel.
Email address: michael.best@weizmann.ac.il
Alexander Lubotzky
Weizmann institute of Science
Rehovot, Israel.
Email address: alex.lubotzky@mail.huji.ac.il