August  2019, 13(3): 457-475. doi: 10.3934/amc.2019029

A subspace code of size $ \bf{333} $ in the setting of a binary $ \bf{q} $-analog of the Fano plane

1. 

Department of Communications and Networking, Aalto University, FI-00076 Aalto, Finland

2. 

Mathematisches Institut, Universität Bayreuth, D-95440 Bayreuth, Germany

Received  July 2018 Published  April 2019

Fund Project: The work was supported by the ICT COST Action IC1104 and grants KU 2430/3-1, WA 1666/9-1 – "Integer Linear Programming Models for Subspace Codes and Finite Geometry" – from the German Research Foundation

We show that there is a binary subspace code of constant dimension 3 in ambient dimension 7, having minimum subspace distance 4 and cardinality 333, i.e., $ 333 \le A_2(7, 4;3) $, which improves the previous best known lower bound of 329. Moreover, if a code with these parameters has at least 333 elements, its automorphism group is in one of 31 conjugacy classes.

This is achieved by a more general technique for an exhaustive search in a finite group that does not depend on the enumeration of all subgroups.

Citation: Daniel Heinlein, Michael Kiermaier, Sascha Kurz, Alfred Wassermann. A subspace code of size $ \bf{333} $ in the setting of a binary $ \bf{q} $-analog of the Fano plane. Advances in Mathematics of Communications, 2019, 13 (3) : 457-475. doi: 10.3934/amc.2019029
References:
[1]

J. Ai, T. Honold and H. Liu, The expurgation-augmentation method for constructing good plane subspace codes, arXiv preprint, arXiv: 1601.01502.Google Scholar

[2]

E. Artin, Geometric Algebra, Interscience Publishers, Inc., New York-London, 1957. Google Scholar

[3]

R. Baer, Linear Algebra and Projective Geometry, Academic Press Inc., New York, N. Y., 1952. Google Scholar

[4]

H. U. Besche, B. Eick and E. O'Brien, Small Groups library, URL http://www.icm.tu-bs.de/ag_algebra/software/small/, Visited on Dec. 12, 2016.Google Scholar

[5]

A. Beutelspacher, Partial spreads in finite projective spaces and partial designs, Mathematische Zeitschrift, 145 (1975), 211-229. doi: 10.1007/BF01215286. Google Scholar

[6]

M. Braun, T. Etzion, P. R. J. Östergård, A. Vardy and A. Wassermann, Existence of q-analogs of Steiner systems, Forum Math. Pi, 4 (2016), e7, 14pp. doi: 10.1017/fmp.2016.5. Google Scholar

[7]

