Skip to main content
added 525 characters in body
Source Link
Emil Jeřábek
  • 47.8k
  • 4
  • 151
  • 209

The minimal number of such Sidon sets is $(1+o(1))\sqrt N$.

On the one hand, any Sidon set in $[0,N]$ has size at most $\sqrt N+O(\sqrt[4]N)$ (due to Erdős and Turán), hence the minimal number of Sidon sets that cover $[0,N]$ is at least $\sqrt N+O(\sqrt[4]N)$. More precisely, Lindström’s bound implies that one needs at least $\sqrt N-\sqrt[4]N$ sets.

For the upper bound, observe that if $S$ is any Sidon set, then the translates of $S$ are nearly disjoint: $|(S+a)\cap(S+b)|\le1$ for any $a\ne b$. (Sidon sets are Golomb rulers, but if $u\ne v$ belong to $(S+a)\cap(S+b)$, then $u-v$ is the difference of two different pairs of elements of $S$.) Thus, if $|S|=s$, then the $s$ sets $S-a$ for $a\in S$ have only the element $0$ in their pairwise intersections, and as such cover $s^2-s+1$ distinct elements.

This holds not just for Sidon sets in $\mathbb Z$ (where we have an issue that some elements covered by the translates stick out of $[0,N]$), but also for Sidon sets in any finite abelian group. In particular, let $p\sim\sqrt N$ be the least odd prime power such that $m=p^2+p+1>N$, and let $S$ be a Sidon set of size $p+1$ in the cyclic group $C_m$, constructed by Singer. Then the $p+1$ translates $S-a$ for $a\in S$ (computed in $C_m$, i.e., modulo $m$) cover all $(p+1)^2-(p+1)+1=m$ elements of $C_m$. If we identify $C_m$ with $[0,m)$, then these sets are also Sidon sets in $\mathbb Z$, and they cover $[0,m)\supseteq[0,N]$.

The minimal number of such Sidon sets is $(1+o(1))\sqrt N$.

On the one hand, any Sidon set in $[0,N]$ has size at most $\sqrt N+O(\sqrt[4]N)$ (due to Erdős and Turán), hence the minimal number of Sidon sets that cover $[0,N]$ is at least $\sqrt N+O(\sqrt[4]N)$. More precisely, Lindström’s bound implies that one needs at least $\sqrt N-\sqrt[4]N$ sets.

For the upper bound, observe that if $S$ is any Sidon set, then the translates of $S$ are nearly disjoint: $|(S+a)\cap(S+b)|\le1$ for any $a\ne b$. (Sidon sets are Golomb rulers, but if $u\ne v$ belong to $(S+a)\cap(S+b)$, then $u-v$ is the difference of two different pairs of elements of $S$.) Thus, if $|S|=s$, then the $s$ sets $S-a$ for $a\in S$ have only the element $0$ in their pairwise intersections, and as such cover $s^2-s+1$ distinct elements.

This holds not just for Sidon sets in $\mathbb Z$, but also for Sidon sets in any finite abelian group. In particular, let $p\sim\sqrt N$ be the least odd prime power such that $m=p^2+p+1>N$, and let $S$ be a Sidon set of size $p+1$ in the cyclic group $C_m$, constructed by Singer. Then the $p+1$ translates $S-a$ for $a\in S$ (computed in $C_m$, i.e., modulo $m$) cover all $(p+1)^2-(p+1)+1=m$ elements of $C_m$. If we identify $C_m$ with $[0,m)$, then these sets are also Sidon sets in $\mathbb Z$, and they cover $[0,m)\supseteq[0,N]$.

The minimal number of such Sidon sets is $(1+o(1))\sqrt N$.

On the one hand, any Sidon set in $[0,N]$ has size at most $\sqrt N+O(\sqrt[4]N)$ (due to Erdős and Turán), hence the minimal number of Sidon sets that cover $[0,N]$ is at least $\sqrt N+O(\sqrt[4]N)$. More precisely, Lindström’s bound implies that one needs at least $\sqrt N-\sqrt[4]N$ sets.

