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 ...

learn more… | top users | synonyms

22
votes
0answers
466 views

probability of zero subset sum

Almost 17 years ago, I asked the following question on USENET, motivated by a method in numerology (I kid you not). Pick integers $n \ge 2$, $k \ge 1$. Toss $n$ $k$-sided dice. The sides of each die ...
18
votes
0answers
494 views

Which sets of roots of unity give a polynomial with nonnegative coefficients?

The question in brief:   When does a subset $S$ of the complex $n$th roots of unity have the property that $$\prod_{\alpha\, \in \,S} (z-\alpha)$$ gives a polynomial in $\mathbb R[z]$ with ...
12
votes
0answers
389 views

Correlation of Fourier transforms of characteristic functions

Let $A$ and $B$ ($A\subset B$) be subsets of a finite abelian group $G$. (For the sake of argument, you can take $G$ to be $\mathbb{Z}/p\mathbb{Z}$ for large $p$, say.) Write $1_S$ for the ...
11
votes
0answers
346 views

How large must $A$ be if $\{1, \ldots, N\} \subseteq A-A$?

Given a positive integer $N$, what is the size of the smallest set of integers $A$ such that, for any integer $1 \leq k \leq N$, we can find two integers $x, y \in A$ such that $x - y = k$? (An ...
10
votes
0answers
572 views

What are the limits of the Erdős-Rankin method for covering intervals by arithmetic progressions?

To construct gaps between primes which are marginally larger than average, Erdős and Rankin covered an interval $[1,y]$ with arithmetic progressions with prime differences. A nice short exposition is ...
9
votes
0answers
288 views

A characterization of quadratics similar to an inverse sieve problem

Suppose $\mathscr{A} \subset \mathbb{N}$ enjoys for all large enough cutoffs $X$ the following properties: $|\mathscr{A} \cap [1,X]| > \sqrt{X}/10$; and the discriminant $\prod_{\alpha \neq ...
9
votes
0answers
600 views

Cliques in the Paley graph and a problem of Sarkozy

The following question is motivated by pure curiosity; it is not a part of any research project and I do not have any applications. The question comes as an interpolation between two notoriously ...
8
votes
0answers
207 views

An abstract zero-sum problem

I would like to know whether the problem described below has appeared in the literature and/or whether similar questions have been studied. I would be very happy to find some references or, if none ...
8
votes
0answers
193 views

Partition regularity in the squares

A linear equation $c_1x_1 + \cdots + c_sx_s = 0$ is partition regular if for every partition of the natural numbers into colour classes $A_1, \ldots, A_r$, there is a solution to the equation in which ...
8
votes
0answers
148 views

Erdös-Fuchs Theorem for multivariate linear forms

Let $A$ be an infinite set of positive integers, and denote by $r(n)$ the number of solutions to the equation $a+a'=n$, with $a,\, a' \in A$. It is not very difficult to show that if $r(n) > 0$ ...
7
votes
0answers
133 views

Sets of natural numbers which are almost closed under addition

I am interested in a classification of sets $A \subseteq \mathbb{N}$ such that for all $k \in A$, $d( A+k \cap \mathbb{N} \setminus A) = 0$ where $d$ is the asymptotic density and $A+k = \{n \in ...
7
votes
0answers
161 views

Distribution of trivial subset sums

Suppose I have a set $S$ of $n$ integers picked independently, uniformly at random from $[-L, L].$ Let $z(S)$ be the number of subsets of $S$ which sum to zero. The question is: what is the ...
7
votes
0answers
219 views

A strong sum-product “for translates” in finite fields

In the course of some recent research, I've sketched out a proof of the following result. My basis question is: is the result interesting? Proposition There exists an absolute constant $c$ such ...
6
votes
0answers
85 views

Why have most maximal cliques of Paley graphs odd size?

I ask this question mainly by curiosity. See here for definitions and a plot of the clique numbers of the Paley graphs for the primes $p\equiv 1 \pmod 4$ up to $10000$. Is there an ...
6
votes
0answers
347 views

Small maximal sets with no 3-AP?

Everyone knows about the problem of finding the largest set in 1,2,...,N which contains no arithmetic progression of length 3.....what happens if we look at the set which is the smallest maximal ...
5
votes
0answers
70 views

Some questions about the Lévy monoid of certain densities

Let $\bf H$ be a set, $f: \mathcal P({\bf H}) \rightharpoonup \bf R$ a partial function, and $\mathcal{D}$ the domain of $f$. Next, denote by $\mathcal M(f)$ the set of all (total) functions $\theta: ...
5
votes
0answers
184 views

Is $AA+A$ always at least as large as $A/A$?

Let $A$ be a finite set of real numbers. Is it always the case that $|AA+A| \geq |A/A|$? In the line above, $AA+A:=\{ab+c:a,b,c \in A \}$, while $A/A:=\{a/b:a,b \in A, b\neq 0 \}$ is the ratio set. ...
5
votes
0answers
185 views

The sum of all the elements of every non empty subset of $A$ is not a multiple of $n$

Let $N=\{1,2,\ldots ,n\},n>1$. We wish to construct a set $A\subseteq N$ with the property: The sum of all the elements of every non empty subset of $A$ is not a multiple of $n$. ...
5
votes
0answers
170 views

Distribution of subset-sums

Let $A$ be a set of $n$ integers uniformly distributed in $\{0,\dots,N-1\}$. Let $S$ be the set of subset-sums modulo $N$ of $A$. Let $f_{n,N}(k)$ be the probability that $|S|=k$. Is there an ...
5
votes
0answers
164 views

Other applications of the 'increment' approach

I would like to hear about other instances of the so-called 'increments' approach, first used by Roth to prove that a subset of $\mathbb{N}$ of positive upper density contained infinitely many ...
5
votes
0answers
592 views

Expectation of Gowers norm

This was a problem that came up during a course on Analytic Combinatorics that I had taken this semester. Here's the problem: Let $\mathbf{F}$ be the set of boolean functions, $f: \mathbb{F}_2^n ...
4
votes
0answers
121 views

Decay to stationarity in a random walk on the hypercube

Let $\mu$ be a probability distribution on $\mathbb F_2^n$. Consider the random walk $X_0,X_1,\ldots$ defined by $$\begin{aligned} X_0 &= 0\\X_{i+1}&=X_i + Z,\end{aligned}$$ where $Z\sim \mu$ ...
4
votes
0answers
224 views

The original proof of Szemerédi's Theorem

Nowadays there are plenty of different proofs of the celebrated Szemerédi's Theorem but for historical reasons I would like to read and understand the original proof. The proof is very tricky and, for ...
4
votes
0answers
106 views

Sparsifiers for 3-term arithmetic progressions

Let $G$ be a finite abelian group of odd order, let $D\subseteq G$, and $\epsilon \in (0,1)$. For $S\subseteq G$ define $$ \Lambda(S) = \frac{1}{|S||G|} \sum_{s\in S}\sum_{g\in G} ...
4
votes
0answers
149 views

Reduction argument from a general vertex set V(G) to a prime power in Prof. Keevash's proof on the Existence of Designs

The proof flow of the paper "On the Existence of Designs" by Prof. Keevash as I understand it is the following: -- Reduction from the general case to $V = \mathbb{F}_{p^a}$ (Lemma 6.3) -- Covering ...
4
votes
0answers
428 views

Largest set of integers without 3-term arithmetic progressions mod $n$

I am interested in a sharp bound on the largest possible size $e_3({\boldsymbol{Z}_n})$ of a subset $S \subset \boldsymbol{Z}_n$ such that for any three distinct elements $a, b, c \in S$ we have $a+b ...
4
votes
0answers
331 views

A question about Erdos thin bases

Let $B \subset \mathbb{N}$ be an additive basis of order $h$. Define $r_{B,h}(n)$ to be the number of ways $n$ can be written as a sum of $h$ elements of $B$. In particular, $B$ is a basis of order ...
3
votes
0answers
208 views

Area defined with $\pm$ closedness

Denote $B_n\subset\Bbb R^n$ to be unit ball at origin. Denote $S\subset B_n$ to region of type $\mathsf I$ if it satisfies $$s\in S\iff\forall t\in S, s+t\in S\mbox{ or }s-t\in S$$ I am convinced ...
3
votes
0answers
106 views

Reference for a lemma on the asymptotic upper density of special sets with large gaps and intervals

Update. Based on Anthony Quas' comment below, the proof can be made sensibly shorter and the lemma can be slightly generalized by weakening the old assumption (iii). In a joint paper that I am ...
3
votes
0answers
156 views

On covering by smooth numbers

Denote $P(n)=\mathsf{greatest}\mbox{ }\mathsf{prime}\mbox{ }\mathsf{factor}\mbox{ }\mathsf{of}\mbox{ }n$. Denote $S(x,y)=\{n<x: P(n)<y\}$. Denote $S_t(x,y)=\sum_{i=1}^tS(x,y)$ as $t$-fold ...
3
votes
0answers
118 views

Applications of Freiman's theorem?

What are some interesting applications of Freiman's theorem or, better-yet, its recent generalizations (eg Green-Ruzsa) that could be included in a graduate course in additive combinatorics? I'm ...
3
votes
0answers
273 views

Solving a doubly exponential generating function

I am analyzing the average time complexity of some algorithm on some probabilistic model, and I've come to a doubly exponential sequence for which I cannot find corresponding generating function. I ...
3
votes
0answers
157 views

Subgroup cliques in the Paley graph

It is a famous open problem to estimate non-trivially, for a prime $p\equiv 1\pmod 4$, the largest size of a subset $A\subset{\mathbb F}_p$ such that the difference of any two elements of $A$ is a ...
3
votes
0answers
93 views

Sets of polynomials with restricted set of products

Let $F = \{f_1, ..., f_n\}$ be a set of distinct monic polynomials (and thus also $f_i^2$ are distinct). Let $F' = \{f_i f_j: i \neq j\}$ be the set of pairwise products of all distinct elements from ...
3
votes
0answers
114 views

Number cubes with consecutive line sums

This is barely of research interest, but I'd classify it as a curiosity with connections to combinatorics. The problem is to place integers in an $n \times n \times n$ array so that all $3n^2$ line ...
3
votes
0answers
67 views

Distribution of the evaluation (at a non-trivial root of -1) of polynomials with small coefficients

When we studied some cryptographic protocol, we came accross the following problem, which seems linked to the uniformity of the residues of small multiplicative subgroups of $\mathbb{F}_q$. Problem ...
3
votes
0answers
105 views

Closest sumset to a set

Suppose $A$ is a subset of the finite field with $p$ elements. What is the best approximation of $A$ by a sumset $B+C$ in the sense that $|A\Delta (B+C)|$ is minimal? Of course if $B=A-x$ and ...
3
votes
0answers
134 views

Bounds on difference sets of relatively dense A \subseteq {1, …, n}

Let $A \subseteq \{1, \dots, n\}$ and let $A-A = \{a-b | a,b \in A\}$. Is it possible to obtain a general bound of the form $|A - A| = O(n^\beta)$ for some $\beta < 1$? If not, can something like ...
3
votes
0answers
231 views

Convex subsets of sumsets

There's a famous old problem in additive number theory which asks whether, for any $\epsilon > 0$, if $B$ is a 2-basis for the set $A =$ {$1^2,2^2,...,n^2$}, i.e.: a set for which $B+B \supseteq ...
3
votes
0answers
129 views

Other interesting examples of pseudo-random measures

Here we use the notion of pseudo-randomness (or variant of) used in the proof of the Green-Tao theorem. In particular, we say a measure $\nu : \mathbb{Z}_N \rightarrow \mathbb{R}^+$ is pseudo-random ...
2
votes
0answers
113 views

Additive combinatorics and a Diophantine equation

Let $(n_k)_{1 \leq k \leq N}$ be a sequence of distinct positive integers. For $v \in \mathbb{Z}$ set $$ A_N(v) = \# \Big\{ (k,\ell) \in \{1, \dots, N\}^2, ~k \neq \ell:\quad n_k - n_\ell = v \Big\}. ...
2
votes
0answers
72 views

Does there exist $k\ge2$ s.t. $X \subseteq \mathbf N^+$ has positive upper Banach density if the counting function of $X$ is $\gg n/\log^{[k]}(n)$?

Does there exist an integer $k \ge 1$ such that ${\sf bd}^\ast(X) > 0$ whenever $X \subseteq \mathbf N^+$ and $\pi_X(n) \gg \frac{n}{\log^{[k]}(n)}$ as $n \to \infty$? Here, ${\sf bd}^\ast$ is the ...
2
votes
0answers
74 views

How is the structure of spectrum in cap-sets with no strong increments unrealistic if density is too large?

I am reading this excellent paper by Bateman and Katz on improved bounds on the cap set problem. Let A be a set in $\mathbb{F}_3^n$ containing no 3-term arithmetic progression and let $A(x)$ denote ...
2
votes
0answers
231 views

Can the affine sieve be used to sieve for $k$-free values?

The affine sieve, developed initially by Bourgain-Gamburd-Sarnak in the paper "Affine linear sieve, expanders, and sum-product" published in Inventiones Mathematicae in 2010, deals generally with the ...
2
votes
0answers
133 views

Doubling for Sumset of the same set

Let $G$ ($G=\mathbb{Z}^n_2$ for my case) be a additive group and $A$ be a subset of $G$. For any set $S\subseteq G$ define its doubling as $$\sigma (S)=\dfrac{|S+S|}{|S|}$$ Suppose $A$ has small ...
2
votes
0answers
118 views

Lower bound on P(Y > 3/2 E(Y)) where Y = # of triangles in graph

Context This is exercise 1.7.1 of Tao/Vu's Additive Combinatorics, generally considered a graduate level math textbook. My question is not "How do I solve this exercise?" My question is "What is ...
2
votes
0answers
253 views

Prime divisors of the difference set

Fix $c\in(0,1)$, and let $N$ be a (large) positive integer. Given a set $A=\{0=a_1<\dots<a_n=N\}$ of density $\alpha:=n/N>c$ with $\gcd(A)=1$, I want to find a prime dividing as few ...
2
votes
0answers
966 views

Fun question in additive combinatorics

It is easy to see that for a finite set of integers $A$ of cardinality $n$, the cardinality of the sumset $A+A$ satisfies $$ 2n-1\leq |A+A|\leq \frac{n(n+1)}{2}. $$ The lower bound is essentially ...
1
vote
0answers
76 views

Consecutive integers divisible by consecutive small numbers

Given $n$, what is the largest set of consecutive integers in $[n,2n]$ can we have so that each integer is divisible by a distinct element from $[\log n,2\log n]$ (no partiular order)? So apriori I am ...
1
vote
0answers
166 views

Generalized arithmetic progressions contained in Bohr sets

Recall that a generalized arithmetic progression of dimension $d$ is, by definition, a set of the form $P = P_1+\dots+P_d$, where $P_j = \{lp_j\ \mid \ |l|\leq l_j\}\subset \mathbb Z$ is an ordinary ...