Questions tagged [sumsets]
The sumsets tag has no usage guidance.
72
questions
2
votes
1answer
67 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,...
1
vote
1answer
157 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?
2
votes
0answers
79 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) ...
3
votes
1answer
250 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 ...
1
vote
1answer
328 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$...
0
votes
0answers
113 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
votes
1answer
499 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 ...
5
votes
1answer
111 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\...
3
votes
1answer
193 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 ...
1
vote
1answer
167 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$, ...
1
vote
1answer
273 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$?
11
votes
2answers
294 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 ...
10
votes
1answer
275 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 ...
16
votes
3answers
609 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 ...
7
votes
2answers
372 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 ...
3
votes
0answers
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)...
1
vote
0answers
33 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}...
6
votes
1answer
243 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)$, ...
0
votes
0answers
46 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= ...
1
vote
0answers
121 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.
...
5
votes
1answer
471 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$. ...
3
votes
1answer
125 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 ...
3
votes
1answer
206 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 $...
3
votes
1answer
232 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
votes
0answers
140 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\...
18
votes
3answers
859 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$? ...
2
votes
0answers
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
votes
2answers
477 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\...
3
votes
0answers
60 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)| &...
3
votes
1answer
229 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$ ...
1
vote
0answers
98 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
1answer
507 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\...
4
votes
2answers
320 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 ...
4
votes
0answers
118 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 ...
2
votes
1answer
146 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 ...
1
vote
1answer
157 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 ~...
1
vote
1answer
178 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.
...
8
votes
1answer
711 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
votes
4answers
507 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 ...
3
votes
2answers
222 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,...
3
votes
2answers
370 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 ...
0
votes
1answer
160 views
Set of number with unique sums of elements [closed]
Is it possible to construct a set of numbers of arbitrary size such that any calculation involving addition and subtraction, on any combination of those numbers, produces a unique result?
For example,...
5
votes
2answers
455 views
Can you simplify (or approximate) $\sum_{n=0}^{N-1} \binom{N-1}n \frac{(-1)^n}{n+1} e^{-\frac{n}{2(n+1)}\lambda}$?
Let $\binom x y$ be the binomial coefficient. I am trying to get a better understanding of the sum
$$
f(N,\lambda)=\sum_{n=0}^{N-1}\binom{N-1}n\frac{(-1)^n}{n+1} e^{-\frac{n}{2(n+1)}\lambda}
$$
as a ...
0
votes
1answer
198 views
determine elements of a sum given set
Is it possible to efficiently find the elements that make up a sum $S$ given a set of number sets which determine the sum elements? It seems like an NP-Complete problem, though I might miss something.
...
2
votes
1answer
435 views
Asymptotic of a sum involving binomial coefficients
Good evening, I'm trying to find an asymptotic of this sum:
$$\sum_{j=0}^n (-1)^j {n \choose j} (n - j)^n = n^n - {n \choose 1} (n - 1)^n + {n \choose 2} (n - 2)^n + ... + (-1)^n {n \choose n} (n - ...
3
votes
3answers
627 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 (|\...
10
votes
2answers
401 views
Iterated sumset inequalities in cancellative semigroups
This question is motivated by the following well-known theorems:
Thm (Plünnecke): If $A$ is a finite nonempty subset of an abelian group, then for every $n$ we have $|A^n| \le \frac{|AA|^n}{|A|^n}|A|$...
10
votes
2answers
564 views
Sumsets and dilates: does $|A+\lambda A|<|A+A|$ ever hold?
The following problem is somehow hidden in this recently asked question, but I believe that it deserves to be asked explicitly.
Is it true that for any finite set $A$ of real numbers, and any real $...
5
votes
1answer
245 views
Element with unique representation in A+B
Let $A, B \subseteq \mathbb{Z}$ be finite subsets of the integers. Then there exists an element in $A+B$ with a unique representation as a sum of an element in $A$ and an element in $B$, namely $\max(...
3
votes
1answer
194 views
On a problem about $GF(2)^n$
For $A\subseteq {\mathbb F}_2^n$ let
$$
Q(A)=\{\alpha+\beta\mid \alpha,\beta \in A,\ \alpha\neq\beta \}.
$$
I want to prove or disprove that if $|A|=2^k+1$ for some integer $k$, then
$$
|Q(A)|\ge2^{k+...
