Fix snf_with_transform issue over non-domain

[fingolfin]

See oscar-system/Oscar.jl#4293

Can't really test this here as the linked example requires code from Nemo and Hecke.

[codecov]

Codecov Report

All modified and coverable lines are covered by tests ✅

Project coverage is 88.16%. Comparing base (3ed3ea9) to head (cd154a2).
Report is 5 commits behind head on master.

Additional details and impacted files

@@           Coverage Diff           @@
##           master    #1899   +/-   ##
=======================================
  Coverage   88.16%   88.16%           
=======================================
  Files         120      120           
  Lines       30291    30291           
=======================================
  Hits        26706    26706           
  Misses       3585     3585           

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

[fingolfin]

Just to explain, this tries to compute "the" lcm of two values a and b where d is the gcd, by doing (a*b)/d, which I change to a*(b/d).

This makes a difference if there are zero divisors, e.g. in $\mathbb{Z}/8\mathbb{Z}$ if $a=b=4$ then $d=4$, then $(a\cdot b)/d = 0$, while $a\cdot(b/d) = 4$.

[fieker]

On Tue, Nov 12, 2024 at 12:13:23AM -0800, Max Horn wrote: @fingolfin commented on this pull request. > @@ -5285,7 +5285,7 @@ function snf_kb!(S::MatrixElem{T}, U::MatrixElem{T}, K::MatrixElem{T}, with_traf K[r, j] = reduce!(t1 + t2) end end - S[j, j] = divexact(S[i, i]*S[j, j], d) + S[j, j] = S[i, i]*divexact(S[j, j], d) Just to explain, this tries to compute "the" `lcm` of two values `a` and `b` where `d` is the gcd, by doing `(a*b)/d`, which I change to `a*(b/d)`. This makes a difference if there are zero divisors, e.g. in $\mathbb{Z}/8\mathbb{Z}$ if $a=b=4$ then $d=4$, then $(a\cdot b)/d = 0$, while $a\cdot(b/d) = 4$.

Good catch - but not enough. Division here is non-unique, so it has to be avoided... One can show, and thats why we have the xxgcd (somewhere) that if (a,b) (e x; f y) = (g, 0) the full 2x2 cofactor matrix, then l = ax is (an) lcm, as is by ans both are without the non-unique division. I think the fix works here as Z/nZ is still well behaved, by accident..

…

-- Reply to this email directly or view it on GitHub: #1899 (review) You are receiving this because you are subscribed to this thread. Message ID: ***@***.***>

[joschmitt]

I think I wrote this function (like > 5 years ago as a HiWi) and I never had zero-divisors in mind. The signature is not more restrictive because we don't have an "euclidean domain supertype" or something like this, if I remember correctly.

I never thought about what is mathematically required to have an SNF, but I am fairly certain that this function assumes euclidean domain or at least PID. It certainly is suspicious that it calls HNF which does not always do the right thing over non-domains (and that's why we have a Howell form these days).

[thofma]

I am tempted to just require is_domain_type(T).

[fieker]

On Tue, Nov 12, 2024 at 01:03:24AM -0800, Tommy Hofmann wrote: I am tempted to just require `is_domain_type(T)`.

No, we need it for Z/nZ as well as (eventually) for ZK/I and others.

…

-- Reply to this email directly or view it on GitHub: #1899 (comment) You are receiving this because you commented. Message ID: ***@***.***>

[fieker]

On Tue, Nov 12, 2024 at 12:44:31AM -0800, Johannes Schmitt wrote: I think I wrote this function (like > 5 years ago as a HiWi) and I never had zero-divisors in mind. The signature is not more restrictive because we don't have an "euclidean domain supertype" or something like this, if I remember correctly. I never thought about what is mathematically required to have an SNF, but I am fairly certain that this function assumes euclidean domain or at least PID. It certainly is suspicious that it calls HNF which does not always do the right thing over non-domains (and that's why we have a Howell form these days).

No, for the SNF you don't need the Howell form, the HNF is just fine here. The "only" issue here is in the final division. I don't know if we want a function gcd_lcm(a,b) -> g, l or use the xxgcd and work with that. Eveltually we'll have to switch to using and supporting the xxgcd as I do not really see how to avoid it in general.

…

-- Reply to this email directly or view it on GitHub: #1899 (comment) You are receiving this because you commented. Message ID: ***@***.***>

[thofma]

When I mean requiring is_domain_type(T), I was mainly referring to this specific implementation. We definitely should have a Smith normal form implementation for "arbitrary" PIRs.

[fingolfin]

In the meantime, anything speak against merging this? I mean if somebody wants to restrict this code or something else, fine by me, but in the meantime I see no downside?

[thofma]

I guess it's fine, although I don't understand why it works for anything else except for this specific example.