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
2 votes
1 answer
120 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 ...
user avatar
5 votes
1 answer
499 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 $...
user avatar
  • 101
2 votes
0 answers
46 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\...
user avatar
  • 909
0 votes
0 answers
35 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 ...
user avatar
  • 1,054
4 votes
1 answer
124 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 ...
user avatar
3 votes
0 answers
63 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 $...
user avatar
0 votes
1 answer
109 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 ...
user avatar
  • 909
10 votes
2 answers
660 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 ...
user avatar
9 votes
3 answers
728 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:...
user avatar
  • 4,350
2 votes
0 answers
71 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 ...
user avatar
  • 21.3k
3 votes
0 answers
101 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 ...
user avatar
  • 12.4k
14 votes
1 answer
445 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 ...
user avatar
  • 12.8k
0 votes
0 answers
113 views

Adjacency matrix of shifts

Let us consider sets $A= \mathbb Z$ and $B = \frac{p}{q}\mathbb Z+s.$ We say $x \in B$ is associated with $y \in A$ if $$\min_{z \in A}\vert x-z \vert = \vert x-y \vert.$$ In particular, if $x \in B$ ...
user avatar
  • 369
16 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 ...
user avatar
  • 4,350
5 votes
0 answers
164 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}/...
user avatar
0 votes
0 answers
61 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|,...
user avatar
  • 21.3k
8 votes
1 answer
367 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) ...
user avatar
  • 83
4 votes
0 answers
117 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 ...
user avatar
0 votes
1 answer
113 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 ...
user avatar
  • 877
7 votes
1 answer
335 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 ...
user avatar
  • 1,775
4 votes
0 answers
367 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$ ...
user avatar
  • 113
7 votes
1 answer
242 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}$.
user avatar
  • 113
3 votes
1 answer
164 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,...
user avatar
1 vote
1 answer
83 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 ...
user avatar
  • 216
5 votes
0 answers
227 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.21^n$ for sufficiently large $n$. His proof is by giving a construction of ...
user avatar
1 vote
0 answers
79 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.$ ...
user avatar
  • 216
5 votes
1 answer
378 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
263 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 ...
user avatar
  • 909
2 votes
1 answer
536 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
155 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 ...
user avatar
  • 216
0 votes
1 answer
180 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 ...
user avatar
  • 216
19 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 ...
user avatar
15 votes
2 answers
1k 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\...
user avatar
  • 29.6k
2 votes
1 answer
175 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 + ...
user avatar
  • 157
6 votes
0 answers
155 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 ...
user avatar
  • 4,350
0 votes
1 answer
181 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 ...
user avatar
  • 390
5 votes
3 answers
424 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 ...
user avatar
  • 390
10 votes
2 answers
386 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 ...
user avatar
5 votes
2 answers
477 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 ...
user avatar
  • 1,010
8 votes
1 answer
336 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 ...
user avatar
  • 1,010
12 votes
2 answers
1k 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 ...
user avatar
  • 1,643
9 votes
1 answer
244 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 ...
user avatar
  • 49.2k
15 votes
1 answer
737 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 ...
user avatar
2 votes
0 answers
124 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 ...
user avatar
  • 193
3 votes
3 answers
453 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\...
user avatar
  • 32.9k
7 votes
3 answers
471 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$ ...
user avatar
  • 32.9k
2 votes
1 answer
110 views

Decoding the Reed–Muller $RM(m, m)$ code, and a matrix related to Pascal's triangle

The Reed–Muller $RM(m, m)$ code sends the message $p(X_0, \ldots , X_{m - 1}) = \sum_{S \subset \{0, \ldots , m - 1\}} \alpha_S \cdot X_S$ to its set of evaluations $\left\{ p(x_0, \ldots , x_{m - 1}) ...
user avatar
  • 61
9 votes
0 answers
153 views

Is almost every number the sum of two numbers with small radicals?

Define a set of numbers with small radicals (A341645 in OEIS) by $$A_2=\{n\in\mathbb{N} \;|\; \text{rad}(n)^2\le n\}$$ The asymptotic density of $A_2\cap \{1,\dots N\}$ is $\sqrt{N}\times e^{2(1+o(1))\...
user avatar
6 votes
1 answer
111 views

Maximal sublattice index in Minkowski's Second Theorem

Let $B$ be a (small) convex compact set in $\mathbb{R}^n$, symmetric around the origin. Let $\Gamma$ be a lattice in $\mathbb{R}^n$ of dimension $n$ (I'm almost sure we can just take $\mathbb{Z}^n$, ...
user avatar
2 votes
0 answers
160 views

Reference for solved execrcises in additive combinatorics

I am aware that additive combinatorics is a relatively new subject and there are not many books available. I will be grateful if anybody can tell me about some source where I can find a few solved ...
user avatar

1
2 3 4 5
12