New and updated semidefinite programming bounds for subspace codes

Daniel Heinlein; Ferdinand Ihringer

doi:10.3934/amc.2020034

Article Contents

2020, Volume 14, Issue 4: 613-630. Doi: 10.3934/amc.2020034

This issue Previous Article Designs from maximal subgroups and conjugacy classes of Ree groups Next Article Abelian non-cyclic orbit codes and multishot subspace codes

New and updated semidefinite programming bounds for subspace codes

Daniel Heinlein^1, , and
Ferdinand Ihringer^2,

1.
Department of Communications and Networking, Aalto University, Finland
2.
Department of Mathematics: Analysis, Logic and Discrete Mathematics, Ghent University, Belgium

* Corresponding author: Daniel Heinlein
* Corresponding author: Daniel Heinlein

Received: August 31, 2018

Revised: June 30, 2019

Early access: November 2019

Published: November 2020

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

Abstract

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

Keywords:

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

Citation:

Full Text(HTML)

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

Related Papers

Cited by

References

[1]	J. Ai, T. Honold and H. Liu, The expurgation-augmentation method for constructing good plane subspace codes, preprint, arXiv: 1601.01502.
[2]	C. Bachoc, A. 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. Braun, M. 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. Reichelt, q-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. Heinlein, M. Kiermaier, S. 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. Honold, M. 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. Kiermaier, S. 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. Miyakawa, A. 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.