Two-point homogeneous-space code

Two-point homogeneous-space code[1]

Alternative names: Rank-one symmetric space code.

Description

Encodes \(K\) states (codewords) into a two-point homogeneous space \(G/H\), i.e., a homogeneous space with a \(G\)-invariant metric whose symmetry group acts transitively on pairs of points at any fixed distance. In the compact connected case, these are precisely the rank-one symmetric spaces. Finite examples tag along as the corresponding combinatorial analogues, where pairs of points are indistinguishable up to the symmetry group once their mutual distance is fixed.

More technically, a two-point homogeneous space \(G/H\) is a homogeneous space with a \(G\)-invariant metric such that for any \(x,x',y,y'\in G/H\), there exists \(g\in G\) with \(gx=x'\) and \(gy=y'\) whenever \(d(x,y)=d(x',y')\) [2; Def. 4.7]. For finite spaces, this is the metric-space analogue of distance transitivity on pairs, not ordinary two-transitivity on all ordered pairs [3; Table 2].

Two-point homogeneous spaces for compact connected \(G\) have been classified and include spheres, the real, complex, and quaternionic projective spaces, and the octonionic projective (a.k.a. Cayley) plane [4][5; Ch. 9]. These compact examples have positive sectional curvature [6][7; Fig. 1].

Examples of two-point homogeneous spaces for finite \(G\) include Hamming space, Johnson space, and distance-transitive graphs [8]. Finite spaces have yet to be classified [2][5; Ch. 9][3; Table 2].

Infinite two-point homogeneous spaces with constant curvature include spheres, Euclidean spaces, and hyperbolic spaces. These spaces are three-point homogeneous (a.k.a. satisfy the mobility axiom), meaning that the \(G\) action maps any triangle to any other triangle with the same parameters [9; Sec. 6.6.1.1].

Protection

The zonal spherical functions of two-point homogeneous spaces depend only on the distance between points due to the pairwise distance-homogeneity of the \(G\) action. For the compact connected families, these spherical functions are Jacobi polynomials; in the spherical case, they reduce to Gegenbauer polynomials [3; Table 1]. This yields a general series of bounds on packings in \(G/H\) originating with the Kabatiansky-Levenshtein bound [1][5; Ch. 9]; see Ref. [10] for a review.

Notes

See [2,3,11][5; Ch. 9] for reviews.

Cousins

Error-correcting code (ECC)— ECCs and \(t\)-designs on two-point homogeneous spaces are intimately related via association schemes [12,13].
Analog code— Euclidean space \(\mathbb{R}^n\) is a noncompact two-point homogeneous space and is, in fact, a noncompact three-point homogeneous space [9; Sec. 6.6.1.1]. One can also think of \(\mathbb{R}^n\) as a homogeneous space of the Euclidean group by the orthogonal group, \(E(n)/O(n)\) [14; Ch. XI].
Lattice— The Levenshtein bound [15–17] and Cohn-Elkies LP bound [18] can be derived for sphere packings by thinking of \(\mathbb{R}^n\) as a homogeneous space of the Euclidean group by the orthogonal group, \(E(n)/O(n)\) [14; Ch. XI].
Higman-Sims graph-adjacency code— The Higman-Sims graph is distance-transitive, hence it is a finite two-point homogeneous space [8].
Hoffman-Singleton graph-adjacency code— The Hoffman-Singleton graph is distance-transitive, hence it is a finite two-point homogeneous space [8].
\(t\)-design— Designs exist on compact connected two-point homogeneous spaces [10,12,19]. ECCs and \(t\)-designs on two-point homogeneous spaces are intimately related via association schemes [12,13].

Member of code lists

Primary Hierarchy

Classical Domain

Homogeneous-space Kingdom

Homogeneous-space codeECC

Symmetric-space code

Parents

Symmetric-space code

A special class of symmetric spaces are the two-point homogeneous spaces (a.k.a. rank-one symmetric spaces [9; Table 6.1]), whose metric is \(G\)-invariant and for which any two pairs of points at the same distance can be mapped to each other by some \(g\in G\) [2; Def. 4.7].

Two-point homogeneous-space code

Children

Constant-weight codeCombinatorial design

The set of all weight-\(w\) binary strings of length \(n\) forms the Johnson space \(J(n,w)\), a finite two-point homogeneous space \(G/H\) with \(G = S_n\) and \(H = S_w \times S_{n-w}\) [2,20–23][3; Table 2].

Hyperbolic sphere packing

Hyperbolic space in \(D\) dimensions is a symmetric space \(G/H\) for \(G = SO(D,1)\) the proper Lorentz group and \(H = O(D)\). The hyperbolic plane is the case \(D=2\). In fact, hyperbolic spaces are noncompact three-point homogeneous spaces [9; Sec. 6.6.1.1].

Complex projective space code

Compact two-point homogeneous spaces \(G/H\) reduce to complex projective spaces for \(G = SU(D+1)\) and \(H = U(D)\) [5; Ch. 9][3; Table 1].

Real projective space code

Compact two-point homogeneous spaces \(G/H\) reduce to real projective spaces for \(G = SO(D+1)\) and \(H = O(D)\) [5; Ch. 9][3; Table 1].

Constant-dimension code

The finite-field Grassmannian (a.k.a. \(q\)-Johnson space) can be regarded as a finite two-point homogeneous space \(G/H\) where \(G = GL(n,\mathbb{F}_q)\) [2,24][3; Table 2][5; Ch. 9][25; Sec. 8.6].

