Questions tagged [sumset]

For questions regarding sumsets such as $A+B$, the set of all sums of one element from $A$ and the other from $B$.

Filter by
Sorted by
Tagged with
1 vote
0 answers
33 views

A Question on the Brunn-Minkowski inequality

It is a direct consequence of the Brunn-Minkowski inequality that \begin{equation} |A\oplus B| - \Big(\sqrt{|A|}+\sqrt{|B|}\Big)^2 \geq |A\oplus\tilde{B}| - \Big(\sqrt{|A|}+\sqrt{|\tilde{B}|}\Big)^...
student_of_geometry's user avatar
1 vote
1 answer
39 views

Affine Combinations and Span

I was reading a bit of convex analysis and came across this problem. Let $S$ be convex. Let $A$ be the set of finite affine combinations of points in $S$ (i.e. finite linear combinations whose weights ...
John Atwood's user avatar
0 votes
0 answers
64 views

What is the maximum range of a convex finite additive 2-basis of cardinality k?

Conjecture: Given any $d \in \mathbb{Z}_{\geq 2}$ and $k=2d-2$, we have \begin{align*} \max \{ n : (\exists &f \in \{ \mathbb{Z}_{\geq 0} \to \mathbb{Z}_{\geq 0} \})\\ &[((\forall i \in \...
Michael Chu's user avatar
0 votes
2 answers
56 views

Whether $\sup(\sum\limits_{i=1}^{\infty}X_i)$ is equal to $\sum\limits_{i=1}^{\infty}(\sup X_i)$

We have $\sup(A+B)=\sup(A)+\sup(B) $.Thus, we have $\sup(\sum\limits_{i=1}^{n}X_i)=\sum\limits_{i=1}^{n}(\sup X_{i})$ for every finite integer $n\in\mathbb{N}$. However, what about the set sequence? ...
MGIO's user avatar
  • 85
1 vote
1 answer
99 views

How many subsets $S$ of integer interval $[0,n]$ such that $n, n-1 \not \in S+S$?

Conjecture: Given any $n \in \mathbb{Z}_{\geq 0}$, we have $$|\{S : (S \subseteq [0,n]) \land (n, n-1 \not \in S+S)\}| = F(n+2),$$ where $F$, the sequence of Fibonacci numbers, is given by $F(j) = F(...
Michael Chu's user avatar
0 votes
0 answers
12 views

Convexity of minkowski space when two triangles collide

I am working on a Python program to show the collision of two triangles by using Minkowski difference. I am subtracting each point from one triangle from every other point on the other triangle. The ...
Hussain Bhavnagarwala's user avatar
0 votes
1 answer
108 views

Is this Minkowski Sum result correct?

Is this Minkowski Sum result correct? I expected a filled shape as it happens when the two polygons don't overlap (longer translation vector). Full discussion here: https://github.com/AngusJohnson/...
abenci's user avatar
  • 185
0 votes
1 answer
78 views

Is the sum of a closed unit ball and a closed set itself closed?

I am reading here that in a Banach space, the sum of the closed unit ball with a closed bounded convex set might fail to be closed itself. It seems there is a counterexample if and only if the ...
Daron's user avatar
  • 10.3k
1 vote
0 answers
32 views

Asymptotic behavior of a set of nonnegative integers whose sumset with itself is the nonnegative integers

Let $S$ be a set of nonnegative integers such that the sumset $S+S$ is the nonnegative integers. If it can, what is the fastest growing function $f$ such that the number of elements of $S$ less than $...
mathlander's user avatar
  • 4,017
4 votes
1 answer
153 views

General formula for $\prod_{i<j} (a_i + b_j)$

I want to expand the product of a sum into a sum of products $$ \prod_{i<j}^n (a_i + b_j) = \sum_{\text{sets } A,B} ~ \prod_{i\in A} a_i \prod_{j\in B} b_j. $$ With the result from this post ...
Cream's user avatar
  • 392
0 votes
1 answer
81 views

$\mathbb N-\{1\}\subseteq\mid S+S\mid$ such that $d\left(S\right)=0$

I am dealing with the set of integers $A=\{x:x\neq i+j+2ij, x\in\mathbb N, i\in\mathbb N, j\in\mathbb N\}$. I am trying to show that $\mathbb N-\{1\}\subseteq\mid A+A\mid$, $\mid A+A\mid=\{a_i+a_j: ...
Juan Moreno's user avatar
  • 1,110
0 votes
1 answer
52 views

Name for a shape consisting of the union of all spheres of a given radius centered at all points in a triangular (or tetrahedral) region?

I'm struggling with finding a name for the following object: Suppose we have a set of points. For example a triangle, including the area inside the triangle, its edges and its vertices. We then ...
iliar's user avatar
  • 123
0 votes
0 answers
39 views

Is this true for a sumset?

We let $A,B\subseteq \mathbb{Z}$ such that $|A|=|B|=n$. I am trying to show that $|A+B|\ge 2n-4$ for large $n$ where we define $A+B=\{a+b:a\in A, b\in B\}$. If this is not true, I'd like to see a ...
user avatar
0 votes
0 answers
63 views

Generating restricted finite additive $2$-bases from doubly-eager bit-strings

A bit-string is any finite sequence of $1$s and $0$s. For example, $1011011$, $1011010$, and $000110$ are bit-strings. In this post, I will refer to bit-strings as strings, to be concise. I now ...
Michael Chu's user avatar
0 votes
1 answer
89 views

How many subsets $S$ of integer interval $[0,n]$ such that $k \not \in S+S$?

After a bit of experimentation, I thought of the following conjecture: Given any $n \in \mathbb{Z}_{\geq 0}$ and $k \in [0,2n]$, we have $$|\{S : (S \subseteq [0,n]) \land (k \not \in S+S)\}| = 2^{|n-...
Michael Chu's user avatar
0 votes
0 answers
82 views

Instead of "sum-free" sets, consider sets where $S\subset S+S$. This is trivially satisfied when $0 \in S$. Is there a subset of $S$ with sum $0$?

As an example, here is a set $S$ with $S\subset S+S$ and $|S|=8$ and having subsets of four elements whose sum is zero, but no smaller subsets have this property: $S=\{-14,-13,-11,-7,1,2,4,8\}$. This ...
user622310's user avatar
0 votes
2 answers
62 views

Sumsets : optimality of two basic inequalities

One can prove that for $A$ and $B$ subsets of $\mathbb{Z}$ one has $$ |A|+|B|-1 \leq |A+B| \leq |A|\times |B| $$ where $A+B = \left\{ a+b,a\in A \text{ and } b \in B \right\}$ and, for $X$ a finite ...
user37238's user avatar
  • 4,017
2 votes
0 answers
58 views

Which sets of $n-1$ non-multiples of $n$ can't make a multiple of $n$ using $+,-$?

This is a follow up to my previous question (see linked question). In short, there it is shown that if $n$ is prime, then any set can make it. I want to characterize sets $\mathbb A_n$ of multisets $...
Vepir's user avatar
  • 12.5k
7 votes
1 answer
152 views

For any $n-1$ non-zero elements of $\mathbb Z/n\mathbb Z$, we can make zero using $+,-$ if and only if $n$ is prime

Inspired by Just using $+$ ,$-$, $\times$ using any given n-1 integers, can we make a number divisible by n?, I wanted to first try to answer a simpler version of the problem, that considers only two ...
Vepir's user avatar
  • 12.5k
1 vote
1 answer
340 views

Minkowski sum of the intersection of a closed and an open set with a compact set

Consider $\mathbb R^n$ with the usual topology and the Borel sigma-algebra. Let $A$ be open and $B$ be closed sets, respectively, in $\mathbb R^n$. Let $C$ be a compact set. Is the set $(A \cap B) \...
VSJ's user avatar
  • 1,081
1 vote
0 answers
74 views

Minkowski sum of disks in 3D

Suppose we have a set of disks in $\Bbb R^3$. These disks are neither parallel nor perpendicular to each other. In general, is it possible to formulate (or write an equation for) the object ...
sqiu47's user avatar
  • 43
0 votes
1 answer
36 views

Banach spaces, $\lVert\cdot\rVert_X$ and $\lVert\cdot\rVert_{X+X}$ are equivalent.

Let $(X,\lVert\cdot\rVert_X)$ and $(Y,\lVert\cdot\rVert_Y)$ be Banach spaces. Then as I understand, $X+Y$ endowed with $$\lVert v\rVert_{X+Y}=\inf\limits_{a+b=v\\ a\in X\\b\in Y}\lVert a\rVert_X+\...
roi_saumon's user avatar
  • 4,206
0 votes
0 answers
56 views

Dimension of sumset

Suppose $X$ and $Y$ are $d$-dimensional set, subsets of $\mathbf{R}^N (N>>d)$ (More precisely, my case is : $X =Y= \{vec(xy^T)|x \in R^{d_1}, y \in R^{d_2}, \|x\|\leq 1, \|y\|\leq 1\}, N=d_1 d_2 ...
user2998690's user avatar
1 vote
0 answers
62 views

A finite Fibonacci sum

Is there a closed form for $$ A(n)=\sum_{k=1}^n\binom{n}{k}\frac{F_k}k $$ A closed form that is not in terms of two hypergeometric functions.
Anthony's user avatar
  • 11
11 votes
1 answer
370 views

If an infinite set $S$ of positive integers is equidistributed, is $S+S$ also equidistributed?

By $S+S$, I mean $\{x+y,$ with $x,y \in S\}$. By equidistributed, I mean equidistributed in residue classes, as defined here (the definition is very intuitive, and examples of such equidistributed ...
Vincent Granville's user avatar
2 votes
2 answers
990 views

Let s be a set of five positive integers at most 9. Prove that the sums of the elements in all the non empty subsets of s cannot be distinct.?

Let s be the set of five positive integer the maximum of which is at most 9 prove that the sums of the elements in all the non empty subset of as cannot be distinct? Note: I know this is similar to ...
marty cohen's user avatar
3 votes
1 answer
172 views

Determine the structure of all finite sets $A$ of integers such that $|A| = k$ and $|2A| = 2k + 1$.

An exercise in Nathanson's text: Additive Number Theory, Inverse problems and the geometry of sumsets is the following (Excercise 16, P.No.37): Determine the structure of all finite sets $A$ of ...
Rajkumar's user avatar
  • 612
1 vote
2 answers
349 views

$X$ open, $X+Y$ also open

Question: Let: $$X,Y \subset\mathbb{R}$$ and: $$X+Y= \{x + y : x\in X, y \in Y\} $$ Show that if $X$ is open, then $X+Y$ is also open. I'm not sure where to start can someone help me it would be ...
bonoboy's user avatar
  • 11
0 votes
1 answer
64 views

Minimal size of a sumset over $\mathbb{F}_p$

Let $A, B \subseteq \mathbb{F}_p$ ($p$ a prime). How to show that $|A+B| \ge \min\{p, |A|+|B|-1\}$? Since $\mathbb{F}_p$ has only $p$ elements, $\forall S \subseteq \mathbb{F}_p, |S| \ge \min\{p, |S|\}...
keyboardAnt's user avatar
2 votes
1 answer
114 views

Set $A$ with $|2A| \geq 100|A|$ but $|3A| < 1000|A|$

Let $kA$ denote the sumset $\{ a_1 + \cdots + a_k \mid a_i \in A \}$. I want to show that $|2A| \geq 100|A|$ does not imply $|3A| \geq 1000|A|$. [I know this to be true experimentally, but am ...
John Don's user avatar
  • 1,179
5 votes
1 answer
215 views

Sum-free sets in finite groups

Suppose $G$ is a group, $S \subset G$. Let’s call $S$ sum-free iff $\forall a, b \in S$ we have $ab \notin S$. Do there exist such $\epsilon > 0$, such that every sufficiently large finite group $G$...
Chain Markov's user avatar
  • 15.6k
4 votes
1 answer
181 views

Two uncountable subsets of real numbers without any interval and two relations

Are there two uncountable subsets $A, B$ of real numbers such that: (1) $(A-A)\cap (B-B)=\{ 0\}$, (2) $(A-A)+B=\mathbb{R}$ or $(B-B)+A=\mathbb{R}$ ? We know that if one of them contains an interval,...
M.H.Hooshmand's user avatar
4 votes
0 answers
131 views

Sidon sets in finite groups

Suppose $G$ is a group, $S \subset G$. Let’s call $S$ a Sidon subset iff $\forall$ quadruples $(a, b, c, d)$ of distinct elements of $S$ we have $ab \neq cd$ (named after Simon Sidon who studied such ...
Chain Markov's user avatar
  • 15.6k
2 votes
1 answer
103 views

Maximal size of bounded “sparse” sets of natural numbers

Let’s call $A \subset \mathbb{N}$ sparse iff for all quadruples of distinct numbers $(a, b, c, d)$ from $A$ it is true, that $a + b \neq c + d$. What is the maximal possible size of a sparse set $A$, ...
Chain Markov's user avatar
  • 15.6k
1 vote
2 answers
96 views

How small can "spanning sumsets" of $[n]$ be?

Let $[n]$ denote the natural numbers $1$ through $n$. Let's say a subset $X \subset [n]$ is a spanning sumset if $\{x+y: x,y \in X\} = [n] \setminus \{1\}$. I'm interested in studying spanning sumsets ...
MathematicsStudent1122's user avatar
2 votes
3 answers
122 views

Minimum number of integers $a_1,....,a_m$ needed to express $2,...,n$ as $a_i + a_j$

I am interested in the following problem. An arbitrary integer $n \geq 2$ is given. Find the minimum integer $m \geq 1$ such that there exist integers $0\lt a_1\lt a_2\lt \cdots \lt a_m$ satisfying ...
Berry van Peer's user avatar
0 votes
2 answers
194 views

Following up with a previous question on $\sup(A)+\sup(B) = \sup(A + B)$

The question link is here: Prove that $Sup(A + B) = Sup(A) + Sup(B)$ Can someone look at the answer given and explain why epsilon is introduced and how that whole second part works?
K. Gibson's user avatar
  • 2,381
1 vote
1 answer
4k views

Prove that $Sup(A + B) = Sup(A) + Sup(B)$

Earlier on in the book it showed that to prove $a = b$ it is often best to show that $a \leq b$ and that $b \leq a$. This is the way I want to go about the proof. I am sure there is an easier way but ...
K. Gibson's user avatar
  • 2,381
1 vote
1 answer
53 views

Does there exist such a non-trivial semigroup $S$ ($|S| > 1$), that $S \cong Add(S)$?

Suppose $S$ is a semigroup. Define $Add(S)$ as the set of all finite subsets of $S$, equipped with the operation of pairwise “addition” ($\forall A, B \in Add(S)$, $AB = \{ab| a \in A, b \in B\}$). It ...
Chain Markov's user avatar
  • 15.6k
2 votes
2 answers
120 views

What is the probability that $\exists N \in \mathbb{N}$ such that $\forall n > N$, $2n \in C + C$?

Suppose $C$ is a random subset of $\mathbb{N}\setminus\{1, 2\}$, such that $\forall n \in \mathbb{N}\setminus\{1, 2\}$, $P(n \in C) = \frac{1}{\ln(n)}$ and the events of different numbers belonging to ...
Chain Markov's user avatar
  • 15.6k
1 vote
0 answers
97 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= ...
Moni's user avatar
  • 11
3 votes
0 answers
28 views

Existence of a nilpotent subgroup $N \leq G$ of step $\leq n$ such that a finite $A$ is in $K^{O_n(1)}$ left cosets of $N$

Some extra details left out of the title: Given a group $G$, a symmetric subset $A \subset G$ containing $1$ is called a $K$-approximate group if $|A^2| = |\{ab \mid a,b \in A\}| \leq K|A|$ We are ...
user366818's user avatar
  • 2,653
2 votes
2 answers
97 views

Show that there exists $i\in \lbrace 1, 2, 3 \rbrace $ s.t. there exists $a, b\in A_i $ s.t. $a+b\in B $.

Let $A=\lbrace 1, 2, 3,..., 2019\rbrace= A_1\cup A_2\cup A_3$, where $A_1\cap A_2=A_2\cap A_3= A_1\cap A_3=\emptyset $ and $B=\lbrace 672, 1008, 1344, 1680, 2016\rbrace $. Show that there exists $i\...
Problemsolving's user avatar
1 vote
0 answers
82 views

Coset Progression is Freiman Isomorphic to Bohr Set

For an abelian group $G$, $H$ a finite subgroup of $G$, $x_1, \dots, x_r \in G$ and $L_1, \dots, L_r \in \mathbb N$, let: $P(x ; L) = P(x_1, \dots, x_r ; L_1, \dots, L_r) = \{l_1x_1 + \dots + l_rx_r ...
user366818's user avatar
  • 2,653
6 votes
1 answer
131 views

Subsets of $\mathbb Z/n\mathbb Z$ disjoint with some of its shifts

Are there any descriptions of all subsets $X$ of $\mathbb Z/n\mathbb Z$ with the following property: there exists $a\ne 0$ in $\mathbb Z/n\mathbb Z$ such that $X$ is disjoint with $X + a = \{x + a \...
Ilya V. Schurov's user avatar
2 votes
1 answer
47 views

Subsets of $\mathbb Z/n\mathbb Z$ that remain disjoint with themselves under shifts

Are there any descriptions of all subsets $X$ of $\mathbb Z/n\mathbb Z$ such that for any $a\ne 0$ in $\mathbb Z/n\mathbb Z$, $X$ is disjoint with $X + a = \{x + a \pmod n\mid x \in X\}$?
Ilya V. Schurov's user avatar
2 votes
1 answer
66 views

Prove that if $|A+A| \leq K|A|$ then $2A - 2A$ is a $K^{16}$-approximate group.

Let $A$ be a finite subset of an abelian group, $G$ (call the operation addition). We say $A$ is a $K$-approximate group if: 1) $e_G \in A$ 2) $A^{-1} = \{ a^{-1} \mid a \in A \} = A$ 3) $\exists X ...
user366818's user avatar
  • 2,653
2 votes
0 answers
21 views

Lower-bounding the density of 3A in terms of that of 2A

Let $A\subset\mathbb{N}$ and $2A=A+A=\{a+b \lvert a,b\in A\}$ and $3A=2A+A$. I wonder how small the density of $3A$ can be, knowing that the density of $2A$ is, say, $\beta >0$, but not knowing ...
Naturfreund's user avatar
5 votes
2 answers
489 views

Finding elements such that none add to a perfect square

Bob asks us to find an infinite set $S$ of positive integers such that the sum of any finite number of distinct elements of S is not a perfect square. Can Bob's request be fulfilled? I can find some ...
user627514's user avatar
0 votes
0 answers
18 views

Nr of monthly eggs that have converted to chickens based on nr of months

I get 1 egg per month every month, which convert to chickens in time t (e.g 9 or 15 months) from when I got the egg with probability P. Given a specific month, e.g 97, how many chickens do I have?
Riku's user avatar
  • 101