All Questions
Tagged with sumsets co.combinatorics
49
questions
5
votes
1
answer
816
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|^{...
15
votes
2
answers
696
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
0
votes
1
answer
246
views
Khovanskii's theorem on iterated sumsets
I was watching Gowers video lectures "Introduction to Additive Combinatorics" (my question is about the statement he made at the 21st minute) and came across wonderful theorem due to ...
- 288
2
votes
0
answers
163
views
Component-wise sums of permutations
Given a set $S$ containing all possible permutations of a vector $v = (1, 2, 3, ..., n-1, n)$, find the size of the set $P$, where $P$ is defined as the set of possible component-wise sums obtained by ...
- 21
11
votes
2
answers
652
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$, ...
- 22.6k
5
votes
2
answers
225
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 ...
- 2,874
9
votes
0
answers
262
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
2
votes
1
answer
245
views
Different sum combinations of $L$ identical lists of consecutive natural numbers
Given $L$ variables $k_i$ where each $k_{i} \in \{1, 2, 3, \ldots, N\}$ I want to obtain how many different sums $k_{1}+k_{2}+\cdots+k_{L}$ are generated and the value of these sums.
There are $L^N$ ...
- 23
3
votes
2
answers
333
views
Sumsets with the property "$A+B=C$ implies $A=C-B$"
Let $(G,+)$ be an abelian group and $A$, $B$ and $C$ be finite subsets of $G$ with $A+B=C$. One may conclude that $A\subset C-B$. However, $A$ need not be equal to $C-B$. What is a necessary and ...
- 421
0
votes
0
answers
118
views
An exercise about sum-product estimate
I am struggling with 1.11 exercise from the George Shakan "Discrete Fourier Transform".
Let $A \subset \mathbb{Z}/q\mathbb{Z}$ be any set not containing zero with $|A|>\sqrt2q^{5/8}$. ...
- 11
0
votes
1
answer
198
views
Controlling iterated sum sets of "most" of $A+B$
I am reading Tao-Vu book on Additive combinatorics and came across the following lemma. I know that it is better to ask this question on MathStack but I asked few questions before and no one answered ...
- 288
2
votes
1
answer
398
views
Rank of sumsets in matroids
Assume that $G$ is a (finite) abelian group and $M$ is a matroid whose ground set is $G$. Let $X$ and $Y$ be subsets of $G$, and $H$ is the stabilizer of $X+Y$. That is $X+Y+H=X+Y$. We denote the rank ...
- 421
15
votes
1
answer
789
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
2
votes
1
answer
134
views
Equal subset-sums of bounded vectors
Let $S\subseteq \{0,\ldots,n\}^d$ be a set of $d$-dimensional vectors of with bounded, natural, coordinates.
We are given that
$$v'+v_1+\ldots+v_t=u'+u_1+\ldots+u_s$$
where $v_1,\ldots,v_t,u_1,\ldots,...
- 203
5
votes
1
answer
152
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
3
votes
1
answer
247
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 ...
- 22.6k
1
vote
1
answer
205
views
Average size of iterated sumset modulo $p-1$,
Given a prime $p$, what is the average size of the iterated sumset, $|kA|$, modulo $p-1$, with $p$ a prime, and $k$ given, with $A$ chosen at random?
You can pick any type of prime you like for $p$, ...
- 221
1
vote
1
answer
298
views
Does $g+A\subseteq A+A$ imply $g\in A$?
Suppose that $A$ is a subset of a (large) finite cyclic group such that $|A|=5$ and $|A+A|=12$. Given that $g$ is a group element with $g+A\subseteq A+A$, can one conclude that $g\in A$?
- 22.6k
12
votes
2
answers
576
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
19
votes
4
answers
851
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.2k
2
votes
0
answers
39
views
Weighted unrestricted Golomb rulers?
A set of integers
${\displaystyle A=\{a_{1},a_{2},...,a_{m}\}\quad a_{1}<a_{2}<...<a_{m}} $
is a Golomb ruler if and only if
${\displaystyle \forall i,j,k,l\in \left\{1,2,...,m\right\},a_{i}...
- 13.5k
1
vote
0
answers
197
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.
...
- 11
3
votes
1
answer
218
views
On particular sumset properties of permanent?
Denote $\mathcal R_2[n]=\mathcal R[n] + \mathcal R[n]$ to be sumset of integers in $\mathcal R[n]$ where $\mathcal R[n]$ to be set of permanents possible with permanents of $n\times n$ matrices with $...
- 13.5k
4
votes
0
answers
149
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.1k
8
votes
2
answers
591
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\...
- 41.2k
3
votes
0
answers
64
views
What's known about $X$ when $|X(n) + X(n)| < kn$, $n \in \mathbb{N}$, absolute constant $k$?
Let $X$ be an infinite sequence of integers$$x_1 < x_2 < x_3 < \ldots,$$and let $X(n)$ be the set$$\{x_1, x_2, \ldots, x_n\}.$$
Question. What is known about $X$ when we have$$|X(n) + X(n)| &...
- 31
3
votes
1
answer
240
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$ ...
- 265
10
votes
1
answer
537
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\...
- 41.2k
4
votes
2
answers
402
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
2
votes
1
answer
188
views
When does the equality hold in Dias da Silva - Hamidoune Theorem?
Let $p$ be prime number and let $A$ be a $k$-elements subset of $\mathbb{Z}/p\mathbb{Z}$. Dias da Silva - Hamidoune Theorem states that $|h^{\hat{}}A| \geq \min(p, hk -h^2 + 1)$, where $h$ is an ...
- 167
8
votes
1
answer
720
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
3
votes
2
answers
279
views
Partition regular systems: do they have solution in (very dense) set of integers?
A partition regular system is a linear system of equations of the form $A\cdot x=0$, which satisfies a Ramsey-type result (namely, that for each $r>0$ whenever we colour the integers in $r$ classes,...
- 1,483
5
votes
2
answers
527
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
2
votes
1
answer
506
views
Asymptotic of a sum involving binomial coefficients
Good evening, I'm trying to find an asymptotic of this sum:
$$\sum_{j=0}^n (-1)^j {n \choose j} (n - j)^n = n^n - {n \choose 1} (n - 1)^n + {n \choose 2} (n - 2)^n + ... + (-1)^n {n \choose n} (n - ...
- 41
3
votes
3
answers
722
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 (|\...
- 11.7k
10
votes
2
answers
431
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,503
10
votes
2
answers
622
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 $...
- 22.6k
3
votes
1
answer
200
views
On a problem about $GF(2)^n$
For $A\subseteq {\mathbb F}_2^n$ let
$$
Q(A)=\{\alpha+\beta\mid \alpha,\beta \in A,\ \alpha\neq\beta \}.
$$
I want to prove or disprove that if $|A|=2^k+1$ for some integer $k$, then
$$
|Q(A)|\ge2^{k+...
- 197
14
votes
1
answer
612
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
1
answer
302
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,421
3
votes
3
answers
469
views
How to find an integer set, s.t. the sums of at most 3 elements are all distinct?
How to find a set $A \subset \mathbb{N}$ such that any sum of at most three Elements $a_i \in A$ is different if at least one element in the sum is different.
Example with $|A|=3$: Out of the set $A :...
- 71
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,095
5
votes
2
answers
489
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 \...
- 706
13
votes
1
answer
567
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
8
votes
2
answers
763
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
3
votes
1
answer
603
views
Additive set with small sum set and large difference set
I have a question!
Can someone explain how (the intuition, method?) one can try to construct an additive set of cardinality $N$ with a small sum set (around $N$) and a very large difference set (say,...
- 39
11
votes
0
answers
812
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 ...
- 22.6k
4
votes
1
answer
815
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 ...
- 22.6k
15
votes
1
answer
700
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 ...
- 22.6k