# Sidon sets, sum-free sets and linear codes

Ingo Czerwinski and Alexander Pott11footnotemark: 1 Faculty of Mathematics,
Otto von Guericke University Magdeburg, 39106 Magdeburg, Germany,
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### 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 loosing the Sidon
property, up to dimension 6 and give all possible sizes for dimension 7 and 8
determined by computer calculations.

Keywords Sidon set, sum-free set, maximum size, linear binary code, codes
bound.

Mathematics Subject Classification (2020) 11B13, 94B05, 94B65

##  1 Sidon sets

In the early 1930s Sidon introduced $B_{2}$-sequences of positive integers in
connection with his work on Fourier analysis [9], [10]. Later, Babai and Sós
[1] generalised the definition of $B_{2}$-sequences to arbitrary groups and
called them Sidon sets. In this work, we focus only on Sidon sets in
$\mathbb{F}_{2}^{t}$, the $t$-dimensional vector space over the binary field
$\mathbb{F}_{2}$.

######  Definition 1.1.

Let $M$ be a subset of $\mathbb{F}_{2}^{t}$. $M$ is called Sidon if
$m_{1}+m_{2}\neq m_{3}+m_{4}$ for all pairwise distinct
$m_{1},m_{2},m_{3},m_{4}\in M$.

Since the definition of Sidon sets is based on sums, we introduce the
following notation: Let $M$ be a subset of $\mathbb{F}_{2}^{t}$. For any
$k\geq 2$ we call

$\mathcal{S}_{k}(M)=\\{m_{1}+\dotsb+m_{k}:m_{1},\dotsc,m_{k}\in M\\}$

the $k$-sums of $M$ and

$\mathcal{S}_{k}^{*}(M)=\\{m_{1}+\dotsb+m_{k}:m_{1},\dotsc,m_{k}\in M\text{
pairwise distinct}\\}$

the $k$-star-sums of $M$. In this paper, only 2, 3 and 4-(star)-sums are
considered. The characteristic 2 of $\mathbb{F}_{2}^{t}$ leads to the
following frequently used properties:

  1. (a)

$\mathcal{S}_{2}(M)=\mathcal{S}_{2}^{*}(M)\cup\\{0\\}$;

  2. (b)

$\mathcal{S}_{3}(M)=\mathcal{S}_{3}^{*}(M)\cup M$;

  3. (c)

$\mathcal{S}_{4}(M)=\mathcal{S}_{4}^{*}(M)\cup\mathcal{S}_{2}^{*}(M)\cup\\{0\\}$.

We recall also, that the (Hamming) weight of a vector is the number of its
non-zero entries. The weight of a vector is of interest when considering the
sums of the elements of a set containing the standard basis.

The Sidon property of $M$ can be characterised in terms of $2$-star-sums and
$3$-star-sums by the following equivalent statements:

  1. (a)

$M$ is Sidon;

  2. (b)

$\left\lvert\mathcal{S}_{2}^{*}(M)\right\rvert=\binom{\left\lvert
M\right\rvert}{2}$;

  3. (c)

$\mathcal{S}_{3}^{*}(M)\cap M=\emptyset$.

The fundamental problem about a Sidon set is the question about its maximum
size, which was already discussed about 40 years ago by Babai and Sós [1]. We
will denote by $s_{max}(\mathbb{F}_{2}^{t})$ the maximum size of a Sidon set
in $\mathbb{F}_{2}^{t}$. An upper bound arises directly from the fact that all
2-star-sums of $M$ have to be distinct and non-zero, hence

$\binom{\left\lvert M\right\rvert}{2}=\frac{\left\lvert
M\right\rvert(\left\lvert
M\right\rvert-1)}{2}\leq\left\lvert\mathbb{F}_{2}^{t}\setminus\\{0\\}\right\rvert.$

This bound is still the best known upper bound and was translated by Carlet
and Mesnager [3] into an explicit form:

$s_{max}(\mathbb{F}_{2}^{t})\leq\left\lfloor\frac{1+\sqrt{2^{t+3}-7}}{2}\right\rfloor.$

In the next Proposition we rewrite this bound slightly and call it from now on
the trivial upper bound for the maximum size of a Sidon set. Later in Theorem
4.3 we will improve this trivial upper bound.

######  Proposition 1.2.

For any $t$, an upper bound for the maximum size of a Sidon set in
$\mathbb{F}_{2}^{t}$ is given by

$s_{max}(\mathbb{F}_{2}^{t})\leq\begin{cases}2^{\frac{t+1}{2}}&\text{ for $t$
odd},\\\ \left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor&\text{ for $t$
even}.\end{cases}$ (1)

###### Proof.

Let $M\subseteq\mathbb{F}_{2}^{t}$ be a Sidon set. Then the sums $m_{1}+m_{2}$
are distinct and non-zero for all distinct $m_{1},m_{2}\in M$ by the Sidon
definition. Therefore

$\binom{\left\lvert M\right\rvert}{2}=\frac{\left\lvert
M\right\rvert(\left\lvert
M\right\rvert-1)}{2}\leq\left\lvert\mathbb{F}_{2}^{t}\setminus\\{0\\}\right\rvert.$

When $t$ is odd, then $\left\lvert M\right\rvert=2^{\frac{t+1}{2}}$ fulfills
this inequality, but $\left\lvert M\right\rvert=2^{\frac{t+1}{2}}+1$ not
anymore.

Let $t$ be even. We show that
$\left\lfloor\frac{1+\sqrt{2^{t+3}-7}}{2}\right\rfloor=\left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor$.
Of course, we have $\frac{1+\sqrt{2^{t+3}-7}}{2}\;\leq\;\sqrt{2^{t+1}}+0.5$.
Assume that there exists $k\in\mathbb{N}$ such that

$\frac{1+\sqrt{2^{t+3}-7}}{2}\;<\;k\;\leq\;\sqrt{2^{t+1}}+0.5,$

which is equivalent to

$2^{t+1}-\frac{7}{4}\;<\;(k-\frac{1}{2})^{2}\;\leq\;2^{t+1}$

and

$2^{t+1}-2\;<\;k(k-1)\;\leq\;2^{t+1}-\frac{1}{4}.$

But this contradicts $k(k-1)$ even. ∎

After looking at an upper bound for the maximum size of a Sidon set, it is
natural to ask wether every Sidon set can be extended to a Sidon set of
maximum size by adding elements. Already in dimension 6 this is not true, as
we will see later in Proposition 1.8.

Therefore, we now concentrate on the question how a Sidon set can be extended
by adding elements without loosing the Sidon property. We recall the following
notation for sets A, B and C: $A\mathbin{\mathaccent 0{\cdot}\cup}B=C$ means
$A\cup B=C$ and $A\cap B=\emptyset$.

######  Proposition 1.3.

Let $M$ be a Sidon set in $\mathbb{F}_{2}^{t}$ and
$g\in\mathbb{F}_{2}^{t}\setminus M$. Then $M\mathbin{\mathaccent
0{\cdot}\cup}\\{g\\}$ is Sidon if and only if
$g\in\mathbb{F}_{2}^{t}\setminus\mathcal{S}_{3}(M)=\mathbb{F}_{2}^{t}\setminus\big{(}\mathcal{S}_{3}^{*}(M)\mathbin{\mathaccent
0{\cdot}\cup}M\big{)}$.

###### Proof.

Let $M\subseteq\mathbb{F}_{2}^{t}$ be a Sidon set. From
$g\in\mathbb{F}_{2}^{t}\setminus M$ follows that $M\mathbin{\mathaccent
0{\cdot}\cup}\\{g\\}$ is not Sidon if and only if there exist
$m,m_{1},m_{2}\in M$ pairwise distinct such that $g+m=m_{1}+m_{2}$ which is
equivalent to $g=m+m_{1}+m_{2}$. Hence
$g\in\mathcal{S}_{3}^{*}(M)\subseteq\mathcal{S}_{3}^{*}(M)\mathbin{\mathaccent
0{\cdot}\cup}M=\mathcal{S}_{3}(M)$. ∎

Those Sidon sets which can not be extended by adding elements without loosing
the Sidon property are of particular interest:

######  Definition 1.4.

A Sidon set $M\subseteq\mathbb{F}_{2}^{t}$ is called maximal if $M=S$ for
every Sidon set $S$ with $M\subseteq S\subseteq\mathbb{F}_{2}^{t}$.

Proposition 1.3 helps us to characterise maximal Sidon sets via their
$3$-star-sums and $3$-sums.

######  Proposition 1.5.

