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.

Filter by
Sorted by
Tagged with
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{\...
e1c25ec7's user avatar
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 $\...
ABIM's user avatar
  • 4,969
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 $...
Sayan Dutta's user avatar
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, ...
John Rached's user avatar
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 ...
Marcos Cramer's user avatar
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 ...
JBuck's user avatar
  • 183
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 +...
Albert Garreta's user avatar
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$ ...
AsksQuestionsAboutMath's user avatar
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 \...
Nate River's user avatar
  • 4,832
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{...
anon's user avatar
  • 43
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 ...
Shahab's user avatar
  • 433
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 ...
Sayan Dutta's user avatar
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 ...
dankane's user avatar
  • 21
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 ...
Pietro Majer's user avatar
  • 56.6k
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}...
rivana's user avatar
  • 29
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$. ...
15948238's user avatar
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: ...
Zur Luria's user avatar
  • 1,623
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) \...
HumbleStudent's user avatar
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$. ...
Sayan Dutta's user avatar
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$ ...
Thomas Browning's user avatar
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 \...
RFZ's user avatar
  • 298
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 ...
Mohannad Shehadeh's user avatar
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: ...
ivmihajlin's user avatar
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 ...
Rishabh Kothary's user avatar
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)...
hofnumber's user avatar
  • 553
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|^{...
Rishabh Kothary's user avatar
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....
Adam Chapman's user avatar
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,\...
Zach Hunter's user avatar
  • 3,403
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 ...
Ryan Alweiss's user avatar
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 ...
RFZ's user avatar
  • 298
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 $\...
RFZ's user avatar
  • 298
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 ...
Kevin's user avatar
  • 530
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 ...
RFZ's user avatar
  • 298
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 $ ...
Arda Aydin's user avatar
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 ...
Jian-An Wang's user avatar
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 ...
Zach Hunter's user avatar
  • 3,403
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 ...
Itay's user avatar
  • 539
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 ...
Zach Hunter's user avatar
  • 3,403
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 ...
Talesseed's user avatar
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-...
Rishabh Kothary's user avatar
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 (...
Gabe K's user avatar
  • 5,384
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 ...
Timo Reichert's user avatar
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{-...
Kevin's user avatar
  • 530
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(\...
Zach Hunter's user avatar
  • 3,403
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 ...
Seva's user avatar
  • 22.8k
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 ...
Seva's user avatar
  • 22.8k
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 $\...
Chao Xu's user avatar
  • 583
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 ...
Marcos's user avatar
  • 577
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 ...
dennis's user avatar
  • 145
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 $...
Zhi-Wei Sun's user avatar
  • 14.5k

1
2 3 4 5
14