Smooth Values of Quadratic Polynomials

Abstract

Let ${\mathcal{Q}}_a(z)$ be the set of z-smooth numbers of the form $q^2+a$. It is not obvious, but this is a finite set. The cardinality can be quite large; for example, $|{\mathcal{Q}}_1(1900)|\ge 646890$. We have a remarkably simple and fast algorithm that for any a and any z yields a subset $Q_a(z)\subset {\mathcal{Q}}_a(z)$ which we believe contains all but a tiny fraction of the elements of ${\mathcal{Q}}_a(z)$, i.e. $|{\mathcal{Q}}_a(z)|=(1+o(1))|Q_a(z)|$. We have used this algorithm to compute $Q_a(500)$ for all $0<a\le 25$. Analyzing these sets has led to several conjectures. One is that the set of logarithms of the elements of $Q_a(z)$ become normally distributed for any fixed a as $z\to \infty$. A second has to do with the prime divisors $p\le z$ of the sets $Q_a(z)$. Clearly any prime divisor p of an element of ${\mathcal{Q}}_a(z)$ must have the property that – a is a square modulo p. For such a p we might naively expect that approximately $2/p$ of the elements of ${\mathcal{Q}}_a(z)$ are divisible by p. Instead we conjecture that around $c_{p,a,z}/\sqrt{p}$ of the elements are divisible by p where $c_{p,a,z}$ is usually between 1 and 2.

Keywords:

• Quadratic sieve
• smooth numbers
• Pell’s equation

Additional information

Funding

The first author was supported in part by a grant from the NSF.