Transforming our number-theoretical constants

The first task

How to transform an Euler product of the shape

prodp (1 - f(p)/g(p)),      p >= p0,

into a product of powers of zeta function values

prodk>1 zeta(k)-e[k]

(where zeta(s) denotes the Riemann zeta function)?

The basic idea, which seems to have been rediscovered independently many times, is to rewrite the original factors as products of factors of the simpler shape (1-p-k), and then rearrange the whole affair, collecting factors with the same k into the zeta(k) contribution. The decomposition of the original factors does not depend on p; it amounts to a formal manipulation of power series.

...

Graphically, the decomposed product can be represented as follows. The dot sizes give a rough indication of the contributions from the individual terms. (More accurately, since we are talking products rather than sums, of how far away from 1 each individual factor is, taking its exponent e[k] into due account.)

The original formula corresponds to collecting entire columns, each of which contributes a factor which can be expressed directly as a rational number, and if we then multiply finitely many of these column products together and discard the remainder, we lose everything to the right of the red rectangle:

The transposed formula corresponds to collecting entire rows, each of which contributes a factor zeta(k)-e[k]. When we take finally many of these (up to some bound M for k) and discard the remainder, we lose everything above the blue rectangle, which looks clearly like a significant improvement:

However, this is only one half of the story.

If the resulting product of powers of zeta values converges, it does so a lot faster than the original Euler product, since the values zeta(k) decrease exponentially towards 1 as k increases. (An upper bound is

zeta(k) < 1 + 2-k + 21-k/k

which follows from the obvious majorization of sumn>2n-k by the corresponding integral from 2 to infinity.)

But the growth of the exponents is also exponential. It can be shown that the |e[k]| behave as well as, but no better than, the powers betak, where beta denotes the maximum of the absolute values of the characteristic roots of the recurrences defining the exponents - that is, of the polynomial (g-f)g. Thus if beta is at least 2, the power product will fail to converge at all, since the factors zeta(k)-e[k] will differ from 1 by something of size (beta/2)k.

When beta equals 2, the picture looks as follows:

(the column at p=2 still has a finite product whose rational value can be written down explicitly, but we are outside the domain of convergence of the decomposition, and the individual factors do not approach 1), and while the original formula converges poorly,

the transposed formula is completely useless:

Fortunately, there is an elegant way around this obstacle, improving the convergence (or the running time) when beta is small, and establishing it in the first place when it is large. It can be brought to bear no matter how large beta turns out to be.

...

In pictures, for small beta and for the case beta=2:

The black dots in the intersection of the two rectangles correspond to the finitely many factors which we pick up twice, via the columns and via the rows, and which we must remove explicitly (once) in order to obtain the correct result. We remove them from the rows, because we then need to raise only one number per row to the e[k]-th power. (Once the exponents get large, this is a time-consuming operation. Moreover, the red-rectangle product over the zeta powers can overflow even the huge floating-point representation range of PARI/gp when beta is large; removing the black-rectangle part immediately from each row keeps the numbers nice and small.)


/