Top

Designs, Codes and Cryptography

Published in:

25-10-2016

Improved upper bounds for partial spreads

Author: Sascha Kurz

Published in: Designs, Codes and Cryptography | Issue 1/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

A partial \((k-1)\)-spread in \({\text {PG}}(n-1,q)\) is a collection of \((k-1)\)-dimensional subspaces with trivial intersection. So far, the maximum size of a partial \((k-1)\)-spread in \({\text {PG}}(n-1,q)\) was known for the cases \(n\equiv 0\pmod k\), \(n\equiv 1\pmod k\), and \(n\equiv 2\pmod k\) with the additional requirements \(q=2\) and \(k=3\). We completely resolve the case \(n\equiv 2\pmod k\) for the binary case \(q=2\).

previous article Lattices from codes over : generalization of constructions D, and

next article Collineations of finite 2-affine planes

Instead of \({\text {PG}}(n-1,q)\) we will mainly use the notation \(\mathbb {F}_{q}^{n}\) in the following.

In the projective space the dimensions are commonly one less compared to the consideration of subspaces in \(\mathbb {F}_{q}^{n}\).

Obviously, we have \(A_q(n,2;1)=\genfrac[]{0.0pt}{}{n}{1}_{q}\).

As \(A_q(k+2,2k;k)=1\) for \(k\ge 2\), the assumption \(n\ge 2k+2\) is no restriction. The case \(k=3\) is covered by [6], see Theorem 4. For \(k=1,2\) the remainder of n is strictly smaller than 2. So, in other words, the binary case \(n\equiv 2\pmod k\) is completely resolved.

We have to exclude the trivial subspace partition \({\mathcal {P}}=\left\{ \mathbb {F}_{q}^{n}\right\} \), where \(d_1=n\) and \(d_2\) does not exist.

Theorem 10(ii,iv) yields \(n_1= 2^{k-1}-1\) or \(n_1>2^{k-1}\), if we set \(d_2=k-1\) and \(d_1=1\). The improvement of Theorem 10, i.e., see [12, Theorem 2], is not sufficient to exclude the case of Lemma 1.

The result is also valid for \(k=2r-1\), \(r\ge 2\), and \(q\in \{2,3\}\).

By a more refined analysis, one can classify the possible hole configurations up to isomorphism.

For even \(q>2\) the tail condition of Theorem 10 cannot be applied directly in the proof of Lemma 3.

The specific use of Theorem 10 is just a shortcut, resting on the same rough idea. However, it points to an area where even more theoretic results are available, that possibly can be used in more involved cases.

In this context, we would like to mention the very recent preprint [15].

Using the notation from this paper, we have \({\overline{s}}=q^k\), \({\overline{r}}=A_q(n,2k;k)\), and \(\mu =q^{n-2k}\).

André J.: Über nicht-desarguessche Ebenen mit transitiver Translationsgruppe. Math. Z. 60(1), 156–186 (1954).MathSciNetCrossRefMATH

Beutelspacher A.: Partial spreads in finite projective spaces and partial designs. Math. Z. 145(3), 211–229 (1975).MathSciNetCrossRefMATH

Dembowski P.: Finite Geometries: Reprint of the 1968 Edition. Springer, Berlin (2012).

Drake D.A., Freeman J.W.: Partial \(t\)-spreads and group constructible \((s, r,\mu )\)-nets. J. Geom. 13(2), 210–216 (1979).MathSciNetCrossRefMATH

Eisfeld J., Storme L.: \(t\)-Spreads and Minimal \(t\)-Covers in Finite Projective Spaces. Lecture NotesUniversiteit Gent, Gent (2000).

El-Zanati S., Jordon H., Seelinger G., Sissokho P., Spence L.: The maximum size of a partial 3-spread in a finite vector space over \({G}{F}(2)\). Des. Codes Cryptogr. 54(2), 101–107 (2010).MathSciNetCrossRefMATH

Etzion T.: Problems on \(q\)-Analogs in Coding Theory. arXiv preprint: arXiv:1305.6126 (2013).

Etzion T., Silberstein N.: Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams. IEEE Trans. Inf. Theory 55(7), 2909–2919 (2009).MathSciNetCrossRef

Etzion T., Storme L.: Galois geometries and coding theory. Des. Codes Cryptogr. 78(1), 311–350 (2016).MathSciNetCrossRefMATH

10.

Gabidulin E.M.: Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21(1), 3–16 (1985).MathSciNetMATH

11.

Heden O.: On the length of the tail of a vector space partition. Discret. Math. 309(21), 6169–6180 (2009).MathSciNetCrossRefMATH

12.

Heden O., Lehmann J., Năstase E., Sissokho P.: The supertail of a subspace partition. Des. Codes Cryptogr. 69(3), 305–316 (2013).MathSciNetCrossRefMATH

13.

Heinlein D., Kiermaier M., Kurz S., Wassermann A.: Tables of Subspace Codes. University of Bayreuth (2015). Available at http://subspacecodes.uni-bayreuth.de.

14.

Hong S.J., Patel A.M.: A general class of maximal codes for computer applications. IEEE Trans. Comput. 100(12), 1322–1331 (1972).MathSciNetCrossRefMATH

15.

Năstase E., Sissokho P.: The Maximum Size of a Partial Spread in a Finite Projective Space. arXiv preprint: arXiv:1605.04824 (2016).

16.

Silva D., Kschischang F.R., Koetter R.: A rank-metric approach to error control in random network coding. IEEE Trans. Inf. Theory 54(9), 3951–3967 (2008).MathSciNetCrossRefMATH

17.

Skachek V.: Recursive code construction for random networks. IEEE Trans. Inf. Theory 56(3), 1378–1382 (2010).MathSciNetCrossRefMATH

Title: Improved upper bounds for partial spreads
Author: Sascha Kurz
Publication date: 25-10-2016
Publisher: Springer US
Published in: Designs, Codes and Cryptography / Issue 1/2017
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-016-0290-8

Springer Professional

Improved upper bounds for partial spreads

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 1/2017

Perfect contrast XOR-based visual cryptography schemes via linear algebra

A combinatorial problem related to sparse systems of equations

Complete mappings and Carlitz rank

Efficient revocable identity-based encryption via subset difference methods

On the construction of quantum constacyclic codes

Strong authenticated key exchange with auxiliary inputs

Premium Partner