betaFeedback

WorksMathematics

Random Non-Commutative Error-Correcting Codes

Abstract

Chapman, Dinur, and Lubotzky recently introduced the theory of non-commutative error-correcting codes, generalizing classical coding theory to arbitrary groups via δδ-robust subsets used to detect proper subgroups. Building on this foundation, this paper systematically studies an analogue of random codes for arbitrary groups, exploring the extent to which the classical Gilbert-Varshamov (GV) bound holds in this non-commutative setting. While random universal codes of linear size in free groups are shown to be asymptotically bad, we establish a complete characterization for general families of finite groups. Specifically, a family of finite groups admits good random codes (forming a GV family) if and only if it exhibits uniform polynomial maximal-subgroup growth. Furthermore, we provide explicit quantitative bounds on the rate and optimal distance range based on intrinsic parameters, proving that families of finite solvable groups always form GV families and determining the exact probabilistic rate for direct powers of a fixed finite simple group.

Introduction

Let pp be a prime and let Fpn\mathbb{F}_p^n be the nn-dimensional vector space over the finite field Fp\mathbb{F}_p. An [n,k,d]p[n,k,d]_p linear code is a linear subspace CC of Fpn\mathbb{F}_p^n of dimension kk and distance dd; that is, the Hamming weight of every nonzero vector v∈Cv \in C is at least dd. A family of [ni,ki,di]p[n_i,k_i,d_i]_p codes Ci≤FpniC_i \leq\mathbb{F}_p^{n_i}, where ni⟶∞n_i \longrightarrow\infty, is called (asymptotically) good if there exist δ,ρ>0\delta,\rho> 0 such that di/ni≥δd_i/n_i \geq\delta and ki/ni≥ρk_i/n_i \geq\rho. We call ρ(Ci):=ki/ni\rho(C_i) := k_i/n_i the rate of the code and δ(Ci):=di/ni\delta(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/p0 < \delta< 1 - 1/p and 0<ρ<1−Hp(δ)0 < \rho< 1 - H_p(\delta). Then a random linear code in Fpn\mathbb{F}_p^n of rate ρ\rho has normalized distance at least δ\delta with high probability.

Here, for a real number s>1s > 1, we denote the ss-ary entropy by Hs(δ)H_s(\delta) for 0<δ<10 < \delta< 1, where

Hs(δ)=δ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)}

By a random code CC of rate ρ\rho, we mean that k=⌊ρn⌋k=\lfloor\rho n\rfloor vectors in Fpn\mathbb{F}_p^n are chosen independently and uniformly at random and that CC is the subspace they span. The condition δ<1−1/p\delta< 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 Ci≤FpniC_i \leq\mathbb{F}_p^{n_i}, ni⟶∞n_i \longrightarrow\infty, and δ(Ci)≥1−1/p\delta(C_i) \geq1 - 1/p, then ρ(Ci)⟶0\rho(C_i) \longrightarrow0.

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 GG be any finitely generated group, let 0<δ<10 < \delta< 1, and let A\mathcal{A} be a finite tuple in GG, viewed as a multiset. We say that A\mathcal{A} is δ\delta-robust if every submultiset containing more than (1−δ)∣A∣(1-\delta)|\mathcal{A}| of its entries generates GG. All cardinalities and intersections involving sampled tuples are understood to count multiplicity.

For a finite tuple A\mathcal{A} in GG, 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\}.

Thus AA is δ\delta-robust if and only if δ(A;G)≥δ\delta(A;G) \ge\delta. We write rk⁡(G)\operatorname{rk}(G) for the minimal number of generators of GG. 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 and C>1C > 1 such that every finitely generated group GG has a δ\delta-robust subset of size at most Crk⁡(G)C\operatorname{rk}(G).

Theorem 1.1 is a special case of Theorem 1.5. Indeed, apply Theorem 1.5 to G=FpkG = \mathbb{F}_p^k to obtain a robust subset A={α1,…,αn}⊆FpkA = \{\alpha_1,\ldots,\alpha_n\} \subseteq\mathbb{F}_p^k. Let CC be the image of the linear map

T:Fpk⟶Fpn,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).

Here, for α=(a1,…,ak)\alpha= (a_1,\ldots,a_k) and β=(b1,…,bk)\beta= (b_1,\ldots,b_k), we put ⟨β,α⟩=∑j=1kajbj\langle\beta,\alpha\rangle= \sum_{j=1}^{k} a_jb_j. One easily checks that C=T(Fpk)≤FpnC = T(\mathbb{F}_p^k) \leq\mathbb{F}_p^n has dimension kk and normalized distance at least δ\delta. Since n≤Ckn \leq Ck, its rate is at least 1/C1/C.

Every kk-generated group is a quotient of the free group FkF_k of rank kk, and robustness is preserved under quotients. It therefore suffices to construct robust subsets in FkF_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×nk \times n generator matrix, considered in the binary case in [BF02, Section II-C]. Viewing the matrix by columns gives a random nn-tuple in Fpk\mathbb{F}_p^k. This suggests our general model: we ask when a random tuple in a group GG is robust.