For the upper bound, observe that if $S$ is any Sidon set, then the translates of $S$ are nearly disjoint: $|(S+a)\cap(S+b)|\le1$ for any $a\ne b$. (Sidon sets are Golomb rulers, but if $u\ne v$ belong to $(S+a)\cap(S+b)$, then $u-v$ is the difference of two different pairs of elements of $S$.) Thus, if $|S|=s$, then the $s$ sets $S-a$ for $a\in S$ have only the element $0$ in their pairwise intersections, and as such cover $s^2-s+1$ distinct elements.

This holds not just for Sidon sets in $\mathbb Z$ (where we have an issue that some elements covered by the translates stick out of $[0,N]$), but also for Sidon sets in any finite abelian group. In particular, let $p\sim\sqrt N$ be the least odd prime power such that $m=p^2+p+1>N$, and let $S$ be a Sidon set of size $p+1$ in the cyclic group $C_m$, constructed by Singer. Then the $p+1$ translates $S-a$ for $a\in S$ (computed in $C_m$, i.e., modulo $m$) cover all $(p+1)^2-(p+1)+1=m$ elements of $C_m$. If we identify $C_m$ with $[0,m)$, then these sets are also Sidon sets in $\mathbb Z$, and they cover $[0,m)\supseteq[0,N]$.

added 525 characters in body
Source Link
Emil Jeřábek
  • 47.8k
  • 4
  • 151
  • 209

The minimal number of such Sidon sets is $\Theta(\sqrt N)$$(1+o(1))\sqrt N$.

On the one hand, any Sidon set in $[0,N]$ has size at most $\sqrt N+O(\sqrt[4]N)$ (due to Erdős and Turán), hence the minimal number of Sidon sets that cover $[0,N]$ is at least $\sqrt N+O(\sqrt[4]N)$. More precisely, Lindström’s bound implies that one needs at least $\sqrt N-\sqrt[4]N$ sets.

OnFor the other handupper bound, let $p$ be the least prime larger thanobserve that if $\sqrt{N/2}$$S$ is any Sidon set, and let $$S=\{2pk+(k^2\bmod p):0\le k<p\}$$ bethen the translates of Erdős–Turán Sidon set$S$ are nearly disjoint: $|(S+a)\cap(S+b)|\le1$ for any $a\ne b$. (=Sidon sets are Golomb ruler)rulers, but if $u\ne v$ belong to $(S+a)\cap(S+b)$, then $u-v$ is the difference of two different pairs of elements of $S$. Then) Thus, if $|S|=s$, then the shifted$s$ sets $$(S+a)\cap[0,N],\qquad -p\le a<2p,$$ cover $[0,N]$$S-a$ for $a\in S$ have only the element $0$ in their pairwise intersections, and as such cover $s^2-s+1$ distinct elements.

This holds not just for Sidon sets in $\mathbb Z$, but also for Sidon sets in any element offinite abelian group. In particular, let $[0,N]\subseteq[0,2p^2)$ can$p\sim\sqrt N$ be written as $2pk+l$ wherethe least odd prime power such that $k<p$$m=p^2+p+1>N$, and let $l<2p$$S$ be a Sidon set of size $p+1$ in the cyclic group $C_m$, andconstructed by Singer. Then the difference between $l$ and$p+1$ translates $k^2\bmod p$ is between$S-a$ for $-p$ and$a\in S$ $2p$(computed in $C_m$, i. This gives a coveringe., modulo $m$) cover all $(p+1)^2-(p+1)+1=m$ elements of $[0,N]$ by$C_m$. If we identify $3p\sim 3\sqrt{N/2}$$C_m$ with $[0,m)$, then these sets are also Sidon sets in $\mathbb Z$, and they cover $[0,m)\supseteq[0,N]$.

