RadicalDenest[ ]: definition and examples ​
​Swastik Banerjee
This blogpost is about the new RadicalDenest function in the Wolfram Function Repository , developed with an aim to solve one of the most ancient and difficult task in symbolic computation, using the Wolfram Language: To denest an algebraic expression containing nested radicals.

Introduction:

An important issue in symbolic computation is the simplification of algebraic expressions.
In general, algebraic manipulations are very difficult for computers to perform like we humans do. Much of it is because, the way we manipulate algebraic expressions come more from mathematical 'experience' in handling equations and expressions than from any particular set of algorithms that we always tend to follow. However, as developers of computer algebraic systems, we have always tried to automate these mathematical manipulations and operations in pursuit of having a model that can possibly think and work like a mathematician in flesh and blood, starting from Automated Theorem Prover to many more.
​
In this post we consider a function developed recently using the Wolfram Language for the simplification of algebraic expressions containing nested radicals.
​
Dealing with radicals has a long history in mathematics. For example, Galois Theory emerged from the problem of solving polynomials by radicals. It seems that in Computer Science people first got interested in radicals by their connection to the bit complexity of certain optimization problems such as the Traveling Salesman Problem (TSP) or the Shortest Path Problem (SPP).​
Throughout the last years this problem has been studied intensively by various mathematicians and computer scientists. Many of them have been attracted by equations of Ramanujan such as the following:
3
3
2
-1
=
3
1
9
-
3
2
9
+
3
4
9
3
5
-
3
4
=
1
3

3
2
+
3
20
-
3
25

6
7
3
20
-19
=
3
5
3
-
3
2
3
​
These examples sufficiently explain the problem itself, naturally begging the question of whether there is a systematic algorithm that can be used to denest radical expressions of arbitrary complexity.
This is still an open question and a subject of current research.

Why denest radicals?

Discovering the relations given in the examples above is an interesting mathematical challenge, but why should a computer algebra system devote computing resources to denesting problems?
◼
  • The first reason is simplicity. Users of any computer algebraic system, like all mathematicians, prefer to see their results expressed in `simplest' form.
    • ◼
  • Another reason for denesting is reliable simplification . For both people and computers, there is a danger that the result of a mathematical simplification will depend upon the order in which rules are applied. For example, the simplification of
    
    2
    1-√2
    can proceed two ways. The first way is called `top-down’ by those who think of the expression as a tree, and `outside to middle’ by those who look at the printed form. Following this procedure, one applies first the rule
    
    2
    x
    =|x|
    for any real x , and obtains
    
    2
    1-√2
    =√2-1
    . The other way is `bottom-up’ or`middle outwards’, in which one expands the square and obtains
    3-2√2
    ) . Without denesting, the simplification will not proceed any further. Thus two people using the same computer algebraic system to solve the same problem could arrive at apparently different answers, and this is what we wish to avoid.
    • ◼
  • A final reason is a small improvement in the accuracy of the numerical evaluation of some radical expressions. For example, the quantity
    √199999-600√111110
    is approximately equal to 0.00158, which approximates to zero if 10 decimal digits of precision are used, and only at 15 digits is the expression found to be nonzero; in contrast, equivalent
    100√10-3√11111
    approximates to 0.00158 using just 7 digits of precision.
    • ​
    Bill Gosper
    , who is a regular user of Mathematica, had once written in a
    blog
    about limitations of our FullSimplify function in actually fully simplifying certain radicals. For example, the following radical does not denest to
    √3-√2
    using FullSimplify, whereas it actually should :
    FullSimplify
    5-2
    6
    
    Out[]=
    5-2
    6
    %√3-√2
    Out[]=
    True
    ​
    Denesting a radical expression means decreasing its nesting depth over a field F. In the last years a lot of progress has been made for the problem of denesting radicals. Landau showed how to compute a denesting for a nested radical whose nesting depth is just one off the optimal one. Horng and Huang achieved a minimal denesting and also showed how to solve a polynomial by a radical of minimum nesting depth, if it is solvable by radicals at all. However, in both cases the denestings are with respect to a field containing all roots of unity. These results cannot explain or compute the special form of Ramanujan' s examples above since in these examples no roots of unity are required.
    All of these motivated us to implement a new RadicalDenest function in the Wolfram Language in an attempt to develop the finest function in any currently existing computer algebraic system which tries to denest a radical as much as possible without getting stuck to do it in an indefinite amount of time.
    ​
    In this blogpost, we will see how our new
    RadicalDenest
    function in the Wolfram Function Repository can achieve some of these beautiful denestings heuristically that Ramanujan had showed almost 100 years back.
    ​Why heuristically?: Because there is no known general denesting algorithm that does not involve resulting expressions that use complex of unity.

    ResourceFunction[“RadicalDenest”]

    Our new
    RadicalDenest
    function tries to denest an expression containing nested radicals heuristically, bounded by a TimeConstraint (which can be set manually) for practical purposes.

    Examples:

    ResourceFunction["RadicalDenest"]
    3
    3
    2
    -1
    
    Out[]=
    1-
    1/3
    2
    +
    2/3
    2
    2/3
    3
    ResourceFunction["RadicalDenest"]
    3
    5
    -
    3
    4
    ​
    Out[]=
    1
    3
    (
    1/3
    2
    +
    2/3
    2
    1/3
    5
    -
    2/3
    5
    )
    ResourceFunction["RadicalDenest"]
    6
    7
    3
    20
    -19
    
    Out[]=
    1/3
    (1+
    2/3
    2
    1/3
    5
    -
    1/3
    2
    2/3
    5
    )
    In[]:=
    ResourceFunction["RadicalDenest"]
    65+6
    10
    -2
    14
    -2
    22
    -6
    35
    -6
    55
    +2
    77
    
    Out[]=
    2
    +3
    5
    -
    7
    -
    11
    ResourceFunction["RadicalDenest"]
    3
    14
    2
    +9
    5
    -
    721+228
    10
    ,TimeConstraint30
    Out[]=
    1/3
    (-19+14
    2
    +9
    5
    -6
    10
    )
    ​
    Please refer to the documentation of
    RadicalDenest
    to see many more interesting examples, options, possible issues, etc. of this function.

    Limitations:

    Though ResourceFunction[“RadicalDenest”] shows many new interesting denestings as shown in the documentation, the heuristic methods may still fail to find a denesting when one exists.

    Credits:

    Much of the work was done by Corey Ziegler and Bill Gosper, and Daniel Lichtblau of Wolfram Research. The current function implemented by Swastik Banerjee, Intern at Wolfram Research, adds time constraints to different heuristic approaches, compares the nesting degrees of the denested expressions obtained from each such approach and returns the best denesting possible.

    Keywords

    ◼
  • Radical denesting
    • ◼
  • Computer algebraic system
    • ◼
  • Symbolic computation
    • ◼
  • Algebraic simplification
    • ◼
  • Algebraic manipulation