All Questions
Tagged with sumsets additive-combinatorics
72 questions
4
votes
2
answers
206
views
Lower bounding a sumset quantity
Given $A,B \subset[0,...,d]^n$ such that $A \cap B = \phi$. Can we show
$$ |(2A \cup 2B) \triangle (A + B)| \geq \Omega_d({\rm poly}(|A|,|B|))$$
where $2A = A+A, 2B = B+B$ and we are taking the ...
- 343
5
votes
0
answers
185
views
Gaps in sumsets and difference sets
a) Let $S\subset \{1,2,\dotsc,N\}$ be a fairly thick set (with at least $N^{1-\epsilon}$ elements, say). Suppose that the intersection of, say,
$$3 S - 3 S = \{a_1+a_2+a_3-(a_4+a_5+a_6): a_1,\dotsc,...
- 20.2k
0
votes
0
answers
87
views
Asymptotic behavior of sumsets of squares with restricted congruence conditions
Recall that if $A$ and $B$ are both subsets of the integers, then $A+B=\{a+b:a \in A,b \in B\}$.
Lagrange's four-square theorem states that if $A$ is the set of squares, then $4A=A+A+A+A=\mathbb{N}$.
...
- 101
7
votes
0
answers
177
views
Sumsets that contains many squares, Improvement on the bound
I'm being troubled by this problem on AoPS:
https://artofproblemsolving.com/community/c6h1998237p13955033
I searched for any literature related to it such as
Nguyen, Hoi H., and Van H. Vu., Squares ...
- 73
0
votes
1
answer
161
views
How to determine if a set is a sumset
Let $G$ be a commutative group (assume whatever you want on $G$ if needed. I am mainly interested in $G = \mathbb{Z}/n\mathbb{Z}$).
Let $k$ be a fixed integer.
Let $(a_1, \dots, a_{k^2})$ be a list of ...
- 527
6
votes
0
answers
176
views
Normality and small doubling
Suppose that $A$ is a finite, generating subset of a group $G$, and that $H$ is a subgroup such that $A^2$ is a union of left $H$-cosets; moreover, $H$ is maximal subject to this property. Is it true ...
- 23k
3
votes
0
answers
160
views
could $|2U+2V|$ be smaller than $|U-V|$?
I am interested in whether there are any conclusion/conterexample that the sum&difference of finite integer sets by more times is smaller than the sum&difference by less times.
The question I ...
- 31
0
votes
0
answers
50
views
Counting zero-sum subsets of a finite field with a particular form
Let $\mathbb{F}$ be a finite prime field of characteristic different than $2$ and $\beta \in \mathbb{F}$ a generator of the $2$-power order multiplicative subgroup of order $2^k$, so $\beta^{2^{k-1}} =...
- 3,058
25
votes
2
answers
3k
views
What is the minimal density of a set A such that A+A = N?
Thinking about the four square theorem and related questions, I found myself wondering: What is the minimal density of a set $A \subset \{0, 1, 2, ... \}$ such that $A + A = \mathbb{N}$?
What I know:
...
- 1,643
5
votes
1
answer
1k
views
Estimate of Minkowski sum
Let A $\subset [0:2]^n$, where $[0:2]=\{0,1,2\}$, then define $2A= \{ a+b\mid a,b \in A \}$. I wanted to know the best known lower-bound estimates for $|2A|$.
I intuitively expect that $|2A| \geq |A|^{...
- 343
15
votes
2
answers
752
views
Subsets of $(\mathbb{Z}/p)^{\times n}$
There seems to be some combinatorial fact that every subset $A$ of $G=(\mathbb{Z}/p)^{\times n}$ of cardinality $\frac{p^n-1}{p-1}+1$ containing $\vec{0}$ satisfies $(p-1)A=G$. ($p$ is a prime number....
- 153
1
vote
1
answer
350
views
Khovanskii's theorem on iterated sumsets
I was watching Gowers video lectures "Introduction to Additive Combinatorics" (my question is about the statement he made at the 21st minute) and came across wonderful theorem due to ...
- 330
2
votes
0
answers
189
views
Component-wise sums of permutations
Given a set $S$ containing all possible permutations of a vector $v = (1, 2, 3, ..., n-1, n)$, find the size of the set $P$, where $P$ is defined as the set of possible component-wise sums obtained by ...
- 21
59
votes
2
answers
4k
views
For a finite set A of positive reals, prove that the set A + A - A contains at least as many positive as negative elements
I am currently working on a proof that would need to use the following theorem that I cannot prove:
"Let $A$ be a finite set of positive real numbers. Then, the set $A + A - A$ contains at least ...
- 643
11
votes
2
answers
661
views
$\mathbb Z/p\mathbb Z=A\cup(A-A)$?
$\newcommand{\Z}{\mathbb Z/p\mathbb Z}$
Can one partition a group of prime order as $A\cup(A-A)$ where $A$ is a subset of the group, $A-A$ is the set of all differences $a'-a''$ with $a',a''\in A$, ...
- 23k
0
votes
0
answers
71
views
Bounds on these numbers
Let $[n]$ be the set of natural numbers $1,2,3 \cdots n$ and $k$ be a natural number. Define $S(n,k) = \# \{ A \subset [n] \mid \displaystyle\sum_{i \in A} i =k \}$. My question is; Are there any ...
- 271
5
votes
2
answers
268
views
Progressions in sumset or complement
Fix $\epsilon>0$.
For all large $N$, does there exist $A\subset [N]:=\{1,\dots,N\}$ such that both $A+A$ and $A^c:=[N]\setminus A$ lack arithmetic progressions of length $N^\epsilon$?
I am aware ...
- 3,499
0
votes
0
answers
60
views
How large must "weak Besicovitch" subsets of groups be?
Consider a group $G$; let call $A\subset G$ a weak Besicovitch subset whenever every element of $G$ can be written under the form $gh^{-1}$, where $g,h\in A$.
General question: how large must a weak ...
- 14.4k
9
votes
0
answers
265
views
If $A+A+A$ contains the extremes, does it contain the middle?
Let $b \ge 1$ and $A\subseteq [0,b]$ be a set of integers (all intervals will be of integers).
Write $hA := \underbrace{A + \ldots + A}_{h\text{ summands}} = \{ \sum_{i=1}^h a_i ~|~a_i \in A,\, \...
- 825
4
votes
2
answers
267
views
Existence of m infinite subsets in an arbitrary group such that all products of one element from each (in order) are distinct
Is it true that for every infinite group $G$ and every $m\in\mathbb{N}$ there are infinite subsets $A_0,\dots,A_{m-1}$ such that all the products $a_0\cdot\dots\cdot a_{m-1}$ with $a_i\in A_i$ are ...
- 73
0
votes
0
answers
125
views
An exercise about sum-product estimate
I am struggling with 1.11 exercise from the George Shakan "Discrete Fourier Transform".
Let $A \subset \mathbb{Z}/q\mathbb{Z}$ be any set not containing zero with $|A|>\sqrt2q^{5/8}$. ...
- 11
2
votes
0
answers
123
views
Restricted sumsets - the origins?
The sumset of the subsets $A$ and $B$ of an additively written group is defined by $A+B:=\{a+b\colon a\in A,\ b\in B\}$. The basic idea to add sets has been around since Cauchy at least.
Erdős and ...
- 23k
0
votes
0
answers
179
views
Additive energy and uniquely representable elements
Suppose that $A$ is a finite, nonempty set in an abelian group. If there is a group element with a unique representation as $a-b$ with $a,b\in A$, then none of $A-A$ and $2A$ are small:
$$ \min\{|A-A|,...
- 23k
0
votes
1
answer
207
views
Controlling iterated sum sets of "most" of $A+B$
I am reading Tao-Vu book on Additive combinatorics and came across the following lemma. I know that it is better to ask this question on MathStack but I asked few questions before and no one answered ...
- 330
16
votes
2
answers
2k
views
Sets that are not sum of subsets
Let $\mathcal P$ be the set of finite subsets of $\mathbb Z_{\geq 0}$ , each of them contains $0$. We say that $A \in \mathcal P$ is indecomposable if it is not $B+C$ (the sum set of $B,C$) with $B,C\...
- 30.6k
15
votes
1
answer
807
views
Explicit constant in Green/Tao's version of Freiman's Theorem?
Green and Tao's version of Freiman's theorem over finite fields (doi:10.1017/S0963548309009821) is as follows:
If $A$ is a set in $\mathbb{F}_2^n$ for which $|A+A| \leqslant K|A|$, then $A$ is ...
- 153
1
vote
1
answer
237
views
An intriguing inverse sumset problem
Start with a natural number $k$, and choose natural numbers $K=\{n_1,\ldots,n_k\}$ which are pairwise distinct. For each $1\leq j\leq k$, choose another integer $i_j$ such that $0\leq i_j\leq n_j$.
...
- 589
7
votes
1
answer
194
views
Trisecting $3$-fold sumsets, II: is the middle part ever thin?
This is a refined version of the question I asked yesterday.
Let $A$ be a finite set of integers with the smallest element $0$ and the largest element $l$. The sumset $C:=3A$ resides in the interval $[...
- 23k
6
votes
1
answer
155
views
Trisecting $3$-fold sumsets: is the middle part always thick?
Here is a truly minimalistic and seemingly basic question which should have a simple solution (I hope it does).
Let $A$ be a finite set of integers with the smallest element $0$ and the largest ...
- 23k
3
votes
0
answers
98
views
Origins of the ``baby Freiman'' theorem
It is a basic folklore fact from the area of additive combinatorics that a subset $A$ of an abelian group satisfies $|2A|<\frac32\,|A|$ if and only if $A$ is contained in a coset of a (finite) ...
- 23k
3
votes
1
answer
361
views
Prime gap distribution in residue classes and Goldbach-type conjectures
Update on 7/20/2020: It appears that conjecture A is not correct, you need more conditions for it to be true. See here (an answer to a previous MO question).
The general problem that I try to solve is ...
- 3,098
0
votes
1
answer
489
views
Congruential equidistribution, prime numbers, and Goldbach conjecture
Let $S$ be an infinite set of positive integers, $N_S(z)$ be the number of elements of $S$ less than or equal to $z$, and let
$$D_S(z, n, p)= \sum_{k\in S,k\leq z}\chi(k\equiv p\bmod{n}).$$
Here $\chi$...
- 3,098
0
votes
0
answers
167
views
General asymptotic result in additive combinatorics (sums of sets)
Let $S_1,\cdots,S_k$ be $k$ infinite sets of positive integers. Let $N_i(z)$ be the numbers of elements in $S_i$ that are less or equal to $z$. Let us further assume that
$$N_i(S) \sim \frac{a_i z^{...
- 3,098
5
votes
1
answer
218
views
Computational version of inverse sumset question
Let $p$ be prime and $\mathbb{F}_p$ the finite field with $p$ elements. Suppose we have a set $B\subseteq \mathbb{F}_p$ satisfying $|B|<p^{\alpha}$ for some $0<\alpha<1$ and there exists $A\...
user156885
4
votes
1
answer
280
views
Unique representation and sumsets
Let $A$ be a finite, nonempty subset of an abelian group, and let $2A:=\{a+b\colon a,b\in A\}$ and $A-A:=\{a-b\colon a,b\in A\}$ denote the sumset and the difference set of $A$, respectively.
If ...
- 23k
1
vote
1
answer
218
views
Average size of iterated sumset modulo $p-1$,
Given a prime $p$, what is the average size of the iterated sumset, $|kA|$, modulo $p-1$, with $p$ a prime, and $k$ given, with $A$ chosen at random?
You can pick any type of prime you like for $p$, ...
- 221
1
vote
1
answer
301
views
Does $g+A\subseteq A+A$ imply $g\in A$?
Suppose that $A$ is a subset of a (large) finite cyclic group such that $|A|=5$ and $|A+A|=12$. Given that $g$ is a group element with $g+A\subseteq A+A$, can one conclude that $g\in A$?
- 23k
10
votes
1
answer
287
views
Freiman inequality for projective space?
This question is suggested by some results in a paper I am writing. I would like to write it down there but want to make sure that it is not known or at least MO-hard.
Freiman's inequality states ...
- 30.6k
19
votes
4
answers
867
views
Size of sets with complete double
Let $[n]$ denote the set $\{0,1,...,n\}$. A subset $S\subseteq [n]$ is said to have complete double if $S+S=[2n]$. Let $m(n)$ be the smallest size of a subset of $[n]$ with complete double. My ...
- 30.6k
3
votes
0
answers
133
views
Is there some sort of formula for $t(S_n)$?
Let $G$ be a finite group. Define $t(G)$ as the minimal number, such that $\forall X \subset G$ if $|X| > t(G)$ and $\langle X \rangle = G$, then $XXX = G$.
Is there some sort of formula for $t(S_n)...
- 2,618
2
votes
0
answers
39
views
Weighted unrestricted Golomb rulers?
A set of integers
${\displaystyle A=\{a_{1},a_{2},...,a_{m}\}\quad a_{1}<a_{2}<...<a_{m}} $
is a Golomb ruler if and only if
${\displaystyle \forall i,j,k,l\in \left\{1,2,...,m\right\},a_{i}...
- 13.9k
6
votes
1
answer
262
views
Is there some sort of formula for $\tau(S_n)$?
Let $G$ be a finite group. Define $\tau(G)$ as the minimal number, such that $\forall X \subset G$ if $|X| > \tau(G)$, then $XXX = \langle X \rangle$.
Is there some sort of formula for $\tau(S_n)$, ...
- 2,618
3
votes
1
answer
146
views
Bounding the size of certain sumsets in the plane
Let $A$ be a finite set in $\mathbb{R}^2$ of $k^2$ elements and consider a set $B=\{x_1,x_2,x_3,x_4\}$ such that the points in $B$ are in general position (no three points on a line).
Question 1: Is ...
- 2,288
3
votes
1
answer
251
views
Are there unique additive decompositions of the reals?
Given $b\in \mathbb{R}_{>1}$ is there $U\subseteq\mathbb{R}_{\ge 0}$ such that $U+bU=\mathbb{R}_{\ge 0}$ and $(U-U)\cap b(U-U)=\{0\}$ (or equivalently: $u+bv=u'+bv' \implies u=u', v=v'$)?
Here is ...
- 5,103
19
votes
3
answers
1k
views
Decomposing a finite group as a product of subsets
My friend Wim van Dam asked me the following question:
For every finite group $G$, does there exist a subset $S\subset G$ such that $\left|S\right| = O(\sqrt{\left|G\right|})$ and $S\times S = G$? ...
- 9,833
2
votes
0
answers
137
views
The set of lengths of $nX$ gets larger and larger for every non-zero, non-empty, finite $X \subseteq \mathbf N$ with $0 \in X$
Let $H$ be a multiplicatively written monoid with identity $1_H$. Given $x \in H$, we take ${\sf L}_H(x) := \{0\}$ if $x = 1_H$; otherwise, ${\sf L}_H(x)$ is the set of all $k \in \mathbf N^+$ for ...
- 10.5k
3
votes
0
answers
65
views
What's known about $X$ when $|X(n) + X(n)| < kn$, $n \in \mathbb{N}$, absolute constant $k$?
Let $X$ be an infinite sequence of integers$$x_1 < x_2 < x_3 < \ldots,$$and let $X(n)$ be the set$$\{x_1, x_2, \ldots, x_n\}.$$
Question. What is known about $X$ when we have$$|X(n) + X(n)| &...
- 31
3
votes
1
answer
246
views
Limit measuring failure of sum-set cancellability
Suppose $A$, $B$ are finite sets of positive integers.
Let $$\mathcal{S}_n = \{C \subset [1,n] \, : \, A+C = B+C \}, $$ and denote $a_n = |\mathcal{S}_n|$.
Note that for any $X \in \mathcal{S}_n$ ...
- 265
1
vote
0
answers
119
views
Lower bound for sumset in discrete cube
Suppose $A\subset\{0,1\}^d$ for some $d\geq 1$. Then how large must $A+A=\{a+b:a,b\in A\}$ be?
4
votes
2
answers
427
views
How big must the sumset $A+A$ be if $A$ satisfies no translation-invariant equations of low height?
Suppose $A$ is a finite subset of an abelian group. If there is no solution to $ma+nb=(m+n)c$ with $0\leq m,n\leq M$, can we bound $|A+A|$ from below? I am interested if one can obtain bounds much ...
- 41