All Questions
Tagged with sumset additive-combinatorics
32
questions
2
votes
2
answers
60
views
Regarding scaling in sumsets
Let $A$ be a finite subset of $\mathbb{N}$. We denote the set $\{a_1 +a_2: a_1, a_2\in A\}$ as $2A$. We call the quantity $\sigma[A]:= |2A|/|A|$ as the doubling constant of $A$, and this constant can ...
- 971
0
votes
0
answers
67
views
What is the maximum range of a convex finite additive 2-basis of cardinality k?
Conjecture:
Given any $d \in \mathbb{Z}_{\geq 2}$ and $k=2d-2$, we have \begin{align*}
\max \{ n : (\exists &f \in \{ \mathbb{Z}_{\geq 0} \to \mathbb{Z}_{\geq 0} \})\\ &[((\forall i \in \...
- 115
1
vote
1
answer
100
views
How many subsets $S$ of integer interval $[0,n]$ such that $n, n-1 \not \in S+S$?
Conjecture:
Given any $n \in \mathbb{Z}_{\geq 0}$, we have $$|\{S : (S \subseteq [0,n]) \land (n, n-1 \not \in S+S)\}| = F(n+2),$$ where $F$, the sequence of Fibonacci numbers, is given by $F(j) = F(...
- 115
0
votes
0
answers
41
views
Is this true for a sumset?
We let $A,B\subseteq \mathbb{Z}$ such that $|A|=|B|=n$. I am trying to show that
$|A+B|\ge 2n-4$ for large $n$
where we define $A+B=\{a+b:a\in A, b\in B\}$.
If this is not true, I'd like to see a ...
user931598
0
votes
0
answers
64
views
Generating restricted finite additive $2$-bases from doubly-eager bit-strings
A bit-string is any finite sequence of $1$s and $0$s. For example, $1011011$, $1011010$, and $000110$ are bit-strings.
In this post, I will refer to bit-strings as strings, to be concise.
I now ...
- 115
0
votes
1
answer
90
views
How many subsets $S$ of integer interval $[0,n]$ such that $k \not \in S+S$?
After a bit of experimentation, I thought of the following conjecture:
Given any $n \in \mathbb{Z}_{\geq 0}$ and $k \in [0,2n]$, we have $$|\{S : (S \subseteq [0,n]) \land (k \not \in S+S)\}| = 2^{|n-...
- 115
0
votes
2
answers
63
views
Sumsets : optimality of two basic inequalities
One can prove that for $A$ and $B$ subsets of $\mathbb{Z}$ one has
$$
|A|+|B|-1 \leq |A+B| \leq |A|\times |B|
$$
where $A+B = \left\{ a+b,a\in A \text{ and } b \in B \right\}$ and, for $X$ a finite ...
- 4,067
11
votes
1
answer
374
views
If an infinite set $S$ of positive integers is equidistributed, is $S+S$ also equidistributed?
By $S+S$, I mean $\{x+y,$ with $x,y \in S\}$. By equidistributed, I mean equidistributed in residue classes, as defined here (the definition is very intuitive, and examples of such equidistributed ...
- 3,645
3
votes
1
answer
176
views
Determine the structure of all finite sets $A$ of integers such that $|A| = k$ and $|2A| = 2k + 1$.
An exercise in Nathanson's text: Additive Number Theory, Inverse problems and the geometry of sumsets is the following (Excercise 16, P.No.37):
Determine the structure of all finite sets $A$ of ...
- 622
2
votes
1
answer
114
views
Set $A$ with $|2A| \geq 100|A|$ but $|3A| < 1000|A|$
Let $kA$ denote the sumset $\{ a_1 + \cdots + a_k \mid a_i \in A \}$.
I want to show that $|2A| \geq 100|A|$ does not imply $|3A| \geq 1000|A|$. [I know this to be true experimentally, but am ...
- 1,179
5
votes
1
answer
218
views
Sum-free sets in finite groups
Suppose $G$ is a group, $S \subset G$. Let’s call $S$ sum-free iff $\forall a, b \in S$ we have $ab \notin S$. Do there exist such $\epsilon > 0$, such that every sufficiently large finite group $G$...
- 15.7k
4
votes
0
answers
138
views
Sidon sets in finite groups
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 ...
- 15.7k
2
votes
1
answer
111
views
Maximal size of bounded “sparse” sets of natural numbers
Let’s call $A \subset \mathbb{N}$ sparse iff for all quadruples of distinct numbers $(a, b, c, d)$ from $A$ it is true, that $a + b \neq c + d$. What is the maximal possible size of a sparse set $A$, ...
- 15.7k
2
votes
3
answers
123
views
Minimum number of integers $a_1,....,a_m$ needed to express $2,...,n$ as $a_i + a_j$
I am interested in the following problem. An arbitrary integer $n \geq 2$ is given. Find the minimum integer $m \geq 1$ such that there exist integers $0\lt a_1\lt a_2\lt \cdots \lt a_m$ satisfying ...
2
votes
2
answers
125
views
What is the probability that $\exists N \in \mathbb{N}$ such that $\forall n > N$, $2n \in C + C$?
Suppose $C$ is a random subset of $\mathbb{N}\setminus\{1, 2\}$, such that $\forall n \in \mathbb{N}\setminus\{1, 2\}$, $P(n \in C) = \frac{1}{\ln(n)}$ and the events of different numbers belonging to ...
- 15.7k