Master-Thesis

A coarse-grained integer is an integer whose few prime factors stem from a given interval.  The issue of this thesis is to learn more about the number of such integers below a given bound x.

Prime counting has long been done and is reasonably well understood. Based on this, smooth numbers have been counted, and also the rough ones. The conjunction of both properties, with different parameters (coarse-grained), poses difficult problems: in a straightforward approach the classical error terms dominate the main term. It is thus important to use strong versions of the prime number theorem to obtain reasonable approximations on the number of such integers.

One application that uses numbers which are a product of just a few primes is the number field sieve. For fine tuning it is vital to understand the distribution of the inputs in detail. This however leads directly to the problem described above: counting coarse-grained integers.

Generalizations of prime counting algorithms to coarse-grained numbers may be used to obtain even exact counts. Similar tasks already occur in the combinatorial method for prime counting. This may at least give answers in lower ranges to check the predicted quality of theoretical approximations.

Another way of attacking the problem may lie in deriving direct exact formulas in the spirit of Riemann. This may lead to much better error bounds and shed more light on classes of integers that are of great importance in the heuristics for factoring algorithms like the GNFS.

There are three classes of algorithms to determine the number of primes up to a bound x (see Oliveira e Silva 2006 or Crandall & Pomerance 2002). Sieving algorithms produce a bit vector identifying primes within a certain interval. The combinatorial method employs structural properties to — loosely speaking — predict a large portion of the sieving results. The analytical method uses exact formulae together with fast multi-evaluation techniques for the Riemann zeta function.

In many investigations bounds on prime counts are used, often with error bounds only obtainable under the Riemann hypothesis. This actually is of no harm if the numbers in the application are small enough to allow experimental verification of these error bounds. For example, Schoenfeld (1976) proved that under the Riemann hypothesis for x≤2657 we have

|π(x) − Li(x)| ≤ (8π)^-1 x^½ ln x.

We have computationally verified this inequality experimentally for x≤2⁴⁰.

Clearly, such calculations cannot prove asymptotical theorems. For example, for x≤2⁸⁰ all known values for π(x) verify |π(x) − Li(x)|≤x^½ / ln x though Littlewood (1914) has proved that the difference π(x) − Li(x) must overshoot K x^½ ln ln ln x / ln x infinitely many times in both directions for some K > 0. However, often good numerical material can be used to disprove conjectures.

The purpose of this thesis (or these theses) would be to transfer knowledge and algorithms on prime counting to counting of coarse-grained numbers. This involves theory and practice:

• Develop and prove a formula for the number of coarse-grained integers in the spirit of Riemann.
• Transfer theory and algorithms for prime counting to counting coarse-grained integers.

• Richard E. Crandall & Carl Pomerance (2002). Prime Numbers: A Computational Perspective. Springer-Verlag, Berlin / New York.
• Xavier Gourdon & Pascal Sebah (2001). Counting the number of primes. Webpage.
• Andrew Granville & Greg Martin (2006). "Prime Number Races". American Mathematical Monthly (Washington, DC: Mathematical Association of American) 113 (1): 1?33. doi:10.2307/27641834. ISSN 0002-9890.
• Andrew Granville (2008). Smooth numbers: computational number theory and beyond. In Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptograohy, JOSEPH P. BUHLER & PETER STEVENHAGEN, editors, number 44 in Mathematical Sciences Research Institute Publications, 69?82. Cambridge University Press, New York. ISBN 978-0-521-80854-5.
• Daniel Loebenberger & Michael Nüsken (2010). Coarse-grained integers.
• Michael Nüsken (2011-). Primeflux.
• Tomás Oliveira e Silva (2006). Computing π(x): the Combinatorial Method. Revista do DETUA 4(6), 759-768.
• Lowell Schoenfeld (1976). Sharper bounds for the Chebyshev functions θ(x) and ψ(x). II. Mathematics of Computation 30(134), 337?360.