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