Transcendental Roots

Adam Strzebonski

Wolfram Research Inc.
100 Trade Centre Dr.
Champaign, IL 61820
U.S.A.

Representation of polynomial roots

Linear equations can be solved without introducing any additional functions.

Reduce[2 x+(3/7)==0,x]

To express solutions of polynomial equations with degrees ≤ 4 we need two additional functions

Reduce[(x^2)+2 x+3==0,x]

Reduce[(x^4)+2 x+3==0,x,Quartics->True]//First

To solve arbitrary polynomial equations we need to introduce an infinite family of functions

or equivalently

Reduce[(x^5)+2 x+5==0,x]

Representation of transcendental function roots

A locally holomorphic fuction has a countable number of roots, so in principle we could use a representation for roots of transcendental functions which would be very similar to what we have in the polynomial case

The problem with this approach is that we have no natural canonical way of assigning indices to roots of transcendental functions, and in most cases we can only find roots in bounded regions. For this reason our representation uses approximations to identify roots. An approximate number represents a circle in the complex plane (or a real interval). Such representation of an exact root of f is valid if we can prove there is exactly one root of f in the region corresponding to the given approximate number.

Root[{f, a}] represents the root of the univariate pure function f in the region represented by the approximate number a. f has been proven to have exactly one simple root in the region represented by a.

Laplace limit constant.

Reduce[((x Exp[(Sqrt[1+(x^2)])])/(1+(Sqrt[1+(x^2)])))-1==0,x,Reals]

r=%[[2]]

A transcendental root object represents an exact quantity. We can compute arbitrary precision approximations.

Precision[r]

We can compute arbitrary precision approximations of r.

N[r,100]

Unlike for algebraic numbers, there is no canonical form for numbers represented by transcendental root objects. Nevertheless some exact simplifications of expressions involving transcendental root objects can be done using FullSimplify.

((x Exp[(Sqrt[1+(x^2)])])/(1+(Sqrt[1+(x^2)])))/.x->r

FullSimplify[%]

Exp-log functions

For exp-log functions, i.e. arbitrary compositions of Plus, Times, Power and Log we have a complete real root isolation algorithm. It allows to find the real roots and the intervals on which the function is identically zero. The algorithm requires a zero testing procedure for constants. The known zero test procedure relies on Schanuel conjecture for termination. In Mathematica we implement a heursitic zero test. If it fails to prove that a constant which numerically seems to be zero is indeed zero, it may give a message about some expressions being assumed to be zero.

Exp-log function examples (Gruntz)

Reduce[(E^x) ((E^(-(E^(-x))+(1/x)))-(E^(1/x)))+5==0,x,Reals]

Reduce[(E^(-(E^(E^x))+(E^(E^((E^(-x))+x)))))-(10^67)==0,x,Reals]

Reduce[((((3^x)+(5^x)))^(1/x))-10==0,x,Reals]

Reduce[(E^(-x+(x/((E^x) ((E^(-x))+(E^(-((2 (x^2))/(1+x)))))))))-(7/10)==0,x,Reals]

Exp-log function examples (MathWorld)

Smarandache constant

Reduce[(127^x)-(113^x)-1==0,x,Reals]

Fixed point of ArcCoth

fps=Reduce[ArcCoth[x]==x,x,Reals]

Show[{Plot[{ArcCoth[x],x},{x,-3,3}],Graphics[{Red,PointSize[Medium],Point[{x,x}]/.{ToRules[fps]}}]}]

Inflection points of Einstein's (Subscript[E, 1]) function

Einstein's (Subscript[E, 1]) function.

(Subscript[E, 1])=(((x^2) Exp[x])/(((Exp[x]-1))^2));

infl=Reduce[(∂_({x,2}))(Subscript[E, 1])==0,x,Reals]

Show[{Plot[(Subscript[E, 1]),{x,-5,5}],Graphics[{Red,PointSize[Medium],Point[{x,(Subscript[E, 1])}]/.{ToRules[infl]}}]}]

