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

Rational points on the unit circle

Is anything known about any of the following questions about rational points on the unit circle? By “double point” I mean an element of 2C, where C is the group of rational points on the unit circle (i.e. Gaussian rationals with unit modulus, under multiplication). Are there two rational points (x1,y1) and (x2,y2) on the … Read more

Is there another proof for Dirichlet’s theorem? [duplicate]

This question already exists: Closed 11 years ago. Possible Duplicate: Is a “non-analytic” proof of Dirichlet’s theorem on primes known or possible? Dirichlet’s theorem on primes in arithmetic progression states that there are infinitely many primes of the form $kn+h$ given that $k$ and $h$ are coprime. Is there a short proof for this? Answer … Read more

Non-asymptotically densest progression-free sets

For the context of this question, a progression-free set is a subset of integers that does not contain length-three arithmetic progressions. For large N, it is known that [N]={1,…,N} contains progression-free sets of size O(Nlog1/4N/22√2log2N) (Elkin, 2011). However, when N is of moderate size (say 220), the original Erdős-Turán progression-free subset of [N] of size … Read more

Can we do better than random when constructing dense kk-AP-free sets

We write [N] to denote {1,…,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 the largest integer N where [N] can be partitioned into two k-AP-free sets. For general k, the best lower bound is w(2;k)≥2k/ko(1) … Read more

“half arithmetic progressions” in dense sets

Fix a positive real number d>0. Szemeredi’s theorem implies that for every integer k, there exists an integer N(k,d) such that if A is a subset of the interval [1,N] with density greater than d >0, then A contains a k-term arithmetic progression. Let us now define a half AP of length 2N, to be … Read more

Thin sets that are well-distributed over arithmetic progressions?

The primes do a nice job of intersecting an arithmetic progression $\{a+dn\}_{n=0}^\infty$ when $a$ and $d$ are coprime (see Dirichlet’s theorem). I would like a set of integers $S$ such that the asymptotic density of $S$ is zero, and for every $a,d>0$, the asymptotic proportion of $S$ in $\{a+dn\}_{n=0}^\infty$ is $1/d$. Is there a well-known … Read more

Smallest prime in an arithmetic progression

Let {an}n∈N be defined as an=a+bn for some a,b>0,(a,b)=1. Are there good bounds on the minimal k s.t. ak is prime. It is well known that there are infinitely many primes in this series, Answer This is Linnik’s theorem, and the best known bound is O(b5) due to Xylouris. (This is in the Wikipedia page, … Read more

residue classes of primes, covering intervals and bounds on the different ways

Take the first n primes p1,…,pn and the primorial Pn .Denote by pi every prime bigger than pn and smaller than Pn. 1) Is that true that there always be a number in any interval of consecutive integers of length Pn not divided by any pi? (It’s the same as taking a residue class rimod … Read more

Does every prime pp appear in a pp-term arithmetic progression of primes? [duplicate]

This question already has an answer here: What is the status on this conjecture on arithmetic progressions of primes? (1 answer) Closed 3 years ago. This is a follow-up to an earlier question. The answer to that question was found on this page. The discussion on OEIS seems to suggest that, for any prime p, … Read more