, , ,

Let

A

be a subset of an abelian group

Γ

. Two

h

-tuples

(a_{1}, \dots, a_{h})

and

(a_{1}^{'}, \dots, a_{h}^{'})

of elements of

A

are called equivalent, denoted

(a_{1}, \dots, a_{h}) \sim (a_{1}^{'}, \dots, a_{h}^{'}),

if there is a permutation

σ

of the set

{1, \dots, h}

such that

a_{i}^{'} = a_{σ (i)}

for

i = 1, \dots, h .

If the

h

-tuples

(a_{1}, \dots, a_{h})

and

(a_{1}^{'}, \dots, a_{h}^{'})

are equivalent, then

a_{1} + \dots + a_{h} = a_{1}^{'} + \dots + a_{h}^{'}

. We write

(a_{1}, \dots, a_{h}) ≁ (a_{1}^{'}, \dots, a_{h}^{'})

if the

h

-tuples

(a_{1}, \dots, a_{h})

and

(a_{1}^{'}, \dots, a_{h}^{'})

are not equivalent.

The

h

-fold sumset of

A

, denoted

h A

, is the set of all elements of

Γ

that can be written as the sum of

h

elements of

A

, with repetitions allowed. For every

x \in Γ,

the representation function

r_{A, h} (x)

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

(a_{1}, \dots, a_{h})

such that

x = a_{1} + \dots + a_{h} .

The set

A

is called a Sidon set of order

h

or a

B_{h}

-set if every element of the sumset

h A

has a unique representation as the sum of

h

elements of

A

, that is, if

r_{A, h} (x) = 1

for all

x \in h A

. This means that if

a_{1}, \dots, a_{h}, a_{1}^{'}, \dots, a_{h}^{'} \in A

and

a_{1} + \dots + a_{h} = a_{1}^{'} + \dots + a_{h}^{'},

then

(a_{1}, \dots, a_{h}) \sim (a_{1}^{'}, \dots, a_{h}^{'}) .

A Sidon set is a Sidon set of order 2.

Let

X

be a subset of the group

Γ,

and denote by

ℬ_{h} (X)

the set of all finite

B_{h}

-sets contained in

X

. Every set is a

B_{1}

-set, and

ℬ_{h} (X) \subseteq ℬ_{h - 1} (X) \subseteq \dots \subseteq ℬ_{2} (X) \subseteq ℬ_{1} (X) .

Moreover,

{a} \in B_{h} (X) for all a \in X and h \geq 1 .

A

is a Sidon subset of order

h

contained in the group

Γ,

then for every

x \in Γ

the translation

x + A = {x + a : a \in A}

and the reflection

x - A = {x - a : a \in A}

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

{1, 2, \dots, n} .

More generally, if

X

is a finite subset of the integers or of any abelian group

Γ

, 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

{1, 2, 3, 4, 5, 6, 7}

, the sets

{1, 3, 6, 7}

and

{1, 2, 5, 7}

are the two maximal Sidon subsets of size 4, but there are also exactly 18 maximal Sidon subsets of size 3, for example,

{1, 3, 4} .

Erdős and Turán [3] proved that the maximum size of a Sidon set of order 2 contained in

{1, 2, \dots, n}

n^{1 / 2} + o (n^{1 / 2}) .

Ruzsa [6] has constructed maximal Sidon subsets of this interval of cardinality

≪ (n log n)^{1 / 3} .

(See Martin and O'Bryant [4] for constructions of finite Sidon sets of integers and O'Bryant [5] for a survey of the recent literature.) The purpose of this paper is to describe a class of finite sets, called

B_{2 h - 1, h - 1}

-sets, in which all maximal Sidon sets of order

h

have the same cardinality. Indeed, we shall prove that every

B_{2 h - 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 $(h, k)$

Let

X

be a subset of an abelian group

Γ .

Let

h

and

k

be positive integers with

k \leq h .

The set

X

is called a generalized Sidon set of order

(h, k)

or a

B_{h, k}

-set if, whenever

a_{1}, \dots, a_{h}, a_{1}^{'}, \dots, a_{h}^{'} \in X

and

\begin{matrix} a_{1} + \dots + a_{h} = a_{1}^{'} + \dots + a_{h}^{'}, \end{matrix}

(1)

there exist sets

I, I^{'} \subseteq {1, \dots, h}

with

| I | = | I^{'} | = k

and a one-to-one map

τ : I^{'} \to I

such that

a_{i^{'}}^{'} = a_{τ (i^{'})}

for all

i^{'} \in I^{'} .

Let

J = {1, \dots, h} \ I

and

J^{'} = {1, \dots, h} \ I^{'}

. Then

| J | = | J^{'} | = h - k

. Since

X

is a subset of the group

Γ,

it follows by subtraction that

\begin{matrix} \sum_{j \in J} a_{j} = \sum_{j^{'} \in J^{'}} a_{j^{'}} . \end{matrix}

(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

{1, 2, 3}

. Indeed,

{1, 2, 3} \in ℬ_{2 h - 1, 1} (Z) \ ℬ_{2 h - 1, 2} (Z)

for every

h \geq 2 .

Another example of a

B_{3, 1}

-set is

{1, 14, 19, 20, 25, 38}

Let

ℬ_{h, k} = ℬ_{h, k} (Γ)

denote the set of all finite

B_{h, k}

-sets in

Γ

. It follows from ( 1 ) and ( 2 ) that if

A

is a

B_{(h, k)}

-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{matrix} ℬ_{h} = ℬ_{(h, k)} \cap ℬ_{h - k} \end{matrix}

(3)

for

k = 1, \dots, h .

In particular, for

h \geq 2

we have

\begin{matrix} ℬ_{2 h - 1} = ℬ_{(2 h - 1, h - 1)} \cap ℬ_{h} . \end{matrix}

(4)

Thus, if

A

is a

B_{h}

-subset of a

B_{2 h - 1, h - 1}

-set, then

A

is a

B_{2 h - 1}

-set.

Similarly, if

k

and

ℓ

are positive integers and

k + ℓ \leq h,

then

\begin{matrix} ℬ_{h, k} = ℬ_{h, ℓ} \cap ℬ_{h - ℓ, k - ℓ} \end{matrix}

(5)

for

0 \leq ℓ < k \leq h .

It follows that

\begin{matrix} ℬ_{2 h - 1, h - 1} \subseteq ℬ_{2 h - k, h - k} \end{matrix}

(6)

for

1 \leq k \leq h - 1 .

Let

X

be a subset of an abelian group

Γ

. We have

\begin{matrix} ℬ_{h, h} (X) \subseteq \dots \subseteq ℬ_{h, k + 1} (X) \subseteq ℬ_{h, k} (X) \subseteq \dots \subseteq ℬ_{h, 1} (X) \end{matrix}

(7)

for

k = 1, \dots, h - 1 .

In the group

Z

of integers, if

g > h,

then every finite subset of the set

{g^{i} : i = 1, 2, 3, \dots}

is a

B_{h}

-set, and so

B_{h, k}

-sets exist for all

h \geq 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

Γ

. If

h \geq 2

and

k \geq h / 2,

then

ℬ_{h} (X) = ℬ_{h, k} (X) .

Proof. It suffices to show that

ℬ_{h, k + 1} (X) = ℬ_{h, k} (X)

h / 2 \leq k \leq h - 1 .

ℬ_{h, k + 1} (X) \neq ℬ_{h, k} (X)

, then there is a set

A \in ℬ_{h, k} (X) \ ℬ_{h, k + 1} (X)

and there are elements

a_{1}, \dots, a_{h - k}, a_{1}^{'}, \dots, a_{h - k}^{'} \in A

such that

\begin{matrix} a_{1} + \dots + a_{h - k} = a_{1}^{'} + \dots + a_{h - k}^{'} \end{matrix}

(8)

and

{a_{1}, \dots, a_{h - k}} \cap {a_{1}^{'}, \dots, a_{h - k}^{'}} = \emptyset .

The inequality

h / 2 \leq k \leq h - 1

implies that

1 \leq h - k \leq k

. By the division algorithm,

h = q (h - k) + r,

where

q \geq 1

and

0 \leq r < h - k .

It follows from ( 8 ) that

q a_{1} + \dots + q a_{h - k} + r a^{*} = q a_{1}^{'} + \dots + q a_{h - k}^{'} + 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 < h - k \leq k

common summands. This is impossible if

A \in ℬ_{h, k} (X)

, and so

ℬ_{h, k + 1} (X) = ℬ_{h, k} (X)

. This completes the proof. □

Dias da Silva and Nathanson [2] have constructed nontrivial generalized Sidon sets of order

(2 h - 1, h - 1)

for all

h \geq 2 .

We remark that if

ℬ_{h, k} (Z) \ ℬ_{h, k + 1} (Z) \neq \emptyset

, then

ℬ_{h, k} (Z) \ ℬ_{h, k + 1} (Z)

contains arbitrarily large finite sets of integers.

Theorem 2. Let

1 \leq k < h / 2

. If

A

is a finite set of integers in

ℬ_{h, k} \ ℬ_{h, k + 1}

and

b > h max (A),

then

A \cup {b} \in ℬ_{h, k} \ ℬ_{h, k + 1} .

Proof. Let $A^{*} = A \cup {b} .$ Let $0 \leq r \leq s \leq h$ and let ${a_{i}}_{i = 1}^{h - r}$ and ${a_{i}^{'}}_{i = 1}^{h - s}$ be subsets of $A$ such that $r b + \sum_{i = 1}^{h - r} a_{i} = s b + \sum_{i = 1}^{h - s} a_{i}^{'} .$ We must show that at least $k$ summands on the left are the same as $k$ summands on the right. If $0 \leq r < s \leq h,$ then $r b + \sum_{i = 1}^{h - r} a_{i} < (r + 1) b \leq s b \leq s b + \sum_{i = 1}^{h - s} a_{i}^{'},$ which is absurd. Therefore, $r = s$ and $\sum_{i = 1}^{h - r} a_{i} = \sum_{i = 1}^{h - r} a_{i}^{'} .$ If $r \geq k,$ we are done. If $r < k,$ then $A \in ℬ_{h, k} \subseteq ℬ_{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 {b} \in ℬ_{h, k} .$ If $A \notin ℬ_{h, k + 1} (Z),$ then $A \cup {b} \notin ℬ_{h, k + 1} (Z) .$ This completes the proof. □

3 Maximal Sidon sets of order $h$

Let

X

be a subset of an abelian group

Γ .

A double representation of length

ℓ

X

is a sequence

a_{1}, a_{2}, \dots, a_{ℓ}, a_{1}^{'}, a_{2}^{'}, \dots, a_{ℓ}^{'}

2 ℓ

not necessarily distinct elements of

X

such that

\begin{matrix} a_{1} + a_{2} + \dots + a_{ℓ} = a_{1}^{'} + a_{2}^{'} + \dots + a_{ℓ}^{'} \end{matrix}

(9)

and

(a_{1}, \dots, a_{ℓ}) ≁ (a_{1}^{'}, \dots, a_{ℓ}^{'}) .

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

{a_{1}, a_{2}, \dots, a_{ℓ}} \cap {a_{1}^{'}, a_{2}^{'}, \dots, a_{ℓ}^{'}} = \emptyset .

If ( 9 ) is a double representation of length

ℓ,

then we can cancel elements that appear on both sides of the equation, and obtain a unique proper double representation of length

ℓ^{'},

where

1 \leq ℓ^{'} \leq ℓ .

Lemma 1. Let

h \geq 2

and let

X

be a finite

B_{2 h - 1, h - 1}

-subset of an abelian group

Γ .

a_{1} + a_{2} + \dots + a_{ℓ} = a_{1}^{'} + a_{2}^{'} + \dots + a_{ℓ}^{'}

is a proper double representation of length

ℓ \leq 2 h - 1,

then

ℓ = h

Proof. By ( 6 ) we have $ℬ_{2 h - 1, h - 1} \subseteq ℬ_{2 h - k, h - k}$ for $k = 1, 2, \dots, h - 1 .$ If $h + 1 \leq ℓ \leq 2 h - 1,$ then $ℓ = 2 h - k,$ where $1 \leq k \leq h - 1 .$ Since $X \in ℬ_{2 h - k, h - k}$ and $h - k \geq 1,$ it follows that $a_{i}^{'} = a_{j}$ for some $i, j \in {1, \dots, ℓ},$ which contradicts the hypothesis that the double representation is proper. Therefore, $ℓ \leq h .$ Suppose that $ℓ \leq h - 1 .$ By the division algorithm, there exist integers $q$ and $r$ such that $2 h - 1 = q ℓ + r$ and $0 \leq r \leq ℓ - 1 \leq h - 2 .$ Then $q a_{1} + q a_{2} + \dots + q a_{ℓ} = q a_{1}^{'} + q a_{2}^{'} + \dots + q a_{ℓ}^{'}$ is a proper double representation of length $q ℓ,$ where $h + 1 \leq q ℓ = 2 h - 1 - r \leq 2 h - 1,$ which is impossible. Therefore, $ℓ = h .$ This completes the proof. □

Lemma 2. Let

h \geq 2,

let

X

be a finite

B_{2 h - 1, h - 1}

-subset of an abelian group

Γ,

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 {x}

and of length at most

2 h - 1 .

Proof. Since

A

is a maximal

B_{h}

-set contained in

X

, it follows that

A \cup {x}

is not a

B_{h}

-set, and so there exists a double representation of the form

u x + a_{1} + \dots + a_{h - u} = v x + a_{1}^{'} + a_{2}^{'} + \dots + a_{h - v}^{'} .

Let

u \geq 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

ℓ \leq h

. By Lemma 1 , we must have

ℓ = h

, and so

v = 0

, there is no cancelation, and the proper double representation is be of the form

\begin{matrix} u x + a_{1} + \dots + a_{h - u} = a_{1}^{'} + a_{2}^{'} + \dots + a_{h}^{'} . \end{matrix}

(10)

Suppose that

w \geq 1

and

\begin{matrix} w x + b_{1} + \dots + b_{h - w} = b_{1}^{'} + b_{2}^{'} + \dots + b_{h}^{'} \end{matrix}

(11)

is also a proper double representation of length

h

A \cup {x} .

Adding equations ( 10 ) and ( 11 ), we obtain

u x + a_{1} + \dots + a_{h - u} + b_{1}^{'} + b_{2}^{'} + \dots + b_{h}^{'} = w x + a_{1}^{'} + a_{2}^{'} + \dots + a_{h}^{'} + b_{1} + \dots + b_{h - w} .

u = w,

we obtain the relation

a_{1} + \dots + a_{h - u} + b_{1}^{'} + b_{2}^{'} + \dots + b_{h}^{'} = a_{1}^{'} + a_{2}^{'} + \dots + a_{h}^{'} + b_{1} + \dots + 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} \neq a_{i}^{'}

for all

i

and

j

, we must have a bijection between the sets

{a_{1}, \dots, a_{h - u}}

and

{b_{1}, \dots, b_{h - u}}

. Similarly, there is a bijection between the sets

{a_{1}^{'}, \dots, a_{h}^{'}}

and

{b_{1}^{'}, \dots, b_{h}^{'}}

, 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 ).

u < w,

we obtain the double representation

a_{1} + \dots + a_{h - u} + b_{1}^{'} + b_{2}^{'} + \dots + b_{h}^{'} = (w - u) x + a_{1}^{'} + a_{2}^{'} + \dots + a_{h}^{'} + b_{1} + \dots + b_{h - w} .

Cancelling elements that appear on both sides of this equation, we obtain a proper double representation of the form

(w - u) x + a_{1} + \dots + a_{h - w + u} = a_{1}^{'} + a_{2}^{'} + \dots + a_{h}^{'},

where

w - u \geq 1

and

{a_{1}, \dots, a_{h - w + u}, a_{1}^{'}, a_{2}^{'}, \dots, a_{h}^{'}} \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 = q u + r,

where

0 \leq r < u .

r \geq 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 = 2 u .

Thus we have proper double representations of the form

\begin{matrix} u x + a_{1} + \dots + a_{h - u} = a_{1}^{'} + a_{2}^{'} + \dots + a_{h}^{'} \end{matrix}

(12)

and

\begin{matrix} 2 u x + b_{1} + \dots + b_{h - 2 u} = b_{1}^{'} + b_{2}^{'} + \dots + b_{h}^{'}, \end{matrix}

(13)

where

{a_{1}, \dots, a_{h - u}} \cap {a_{1}^{'}, a_{2}^{'}, \dots, a_{h}^{'}} = \emptyset

and

{b_{1}, \dots, b_{h - 2 u}} \cap {b_{1}^{'}, b_{2}^{'}, \dots, b_{h}^{'}} = \emptyset .

Adding equations ( 12 ) and ( 13 ) and cancelling

u x,

we obtain the following double representation of length

2 h - u

u x + a_{1}^{'} + a_{2}^{'} + \dots + a_{h}^{'} + b_{1} + \dots + b_{h - 2 u} = a_{1} + \dots + a_{h - u} + b_{1}^{'} + b_{2}^{'} + \dots + b_{h}^{'} .

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} + \dots + a_{h - u}

. Since

{a_{1}, \dots, a_{h - u}} \cap {a_{1}^{'}, a_{2}^{'}, \dots, a_{h}^{'}} = \emptyset,

it follows that the sequence

(a_{1}, a_{2}, \dots, a_{h - u})

is equivalent to the sequence

(b_{1}, b_{2}, \dots, b_{h - 2 u})

, which is absurd since

h - 2 u < h - u .

This completes the proof. □

Lemma 3. Let

h \geq 2,

and let

A

be a maximal

B_{h}

-subset of the

B_{2 h - 1, h - 1}

-set

X

. Let

x \in X \ A,

and let

\begin{matrix} u x + a_{1} + \dots + a_{h - u} = a_{1}^{'} + a_{2}^{'} + \dots + a_{h}^{'} \end{matrix}

(14)

be the unique proper double representation of length

h

with elements in

A \cup {x} .

For every

a^{*} \in {a_{1}, a_{2}, \dots, a_{h - u}, a_{1}^{'}, a_{2}^{'}, \dots, a_{h}^{'}},

the set

(A \cup {x}) \ {a^{*}}

is a

B_{h}

-set contained in

X

Proof. If

(A \cup {x}) \ {a^{*}}

is not a

B_{h}

-set, then there must exist a positive integer

v

and elements

b_{1}, \dots, b_{v}, b_{1}^{'}, \dots, b_{h}^{'} \in A \ {a^{*}}

such that

\begin{matrix} v x + b_{1} + \dots + b_{h - v} = b_{1}^{'} + b_{2}^{'} + \dots + b_{h}^{'} \end{matrix}

(15)

is a proper double representation in

X

. Then ( 14 ) and ( 15 ) are different proper double representations of length

h

X

, which contradicts Lemma 2 . □

Theorem 3. Let

h \geq 2,

and let

X

be a finite

B_{2 h - 1, h - 1}

-set contained in the abelian group

Γ .

Then the maximal

B_{h}

-subsets of

X

have the same cardinality.

Proof. Let

ℳ_{h} (X)

be the set of maximal

B_{h}

-sets contained in

X

, and let

m = max {| C | : C \in ℳ_{h} (X)} .

We must prove that

| C | = m

for every

C \in ℳ_{h} (X) .

Let

C \in ℳ_{h} (X),

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 .

C^{*} \neq C,

then there exists

s \in C \ A .

By the maximality of

A

, the set

A \cup {s}

is not a

B_{h}

-set, and there exists a proper double representation of the form

w s + a_{1} + \dots + a_{h - w} = a_{1}^{'} + \dots + a_{h}^{'},

where

{s, a_{1}, a_{2}, \dots, a_{h - u}} \cap {a_{1}^{'}, a_{2}^{'}, \dots, a_{h}^{'}} = \emptyset .

\begin{matrix} {a_{1}, a_{2}, \dots, a_{h - u}, a_{1}^{'}, a_{2}^{'}, \dots, a_{h}^{'}} \subseteq C^{*} \subseteq A, \end{matrix}

(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 {a_{1}, a_{2}, \dots, a_{h - u}, a_{1}^{'}, a_{2}^{'}, \dots, a_{h}^{'}} \ C^{*} .

By Lemma 3 , the set

(A \cup {s}) \ {a^{*}}

is a

B_{h}

-set contained in

X

, and

C^{*} \cup {s} \subseteq (A \cup {s}) \ {a^{*}} .

This is impossible, since

C^{*} \cup {s} \subseteq C,

| C^{*} \cup {s} | = | C^{*} | + 1,

and

| (A \cup {s}) \ {a^{*}} | = | A | = m .

Therefore,

C^{*} = C .

This completes the proof. □

4 Matroids of $B_{h}$ -sets

A matroid

M = M (X, ℐ)

consists of a finite set

X

and a collection

ℐ

of subsets of

X

that satisfy the following properties:

(i) $\emptyset \in ℐ,$
(ii) If $B \in ℐ$ and $A \subseteq B,$ then $A \in ℐ,$
(iii) If $A, B \in ℐ$ and $| A | < | B |,$ then there exists $b \in B \ A$ such that $A \cup {b} \in ℐ .$

The members of

ℐ

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 \geq 2,

and let

X

be a finite

B_{2 h - 1, h - 1}

-subset of an abelian group. Let

ℐ

be the collection of

B_{h}

-sets contained in

X

. Then

M = M (X, ℐ)

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 {b}$ is a $B_{h}$ -set.
Let $X^{'} = A \cup B .$ Then $X^{'}$ is a $B_{2 h - 1, h - 1}$ -subset of $X$ . Let $m$ be the cardinality of the maximal $B_{h}$ -subsets of $X^{'}$ . Let $A^{*}$ be a maximal $B_{h}$ -subset of $X^{'}$ that contains $A$ . Then $| A | < | B | \leq m = | A^{*} |,$ and so there exists an element $b \in A^{*} \ A \subseteq X^{'} \ A = B \ A .$ Then $A \cup {b} \subseteq A^{*},$ and so $A \cup {b}$ is a $B_{h}$ -set. This completes the proof. □

Let

M = M (X, ℐ)

be a matroid. For every positive integer

k

, let

ℐ^{(k)}

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 \dots \cup I_{k},

where

I_{1}, I_{2}, \dots, I_{k} \in ℐ .

Then

M^{(k)} = M (X, ℐ^{(k)})

is also a matroid on the set

X

(Welsh [7,Section8.3] ). We denote the rank of the matroid

M^{(k)}

ρ_{k} .

Then

ρ_{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

{x} \in ℐ

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^{(k)}

. The set

X

has covering number

k

if and only if

ρ_{1} < ρ_{2} < \dots < ρ_{k} = | X | .

Let

X

be a

B_{2 h - 1, h - 1}

-set contained in an abelian group. For every subset

S

X

, we define the

B_{h}

-covering number of

S

as the smallest integer

k

such that

S = A_{1} \cup \dots \cup A_{k},

where

A_{1}, \dots, A_{k}

are

B_{h}

-sets. Since

{x}

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_{2 h - 1, h - 1}

-set contained in an abelian group, and let

ℓ

be the

B_{h}

-covering number of

X

. For every positive integer

k \leq ℓ

there is a number

n_{X} (k)

such that if

S

is a maximal subset of

X

whose

B_{h}

-covering number is

k

, then

| S | = n_{X} (k) .

Proof. By Theorem 4 , $M = M (X, ℐ)$ is a matroid, where $ℐ$ is the set of $B_{h}$ -subsets of $X$ . Let $n_{X} (k)$ denote the cardinality of the bases in the matroid $M^{(k)} .$ The maximal subsets of $X$ with $B_{h}$ -covering number $k$ are precisely the bases in the matroid $M^{(k)} .$ This completes the proof. □

Let

I_{1}, I_{2}, \dots, I_{k}

be independent sets in a matroid

M = M (X, ℐ)

. We define

I_{1}^{'} = I_{1}

and

I_{j}^{'} = I_{j} \ (I_{1} \cup \dots \cup I_{j - 1})

for

j = 2, \dots, k .

Since every subset of an independent set is independent, it follows that the sets

I_{1}^{'}, I_{2}^{'}, \dots, I_{k}^{'}

are pairwise disjoint independent sets in

M

, and

I_{1} \cup I_{2} \cup \dots \cup I_{k} = I_{1}^{'} \cup I_{2}^{'} \cup \dots \cup I_{k}^{'}

. Therefore, every independent set in the matroid

M^{(k)}

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

μ = (μ_{1}, \dots, μ_{r})

be a partition of

| X |,

that is,

μ_{1}, μ_{2}, \dots, μ_{r}

are positive integers such that

μ_{1} + μ_{2} + \dots + μ_{r} = | X |

and

μ_{1} \geq μ_{2} \geq \dots \geq μ_{r} .

μ

-covering of the matroid

M = M (X, ℐ)

consists of

r

pairwise disjoint independent sets

I_{1}, I_{2}, \dots, I_{r}

such that

X = I_{1} \cup I_{2} \cup \dots \cup I_{r}

and

| I_{j} | = μ_{j} for j = 1, 2, \dots, r .

Let

k

be the covering number of the matroid

M

. Dias da Silva [1] proved that there exists a

μ

-covering of

X

if and only if

k \leq r

and

ρ_{j} \geq μ_{1} + \dots + μ_{j}

for

j = 1, \dots, k .

Theorem 6. Let

X

be a

B_{2 h - 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

ρ_{j}

denote the maximum cardinality of a union of

j

B_{h}

-subsets of

X

. Let

μ = (μ_{1}, \dots, μ_{r})

be any partition of

| X | .

There exist pairwise disjoint

B_{h}

-sets

I_{1}, \dots, I_{r}

such that

X = I_{1} \cup \dots \cup I_{r}

and

| I_{j} | = μ_{j}

for

j = 1, \dots, r

if and only if

r \geq k

and

ρ_{j} \geq μ_{1} + \dots + μ_{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

J. A. Dias da Silva, On the $μ$ colorings of a matroid, Linear and Multilinear Algebra 27 (1990), 25–32.
J. A. Dias da Silva and M. B. Nathanson, Construction of generalized Sidon sets of order $(2 h - 1, h - 1)$ , in preparation.
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.
G. Martin and K. O'Bryant, Constructions of generalized Sidon sets, arxiv: math.NT/0408081, 2004.
K. O'Bryant, A complete annotated bibliography of work related to Sidon sequences, Electronic J. Combinatorics (2004), Dynamic Surveys DS 11.
I. Z. Ruzsa, A small maximal Sidon set, Ramanujan J. 2 (1998), 55–58.
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

J. A. Dias da Silva

Melvyn B. Nathanson