Re: PolynomialGCD
- To: mathgroup at smc.vnet.net
- Subject: [mg60297] Re: [mg60276] PolynomialGCD
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Sat, 10 Sep 2005 06:46:46 -0400 (EDT)
- References: <200509090807.EAA16029@smc.vnet.net> <B97D9B4F-43B3-4292-903C-161961237664@mimuw.edu.pl> <4321A57D.10103@wolfram.com>
- Sender: owner-wri-mathgroup at wolfram.com
On 10 Sep 2005, at 00:08, Daniel Lichtblau wrote:
> Andrzej Kozlowski wrote:
>
>> *This message was transferred with a trial version of CommuniGate
>> (tm) Pro*
>> On 9 Sep 2005, at 17:07, jonspalmer at gmail.com wrote:
>>
>>> Is there anyway to get PolynomialGCD to work with Complex
>>> numbers? For
>>> example get:
>>>
>>> PolynomialGCD[(x+y) I, (x+y) 2 I]
>>>
>>> to return:
>>>
>>> (x+y) I
>>>
>>>
>>> ?
>>>
>>> Many thanks
>>> Jon Palmer
>>>
>>>
>>>
>> It looks to me you have found prehistoric bug. But first let me
>> point out that in general PolynomialGCD cannot be expected to
>> work over real or complex numbers. PolynomialGCD is
>> mathematically defined but it does not make sense to try to
>> compute it by means of the Euclidean algorithm because a crucial
>> step in the algorithms demands determining if a real or complex
>> expression is 0 and this cannot be done exactly. On the other
>> hand there is no problem with using the Euclidean algorithm over
>> any algebraic extension of the rationals, and you can do it with
>> PolynomialGCD by means of the option Extension- >{a sequence of
>> algebraic numbers}.
>> However, this has nothing to do with the problem here. In fact
>> just replace I by 1+I and everything works fine:
>> PolynomialGCD[(x + 1)*(I + 1), (x + 1)*2*(I + 1)]
>> (1 + I)*x + (1 + I)
>> here PolynomialGCD simply treats I as a variable, which is
>> exactly what the documentation tells you it will do:
>> PolynomialGCD[poly1, poly2, ? ] will by default treat algebraic
>> numbers that appear in the polyi as independent variables.
>> So we have to conclude that
>> PolynomialGCD[(x+y) I, (x+y) 2 I]
>> x+y
>> is a bug and one that must have been with us since time
>> immemorial. In the immortal words of a former contributor this
>> list it is a "bug the long liver" ;-)
>> Andrzej
>>
>
> The Euclidean algorithm is really irrelevant because we consider
> multivariate gcds (k[x1,...xn] is not a Euclidean domain for n>1).
> One can use something similar, a remainder sequence, and we do for
> some inputs.
Yes, of course. Still. the main point is valid: there is no practical
algorithm for computing a general polynomial GCD over the reals or
complexs, for essentially for the reason I indicated. Of course this
has hardly anything to do with the issue except that the poster
referred to "PolynomialGCD with the Complex numbers" while the
correct concept is polynomial GCD over an algebraic extension of the
rationals.
>
> Note I is a unit in Z[I], and gcds are only defined up to units. It
> seems to me that Gaussians are automatically encorporated into the
> base ring when they are present in the input. So the bug, such as
> it is, is that there is no obvious way to keep them out of the
> ring. This contradicts documentation which claims (in effect) the
> base ring is always rationals. Tsis was reported several years ago
> in a setting where it causes more harm (due to speed), factorization.
>
>
> Daniel
Yes, I am now ready to admit that this could be regarded as an old
"documentation bug". The answer x + y is correct up to a unit.
Andrzej
- References:
- PolynomialGCD
- From: jonspalmer@gmail.com
- PolynomialGCD