[PATCH] changes to "smaller?" in Fraction

[Qian Yun]

Very likely this patch needs further revision.

But I'm posting it here for discussion.

Notes on the patch:

1. Current order in Localize does not make sense.
So I removed the export and implementation.

2. I add the implementation to LocalAlgebra instead.

3. For "<" in QuotientFieldCategory, the implementation
depends on Rep, whether the Rep is normalized.

4. For "smaller?" in QuotientFieldCategory, if "<"
exists, use that instead. This is needed, otherwise
a test in ncalg.input fails. I suspect somewhere
in the factoring code, it needs OrderedSet but only
Comparable is provided.

5. This changes the ordering in Kernel and EXPR.
I think there is agreement that this change of ordering
will not cause unsoundness in computation in EXPR?

To recap:

If R has OrderedSet, then FRAC R has OrderedSet
if R has OrderedSet, then SMP R has OrderedSet

But Complex INT only has Comparable, not OrderedSet.

So for current implementation, smaller?$(Rep of EXPR INT)
is a total order, but for EXPR COMPLEX INT, it's not.

This patch changes to lexicographical order.

6. Thoughts on OrderedSet and Comparable.

If a domain says it has OrderedSet, it means "natural order
on given structure". It should further state that
it is OrderedSemiGroup or OrderedAbelianGroup.

For Comparable, it could be tricky to define "smaller?".
For Q[sqrt(-5)], it is INTDOM, but not GCDDOM, and not OrderedSet.
So no canonical representation.

The lexicographical order doesn't work strictly, for example
a/b and c/d where ad=bc but a~=c.

In theory Q[sqrt(-5)] can be totally ordered, using cantor
diagonal method and crossing duplicates.

But that can not be turned into an algorithm.

I suggest this point of view:
take a list of N elements of R, making it a set by removing
duplicates (for example by N(N-1)/2 "=" comparisons).

Then "smaller?" (the lexicographical order) is a total order
for this list/set.

- Qian

[Waldek Hebisch]

On Sat, Jul 04, 2026 at 06:19:16PM +0800, Qian Yun wrote:
> Very likely this patch needs further revision.
>
> But I'm posting it here for discussion.
>
> Notes on the patch:
>
> 1. Current order in Localize does not make sense.
> So I removed the export and implementation.

AFAICS you only removed implementation. You should also remove
the export.

> 2. I add the implementation to LocalAlgebra instead.

That looks resonable. I wonder if we should insist on having
positive denominators. We can ensure this when ring is an
ordered ring, that would save comparison of denominator with 0.

> 3. For "<" in QuotientFieldCategory, the implementation
> depends on Rep, whether the Rep is normalized.
>
> 4. For "smaller?" in QuotientFieldCategory, if "<"
> exists, use that instead. This is needed, otherwise
> a test in ncalg.input fails. I suspect somewhere
> in the factoring code, it needs OrderedSet but only
> Comparable is provided.

I think it should be done a bit different. 'has' tests at
runtime have costs, so it is more efficient to store result
in a variable and test the variable inside the function.
Or provide conditional implementation.

You removeconditional export of OrderedSet. But I think we should
conditionally export OrderedRing and possibly remove export of
OrderedIntegralDomain. Why? Only few domains have
OrderedIntegralDomain and it really does not give more information
than Join(OrderedRing, IntegralDomain). But Spad compiler will
_not_ infer OrderedIntegralDomain knowing that domain have
OrderedRing and IntegralDomain. So we need rules for propagation
of OrderedRing (and of course IntegralDomain), but
OrderedIntegralDomain is of limited use.

> 5. This changes the ordering in Kernel and EXPR.
> I think there is agreement that this change of ordering
> will not cause unsoundness in computation in EXPR?
>
> To recap:
>
> If R has OrderedSet, then FRAC R has OrderedSet
> if R has OrderedSet, then SMP R has OrderedSet
>
> But Complex INT only has Comparable, not OrderedSet.

To say the truth we should only export Comparable in
cases when S has OrderedSet or fractions are canonical.
Unfortunately, it is easy to make Fraction(Complex(Integer))
cononical, but it is problematic to write correct condition
("S is Complex(Integer)" is not allowed in export part).

