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 and with \(G\) acting two-transitively [2; Def. 4.7]. Two-transitivity is equivalent to the property that any two points can be mapped, via some \(g\in G\), to any other two points that are the same distance apart [2; Def. 4.7].
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 [3][4; Ch. 9]. All of these spaces except real projective space have positive curvature [5][6; Fig. 1].
Examples of two-point homogeneous spaces for finite \(G\) include Hamming space, Johnson space, and distance-transitive graphs [7]. Finite spaces have yet to be classified [2][4; Ch. 9][8; 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 two-transitivity of the \(G\) action. This yields a general series of bounds on packings in \(G/H\) originating with the Kabatiansky-Levenshtein bound [1][4; Ch. 9]; see Ref. [10] for a review.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].
- Lattice-based code— The Levenshtein bound [14–16] and Cohn-Elkies LP bound [17] 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)\) [18; Ch. XI].
- Higman-Sims graph-adjacency code— The Higman-Sims graph is distance-transitive, hence it is a finite two-point homogeneous space [7].
- Hoffman-Singleton graph-adjacency code— The Hoffman-Singleton graph is distance-transitive, hence it is a finite two-point homogeneous space [7].
- Matrix-based code— Matrices over \(\mathbb{F}_q\) form a finite two-point homogeneous space [8; Table 2].
- \(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
Parents
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 points can be mapped, via some \(g\in G\), to any other two points that are the same distance apart [2; Def. 4.7]. This is equivalent to saying that \(G\) acts two-transitively.
Two-point homogeneous-space code
Children
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-q}\) [2,20–23][8; Table 2].
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].
Compact two-point homogeneous spaces \(G/H\) reduce to complex projective spaces for \(G = SU(D+1)\) and \(H = U(D)\) [4; Ch. 9][8; Table 1].
Compact two-point homogeneous spaces \(G/H\) reduce to real projective spaces for \(G = SO(D+1)\) and \(H = O(D)\) [4; Ch. 9][8; Table 1].
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][8; Table 2][4; Ch. 9][25; Sec. 8.6].
Matrices of dimension \(m\times n\) over \(\mathbb{F}_q\) are in one-to-one correspondence with bilinear forms, which form a finite two-point homogeneous space [11,26,27][8; Table 2].
\(q\)-ary codeConstant-weight Combinatorial design Self-dual additive Linear \(q\)-ary Gray Evaluation Self-dual linear Cyclic QR Projective geometry Quantum-inspired classical block Tanner \(q\)-ary LDPC Divisible AG OA Perfect Nearly perfect Perfect binary GRM MDS GRS Balanced
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][8; Table 2].
Compact two-point homogeneous spaces \(G/H\) reduce to real spheres for \(G = SO(D+1)\) and \(H = SO(D)\) and to complex spheres for \(G = SU(D+1)\) and \(H = SU(D)\) [8; Table 1]. 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]
- H.-C. Wang, “Two-Point Homogeneous Spaces”, The Annals of Mathematics 55, 177 (1952) DOI
- [4]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [5]
- N. R. Wallach, “Compact Homogeneous Riemannian Manifolds with Strictly Positive Curvature”, The Annals of Mathematics 96, 277 (1972) DOI
- [6]
- K. Shankar, “Isometry groups of homogeneous spaces with positive sectional curvature”, Differential Geometry and its Applications 14, 57 (2001) DOI
- [7]
- A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-Regular Graphs (Springer Berlin Heidelberg, 1989) DOI
- [8]
- 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
- [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]
- 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.
- [15]
- V. I. Levenshtein, “On bounds for packings in n-dimensional Euclidean space”, Dokl. Akad. Nauk SSSR, 245:6 (1979), 1299–1303
- [16]
- V. I. Levenshtein. Bounds for packings of metric spaces and some of their applications. Problemy Kibernet, 40 (1983), 43-110.
- [17]
- H. Cohn and N. Elkies, “New upper bounds on sphere packings I”, Annals of Mathematics 157, 689 (2003) arXiv:math/0110009 DOI
- [18]
- Vilenkin, N. I. (1978). Special functions and the theory of group representations (Vol. 22). American Mathematical Soc.
- [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