Opened 4 years ago

Closed 4 years ago

#24035 closed enhancement (fixed)

Normal forms for TorsionQuadraticModules

Reported by: sbrandhorst Owned by:
Priority: major Milestone: sage-8.1
Component: linear algebra Keywords:
Cc: Merged in:
Authors: Simon Brandhorst Reviewers: Paolo Menegatti
Report Upstream: N/A Work issues:
Branch: 9ae1c13 (Commits, GitHub, GitLab) Commit: 9ae1c1369b171d417e7a291055fa747335244abe
Dependencies: #23699 Stopgaps:

Status badges

Description (last modified by sbrandhorst)

Finite quadratic/bilinear forms can be diagonalized for p!=2. For p=2 they can be decomposed into blocks of size at most 2. This is completely analogous to quadratic forms over the p-adics.

With further normalizations one can compute a normal form. In the sense that two torsion quadratic forms are isomorphic if and only if they have the same normal form. We follow the exposition of Miranda & Morrison Embeddings of Integral Quadratic forms

web.math.ucsb.edu/~drm/manuscripts/eiqf.pdf

Change History (51)

comment:1 Changed 4 years ago by sbrandhorst

  • Branch #23699 deleted
  • Dependencies set to #23699

comment:2 Changed 4 years ago by sbrandhorst

  • Branch set to u/sbrandhorst/orthogonal_jordan_decomposition_for_torsionquadraticmodules

comment:3 Changed 4 years ago by git

  • Commit set to e3452d5382845b1b899b2bd55e7ba25fab6f4759

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

6f2a601Doctests
e3452d5Printmode set to series.

comment:4 Changed 4 years ago by git

  • Commit changed from e3452d5382845b1b899b2bd55e7ba25fab6f4759 to 116463a3d42f6f2f15306ad747d3034c4d6edc61

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

116463aDoctests for jordan_odd_adic

comment:5 Changed 4 years ago by git

  • Commit changed from 116463a3d42f6f2f15306ad747d3034c4d6edc61 to 6cd38974d86e094ec650be20d9a5f2df6fa4b63d

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

6cd3897added orthogonal_gens

comment:6 Changed 4 years ago by git

  • Commit changed from 6cd38974d86e094ec650be20d9a5f2df6fa4b63d to 3e23a14452cf947d77180661f082cc11697f0386

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

437bba1Merge branch 'develop' into t/23699/torsion_quadratic_module_symmetric
b809ccbAdded submodule_with_gens
25ede84Merge branch 'u/sbrandhorst/torsion_quadratic_module_symmetric' of git://trac.sagemath.org/sage into t/24035/orthogonal_jordan_decomposition_for_torsionquadraticmodules
3e23a14Documentation added

comment:7 Changed 4 years ago by sbrandhorst

  • Status changed from new to needs_review

comment:8 Changed 4 years ago by git

  • Commit changed from 3e23a14452cf947d77180661f082cc11697f0386 to fea31dba3762a9d069f83fb96e7377be2aca7e39

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

ea6072aMore docs...
82a1293back to raw strings
e5cecc5Polished docstrings
38091bbFixed indentation for docstrings at module level.
a7a9c39Lazy import IntegralLattice
6ca8126Formatting, minor doc changes, cleanup, and whitespace removal.
76987faSome trivial changes in the documentation.
12c8163Added b as an alias for _mul_.
c8ce05bAdded documentation for `b` and `inner_product`
fea31dbMerge branch 't/23699/torsion_quadratic_module_symmetric' into t/24035/orthogonal_jordan_decomposition_for_torsionquadraticmodules

comment:9 Changed 4 years ago by git

  • Commit changed from fea31dba3762a9d069f83fb96e7377be2aca7e39 to bdedeb7b5defa591e3a6d12a66194d7ca6290152

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

bdedeb7Formating.

comment:10 Changed 4 years ago by sbrandhorst

I have tested the functions on the 290 lattices of https://arxiv.org/abs/1505.06420

There are many lattices with determinants divisible by 2n. So they are good for testing the 2-adic case which is the most complicated.

comment:11 Changed 4 years ago by davidloeffler

  • Authors set to Simon Brandhorst

comment:12 Changed 4 years ago by git

  • Commit changed from bdedeb7b5defa591e3a6d12a66194d7ca6290152 to 60aa2eceadb3c1b313f9fb894bff7efafbc102ca

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

60aa2ecMerge branch 'develop' into t/24035/orthogonal_jordan_decomposition_for_torsionquadraticmodules

