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
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 ...
The Amplitwist's user avatar
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=...
aglearner's user avatar
  • 14k
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 ...
aglearner's user avatar
  • 14k
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}$. ...
Sei's user avatar
  • 11
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 ...
Seva's user avatar
  • 22.8k
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 ...
M.H.Hooshmand's user avatar
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 $...
yangpliu's user avatar
  • 101
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\...
Jiayi Liu's user avatar
  • 909
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 ...
Johnny Cage's user avatar
  • 1,543
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 ...
Zach Hunter's user avatar
  • 3,393
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 $...
Atticus Stonestrom's user avatar
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 ...
Jiayi Liu's user avatar
  • 909
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 ...
XYC's user avatar
  • 389
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:...
Ivan Meir's user avatar
  • 4,782
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 ...
Seva's user avatar
  • 22.8k
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 ...
Wolfgang's user avatar
  • 13.2k
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 ...
Zhi-Wei Sun's user avatar
  • 14.4k
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 ...
Ivan Meir's user avatar
  • 4,782
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}/...
Killua Zoldyck's user avatar
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|,...
Seva's user avatar
  • 22.8k
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) ...
locra's user avatar
  • 83
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 ...
Oliver Roche-Newton's user avatar
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 ...
BharatRam's user avatar
  • 939
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 ...
Maarten Derickx's user avatar
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$ ...
Andyqian7's user avatar
  • 165
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}$.
Andyqian7's user avatar
  • 165
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,...
Zach Hunter's user avatar
  • 3,393
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 ...
RFZ's user avatar
  • 298
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 ...
JPMarciano's user avatar
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.$ ...
RFZ's user avatar
  • 298
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 ...
user avatar
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 ...
Jiayi Liu's user avatar
  • 909
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 ...
user avatar
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 ...
RFZ's user avatar
  • 298
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 ...
RFZ's user avatar
  • 298
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 ...
Roland Bacher's user avatar
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\...
Hailong Dao's user avatar
  • 30.3k
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 + ...
Rajkumar's user avatar
  • 167
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 ...
Ivan Meir's user avatar
  • 4,782
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 ...
qifeng618's user avatar
  • 838
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 ...
qifeng618's user avatar
  • 838
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 ...
Christian Bernert's user avatar
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 ...
shurtados's user avatar
  • 1,010
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 ...
shurtados's user avatar
  • 1,010
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 ...
Gautam's user avatar
  • 1,693
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 ...
Tim Campion's user avatar
  • 60.6k
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 ...
Tomasz Popiel's user avatar
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 ...
richrow's user avatar
  • 367
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\...
Taras Banakh's user avatar
  • 40.8k
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$ ...
Taras Banakh's user avatar
  • 40.8k

1 2
3
4 5
14