Nothing Special   »   [go: up one dir, main page]

skip to main content
article

Higgledy-piggledy subspaces and uniform subspace designs

Published: 01 June 2016 Publication History

Abstract

In this article, we investigate collections of `well-spread-out' projective (and linear) subspaces. Projective k-subspaces in $$\mathsf {PG}(d,\mathbb {F})$$PG(d,F) are in `higgledy-piggledy arrangement' if they meet each projective subspace of co-dimension k in a generator set of points. We prove that the higgledy-piggledy set $$\mathcal {H}$$H of k-subspaces has to contain more than$$\min \left\{ |\mathbb {F}|,\sum _{i=0}^k\left\lfloor \frac{d-k+i}{i+1}\right\rfloor \right\} $$min|F|, i=0kd-k+ii+1 elements. We also prove that $$\mathcal {H}$$H has to contain more than$$(k+1)\cdot (d-k)$$(k+1)·(d-k) elements if the field $$\mathbb {F}$$F is algebraically closed. An r-uniform weak (s, A) subspace design is a set of linear subspaces $$H_1,\ldots,H_N\le \mathbb {F}^m$$H1,HN≤Fm each of rank r such that each linear subspace $$W\le \mathbb {F}^m$$W≤Fm of rank s meets at most A among them. This subspace design is an r-uniform strong (s, A) subspace design if $$\sum _{i=1}^N\mathrm {rank}(H_i\cap W)\le A$$ i=1Nrank(Hi W)≤A for $$\forall W\le \mathbb {F}^m$$ W≤Fm of rank s. We prove that if $$m=r+s$$m=r+s then the dual ($$\{H_1^\bot,\dots,H_N^\bot \}$${H1,HN }) of an r-uniform weak (strong) subspace design of parameter (s, A) is an s-uniform weak (strong) subspace design of parameter (r, A). We show the connection between uniform weak subspace designs and higgledy-piggledy subspaces proving that $$A\ge \min \left\{ |\mathbb {F}|,\sum _{i=0}^{r-1}\left\lfloor \frac{s+i}{i+1}\right\rfloor \right\} $$A min|F|, i=0r-1s+ii+1 for r-uniform weak or strong (s, A) subspace designs in $$\mathbb {F}^{r+s}$$Fr+s. We show that the r-uniform strong $$(s,r\cdot s+\left( {\begin{array}{c}r\\ 2\end{array}}\right) )$$(s,r·s+r2) subspace design constructed by Guruswami and Kopparty (based on multiplicity codes) has parameter $$A=r\cdot s$$A=r·s if we consider it as a weak subspace design. We give some similar constructions of weak and strong subspace designs (and higgledy-piggledy subspaces) and prove that the lower bound $$(k+1)\cdot (d-k)+1$$(k+1)·(d-k)+1 over algebraically closed field is tight.

References

[1]
Chistov A., Fournier H., Gurvits L., Koiran P.: Vandermonde matrices, NP-completeness, and transversal subspaces. Found. Comput. Math. 3(4), 421---427 (2003).
[2]
Chistov A., Fournier H., Koiran P., Perifel S.: On the construction of a family of transversal subspaces over finite fields. Linear Algebra Appl. 429(2---3), 589---600 (2008).
[3]
Fancsali Sz.L., Sziklai P.: Lines in higgledy-piggledy arrangement. Electron. J. Comb. 21(Issue 2) (2014), Paper #2.56. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p56/pdf.
[4]
Forbes M.A.: Polynomial identity testing of read-once oblivious algebraic branching programs. Ph.D. Thesis, Massachusetts Institute of Technology (2014). http://www.mit.edu/~miforbes/papers/thesis-hyperref.
[5]
Forbes M.A., Shpilka A.: On identity testing of tensors, low-rank recovery and compressed sensing. STOC'12--Proceedings of the 2012 ACM Symposium on Theory of Computing, pp. 163---171. ACM, New York (2012).
[6]
Forbes M.A., Guruswami V.: Dimension expanders via rank condensers. Electron. Colloq. Comput. Complex. (ECCC) 21, 162 (2014). arXiv:1411.7455v1.
[7]
Forbes M.A., Saptharishi R., Shpilka A.: Hitting sets for multilinear read-once algebraic branching programs, in any order. STOC'14--Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 867---875. ACM, New York (2014).
[8]
Guruswami V., Kopparty S.: Explicit subspace designs. Electron. Colloq. Comput. Complex. (ECCC) 20, 60 (2013) and Combinatorica (2014).
[9]
Héger T., Patkós B., Takáts M.: Search problems in vector spaces. Des. Codes Cryptogr. 76(2), 207---216 (2015).
[10]
Manivel L.: Swallow J.R. (Translator): Symmetric Functions, Schubert Polynomials and Degeneracy Loci. SMF/AMS Texts and Monographs, vol. 6; Cours Spécialisés {Specialized Courses}, vol. 3. American Mathematical Society; Société Mathématique de France, Paris (2001).

Cited By

View all
  • (2022)Short Minimal Codes and Covering Codes via Strong Blocking Sets in Projective SpacesIEEE Transactions on Information Theory10.1109/TIT.2021.312373068:2(881-890)Online publication date: 1-Feb-2022
  • (2022)Constructing saturating sets in projective spaces using subgeometriesDesigns, Codes and Cryptography10.1007/s10623-021-00951-y90:9(2113-2144)Online publication date: 1-Sep-2022

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Designs, Codes and Cryptography
Designs, Codes and Cryptography  Volume 79, Issue 3
June 2016
230 pages

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 June 2016

Author Tags

  1. 05B25
  2. 51D20
  3. 51E20
  4. General position
  5. Projective space
  6. Subspace design

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 28 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2022)Short Minimal Codes and Covering Codes via Strong Blocking Sets in Projective SpacesIEEE Transactions on Information Theory10.1109/TIT.2021.312373068:2(881-890)Online publication date: 1-Feb-2022
  • (2022)Constructing saturating sets in projective spaces using subgeometriesDesigns, Codes and Cryptography10.1007/s10623-021-00951-y90:9(2113-2144)Online publication date: 1-Sep-2022

View Options

View options

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media