solving the x's and y's of math, programming and life

GSoC Week 3

Jun 25, 2017 • Gaurav Dhingra

Risch’s structure theorem’s

For the next couple of weeks we will be moving to understand and implement the Risch’s structure theorem and applications that we will make use of in gsoc project. One of the application is that of “Simplification of real elementary functions”, a paper by Manuel Bronstein (in 1989)[1]. This paper by Bronstein uses Risch’s real structure theorem, the paper determines explicitly all algebraic relations among a set of real elementary functions.

Simplification of Real Elementary Functions

Risch in 1979 gave a theorem and an algorithm that found explicitly all algebraic relations among a set of only \(\log\)’s and \(\exp\)’s. And to apply this algorithm required to convert trigonometric functions to \(\log\)’s and \(\exp\)’s.

Consider the integrand \(f = \frac{\tan ^2(\arctan(x)/3) + 1}{x^2 + 1}\). For this first we make use of \(\log\) form of \(\arctan\), i.e \(\arctan(x) = \frac{1}{2I} \log(\frac{1 + Ix}{1 - Ix})\). Substituting it in the original expression we get \(\frac{\sec^2 (\frac{1}{6I} \log(\frac{1 + Ix}{1 - Ix}))}{x^2 + 1}\). Now using the exponential form of \(\sec\) we get \(\frac{4}{x^2 + 1} (\frac{1}{[(\frac{1 + Ix}{1 - Ix})^{1/6} + (\frac{1 + Ix}{1 - Ix})^{-1/6}]})^2\). And substituting \(\sqrt \alpha\) in place of \((\frac{1 + Ix}{1 - Ix})^{1/6}\) we get the final expression. \(f = \frac{4 \alpha}{(x^2 + 1)(\alpha + 1)^2}\), which is a complex algebraic function.

All of this could be avoided since the original function \(f = \frac{\tan ^2(\arctan(x)/3) + 1}{x^2 + 1}\) is a real algebraic function. The part that could be a problem to see it is \(\tan(\arctan(x)/3)\), which can be seen to satisfy the algebraic equation \(y^3 - 3y^2 x - 3y + x = 0\) using the formula for \(\tan(3\theta)\). Bronstein discusses the algorithm that wouldn’t require the use of complex \(\log\)’s and \(\exp\)’s.

A function \(\theta\) is called real elementary over a differential field \(k\), if for a differential extension \(K\) (\(\theta \in K\)) of \(k\). If either \(\theta\) is algebraic over \(k\) or it is \(\exp\), \(\log\), \(\tan\), \(\arctan\) of an element of \(k\) (consider this recursively). For example: \(\log(x)\) is real elementary over \(\mathbb{Q}(x)\), so is \(\log(\log(x))\) and \(\log(\exp(x) + \tan(x))\).

Point to mention here is, we have to explicitly include \(\tan\), \(\arctan\), since we don’t want the function to be a complex function by re-writing \(\tan(x)\) as \(\log\), \(\exp\) form(\(\tan\) and \(\arctan\) can be written in form of complex \(\log\) and \(\exp\) respectively), and we can write other trigonometric functions have real elementary relations with \(\tan\) and \(\arctan\). Alone \(\tan\) or alone \(\arctan\) can’t do the job.

This way we can form the definition of a real-elementary extension of a differential field \(k\).

Functions currently using approach of structure theorems in SymPy

Moving on, let us now look at the three functions in SymPy that use the structure theorem “approach”:

  1. is_log_deriv_k_t_radical(fa, fd, DE): Checks if \(Df\) is the logarithmic derivative of a k(t)-radical. Mathematically \(Df = \frac{1}{n} \frac{Da}{a}\) where \(a \in k\), \(n \in \mathbb{Z}\). In naive terms if \(f = \log(\sqrt[n]{a}) \Rightarrow Df = \frac{1}{n} \frac{Da}{a}\). Here k(t)-radical means n-th roots of element of \(k\). Used in process of calculating DifferentialExtension of an object where ‘case’ is ‘exp’.

  2. is_log_deriv_k_t_radical_in_field(fa, fd, DE): Checks if \(f\) is the logarithmic derivative of a k(t)-radical. Mathematically \(f = \frac{1}{n} \frac{Da}{a}\) where \(a \in k\), \(n \in \mathbb{Z}\). It may seem like it is just the same as above with f given as input instead of having to calculate \(Df\), but the “in_field” part in function name is important.

  3. is_deriv_k: Checks if \(Df/f\) is the derivative of a k(t), i.e. \(Df/f = Db\) where \(b \in k(t) \Rightarrow \log(f) = b\).

What have I done this week?

Moving onto what I have been doing for the last few days (at a very slow pace) went through a debugger for understanding the working of DifferentialExtension(exp(x**2/2) + exp(x**2), x) in which integer_powers function is currently used to determine the relation \(t_{0} = \exp(x^2/2)\) and \(t_{0}^2 = \exp(x^2)\), instead of \(t_{0} = \exp(x^2)\) and \(\sqrt {t_{0}} = \exp(x^2/2)\), since we can’t handle algebraic extensions currently (that will hopefully come later in my gsoc project). Similar example for \(\log\) is there in the book \(f = \log(x) \log(x + 1) \log(2x^2 + 2x)\), though the difference is it uses the is_deriv_k (for case == 'primitive', we have is_log_deriv_k_t_radical for case == ‘exp’) to reach the conclusion that \(t_{0} = \log(x)\), \(t_{1} = \log(x + 1)\) and \(\log(2x^2 + 2 x) = t_0 + t_1 + \log(2)\).

I still have to understand the structure theorem, for what they are? and how exactly they are used. According to Aaron, Kalevi, I should start reading the source of is_deriv_k, is_log_deriv_k_t_radical and parametric_log_deriv functions in prde.py file.

We worked on #12743 Liouvillian case for Parametric Risch Diff Eq. this week, it handles liouvillian cancellation cases. It enables us to handle integrands like \(f = \log(\frac{x}{\exp(x)} + 1)\).

>>> risch_integrate(log(x/exp(x) + 1), x)
(x*log(x*exp(-x) + 1) + NonElementaryIntegral((x**2 - x)/(x + exp(x)), x))

earlier it used to raise error prde_cancel() not implemented. After testing it a bit I realised that part of returned answer could be further integrated instead of being returned as a NonElementaryIntegral. Consider this

In [4]: risch_integrate(x + exp(x**2), x)
Out[4]: Integral(x + exp(x**2), x)

as can be easily seen it can be further integrated. So Aaron opened the issue #12779 Risch algorithm could split out more nonelementary cases.

Though I am not sure why Kalevi has still not merged the liouvillian PR (only a comment needs to be fixed n=2 -> n=5 in a comment), though that PR is not blocking me from doing further work.

Starting tomorrow (26th) we have the first evaluation of GSoC. Anyways I don’t like the idea of having 3 evaluations.

TODO for the next week:

Figuring out and implementing the structure theorems.

References

  • {1}. Simplification of real elementary functions, http://dl.acm.org/citation.cfm?id=74566