Comparision with < of rational functions is not transitive.

[fingolfin]

A report on GAP support lead to the following observation:

gap> t:=Indeterminate(GF(7), "t");;
gap> f1:=t^4+Z(7)^5*t^3+t^2+Z(7)^5*t+Z(7)^0;;
gap> f2:=(t^6+Z(7)*t^5-t^4+Z(7)^5*t^3+Z(7)^4*t^2+Z(7)^2*t+Z(7)^0)/(t^2+Z(7)^5*t+Z(7)^0);;
gap> f3:=t^4+t^2+Z(7)^0;;
gap> f1 < f2; f2 < f3; f1<f3;
true
true
false

The responsible function is SMALLER_RATFUN in ratfun1.gi.

The problem stems from that the fact that it tries to compare rational functions by multiplying out the denominators, while "avoiding" negative leading coefficients, i.e.

f/g  < u/v  <=>  fv < ug    if  v, g have "positive" leading coeffs.

But that breaks down in positive characteristic (and also for imaginary coefficients). Indeed, I am tempted to say "this cannot possibly work", simply because fields in positive characteristic, or which contain non-real complex values are non-orderable.

It seems to me the above relies on the following supposed "property" of the ordering:

 0 < d  and f < g   =>   f*d < g*d

but the ordering as implemented by SMALLER_RATFUN simply does not have this property, as this example shows:

gap> t:=Indeterminate(GF(7), "t");;
gap> f:=t+Z(7)^5;; g:=t;;
gap> d:=t^2+Z(7)^5*t+1;;
gap> 0*d < d;
true
gap> f < g;
false
gap> f/d < g/d;
true
gap> d*f<d*g;
true

A similar example with imaginary coefficients in char 0:

gap> x:=Indeterminate(Cyclotomics, "x");;
gap> f:=x+E(4);; g:=x;;
gap> d:=x^2-E(4)*x+1;;
gap> 0*d < d;
true
gap> f < g;
false
gap> f/d < g/d;
true
gap> d*f < d*g;
true

To my surprise, it even fails with integer coefficients, but in an inconsistent way (compare the two last computations, which surprisingly return different results):

gap> x:=Indeterminate(Cyclotomics, "x");;
gap> f:=x+1;; g:=x;;
gap> d:=x^2-x+1;;
gap> 0*d < d;
true
gap> f < g;
false
gap> f/d < g/d;
true
gap> d*f < d*g;
false

[hulpke]

@fingolfin Yes, this is a bug (in code I wrote almost 20 years ago). What I remember is that I tried to mimic the behavior for the equality test and was hoping the total orderings on each field would carry through appropriately to finite fields.

What makes the comparison a pain is that rational functions are not guaranteed to be represented in cancelled form (as we did not have a multivariate GCD when the code was written), so one cannot just rely on some arbitrary lexicography on coefficient lists.

Naively, my attempt for fixing it would be to replace the avoid negative denominator withscale the denominator to have leading coefficient 1, but having been wrong on this before I'd like a second opinion.

[fingolfin]

In the "counterxamples" I provided, the leading coefficient is already 1 for all polynomials.

[fingolfin]

For your convenience, here is a smaller test case:

gap> t:=Indeterminate(GF(7), "t");;
gap> f1:=t^2+4*t+1;;
gap> f2:=(t^4+3*t^3)/(t^2+3*t+1);;
gap> f3:=t^2+t+1;;
gap> f1 < f2; f2 < f3; f1<f3;
true
true
false

[fingolfin]

And to underline my claim that it is impossible to make this technique work in general, even in characteristic 0, here is an example over the Gaussian rationals:

gap> x:=Indeterminate(Rationals, "x");;
gap> f1 := x^2 + E(4)*2;;
gap> f2 := (x^4+5) / (x^2-2*E(4));;
gap> f3 := x^2 + (E(4)-1);;
gap> f1 < f2; f2 < f3; f1<f3;
true
true
false

The whole tricking with multipliying out denominators really requires the coefficient field to be orderable (i.e. in a fashion compatible with addition and multiplication), which simply is impossible for "most" fields.

[stevelinton]

Since we now have a multivariate Gcd, should we simply redefine the ordering to something based on the reduced form of the rational function (like by denominator, then by numerator). Are there any requirements on the ordering?

