Bounding Smooth Integers (Extended Abstract)

Daniel J. Bernstein

Department of Mathematics, Statistics, and Computer Science (M/C 249) The University of Illinois at Chicago Chicago, IL 60607–7045

                              djb@pobox.com

1 Introduction

Refereed. Pages 128–130 in Algorithmic number theory: ANTS-III, edited by Joe Buhler, Lecture Notes in Computer Science 1423, Springer, 1998. An integer is y-smooth if it is not divisible by any primes larger than y. Define Ψ(x, y) = #{n : 1 ≤ n ≤ x and n is y-smooth}. This function Ψ is used to estimate the speed of various factoring methods; see, e.g., [1, section 10].

Section 4 presents a fast algorithm to compute arbitrarily tight upper and lower bounds on Ψ(x, y). For example, 1.16 · 10^{45} < Ψ(10^{54}, 10^{6}) < 1.19 · 10^{45}.

The idea of the algorithm is to bound the relevant Dirichlet series between two power series. Thus bounds are obtained on Ψ(x, y) for all x at one fell swoop.

More general functions can be computed in the same way.

Previous work

The literature contains many loose bounds and asymptotic estimates for Ψ; see, e.g., [2], [4], [5], and [9]. Hunter and Sorenson in [6] showed that some of those estimates can be computed quickly.

Acknowledgments

The author was supported by the National Science Foundation under grant DMS–9600083.

2 Discrete generalized power series

A series is a formal sum f = ∑_{r∈R} f_{r}t^{r} such that, for any x ∈ R, there are only finitely many r ≤ x with f_{r} ≠ 0.

Let f = ∑_{r} f_{r}t^{r} and g = ∑_{r} g_{r}t^{r} be series. The sum f + g is ∑_{r}(f_{r} + g_{r})t^{r}. The product fg is ∑_{r} ∑_{s} f_{r}g_{s}t^{r+s}.

I write f ≤ g if ∑_{r≤x} f_{r} ≤ ∑_{r≤x} g_{r} for all x ∈ R. If h = ∑_{r} h_{r}t^{r} is a series with all h_{r} ≥ 0, then fh ≤ gh whenever f ≤ g.

3 Logarithms

Fix a positive real number α. This is a scaling factor that determines the speed and accuracy of my algorithm: the time is roughly proportional to α, and the error is roughly proportional to 1/α.

For each prime p select integers L(p) and U(p) with L(p) ≤ α log p ≤ U(p). I use the method of [7, exercise 1.2.2–25] to approximate α log p.

4 Bounding smooth integers

Define f as the power series ∑_{p≤y}(t^{L(p)} + \frac{1}{2}t^{2L(p)} + \frac{1}{3}t^{3L(p)} + ⋯). Then

∑_{n is y smooth} t^{α log n} = ∏_{p≤y} \frac{1}{1 − t^{α log p}} ≤ ∏_{p≤y} \frac{1}{1 − t^{L(p)}} = exp f,

so Ψ(x, y) ≤ ∑_{r≤α log x} a_{r} if exp f = ∑_{r} a_{r}t^{r}.

Similarly, if ∑_{r} b_{r}t^{r} = exp ∑_{p}(t^{U(p)} + \frac{1}{2}t^{2U(p)} + \frac{1}{3}t^{3U(p)} +⋯), then Ψ(x, y) ≥ ∑_{r≤α log x} b_{r}.

One can easily compute exp f in Q[t]/t^{m} as 1 + f + \frac{1}{2}f^{2} + ⋯, since f is divisible by a high power of t; it also helps to handle small p separately. An alternative is Brent’s method in [8, exercise 4.7–4].

It is not necessary to enumerate all primes p ≤ y. There are fast methods to count (or bound) the number of primes in an interval; when y is much larger than α, many primes p will have the same value ⌊α log p⌋.

5 Results

The following table shows some bounds on Ψ(x, y) for various (x, y), along with u = (log x)/log y.

x  y α lower  upper  u xρ(u)
10^{60} 10^{2} 10^{1} 10^{18} · 5.2  10^{18} · 11.6  30 10^{11} · 0.327−
10^{60} 10^{2} 10^{2} 10^{18} · 6.73  10^{18} · 7.28  30 10^{11} · 0.327−
10^{60} 10^{3} 10^{1} 10^{32} · 1.44  10^{32} · 5.07  20 10^{32} · 0.246+
10^{60} 10^{3} 10^{2} 10^{32} · 2.278 10^{32} · 2.580 20 10^{32} · 0.246+
10^{60} 10^{3} 10^{3} 10^{32} · 2.4044 10^{32} · 2.4345 20 10^{32} · 0.246+
10^{60} 10^{4} 10^{1} 10^{41} · 0.70 10^{41} · 2.88 15 10^{41} · 0.759−
10^{60} 10^{4} 10^{2} 10^{41} · 1.191 10^{41} · 1.370 15 10^{41} · 0.759−
10^{60} 10^{4} 10^{3} 10^{41} · 1.2649 10^{41} · 1.2827 15 10^{41} · 0.759−
10^{60} 10^{5} 10^{1} 10^{46} · 0.99 10^{46} · 4.07 12 10^{46} · 1.420−
10^{60} 10^{5} 10^{2} 10^{46} · 1.679 10^{46} · 1.931 12 10^{46} · 1.420−
10^{60} 10^{5} 10^{3} 10^{46} · 1.7817 10^{46} · 1.8069 12 10^{46} · 1.420−
10^{60} 10^{6} 10^{1} 10^{49} · 1.82 10^{49} · 7.14 10 10^{49} · 2.770+
10^{60} 10^{6} 10^{2} 10^{49} · 3.025 10^{49} · 3.463 10 10^{49} · 2.770+
10^{60} 10^{6} 10^{3} 10^{49} · 3.2017 10^{49} · 3.2453 10 10^{49} · 2.770+

In the final column, ρ is Dickman’s rho function.

References

1. Joseph P. Buhler, Hendrik W. Lenstra, Jr., Carl Pomerance, Factoring integers with the number field sieve, in [10], 50–94.

2. E. Rodney Canfield, Paul Erdős, Carl Pomerance, On a problem of Oppenheim concerning “factorisatio numerorum”, Journal of Number Theory 17 (1983), 1– 28.

3. Ronald L. Graham, Jaroslav Nešetřil, The mathematics of Paul Erdős, volume 1, Algorithms and Combinatorics 13, Springer-Verlag, Berlin, 1997.

4. Adolf Hildebrand, Gérald Tenenbaum, On integers free of large prime factors, Transactions of the AMS 296 (1986), 265–290.

5. Adolf Hildebrand, Gérald Tenenbaum, Integers without large prime factors, Journal de Théorie des Nombres de Bordeaux 5 (1993), 411–484.

6. Simon Hunter, Jonathan Sorenson, Approximating the number of integers free of large prime factors, Mathematics of Computation 66 (1997), 1729–1741.

7. Donald E. Knuth, The art of computer programming, volume 1: fundamental algorithms, 2nd edition, Addison-Wesley, Reading, Massachusetts, 1973.

8. Donald E. Knuth, The art of computer programming, volume 2: seminumerical algorithms, 2nd edition, Addison-Wesley, Reading, Massachusetts, 1981.

9. Sergei Konyagin, Carl Pomerance, On primes recognizable in deterministic polynomial time, in [3], 176–198.

10. Arjen K. Lenstra, Hendrik W. Lenstra, Jr. (editors), The development of the number field sieve, Lecture Notes in Mathematics 1554, Springer-Verlag, Berlin, 1993.