Let $M$ be a Sidon set in $\mathbb{F}_{2}^{t}$ with $\left\lvert
M\right\rvert\geq 3$ (and therefore $t\geq 2$). Then the following statements
are equivalent:

  1. (a)

$M$ is maximal;

  2. (b)

$\mathcal{S}_{3}(M)=\mathbb{F}_{2}^{t}$;

  3. (c)

$\mathcal{S}_{3}^{*}(M)\mathbin{\mathaccent 0{\cdot}\cup}M=\mathbb{F}_{2}^{t}$
(that means: $\mathcal{S}_{3}^{*}(M)\cup M=\mathbb{F}_{2}^{t}$ and
$\mathcal{S}_{3}^{*}(M)\cap M=\emptyset$).

The property of being Sidon and of being maximal Sidon is invariant under the
action of the affine group.

######  Proposition 1.6.

Let $M$ be a subset of $\mathbb{F}_{2}^{t}$ and
$T\colon\mathbb{F}_{2}^{t}\to\mathbb{F}_{2}^{t}$ be an affine permutation.
Then

  1. (a)

$M$ is Sidon if and only if $T(M)$ is Sidon; and

  2. (b)

$M$ is maximal Sidon if and only if $T(M)$ is maximal Sidon.

###### Proof.

Let be $T=L+a$ where $L\colon\mathbb{F}_{2}^{t}\to\mathbb{F}_{2}^{t}$ is a a
linear permutation and $a\in\mathbb{F}_{2}^{t}$. From $T$ affine and bijective
follows $\left\lvert T(M)\right\rvert=\left\lvert M\right\rvert$,

$\displaystyle\left\lvert\mathcal{S}_{2}^{*}\bigl{(}T(M)\bigr{)}\right\rvert$
$\displaystyle=\left\lvert
L\bigl{(}\mathcal{S}_{2}^{*}(M)\bigr{)}\right\rvert=\left\lvert\mathcal{S}_{2}^{*}(M)\right\rvert=\binom{\left\lvert
M\right\rvert}{2},$
$\displaystyle\left\lvert\mathcal{S}_{3}^{*}\bigl{(}T(M)\bigr{)}\right\rvert$
$\displaystyle=\left\lvert
T\bigl{(}\mathcal{S}_{3}^{*}(M)\bigr{)}\right\rvert=\left\lvert\mathcal{S}_{3}^{*}(M)\right\rvert=\left\lvert\mathbb{F}_{2}^{t}\setminus
M\right\rvert,$

and therefore (a) and (b). ∎

We recall some basic properties of subsets of $\mathbb{F}_{2}^{t}$.

######  Lemma 1.7.

Let $M$ be a subset of $\mathbb{F}_{2}^{t}$ and let $e_{1},\dots,e_{t}$ be the
standard basis of $\mathbb{F}_{2}^{t}$.

  1. (a)

If $\dim\langle M\rangle=t$ and $\left\lvert M\right\rvert\geq t+1$, then
there exists an affine permutation
$T\colon\mathbb{F}_{2}^{t}\to\mathbb{F}_{2}^{t}$ such that

$\\{0,e_{1},\dots,e_{t}\\}\subseteq T(M).$

  2. (b)

If $\\{0,e_{1},\dots,e_{t}\\}\subseteq M$ and if there is an element $m$ of
$M$ with weight $w\geq 2$, then there exists a linear permutation
$L\colon\mathbb{F}_{2}^{t}\to\mathbb{F}_{2}^{t}$ such that

$\\{0,e_{1},\dots,e_{t},e_{1}+e_{2}+\dotsb+e_{w}\\}\subseteq L(M).$

Using Proposition 1.6 and Lemma 1.7 we are able to characterise all maximal
Sidon sets up to dimension 6.

######  Proposition 1.8.

Let $M$ be a maximal Sidon set of $\mathbb{F}_{2}^{t}$ and let
$e_{1},\dots,e_{t}$ be the standard basis of $\mathbb{F}_{2}^{t}$. Then there
exists an affine permutation $T\colon\mathbb{F}_{2}^{t}\to\mathbb{F}_{2}^{t}$
such that $T(M)$ equals to

  1. t=1:

$M_{1}=\\{0,e_{1}\\}=\mathbb{F}_{2}^{1}$ with $\left\lvert
M_{1}\right\rvert=2$.

  2. t=2:

$M_{2}=\\{0,e_{1},e_{2}\\}=\mathbb{F}_{2}^{2}\setminus\\{0\\}$ with
$\left\lvert M_{2}\right\rvert=3$.

  3. t=3:

$M_{3}=\\{0,e_{1},e_{2},e_{3}\\}$ with $\left\lvert M_{3}\right\rvert=4$.

  4. t=4:

$M_{4}=\\{0,e_{1},e_{2},e_{3},e_{4},e_{1}+e_{2}+e_{3}+e_{4}\\}$ with
$\left\lvert M_{4}\right\rvert=6$.

  5. t=5:

$M_{5}=\\{0,e_{1},e_{2},e_{3},e_{4},e_{5},e_{1}+e_{2}+e_{3}+e_{4}\\}$ with
$\left\lvert M_{5}\right\rvert=7.$

  6. t=6:

$M_{6a}=\\{0,e_{1},e_{2},e_{3},e_{4},e_{5},e_{6},e_{1}+e_{2}+e_{3}+e_{4},e_{1}+e_{2}+e_{5}+e_{6}\\}$
or
$M_{6b}\;=\;\\{0,e_{1},e_{2},e_{3},e_{4},e_{5},e_{6},e_{1}+e_{2}+e_{3}+e_{4}+e_{5}+e_{6}\\}$
with $\left\lvert M_{6a}\right\rvert=9>\left\lvert M_{6b}\right\rvert=8$.

###### Proof.

Let $M\subseteq\mathbb{F}_{2}^{t}$ be maximal Sidon, hence
$\mathcal{S}_{3}(M)=\mathbb{F}_{2}^{t}$. Because of Proposition 1.6 and Lemma
1.7 (a) we may assume without loss of generality that
$\\{0,e_{1},\dots,e_{t}\\}\subseteq M$ and therefore $M$ contains no elements
of weight 2 or 3. Hence $\mathbb{F}_{2}^{t}\setminus\mathcal{S}_{3}(M)$
consists of vectors of weight $\geq 4$ and the cases up to $t=4$ are shown. A
vase distinction of the maximal weight for vectors in $M$ leads, together with
Lemma 1.7 (b) and straight forward calculations, to the remaining cases:

  1. t=5:

$M_{5}=\\{0,e_{1},e_{2},e_{3},e_{4},e_{5},e_{1}+e_{2}+e_{3}+e_{4}\\}$ or
$M^{\prime}_{5}=\\{0,e_{1},e_{2},e_{3},e_{4},e_{5},e_{1}+e_{2}+e_{3}+e_{4}+e_{5}\\}$
with $\left\lvert M_{5}\right\rvert=\left\lvert M^{\prime}_{5}\right\rvert=7.$

  2. t=6:

$M_{6a1}=\\{0,e_{1},e_{2},e_{3},e_{4},e_{5},e_{6},e_{1}+e_{2}+e_{3}+e_{4},e_{i_{1}}+e_{i_{2}}+e_{5}+e_{6}\\}$,
$M_{6a2}=\\{0,e_{1},e_{2},e_{3},e_{4},e_{5},e_{6},e_{1}+e_{2}+e_{3}+e_{4}+e_{5},e_{j_{1}}+e_{j_{2}}+e_{j_{3}}+e_{6}\\}$
or
$M_{6b}=\\{0,e_{1},e_{2},e_{3},e_{4},e_{5},e_{6},e_{1}+e_{2}+e_{3}+e_{4}+e_{5}+e_{6}\\}$
with distinct $i_{1},i_{2}\in\\{1,2,3,4\\}$, pairwise distinct
$j_{1},j_{2},j_{3}\in\\{1,2,3,4,5\\}$
and $\left\lvert M_{6a1}\right\rvert=\left\lvert
M_{6a2}\right\rvert=9>\left\lvert M_{6c}\right\rvert=8$.

Now we show that some of the cases above can be transformed into each other
via affine transformations. The affine transformation $T_{5}=L_{5}+e_{5}$ on
$\mathbb{F}_{2}^{5}$ fulfils $T_{5}(M^{\prime}_{5})=M_{5}$ where the used
linear transformation $L_{5}\colon\mathbb{F}_{2}^{5}\to\mathbb{F}_{2}^{5}$ is
defined by:

$e_{1}\mapsto e_{1}+e_{5}\quad e_{2}\mapsto e_{2}+e_{5}\quad e_{3}\mapsto
e_{3}+e_{5}\quad e_{4}\mapsto e_{4}+e_{5}\quad e_{5}\mapsto e_{5}.$