> So for current implementation, smaller?$(Rep of EXPR INT)
> is a total order, but for EXPR COMPLEX INT, it's not.
>
> This patch changes to lexicographical order.

When using canonical representation lexicographical order
is a linear order. Without canonical representation
order is not well defined.

> 6. Thoughts on OrderedSet and Comparable.
>
> If a domain says it has OrderedSet, it means "natural order
> on given structure". It should further state that
> it is OrderedSemiGroup or OrderedAbelianGroup.

I do not think so. Look at ReverseOrderInteger that I included
in replay to Ralf. The order is natural for purpose of
sorting, but the domain is not OrderedRing.

So OrderedSemiGroup says more than Join(OrderedSet, SemiGroup).
OTOH OrderedIntegralDomain is exactly the same as Join(OrderedRing,
IntegralDomain), so is redundant.

> For Comparable, it could be tricky to define "smaller?".
> For Q[sqrt(-5)], it is INTDOM, but not GCDDOM, and not OrderedSet.
> So no canonical representation.

Actually the solution is the same as for expression: remove
irrationalities from denominator. Our trouble is that
we can write is as SAE(FRAC(INT), ..., ...) or as
FRAC(SAE(INT, ..., ...)). The second variant currently does
not have canonical representation. OTOH
Localize(SAE(INT, ..., ...), INT) could be made canonical,
but we lack apropriate function and conditions.

> The lexicographical order doesn't work strictly, for example
> a/b and c/d where ad=bc but a~=c.
>
> In theory Q[sqrt(-5)] can be totally ordered, using cantor
> diagonal method and crossing duplicates.
>
> But that can not be turned into an algorithm.
>
> I suggest this point of view:
> take a list of N elements of R, making it a set by removing
> duplicates (for example by N(N-1)/2 "=" comparisons).
>
> Then "smaller?" (the lexicographical order) is a total order
> for this list/set.

That looks like well known (and extremaly inefficient) method of
forcing canonical representation.

