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.
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).
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.
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.
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.
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.
