# A lower bound for the least prime in an arithmetic progression

@article{Li2016ALB, title={A lower bound for the least prime in an arithmetic progression}, author={Junxian Li and Kyle Pratt and George Shakan}, journal={arXiv: Number Theory}, year={2016} }

Fix $k$ a positive integer, and let $\ell$ be coprime to $k$. Let $p(k,\ell)$ denote the smallest prime equivalent to $\ell \pmod{k}$, and set $P(k)$ to be the maximum of all the $p(k,\ell)$. We seek lower bounds for $P(k)$. In particular, we show that for almost every $k$ one has $P(k) \gg \phi(k) \log k \log_2 k \log_4 k / \log_3 k,$ answering a question of Ford, Green, Konyangin, Maynard, and Tao. We rely on their recent work on large gaps between primes. Our main new idea is to use sieve… Expand

#### 14 Citations

On the nth record gap between primes in an arithmetic progression

- Mathematics
- 2018

Let $q>r\ge1$ be coprime integers. Let $R(n,q,r)$ be the $n$th record gap between primes in the arithmetic progression $r$, $r+q$, $r+2q,\ldots,$ and denote by $N_{q,r}(x)$ the number of such records… Expand

Long gaps between primes

- Mathematics
- 2014

Let $p_n$ denotes the $n$-th prime. We prove that $$\max_{p_{n+1} \leq X} (p_{n+1}-p_n) \gg \frac{\log X \log \log X\log\log\log\log X}{\log \log \log X}$$ for sufficiently large $X$, improving upon… Expand

Predicting Maximal Gaps in Sets of Primes

- Mathematics
- Mathematics
- 2019

Let q > r ≥ 1 be coprime integers. Let P c = P c ( q , r , H ) be an increasing sequence of primes p satisfying two conditions: (i) p ≡ r (mod q) and (ii) p starts a prime k-tuple with a given… Expand

Dirichlet's proof of the three-square theorem: An algorithmic perspective

- Computer Science
- Math. Comput.
- 2019

It is explained how to turn Dirichlet’s proof of the Gauss–Legendre three-square theorem into an algorithm; if one assumes the Extended Riemann Hypothesis (ERH), there is a random algorithm for expressing n = x + y + z where the expected number of bit operations is O((lgn)(lg lgn)−1 ·M(lgn). Expand

Polynomial multiplication over finite fields in time O ( n log n )

- 2019

Let I(n) denote the bit complexity of multiplying two integers of at most n bits in the deterministic multitape Turing model [16]. Similarly, letMq(n) denote the bit complexity of multiplying two… Expand

N T ] 8 O ct 2 02 0 SCHINZEL HYPOTHESIS ON AVERAGE AND RATIONAL POINTS

- 2021

Schinzel’s Hypothesis (H) [52] has very strong implications for the local-to-global principles for rational points on conic bundles, as demonstrated by Colliot-Thélène and Sansuc in [17]. There have… Expand

Schinzel Hypothesis with probability 1 and rational points

- Mathematics
- 2020

We prove the existence version of Schinzel's Hypothesis (H) for $100\%$ of integer polynomials $P_1, \ldots, P_n$ of fixed degrees, when ordered by the size of coefficients. We deduce that a positive… Expand

Bernoulli models of Euler factors 6 3 . Möbius randomness law 9 4 . Dispersion 16 5

- 2020

Schinzel’s Hypothesis (H) [29] has very strong implications for the local-to-global principles for rational points on conic bundles, as demonstrated by Colliot-Thélène and Sansuc in [12]. There have… Expand

Large prime gaps and progressions with few primes

- Mathematics
- 2019

We show that the existence of arithmetic progressions with few primes, with a quantitative bound on "few", implies the existence of larger gaps between primes less than x than is currently known… Expand

Faster integer multiplication using plain vanilla FFT primes

- Mathematics, Computer Science
- Math. Comput.
- 2019

It is shown that n-bit integers may be multiplied in O(n log n 4^(log^* n)) bit operations. Expand

#### References

SHOWING 1-10 OF 30 REFERENCES

Long gaps between primes

- Mathematics
- 2014

Let $p_n$ denotes the $n$-th prime. We prove that $$\max_{p_{n+1} \leq X} (p_{n+1}-p_n) \gg \frac{\log X \log \log X\log\log\log\log X}{\log \log \log X}$$ for sufficiently large $X$, improving upon… Expand

Prime Chains and Pratt Trees

- Mathematics
- 2009

Prime chains are sequences $$p_{1}, \ldots , p_{k}$$ of primes for which $${p_{j+1} \equiv 1}$$ (mod pj) for each j. We introduce three new methods for counting long prime chains. The first is used… Expand

Dense clusters of primes in subsets

- Mathematics
- Compositio Mathematica
- 2016

We prove a generalization of the author’s work to show that any subset of the primes which is ‘well distributed’ in arithmetic progressions contains many primes which are close together. Moreover,… Expand

On the Least Prime in an Arithmetical Progression and Theorems Concerning the Zeros of Dirichlet’s L -Functions ( V )

- Mathematics
- 1991

Let D be a large positive integer, (K, D) = 1, and P(D, K) the least prime p ≡ K (mod D). In 1934, S. Chowla conjectured that P(D, K) ≪ D 1+e . Three years later, P. Turan proved that under the… Expand

A note on the least prime in an arithmetic progression

- Mathematics
- 1980

Abstract Let k , l denote positive integers with ( k , l ) = 1. Denote by p ( k , l ) the least prime p ≡ l (mod k ). Let P ( k ) be the maximum value of p ( k , l ) for all l . We show lim inf P(k)… Expand

Unusually large gaps between consecutive primes

- Mathematics
- 1990

Let G(x) denote the largest gap between consecutive primes below x. In a series of papers from 1935 to 1963, Erdos, Rankin, and Schonhage showed that G(x) > (c + o(1)) logx loglogx… Expand

The Least Prime in Certain Arithmetic Progressions

- Computer Science
- Am. Math. Mon.
- 2009

1. S. Hedman, A First Course in Logic, Oxford University Press, New York, 2004. 2. D. Hobby and D. M. Silberger, Quotients of Primes, this MONTHLY 100 (1993) 50–52. 3. S. Marivani, On some particular… Expand

The Difference between Consecutive Prime Numbers, III

- Mathematics
- 1938

I = lim inf v n-a* log n The purpose of this paper is to combine the methods used in two earlier papers' in order to prove the following theorem. THEOREM. (1) 1 5 c(1 + 4e)/5, where c 1 -c, so that… Expand

On the difference between consecutive prime numbers

- Mathematics
- 1975

/ = lim inf ̂ 11-tl . »->» log pn The purpose of this paper is to combine the methods used in two earlier papers1 in order to prove the following theorem. Theorem. (1) / = c(l + 40)/5, where c<… Expand