> diff --git a/src/algebra/fraction.spad b/src/algebra/fraction.spad
> index 499616eb..cee6f9e9 100644
> --- a/src/algebra/fraction.spad
> +++ b/src/algebra/fraction.spad
> @@ -36,11 +36,6 @@ Localize(M : Module R,
> x = y == y.den*x.num = x.den*y.num
> numer x == x.num
> denom x == x.den
> - if M has OrderedAbelianGroup then
> - x < y ==
> --- if y.den::R < 0 then (x, y) := (y, x)
> --- if x.den::R < 0 then (x, y) := (y, x)
> - y.den*x.num < x.den*y.num
> x+y == [y.den*x.num+x.den*y.num, x.den*y.den]
> n*x == [n*x.num, x.den]
> r*x == if r = x.den then [x.num, 1] else [r*x.num, x.den]
> @@ -77,6 +72,11 @@ LocalAlgebra(A : Algebra R,
> 1 == 1$A / 1$R
> x : % * y : % == (numer(x) * numer(y)) / (denom(x) * denom(y))
> characteristic() == characteristic()$A
> + if A has OrderedRing then
> + x < y ==
> + ((denom x)::A > 0) = ((denom y)::A > 0) =>
> + denom(y) * numer(x) < denom(x) * numer(y)
> + denom(y) * numer(x) > denom(x) * numer(y)
>
> )abbrev category QFCAT QuotientFieldCategory
> ++ Author:
> @@ -106,7 +106,6 @@ QuotientFieldCategory(S : IntegralDomain) : Category ==
> if S has RetractableTo Integer then
> RetractableTo Integer
> RetractableTo Fraction Integer
> - if S has OrderedSet then OrderedSet
> if S has Comparable then Comparable
> if S has OrderedIntegralDomain then OrderedIntegralDomain
> if S has RealConstant then RealConstant
> @@ -169,13 +168,11 @@ QuotientFieldCategory(S : IntegralDomain) : Category ==
> convert(x : %) : Float == (convert numer x) / (convert denom x)
> convert(x : %) : DoubleFloat == (convert numer x) / (convert denom x)
>
> - if S has OrderedSet then
> - x : % < y : % ==
> - (numer x * denom y) < (numer y * denom x)
> -
> if S has Comparable then
> smaller?(x : %, y : %) ==
> - smaller?(numer x * denom y, numer y * denom x)
> + % has OrderedSet => x < y
> + denom(x) = denom(y) => smaller?(numer(x), numer(y))
> + smaller?(denom(x), denom(y))
>
> if (S has EuclideanDomain) then
> fractionPart x == x - (wholePart(x)::%)
> diff --git a/src/input/rsimp.input b/src/input/rsimp.input
> index 5a4b2f44..50440eca 100644
> --- a/src/input/rsimp.input
> +++ b/src/input/rsimp.input
> @@ -39,10 +39,10 @@ testEquals("rs3a", "sqrt(3)::eI*(sqrt(6) + 3)/3")
>
> w4 := 28*11^(1/2)*15^(1/2)+497
> -- Need subst, otherwise square root would mangle the argument
> -a7715 := subst(a^(1/2), [a = 77/15])
> +a28 := subst(a^(1/2), [a = 28])
> rs4 := ratDenom(rsimp(sqrt(w4)))
> testEquals("w4 - rs4^2", "0")
> -testEquals("rs4", "(30*sqrt(11)::eI + 11*sqrt(15))*a7715/11")
> +testEquals("rs4", "(2*sqrt(15)::eI + sqrt(11))*a28/2")
>
> w5 := 16 - 2*sqrt(29) + 2*sqrt(55 - 10*sqrt(29));
> rs5 := rsimp(sqrt(w5))
> @@ -90,10 +90,9 @@ testEquals("w12 - rs12^5", "0")
> testEquals("rs12", "(3*sqrt(2) + 2*sqrt(3))*a544/2")
>
> w13 := 7*(2*sqrt(3) - sqrt(11))^6
> -a12096_1331 := subst(a^(1/6), [a = 12096/1331])
> rs13 := rsimp(w13^(1/6))
> testEquals("w13 - rs13^6", "0")
> -testEquals("rs13", "(6*sqrt(11) - 11*sqrt(3))*a12096_1331/6")
> +testEquals("rs13", "7^(1/6)*(sqrt(11)-2*sqrt(3))")
>
> w14 := 19*(5*sqrt(2) - sqrt(7))^7
> rs14 := rsimp(w14^(1/7))


--
Waldek Hebisch

[Qian Yun]

On 7/5/26 2:43 AM, Waldek Hebisch wrote:
>
>> 2. I add the implementation to LocalAlgebra instead.
>
> That looks resonable. I wonder if we should insist on having
> positive denominators. We can ensure this when ring is an
> ordered ring, that would save comparison of denominator with 0.

That is up to the details of representation. In Fraction
we can have this more efficient version.

>
> You removeconditional export of OrderedSet. But I think we should
> conditionally export OrderedRing and possibly remove export of
> OrderedIntegralDomain. Why? Only few domains have
> OrderedIntegralDomain and it really does not give more information
> than Join(OrderedRing, IntegralDomain). But Spad compiler will
> _not_ infer OrderedIntegralDomain knowing that domain have
> OrderedRing and IntegralDomain. So we need rules for propagation
> of OrderedRing (and of course IntegralDomain), but
> OrderedIntegralDomain is of limited use.

Is this the same for OrderedMonoid? It doesn't add new axioms
to OrderedSemiGroup.

>
>> 6. Thoughts on OrderedSet and Comparable.
>>
>> If a domain says it has OrderedSet, it means "natural order
>> on given structure". It should further state that
>> it is OrderedSemiGroup or OrderedAbelianGroup.
>
> I do not think so. Look at ReverseOrderInteger that I included
> in replay to Ralf. The order is natural for purpose of
> sorting, but the domain is not OrderedRing.

Well, ReverseOrderInteger is still OrderedAbelianGroup.

>
>> For Comparable, it could be tricky to define "smaller?".
>> For Q[sqrt(-5)], it is INTDOM, but not GCDDOM, and not OrderedSet.
>> So no canonical representation.
>
> Actually the solution is the same as for expression: remove
> irrationalities from denominator.

This is an example to illustrate that we can not define "smaller?"
at category (QuotientFieldCategory) level, we have to know the
details of the domain representation.

>> In theory Q[sqrt(-5)] can be totally ordered, using cantor
>> diagonal method and crossing duplicates.
>>
>> But that can not be turned into an algorithm.
>>
>> I suggest this point of view:
>> take a list of N elements of R, making it a set by removing
>> duplicates (for example by N(N-1)/2 "=" comparisons).
>>
>> Then "smaller?" (the lexicographical order) is a total order
>> for this list/set.
>
> That looks like well known (and extremaly inefficient) method of
> forcing canonical representation.
>

This is basically what we did in SCACHE Kernel.
Also in Fractored where R is not even Comparable.

- Qian

[Waldek Hebisch]

On Sun, Jul 05, 2026 at 08:52:21AM +0800, Qian Yun wrote:
> On 7/5/26 2:43 AM, Waldek Hebisch wrote:
> >
> >> 2. I add the implementation to LocalAlgebra instead.
> >
> > That looks resonable. I wonder if we should insist on having
> > positive denominators. We can ensure this when ring is an
> > ordered ring, that would save comparison of denominator with 0.
>
> That is up to the details of representation. In Fraction
> we can have this more efficient version.

Representation is defined in Localize. It is natural to keep
things consistent in the inheritance chain. That IMO actually
is the main cost of positive denominators: we need to coordinate
a few domains.

> > You removeconditional export of OrderedSet. But I think we should
> > conditionally export OrderedRing and possibly remove export of
> > OrderedIntegralDomain. Why? Only few domains have
> > OrderedIntegralDomain and it really does not give more information
> > than Join(OrderedRing, IntegralDomain). But Spad compiler will
> > _not_ infer OrderedIntegralDomain knowing that domain have
> > OrderedRing and IntegralDomain. So we need rules for propagation
> > of OrderedRing (and of course IntegralDomain), but
> > OrderedIntegralDomain is of limited use.
>
> Is this the same for OrderedMonoid? It doesn't add new axioms
> to OrderedSemiGroup.

Yes, OrderedMonoid does not add new axioms. We should replace
it by Join(OrderedSemiGroup, Monoid)

> >> 6. Thoughts on OrderedSet and Comparable.
> >>
> >> If a domain says it has OrderedSet, it means "natural order
> >> on given structure". It should further state that
> >> it is OrderedSemiGroup or OrderedAbelianGroup.
> >
> > I do not think so. Look at ReverseOrderInteger that I included
> > in replay to Ralf. The order is natural for purpose of
> > sorting, but the domain is not OrderedRing.
>
> Well, ReverseOrderInteger is still OrderedAbelianGroup.

Yes.

> >> For Comparable, it could be tricky to define "smaller?".
> >> For Q[sqrt(-5)], it is INTDOM, but not GCDDOM, and not OrderedSet.
> >> So no canonical representation.
> >
> > Actually the solution is the same as for expression: remove
> > irrationalities from denominator.
>
> This is an example to illustrate that we can not define "smaller?"
> at category (QuotientFieldCategory) level, we have to know the
> details of the domain representation.

Yes.

> >> In theory Q[sqrt(-5)] can be totally ordered, using cantor
> >> diagonal method and crossing duplicates.
> >>
> >> But that can not be turned into an algorithm.
> >>
> >> I suggest this point of view:
> >> take a list of N elements of R, making it a set by removing
> >> duplicates (for example by N(N-1)/2 "=" comparisons).
> >>
> >> Then "smaller?" (the lexicographical order) is a total order
> >> for this list/set.
> >
> > That looks like well known (and extremaly inefficient) method of
> > forcing canonical representation.
> >
> This is basically what we did in SCACHE Kernel.
> Also in Fractored where R is not even Comparable.

Sure. For Kernel AFAICS assumption was that there are not many
kernels (and we have trouble when there are many). Fractored
IMO should be a niche.

--
Waldek Hebisch

[Qian Yun]

OK, after recent discussions on ordering, I plan to
do the changes to fraction.spad and expr.spad separately.

For ordering EXPR, I now agree that we should not assert
it to be Comparable. Because current ordering, or the
lexicographical ordering is not true total order
(for some a=b, one of smaller?(a,b) and smaller?(b,a) may
still return true).

So after removing Comparable from EXPR, we should give
"smaller?" a new name, how about "lex_smaller?"?

- Qian

[Qian Yun]

On 7/6/26 6:53 AM, Qian Yun wrote:
>
> For ordering EXPR, I now agree that we should not assert
> it to be Comparable. Because current ordering, or the
> lexicographical ordering is not true total order
> (for some a=b, one of smaller?(a,b) and smaller?(b,a) may
> still return true).
>
> So after removing Comparable from EXPR, we should give
> "smaller?" a new name, how about "lex_smaller?"?
>

Well, it turns out it is not practical to remove Comparable
from EXPR (ExpressionSpace2).

Simply removing the export will cause compilation failure
that I can not explain.

- Qian

[Waldek Hebisch]

I suspected such thing. In Kernel we use 'smaller?'. We may
rename it, but we need some ingredients to build it. Not
all domains provide needed ingredients, so we need
appropriate conditions. Currently this condition is
Comparable. Structure of FriCAS algebra is highly recursive,
so this condition must be propageted in coordinated way
between involved domains and categories. Net effect is
that as long as we want to use binary search for kernels
we need something like Comparable. It may have somewhat
different name and different meaning. But any argument
acceptable to Expression must provide it. Since we
use Expression(Expression(Integer)) Expression must
provide it. Due to how expression is build it must
propagate trough polynomials and fractions. And of
course kernels.

Let me repeat and amend slightly what I previously wrote.
AFAICS we have the following possibilities:
- try to make 'smaller?' well defined in expression by insisting
on canonical representation (in practice removing irrationalites
from denominators),
- do not depend on order when doing kernel searches. We can make
it a bit smarter, but it is not clear if we can be better than
linear search,
- say that current state of Comparable for Expression is the correct
one, that is 'smaller?' compares representations and may give
different results for different representatives. IIUC at some
point you proposed essenially this. This will need
correcting all places in algebra that assume that 'smaller?'
is mathematicaly well defined (that is independent of representative).

The second option is likely to lead to significantly worse
performance than what we have currently. As I wrote first one
may be acceptable performancewise if we transform arguments to
kernels when we insert them into cache. Removing irrationalites
from denominators on each comparison is likely to lead to much
worse performance. Third option allows current and proposed
performance improvements. But it requires ispection of other
uses of Comparable: use for printing would be OK, use in say
Factored would be highly suspect (almost surely wrong).

There is some chance that performace dilema that we have now
will be irrelevant in the future, when expression machinery
is reorganized. But I think that we should get consistently
working Expression before next release and deeper changes
are likely to happen later. So we should decide based on
current constraints.

--
Waldek Hebisch

[Qian Yun]

On 7/10/26 8:11 AM, Waldek Hebisch wrote:
> worse performance. Third option allows current and proposed
> performance improvements. But it requires ispection of other
> uses of Comparable: use for printing would be OK, use in say
> Factored would be highly suspect (almost surely wrong).
>

"smaller?" usage in code base related with EXPR:

rdeefx.spad, laplace.spad:

compare against 0, to put a "positive" expr under "sqrt".
I would classic this usage as "printing".
Similar situation goes for algfunc.spad.

elemntry.spad:

compare against 0, to put a "positive" expr under "exp".
Same goes for combfunc.spad.

oderf.spad:

sort to make sure 'log' comes after rational coefficients.

expexpan.spad:

situation is noted in comments.

fr.spad:

it is suspicious, but the new version of "smaller?" will
not be worse than the old one.


So we need to make sure "smaller?" to have the property of
symmetry around 0:

For all expr1 (which is not 0) that smaller?(0, expr1) is true,
smaller?(-expr1, 0) should be also true.

My proposed lexicographic ordering has this property.

- Qian