Rational Function Reconstruction

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

$$\equiv \leq$$ (86)

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

$$\equiv \leq$$ (87)

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

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

The following Theorem 5:

• says that problem WRFR(m, n, f, d ) mathend000# 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 ) mathend000# to be a solution of RFR(m, n, f, d ) mathend000#,
• tells that this condition is also a necessary and sufficient condition for RFR(m, n, f, d ) mathend000# to have a solution.

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

Theorem 5   Let r_j, s_j, t_j $\in$ $\bf k$[x] mathend000# be the j mathend000#-th row of the Extended Euclidean Algorithm applied to (a, b) = (m, f ) mathend000# where j mathend000# is minimal such that degr_j < d mathend000#.

(i) mathend000#

The couple (r, t) = (r_j, t_j) mathend000# is a solution to problem WRFR(m, n, f, d ) mathend000#.

(ii) mathend000#

If gcd(r_j, t_j) = 1 mathend000#, then the couple (r, t) = (r_j, t_j) mathend000# is a solution to problem RFR(m, n, f, d ) mathend000#.

(iii) mathend000#

If (r, t) mathend000# is a solution to problem RFR(m, n, f, d ) mathend000# and if r/t mathend000# is a canonical form, then we have (r, t) = (w_j^-1r_j, w_j^-1t_j) mathend000# where w_j = lc(t_j) mathend000#.

(iv) mathend000#

Problem RFR(m, n, f, d ) mathend000# admits a solution if and only if gcd(r_j, t_j) = 1 mathend000#.

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

$$\infty$$ (88)

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

$$\leq$$ (89)

From Point (iv) mathend000# of Proposition 1 we have

r_j = s_jm + t_jf (90)

leading to r_j $\equiv$ t_jf modm mathend000#. From Proposition 2, we deduce

$$\leq$$ (91)

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

gcd(m, t_j) = gcd(r_j, t_j) = 1. (92)

This implies that t_j mathend000# is invertible modulo m mathend000#, leading to rt^-1 $\equiv$ f modm mathend000#. Hence, under the assumption gcd(r_j, t_j) = 1 mathend000#, the couple (r_j, t_j) mathend000# is also a solution to RFR(m, n, f, d ) mathend000#.

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

$$\ell \leq \ell$$ (93)

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

If degr_j $\leq$ degr mathend000# then we have $\ell$ = j mathend000#. If degr < degr_j mathend000# then we have $\ell$ > j mathend000#.

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

$$\alpha \beta \ell$$ (94)

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

$$\alpha \alpha$$ (95)

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