Simple permutations of the standard basis result in affine transformations
$T_{61},T_{62}\colon\mathbb{F}_{2}^{6}\to\mathbb{F}_{2}^{6}$ such that

$\displaystyle T_{61}(M_{6a1})=M_{6a}$ and $\displaystyle
T_{62}(M_{6a2})=M^{\prime}_{6a}$
$\displaystyle=\\{0,e_{1},e_{2},e_{3},e_{4},e_{5},e_{6},e_{1}+e_{2}+e_{3}+e_{4}+e_{5},$
$\displaystyle\qquad e_{1}+e_{2}+e_{5}+e_{6}\\}.$

Extending the definition of $L_{5}$ by $e_{6}\mapsto e_{6}+e_{5}$ leads to a
linear transformation $L_{6}\colon\mathbb{F}_{2}^{6}\to\mathbb{F}_{2}^{6}$ and
results in an affine transformation $T_{6}=L_{6}+e_{5}$ on
$\mathbb{F}_{2}^{6}$ which fulfils $T_{6}(M^{\prime}_{6a})=M_{6a}$. ∎

For dimension 7 and 8 we were not able to classify all maximal Sidon sets, but
determined all possible sizes of maximal Sidon sets by computer calculations.

######  Proposition 1.9.

Let $M$ be a maximal Sidon set of $\mathbb{F}_{2}^{t}$. If $t=7$, then
$\left\lvert M\right\rvert=12$ and if $t=8$, then $\left\lvert
M\right\rvert\in\\{15,16,18\\}$.

Examples of maximal Sidon sets with the sizes from Proposition 1.9 can be
found in Table 1. We use the standard integer representation of vectors in
$\mathbb{F}_{2}^{t}$: the integer $\sum_{i=0}^{t-1}a_{i}2^{i}$ in 2-adic
representation “is” the vector $(a_{0},\ldots,a_{t-1})$.

$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 1:  Examples of maximal Sidon sets $M$ in $\mathbb{F}_{2}^{t}$ of all
possible sizes for dimension $t=7$ and $t=8$.

######  Remark 1.10.

Here are some details about the computer calculations used in Proposition 1.9:

  1. (a)

The algorithm is based on Proposition 1.3: if $M\subseteq\mathbb{F}_{2}^{t}$
is Sidon and $g\in\mathbb{F}_{2}^{t}\setminus\mathcal{S}_{3}(M)$, then
$M\mathbin{\mathaccent 0{\cdot}\cup}\\{g\\}$ is Sidon.

  2. (b)

Because of Proposition 1.6 and Lemma 1.7 (a) we may assume without loss of
generality that $0,e_{1},\dots,e_{t}$ is contained in any maximal Sidon set in
$\mathbb{F}_{2}^{t}$.

  3. (c)

For dimension 7, the assumption from (b) is sufficient to complete the
calculations after 12 seconds. As a result, we get 524160 maximal Sidon sets
of size 12 containing $0,e_{1},\dots,e_{7}$.

  4. (d)

For dimension 8, the assumption from (b) is still not sufficient to complete
the calculations. We divided the calculation into 5 subtasks with the help of
Lemma 1.7 (b): let $M$ be a maximal Sidon set containing
$0,e_{1},\dots,e_{t}$. Then the maximal weight of all elements of $M$ is
either 4,5,6,7 or 8 and we can assume without loss of generality, because of
the Sidon property, that

    1. (1)

for the maximal weight 4, $e_{1}+e_{2}+e_{3}+e_{4}$ is contained in $M$ and
the weight of all other elements is at most 4;

    2. (2)

for the maximal weight 5, $e_{1}+e_{2}+e_{3}+e_{4}+e_{5}$ is contained in $M$
and the weight of all other elements is at most 5;

    3. (3)

for the maximal weight 6, $e_{1}+e_{2}+\dotsb+e_{5}+e_{6}$ is contained in $M$
and the weight of all other elements is at most 6;

    4. (4)

for the maximal weight 7, $e_{1}+e_{2}+\dotsb+e_{6}+e_{7}$ is contained in $M$
and the weight of all other elements is at most 6;

    5. (5)

for the maximal weight 8, $e_{1}+e_{2}+\dotsb+e_{7}+e_{8}$ is contained in $M$
and the weight of all other elements is at most 5.

Task (5) was the most time-consuming and took about 14 days without
parallelisation.

We close this section with a result on the 4-sums of Sidon sets. As seen
before in Proposition 1.5, a maximal Sidon set can be characterised via its
3-sums, i.e. a Sidon set $M$ is maximal if and only if
$\mathcal{S}_{3}(M)=\mathbb{F}_{2}^{t}$. For sufficiently large Sidon sets we
obtain the following result about the 4-sums of Sidon sets. It is used later
in Proposition 3.3 in connection with linear codes to indicate the covering
radius of the code associated with a sum-free Sidon set.

######  Theorem 1.11.

Let $M$ be a Sidon set of $\mathbb{F}_{2}^{t}$. If $\left\lvert
M\right\rvert>s_{max}(\mathbb{F}_{2}^{t-1})$, then

  1. (a)

$\mathcal{S}_{4}(M)=\mathbb{F}_{2}^{t}$ and

  2. (b)

$\dim\langle M\rangle=\dim\langle\mathcal{S}_{2}^{*}(M)\rangle=t$.

###### Proof.

We only prove (a) as (b) is a direct consequence of it.

Assume that there exists an
$a\in\mathbb{F}_{2}^{t}\setminus\mathcal{S}_{4}(M)$. Let
$b\in\mathbb{F}_{2}^{t}\setminus a^{\perp}$ and
$f_{b}\colon\mathbb{F}_{2}^{t}\to\mathbb{F}_{2}$ be defined by $g\mapsto
b\cdot g$, where $\cdot$ denotes the standard inner product, and ⟂ denotes the
orthogonal space with respect to this inner product. We now consider the
mapping $T\colon\mathbb{F}_{2}^{t}\to\mathbb{F}_{2}^{t}$ defined by $g\mapsto
g+f_{b}(g)\cdot a$. From $b\cdot a=1$, it follows
$\mathbb{F}_{2}^{t}=b^{\perp}\mathbin{\mathaccent 0{\cdot}\cup}(a+b^{\perp})$
and $T(g)=\begin{cases}g&\text{ for }g\in b^{\perp},\\\ g+a&\text{ for
}g=a+b^{\perp},\end{cases}$ hence $T(\mathbb{F}_{2}^{t})\subseteq b^{\perp}$.
Assuming $T(m_{1})=T(m_{2})$ for distinct $m_{1},m_{2}\in M$ would lead to
$m_{1}+m_{2}=a$, but this contradicts
$a\notin\mathcal{S}_{4}(M)=\mathcal{S}_{4}^{*}(M)\cup\mathcal{S}_{2}(M)$.
Hence $\left\lvert T(M)\right\rvert=\left\lvert M\right\rvert$. Assuming
$T(m_{1})+T(m_{2})=T(m_{3})+T(m_{4})$ would lead because of the Sidon property
of $M$ to $m_{1}+m_{2}+m_{3}+m_{4}=a$ but this contradicts
$a\notin\mathcal{S}_{4}^{*}(M)$. Hence $T(M)$ is Sidon. But now we found a
Sidon set $T(M)\subseteq b^{\perp}$ with $\left\lvert
T(M)\right\rvert>s_{max}(\mathbb{F}_{2}^{t-1})$, a contradiction. ∎

Note that the opposite direction of Theorem 1.11 is, in general, not true. For
instance, $M=\\{0,e_{1},\dots,e_{t}\\}\subseteq\mathbb{F}_{2}^{t}$ is a Sidon
set with $\dim\langle M\rangle=\dim\langle\mathcal{S}_{2}^{*}(M)\rangle=t$ but
$\mathcal{S}_{4}(M)\subsetneq\mathbb{F}_{2}^{t}$ and $\left\lvert
M\right\rvert\leq s_{max}(\mathbb{F}_{2}^{t-1})$ for $t\geq 5$.

##  2 Sum-free sets

In this section we introduce sum-free sets, give some basic properties and
show that it is equivalent to discuss the maximum size of a sum-free Sidon set
instead of a Sidon set. Then, in the next section, we recall a one-to-one
correspondence between sum-free Sidon sets and linear codes with a minimum
distance greater than or equal to 5, which gives us the possibility to
translate the question about the maximum size of a Sidon set into a question
about linear codes with certain properties.

######  Definition 2.1.

