Rational Function Reconstruction

Let $ {\bf k}$ be a field, let $ m \in {\bf k}[x]$ be a polynomial of degree $ n > 0$ . Given a polynomial $ f \in {\bf k}[x]$ of degree less than $ n$ and an integer $ d \in \{1, \ldots, n\}$ , we want to find a rational function $ r/t \in {\bf k}(x)$ with $ r,t \in {\bf k}[x]$ satisfying

$\displaystyle {\gcd}(t,m) = 1 \ \ {\rm and} \ \ r t^{-1} \equiv f \mod{m}, \ \ {\deg} r < d, \ \ {\deg} t \leq n - d.$ (86)

Let us denote this problem by $ RFR(m, n, f, d)$ . A solution to this problem is also a solution to the following weaker problem: compute a rational function $ r/t \in {\bf k}(x)$ with $ r,t \in {\bf k}[x]$ satisfying

$\displaystyle r \equiv t f \mod{m}, \ \ {\deg} r < d, \ \ {\deg} t \leq n - d.$ (87)

We denote this second problem by $ WRFR(m, n, f, d)$ .

We recall that a rational function $ r/t \in {\bf k}(x)$ is said to be in canonical form if $ t$ is monic and if $ {\gcd}(r,t) = 1$ . Clearly, every rational function has a unique canonical form.

The following Theorem 5:

As a result, we obtain an algorithm for solving both problems $ WRFR(m, n, f, d)$ and $ RFR(m, n, f, d)$ .

Theorem 5   Let $ r_j, s_j, t_j \in {\bf k}[x]$ be the $ j$ -th row of the Extended Euclidean Algorithm applied to $ (a,b ) = (m, f)$ where $ j$ is minimal such that $ {\deg} r_j < d$ .
$ (i)$
The couple $ (r, t) = (r_j, t_j)$ is a solution to problem $ WRFR(m, n, f, d)$ .
$ (ii)$
If $ {\gcd}(r_j, t_j) = 1$ , then the couple $ (r, t) = (r_j, t_j)$ is a solution to problem $ RFR(m, n, f, d)$ .
$ (iii)$
If $ (r,t)$ is a solution to problem $ RFR(m, n, f, d)$ and if $ r/t$ is a canonical form, then we have $ (r, t) = (w_j^{-1} r_j, w_j^{-1}t_j)$ where $ w_j = {\rm lc}(t_j)$ .
$ (iv)$
Problem $ RFR(m, n, f, d)$ admits a solution if and only if $ {\gcd}(r_j, t_j) = 1$ .

Proof. First, we observe that $ r_j, s_j, t_j$ are uniquely defined. Indeed, we have $ 1 \leq d \leq n$ and,

$\displaystyle - \infty = {\deg} r_{k+1} < {\deg} r_k < \cdots < {\deg} r_{i+1} < {\deg} r_{i} < \cdots < {\deg} a = n.$ (88)

Hence, there exists a unique $ j \in \{1, \dots, k+1\}$ such that we have

$\displaystyle {\deg} r_j < d \leq {\deg} r_{j-1}.$ (89)

From Point $ (iv)$ of Proposition 1 we have

$\displaystyle r_j = s_j m + t_j f$ (90)

leading to $ r_j \equiv t_j f \mod{m}$ . From Proposition 2, we deduce

$\displaystyle {\deg} t_j = {\deg} m - {\deg} r_{j-1} \leq n - d.$ (91)

Since $ {\deg} r_j < d$ holds, we have proved that $ (r_j, t_j)$ is a solution to problem $ WRFR(m, n, f, d)$ . This shows $ (i)$ . Now, we prove $ (ii)$ . We assume that $ {\gcd}(r_j, t_j) = 1$ holds. From Point $ (vii)$ of Proposition 1 we have

$\displaystyle {\gcd}(m, t_j) = {\gcd}(r_j,t_j) = 1.$ (92)

This implies that $ t_j$ is invertible modulo $ m$ , leading to $ r t^{-1} \equiv f \mod{m}$ . Hence, under the assumption $ {\gcd}(r_j, t_j) = 1$ , the couple $ (r_j, t_j)$ is also a solution to $ RFR(m, n, f, d)$ .

Next, we prove $ (iii)$ . So we consider $ (r,t)$ a solution to $ RFR(m, n, f, d)$ such that the fraction $ r/t$ is in canonical form. There exists $ s \in {\bf k}[x]$ such that we have $ r = s m + t f$ . Since $ {\deg} r + {\deg} t < {\deg} m$ holds, we can apply Proposition 3. So, let $ {\ell} \in \{ 1, \ldots, k + 1 \}$ be such that

$\displaystyle {\deg} r_{\ell} \leq {\deg} r < {\deg} r_{{\ell}-1}.$ (93)

Then, there exists $ {\alpha} \in {\bf k}[x]$ such that $ r = {\alpha} r_{\ell}$ and $ t = {\alpha} t_{\ell}$ both hold.

If $ {\deg} r_j \leq {\deg} r$ then we have $ {\ell} = j$ . If $ {\deg} r < {\deg} r_j$ then we have $ {\ell} > j$ .

We prove that $ {\ell} = j$ holds. If $ t = t_j$ then $ r - r_j \equiv 0 \mod{m}$ , and thus $ r = r_j$ , since $ {\deg}(r - r_j) < n$ holds, which implies $ {\ell} = j$ . If $ t \neq t_j$ , we can apply Proposition 3 again. Then, there exists $ {\beta} \in {\bf k}[x]$ such that $ r - r_j = {\beta} r_{\ell}$ and $ t - t_j = {\beta} t_{\ell}$ both hold. It follows that we have $ r_j = ({\alpha} - {\beta}) r_{\ell}$ and $ t_j = ({\alpha} - {\beta}) t_{\ell}$ . Hence, we deduce

$\displaystyle m s_j = r_j - t_j f = ({\alpha} - {\beta}) m s_{\ell}$ (94)

leading to $ s_j = ({\alpha} - {\beta}) s_{\ell}$ . Since $ {\gcd}(s_j, t_j) = 1$ holds we must have $ {\alpha} - {\beta} \in {\bf k}$ and thus $ r_j = r_{\ell}$ . Therefore, we have proved that $ {\ell} = j$ holds. This implies

$\displaystyle r = {\alpha} r_j \ \ {\rm and} \ \ t = {\alpha} t_j$ (95)

Since $ r/t$ is in canonical form, we deduce that $ {\gcd}(t_j, r_j) = 1$ and $ {\alpha} = ({\rm lc}(t_j))^{-1}$ hold. This proves $ (iii)$ . Finally, $ (iv)$ follows from $ (ii)$ and $ (iii)$ . $ \qedsymbol$

Marc Moreno Maza
2008-01-07