Two-point homogeneous-space code

Two-point homogeneous-space code[1]

Description

Encodes \(K\) states (codewords) into a two-point homogeneous space \(G/H\), i.e., a homogeneous space on which \(G\) acts two-transitively.

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 plane [2][3; Ch. 9]. Examples of two-point homogeneous spaces for finite \(G\) include Hamming space, Johnson space, and distance-transitive graphs [4]; such spaces have yet to be classified [5][3; Ch. 9][6; Table 2].

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][3; Ch. 9]; see Ref. [7] for a review.

Notes

See [5,6,8][3; Ch. 9] for reviews.

Cousins

Error-correcting code (ECC)— ECCs and \(t\)-designs on two-point homogeneous spaces are intimately related via association schemes [9].
Higman-Sims graph-adjacency code— The Higman-Sims graph is distance-transitive, hence it is a finite two-point homogeneous space [4].
Hoffman-Singleton graph-adjacency code— The Hoffman-Singleton graph is distance-transitive, hence it is a finite two-point homogeneous space [4].
Matrix-based code— Matrices over \(GF(q)\) form a finite two-point homogeneous space [6; Table 2].
\(t\)-design— Designs exist on compact connected two-point homogeneous spaces [7,9,10]. ECCs and \(t\)-designs on two-point homogeneous spaces are intimately related via association schemes [9].

Member of code lists

Classical codes

Primary Hierarchy

Classical Domain

Homogeneous-space Kingdom

Homogeneous-space codeECC

Parents

Homogeneous-space code

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-q}\) [5,11–14][6; Table 2].

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,GF(q))\) [5,15][6; Table 2][3; Ch. 9][16; Sec. 8.6].

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 [5][6; Table 2].

Constant-energy spherical codePolytope Polyhedron Lattice-shell Spherical design

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)\) [6; Table 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]: H.-C. Wang, “Two-Point Homogeneous Spaces”, The Annals of Mathematics 55, 177 (1952) DOI
[3]: J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
[4]: A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-Regular Graphs (Springer Berlin Heidelberg, 1989) DOI
[5]: C. Bachoc, “Semidefinite programming, harmonic analysis and coding theory”, (2010) arXiv:0909.4767
[6]: 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
[7]: 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.
[8]: D. Stanton, “Orthogonal Polynomials and Chevalley Groups”, Special Functions: Group Theoretical Aspects and Applications 87 (1984) DOI
[9]: P. Delsarte and V. I. Levenshtein, “Association schemes and coding theory”, IEEE Transactions on Information Theory 44, 2477 (1998) DOI
[10]: H. Cohn, A. Kumar, and G. Minton, “Optimal simplices and codes in projective spaces”, Geometry & Topology 20, 1289 (2016) arXiv:1308.3188 DOI
[11]: Delsarte, Philippe. “An algebraic approach to the association schemes of coding theory.” Philips Res. Rep. Suppl. 10 (1973): vi+-97.
[12]: P. Delsarte, “Association schemes and t-designs in regular semilattices”, Journal of Combinatorial Theory, Series A 20, 230 (1976) DOI
[13]: Ph. Delsarte, “Hahn Polynomials, Discrete Harmonics, andt-Designs”, SIAM Journal on Applied Mathematics 34, 157 (1978) DOI
[14]: V. I. Levenshtein, “Designs as maximum codes in polynomial metric spaces”, Acta Applicandae Mathematicae 29, 1 (1992) DOI
[15]: V. Lakshmibai and J. Brown, The Grassmannian Variety (Springer New York, 2015) DOI
[16]: T. Ceccherini-Silberstein, F. Scarabotti, and F. Tolli, Harmonic Analysis on Finite Groups (Cambridge University Press, 2008) 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/2pt_homogeneous.yml.