Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [sumset]

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

2
votes
2answers
60 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 ...
1
vote
0answers
23 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
12 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 ...
2
votes
2answers
74 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\...
1
vote
0answers
14 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 ...
6
votes
1answer
70 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 \...
2
votes
1answer
35 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\}$?
2
votes
1answer
39 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 ...
1
vote
0answers
15 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 ...
4
votes
2answers
293 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 ...
0
votes
0answers
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?
1
vote
1answer
35 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 ...
2
votes
0answers
39 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 ...
1
vote
1answer
64 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?
14
votes
1answer
178 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 ...
1
vote
1answer
16 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$...
2
votes
2answers
222 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 $...
0
votes
3answers
87 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 ...
0
votes
0answers
35 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 ...
3
votes
3answers
83 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 ...
1
vote
0answers
22 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+.....
2
votes
2answers
136 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 ...
5
votes
3answers
2k 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 ...
7
votes
2answers
311 views

In how many different from a set of numbers can a fixed sum be achieved?

I have a set of number, and I want to know in how many ways from that set with each number being used zero, once or more times can a certain sum if at all, be achieved. The order doesn't matter. For ...
8
votes
1answer
107 views

An inequality on sumsets.

Given two finite sets $A,B\subset \mathbb{R}$, can we assert the inequality $$|A+B|^2\ge |A+A|\cdot|B+B|?$$ I tried to construct an injective function from $(A+A)\times (B+B)$ to $(A+B)^2$ but failed ...
1
vote
0answers
33 views

sigma notation for sumsets $\Sigma B$

I am reading a number theory paper about sumsets [1]. If $A, B \in \mathbb{Z}$ are two sets of integers we can define: $$ A + B = \{ a + b : a \in A, b \in B \} \subseteq \mathbb{Z}$$ what do you ...
3
votes
1answer
364 views

The sum of a set $A$ with the empty set, $\varnothing$

Given that the sum of two sets is defined as $$ A + B = \big\{ a + b : a \in A, b \in B \big\}, $$ how might one compute the sum $$ A + \varnothing $$ where $A$ may or may not be empty? In his book ...
4
votes
0answers
51 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$ ...
-2
votes
1answer
48 views

inclusion-exclusion principle

I don't have any way to see if I have done this in a correct way(no answers in my book). Did I do it right? Question: "How many eight-bit strings either begin 100 or have the fourth bit 1 or both?" ...
0
votes
1answer
347 views

Proving $\sup \left( {A + B} \right) = \sup A + \sup B$ using the usual definition.

Prove $\sup \left( {A + B} \right) = \sup A + \sup B$ using the definition given in this problem (link). I was able to prove using lemma of the given definition. My attempt is here, let $s = \sup A$,...
4
votes
1answer
62 views

Does $2X\neq X$ imply $2Y\neq Y$?

