34 votes
Accepted

A proof of Van der Waerden's theorem using a weakened form of Szemeredi's theorem

As (implicitly) observed already in Szemerédi's celebrated paper Szemerédi, Endre, On sets of integers containing no (k) elements in arithmetic progression, Acta Arith. 27, 199-245 (1975). ZBL0303....
user avatar
  • 91.7k
27 votes
Accepted

What is the status on this conjecture on arithmetic progressions of primes?

Yes, this is unknown; it is even unknown (as GH from MO suspected in a comment) whether $P(p) \ge 3$ always. An equivalent statement to $P(p) \ge 3$ is that there exists an integer $x>0$ such $p+x$ ...
user avatar
  • 12.4k
19 votes
Accepted

Are there any papers about this observation of the distribution of the zeros of the zeta function?

This is called Landau's formula. More precisely, if we extend the von Mangoldt function $\Lambda(n)$ to the function $\Lambda:\mathbb R_+\to \mathbb R$ by $\Lambda(x)=0$ for non-integer $x$, then $$ \...
user avatar
17 votes
Accepted

Sums of two squares in arithmetic progressions

The first result in this direction seems to be due to R. A. Smith, ``The Circle Problem in an Arithmetic Progression,'' Can. Math. Bull. 11 (2), 175–184 (1968). He showed that if we write $$\sum _{n\...
user avatar
16 votes
Accepted

Most dense subset of numbers that avoids arbitrarily long arithmetic progressions

You are essentially asking for quantitative estimates on Szemerédi's theorem, which states that the largest subset of $[1,n]$ without a k-term arithmetic progression has size $o(n)$. To be precise, ...
user avatar
16 votes
Accepted

Arbitrarily long arithmetic progressions

A simple proof is available as well. Pick p coprime to d and let t be such that td=1 mod p. Then, mod p, t times the arithmetic progression looks like a sequence of consecutive integers. Thus its ...
user avatar
14 votes

Primes from a Dirichlet sequence and an irrational number

It is well-known that not only does the arithmetic progression $\{ak+b\}_{k \in \mathbb{Z}^{+}}$ contain infinitely many prime numbers, but also that the series of the reciprocals of those primes ...
user avatar
13 votes

Is there an 11-term arithmetic progression of primes beginning with 11?

Siemion Fajtlowicz has been promoting the topic of $p$-long arithmetic progressions of primes which start with $p$ during 1993-4 (or longer). He and his colleague Micha Hofri got an $11$-long ...
user avatar
  • 3,655
12 votes

Largeness and arithmetic progression properties of generic reals

Nice question! I happened to be thinking about some similar things a few weeks ago. Here is what I found: Cohen and random reals: Cohen and random reals have just about any Ramsey-theoretic property ...
user avatar
12 votes

Arbitrarily long arithmetic progressions

If $x,y,z$ are in arithmetic progression, then $x+z-2y=0$. By the S-unit theorem of Evertse, Schmidt and Schlikewei, this equation has only finitely many solutions in $x,y,z$ having all its prime ...
user avatar
12 votes

Smallest set such that all arithmetic progression will always contain at least a number in a set

Considering the complement of $P$ in $[1,100]$, you are asking how large can a subset of $[1,100]$ be given that it does not contain any $10$-term arithmetic progression. The more general question ...
user avatar
  • 21.8k
12 votes
Accepted

A set with positive upper density whose difference set does not contain an infinite arithmetic progression

Let $\langle x\rangle$ denote the fractional part of a real number $x$ (i.e. $\langle x \rangle := x- \lfloor x\rfloor $, where $\lfloor x\rfloor $ is the greatest integer less than or equal to $x$). ...
user avatar
11 votes

Smallest set such that all arithmetic progression will always contain at least a number in a set

Using a tabu search procedure, I have found a solution for $|P|=17$, namely ${1, 11, 18, 25, 31, 32, 33, 36, 44, 51, 58, 65, 69, 70, 77, 84, 91}$. I don't know if this is optimal. EDIT: Found a ...
user avatar
11 votes
Accepted

Prime-like numbers that avoid Green-Tao?

This is likely impossible. Indeed the largest sets known to be free of arbitrarily long arithmetic progressions asymptotically satisfy $| [ A \cap [1, n] | \lesssim_{k} n / \log^{k} n$ for all $k&...
user avatar
  • 11.1k
10 votes
Accepted

Smallest prime in an arithmetic progression

This is Linnik's theorem, and the best known bound is $O(b^5)$ due to Xylouris. (This is in the Wikipedia page, and as I admitted in this year's JMM I added it to the Wikipedia page. It's in his ...
user avatar
  • 8,378
10 votes
Accepted

Adding sets not containing arithmetic progressions of length three by forcing

A "yes" answer to your question is equivalent to the statement "there exists a large set of natural numbers that admits no arithmetic progression of length three." I'm submitting the proof of this ...
user avatar
9 votes

About consecutive integers covered by arithmetic progressions

Not only is no upper bound known, it is unknown whether $m(n)$ can be infinite. It is a well-known open conjecture of Erdős and Selfridge that there does not exist an incongruent covering system whose ...
user avatar
9 votes
Accepted

Bounded gaps between primes in arithmetic progressions

Yes, see Deniz Ali Kaptan's recent arXiv preprint. (Added: See Terry Tao's comment below for more references.) Concerning your second question, even full relative density is not enough to produce ...
user avatar
  • 86.4k
9 votes

Primes from a Dirichlet sequence and an irrational number

Yes, it is irrational. This is because any finite digit sequence occurs as the initial digits of a prime in your sequence (in fact you can prescribe 41% of all the digits in the beginning), hence the ...
user avatar
  • 86.4k
9 votes
Accepted

Homogeneous van der Waerden

This is false already for $k=2,n=4$. Color an integer $m$ according to the parity of the exponent of $2$ in the prime factorization. Among $i+1,i+2,i+3,i+4$ at least one number is odd, and at least ...
user avatar
  • 24k
9 votes

Infinitely many primes in particular progressions

Chen's theorem says that there are infinitely many numbers $k$ such that $k-2$ is prime and $k$ is either prime or the product of two primes ("$k$ is a $P_2$ number"). This theorem can be modified ...
user avatar
  • 12.4k
9 votes

A reformulation of Erdős conjecture on arithmetic progressions

This question is basically asking how good greedy-type constructions of sets without long arithmetic progressions can be. The answer is actually pretty terrible. Firstly, as you note, if $f_k(n)$ is ...
user avatar
  • 5,803
8 votes

Most dense subset of numbers that avoids arbitrarily long arithmetic progressions

If a sequence avoids three term arithmetic progressions it is less than ((log log N)^4)N/log N according to "A Quantitative improvement for Roths’s Theorem On Arithmetic Progressions" which is ...
user avatar
8 votes
Accepted

Thin sets that are well-distributed over arithmetic progressions?

Sets of the form $[n^\alpha]$, $\alpha\in(1, \infty)\setminus\mathbb{N}$ are well distributed in arithmetic progressions. More generally we have that for every $\alpha\in(1, \infty)\setminus\mathbb{N}$...
user avatar
8 votes
Accepted

Subsets of [1..N] with no three-term arithmetic progressions and no large gaps

For the sake of having a reference, Ron Graham shows in "On the growth of a van der Waerden-like function" that for a fixed $k$, there exists a 3AP-free subset of $\{1,2,\dots,N\}$ with gaps bounded ...
user avatar
8 votes

Is there an 11-term arithmetic progression of primes beginning with 11?

For the sake of easy education let me mention the first simplest step toward finding $p$-long arithmetic progressions of primes which start with $p$. Let $q$ be an arbitrary prime. Then the ...
user avatar
  • 3,655
7 votes

Primes in arithmetic progression with a moduli equal to a power of 2

There is nothing special about $p=2$; just that there are some technical differences, e.g. the group of reduced residues looks a little different than for odd prime powers. In the case of powers of a ...
user avatar
  • 42.5k
7 votes
Accepted

Siegel-Walfisz for the Möbius function

The Siegel-Walfisz principle for a function $f(n)$ states that for all $A>0$ fixed then whenever $a$ modulo $q$ is a residue class with $a$ and $q$ coprime then one has $$\sum_{\substack{n\leq x \\ ...
user avatar
  • 2,645

Only top scored, non community-wiki answers of a minimum length are eligible