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
0 votes
0 answers
29 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
36 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 ...
user avatar
0 votes
1 answer
67 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-...
user avatar
0 votes
0 answers
33 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 ...
user avatar
0 votes
2 answers
48 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 ...
user avatar
  • 3,841
2 votes
0 answers
46 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 $...
user avatar
  • 11.9k
7 votes
1 answer
133 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 ...
user avatar
  • 11.9k
1 vote
1 answer
58 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) \...
user avatar
  • 1,031
0 votes
0 answers
40 views

Minkowski sum of disks in 3D space

In general, is it possible to formulate (or write an equation) the object constructed by the Minkowski summation of multiple disks? These disks are neither parallel nor perpendicular to each other. ...
user avatar
  • 31
0 votes
1 answer
28 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+\...
user avatar
  • 3,848
0 votes
0 answers
42 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 ...
user avatar
1 vote
0 answers
56 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.
user avatar
  • 11
11 votes
1 answer
323 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 ...
user avatar
2 votes
2 answers
420 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 ...
user avatar
3 votes
1 answer
132 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 ...
user avatar
  • 614
1 vote
2 answers
156 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 ...
user avatar
  • 11
0 votes
1 answer
38 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|\}...
user avatar
2 votes
1 answer
92 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 ...
user avatar
  • 1,082
5 votes
1 answer
197 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$...
user avatar
  • 14.8k
4 votes
1 answer
130 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,...
user avatar
4 votes
0 answers
109 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 ...
user avatar
  • 14.8k
2 votes
1 answer
66 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$, ...
user avatar
  • 14.8k
1 vote
2 answers
75 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 ...
user avatar
2 votes
3 answers
115 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 ...
user avatar
0 votes
2 answers
98 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?
user avatar
  • 2,303
1 vote
1 answer
913 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 ...
user avatar
  • 2,303
1 vote
1 answer
44 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 ...
user avatar
  • 14.8k
2 votes
2 answers
79 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 ...
user avatar
  • 14.8k
1 vote
0 answers
79 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= ...
user avatar
  • 11
2 votes
0 answers
21 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 ...
user avatar
  • 2,473
2 votes
2 answers
95 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\...
user avatar
1 vote
0 answers
60 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 ...
user avatar
  • 2,473
6 votes
1 answer
96 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 \...
user avatar
2 votes
1 answer
46 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\}$?
user avatar
2 votes
1 answer
58 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 ...
user avatar
  • 2,473
1 vote
0 answers
20 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 ...
user avatar
4 votes
2 answers
397 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 ...
user avatar
0 votes
0 answers
17 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?
user avatar
  • 101
1 vote
1 answer
37 views

Retrieve a series knowing all its convergent infinite powersums

We would like to identify $s_n$ (non-increasing series) once we know, assuming are all of them convergent: $$S_k=\sum_{n>=0}{s_n^k}$$ Known for all k values. As example $\zeta(2k)$ should ...
user avatar
3 votes
0 answers
96 views

Where can I find this article by I. Ruzsa?

Title says it all. Have tried googling and my college library, but no success so far. I. Ruzsa, On the cardinality of $A + A$ and $A − A$. In Combinatorics (Keszthely, 1976), Coll. Math. Soc. Bolyai ...
user avatar
  • 613
1 vote
1 answer
68 views

If the set $A$ is open in $X$, is the set $\{x+y : x\in A \}$ also open for a given $y \in X$ under any metric space?

I think it can be shown for the Euclidean metric in an $\mathbb{R}^n$ set, since $\|x-y\|=\|(x+a)-(y+a)\|$ but is it true for any metric space? Let's say the discrete metric space?
user avatar
  • 93
15 votes
1 answer
425 views

Is the sum (difference) of Borel set with itself a Borel set?

Let $d \in \mathbb{N}$, $A \subset \mathbb{R}^d$, be a Borel set. Consider Minkowski sums $$ \mathbb{S}(A) = A + A = \{x + y:\; x,y\in A \} $$ $$ \mathbb{D}(A) = A - A = \{x - y:\; x,y\in A\} $$ Must ...
user avatar
  • 3,326
1 vote
1 answer
27 views

number of sums in $\mathbb{Z}_{p^r}$ which are coprime to $p^r$

We look at the ring of integers modulo a prime power, say $p^r$ and $r>1$. Eulers totient formula says that there are $p^r-p^{r-1}$ elements in this ring $\mathbb{Z}_{p^r}$ that are coprime to $p^r$...
user avatar
  • 339
4 votes
2 answers
3k views

Sum of two subspaces is a subspace

I am wondering if someone can check my proof that the sum of two subspaces is a subspace: 1) First show that $0 \in W_1 + W_2$: Since $W_1, W_2$ are subspaces, we know that $0 \in W_1, W_2$. So if $...
user avatar
  • 561
0 votes
3 answers
130 views

Supremum of Sumset (Proof Writing)

Given $A,b\subseteq\mathbb{R}$, define the set $A+B=\lbrace a + b | a\in A, b\in B\rbrace$. I would like to prove that $\sup(A+B)=\sup(A)+\sup(B)$, but in a specific way. Here is what I have done so ...
user avatar
  • 2,029
0 votes
0 answers
55 views

How many consecutive numbers in a sumset?

Let $A=\{a_1,a_2,\dots,a_n\,\vert\,a_1\lt a_2\lt\cdots\lt a_n\}$ be a finite subset of $\Bbb N$ with sumset $$A+A=\{a_i+a_j\,\vert\, a_i,a_j\in A\}$$ What is the longest possible chain of consecutive ...
user avatar
  • 2,788
3 votes
3 answers
117 views

$\lim_{n\to\infty} \sum_{k=1}^n \frac{k!}{n!}$

I'm presented with the limit $\lim_{n\to\infty}\sum_{k=1}^{n} \frac{k!}{n!}$ I've got a hunch that it diverges to infinity but I wasn't able the prove that the sum is superior to a series diverging ...
user avatar
1 vote
0 answers
36 views

Applications for Sumsets?

Given an abelian group or semigroup $\mathcal{G}$ and sets $A,B\subseteq\mathcal{G}$, we define the sumset of $A$ and $B$ by $A+B=\lbrace a+b|a\in A,b\in B\rbrace$. We also denote by $hA=\lbrace a_1+.....
user avatar
  • 2,029
2 votes
2 answers
458 views

Does $\overline{A+B}=\overline A+\overline B$ hold if $\overline A$ and $\overline B$ are compact?

Let us assume that we are working with subsets $A$, $B$ of some topological space $X$ such that also $A+B$ makes sense. (For example, we can have $X=\mathbb R^n$, $X$ could be a topological group, a ...
user avatar
9 votes
3 answers
6k views

Prove that the sum of two compact sets in $\mathbb R^n$ is compact.

Given two sets $S_1$ and $S_2$ in $\mathbb R^n$ define their sum by $$S_1+S_2=\{x\in\mathbb R^n; x=x_1+x_2, x_1\in S_1, x_2\in S_2\}.$$ Prove that if $S_1$ and $S_2$ are compact, $S_1+S_2$ is ...
user avatar
  • 181