Talk:Square-free polynomial

[Untitled]

Sometimes people do really weird things with TeX. I found this:

$f_{0}=f\,$, $f_{1}=\gcd(f_{0},f_{0}')\,$, $f_{2}=\gcd(f_{1},f_{1}')\,$, $f_{3}=\gcd(f_{2},f_{2}')\,$, $\dots$

and I changed it to this:

$f_{0}=f,\ f_{1}=\gcd(f_{0},f_{0}'),\ f_{2}=\gcd(f_{1},f_{1}'),\ f_{3}=\gcd(f_{2},f_{2}'),\dots$

The misaligned commas and misaligned final dots wouldn't have happened if TeX had been used properly. Michael Hardy (talk) 00:45, 13 February 2009 (UTC)

Complexity

What is the meaning of the sentence In characteristic zero, their computational complexity is lower than twice that of the computation of the greatest common divisor of the polynomial and its derivative.?

Usually one ignores constant factors when talking about complexity, so can we drop the twice? Then it seems that, at least naively, you need to compute degree many gcds.

Is it obvious that the gcd is provably the dominating factor in the complexity? I.e., how do we know that in this special case, it's not possible to compute the gcd quickly, which make the divisons dominate? [I trust that these gcds are harder, but it's not entirely obvious, is it?]

I changed the wording, feel free to edit it back. Saraedum (talk) 23:28, 9 August 2012 (UTC)

In fact, this assertion on complexity is true only for univariate polynomials and one should include in the computation time of the GCD the time for computing the quotients of the input polynomials by their GCD. I believe that this is the main result of Yun's paper, but not having the paper at hand, I can not verify this immediately. The result follows from the fact that the complexity of GCD is at least linear in the input degree and from the following result: let us call input degree of a GCD computation, the maximal degree of its input. Then the sum of the input degrees of the GCD's that are needed to complete the computation (after having computed the GCD of the polynomial and its derivative) is upper bounded by the degree of the input polynomial. I'll thus revert your edit and correct the assertion. D.Lazard (talk) 10:07, 10 August 2012 (UTC)

square root of a polynomial

Given we are talking about square free polynomial, should we have a link for find the square root of a polynomial, especially for the context of a extended Finite field. Jackzhp (talk) 07:23, 15 January 2018 (UTC)

I have added a section to the article, and updated accordingly the redirect Square root of polynomial. I do not know what is "a extended Finite field". D.Lazard (talk) 08:10, 15 January 2018 (UTC)

Square-Free vs Separable Polynomials

Hi @D.Lazard, I saw that you reverted my edit a couple days ago regarding square-free polynomials. Your condition, that there is no repeated root in any algebraically closed field extension of the polynomial, appears to be rather the condition for a polynomial to be a separable polynomial. Here is the first paragraph therein:

"In mathematics, a polynomial P(X) over a given field K is separable if its roots are distinct in an algebraic closure of K, that is, the number of distinct roots is equal to the degree of the polynomial."

This appears to me to be equivalent to your definition of square-free, which I copy here for ease:

"In mathematics, a square-free polynomial is a univariate polynomial (over a field or an integral domain) that has no multiple root in an algebraically closed field containing its coefficients."

Could you please clarify this?

Athena.Jennings (talk) 15:49, 19 May 2024 (UTC)

There are two definitions of separable that coincide for irreducible polynomials. The article Separable polynomial asserts that one is no longer in use. I have tagged this assertion with {{citation needed}} because this seem wrong to me. Nevertheless, the concept of separability being used only in field theory, most authors do not define separability of reducible polynomials.

In any case, "separable polynomial" is generally used in the context of field extensions and "square-free polynomials" are mainly considered in the context of polynomial factorization. As these two domains are very different, there is no harm if the same notion has differnt names in the two domains.

A note could be added for saying that the two definitions coincide. D.Lazard (talk) 17:45, 19 May 2024 (UTC)