M. Braun, A. Kerber and R. Laue, Systematic construction of q-analogs of t-(v, l, λ-designs, Designs, Codes and Cryptography, 34 (2005), 55–70, URL https://doi.org/10.1007/s10623-003-4194-z. doi: 10.1007/s10623-003-4194-z. Google Scholar

[8]

M. BraunM. Kiermaier and A. Nakić, On the automorphism group of a binary q-analog of the Fano plane, European Journal of Combinatorics, 51 (2016), 443-457. doi: 10.1016/j.ejc.2015.07.014. Google Scholar

[9]

M. BraunP. R. J. Östergård and A. Wassermann, New lower bounds for binary constant dimension subspace codes, Experimental Mathematics, 27 (2018), 179-183. doi: 10.1080/10586458.2016.1239145. Google Scholar

[10]

M. Braun and J. Reichelt, q-analogs of packing designs, Journal of Combinatorial Designs, 22 (2014), 306-321. doi: 10.1002/jcd.21376. Google Scholar

[11]

M. Buratti, M. Kiermaier, S. Kurz, A. Nakić and A. Wassermann, q-analogs of group divisible designs, arXiv preprint, arXiv: 1804.11172.Google Scholar

[12]

A. Cossidente and F. Pavese, On subspace codes, Designs, Codes and Cryptography, 78 (2016), 527-531. doi: 10.1007/s10623-014-0018-6. Google Scholar

[13]

A. Cossidente, F. Pavese and L. Storme, Geometrical aspects of subspace codes, in Network Coding and Subspace Designs, Springer, 2018,107–129. Google Scholar

[14]

T. Etzion, A new approach to examine q-Steiner systems, arXiv preprint, arXiv: 1507.08503.Google Scholar

[15]

T. Etzion, On the structure of the q-Fano plane, arXiv preprint, arXiv: 1508.01839.Google Scholar

[16]

T. Etzion and L. Storme, Galois geometries and coding theory, Designs, Codes and Cryptography, 78 (2016), 311–350, URL http://dx.doi.org/10.1007/s10623-015-0156-5. doi: 10.1007/s10623-015-0156-5. Google Scholar

[17]

T. Etzion and N. Silberstein, Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams, IEEE Transactions on Information Theory, 55 (2009), 2909-2919. doi: 10.1109/TIT.2009.2021376. Google Scholar

[18]

T. Etzion and A. Vardy, On q-analogs of Steiner systems and covering designs, Advances in Mathematics of Communications, 5 (2011), 161-176. doi: 10.3934/amc.2011.5.161. Google Scholar

[19]

M. Greferath, M. O. Pavčević, N. Silberstein and M. Á. Vázquez-Castro, Network Coding and Subspace Designs, Springer, 2018. doi: 10.1007/978-3-319-70293-3. Google Scholar

[20]

M. Hall Jr, The Theory of Groups, Macmillan New York, 1959. Google Scholar

[21]

O. Heden and P. A. Sissokho, On the existence of a (2, 3)-spread in V(7, 2), Ars Combinatoria, 124 (2016), 161-164. Google Scholar

[22]

D. HeinleinT. HonoldM. Kiermaier and S. Kurz, Generalized vector space partitions, The Australasian Journal of Combinatorics, 73 (2019), 162-178. Google Scholar

[23]

D. Heinlein, M. Kiermaier, S. Kurz and A. Wassermann, Tables of subspace codes, arXiv preprint, arXiv: 1601.02864.Google Scholar

[24]

D. Heinlein and S. Kurz, Asymptotic bounds for the sizes of constant dimension codes and an improved lower bound, in International Castle Meeting on Coding Theory and Applications, Springer, 10495 (2017), 163–191. Google Scholar

[25]

T. HonoldM. Kiermaier and S. Kurz, Optimal binary subspace codes of length 6, constant dimension 3 and minimum distance 4, Contemporary Mathematics, 632 (2015), 157-176. doi: 10.1090/conm/632/12627. Google Scholar

[26]

T. Honold and M. Kiermaier, On putative q-analogues of the Fano plane and related combinatorial structures, in Dynamical Systems, Number Theory and Applications, World Sci. Publ., Hackensack, NJ, 2016,141–175. Google Scholar

[27]

M. KiermaierS. Kurz and A. Wassermann, The order of the automorphism group of a binary q-analog of the Fano plane is at most two, Designs, Codes and Cryptography, 86 (2018), 239-250. doi: 10.1007/s10623-017-0360-6. Google Scholar

[28]

M. Kiermaier and M. O. Pavčević, Intersection numbers for subspace designs, Journal of Combinatorial Designs, 23 (2015), 463-480. doi: 10.1002/jcd.21403. Google Scholar

[29]

R. Koetter and F. Kschischang, Coding for errors and erasures in random network coding, IEEE Transactions on Information Theory, 54 (2008), 3579-3591. doi: 10.1109/TIT.2008.926449. Google Scholar

[30]

A. Kohnert and S. Kurz, Construction of large constant dimension codes with a prescribed minimum distance, in Mathematical Methods in Computer Science, vol. 5393 of Lecture Notes in Computer Science, Springer, Berlin, 2008, 31–42. doi: 10.1007/978-3-540-89994-5_4. Google Scholar

[31]

S. Kurz, Improved upper bounds for partial spreads, Designs, Codes and Cryptography, 85 (2017), 97-106. doi: 10.1007/s10623-016-0290-8. Google Scholar

[32]

S. Kurz, Packing vector spaces into vector spaces, The Australasian Journal of Combinatorics, 68 (2017), 122-130. Google Scholar

[33]

H. Liu and T. Honold, Poster: A new approach to the main problem of subspace coding, in 9th International Conference on Communications and Networking in China (ChinaCom 2014, Maoming, China, Aug. 14–16), 2014, 676–677, Full paper available as arXiv: 1408.1181.Google Scholar

[34]

K. Metsch, Bose-Burton type theorems for finite projective, affine and polar spaces, in Surveys in Combinatorics, 1999 (Canterbury), vol. 267 of London Math. Soc. Lecture Note Ser., Cambridge Univ. Press, Cambridge, 1999, 137-166. Google Scholar

[35]

M. MiyakawaA. Munemasa and S. Yoshiara, On a class of small 2-designs over GF(q), Journal of Combinatorial Designs, 3 (1995), 61-77. doi: 10.1002/jcd.3180030108. Google Scholar

[36]

D. SilvaF. Kschischang and R. Koetter, A rank-metric approach to error control in random network coding, IEEE Transactions on Information Theory, 54 (2008), 3951-3967. doi: 10.1109/TIT.2008.928291. Google Scholar

[37]

A. Storjohann, An $ {O}(n^3) $ algorithm for the {F}robenius normal form, in Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation, ACM, 1998,101–104. doi: 10.1145/281508.281570. Google Scholar

[38]

S. Thomas, Designs over finite fields, Geometriae Dedicata, 24 (1987), 237-242. doi: 10.1007/BF00150939. Google Scholar

[39]

S. Thomas, Designs and partial geometries over finite fields, Geometriae Dedicata, 63 (1996), 247-253. doi: 10.1007/BF00181415. Google Scholar

[40]

J. Zumbrägel, Designs and codes in affine geometry, arXiv preprint, arXiv: 1605.03789.Google Scholar

show all references

References:
[1]

J. Ai, T. Honold and H. Liu, The expurgation-augmentation method for constructing good plane subspace codes, arXiv preprint, arXiv: 1601.01502.Google Scholar

[2]

E. Artin, Geometric Algebra, Interscience Publishers, Inc., New York-London, 1957. Google Scholar

[3]

R. Baer, Linear Algebra and Projective Geometry, Academic Press Inc., New York, N. Y., 1952. Google Scholar

[4]

H. U. Besche, B. Eick and E. O'Brien, Small Groups library, URL http://www.icm.tu-bs.de/ag_algebra/software/small/, Visited on Dec. 12, 2016.Google Scholar

[5]

A. Beutelspacher, Partial spreads in finite projective spaces and partial designs, Mathematische Zeitschrift, 145 (1975), 211-229. doi: 10.1007/BF01215286. Google Scholar

[6]

M. Braun, T. Etzion, P. R. J. Östergård, A. Vardy and A. Wassermann, Existence of q-analogs of Steiner systems, Forum Math. Pi, 4 (2016), e7, 14pp. doi: 10.1017/fmp.2016.5. Google Scholar

[7]

M. Braun, A. Kerber and R. Laue, Systematic construction of q-analogs of t-(v, l, λ-designs, Designs, Codes and Cryptography, 34 (2005), 55–70, URL https://doi.org/10.1007/s10623-003-4194-z. doi: 10.1007/s10623-003-4194-z. Google Scholar

[8]

M. BraunM. Kiermaier and A. Nakić, On the automorphism group of a binary q-analog of the Fano plane, European Journal of Combinatorics, 51 (2016), 443-457. doi: 10.1016/j.ejc.2015.07.014. Google Scholar

[9]

M. BraunP. R. J. Östergård and A. Wassermann, New lower bounds for binary constant dimension subspace codes, Experimental Mathematics, 27 (2018), 179-183. doi: 10.1080/10586458.2016.1239145. Google Scholar

[10]

M. Braun and J. Reichelt, q-analogs of packing designs, Journal of Combinatorial Designs, 22 (2014), 306-321. doi: 10.1002/jcd.21376. Google Scholar

[11]

M. Buratti, M. Kiermaier, S. Kurz, A. Nakić and A. Wassermann, q-analogs of group divisible designs, arXiv preprint, arXiv: 1804.11172.Google Scholar

[12]

A. Cossidente and F. Pavese, On subspace codes, Designs, Codes and Cryptography, 78 (2016), 527-531. doi: 10.1007/s10623-014-0018-6. Google Scholar

[13]

A. Cossidente, F. Pavese and L. Storme, Geometrical aspects of subspace codes, in Network Coding and Subspace Designs, Springer, 2018,107–129. Google Scholar

[14]

T. Etzion, A new approach to examine q-Steiner systems, arXiv preprint, arXiv: 1507.08503.Google Scholar

[15]

T. Etzion, On the structure of the q-Fano plane, arXiv preprint, arXiv: 1508.01839.Google Scholar

[16]

T. Etzion and L. Storme, Galois geometries and coding theory, Designs, Codes and Cryptography, 78 (2016), 311–350, URL http://dx.doi.org/10.1007/s10623-015-0156-5. doi: 10.1007/s10623-015-0156-5. Google Scholar

[17]

T. Etzion and N. Silberstein, Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams, IEEE Transactions on Information Theory, 55 (2009), 2909-2919. doi: 10.1109/TIT.2009.2021376. Google Scholar

[18]

T. Etzion and A. Vardy, On q-analogs of Steiner systems and covering designs, Advances in Mathematics of Communications, 5 (2011), 161-176. doi: 10.3934/amc.2011.5.161. Google Scholar

[19]

M. Greferath, M. O. Pavčević, N. Silberstein and M. Á. Vázquez-Castro, Network Coding and Subspace Designs, Springer, 2018. doi: 10.1007/978-3-319-70293-3. Google Scholar

[20]

M. Hall Jr, The Theory of Groups, Macmillan New York, 1959. Google Scholar

[21]

O. Heden and P. A. Sissokho, On the existence of a (2, 3)-spread in V(7, 2), Ars Combinatoria, 124 (2016), 161-164. Google Scholar

[22]

D. HeinleinT. HonoldM. Kiermaier and S. Kurz, Generalized vector space partitions, The Australasian Journal of Combinatorics, 73 (2019), 162-178. Google Scholar

[23]

D. Heinlein, M. Kiermaier, S. Kurz and A. Wassermann, Tables of subspace codes, arXiv preprint, arXiv: 1601.02864.Google Scholar

[24]

D. Heinlein and S. Kurz, Asymptotic bounds for the sizes of constant dimension codes and an improved lower bound, in International Castle Meeting on Coding Theory and Applications, Springer, 10495 (2017), 163–191. Google Scholar

[25]

T. HonoldM. Kiermaier and S. Kurz, Optimal binary subspace codes of length 6, constant dimension 3 and minimum distance 4, Contemporary Mathematics, 632 (2015), 157-176. doi: 10.1090/conm/632/12627. Google Scholar

[26]

T. Honold and M. Kiermaier, On putative q-analogues of the Fano plane and related combinatorial structures, in Dynamical Systems, Number Theory and Applications, World Sci. Publ., Hackensack, NJ, 2016,141–175. Google Scholar

[27]

M. KiermaierS. Kurz and A. Wassermann, The order of the automorphism group of a binary q-analog of the Fano plane is at most two, Designs, Codes and Cryptography, 86 (2018), 239-250. doi: 10.1007/s10623-017-0360-6. Google Scholar

[28]

M. Kiermaier and M. O. Pavčević, Intersection numbers for subspace designs, Journal of Combinatorial Designs, 23 (2015), 463-480. doi: 10.1002/jcd.21403. Google Scholar

[29]

R. Koetter and F. Kschischang, Coding for errors and erasures in random network coding, IEEE Transactions on Information Theory, 54 (2008), 3579-3591. doi: 10.1109/TIT.2008.926449. Google Scholar

[30]

A. Kohnert and S. Kurz, Construction of large constant dimension codes with a prescribed minimum distance, in Mathematical Methods in Computer Science, vol. 5393 of Lecture Notes in Computer Science, Springer, Berlin, 2008, 31–42. doi: 10.1007/978-3-540-89994-5_4. Google Scholar

[31]

S. Kurz, Improved upper bounds for partial spreads, Designs, Codes and Cryptography, 85 (2017), 97-106. doi: 10.1007/s10623-016-0290-8. Google Scholar

[32]

S. Kurz, Packing vector spaces into vector spaces, The Australasian Journal of Combinatorics, 68 (2017), 122-130. Google Scholar

[33]

H. Liu and T. Honold, Poster: A new approach to the main problem of subspace coding, in 9th International Conference on Communications and Networking in China (ChinaCom 2014, Maoming, China, Aug. 14–16), 2014, 676–677, Full paper available as arXiv: 1408.1181.Google Scholar

[34]

K. Metsch, Bose-Burton type theorems for finite projective, affine and polar spaces, in Surveys in Combinatorics, 1999 (Canterbury), vol. 267 of London Math. Soc. Lecture Note Ser., Cambridge Univ. Press, Cambridge, 1999, 137-166. Google Scholar

[35]

M. MiyakawaA. Munemasa and S. Yoshiara, On a class of small 2-designs over GF(q), Journal of Combinatorial Designs, 3 (1995), 61-77. doi: 10.1002/jcd.3180030108. Google Scholar

[36]

D. SilvaF. Kschischang and R. Koetter, A rank-metric approach to error control in random network coding, IEEE Transactions on Information Theory, 54 (2008), 3951-3967. doi: 10.1109/TIT.2008.928291. Google Scholar

[37]

A. Storjohann, An $ {O}(n^3) $ algorithm for the {F}robenius normal form, in Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation, ACM, 1998,101–104. doi: 10.1145/281508.281570. Google Scholar

[38]

S. Thomas, Designs over finite fields, Geometriae Dedicata, 24 (1987), 237-242. doi: 10.1007/BF00150939. Google Scholar

[39]

S. Thomas, Designs and partial geometries over finite fields, Geometriae Dedicata, 63 (1996), 247-253. doi: 10.1007/BF00181415. Google Scholar

[40]

J. Zumbrägel, Designs and codes in affine geometry, arXiv preprint, arXiv: 1605.03789.Google Scholar

[1]

Thomas Honold, Michael Kiermaier, Sascha Kurz. Constructions and bounds for mixed-dimension subspace codes. Advances in Mathematics of Communications, 2016, 10 (3) : 649-682. doi: 10.3934/amc.2016033

[2]

Daniel Heinlein, Sascha Kurz. Binary subspace codes in small ambient spaces. Advances in Mathematics of Communications, 2018, 12 (4) : 817-839. doi: 10.3934/amc.2018048

[3]

Heide Gluesing-Luerssen, Carolyn Troha. Construction of subspace codes through linkage. Advances in Mathematics of Communications, 2016, 10 (3) : 525-540. doi: 10.3934/amc.2016023

[4]

Ernst M. Gabidulin, Pierre Loidreau. Properties of subspace subcodes of Gabidulin codes. Advances in Mathematics of Communications, 2008, 2 (2) : 147-157. doi: 10.3934/amc.2008.2.147

[5]

Daniele Bartoli, Matteo Bonini, Massimo Giulietti. Constant dimension codes from Riemann-Roch spaces. Advances in Mathematics of Communications, 2017, 11 (4) : 705-713. doi: 10.3934/amc.2017051

[6]

Anna-Lena Trautmann. Isometry and automorphisms of constant dimension codes. Advances in Mathematics of Communications, 2013, 7 (2) : 147-160. doi: 10.3934/amc.2013.7.147

[7]

Natalia Silberstein, Tuvi Etzion. Large constant dimension codes and lexicodes. Advances in Mathematics of Communications, 2011, 5 (2) : 177-189. doi: 10.3934/amc.2011.5.177

[8]

Daniele Bartoli, Adnen Sboui, Leo Storme. Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes. Advances in Mathematics of Communications, 2016, 10 (2) : 355-365. doi: 10.3934/amc.2016010

[9]

Linda Beukemann, Klaus Metsch, Leo Storme. On weighted minihypers in finite projective spaces of square order. Advances in Mathematics of Communications, 2015, 9 (3) : 291-309. doi: 10.3934/amc.2015.9.291

[10]

Roland D. Barrolleta, Emilio Suárez-Canedo, Leo Storme, Peter Vandendriessche. On primitive constant dimension codes and a geometrical sunflower bound. Advances in Mathematics of Communications, 2017, 11 (4) : 757-765. doi: 10.3934/amc.2017055

[11]

Andries E. Brouwer, Tuvi Etzion. Some new distance-4 constant weight codes. Advances in Mathematics of Communications, 2011, 5 (3) : 417-424. doi: 10.3934/amc.2011.5.417

[12]

Hannes Bartz, Antonia Wachter-Zeh. Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. Advances in Mathematics of Communications, 2018, 12 (4) : 773-804. doi: 10.3934/amc.2018046

[13]

Antonio Cossidente, Francesco Pavese, Leo Storme. Optimal subspace codes in $ {{\rm{PG}}}(4,q) $. Advances in Mathematics of Communications, 2019, 13 (3) : 393-404. doi: 10.3934/amc.2019025

[14]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119

[15]

Somphong Jitman, Ekkasit Sangwisut. The average dimension of the Hermitian hull of constacyclic codes over finite fields of square order. Advances in Mathematics of Communications, 2018, 12 (3) : 451-463. doi: 10.3934/amc.2018027

[16]

Aicha Batoul, Kenza Guenda, T. Aaron Gulliver. Some constacyclic codes over finite chain rings. Advances in Mathematics of Communications, 2016, 10 (4) : 683-694. doi: 10.3934/amc.2016034

[17]

Somphong Jitman, San Ling, Patanee Udomkavanich. Skew constacyclic codes over finite chain rings. Advances in Mathematics of Communications, 2012, 6 (1) : 39-63. doi: 10.3934/amc.2012.6.39

[18]

Eimear Byrne. On the weight distribution of codes over finite rings. Advances in Mathematics of Communications, 2011, 5 (2) : 395-406. doi: 10.3934/amc.2011.5.395

[19]

Pedro A. S. Salomão. The Thurston operator for semi-finite combinatorics. Discrete & Continuous Dynamical Systems - A, 2006, 16 (4) : 883-896. doi: 10.3934/dcds.2006.16.883

[20]

Thomas Westerbäck. Parity check systems of nonlinear codes over finite commutative Frobenius rings. Advances in Mathematics of Communications, 2017, 11 (3) : 409-427. doi: 10.3934/amc.2017035

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (45)
  • HTML views (263)
  • Cited by (0)

[Back to Top]