1.Introduction

Consider the class of exp-log constant expressions, which is constructed from the integers using the field operations, exponentiation and logarithm. An important problem in computer algebra is to test whether an exp-log constant expression represents zero. A straightforward approach is to evaluate up to a certain number of decimal digits and test whether this evaluation vanishes. Witness conjectures attempt to give bounds for the number of decimal digits which are necessary as a function of the size of the expression .

Of course, exponentials can be used in order to produce massive cancellations, like in

For this reason, it is appropriate to allow only for exp-log expressions such that for all subexpressions of the form . In that context, several witness conjectures appeared in the literature [vdH97, vdH01a, vdH01b, Ric01], and the strongest one states that we may take .

In this paper we give a counterexample to this strong witness conjecture. The counterexample is based on the observation that it suffices to find a counterexample for the power series analogue of the problem [vdH01b] and a suggestion made by D. Richardson. In Section 4, we will generalize our technique and give counterexamples to all witness conjectures with . However, for this generalization, we need to extend the notion of exp-log constants so as to include algebraic numbers.

In what follows, we will freely use Hardy's notations for and for . We also write if and if . Finally, given a field , we denote .

2.Notations

Let be the set of admissible constant expressions built up from and . Here a constant is said to be admissible if it evaluates to a real number. Given , we denote by its size (the number of inner nodes in the corresponding expression tree plus the number of digits which are needed to write the integers at the leaves) and by its evaluation. We denote by the subset of all expressions , such that for all subexpressions of the form .

Consider the ring of formal power series. A series is said to be infinitesimal if . If , then its valuation is the smallest number with . Let be the set of series expressions built up from , elements in , the ring operations and left composition of expressions which represent infinitesimal series by one of the series

Given such an expression , we denote by its size (the number of nodes of the corresponding expression tree) and by the represented series. We also denote by the number of occurrences of in and by the valuation of .

Given and with , the substitution of for in yields another series expression in and we have

			(1)
			(2)

Similarly, given and , such that is sufficiently small, the substitution of for in yields a constant expression of size

(3)

where is the number of inner nodes of plus the sizes of the rational numbers on the leaves. For , we also have

Proposition 1. Given with and , we have

			(4)
			(5)

If is such that is sufficiently small, then we also have

(6)

Proof. This follows from (1), (2) and (3) by a straightforward induction.

3.The strong witness conjecture

Consider

We have , and , since

Proof. By Proposition 1, we have and . It therefore suffices to take for a sufficiently large .

Proof. On the interval , we notice that satisfies . Hence, for all . By Proposition 1, we also have for large . Therefore, it suffices to take for a sufficiently large .

4.Polynomial witness conjectures

Let , and be the analogues of , and , if we replace and by the set of algebraic numbers in their respective definitions. The size of an algebraic number is defined to be the minimal size of a polynomial equation satisfied by . After choosing a suitable determination of , the evaluations of constants in are complex numbers. The analogues of all observations in Section 2 remain valid.

Given and , we denote

Proof. Let be maximal such that . Modulo postcomposition of both sides of the equation with

we may assume without loss of generality that . Then admits a singularity above , near to which . On the other hand, the number of nested logarithms in the logarithmic transseries expansion of near any point above cannot exceed . Therefore, we must have .

Proof. The mapping from into , which maps to the first Taylor coefficients of , is polynomial. Since , this mapping cannot be injective. We conclude by the previous Lemma.

Theorem 6. Let be a witness function with

Then there exists an expression of size with and .

Proof. With as in Lemma 5, consider for large and

Since , and , Proposition 1 implies

(7)

and

(8)

From (7) it follows that

Plugging this into (8), we obtain

which clearly implies the Theorem, by choosing large enough.

Proof. With as in Lemma 5, choose such that . Then for sufficiently small, the closed disk is mapped into itself and for . Now Proposition 1 implies and for large . Therefore, yields the desired counterexample for a sufficiently large .

5.Algebraic counterexamples

The technique from the previous Section may also be used in order to produce algebraic counterexamples. Indeed, given and , let

Then we have the following analogue of Lemma 4:

Proof. Consider the Riemann surface of admits an algebraic singularity at

of degree . On one of the two leaves, we again have an algebraic singularity at

of degree , and so on for the given by

We conclude by the observation that the mapping is injective.

6.Conclusion

We have given counterexamples to the most optimistic kind of witness conjectures. In the power series context, we previously proved a witness conjecture for a doubly exponential witness function [SvdH01]. Hopefully, this technique may be extended in order to yield Khovanskii-like bounds [Kho91]. If this turns out to be possible indeed, the next challenge would be to study what happens for growth rates between and . In particular, it would be very useful for practical applications if the witness conjecture would hold for a witness function of exponentiality (i.e., for sufficiently large ).

It might also be interesting to further investigate the proof technique used in this paper. For instance, can we do without algebraic numbers? Would it be possible to replace by in Lemma 5? Can we make Theorem 7 as strong as Theorem 6? Does there exist an approximation theory for power series by expressions of the form (analogous to Padé approximation)?

Bibliography