axiom-developer
[Top][All Lists]

## Re: [Axiom-developer] about Expression Integer (with Quizzes)

 From: William Sit Subject: Re: [Axiom-developer] about Expression Integer (with Quizzes) Date: Sun, 26 Feb 2006 01:32:22 -0500

"Page, Bill" wrote:
>
> William
>
> On Friday, February 24, 2006 8:07 AM you wrote:
> >
> > Any scientific literate person, when (s)he wrote down:
> >
> >    2*x + 1/x
> >
> > would mean that there is only ONE x, the x means the same
> > thing throughout the expression.
>
> Yes.

I'm glad you agreed. So how can you keep arguing that one x lives in one domain,
and the other x in another?

> > So
> >
> > (1) -> (2*x+1/x)::DMP([x], EXPR INT)
> >
> >           2
> >         2x  + 1
> >    (1)  -------
> >            x
> >               Type:
> > DistributedMultivariatePolynomial([x],Expression Integer)
> > (2) -> degree(%)
> >
> >    (6)  [0]
> >
> > is perfectly correctly interpreted by Axiom. The entire
> > expression is a coefficient, in EXPR INT.
>
> It is a correct interpretation, but it is not the only
> possible interpretation. The reason it is interpreted as
> entirely with 'EXPR INT' is because you used a conversion
> '::' instead of a package call $. Axiom processes what is > inside the parenthesis first. Since there is no package > specification there, the interpreter assumes we are talking > about 'EXPR INT'. Then it applies the coercion from 'EXPR INT' > to 'DMP([x], EXPR INT)' which simply embeds the expression > as a term of degree 0. I kind of agree with your explanation when using a package call (though the expression goes through FRAC POLY INT before reaching EXPR INT). But unfortunately, package call is no guarantee and the above is incomplete explanation (Hint: do the quizzes at bottom). Aside: Hyperdoc reports that DMP([x], EXPR INT) is an invalid type. (Type the domain in the search box, click Constructors, then click operations). Yet another inconsistency in the system. > Try this instead: > > (1) -> (2*x+1/x)$DMP([x], EXPR INT)
>
>              1
>    (1)  2x + -
>              x
>    Type: DistributedMultivariatePolynomial([x],Expression Integer)
>
> (2) -> monomials(%% 1)
>
>             1
>    (2)  [2x,-]
>             x
>    Type: List DistributedMultivariatePolynomial([x],Expression Integer)
>
> In this case we told Axiom to use only operations from the
> domain 'DMP([x], EXPR INT)'. It sees '2*x' and selects the
> '*' with signature '?*? : (Integer,%) -> %'. The result is
> a term of degree 1. Then it looks at '1/x' and selects
> '?/? : (%,Expression Integer) -> %'. The result is a term
> of degree 0.
>
> This also is correctly interpreted by Axiom. But these two
> expressions are not equivalent in this domain.

