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$.
81
questions
0
votes
0answers
28 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. ...
0
votes
0answers
17 views
'Volume' of the rank-r matrix manifold?
I know that the manifold of rank-r matrices $\mathcal{M}_r \subset \mathbf{R}^{d_1 \times d_2}$ is $r(d_1 + d_2 - r)$,
and $\epsilon$-covering number is deeply related with Hausdorff dimension.
For a ...
0
votes
1answer
26 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+\...
0
votes
0answers
34 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 ...
1
vote
0answers
52 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.
11
votes
1answer
287 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 ...
2
votes
2answers
121 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 ...
3
votes
1answer
111 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 ...
1
vote
2answers
121 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 ...
0
votes
1answer
32 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|\}...
1
vote
1answer
78 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 ...
5
votes
1answer
180 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$...
4
votes
1answer
109 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,...
4
votes
0answers
86 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 ...
2
votes
1answer
53 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$, ...
1
vote
1answer
31 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 ...
1
vote
1answer
35 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 ...
2
votes
2answers
71 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
59 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= ...
2
votes
0answers
17 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
91 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
35 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
85 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
40 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
51 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
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 ...
4
votes
2answers
335 views
Finding elements such that none add to a perfect square
Bob asks us to find an inļ¬nite set $S$ of positive integers such that the sum of any ļ¬nite 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
69 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
66 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
297 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
24 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
565 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
121 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
48 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
96 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
32 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
355 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 ...
7
votes
3answers
4k 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
391 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
131 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
39 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 ...
5
votes
1answer
799 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
52 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
68 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
2answers
553 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
64 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
46 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
37 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=...
