Article Contents
Article Contents

# Lengths of divisible codes with restricted column multiplicities

• *Corresponding author: Sascha Kurz
• We determine the minimum possible column multiplicity of even, doubly-, and triply-even codes given their length. This refines a classification result for the possible lengths of $q^r$-divisible codes over $\mathbb{F}_q$. We also give a few computational results for field sizes $q>2$. Non-existence results of divisible codes with restricted column multiplicities for a given length have applications e.g. in Galois geometry and can be used for upper bounds on the maximum cardinality of subspace codes.

Mathematics Subject Classification: Primary: 51E23; Secondary: 05B40.

 Citation:

• Table 1.  Combinatorial data of 4-divisible multisets of points of cardinality 17

 $n$ $k$ $\Delta$ $\gamma_1$ $\lambda_1$ $\lambda_2$ $\lambda_3$ spectrum 17 3 4 7 4 0 2 $(a_{5},a_{9},a_{13})=(4,2,1)$ 17 3 4 5 3 0 3 $(a_{5},a_{9},a_{13})=(3,4,0)$ 17 4 4 7 6 2 0 $(a_{5},a_{9},a_{13})=(8,3,4)$ 17 4 4 6 6 1 1 $(a_{5},a_{9},a_{13})=(7,5,3)$ 17 4 4 5 5 2 1 $(a_{5},a_{9},a_{13})=(6,7,2)$ 17 4 4 4 6 2 1 $(a_{5},a_{9},a_{13})=(5,9,1)$ 17 4 4 4 4 0 3 $(a_{5},a_{9},a_{13})=(6,7,2)$ 17 4 4 3 4 2 3 $(a_{5},a_{9},a_{13})=(5,9,1)$ 17 4 4 3 6 4 1 $(a_{5},a_{9},a_{13})=(4,11,0)$ 17 5 4 7 10 0 0 $(a_{5},a_{9},a_{13})=(16,5,10)$ 17 5 4 6 7 2 0 $(a_{5},a_{9},a_{13})=(14,9,8)$ 17 5 4 5 9 0 1 $(a_{5},a_{9},a_{13})=(12,13,6)$ 17 5 4 5 6 3 0 $(a_{5},a_{9},a_{13})=(12,13,6)$ 17 5 4 4 7 3 0 $(a_{5},a_{9},a_{13})=(10,17,4)$ 17 5 4 4 10 0 1 $(a_{5},a_{9},a_{13})=(10,17,4)$ 17 5 4 4 6 2 1 $(a_{5},a_{9},a_{13})=(11,15,5)$ 17 5 4 3 5 3 2 $(a_{5},a_{9},a_{13})=(10,17,4)$ 17 5 4 3 9 1 2 $(a_{5},a_{9},a_{13})=(9,19,3)$ 17 5 4 3 10 2 1 $(a_{5},a_{9},a_{13})=(8,21,2)$ 17 5 4 3 6 4 1 $(a_{5},a_{9},a_{13})=(9,19,3)$ 17 5 4 2 7 5 0 $(a_{5},a_{9},a_{13})=(8,21,2)$ 17 5 4 2 11 3 0 $(a_{5},a_{9},a_{13})=(7,23,1)$ 17 5 4 2 15 1 0 $(a_{5},a_{9},a_{13})=(6,25,0)$ 17 6 4 4 10 0 1 $(a_{5},a_{9},a_{13})=(21,31,11)$ 17 6 4 4 7 3 0 $(a_{5},a_{9},a_{13})=(21,31,11)$ 17 6 4 3 11 0 2 $(a_{5},a_{9},a_{13})=(18,37,8)$ 17 6 4 3 10 2 1 $(a_{5},a_{9},a_{13})=(17,39,7)$ 17 6 4 3 6 4 1 $(a_{5},a_{9},a_{13})=(19,35,9)$ 17 6 4 3 12 1 1 $(a_{5},a_{9},a_{13})=(16,41,6)$ 17 6 4 2 7 5 0 $(a_{5},a_{9},a_{13})=(17,39,7)$ 17 6 4 2 11 3 0 $(a_{5},a_{9},a_{13})=(15,43,5)$ 17 6 4 2 13 2 0 $(a_{5},a_{9},a_{13})=(14,45,4)$ 17 6 4 2 15 1 0 $(a_{5},a_{9},a_{13})=(13,47,3)$ 17 6 4 1 17 0 0 $(a_{5},a_{9},a_{13})=(12,49,2)$ 17 7 4 2 11 3 0 $(a_{5},a_{9},a_{13})=(31,83,13)$ 17 7 4 2 7 5 0 $(a_{5},a_{9},a_{13})=(35,75,17)$ 17 7 4 2 13 2 0 $(a_{5},a_{9},a_{13})=(29,87,11)$ 17 7 4 2 15 1 0 $(a_{5},a_{9},a_{13})=(27,91,9)$ 17 7 4 1 17 0 0 $(a_{5},a_{9},a_{13})=(25,95,7)$ 17 8 4 1 17 0 0 $(a_{5},a_{9},a_{13})=(51,187,17)$