comment:13 Changed 4 years ago by git

  • Commit changed from 60aa2eceadb3c1b313f9fb894bff7efafbc102ca to fdc5314f752aa7eb978aa657690f4b895de21dbd

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

7740f72A few small fixes and doctests
fdc5314Removed a non-ascii character and added p_adic_jordan_blocks to the index

comment:14 Changed 4 years ago by git

  • Commit changed from fdc5314f752aa7eb978aa657690f4b895de21dbd to 17b60b05508739b46c554225eb903fca98444879

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

17b60b0Cosmetics

comment:15 Changed 4 years ago by git

  • Commit changed from 17b60b05508739b46c554225eb903fca98444879 to ab68b56296157fb8f19190e38460efaa1d1b43a7

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

ab68b56Merge branch 'develop' into t/24035/orthogonal_jordan_decomposition_for_torsionquadraticmodules

comment:16 Changed 4 years ago by pmenegat

  • Branch changed from u/sbrandhorst/orthogonal_jordan_decomposition_for_torsionquadraticmodules to u/pmenegat/orthogonal_jordan_decomposition_for_torsionquadraticmodules

comment:17 Changed 4 years ago by pmenegat

  • Branch changed from u/pmenegat/orthogonal_jordan_decomposition_for_torsionquadraticmodules to u/sbrandhorst/orthogonal_jordan_decomposition_for_torsionquadraticmodules
  • Status changed from needs_review to needs_work

comment:18 Changed 4 years ago by pmenegat

(fixed) Diagonalization fails in this example:

from sage.modules.torsion_quadratic_module import TorsionQuadraticModule
M = CartanMatrix(['D',8])*3^4
L = FreeQuadraticModule(ZZ,8,M)
Ld = L.span(M.inverse())
T = TorsionQuadraticModule(Ld,L)
T.orthogonal_gens()

the problem is related to how p-adic precision is setted. It could be at least equivalent to the discriminant group

Last edited 4 years ago by pmenegat (previous) (diff)

comment:19 Changed 4 years ago by pmenegat

  • Branch changed from u/sbrandhorst/orthogonal_jordan_decomposition_for_torsionquadraticmodules to u/pmenegat/orthogonal_jordan_decomposition_for_torsionquadraticmodules

comment:20 Changed 4 years ago by pmenegat

  • Commit changed from ab68b56296157fb8f19190e38460efaa1d1b43a7 to 42d780718838f12feee4946fadb14d1f1bcb9bce

The normalisation doesn't order square and not square elements. This functionality could be useful in order to compare two discriminant forms (together with the order given by the p-valuation)

for example:

from sage.modules.torsion_quadratic_module import TorsionQuadraticModule
M = CartanMatrix(['D',8])*3^4
L = FreeQuadraticModule(ZZ,8,M)
Ld = L.span(M.inverse())
T = TorsionQuadraticModule(Ld,L)
T2= T.primary_part(2)
Todd=T.orthogonal_submodule_to(T2)
Todd.orthogonal_gens()

gives:

Finite quadratic module over Integer Ring with invariants (81, 81, 81, 81, 81, 81, 81, 81)
Gram matrix of the quadratic form with values in Q/2Z:
[ 2/81     0     0     0     0     0     0     0]
[    0  2/81     0     0     0     0     0     0]
[    0     0  2/81     0     0     0     0     0]
[    0     0     0 82/81     0     0     0     0]
[    0     0     0     0 82/81     0     0     0]
[    0     0     0     0     0 82/81     0     0]
[    0     0     0     0     0     0 82/81     0]
[    0     0     0     0     0     0     0  2/81]

New commits:

