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.
744 questions
1 vote
0 answers
218 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
197 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\...
- 17.5k
1 vote
0 answers
111 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 ...
- 17.5k
6 votes
0 answers
294 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$ ...
- 17.5k
1 vote
0 answers
64 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
110 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
285 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
654 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 ...
- 7,853
0 votes
0 answers
145 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
434 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
242 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\}.$$ ...
- 17.5k
7 votes
1 answer
531 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
210 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
210 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
406 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
318 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
686 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
162 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
146 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
364 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
227 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
474 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
138 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
242 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.4k
5 votes
2 answers
269 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
158 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
448 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
514 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|$? ...
- 12.7k
9 votes
0 answers
317 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}>...
- 12.7k
9 votes
1 answer
495 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....
- 17.5k
1 vote
0 answers
380 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
118 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
349 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
169 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
611 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
5 votes
2 answers
263 views
Solution-free set structure for x + 3y = z
I've been considering this theorem, theorem 1.2 in https://users.renyi.hu/~sos/1999_On_the_Structure_of_Sum_Free_Sets_2.pdf, that states $$ \textbf{Theorem } \quad \text{If } A \subseteq [n] \text{ is ...
1 vote
0 answers
269 views
Upper bound on the Frobenius number by Erdős-Graham
I am reading the proof by Erdős and Graham on the upper bound of the Frobenius number (i.e., the largest number that cannot be expressed as a nonnegative linear combination of basis elements). Below, ...
4 votes
0 answers
235 views
Sets $S$ of natural numbers such that most natural numbers admit exactly two representations as sums of numbers in $S$
My main question is the following, but I am more broadly interested in any potentially interesting variants that may come up, as well as references for similar questions in the literature. Main ...
- 585
5 votes
2 answers
263 views
Petridis' inequality and Plünnecke's inequality with different summands
One version of the Plünnecke–Ruzsa inequality is the following. Theorem 1 (Plünnecke–Ruzsa inequality). Let $A, B_1, \ldots, B_m$ be finite subsets of an abelian group and suppose that $|A+B_i|\le K_i|...
- 1,251
1 vote
0 answers
79 views
Inequality Comes from Bohr Set
I am reading the paper from Helfgott and de Roton "Improving Roth’s Theorem in the Primes". I am unable to find out why we need $\varepsilon^{\delta^{-5/2}}\geq N^{-1/2}$ to have $|B|\geq \...
- 281
4 votes
0 answers
194 views
If $X$ is a subset of $\mathbb N$ containing $0$ and its lower asymptotic density is not too small, then $nX = (n+1)X$ for some $n$
Given $m \in \mathbb N$ and $X \subseteq \mathbb N$, denote by $mX$ the $m$-fold sum of $X$, that is, $$ mX := \{x_1 + \cdots + x_m : x_1, \ldots, x_m \in X\} \subseteq \mathbb N; $$ and by $\mathsf ...
- 11.4k
0 votes
0 answers
357 views
Additive combinatorics for Ramanujan's tau function
Ramanujan's tau function defined over $\mathbb Z^+=\{1,2,3,\ldots\}$ is given by $$q\prod_{n=1}^\infty (1-q^n)^{24}=\sum_{n=1}^\infty\tau(n)q^n\quad \ (|q|<1).$$ It plays an important role in the ...
- 17.5k
1 vote
0 answers
106 views
Specific counting function in $\mathbb{Z}_2^n$
Let $A, B, C \subseteq \mathbb{Z}_2^n$. Define $r(A, B, C) := |\{(a, b, c) \in A \times B \times C : a + b = c\}|$. For $1 \leq a \leq 2^n - 1$, let $A_a \subseteq \mathbb{Z}_2^n$ denote the set ...
- 448
6 votes
1 answer
392 views
Kneser's theorem on the structure of a set of non-negative integers whose lower asymptotic density is positive
Let $\mathrm{d}_\ast$ be the lower asymptotic density on $\mathbb N$ (the non-negative integers), that is, the function $$ \mathcal P(\mathbb N) \to [0, 1] \colon A \mapsto \liminf_{n \to \infty} \...
- 11.4k
4 votes
1 answer
341 views
Maximum density of sum-free sets with respect to Knuth's "addition"
A subset $S\subseteq\mathbb{N}$ is said to be sum-free if whenever $s,t\in S$, then $s+t\notin S$. For instance the set of odd numbers is sum-free and has (lower and upper) asymptotic density 1/2. ...
- 53.2k
4 votes
0 answers
229 views
Lemma in Roth's Theorem for Primes
I am reading Ben Green's paper Roth's Theorem in the Primes and I don't follow the proof of Lemma 6.1. I am not sure where the fact there are no more than $n^{3/4}$ elements $x\in A_0$ with $x\leq n^{...
- 281
1 vote
0 answers
72 views
Lower bound for restricted sumset in ordered groups
Recently in The restricted sumsets in finite abelian groups it is proved that Suppose that $k \geq 2$ and $A$ is a non-empty subset of a finite abelian group $G$ with $|G| > 1$. Then the ...
