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 instance, he uses a primitive version of the Regularity Lemma (weaker and more complicated), so I would like to find some source … Read more

Restricted addition analogue of Freiman’s (3n−4)(3n-4)-theorem

There is a well-known theorem of Freiman saying that if A is a finite set of integers with |2A|≤3|A|−4, then A is contained in an arithmetic progression with at most |2A|−|A|+1 terms. Is there an analogue of this result for the “restricted sumset” 2^A={a+b:a,b∈A,a≠b}? How “long” can A be given that |2^A| is small? Answer … Read more

An inequality from Green-Tao “The primes contain arbitrary long arithmetic progressions”

I have been reading “The primes contain arbitrary long arithmetic progressions” by Green and Tao (The version on the ArXiv: going through the details and there is this inequality I am not seeing at the moment. I would greatly appreciate if someone could explain me how to get it. The inequality is on p27 … Read more

Two variants of the Littlewood-Offord theorem

I found two different looking things being called the Littlewood-Offord theorem, If →a∈Rk∖0 and t∈R then there are O(2k√k) points x∈{1,−1}k such that →a.→x=t If →a∈Rk is such that at least n of the ai have |ai|≥1 then for x∼{1,−1}k uniformly at random and I an interval of length 2 we have Prx[→a.→x∈I]≤O(1√n) Can someone … Read more

On point sets with many distinct distances

Let P be a set of n points in the plane and let D be the set of Euclidean distances determined by the pairs of points in P. Suppose that for each d∈D there are at most 5 (unordered) pairs (A,B)∈P×P so that AB=d. Must P contain a subset of points P′ of size Ω(n) … Read more

Linear combination of characters

For each i∈N, let Gi be a finite abelian group and ^Gi the ¯Q-valued character group of Gi. Suppose that |Gi|→∞ as i→∞. Let Si⊂^Gi be a subset of characters satisfying the following. (i) For given ϵ>0, we have ⟨s|s∈Si⟩≫|Gi|1−ϵ as i→∞. (ii) Si is GQ-stable i.e. if s∈Si, then sσ∈Si for each σ∈Gal(¯Q/Q) with … Read more

Does every n×n×nn\times n\times n Latin cube contain a Latin transversal?

In 1967 H. J. Ryser conjectured that every Latin square of odd order has a Latin transversal. Similar to Latin squares, we may consider Latin cubes. QUESTION: Let n be any positive integer. Does every n×n×n Latin cube contain a Latin transversal? Let N be any positive integer. In 2008, I proved that for the … Read more

Inequalities about tripling and doubling sumsets

Let A be a set of vectors in Zd who R-span is the whole Rd. Let si(A) denote the size of A+A+…A (i times). I am interested in the following: Question 1: Find sufficient conditions on A so we have: s_3(A)\geq (d+2)s_2(A) -\binom{d+2}{2}s_1(A)+\binom{d+2}{3} ? For d=1 A is just a bunch of integers. Then the … Read more

A conjecture on the cardinality of minimal mediated sequences

For a sequence of integer numbers $A=\{0,q_1,\ldots,q_m,p\}$ (arranged from small to large), if every $q_i$ is an average of two distinct numbers in $A$, then we say $A$ is a mediated sequence. Example. $A=\{0,2,4,5,8,11\}$ is a mediated sequence. For a fixed $p$ and an integer $0<q<p$, a minimal mediated sequence containing $q$ is a mediated … Read more

Strengthening of Freiman’s theorem

Is the following strengthening of Freiman’s theorem true? Let G be an abelian group. We say that a set X⊂G is d-structured if X is a union of d or less d–dimensional (generalized) arithmetic progressions. For every C,ε>0 there exists d=d(C,ε) such that for every sets A,B⊂G of cardinality n satisfying |A+B|≤Cn, there exist d–structured … Read more