Intersection of Einstein's (Subscript[E, 4]) function with hyperbola

Einstein's (Subscript[E, 4]) function.

(Subscript[E, 4])=(x/(Exp[x]-1))-Log[1-Exp[-x]];

intp=Reduce[(Subscript[E, 4])==(1/x),x,Reals]

Show[{Plot[{(Subscript[E, 4]),1/x},{x,0,3}],Graphics[{Red,PointSize[Medium],Point[{x,(Subscript[E, 4])}]/.{ToRules[intp]}}]}]

Planck's radiation function

P=(15/((π^4) ((x^5) (Exp[(1/x)]-1))));

Maximum of P.

max=Reduce[(∂_x)P==0,x,Reals]

Inflection points of P.

infl=Reduce[(∂_({x,2}))P==0,x,Reals]

Show[{Plot[P,{x,0,1}],Graphics[{PointSize[Medium],{Red,Point[{x,P}]/.{ToRules[max]}},{Green,Point[{x,P}]/.{ToRules[infl]}}}]}]

Special exp-log functions

High degree sparse polynomial

Reduce[(x^1000000)-2 (x^777777)+3 (x^123456)-4 (x^54321)+5 (x^6789)-6 (x^555)+7 (x^100)-8 (x^21)+9 x-10==0,x,Reals]

Algebraic function involving high degree radicals

Reduce[2 (x^(123451/67890))-(x^2)+4 (Sqrt[x])-4 x-(9/8)==0,x,Reals]

Function involving non-rational real powers

Reduce[(x^π)-(x^(x^(Sqrt[2])))-(Sqrt[3]) x+(2^(1/3))==0,x,Reals]

Exp-log examples with many roots

{(Subscript[F, 1]),(Subscript[F, 2]),(Subscript[F, 3])}={Exp[ChebyshevT[7,x]]-Log[ChebyshevU[7,x]+10],Exp[ChebyshevT[10,x]]-Log[ChebyshevU[10,x]+10],Exp[ChebyshevT[10,x]]-9 Log[ChebyshevU[10,x]+10]-(x^2)+(389/20)};

Plot[Evaluate[{(Subscript[F, 1]),(Subscript[F, 2]),(Subscript[F, 3])}],{x,-1.1,1.1}]

