)abbrev package AF AlgebraicFunction
++ Author: Manuel Bronstein
++ Date Created: 21 March 1988
++ Date Last Updated: 11 November 1993
++ Description:
++ This package provides algebraic functions over an integral domain.
++ Keywords: algebraic, function.
AlgebraicFunction(R, F): Exports == Implementation where
R: IntegralDomain
F: FunctionSpace R
SE ==> Symbol
Z ==> Integer
Q ==> Fraction Z
OP ==> BasicOperator
K ==> Kernel F
P ==> SparseMultivariatePolynomial(R, K)
UP ==> SparseUnivariatePolynomial F
UPR ==> SparseUnivariatePolynomial R
Exports ==> with
rootOf : (UP, SE) -> F
++ rootOf(p, y) returns y such that \spad{p(y) = 0}.
++ The object returned displays as \spad{'y}.
operator: OP -> OP
++ operator(op) returns a copy of \spad{op} with the domain-dependent
++ properties appropriate for \spad{F}.
++ Error: if op is not an algebraic operator, that is,
++ an nth root or implicit algebraic operator.
belong? : OP -> Boolean
++ belong?(op) is true if \spad{op} is an algebraic operator, that is,
++ an nth root or implicit algebraic operator.
inrootof: (UP, F) -> F
++ inrootof(p, x) should be a non-exported function.
-- un-export when the compiler accepts conditional local functions!
droot : List F -> OutputForm
++ droot(l) should be a non-exported function.
-- un-export when the compiler accepts conditional local functions!
if R has RetractableTo Integer then
** : (F, Q) -> F
++ x ** q is \spad{x} raised to the rational power \spad{q}.
minPoly: K -> UP
++ minPoly(k) returns the defining polynomial of \spad{k}.
definingPolynomial: F -> F
++ definingPolynomial(f) returns the defining polynomial of \spad{f}
++ as an element of \spad{F}.
++ Error: if f is not a kernel.
iroot : (R, Z) -> F
++ iroot(p, n) should be a non-exported function.
-- un-export when the compiler accepts conditional local functions!
Implementation ==> add
macro ALGOP == '%alg
macro SPECIALDISP == '%specialDisp
macro SPECIALDIFF == '%specialDiff
ialg : List F -> F
dvalg: (List F, SE) -> F
dalg : List F -> OutputForm
opalg := operator('rootOf)$CommonOperators
oproot := operator('nthRoot)$CommonOperators
belong? op == has?(op, ALGOP)
dalg l == second(l)::OutputForm
rootOf(p, x) ==
k := kernel(x)$K
(r := retractIfCan(p)@Union(F, "failed")) case "failed" =>
inrootof(p, k::F)
n := numer(f := univariate(r::F, k))
positive? degree denom f => error "roofOf: variable appears in denom"
inrootof(n, k::F)
dvalg(l, x) ==
p := numer univariate(first l, retract(second l)@K)
alpha := kernel(opalg, l)
- (map(differentiate(#1, x), p) alpha) / ((differentiate p) alpha)
ialg l ==
f := univariate(p := first l, retract(x := second l)@K)
positive? degree denom f => error "roofOf: variable appears in denom"
inrootof(numer f, x)
operator op ==
is?(op,'rootOf) => opalg
is?(op,'nthRoot) => oproot
error "Unknown operator"
if R has AlgebraicallyClosedField then
UP2R: UP -> Union(UPR, "failed")
inrootof(q, x) ==
monomial? q => 0
(d := degree q) <= 0 => error "rootOf: constant polynomial"
one? d=> - leadingCoefficient(reductum q) / leadingCoefficient q
((rx := retractIfCan(x)@Union(SE, "failed")) case SE) and
((r := UP2R q) case UPR) => rootOf(r::UPR, rx::SE)::F
kernel(opalg, [q x, x])
UP2R p ==
ans:UPR := 0
while p ~= 0 repeat
(r := retractIfCan(leadingCoefficient p)@Union(R, "failed"))
case "failed" => return "failed"
ans := ans + monomial(r::R, degree p)
p := reductum p
ans
else
inrootof(q, x) ==
monomial? q => 0
(d := degree q) <= 0 => error "rootOf: constant polynomial"
one? d => - leadingCoefficient(reductum q) /leadingCoefficient q
kernel(opalg, [q x, x])
evaluate(opalg, ialg)$BasicOperatorFunctions1(F)
setProperty(opalg, SPECIALDIFF,
dvalg@((List F, SE) -> F) pretend None)
setProperty(opalg, SPECIALDISP,
dalg@(List F -> OutputForm) pretend None)
if R has RetractableTo Integer then
import PolynomialRoots(IndexedExponents K, K, R, P, F)
dumvar := '%%var::F
lzero : List F -> F
dvroot : List F -> F
inroot : List F -> F
hackroot: (F, Z) -> F
inroot0 : (F, Z, Boolean, Boolean) -> F
lzero l == 0
droot l ==
x := first(l)::OutputForm
(n := retract(second l)@Z) = 2 => root x
root(x, n::OutputForm)
dvroot l ==
n := retract(second l)@Z
(first(l) ** ((1 - n) / n)) / (n::F)
x ** q ==
qr := divide(numer q, denom q)
x ** qr.quotient * inroot([x, (denom q)::F]) ** qr.remainder
hackroot(x, n) ==
(n = 1) or (x = 1) => x
(not one?(dx := denom x) and
((rx := retractIfCan(dx)@Union(Integer,"failed")) case Integer) and
positive?(rx))
=> hackroot((numer x)::F, n)/hackroot(rx::Integer::F, n)
(x = -1) and n = 4 =>
((-1::F) ** (1::Q / 2::Q) + 1) / ((2::F) ** (1::Q / 2::Q))
kernel(oproot, [x, n::F])
inroot l ==
zero?(n := retract(second l)@Z) => error "root: exponent = 0"
one?(x := first l) or one? n => x
(r := retractIfCan(x)@Union(R,"failed")) case R => iroot(r::R,n)
(u := isExpt(x)) case Record(var:K, exponent:Z) =>
pr := u::Record(var:K, exponent:Z)
is?(pr.var,oproot) and #argument(pr.var) = 2 =>
(first argument(pr.var)) **
(pr.exponent /$Fraction(Z)
(n * retract(second argument(pr.var))@Z))
inroot0(x, n, false, false)
inroot0(x, n, false, false)
-- removes powers of positive integers from numer and denom
-- num? or den? is true if numer or denom already processed
inroot0(x, n, num?, den?) ==
rn:Union(Z, "failed") := (num? => "failed"; retractIfCan numer x)
rd:Union(Z, "failed") := (den? => "failed"; retractIfCan denom x)
(rn case Z) and (rd case Z) =>
rec := qroot(rn::Z / rd::Z, n::NonNegativeInteger)
rec.coef * hackroot(rec.radicand, rec.exponent)
rn case Z =>
rec := qroot(rn::Z::Fraction(Z), n::NonNegativeInteger)
rec.coef * inroot0((rec.radicand**(n exquo rec.exponent)::Z)
/ (denom(x)::F), n, true, den?)
rd case Z =>
rec := qroot(rd::Z::Fraction(Z), n::NonNegativeInteger)
inroot0((numer(x)::F) /
(rec.radicand ** (n exquo rec.exponent)::Z),
n, num?, true) / rec.coef
hackroot(x, n)
if R has AlgebraicallyClosedField then iroot(r, n) == nthRoot(r, n)::F
else
iroot0: (R, Z) -> F
if R has RadicalCategory then
if R has imaginary:() -> R then iroot(r, n) == nthRoot(r, n)::F
else
iroot(r, n) ==
odd? n or not before?(r,0) => nthRoot(r, n)::F
iroot0(r, n)
else iroot(r, n) == iroot0(r, n)
iroot0(r, n) ==
rec := rroot(r, n::NonNegativeInteger)
rec.coef * hackroot(rec.radicand, rec.exponent)
definingPolynomial x ==
(r := retractIfCan(x)@Union(K, "failed")) case K =>
is?(k := r::K, opalg) => first argument k
is?(k, oproot) =>
dumvar ** retract(second argument k)@Z - first argument k
dumvar - x
dumvar - x
minPoly k ==
is?(k, opalg) =>
numer univariate(first argument k,
retract(second argument k)@K)
is?(k, oproot) =>
monomial(1,retract(second argument k)@Z :: NonNegativeInteger)
- first(argument k)::UP
monomial(1, 1) - k::F::UP
evaluate(oproot, inroot)$BasicOperatorFunctions1(F)
derivative(oproot, [dvroot, lzero])
else -- R is not retractable to Integer
droot l ==
x := first(l)::OutputForm
(n := second l) = 2::F => root x
root(x, n::OutputForm)
minPoly k ==
is?(k, opalg) =>
numer univariate(first argument k,
retract(second argument k)@K)
monomial(1, 1) - k::F::UP
setProperty(oproot, SPECIALDISP,
droot@(List F -> OutputForm) pretend None)
