16
$\begingroup$

Introduction: Given two univariate and coprime integer polynomials $f(x), g(x)$, we can always write \begin{equation} u(x)f(x)+v(x)g(x)=c \end{equation} for a unique pair of integer polynomials $u(x), v(x)$, and a unique positive integer $c$, such that $\deg u<\deg g$ and $\deg v<\deg f$. (This is a consequence of cancellation in the denominators in Bezout's identity, applied to $f$ and $g$ as elements of $\mathbb{Q}[x]$ and $c$ is the $lcm$ of the denominators of the unique pair of rational polynomials determined by Bezout's identity).

However, the positive integer $c$ need not be the minimal integer satisfying such a relation—there may be integer polynomials $p(x)$ and $ q(x)$ of arbitrary degrees such that $$ p(x)f(x)+q(x)g(x)=d $$ with $d<c$.

As an example, consider $f(x)=2x+1$, $g(x)=2x+17$, for which Bezout's identity gives $c=16$: $$ \frac{1}{16}(2x+17)-\frac{1}{16}(2x+1)=1 \Leftrightarrow (2x+17)-(2x+1)=16; $$ while for $p(x)=-(x^4 + 8 x^3 - 4x^2 + 2 x - 1)$, $q(x)=x^4$, we obtain $d=1$: $$ (2 x + 17) (x^4)-(2 x + 1) (x^4 + 8 x^3 - 4x^2 + 2 x - 1)=1. $$ (This example is cited in On resultants, Proc Amer Math Soc 89 (1983) 419-420, G. Myerson.)

The minimal positive integer $c$ satisfying such a relation $p(x)f(x)+q(x)g(x)=c$, for $p(x), q(x)$ integer polynomials, is by definition called the reduced resultant of $f,g$ (see The resultant and the ideal generated by two polynomials in $\mathbb{Z}[x]$). As I understand it, if $f$ and $g$ are both monic (see Reduced resultant of monic polynomials), then this minimal positive integer (that is, the reduced resultant), can be found by applying the extended Euclidean algorithm, obtaining the Bezout's identity, and then clearing denominators.

Now the question: For any pair of coprime, integer polynomials $f$ and $g$, how can we find polynomials $p(x)$ and $q(x)$—of suitable degrees—together with the minimal positive integer $c$, such that $$ p(x)f(x)+q(x)g(x)=c. $$

P.S.: Given two coprime integer polynomials $f,g$, by Bezout's identity in $\mathbb{Q}[x]$, we know that all other pairs of rational polynomials, satisfying the relation $A(x)f(x)+B(x)g(x)=1$ are of the form $$ A(x)=\frac{1}{c}u(x)+g(x)w(x), \ \ \ B(x)=\frac{1}{c}v(x)-f(x)w(x) $$ for arbitrary $w(x)\in\mathbb{Q}[x]$. Notice also, that in the preceding example, by long-division we get: $$ B(x)=q(x)=x^4 + 8 x^3 - 4 x^2 + 2 x - 1=\left(-\frac{1}{16}+\frac{x}{8}-\frac{x^2}{4}+\frac{x^3}{2}\right) (2 x+17) +\frac{1}{16} $$ and: $$ A(x)=p(x)=x^4=\left(-\frac{1}{16}+\frac{x}{8}-\frac{x^2}{4}+\frac{x^3}{2}\right) (2 x+1)+\frac{1}{16} $$ for: $w(x)=\left(-\frac{1}{16}+\frac{x}{8}-\frac{x^2}{4}+\frac{x^3}{2}\right)$.

Thus, the problem amounts to deciding, whether we can determine a suitable rational polynomial $w(x)$, such that $A(x)$, $B(x)$ have $lcm$ of their denominators less than $c$.

$\endgroup$
  • $\begingroup$ as I was saying on the other site, I do not think Gerry would object to an email question on this; he seems to be the one who knows exactly what is going on. $\endgroup$ – Will Jagy Aug 29 '16 at 20:37
  • $\begingroup$ @ Will Jagy: thank you for the info! I appreciate that. I think I will wait for a while and then maybe I will follow your advice. $\endgroup$ – Konstantinos Kanakoglou Aug 29 '16 at 20:45
  • $\begingroup$ this question has a partial overlap with: mathoverflow.net/questions/248574/… $\endgroup$ – Konstantinos Kanakoglou Sep 3 '16 at 0:44
  • 1
    $\begingroup$ @Gerry Myerson, what i meant was that $u,v,c$ are uniquely determined by the application of Bezout's identity (and then clearing denominators). In the example cited this is $u(x)=-1$, $v(x)=1$ and $c=16$. Am i misinterpreting something? $\endgroup$ – Konstantinos Kanakoglou Jun 6 '19 at 15:14
  • 2
    $\begingroup$ @Gerry Myerson, i have edited hoping to become more clear. $\endgroup$ – Konstantinos Kanakoglou Jun 8 '19 at 2:27
