Sidon sets, sum-free sets and linear codes

Ingo Czerwinski; Alexander Pott

doi:10.3934/amc.2023054

Article Contents

2024, Volume 18, Issue 2: 549-566. Doi: 10.3934/amc.2023054

This issue Previous Article On the structure of the linear codes with a given automorphism Next Article On the number of $ t $-Lee-error-correcting codes

Sidon sets, sum-free sets and linear codes

Ingo Czerwinski^1, , and
Alexander Pott^1,

1.
Otto-von-Guericke University Magdeburg, Germany

^*Corresponding author: Ingo Czerwinski
^*Corresponding author: Ingo Czerwinski

Received: April 2023

Revised: October 2023

Early access: November 2023

Published: April 2024

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

Abstract

Finding the maximum size of a Sidon set in $ \mathbb{F}_2^{{t}} $ is of research interest for more than 40 years. In order to tackle this problem we recall a one-to-one correspondence between sum-free Sidon sets and linear codes with minimum distance greater or equal 5. Our main contribution about codes is a new non-existence result for linear codes with minimum distance 5 based on a sharpening of the Johnson bound. This gives, on the Sidon set side, an improvement of the general upper bound for the maximum size of a Sidon set. Additionally, we characterise maximal Sidon sets, that are those Sidon sets which can not be extended by adding elements without losing the Sidon property, up to dimension 6 and give all possible sizes for dimension 7 and 8 determined by computer calculations.

Keywords:

Mathematics Subject Classification: Primary: 11B13, 94B05, 94B65.

Citation:

Full Text(HTML)

Table 1. Examples of maximal Sidon sets $ M $ in $ \mathbb{F}_2^{{t}} $ of all possible sizes for dimension $ t = 7 $ and $ t = 8 $

$ t $	$ \left\lvert{M}\right\rvert $	$ M $
7	12	$ {0, 1, 2, 4, 8, 16, 32, 64, 15, 60,101, 87} $
8	15	$ {0, 1, 2, 4, 8, 16, 32, 64,128, 29, 58,116,135,223,236} $
8	16	$ {0, 1, 2, 4, 8, 16, 32, 64,128, 29, 58,116,232,205,135,222} $
8	18	$ {0, 1, 2, 4, 8, 16, 32, 64,128, 29, 58,116,232,205,135,254, 91,171} $

| Show Table

DownLoad: CSV

Table 2. Maximal size of a Sidon set in $ \mathbb{F}_2^{{t}} $ and related bounds/constructions

$ t $	4	5	6	7	8	9	10	11	12	13	14	15
Trivial bound (1)	6	8	11	16	23	32	45	64	91	128	181	256
New bound (2)			10	14	21	30	43	62	90	126	180	254
Codes bound	6	7	9	12	18	24	34	58	89	125	179	254
$ s_{max}(\mathbb{F}_2^{{{t}}}) $	6	7	9	12	18	24	34	?	?	?	?	?
Codes constr.	6	7	9	12	18	24	34	48	66	82	129	152

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	L. Babai and V. T. Sós, Sidon sets in groups and induced subgraphs of Cayley graphs, European Journal of Combinatorics, 6 (1985), 101-114. doi: 10.1016/S0195-6698(85)80001-9.
[2]	A. E. Brouwer and L. M. G. M. Tolhuizen, A sharpening of the Johnson bound for binary linear codes and the nonexistence of linear codes with Preparata parameters, Designs, Codes and Cryptography, 3 (1993), 95-98. doi: 10.1007/BF01388407.
[3]	C. Carlet, On APN functions whose graphs are maximal Sidon sets, in Armando Castañeda and Francisco Rodríguez-Henríquez, editors, LATIN 2022: Theoretical Informatics, Springer International Publishing, Cham, (2022), 243-254. doi: 10.1007/978-3-031-20624-5_15.
[4]	C. Carlet, P. Charpin and V. Zinoviev, Codes, bent functions and permutations suitable for DES-like cryptosystems, Designs, Codes and Cryptography, 15 (1998), 125-156. doi: 10.1023/A:1008344232130.
[5]	C. Carlet and S. Mesnager, On those multiplicative subgroups of $\mathbb{F}_{2^n}^$ which are Sidon sets and/or sum-free sets, Journal of Algebraic Combinatorics*, 55 (2022), 43-59. doi: 10.1007/s10801-020-00988-7.
[6]	C. Carlet and S. Picek, On the exponents of APN power functions and Sidon sets, sum-free sets, and Dickson polynomials, Advances in Mathematics of Communications, 17 (2023), 1507-1525. doi: 10.3934/amc.2021064.
[7]	W. E. Clark and J. Pedersen, Sum-free sets in vector spaces over GF(2), Journal of Combinatorial Theory, Series A, 61 (1992), 222-229. doi: 10.1016/0097-3165(92)90019-Q.
[8]	G. Cohen and G. Zémor, Subset sums and coding theory, in Deshouilliers Jean-Marc, Landreau Bernard, and Yudin Alexander A., editors, Structure Theory of set Addition, number 258 in Astérisque. Société mathématique de France, 1999.
[9]	M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, Online available at http://www.codetables.de.
[10]	B. Green and I. Z. Ruzsa, Sum-free sets in abelian groups, Israel Journal of Mathematics, 147 (2005), 157-188. doi: 10.1007/BF02785363.
[11]	S. M. Johnson, A new upper bound for error-correcting codes, IRE Transactions on Information Theory, 8 (1962), 203-207. doi: 10.1109/tit.1962.1057714.
[12]	G. Péter Nagy, Thin Sidon sets and the nonlinearity of vectorial Boolean functions, preprint, (2022). arXiv: 2212.05887.
[13]	M. Redman, L. Rose and R. Walker, A small maximal Sidon set in ${\mathbb{Z}}_2^n$, SIAM Journal on Discrete Mathematics, 36 (2022), 1861-1867. doi: 10.1137/21M1454663.
[14]	R. Schürer and W. C. Schmid, MinT: A database for optimal net parameters, in Monte Carlo and Quasi-Monte Carlo Methods 2004, Springer, (2006), 457-469. doi: 10.1007/3-540-31186-6_28.
[15]	S. Sidon, Ein Satz über trigonometrische Polynome und seine Anwendung in der Theorie der Fourier-Reihen, Mathematische Annalen, 106 (1932), 536-539. doi: 10.1007/BF01455900.
[16]	S. Sidon, Über die Fourier Konstanten der Funktionen der Klasse $L_p$ für $p>1$, Acta Univ. Szeged Sect. Sci. Math., 7 (1935), 175-176.
[17]	A. Sidorenko, On generalized Erdős-Ginzburg-Ziv constants for ${\mathbb{Z}}_2^d$, Journal of Combinatorial Theory, Series A, 174 (2020), 105254, 20 pp. doi: 10.1016/j.jcta.2020.105254.
[18]	M. Tait and R. Won, Improved bounds on sizes of generalized caps in $AG(n, q)$, SIAM Journal on Discrete Mathematics, 35 (2021), 521-531. doi: 10.1137/20M1369439.
[19]	T. Tao and Van Vu, Sum-free sets in groups: A survey, Journal of Combinatorics, 8 (2017), 541-552. doi: 10.4310/JOC.2017.v8.n3.a7.