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.
102
questions
57
votes
3
answers
5k
views
Number of elements in the set $\{1,\cdots,n\}\cdot\{1,\cdots,n\}$
Let $A_n=\{a\cdot b : a,b \in \mathbb{N}, a,b\leq n\}$. Are there any estimates for $|A_n|$? Will it be $o(n^2)$?
7
votes
1
answer
721
views
Difference Sets
Suppose
$$
P \subseteq \{1,2,\dots,N\},\quad |P| = K
$$
We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$
Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...
5
votes
3
answers
2k
views
Goldbach conjecture and other problems in additive combinatorics
The field is also known as additive number theory. I am interested in sums $z=x + y$ where $x \in S, y\in T$, and both $S, T$ are infinite sets of positive integers. For instance:
$S = T$ is the set ...
35
votes
5
answers
4k
views
Cliques, Paley graphs and quadratic residues
A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs.
If p=1 mod 4 is a prime, we can define the ...
18
votes
1
answer
869
views
Two conjectures about zero inner products and dissociated sets
The following problems come from something I worked on (with my coauthors) related to proving a new time lower bound for streaming problems. Having worked on these problems for some time with little ...
5
votes
1
answer
468
views
Additivity of upper densities with respect to arithmetic progressions of integers
Let $\mathsf{d}^\star$ be the asymptotic upper density, defined on the power set of positive integers $\mathbf{N}^+$, so that
$$
\mathsf{d}^\star\colon \mathcal{P}(\mathbf{N}^+) \to\mathbf{R}\colon X\...
19
votes
3
answers
1k
views
The sum of integers being a bijection
What are the pairs $(P,Q)$ of subsets of $\mathbb N$ for which the map
\begin{eqnarray*}
P\times Q & \rightarrow & {\mathbb N} \\\\
(p,q) & \mapsto & p+q
\end{eqnarray*}
is a bijection ...
11
votes
2
answers
1k
views
Most dense subset of numbers that avoids arbitrarily long arithmetic progressions
The famous Green-Tao theorem says that there exist arbitrarily long sequences of primes in arithmetic progression.
I am wondering: How dense can a subset $S \subset \mathbb{N}$ be and still avoid
...
3
votes
0
answers
190
views
A conjectural lower bound for $|\{\sum_{k=1}^nka_k:\ a_1,\ldots,a_n\ \text{are distinct elements of }\ A\}|$
Motivated by Question 315568 of mine, I'm interested in the set
$$S(n):=\bigg\{\sum_{k=1}^n k\pi(k):\ \pi\in S_n\bigg\}.$$
It is easy to see that
$$S(1)=\{1\},\ S(2)=\{4,5\}\ \text{and}\ S(3)=\{10,...
3
votes
0
answers
131
views
Reference for a lemma on the asymptotic upper density of special sets with large gaps and intervals
Update. Based on Anthony Quas' comment below, the proof can be made sensibly shorter and the lemma can be slightly generalized by weakening the old assumption (iii).
In a joint paper that I am ...
1
vote
1
answer
377
views
Curious inversion formula in additive combinatorics
Let $S$ be an infinite set of positive integers, and $T=S+S=\{x+y, \mbox{ with } x,y\in S\}$.We definte the following functions:
$N_S(z)$ is asymptotic continuous version of the function counting the ...
0
votes
0
answers
152
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^{...
111
votes
7
answers
8k
views
Is the set $ AA+A $ always at least as large as $ A+A $?
Let $A$ be a finite set of real numbers. Is it always the case that $|AA+A| \geq |A+A|$?
My first instinct is that this is obviously true, and there is a one-line proof which I am foolishly ...
62
votes
5
answers
9k
views
Jean Bourgain's relatively lesser known significant contributions
Jean Bourgain passed away on December 22, 2018.
A great mathematician is no longer with us.
Terry Tao has blogged about Bourgain's death and mentioned some of his more recent significant contributions,...
26
votes
2
answers
1k
views
Partitions to different parts not exceeding $n$
Consider the polynomial $(1+x)(1+x^2)\dots (1+x^n)=1+x+\dots+x^{n(n+1)/2}$, which enumerates subj. How to prove that it's coefficients increase up to $x^{n(n+1)/4}$ (and hence decrease after this)? Or ...
23
votes
3
answers
3k
views
How many different numbers can be obtained as product of first $n$ natural numbers?
Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set
$\{1^{a_1} \cdot 2^{...
20
votes
3
answers
1k
views
Size of set of integers with all sums of two distinct elements giving squares
Are there arbitrarily large sets $\mathcal S=\{a_1,\ldots,a_n\}$ of strictly positive integers such that all sums $a_i+a_j$ of two distinct elements in $\mathcal S$ are squares?
Considering subsets in ...
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 \...
11
votes
1
answer
728
views
What is the smallest cardinality of a set A whose difference A-A contains $n$ consequtive integer numbers?
Problem. What is the smallest cardinality $d(n)$ of a set $A$ of integer numbers such that the difference set $A-A=\{a-b:a,b\in A\}$ contains $n$ consequtive integer numbers?
It can be shown that $(1+...
10
votes
3
answers
543
views
Is each finite group multifactorizable?
Definition. A finite group $G$ is called multifactorizable if for any positive integer numbers $a_1,\dots,a_n$ with $a_1\cdots a_n=|G|$ there are subsets $A_1,\dots,A_n\subset G$ such that $A_1\cdots ...
10
votes
1
answer
542
views
Who was/were the first to note that if $\sum_{x \in X} \frac{1}{x} < \infty$ then the natural density of $X$ is zero?
It is a result of folklore that the natural density of a set $X$ of positive integers such that $\sum_{x \in X} \frac{1}{x} < \infty$ is zero. This is reproved, e.g., in T. Šalát's paper: ...
6
votes
1
answer
154
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 ...
6
votes
1
answer
466
views
Ref. request: Additive probability measure on $\mathcal P({\bf N})$ supplies subset of $\mathbf R$ without Baire property
ZFC proves, among the other things, the existence of a (finitely) additive probability measure $\theta: \mathcal P(\mathbf N) \to \mathbf R$ on the power set of $\mathbf N$ such that $\theta(X) = 0$ ...
5
votes
2
answers
494
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 \...
3
votes
1
answer
237
views
Can we do better than random when constructing dense $k$-AP-free sets
We write $[N]$ to denote $\{1,\dots,N\}$. We say a set $S$ is $k$-AP-free if it lacks non-trivial arithmetic progressions of length $k$.
We define the 2-color van der Waerden number, $w(2;k)$, to be ...
3
votes
2
answers
508
views
Proof of Pollard's inequality
Let $A, B \subseteq \mathbb{Z}_p$, $p$ prime, $|B| \leq |A|$.
If $N_t$ denotes the number of elements of $\mathbb{Z}_p$ having at least $t$ representations as $a+b$, $a \in A, b \in B$, Pollard's ...
3
votes
1
answer
255
views
Is every sufficiently dense well mixed set an additive basis?
Let $B \subset \mathbb{N}$ be a set of natural numbers such that $|B \cap [1,N]| \sim N^\gamma$, for some $\gamma > 0$ with the following property:
For any pair of positive integers $k,n$ we ...
2
votes
1
answer
172
views
Only trivial solution to a pair of constrained linear diophantine equations
Given positive integer $n$, we are looking for a set
of $n$ positive integers $a_i$.
The following linear integer program must have only
the trivial integer solution of all ones.
$0 \le x_i \le \frac{...
1
vote
1
answer
194
views
Covering a finite ring with arithmetic progressions
Let $n\geq 2$ be a positive integer and $k$ be a number between $1$ and $n$. Recently, I came across the following question about $\mathbb Z/n\mathbb Z$ and I wonder if it was studied before. I'd be ...
0
votes
1
answer
652
views
Paradox in additive combinatorics
Let $S$ be an infinite set of positive integers. Let us define the following quantities:
$N_S(z)$ is the number of elements of $S$, less or equal to $z$
$r_S(z)$ if the number of positive integer ...
58
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 ...
49
votes
3
answers
2k
views
Is each squared finite group trivial?
A semigroup $S$ is defined to be squared if there exists a subset $A\subseteq S$ such that the function $A\times A\to S$, $(x,y)\mapsto xy$, is bijective.
Problem: Is each squared finite group ...
31
votes
2
answers
3k
views
The Erdős-Turán conjecture or the Erdős' conjecture?
This has been bothering me for a while, and I can't seem to find any definitive answer. The following conjecture is well known in additive combinatorics:
Conjecture: If $A\subset \mathbb{N}$ and $$\...
28
votes
3
answers
872
views
Ordering subsets of the cyclic group to give distinct partial sums
Suppose that you are given a set $S$ of $k$ nonzero elements from $\mathbb{Z}_n$. Is it always possible to order the elements of $S$, say $a_1,a_2,\dots,a_k$ in such a way that the partial sums $a_1,...
26
votes
1
answer
3k
views
Monochromatic triangles in every two-coloring of the plane?
An old problem (possibly due to Erdős and Graham?): given a triangle $T$ and a two-coloring of the plane, does there necessary exist a monochromatic congruent copy of $T$? Here "monochromatic" means ...
26
votes
3
answers
2k
views
long enough interval of integers to solve a simultaneous congruence
Let $a$, $b$ be two coprime natural numbers. Let $A \subseteq \{0,1,\ldots, a-1\}$ and $B \subseteq \{0,1,\ldots,b-1\}$ be two nonempty sets, which we think of as sets of residues mod $a$ and $b$ ...
26
votes
0
answers
899
views
Which sets of roots of unity give a polynomial with nonnegative coefficients?
The question in brief: When does a subset $S$ of the complex $n$th roots of unity have the property that
$$\prod_{\alpha\, \in \,S} (z-\alpha)$$
gives a polynomial in $\mathbb R[z]$ with ...
24
votes
2
answers
7k
views
EGZ theorem (Erdős-Ginzburg-Ziv)
Erdős, Ginzburg and Ziv prove the following:
Let $n \geq 1$ and $a_1,\ldots, a_{2n-1}\in \mathbb{Z}$. There exist distinct $i_1,\ldots , i_n$
such that
$$
a_{i_1} + \cdots + a_{i_n} \equiv 0 \pmod{n}....
18
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$? ...
17
votes
2
answers
2k
views
A proof of Van der Waerden's theorem using a weakened form of Szemeredi's theorem
Van der Waerden's theorem states that any colouring of the integers in a finite number of colours has monochromatic arithmetic progressions of arbitrary length. Szemerédi's Theorem is a dramatic ...
17
votes
1
answer
1k
views
Sum and product estimate over integers, rationals, and reals
My question is the following: is finding a lower bound for $|A+A\cdot A|$ (as a function of $|A|$) where $A$ is any finite subset of the positive integers equivalent to finding the same lower bound ...
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\...
15
votes
1
answer
972
views
Sets with both additive and multiplicative gaps
I feel that the following problem should have a clean and simple solution, but so far I couldn't find one.
Suppose that $p$ is a prime, and that $A\subseteq\mathbb Z/p\mathbb Z$ is a set such that
...
15
votes
1
answer
404
views
What is the smallest cardinality of a self-linked set in a finite cyclic group?
A subset $A$ of a group $G$ is defined to be self-linked if $A\cap gA\ne\emptyset$ for all $g\in G$. This happens if and only if $AA^{-1}=G$.
For a finite group $G$ denote by $sl(G)$ the smallest ...
14
votes
1
answer
616
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 ...
14
votes
3
answers
1k
views
Density of all n such that 2^n-1 is square free
Is it true that the set $$S:=\{n\in \mathbb N\ |\ 2^n-1 \ \mbox{ is square free}\}$$ has positive density? What can we say when we replace $2^n-1$ with $\frac{a^n-1}{a-1}$?
14
votes
1
answer
2k
views
On the $L^1$-norm of certain exponential sums
I am stuck with an elementary-looking problem, which does not belong to my usual field of research so I eventually decided to ask it on MO.
Let $S$ be a finite set of integers. For $P$ a subset of $S$,...
13
votes
1
answer
454
views
Near-linear mappings from $\mathbb F_p$ to $\mathbb R$
$\newcommand{\F}{{\mathbb F}}$
$\newcommand{\R}{{\mathbb R}}$
$\renewcommand{\phi}{\varphi}$
Let $p\ge 5$ be a prime.
If the functions $\phi_1,\phi_2,\phi_3\colon\F_p\to\R$ satisfy $\phi_1(x)+\...
12
votes
2
answers
867
views
Arithmetic progressions modulo $p$ under the squaring map
I feel that the following problem should be known, but I'm not sure where to look for it.
Fix a real constant $\frac{1}{2} \ge \epsilon > 0$. For varying primes $p$, Let $A_p$ denote the set of ...
12
votes
2
answers
513
views
Small set such that $\{1 , \ldots , n\} \cdot A = \mathbb{Z} / p \mathbb{Z}$
Let $p$ be a large prime and $n < p$. What is the smallest size of a set $A \subset \mathbb{Z} / p \mathbb{Z}$ such that $A \cdot \{1 , \ldots , n\} = \mathbb{Z} / p \mathbb{Z}$? Here $\cdot$ ...