Questions tagged [sumsets]
The sumsets tag has no usage guidance.
81
questions
2
votes
0
answers
71
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 ...
- 21.3k
0
votes
0
answers
61
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|,...
- 21.3k
0
votes
1
answer
180
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 ...
- 216
15
votes
2
answers
1k
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\...
- 29.6k
2
votes
1
answer
381
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 ...
- 359
15
votes
1
answer
737
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
135
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$.
...
- 385
6
votes
1
answer
127
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 $[...
- 21.3k
6
votes
1
answer
146
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 ...
- 21.3k
2
votes
1
answer
94
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
1
vote
1
answer
188
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
83
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) ...
- 21.3k
3
votes
1
answer
272
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 ...
- 2,279
0
votes
1
answer
376
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$...
- 2,279
0
votes
0
answers
122
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^{...
- 2,279
-2
votes
1
answer
563
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 ...
- 1
5
votes
1
answer
135
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\...
- 292
3
votes
1
answer
208
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 ...
- 21.3k
1
vote
1
answer
173
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
287
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$?
- 21.3k
11
votes
2
answers
372
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 ...
- 532
10
votes
1
answer
279
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 ...
- 29.6k
19
votes
4
answers
789
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 ...
- 29.6k
7
votes
2
answers
410
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 ...
- 71
3
votes
0
answers
129
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,598
2
votes
0
answers
37
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}...
- 12.8k
6
votes
1
answer
247
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,598
0
votes
0
answers
49
views
Rewriting a set of integers to get rid of repetition but keeping subset sum ordering
Say, I have a set of 6 +ve integers sorted in ascending order:
$A = \{2,4,4,4,5,7\}$
Now to make it easier to deal with (Minimum one starts with 1) I deducted one from all of them:
$\therefore B= ...
- 11
1
vote
0
answers
159
views
Generating Subsets of a Multiset in Ascending Order of the Sums of the Elements of the Subset
I am trying to come up with an algorithm where you can generate combination from a set in a order such that their sums are in increasing order. This set has to be a multiset i.e. repetition allowed.
...
- 11
5
votes
1
answer
591
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$. ...
- 333
3
votes
1
answer
135
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,256
3
votes
1
answer
210
views
On particular sumset properties of permanent?
Denote $\mathcal R_2[n]=\mathcal R[n] + \mathcal R[n]$ to be sumset of integers in $\mathcal R[n]$ where $\mathcal R[n]$ to be set of permanents possible with permanents of $n\times n$ matrices with $...
- 12.8k
3
votes
1
answer
240
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 ...
- 4,205
4
votes
0
answers
145
views
Dividing a finite arithmetic progression into two sets of same sum: always the same asymptotics?
This is inspired by the recent question How many solutions $\pm1\pm2\pm3…\pm n=0$.
The oeis entries A063865 linked to this question and A292476/A156700 for the related one "How many solutions $\pm1\...
- 12.4k
18
votes
3
answers
898
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,465
2
votes
0
answers
135
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 ...
- 8,388
8
votes
2
answers
524
views
sum-sets in a finite field
Let $\mathbb{F}_p$ be a finite field, $A=\{a_1,\dots,a_k\}\subset\mathbb{F}_p^*$ a $k$-element set, for $k<p$. $\mathfrak{S}_k=$permutation gp.
Question. Is it true there is always a $\pi\in\...
- 37.8k
3
votes
0
answers
63
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
236
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$ ...
- 255
1
vote
0
answers
107
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?
10
votes
1
answer
525
views
what is the status of this problem? an equivalent formulation?
R. Guy, Unsolved problems in number theory, 3rd edition, Springer, 2004.
In this book, on page 167-168, Problem C5, Sums determining members of a set, discusses a question Leo Moser asked: suppose $X\...
- 37.8k
4
votes
2
answers
366
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
4
votes
0
answers
120
views
Restricted addition analogue of Freiman's $(3n-4)$-theorem
There is a well-known theorem of Freiman saying that if $A$ is a finite set of integers with $|2A| \le 3|A|-4$, then $A$ is contained in an arithmetic progression with at most $|2A|-|A|+1$ terms. Is ...
- 41
2
votes
1
answer
162
views
When does the equality hold in Dias da Silva - Hamidoune Theorem?
Let $p$ be prime number and let $A$ be a $k$-elements subset of $\mathbb{Z}/p\mathbb{Z}$. Dias da Silva - Hamidoune Theorem states that $|h^{\hat{}}A| \geq \min(p, hk -h^2 + 1)$, where $h$ is an ...
- 157
1
vote
1
answer
164
views
Sumset achieving extreme upper bound [closed]
It is trivial that $|A_1 + \cdots + A_h| \leq |A_1|\cdots |A_h|$, where $h \geq 2$ and $A_i \subseteq \mathbb{Z}$ are nonempty finite sets and $A_1 + \cdots + A_h :=\{a_1 + \cdots + a_h : a_i \in A_i ~...
- 157
1
vote
1
answer
184
views
Some question on haar measure for sumsets of closed subsets of profinite groups
Let $H$ be a profinite group with the haar measure $\mu_H$. Let $H_1$ and $H_2$ be closed subgroups of $H$. $H_1$ and $H_2$ have their own haar measures $\mu_{H_1}$ and $\mu_{H_2}$ respectively.
...
- 11
8
votes
1
answer
715
views
Does $|A+A|$ concentrate near its mean?
Fix $N$ to be a large prime. Let $A \subset \mathbb{Z}/N\mathbb{Z}$ be a random subset defined by $\mathbb{P}(a \in A) = p$, where $p = N^{-2/3 + \epsilon}$ for some fixed $\epsilon > 0$. My ...
- 2,213
2
votes
4
answers
544
views
Show that the Minkowski sum of two triangles in 3D is the union of Minkowski sums of each triangle along the other's edges?
I'd like to show (or disprove) the claim that the Minkowski sum of two triangles with vertices in $\mathbb{R}^3$, $A+B$, is equal to the union of the unions of the Minkowski sums of $A$ along all ...
- 621
3
votes
2
answers
240
views
Partition regular systems: do they have solution in (very dense) set of integers?
A partition regular system is a linear system of equations of the form $A\cdot x=0$, which satisfies a Ramsey-type result (namely, that for each $r>0$ whenever we colour the integers in $r$ classes,...
- 1,054
3
votes
2
answers
389
views
Sumsets with distinct numbers, upper bound for maximum element
Let $A$ be a finite set of positive natural numbers with $n$ elements, $|A|=n$, with the property that all sums of two (not necessarily different) elements are distinct, or in the usual notation for ...
- 133