Higgledy-piggledy subspaces and uniform subspace designs

详细信息    查看全文

• 作者：Szabolcs L. Fancsali ; Péter Sziklai
• 刊名：Designs, Codes and Cryptography
• 出版年：2016
• 出版时间：June 2016
• 年：2016
• 卷：79
• 期：3
• 页码：625-645
• 全文大小：537 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Coding and Information Theory
  Data Structures, Cryptology and Information Theory
  Data Encryption
  Discrete Mathematics in Computer Science
  Information, Communication and Circuits
  
• 出版者：Springer Netherlands
• ISSN：1573-7586
• 卷排序：79

文摘

In this article, we investigate collections of ‘well-spread-out’ projective (and linear) subspaces. Projective k-subspaces in \(\mathsf {PG}(d,\mathbb {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}\) 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\} \) elements. We also prove that \(\mathcal {H}\) has to contain more than\((k+1)\cdot (d-k)\) elements if the field \(\mathbb {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\) each of rank r such that each linear subspace \(W\le \mathbb {F}^m\) 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\) for \(\forall W\le \mathbb {F}^m\) of rank s. We prove that if \(m=r+s\) then the dual (\(\{H_1^\bot ,\dots ,H_N^\bot \}\)) 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\} \) for r-uniform weak or strong (s, A) subspace designs in \(\mathbb {F}^{r+s}\). We show that the r-uniform strong \((s,r\cdot s+\left( {\begin{array}{c}r\\ 2\end{array}}\right) )\) subspace design constructed by Guruswami and Kopparty (based on multiplicity codes) has parameter \(A=r\cdot 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\) over algebraically closed field is tight.KeywordsProjective spaceSubspace designGeneral position