# Questions tagged [sumsets]

The sumsets tag has no usage guidance.

72
questions

**2**

votes

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**1**answer

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

**3**answers

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

**2**answers

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

**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)...

**1**

vote

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**3**answers

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

**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**

votes

**2**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**2**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**4**answers

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

**2**answers

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

**2**answers

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**3**answers

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

**2**answers

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

**2**answers

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

**1**answer

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

**1**answer

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+...