Counterexamples to witness conjectures

Consider the class of exp–log constants, which is constructed from the integers using the field operations, exponentiation and logarithm. Let z be such an exp–log constant and let nbe its size as an expression. Witness conjectures attempt to give bounds (n) for the number of decimal digits which need to be evaluated in order to test whether z equals zero. For this purpose, it is convenient to assume that exponentials are only applied to arguments with absolute values bounded by 1. In that context, several witness conjectures have appeared in the literature and the strongest one states that it is possible to choose (n)=O(n). In this paper we give a counterexample to this conjecture. We also extend it so as to cover similar, polynomial witness conjectures.