A set $S \subseteq \mathbb{Z}/p\mathbb{Z}$ is called a Sidon set if given $a, b, c, d \in S$ and $a+ b = c+ d$, then $\{a, b\} = \{c,d\}$. I was interested in knowing about the largest possible Sidon set $\mathbb{Z}/p\mathbb{Z}$ has (Here $p$ is prime). What are known about the largest possible Sidon sets contained in $\mathbb{Z}/p\mathbb{Z}$? Are there any explicit examples or constructive proof for `large' Sidon sets? Any information is appreciated.
$\begingroup$
$\endgroup$
1
-
4$\begingroup$ The start of Section 3 of this paper describes some bounds, due to Erdos and Turan. This blog post by Gowers discusses Sidon sets close to the upper bound. $\endgroup$– Gabe ConantDec 11, 2019 at 21:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I am not sure of your level of knowledge of Sidon sets, but a good reference is O' Bryant's survey (see section 4.3 in particular) which contains several constructions in the integers. If you are already aware of the three constructions then as far as I know, we do not know much more. We do know if you replace prime with a number of the form $n = p^2 - 1$, then the largest Sidon set of $\mathbb{Z}/n\mathbb{Z}$ has size $(1 + o(1))\sqrt{n}$, thanks to Bose and Chowla (see the cited survey for details).
We can always make a large Sidon subset of $\mathbb{Z}/p\mathbb{Z}$ from one in the integers as follows: Given $N < p/2$ and a Sidon Set $$A \subset\{1 , \ldots , N\},$$ embed $A$ into $\mathbb{Z}/p\mathbb{Z}$ via the projection map. With the constructions in the aforementioned survey this gives a Sidon subset of $\mathbb{Z}/p\mathbb{Z}$ of size $(1 + o(1))\sqrt{p/2}$.
On the other hand, there is an easy counting that gives a Sidon subset of $\mathbb{Z}/p\mathbb{Z}$ has size at most $(1 + o(1))\sqrt{p}$.
Thus the largest Sidon subset, $A$, of $\mathbb{Z}/p\mathbb{Z}$ has size $$(1 + o(1))\sqrt{p/2} \leq |A| \leq (1 + o(1))\sqrt{p}.$$ Closing the gap in the constant is an interesting question.
