Higgledy-piggledy subspaces and uniform subspace designs

DOI10.1007/S10623-016-0189-4MaRDI QIDQ281328zbMATH OpenOpenAlexFDO

Authors Szabolcs L. Fancsali, Peter Sziklai

Publication date 10 May 2016

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

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

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)

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.

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

Cites work

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

Cited in

(4)

• Higgledy-piggledy sets in projective spaces of small dimension
• Lines in higgledy-piggledy arrangement
• Constructing saturating sets in projective spaces using subgeometries
• 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)