The minimal number of such Sidon sets is $\Theta(\sqrt N)$.

On the one hand, any Sidon set in $[0,N]$ has size at most $\sqrt N+O(\sqrt[4]N)$ (due to Erdős and Turán), hence the minimal number of Sidon sets that cover $[0,N]$ is at least $\sqrt N+O(\sqrt[4]N)$.

On the other hand, let $p$ be the least prime larger than $\sqrt{N/2}$, and let $$S=\{2pk+(k^2\bmod p):0\le k<p\}$$ be the Erdős–Turán Sidon set (= Golomb ruler). Then the shifted sets $$(S+a)\cap[0,N],\qquad -p\le a<2p,$$ cover $[0,N]$, as any element of $[0,N]\subseteq[0,2p^2)$ can be written as $2pk+l$ where $k<p$ and $l<2p$, and the difference between $l$ and $k^2\bmod p$ is between $-p$ and $2p$. This gives a covering of $[0,N]$ by $3p\sim 3\sqrt{N/2}$ Sidon sets.

The minimal number of such Sidon sets is $(1+o(1))\sqrt N$.

On the one hand, any Sidon set in $[0,N]$ has size at most $\sqrt N+O(\sqrt[4]N)$ (due to Erdős and Turán), hence the minimal number of Sidon sets that cover $[0,N]$ is at least $\sqrt N+O(\sqrt[4]N)$. More precisely, Lindström’s bound implies that one needs at least $\sqrt N-\sqrt[4]N$ sets.

For the upper bound, observe that if $S$ is any Sidon set, then the translates of $S$ are nearly disjoint: $|(S+a)\cap(S+b)|\le1$ for any $a\ne b$. (Sidon sets are Golomb rulers, but if $u\ne v$ belong to $(S+a)\cap(S+b)$, then $u-v$ is the difference of two different pairs of elements of $S$.) Thus, if $|S|=s$, then the $s$ sets $S-a$ for $a\in S$ have only the element $0$ in their pairwise intersections, and as such cover $s^2-s+1$ distinct elements.

This holds not just for Sidon sets in $\mathbb Z$, but also for Sidon sets in any finite abelian group. In particular, let $p\sim\sqrt N$ be the least odd prime power such that $m=p^2+p+1>N$, and let $S$ be a Sidon set of size $p+1$ in the cyclic group $C_m$, constructed by Singer. Then the $p+1$ translates $S-a$ for $a\in S$ (computed in $C_m$, i.e., modulo $m$) cover all $(p+1)^2-(p+1)+1=m$ elements of $C_m$. If we identify $C_m$ with $[0,m)$, then these sets are also Sidon sets in $\mathbb Z$, and they cover $[0,m)\supseteq[0,N]$.

Source Link
Emil Jeřábek
  • 47.8k
  • 4
  • 151
  • 209

The minimal number of such Sidon sets is $\Theta(\sqrt N)$.

On the one hand, any Sidon set in $[0,N]$ has size at most $\sqrt N+O(\sqrt[4]N)$ (due to Erdős and Turán), hence the minimal number of Sidon sets that cover $[0,N]$ is at least $\sqrt N+O(\sqrt[4]N)$.

On the other hand, let $p$ be the least prime larger than $\sqrt{N/2}$, and let $$S=\{2pk+(k^2\bmod p):0\le k<p\}$$ be the Erdős–Turán Sidon set (= Golomb ruler). Then the shifted sets $$(S+a)\cap[0,N],\qquad -p\le a<2p,$$ cover $[0,N]$, as any element of $[0,N]\subseteq[0,2p^2)$ can be written as $2pk+l$ where $k<p$ and $l<2p$, and the difference between $l$ and $k^2\bmod p$ is between $-p$ and $2p$. This gives a covering of $[0,N]$ by $3p\sim 3\sqrt{N/2}$ Sidon sets.