Questions tagged [arithmetic-progression]

An arithmetic progression is a (possibly infinite) sequence of numbers such that the difference between consecutive terms is always the same value.

Filter by
Sorted by
Tagged with
59 votes
1 answer
14k views

Is the Green-Tao theorem true for primes within a given arithmetic progression?

Ben Green and Terrence Tao proved that there are arbitrary length arithmetic progressions among the primes. Now, consider an arithmetic progression with starting term $a$ and common difference $d$. ...
Akela's user avatar
  • 3,579
10 votes
2 answers
3k views

least prime in a arithmetic progression

Hello Here I want to consider the simplest arithmetic progression $n\equiv 1\pmod{q}$ where $q$ is a prime. Is it true that we can find a prime $p\leq q^2$ in this arithmetic progression? This ...
M.B's user avatar
  • 2,468
69 votes
4 answers
13k views

Is a "non-analytic" proof of Dirichlet's theorem on primes known or possible?

It is well-known that one can prove certain special cases of Dirichlet's theorem by exhibiting an integer polynomial $p(x)$ with the properties that the prime divisors of $\{ p(n) | n \in \mathbb{Z} \}...
Qiaochu Yuan's user avatar
27 votes
5 answers
8k views

Erdos Conjecture on arithmetic progressions

Introduction: Let A be a subset of the naturals such that $\sum_{n\in A}\frac{1}{n}=\infty$. The Erdos Conjecture states that A must have arithmetic progressions of arbitrary length. Question: I ...
Alex R.'s user avatar
  • 4,902
16 votes
4 answers
2k views

Arithmetic progressions without small primes

The following question came up in the discussion at How small can a group with an n-dimensional irreducible complex representation be? : Is it known that there are infinitely many primes p for which ...
David E Speyer's user avatar
11 votes
2 answers
1k views

Most dense subset of numbers that avoids arbitrarily long arithmetic progressions

The famous Green-Tao theorem says that there exist arbitrarily long sequences of primes in arithmetic progression. I am wondering: How dense can a subset $S \subset \mathbb{N}$ be and still avoid ...
Joseph O'Rourke's user avatar
26 votes
1 answer
1k views

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

The Green-Tao theorem states that for every $n$, there is an arithmetic sequence of length $n$ consisting of primes. For primes, $p$, let $P(p)$ be the maximum length of an arithmetic progression of ...
Gorka's user avatar
  • 1,825
12 votes
3 answers
892 views

Mertens-like sum in arithmetic progressions

