nach oben

Designs, Codes and Cryptography

25.10.2016

Improved upper bounds for partial spreads

verfasst von: Sascha Kurz

Erschienen in: Designs, Codes and Cryptography | Ausgabe 1/2017

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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\).

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

Titel: Improved upper bounds for partial spreads
verfasst von: Sascha Kurz
Publikationsdatum: 25.10.2016
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 1/2017
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-016-0290-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.