Opened 13 years ago

Closed 3 years ago

# Add code to lift SLm(Z/NZ) to SLm(Z) (also for m not equal 2)

Reported by: Owned by: ncalexan was minor sage-8.2 number theory lift symplectic sl sl2 sl2z special linear ncalexan, mstreng, mmasdeu Nick Alexander, Frédéric Chapoton Vincent Delecroix N/A 0d26272 0d26272b81d7768c26650a6693d705449ec7e102

### Description

This is very handy in the theory of abelian varieties... here's some code to do it. Maybe someday I'll write the patch.

```def lift(A, N):
r"""
Lift a matrix A from SL_m(Z/NZ) to SL_m(Z).

Follows Shimura, Lemma 1.38, p21.

sage: N = 11
sage: A = matrix(ZZ, 4, 4, [6, 0, 0, 9, 1, 6, 9, 4, 4, 4, 8, 0, 4, 0, 0, 8])
sage: A.det()
144
sage: A.change_ring(Zmod(N)).det()
1
sage: L = lift(A, N)
sage: L.det()
1
sage: (L - A) * Mod(1, N) == 0
True

sage: N = 19
sage: B = matrix(ZZ, 4, 4, [1, 6, 10, 4, 4, 14, 15, 4, 13, 0, 1, 15, 15, 15, 17, 10])
sage: B.det()
4447
sage: B.change_ring(Zmod(N)).det()
1
sage: L = lift(B, N)
sage: L.det()
1
sage: (L - B) * Mod(1, N) == 0
True
"""
assert A.is_square()
assert det(A) != 0
m = A.nrows()
if m == 1:
return identity_matrix(1)

D, U, V = A.smith_form()
assert det(U) == 1
assert det(V) == 1
#     print
#     print "D"
#     print D

a = [ D[i, i] for i in range(m) ]
b = prod(a[1:])
W = identity_matrix(m)
W[0, 0] = b
W[1, 0] = b-1
W[0, 1] = 1
#     print
#     print "W"
#     print W

X = identity_matrix(m)
X[0, 1] = -a[1]
#     print
#     print "X"
#     print X

Ap = D.copy()
Ap[0, 0] = 1
Ap[1, 0] = 1-a[0]
Ap[1, 1] *= a[0]
#     print
#     print "Ap"
#     print Ap

assert (W*U*A*V*X).change_ring(Zmod(N)) == Ap.change_ring(Zmod(N))
Cp = diagonal_matrix(a[1:])
Cp[0, 0] *= a[0]
C = lift(Cp, N)
#     print "C"
#     print C

Cpp = block_diagonal_matrix(identity_matrix(1), C)
Cpp[1, 0] = 1-a[0]
#     print "Cpp"
#     print Cpp

#     print
return (~U * ~W * Cpp * ~X * ~V).change_ring(ZZ)
```

### comment:1 Changed 9 years ago by mstreng

• Report Upstream set to N/A

### comment:2 Changed 8 years ago by tmonteil

There seems to be a fix for matrices arising with determinant -1 instead of +1 at this ask question.

### comment:3 Changed 4 years ago by mstreng

• Summary changed from Add code to lift SL2(Z/NZ) to SL2(Z) (and for m not equal 2) to Add code to lift SLm(Z/NZ) to SLm(Z) (also for m not equal 2)

The case m=2 is already in there, but a bit hidden.

```sage: from sage.modular.local_comp.liftings import lift_matrix_to_sl2z
sage: Matrix(ZZ, 2, lift_matrix_to_sl2z([3,7,5,6], 18))

[21 25]
[ 5  6]
```

It also has no examples in its documentation: http://doc.sagemath.org/html/en/reference/modmisc/sage/modular/local_comp/liftings.html

### comment:4 Changed 4 years ago by chapoton

• Branch set to u/chapoton/3313
• Status changed from new to needs_review

done

New commits:

 ​5b88fd7 `trac 3313 lift from SL_m(Z/N) to SL_m(Z)`

### comment:5 Changed 4 years ago by git

• Commit changed from 5b88fd72731ae7669a95ec78b66e28badc46c092 to defa4706cbdb23d70b615160387d39e41fe8a6a5

Branch pushed to git repo; I updated commit sha1. New commits:

 ​defa470 `trac 3313 make the tests appear`

### comment:7 Changed 4 years ago by mderickx

• Status changed from needs_review to needs_work

Could you tell me which article of Shimura you are following? That makes it easier to review.

Also the reference to shimura should be formatted as explained under the references section in http://doc.sagemath.org/html/en/developer/coding_basics.html#documentation-strings

### comment:8 Changed 4 years ago by chapoton

As you may guess, given the number of the ticket, this was archeological work..

I can only guess that this refers to Shimura's book "Introduction to the arithmetic theory of automorphic functions".

### comment:9 Changed 4 years ago by git

• Commit changed from defa4706cbdb23d70b615160387d39e41fe8a6a5 to 650c674e0a2cb3fb9370ea1a2dfffb5494a72831

Branch pushed to git repo; I updated commit sha1. New commits:

 ​650c674 `trac 3313 added ref to shimura`

### comment:10 Changed 4 years ago by chapoton

• Status changed from needs_work to needs_review

done

author?

### comment:12 Changed 4 years ago by chapoton

• Authors set to Nick Alexander, Frédéric Chapoton

review?

### comment:14 Changed 4 years ago by vdelecroix

