30
$\begingroup$

Specifically, consider expressions involving integers, addition, multiplication, division, and nth roots for any positive integer n. Is there an algorithm that can determine whether such an expression is a rational number? If the expression is a rational number, is it possible to determine which rational number (e.g. test whether an expression is 0?

I've seen papers on denesting radicals, but I couldn't find anything on testing for rationality.

$\endgroup$
13
  • 10
    $\begingroup$ Beware that formally speaking, the question is ambiguous for such an expression as $\sqrt{7+\sqrt{4}}$. Indeed $\sqrt{4}$ might mean both $2$ and $-2$. Possibly you only allow only positive radicals, which removes the ambiguity, but restricts the scope since in this way you for instance miss roots of totally real cubic (irreducible rational) polynomials. $\endgroup$
    – YCor
    Oct 24, 2019 at 10:01
  • 6
    $\begingroup$ @YCor: Are you sure? As far as I know, for a positive real number $x$ the expression $\sqrt{x}$ denotes the positive square root, the negative one being denoted by $-\sqrt{x}$. $\endgroup$ Oct 24, 2019 at 13:00
  • 5
    $\begingroup$ @FrancescoPolizzi I wrote explicitly "formally speaking", and also explicitly mentioned that one can interpret radicals using positivity. As far as I know, the Cardan formulas for roots of cubic polynomials use radical signs for complex numbers. $\endgroup$
    – YCor
    Oct 24, 2019 at 13:02
  • 2
    $\begingroup$ Yes I know, the point of my comment is to request clarification, since the OP was sloppy about this point. My example was here to illustrate the difficulties occurring if radicals are not properly defined (as they are not only used for positive numbers), even if the example with square root of a positive number is a bit caricatural. $\endgroup$
    – YCor
    Oct 24, 2019 at 13:17
  • 3
    $\begingroup$ Here is an ambiguous example with complex numbers: $i+\sqrt{2i}$ $\endgroup$ Oct 24, 2019 at 21:03

5 Answers 5

21
$\begingroup$

I'm assuming that you stay within the field of real numbers. You can represent an algebraic real number $\alpha$ by its minimal polynomial $P_\alpha$ plus an additional data, such as the position of $\alpha$ in the set of real roots of $P_\alpha$ (I think there are more efficient encodings). In any case, the main point is that all the usual operations on real algebraic numbers, including real radicals, can be performed exactly using the previous description. In particular, given an expression involving nested real radicals, you can compute its minimal polynomial, and then just need to look whether this polynomial has degree 1.

One reference is the book of Bochnak, Coste and Roy, Real algebraic geometry (there may be other but I don't know them). The procedure I outlined here is a very special case of quantifier elimination over real closed fields (for the field of real algebraic numbers).

$\endgroup$
6
  • $\begingroup$ To quote from doc.sagemath.org/html/en/reference/number_fields/sage/rings/… "minpoly() Compute the minimal polynomial of this algebraic number." so I guess AA implements this functionality. $\endgroup$
    – Ville Salo
    Oct 24, 2019 at 11:16
  • $\begingroup$ @VilleSalo I didn't know this package. Do you know if this implementation allows to convert a nested expression into an absolute expression (meaning an irreducible polynomial plus a sufficiently precise approximation of the root)? Moreover, the doc says that conversion works only if the number is rational, and it's not clear to me whether they mean "is" or " is represented as". $\endgroup$ Oct 24, 2019 at 11:27
  • $\begingroup$ My experience is that it is pretty much an implementation of algebraic reals in both a very correct, and a very practical sense. But I have not studied its theory or exact promises, and have only done simple things with it (computing exact trajectories for some toral automorphisms). (So the answer to your question would be "is", is my best guess.) $\endgroup$
    – Ville Salo
    Oct 24, 2019 at 11:31
  • $\begingroup$ Let me retract that after reading "Algebraic numbers exist in one of the following forms". Any experts on CAS present? $\endgroup$
    – Ville Salo
    Oct 24, 2019 at 11:33
  • $\begingroup$ I see -- that's good to know in any case. The doc gives the example of the computation of the regular 34-gon, and they say that comparing the two algebraic numbers "is currently infinitely long". I don't know whether this means that the algorithm fails in this case. $\endgroup$ Oct 24, 2019 at 11:34
12
$\begingroup$

One possible algorithm (I fear that terribly slow) would be to produce all algebraic conjugates of your expression (substituting in every possible way each radical by all it's conjugates) and finding the polynomial $\prod (x-\alpha)$ were the product is extended to all the conjugates of your number. By the symmetric function theorem this should give a polynomial with rational coefficients and then you can find it's rational and real roots and check numerically if your expression is nearest to one of the rational roots than to any other root.

On the other hand in Cohen's Computational algebraic Number theory section 2.7.4, there is a very nice algorithm that can be used to find the minimal polynomial of an real or complex number $\alpha$, grossly simplified it finds the LLL-reduction of the matrix: $$ \begin{pmatrix} 1&0&\dots &0\\ 0 &1&\dots& 0\\ \vdots& & \ddots &\vdots\\ 0&0&\dots&1\\ \sqrt{N}\alpha^{n-1} & \sqrt{N}\alpha^{n-2}&\dots& \sqrt{N} \end{pmatrix} $$ For a suitable $N$ where $n$ is an upper bound of the expected degree of the relation. Usually the first column will give you a relation of the $\alpha^i$ with reasonably small coefficients which possibly has $\alpha$ as a root and then you can proceed as before. However I'm not sure if there is any guaranty of finding the poynomial. (This algorithm is implemented in the software Pari-Gp son you can check it downloading the program).

Here is an example taken from a note of Daniel Shanks: Incredible identities (A, B, C):

$$ \sqrt{5} + \sqrt{22+2\sqrt{5}} = \sqrt{11+2\sqrt{29}} + \sqrt{16-2\sqrt{29}+2\sqrt{55-10\sqrt{29}}} $$

both sides are equal to 7.381175940895657970987266875465130332 using algdep you find that the minimal polynomial of both sides is probably $$x^4-54x^2-40x+269$$ and you can check algebraically that both sides are actually roots of this polynomial.

$\endgroup$
4
  • 1
    $\begingroup$ Computing a polynomial vanishing at $\alpha$ is possible without too much effort, using resultants for sums/products, and the obvious substition for radicals. Using numerical evaluation as you say, you can even find the minimal polynomial at each step. Actually this method may be the best thing to do in practice. (But to be certain we need something like interval arithmetic, at least for the operations of sums/products/radicals.) $\endgroup$ Oct 24, 2019 at 20:50
  • 1
    $\begingroup$ Regarding Pari/GP, I guess that you mean the algdep command, which indeed works well. But since here we only need to guess whether $\alpha$ is rational, we can even use lindep (LLL with 2 vectors) $\endgroup$ Oct 24, 2019 at 20:52
  • $\begingroup$ @FrançoisBrunault you are right but in the case of value 0 you would use algdep(0,2) which is not very useful, I have added an example to clarify what I mean $\endgroup$ Oct 25, 2019 at 6:57
  • $\begingroup$ Why is the case of the value 0 different? In Pari/GP the command for detecting rationality is lindep([1,x]) which is a synonym for algdep(x,1). The case where x is a complex number very close to 0 is not different from the other ones. $\endgroup$ Oct 25, 2019 at 9:56
9
$\begingroup$

If you're only interested in a root of each radical, rather than the unique positive real root or another chosen root, then you only have to keep track at each step of the rational polynomial whose roots are all the possible values of that expression.

In this case, it's probably best to compute it inductively, inside-out. Given polynomials $f(x)$ and $g(x)$, we can find polynomials whose roots are the roots of $f$ plus the roots of $g$, the roots of $f$ times the roots of $g$, and so on for the other arithmetic operations. For radicals this process is particularly simply, as we just replace $f(x)$ with $f(x^n)$. At the end you have a rational polynomial and can test for rational roots.

I don't know the best way to compute each step. One possibility is to view it as a matrix problem, forming the companion matrices $M_f, M_g$ to $f$ and $g$, taking $M_f \otimes I + I \otimes M_g$ or $M_f \otimes M_g$, and calculating the characteristic polynomial.

Regardless, because this method involves manipulating polynomials with integer coefficients, it's probably best to handle it by working mod $p$ for many large $p$ and then using the Chinese remainder theorem.

If your expression has a simple form then there are many tricks which you can possibly do to check if it has a rational root. For instance if your whole expression is wrapped in a single radical which is then added, multiplied with, and divided by other numbers, then the final output is rational if and only if this radical is rational, and this radical is rational only if the term inside is rational, potentially allowing you to prove irrationality by considering only a smaller sub-expression.

$\endgroup$
7
$\begingroup$

An algorithm to check whether an expression $f$ involving nested radicals is 0 may be obtained from a general procedure to check whether a semialgebraic set is non-empty. Indeed, you may introduce new variables, to replace each radical $\sqrt{a}$ (or, in general $a^{1/n_a}$) with $\alpha$, with extra equation $\alpha^2=a$ (or, in more generality, for each $a^{1/n_a}$ the equation will be $\alpha^{n_a}=a$) and inequality $\alpha \geq 0$. This will convert $f$ into a multivariate polynomial, so you will end up with a system of polynomial equations and inequalities, which you will need to test for a solution (something known to be doable in polynomial time for fixed number of inequalities and variables).


EDIT: this way one can also solve the full problem in question, i.e. finding whether $f\in\mathbb{Q}$. To this end, we can, instead of the "converted" as above equation $f=0$ we can consider the equation $f=\alpha_0$, where $\alpha_0$ yet another variable. Then the procedure as above will produce a finite semialgberaic set, defined in terms of the variables $\alpha$ introduced while eliminating radicals, and $\alpha_0$. In particular, it will be possible to construct a univariate polynomial $p\in\mathbb{Z}[\alpha_0]$, so that the value of $f$ is one of the (real) roots of $p$. Thus the linear terms of the factorisation of $p$ over $\mathbb{Q}$ will either produce the rational value of $f$, or indication that it is not rational.

Details of these algorithms may be found in e.g. S.Basu, R.Pollack, M.-F.Roy's book Algorithms in Real Algebraic Geometry.

$\endgroup$
3
  • $\begingroup$ Can this procedure be generalized to determine whether the expression is rational (and if so, which rational it is)? $\endgroup$ Oct 25, 2019 at 20:30
  • $\begingroup$ @TimothyChow - yes, it can do this, see my EDIT above. $\endgroup$ Oct 27, 2019 at 22:21
  • $\begingroup$ This quantifier elimination over the reals has been implemented in QEPCAD usna.edu/CS/qepcadweb/B/QEPCAD.html and Redlog redlog.eu $\endgroup$ Dec 20, 2019 at 13:13
5
$\begingroup$

Yes, you can do so exactly, as long as you can express arbitrary rational numbers exactly.

One way of doing this (though probably not the most efficient one) is to explicitly construct a field extension $E$ (as a rational vector space) through iterative adjoining of roots of equations x^k-a. (This can be done e.g. using resultants, but is hard to get to work efficiently in larger cases.) In this extension you can express the radical expression (or one interpretation of the radical expression) exactly.

Then choose a basis of $E$ that has one rational basis vector (say $1$), then an element of $E$ is rational if its coefficients for all other basis vectors are zero.

To take the famous Daniel Shanks example given by Esteban Crespi, a polynomial for the field $E$ is $x^8-8x^7-196x^6+1208x^5+8742x^4-43224x^3-41476x^2+227880x+8609$. (I calculated this as iterated extension.)

Now, using GAP (not that it is the best tool for this, but its the one I know), we can construct the extension $E$:

gap> pol:=x^8-8*x^7-196*x^6+1208*x^5+8742*x^4-43224*x^3-41476*x^2+227880*x+8609;;
x^8-8*x^7-196*x^6+1208*x^5+8742*x^4-43224*x^3-41476*x^2+227880*x+8609
gap> e:=AlgebraicExtension(Rationals,pol);;
gap> x:=X(e,"x");; # define variable

Now we take roots of certain quadratic polynomials to get the various radical expressions (here a is a root of the degree 8 polynomial, we work in the basis $1,a,a^2,\ldots$).

gap> r5:=RootsOfUPol(x^2-5)[1]; # root 5
-609/61755136*a^7+2095/30877568*a^6+133959/61755136*a^5-26101/30877568*a^4-7625627/61755136*a^3+12216013/30877568*a^2+92459893/61755136*a-67326631/30877568
gap> r29:=RootsOfUPol(x^2-29)[1]; #root 29
20639/111931184*a^7-113083/111931184*a^6-290319/111931184*a^5+13886605/111931184*a^4+206942825/111931184*a^3-340055609/111931184*a^2-1241123913/111931184*a+556675495/111931184
gap> r22:=RootsOfUPol(x^2-(22+2*r5))[1]; # root of expression starting with 22
-312563/1790898944*a^7+843909/895449472*a^6+64760293/1790898944*a^5-101635911/895449472*a^4-3089942017/1790898944*a^3+2366180495/895449472*a^2+18967544655/1790898944*a-3396381133/895449472
gap> r11:=RootsOfUPol(x^2-(11+2*r29))[1]; # root of expression starting with 11
-318289/3581797888*a^7+1674531/3581797888*a^6+66219455/3581797888*a^5-200118013/3581797888*a^4-3175703931/3581797888*a^3+4847083105/3581797888*a^2+19761660493/3581797888*a-15977491783/3581797888
gap> r55:=RootsOfUPol(x^2-(55-10*r29))[1]; # root of expression starting with 55
-587121/3581797888*a^7+2690715/3581797888*a^6+125087039/3581797888*a^5-281976997/3581797888*a^4-6353565723/3581797888*a^3+4276345801/3581797888*a^2+54570779021/3581797888*a-1796485759/3581797888
gap> r16:=RootsOfUPol(x^2-(16-2*r29+2*r55))[1]; # root of expression starting with 16    -342159/3581797888*a^7+1944125/3581797888*a^6+71070753/3581797888*a^5-244253347/3581797888*a^4-3446466469/3581797888*a^3+6034696383/3581797888*a^2+23536102611/3581797888*a-5417921945/3581797888

Finally we can calculate left and right side and e.g. subtract.

gap> left:=r5+r22;
-20639/111931184*a^7+113083/111931184*a^6+4290319/111931184*a^5-13886605/111931184*a^4-206942825/111931184*a^3+340055609/111931184*a^2+1353055097/111931184*a-668606679/111931184
gap> right:=r11+r16;
-20639/111931184*a^7+113083/111931184*a^6+4290319/111931184*a^5-13886605/111931184*a^4-206942825/111931184*a^3+340055609/111931184*a^2+1353055097/111931184*a-668606679/111931184
gap> left-right;
!0

Thu everything works exactly, but even in this tiny example the coefficients are a mess, so this in not something to do by hand.

$\endgroup$
2
  • 1
    $\begingroup$ How do you know that the elements $r_5,r_{29}...$ you have defined are the positive roots? $\endgroup$ Oct 26, 2019 at 2:02
  • $\begingroup$ @FrançoisBrunault. I do not (respectively it does not make sense to ask this in this model). For the first two roots I can assume WLOG that they are positive since there are Galois automorphisms. What one could do is to calculate a suitable approximation of the root $a$ and then evaluate each root numerically to check which one is positive. $\endgroup$
    – ahulpke
    Oct 26, 2019 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.