Let $M$ be a subset of $\mathbb{F}_{2}^{t}$. $M$ is called sum-free if
$m_{1}+m_{2}\neq m_{3}$ for all $m_{1},m_{2},m_{3}\in M$.

By definition, $0$ is never contained in a sum-free set. We give some basic
properties: Let $M$ be a subset of $\mathbb{F}_{2}^{t}$.

  1. (a)

$M$ is sum-free if and only if $\mathcal{S}_{2}(M)\cap M=\emptyset$.

  2. (b)

If $M$ is sum-free, then $\left\lvert M\right\rvert\leq 2^{t-1}$.

  3. (c)

$M$ is sum-free and $\left\lvert M\right\rvert=2^{t-1}$ if and only if $M=H+a$
for a hyperplane $H$ of $\mathbb{F}_{2}^{t}$ (which is a linear subspace of
dimension $t-1$) and $a\in\mathbb{F}_{2}^{t}\setminus H$.

More on sum-free sets can be found in the survey papers of Green and Ruzsa [6]
as well as Tao and Vu [12].

The Sidon property and the maximal Sidon property are invariant under the
action of the affine group. This is not true, in general, for the property of
being sum-free. But being sum-free is still invariant under the action of the
general linear group:

######  Proposition 2.2.

Let $M$ be a subset of $\mathbb{F}_{2}^{t}$,
$L\colon\mathbb{F}_{2}^{t}\to\mathbb{F}_{2}^{t}$ be a linear permutation and
$a\in\mathbb{F}_{2}^{t}$. Then

  1. (a)

$M$ is sum-free if and only if $L(M)$ is sum-free.

  2. (b)

$M+a$ is sum-free if and only if
$a\in\mathbb{F}_{2}^{t}\setminus\mathcal{S}_{3}(M)=\mathbb{F}_{2}^{t}\setminus\bigl{(}\mathcal{S}_{3}^{*}(M)\cup
M\bigr{)}$.

###### Proof.

(a) follows directly from the definition of sum-free and from the linearity
and bijectivity of $L$. In order to show (b) we assume that $M+a$ is not sum-
free. Hence there exist $m_{1},m_{2},m_{3}\in M$ such that
$m_{1}+a+m_{2}+a=m_{3}+a$, thus $m_{1}+m_{2}+m_{3}=a$. But this is equivalent
to $a\in\mathcal{S}_{3}(M)=(\mathcal{S}_{3}^{*}(M)\cup M)$ and (b) is shown. ∎

The next Proposition is about extending sum-free sets and sum-free Sidon sets
by adding elements.

######  Proposition 2.3.

Let $M$ be a subset of $\mathbb{F}_{2}^{t}$ and
$g\in\mathbb{F}_{2}^{t}\setminus M$.

  1. (a)

Let $M$ be sum-free. Then $M\mathbin{\mathaccent 0{\cdot}\cup}\\{g\\}$ is sum-
free if and only if $g\in\mathbb{F}_{2}^{t}\setminus\mathcal{S}_{2}(M)$.

  2. (b)

Let $M$ be sum-free Sidon. Then $M\mathbin{\mathaccent 0{\cdot}\cup}\\{g\\}$
is sum-free Sidon if and only if
$g\in\mathbb{F}_{2}^{t}\setminus\big{(}\mathcal{S}_{3}(M)\cup\mathcal{S}_{2}(M)\big{)}$.

  3. (c)

Let $M$ be sum-free Sidon. Then $M\mathbin{\mathaccent 0{\cdot}\cup}\\{g\\}$
is Sidon and not sum-free if and only if
$g\in\mathcal{S}_{2}(M)\setminus\mathcal{S}_{3}(M)$.

###### Proof.

Let $M$ be sum-free and $g\in\mathbb{F}_{2}^{t}\setminus M$. We assume that
$M\mathbin{\mathaccent 0{\cdot}\cup}\\{g\\}$ is not sum-free. Hence there
exist $m_{1},m_{2}\in M\mathbin{\mathaccent 0{\cdot}\cup}\\{g\\}$ such that
$m_{1}+m_{2}=g$. But this is equivalent to either $g\in\mathcal{S}_{2}^{*}(M)$
or $g=0$, hence $g\in\mathcal{S}_{2}(M)=\mathcal{S}_{2}^{*}(M)\cup\\{0\\}$ and
(a) is shown. Cases (b) and (c) follow from (a) and Proposition 1.3. ∎

The case when 0 is contained in a Sidon set is of special interest.

######  Proposition 2.4.

Let $M$ be a subset of $\mathbb{F}_{2}^{t}$.

  1. (a)

If $M$ is sum-free Sidon, then $M\mathbin{\mathaccent 0{\cdot}\cup}\\{0\\}$ is
Sidon and not sum-free.

  2. (b)

If $M$ is Sidon and $0\in M$, then $M\setminus\\{0\\}$ is sum-free Sidon.

###### Proof.

(a) is a direct consequence of Proposition 2.3 (c) due to
$0\in\mathcal{S}_{2}(M)\setminus\mathcal{S}_{3}(M)$.

Now we consider (b). Since every subset of a Sidon set is Sidon, it remains to
show that $M\setminus\\{0\\}$ is sum-free. We assume that $M\setminus\\{0\\}$
is not sum-free. Hence, there exist $m_{1},m_{2},m_{3}\in M\setminus\\{0\\}$
such that $m_{1}+m_{2}=m_{3}$. Since $0\notin M\setminus\\{0\\}$ it follows
that $m_{1},m_{2},m_{3}$ are pairwise distinct. But then, we found
$m_{1},m_{2},m_{3},0\in M$ pairwise distinct such that $m_{1}+m_{2}=m_{3}+0$
which contradicts $M$ Sidon and (b) is shown. ∎

Therefore, the problem to find the maximum size of a sum-free Sidon set is
equivalent to find the maximum size of a Sidon set.

######  Proposition 2.5.

Let $\operatorname{\mathit{sfs}}_{max}(\mathbb{F}_{2}^{t})$ denote the maximum
size of a sum-free Sidon set in $\mathbb{F}_{2}^{t}$. Then

$s_{max}(\mathbb{F}_{2}^{t})=\operatorname{\mathit{sfs}}_{max}(\mathbb{F}_{2}^{t})+1.$

##  3 Linear Codes

A (binary) linear code $\mathcal{C}$ of length $n$ and dimension $k$ is a $k$
dimensional vector subspace $\mathcal{C}$ in $\mathbb{F}_{2}^{n}$. Such a code
$\mathcal{C}$ is called an $[n,k]$-code and $c\in\mathcal{C}$ is called a code
word of $\mathcal{C}$. We consider all vectors to be row vectors.

If the minimum distance of $\mathcal{C}$ is $d$, that is the minimum number of
non-zero entries of all non-zero code words of $\mathcal{C}$, then
$\mathcal{C}$ is called a $[n,k,d]$-code.

A parity check matrix of an $[n,k]$-code $\mathcal{C}$ is an $(n-k)\times n$
matrix $\mathcal{H}$ such that $\mathcal{C}$ equals to the kernel of
$\mathcal{H}$ i.e $\mathcal{C}=\\{v\in\mathbb{F}_{2}^{n}:\mathcal{H}\cdot
v^{\intercal}=0\\}$. We note that the rank of $\mathcal{H}$ is $n-k$.

The covering radius of an $[n,k]$-code $\mathcal{C}$ with parity check matrix
$\mathcal{H}$ is the smallest integer $R$ such that every binary column vector
with $n-k$ entries can be written as the sum of at most $R$ columns of
$\mathcal{H}$.

We recall a fruitful one-to-one correspondence between additive structures and
linear codes, see [4]. It translates additive properties of a subset $M$ of
$\mathbb{F}_{2}^{t}$ into properties of an associated code of length
$\left\lvert M\right\rvert$, such as minimum distance or covering radius, and
vice versa.

When formulating the correspondence we will see that we need an ordering for
the elements of $\mathbb{F}_{2}^{t}$. Therefore, for the rest of this section,
we assume, that $\mathbb{F}_{2}^{n}$ is endowed with an ordering, but all what
follows is independent of this ordering.

Additionally, our purpose is to read information about a given set $M$ from
its associated code. However, this is not possible if the associated code is
trivial, that is, of dimension $0$ or $\left\lvert M\right\rvert$. So we
formulate the correspondence in such a way that we never obtain a trivial
associated code from a given set $M$.

The one-to-one correspondence

