Questions tagged [sumsets]
The sumsets tag has no usage guidance.
108 questions
4
votes
2
answers
207
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
3
votes
1
answer
75
views
APs in sumsets of exponential growing sequences
I posted this initially on SE, but after I didn't found a particular reference on it, I decided it would be more appropriate to post it here. A friend shared this observation with me and I thought ...
- 73
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
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
-1
votes
1
answer
122
views
Is there another representation for the summation: $\sum_{j=1}^{N}\frac{a_j}{(c+a_j)(c+a_j+1)} $, how to reformulate that to keep $c$ out of the sum [closed]
Is there a closed form (without summation) for the summation or at least can I reformulate that so I keep $c$ out of the summation, for example, $c \sum_{n=1}^{N} f(a_n,b_n)$.
$$
\sum_{n=1}^{N}\frac{...
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
3
votes
1
answer
595
views
Euro2024-inspired scoring problem
Motivation. The Euro 2024 soccer football championship is in full swing, and the male part of my family are avid watchers. Right now the championship is in the group stage where every group member ...
- 48.9k
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
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
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
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
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
1
answer
133
views
Centroid of Minkowski sum
Let $A$ and $B$ be two compact convex subsets of $\mathbb{R}^n, n\geq 2$. Assume $x_A$ and $x_B$ are their respective centroid. If we form the Minkowski sum $C=A+B = \{x+y\mid x\in A, y\in B\}$, what ...
- 161
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
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
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
0
votes
0
answers
52
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
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
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
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
3
votes
2
answers
365
views
Sumsets with the property "$A+B=C$ implies $A=C-B$"
Let $(G,+)$ be an abelian group and $A$, $B$ and $C$ be finite subsets of $G$ with $A+B=C$. One may conclude that $A\subset C-B$. However, $A$ need not be equal to $C-B$. What is a necessary and ...
- 429
5
votes
2
answers
270
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
2
votes
1
answer
268
views
Different sum combinations of $L$ identical lists of consecutive natural numbers
Given $L$ variables $k_i$ where each $k_{i} \in \{1, 2, 3, \ldots, N\}$ I want to obtain how many different sums $k_{1}+k_{2}+\cdots+k_{L}$ are generated and the value of these sums.
There are $L^N$ ...
- 23
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
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
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
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
12
votes
2
answers
661
views
The $r$-dimensional volume of the Minkowski sum of $n$ ($n\geq r$) line sets
Let $n$ line sets be $\mathcal{S}_i=\{a\mathbf{h}_i:0 \le a \le 1\}$, for $1 \le i \le n$, where $\{\mathbf{h}_1,\cdots,\mathbf{h}_n\}$ is a vector group of rank $r$ in the $r$-dimensional Euclidean ...
- 550
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
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
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
2
votes
1
answer
403
views
Rank of sumsets in matroids
Assume that $G$ is a (finite) abelian group and $M$ is a matroid whose ground set is $G$. Let $X$ and $Y$ be subsets of $G$, and $H$ is the stabilizer of $X+Y$. That is $X+Y+H=X+Y$. We denote the rank ...
- 429
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
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
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
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
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
8
votes
2
answers
596
views
Do Minkowski sums have anything like calculus?
Is there anything resembling differential calculus over the space of (nicely behaved) regions in $\mathbb{R}^d$, where addition is interpreted in terms of Minkowski sums? For example, it is known ...
- 81
1
vote
1
answer
238
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
2
votes
1
answer
156
views
Equal subset-sums of bounded vectors
Let $S\subseteq \{0,\ldots,n\}^d$ be a set of $d$-dimensional vectors of with bounded, natural, coordinates.
We are given that
$$v'+v_1+\ldots+v_t=u'+u_1+\ldots+u_s$$
where $v_1,\ldots,v_t,u_1,\ldots,...
- 203
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
1
vote
1
answer
230
views
Probability of getting two subsets with the same sum
Let $A=\{1,...,n\}$. Two subsets of $A$, not necessarily distinct, chosen uniformly at random. What is the probability that both subsets have the same sum? Alternatively, is there a known upper bound?
- 11
2
votes
0
answers
124
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
-2
votes
1
answer
708
views
Prove or disprove this integral of a function, defined on a countable set with infinite limit points, converges to zero [closed]
Edit: I got rid of my old definitions. Everything should be clear now
Since no one has answered my question on MSE, I’m hoping to get an answer here. I apologize if you dislike my writing. I am an ...
- 63
3
votes
3
answers
749
views
Is the sumset or the sumset of the square set always large?
Let A be a finite subset of $\mathbb{N}$, $\mathbb{R}$, or a sufficiently small subset of $\mathbb{F}_{p}$.
Do we have a lower bound of the form $|A|^{1+\delta}$ on the following quantity:
$$\max (|\...
- 13k
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
7
votes
1
answer
1k
views
Minkowski sum of polytopes from their facet normals and volumes
By Minkowski's work in the early 1900s, every polytope $P\subset\mathbb R^n$ is determined up to translation by its unit facet normals $u_1,\dots,u_k$ and facet volumes $\alpha_1,\dots,\alpha_k$. ...
- 373
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