# Smith normal form over GF(4) is sometimes incorrect on Mac OS

Reported by: Owned by: gh-DaveWitteMorris critical sage-duplicate/invalid/wontfix linear algebra jhpalmieri, malb John Palmieri N/A

### Description

This is split off from the discussion at #28944.

I am using a Python 3 build of 9.0 on Mac OS 10.15.1. The following code should always print True.

```M = random_matrix(GF(4), 100, 100)
for k in range(50):
S,U,V = M.smith_form()
print(S == U * M * V) # True
```

Instead, in any given run, I always get False at least a few times. And the loop usually does not get through the entire set of 50, because it is terminated by `NotImplementedError` (or, occasionally, a sage crash like the one reported in #28944). We are using the same matrix for the entire run, so the output should not be random.

@jhpalmieri reported in #28944 that he has seen this issue on OS X 10.14.6, but not on an Ubuntu virtual machine. It also did not show up in my limited testing on `CoCalc`. So (like #28944) this seems to be a Mac OS issue.

I do not see this problem when `GF(4)` is replaced with a different finite field. Fields of odd order do not seem to have any problems at all, but fields of characteristic 2 crash as reported for `GF(2)` in #28944.

I understand the superficial cause of the `NotImplementedError`, but not the underlying cause. The value of `t[0,0]` is always nonzero at the start of the following code snippet from the definition of `smith_form`.

```        # now recurse: t now has a nonzero entry at 0,0 and zero entries in the rest
# of the 0th row and column, so we apply smith_form to the smaller submatrix
mm = t.submatrix(1,1)
if transformation:
dd, uu, vv = mm.smith_form(transformation=True)
else:
dd = mm.smith_form(transformation=False)
mone = self.new_matrix(1, 1, [1])
d = dd.new_matrix(1,1,[t[0,0]]).block_sum(dd)
```

However, executing `mm.smith_form` sometimes changes the value of `t[0,0]`, so that `t[0,0]` is 0 in the definition of `d`. (In the cases where the value of `t[0,0]` is changed, it seems to always be changed to 0.) This 0 in the top left corner of `d` causes a `NotImplementedError`. (The patch in ticket #28967 eliminates the `NotImplementedError`, by providing a definition of `inverse_mod`, but the value returned by `smith_form` will be incorrect, because the value of `t[0,0]` is wrong.)

How can `mm.smith_form` be changing the value of `t`?

### comment:2 Changed 16 months ago by jhpalmieri

First, I asked about this on sage-devel, so we'll see if anyone can help. Second, I tried with some other fields: cardinality 2, 3, 4, 5, 8, and 9. I only see the problem with GF(4) or GF(8), although GF(9) is slow enough that I didn't want to try too many iterations. I wonder if there is some problem with `m4rie` on OS X. (I don't know anything about `m4rie` except that it does matrix manipulations over the fields `GF(2^k)` for `2 <= k <= 10`.)

### comment:4 Changed 16 months ago by dimpase

m4ri(e) now may come from "the system": https://trac.sagemath.org/ticket/28342

Do you build m4ri(e), or use one from Homebrew (or something like this)?

### comment:5 Changed 16 months ago by dimpase

Assuming you use Sage's m4ri(e): Try doing internal tests of m4ri and m4rie:

```SAGE_CHECK=yes ./sage -f m4ri
SAGE_CHECK=yes ./sage -f m4rie
```

and see whether you manage to get errors there.

### comment:6 Changed 15 months ago by jhpalmieri

I'm using Sage's m4ri and m4rie, and both pass their test suites. There are warnings in the log files, but nothing jumps out at me. For m4rie, I saw this:

```m4rie/strassen.c:52:7: warning: absolute value function 'abs' given an argument of type 'long' but has parameter of type 'int' which may cause truncation of value [-Wabsolute-value]
if (CLOSER(m, m/2, cutoff) || CLOSER(k, k/2, cutoff) || CLOSER(n, n/2, cutoff)) {
^
m4rie/strassen.c:31:29: note: expanded from macro 'CLOSER'
#define CLOSER(a,b,target) (abs((long)a-(long)target)<abs((long)b-(long)target))
^
m4rie/strassen.c:52:7: note: use function 'labs' instead
```

so I patched m4rie to change `abs` to `labs`. It didn't affect the behavior.

### comment:7 Changed 15 months ago by dimpase

Should be fixed by the new patch on #29026 Please verify it fixes the issue.

### comment:8 Changed 15 months ago by gh-DaveWitteMorris

Yes, #29026 got rid of the problem in my testing (like it did for #28944). I tried a few hundred times, and never got `False` or an error. Thank you!

### comment:9 Changed 15 months ago by jhpalmieri

• Milestone changed from sage-9.1 to sage-duplicate/invalid/wontfix
• Status changed from new to needs_review

Looks good to me, too. Let's close this as a duplicate of #29026.

### comment:10 Changed 15 months ago by jhpalmieri

• Reviewers set to John Palmieri
• Status changed from needs_review to positive_review

### comment:11 Changed 15 months ago by chapoton

• Resolution set to duplicate
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.