To formalize this model, let G=(Gi)i≥1\mathcal{G} = (G_i)_{i\geq1} be a family of nontrivial finitely generated groups, where each GiG_i is equipped with a probability measure Pi\mathbb{P}_i. For 0<ρ<10 < \rho< 1, put Ni(ρ):=⌈rk⁡(Gi)/ρ⌉N_i(\rho) := \lceil\operatorname{rk}(G_i)/\rho\rceil and let Ai(ρ)A_i(\rho) be a tuple of Ni(ρ)N_i(\rho) independent Pi\mathbb{P}_i-distributed elements of GiG_i. We use the same notation Pi\mathbb{P}_i for the corresponding product measure on such tuples.

Definition 1.6 ((δ,ρ\delta,\rho)-GV family). The family G\mathcal{G} is a (δ,ρ)(\delta,\rho)-Gilbert–Varshamov family, or a (δ,ρ)(\delta,\rho)-GV family, if

PG(δ,ρ):=lim inf⁡i→∞Pi[δ(Ai(ρ);Gi)≥δ]>0.\mathbb{P}_{\mathcal{G}}(\delta,\rho) := \liminf_{i\to\infty} \mathbb{P}_i[\delta(A_i(\rho);G_i) \geq\delta] > 0.

We call G\mathcal{G} a GV family if this holds for some 0<δ,ρ<10 < \delta,\rho< 1. We call G\mathcal{G} strong GV if, for every 0<δ<10 < \delta< 1, there is some 0<ρ<10 < \rho< 1 for which G\mathcal{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 11, 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 Fk=⟨x1,…,xk⟩F_k = \langle x_1,\ldots,x_k\rangle and S={i1<⋯<ir}⊆[k]S = \{i_1 < \cdots< i_r\} \subseteq[k], put xS=xi1⋯xirx_S = x_{i_1}\cdots x_{i_r} and Hk:={xS:S⊆[k]}\mathcal{H}_k := \{x_S : S \subseteq[k]\}. As shown in [CDL24, Theorem 3.3 and its proof], this universal Hadamard code has 2k2^k elements and detection probability at least 1/21/2. Thus its normalized distance is bounded away from zero, but its rate k/2kk/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 Hk\mathcal{H}_k.

Theorem 1.7. Let Pk\mathbb{P}_k be the uniform probability measure on Hk\mathcal{H}_k. For C>1C > 1, let Ak(C)A_k(C) be a tuple of ⌈Ck⌉\lceil Ck\rceil independent Pk\mathbb{P}_k-distributed elements of FkF_k. Then

Pk[δ(Ak(C);Fk)=0]→k→∞1.\mathbb{P}_k[\delta(A_k(C);F_k) = 0] \xrightarrow[k\to\infty]{} 1.

In particular, the family (Fk,Pk)k≥1(F_k,\mathbb{P}_k)_{k\geq1} 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 GiG_i are finite and, unless specified otherwise, Πi\Pi_i is the uniform probability measure on GiG_i.

To state our results for GV families of finite groups, write q(G)q(G) for the smallest index of a proper subgroup of GG, and put qG:=lim inf⁡i→∞q(Gi)q_{\mathcal{G}} := \liminf_{i\to\infty} q(G_i).

We say that G\mathcal{G} has uniform polynomial maximal-subgroup growth, or uniform PMSG, if there is a constant A≥0A \ge0 such that, for all sufficiently large ii and every s≥2s \ge2, the number of maximal subgroups of index ss in GiG_i is at most sArk⁡(Gi)s^{A\operatorname{rk}(G_i)}. Thus the polynomial exponent is controlled uniformly by the generating rank.

References

  1. [1]Alexander Lubotzky. “Counting Finite Index Subgroups”. In: Groups ’93 Galway/St Andrews, Volume 2. Ed. by Colin M. Campbell et al. Vol. 212. London Mathematical Society Lecture Note Series. Cambridge: Cambridge University Press, 1995, pp. 368–404. DOI: 10.1017/CBO9780511629297.008.DOI
  2. [2]Avinoam Mann. “Positively Finitely Generated Groups”. In: Forum Mathematicum 8.4 (1996), pp. 429–459. DOI: 10.1515/form.1996.8.429.DOI
  3. [3]Avinoam Mann and Aner Shalev. “Simple Groups, Maximal Subgroups and Probabilistic Aspects of Profinite Groups”. In: Israel Journal of Mathematics 96 (1996), pp. 449–468. DOI: 10.1007/BF02937317.DOI
  4. [4]Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
  5. [5]Morris Plotkin. “Binary Codes with Specified Minimum Distance”. In: IRE Transactions on Information Theory 6.4 (1960), pp. 445–450. DOI: 10.1109/TIT.1960.1057584.DOI
  6. [6]Claude E. Shannon. “A Mathematical Theory of Communication”. In: Bell System Technical Journal 27 (1948), pp. 379–423, 623–656. DOI: 10.1002/j.1538-7305.1948.tb01338.x.DOI
  7. [8]R. R. Varshamov. “Estimate of the Number of Signals in Error Correcting Codes”. In: Doklady Akademii Nauk SSSR 117 (1957), pp. 739–741. URL: https://sovietrxiv.org/items/ru-195701.07174.

Paper details

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

views · 1

downloads · 0

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

  • Mathematics

OpenAI’s ChatGPT

View statement
Looking for related papers…
Contents