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.
663
questions
2
votes
0
answers
99
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
515
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
39
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
73
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
148
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
262
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
74
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
268
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
126
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
335
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$. ...
23
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
957
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
431
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
208
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
416
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 ...
39
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
148
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
138
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
883
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
712
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
161
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
307
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
307
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
119
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
641
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
169
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
403
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
277
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
145
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
127
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
91
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
172
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
213
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
155
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
87
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
148
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 $...
0
votes
0
answers
32
views
Partitioning vectors from Z^k into bundles preserving their additive properties
Let $B_1, B_2, \dots, B_m$ be disjoint subsets of $\mathbb{Z}^k$ and $B$ denote their union.
Also suppose that $k$ upper bounds the $\ell^\infty$-norm of every vector in $B$.
A set $V \subseteq B$ of ...
14
votes
2
answers
985
views
A sum-product phenomenon on reciprocals
Let $A \subset \mathbb F_p \setminus \{0\} $ and let $A+1/A = \{x+1/y:x,y \in A\}$.
Question: For fixed $c>0$, if $|A| \geq cp$, is $|A+1/A|$ at least $(1-o(1))p$ when $p \rightarrow \infty$?
Known:...
1
vote
1
answer
393
views
Dimension of a kernel of a linear map
Let $\mathbb{F}$ be a field of characteristic $2$, $n$ be a positive integer and $f_n:\bigoplus\limits_{i=1}^n\mathbb{F}\sigma_{i}\mapsto \bigoplus\limits_{i,j=1,i<j}^n\mathbb{F}\sigma_{i,j}$ be a ...