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.

[2]

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

[3]

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

[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.

[5]

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

[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.

[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.

[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.

[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.

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[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.

[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.

[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.

[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.

[20]

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

[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.

[22]

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

[23]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[31]

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

[32]

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

[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.

[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.

[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.

[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.

[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.

[38]

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

[39]

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

[40]

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

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.

[2]

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

[3]

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

[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.

[5]

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

[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.

[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.

[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.

[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.

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[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.

[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.

[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.

[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.

[20]

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

[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.

[22]

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

[23]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[31]

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

[32]

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

[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.

[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.

[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.

[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.

[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.

[38]

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

[39]

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

[40]

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

[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]

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

[15]

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

[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

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (38)
  • HTML views (207)
  • Cited by (0)

[Back to Top]