User kdr - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T09:19:09Z http://mathoverflow.net/feeds/user/10792 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90523/on-the-least-prime-in-arithmetic-progressions On the least prime in arithmetic progressions kdr 2012-03-08T00:32:33Z 2012-03-13T14:46:12Z <p>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$. <a href="http://en.wikipedia.org/wiki/Linnik%2527s_theorem" rel="nofollow">Wiki page</a> 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$.</p> <p>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?</p> http://mathoverflow.net/questions/45855/what-is-the-current-status-of-agrawals-conjecture What is the current status of Agrawal's conjecture? kdr 2010-11-12T18:38:01Z 2010-11-30T09:00:57Z <p>In their famous 'Primes is in P' paper Agrawal, Kayal and Saxena stated the following conjecture:</p> <blockquote> <p>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}$.</p> </blockquote> <p>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.</p> <p>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 <a href="http://www.aimath.org/WWN/primesinp/primesinp.pdf" rel="nofollow">Lenstra's and Pomerance's note</a>, 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.</p> <p>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.</p> <p>Martin Mačaj (see <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.144.7953&amp;rep=rep1&amp;type=pdf" rel="nofollow">Some remarks and questions about the AKS algorithm and related conjecture</a>) gave another version of this conjecture together with a proof that relied on yet another unsolved problem.</p> <p>Does anyone know if there were any advances in this area in the recent years?</p> http://mathoverflow.net/questions/90523/on-the-least-prime-in-arithmetic-progressions/91084#91084 Comment by kdr kdr 2012-03-25T21:26:20Z 2012-03-25T21:26:20Z Thanks to both of you: unknown and Greg. I think I understand. Your arguments sound convincing.