MathAction #191 exquo and therefore gcd cannot handle UP(x, EXPR INT)

login home contents what's new discussion bug reports

help links subscribe changes refresh edit

	IssueTracker
#190 Compile fail on Fedora Core 4 ←	↑	→ #192 Folding does not work in Konqueror 3.1.4

#191 exquo and therefore gcd cannot handle UP(x, EXPR INT)

Topics

FrontPage
- IssueTracker
  - #191 exquo and therefore gcd cannot handle UP(x, EXPR INT) <-- You are here.

(new) exquo and therefore gcd cannot handle UP(x, EXPR INT) --Bill Page, Mon, 11 Jul 2005 15:56:25 -0500 reply

Update of bug #10530 (project axiom):

Status: None => transferred

fricas

(1) -> gcd((x-2^a)::UP(x, EXPR INT), simplify((x-2^a)*(x+2^a))::UP(x, EXPR INT))

$\label{eq1}1$

Type: UnivariatePolynomial(x,Expression(Integer))

Gives 1, while the correct answer should be , as given by

fricas

gcd((x-2^a)::UP(x, EXPR INT),((x-2^a)*(x+2^a))::UP(x, EXPR INT))

$\label{eq2}x -{{2}^{a}}$

Type: UnivariatePolynomial(x,Expression(Integer))

In fact, to ensure that algebraic relations are respected inside expressions one has to normalize all involved expressions:

fricas

uP := UP(x, EXPR INT)

$\label{eq3}\hbox{\axiomType{UnivariatePolynomial}\ } \left({x , \:{\hbox{\axiomType{Expression}\ } \left({\hbox{\axiomType{Integer}\ }}\right)}}\right)$

Type: Type

fricas

p1 := (x-2^a)::uP

$\label{eq4}x -{{2}^{a}}$

Type: UnivariatePolynomial(x,Expression(Integer))

fricas

p2 := simplify((x-2^a)*(x+2^a))::uP

$\label{eq5}{{x}^{2}}-{{4}^{a}}$

Type: UnivariatePolynomial(x,Expression(Integer))

fricas

cl1 := coefficients(p1)

$\label{eq6}\left[ 1, \: -{{2}^{a}}\right]$

Type: List(Expression(Integer))

fricas

cl2 := coefficients(p2)

$\label{eq7}\left[ 1, \: -{{4}^{a}}\right]$

Type: List(Expression(Integer))

fricas

ncl := normalize(concat(cl1, cl2))

$\label{eq8}\left[ 1, \: -{{e}^{a \ {\log \left({2}\right)}}}, \: 1, \: -{{{e}^{a \ {\log \left({2}\right)}}}^{2}}\right]$

Type: List(Expression(Integer))

fricas

