Sidon sets and difference sets

Sidon and B_h-sets (bounds, counts, greedy and thick constructions, isolated sums, the Sidon ideal), Golomb rulers, difference bases, cyclic and perfect difference sets including Singer's theorem, and difference sets of sparse sets.

• B_h-sets
• Constructions of thick B_h-sets
• Difference bases
• Difference sets of sparse sets
• Greedy B_h-sets
• Sidon sets
• Golomb rulers
• Number of Sidon sets
• Sidon ideal
• Sidon sets and perfect difference sets
• Sidon sets meeting every infinite progression
• Upper bounds for Sidon sets

TheoremSinger's difference set theorem#✓fully proved

For every prime power \(q\), there is a subset \(D\) of the cyclic group \(\mathbb{Z}/(q^2 + q + 1)\mathbb{Z}\) with \(q + 1\) elements such that every nonzero element \(x\) of this group can be written as \(x = a - b\) for exactly one ordered pair \((a, b)\) of elements of \(D\).

public theorem singer_cyclic_difference_set_exists
    (q : ℕ) (hq : IsPrimePow q) :
    ∃ D : Finset (ZMod (q ^ 2 + q + 1)), D.card = q + 1 ∧
      ∀ x : ZMod (q ^ 2 + q + 1), x ≠ 0 →
        ∃! ab : D × D, (ab.1 : ZMod (q ^ 2 + q + 1)) -
          (ab.2 : ZMod (q ^ 2 + q + 1)) = x

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.