Erdos Problem #30 $1,000 Prize

The Sidon Set Conjecture

How large can a set of integers be if all pairwise sums are distinct? A fundamental question connecting number theory, combinatorics, and coding theory.

The Question

What is the maximum size of a Sidon set (B_2 sequence) contained in {1, 2, ..., n}? The best constructions give roughly sqrt(n) elements, but the exact constant remains unknown.

Explore the problem

Part 1

What is a Sidon Set?

A Sidon set (also called a B_2 sequence) is a set of positive integers with a remarkable property: every pairwise sum is unique. Named after the Hungarian mathematician Simon Sidon, these sets appear throughout mathematics and have surprising applications.

Sidon Set (B_2 Sequence)

A set S of positive integers is a Sidon set if for all a, b, c, d in S:

a + b = c + d implies {a, b} = {c, d}

In other words: all pairwise sums a + b (where a ≤ b are both in S) are distinct.

Example: The set {1, 2, 5, 10}

{1, 2, 5, 10

All pairwise sums are distinct:

1+1=2, 1+2=3, 1+5=6, 1+10=11 2+2=4, 2+5=7, 2+10=12 5+5=10, 5+10=15 10+10=20

All 10 sums {2, 3, 4, 6, 7, 10, 11, 12, 15, 20} are different. This is a Sidon set!

Why "All Pairwise Sums Distinct"?

The key insight is that if two different pairs give the same sum, we can "untangle" them. For example, if a + b = c + d with {a,b} different from {c,d}, then:

a + b = c + d implies a - c = d - b

This creates unwanted additive structure. Sidon sets avoid this entirely — they are "additively independent" in a precise sense.

Part 2

Build Your Own Sidon Set

Sidon Set Explorer

Click numbers to add them to your set. Watch for conflicts when two pairs have the same sum!

Click to select numbers (1-40):

Set Size

sqrt(40) ~ 6.3

Distinct Sums

of 0 pairs

Is Sidon Set?

Yes

No conflicts

Pairwise Sums (hover to see pair):

Select at least 2 numbers...

Part 3

The Central Question

Let F(n) denote the maximum size of a Sidon set contained in {1, 2, ..., n}. The fundamental question is: how does F(n) grow as n increases?

The Erdos Conjecture

Determine the exact asymptotic behavior of F(n). Specifically, what is the value of:

lim (n -> infinity) F(n) / sqrt(n) = ?

We know this limit exists and lies between 1 and sqrt(2).

What We Know

Through clever counting arguments and probabilistic methods, we have established bounds:

Current Bounds Gap Remains Open

Lower Bound

sqrt(n) - O(n^0.25)

≤ F(n) ≤

Upper Bound

sqrt(n) + O(n^0.25)

The exact coefficient of sqrt(n) remains unknown — this is worth $1,000!

Part 4

Singer's Construction

One of the most elegant constructions of Sidon sets comes from finite field theory. James Singer discovered in 1938 that perfect difference sets give optimal Sidon sets.

Singer Construction (using finite fields)

Let q be a prime power. Consider the finite field GF(q^2).

1. Take the multiplicative group of GF(q^2), which has order q^2 - 1
2. Find a primitive root g (generator of the multiplicative group)
3. The set S = {i : g^i is in some specific subfield structure}
4. This gives a Sidon set of size q + 1 in {0, 1, ..., q^2 + q}

Example: q = 3 (Smallest non-trivial case)

With q = 3, we get a Sidon set of size q + 1 = 4 in {0, 1, ..., 12}:

{0, 1, 3, 9

Or equivalently shifted: {1, 2, 4, 10} in {1, ..., 13}

Why Does It Work?

The magic comes from the algebraic structure of finite fields. The differences between elements of a Singer difference set cover each non-zero residue exactly once. This "perfect difference" property directly implies the Sidon property.

Perfect Difference Set

A set D of size k in Z_n is a perfect difference set if every non-zero element of Z_n can be expressed as a difference d_i - d_j (mod n) in exactly one way.

Perfect difference sets are automatically Sidon sets!

Part 5

Why Sidon Sets Matter

Sidon sets appear in surprising places across mathematics and engineering. Their "no repeated sums" property makes them ideal for avoiding interference.

Coding Theory

Sidon sets yield error-correcting codes. The distinct-sums property ensures codewords stay well-separated, enabling error detection.

Signal Processing

In radar and sonar, Sidon sets create signals with optimal autocorrelation properties, minimizing interference.

Additive Combinatorics

Sidon sets are the "opposite" of arithmetic progressions — maximally avoiding additive structure, a central theme in the field.

Fourier Analysis

Sidon sets have remarkable properties under the Fourier transform, connecting to harmonic analysis and analytic number theory.

Generalizations

The Sidon set concept extends naturally:

B_h sequences: Sets where all h-fold sums are distinct
B_2[g] sequences: Each sum appears at most g times
Infinite Sidon sets: Study of density in the integers
Sidon sets in groups: Generalizations to non-abelian settings

Part 6

The Road Ahead

Despite over 80 years of research since Sidon first studied these sets in the 1930s, the exact asymptotic formula remains elusive. The $1,000 prize awaits whoever can determine the precise constant.

"A problem worthy of attack proves its worth by fighting back."

- Paul Erdos

Key Open Questions

Is F(n) = sqrt(n) + o(sqrt(n))? (Does the main term have coefficient 1?)
Can we close the gap in the error term below O(n^0.25)?
Are there constructions beating Singer's for infinitely many n?
What is the structure of near-optimal Sidon sets?

The problem beautifully illustrates how simple-sounding questions about integers can lead to deep connections across mathematics. Whether you approach it through algebra, analysis, probability, or computation, the Sidon set conjecture continues to reward exploration.