No, Axiom erred in performing a "coercion" from DMP([x], R) into R when
mathematically, it is clear that x does not belong to R. It should only coerce
from DMP([x],R) into POLY R or EXPR R.  You already agreed that the x should
mean the same mathematical object in the expression. Now look at this (I used UP
instead of DMP, but DMP would show almost the same except b would be in List
OVAR [x], and (7) would return 'false' (this is better, but in both the UP and
DMP cases, (6) and (7) should end in error. More of this later.)

(1) -> a:= (2*x+1/x)$UP(x, EXPR INT) 1 (1) 2x + - x Type: UnivariatePolynomial(x,Expression Integer) (2) -> b:=variables a (2) ["?"] Type: List SingletonAsOrderedSet (3) -> c:=coefficient(a, b, [0]) 1 (3) - x Type: UnivariatePolynomial(x,Expression Integer) (4) -> d:=retract(c)@(EXPR INT) 1 (4) - x Type: Expression Integer (5) -> e:=variables d (5) [x] Type: List Symbol So the two instances of 'x' are not treated as the same mathematical object or even the same computer object or variable. Indeed, in Axiom, they live in two different domains! So Axiom did not interpret the two x's consistently. Warning, do not let (6) -> t:Boolean:=(b.1=e.1) (6) true Type: Boolean deceive you into thinking the two variables are the same. The Interpreter actually tried very hard to please you (too bad, it shouldn't, and should have complained that there is no = function that is applicable; we are testing equality, and the Interpreter should not perform ANY coercion in equality tests because then equality test in the Interpreter are no longer predictable without a deep understanding of how the Interpreter works). Just )set mess bot on before (6) to see (its too long to reproduce here). Moreover, this may or may not surprise you: (7) -> s:Boolean:=(b.1=(y::Symbol)) (7) true Type: Boolean This is not a surprise at all. You see, b.1 is simply a place holder ? and it can match ANY symbol. The type of b indicates NOTHING about x. The Interpreter went through the same set of coercions as for (6) to say, "Ah-ha, I found a common domain where they can be equal. I don't care what the user meant!" (BTW, the domain is UP(y, INT)). As mentioned, the case for DMP is better handled, in which case the type of b, List OVAR [x], does indicate x. Would you have guessed from what common domain is the equality test function taken? > > > > However, I think Axiom is wrong in allowing that, since x, > > being an indeterminate over EXPR INT, should not be in > > EXPR INT. > > I suppose what you are saying is that the ring over which > DMP is defined should not be 'EXPR INT' but rather > 'SubDomain(EXPR INT, not member?(x::Symbol,variables(#1))'. No, that is not the same. The above still accepts that the two x are the same and this is mathematically incorrect. You can have a different x in EXPR INT, and you can substitute DMP-x for EXPR-x, but they are different. DMP-x is transcendental over EXPR INT whereas EXPR-x is in the field. > This is a possible definition but it seems unnecessarily > complicated. Further it would explicitly prevent the kind > of coercion that Axiom was apparently carefully designed > to do (see below). Quite the contrary. There ARE legitimate use of these construction and they ARE used in the Axiom library. Just to give you an example, SUP in idecomp.spad IdealDecompositionPackage(vl,nv) : C == T -- take away nv, now doesn't -- compile if it isn't there where vl : List Symbol nv : NonNegativeInteger Z ==> Integer -- substitute with PFE cat Q ==> Fraction Z F ==> Fraction P P ==> Polynomial Z UP ==> SparseUnivariatePolynomial P Expon ==> DirectProduct(nv,NNI) OV ==> OrderedVariableList(vl) SE ==> Symbol SUP ==> SparseUnivariatePolynomial(DPoly) DPoly1 ==> DistributedMultivariatePolynomial(vl,Q) DPoly ==> DistributedMultivariatePolynomial(vl,F) Axiom actually allows other ways to add new indeterminates to a domain that already uses Symbol as the set of indeterminates, by using a direct product of say NNI to the existing EXPON, for example (see definition of POLYCAT and gbintern.spad for such use). These towers are needed and as far as I can tell, the Axiom compiler handles them perfectly. Any confusion is caused by "features" in the Interpreter. The Interpreter is, unfortunately, a main reason why the learning curve for Axiom is so steep. I don't think to understand that indeterminates are transcendentals is too complicated, or an x in one expression must mean the same mathematical object throughout. These are the only two principles I used. > There is no danger that Axiom will confuse the two uses of > 'x' and to the user this result looks perfectly reasonable - > it looks like just a different way of formatting the > expression - but of course as "advanced users" we know the > difference is more subtle than that. Axiom does confuse the users by performing a substitution for one x and not the other, thus splitting one x into two. If you goal is to reformat the expression, then reformat it entirely within EXPR INT (that is, create a "reformat" command that does that by walking a parse tree for the expression, or create extraction functions similar to univariatePolynomial in UPS that extracts only monomial terms from a sum of terms). > >The coercion should simply fail, or end up in > > FRAC DMP([x], EXPR INT). > > I do not see how it could possibly end of in > 'FRAC DMP([x], EXPR INT)' in either version of (1) above. If x is to be the variable in DMP, then 1/x needs to be in FRAC DMP. x is a transcendental over EXPR INT and should not and cannot be interpreted as ALSO in EXPR INT. The design to allow Symbol as the set of variables in POLY or EXPR is ingenious in concept and gives Axiom its power to program categorically without hardcoding any predefined finite set of symbols. Users should not equate this to mean no other indeterminates can be constructed over POLY INT or EXPR INT. In fact, EXPR was constructed over as the quotient field of a polynomial ring where indeterminates are kernels. > > Note that even if the following is used, Axiom continues to > > "retract" the x from 1/x to EXPR INT. This is simply wrong. > > > > x:DMP([x], EXPR INT):=x > > 2*x + 1/x > > degree(%) > > [1] > > > > It is not wrong. No, you are wrong. The Interpreter performs a mathematically unwarranted coercion (via a substitution). If the Interpreter is allowed to reinterpret an identifier that I explicitly declared and defined, and coerce an element into a ring that the element should not belong to in the mathematical sense, how can I predict what subsequent computations will be? If a user does not declare the type, yes, the Interpreter would be given the freedom to coerce; otherwise, it should coerce only with specific directives from the user, or when it is mathematically correct to do so. > I agree that it might be unexpected if > one does not keep in mind the domains from which Axiom will > select functions. One might (incorrectly) thought that the > 1/x must be evaluated in 'FRAC DMP([x],EXPR INT)' Expecting that 1/x must be evaluated in FRAC DMP is the ONLY mathematically reasonable expectation when x is the indeterminate in DMP and therefore NOT a member of its coefficient domain. > but once > again Axiom first considers the '/' function defined in > domain that it already knows: 'DMP([x],EXPR INT)' before it > attempts anything more complex. The error is not in using '/' from DMP but in making an unwarranted and wrong *substitution*. Indeed, the sequence to parse the expression 2*x + 1/x, as you noted, is (skipping some obvious ones): 2*x is in DMP 1, don't know yet x, is in DMP / is a function to be looked up Ok, I can coerce 1 to be in DMP as its unit Ooops, I can't find a / in DMP with signature (%,%)->% But there is a / in DMP([x], EXPR INT) with signature (%, EXPR INT)->EXPR INT (because EXPR INT has FIELD) Ah ha, I'll coerce the denominator into EXPR INT -- wrong step! As explained in my previous email, this coercion is a *substitution* and is wrong because there should not be a *coercion* from DMP([x], EXPR INT) to EXPR INT; there is only a *retractIfCan*. I repeat: 'x' is transcendental over EXPR INT and should not and cannot be in EXPR INT. This total disregard of what x is, is a bug, and demonstrates inconsistency in the Interpreter. In the above setup, (1/x)*x is not 1 so the denominator x is coerced to EXPR INT, but the other x is not. This can cause other problems: \begin{axiom} )clear all y:=DMP([x], EXPR INT):=x z:=1/y w:=1/z t:Boolean:=w=y \end{axiom} If you consider this is not a bug, I don't know what is. Of course, I know how this came about. If z had been computed in FRAC DMP([x], EXPR INT), as it should, this problem would not be there. > It discovers that it can > evaluate 1 in 'DMP([x],EXPR INT)' and that since 'x' is a > variable of type 'DMP([x],EXPR INT)', it knows that it can > always coerce such polynomials into 'EXPR INT'. This allows > it to apply the operator '/' from 'DMP([x],EXPR INT)'. This is not the whole story as indicated above. The 'x' is a polynomial, but in this case, it is mathematically incorrect to "coerce" it into the coefficient domain, even if it happens to be EXPR INT. Moreover, selective substitution is another evil here (substituting one x and not the other). > > On the other hand, the following is correct, and should > > be the case no matter what the coefficient domain is. > > > > y:DMP([y], INT):=y > > 2*y+1/y > > > > 2 > > 2y + 1 > > ------- > > y > > Type: Fraction > > DistributedMultivariatePolynomial([y],Integer) > > > > The two cases should not be handled differently. > > I agree that this result is correct but I disagree that > these two cases can be handled the same way (i.e. by > selecting the '/' operation in 'DMP([y], INT)'. This is > not possible because Axiom cannot coerce polynomials of > type 'DMP([y], INT)' into 'INT'. Neither should Axiom coerce polynomials of type DMP([y], R) into R for ANY R. Bill, Axiom is to model mathematics, *categorically*. It is allowed that a different algorithm is used by tapping into the properties of the coefficient domain, IF THEY PRODUCE THE SAME RESULT (consistency). The alternative algorithm should not be allowed when it produces a different answer. Mathematically, if y is an element of an integral domain, then 1/y is its reciprocal in the quotient field and 1/(1/y) has to be y itself. The Axiom interpreter (not Axiom) fails in these examples to uphold a mathematical result. That is WRONG (even though it originates from user input error: expecting 1/x to be in DMP([x], EXPR INT) where x is not in EXPR INT). > > If a user wants to push the result down to the coefficient > > domain, it should be done with a substitution map, > > explicitly, and the user should not use x in EXPR INT. > > > > This sort of coercion is only possible when the coefficient > domain has 'PDRING Symbol' or at least 'PDRING OVAR vl' > where 'vl' is polynomial variable list. Apparently Axiom > attempts to use it during the function selection process. The Interpreter is designed to coerce polynomials over a ground ring R into EXPR over the SAME ground ring, and it is an oversight that it actually coerce polynomials over a ring R into R itself when R is EXPR INT. Had the Interpreter coerced 1/x into EXPR EXPR INT, in the example where x is in DMP([x], EXPR INT), that would be correct. But the Interpreter, unfortunately, does not allow EXPR EXPR INT. I failed to see why PDRING has anything to do with it. All you are saying is that if the coefficient domain does NOT have PDRING Symbol, etc, then the Interpreter will not produce the incorrect coercion, but it does -- see Quizzes. It should not matter whether the coefficient domain has millions of other properties or not. The Interpreter should not perform a *partial substitution* behind my back and call it *coercion*, and worse, by doing so it produces inconsistent results on a categorical level and is mathematically wrong. By the way, I don't think it is easy to fix this bug because it involves how deeply the Interpreter should try to coerce. My suggestion to users is: ignore these examples, don't use towers involving polynomial rings, and if you really need these tower constructions, don't do this in the Interpreter since you won't know what the consequence will be without wasting a lot of time (and we might still get it wrong). Here are some quizzes if you have read so far (it does not matter if you agree with me or not). Instructions: What is the output for each of the following? Do the problems only one at a time. You should write down your answer, its type, and with explanations and any expected error messages. Then check it (using )set mess bot off), revise your explanation if necessary, or explain Axiom's output. Finally, use )set mess bot on to see exactly what the Interpreter did. Then and only then, advance to the next problem. Just in case: the function 'variables' returns a list of the variables occurring in the argument. )set mess bot off -- no cheating (1) variables (2*x+1/x)$DMP([x], EXPR INT)

(Got you, right? It got me too. To understand this, repeat with )set mess bot
on. You must understand what the Interpreter was doing before starting quiz (2))

)set mess bot off
(2) variables (2*y+1/y)$DMP([y], INT) (Got me again! Repeat with )set mess bot on, read carefully, and compare with that from (1)). )set mess bot off (3) a:=(2*x + 1/x)$DMP([x], EXPR INT);
variables a

)set mess bot off
(4) b:=(2*y+1/y)\$DMP([y], INT);
variables b

)set mess bot off
(5) x:DMP([x], EXPR INT);
variables (2*x+1/x)

)set mess bot off
(6) y:DMP([y], INT);
variables (2*y+1/y)

For your convenience, the quizzes have been set up at SandBox Polynomials.
Solutions are at SandBoxPolynomialQuiz and you can enter your insights at
SandBoxPolynomialQuizExplained.

Have fun. If you got all 6 perfectly, you are a "guru", congratulations, and let
us know (so we know whom to ask questions next time :-) (Actually, I do have a
few related to these quizzes, but rather than scratching my head again, I'll
wait for the "guru"s to tell me.)

William