• Milestone changed from sage-feature to sage-8.1
• Reviewers set to Vincent Delecroix
• Status changed from needs_review to needs_work
• `INPUT` section of the doc is missing
• such function would better accept matrices from `SL(m, Z/NZ)` (in which case the `N` argument should be optional)
```sage: A = matrix(Zmod(7), 2, [1,0,0,1])
sage: L = lift_for_SL(A, 7)
Traceback (most recent call last):
...
TypeError: unsupported operand parent(s) for *: 'Full MatrixSpace of 2 by 2 dense matrices over Ring of integers modulo 7' and 'Full MatrixSpace of 2 by 2 dense matrices over Rational Field'
```
• you are using inverses `~U * ~W * Cpp * ~X * ~V` but at least two of them are trivial (`W` and `X`). Why not constructing the inverses directly?
• The matrix `Ap` is constructed but not used
• in the matrix `D = U * A * V` you seem to be using only the diagonal terms. Would be smarter to compute only them (that would result in computing `n` terms instead of `n^2`).
• the call to `C = lift_for_SL(Cp, N)` is making the function recursive. But `Cp` is a diagonal matrix, case for which the lifting is trivial.

### comment:15 Changed 3 years ago by git

• Commit changed from 650c674e0a2cb3fb9370ea1a2dfffb5494a72831 to a889c310d1ced386492facc9412fd13e4285227f

Branch pushed to git repo; I updated commit sha1. New commits:

 ​29b9433 `Merge branch 'u/chapoton/3313' in 8.1.rc3` ​a889c31 `trac 3313 some enhancements`

### comment:16 Changed 3 years ago by chapoton

some work done. Remains to get rid of the recursive call.

### comment:17 Changed 3 years ago by git

• Commit changed from a889c310d1ced386492facc9412fd13e4285227f to f58b626dbd062617c585412ffc9c9a51c1a0f1a2

Branch pushed to git repo; I updated commit sha1. New commits:

 ​20e4e41 `Merge branch 'u/chapoton/3313' in 8.1.rc4` ​f58b626 `trac 3313 some details, allow ZZ matrices as input again`

### comment:18 Changed 3 years ago by chapoton

• Status changed from needs_work to needs_review

It is not true that the lift of diagonal matrices is trivial.

So this is now ready for review.

### comment:19 Changed 3 years ago by git

• Commit changed from f58b626dbd062617c585412ffc9c9a51c1a0f1a2 to 42108d59dd989161960dbab4933eeae4cd7d05dc

Branch pushed to git repo; I updated commit sha1. New commits:

 ​42108d5 `trac 3313 one more enhancement`

### comment:20 Changed 3 years ago by vdelecroix

Salut Frédéric,

I don't understand completely why recursion is needed. In the recursive call, you are calling the function with a diagonal matrix as input that only depends on the Smith form. But this Smith form is trivial (U=V=identité and D=the input matrix). Of course `Winv` and `Xinv` are non trivial. But it should not be so complicated to include them in a loop. Though I did not give a try. Perhaps you want me to?

```    diag = diagonal_matrix([-1] + [1] * (m - 1))
if U.det() == -1:
U = diag * U
if V.det() == -1:
V = V * diag
```

wouldn't

```    if U.det() * V.det() == -1:
diag = diagonal_matrix([-1] + [1] * (m - 1))
U = diag * U
```

be ok?

### comment:21 Changed 3 years ago by chapoton

I would rather not spend a too large amount of time on that ticket. I would prefer to have feedback on #22397, potentially useful for my research.

Smith form of a diagonal matrix may not be totally trivial:

```sage: m = diagonal_matrix(ZZ,[2*2*3,2*3*5,2*3*5*7])
sage: m.smith_form()

(
[  6   0   0]  [  1   0   1]  [-17   0 -35]
[  0  30   0]  [  0   1   0]  [  0   1   0]
[  0   0 420], [-35   0 -34], [  1   0   2]
)
```

### comment:22 Changed 3 years ago by vdelecroix

I see now. Thanks for the example.

• What about input matrices being defined over `ZZ/N ZZ`? (see also comment:14)
• Could you add some random tests
```sage: for _ in range(100):
....:     d = randint(0, 10)
....:     p = choice([2,3,5,7,11])
....:     M = random_matrix(Zmod(p), d, algorithm='unimodular')
....:     lift_for_SL(M)
```

### comment:23 Changed 3 years ago by git

• Commit changed from 42108d59dd989161960dbab4933eeae4cd7d05dc to 2a0765a947feef6e61d4bff50dde7635c1711198

Branch pushed to git repo; I updated commit sha1. New commits:

 ​6aa4f53 `Merge branch 'u/chapoton/3313' in 8.1` ​2a0765a `trac 3313 add random tests`

### comment:24 Changed 3 years ago by chapoton

And the function already accepts both matrices in ZZ and in Zmod.

### comment:25 Changed 3 years ago by vdelecroix

• Milestone changed from sage-8.1 to sage-8.2
• Status changed from needs_review to positive_review

### comment:26 Changed 3 years ago by vbraun

• Status changed from positive_review to needs_work

Merge conflict

### comment:27 Changed 3 years ago by git

Branch pushed to git repo; I updated commit sha1. New commits:

 ​734dead `Merge branch 'u/chapoton/3313' of trac.sagemath.org:sage into 8.2.b2`

### comment:28 Changed 3 years ago by chapoton

• Status changed from needs_work to positive_review

after a trivial rebase, I allow myself to set this back to positive

### comment:29 Changed 3 years ago by vbraun

• Status changed from positive_review to needs_work

Documentation doesn't build (see patchbot)

### comment:30 Changed 3 years ago by git

Branch pushed to git repo; I updated commit sha1. New commits:

 ​0d26272 `trac 3313 fix doc`

### comment:31 Changed 3 years ago by chapoton

• Status changed from needs_work to positive_review

ok, bot is now green

### comment:32 Changed 3 years ago by vbraun

• Branch changed from u/chapoton/3313 to 0d26272b81d7768c26650a6693d705449ec7e102
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.