Bonn-Aachen International Center
for Information Technology

Imprint

cosec

students

science

city life
cosec >students >Theses topics >Completed topics 

Master-Thesis

Counting coarse-grained integers

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≤240.

Clearly, such calculations cannot prove asymptotical theorems. For example, for x≤280 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:

Literature

Imprint, webmaster & more