Length[Reduce[#==0,x,Reals]]&/@{(Subscript[F, 1]),(Subscript[F, 2]),(Subscript[F, 3])}

Elementary functions over bounded intervals

If a function is differentiable on a closed and bounded interval and does not have multiple roots in the interval, we can find its roots using interval arithmetic methods. In Mathematica interval arithmetic is available for elementary functions.

Elementary functions over bounded intervals: examples

Kepler's equation

Reduce[x-((Sin[x])/2)==1&&0≤x≤2,x]

Smallest positive fixed points of elementary functions

TableForm[rr={Reduce[Cos[x]==x&&0<x<(π/2),x,Reals],Reduce[Cot[x]==x&&0<x<(π/2),x,Reals],Reduce[Csc[x]==x&&0<x<(π/2),x,Reals],Reduce[Tan[x]==x&&π<x<((3 π)/2),x,Reals],Reduce[Sec[x]==x&&((3 π)/2)<x<2 π,x,Reals],Reduce[ArcCos[x]==x&&0<x<1,x,Reals],Reduce[ArcCot[x]==x&&0<x<1,x,Reals],Reduce[ArcCsc[x]==x&&1<x<2,x,Reals]}]

Show[{Plot[Tooltip[{Cos[x],Csc[x],Cot[x],Tan[x],Sec[x],ArcCos[x],ArcCot[x],ArcCsc[x],x}],{x,0,7},PlotRange->{{0,7},{0,7}}],Graphics[{PointSize[Medium],Red,Point[{x,x}]/.{ToRules[Or@@rr]}}]},PlotRange->{{0,7},{0,7}},AspectRatio->Automatic]

A function involving trigs, arctrigs, exp and log.

f=Sin[Cos[x]]+(E^(1/(Log[x]+1)))+(1/2) ArcCos[(1/x)]-2;

rr=Reduce[f==0&&1<x<10,x]

Show[{Plot[f,{x,1,10}],Graphics[{PointSize[Medium],Red,Point[{x,f}]/.{ToRules[rr]}}]}]

Analytic functions in bounded regions

For arbitrary holomorphic functions we can find roots in bounded regions of the complex plane. There are three main components to this algorithm, and each of the three components may fail. First, we need to be able to count the number of roots in the region. For elementary functions we can do it in a provably correct way by using complex interval arithmetic to compute the winding number. For other functions we need to rely on correctness of numeric integration (in this case Reduce gives a warning message). Next, we need to find approximations of all roots in the region. This is done using FindRoot with starting points provided either by computational geometry or by the Kravanja-Van Barel algorithm. Finally, we need to validate the approximations. We use Neumaier's criterion with radius estimation based on Rouche's theorem. The criterion allows to prove that a given circle (represented by an approximate number) contains exactly a certain number of roots, multiplicities counted. Again, the criterion requires complex interval arithmetic, so the results are only provably correct for elementary functions. For other functions correctness depends on correctness of error bounds given by significance arithmetic (by default we use approximations with at least 30 digits of precision, so significance arithmetic is expected to give good error bounds). The algorithm fully succeeds if the number of validated roots, counted with multiplicities, equals the number of roots computed in the first step. If we find and validate some roots, but their number is less than the computed total number of roots or we failed to compute the total number of roots, Reduce gives a message and returns the roots it has found.

Analytic functions in bounded regions: examples

Elementary function equations over bounded complex regions.

Reduce[(((x+1))^(Sin[x]))==Cos[(x^2)-Tan[x]]+(I/2)&&0≤Re[x]≤1&&0≤Im[x]≤1,x]

The n-dimensional unit ball with maximal volume

The volume of an n-dimensional ball is equal to (((π^(n/2)) (R^n) )/(Γ((n/2)+1))). This illustrates how the volume of the n-dimensional unit ball changes with n.

vol[n_]:=((π^(n/2))/(Gamma[(n/2)+1]))
ListPlot[vol/@Range[20]]

Treating the volume as a function of a real parameter n, we can compute the maximum.

Maximize[{vol[n],1≤n≤20},n]

Extension: Periodic equations

Periodic analytic function equations over the reals.

Reduce[(E^(Sin[x]))-Cos[3 Sin[x]]==0,x,Reals]

An equation involving a holomorphic function with a purely imaginary period over a vertical stripe in the complex plane.

Reduce[AiryAi[(E^x)]==3 (E^(-x))+1&&0≤Re[x]≤1,x]

An equation involving a doubly-periodic locally holomorphic function over the complex plane. Reduce cannot prove completeness here, because the function has poles within each period region.

Reduce[JacobiCS[x,3]==1,x]

Extension: Multivariate real systems exp-log in the first variable

We can find the solution sets for multivariate systems that involve exp-log functions of the first variable and are polynomial in the remaining variables.

Reduce[(E^x) (y^3)+Log[x] y>3 x,{x,y},Reals]

Extension: Multivariate real systems bounded in the first variable

We can find the solution sets for multivariate systems that involve analytic transcendental functions of the first variable and are polynomial in the remaining variables, as long as the values of the first variable are bounded.

Reduce[Sin[x-Cos[x]] (y^3)-x==1&&(x^2)+(y^2)≤1,{x,y},Reals]

Reduce[Erf[x-Cos[x+1]] (y^2)-x y z==1&&(x^2)+(y^2)+(z^2)<2,{x,y,z},Reals]

Reduce[(y^4)-Gamma[x+2] y-y-3 ArcSin[(x/3)]>-2&&(1/2)<x<1,{x,y},Reals]