All Questions
Tagged with sumset combinatorics
21
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
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
86
views
Instead of "sum-free" sets, consider sets where $S\subset S+S$. This is trivially satisfied when $0 \in S$. Is there a subset of $S$ with sum $0$?
As an example, here is a set $S$ with $S\subset S+S$ and $|S|=8$ and having subsets of four elements whose sum is zero, but no smaller subsets have this property: $S=\{-14,-13,-11,-7,1,2,4,8\}$. This ...
- 11
2
votes
0
answers
58
views
Which sets of $n-1$ non-multiples of $n$ can't make a multiple of $n$ using $+,-$?
This is a follow up to my previous question (see linked question).
In short, there it is shown that if $n$ is prime, then any set can make it.
I want to characterize sets $\mathbb A_n$ of multisets $...
- 12.5k
7
votes
1
answer
154
views
For any $n-1$ non-zero elements of $\mathbb Z/n\mathbb Z$, we can make zero using $+,-$ if and only if $n$ is prime
Inspired by Just using $+$ ,$-$, $\times$ using any given n-1 integers, can we make a number divisible by n?, I wanted to first try to answer a simpler version of the problem, that considers only two ...
- 12.5k
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
1
vote
2
answers
98
views
How small can "spanning sumsets" of $[n]$ be?
Let $[n]$ denote the natural numbers $1$ through $n$. Let's say a subset $X \subset [n]$ is a spanning sumset if $\{x+y: x,y \in X\} = [n] \setminus \{1\}$. I'm interested in studying spanning sumsets ...
- 12.8k
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
1
answer
67
views
Prove that if $|A+A| \leq K|A|$ then $2A - 2A$ is a $K^{16}$-approximate group.
Let $A$ be a finite subset of an abelian group, $G$ (call the operation addition). We say $A$ is a $K$-approximate group if:
1) $e_G \in A$
2) $A^{-1} = \{ a^{-1} \mid a \in A \} = A$
3) $\exists X ...
- 2,683
4
votes
0
answers
149
views
Where can I find this article by I. Ruzsa?
Title says it all. Have tried googling and my college library, but no success so far.
I. Ruzsa, On the cardinality of $A + A$ and $A − A$. In Combinatorics (Keszthely, 1976), Coll. Math. Soc. Bolyai ...
- 753
0
votes
0
answers
65
views
How many consecutive numbers in a sumset?
Let $A=\{a_1,a_2,\dots,a_n\,\vert\,a_1\lt a_2\lt\cdots\lt a_n\}$ be a finite subset of $\Bbb N$ with sumset $$A+A=\{a_i+a_j\,\vert\, a_i,a_j\in A\}$$ What is the longest possible chain of consecutive ...
- 3,226