Table 2.  Number of even codes per dimension $k$ and effective length $n$

 n / k 1 2 3 4 5 6 7 8 9 2 1 3 1 4 1 1 1 5 1 1 1 6 1 2 3 2 1 7 2 4 4 2 1 8 1 3 8 10 7 3 1 9 3 9 18 16 9 3 1 10 1 4 17 37 46 30 13 4 1

Table 3.  Number of doubly-even codes per dimension $k$ and effective length $n$

 n / k 1 2 3 4 5 6 7 8 9 4 1 6 1 7 1 8 1 1 1 1 10 1 1 1 11 1 1 12 1 2 3 4 2 13 1 1 2 14 2 4 6 5 4 15 3 6 6 4 2 16 1 3 8 18 21 15 7 2 17 2 7 14 11 5 1 18 3 9 27 44 45 21 6 19 6 22 52 62 40 10 20 1 4 17 64 149 212 156 65 10

Table 4.  Number of triply-even codes per dimension $k$ and effective length $n$

 n / k 1 2 3 4 5 6 7 8 9 10 11 8 1 12 1 14 1 15 1 16 1 1 1 1 1 20 1 1 1 22 1 1 23 1 1 24 1 2 3 4 4 1 26 1 1 2 27 1 1 1 28 2 4 6 7 6 1 29 1 1 2 1 30 3 6 8 7 6 2 31 4 8 8 6 4 1 32 1 3 8 18 32 34 24 13 5 1 34 2 7 14 11 5 1 35 3 7 7 3 1 36 3 9 27 54 65 36 11 1 37 2 5 8 5 1 38 6 22 57 79 61 21 2 39 10 36 57 49 30 10 1 40 1 4 17 64 194 347 323 187 59 11 1 41 2 12 29 26 12 3

Table 5.  Number of 16-divisible codes per dimension $k$ and effective length $n$

 n / k 1 2 3 4 5 6 7 8 9 10 11 12 16 1 24 1 28 1 30 1 31 1 32 1 1 1 1 1 1 40 1 1 1 44 1 1 46 1 1 47 1 1 48 1 2 3 4 4 3 1 52 1 1 2 54 1 1 1 55 1 1 1 56 2 4 6 7 8 3 1 58 1 1 2 1 59 1 1 1 1 60 3 6 8 9 8 4 1 61 1 1 2 1 1 62 4 8 10 9 8 4 2 63 5 10 10 8 6 3 1 64 1 3 8 18 32 48 48 35 21 11 4 1 68 2 7 14 11 5 1 70 3 7 7 3 1 71 3 7 7 3 1 72 3 9 27 54 75 56 26 6 1 74 2 5 8 5 1 75 2 5 5 4 1 76 6 22 59 86 75 34 9 1 77 2 5 8 6 4 1 78 10 36 64 66 52 28 11 2 79 14 47 71 63 44 23 8 1

Table 6.  Number of 3-divisible ternary linear codes per dimension $k$ and effective length $n$

 n / k 1 2 3 3 1 4 1 6 1 1 7 1 1

Table 7.  Number of 4-divisible quaternary linear codes per dimension $k$ and effective length $n$

 n / k 1 2 3 4 5 6 7 4 1 5 1 8 1 1 9 1 1 10 1 1 1 12 1 2 2 13 2 3 1 14 1 5 3 1 15 1 3 6 2 1 16 1 4 9 7 2 17 3 12 9 2 18 2 18 25 8 1 19 1 14 42 25 6 1
