Higgledy-piggledy subspaces and uniform subspace designs

DOI10.1007/S10623-016-0189-4zbMATH Open1336.05024arXiv1409.6227OpenAlexW1653012935MaRDI QIDQ281328FDOQ281328

Authors: Szabolcs L. Fancsali, Peter Sziklai 

Publication date: 10 May 2016

Published in: Designs, Codes and Cryptography (Search for Journal in Brave)

Abstract: In this article, we investigate collections of `well-spread-out' projective (and linear) subspaces. Projective $k$-subspaces in $mathsfPG(d,mathbbF)$ 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 set $mathcalH$ of higgledy-piggledy $k$-subspaces has to contain more than $min|mathbbF|,su{m}_{i=0}^{k}lfloorfracd-k+ii+1floor$ elements. We also prove that $mathcalH$ has to contain more than $(k+1)cdot(d-k)$ elements if the field $mathbbF$ is algebraically closed. An $r$-uniform weak $(s,A)$ subspace design is a set of linear subspaces $H_1,\mathrm{..},H_{N}lemathbb{F}^m$ each of rank $r$ such that each linear subspace $Wlemathbb{F}^m$ of rank $s$ meets at most $A$ among them. This subspace design is an $r$-uniform strong $(s,A)$ subspace design if $su{m}_{i=1}^{N}mathrmrank(H_{i}capW)leA$ for $forallWlemathbb{F}^m$ of rank $s$. We prove that if $m=r+s$ then the dual ($$) 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 $Agemin|mathbbF|,su{m}_{i=0}^{r-1}lfloorfracs+ii+1floor$ for $r$-uniform weak or strong $(s,A)$ subspace designs in $mathbb{F}^{r+s}$. We show that the $r$-uniform strong $$ subspace design constructed by Guruswami and Kopprty (based on multiplicity codes) has parameter $A=rcdots$ 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$ over algebraically closed field is tight.

Full work available at URL: https://arxiv.org/abs/1409.6227

Recommendations

• Lines in higgledy-piggledy arrangement
• Higgledy-piggledy sets in projective spaces of small dimension
• Explicit subspace designs
• Subspace designs based on algebraic function fields
• Subspace designs based on algebraic function fields

zbMATH Keywords

projective spacegeneral positionsubspace design

Mathematics Subject Classification ID

Combinatorial aspects of finite geometries (05B25) Combinatorial structures in finite projective spaces (51E20) Combinatorial geometries and geometric closure systems (51D20)

Cites Work

• Symmetric functions, Schubert polynomials and degeneracy loci. Transl. from the French by John R. Swallow
• Vandermonde matrices, NP-completeness and transversal subspaces
• Explicit subspace designs
• Lines in higgledy-piggledy arrangement
• Search problems in vector spaces
• Hitting sets for multilinear read-once algebraic branching programs, in any order
• Dimension Expanders via Rank Condensers
• On identity testing of tensors, low-rank recovery and compressed sensing
• On the construction of a family of transversal subspaces over finite fields

Cited In (4)

• Lines in higgledy-piggledy arrangement
• Constructing saturating sets in projective spaces using subgeometries
• Higgledy-piggledy sets in projective spaces of small dimension
• A higgledy-piggledy set of planes based on the ABB-representation of linear sets

This page was built for publication: Higgledy-piggledy subspaces and uniform subspace designs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q281328)