Rank-metric codeMRD

Matrices of dimension \(m\times n\) over \(\mathbb{F}_q\) under the rank metric form a finite two-point homogeneous space [11,26,27][3; Table 2].

Sharp configuration

Hamming space can be regarded as a finite two-point homogeneous space \(G/H\) where \(G = S_q \wr S_n\) is its isometry group [2][3; Table 2].

Constant-energy spherical codePolytope Polyhedron Lattice-shell Spherical design

Real spheres are compact connected two-point homogeneous spaces with quotient \(SO(D+1)/SO(D)\) [3; Table 1]. Complex spheres can be treated as real spheres of twice the dimension over \(\mathbb{R}\), with quotient \(SU(D+1)/SU(D)\). In fact, spheres are compact three-point homogeneous spaces [9; Sec. 6.6.1.1].

References

[1]: G. A. Kabatiansky, V. I. Levenshtein, “On Bounds for Packings on a Sphere and in Space”, Probl. Peredachi Inf., 14:1 (1978), 3–25; Problems Inform. Transmission, 14:1 (1978), 1–17
[2]: C. Bachoc, “Semidefinite programming, harmonic analysis and coding theory”, (2010) arXiv:0909.4767
[3]: C. Bachoc, D. C. Gijswijt, A. Schrijver, and F. Vallentin, “Invariant Semidefinite Programs”, International Series in Operations Research & Management Science 219 (2011) arXiv:1007.2905 DOI
[4]: H.-C. Wang, “Two-Point Homogeneous Spaces”, The Annals of Mathematics 55, 177 (1952) DOI
[5]: J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
[6]: N. R. Wallach, “Compact Homogeneous Riemannian Manifolds with Strictly Positive Curvature”, The Annals of Mathematics 96, 277 (1972) DOI
[7]: K. Shankar, “Isometry groups of homogeneous spaces with positive sectional curvature”, Differential Geometry and its Applications 14, 57 (2001) DOI
[8]: A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-Regular Graphs (Springer Berlin Heidelberg, 1989) DOI
[9]: M. Berger, A Panoramic View of Riemannian Geometry (Springer Berlin Heidelberg, 2003) DOI
[10]: V. I. Levenshtein, “Universal bounds for codes and designs,” in Handbook of Coding Theory 1, eds. V. S. Pless and W. C. Huffman. Amsterdam: Elsevier, 1998, pp.499-648.
[11]: D. Stanton, “Orthogonal Polynomials and Chevalley Groups”, Special Functions: Group Theoretical Aspects and Applications 87 (1984) DOI
[12]: P. Delsarte and V. I. Levenshtein, “Association schemes and coding theory”, IEEE Transactions on Information Theory 44, 2477 (1998) DOI
[13]: R. A. Bailey, Association Schemes (Cambridge University Press, 2004) DOI
[14]: Vilenkin, N. I. (1978). Special functions and the theory of group representations (Vol. 22). American Mathematical Soc.
[15]: V. I. Levenshtein, “On choosing polynomials to obtain bounds in packing problems.” Proc. Seventh All-Union Conf. on Coding Theory and Information Transmission, Part II, Moscow, Vilnius. 1978.
[16]: V. I. Levenshtein, “On bounds for packings in n-dimensional Euclidean space”, Dokl. Akad. Nauk SSSR, 245:6 (1979), 1299–1303
[17]: V. I. Levenshtein. Bounds for packings of metric spaces and some of their applications. Problemy Kibernet, 40 (1983), 43-110.
[18]: H. Cohn and N. Elkies, “New upper bounds on sphere packings I”, Annals of Mathematics 157, 689 (2003) arXiv:math/0110009 DOI
[19]: H. Cohn, A. Kumar, and G. Minton, “Optimal simplices and codes in projective spaces”, Geometry & Topology 20, 1289 (2016) arXiv:1308.3188 DOI
[20]: Delsarte, Philippe. “An algebraic approach to the association schemes of coding theory.” Philips Res. Rep. Suppl. 10 (1973): vi+-97.
[21]: P. Delsarte, “Association schemes and t-designs in regular semilattices”, Journal of Combinatorial Theory, Series A 20, 230 (1976) DOI
[22]: Ph. Delsarte, “Hahn Polynomials, Discrete Harmonics, andt-Designs”, SIAM Journal on Applied Mathematics 34, 157 (1978) DOI
[23]: V. I. Levenshtein, “Designs as maximum codes in polynomial metric spaces”, Acta Applicandae Mathematicae 29, 1 (1992) DOI
[24]: V. Lakshmibai and J. Brown, The Grassmannian Variety (Springer New York, 2015) DOI
[25]: T. Ceccherini-Silberstein, F. Scarabotti, and F. Tolli, Harmonic Analysis on Finite Groups (Cambridge University Press, 2008) DOI
[26]: P. Delsarte, “Bilinear forms over a finite field, with applications to coding theory”, Journal of Combinatorial Theory, Series A 25, 226 (1978) DOI
[27]: K.-U. Schmidt, “Symmetric bilinear forms over finite fields of even characteristic”, Journal of Combinatorial Theory, Series A 117, 1011 (2010) DOI

Page edit log

Alexander Barg (2025-10-27) — most recent
Victor V. Albert (2025-10-27)

Cite as:

“Two-point homogeneous-space code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2025. https://errorcorrectionzoo.org/c/2pt_homogeneous

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/homogeneous/symmetric/2pt_homogeneous/2pt_homogeneous.yml.