Article Contents
Article Contents

# Sidon sets, sum-free sets and linear codes

• *Corresponding author: Ingo Czerwinski
• 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.

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

 Citation:

• 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}$

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
•  [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.

Tables(2)