## You are here

HomeSidon set

## Primary tabs

# Sidon set

A set of natural numbers is called a *Sidon set* if all
pairwise sums of its elements are distinct. Equivalently, the equation
$a+b=c+d$ has only the trivial solution $\{a,b\}=\{c,d\}$ in
elements of the set.

Sidon sets are a special case of so-called $B_{h}[g]$ sets. A set $A$ is called a $B_{h}[g]$ set if for every $n\in\mathbb{N}$ the equation $n=a_{1}+\ldots+a_{h}$ has at most $g$ different solutions with $a_{1}\leq\cdots\leq a_{h}$ being elements of $A$. The Sidon sets are $B_{2}[1]$ sets.

Define $F_{h}(n,g)$ as the size of the largest $B_{h}[g]$ set contained in the interval $[1,n]$. Whereas it is known that $F_{2}(n,1)=n^{{1/2}}+O(n^{{5/16}})$[3, p. 85], no asymptotical results are known for $g>1$ or $h>2$ [2].

Every finite set has a rather large $B_{h}[1]$ subset. Komlós, Sulyok, and Szemerédi[4] proved that in every $n$-element set there is a $B_{h}[1]$ subset of size at least $cF_{h}(n,1)$ for $c=\tfrac{1}{8}(2h)^{{-6}}$. For Sidon sets Abbott[1] improved that to $c=2/25$. It is not known whether one can take $c=1$.

The infinite $B_{h}[g]$ sets are understood even worse. Erdős [3, p. 89] proved that for every infinite Sidon set $A$ we have $\liminf_{{n\to\infty}}(n/\log n)^{{-1/2}}\left\lvert A\cap[1,n]\right\rvert<C$ for some constant $C$. On the other hand, for a long time no example of a set for which $\left\lvert A\cap[1,n]\right\rvert>n^{{1/3+\epsilon}}$ for some $\epsilon>0$ was known. Only recently Ruzsa[6] used an extremely clever construction to prove the existence of a set $A$ for which $\left\lvert A\cap[1,n]\right\rvert>n^{{\sqrt{2}-1-\epsilon}}$ for every $\epsilon>0$ and for all sufficiently large $n$.

For an excellent survey of Sidon sets see [5].

# References

- 1 Harvey Leslie Abbott. Sidon sets. Canad. Math. Bull., 33(3):335–341, 1990. Zbl 0715.11004.
- 2 Ben Green. $B_{h}[g]$ sets: The current state of affairs. http://www.dpmms.cam.ac.uk/ bjg23/papers/bhgbounds.dvi, 2000.
- 3 Heini Halberstam and Klaus Friedrich Roth. Sequences. Springer-Verlag, second edition, 1983. Zbl 0498.10001.
- 4 János Komlós, Miklos Sulyok, and Endre Szemerédi. Linear problems in combinatorial number theory. Acta Math. Acad. Sci. Hung., 26:113–121, 1975. Zbl 0303.10058.
- 5 Kevin O’Bryant. A complete annotated bibliography of work related to Sidon sequences. Electronic Journal of Combinatorics. http://arxiv.org/abs/math.NT/0407117.
- 6 Imre Ruzsa. An infinite Sidon sequence. J. Number Theory, 68(1):63–71, 1998. Available at http://www.math-inst.hu/ ruzsa/cikkek.html.

## Mathematics Subject Classification

11B05*no label found*11B34

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## Mian-Chowla question

If we can stop talking about elliptical spaces in hypothetically large n-dimensional space and curvature tensors of antitime for a minute, I would like to ask a very mundane, perhaps even vulgar, question, and I will be grateful to anyone who doesn't mind to step down from the usual lofty planes to such a low level of inquiry for a minute.

Why does the Mian-Chowla sequence go 1, 2, 4, 8, 13, 21, 31, ... (A5282)? Why couldn't it go, say, 1, 2, 3, ... ? To rule out 3 the only thing I can come up with is making the sequence 0, 1, 2, 4, ... but then I still can't rule out 7 to favor 8. Have I missed something very basic here?

## Re: Mian-Chowla question

Isn't is just because you would than have 1+3=2+2=4, so those two sums of sequence entries wouldn't be distinct?

Cam

## Re: Mian-Chowla question

For those of us not in th know, would someone be so kind as to define the Mian-Chowla sequence? Preferrably, make this definition an entry for the benefit of the beknighted and bewildered of future generations.

## Re: Mian-Chowla question

The definition that is repeated by many sources roughly goes like this:

a_1 = 1. For n > 1, using the greedy algorithm, choose for a_n the smallest integer such that each a_i + a_j for 0 < i <= n and 0 < j <= n is unique (the pairwise sums).

Some definitions also specify that i = j is not considered, others add that maybe i = j is allowed when also i = j = n.

From what I can tell, the original definition is in a paper in an Indian journal, but since I can't read Indian, I don't even dare look up that paper.

As a woman, and uninterested in knowledge encryption as so many men are, I can admit that I don't understand exactly how the greedy algorithm fits into this. I understand how it applies to making change given a set of coin or bill currency, but I'm not sure how it works here.

At the very least I have to applaud PrimeFan's courage in admitting to not understanding something. Such an admission doesn't make you any less of a man.

## Re: Mian-Chowla question

I certainly don't mean to encrypt any knowledge. CompositeFan has pretty much correctly recapitulated what is most often repeated about the Mian-Chowla sequence.

But her incorrect remark about the "Indian language" (of which there are many) leads me to believe that the journal in question might be in English after all.

As for gender politics, I don't care to comment on that.

## Re: Mian-Chowla question; replied to mathcam

Isn't is just because you would than have 1+3=2+2=4, so those two sums of sequence entries wouldn't be distinct?

Cam

That would be true if i = j is acceptable as a pairwise sum. I'm hoping the original journal paper is in English and explains this in a little more detail.

## Re: Mian-Chowla question; replied to mathcam

It has to be. Otherwise you spin your wheels in the dirt for like, forever. The i != j in the Guy book is a mistake.