Alternative names: \(q\)-design, Geometric design, Design over finite fields, Design over \(\mathbb{F}_q\), Design in the \(q\)-Johnson scheme, Design in vector spaces.
Description
A constant-dimension code that forms a design on the finite Grassmannian. Subspace designs exist for all parameters in sufficiently large dimension that also satisfies divisibility constraints [4,5].
An alternative but related definition is given in Refs. [6,7].
Notes
See [8] for a review and history of subspace designs.Popular summary of the existence of subspace designs in Quanta Magazine.Cousin
- Combinatorial design— Combinatorial designs are designs in Johnson space, the space of all size-\(w\) subsets of a set with \(n\) elements. The \(q\)-Johnson spaces generalize this notion to subspaces and reduce to Johnson spaces at \(q=1\). In other words, combinatorial designs are designs over spaces of subsets, while subspace designs are designs over spaces of subspaces.
Member of code lists
Primary Hierarchy
Parents
Subspace designs are designs on the finite-field Grassmannian (a.k.a. \(q\)-Johnson space or \(q\)-Johnson association scheme) [9][10; Sec. 8.6].
Subspace design
References
- [1]
- C. Berge and D. Ray-Chaudhuri, “Unsolved problems”, Lecture Notes in Mathematics 278 (1974) DOI
- [2]
- Cameron, Peter J. “Generalisation of Fisher’s inequality to fields with more than one element.” Combinatorics, London Math. Soc. Lecture Note Ser 13 (1973): 9-13.
- [3]
- P. Delsarte, “Association schemes and t-designs in regular semilattices”, Journal of Combinatorial Theory, Series A 20, 230 (1976) DOI
- [4]
- A. Fazeli, S. Lovett, and A. Vardy, “Nontrivial t-designs over finite fields exist for all t”, Journal of Combinatorial Theory, Series A 127, 149 (2014) DOI
- [5]
- P. Keevash, A. Sah, and M. Sawhney, “The existence of subspace designs”, (2023) arXiv:2212.00870
- [6]
- V. Guruswami and S. Kopparty, “Explicit Subspace Designs”, 2013 IEEE 54th Annual Symposium on Foundations of Computer Science 608 (2013) DOI
- [7]
- V. Guruswami and C. Xing, “List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound”, Proceedings of the forty-fifth annual ACM symposium on Theory of Computing 843 (2013) DOI
- [8]
- M. Braun, M. Kiermaier, and A. Wassermann, “q-Analogs of Designs: Subspace Designs”, Signals and Communication Technology 171 (2018) DOI
- [9]
- Ph. Delsarte, “Hahn Polynomials, Discrete Harmonics, andt-Designs”, SIAM Journal on Applied Mathematics 34, 157 (1978) DOI
- [10]
- T. Ceccherini-Silberstein, F. Scarabotti, and F. Tolli, Harmonic Analysis on Finite Groups (Cambridge University Press, 2008) DOI
Page edit log
- Victor V. Albert (2024-01-09) — most recent
Cite as:
“Subspace design”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/subspace_design