Lengths of divisible codes with restricted column multiplicities

Theresa Körner; Sascha Kurz

doi:10.3934/amc.2023050

Article Contents

2024, Volume 18, Issue 2: 505-534. Doi: 10.3934/amc.2023050

This issue Previous Article A class of weightwise almost perfectly balanced Boolean functions Next Article On the structure of the linear codes with a given automorphism

Lengths of divisible codes with restricted column multiplicities

Theresa Körner^1, and
Sascha Kurz^1, ,

1.
University of Bayreuth, 95440 Bayreuth, Germany

^*Corresponding author: Sascha Kurz
^*Corresponding author: Sascha Kurz

Received: March 2023

Revised: November 2023

Early access: November 2023

Published: April 2024

Abstract / Introduction Full Text(HTML) Figure(0) / Table(7) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[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 Co₁, 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.