inconsistent semantics of gcd, lcm

[nsajko]

Regarding the greatest common divisor (GCD) and least common multiple (LCM), as binary operators, it seems that two incompatible meanings exist:

• The meaning used in Euclid's geometrical text (Elements), based on commensurability
  • An issue with this meaning, for Julian purposes, is that it's not defined when all arguments are zero.
  • As used, for example, here:
    • https://math.stackexchange.com/questions/151081/gcd-of-rationals
    • https://math.stackexchange.com/questions/122307/gcd-of-any-two-real-numbers
• A, more modern, abstract algebraic meaning
  • An issue with this meaning, for Julian purposes, is that the values are trivial for any field, such as the rational numbers, for example. Rational numbers are supported for Julia's gcd and lcm for a long time, and changes here would be breaking and quite disruptive.
  • As used, for example, here:
    • https://math.stackexchange.com/questions/85565/motivation-behind-the-definition-of-gcd-and-lcm
    • https://math.stackexchange.com/questions/4145760/gcd-of-rational-and-irrational-numbers
  • As used in the standard library of Fricas
    • the gcd defined for Euclidean domains seems incorrect for types that are not integers, such as fractions of integers fricas/fricas#183

@cyanescent and @barucden point out in #55379 and #56113 that:

• lcm is currently broken for arrays of nonintegral numbers
• the breakage stems from a faulty, non-identity, init argument to reduce (the lcm for array arguments is implemented in terms of reduce and the binary lcm)

@cyanescent further points out in the linked PR that perhaps a valid value for init doesn't exist. It seems to me that @cyanescent is correct and the attempt at supporting empty collections is misguided, because it corresponds to the second meaning above, while Julia otherwise uses the first meaning above.

The init arguments should be removed, I guess, while breaking support for empty arrays, as per @barucden's suggestion in the linked issue. I'll try to guide @cyanescent in forming their PR to fix this (mostly just tests are necessary). Also I guess a PkgEval will be necessary.

[fingolfin]

I am not quite sure what your concrete issue you are trying to report here beyond what is already in issue #55379? I.e. in other words: isn't this just a comment on that issue? If not perhaps you could clarify what the separate issue you are raising here is?

[nsajko]

That issue is about results that are unambiguously incorrect, while this issue is about a "minor change", that is, making the functions throw given empty argument, where a value had been returned in previous Julia versions.

[fingolfin]

I disagree that the results in the other issue are "unambiguously incorrect", because that would require comparing it to the specification for the expected output. But the Julia documentation for gcd and lcm is completely ambiguous. It does not state how gcd and lcm are defined for non-integer arguments, and there is no single accepted definition for that out there.

Indeed my personal main gripe with gcd and lcm in Julia is precisely that its documentation is insufficient. While for integers basically all definitions and implementations out there agree, this is not the case for rational arguments. The docstrings should really clarify what is computed.

Based on observation I think the rationale for the Julia behavior is to extend the "usual" definition of gcd for integers (where the "modern" mathematical definition is taken and turned unambiguous by agreeing that there unique non-negative gcd is the value to return, which agrees with the "classical" definition as well), so that gcd(a,b) == gcd(a//1,b//1) holds. Fair enough, but this should be documented then.

Afterwards we can debate whether some specific output is correct or not :-)

[fingolfin]

(Oh and array inputs are not documented at all, so correctness is even unclear)

[LilithHafner]

two incompatible meanings exist

Can you provide an example where the two definitions give different answers? Or where an answer is defined for one definition but not the other? AFAICT the definitions you are alluding to coincide when working over the rationals or the integers.

[nsajko]

Can you provide an example where the two definitions give different answers?

1. julia> gcd(3//7, 6//7)
   3//7

2. (2) -> gcd(3/7, 6/7)
   
      (2)  1
   

[LilithHafner]

Is this what you mean by definition 2?

d is a GCD of a and b if

• d divides both a and b; and
• If d′ also divides both a and b, then d′ divides d.

And

a divides b if there exists an integer n such that a*n = b

[cyanescent]

Giving up the "antic" definition of the gcd for rationals for the sake of a "universal" definition, designed for more abstract objects without ordering that are not implemented in base julia, and which considers as valid any other rational... feels like sabotage for unclear purpose.

Even if these integral domains were to be implemented in base julia, I don't see how this arbitrary init choice would end up having any usefulness here. The spirit of julia is multiple dispatch, so not breaking the simpler use-cases of the function when introducing more sophisticated ones. The result given by the "antic" definition is not even incompatible with the "universal" one!