Talk:Polynomial greatest common divisor

Comments removed in the article

Akritas2 has introduced the following comments in the article. I have reverted them. Nevertheless, they deserve to be discussed. Therefore, I reproduce them here.

Lazard, this section [Pseudo-remainder sequences] is of great historical interest, because it shows how science evolves through mistakes. Despite the fact that the ideas and the material presented are obsolete, they should not be removed. New material and ideas are interspersed throughout the text and delimited by <NM>. If you do not like them revert to the old text and I will not bother with it again. After all, it was you who asked me in the past to write about it.

The above sequence [the sequence with large rational coefficients in section "Pseudo-remainder sequences"] can be easily computed by the ${\text{sympy}}$ function ${\text{euclid}}\_{q}(A,B,x).$ This function and all the others mentioned below are available upon request.

After the discovery of the Pell-Gordon theorem of 1917 (by P. S. Vigklas in 2013) we can use the function ${\text{euclid}}\_{pg}(A,B,x)$, which performs polynomial divisions in Q[X], to compute not a "variant" but the actual Euclidean sequence for which all remainders belong to Z[X]. Polynomial divisions in Q[X] are performed using the function ${\text{rem}}(A,B,x).$

Moreover, after the formulation of the Akritas-Malaschonok-Vigklas theorem in 2015, we can use the function ${\text{euclid}}\_{amv}(A,B,x)$, which performs polynomial divisions in Z[X], to compute the actual Euclidean sequence for which all remainders belong to Z[X]. Polynomial divisions in Z[X] are performed using the function ${\text{rem}}\_{z}(A,B,x).$ This is the same function denoted below as ${\text{prem2}}(A,B,x).$

As stated above, using the function ${\text{prem}}(A,B,x),$ we can compute a variant of Euclid's sequence for which all remainders belong to Z[X].

However, this is messing up not only the signs of the Euclidean sequence, but also destroys the one-to-one correspondence that exists between Euclidean sequences and subresultant sequences. This correspondence is implied by the Pell-Gordon theorem of 1917 and is explicitly stated (along with some extensions/generalizations) in the Akritas-Malaschonok-Vigklas theorem of 2015.

In other words, the variant of the Euclidean sequence of the polynomials A and B obtained with ${\text{prem}}(A,B,x)$ uniquely corresponds to a variant of the subresultant sequence of A and B.

By contrast,

${\text{rem}}\_{z}(A,B,x)={\text{rem}}(|{\text{lc}}(B)|^{a-b+1}A,B),$

where |lc(B)| is the absolute value of the leading coefficient of B (the coefficient of X^b). This way we obtain the actual Euclidean sequence.

However, there is a snag! Namely, we cannot use ${\text{rem}}\_{z}(A,B,x)$ in the Collins-Brown-Traub algorithm, described below, to compute the subresultant prs of A and B. So, we have developed the function ${\text{subresultants}}\_{amv}(A,B,x)$.

What Collins, Brown and Traub did back in the late 1960's and early 1970's is absolutely remarkable. Namely, using the flawed function ${\text{prem}}(A,B,x)$ they were able to correctly compute the subresultant prs of A and B. That was the best they could do given the fact that they were not aware of the Pell-Gordon theorem and its ramifications.

Despite their mistaken approach, we should all be thankful to them because even in our new approach we use the absolute value of their coefficient reduction factor.

Lazard, with this I rest my case. Integrate the new material any way you want or ignore it altogether. But remember, as I said before, the material you already have placed is invaluable and should be kept for posterity. I already use it in my lectures and talks to show "how things were."

For avoiding personal disputes, I'll wait comments by other editors before commenting myself the content of Akritas2 edits. D.Lazard (talk) 09:30, 19 January 2016 (UTC)

omission in subresultant pseudo-remainder sequence algorithm

The γ in the last line of the loop lacks a subscript, but subscriptless γ hasn't been defined. I assume it should be γ_i since γ₁ is the only γ value that has been defined when i = 1? — Preceding unsigned comment added by 50.107.103.122 (talk) 18:20, 12 January 2018 (UTC)

Good point, fixed. D.Lazard (talk) 18:27, 12 January 2018 (UTC)

Off-by-one error in subresultant pseudo-remainder sequence algorithm

I consulted Zippel's "Effective Polynomial Computation" section 8.6. page 135 to double-check the indexing, and it seems to me the pseudo-code as given is slightly wrong. I think it's crucial that

$\psi _{i}:={\frac {(-\gamma _{i})^{d_{i-1}}}{\psi _{i-1}^{d_{i-1}-1}}}$

should instead be

$\psi _{i}:={\frac {(-\gamma _{i-1})^{d_{i-1}}}{\psi _{i-1}^{d_{i-1}-1}}}$

A quick typescript implementation with some notes about how it relates to Zippel's notation is https://bitbucket.org/snippets/jcreed/EbGMEB . If I'm not mistaken, I'm happy to make the edit myself. Jcreed (talk) 19:26, 3 January 2020 (UTC)

Problem with the degree bounds in the extended GCD?

It appears that the bounds $\deg(u)<\deg(b)-\deg(g),\quad \deg(v)<\deg(a)-\deg(g)$ require some extra assumptions. E.g., it is nowhere mentioned if $a,b$ should be non-zero. If we allow $\deg(a)\geq 0$ and $b=0$, the GCD is $a$; however, then $u=1,v=0$ leads to $0=\deg(u)<\deg(b)-\deg(a)=-\deg(a)$. Furthermore, even if it is required that $a,b$ are both non-zero polynomials, it is possible that $\deg(a)=\deg(b)=0$ and $u=0,v=1$, for example. This leads to $0<0$. Shouldn't one require that $u,v$ are both non-zero and $\max\{\deg(a),\deg(b)\}>0$? Mk4124 (talk) 12:42, 22 January 2019 (UTC)

Good point. I'll try fixing it. D.Lazard (talk) 12:56, 22 January 2019 (UTC)

Terminology: Euclidean division

The "Euclidean division" page specifically states that it refers to integer division. This page even mentions Euclidean domains as a generalization. Maybe we should be strict with the terminology and call it "Euclidean function for polynomials, or division with remainder for polynomials, which is ...". The introduction is actually careful in not calling it Euclidean division, and instead just saying that the division "can be derived" from Euclidean division. But after that, the polynomial division is just called Euclidean division. Dragomang87 (talk) 18:56, 4 January 2024 (UTC)

We must use the most common terminology that is used in the literature. Commonly, the Euclidean function is a function from a Euclidean domain to the integers that Euclidean division allows to minimize. It is the absolute value in the case of the integers and the degree in the case of polynomials. Euclidean division is commonly used not only for integers but also for Euclidean division of polynomials and division in Euclidean domains. So, nothing needs to be changed in the terminology. On the contrary, the change you suggest would be WP:original research. Note that the lead uses long division instead of Euclidean division; it is because Euclidean division does not provide an algorithm by itself, and that the corresponding algorithm is called "long division". There are Euclidean domains for which there is no algorithm for Euclidan division, or, at least only very complicated algorithms. D.Lazard (talk) 21:40, 4 January 2024 (UTC)