7
$\begingroup$

First off, it can be seen that the reduced resultant must divide $c$. Indeed, if $u_1(x)f(x)+v_1(x)g(x)=c$ and $u_2(x)f(x)+v_2(x)g(x)=d$, then from the Bezout identity for integers $c,d$, we can construct the identity $u(x)f(x)+v(x)g(x)=\gcd(c,d)$. Hence, if $d$ is the reduced resultant, then $d=\gcd(c,d)$, i.e. $d\mid c$.

Now, let's see if a prime factor $p|c$ can be cancelled from the r.h.s. of the identity $u(x)f(x)+v(x)g(x)=c$. From polynomials $u(x)$ and $v(x)$, we need to obtain polynomials $cA(x)$ and $cB(x)$ with integer coefficients such that $cA(x)\equiv cB(x)\equiv 0\pmod{p}$. (I follow the notation of OP.)

I'll consider the case $\mathrm{cont}(f)=\mathrm{cont}(g)=1$. Then Gauss' lemma implies that $cw(x)$ is a polynomial with integer coefficients. Thus, the condition $v(x)-f(x)(cw(x))=cB(x)\equiv 0\pmod{p}$ implies that $f(x)$ divides $v(x)$ modulo $p$. The last condition is necessary and sufficient for cancellation of $p$. When the divisibility modulo $p$ holds, setting $w(x) = \frac{1}{c}\left(\frac{v(x)}{f(x)}\bmod p\right)$ delivers us the required polynomials $u'(x): = \frac{cA(x)}{p}=\frac{u(x)+g(x)(\frac{v(x)}{f(x)}\bmod p)}p$ and $v'(x): = \frac{cB(x)}{p}=\frac{v(x)-f(x)(\frac{v(x)}{f(x)}\bmod p)}p$, for which $$u'(x)f(x)+v'(x)g(x) = \frac{c}{p}.$$

So, the reduced resultant can be computed by first computing some $c=u(x)f(x)+v(x)g(x)$ (e.g., with the extended Euclidean algorithm), and then by eliminating prime factors from $c$ (as described above) one by one while this is possible.


Example. For $f(x)=2x+1$ and $g(x)=2x+17$, we have $c=16$ with $u(x)=-1$ and $v(x)=1$. To check if we can cancel factor $p=2$, we check if $g(x)$ divides $u(x)$ modulo $2$. It does, and we set $c w(x)$ to the quotient, i.e. $cw(x)=1$, to get new polynomials $u_2(x):=\frac{u(x) + g(x)}2 = x+8$ and $v_2(x):=\frac{v(x)-f(x)}2=-x$. It is easy to check that $$u_2(x)f(x) + v_2(x)g(x) = 8,$$ i.e. the factor $2$ is cancelled in the r.h.s.

Continuing this way, we can cancel another factor of $2$ by setting $cw(x)=x$ to get $u_3(x):=\frac{u_2(x)+g(x)x}2 = x^2 + 9x + 4$ and $v_3(x):=\frac{v_2(x)-f(x)x}2 = -x^2 - x$ with $$u_3(x)f(x) + v_3(x)g(x) = 4,$$ and so on.

$\endgroup$
  • $\begingroup$ "From polynomials u(x) and v(x), we need to obtain polynomials cA(x) and cB(x) with integer coefficients such that cA(x)≡cB(x)≡0(modp)." What do you mean by this? cA(x) will always be divisible by p, since c is. And what is w(x) in the next paragraph? $\endgroup$ – darij grinberg Jun 5 '19 at 11:44
  • 1
    $\begingroup$ @darijgrinberg: "cA(x) will always be divisible by p, since c is" - No! Recall that $A(x)$ is a polynomial with rational coefficients, while multiplying it by $c$ makes its coefficients integer. As of $w(x)$, I follow the notation of OP. $\endgroup$ – Max Alekseyev Jun 5 '19 at 12:13
  • $\begingroup$ Ah! I only read the main question, not the OP. $\endgroup$ – darij grinberg Jun 5 '19 at 12:25
  • 1
    $\begingroup$ @KonstantinosKanakoglou: I have no idea if this is already known, but if not, given the simplicity of arguments publishing in a journal like AMM may be an option. Would you like to take the lead? $\endgroup$ – Max Alekseyev Jun 7 '19 at 14:36
  • 1
    $\begingroup$ @KonstantinosKanakoglou: Sure - you are welcome to drop me an email to maxal@gwu.edu $\endgroup$ – Max Alekseyev Jun 8 '19 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.