Questions tagged [additive-combinatorics]
Questions on the subject additive combinatorics, also known as arithmetic combinatorics, such as questions on: additive bases, sum sets, inverse sum set theorems, sets with small doubling, Sidon sets, Szemerédi's theorem and its ramifications, Gowers uniformity norms, etc. Often combined with the top-level tags nt.number-theory or co.combinatorics. Some additional tags are available for further specialization, including the tags sumsets and sidon-sets.
756 questions
3
votes
1
answer
317
views
On sums of a prime and a central binomial coefficient
Let $\mathbb Z^+$ be the set of positive integers. In 1934, Romanoff proved that
$$\liminf_{x\to+\infty}\frac{|\{n\le x:\ 2n+1=p+2^k\ \text{for some prime}\ p\ \text{and}\ k\in\mathbb Z^+\}|}x>0.$$
...
- 18.1k
1
vote
1
answer
274
views
What proportion of vectors in ${\mathbb{F}_2^n}$ have more than $\frac{n+\sqrt{n}}{2}$ ones
Ben Green's "Finite field models in additive combinatorics" (proof of theorem 9.4) states that for sufficiently large $n$, the set $A$ of vectors in ${\mathbb{F}_2^n}$ with more than $\frac{...
2
votes
2
answers
164
views
On even numbers of the form $p+p'+2^k$
Let $\mathbb Z^+$ be the set of positive integers. In 1934, Romanoff proved that
$$\liminf_{x\to+\infty}\frac{|\{n\le x:\ 2n+1=p+2^k\ \text{for some prime}\ p\ \text{and}\ k\in\mathbb Z^+\}|}x>0.$$
...
- 18.1k
0
votes
1
answer
182
views
Whether $2n>10$ can be written as $p+p'+2^a+2^b$ with $p$ and $p'$ consecutive primes?
In a paper published in 1971, R. Crocker proved that there are infinitely many positive odd numbers not of the form $p+2^a+2^b$ with $p$ prime and $a,b\in\mathbb Z^+=\{1,2,3,\ldots\}$. The proof makes ...
- 18.1k
2
votes
0
answers
91
views
Can $w^2+bx^2+cy^2+dz^2$ be universal over a sparse subset of $\mathbb N$?
Let $b,c,d\in\mathbb N=\{0,1,2,\ldots\}$ with $1\le b\le c\le d$. For a subset $S$ of $\mathbb N=\{0,1,2,\ldots\}$, if
$$\{w^2+bx^2+cy^2+dz^2:\ w,x,y,z\in S\}=\mathbb N$$
then we say that $w^2+bx^2+cy^...
- 18.1k
2
votes
1
answer
169
views
Lower bounds for difference sets of finite integer sets
Let $S$ be a finite subset of integer. Let $\{p \leq X\}$ be the set of primes bounded by $X$. Is it true that the set $S-S$ has a subset $A$ of positive density such that
$p \mid a$ for all prime $p \...
- 317
6
votes
2
answers
448
views
A question related to matrix inverse diagonal zero property
$\DeclareMathOperator\supp{supp}$Let a symmetric nonsingular matrix $A \in \mathbb{R}^{2n \times 2n} $ have the following block form
$$ A = \begin{bmatrix}
X & D \\
D^{\top} ...
- 61
7
votes
2
answers
743
views
The number of distinct possible values of $\pm a_1 \pm a_2 \pm \cdots \pm a_n$ for sufficiently large $n$
Conjecture. Assume that $(a_i)_{i = 1}^{\infty}$ is a sequence of positive integers such that $a_{n+1} \leq 1+\sum_{i = 1}^n a_i$ for sufficiently large $n$. If $A_n$ denotes the number of distinct ...
- 161
2
votes
0
answers
395
views
Finding a sum that is always divisible by $1+2+3+\cdots+n$ [closed]
There are $n$ consecutive integers $m,m+1, \ldots, m+n-1$. Prove that you can choose some nonempty subset of these numbers whose sum is divisible by $1+2+\dots+n$.
- 77
0
votes
1
answer
199
views
Ternary Goldbach-type problems
I am looking for problems comparable to the ternary Goldbach problem, which says that every positive odd integer may be written as the sum of three primes. For instance, something of the shape
Is ...
user574181
4
votes
0
answers
264
views
Can $D-D$ be a set of $2$-topological recurrence if $D$ is lacunary?
Background.
For $k \in \mathbb{N}=\{1,2,3,\dots\}$, a set $R \subseteq \mathbb{N}$ is a set of $k$-topological recurrence if for every minimal topological dynamical system $(X,T)$ and every nonempty ...
- 41
3
votes
1
answer
202
views
A universal additive complement
Let's say that two subsets of a group are additive complements of each other if their sumset is the whole group. Suppose that the group is finite of prime order. For a fixed $\alpha\in(0,1)$, what is ...
- 23.5k
2
votes
0
answers
251
views
Equality of multisets
I have tested this statement with several examples and it seems to hold true in all cases. Is there an elegant way to prove it, assuming it is indeed correct? A proof that avoids case-by-case analysis ...
3
votes
0
answers
217
views
On the set $\{\sum_{k=1}^n p_k:\ n = 1,2,3,\ldots\}$
For any positive integer $n$, let $S(n)$ be the sum of the first $n$ primes. Then
$$S(1) = 2,\ S(2)=2+3=5,\ S(3)=2+3+5 =10,\ S(4) = 2+ 3+5+7 =17.$$
By the Prime Number Theorem,
$$S(n)\sim \frac{n^2}2\...
- 18.1k
1
vote
0
answers
125
views
Weighted sums of four primes
Sums of primes have been studied by number theorists for many years. Goldbach's conjecture is the most famous unsolved problem in this direction.
Here I'd like to consider weighted sums of primes. For ...
- 18.1k
6
votes
0
answers
306
views
Questions motivated by Goldbach's conjecture and the four-square theorem
Goldbach's conjecture asserts that for any integer $n>1$ we have $2n=p+q$ for some primes $p$ and $q$. A similar conjecture of Lemoine states that for any integer $n>2$ we can write $2n+1=p+2q$ ...
- 18.1k
1
vote
0
answers
71
views
Dimension of Chowla subspaces
Definition (Chowla subspace).
Let $K \subseteq L$ be a field extension and let $A$ be a $K$-subspace of $L$.
We say that $A$ is a Chowla subspace if for every $a \in A \setminus \{0\}$ one has
$$[K(a):...
- 379
2
votes
0
answers
132
views
Size of Chowla sets
Definition (Chowla subset).
A nonempty subset $S$ of a group $G$ is called a Chowla subset if every element of $S$ has order strictly larger than $|S|$, i.e.
$$\mathrm{ord}(x) > |S| \quad \text{for ...
- 379
3
votes
2
answers
298
views
Sharp additive divisor sum bounds
For $R\to\infty$ and shifts $|h|\le \sqrt{R}$, let $$S(R,h)=\sum_{R\le r<2R} d(r)d(r+h).$$
What is the sharpest upper bound for $S(R,h)$, uniformly for fixed $h$?
user566642
17
votes
0
answers
722
views
How to compute A263996?
Consider the sequence
$$a_n:=\min_{\substack{A\subseteq\mathbb{Z}\\|A|=n}}|(A+A)\cup (A\cdot A)|.$$
This is A263996 in OEIS. (Actually, they restrict to $\mathbb{N}$, but it makes little difference to ...
- 8,150
0
votes
0
answers
153
views
4-Flower free set family of 3-uniform sets (AKA f(3, 4)) largest construction?
On Polymath, the table shows that the largest known 3-uniform 4-flower free set family has size 38, sourced by this paper. I don't have access to the paper though, and wanted to see the set family ...
- 11
1
vote
2
answers
461
views
Largest 3-zero-sum-free subset in $(\mathbb{Z}/4\mathbb{Z})^n$?
I’m investigating the largest subset $H \subseteq (\mathbb{Z}/4\mathbb{Z})^n$ with no three distinct vectors $x, y, z \in H$ such that $x + y + z \equiv 0 \pmod{4}$ (pointwise addition), as posed by ...
- 11
2
votes
2
answers
244
views
$\left\{\frac{x(ax+b)}2+\frac{y(ay-b)}2:\ x,y=0,1,2,\ldots\right\}$ and asymptotic bases of order 2
A subset $A$ of $\mathbb N=\{0,1,2,\ldots\}$ is called an asymptotic base of order $h$ if any sufficiently large $n\in\mathbb N$ belongs to the set
$$hA=\{a_1+\ldots+a_h:\ a_1,\ldots,a_h\in A\}.$$
...
- 18.1k
7
votes
1
answer
542
views
Khovanskii's theorem in nilpotent groups?
In $\mathbb{Z}^d$, a classical result of Khovanskii states that for any finite set $A \subseteq \mathbb{Z}^d$, the sumset $hA := A + \cdots + A$ eventually agrees with a polynomial in $h$; that is, $|...
- 962
0
votes
1
answer
215
views
Unique sums in dilation of sumsets
Let $A \subset [0:d]^n$, then I call $(a,b) \in A^2$ a unique sum $a+b$ cannot be written as $a'+b'$ for some distinct pair $(a',b')$ upto permutation. I conjecture that number of unique sums might be ...
- 341
1
vote
0
answers
214
views
Some conditions related to Maillet's Conjecture and associated research directions
In the study of subindices of group subsets and integers, I have encountered to some properties (conjectures) about the set of prime numbers $\mathbb{P}$:
(1) If $(\mathbb{P}-\mathbb{P})\cap (B-B)=\{0\...
- 1,011
10
votes
1
answer
414
views
Sumset covering problem
I am trying to understand the following problem:
Let $A, B \subset \mathbb{F}_2^n$, and define
$$
c(B) := \min \{ |A| : B \subseteq A + A \}.
$$
I am interested in computing, or at least bounding, the ...
- 103
5
votes
1
answer
322
views
Does the sumset inequality $|A+A|\cdot |B+B| \le |A+B|^2$ hold?
The question is more or less the title, though I suppose it is worth mentioning that the energy version of this statement,
$$ E(A,B)^2 \le E(A,A) E(B,B),$$
does in fact hold (it is the Cauchy--Schwarz ...
- 1,251
2
votes
1
answer
699
views
Why Catalan numbers appear
Let $(x_1,x_2,...,x_{2n+1 })$ be a sequence from 0 and 2, whose members satisfy all conditions
$$
\begin{align}
x_1&\le 1 \\
x_1&+x_2\le 2\\
\vdots &\qquad\vdots\\
x_1&+x_2+\ldots+x_{...
- 37
2
votes
0
answers
166
views
Understanding monomial cancellation in $f^2$ for sparse polynomials with bounded individual degree
Let $f(x_1, \dots, x_n)$ be an $s$-sparse polynomial over a field $\mathbb{F}$, where each variable has individual degree strictly less than $d$ (i.e., $\deg_{x_i}(f) < d$ for all $i$). When we ...
4
votes
0
answers
147
views
Partitioning an infinite sumset into primes and composites
Let $A = \{a_1, a_2, \ldots\}$ and $B = \{b_1, b_2, \ldots\}$ be infinite, strictly increasing sequences of natural numbers. Define $S_{ij} = a_i + b_j$.
Question: Do there exist sequences $A$ and $B$ ...
7
votes
0
answers
367
views
Sets of vectors with pairwise differences having product of coordinates 1
Let $k$ be a field and $f(x_1,...,x_n)=x_1...x_n$.
$\textbf{Question:}$ what is the largest possible size of a set $S\subset k^n$ such that $f(x-y)=\pm1$ for all distinct $x,y\in S$?
The problem can ...
4
votes
1
answer
235
views
"Polynomial evaluation estimates" in the spirit of sum-product estimates
A well-studied problem in additive combinatorics is to give sum-product estimates, i.e. lower bounds on $\max\{|A + A|, |AA|\}$ for a set $A \subseteq \mathbb{F}_p$.
I'm interested in a related ...
- 183
3
votes
2
answers
487
views
Clique number of Cayley graph on finite field
Let $k$ be a finite field and $S\subset k^\times$ a subgroup containing $-1$ (in particular $S$ is cyclic). Consider the Cayley graph $G=\operatorname{Cay}(k,S)$, i.e. the graph whose vertex set is $k$...
2
votes
0
answers
140
views
Understanding the sumset compression theorem in $\mathbb{Z}_2^n$
I was reading Even-Zohar’s paper "On sums of generating sets in $\mathbb{Z}_2^n$", which I found very interesting. Here is the link to the arXiv version of the paper.
I’m particularly ...
- 448
3
votes
1
answer
251
views
Complete subsets in elementary abelian groups
Let's say that a subset $A$ of an abelian group is complete if its subset sum set $\Sigma(A):=\{ \sum_{b\in B} b\colon B\subseteq A, |B|<\infty \}$ is the whole group. Let $\mu(G)$ be the size of ...
- 23.5k
5
votes
2
answers
273
views
Set compression in $\mathbb{Z}_2^n$
Consider the group $\mathbb{Z}_2^n$ and the linear basis $\{e_1, \dots, e_n\}$ for $\mathbb{Z}_2^n$. Elements $x \in \mathbb{Z}_2^n$ are expressed as $x = \sum_{i=1}^n x_i e_i$. Let $[n] := \{1, \dots,...
- 448
2
votes
0
answers
161
views
Additive combinatorics and the Waring-Goldbach problem
I have been reading this article https://arxiv.org/pdf/math/0412220 about the Waring-Goldbach problem. It's really nicely written.
They discuss the Waring-Goldbach problem as well as in the end ...
- 21
3
votes
1
answer
450
views
Lower bound for trilinear character sum in $\mathbb{Z}_2^n$
Consider the group $\mathbb{Z}_2^n$, equipped it with the following dot product: for $a=(a_1,\dots,a_n)\in \mathbb{Z}_2^n$ and $b=(b_1,\dots,b_n)\in \mathbb{Z}_2^n$, define $a\cdot b :=a_1b_1+\dots+...
- 448
1
vote
0
answers
83
views
Does a spectrum with small multiplicative doubling force a low-rank structure for the matrix?
Let $A\in\mathrm{GL}_{n}(\mathbb C)$ and let $\Lambda=\{\lambda_1,\dots,\lambda_n\}$ be its multiset of eigenvalues (with algebraic multiplicities). For any finite multiset $S\subset\mathbb C^{\times}$...
15
votes
1
answer
521
views
How much does a set intersect its square shifts in finite groups?
Let $a>0$. Is there $\varepsilon>0$ such that, for all finite groups $G$ and all subsets $A\subseteq G$ with $|A|\geq a|G|$, we have $\frac{1}{|G|}\sum_{g\in G}|A\cap g^2A|\geq\varepsilon|G|$?
...
- 13.1k
9
votes
0
answers
321
views
Is there a positive density set whose elements are very far from each other?
Let $d=10^{10}$, let $F=\{-1000,\dots,1000\}^d\subseteq\mathbb{Z}^d$. Let $L$ be an extremely big number, e.g. $L>10^{100}$. Is there a subset $A$ of $\{1,\dots,L\}^d$ such that $\frac{|A|}{L^d}>...
- 13.1k
9
votes
1
answer
505
views
On positive integers not representable as $ax^k+by^l+cz^m$
It is well known that for any $a,b,c\in\mathbb Z^+=\{1,2,3,\ldots\}$ there are infinitely many $n\in \mathbb N=\{0,1,2,\ldots\}$ not representable as $ax^2+by^2+cz^2$ with $x,y,z\in\mathbb N$. See, e....
- 18.1k
1
vote
0
answers
382
views
More about the algebraic strengthening of Frankl's union-closed conjecture
Continue my previous question, consider the first conjecture:
Let $\mathcal{F}$ be a union-closed family of subsets of $[n]=\{1,2,...n\}$ and $n$ real numbers $x_1,x_2,...,x_n\geq 1$.
Conjecture: ...
- 1,558
0
votes
0
answers
120
views
Decay of the discrete Fourier transform
Let $G$ be a finite abelian group of order $n$. Let $\hat{G}$ be the dual group of $G$, i.e., the group of characters on $G$. For $f:G\to \mathbb{C}$, we define its Fourier transform $\hat{f}:\hat{G}\...
- 448
3
votes
1
answer
354
views
Difficulty with "Monochromatic products and sums in the rationals" by Bowen and Sabok
I'm studying ""Monochromatic products and sums in the rationals" by Bowen and Sabok and I'm finding some problems understanding some parts of it. For example, I don't see how to get the ...
- 191
7
votes
0
answers
179
views
Set $S$ satisfies several conditions about the sumset, is $S$ the set of powers of $2$?
Same question asked here at MSE
I want to ask a question.
Let $S$ be a proper subset of $\mathbb N$. We call simplest sum representation (SSR) of a positive integer $n$ is a representation of $n$ as a ...
- 1,153
11
votes
1
answer
2k
views
Why is Erdős' conjecture on arithmetic progressions not discussed much, and is there an active pathway to its resolution?
Erdős' conjecture on arithmetic progressions (also known as the Erdős–Turán conjecture) is a major open problem in arithmetic combinatorics. It asserts that if the sum of the reciprocals of the ...
- 147
9
votes
1
answer
612
views
About a reduction in the proof of a 1986 theorem by Spake
Below, $\mathcal P_\text{fin}(\mathbb Z)$ is the finitary power monoid of the additive group of integers, that is, the (additively written) monoid obtained by endowing the family of all non-empty ...
- 11.4k
20
votes
1
answer
1k
views
$AA+AA$ versus $(A+A)(A+A)$
Let $R$ be a commutative ring and let $A\subseteq R$ contain no zero divisors. Under the assumption that $|A+A|\le K|A|$ and $|A\cdot A|\le K|A$, I believe I have a rather simple proof of
$$|(A+A')\...
- 1,251