Let $n$ be a sufficiently large integer and $X\subseteq \mathbf{Z}_n$ a finite set of residues modulo $n$ such that $0\in X$ and $2X \neq X$. Fix also $y \in 2X\setminus X$ and define $Y=\{x \in X:y\...
2
votes
0answers
44 views

$p$ divides $ax+by+cz$

I am going to ask here a generalization of this other question: Problem Fix $\varepsilon>0$ and let $p$ be a sufficiently large prime. Then, show that, for every $X\subseteq \{1,\ldots,p\}$ with $|...
1
vote
0answers
30 views

$|2C|<2^k|C|$ if $C$ is a generalized arithmetic progression

Let $C$ be a generalized arithmetic progression, i.e., given positive integers $N_1,\ldots,N_k$ and $a_0,a_1,\ldots,a_k$ then $$ C=\left\{a_0+\sum_{i=1}^n a_in_i: 0\le n_i \le N_i-1 \text{ for all }i=...
9
votes
3answers
2k views

Is the measure of the sum equal to the sum of the measures?

Let $A,B$ be subsets in $\mathbb{R}$. Is it true that $$m(A+B)=m(A)+m(B)?$$ Provided that the sum is measurable. I think it should not be true, but could not find a counterexample.
8
votes
3answers
847 views

If $C$ is the Cantor set, then $C+C=[0,2]$.

Question : Prove that $C+C=\{x+y\mid x,y\in C\}=[0,2]$, using the following steps: We will show that $C\subseteq [0,2]$ and $[0,2]\subseteq C$. a) Show that for an arbitrary $n\in\mathbb{...
5
votes
1answer
52 views

Are large enough numbers the sum of two members of a dense, well-distributed set?

I have a set $S$ of positive integers, and would like to prove that all large enough $n$ are of the form $s+t$ with $s,t\in S.$ (In other words, $\mathbb{N} \setminus (S+S)$ is finite, where $+$ is ...
1
vote
0answers
29 views

An inequality for sumsets

Let $A \subset \mathbb{Z}/N\mathbb{Z}$ and let $m \geq 1$ be an integer such that $|A| < N^{1/m}$. I'm wondering if anyone has seen a good upper bound for the sum $$ S_m(A) = \sum_{k=1}^m|kA|, $$ ...
2
votes
1answer
70 views

Lower bound for arithmetic progressions in sumsets

I'm reading some lecture notes and get stuck on one detail. We wish to prove the following: (1) Let $\alpha > 0$ and $A \subseteq [N]$ be of size $\geq$ $\alpha N$. Then $A + A + A$ contains an ...
1
vote
3answers
181 views

Show that $|A+A|\geq (2n-1)$

Consider a set $A$ consisting of $n$ natural numbers $\{a_i\}_{i=1}^n$ such that $a_1<a_2 < \cdots <a_{n-1} < a_n$. Define the set $A+A$ such that it contains $a_i + a_j \ ; \ i \leq j$ as ...
2
votes
1answer
1k views

What's the difference between the Minkowski difference of $A$ and $B$ and the Minkowski sum of $A$ and $-B$?

In the book Computational Geometry, Algorithms and Applications from de Berg, van Kreveld, Overmars and schwarzkopf, I read the following in chapter 13.3 on Minkowski sums: Sometimes $ P \oplus(-R(...
1
vote
1answer
48 views

A set such that $A$, $A+A$ have density zero but $A+A+A$ has positive density.

I have been thinking about Lagrange's theorem in terms of sumsets. Certainly the perfect squares $\square = \{ n^2: n \in \mathbb{Z}\} = \{ 0,1,4,9,\dots\}$ has density $0$. In fact, I think $$ \...
1
vote
2answers
65 views

Find $S=(a-b)(99-c)(999-2c)+(b-c)(99-a)(999-2a)+(c-a)(99-b)(999-2b)$

Given $(a-b)(b-c)(c-a)=3$ Find $$S=(a-b)(99-c)(999-2c)+(b-c)(99-a)(999-2a)+(c-a)(99-b)(999-2b)$$ Any formula or link related to equation like this?
4
votes
1answer
1k views

Sum of open and closed sets

Let $A,B$ subsets of a normed space $(X,\|\cdot\|)$ and $A+B=\{a+b\mid a\in A,\, b\in B\}$ I need help with the next proofs, I can't figure how to begin the proofs: (a) If $A,B$ open then $A+B$ open ...
5
votes
1answer
138 views

Prove there is a Bernstein set $B$ such that $B+B$ is also Bernstein

Show that there exists a Bernstein set $B$ such that $B+B$ is also Bernstein. I have tried to use the definition that neither $B$ nor its complement contain a perfect set.
4
votes
1answer
54 views

Distribution of the sumset of two GF($q$) subsets

First, a simple definition. The sumset of two subsets $\mathcal{S}_1$ and $\mathcal{S}_2$ containing $GF(q)$ elements is defined as: $$\mathcal{S}_1 + \mathcal{S}_2 = \left\{ s_1 + s_2:s_1 \in \...
3
votes
1answer
143 views

What are the bounds (upper and lower) for $|A+A|$?

Let $A$ be a finite set of real (or complex) numbers. If I consider sets with small sizes, we have that: If $A$ is the empty set, then $A+A$ is also empty. If $A$ is a singleton, then $A+A$ is ...
17
votes
1answer
704 views

Two sets $X,Y \subset [0,1]$ such that $X+Y=[0,2]$

A set $X\subset \mathbb{R}$ is called nice if, for every $\epsilon > 0$, there are a positive integer $k$ and some bounded intervals $I_1,I_2,...,I_k$ such that $X \subset I_1 \cup I_2 \cup \...
0
votes
2answers
115 views

If the sum of sets is open then one of them is open?

I have managed to prove that if one of two subsets $A$ and $B$ is open, then $A+B$ is open. The next question is: If $A+B$ is open, is it (always) true that either $A$ or $B$ is open (or both)? For ...
1
vote
2answers
56 views

Proving if $|A|\ge 4 \vee |A|\le 2$ then $|A+A|\neq 4$ with direct, contradiction and contraposition

Prove if $|A|\ge 4 \vee |A|\le 2$ then $|A+A|\neq 4$. $A$ is some set and we define $A+B=\{a+b|a\in A, b\in B\}$, $A$ is some subset of the reals. In a direct proof and proof by contradiction I'd ...
1
vote
2answers
278 views

To show sum of two sets is closed in R^2

Let $A=\{(x,y)\in \mathbb R^2:\max\{|y|,|x|\}\leq 1\}$ and $B=\{(0,y)\in \mathbb R^2:y\in \mathbb R\}$. Show that $A+B$ is a closed subset of $\mathbb R^2$ My try: let $z_n=x_n+y_n$ be a sequence in ...