$\displaystyle\left\\{\begin{array}[]{c}\text{$M\subseteq\mathbb{F}_{2}^{t}\setminus\\{0\\}$}\\\
\text{with $\left\lvert M\right\rvert\geq t+1$}\end{array}\right\\}$
$\displaystyle\longleftrightarrow\left\\{\begin{array}[]{c}\text{$[n,k,d]$-code
$\mathcal{C}$}\\\ \text{with $n-1\geq k\geq 1$ and $d\geq
3$}\end{array}\right\\}$ $\displaystyle M\quad$
$\displaystyle\,\longmapsto\quad\mathcal{C}_{M}$ $\displaystyle
M_{\mathcal{C}}\quad$
$\displaystyle\,\,\reflectbox{$\longmapsto$}\qquad\mathcal{C}$

is defined as follows:

Let $M$ be a subset of $\mathbb{F}_{2}^{t}\setminus\\{0\\}$ with $\left\lvert
M\right\rvert\geq t+1$. We define the associated matrix $\mathcal{M}_{M}$ of
$M$ as the $t\times\left\lvert M\right\rvert$ matrix, where the columns are
the vectors of $M$, i.e

$\mathcal{M}_{M}=(m^{\intercal})_{m\in M}$

and the associated code $\mathcal{C}_{M}$ of $M$ is the kernel of this matrix,
i.e

$\mathcal{C}_{M}=\\{v\in\mathbb{F}_{2}^{\left\lvert
M\right\rvert}:\mathcal{M}_{M}\cdot v^{\intercal}=0\\}.$

If the rank of $\mathcal{M}_{M}$ is $t$, then it is a parity check matrix of
the associated code $\mathcal{C}_{M}$.

The dimension of $\mathcal{C}_{M}$ is never $0$ because of $\left\lvert
M\right\rvert\geq t+1$, and never $\left\lvert M\right\rvert$ because $0\notin
M$.

Some basic properties of the associated codes are the following:

Let $M$ be a subset of $\mathbb{F}_{2}^{t}\setminus\\{0\\}$ with $\left\lvert
M\right\rvert\geq t+1$ and let $\mathcal{C}_{M}$ be its associated
$[\left\lvert M\right\rvert,k,d]$-code. Then

  1. (a)

$\left\lvert M\right\rvert>t\geq 2$;

  2. (b)

$\left\lvert M\right\rvert-1\geq k\geq\left\lvert M\right\rvert-t\geq 1$;

  3. (c)

$k=\left\lvert M\right\rvert-t$ if and only if $\dim\langle M\rangle=t$;

  4. (d)

$d\geq 3$, as no column is 0 and no column appears twice.

The columns of a parity check matrix of an $[n,k,d]$-code $\mathcal{C}$ with
$n-1\geq k\geq 1$ and $d\geq 3$ form a subset $M_{\mathcal{C}}$ of
$\mathbb{F}_{2}^{t}\setminus\\{0\\}$ with $t=n-k$ and $\left\lvert
M_{\mathcal{C}}\right\rvert=n\geq t+1=n-k+1$, which we call the associated set
of $\mathcal{C}$.

It should be noted that the associated set $M_{\mathcal{C}}$ of a code
$\mathcal{C}$ is not unique, just like the parity check matrix of a code is
not unique.

As an example of the one-to-one correspondence we give the following
proposition, with the proof appended for the convenience of the reader.

######  Proposition 3.1 (Proposition 2.1 of [4]).

Let $M$ be a subset of $\mathbb{F}_{2}^{t}\setminus\\{0\\}$ with $\left\lvert
M\right\rvert\geq t+1$ and let $\mathcal{C}_{M}$ be its associated
$[\left\lvert M\right\rvert,k,d]$-code. Then

  1. (a)

$M$ is sum-free if and only if $d\geq 4$;

  2. (b)

$M$ is sum-free Sidon if and only if $d\geq 5$.

###### Proof.

The minimum distance of an associated code is at least 3.

  1. (a)

$M$ is sum-free if and only if the equation

$m_{1}+m_{2}+m_{3}=0$

has no solution for pairwise distinct $m_{1},m_{2},m_{3}\in M$. This is
equivalent to: $\mathcal{C}_{M}$ has no code words of weight 3.

  2. (b)

$M$ is sum-free Sidon if and only if the system of equations

$\begin{cases}m_{1}+m_{2}+m_{3}=0\\\ m_{1}+m_{2}+m_{3}+m_{4}=0\\\ \end{cases}$

has no solution for pairwise distinct $m_{1},m_{2},m_{3},m_{4}\in M$. This is
equivalent to: $\mathcal{C}_{M}$ has no code words of weight 3 or 4.

∎

The following Theorem gives details on the one-to-one correspondence with a
focus on Sidon sets.

######  Theorem 3.2.

Let $M$ be a subset of $\mathbb{F}_{2}^{t}\setminus\\{0\\}$ with $\left\lvert
M\right\rvert\geq t+1$ and let $\mathcal{C}_{M}$ be its associated
$[\left\lvert M\right\rvert,k,d]$-code.

  1. (a)

If $M$ is sum-free and if $\left\lvert M\right\rvert\geq
s_{max}(\mathbb{F}_{2}^{t})$, then $d=4$ and $M$ is not Sidon.

  2. (b)

If $M$ is sum-free Sidon and if $\left\lvert M\right\rvert\geq
s_{max}(\mathbb{F}_{2}^{t-1})$, then $k=\left\lvert M\right\rvert-t$ and
$\mathcal{M}_{M}$ is a parity check matrix of $\mathcal{C}_{M}$.

  3. (c)

If $M$ is sum-free Sidon and if $\left\lvert M\right\rvert\geq
s_{max}(\mathbb{F}_{2}^{t-1})+1$, then $d=5$.

###### Proof.

  1. (a)

Let $M\subseteq\mathbb{F}_{2}^{t}\setminus\\{0\\}$ be sum-free. Then $d\geq 4$
from Proposition 3.1 (a). If $\left\lvert M\right\rvert\geq
s_{max}(\mathbb{F}_{2}^{t})$ then $\left\lvert M\mathbin{\mathaccent
0{\cdot}\cup}\\{0\\}\right\rvert>s_{max}(\mathbb{F}_{2}^{t})$ and therefore
neither $M\mathbin{\mathaccent 0{\cdot}\cup}\\{0\\}$ nor $M$ is Sidon, hence
$d=4$ due to Proposition 3.1 (b).

  2. (b)

If $M\subseteq\mathbb{F}_{2}^{t}\setminus\\{0\\}$ is sum-free Sidon and if
$\left\lvert M\right\rvert\geq s_{max}(\mathbb{F}_{2}^{t-1})$ then
$M\mathbin{\mathaccent 0{\cdot}\cup}\\{0\\}$ is still Sidon and $\left\lvert
M\mathbin{\mathaccent
0{\cdot}\cup}\\{0\\}\right\rvert>s_{max}(\mathbb{F}_{2}^{t-1})$. From Theorem
1.11 (b) follows $\dim\langle M\rangle=t$ and therefore $k=\left\lvert
M\right\rvert-t$.

  3. (c)

From $M$ sum-free Sidon follows that $d\geq 5$ and due to $\left\lvert
M\right\rvert\geq s_{max}(\mathbb{F}_{2}^{t-1})+1$ and (a), the matrix
$\mathcal{H}_{M}:=\mathcal{M}_{M}$ is a parity check matrix of
$\mathcal{C}_{M}$.

Assume that $d\geq 6$. Then $\mathcal{PU}(\mathcal{C}_{M})$, the puncturing of
$\mathcal{C}_{M}$ (remove one column and one row of $\mathcal{H}_{M}$), is an
$[\left\lvert M\right\rvert-1,\left\lvert M\right\rvert-t,d^{\prime}]$-code
with $d^{\prime}\geq 5$. Therefore the columns of the check matrix
$\mathcal{H}_{\mathcal{PU}(\mathcal{C}_{M})}$ of
$\mathcal{PU}(\mathcal{C}_{M})$ form a sum-free Sidon set
$M^{\prime}\subseteq\mathbb{F}_{2}^{t^{\prime}}$ with $\left\lvert
M^{\prime}\right\rvert=\left\lvert M\right\rvert-1$ and $t^{\prime}=t-1$. From
$\left\lvert M\right\rvert\geq s_{max}(\mathbb{F}_{2}^{t-1})+1$ follows that
$\left\lvert M^{\prime}\right\rvert=\left\lvert M\right\rvert-1\geq
s_{max}(\mathbb{F}_{2}^{t-1})$ and $M^{\prime}\subseteq\mathbb{F}_{2}^{t-1}$
not Sidon due to (a).

∎

Another interesting connection between a code property and a Sidon property is
the following:

