\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

New and updated semidefinite programming bounds for subspace codes

  • * Corresponding author: Daniel Heinlein

    * Corresponding author: Daniel Heinlein 

The first author is supported by the Academy of Finland, Grant #289002. The second author is supported by a postdoctoral fellowship of the Research Foundation - Flanders (FWO)

Abstract Full Text(HTML) Figure(0) / Table(6) Related Papers Cited by
  • We show that $A_2(7, 4) \leq 388$ and, more generally, $A_q(7, 4) \leq (q^2-q+1) [7] + q^4 - 2q^3 + 3q^2 - 4q + 4$ by semidefinite programming for $q \leq 101$. Furthermore, we extend results by Bachoc et al. on SDP bounds for $A_2(n, d)$, where $d$ is odd and $n$ is small, to $A_q(n, d)$ for small $q$ and small $n$.

    Mathematics Subject Classification: Primary: 51E20; Secondary: 05B25, 11T71, 94B25.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Table 1.  Here $ \varphi = q^2+1 $ and $ \psi = q^2-q+1 $

    $ A_{abc} $ $ m_{abc}/|X_a| $ $ \Delta_0(A_{abc}) $ $ \Delta_1(A_{abc}) $ $ \Delta_2(A_{abc}) $ $ \Delta_3(A_{abc}) $
    $ A_{110} $ $ 1 $ $ E_{11} $ $ E_{11} $
    $ A_{111} $ $ q[6] $ $ q[6] E_{11} $ $ -E_{11} $
    $ A_{120} $ $ [6] $ $ [2] \sqrt{ \psi[3] } E_{12} $ $ \sqrt{q [5] } E_{12} $
    $ A_{121} $ $ q^2\psi [3] [5] $ $ q^2 [5] \sqrt{ \psi[3] } E_{12} $ $ -\sqrt{q [5] } E_{12} $
    $ A_{130} $ $ \left[ \begin{array}{l} {6}\\{2} \end{array} \right] $ $ [3] \sqrt{ \psi [5] } E_{13} $ $ q \sqrt{ \varphi [5]} E_{13} $
    $ A_{131} $ $ q^3(q^3+1)\left[ \begin{array}{l}{5}\\{2}\end{array} \right] $ $ q^3 [4] \sqrt{ \psi [5] } E_{13} $ $ -q \sqrt{ \varphi [5]}E_{13} $
    $ A_{140} $ $ \left[ \begin{array}{l} 6\\3\end{array} \right] $ $ [4] \sqrt{ \psi [5] } E_{14} $ $ q \sqrt{q \varphi [5]} E_{14} $
    $ A_{141} $ $ q^4 \psi [3] [5] $ $ q^4 [3] \sqrt{ \psi [5] } E_{14} $ $ -q \sqrt{q \varphi [5]} E_{14} $
    $ A_{150} $ $ \left[ \begin{array}{l} {6}\\{4} \end{array} \right] $ $ [5] \sqrt{ \psi [3] } E_{15} $ $ q^2 \sqrt{ [5] } E_{15} $
    $ A_{151} $ $ q^5[6] $ $ q^5 [2] \sqrt{ \psi [3] } E_{15} $ $ -q^2 \sqrt{ [5] } E_{15} $
    $ A_{160} $ $ \left[ \begin{array}{l} 6\\5\end{array} \right] $ $ [6] E_{16} $ $ q^{5/2} E_{16} $
    $ A_{161} $ $ q^6 $ $ q^6 E_{16} $ $ -q^{5/2} E_{16} $
    $ A_{220} $ $ 1 $ $ E_{22} $ $ E_{22} $ $ E_{22} $
    $ A_{221} $ $ q[2] [5] $ $ q[2] [5] E_{22} $ $ (q^2 [4] - 1)E_{22} $ $ -[2]E_{22} $
    $ A_{222} $ $ q^4\varphi [5] $ $ q^4\varphi [5] E_{22} $ $ -q^2 [4] E_{22} $ $ qE_{22} $
    $ A_{230} $ $ [5] $ $ \sqrt{ [3] [5] } E_{23} $ $ [2] \sqrt{q\varphi} E_{23} $ $ q \sqrt{ [3] } E_{23} $
    $ A_{231} $ $ q^2 [4][5] $ $ q^2 [4] \sqrt{ [3] [5] } E_{23} $ $ (q^3[3] - [2]) \sqrt{q\varphi} E_{23} $ $ -q[2] \sqrt{ [3] } E_{23} $
    $ A_{232} $ $ q^6\varphi[5] $ $ q^6 \varphi \sqrt{ [3] [5] } E_{23} $ $ -q^3[3] \sqrt{q\varphi} E_{23} $ $ q^2\sqrt{ [3] } E_{23} $
    $ A_{240} $ $ \varphi[5] $ $ \varphi \sqrt{ [3] [5] } E_{24} $ $ q [3] \sqrt{\varphi} E_{24} $ $ q^2 \sqrt{[3]}E_{24} $
    $ A_{241} $ $ q^3 [4][5] $ $ q^3 [4] \sqrt{ [3] [5] } E_{24} $ $ q (q^4[2]-[3]) \sqrt{\varphi} E_{24} $ $ -q^2[2] \sqrt{[3]} E_{24} $
    $ A_{242} $ $ q^8 [5] $ $ q^8 \sqrt{ [3] [5] } E_{24} $ $ -q^5 [2] \sqrt{\varphi} E_{24} $ $ q^3 \sqrt{[3]} E_{24} $
    $ A_{250} $ $ \varphi [5] $ $ \varphi [5] E_{25} $ $ q^{3/2} [4] E_{25} $ $ q^3 E_{25} $
    $ A_{251} $ $ q^4 [2] [5] $ $ q^4 [2] [5] E_{25} $ $ q^{3/2}(q^5 - [4]) E_{25} $ $ -[2] q^3E_{25} $
    $ A_{252} $ $ q^{10} $ $ q^{10} E_{25} $ $ -q^{13/2} E_{25} $ $ q^4 E_{25} $
    $ A_{330} $ $ 1 $ $ E_{33} $ $ E_{33} $ $ E_{33} $ $ E_{33} $
    $ A_{331} $ $ q [3] [4] $ $ q [3] [4] E_{33} $ $ (q^2[2][3] - 1)E_{33} $ $ (q^2-1) [3] E_{33} $ $ -[3] E_{33} $
    $ A_{332} $ $ q^4 \varphi [3]^2 $ $ q^4 \varphi [3]^2 E_{33} $ $ q^2 [3] (q^4-q-1)E_{33} $ $ -q[3] (q^2+q-1)E_{33} $ $ q [3] E_{33} $
    $ A_{333} $ $ q^9[4] $ $ q^9[4] E_{33} $ $ -q^6 [3] E_{33} $ $ q^4 [2]E_{33} $ $ -q^3 E_{33} $
    $ A_{340} $ $ [4] $ $ [4] E_{34} $ $ [3] \sqrt{q} E_{34} $ $ q [2] E_{34} $ $ \sqrt{q^3 } E_{34} $
    $ A_{341} $ $ q^2\varphi[3]^2 $ $ q^2 \varphi [3]^2 E_{34} $ $ [3] (q^3[2]-1) \sqrt{q} E_{34} $ $ q [3](q^2-q-1) E_{34} $ $ -[3] \sqrt{q^3 } E_{34} $
    $ A_{342} $ $ q^6[3] [4] $ $ q^6 [3] [4] E_{34} $ $ q^3(q^5-[2][3]) \sqrt{q} E_{34} $ $ -q^2 (q^3-1) [2] E_{34} $ $ q[3] \sqrt{q^3 }E_{34} $
    $ A_{343} $ $ q^{12} $ $ q^{12} E_{34} $ $ -q^8 \sqrt{q} E_{34} $ $ q^6 E_{34} $ $ -q^3\sqrt{q^3 }E_{34} $
    $ f_s $ $ 1 $ $ [7]-1 $ $ \left[ \begin{array}{l} 7\\2\end{array} \right] - [7] $ $ \left[ \begin{array}{l} 7\\3\end{array} \right] - \left[ \begin{array}{l} 7\\2\end{array} \right] $
     | Show Table
    DownLoad: CSV

    Table 2.  SDP bounds on $ A_2(n, d) $

    $ d \setminus n $ 8 9 10 11 12 13 14
    3 9191 107419 2531873 57201557 2685948795 119527379616 11215665059647
    4 6479 53710 1705394 28600778 1816165540 59763689822 7496516673358
    5 327 2458 48255 660265 26309023 688127334 54724534275
    6 260 1240 38455 330133 21362773 344063682 43890879895
    7 1219 8844 314104 4678401 330331546
    8 1090 4480 279476 2343888 292988615
    9 4483 34058 2298622
    10 4226 17133 2164452
    11 259 17155
    12 16642
     | Show Table
    DownLoad: CSV

    Table 3.  SDP bounds on $ A_3(n, d) $

    $ d \setminus n $ 6 7 8 9 10 11 12
    3 967 15394 760254 34143770 5026344026 675225312722 298950313257852
    4 788 7696 627384 17071886 4112061519 337612656529 244829520433920
    5 166 7222 123535 16008007 818518696 320387589445
    6 6727 61962 14893814 409259348 298571221318
    7 490 61002 1076052 400831735
    8 59539 539351 391178436
    9 1462 537278
    10 532903
     | Show Table
    DownLoad: CSV

    Table 4.  SDP bounds on $ A_4(n, d) $

    $ d \setminus n $ 6 7 8 9 10 11
    3 4772 142313 20482322 2341621613 1343547758223 614496020025690
    4 4231 71156 18245203 1170810807 1194101275238 307248010015067
    5 516 68117 2132181 1122729102 140323867490
    6 66054 1067796 1088550221 70161933745
    7 2052 1058831 33669242
    8 1050630 16847095
    9 8196
     | Show Table
    DownLoad: CSV

    Table 5.  SDP bounds on $ A_5(n, d) $

    $ d \setminus n $ 6 7 8 9 10
    3 17179 821170 277100135 64262978412 108238287449582
    4 15883 410585 256754528 32131489207 100215014898311
    5 1254 398154 19675409 31196584033
    6 391883 9847885 30703887393
    7 6254 9803150
    8 9771883
     | Show Table
    DownLoad: CSV

    Table 6.  SDP bounds on $ A_7(n, d) $

    $ d \setminus n $ 6 7 8 9 10
    3 123239 11807778 14753449680 9728400942608 85039309360944189
    4 118347 5903889 14176726504 4864200471305 81703574152063079
    5 4806 5803270 566262547 4784663914039
    6 5769615 283240686 4756893963688
    7 33618 282744208
    8 282508875
     | Show Table
    DownLoad: CSV
  • [1] J. Ai, T. Honold and H. Liu, The expurgation-augmentation method for constructing good plane subspace codes, preprint, arXiv: 1601.01502.
    [2] C. BachocA. Passuello and F. Vallentin, Bounds for projective codes from semidefinite programming, Adv. Math. Commun., 7 (2013), 127-145.  doi: 10.3934/amc.2013.7.127.
    [3] A. Beutelspacher, Partial spreads in finite projective spaces and partial designs, Math. Z., 145 (1975), 211-229.  doi: 10.1007/BF01215286.
    [4] 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.
    [5] M. BraunM. Kiermaier and A. Nakić, On the automorphism group of a binary q-analog of the Fano plane, European J. Combin., 51 (2016), 443-457.  doi: 10.1016/j.ejc.2015.07.014.
    [6] M. Braun and J. Reicheltq-analogs of packing designs, J. Combin. Des., 22 (2014), 306-321.  doi: 10.1002/jcd.21376.
    [7] A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, Results in Mathematics and Related Areas, 18, Springer-Verlag, Berlin, 1989. doi: 10.1007/978-3-642-74341-2.
    [8] P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl., (1973), 97pp.
    [9] C. F. Dunkl, An addition theorem for some q-Hahn polynomials, Monatsh. Math., 85 (1978), 5-37.  doi: 10.1007/BF01300958.
    [10] T. Etzion, On the structure of the q-Fano plane, preprint, arXiv: 1508.01839.
    [11] T. Etzion, A new approach for examining q-Steiner systems, Electron. J. Combin., 25 (2018), 24pp.
    [12] T. Etzion and N. Silberstein, Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams, IEEE Trans. Inform. Theory, 55 (2009), 2909-2919.  doi: 10.1109/TIT.2009.2021376.
    [13] T. Etzion and A. Vardy, Error-correcting codes in projective space, IEEE Trans. Inform. Theory, 57 (2011), 1165-1173.  doi: 10.1109/TIT.2010.2095232.
    [14] T. Etzion and A. Vardy, On q-analogs of Steiner systems and covering designs, Adv. Math. Commun., 5 (2011), 161-176.  doi: 10.3934/amc.2011.5.161.
    [15] O. Heden and P. A. Sissokho, On the existence of a (2, 3)-spread in V(7, 2), Ars Combin., 124 (2016), 161-164. 
    [16] D. Heinlein, M. Kiermaier, S. Kurz and A. Wassermann, Tables of subspace codes, preprint, arXiv: 1601.02864.
    [17] D. HeinleinM. KiermaierS. Kurz and A. Wassermann, A subspace code of size 333 in the setting of a binary q-analog of the Fano plane, Adv. Math. Commun., 13 (2019), 457-475.  doi: 10.3934/amc.2019029.
    [18] D. G. Higman, Coherent configurations part Ⅰ: Ordinary representation theory, Geometriae Dedicata, 4 (1975), 1-32.  doi: 10.1007/BF00147398.
    [19] D. G. Higman, Coherent configurations part: Ⅱ: Weights, Geometriae Dedicata, 5 (1976), 413-424.  doi: 10.1007/BF00150773.
    [20] D. G. Higman, Coherent algebras, Linear Algebra Appl., 93 (1987), 209-239.  doi: 10.1016/S0024-3795(87)90326-0.
    [21] S. A. Hobart, Bounds on subsets of coherent configurations, Michigan Math. J., 58 (2009), 231-239.  doi: 10.1307/mmj/1242071690.
    [22] S. A. Hobart and J. Williford, Tightness in subset bounds for coherent configurations, J. Algebraic Combin., 39 (2014), 647-658.  doi: 10.1007/s10801-013-0459-4.
    [23] 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.
    [24] T. HonoldM. Kiermaier and S. Kurz, Constructions and bounds for mixed-dimension subspace codes, Adv. Math. Commun., 10 (2016), 649-682.  doi: 10.3934/amc.2016033.
    [25] T. Honold, M. Kiermaier and S. Kurz, Johnson type bounds for mixed dimension subspace codes, preprint, arXiv: 1808.03580.
    [26] 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, Des. Codes Cryptogr., 86 (2018), 239-250.  doi: 10.1007/s10623-017-0360-6.
    [27] M. Kiermaier and M. O. Pavčević, Intersection numbers for subspace designs, J. Combin. Des., 23 (2015), 463-480.  doi: 10.1002/jcd.21403.
    [28] A. Kohnert and S. Kurz, Construction of large constant dimension codes with a prescribed minimum distance, in Mathematical Methods in Computer Science, Lecture Notes in Comput. Sci., 5393, Springer, Berlin, 2008, 31–42. doi: 10.1007/978-3-540-89994-5_4.
    [29] R. Kötter and F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory, 54 (2008), 3579-3591.  doi: 10.1109/TIT.2008.926449.
    [30] H. Liu and T. Honold, A new approach to the main problem of subspace coding, 9th International Conference on Communications and Networking in China, 2014. Available at arXiv: 1408.1181.
    [31] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. I, North-Holland Mathematical Library, 16, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.
    [32] K. Metsch, Bose-Burton type theorems for finite projective, affine and polar spaces, in Surveys in Combinatorics, London Math. Soc. Lecture Note Ser., 267, Cambridge Univ. Press, Cambridge, 1999, 137-166.
    [33] M. MiyakawaA. Munemasa and S. Yoshiara, On a class of small 2-designs over GF(q), J. Combin. Des., 3 (1995), 61-77.  doi: 10.1002/jcd.3180030108.
    [34] A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory, 51 (2005), 2859-2866.  doi: 10.1109/TIT.2005.851748.
    [35] S. Thomas, Designs over finite fields, Geom. Dedicata, 24 (1987), 237-242.  doi: 10.1007/BF00150939.
    [36] S. Thomas, Designs and partial geometries over finite fields, Geom. Dedicata, 63 (1996), 247-253.  doi: 10.1007/BF00181415.
    [37] L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Rev., 38 (1996), 49-95.  doi: 10.1137/1038003.
    [38] Y. Watanabe, An Algebraic Study of Association Schemes and Its Applications, Master's thesis, Tohoku University, 2015.
    [39] M. Yamashita, K. Fujisawa, M. Fukuda, K. Kobayashi, K. Nakata and M. Nakata, Latest developments in the SDPA family for solving large-scale SDPs, in Handbook on Semidefinite, Conic and Polynomial Optimization, Internat. Ser. Oper. Res. Management Sci., 166, Springer, New York, 2012,687–713. doi: 10.1007/978-1-4614-0769-0_24.
  • 加载中

Tables(6)

SHARE

Article Metrics

HTML views(931) PDF downloads(307) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return