•  [1] K. Betsumiya and A. Munemasa, On triply even binary codes, Journal of the London Mathematical Society, 86 (2012), 1-16.  doi: 10.1112/jlms/jdr054. [2] I. Bouyukliev, S. Bouyuklieva and S. Kurz, Computer classification of linear codes, IEEE Transactions on Information Theory, 67 (2021), 7807-7814.  doi: 10.1109/TIT.2021.3114280. [3] R. Calderbank and W. M. Kantor, The geometry of two-weight codes, Bulletin of the London Mathematical Society, 18 (1986), 97-122. [4] J. De Beule, J. Demeyer, S. Mattheus and P. Sziklai, On the cylinder conjecture, Designs, Codes and Cryptography, 87 (2019), 879-893.  doi: 10.1007/s10623-018-0571-5. [5] S. Dodunekov and J. Simonis, Codes and projective multisets, The Electronic Journal of Combinatorics, 5 (1998), 23 pp. doi: 10.37236/1375. [6] C. F. Doran, M. G. Faux, S. James, G. D. Landweber and R. L. Miller, Codes and supersymmetry in one dimension, Advances in Theoretical and Mathematical Physics, 15 (2011), 1909-1970. [7] T. Etzion, Covering of subspaces by subspaces, Designs, Codes and Cryptography, 72 (2014), 405-421.  doi: 10.1007/s10623-012-9766-3. [8] T. Etzion, S. Kurz, K. Otal and F. Özbudak, Subspace packings: Constructions and bounds, Designs, Codes and Cryptography, 88 (2020), 1781-1810.  doi: 10.1007/s10623-020-00732-z. [9] D. Heinlein, T. Honold, M. Kiermaier, S. Kurz and A. Wassermann, Projective divisible binary codes, in The Tenth International Workshop on Coding and Cryptography 2017 : WCC Proceedings, IEEE Information Theory Society, Saint-Petersburg, 2017, https://eref.uni-bayreuth.de/40887/. [10] T. Honold, M. Kiermaier and S. Kurz, Partial spreads and vector space partitions, in Network Coding and Subspace Designs, (2018), 131-170. [11] T. Honold, M. Kiermaier and S. Kurz, Classification of large partial plane spreads in PG(6, 2) and related combinatorial objects, Journal of Geometry, 110 (2019), 1-31.  doi: 10.1007/s00022-018-0459-6. [12] T. Honold, M. Kiermaier and S. Kurz, Johnson type bounds for mixed dimension subspace codes, The Electronic Journal of Combinatorics, 26 (2019), 21 pp. doi: 10.37236/8188. [13] T. Honold, M. Kiermaier, S. Kurz and A. Wassermann, The lengths of projective triply-even binary codes, IEEE Transactions on Information Theory, 66 (2020), 2713-2716.  doi: 10.1109/tit.2019.2940967. [14] M. Kiermaier and S. Kurz, On the lengths of divisible codes, IEEE Transactions on Information Theory, 66 (2020), 4051-4060.  doi: 10.1109/TIT.2020.2968832. [15] M. Kiermaier and S. Kurz, Classification of δ-divisible linear codes spanned by codewords of weight δ, IEEE Transactions on Information Theory, 69 (2023), 3544-3551. [16] S. Kurz, No projective 16-divisible binary linear code of length 131 exists, IEEE Communications Letters, 25 (2020), 38-40. [17] S. Kurz and S. Mattheus, A generalization of the cylinder conjecture for divisible codes, IEEE Transactions on Information Theory, 68 (2022), 2281-2289. [18] I. Landjev and A. Rousseva, Divisible arcs, divisible codes, and the extension problem for arcs and codes, Problems of Information Transmission, 55 (2019), 226-240.  doi: 10.1134/s0555292319030033. [19] T. Miezaki and H. Nakasora, The support designs of the triply even binary codes of length 48, Journal of Combinatorial Designs, 27 (2019), 673-681.  doi: 10.1002/jcd.21670. [20] B. G. Rodrigues, On some projective triply-even binary codes invariant under the conway group Co1, International Journal of Group Theory, 11 (2022), 23-35. [21] H. N. Ward, Divisible codes, Archiv der Mathematik, 36 (1981), 485-494.  doi: 10.1007/BF01223730.

Tables(7)