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.
664
questions
10
votes
1
answer
846
views
How hard is it to compute the Davenport constant?
The Davenport constant $D(G)$ of a finite abelian group $(G,+)$ is the least positive integer $k$ such that every sequence in $G$ of length $k$ has a zero-sum (nonempty) subsequence.
It seems that the ...
2
votes
0
answers
117
views
Almost subgroups of $\mathbb S^1$
Suppose $X\subset \mathbb S^1$ is a finite subset of the group $\mathbb S^1$ such that $|X+X|<(1+c )|X|$ for a sufficiently small $c\in(0,1)$. I believe that in such case there exists a subgroup $G=...
4
votes
1
answer
139
views
Number of "half symmetries" of a finite subset of $\mathbb S^1$
Suppose $X\subset \mathbb S^1$ is a finite subset of the group $\mathbb S^1=\mathbb R/\mathbb Z$. We say that $t\in \mathbb S^1$ is a half symmetry of $X$ if $|(X+t)\cap X|>|X|/2$.
Question. Can ...
0
votes
0
answers
122
views
An exercise about sum-product estimate
I am struggling with 1.11 exercise from the George Shakan "Discrete Fourier Transform".
Let $A \subset \mathbb{Z}/q\mathbb{Z}$ be any set not containing zero with $|A|>\sqrt2q^{5/8}$. ...
9
votes
2
answers
254
views
Alon-Füredi for homogeneous polynomials
A theorem of Alon and Füredi says that if $A$ and $B$ are finite, nonempty subsets of the field $\mathbb F$, and if a polynomial $P(x,y)\in\mathbb F[x,y]$ vanishes on all, but exactly one point of the ...
2
votes
1
answer
179
views
Difference sequences of sets of integers
In this paper, the conception of the difference sequence and $\infty$-difference length of a subset of groups is introduced. As an important case, subsets of the additive group of integers are ...
5
votes
1
answer
818
views
Much weaker condition for Kakeya sets over finite fields
What is the minimum size of a subset $S \subseteq \mathbb{F}_p^n$ such that for all directions $a \in \mathbb{F}_p^n$, there is a line in direction $a$ that intersects $S$ in at least $C$ points?
If $...
2
votes
0
answers
59
views
Does periodic pattern arise in syndetic pattern
We wonder for two "large" sets $I,J\subseteq \omega$, if $(J-J)\cap I=\emptyset$, then it must be due to certain periodic pattern.
We say $I\subseteq \omega$ is $t$-syndetic iff for every $n\...
3
votes
1
answer
191
views
Extremal problems in additive combinatorics (over finite fields)
As you may know, there has been very recently a big breakthrough concerning upper bounds for the capset problem over $\mathbb{F}_3^n$ (and further generalizations to $\mathbb{F}_q^n$). I was wondering ...
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
0
answers
91
views
"Skew-dimension" and discrete parallelepipeds
Let $(G,+)$ be an abelian group. Given a subset $B\subseteq G\setminus\{0\}$, define the "discrete span" of $B$, which I will denote $\langle B\rangle_d$, to be the set of all $\sum A$ for $...
0
votes
1
answer
149
views
Finite Hindman theorem
Consider the following finite version Hindman theorem:
For every sufficiently large $N\in\omega$ and 2-partition of $N=N_0\cup N_1$, there are $i<2,a,b,c\in N_i$ such that $a+b=c$.
The only proof I ...
10
votes
2
answers
842
views
The maximal subset of a finite field where the sum of any subset is non-zero
Given a finite field $\mathbb{F}_q$ with $q=p^m$ where $p$ is the characteristic.
For any subset $S=\{a_1,\dots,a_n\}$ of $\mathbb{F}_q$, if any partial sum (i.e. the sum of elements in a non-empty ...
9
votes
3
answers
1k
views
A set with positive upper density whose difference set does not contain an infinite arithmetic progression
For $S \subset \mathbb{N}$ define $S-S=\{x-y:x \in S, y \in S\}$.
As noted below there is a simple example showing that a set $S \subset \mathbb{N}$ with positive upper density has a sumset $S+S=\{x+y:...
2
votes
0
answers
113
views
Restricted sumsets - the origins?
The sumset of the subsets $A$ and $B$ of an additively written group is defined by $A+B:=\{a+b\colon a\in A,\ b\in B\}$. The basic idea to add sets has been around since Cauchy at least.
Erdős and ...
3
votes
0
answers
142
views
Flat polynomials with factors of big height
Let $p(x)$ be a polynomial of degree $n$ with all coefficients in $\{-1,0,1\}$ (such polynomials are sometimes called flat). I am wondering how big the coefficients of a factor of $p$ can be. Call ...
14
votes
1
answer
495
views
Does $A-A=\mathbb Q$ hold for $A=\{x^4+y^4:\ x,y\in\mathbb Q\}$?
Let $A=\{x^4+y^4:\ x,y\in\mathbb Q\}$. Then
$$A-A:=\{a-b:\ a,b\in A\}=\{u^4+v^4-x^4-y^4:\ u,v,x,y\in\mathbb Q\}.$$
Motivated by Question 415482, here I ask the following question.
Question. Is it true ...
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 ...
5
votes
0
answers
191
views
Showing that Fourier pseudorandomness is insufficient for $k=4$ case (four arithmetic progressions)
I wish to show that the Fourier pseudorandomness is insufficient to count the number of 4-term arithmetic progression.
Let $A \subset \mathbb{Z}/N\mathbb{Z}$ be a subset of a cyclic group $\mathbb{Z}/...
0
votes
0
answers
140
views
Additive energy and uniquely representable elements
Suppose that $A$ is a finite, nonempty set in an abelian group. If there is a group element with a unique representation as $a-b$ with $a,b\in A$, then none of $A-A$ and $2A$ are small:
$$ \min\{|A-A|,...
8
votes
1
answer
561
views
Why are exponential sums so bad at solving this very easy problem?
Exponential sums are a powerful tool in additive combinatorics and number theory. In my understanding, when it comes to estimate the cardinality of a certain set, exponential sums are (essentially) ...
4
votes
0
answers
144
views
How many convex or concave subsets are contained in an arbitrary set of $n$ real numbers?
This question is closely related to this post. A set $A=\{a_1<a_2<\dots<a_n\} \subset \mathbb R$ is said to be convex if the consecutive differences are non-decreasing, i.e. if $a_{j+1} - a_j ...
0
votes
1
answer
135
views
Is there a notion of "rapid" expansion for graphs?
I'll be as intuitive and hand-wavy as possible so as to get to what I am looking for.
Suppose we have a graph $G=(V,E)$. One notion of expansion, namely vertex expansion, can be intuitively described ...
7
votes
1
answer
481
views
Subgroups of the multiplicative group of a finite field satisfying a certain additive property
Let $G \subseteq \mathbb F_p^*$ be a subgroup. Then $G$ is called almost trivial if $G \cap (2-G)$ consists of the element 1.
Then I am wondering how big $G$ can be in terms of $p$. If $G$ is a random ...
6
votes
0
answers
491
views
At most two elements give 1 to n
Fix a positive integer $m$. Let $n$ ( $= n(m)$) be the largest positive integer for which there exists some subset $\{a_1,\ldots,a_m\} \subseteq \{1,2,\ldots,n\}$ of $m$ positive integers between $1$ ...
7
votes
1
answer
263
views
$p-1$ elements in $\mathbb{Z}_p\times\mathbb{Z}_p$ with a sum $(0,0)$
Given prime $p\ge 11$, $S$ is a subset of $\mathbb{Z}_p\times\mathbb{Z}_p$ with $3p-3$ elements. Prove: $S$ has a subset $T$ with $p-1$ elements, such that$\sum_{x\in T}x\equiv (0,0)\pmod{p}$.
3
votes
1
answer
267
views
What are bounds on this van der Waerden-esque problem?
I was reading a problem list by Erdos (doi). On page 144 (which is the 12-th page of the pdf), a problem stuck out to me.
For positive integer $n$, let $h(n)$ be the smallest $k$ such that $[n] := \{1,...
2
votes
1
answer
193
views
Double estimates relating Ruzsa distance and doubling constant
I am trying to solve the following exercise (2.3.16) from Tao-Vu book.
Let $A,B$ be additive sets with common ambient group $Z$. Show that
$\sigma[A\cup B]\leq e^{d(A,B)}+2e^{4d(A,B)}$. In the ...
9
votes
1
answer
560
views
Known approaches for the lower bound on cap-set problem
Let $r(n):=r_3(\mathbb{F}_3^n)=\max\{|A|: A \subset \mathbb{F}_3^n, \ A \text{ is 3-AP-free}\}$.
Edel proved that $r(n)\geq 2.217^n$ for sufficiently large $n$. His proof is by giving a construction ...
1
vote
0
answers
91
views
$d(A,B\cup C)\leq \max\{d(A,B),d(A,C)\}+\log 2$ for additive sets $A,B,C$
Suppose that $A,B$ are additive sets in $Z$. Show that $d(A,B\cup
C)\leq \max\{d(A,B), d(A,C)\}+\log 2.$
Suppose that $d(A,B)\leq d(A,C),$ then we need to show that $d(A,B\cup C)\leq d(A,C)+\log 2.$ ...
5
votes
1
answer
449
views
Questions on 'Improved bounds for the sunflower lemma'
I have been reading 'Improved bounds for the sunflower lemma' by Alweiss, Lovett, Wu and Zhang (Ann. of Math., Vol. 194(3), 2021), and have some gaps in my understanding of the paper. They are as ...
2
votes
1
answer
286
views
Is the consecutive sum set large in general?
$\DeclareMathOperator\CSS{CSS}$It is well known that for a set $A$ of integers, if $\gcd(A) = d$,
then the set of (integer) linear combinations of $A$ is $d\mathbb{Z}$.
I'm looking for a probability ...
2
votes
1
answer
590
views
On 'Improved Bounds for the Sunflower Lemma' [Alweiss, Lovett, Wu, Zhang]
I have been reading the paper 'Improved Bounds for the Sunflower Lemma' (Ann. of Math., Vol. 194(3), pp. 795-815), and have not managed to understand the following:
I would like a formalization for ...
1
vote
1
answer
177
views
Ubiquity of simplices in subsets of $\mathbb{F}_q^d$
I was reading Hart and Iosevich - Ubiquity of simplices in subsets of vector spaces over finite fields about some quantitative results on simplices in subsets of vector spaces over finite fields. I ...
0
votes
1
answer
200
views
Controlling iterated sum sets of "most" of $A+B$
I am reading Tao-Vu book on Additive combinatorics and came across the following lemma. I know that it is better to ask this question on MathStack but I asked few questions before and no one answered ...
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 ...
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\...
2
votes
1
answer
201
views
Coefficient of a term in a several variable polynomial multipled with Vandermonde determinant
Let $\Delta_n(x_1, \ldots, x_n)$ denote the Vandermonde determinant $\displaystyle \prod_{1 \leq i < j \leq n}(x_j - x_i)$. Let $c_1, \ldots, c_n$ and $K$ be nonnegative integers satisfying
$$c_1 + ...
6
votes
0
answers
171
views
Plausible ways to discover higher order fourier analysis
Szemeredi's Theorem is a difficult theorem that falls into the category of not obviously foundational or widely applicable in itself but where the search for proofs have led to a number of ...
0
votes
1
answer
209
views
Where is the source of the formula $\sum_{j=0}^\infty \bigl(j+\frac{1}{2}\bigr)^{n-1}\frac{2^{j+1/2}}{\binom{2j+1}{j+1/2}}$ for an integer sequence?
The infinite series representation
\begin{equation}
\frac1\pi\sum_{j=0}^\infty \biggl(j+\frac{1}{2}\biggr)^{n-1}\frac{2^{j+1/2}}{\binom{2j+1}{j+1/2}}, \quad n\ge0
\end{equation}
for the positive ...
5
votes
3
answers
668
views
How to prove the combinatorial identity $\sum_{k=\ell}^{n}\binom{2n-k-1}{n-1}k2^k=2^\ell n\binom{2n-\ell}{n}$ for $n\ge\ell\ge0$?
With the aid of the simple identity
\begin{equation*}
\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^{k}}=2^n
\end{equation*}
in Item (1.79) on page 35 of the monograph
R. Sprugnoli, Riordan Array Proofs of ...
11
votes
2
answers
605
views
Methods to bound the number of solutions to $x^x \equiv 1 \mod p$ with $1 \le x \le p$
For a prime $p$, let $N(p)$ be the number of solutions $1 \le x \le p$ to $x^x \equiv 1 \mod p$. I am interested in methods to bound $N(p)$.
Background: This quantity appears in Problem 1 of the ...
5
votes
2
answers
664
views
Distribution of some sums modulo p
Fix a finite set of integers $S$ and a prime number $p$. Let $(a_1, a_2, \dotsc, a_n)$, $(b_1, b_2, b_3, \dotsc, b_n)$ be two sequences of integers where the numbers $a_i$ and $b_i$ are chosen ...
8
votes
1
answer
368
views
Question about estimating random symmetric sums modulo p
Let $n > 0$ be a positive integer (large) and $p > 2$ a fixed prime number. What is the probability that $$\sum_{ 1 \leq i < j \leq n} a_ia_j = 0 \mod p$$ where $a_1, a_2, \dots a_n$ are ...
12
votes
2
answers
2k
views
Subsets of the integers which are closed under multiplication
Let $S$ be a subset of the integers which is closed under multiplication. There are many possible choices of $S$:
$S = \{-1, 1\}$.
$S$ is the set of integers of the form $a^k$, where $a$ is fixed and ...
9
votes
1
answer
297
views
How small can the support of a nontrivial $\mathbb F_p$-cocycle on $C_p$ be?
Let $p$ be a prime, and let $\phi : C_p^n \to \mathbb F_p$ be an $\mathbb F_p$-valued $n$-cocycle on $C_p$ (the cyclic group of order $p$) which is not an $n$-coboundary, i.e. $\phi$ represents a ...
15
votes
1
answer
794
views
Explicit constant in Green/Tao's version of Freiman's Theorem?
Green and Tao's version of Freiman's theorem over finite fields (doi:10.1017/S0963548309009821) is as follows:
If $A$ is a set in $\mathbb{F}_2^n$ for which $|A+A| \leqslant K|A|$, then $A$ is ...
2
votes
0
answers
138
views
Structure of certain "arithmetic" sets
First, define an arithmetic set as a finite subset $A$ of the segment $[-1,1]$ which satisfies the following conditions:
$\{-1,1\}\subset A$.
For each $a\in A\setminus\{\pm 1\}$ there are two ...
3
votes
3
answers
471
views
Large product-1-free sets in finite groups
$\DeclareMathOperator\SmallGroup{SmallGroup}$Definition. A subset $A$ of a group $G$ is called product-1-free if for any sequence of pairwise distinct elements $a_1,\dots,a_n$ of $A$ the product $a_1\...
7
votes
3
answers
493
views
Product-one sets in non-commutative groups
A nonempty subset $D$ of a group $G$ is called
$\bullet$ decomposable if $D\subseteq DD$, that is every element $x\in D$ is can be written as the product $x=yz$ of some elements $y,z\in D$;
$\bullet$ ...