[Octave-bug-tracker] [bug #53013] Comparison of complex values 2

[Michael Leitner]

Follow-up Comment #4, bug #53013 (project octave):

I want to maintain that, from the point of view of abstract mathematics, an
order relation is just a binary relation with specific properties. That is,
you could define your own order on, e.g., the real numbers which is equivalent
to the conventional order with the exception that 5<=x for all positive x.
That's a perfectly valid order, every sorting algorithm would happily sort
your numbers according to this order (5 would come before 3, if both are in
your input data, but that's consistent), and when you perform unique(), you
would get exactly the same unique elements as with every other order relation
(only in a different order, of course). 

Naturally, there is not much reason why anyone would want to define such an
order, because there is a natural order on the real numbers that follows from
the order on the natural numbers (which naturally derives e.g. from the Peano
construction) and that fulfills the laws how arithmetic operations affect
order (e.g. a<b <=> a+c<b+c). 

So it is possible to extend this order relation all the way from the naturals
to the integers to the rationals to the real numbers, fulfilling said laws.
However, it is not possible to extend it to the complex numbers: consider the
law that a>b => (a* c>b* c if c>0 and a* c<b* c if c<0). Assume b=0, a=i and
c=i. If we choose i>0, then we have a>0, but we have a* c=i* i=-1, which would
also need to be greater than zero because c>0, which is a contradiction. See
also https://proofwiki.org/wiki/Complex_Numbers_cannot_be_Totally_Ordered
(where the title is misleading, there is just no ordering compatible with the
multiplication law).

This is the reason that you often find "you cannot compare complex numbers for
order" when you search for it. That's nonsense, of course you can, you could
also define an order on the set {"Mickey", "Donald"} by setting
"Mickey"<"Donald". Then you have a<b iff a=="Mickey" and b=="Donald". Octave
wants to have a total order on the complex numbers, which I accept, because it
allows for the standart implementation of unique() to directly work on complex
values.

But for defining an order relation on the complex numbers, some choices have
to be made, corresponding to which laws of ordering relations under arithmetic
operations should be conserved. And, by the way: "total order" means that if
a!=b we have either a<b or b<a. This is what we want, and by the way what
Matlab according to their documentation does not do, as they compare only the
real part (i.e., neither 1<1+1i nor 1>1+1i should evaluate to true, and of
course also not 1==1+1i). 

There seem to be two main contenders: either lexicographic order, where a<b ==
(real(a)<real(b))||((real(a)==real(b))&&(imag(a)<imag(b))), or abs-based
order, where a<b == (abs(a)<abs(b))||((abs(a)==abs(b))&&(arg(a)<arg(b))). 
I argue for lexicographic order, because this keeps the law a<b <=> a+c<b+c
for any a,b,c, and further because it allows Octave's narrowing operation
(that is, seeing a complex number with zero imaginary part as a real number)
to be an order embedding https://en.wikipedia.org/wiki/Order_embedding.
Indeed, there is even a trivial arxiv paper on it
https://arxiv.org/abs/1003.4906 -- I did not check it in detail, but its main
claims seem valid. Under abs-based order, this is no order embedding. I find
this problematic, because it can lead to subtle bugs, when a few entries in a
large vector become complex and thus completely change the ordering relations
on it.

Let's see how other environments to it:
Octave, as we all know, uses abs-based order.
Matlab is inconsistent, it uses abs-based order for sort, max and min, but
compares only the real part (that is, not even lexicographic order) when < or
> is evaluated directly.
R, according to comment 15 on bug #52919, uses lexicographic order.

All the other environments I could think of that define complex numbers
refrain from defining an order, including Fortran, C, C++ and Python. That's
actually what I would do also, so that programming errors that lead to complex
values where there should be none raise errors sooner, and if anybody wants to
actually compare or sort complex values, to do it explicitly.

As to the comments: Michael Godfrey, both in this thread and in bug #52919 you
seem to be much in favour of abs-based order, commenting on R using
lexicographic order as "Looks like they have not given it much thought".
Perhaps R inherited it just from S, as Octave inherited a host of decisions
from Matlab, but I have to admit that I also seem to have given it not much
thought as I fail to see why it should be obvious that lexicographic sorting
can only be chosen due to lack of thought. Further, you postulate "For complex
the ordering is a measure of distance in the complex plane" (here should be
inserted "distance from zero", as the distance from any other point would also
give a perfectly well-defined ordering relation). But this postulate implies
already the solution: of course, when you want to order by the distance from
zero, you do arg-based sorting. My point is that "the order of any two complex
numbers is inherited from the order of the nearest real numbers" is an equally
valid postulate. What we want to do here is to collect arguments for both
possibilities. And how Knuth would sort complex values is beside the point, of
course he would sort them as he orders them (I would actually expect him to
discuss sorting algorithms only in terms of generic sets with total order). So
we are back at having to deliberate which identities we want our order to
fulfill.


    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?53013>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/