I find myself needing a good estimate for $\sum_{p\le x,\, p\equiv a\bmod q} 1/p$, perhaps something like $$ \sum_{p\le x,\, p\equiv a\bmod q} \frac1p = \frac{\log\log x}{\phi(q)} + b(q,a) + O\big(\...
Greg Martin's user avatar
  • 12.7k
4 votes
1 answer
234 views

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

We write $[N]$ to denote $\{1,\dots,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 ...
Zach Hunter's user avatar
  • 3,375
41 votes
3 answers
4k views

A game on integers

$A$ and $B$ take turns to pick integers: $A$ picks one integer and then $B$ picks $k > 1$ integers ($k$ being fixed). A player cannot pick a number that his opponent has picked. If $A$ has $5$ ...
Haoran Chen's user avatar
29 votes
4 answers
3k views

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

i.e. does there exist an integer $C > 0$ such that $11, 11 + C, ..., 11 + 10C$ are all prime?
Kim's user avatar
  • 4,034
25 votes
5 answers
4k views

Finitely many arithmetic progressions

A few years ago, somebody told me a lovely problem. I suspect there may be more to it (which I would be interested in learning), and would very much like to find a reference, it makes me uncomfortable ...
Andrés E. Caicedo's user avatar
17 votes
2 answers
2k views

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

Van der Waerden's theorem states that any colouring of the integers in a finite number of colours has monochromatic arithmetic progressions of arbitrary length. Szemerédi's Theorem is a dramatic ...
Ivan Meir's user avatar
  • 4,762
15 votes
1 answer
3k views

The Green-Tao theorem and positive binary quadratic forms

Some time ago I asked a question on consecutive numbers represented integrally by an integral positive binary quadratic form. It has occurred to me that, instead, the Green-Tao theorem may include a ...
Will Jagy's user avatar
  • 25.3k
13 votes
7 answers
3k views

Special arithmetic progressions involving perfect squares

Prove that there are infinitely many positive integers $a$, $b$, $c$ that are consecutive terms of an arithmetic progression and also satisfy the condition that $ab+1$, $bc+1$, $ca+1$ are all perfect ...
Cosmin Pohoata's user avatar
12 votes
2 answers
867 views

Arithmetic progressions modulo $p$ under the squaring map

I feel that the following problem should be known, but I'm not sure where to look for it. Fix a real constant $\frac{1}{2} \ge \epsilon > 0$. For varying primes $p$, Let $A_p$ denote the set of ...
user avatar
5 votes
2 answers
627 views

Primes from a Dirichlet sequence and an irrational number

From Dirichlet's theorem on arithmetic progressions, if $\text{gcd}(a,b)=1$ we know $\{ak+b\}_{k\ge 0}$ contains infinitely many primes. Let those primes be $p_1,p_2,\cdots$. Then the real $$\alpha=0....
shadow10's user avatar
  • 1,090
4 votes
2 answers
656 views

"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, ...
Mark Lewko's user avatar
  • 11.7k
4 votes
5 answers
2k views

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

Take the first $n$ primes $p_1,...,p_n$ and the primorial $P_n$ .Denote by $p_i$ every prime bigger than $p_n$ and smaller than $P_n$. 1) Is that true that there always be a number in any interval of ...
Asterios Gkantzounis's user avatar
3 votes
1 answer
344 views

Primes in simultaneous arithmetic progressions

Suppose we're given four positive integers $a$, $b$, $c$, $d$ such that $a$ and $b$ are coprime, and $c$ and $d$ are coprime. Is there a non-negative integer $k$ such that both $ak+b$ and $ck+d$ are ...
Filip Nikšić's user avatar
2 votes
1 answer
264 views

Averages of Möbius function in arithmetic progressions

It is mentioned in multiple occasions here that the bound $$ \mathop{\sum_{n=1}^{N}}_{n\equiv a\mod l} \mu(n) = o(N) $$ is equivalent to the prime number theorem in arithmetic progressions. But I am ...
Krishnarjun's user avatar
2 votes
1 answer
108 views

Capset problem but considering differences with bounded support

For any dimension $D\ge 1$, we define the homomorphism $\phi: \Bbb{Z}^D\to (\Bbb{Z}/3\Bbb{Z})^D; \xi\mapsto \xi+3\Bbb{Z}^D$. Given a set $A \subset \{0,1,2\}^D$, we define $S_A$ to be the set of $v \...
Zach Hunter's user avatar
  • 3,375
2 votes
1 answer
421 views

Essential clarifications on application of pigeonhole principle

In here Lemma $4$ using pigeonhole says: For $T_1,\dots,T_s\in\Bbb R$ with $1\leq T_1,\dots,T_s<p$ and $\prod_{i=1}^sT_i > p^{s−1}$ and any integers $a_1,\dots,a_s$ there is an integer $t$ ...
user avatar
2 votes
0 answers
614 views

Arithmetic progression and average of two prime numbers

Let $A=(a_n : n \in \mathbb{N})$ be the sequence given by: $$ \ a_n = a_1 + (n - 1)d,\quad a_1,\ d,\ n \in \mathbb N,\quad d\gt a_1,\quad \gcd(a_1,\ d)=1. $$ For all terms of $A$ greater than $\ \...
Mike's user avatar
  • 359