The least prime number represented by a binary quadratic form (Q2031665)

In this paper, the author considers the problem of obtaining the optimal upper bound for the least prime number represented by a positive definite binary quadratic form in terms of its discriminant. Connections of this problem to the analysis of the complexity of some algorithms in quantum compiling are pointed out. Let \(D<0\) be a fundamental discriminant and let \(h(D)\) be the class number of the quadratic field \(\mathbb Q(\sqrt{D})\). Denote by \(\pi(X)\) the number of primes in the interval \([X,2X]\), and \(\pi_D(X)\) the number of those primes that split in \(\mathbb Q(\sqrt{D})\). A form of the main theorem of the paper is as follows. Let \(R(X,D)\) be the number of classes of binary quadratic forms of discriminant \(D\) that represent a prime in the interval \([X,2X]\). Then \[ \left(\frac{\pi_D(X)}{\pi(X)}\right)^2\ll \frac{R(X,D)}{h(D)}\left(1+\frac{h(D)}{\pi(X)}\right), \] where the implied constant is independent of \(D\) and \(X\). So with probability at least \(\alpha \left(\frac{\pi_D(X)}{\pi(X)}\right)^2\), a binary quadratic form of discriminant \(D\) represents a prime number smaller than any fixed scalar multiple of \(h(D)\log (|D|)\), where \(\alpha\) is an absolute constant independent of \(D\). It is shown that this result is optimal, in the sense that if a positive proportion of the binary quadratic forms of discriminant \(D\) represent a prime less than \(X\), then \(h(D)\log (|D|)\ll X\).