######  Theorem 3.3.

Let $M$ be a subset of $\mathbb{F}_{2}^{t}\setminus\\{0\\}$ with $\left\lvert
M\right\rvert\geq t+1$ and let $\mathcal{C}_{M}$ be its associated
$[\left\lvert M\right\rvert,k,d]$-code with covering radius $R$.

  1. (a)

If $M$ is sum-free Sidon and $\left\lvert M\right\rvert\geq
s_{max}(\mathbb{F}_{2}^{t-1})$, then $R=3$ or $R=4$.

  2. (b)

$M$ is maximal sum-free Sidon (that means we cannot extend it to a larger sum-
free Sidon set by adding elements) if and only if $R=3$.

###### Proof.

  1. (a)

$M$ is Sidon and therefore
$\left\lvert\mathcal{S}_{2}^{*}(M)\right\rvert=\binom{\left\lvert
M\right\rvert}{2}$. From $\left\lvert M\right\rvert\geq t+1$ follows that
$\left\lvert M\right\rvert>t\geq 2$. But then
$\left\lvert\mathcal{S}_{2}^{*}(M)\right\rvert=\binom{\left\lvert
M\right\rvert}{2}<2^{t}$ and $R\geq 3$. From Theorem 1.11 (a) follows $R\leq
4$.

  2. (b)

This is a direct consequence of Proposition 1.5.

∎

We close this section by discussing the best possible minimum distance of a
code with given length $n$ and dimension $k$. Therefore we define

$d_{max}(n,k)=\max\\{d:\text{there exists an $[n,k,d]$-code}\\}.$

