Questions tagged [sumsets]
The sumsets tag has no usage guidance.
23 questions
0
votes
0
answers
167
views
General asymptotic result in additive combinatorics (sums of sets)
Let $S_1,\cdots,S_k$ be $k$ infinite sets of positive integers. Let $N_i(z)$ be the numbers of elements in $S_i$ that are less or equal to $z$. Let us further assume that
$$N_i(S) \sim \frac{a_i z^{...
- 3,098
18
votes
4
answers
2k
views
Number of vectors so that no two subset sums are equal
Consider all $10$-tuple vectors each element of which is either $1$ or $0$. It is very easy to select a set $v_1,\dots,v_{10}= S$ of $10$ such vectors so that no two distinct subsets of vectors $S_1 \...
- 3,377
6
votes
1
answer
155
views
Trisecting $3$-fold sumsets: is the middle part always thick?
Here is a truly minimalistic and seemingly basic question which should have a simple solution (I hope it does).
Let $A$ be a finite set of integers with the smallest element $0$ and the largest ...
- 23k
5
votes
2
answers
517
views
Anticoncentration of the convolution of two characteristic functions
Edit: This is a question related to my other post, stated in a much more concrete way I think.
I am interested in anything (ideas, references) related to the following problem:
Suppose that $A \...
- 696
59
votes
2
answers
4k
views
For a finite set A of positive reals, prove that the set A + A - A contains at least as many positive as negative elements
I am currently working on a proof that would need to use the following theorem that I cannot prove:
"Let $A$ be a finite set of positive real numbers. Then, the set $A + A - A$ contains at least ...
- 643
26
votes
1
answer
786
views
Distribution of $a^2+\alpha b^2$
It is well known that size of the set of positive integers up to $n$ that can be written as $a^2+b^2$ is asymptotic to $C \frac{n}{\sqrt{\log n}}$. Here I'm interested mostly in the weaker fact that ...
- 1,235
19
votes
3
answers
1k
views
Decomposing a finite group as a product of subsets
My friend Wim van Dam asked me the following question:
For every finite group $G$, does there exist a subset $S\subset G$ such that $\left|S\right| = O(\sqrt{\left|G\right|})$ and $S\times S = G$? ...
- 9,833
16
votes
2
answers
2k
views
Sets that are not sum of subsets
Let $\mathcal P$ be the set of finite subsets of $\mathbb Z_{\geq 0}$ , each of them contains $0$. We say that $A \in \mathcal P$ is indecomposable if it is not $B+C$ (the sum set of $B,C$) with $B,C\...
- 30.6k
14
votes
1
answer
633
views
Minimal "sumset basis" in the discrete linear space $\mathbb F_2^n$
For a set $C\subseteq \mathbb F_2^n$, let $2C=C+C:=\{\alpha+\beta\colon \alpha,\beta\in C\}$.
I want to find $C$ of the smallest possible size such that $2C=\mathbb F_2^n$. Let $m(n)$ be the size of a ...
- 197
12
votes
2
answers
661
views
The $r$-dimensional volume of the Minkowski sum of $n$ ($n\geq r$) line sets
Let $n$ line sets be $\mathcal{S}_i=\{a\mathbf{h}_i:0 \le a \le 1\}$, for $1 \le i \le n$, where $\{\mathbf{h}_1,\cdots,\mathbf{h}_n\}$ is a vector group of rank $r$ in the $r$-dimensional Euclidean ...
- 550
11
votes
1
answer
617
views
Lower bounds for $|A+A|$ if $A$ contains only perfect squares
Let $A$ a set with $|A|=n$ that contains only perfect squares of integers.
What lower bounds can we give for $|A+A|$?
I think the lower bound $\gg \frac{n^2}{\sqrt{log \,n}}$ holds (this would be ...
- 1,235
8
votes
2
answers
618
views
sum-sets in a finite field
Let $\mathbb{F}_p$ be a finite field, $A=\{a_1,\dots,a_k\}\subset\mathbb{F}_p^*$ a $k$-element set, for $k<p$. $\mathfrak{S}_k=$permutation gp.
Question. Is it true there is always a $\pi\in\...
- 43.2k
8
votes
2
answers
797
views
A sum-product estimate in Z/p^2Z
We are interested in a sum-product type estimate. Let $p$ be an odd prime, and let $A$ be the order $p-1$ subgroup of $(\mathbb{Z}/p^2\mathbb{Z})^\times$. That is, let $A = \langle g^p \rangle$, where ...
- 165
7
votes
1
answer
194
views
Trisecting $3$-fold sumsets, II: is the middle part ever thin?
This is a refined version of the question I asked yesterday.
Let $A$ be a finite set of integers with the smallest element $0$ and the largest element $l$. The sumset $C:=3A$ resides in the interval $[...
- 23k
6
votes
1
answer
262
views
Is there some sort of formula for $\tau(S_n)$?
Let $G$ be a finite group. Define $\tau(G)$ as the minimal number, such that $\forall X \subset G$ if $|X| > \tau(G)$, then $XXX = \langle X \rangle$.
Is there some sort of formula for $\tau(S_n)$, ...
- 2,618
4
votes
2
answers
427
views
How big must the sumset $A+A$ be if $A$ satisfies no translation-invariant equations of low height?
Suppose $A$ is a finite subset of an abelian group. If there is no solution to $ma+nb=(m+n)c$ with $0\leq m,n\leq M$, can we bound $|A+A|$ from below? I am interested if one can obtain bounds much ...
- 41
3
votes
3
answers
749
views
Is the sumset or the sumset of the square set always large?
Let A be a finite subset of $\mathbb{N}$, $\mathbb{R}$, or a sufficiently small subset of $\mathbb{F}_{p}$.
Do we have a lower bound of the form $|A|^{1+\delta}$ on the following quantity:
$$\max (|\...
- 13k
3
votes
1
answer
361
views
Prime gap distribution in residue classes and Goldbach-type conjectures
Update on 7/20/2020: It appears that conjecture A is not correct, you need more conditions for it to be true. See here (an answer to a previous MO question).
The general problem that I try to solve is ...
- 3,098
3
votes
1
answer
146
views
Bounding the size of certain sumsets in the plane
Let $A$ be a finite set in $\mathbb{R}^2$ of $k^2$ elements and consider a set $B=\{x_1,x_2,x_3,x_4\}$ such that the points in $B$ are in general position (no three points on a line).
Question 1: Is ...
- 2,288
2
votes
0
answers
230
views
Generating Subsets of a Multiset in Ascending Order of the Sums of the Elements of the Subset
I am trying to come up with an algorithm where you can generate combination from a set in a order such that their sums are in increasing order. This set has to be a multiset i.e. repetition allowed.
...
- 21
2
votes
0
answers
137
views
The set of lengths of $nX$ gets larger and larger for every non-zero, non-empty, finite $X \subseteq \mathbf N$ with $0 \in X$
Let $H$ be a multiplicatively written monoid with identity $1_H$. Given $x \in H$, we take ${\sf L}_H(x) := \{0\}$ if $x = 1_H$; otherwise, ${\sf L}_H(x)$ is the set of all $k \in \mathbf N^+$ for ...
- 10.5k
1
vote
1
answer
189
views
Sumset achieving extreme upper bound [closed]
It is trivial that $|A_1 + \cdots + A_h| \leq |A_1|\cdots |A_h|$, where $h \geq 2$ and $A_i \subseteq \mathbb{Z}$ are nonempty finite sets and $A_1 + \cdots + A_h :=\{a_1 + \cdots + a_h : a_i \in A_i ~...
- 167
0
votes
1
answer
489
views
Congruential equidistribution, prime numbers, and Goldbach conjecture
Let $S$ be an infinite set of positive integers, $N_S(z)$ be the number of elements of $S$ less than or equal to $z$, and let
$$D_S(z, n, p)= \sum_{k\in S,k\leq z}\chi(k\equiv p\bmod{n}).$$
Here $\chi$...
- 3,098