Opened 13 years ago
Closed 3 years ago
#3313 closed enhancement (fixed)
Add code to lift SLm(Z/NZ) to SLm(Z) (also for m not equal 2)
Reported by:  ncalexan  Owned by:  was 

Priority:  minor  Milestone:  sage8.2 
Component:  number theory  Keywords:  lift symplectic sl sl2 sl2z special linear 
Cc:  ncalexan, mstreng, mmasdeu  Merged in:  
Authors:  Nick Alexander, Frédéric Chapoton  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  0d26272 (Commits, GitHub, GitLab)  Commit:  0d26272b81d7768c26650a6693d705449ec7e102 
Dependencies:  Stopgaps: 
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] = b1 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] = 1a[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] = 1a[0] # print "Cpp" # print Cpp # print return (~U * ~W * Cpp * ~X * ~V).change_ring(ZZ)
Change History (32)
comment:1 Changed 9 years ago by
 Cc mstreng added
 Report Upstream set to N/A
comment:2 Changed 8 years ago by
comment:3 Changed 4 years ago by
 Cc mmasdeu added
 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
 Branch set to u/chapoton/3313
 Commit set to 5b88fd72731ae7669a95ec78b66e28badc46c092
 Status changed from new to needs_review
comment:5 Changed 4 years ago by
 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:6 Changed 4 years ago by
green bot, please review
comment:7 Changed 4 years ago by
 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#documentationstrings
comment:8 Changed 4 years ago by
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".
and https://mathoverflow.net/questions/164232/modulargroupmodulon
comment:9 Changed 4 years ago by
 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:11 Changed 4 years ago by
author?
comment:12 Changed 4 years ago by
comment:13 Changed 4 years ago by
review?
comment:14 Changed 4 years ago by
 Milestone changed from sagefeature to sage8.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 theN
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
andX
). 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 computingn
terms instead ofn^2
).
 the call to
C = lift_for_SL(Cp, N)
is making the function recursive. ButCp
is a diagonal matrix, case for which the lifting is trivial.
comment:15 Changed 3 years ago by
 Commit changed from 650c674e0a2cb3fb9370ea1a2dfffb5494a72831 to a889c310d1ced386492facc9412fd13e4285227f
comment:16 Changed 3 years ago by
some work done. Remains to get rid of the recursive call.
comment:17 Changed 3 years ago by
 Commit changed from a889c310d1ced386492facc9412fd13e4285227f to f58b626dbd062617c585412ffc9c9a51c1a0f1a2
comment:18 Changed 3 years ago by
 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
 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
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?
Instead of
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
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
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
 Commit changed from 42108d59dd989161960dbab4933eeae4cd7d05dc to 2a0765a947feef6e61d4bff50dde7635c1711198
comment:24 Changed 3 years ago by
Random tests were added.
And the function already accepts both matrices in ZZ and in Zmod.
comment:25 Changed 3 years ago by
 Milestone changed from sage8.1 to sage8.2
 Status changed from needs_review to positive_review
comment:27 Changed 3 years ago by
 Commit changed from 2a0765a947feef6e61d4bff50dde7635c1711198 to 734dead038f36f15ac24badcf400b092d49be06f
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
 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
 Status changed from positive_review to needs_work
Documentation doesn't build (see patchbot)
comment:30 Changed 3 years ago by
 Commit changed from 734dead038f36f15ac24badcf400b092d49be06f to 0d26272b81d7768c26650a6693d705449ec7e102
Branch pushed to git repo; I updated commit sha1. New commits:
0d26272  trac 3313 fix doc

comment:31 Changed 3 years ago by
 Status changed from needs_work to positive_review
ok, bot is now green
comment:32 Changed 3 years ago by
 Branch changed from u/chapoton/3313 to 0d26272b81d7768c26650a6693d705449ec7e102
 Resolution set to fixed
 Status changed from positive_review to closed
There seems to be a fix for matrices arising with determinant 1 instead of +1 at this ask question.