Rationality test for a rational power of a rational

Question

It has been known since Pythagoras that 2^(1/2) is irrational. It is also obvious that 4^(1/2) is rational. There is also a fun proof that even the power of two irrational numbers can be rational.

Can you, in general, compute whether the power of two rational numbers is rational?

The reason I am asking, besides curiosity, is that the Fraction-type in Python always returns a float on exponentiation. If there is a quick way to tell if it could be accurately expressed as a fraction, the power function could conceivably only return floats when it has to.

EDIT: By popular demand, I changed 0.5 to 1/2 to make it clearer that it is a fraction and not a float.

Answer 1

We can do this much quicker than using prime factorization. Below I show how to reduce the problem to testing if an integer is a (specific) perfect power - i.e. an integer perfect power test.

Lemma $\ $ If $\rm\,R\,$ and $\,\rm K/N\:$ are rationals, $\rm\:K,N\in\mathbb Z,\ \gcd(K,N)=1,\,$ then $$\rm\:R^{K/N}\in\Bbb Q\iff R^{1/N}\in \mathbb Q\qquad$$

Proof $\ (\Rightarrow)\ $ If $\,\rm\color{#0a0}{R^{K/N}\in\Bbb Q},\,$ then by $\rm\:gcd(N,K) = 1\:$ we have a Bezout equation

$$\rm 1 = JN+I\:\!K\, \overset{\!\div\ N}\Rightarrow\ 1/N = J + IK/N\ \Rightarrow\ R^{1/N} =\ R^J(\color{#0a0}{R^{K/N}})^I \in \mathbb Q$$

$(\Leftarrow)\ \ \rm\:R^{1/N}\in \mathbb Q\ \Rightarrow\ R^{K/N} = (R^{1/N})^K\in \mathbb Q.\ \ \small\bf QED$

So we've reduced the problem to determining if $\rm\:R^{1/N} = A/B \in \mathbb Q.\,$ If so then $\rm\: R = A^N/B^N\:$ and $\rm\:gcd(A,B)=1\:$ $\Rightarrow$ $\rm\:gcd(A^N,B^N) = 1,\:$ by unique factorization or Euclid's Lemma. By uniqueness of reduced fractions, this is true iff the lowest-terms numerator and denominator of $\rm\:R\:$ are both $\rm\:N'th\:$ powers of integers.

So we reduce to the problem of checking if an integer is a perfect power. This can be done very quickly, even in the general case, see D. J. Bernstein, Detecting powers in almost linear time. 1997.

Answer 2

There is no really easy way to test if the result of a ** b with a and b being rational numbers is rational. The easiest way is to decompose a into its prime factorisation

a = p_0 ** k_0 * p_1 ** k_1 ... p_r ** k_r

with p_i being prime numbers and k_i being (signed) integers. The result of a ** b is rational if all k_i * b are integers again.

Answer 3

Hmmm, I think that your assertion that 4^0.5 is rational is arguable. Bear in mind that in floating-point arithmetic 0.5 represents a range of real numbers, all of whose closest representation in the chosen version of f-p is closer to 0.5 than to either of its neighbouring f-p numbers. Only one of the numbers in that range leads to a rational result for the calculation of 4^0.5.

It is perfectly reasonable for Python (or any other computer) to, given f-p input, provide f-p output.

Perhaps you should have written it is obvious that 4^(1/2) is rational ?

And I see that you already have an answer to your question so I'll stop now.

Answer 4

I'd say that the real answer here is as follows: You don't want to be recovering precision once you've lost it.

For example (as senderle points out) one such irrational^irrational = rational example would be e^ln(10) = 10. In such a case, you don't want to be working with floats; you want to be working with symbolic math, like a computer algebra system. You look up your rules for exponentiation, and do a search to determine that it simplifies.

---

If you really were forced to lose precision however and try to recover it, and wanted to in this strange context (irrational^irrational = rational), and you don't care about being 100% correct, you can do as follows:

1. calculate a**b = c
2. if c is "close to a rational", return that rational

I believe this is used in graphing calculators. Even python's Fraction library uses this technique as .limit_denominator(...). Specifically you say that you will return the "closest" rational, but slightly penalizing rationals which are "complicated" (e.g. number of digits) compared to the inputs (base and exponent). One such algorithm for the "best rational approximation" would use continued fractions, e.g. http://en.wikipedia.org/wiki/Continued_fraction#Best_rational_approximations (similar to how rational approximations of pi are computed); you could tweak this to penalize guesses which are complicated with respect to the base and exponent.

Thus, I personally would prefer to have the power to simplify mathematical expressions, rather than lose precision and have to recover it. =)