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

2
votes
2answers
1k views

Almost periodic functions in Tao's ergodic proof of Szemerédi's theorem

Do we say that a function $f$ is uniformly almost periodic in the aforementioned proof if $f$ is bounded (in the sense that $||f||_{L^\infty}\leq 1$) and that there exists a natural number $d>0$ ...
27
votes
4answers
2k views

Cliques, Paley graphs and quadratic residues

A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs. If p=1 mod 4 is a prime, we can define the ...
15
votes
3answers
1k views

What is the shortest route to Roth's theorem?

Roth first proved that any subset of the integers with positive density contains a three term arithmetic progression in 1953. Since then, many other proofs have emerged (I can think of eight off the ...
5
votes
1answer
308 views

Upper bound for size of subsets of a finite group that contains a sum-full set

Problem I'm looking for an upper bound for the number $k(G)$ of a finite group $G$, defined as follow: Let $\mathcal{F}_k$ be the family of subsets of $G$ with size $k$, and we define $k(G)$ be ...
11
votes
7answers
806 views

describe subsets of the integers closed under the binary operation Ax+By

Could one describe the subsets of the integers closed under the binary operation Ax+By where A and B are arbitrary fixed integers ? That is, describe the subsets S of the integers such that if ...
3
votes
1answer
956 views

Queries about the Skolem-Mahler-Lech theorem (integer zeros of exponential polynomials)

The Skolem-Mahler-Lech Theorem says that the integer zeros of an exponential polynomial are the union of complete arithmetic progressions and a finite number of exceptional zeros. ...
7
votes
1answer
573 views

Homogeneous arithmetic progressions in difference sets

I have a nasty feeling that I ought to be able to answer this question, but I've got other things to think about right now and I'm interested in the answer just so that I can reply to a mathematical ...
4
votes
1answer
501 views

Cauchy-Davenport strengthening?

Is the following statement, refining classical Cauchy-Davenport Theorem (that states that for sets $A$, $B$ of residues modulo prime $p$, $|A+B|\geq |A|+|B|-1$ provided that RHS does not exceed $p$) ...
6
votes
1answer
797 views

Additive combinatorics and large Fourier coefficients

Elon Lindenstrauss explains in his talk at the MSRI in Fall 2008 (the relevant comment is at minute 41 of the video) that the set of large Fourier coefficients of a probability measure $\mu$ on the ...
4
votes
2answers
490 views

Sum of sets modulo a square

I would be glad to see a reference to the following easy lemma in additive combinatorics: if $A_1$ and $A_2$ are two sets of remainders modulo $n^2$, each has cardinality $n > 1$ and all elements ...
20
votes
1answer
1k views

Monochromatic triangles in every two-coloring of the plane?

An old problem (possibly due to Erdős and Graham?): given a triangle $T$ and a two-coloring of the plane, does there necessary exist a monochromatic congruent copy of $T$? Here "monochromatic" means ...
7
votes
1answer
430 views

A variation of Minkowski sum

I have to work with the following variation of Minkowski sum: Let $\mathbb E$ be a Euclidean space and $K$ be a convex set in $\mathbb E\times \mathbb E$. Set $$K^+=\{\\,x+y\in\mathbb ...
2
votes
3answers
215 views

Given N points on a number line and m total distances between those points, are there efficent ways to optimize for particular values in m?

Given a set of distances S, choose N unique points P on a number line such that the distances between the N points occur in S as much as possible. That is, maximize the occurence in S of the distances ...
13
votes
1answer
587 views

Goldbach-type theorems from dense models?

I'm not a number theorist, so apologies if this is trivial or obvious. From what I understand of the results of Green-Tao-Ziegler on additive combinatorics in the primes, the main new technical tool ...
5
votes
2answers
367 views

k-pseudorandom measures

In reading the paper of Green and Tao on arithmetic progressions within the primes, I became very interested in the notion of a k-pseudorandom measure discussed in that paper. A measure here is a ...