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: sage-8.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:

Status badges

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)

Change History (32)

comment:1 Changed 9 years ago by mstreng

  • Cc mstreng added
  • 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

  • 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 chapoton

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

done


New commits:

5b88fd7trac 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:

defa470trac 3313 make the tests appear

comment:6 Changed 4 years ago by chapoton

green bot, please review

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".

See https://math.stackexchange.com/questions/1409197/induced-group-homomorphism-textsl-n-mathbbz-twoheadrightarrow-textsl

and https://mathoverflow.net/questions/164232/modular-group-modulo-n

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:

650c674trac 3313 added ref to shimura

comment:10 Changed 4 years ago by chapoton

  • Status changed from needs_work to needs_review

done

comment:11 Changed 4 years ago by vdelecroix

author?

comment:12 Changed 4 years ago by chapoton

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

comment:13 Changed 4 years ago by 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:

29b9433Merge branch 'u/chapoton/3313' in 8.1.rc3
a889c31trac 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:

20e4e41Merge branch 'u/chapoton/3313' in 8.1.rc4
f58b626trac 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:

42108d5trac 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?

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 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:

6aa4f53Merge branch 'u/chapoton/3313' in 8.1
2a0765atrac 3313 add random tests

comment:24 Changed 3 years ago by chapoton

Random tests were added.

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

  • Commit changed from 2a0765a947feef6e61d4bff50dde7635c1711198 to 734dead038f36f15ac24badcf400b092d49be06f

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

734deadMerge 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

  • Commit changed from 734dead038f36f15ac24badcf400b092d49be06f to 0d26272b81d7768c26650a6693d705449ec7e102

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

0d26272trac 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.