as the maximal minimum distance of a code with given length $n$ and dimension
$k$. It is one of the main properties of optimal codes and frequently listed
as a matrix $(d_{max}(n,k))_{n,k}$, for example in Grassl’s codes table [5]
(http://codetables.de) or the codes table of the MinT project from Schürer and
Schmid [8] (http://mint.sbg.ac.at/). Now we translate Theorem 3.2 to some
properties of the subdiagonals of $(d_{max}(n,k))_{n,k}$, namely the entries
$(d_{max}(n,n-t))_{n}$ for a fixed $t$.

######  Proposition 3.4.

Let be $n,t\in\mathbb{N}$ with $n>t\geq 2$. Then

  1. (a)

$d_{max}(n,n-t)=3$ if and only if $2^{t-1}<n<2^{t}$;

  2. (b)

$d_{max}(n,n-t)=4$ if and only if $s_{max}(\mathbb{F}_{2}^{t})\leq n\leq
2^{t-1}$;

  3. (c)

$d_{max}(n,n-t)=5$ if and only if
$s_{max}(\mathbb{F}_{2}^{t-1})<n<s_{max}(\mathbb{F}_{2}^{t})$;

  4. (d)

$d_{max}(n,n-t)\geq 6$ if and only if $n\leq s_{max}(\mathbb{F}_{2}^{t-1})$.

###### Proof.

From our correspondence it follows that every
$M\subseteq\mathbb{F}_{2}^{t}\setminus\\{0\\}$ with $\left\lvert
M\right\rvert\geq t+1$ gives rise to an associated $[\left\lvert
M\right\rvert,k,d]$-code with $d\geq 3$.

  1. (a)

If $\left\lvert M\right\rvert>2^{t-1}$, then $\dim\langle M\rangle=t$ and
$k=\left\lvert M\right\rvert-d$, but $M$ cannot be sum-free anymore. Thus
$d=3$ and (a) is shown.

  2. (b)

Let $M=H+a$ with a hyperplane $H$ of $\mathbb{F}_{2}^{t}$ (which is a linear
subspace of dimension $t-1$) and $a\in\mathbb{F}_{2}^{t}\setminus H$. Hence
$M$ is sum-free and $d=4$ from Theorem 3.2 (a). Additionally, $\dim\langle
M\rangle=t$ and $k=\left\lvert M\right\rvert-d$. Now, removing elements from
$M$ such that $\dim\langle M\rangle=t$ is still valid, leads, together with
Theorem 3.2 (a), to (b).

  3. (c)

This is a direct consequence of Theorem 3.2 (b) and (c).

  4. (d)

This follows from (a), (b) and (c).

∎

##  4 Non-existence results

Due to the importance of non-existence statements for Sidon sets and as well
for linear codes we reformulate Proposition 3.4.

######  Corollary 4.1.

Let be $n,t\in\mathbb{N}$ with $n>t\geq 2$. Then the following statements are
equivalent:

  1. (a)

There is no $[n,n-t,5]$ code.

  2. (b)

There is no Sidon set $M\subseteq\mathbb{F}_{2}^{t}$ of size $n+1$.

  3. (c)

$s_{max}(\mathbb{F}_{2}^{t})\leq n$.

The following result from Brouwer and Tolhuizen [2] is achieved by a
sharpening of the Johnson bound. It improves the trivial upper bound (1) for
odd dimension.

######  Theorem 4.2 ([2]).

There is no $\left[n,n-t,5\right]$ code for $n=2^{(t+1)/2}-2$, hence

$s_{max}(\mathbb{F}_{2}^{t})\leq 2^{(t+1)/2}-2$

for $t$ odd with $t\geq 7$.

With arguments similar to those used by Brouwer and Tolhuizen, we are able to
generalise this result to arbitrary $t\geq 6$ and thereby further improve the
trivial upper bound (1). This improves also a recent bound given by Tait and
Won (Theorem 5.1 of [11]).

######  Theorem 4.3.

Let $t\geq 6$, and write $\left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor-4=3a+b$
with $a\in\mathbb{Z}_{\geq 0}$, $b\in\\{0,1,2\\}$,
$\varepsilon={\sqrt{2^{t+1}}+0.5}-\left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor\in[0,1)$
and

$\lambda_{a,b,\varepsilon}=\begin{cases}1&\text{ for $a$ odd and $b=0$},\\\
2&\text{ for $a$ odd, $b=1$ and $0\leq\varepsilon\leq
1-\frac{1}{2^{(t-4)/2}}$},\\\ 1&\text{ for $a$ odd, $b=1$ and
$1-\frac{1}{2^{(t-4)/2}}<\varepsilon<1$},\\\ 2&\text{ for $a$ odd and
$b=2$},\\\ 2&\text{ for $a$ even, $b=0$ and $0\leq\varepsilon\leq 0.5$},\\\
1&\text{ for $a$ even, $b=0$ and $0.5<\varepsilon<1$},\\\ 2&\text{ for $a$
even, $b=1$ and $0\leq\varepsilon\leq 1-\frac{1}{2^{(t-5)/2}}$},\\\ 1&\text{
for $a$ even, $b=1$ and $1-\frac{1}{2^{(t-5)/2}}<\varepsilon\leq
1-\frac{1}{2^{(t+7)/2}}$},\\\ 0&\text{ for $a$ even, $b=1$ and
$1-\frac{1}{2^{(t+7)/2}}<\varepsilon<1$},\\\ 0&\text{ for $a$ even and
$b=2$}.\end{cases}$

Then there is no $\left[n_{t},n_{t}-t,5\right]$ code for
$n_{t}=\left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor-\lambda_{a,b,\varepsilon}$
and therefore

$s_{max}(\mathbb{F}_{2}^{t})\leq\begin{cases}2^{\frac{t+1}{2}}-2&\text{ for
$t$ odd},\\\
\left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor-\lambda_{a,b,\varepsilon}&\text{
for $t$ even}.\end{cases}$ (2)

###### Proof.

Because of Corollary 4.1 it is sufficient to show the non-existence of an
$\left[n_{t},n_{t}-t,5\right]$ code.

Let us recall some arguments from the proof of Theorem 4.2 in [2]. Let $C$ be
an arbitrary (linear or non-linear) code of length $n$, with minimum distance
$5$, and where, on the average, each codeword is at distance 5 from $a_{5}$
other codewords. The Johnson upper bound (Theorem 1 of [7]) states

$\left\lvert C\right\rvert\leq\frac{2^{n}}{s}$ (3)

for

$s=1+n+\frac{n(n-1)}{2}+\frac{1}{\left\lfloor
n/3\right\rfloor}\Bigl{(}\binom{n}{3}-10\cdot a_{5}\Bigr{)}$

and the term $10\cdot a_{5}$ can be estimated by

$10\cdot a_{5}\leq\left\lfloor\frac{n-2}{3}\right\rfloor\cdot\binom{n}{2}.$

Brouwer and Tolhuizen sharpened the estimate of $10\cdot a_{5}$ for linear
codes in the following way. Let $C$ be additionally linear and let $n-2=3\cdot
a+b$ with $a\in\mathbb{Z}_{\geq 0}$, $b\in\\{0,1,2\\}$, then

$10\cdot a_{5}\leq\begin{cases}a\cdot\binom{n}{2}&\text{ for $a$ odd and
$b=0$,}\\\ (a-1)\cdot\binom{n}{2}&\text{ for $a$ odd and $b\in\\{1,2\\}$,}\\\
(a-1)\cdot\binom{n}{2}+\frac{\binom{n}{b}\cdot\binom{b+2}{2}}{\binom{b+2}{b}}&\text{
for $a$ even.}\end{cases}$ (4)

Our purpose is to show that if $C$ is an $\left[n_{t},n_{t}-t,5\right]$ code,
then $2s>2^{t+1}$ or equivalently $s>2^{t}$. But this contradicts $s\leq
2^{t}$ which follows from (3).

Let us therefore distinguish 6 cases depending on wether $a$ is odd or even
and wether $b$ equals 2, 1 or 0.
Case $a$ odd: If $\mathbf{b=2}$, then $a-1=\frac{n-7}{3}$. From (4) follows

$10\cdot a_{5}\leq(a-1)\cdot\binom{n}{2}=\frac{n(n-1)(n-7)}{6}$

and therefore

$s\geq 1+n+\frac{n(n-1)}{2}+\frac{5}{2}n$

which is equivalent to

$2s\geq(n+3)^{2}-7.$ (5)

Now we set $\lambda_{a,b,\varepsilon}=2$,
$n=n_{t}=\left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor-2=\sqrt{2^{t+1}}-\frac{3}{2}-\varepsilon$
with $\varepsilon\in[0,1)$ and $k=n-t$. Hence

$\displaystyle 2s\geq(n_{t}+3)^{2}-7$
$\displaystyle=(\sqrt{2^{t+1}}+\frac{1}{2}+1-\varepsilon)^{2}-7$
$\displaystyle>2^{t+1}+\sqrt{2^{t+1}}+\frac{1}{4}-7$ $\displaystyle>2^{t+1}$

when $t\geq 5$, and this contradicts (3).

If $\mathbf{b=1}$, then $a-1=\frac{n-6}{3}$. From (4) follows

$10\cdot a_{5}\leq(a-1)\cdot\binom{n}{2}=\frac{n(n-1)(n-6)}{6}$

and therefore

$s\geq 1+n+\frac{n(n-1)}{2}+2(n-1)$

which is equivalent to

$2s\geq(n+\frac{5}{2})^{2}-\frac{33}{4}.$ (6)

Now we set $\lambda_{a,b,\varepsilon}=2$,
$n=n_{t}=\left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor-2=\sqrt{2^{t+1}}-\frac{3}{2}-\varepsilon$
with $\varepsilon\in[0,1)$, $k=n-t+1$ and want to show that

$2s\geq(\sqrt{2^{t+1}}+1-\varepsilon)^{2}-\frac{33}{4}>2^{t+1}.$

This is true if $0\leq\varepsilon\leq 1-\frac{1}{2^{(t-4)/2}}$ and $t\geq 5$
because setting $\varepsilon=1-\frac{1}{2^{(t-4)/2}}$ leads to

$\displaystyle 2s\geq(\sqrt{2^{t+1}}+\frac{1}{2^{(t-4)/2}})^{2}-\frac{33}{4}$
$\displaystyle=2^{t+1}+\frac{2\sqrt{2^{t+1}}}{2^{(t-4)/2}}+\frac{1}{2^{t-4}}-\frac{33}{4}$
$\displaystyle=2^{t+1}+8\sqrt{2}+\frac{1}{2^{t-4}}-2\frac{33}{4}$
$\displaystyle>2^{t+1}$

which contradicts (3). If $1-\frac{1}{2^{(t-4)/2}}<\varepsilon<1$ we set
$\lambda_{a,b,\varepsilon}=1$,
$n=n_{t}=\left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor-1$, $k=n-t$ and are now
in the case $a$ odd and $b=2$. Putting these values into (5) leads to

$2s\geq(n_{t}+3)^{2}-7>2^{t+1}$

which contradicts (3).

If $\mathbf{b=0}$, then $a=\frac{n-2}{3}$. From (4) follows

$10\cdot a_{5}\leq a\cdot\binom{n}{2}=\frac{n(n-1)(n-2)}{6}$

and therefore

$s\geq 1+n+\frac{n(n-1)}{2}$

which is equivalent to

$2s\geq(n+\frac{1}{2})^{2}+\frac{7}{4}.$ (7)

But setting $\lambda_{a,b,\varepsilon}=2$,
$n=\left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor-2$ and $k=n-t$ does not
contradict (3). Therefore we set $\lambda_{a,b,\varepsilon}=1$,
$n=n_{t}=\left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor-1$, $k=n_{t}-t$ and are
now in the case $a$ odd and $b=1$. Putting these values into (6) leads to

$2s\geq(n_{t}+\frac{5}{2})^{2}-\frac{33}{4}>2^{t+1}$

for $t\geq 3$ which contradicts (3).

Case $a$ even: If $\mathbf{b=2}$, then $a=\frac{n-4}{3}$. From (4) follows

$10\cdot a_{5}\leq\frac{n(n-1)(n-4)}{6}$

and therefore

$\displaystyle s$ $\displaystyle\geq
1+n+\frac{n(n-1)}{2}+\frac{3}{n-1}\left(\binom{n}{3}-\frac{n(n-1)(n-4)}{6}\right)$
$\displaystyle=1+n+\frac{n(n-1)}{2}+n$

which is equivalent to

$2s\geq(n+\frac{3}{2})^{2}-\frac{1}{4}.$ (8)

But setting $\lambda_{a,b,\varepsilon}=2$,
$n=\left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor-2$ and $k=n-t$ does not
contradict (3). Therefore we set $\lambda_{a,b,\varepsilon}=1$,
$n=n_{t}=\left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor-1$, $k=n_{t}-t$ and are
now in the case $a$ odd and $b=0$. But again, putting these values into (7)
does not contradict (3). Hence we set $\lambda_{a,b,\varepsilon}=0$,
$n=n_{t}=\left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor$, $k=n-t$ and are now in
the case $a$ odd and $b=1$. Now, putting these values into (6) contradicts
(3).

If $\mathbf{b=1}$, then $a=\frac{n-3}{3}=\frac{n}{3}-1$. From (4) follows

$10\cdot a_{5}\leq\frac{n(n-1)(n-6)}{6}+n=\frac{n(n-3)(n-4)}{6}$

and therefore

$\displaystyle s$ $\displaystyle\geq
1+n+\frac{n(n-1)}{2}+\frac{3}{n}\left(\binom{n}{3}-\frac{n(n-3)(n-4)}{6}\right)$
$\displaystyle=1+n+\frac{n(n-1)}{2}+2n-5$

which is equivalent to

$2s\geq(n+\frac{5}{2})^{2}-\frac{57}{4}.$ (9)

Now we set $\lambda_{a,b,\varepsilon}=2$,
$n=n_{t}=\left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor-2=\sqrt{2^{t+1}}+-\frac{3}{2}-\varepsilon$
with $\varepsilon\in[0,1)$, $k=n-t$ and want to show that

$2s\geq(\sqrt{2^{t+1}}+1-\varepsilon)^{2}-\frac{57}{4}>2^{t+1}.$

This is true if $0\leq\varepsilon\leq 1-\frac{1}{2^{(t-5)/2}}$ and $t\geq 6$
because setting $\varepsilon=1-\frac{1}{2^{(t-5)/2}}$ leads to

$\displaystyle 2s\geq(n_{t}+\frac{5}{2})^{2}-\frac{57}{4}$
$\displaystyle=(\sqrt{2^{t+1}}+\frac{1}{2^{(t-5)/2}})^{2}-\frac{57}{4}$
$\displaystyle=2^{t+1}+\frac{2\sqrt{2^{t+1}}}{2^{(t-5)/2}}+\frac{1}{2^{t-5}}-\frac{57}{4}$
$\displaystyle=2^{t+1}+16+\frac{1}{2^{t-5}}-\frac{57}{4}$
$\displaystyle>2^{t+1}$

which contradicts (3). If $1-\frac{1}{2^{(t-5)/2}}<\varepsilon<1$ we try
setting $\lambda_{a,b,\varepsilon}=1$,
$n=n_{t}=\left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor-1$, $k=n-t$ and are now
in the case $a$ even and $b=2$. Putting these values into (8) we want to show
that

$2s\geq(n_{t}+\frac{3}{2})^{2}-\frac{1}{4}>2^{t+1}.$

This is true if $\varepsilon\leq 1-\frac{1}{2^{(t+7)/2}}$ because setting
$\varepsilon=1-\frac{1}{2^{(t+7)/2}}$ leads to

$\displaystyle 2s\geq(n_{t}+\frac{3}{2})^{2}-\frac{1}{4}$
$\displaystyle=(\sqrt{2^{t+1}}+\frac{1}{2^{(t+7)/2}})^{2}-\frac{1}{4}$
$\displaystyle=2^{t+1}+\frac{2\sqrt{2^{t+1}}}{2^{(t+7)/2}}+\frac{1}{2^{t+7}}-\frac{1}{4}$
$\displaystyle=2^{t+1}+\frac{1}{4}+\frac{1}{2^{t+7}}-\frac{1}{4}$
$\displaystyle>2^{t+1}$

which contradicts (3). Therefore we set $\lambda_{a,b,\varepsilon}=0$,
$n=n_{t}=\left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor$, $k=n-t$ if
$1-\frac{1}{2^{(t+7)/2}}<\varepsilon<1$ and are now in the case $a$ odd and
$b=0$. Putting these values into (7) contradicts (3).

If $\mathbf{b=0}$, then $a=\frac{n-2}{3}$. From (4) follows

$10\cdot a_{5}\leq\frac{n(n-1)(n-5)}{6}+1$

and therefore

$\displaystyle s$ $\displaystyle\geq
1+n+\frac{n(n-1)}{2}+\frac{3}{n-2}\left(\binom{n}{3}-\frac{n(n-1)(n-5)}{6}-1\right)$
$\displaystyle=1+n+\frac{n(n-1)}{2}+\frac{3n+3}{2}$

which is equivalent to

$2s\geq(n+2)^{2}+1.$

But setting $\lambda_{a,b,\varepsilon}=2$,
$n=n_{t}=\left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor-2$ and $k=n-t$ only
contradicts (3) if $0\leq\varepsilon\leq\frac{1}{2}$. If
$\frac{1}{2}<\varepsilon<1$ we set
$n=n_{t}=\left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor-1$, $k=n_{t}-t$ and are
now in the case $a$ even and $b=1$. Putting these values into (9) leads to

$2s\geq(n_{t}+\frac{5}{2})^{2}-\frac{57}{4}>2^{t+1}$

for $t\geq 5$ which contradicts (3). ∎

On the codes side, Theorem 4.3 improves for $t$ even and $t\geq 16$ several
entries in the codes table of the MinT project [8] (http://mint.sbg.ac.at/).
Some examples are listed in Corollary 4.4. In [8], the maximal minimum
distance was listed as 4 or 5, but now we know that it is 4:

######  Corollary 4.4.

The maximal minimum distance of a linear code with the following parameters
$[n,k]$ is 4:

$[360,344]$ | $[723,705]$ | $[1446,1426]$
---|---|---
$[2895,2873]$ |  $[5791,5767]$, $[5792,5768]$ | $[11583,11557]$

###### Proof.

For $t\in\\{16,18,20,22,24,26\\}$ we follow Theorem 4.3, calculate $a,b$ and
$\varepsilon$, and obtain $\lambda_{a,b,\varepsilon}$, n and k as in the
following table:

$t$ | $\left\lfloor\sqrt{2^{t+1}}+0.5\right\rfloor$ | $a$ | $b$ | $\varepsilon$ | $\lambda_{a,b,\varepsilon}$ | $[n,k]$
---|---|---|---|---|---|---
16 | 362 | 119 | 1 | $\approx 0.538<0.984$ | 2 | $[360,344]$
18 | 724 | 240 | 0 | $\approx 0.577>0.500$ | 1 | $[723,705]$
20 | 1448 | 481 | 1 | $\approx 0.654<0.996$ | 2 | $[1446,1426]$
22 | 2896 | 964 | 0 | $\approx 0.809>0.500$ | 1 | $[2895,2873]$
24 | 5793 | 1929 | 2 | $\approx 0.118<0.999$ | 2 |  $[5791,5767]$ and
|  |  |  |  |  | $[5792,5768]$
26 | 11585 | 3860 | 1 | $\approx 0.737<0.999$ | 2 | $[11583,11557]$

∎

##  5 Conclusion

We finish by giving Table 2 about the maximum size of Sidon sets and related
bounds/constructions in small dimensions. The codes bound mentioned in this
table arises from Proposition 3.4 (b) and Grassl’s codes table [5]
(http://codetables.de). Similarly, the codes constructions come from
Proposition 3.4 (c) and Grassl’s codes table.

For example, take column $t=12$ from Table 2: The calculation of the trivial
bound (1) leads to $s_{max}(\mathbb{F}_{2}^{t})\leq 91$ and that of the new
bound (2) from Theorem 4.3 leads to $s_{max}(\mathbb{F}_{2}^{t})\leq 90$
($a=29$, $b=0$, $\varepsilon\approx 0.009$ and $\lambda_{a,b,\varepsilon}=1$).

Proposition 3.4 (b) gives us the codes bound, that is the smallest $n$, such
that $d_{max}(n,n-12)=4$. A look at Grassl’s codes table leads to
$s_{max}(\mathbb{F}_{2}^{t})\leq n=89$, since $d_{max}(89,77)=4$ but
$d_{max}(88,76)=4\mbox{\ or }5$.

The codes construction uses Proposition 3.4 (c) in the following way: Finding
the largest $n$ such that $d_{max}(n,n-12)\geq 5$ gives a sum-free Sidon set,
and adding 0 leads to $n+1$, which is the size of the largest known Sidon set.
Again, Grassl’s codes table leads to $n=65$ and so
$s_{max}(\mathbb{F}_{2}^{t})\geq 66$, since $d_{max}(65,53)=5$ but
$d_{max}(66,54)=4\mbox{\ or }5$.

$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
Table 2:  Maximal size of a Sidon set in $\mathbb{F}_{2}^{t}$ and related
bounds/constructions.

## References

  * [1] László Babai and Vera T Sós  “Sidon sets in groups and induced subgraphs of Cayley graphs”  In _European Journal of Combinatorics_ 6.2 Elsevier, 1985, pp. 101–114
  * [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”  In _Designs, Codes and Cryptography_ 3.2, 1993, pp. 95–98
  * [3] Claude Carlet and Sihem Mesnager  “On those multiplicative subgroups of $\mathbb{F}_{2^{n}}^{*}$ which are Sidon sets and/or sum-free sets”  In _Journal of Algebraic Combinatorics_ Springer, 2020, pp. 1–17
  * [4] Gilles Cohen and Gérard Zémor  “Subset sums and coding theory”  In _Structure theory of set addition_ , Astérisque 258  Société mathématique de France, 1999  URL: http://www.numdam.org/item/AST_1999__258__327_0/
  * [5] Markus Grassl  “Bounds on the minimum distance of linear codes and quantum codes” Accessed on 2023-04-07, Online available at http://www.codetables.de, 2007
  * [6] Ben Green and Imre Z Ruzsa  “Sum-free sets in abelian groups”  In _Israel Journal of Mathematics_ 147.1, 2005, pp. 157–188
  * [7] S. Johnson  “A new upper bound for error-correcting codes”  In _IRE Transactions on Information Theory_ 8.3, 1962, pp. 203–207  DOI: 10.1109/TIT.1962.1057714
  * [8] Rudolf Schürer and Wolfgang Ch Schmid  “MinT: A database for optimal net parameters”  In _Monte Carlo and Quasi-Monte Carlo Methods 2004_ Springer, 2006, pp. 457–469
  * [9] Simon Sidon  “Ein Satz über trigonometrische Polynome und seine Anwendung in der Theorie der Fourier-Reihen”  In _Mathematische Annalen_ 106.1, 1932, pp. 536–539
  * [10] Simon Sidon  “Über die Fourier Konstanten der Funktionen der Klasse $L_{p}$ für $p>1$”  In _Acta Univ. Szeged Sect. Sci. Math_ 7, 1935, pp. 175–176
  * [11] Michael Tait and Robert Won  “Improved Bounds on Sizes of Generalized Caps in $AG(n,q)$”  In _SIAM Journal on Discrete Mathematics_ 35.1, 2021, pp. 521–531  DOI: 10.1137/20M1369439
  * [12] Terence Tao and Van Vu  “Sum-free sets in groups: a survey”  In _Journal of Combinatorics_ 8.3 International Press of Boston, 2017, pp. 541–552  DOI: 10.4310/JOC.2017.v8.n3.a7