MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Solving 2D scalar wave equation?
  • Next by Date: Re: Matrix question
  • Previous by thread: Re: PolynomialGCD
  • Next by thread: A very EZ Question! Make a Graph!