11
votes
Accepted
Size of sets with complete double
Let $S\subset [1,N]$ with $S+S=2N$. I will show that $S$ must have at least $(2.033 +o(1))\sqrt{N}$ elements for large $N$. The argument can certainly be improved, but I don't know what the right ...
- 43.7k
10
votes
Accepted
Sidon sets of $\mathbb{Z}/p\mathbb{Z}$
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 ...
- 2,283
8
votes
Accepted
Is this set of numbers independent/Sidon?
It was proved by Pisier (Arithmetic characterizations of Sidon sets) that a set $\Lambda \subset \mathbf{Z}$ is Sidon if and only if there is a constant $c$ such that any finite subset $A \subset \...
- 9,486
8
votes
Is this set of numbers independent/Sidon?
No, it is not.
By pigeonhole principle, an independent set $E$ has $O(\log x) $ elements not exceeding $x$: otherwise two subsets have equal sums (since there are $2^{|E\cap [1,x]|}$ subsets, and only ...
- 109k
8
votes
Size of sets with complete double
For a fixed $n$, you can solve the problem via integer linear programming. For $j \in [n]$, let binary decision variable $x_j$ indicate whether $j\in S$. For $0\le j_1\le j_2 \le n$, let binary ...
- 5,429
4
votes
Accepted
An extremal combinatorics problem
Taking Fedor Petrov's observation a little further, I believe the right question to ask is as follows:
$$ \text{What is the largest size of a $b$-separated Sidon set in the interval $[0,L]$?} $$
...
- 23k
4
votes
Accepted
Eccentricity in the number of representations for sets too large to be Sidon sets
There exists a set $A$ on $\{1,...,N\}$ where $ |A|\geq\frac{2}{\sqrt{3}}\sqrt{N}$ and $E(A)=o(N)$.
Let $B$ be a Sidon set on $\{1,...,n\}$. Let $C = \{3n+1-b | b\in B\}$. Let $A=B\cup C$.
Suppose $...
- 9,501
4
votes
Size of sets with complete double
Short answer: Such a set $S$ is known as a restricted additive basis.
As observed in comments, the general term to search for is [finite]
additive basis: a finite set $S \subset \mathbb{N}$ such that ...
- 4,219
3
votes
Accepted
Difference set of difference set
I’m assuming from the examples that you are only considering non-negative differences.
Let us first see what “as unique as possible” means. If the original set is $\{a_i:0\le i<n\}$, the set of ...
- 47.1k
3
votes
Size of sets with complete double
Note that any solution will be of the form $S=\{0,1,s_2,\cdots,s_j,n-1,n\}$ and then $S'=\{0,1,n-s_j,\cdots,n-s_2,n-s_1,n-1,n\}$ is also a solution. If $S=S'$ one might call it a symmetric solution. ...
- 30.1k
2
votes
An extremal combinatorics problem
(This answer is totally different from the one I posted several days ago, so I prefer to post it separately and not as a sort of an edit / appendix.)
It is well known that the largest Sidon subset of ...
- 23k
1
vote
Accepted
Unique representation and sumsets
One can have $|2A|$ as small as $2|A|$. Take $A = H \cup \{g\}$ where $H$ is a subgroup, $g \notin H$ and$g \neq -g$. Then $|A+A| = 2|A| + O(1)$ while
$g+H$ and $H - g$ all have a unique ...
- 2,283
1
vote
Lower bound for k-fold Sidon Sets
Cilleruelo, Javier, and Craig Timmons. "$k$-fold Sidon sets." arXiv:1310.5374 (2013).
Here is some lower-bound information as of about five years ago.
The conjecture is that $\sqrt{N}$ is a lower ...
- 151k
1
vote
$B_k[1]$ sets with smallest possible $m = \max B_k[1]$ for given $k$ and $n = \lvert B_k[1]\rvert$ elements
Since the question asks for exact smallest values, not bounds or asymptotics, it is likely to be a difficult problem.
First note that instead of taking sums of at most $k$ elements, we can take sums ...
- 4,219
Only top scored, non community-wiki answers of a minimum length are eligible