ncl1 := first(ncl, #cl1)

$\label{eq9}\left[ 1, \: -{{e}^{a \ {\log \left({2}\right)}}}\right]$

Type: List(Expression(Integer))

fricas

ncl2 := rest(ncl, #cl1)

$\label{eq10}\left[ 1, \: -{{{e}^{a \ {\log \left({2}\right)}}}^{2}}\right]$

Type: List(Expression(Integer))

fricas

np1 := reduce(_+, [monomial(c,degree(m))$uP for m in monomials(p1) for c in ncl1])

$\label{eq11}x -{{e}^{a \ {\log \left({2}\right)}}}$

Type: UnivariatePolynomial(x,Expression(Integer))

fricas

np2 := reduce(_+, [monomial(c,degree(m))$uP for m in monomials(p2) for c in ncl2])

$\label{eq12}{{x}^{2}}-{{{e}^{a \ {\log \left({2}\right)}}}^{2}}$

Type: UnivariatePolynomial(x,Expression(Integer))

fricas

gcd(np1, np2)

$\label{eq13}x -{{e}^{a \ {\log \left({2}\right)}}}$

Type: UnivariatePolynomial(x,Expression(Integer))

Not nice, but in general this is what is needed (below are simpler attempts which sometimes work, but may fail).

Internal Cause

In EXPR INT, and $2^{(2a)}$ are treated as two variables without relations in EXPR INT. But

fricas

simplify((x-2^a)*(x+2^a))::UP(x, EXPR INT)

$\label{eq14}{{x}^{2}}-{{4}^{a}}$

Type: UnivariatePolynomial(x,Expression(Integer))

Therefore exquo in:

  exquo(simplify((x-2^a)*(x+2^a))::UP(x,EXPR INT),(x-2^a)::UP(x,EXPR INT))

fails. In details, it calls exquo$UP(x,EXPR INT). This implements exact division of polynomials p1 by p2 as usual. After each subtraction - done via fmecg$UP - the result is again stored in p1. exquo terminates when p1 is the empty list - note that UPs? are stored as lists of pairs (degree, coefficient) - or the degree of p2 is larger than p1. In the latter case, exquo fails.

Thus, in our case, at one point p1 is $4^a-2^{(2a)}$ , which is zero mathematically, but FriCAS does not know it. In particular, p1 is not the empty list, but rather a constant polynomial...

To get correct result we need to express coefficients of p1 and p2 in terms of independent kernels. In more general contexts (in particular involving abs) this is undecidable, but for elementary functions normalize works. More precisely, currently normalize ignores possible dependencies between algebraic quantities like roots. And to simplification of transcendental constants depends on Schanuel conjecture (if Schanuel conjecture is false we may miss some dependencies).

Wed 09/29/2004 at 16:02, comment #1:

I should have added:

fricas

exquo(normalize(simplify(((A-2^a)*(A+2^a)))::EXPR INT),normalize((A-2^a)::EXPR INT))

$\label{eq15}\frac{{{e}^{a \ {\log \left({4}\right)}}}-{{A}^{2}}}{{{e}^{a \ {\log \left({2}\right)}}}- A}$

Type: Union(Expression(Integer),...)

fricas

exquo(simplify((A-2^a)*(A+2^a))::UP(A,EXPR INT),(A-2^a)::UP(A,EXPR INT))

$\label{eq16}\verb#"failed"#$

Type: Union("failed",...)

This shows that using normalize separately on polynomials does not help, we need to normalize list of coefficients as a whole.

Few examples showing that without normalization FriCAS does not always treat $2^{a2}$ the same as :

fricas

dom:=UP('x,EXPR INT)

$\label{eq17}\hbox{\axiomType{UnivariatePolynomial}\ } \left({x , \:{\hbox{\axiomType{Expression}\ } \left({\hbox{\axiomType{Integer}\ }}\right)}}\right)$

Type: Type

fricas

p:dom:=x-2^a

$\label{eq18}x -{{2}^{a}}$

Type: UnivariatePolynomial(x,Expression(Integer))

fricas

q:=(x-2^a)*(x+2^a)

$\label{eq19}-{{{2}^{a}}^{2}}+{{x}^{2}}$

Type: Expression(Integer)

fricas

qq:= simplify(q)

$\label{eq20}-{{4}^{a}}+{{x}^{2}}$

Type: Expression(Integer)

fricas

r:= q::dom

$\label{eq21}{{x}^{2}}-{{{2}^{a}}^{2}}$

Type: UnivariatePolynomial(x,Expression(Integer))

fricas

rr:= qq::dom

$\label{eq22}{{x}^{2}}-{{4}^{a}}$

Type: UnivariatePolynomial(x,Expression(Integer))

fricas

gcd(p,q)

$\label{eq23}x -{{2}^{a}}$

Type: UnivariatePolynomial(x,Expression(Integer))

fricas

exquo(q,p)

$\label{eq24}{{2}^{a}}+ x$

Type: Union(Expression(Integer),...)

fricas

gcd(p,r)

$\label{eq25}x -{{2}^{a}}$

Type: UnivariatePolynomial(x,Expression(Integer))

fricas

gcd(p,qq)

$\label{eq26}1$

Type: UnivariatePolynomial(x,Expression(Integer))

fricas

gcd(p,rr)

$\label{eq27}1$

Type: UnivariatePolynomial(x,Expression(Integer))

fricas

q - qq

$\label{eq28}{{4}^{a}}-{{{2}^{a}}^{2}}$

Type: Expression(Integer)

fricas

simplify q - qq

$\label{eq29}0$

Type: Expression(Integer)

fricas

simplify ((r - rr)::EXPR INT)

$\label{eq30}0$

Type: Expression(Integer)

fricas

t:Boolean:=(r = rr)

$\label{eq31} \mbox{\rm false}$

Type: Boolean

... --test1, Thu, 23 Feb 2017 19:30:42 +0000 reply

Status: open => closed