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