User kdr - MathOverflow

On the least prime in arithmetic progressions

2012-03-08T00:32:33Z

My question concerns the least prime (denoted $p(a, q)$) in the arithmetic progression $a \pmod q$ where $a$ and $q$ are coprime. Quite a time ago Linnik demonstrated that $$p(a, q) \ll q^L$$ for some absolute constant $L$. Wiki page for this theorem lists a number of papers that estimate $L$ with the most recent result by Xylouris who proved that $L \leq 5.2$.

It is also known that the Generalized Riemann Hypothesis implies $$p(a, q) \ll (q\log q)^2 \text{,}$$ while in 1978, Heath-Brown conjectured even tighter bound: $$p(a, q) \ll q(\log q)^2 \text{.}$$ I'm wondering whether this last bound, if true (it is still an open problem), implies something non-trivial about $L$-functions?

What is the current status of Agrawal's conjecture?

2010-11-12T18:38:01Z

In their famous 'Primes is in P' paper Agrawal, Kayal and Saxena stated the following conjecture:

If for coprime integers $n$ and $r$ the equality $(X-1)^n = X^n - 1$ holds in $\mathbb{Z}_n[X]/(X^r-1)$ then either $n$ is prime or $n^2 = 1 \pmod{r}$.

If true this would give a beautiful characterization of primes that could be easily transformed into a fast ($O(\log^{3+\epsilon}{n})$) and deterministic primality test.

Shortly after publishing 'Primes is in P' Hendrik Lenstra noticed that the conjecture may not be valid for $r=5$ and $n$ of the very special form (see Lenstra's and Pomerance's note, p.30). It was unknown whether any such $n$ existed but Carl Pomerance gave a heuristic argument convincing that there should be infinitely many $n$'s sharing these, apparently rare, properties. I'm not aware of any strict proof for this.

It may also happen that the conjecture in a modified form (if we restrict $r$ to be greater than $\log{n}$) can be still true.

Martin Mačaj (see Some remarks and questions about the AKS algorithm and related conjecture) gave another version of this conjecture together with a proof that relied on yet another unsolved problem.

Does anyone know if there were any advances in this area in the recent years?

Comment by kdr

2012-03-25T21:26:20Z

Thanks to both of you: unknown and Greg. I think I understand. Your arguments sound convincing.