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$.
92
questions
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 ...
- 243
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 ...
- 103
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-...
- 103
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 ...
- 11
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 ...
- 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 $...
- 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 ...
- 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) \...
- 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. ...
- 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+\...
- 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 ...
- 109
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.
- 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 ...
- 3,509
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 ...
- 101k
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 ...
- 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 ...
- 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|\}...
- 159
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 ...
- 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$...
- 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,...
- 2,153
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 ...
- 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$, ...
- 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 ...
- 12.4k
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 ...
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?
- 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 ...
- 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 ...
- 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 ...
- 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= ...
- 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 ...
- 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\...
- 2,035
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 ...
- 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 \...
- 235
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\}$?
- 235
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 ...
- 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 ...
- 11
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 ...
- 77
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?
- 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 ...
- 619
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 ...
- 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?
- 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 ...
- 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$...
- 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 $...
- 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 ...
- 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 ...
- 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 ...
- 115
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+.....
- 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 ...
- 50.2k
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 ...
- 181