<\body> >>>|\>>|\>>>>>>||<\expand|make-title> differential diophantine approximation> Université Paris-Sud91405 Orsay CEDEXFrance> > <\abstract> Consider a class of constants built up from the rationals using the field operations and a certain number of transcendental functions like . A central problem in computer algebra is to test whether such a constant, which is represented by an expression, is zero. The simplest approach to the zero-test problem is to evaluate the constants up to a certain number of decimal digits. Modulo certain precautions, we will make it likely that this approach is actually a valid one. More precisely, one may for instance restrict oneself to certain subsets of expressions in order to avoid ``high precision fraud''. For such subsets, we will state witness conjectures, which propose reasonable lower bounds for non zero constants as a function of the minimal sizes of expressions that represent them. Unfortunately, such witness conjectures are extremely hard to prove, since they are really far reaching generalizations of results in diophantine approximations. Nevertheless, we will also discuss their counterparts for formal power series, which are more accessible. Zero-testing an important issue in mathematics and more specifically in computer algebra. Standard mathematical notation provides a way of representing many transcendental functions. However, trivial cases apart, this notation gives rise to the following problems: <\itemize> Expressions may not be defined: consider , or -e*e)>. Expressions may be ambiguous: what values should we take for )> or |>>? Expressions may be redundant: we have the functional equation <\expand|equation*> sin x+cos x=1, although x+cos x> and are different as expressions. Similarly, -|3>=(1+-)/.> The first two problems can usually be solved by restricting oneself to an appropriate setting. Remains the third and most difficult problem, which is known as the zero-test or zero-equivalence problem, since we are usually interested in expressions that represent functions in a ring. As a reflex, most mathematicians tend to deal with the zero-test problem by restricting their attention to expressions of a certain form and proving a structure theorem for such expressions. Some successes of this approach are the following: <\itemize> Computations in algebraic extensions of a field using Groebner basis techniques. In this case an element of the algebraic extension is represented uniquely by its reduction modulo the Groebner basis. The Risch structure theorem allows computations in differential field extensions by exponentials, logarithms, or integrals. This technique may be adapted to a few other cases . Richardson designed a zero-test for elementary constants (i.e. constants which may be defined implicitly using rational numbers, the field operations and exponentiation), which assumes Schanuel's conjecture , . More recently, Ecalle has proved several structure theorems for generalized polylogarithms and zeta functions. One may expect the design of fast algorithms for dealing with such functions on the basis of his results. However, it should be stressed that a structure theorem explicitly describes relations which hold for the class of expressions being considered. Such a theorem is much more powerful than a zero-test algorithm, which just provides a method to test whether a expression represents zero. It is therefore recommended to treat the zero-test problem independently from the problem of establishing a complete structure theorem. Indeed, we have just stressed that the zero-test problem is less ambitious, so it may be solved for larger classes of expressions. Secondly, even if a structure theorem exist, a special purpose zero-test may be more efficient than a zero-test derived from the theorem, which may be very complicated. Now engineers have a very simple solution to the zero-test problem for constants: evaluate the constant with double precision and test whether the result vanishes. The advantage of this method, which works most of the time, is that it is very fast. However, double precision is not always sufficient to ensure the correctness of the answers. This problem can not merely be solved by considering quadruple or higher fixed precisions. Instead, it rises an interesting theoretical question: what is the required precision of evaluation the size of the input expression in the zero-test. Now there are some well-known examples of small, but non-zero expressions, like *>-640320,> or >+e>>>-e>>-1.> Essentially, we conjecture that such examples always come down to the substitution of a very small number in a non-zero power series with high valuation. This is clear in the second example, but may necessitate some extra work in other cases. For other nice examples of ``high precision fraud'', we refer to . In order to develop reliable zero-tests, we thus have to search for a setting in which high precision fraud is impossible. In the case of exp-log constants, one possible approach is to limit the modules of certain subexpressions. In such a setting an expression like > might become invalid and need to be rewritten as \\10>, which increases its size. Then it is reasonable to expect that there exist bounds from below for the absolute values of non-zero constants as a function of the sizes of their representing expressions. Such ``witness conjectures'' were first stated in , and later by Richardson , who has also done some numerical computations which tend to confirm our expectations. In this paper, we study several possible formulations of witness conjectures and we consider more general transcendental functions, defined by differential equations and initial conditions. We will also discuss some analogue conjectures for formal power series, on which we some progress has already been made . Witness conjectures may be interpreted as far reaching generalizations of existing conjectures and results in diophantine approximation . Indeed, this theory is concerned with finding good rational approximations of real numbers , which is equivalent to minimizing <\expand|equation*> \|p*x-q\| for large >. More generally, diophantine approximation is concerned with minimizing for polynomials [X]>. In our case, we are interested in even more general expressions, which involve transcendental functions defined by differential equations and initial conditions. The theory of minimizing the absolute values of such more general expressions might therefore be baptized as ``differential diophantine approximation''. We finally want to stress the interest of our approach for transcendental number theory. One major problem in this area is that it is already very hard to just state something like a generalization of the Schanuel conjecture for more general transcendental functions. The reason of this difficulty is that this conjecture is a result of the ``structure theorem'' approach. In order to state such a generalization, one thus has to anticipate the structure theorems which hold in the more general setting. By contrast, our ``witness conjecture'' approach directly applies to more general settings and it is legitimate to hope that some of the tools developed in this context can also be applied elsewhere. Let > be the set of exp-log constant expressions, i.e. the expressions formed from using ,/,exp> and . We will denote by > the set of real numbers which can be represented by an expression in > and by > the real number represented by an expression >\>. We will denote by (>)> the size of an expression >\> (i.e. the number of nodes when interpreting the expression as a tree). Given a rational number 3>, we denote by > the set of all expressions >\>, such that \\|y\|\N> for all subexpressions >> of >>. In , we stated the first : <\conjecture> There exists a function > of one of the forms <\expand|enumerate-alpha> (\)=K*\>; (\)=K>,> where 1> depends on , such that e(\(>))>>.> for all >\> with 0>. Actually, we conjectured the -part and we remarked that the conjecture might even hold for smaller >, such as in the -part. We will call the -part a and the -part a . It is also possible to consider intermediate witness conjecture, by taking (\)=\>, for instance. In general, we call a weakness conjecture strong, if \(exp \)\\>, for some >, where > and > denote the -th iterates of and . In what follows, we will only state strong witness conjectures with linear witness functions, but it might turn out in the future that other witness functions are necessary. A slightly different setting was first considered (in a more general form) in . Given a rational number 1>, let > be the class of all expressions >> in >, such that for each subexpression >> of >> of the form >=exp >> we have N>, and such that for each subexpression >> of >> of the form >=log >> we have z\N>. <\conjecture> There exists a witness function of the form (\)=K*\>, where 1> depends on , and such that for all >\\ >, we either have or e(\(>))>>. It should be noticed that this conjecture holds for all as soon as it holds for a particular . Indeed, for \N> we may take >=\>. For \N> we may take >(\)=\(\N/N\*(\+K))> for some constant , since any with \|z\|\N> may be rewritten as <\expand|equation*> y=exp N/N\>>\ |\N/N\>exp N/N\>>. In a similar way, if with \z\1/N> or z\N>, then we may decompose *z,> where \(1/N,N)> and >, so that <\expand|equation*> y=k*log r+log z. Moreover, by selecting to be a fixed rational number of small size close to , we may bound by a fixed constant, which explains (). Obviously, conjecture is implied by conjecture . We do not know at present whether the inverse is also true. Yet another variant of conjecture is obtained by dropping the requirement on the arguments to logarithms. Using (), this variant can again be reduced to conjecture , but the witness function may change in a non linear way, since can no longer be bound from above by a fixed constant, but only by (\(>)))>. In , we have generalized the witness conjectures for exp-log constants to so called ``holonomic constants''. Such constants are formed from the rationals, using the field operations and holonomic functions (i.e. functions that satisfy a linear differential equation over [x]>). The approach actually easily generalizes to more general constants, which arise as values of differentially algebraic functions. Let \> be a certain field of constants and let be a function which is analytic in . We say that is differentially algebraic over with initial conditions in , if satisfies a differential equation <\expand|equation*> f=,f)|Q(f,\,f)>, with [F,\,F]> and where ,f(0)\> are such that <\expand|equation*> Q(f(0),\,f(0))\0. We will consider values of such functions in points >, such that is strictly smaller than the radius of convergence > of . We may now construct a huge class of constants as follows. We start with =>. Assuming that > has been constructed, we let > be the set of all possible values in elements of > of differentially algebraic functions over > with initial conditions in >. It can be shown that each > is a field, which contains >. Finally, we take =\\\\ >. Elements in > may be represented by expressions as follows. Let > be the smallest set of expressions such that <\itemize> |\>>\>. >+>,>->,>*>,>/>\> for all >,>\>. Let be a differentially algebraic function as above, such that ,f(0)> are represented by >,\,>\> and such that and are represented by expressions in [F,\,F]>. Given >\> with \>, the expression (>,>,>,\,>,>)\> then represents . From the expressiveness point of view, it is not really necessary to have special expressions for the field operations (if we take \>). However, we do need them in order to keep the sizes of expressions reasonably small. In order to state witness conjectures for constants in >, several approaches are possible. One approach, which will be developed in the section , is to restrict ones attention to representations by expressions in > of a special form, like we did in the case of exp-log constants. Another approach, which was introduced in , is to redefine the size of an expression in such a way that expressions like > have a large size. In the present setting, this comes down to defining the ``size'' >(>)> of an expression >\> as follows: <\itemize> If >=0> or >=1>, then >(>)=1>. If >=>+>,>=>->,>=>*>> or >=>/>>\ , then >(>)=\>(>)+\>(>)+1>. If >=\(>,>,>,\,>,>)>, then <\expand|equation*> \>(>)=\>(>)+\>(>)+log sup\|u\|>\|f(v)\|+1, where <\expand|equation*> \>(>)=\>(>)+\>(>)+\<\ rsup|\>(>)+\+\>(>)+1 and <\expand|equation*> \>(>)=\deg >>\\deg> >>\>(>,\,i>) and similarly for >(>)>. For example, in the case of the exponential function, we have =f> and , so that >(exp)=5> and >(exp >)=\>(>)+5+log (e+1)>. Hence, >(exp >)\\>(>)+5+\ \|u\|> for large . Because of the corrective term , an expression like > will therefore have a large size. <\conjecture> There exists a witness function (\)=K*\> with 1>, such that for all >\>, we either have or e(\>(>))>>. <\remark> It is easy to show by structural induction that we also have the upper bound <\expand|equation*> \|z\|\e(\>(>))> for all >\>, if the conjecture holds. Notice also that this bound holds independently from the conjecture, if we disallow expressions of the form >/>>. The second approach in order to state witness conjectures for > is to use the usual size function >, which is defined recursively as the corrected size function >> by omitting the corrective term sup\|u\|\ >\|f(v)\|+1>, but to restrict our attention to a subset of admissible expressions of >. Let \(0,1)> be a rational parameter. We recursively define the subset >> in a similar way as >, but each time that >\>> is of the form >=\(\ >,>,>,\,\ >,>)>, we require that \>, 0> for all \>, and \|\1> for each Taylor coefficient > of . We first claim that each constant in > may be represented by an expression in >>. This follows from the following two observations: <\itemize> The Taylor coefficients of any analytic function in satisfy a bound of the form \|\\*\>, with ,\\> (and > as close to > as we wish). If is also differentially algebraic over with initial conditions in , then so is *f(\*z)>. We may therefore assume without loss of generality that \|\1> for all when constructing constants in >. If we want to evaluate in a point with \>, then we may use analytic continuation: taking <\expand|equation*> g(z)=f\*>+z, satisfies a similar algebraic differential equation as , whose initial conditions correspond to evaluations of and its derivatives in *z)/\|z\|>. Assuming that we chose > sufficiently close to > in the first observation, and repeating the analytic continuation argument, we may finally evaluate in . We notice that the analytic continuation procedure in the second observation is very close to rewriting =e*\*e>, as we did before. <\conjecture> Let \(0,1)>. Then there exists a witness function (\)=K*\>, where 1> depends on >, and such that for all >\>>, we either have or e(\(>))>>. Because of the analytic continuation argument, conjecture holds for all \(0,1)> as soon as it holds for a particular >. It is not hard to see that conjecture is also implied by conjecture . Indeed, the coefficients of the Taylor series of in are all bounded by in module, so if >\>> and >\>>> represent the same number with \>, then (F,1,1,>)\>> and >\>> both represent > and we have (\(F,1,1,>))=\(>)+O(1)> as well as (exp >)=\(>)+O(1)>. Logarithms may be handled in a similar fashion. Let us now show that conjecture is implied by conjecture . Indeed, an analytic function , such that \|\1> for all , satisfies the bound <\expand|equation*> sup\>\|f(z)\|\>. Consequently, the corrective terms in the corrected sizes >(>)> of expressions >\>> are uniformly bounded. We conclude that >\ (>)=O(\(>))> for >\>>, which implies our claim. Actually, conjecture seems to be slightly stronger than conjecture . When using <\expand|equation*> log sup\*\|u\|>\|f(v)\|+1 as a corrective term for some rational \(0,1\ )> instead of the usual one, both conjectures are equivalent. Indeed, in this case we may normalize )=M*f(u*u/\)> and replace by )>, where is a good rational upper approximation of \\ *\|u\|>\|f(v)\|>. Performing this trick recursively in expressions in > of corrected size >>, we end up with expressions in >> of usual size =O(\>)>. Witness conjectures may also be stated for more general types of constants, such as <\itemize> Constants that arise as values of solutions to partial differential equations, whose boundary conditions recursively satisfy partial differential equations in less variables. Constants that arise during the process of accelero-summation of divergent solutions to algebraic differential equations, or as limits of such solutions in singular points, if these limits exist. This may for instance be done using the approach from section , but where the supremum in the corrective term for >(>)> is taken over a sector instead of a disk. Constants that arise as values of solutions to more general functional equations. Of course, one has to be much more careful in this setting, since it is much easier to construct examples of high-precision fraud in this setting, by considering equations such as <\expand|equation*> f(x)=+f(e) for \\ >. Consider the ring of formal power series over a field of characteristic zero. Let > be the smallest set of expressions >> that represent series C[[z]]>, such that <\itemize> >. >, for all C>. >+>,>->> and >*>> are in >, for all >,>\>. >>,exp >> and >)> are in > for all >\> with =0>. The set > of series represented by expressions in > is called the set of in . We will denote by the valuation of a series C[[z]]>. <\conjecture> There exists a constant 1>, such that for all >\>, we either have or K*\(>)>. We observe that the coefficients of > are polynomials with rational coefficients in the constants of which occur in a representing expression >\> of . Consequently, it suffices to check conjecture in the case when is the field of algebraic numbers. Let us now show that conjecture is implied by conjecture () in the case when >. Indeed, assume that there exists a counterexample >\> to conjecture for each with 0> and K*\(>)>. Then for > sufficiently large, we may represent )> by an expression in >> whose size is bounded by >*n*\(\ >)>. Moreover, since >> is a counterexample to conjecture , there exists a constant , such that )\0> and <\expand|equation*> \|f(e)\|\M*e(>)>\M*e>)**\()|\\ >)>. This yields a counterexample to conjecture (), for sufficiently large . The above argument suggests that, in order to prove numerical witness conjectures, it may be good to start proving their power series equivalents. Although this project seems still to be out of reach for linear witness functions, we were able to prove the following weak witness theorem ; this result is based on a careful complexity analysis of the zero-test algorithm from . <\theorem> For all >\>, we either have or \(\(>))<\ rsup|>>, with (\)=(4*\)>>>. Recently, we have been made aware of the work of Khovanskii , which seems to imply even better bounds of the form (\)=\*2<\ rsup|2>>>. We are still studying this work and trying to prove similar bounds with our techniques. Our main reason for doing this is that the techniques from are better suited for generalizations. Let > be a differential subring of . In analogy with section , we define a series C[[z]]> to be differentially algebraic over >, if satisfies an algebraic differential equation =,f)|Q(f,\,f)>,> with [F,\,F]> and where ,f(0)> are such that <\expand|equation*> Q(f(0),\,f(0))\0. Starting with \C>, we may again recursively construct > to be the ring of differentially algebraic power series over >, and define \\\\>. Power series in > may be represented in a similar way as in section and we have the following power series analogue of conjectures and . <\conjecture> There exists a witness function (\)=K*\> with 1>, such that for all >\>, we either have or \(>)>. In , we proved the above conjecture for (\)=(4*\)>>> in the case of differential equations () of order . We believe to have found a generalization of this theorem to higher orders, but this still has to be worked out in detail. In the first order case, better bounds of the form (\)=\*2<\ rsup|2>>> seem to result from . Actually, there is no reason to restrict ourselves to formal power series in one variable in sections and , so that we may very well replace by ,\,z\ ]]>. In the construction of >, given >\>, we then have to assume that ,0>=0>, for >)>, >)> or >>> to be in >. Similarly, the differential equation () should be replaced by a system of partial differential equations > f|\ z>=(f,\,\-1\ > f/\ z)|Q(f,\,\-1> f/\ z)>,> for ,k>, such that the polynomials ,Q> satisfy <\expand|equation*> Q(f(0,\,0),\,\-1> f/\ z(0,\,0))\0. One might also investigate other ways to present the partial differential equations (), such as coherent autoreduced systems. Now given such a multivariate setting, it is interesting to study the dependence of the witness conjectures on the parameter . The following result has been proved in ; better bounds might follow from . <\theorem> For all >\>, we either have or \(\<\ sigma\>(>))>, where (\)\ =(4*k*\)>>>. Technically speaking, it turns out that the exponential behavior in (>)> in theorem is due to the ``differential part'' of >>. More precisely, if we consider a non zero power series in a fixed polynomial ring ,\,g]> with ,\,g\>, then there exists a polynomial bound for in > f,\,deg> f}>. This observation seems to generalize to higher order differential power series. As a first step to the proofs of stronger witness conjectures for differential power series, it may therefore be a good idea to find more subtle size parameters for expressions in >, such as and above. It may also be interesting to consider other interesting classes of power series, such as rings of the form <\expand|equation*> C[z,e(*z)>,\,e(z)>], where ,\,P\C[z]>. Can the exponential bound in be further improved for such rings? It might also be interesting to do some computer algebra experiments for expressions of a simple form and small size. For instance, one might consider all expressions formed using , formal parameters ,\,\>, additional, multiplication and exponentiation of infinitesimals. Given a power series represented by such an expression, one may set the first coefficients to zero (this puts constraints on the parameters ,\,\>\ ) and study the number of remaining free parameters as a function of . Doing this for all expressions up to a certain size, one may collect concrete evidence for the witness conjectures and determine the ``worst case expressions''. Now we have stated different types of witness conjectures, it is interesting to investigate what is already known on this subject. Probably, the classical theory of diophantine approximation, which is concerned with the approximation of a given real number by rationals, comes closest to our subject. Equivalently, one may ask how small m\|> can get for large >. More generally, an interesting question is to know how small can get as a function of [X]\\{0}>. Even more generally, one may consider complex numbers ,\,z> and ask how small ,\,z)\|> can get as a function of [Z,\,Z]\\{0}>. Let us first consider an algebraic number , with for some polynomial [Z]> of minimal degree 2> and minimal leading coefficient >>. Let <\expand|equation*> P=c*(Z-\)*\*(Z-\) be the factorization of with > and \\> for all j>. Given > close to (say \|p/q-\\|> for all 1>), we then have <\expand|equation*> z-=P|c*\-*\*\ \->\*c*\-\*\\ *\-\*q>, since *P(p/q)\>>. This bound, which is due to Liouville, shows that \| can be bounded from below by an expression of the form /q>, where > can be expressed as a function of the polynomial (and actually as a function of its size). This seems to give some evidence for a strong witness conjecture for algebraic numbers. Actually, the above bound can be sharpened in an asymptotical way. Given a real number , let x\<\|\|\>> be the distance between and the closest point in . The following theorem is due to Roth , based on previous work by Schneider . <\theorem> Given an algebraic irrational number and \0>, there are only a finite number of solutions to the inequality q*x\<\|\|\>\1/q>>, for >>. Unfortunately, asymptotic bounds are not really suited for establishing witness theorems, because such theorems do not accommodate exceptions, even if finite in number. Nevertheless, they contribute to the likeliness of witness conjectures. Another, very general, probabilistic and asymptotic result is the following : <\theorem> Let > be a positive function, such that >\(q)> converges. Then for almost all numbers (for the Lebesgue measure), the equation q*x\<\|\|\>\\(x)> admits only a finite number of solutions. We refer to for a more detailed survey on diophantine approximation and in particular on the diophantine approximation of transcendental constants like , logarithms and exponentials of algebraic numbers and so on. Unfortunately, the scope of the actual theory is very limited from our point of view, since it lacks effectiveness and no general results exist for, say, the exp-log constants. In the light of witness conjectures, there is no good reason to restrict oneself to the approximation of transcendental constants by rational or algebraic numbers. On the contrary, we might consider the approximation by more general constants, like exp-log constants or differentially algebraic constants. Equivalently, given complex numbers ,\,z> and a class of multivariate analytic functions >, one might be interested in lower bounds for ,\,z)\|> as a function of the size of an expression which represents >. Several classical questions in diophantine approximations have natural analogues. For instance, is there an analogue of theorem ? We expect this to be so, since we will usually only consider countable sets of constants. Similarly, one may search for analogues of asymptotic results like theorem . It would also be interesting to have effective analogues for continued fraction expansions. By preference, such expansions should have more structure than the successive approximations found by, say, the LLL-algorithm . Finally, it is worth it to investigate the power series counterpart of differential diophantine approximation. In this context, there is a need for transfer principles back to the numeric setting. Of course, such transfer principles would also be useful for proving witness conjectures or designing zero-tests for constants. In the case of zero-tests, one might for instance wonder how to represent a constant which is suspected to be zero by the value of a function which can be proved to vanish globally. The main application of witness conjectures is zero-testing. However, it is not recommended to directly apply the witness conjectures in all circumstances. For instance, if we want to test whether the expression () from the introduction vanishes, then conjecture would give a very bad bound for the number of digits that we need to evaluate. Nevertheless, using asymptotic expansion techniques, it is easy to detect that () does not vanish. In this section, we briefly discuss two zero-test algorithms which only indirectly rely on witness conjectures. In both cases, the witness conjectures enable us to obtain reasonable complexity bounds for such zero-tests, something which is impossible for algorithms that rely on structure theorems . We should also mention that it is not necessary to wait for proofs of the witness conjecture in order to base zero-test algorithms on them. Indeed, since most general purpose zero-tests implemented so far are either based on non reliable heuristic or are limited to relatively small classes of constants, we think that the mere statement of a precise conjecture already forms a progress, since such a conjecture can be used as a reliable and efficient heuristic. In , we considered linear combinations of the form *e>+\+c*e>\ ,> where ,\,c,z,\,z> are ``holonomic constants''. Such expressions naturally occur when computing with solutions to linear differential equations near singularities. We proved a theorem, which implies the following one for ``sufficiently regular'' witness functions >: <\theorem> Assume conjecture . Then we may test whether )> vanishes in a time bounded by <\expand|equation*> (\*log \*log log \)\(C*r*\(\))r> for some constant 0>, and where ,\,c,z,\,z> can be represented by expressions of size \>. The following points should be noticed about this result: <\itemize> The left composition with *log \*log log \> is due to the cost of the evaluation of () up to (\))r>> digits. If the class of holonomic constants is replaced by a larger one, such as >>, then one should rather compose on the left by *log \*log log \>. There is a big difference between strong and weak witness conjectures as to the behavior of the -th iterate of (\)>. Indeed, if (\)> has exponentiality zero in >, then so has its -th iterate (see for a definition of exponentiality; examples of such functions are (\)=K*\>, (\)=\> or (\)=e \>>). Moreover, the growth of (\))r>> in is bounded by an iterated exponential in this case. On the other hand, as soon as > has exponentiality 0>>, the -th iterate of (\)\ > has an extremely bad behavior for large , since it is not longer bounded by any iterated exponential. It is therefore of the to prove witness conjectures for witness functions of exponentiality ; unfortunately, even in the power series setting, the existing techniques do not allow us to do so. In we described the first efficient zero-test for real exp-log constants. At the time, we were not able to give any complexity bound for our algorithm, and this was one of our main motivation for the statement of witness conjectures. Using the more powerful asymptotic expansion algorithms from , which rely on Cartesian representations, and the more powerful zero-tests for multivariate exp-log series from , we also designed a more efficient zero-test for real exp-log constants in collaboration with J. Shackell. This algorithm, which will be detailed in a forthcoming paper, is expected to satisfy a similar complexity bound as in theorem in the sense that it again involves an iterate of the witness function >. <\bibliography|bib|alpha|zerotest.bib> J. Ax. On Schanuel's conjecture. , 93:252--268, 1971. J.M. Borwein and P.B. Borwein. Strange series and high precision fraud. , 99:622--640, 1992. J. Écalle. . Hermann, collection: Actualités mathématiques, 1992. A. Ya. Khinchin. . Fizmatgiz, Moscow, 1961. English transl., Univ. of Chicago Press, Chicago, Ill., 1964, MR 28 #5037. A. G. Khovanskii. . American Mathematical Society, Providence, RI, 1991. S. Lang. Transcendental numbers and diophantine approximation. , 77/5:635--677, 1971. A.K. Lenstra, H.W. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. , 261:515--534, 1982. D. Richardson. How to recognise zero. , 24(6):627--646, 1994. D. Richardson. The uniformity conjecture. In , volume 2064, pages 253--272. Springer Verlag, 2001. R.H. Risch. Algebraic properties of elementary functions in analysis. , 4(101):743--759, 1975. K. Roth. Rational approximations to algebraic numbers. , 2:1--20, 1955. Corrigendum, 168, MR 17, 242. T. Schneider. Über die approximation algebraischer zahlen. , 175:110--128, 1936. J.R. Shackell. A differential-equations approach to functional equivalence. In G. Gonnet, editor, , pages 7--10, Portland, Oregon, 1989. A.C.M. Press. M.F. Singer, B.D. Saunders, and B.F. Caviness. An extension of Liouville's theorem on integration in finite terms. , 14:966--990, 1985. J.R. Shackell and J. van der Hoeven. Complexity bounds for zero-test algorithms. Technical Report 2001-63, Prépublications d'Orsay, 2001. J. van der Hoeven. Automatic numerical expansions. In J.-C. Bajard, D. Michelucci, J.-M. Moreau, and J.-M. Müller, editors, , pages 261--274, 1995. J. van der Hoeven. . PhD thesis, École Polytechnique, Laboratoire d'Informatique, École Polytechnique, Paris, France, 1997. J. van der Hoeven. Fast evaluation of holonomic functions near and in singularities. , 31:717--743, 2001. <\initial> <\collection> <\references> <\collection> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > <\auxiliary> <\collection> <\associate|bib> Ris75 SSC85 Richardson94a Ax71 BB92 vdHoeven97 vdH:singhol Rich01 Khov91 ShVdH01 Lang71 vdHoeven97 vdH:singhol vdH:singhol vdH:singhol Ec92 ShVdH01 Sh3 Khov91 ShVdH01 ShVdH01 Khov91 ShVdH01 Khov91 Roth55 Schn36 Khin61 Lang71 LLL82 Richardson94a vdH:singhol vdHoeven97 vdH:ane vdHoeven97 ShVdH01 <\associate|toc> |1Introduction><\ value|toc-dots> |2Witness conjectures for constants> 2.1Exp-log constants 2.2Values of differentially algebraic functions 2.3Corrected size functions 2.4Admissible expressions 2.5More general constants |3Witness conjectures for power series> 3.1Exp-log series 3.2Differentially algebraic series 3.3Multivariate series 3.4Finer size parameters |4Differential diophantine approximation> 4.1Classical results in diophantine approximation 4.2Differential diophantine approximation |5Applications that rely on witness conjectures> 5.1Linear combinations of exponentials 5.2Exp-log constants |Bibliography>