1
$\begingroup$

Suppose $G$ is a group, $S \subset G$. Let’s call $S$ a Sidon subset iff $\forall$ quadruples $(a, b, c, d)$ of distinct elements of $S$ we have $ab \neq cd$ (named after Simon Sidon who studied such subsets in $C_\infty$). Let’s define $Sid(G)$ as the maximal possible cardinality of a Sidon subset in $G$. Do there exist such $0<c<C<+\infty$, such that $c \leq \frac{Sid(G)}{\sqrt{|G|}} \leq C$ for any finite group $G$?

The existence of $C$ can be proved the following way:

If $S$ is a Sidon subset of $G$, then $|G| \geq |S^2| \geq \frac{|S|(|S| - 1)}{2}$, thus $C = \sqrt{2} + 1$ will work.

The only thing I know about $c$ is that Erdos proved such constant exist for finite cyclic groups $G$. But does it exist for all finite $G$?

This question on MSE

$\endgroup$
8
  • $\begingroup$ Did you try $S_n$? $\endgroup$
    – user6976
    Jan 15, 2020 at 3:08
  • 2
    $\begingroup$ The paper of Babai and Sos "Sidon Sets in Groups and Induced Subgraphs of Cayley Graphs" (European J. Comb. (1985) 6, pp.101-114) is highly relevant. $\endgroup$
    – Seva
    Jan 15, 2020 at 6:47
  • $\begingroup$ @Seva: This paper does not answer the question. Right? $\endgroup$
    – user6976
    Jan 16, 2020 at 10:10
  • 1
    $\begingroup$ Sets which meet the upper bound with equality are called planar difference sets, and are closely related to finite projective planes. I am not aware of work which addresses your question, but this might give you some additional terms to search for. $\endgroup$ Jan 17, 2020 at 16:45
  • 1
    $\begingroup$ @Seva: Apparently there is a gap. The constant lower bound is known for $Sid(G)/\sqrt[3]{|G|}$ and the constant upper bound is known for $Sid(G)/\sqrt{|G|}$, $\endgroup$
    – user6976
    Jan 19, 2020 at 2:22

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.