<\body> >>>|\>>|\>>>>>>||||<\author-address> Dépt. de Mathématiques (bât. 425)Université Paris-Sud91405 Orsay CEDEXFrance >|||>> <\abstract> Consider the class of exp-log constants, which is constructed from the integers using the field operations, exponentiation and logarithm. Let be such an exp-log constant and let be 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 equals zero. For this purpose, it is convenient to assume that exponentials are only applied to arguments with absolute values bounded by . 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. 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 (n)> 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 <\equation*> \>+\

>>>-\>>-1\0. For this reason, it is appropriate to allow only for exp-log expressions such that 1> for all subexpressions of the form >. In that context, several witness conjectures appeared in the literature , and the strongest one states that we may take (n)=O(n)>. 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 and a suggestion made by

Richardson>. In Section , we will generalize our technique and give counterexamples to all witness conjectures with (n)=n>. 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 =o(\)> and \\> for =O(\)>. We also write \\> if \\\\> and \\> if -\\\>. Finally, given afield

>, we denote >=\\{0}>.

Let > be the set of admissible constant expressions built up from ,+,-,\,/,exp> and . Here a constant is said to be admissible if it evaluates to a real number. Given \>, we denote by (c)\\> 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 >\|\1> for all subexpressions of the form >. Consider the ring =\[[z]]> of formal power series. A series +f z+\\\> is said to be if =0>. If 0>, then its is the smallest number\> with \0>. 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 <\eqnarray*> ||>|||>|||>>> Given such an expression \>, we denote by (f)\\> its size (the number of nodes of the corresponding expression tree) and by >\\> the represented series. We also denote by f> the number of occurrences of in and by >)> the valuation of >>. Given \> and \> with >)\0>, the substitution of for in yields another series expression g> in > and we have <\eqnarray*> (f\g)>||(f)+(# f)*(\(g)-1);

>>|g|\>)>||>)*v(>).

>>>> Similarly, given \> and \>, such that >\|> is sufficiently small, the substitution of for in yields a constant expression \> of size <\equation> \(f(c))=|~>(f)+(# f)*(\(c)-1), where |~>(f)> is the number of inner nodes of plus the sizes of the rational numbers on the leaves. For >\0>, we also have <\equation*> log \|>\|\v(>)*log \|>\|. <\proposition> Given \> with >)\0> and \>, we have <\eqnarray*> (fk>)>||(f)-# f)* f)-1|# f-1>+(# f);

>>|k>|\>)>||>).

>>>> If \> is such that >\|> is sufficiently small, then we also have <\equation> \(fk>(c))=(|~>(f)-# f)* f)-1|# f-1>+(# f)*\(c). <\proof> This follows from (), () and () by a straightforward induction. Consider <\equation*> \=2*log(1-log(1-z/2))-z\\. We have (\)=11>, \=2> and |\>)=3>, since <\equation*> |\>=*z+O(z). <\theorem> Let > be a witness function with (n)=O(n>)> and \log 3/log 2>. Then there exists an expression \\> of size with |\>\0> and |\>)\\(n)>. <\proof> By Proposition , we have \(\k>)=10\2-9\2> and k>|\>)=3>. It therefore suffices to take =\k>> for a sufficiently large . <\theorem> Let > be a witness function with (n)=O(n>)> and \log 3/log 2>. Then there exists a constant expression \> of size with >\0> and >\|\\\(n)>>. <\proof> On the interval ]>, we notice that |\>> satisfies |\>(c)\c>. Hence, k>()|\>\|\23>> for all . By Proposition , we also have \(\k>())\2> for large . Therefore, it suffices to take k>()> for a sufficiently large . 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 remain valid. Given 2> and =(a,\,a)\(|^>>)>, we denote <\equation*> \

>=(a*z)\log(1+z)\(a*z)\\\(a*z)\log(1+z)\(a*z)\

|^>. <\lemma> Given ,\\(|^>>)> with \\>, we have

>\\

>>. <\proof> Let be maximal such that \