# Reverse search for rational function

Say we have two transcendental numbers, u and v. And u presumably can be obtained as a result of applying a rational function $Q$ with integer coefficients to v. Is it possible to find such rational function?

In other words we need to find two polynomials $P_1$ and $P_2$ with integer coefficients such that

$u=\frac{P_1(v)}{P_2(v)}$

-
You would want to include the restriction that $P_1$ and $P_2$ have no common factors. – J. M. Apr 30 '11 at 11:06
Yes, of course. I meant the simplest form of that function. – Anixx Apr 30 '11 at 11:08
If we find at leat one pair of polynomials we can cancel the common factors out of course so the task is ti find at least one such pair or the function Q directly. – Anixx Apr 30 '11 at 11:09
It looks as if even the case of $P_2=1$ is hard... – J. M. Apr 30 '11 at 11:12
How are you given $u$ and $v$? – Qiaochu Yuan Apr 30 '11 at 11:19

## 2 Answers

Let's ask a much simpler question: if we have two transcendental numbers, and their difference is a rational number, can we find that rational number? Seems to me it would depend a bit on what it means to "have" a transcendental number. For all we know, $\pi-e$ is rational. The more decimals we know in the expansions of $\pi$ and $e$, the better the lower bound we can put on the numerator and denominator of the rational, but how can we ever find the rational?

-

Let's write it as $P_1(v)u = P_2(v)$, or rather $$\sum \alpha_i v^i u - \sum \beta_i v^i = 0.$$ Now use an integer relation algorithm.

-
I'm sure Yuval knows this, but just for the record: these algorithms will either tell you there is no relation with small numbers (leaving open the possibility that there is a relation with bigger ones) or they will give a relation that works up to the accuracy to which you know $u$ and $v$ (but won't give a proof that the relation is exact). – Gerry Myerson May 1 '11 at 0:20