2000 Mathematics Subject Classification. 11B34,11B75,05B35,05A17,05B40. M.B.N. is supported in part by grants from the NSA Mathematical Sciences Program and the PSC-CUNY Research Award Program.
<ph f="cmbx">Maximal Sidon sets and matroids</ph>

### Melvyn B. Nathanson

Departamento de Matematica, Faculdade de Ciencias, Universidade de Lisboa, Campo Grande, Bloco C6, 1749-016 Lisboa, Portugal E-mail address : perdigao@hermite.cii.fc.ul.pt Department of Mathematics, Lehman College (CUNY), Bronx, New York 10468, USA E-mail address : melvyn.nathanson@lehman.cuny.edu
• Abstract. Let $X$  be a subset of an abelian group and ${a}_{1},\dots ,{a}_{h},{a}_{1}^{\prime },\dots ,{a}_{h}^{\prime }$  a sequence of $2h$  elements of $X$  such that ${a}_{1}+\cdots +{a}_{h}={a}_{1}^{\prime }+\cdots +{a}_{h}^{\prime }$  . The set $X$  is a Sidon set of order $h$  if, after renumbering, ${a}_{i}={a}_{i}^{\prime }$  for $i=1,\dots ,h.$  For $k\le h,$  the set $X$  is a generalized Sidon set of order $\left(h,k\right)$  , if, after renumbering, ${a}_{i}={a}_{i}^{\prime }$  for $i=1,\dots ,k.$  It is proved that if $X$  is a generalized Sidon set of order $\left(2h-1,h-1\right),$  then the maximal Sidon sets of order $h$  contained in $X$  have the same cardinality. Moreover, $X$  is a matroid where the independent subsets of $X$  are the Sidon sets of order $h$  .

1 An extremal problem for Sidon sets

