# 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.

665
questions

3
votes

2
answers

201
views

### Unique "clique" of differences in $\mathbb{Z}/m\mathbb{Z}$

Are there absolute constants $0 < \epsilon < 1$ and $N \in \mathbb{N}$ such that the following holds: For every $m \in \mathbb{N}$ and every $A \subseteq \mathbb{Z}/m\mathbb{Z}$ with $\frac{\...

1
vote

0
answers

70
views

### Szemeredi Regularity Lemma - Reasonable Bounds

Recently, I came across the wonderful Szemeredi regularity lemma and I was wondering. Are these "natural/reasonable/standard" examples of random graphs families, for which the number of $\...

2
votes

0
answers

255
views

### On $(k,\ell)$-sumfree sets

Call a set $\mathcal S \subset \mathbb N$ to be $(k,\ell)$-sumfree if there are no non-trivial solutions to the equation
$$x_1+\dots +x_k = y_1+\dots +y_\ell$$
in the set (for distinct $x_i$'s and $...

3
votes

0
answers

162
views

### Bourgain-Gamburd-like theorems in the non-algebraic case

For $\mu$ a Borel probability measure on the compact group $G=\operatorname{SU}(d)$, Bourgain-Gamburd prove that the spectral radius of the associated operator on $L^2(G)$ is strictly less than one, ...

5
votes

2
answers

553
views

### Representing natural numbers as sums of distinct prime powers

I am investigating whether every natural number $n > 18$ can be represented as a sum $p_1^{m_1} + \dots + p_k^{m_k}$, where $p_1, \dots, p_k$ are distinct primes, and $m_1, \dots, m_k$ are distinct ...

0
votes

1
answer

40
views

### Bounding maximum sum of integer matrix entries in a non-attacking rook placement

Let $A =(a_{ij})$ be a $m \times n$ matrix with nonnegative integer entries bounded above by $k$. To find the set of entries of $A$ in a non-attacking rook placement such that the sum $S$ of them is ...

0
votes

0
answers

74
views

### Number of solutions $x$ of equation $a_1 b_1^x + \dotsb + a_n b_n^x=0$ over a finite field

Let $F$ be a finite field and let $a_1, b_1, \dotsc, a_n, b_n \in F$ be field elements. I am interested in the number of solutions $0\leq x \leq |F|-1$ such that
\begin{equation}\label{e:1}
a_1 b_1^x +...

1
vote

1
answer

156
views

### Density of a set of numbers whose prime factors are defined by congruences

Let $S$ be the set of positive integers not divisible by $3$ where if $p$ is a prime factor of $n \in S$ and $p \equiv 1\bmod 3$ then $p^2$ does not divide $n$, but if $p\equiv2 \bmod 3$ then $p^2$ ...

5
votes

1
answer

268
views

### Expected number of coin flips before you see a $k$-term arithmetic progression of heads

Let $\{X_i\}_{i \in \mathbb Z_+} $ be independent fair coin flips. Write $S := \{i \in \mathbb Z_+\, | \, X_i \text{ is heads}\}$, and define, for an integer $k \geq 3$,
$$Y := \inf \{n \in \mathbb N \...

0
votes

0
answers

75
views

### High probability bound on number of sparse solutions to Gaussian linear system

Suppose we have a random matrix $A \in \mathbb{R}^{m \times n}$ with all entries i.i.d. from the standard Normal distribution $\mathcal{N}(0, 1)$. Suppose $k$ divides $n$, and let $S \subseteq \mathbb{...

6
votes

2
answers

1k
views

### Acyclic matching property in $\mathbb{Z}/p\mathbb{Z}$

Let $B$ be a finite subset of the group $G$ which does not contain the neutral element. For any subset $A$ in $G$ with the same cardinality as $B$, a matching from $A$ to $B$ is defined to be a ...

1
vote

0
answers

270
views

### On fifth powers forming a Sidon set

We call a set of natural numbers $\mathcal S$ to be a Sidon Set if $a+b=c+d$ for $a,b,c,d\in \mathcal S$ implies $\{a,b\}=\{c,d\}$. In other words, all pairwise sums are distinct.
Erdős conjectured ...

2
votes

1
answer

129
views

### Are there a few input bits that randomize the output of an $\mathbb{F}_2$ polynomial?

Suppose $f:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$ is a degree $d$ polynomial and $\epsilon>0$ is some real number. Does there necessarily exist a set $C\subset [n]$ of coordinates with the size of ...

27
votes

1
answer

2k
views

### Is every real number in [0,1] a product of three (or more) Cantor set's numbers?

It is well known that every number $x$ in the unit interval $[0,1]$ is the arithmetic mean of two elements of the (triadic) Cantor set $C$. The way to see it I like the most: the Cantor set is the ...

0
votes

0
answers

175
views

### Upper bound of number of different rows for a binary matrix

Let $\mathcal{X} \subseteq \mathbb{R}^n$ be a measurable space, Fix $m,q \in \mathbb{N}^*$, (the $m$ $x_i$'s are i.i.d and follow distribution $\mathcal{D}$)
and $X = (x_1, \dots, x_m) \sim \mathcal{D}...

2
votes

2
answers

339
views

### Why can we not find exact values for sizes of cap sets for $d>6$?

I've been reading about cap sets in $\mathbb{F}_3^d $ over the past couple of days and wondered why we can only find bounds, as opposed to exact values, for (maximum) sizes of cap sets for $d>6$. ...

24
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
vote

0
answers

68
views

### subsets of $\mathbb{N}$ whose shifts have finite intersection property in density

I am interested in proving the statement:
Let $S\subseteq\mathbb{N}$ such that for every $r\in\mathbb{N}$ and for every $k_{1}$, $k_{2}$, $\ldots$, $k_{r}\in\mathbb{N}$, the set $\big(S-k_{1}\big) \...

16
votes

2
answers

965
views

### The Stable Set Conjecture

A set $\mathcal S$ of positive integers is called stable if for every fixed positive integer $d$, the relation
$$n\in \mathcal S \iff dn\in \mathcal S$$
holds for almost all positive integers $n$. ...

9
votes

1
answer

439
views

### Growth of powers of symmetric subsets in a finite group

(This question was originally asked on Math.SE, where it was answered in the abelian case)
Let $G$ be a finite group, and let $A$ be a symmetric subset of $G$ containing the identity (i.e., $A^{-1}=A$ ...

2
votes

1
answer

210
views

### Structural description of Bohr sets in $\mathbb{Z}_N$

Definition 1. Let $\Gamma\subset \widehat{G}$ and $\delta\in [0,2]$. The Bohr set with frequency set $\Gamma$ and width $\delta$ is the set $\text{Bohr}(\Gamma; \delta)= \big\{x\in G: |\chi(x)-1|\leq \...

8
votes

1
answer

423
views

### When can $L$ sets of the form $\{a,b,a+b\}$ partition $\{1,2,\dots, 3L\}$?

Firstly, this question has been posted to Math StackExchange with no complete answer so far.
Consider a set of the form $\{a,b,a+b\}$ where $a$ and $b$ are positive integers with $b > a$. I will ...

40
votes

2
answers

2k
views

### Is number of different sums monotone?

Suppose you have a set $S$ consisting of $n$ different integers.
Let $$W_k = \#\biggl\{x\in\Bbb Z\colon \text{there exists } T \subseteq S,\, \#T=k,\, \sum_{a \in T} a = x\biggr\}.$$
My question is: ...

0
votes

1
answer

150
views

### Upper bounds estimates of Minkowski sum

Let $A,B \subset \{0,...,d\}^n$, do we have any result that says $|A+B| \leq \mathcal{O}_d(|A|\cdot |B|)^\tau$ for $\tau < 1$. The case $\tau = 1$ is trivial, and due to the restricted setting, I ...

1
vote

0
answers

142
views

### On two formulas involving the $k$-fold divisor function $d_k$ and the function $r_k$

I have a puzzle which needs some help form the experts here. Let $d(n)$ be the divisor function, and $d_k(n)$ the $k$-fold divisor function.
I) It is known that, for any positive integer $h$,
$$d(n+h)...

5
votes

1
answer

901
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

717
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....

1
vote

1
answer

166
views

### Instance of polynomial van der Waerden without good bounds

Let $P\subset \Bbb{Z}[X]$ be a finite set of polynomials with constant-term zero. Then, polynomial vdW says:
For eacg finite $r$, there exists some $N=N(P,r)$, such that every $r$-coloring $C:\{1,\...

5
votes

1
answer

315
views

### Primitive recursive bounds for multidimensional polynomial vdW / HJ

In Shelah's paper 679, he proves primitive recursive bounds for the polynomial Hales-Jewett theorem and thus for the polynomial van der Waerden theorem.
How about for the multidimensional polynomial ...

1
vote

1
answer

310
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 ...

1
vote

0
answers

121
views

### The number of incidences between points and parabolas on $\mathbb{R}^2$

I was reading Adam Sheffer's book "Polynomial Methods and Incidence Theory" and I tried to solve the following exercise:
Exercise 1.1 Construct a set $\mathcal{P}$ of $m$ points and a set $\...

11
votes

1
answer

657
views

### A variant of the corners problem

Question: What is the size of the largest subset of $[n]^2$ containing no three point configurations of the form $(x,y), (x,y+d), (x+d,y')$ with $d \neq 0$? In particular, is it at most $O(n)$?
Recall ...

0
votes

0
answers

170
views

### Equivalent formulation of Szemerédi-Trotter theorem

I am reading the first chapter of Adam Sheffer's book "Polynomial Methods and Incidence Theory" and in Lemma 1.15 he proves an equivalent formulation of Szemerédi-Trotter theorem. Before ...

6
votes

1
answer

409
views

### A summation involving fraction of binomial coefficients

I need to prove the following statement.
Let $ n, g, m, a ,t$ be integers. Prove that the following statement is true for all $ n \geq g(1+2m)+1 $, $ g\geq 2t $, $ m\geq t $, $ 0\leq a <t $, and $ ...

1
vote

1
answer

282
views

### Szemerédi–Trotter type theorem in finite field

This question is about the content of this paper by J. Bourgain, N. Katz, T. Tao.
In the final step (page 18) of the proof of Szemerédi-Trotter type theorem, we have already known
$$|A''+A''|\lesssim ...

5
votes

1
answer

146
views

### Beating trivial bound for $k$-AP-free sets in characteristic $k$

Given integers $k,n\ge 1$, I shall write $\Bbb{Z}_k^n := (\Bbb{Z}/k\Bbb{Z})^n$.
Fix $k\ge 3$. Let $r_k(\Bbb{Z}_k^n)$ denote the cardinality of the largest $A\subset \Bbb{Z}_k^n$, such that $A$ does ...

1
vote

0
answers

54
views

### Largest interval containing family of sets with an overlap property

Here's a simplified version of a question I'm interested in.
Given $p$ and $q$ distinct prime numbers, we consider sets $A\subset \mathbb{N}\cup\{0\}, 0\in A$ of size $pq$, which are uniformly ...

1
vote

0
answers

68
views

### Progressions in finite fields with bounded hamming weight

Given $k\ge 2$ and an additive set $S$ (understood to live some implicit group $G$), define $$\Delta_k(S) := \left\{ d \in G: \bigcap_{i=1}^k (S+i\cdot d) \neq \emptyset \right\} $$(i.e., this is the ...

2
votes

0
answers

173
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 ...

2
votes

0
answers

120
views

### An additive combinatoric probability question

I asked the question in cs-theory stack exchange but was advised a pure math forum would be more apt. Link to the question:
https://cstheory.stackexchange.com/questions/52930/an-additive-combinatoric-...

3
votes

0
answers

128
views

### Counting $A+A-A$ with partial multiplicity

A recent question asked whether, given a finite set of positive numbers $A$, it is always the case that the set $A+A-A$ has more positive than negative elements. Terry Tao showed that this is false (...

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 ...

2
votes

0
answers

92
views

### Trapezoid-free subsets of the plane obtained by deleting lines

Let $A,B,C \subseteq \mathbb{Z}_n$. Suppose that for any $a' \in A, b' \in B, c' \in C$,
\begin{align*}
|(A+b') \cap (B+a') \cap -C| &\le 1,\\
|(A+c') \cap -B \cap (C+a')| &\le 1,\\
|-\hspace{-...

3
votes

0
answers

174
views

### Szemerédi’s theorem in really dense sets

This question is inspired by Tao’s answer in this post. I have thought about this occasionally for several months without anything concrete.
Question:
Given $\delta>0$ and $k\ge 3$, let $N= N_k(\...

3
votes

1
answer

214
views

### Bins-and-primes (prime divisors of $\prod(a_i-a_j)$, II)

This is a refined version of a question I have recently posted.
For a prime $p$, let $\varphi_p\colon\mathbb Z\to\mathbb Z/p\mathbb Z$ denote the canonical homomorphism from the integers onto the ...

2
votes

1
answer

156
views

### Prime divisors of $\prod(a_i-a_j)$

For a prime $p$, let $\varphi_p\colon\mathbb Z\to\mathbb Z/p\mathbb Z$ denote the canonical homomorphism from the integers onto the group of order $p$.
Given an integer $n\ge 3$, what is the smallest ...

0
votes

0
answers

42
views

### Non-isolating group labeling of a hypergraph

Let $(G,+,0)$ be an abelian group, $H=(V,\mathcal{E})$ is a $r$-uniform hypergraph. Let $\ell:V\to G$ be a labelling of the vertices. The label of an edge is the sum of the label of the vertices, so $\...

3
votes

0
answers

90
views

### Dimension of a kernel of a cocycle map

Inspired by a previous question (Dimension of a kernel of a linear map) and some of the answers I was given I thought wheter I can generalize the question to the following:
Compute the kernel (or at ...

8
votes

1
answer

303
views

### The growth rate of a commutator set in a non-elementary group

Let $G$ be a non-elementary group generated by a finite set $S$. Here, a group is called non-elementary if it is not virtually abelian. Denote $S^{\le n}:=\{g\in G: |g|_S\le n\}$ for any $n\in \mathbb ...

1
vote

0
answers

150
views

### A representation problem involving strict partition numbers

For each positive integer $n$, let $q(n)$ denote the number of ways to write $n$ as a sum of distinct positive integers. We call those $q(n)\ (n=1,2,3,\ldots)$ strict partition numbers.
The sequence $...