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:
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.)