96e708eMinor modifications: deleted ` symbol and modified an assert check
42d7807Fixed bug related p-adic precision

comment:21 Changed 4 years ago by pmenegat

If L is an even lattice, sometimes orthogonal_gens returns a matrix not in the form declared in the documentation. For odd p we could have diagonal values bigger than 1:

sage: from sage.modules.torsion_quadratic_module import TorsionQuadraticModule
sage: M = CartanMatrix(['E',8])*3
sage: L = FreeQuadraticModule(ZZ,8,M)
sage: Ld = L.span(M.inverse())
sage: T = TorsionQuadraticModule(Ld,L)
sage: T.orthogonal_gens()

Finite quadratic module over Integer Ring with invariants (3, 3, 3, 3, 3, 3, 3, 3)
Gram matrix of the quadratic form with values in Q/2Z:
[2/3   0   0   0   0   0   0   0]
[  0 2/3   0   0   0   0   0   0]
[  0   0 2/3   0   0   0   0   0]
[  0   0   0 2/3   0   0   0   0]
[  0   0   0   0 4/3   0   0   0]
[  0   0   0   0   0 2/3   0   0]
[  0   0   0   0   0   0 4/3   0]
[  0   0   0   0   0   0   0 2/3]

And for p=2 we could have not normalized blocks

sage: from sage.modules.torsion_quadratic_module import TorsionQuadraticModule
sage: M = CartanMatrix(['E',8])*8
sage: L = FreeQuadraticModule(ZZ,8,M)
sage: Ld = L.span(M.inverse())
sage: T = TorsionQuadraticModule(Ld,L)
sage: T.orthogonal_gens()

Finite quadratic module over Integer Ring with invariants (8, 8, 8, 8, 8, 8, 8, 8)
Gram matrix of the quadratic form with values in Q/2Z:
[5/4 1/8   0   0   0   0   0   0]
[1/8 1/4   0   0   0   0   0   0]
[  0   0   0 1/8   0   0   0   0]
[  0   0 1/8   1   0   0   0   0]
[  0   0   0   0 1/4 1/8   0   0]
[  0   0   0   0 1/8 1/4   0   0]
[  0   0   0   0   0   0   1 1/8]
[  0   0   0   0   0   0 1/8   0]

comment:22 Changed 4 years ago by sbrandhorst

  • Branch changed from u/pmenegat/orthogonal_jordan_decomposition_for_torsionquadraticmodules to u/sbrandhorst/orthogonal_jordan_decomposition_for_torsionquadraticmodules

comment:23 Changed 4 years ago by git

  • Commit changed from 42d780718838f12feee4946fadb14d1f1bcb9bce to cf8aa9012e37c6f0e671d795884f1cc1ce5ec069

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

cf8aa90Relations of 2-adic forms

comment:24 Changed 4 years ago by sbrandhorst

  • Description modified (diff)
  • Summary changed from Orthogonal/Jordan decomposition for TorsionQuadraticModules to Normal forms for TorsionQuadraticModules

comment:25 Changed 4 years ago by git

  • Commit changed from cf8aa9012e37c6f0e671d795884f1cc1ce5ec069 to f7a3ccdbd4e211e2fcad543a1b2d592cde009695

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

f7a3ccdPartial normal form implemented.

comment:26 Changed 4 years ago by git

  • Commit changed from f7a3ccdbd4e211e2fcad543a1b2d592cde009695 to c40e2469182815226f48e1f954dc09d65f6738f1

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

c40e246Full normal form - first prototype

comment:27 Changed 4 years ago by git

  • Commit changed from c40e2469182815226f48e1f954dc09d65f6738f1 to 1f5ad0f1eb417db20a1a9356b968f94b3dcd2469

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

1f5ad0fBugfixes and documentation

comment:28 Changed 4 years ago by git

  • Commit changed from 1f5ad0f1eb417db20a1a9356b968f94b3dcd2469 to 00b2fa5a6120787c8ac34d077187f339af922ad4

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

00b2fa5Optimizations and documentation

comment:29 Changed 4 years ago by git

  • Commit changed from 00b2fa5a6120787c8ac34d077187f339af922ad4 to 087867dd6c9acd0f8f8ac79c5a8a3c8e6a88487c

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

087867drenamed orthogonal_gens to normal_form

comment:30 Changed 4 years ago by sbrandhorst

  • Status changed from needs_work to needs_review

comment:31 Changed 4 years ago by git

  • Commit changed from 087867dd6c9acd0f8f8ac79c5a8a3c8e6a88487c to 94fbd5b630b79ade30301b87d6a08a98de15ad3b

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

94fbd5bChange in convention in Torsion quadratic module normal form.

comment:32 Changed 4 years ago by sbrandhorst

The following code is still running after 176 000 examples. So far no bugs.

block = []
for x in mrange([5,5,5,5]):
    x = [2*d-1 for d in x]
    y = []
    for d in x:
        if d!=-1:
            y.append(d)
    block.append(matrix.diagonal(R,y))

#L = []
s = 0
for b0 in block:
    for b1 in block:
        for b2 in block:
            print(s)
            s = s+1
            D = Matrix.block_diagonal([b0,2*b1,4*b2])
            if D.ncols()!=0:
                a = p_adic_normal_form(D,p,precision=prec)[0].change_ring(ZZ)
                n = a.ncols()
                for k in range(20):
                    u = random_matrix(ZZ,n,n,algorithm='unimodular')
                    aa = p_adic_normal_form(u*D*u.T,p,precision=prec)[0].change_ring(ZZ)
                    assert a == aa

comment:33 Changed 4 years ago by pmenegat

  • Branch changed from u/sbrandhorst/orthogonal_jordan_decomposition_for_torsionquadraticmodules to u/pmenegat/orthogonal_jordan_decomposition_for_torsionquadraticmodules

comment:34 Changed 4 years ago by pmenegat

  • Commit changed from 94fbd5b630b79ade30301b87d6a08a98de15ad3b to 21d142f20cea6a7cf43bf0e5a7ae2999c98df59a

The mathematical part seems ok and the examples tested work. The code is well commented, it remains now to check python conventions and improve the documentation

comment:35 Changed 4 years ago by sbrandhorst

  • Branch changed from u/pmenegat/orthogonal_jordan_decomposition_for_torsionquadraticmodules to u/sbrandhorst/orthogonal_jordan_decomposition_for_torsionquadraticmodules

comment:36 Changed 4 years ago by git

  • Commit changed from 21d142f20cea6a7cf43bf0e5a7ae2999c98df59a to 1ae8c8bbd20a56eb4ec521c058ed2e6797b16d62

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

1ae8c8bLots and lots of documentation.

comment:37 Changed 4 years ago by sbrandhorst

  • documentation builds and seems to look okay.

comment:38 Changed 4 years ago by git

  • Commit changed from 1ae8c8bbd20a56eb4ec521c058ed2e6797b16d62 to 52df7c6e919767c83333d0b5ddea6788f4989c5e

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

52df7c6Some extra docs.

comment:39 Changed 4 years ago by git

  • Commit changed from 52df7c6e919767c83333d0b5ddea6788f4989c5e to 5097c404493bbf331ca8dd4e3c3ebd135b639a56

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

5097c40Precision bugfix.

comment:40 Changed 4 years ago by git

  • Commit changed from 5097c404493bbf331ca8dd4e3c3ebd135b639a56 to 5a986593b4d655c88bb703f837a043ed423c3ff5

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

5a98659SEEALSO: --> SEEALSO::

comment:41 Changed 4 years ago by git

  • Commit changed from 5a986593b4d655c88bb703f837a043ed423c3ff5 to 987417dddffad67d0226ff151a6c5b0367b6968f

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

987417dDoc formating in torsion_quadratic_module.py

comment:42 Changed 4 years ago by pmenegat

  • Status changed from needs_review to positive_review

comment:43 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

Reviewer name is missing

comment:44 Changed 4 years ago by davidloeffler

  • Reviewers set to Paolo Menegatti
  • Status changed from needs_work to positive_review

comment:45 Changed 4 years ago by git

  • Commit changed from 987417dddffad67d0226ff151a6c5b0367b6968f to 05927ca9fc67da6409f70b0b0ce48fa45ad57b8f
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

05927caMerge branch 'develop' of git://trac.sagemath.org/sage into t/24035/orthogonal_jordan_decomposition_for_torsionquadraticmodules

comment:46 Changed 4 years ago by git

  • Commit changed from 05927ca9fc67da6409f70b0b0ce48fa45ad57b8f to 8f944ccb9b950d7baa7b48b622870afb3abe33db

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

8f944ccDoc formatting.

comment:47 Changed 4 years ago by git

  • Commit changed from 8f944ccb9b950d7baa7b48b622870afb3abe33db to 0600a540a2e43da79c0a0fa53968832323677019

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

0600a54Documentation only

comment:48 Changed 4 years ago by git

  • Commit changed from 0600a540a2e43da79c0a0fa53968832323677019 to a88fbf6fa68aae05afa6e251aac1c612b056a6b9

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

a88fbf6Change in convention for the normal form of a p-torsion module.

comment:49 Changed 4 years ago by git

  • Commit changed from a88fbf6fa68aae05afa6e251aac1c612b056a6b9 to 9ae1c1369b171d417e7a291055fa747335244abe

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

9ae1c13Revert "Change in convention for the normal form of a p-torsion module."

comment:50 Changed 4 years ago by pmenegat

  • Status changed from needs_review to positive_review

comment:51 Changed 4 years ago by vbraun

  • Branch changed from u/sbrandhorst/orthogonal_jordan_decomposition_for_torsionquadraticmodules to 9ae1c1369b171d417e7a291055fa747335244abe
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.