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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#### Related Tags

arithmetic-progression × 149nt.number-theory × 101

prime-numbers × 50

co.combinatorics × 41

additive-combinatorics × 37

analytic-number-theory × 34

reference-request × 15

conjectures × 4

prime-number-theorem × 4

set-theory × 3

sequences-and-series × 3

open-problems × 3

divisors-multiples × 3

ramsey-theory × 3

ds.dynamical-systems × 2

discrete-geometry × 2

fourier-analysis × 2

asymptotics × 2

forcing × 2

ergodic-theory × 2

diophantine-equations × 2

riemann-zeta-function × 2

infinite-combinatorics × 2

computational-number-theory × 2

extremal-combinatorics × 2