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

$${\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

$$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:

• says that problem $WRFR(m, n, f, d)$ has always a solution, which can be computed by an algorithm,
• gives a necessary and sufficient condition for a solution of $WRFR(m, n, f, d)$ to be a solution of $RFR(m, n, f, d)$ ,
• tells that this condition is also a necessary and sufficient condition for $RFR(m, n, f, d)$ to have a solution.

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,

$$- \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

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

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

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

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

$${\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

$${\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

$${\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

$$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

$$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$