\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Sidon sets, sum-free sets and linear codes

  • *Corresponding author: Ingo Czerwinski

    *Corresponding author: Ingo Czerwinski 
Abstract / Introduction Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by
  • 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:

    \begin{equation} \\ \end{equation}
  • 加载中
  • 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
  • [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. CarletP. 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. RedmanL. 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)

SHARE

Article Metrics

HTML views(1023) PDF downloads(189) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return