Let $A$  be a subset of an abelian group $\Gamma$  . Two $h$  -tuples $\left({a}_{1},\dots ,{a}_{h}\right)$  and $\left({a}_{1}^{\prime },\dots ,{a}_{h}^{\prime }\right)$  of elements of $A$  are called equivalent, denoted $\left({a}_{1},\dots ,{a}_{h}\right)\sim \left({a}_{1}^{\prime },\dots ,{a}_{h}^{\prime }\right),$  if there is a permutation $\sigma$  of the set $\left\{1,\dots ,h\right\}$  such that ${a}_{i}^{\prime }={a}_{\sigma \left(i\right)}$  for $i=1,\dots ,h.$  If the $h$  -tuples $\left({a}_{1},\dots ,{a}_{h}\right)$  and $\left({a}_{1}^{\prime },\dots ,{a}_{h}^{\prime }\right)$  are equivalent, then ${a}_{1}+\cdots +{a}_{h}={a}_{1}^{\prime }+\cdots +{a}_{h}^{\prime }$  . We write $\left({a}_{1},\dots ,{a}_{h}\right)\nsim \left({a}_{1}^{\prime },\dots ,{a}_{h}^{\prime }\right)$  if the $h$  -tuples $\left({a}_{1},\dots ,{a}_{h}\right)$  and $\left({a}_{1}^{\prime },\dots ,{a}_{h}^{\prime }\right)$  are not equivalent.
The $h$  -fold sumset of $A$  , denoted $hA$  , is the set of all elements of $\Gamma$  that can be written as the sum of $h$  elements of $A$  , with repetitions allowed. For every $x\in \Gamma ,$  the representation function ${r}_{A,h}\left(x\right)$  counts the number of inequivalent representations of $x$  as a sum of $h$  elements of $A$  , that is, the number of equivalence classes of $h$  -tuples $\left({a}_{1},\dots ,{a}_{h}\right)$  such that $x={a}_{1}+\cdots +{a}_{h}.$  The set $A$  is called a Sidon set of order $h$  or a ${B}_{h}$  -set if every element of the sumset $hA$  has a unique representation as the sum of $h$  elements of $A$  , that is, if ${r}_{A,h}\left(x\right)=1$  for all $x\in hA$  . This means that if ${a}_{1},\dots ,{a}_{h},{a}_{1}^{\prime },\dots ,{a}_{h}^{\prime }\in A$  and ${a}_{1}+\cdots +{a}_{h}={a}_{1}^{\prime }+\cdots +{a}_{h}^{\prime },$  then $\left({a}_{1},\dots ,{a}_{h}\right)\sim \left({a}_{1}^{\prime },\dots ,{a}_{h}^{\prime }\right).$  A Sidon set is a Sidon set of order 2.
Let $X$  be a subset of the group $\Gamma ,$  and denote by ${\mathcal{ℬ}}_{h}\left(X\right)$  the set of all finite ${B}_{h}$  -sets contained in $X$  . Every set is a ${B}_{1}$  -set, and ${\mathcal{ℬ}}_{h}\left(X\right)\subseteq {\mathcal{ℬ}}_{h-1}\left(X\right)\subseteq \cdots \subseteq {\mathcal{ℬ}}_{2}\left(X\right)\subseteq {\mathcal{ℬ}}_{1}\left(X\right).$  Moreover, $\left\{a\right\}\in {B}_{h}\left(X\right)\text{for all}a\in X\text{and}h\ge 1.\text{}$  If $A$  is a Sidon subset of order $h$  contained in the group $\Gamma ,$  then for every $x\in \Gamma$  the translation $x+A=\left\{x+a:a\in A\right\}$  and the reflection $x-A=\left\{x-a:a\in A\right\}$  are also Sidon sets of order $h$  .
A classical problem in combinatorial and additive number theory is to determine the cardinality of the largest Sidon set of order $h$  contained in the interval of integers $\left\{1,2,\dots ,n\right\}.$  More generally, if $X$  is a finite subset of the integers or of any abelian group $\Gamma$  , it is an open problem to estimate the maximum cardinality of a Sidon set of order $h$  contained in $X$  . Every ${B}_{h}$  -subset of a finite set $X$  is contained in a maximal ${B}_{h}$  -set, but there can be maximal Sidon sets of different cardinalities contained in $X$  . For example, in the interval $\left\{1,2,3,4,5,6,7\right\}$  , the sets $\left\{1,3,6,7\right\}$  and $\left\{1,2,5,7\right\}$  are the two maximal Sidon subsets of size 4, but there are also exactly 18 maximal Sidon subsets of size 3, for example, $\left\{1,3,4\right\}.$  Erdős and Turán [3proved that the maximum size of a Sidon set of order 2 contained in $\left\{1,2,\dots ,n\right\}$  is ${n}^{1/2}+o\left({n}^{1/2}\right).$  Ruzsa [6has constructed maximal Sidon subsets of this interval of cardinality $\ll \left(nlogn{\right)}^{1/3}.$  (See Martin and O'Bryant [4for constructions of finite Sidon sets of integers and O'Bryant [5for a survey of the recent literature.) The purpose of this paper is to describe a class of finite sets, called ${B}_{2h-1,h-1}$  -sets, in which all maximal Sidon sets of order $h$  have the same cardinality. Indeed, we shall prove that every ${B}_{2h-1,h-1}$  -set is a matroid in which the ${B}_{h}$  -sets are the independent sets. A maximal independent set in a matroid is called a basis, and all bases in a matroid have the same cardinality.

2 Generalized Sidon sets of order $\left(h,k\right)$

Let $X$  be a subset of an abelian group $\Gamma .$  Let $h$  and $k$  be positive integers with $k\le h.$  The set $X$  is called a generalized Sidon set of order $\left(h,k\right)$  or a ${B}_{h,k}$  -set if, whenever ${a}_{1},\dots ,{a}_{h},{a}_{1}^{\prime },\dots ,{a}_{h}^{\prime }\in X$  and
 $\begin{array}{c}{a}_{1}+\cdots +{a}_{h}={a}_{1}^{\prime }+\cdots +{a}_{h}^{\prime },\end{array}$ (1)
there exist sets $I,{I}^{\prime }\subseteq \left\{1,\dots ,h\right\}$  with $|I|=|{I}^{\prime }|=k$  and a one-to-one map $\tau :{I}^{\prime }\to I$  such that ${a}_{{i}^{\prime }}^{\prime }={a}_{\tau \left({i}^{\prime }\right)}$  for all ${i}^{\prime }\in {I}^{\prime }.$  Let $J=\left\{1,\dots ,h\right\}\I$  and ${J}^{\prime }=\left\{1,\dots ,h\right\}\{I}^{\prime }$  . Then $|J|=|{J}^{\prime }|=h-k$  . Since $X$  is a subset of the group $\Gamma ,$  it follows by subtraction that
 $\begin{array}{c}{\sum }_{j\in J}{a}_{j}={\sum }_{{j}^{\prime }\in {J}^{\prime }}{a}_{{j}^{\prime }}.\end{array}$ (2)
The Sidon sets of order $h$  are precisely the ${B}_{h,h}$  -sets.
A simple example of a ${B}_{3,1}$  -set that is not a ${B}_{3}$  -set is $\left\{1,2,3\right\}$  . Indeed, $\left\{1,2,3\right\}\in {\mathcal{ℬ}}_{2h-1,1}\left(\mathbf{Z}\right)\{\mathcal{ℬ}}_{2h-1,2}\left(\mathbf{Z}\right)$  for every $h\ge 2.$  Another example of a ${B}_{3,1}$  -set is $\left\{1,14,19,20,25,38\right\}$  .
Let ${\mathcal{ℬ}}_{h,k}={\mathcal{ℬ}}_{h,k}\left(\Gamma \right)$  denote the set of all finite ${B}_{h,k}$  -sets in $\Gamma$  . It follows from ( 1 ) and ( 2 ) that if $A$  is a ${B}_{\left(h,k\right)}$  -set and also a ${B}_{h-k}$  -set, then $A$  is a ${B}_{h}$  -set. Conversely, if $A$  is a ${B}_{h}$  -set, then $A$  is both a ${B}_{h,k}$  -set and a ${B}_{h-k}$  -set. Therefore,
 $\begin{array}{c}{\mathcal{ℬ}}_{h}={\mathcal{ℬ}}_{\left(h,k\right)}\cap {\mathcal{ℬ}}_{h-k}\end{array}$ (3)
for $k=1,\dots ,h.$  In particular, for $h\ge 2$  we have
 $\begin{array}{c}{\mathcal{ℬ}}_{2h-1}={\mathcal{ℬ}}_{\left(2h-1,h-1\right)}\cap {\mathcal{ℬ}}_{h}.\end{array}$ (4)
Thus, if $A$  is a ${B}_{h}$  -subset of a ${B}_{2h-1,h-1}$  -set, then $A$  is a ${B}_{2h-1}$  -set.
Similarly, if $k$  and $\ell$  are positive integers and $k+\ell \le h,$  then
 $\begin{array}{c}{\mathcal{ℬ}}_{h,k}={\mathcal{ℬ}}_{h,\ell }\cap {\mathcal{ℬ}}_{h-\ell ,k-\ell }\end{array}$ (5)
for $0\le \ell   It follows that
 $\begin{array}{c}{\mathcal{ℬ}}_{2h-1,h-1}\subseteq {\mathcal{ℬ}}_{2h-k,h-k}\end{array}$ (6)
for $1\le k\le h-1.$  Let $X$  be a subset of an abelian group $\Gamma$  . We have
 $\begin{array}{c}{\mathcal{ℬ}}_{h,h}\left(X\right)\subseteq \cdots \subseteq {\mathcal{ℬ}}_{h,k+1}\left(X\right)\subseteq {\mathcal{ℬ}}_{h,k}\left(X\right)\subseteq \cdots \subseteq {\mathcal{ℬ}}_{h,1}\left(X\right)\end{array}$ (7)
for $k=1,\dots ,h-1.$  In the group $\mathbf{Z}$  of integers, if $g>h,$  then every finite subset of the set $\left\{{g}^{i}:i=1,2,3,\dots \right\}$  is a ${B}_{h}$  -set, and so ${B}_{h,k}$  -sets exist for all $h\ge 1$  and $k=1,\dots ,h.$  However, not all of the set inclusions in ( 7 ) are proper.
Theorem 1. Let $X$  be a subset of an abelian group $\Gamma$  . If $h\ge 2$  and $k\ge h/2,$  then ${\mathcal{ℬ}}_{h}\left(X\right)={\mathcal{ℬ}}_{h,k}\left(X\right).$
• Proof. It suffices to show that ${\mathcal{ℬ}}_{h,k+1}\left(X\right)={\mathcal{ℬ}}_{h,k}\left(X\right)$  if $h/2\le k\le h-1.$  If ${\mathcal{ℬ}}_{h,k+1}\left(X\right)\ne {\mathcal{ℬ}}_{h,k}\left(X\right)$  , then there is a set $A\in {\mathcal{ℬ}}_{h,k}\left(X\right)\{\mathcal{ℬ}}_{h,k+1}\left(X\right)$  and there are elements ${a}_{1},\dots ,{a}_{h-k},{a}_{1}^{\prime },\dots ,{a}_{h-k}^{\prime }\in A$  such that  $\begin{array}{c}{a}_{1}+\cdots +{a}_{h-k}={a}_{1}^{\prime }+\cdots +{a}_{h-k}^{\prime }\end{array}$ (8)
and $\left\{{a}_{1},\dots ,{a}_{h-k}\right\}\cap \left\{{a}_{1}^{\prime },\dots ,{a}_{h-k}^{\prime }\right\}=\varnothing .$  The inequality $h/2\le k\le h-1$  implies that $1\le h-k\le k$  . By the division algorithm, $h=q\left(h-k\right)+r,$  where $q\ge 1$  and $0\le r  It follows from ( 8 ) that $q{a}_{1}+\cdots +q{a}_{h-k}+r{a}^{*}=q{a}_{1}^{\prime }+\cdots +q{a}_{h-k}^{\prime }+r{a}^{*}$  for any ${a}^{*}\in A$  . Each side of this equation is a sum of $h$  elements of $A$  , but the two sides have only $r  common summands. This is impossible if $A\in {\mathcal{ℬ}}_{h,k}\left(X\right)$  , and so ${\mathcal{ℬ}}_{h,k+1}\left(X\right)={\mathcal{ℬ}}_{h,k}\left(X\right)$  . This completes the proof.
Dias da Silva and Nathanson [2have constructed nontrivial generalized Sidon sets of order $\left(2h-1,h-1\right)$  for all $h\ge 2.$  We remark that if ${\mathcal{ℬ}}_{h,k}\left(\mathbf{Z}\right)\{\mathcal{ℬ}}_{h,k+1}\left(\mathbf{Z}\right)\ne \varnothing$  , then ${\mathcal{ℬ}}_{h,k}\left(\mathbf{Z}\right)\{\mathcal{ℬ}}_{h,k+1}\left(\mathbf{Z}\right)$  contains arbitrarily large finite sets of integers.
Theorem 2. Let $1\le k  . If $A$  is a finite set of integers in ${\mathcal{ℬ}}_{h,k}\{\mathcal{ℬ}}_{h,k+1}$  and $b>hmax\left(A\right),$  then $A\cup \left\{b\right\}\in {\mathcal{ℬ}}_{h,k}\{\mathcal{ℬ}}_{h,k+1}.$
• Proof. Let ${A}^{*}=A\cup \left\{b\right\}.$  Let $0\le r\le s\le h$  and let $\left\{{a}_{i}{\right\}}_{i=1}^{h-r}$  and $\left\{{a}_{i}^{\prime }{\right\}}_{i=1}^{h-s}$  be subsets of $A$  such that $rb+{\sum }_{i=1}^{h-r}{a}_{i}=sb+{\sum }_{i=1}^{h-s}{a}_{i}^{\prime }.$  We must show that at least $k$  summands on the left are the same as $k$  summands on the right. If $0\le r  then $rb+{\sum }_{i=1}^{h-r}{a}_{i}<\left(r+1\right)b\le sb\le sb+{\sum }_{i=1}^{h-s}{a}_{i}^{\prime },$  which is absurd. Therefore, $r=s$  and ${\sum }_{i=1}^{h-r}{a}_{i}={\sum }_{i=1}^{h-r}{a}_{i}^{\prime }.$  If $r\ge k,$  we are done. If $r  then $A\in {\mathcal{ℬ}}_{h,k}\subseteq {\mathcal{ℬ}}_{h-r,k-r}$  implies that $k-r$  summands on the left are the same as $k-r$  summands on the right, and so $A\cup \left\{b\right\}\in {\mathcal{ℬ}}_{h,k}.$  If $A\notin {\mathcal{ℬ}}_{h,k+1}\left(\mathbf{Z}\right),$  then $A\cup \left\{b\right\}\notin {\mathcal{ℬ}}_{h,k+1}\left(\mathbf{Z}\right).$  This completes the proof.

3 Maximal Sidon sets of order $h$

Let $X$  be a subset of an abelian group $\Gamma .$  A double representation of length $\ell$  in $X$  is a sequence ${a}_{1},{a}_{2},\dots ,{a}_{\ell },{a}_{1}^{\prime },{a}_{2}^{\prime },\dots ,{a}_{\ell }^{\prime }$  of $2\ell$  not necessarily distinct elements of $X$  such that
 $\begin{array}{c}{a}_{1}+{a}_{2}+\cdots +{a}_{\ell }={a}_{1}^{\prime }+{a}_{2}^{\prime }+\cdots +{a}_{\ell }^{\prime }\end{array}$ (9)
and $\left({a}_{1},\dots ,{a}_{\ell }\right)\nsim \left({a}_{1}^{\prime },\dots ,{a}_{\ell }^{\prime }\right).$  There exists a double representation of length $h$  in the set $X$  if and only if $X$  is not a ${B}_{h}$  -set.
The double representation ( 9 ) is called proper if $\left\{{a}_{1},{a}_{2},\dots ,{a}_{\ell }\right\}\cap \left\{{a}_{1}^{\prime },{a}_{2}^{\prime },\dots ,{a}_{\ell }^{\prime }\right\}=\varnothing .$  If ( 9 ) is a double representation of length $\ell ,$  then we can cancel elements that appear on both sides of the equation, and obtain a unique proper double representation of length ${\ell }^{\prime },$  where $1\le {\ell }^{\prime }\le \ell .$
Lemma 1. Let $h\ge 2$  and let $X$  be a finite ${B}_{2h-1,h-1}$  -subset of an abelian group $\Gamma .$  If ${a}_{1}+{a}_{2}+\cdots +{a}_{\ell }={a}_{1}^{\prime }+{a}_{2}^{\prime }+\cdots +{a}_{\ell }^{\prime }$  is a proper double representation of length $\ell \le 2h-1,$  then $\ell =h$  .
• Proof. By ( 6 ) we have ${\mathcal{ℬ}}_{2h-1,h-1}\subseteq {\mathcal{ℬ}}_{2h-k,h-k}$  for $k=1,2,\dots ,h-1.$  If $h+1\le \ell \le 2h-1,$  then $\ell =2h-k,$  where $1\le k\le h-1.$  Since $X\in {\mathcal{ℬ}}_{2h-k,h-k}$  and $h-k\ge 1,$  it follows that ${a}_{i}^{\prime }={a}_{j}$  for some $i,j\in \left\{1,\dots ,\ell \right\},$  which contradicts the hypothesis that the double representation is proper. Therefore, $\ell \le h.$  Suppose that $\ell \le h-1.$  By the division algorithm, there exist integers $q$  and $r$  such that $2h-1=q\ell +r$  and $0\le r\le \ell -1\le h-2.$  Then $q{a}_{1}+q{a}_{2}+\cdots +q{a}_{\ell }=q{a}_{1}^{\prime }+q{a}_{2}^{\prime }+\cdots +q{a}_{\ell }^{\prime }$  is a proper double representation of length $q\ell ,$  where $h+1\le q\ell =2h-1-r\le 2h-1,$  which is impossible. Therefore, $\ell =h.$  This completes the proof.
Lemma 2. Let $h\ge 2,$  let $X$  be a finite ${B}_{2h-1,h-1}$  -subset of an abelian group $\Gamma ,$  and let $A$  be a maximal ${B}_{h}$  -subset of $X$  . For every $x\in X\A,$  there is exactly one proper double representation with elements in $A\cup \left\{x\right\}$  and of length at most $2h-1.$
• Proof. Since $A$  is a maximal ${B}_{h}$  -set contained in $X$  , it follows that $A\cup \left\{x\right\}$  is not a ${B}_{h}$  -set, and so there exists a double representation of the form $ux+{a}_{1}+\cdots +{a}_{h-u}=vx+{a}_{1}^{\prime }+{a}_{2}^{\prime }+\cdots +{a}_{h-v}^{\prime }.$  Let $u\ge v.$  Subtracting equal elements that appear on both sides of this equation and renumbering the elements that remain in the equation, we obtain a proper double representation of length $\ell \le h$  . By Lemma  1 , we must have $\ell =h$  , and so $v=0$  , there is no cancelation, and the proper double representation is be of the form  $\begin{array}{c}ux+{a}_{1}+\cdots +{a}_{h-u}={a}_{1}^{\prime }+{a}_{2}^{\prime }+\cdots +{a}_{h}^{\prime }.\end{array}$ (10)
Suppose that $w\ge 1$  and  $\begin{array}{c}wx+{b}_{1}+\cdots +{b}_{h-w}={b}_{1}^{\prime }+{b}_{2}^{\prime }+\cdots +{b}_{h}^{\prime }\end{array}$ (11)
is also a proper double representation of length $h$  in $A\cup \left\{x\right\}.$  Adding equations ( 10 ) and ( 11 ), we obtain $ux+{a}_{1}+\cdots +{a}_{h-u}+{b}_{1}^{\prime }+{b}_{2}^{\prime }+\cdots +{b}_{h}^{\prime }=wx+{a}_{1}^{\prime }+{a}_{2}^{\prime }+\cdots +{a}_{h}^{\prime }+{b}_{1}+\cdots +{b}_{h-w}.$  If $u=w,$  we obtain the relation ${a}_{1}+\cdots +{a}_{h-u}+{b}_{1}^{\prime }+{b}_{2}^{\prime }+\cdots +{b}_{h}^{\prime }={a}_{1}^{\prime }+{a}_{2}^{\prime }+\cdots +{a}_{h}^{\prime }+{b}_{1}+\cdots +{b}_{h-u},$  where all of the summands belong to the ${B}_{h}$  -set $A$  . It follows that every term on the left appears on the right, and conversely. Since ${a}_{j}\ne {a}_{i}^{\prime }$  for all $i$  and $j$  , we must have a bijection between the sets $\left\{{a}_{1},\dots ,{a}_{h-u}\right\}$  and $\left\{{b}_{1},\dots ,{b}_{h-u}\right\}$  . Similarly, there is a bijection between the sets $\left\{{a}_{1}^{\prime },\dots ,{a}_{h}^{\prime }\right\}$  and $\left\{{b}_{1}^{\prime },\dots ,{b}_{h}^{\prime }\right\}$  , and so the double representations ( 10 ) and ( 11 ) are equivalent. Thus, for every positive integer $u$  there is at most one proper double representation of the form ( 10 ).
If $u  we obtain the double representation ${a}_{1}+\cdots +{a}_{h-u}+{b}_{1}^{\prime }+{b}_{2}^{\prime }+\cdots +{b}_{h}^{\prime }=\left(w-u\right)x+{a}_{1}^{\prime }+{a}_{2}^{\prime }+\cdots +{a}_{h}^{\prime }+{b}_{1}+\cdots +{b}_{h-w}.$  Cancelling elements that appear on both sides of this equation, we obtain a proper double representation of the form $\left(w-u\right)x+{a}_{1}+\cdots +{a}_{h-w+u}={a}_{1}^{\prime }+{a}_{2}^{\prime }+\cdots +{a}_{h}^{\prime },$  where $w-u\ge 1$  and $\left\{{a}_{1},\dots ,{a}_{h-w+u},{a}_{1}^{\prime },{a}_{2}^{\prime },\dots ,{a}_{h}^{\prime }\right\}\subseteq A.$  We call this process the “subtraction algorithm.” Let $u$  be the smallest positive integer for which there exists a proper double representation of the form ( 10 ). Suppose that there is a proper double representation of the form ( 11 ) for some integer $w>u.$  By the division algorithm, we write $w=qu+r,$  where $0\le r  If $r\ge 1,$  then iteration of the subtraction algorithm above yields a proper double representation in which the element $x$  appears exactly $r$  times, which contradicts the minimality of $u$  . It follows that $u$  must divide $w$  .
Moreover, if there exists a proper double representation for some $w>u,$  then the subtraction algorithm produces a double representation with $w=2u.$  Thus we have proper double representations of the form  $\begin{array}{c}ux+{a}_{1}+\cdots +{a}_{h-u}={a}_{1}^{\prime }+{a}_{2}^{\prime }+\cdots +{a}_{h}^{\prime }\end{array}$ (12)
and  $\begin{array}{c}2ux+{b}_{1}+\cdots +{b}_{h-2u}={b}_{1}^{\prime }+{b}_{2}^{\prime }+\cdots +{b}_{h}^{\prime },\end{array}$ (13)
where $\left\{{a}_{1},\dots ,{a}_{h-u}\right\}\cap \left\{{a}_{1}^{\prime },{a}_{2}^{\prime },\dots ,{a}_{h}^{\prime }\right\}=\varnothing$  and $\left\{{b}_{1},\dots ,{b}_{h-2u}\right\}\cap \left\{{b}_{1}^{\prime },{b}_{2}^{\prime },\dots ,{b}_{h}^{\prime }\right\}=\varnothing .$  Adding equations ( 12 ) and ( 13 ) and cancelling $ux,$  we obtain the following double representation of length $2h-u$  : $ux+{a}_{1}^{\prime }+{a}_{2}^{\prime }+\cdots +{a}_{h}^{\prime }+{b}_{1}+\cdots +{b}_{h-2u}={a}_{1}+\cdots +{a}_{h-u}+{b}_{1}^{\prime }+{b}_{2}^{\prime }+\cdots +{b}_{h}^{\prime }.$  After subtracting $h-u$  equal terms on both sides of this equation, we must obtain the proper double representation ( 12 ). This means that on the left side we must have ${a}_{1}+{a}_{2}+\cdots +{a}_{h-u}$  . Since $\left\{{a}_{1},\dots ,{a}_{h-u}\right\}\cap \left\{{a}_{1}^{\prime },{a}_{2}^{\prime },\dots ,{a}_{h}^{\prime }\right\}=\varnothing ,$  it follows that the sequence $\left({a}_{1},{a}_{2},\dots ,{a}_{h-u}\right)$  is equivalent to the sequence $\left({b}_{1},{b}_{2},\dots ,{b}_{h-2u}\right)$  , which is absurd since $h-2u  This completes the proof.
Lemma 3. Let $h\ge 2,$  and let $A$  be a maximal ${B}_{h}$  -subset of the ${B}_{2h-1,h-1}$  -set $X$  . Let $x\in X\A,$  and let
 $\begin{array}{c}ux+{a}_{1}+\cdots +{a}_{h-u}={a}_{1}^{\prime }+{a}_{2}^{\prime }+\cdots +{a}_{h}^{\prime }\end{array}$ (14)
be the unique proper double representation of length $h$  with elements in $A\cup \left\{x\right\}.$  For every ${a}^{*}\in \left\{{a}_{1},{a}_{2},\dots ,{a}_{h-u},{a}_{1}^{\prime },{a}_{2}^{\prime },\dots ,{a}_{h}^{\prime }\right\},$  the set $\left(A\cup \left\{x\right\}\right)\\left\{{a}^{*}\right\}$  is a ${B}_{h}$  -set contained in $X$  .
• Proof. If $\left(A\cup \left\{x\right\}\right)\\left\{{a}^{*}\right\}$  is not a ${B}_{h}$  -set, then there must exist a positive integer $v$  and elements ${b}_{1},\dots ,{b}_{v},{b}_{1}^{\prime },\dots ,{b}_{h}^{\prime }\in A\\left\{{a}^{*}\right\}$  such that  $\begin{array}{c}vx+{b}_{1}+\cdots +{b}_{h-v}={b}_{1}^{\prime }+{b}_{2}^{\prime }+\cdots +{b}_{h}^{\prime }\end{array}$ (15)
is a proper double representation in $X$  . Then ( 14 ) and ( 15 ) are different proper double representations of length $h$  in $X$  , which contradicts Lemma  2 .
Theorem 3. Let $h\ge 2,$  and let $X$  be a finite ${B}_{2h-1,h-1}$  -set contained in the abelian group $\Gamma .$  Then the maximal ${B}_{h}$  -subsets of $X$  have the same cardinality.
• Proof. Let ${\mathcal{ℳ}}_{h}\left(X\right)$  be the set of maximal ${B}_{h}$  -sets contained in $X$  , and let $m=max\left\{|C|:C\in {\mathcal{ℳ}}_{h}\left(X\right)\right\}.$  We must prove that $|C|=m$  for every $C\in {\mathcal{ℳ}}_{h}\left(X\right).$  Let $C\in {\mathcal{ℳ}}_{h}\left(X\right),$  and let ${C}^{*}$  be the largest subset of $C$  that is contained in a ${B}_{h}$  -set $A$  of cardinality $m$  . If ${C}^{*}=C,$  then the maximality of $C$  implies that $C=A$  , and so $|C|=m.$  If ${C}^{*}\ne C,$  then there exists $s\in C\A.$  By the maximality of $A$  , the set $A\cup \left\{s\right\}$  is not a ${B}_{h}$  -set, and there exists a proper double representation of the form $ws+{a}_{1}+\cdots +{a}_{h-w}={a}_{1}^{\prime }+\cdots +{a}_{h}^{\prime },$  where $\left\{s,{a}_{1},{a}_{2},\dots ,{a}_{h-u}\right\}\cap \left\{{a}_{1}^{\prime },{a}_{2}^{\prime },\dots ,{a}_{h}^{\prime }\right\}=\varnothing .$  If  $\begin{array}{c}\left\{{a}_{1},{a}_{2},\dots ,{a}_{h-u},{a}_{1}^{\prime },{a}_{2}^{\prime },\dots ,{a}_{h}^{\prime }\right\}\subseteq {C}^{*}\subseteq A,\end{array}$ (16)
then ( 16 ) is a proper double representation of length $h$  with elements in $C$  , which contradicts the fact that $C$  is a ${B}_{h}$  -set. Therefore, there exists an element ${a}^{*}\in \left\{{a}_{1},{a}_{2},\dots ,{a}_{h-u},{a}_{1}^{\prime },{a}_{2}^{\prime },\dots ,{a}_{h}^{\prime }\right\}\{C}^{*}.$  By Lemma  3 , the set $\left(A\cup \left\{s\right\}\right)\\left\{{a}^{*}\right\}$  is a ${B}_{h}$  -set contained in $X$  , and ${C}^{*}\cup \left\{s\right\}\subseteq \left(A\cup \left\{s\right\}\right)\\left\{{a}^{*}\right\}.$  This is impossible, since ${C}^{*}\cup \left\{s\right\}\subseteq C,$  $|{C}^{*}\cup \left\{s\right\}|=|{C}^{*}|+1,$  and $|\left(A\cup \left\{s\right\}\right)\\left\{{a}^{*}\right\}|=|A|=m.$  Therefore, ${C}^{*}=C.$  This completes the proof.

4 Matroids of ${B}_{h}$  -sets

A matroid $M=M\left(X,\mathcal{ℐ}\right)$  consists of a finite set $X$  and a collection $\mathcal{ℐ}$  of subsets of $X$  that satisfy the following properties:
• (i) $\varnothing \in \mathcal{ℐ},$
• (ii) If $B\in \mathcal{ℐ}$  and $A\subseteq B,$  then $A\in \mathcal{ℐ},$
• (iii) If $A,B\in \mathcal{ℐ}$  and $|A|<|B|,$  then there exists $b\in B\A$  such that $A\cup \left\{b\right\}\in \mathcal{ℐ}.$
The members of $\mathcal{ℐ}$  are called the independent sets in $X$  . A basis for $X$  is a maximal independent set. Condition (iii) implies that all bases have the same cardinality.
The rank of the matroid $M$  is the cardinality of a basis for $M$  .
Theorem 4. Let $h\ge 2,$  and let $X$  be a finite ${B}_{2h-1,h-1}$  -subset of an abelian group. Let $\mathcal{ℐ}$  be the collection of ${B}_{h}$  -sets contained in $X$  . Then $M=M\left(X,\mathcal{ℐ}\right)$  is a matroid.
• Proof. Every subset of a ${B}_{h}$  -set is a ${B}_{h}$  -set, and the empty set is also a ${B}_{h}$  -set. We must show that if $A$  and $B$  are ${B}_{h}$  -subsets of $X$  with $|A|<|B|,$  then there exists $b\in B\A$  such that $A\cup \left\{b\right\}$  is a ${B}_{h}$  -set.
Let ${X}^{\prime }=A\cup B.$  Then ${X}^{\prime }$  is a ${B}_{2h-1,h-1}$  -subset of $X$  . Let $m$  be the cardinality of the maximal ${B}_{h}$  -subsets of ${X}^{\prime }$  . Let ${A}^{*}$  be a maximal ${B}_{h}$  -subset of ${X}^{\prime }$  that contains $A$  . Then $|A|<|B|\le m=|{A}^{*}|,$  and so there exists an element $b\in {A}^{*}\A\subseteq {X}^{\prime }\A=B\A.$  Then $A\cup \left\{b\right\}\subseteq {A}^{*},$  and so $A\cup \left\{b\right\}$  is a ${B}_{h}$  -set. This completes the proof.
Let $M=M\left(X,\mathcal{ℐ}\right)$  be a matroid. For every positive integer $k$  , let ${\mathcal{ℐ}}^{\left(k\right)}$  be the set of all unions of $k$  independent subsets of $X$  , that is, all sets of the form ${I}_{1}\cup {I}_{2}\cup \cdots \cup {I}_{k},$  where ${I}_{1},{I}_{2},\dots ,{I}_{k}\in \mathcal{ℐ}.$  Then ${M}^{\left(k\right)}=M\left(X,{\mathcal{ℐ}}^{\left(k\right)}\right)$  is also a matroid on the set $X$  (Welsh [7,Section8.3). We denote the rank of the matroid ${M}^{\left(k\right)}$  by ${\rho }_{k}.$  Then ${\rho }_{k}$  is the cardinality of the largest subset of $X$  that can be written as the union of $k$  independent sets in $X$  .
The covering number of a set $S$  contained in $X$  is the smallest integer $k$  such that $S$  can be written as the union of $k$  independent subsets of $X$  . If $\left\{x\right\}\in \mathcal{ℐ}$  for every $x\in X,$  then the covering number exists, and the covering number of $S$  is at most $|S|.$  The set $S$  has covering number $k$  if and only if $k$  is the smallest integer such that $S$  is an independent set in the matroid ${M}^{\left(k\right)}$  . The set $X$  has covering number $k$  if and only if ${\rho }_{1}<{\rho }_{2}<\cdots <{\rho }_{k}=|X|.$  Let $X$  be a ${B}_{2h-1,h-1}$  -set contained in an abelian group. For every subset $S$  of $X$  , we define the ${B}_{h}$  -covering number of $S$  as the smallest integer $k$  such that $S={A}_{1}\cup \cdots \cup {A}_{k},$  where ${A}_{1},\dots ,{A}_{k}$  are ${B}_{h}$  -sets. Since $\left\{x\right\}$  is a ${B}_{h}$  -set for all $x\in X,$  it follows that every subset of $X$  has a finite ${B}_{h}$  -covering number.
Theorem 5. Let $X$  be a ${B}_{2h-1,h-1}$  -set contained in an abelian group, and let $\ell$  be the ${B}_{h}$  -covering number of $X$  . For every positive integer $k\le \ell$  there is a number ${n}_{X}\left(k\right)$  such that if $S$  is a maximal subset of $X$  whose ${B}_{h}$  -covering number is $k$  , then $|S|={n}_{X}\left(k\right).$
• Proof. By Theorem  4 , $M=M\left(X,\mathcal{ℐ}\right)$  is a matroid, where $\mathcal{ℐ}$  is the set of ${B}_{h}$  -subsets of $X$  . Let ${n}_{X}\left(k\right)$  denote the cardinality of the bases in the matroid ${M}^{\left(k\right)}.$  The maximal subsets of $X$  with ${B}_{h}$  -covering number $k$  are precisely the bases in the matroid ${M}^{\left(k\right)}.$  This completes the proof.
Let ${I}_{1},{I}_{2},\dots ,{I}_{k}$  be independent sets in a matroid $M=M\left(X,\mathcal{ℐ}\right)$  . We define ${I}_{1}^{\prime }={I}_{1}$  and ${I}_{j}^{\prime }={I}_{j}\\left({I}_{1}\cup \cdots \cup {I}_{j-1}\right)$  for $j=2,\dots ,k.$  Since every subset of an independent set is independent, it follows that the sets ${I}_{1}^{\prime },{I}_{2}^{\prime },\dots ,{I}_{k}^{\prime }$  are pairwise disjoint independent sets in $M$  , and ${I}_{1}\cup {I}_{2}\cup \cdots \cup {I}_{k}={I}_{1}^{\prime }\cup {I}_{2}^{\prime }\cup \cdots \cup {I}_{k}^{\prime }$  . Therefore, every independent set in the matroid ${M}^{\left(k\right)}$  can be written as the union of $k$  pairwise disjoint independent sets in $M$  . In particular, if $X$  has covering number $k,$  then $X$  is the union of $k$  pairwise disjoint nonempty independent subsets of $X$  .
Let $\mu =\left({\mu }_{1},\dots ,{\mu }_{r}\right)$  be a partition of $|X|,$  that is, ${\mu }_{1},{\mu }_{2},\dots ,{\mu }_{r}$  are positive integers such that ${\mu }_{1}+{\mu }_{2}+\cdots +{\mu }_{r}=|X|$  and ${\mu }_{1}\ge {\mu }_{2}\ge \cdots \ge {\mu }_{r}.$  A $\mu$  -covering of the matroid $M=M\left(X,\mathcal{ℐ}\right)$  consists of $r$  pairwise disjoint independent sets ${I}_{1},{I}_{2},\dots ,{I}_{r}$  such that $X={I}_{1}\cup {I}_{2}\cup \cdots \cup {I}_{r}$  and $|{I}_{j}|={\mu }_{j}\text{for}j=1,2,\dots ,r.\text{}$  Let $k$  be the covering number of the matroid $M$  . Dias da Silva [1proved that there exists a $\mu$  -covering of $X$  if and only if $k\le r$  and ${\rho }_{j}\ge {\mu }_{1}+\cdots +{\mu }_{j}$  for $j=1,\dots ,k.$
Theorem 6. Let $X$  be a ${B}_{2h-1,h-1}$  -set contained in an abelian group, and let $k$  be the ${B}_{h}$  -covering number of $X$  . For $j=1,\dots ,k,$  let ${\rho }_{j}$  denote the maximum cardinality of a union of $j$  ${B}_{h}$  -subsets of $X$  . Let $\mu =\left({\mu }_{1},\dots ,{\mu }_{r}\right)$  be any partition of $|X|.$  There exist pairwise disjoint ${B}_{h}$  -sets ${I}_{1},\dots ,{I}_{r}$  such that $X={I}_{1}\cup \cdots \cup {I}_{r}$  and $|{I}_{j}|={\mu }_{j}$  for $j=1,\dots ,r$  if and only if $r\ge k$  and ${\rho }_{j}\ge {\mu }_{1}+\cdots +{\mu }_{j}$  for $j=1,\dots ,k.$
• Proof. This follows immediately from the fact that the ${B}_{h}$  -sets are the independent sets of a matroid on $X$  .
References

1. J. A. Dias da Silva, On the $\mu$  colorings of a matroid, Linear and Multilinear Algebra 27 (1990), 25–32.
2. J. A. Dias da Silva and M. B. Nathanson, Construction of generalized Sidon sets of order $\left(2h-1,h-1\right)$  , in preparation.
3. P. Erdős and P. Turán, On a problem of Sidon in additive number theory, and on some related problems, J. London Math. Soc. 16 (1941), 212–215.
4. G. Martin and K. O'Bryant, Constructions of generalized Sidon sets, arxiv: math.NT/0408081, 2004.
5. K. O'Bryant, A complete annotated bibliography of work related to Sidon sequences, Electronic J. Combinatorics (2004), Dynamic Surveys DS 11.
6. I. Z. Ruzsa, A small maximal Sidon set, Ramanujan J. 2 (1998), 55–58.
7. D. J. A. Welsh, Matroid theory, Academic Press, London, 1976.

Departamento de Matematica, Faculdade de Ciencias, Universidade de Lisboa, Campo Grande, Bloco C6, 1749-016 Lisboa, Portugal E-mail address : perdigao@hermite.cii.fc.ul.pt Department of Mathematics, Lehman College (CUNY), Bronx, New York 10468, USA E-mail address : melvyn.nathanson@lehman.cuny.edu