Questions tagged [sumsets]
The sumsets tag has no usage guidance.
108 questions
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
25
votes
2
answers
3k
views
What is the minimal density of a set A such that A+A = N?
Thinking about the four square theorem and related questions, I found myself wondering: What is the minimal density of a set $A \subset \{0, 1, 2, ... \}$ such that $A + A = \mathbb{N}$?
What I know:
...
- 1,643
20
votes
3
answers
1k
views
A sumset inequality
A friend asked me the following problem:
Is it true that for every $X\subset A\subset \mathbb{Z}$, where $A$ is finite and $X$ is non-empty, that $$\frac{|A+X|}{|X|}\geq \frac{|A+A|}{|A|}?$$
Here ...
- 11.4k
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
19
votes
4
answers
867
views
Size of sets with complete double
Let $[n]$ denote the set $\{0,1,...,n\}$. A subset $S\subseteq [n]$ is said to have complete double if $S+S=[2n]$. Let $m(n)$ be the smallest size of a subset of $[n]$ with complete double. My ...
- 30.6k
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
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
15
votes
2
answers
752
views
Subsets of $(\mathbb{Z}/p)^{\times n}$
There seems to be some combinatorial fact that every subset $A$ of $G=(\mathbb{Z}/p)^{\times n}$ of cardinality $\frac{p^n-1}{p-1}+1$ containing $\vec{0}$ satisfies $(p-1)A=G$. ($p$ is a prime number....
- 153
15
votes
1
answer
807
views
Explicit constant in Green/Tao's version of Freiman's Theorem?
Green and Tao's version of Freiman's theorem over finite fields (doi:10.1017/S0963548309009821) is as follows:
If $A$ is a set in $\mathbb{F}_2^n$ for which $|A+A| \leqslant K|A|$, then $A$ is ...
- 153
15
votes
1
answer
717
views
The hypercube: $|A {\stackrel2+} E| \ge |A|$?
I have a good motivation to ask the question below, but since the post is
already a little long, and the problem looks rather natural and appealing
(well, to me, at least), I'd rather go straight to ...
- 23k
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
13
votes
1
answer
572
views
Size of a certain sumset in $\mathbb{Z}/p^2\mathbb{Z}$
We are interested in estimating the size of a certain sumset in $\mathbb{Z}/p^2\mathbb{Z}$. Let $p$ be an odd prime, $g$ a primitive root modulo $p^2$, and $A=\langle g^p\rangle$ the unit subgroup of ...
- 165
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
12
votes
1
answer
353
views
Number of orders of $k$-sums of $n$-numbers
Suppose we have a $n$-element set $S$. Denote the set of its $k$-element subsets by $K$ ($|K|=\binom{n}{k}$).
If the elements of $S$ are real numbers then to each $k$-element subset we can associate ...
- 1,431
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
11
votes
2
answers
661
views
$\mathbb Z/p\mathbb Z=A\cup(A-A)$?
$\newcommand{\Z}{\mathbb Z/p\mathbb Z}$
Can one partition a group of prime order as $A\cup(A-A)$ where $A$ is a subset of the group, $A-A$ is the set of all differences $a'-a''$ with $a',a''\in A$, ...
- 23k
11
votes
0
answers
830
views
Cliques in the Paley graph and a problem of Sarkozy
The following question is motivated by pure curiosity; it is not a part
of any research project and I do not have any applications. The question
comes as an interpolation between two notoriously ...
- 23k
10
votes
1
answer
547
views
what is the status of this problem? an equivalent formulation?
R. Guy, Unsolved problems in number theory, 3rd edition, Springer, 2004.
In this book, on page 167-168, Problem C5, Sums determining members of a set, discusses a question Leo Moser asked: suppose $X\...
- 43.2k
10
votes
2
answers
641
views
Sumsets and dilates: does $|A+\lambda A|<|A+A|$ ever hold?
The following problem is somehow hidden in this recently asked question, but I believe that it deserves to be asked explicitly.
Is it true that for any finite set $A$ of real numbers, and any real $...
- 23k
10
votes
1
answer
287
views
Freiman inequality for projective space?
This question is suggested by some results in a paper I am writing. I would like to write it down there but want to make sure that it is not known or at least MO-hard.
Freiman's inequality states ...
- 30.6k
10
votes
2
answers
445
views
Iterated sumset inequalities in cancellative semigroups
This question is motivated by the following well-known theorems:
Thm (Plünnecke): If $A$ is a finite nonempty subset of an abelian group, then for every $n$ we have $|A^n| \le \frac{|AA|^n}{|A|^n}|A|$...
- 8,810
9
votes
0
answers
265
views
If $A+A+A$ contains the extremes, does it contain the middle?
Let $b \ge 1$ and $A\subseteq [0,b]$ be a set of integers (all intervals will be of integers).
Write $hA := \underbrace{A + \ldots + A}_{h\text{ summands}} = \{ \sum_{i=1}^h a_i ~|~a_i \in A,\, \...
- 825
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
596
views
Do Minkowski sums have anything like calculus?
Is there anything resembling differential calculus over the space of (nicely behaved) regions in $\mathbb{R}^d$, where addition is interpreted in terms of Minkowski sums? For example, it is known ...
- 81
8
votes
1
answer
326
views
Sumsets and a bound
Let $q$ be a positive integer. Is it true there exists a constant $C_q$ such that the following inequality holds for any finite set $A$ of reals:
$$\displaystyle |A+qA|\ge (q+1)|A|-C_q\qquad (1)$$
I ...
- 1,090
8
votes
1
answer
723
views
Does $|A+A|$ concentrate near its mean?
Fix $N$ to be a large prime. Let $A \subset \mathbb{Z}/N\mathbb{Z}$ be a random subset defined by $\mathbb{P}(a \in A) = p$, where $p = N^{-2/3 + \epsilon}$ for some fixed $\epsilon > 0$. My ...
- 2,283
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
1k
views
Minkowski sum of polytopes from their facet normals and volumes
By Minkowski's work in the early 1900s, every polytope $P\subset\mathbb R^n$ is determined up to translation by its unit facet normals $u_1,\dots,u_k$ and facet volumes $\alpha_1,\dots,\alpha_k$. ...
- 373
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
7
votes
0
answers
177
views
Sumsets that contains many squares, Improvement on the bound
I'm being troubled by this problem on AoPS:
https://artofproblemsolving.com/community/c6h1998237p13955033
I searched for any literature related to it such as
Nguyen, Hoi H., and Van H. Vu., Squares ...
- 73
6
votes
1
answer
444
views
A problem related with 'Postage stamp problem'
A friend of mine taught me this question. I found that it is related with 'Postage stamp problem' (though it does not seem to be same).
Let $m,a_1\lt a_2\lt \cdots\lt a_n$ be natural numbers. Now let ...
- 4,757
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
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
6
votes
0
answers
176
views
Normality and small doubling
Suppose that $A$ is a finite, generating subset of a group $G$, and that $H$ is a subgroup such that $A^2$ is a union of left $H$-cosets; moreover, $H$ is maximal subject to this property. Is it true ...
- 23k
5
votes
2
answers
550
views
Can you simplify (or approximate) $\sum_{n=0}^{N-1} \binom{N-1}n \frac{(-1)^n}{n+1} e^{-\frac{n}{2(n+1)}\lambda}$?
Let $\binom x y$ be the binomial coefficient. I am trying to get a better understanding of the sum
$$
f(N,\lambda)=\sum_{n=0}^{N-1}\binom{N-1}n\frac{(-1)^n}{n+1} e^{-\frac{n}{2(n+1)}\lambda}
$$
as a ...
- 345
5
votes
1
answer
1k
views
Estimate of Minkowski sum
Let A $\subset [0:2]^n$, where $[0:2]=\{0,1,2\}$, then define $2A= \{ a+b\mid a,b \in A \}$. I wanted to know the best known lower-bound estimates for $|2A|$.
I intuitively expect that $|2A| \geq |A|^{...
- 343
5
votes
1
answer
279
views
Element with unique representation in A+B
Let $A, B \subseteq \mathbb{Z}$ be finite subsets of the integers. Then there exists an element in $A+B$ with a unique representation as a sum of an element in $A$ and an element in $B$, namely $\max(...
- 83
5
votes
2
answers
270
views
Progressions in sumset or complement
Fix $\epsilon>0$.
For all large $N$, does there exist $A\subset [N]:=\{1,\dots,N\}$ such that both $A+A$ and $A^c:=[N]\setminus A$ lack arithmetic progressions of length $N^\epsilon$?
I am aware ...
- 3,499
5
votes
1
answer
218
views
Computational version of inverse sumset question
Let $p$ be prime and $\mathbb{F}_p$ the finite field with $p$ elements. Suppose we have a set $B\subseteq \mathbb{F}_p$ satisfying $|B|<p^{\alpha}$ for some $0<\alpha<1$ and there exists $A\...
user156885
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
5
votes
0
answers
185
views
Gaps in sumsets and difference sets
a) Let $S\subset \{1,2,\dotsc,N\}$ be a fairly thick set (with at least $N^{1-\epsilon}$ elements, say). Suppose that the intersection of, say,
$$3 S - 3 S = \{a_1+a_2+a_3-(a_4+a_5+a_6): a_1,\dotsc,...
- 20.2k
4
votes
2
answers
267
views
Existence of m infinite subsets in an arbitrary group such that all products of one element from each (in order) are distinct
Is it true that for every infinite group $G$ and every $m\in\mathbb{N}$ there are infinite subsets $A_0,\dots,A_{m-1}$ such that all the products $a_0\cdot\dots\cdot a_{m-1}$ with $a_i\in A_i$ are ...
- 73
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
4
votes
2
answers
207
views
Lower bounding a sumset quantity
Given $A,B \subset[0,...,d]^n$ such that $A \cap B = \phi$. Can we show
$$ |(2A \cup 2B) \triangle (A + B)| \geq \Omega_d({\rm poly}(|A|,|B|))$$
where $2A = A+A, 2B = B+B$ and we are taking the ...
- 343
4
votes
1
answer
280
views
Unique representation and sumsets
Let $A$ be a finite, nonempty subset of an abelian group, and let $2A:=\{a+b\colon a,b\in A\}$ and $A-A:=\{a-b\colon a,b\in A\}$ denote the sumset and the difference set of $A$, respectively.
If ...
- 23k
4
votes
1
answer
156
views
$B_k[1]$ sets with smallest possible $m = \max B_k[1]$ for given $k$ and $n = \lvert B_k[1]\rvert$ elements
Sidon sets are sets $A \subset \mathbb{N}$ such that for all $a_j,b_j \in A$ holds
$$a_1+a_2=b_1+b_2 \iff \{a_1,a_2\}=\{b_1,b_2\}.$$
Thus if you know the sum of two elements, you know which elements ...
- 71
4
votes
1
answer
864
views
Intersecting Hamming spheres: is $|A\stackrel k+E|\ge|A|$?
Since my original posting some ten days ago, I discovered an amazing
example which changed significantly my perception of the problem.
Accordingly, the whole post got re-written now.
The most general ...
- 23k
4
votes
0
answers
150
views
Dividing a finite arithmetic progression into two sets of same sum: always the same asymptotics?
This is inspired by the recent question How many solutions $\pm1\pm2\pm3…\pm n=0$.
The oeis entries A063865 linked to this question and A292476/A156700 for the related one "How many solutions $\pm1\...
- 13.4k
4
votes
0
answers
127
views
Restricted addition analogue of Freiman's $(3n-4)$-theorem
There is a well-known theorem of Freiman saying that if $A$ is a finite set of integers with $|2A| \le 3|A|-4$, then $A$ is contained in an arithmetic progression with at most $|2A|-|A|+1$ terms. Is ...
- 41