[frankluebeck]

I don't see a sensible "mathematical" definition here. I guess we need a normal form for rational functions. Once this is available one could define an ordering via lexicographic ordering of some serialization to a list of comparable things, say [characteristic, degree of denominator, ....., [exponent data for monomials], [coefficients]]

[stevelinton]

@frankluebeck I'm not sure we want comparison across characteristics at all -- hard to see when it ever really makes sense. Within a characteristic, the only thing is that we don't want to change the existing ordering for polynomials since that's unproblematic and people rely on it.

[fingolfin]

It may not make sense, but as long as GAP sets rely on arbitrary objects being comparable, shouldn't we take this into account?

The alternative would be to tell people that forming a set of polynomials in different characteristic is not supported, and will behave weirdly.

[stevelinton]

Section 4.12 in the reference manual. This is a question that was much discussed early in GAP4. I don't have any great problem with making rational functions comparable across characteristics, and perhaps comparable with their coefficient families, but whatever we do should be carefully documented in that section and checked for global consistency.

In GAP 3 basically every new class of object tried to make itself compare bigger than all other objects, with many paradoxical results.

[hulpke]

If we enforce a unique representation (which also gets around the problem that we do not guarantee that a (mathematical) polynomial is always represented as a (GAP) polynomial) for comaprison, then any arbitrary lexicography will work. I will not have any further meaning but that is fine.

Different characteristics are harmless, one could rely e.g. on comparison of the families (in fact the existing method assumes same families).

A potential problem is cost. The multivariate GCD is a Groebner basis calculation (yes one could store a ``reduced form'' to avoid repetition) and in the end few such calculations will in fact find a gcd.

If nobody else has a better idea, feel free to assign this to me in desperation, and I'll implement it over the summer.

[olexandr-konovalov]

@hulpke have you had any chance to look at this? Shall I assign this to GAP 4.9 to ensure that we keep an eye on this, or delay until 4.10 instead?

[fingolfin]

To bring some new life to this four year old issue... We really ought to resolve this before people produce wrong research results due to this.

Even if it means that comparing rational functions "properly" will be rather expensive in the general case.

After all, a fast but wrong comparison doesn't really help anybody, does it? Sure, we want it fast so that Set is fast when called on a list of rational functions. But since < is not transitive, it's not even clear to me that Set can return a list which is "sorted" in any meaningful sense... and even if, would e.g. binary search on such a list work?

In my examples, [f1, f2, f3] is "sorted" in the sense that each entry is greater than the one immediately before it; but not in the sense that each entry is greater than all entries before it. But the latter is required for IsSet according to its documentation. (Interestingly, the default function for testing for IsSet in the kernel, IsSSortListDefault, only compares adjacent elements; i.e., it implicitly relies on < being transitive; which seems reasonable, although I am not even sure whether we guarantee this anywhere in the documentation? We probably should, though).

Next, if one looks at [f1, f2], it is a set in both senses; but we can't extend it to a larger set by adding f3 to it in the second, stronger sense. But we can do it in the first, weaker sense, in two ways: [f1,f2,f3] but also [f3,f1,f2]. Which position should PositionSorted report?

Finally, because of all this, IsSet([f3,f1,f2,f3]) returns true, even though the given list clearly is not duplicate free.

So, in summary, lots of bad things can happen here.

Ping @ThomasBreuer whom I told about this issue earlier today.

[fingolfin]

BTW, we can of course perform the normalization only lazily, i.e., only if explicitly requested or needed, such as when comparing elements. In that scenario the rational function objects would change itself in-place to the normal form if asked to do so.

Or, if we want to avoid such in-place changes, it could have the normal form as an "attribute" (stored in a slot of the underlying positional object), and compute that only when needed.

[stevelinton]

@fingolfin I'd definitely recommend the attribute approach, but otherwise I agree normalisation is the only way to produce an ordering consistent with equality .

[hulpke]

Having the normal form as attribute also makes it easy to deal with the different representations.

[ChrisJefferson]

I hadn't realised how bad this is. I agree it's bad we didn't fix it ealier, and storing a normalised form seems like the most sensible option.

[wilfwilson]

I agree with the importance of this problem. However I wouldn't know where to start with implementing the solution.