Opened 5 years ago

Closed 4 years ago

#17425 closed enhancement (fixed)

Rational isometry test for quadratic forms over number fields

Reported by: annahaensch Owned by:
Priority: major Milestone: sage-6.9
Component: quadratic forms Keywords:
Cc: Merged in:
Authors: Anna Haensch Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 729976e (Commits) Commit: 729976e5b068df72836f6700b71e8fdddc524949
Dependencies: Stopgaps:

Description

This introduces a new function is_rationally_isometric which tests for isometry between two regular rational forms over some number field.

Change History (49)

comment:1 Changed 5 years ago by annahaensch

  • Branch set to u/annahaensch/ticket/17425
  • Created changed from 12/01/14 13:51:11 to 12/01/14 13:51:11
  • Modified changed from 12/01/14 13:51:11 to 12/01/14 13:51:11

comment:2 Changed 5 years ago by annahaensch

  • Commit set to 613901acd98fc0235f871336df3eaed5c6cf5a74
  • Status changed from new to needs_review

New commits:

57f6b6aAdded is_rationally_isometric to library
6e5a563Adjusted preamble in quadratic_forms__equivalence_testing.py
fa4812bUpdated imports in quadratic_form.py
613901aRemoved trailing whitespace

comment:3 Changed 4 years ago by vdelecroix

  • Milestone changed from sage-6.5 to sage-6.9
  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to needs_work

Hello,

I am sorry that this ticket waited that long before a review.

  1. There are some (minor) problems with typography:
    • indentation is not correct. It should be
      def my_function(a, b):
           """
           The text here
           ...
           """
      
      and not
      def my_function(a, b):
          """
              The text here
          ...
          """
      
    • try to keep a space around the == and != signs. In other words a == b instead of a==b. Similarly, add space after a comma as function(a, b) and not function(a,b). This is just to clarify the reading. It is not mandatory.
  1. There is a method .diagonal() to extract the diagonal of a matrix
    sage: K.<a> = NumberField(x^2-3)
    sage: V = QuadraticForm(K,4,[1,0,0,0,2*a,0,0,a,0,2])
    sage: m = V.Gram_matrix_rational()
    sage: m.diagonal()
    [1, 2*a, a, 2]
    
    would be better than using the map(lambda x: M.Gram_matrix_rational()[x][x], ...)
  1. Instead of
        if self.base_ring()==QQ:
            return self.signature() == other.signature():
                Rat_Isom_flag = False
    
    you can do
        if self.base_ring() == QQ:
            return self.signature() == other.signature()
    
    And more generally you do not need to carry over this variable Rat_Isom_flag, just write some return in the conditional statements.
  1. You can simplify the following
    for i in range(len(K.real_embeddings())): 
        Mentries_emb = map(lambda(x):K.real_embeddings()[i](x),Mentries)
        Nentries_emb = map(lambda(x):K.real_embeddings()[i](x),Nentries)
    
        Mpos=0
        for i in range(self.dim()):
            if Mentries_emb[i]>=0:
                Mpos += 1
        ...
    
    into
    for emb in K.real_embeddings():
        Mpos = 0
        for x in Mentries:
            Mpos += emb(x) >= 0
    
        ...
    
    I used two simplifications here
    • you can iterate over a list elements
    • adding a boolean to an integer is equivalent to adding 0 or 1 depending on the truth value

Vincent

comment:4 Changed 4 years ago by git

  • Commit changed from 613901acd98fc0235f871336df3eaed5c6cf5a74 to f7d2f4f2e520952a936d04eebcd9886881153f5b

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

f7d2f4fIncorporated changes 1,2, and 4 from reviewer comments.

comment:5 Changed 4 years ago by annahaensch

  • Status changed from needs_work to needs_review

Thank you kindly for the review, Vincent. I implemented all of your changes with the exception of item 3 (that one ended up causing more difficulty than simplicity). Things should still run as desired.

-Anna

comment:6 Changed 4 years ago by vdelecroix

Hi Anna,

You made a small typo

if self.base_ring() == QQ:
    return self.signature() == other.signature():
        Rat_Isom_flag = False

You need to replace the return with if!

comment:7 Changed 4 years ago by git

  • Commit changed from f7d2f4f2e520952a936d04eebcd9886881153f5b to 8972c8097f74e9bd8e393a839b7ff9e250476af7

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

8972c80fixed two small typos

comment:8 Changed 4 years ago by annahaensch

Thanks, Vincent. I fixed that, and added some blank space around another instance of '!='

comment:9 Changed 4 years ago by vdelecroix

  • Status changed from needs_review to needs_work

With the current code there is something wrong going on. If the dimensions are different then Rat_Isom_flag is set to False. This is fine. But then it will try to multiply the Gram determinant (for nothing since we already knew that they were not equivalent).

Similarly, in this loop

    for p in L:
        if self.hasse_invariant(p) != other.hasse_invariant(p):
            Rat_Isom_flag = False

if you found out that something is wrong during the first pass you will have to wait!

This is why I suggested to modify the code to

if bad behavior 1:
    return False
if bad behavior 2:
    return False
for i in some test case:
    if bad behavior 3:
        return False
return True

comment:10 Changed 4 years ago by git

  • Commit changed from 8972c8097f74e9bd8e393a839b7ff9e250476af7 to 91c47046f8c18487b8e76469ece0618b868df1ef

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

91c4704Removed isom_flag from code

comment:11 Changed 4 years ago by annahaensch

  • Status changed from needs_work to needs_review

Ah, I understand. I changed that throughout, and also caught one error with the signature test over QQ.

comment:12 follow-ups: Changed 4 years ago by vdelecroix

Instead of doing L=L1+L2 you can do L=set().union(L1,L2). That way you will remove duplicates as in

sage: V = DiagonalQuadraticForm(K,[-1,a,-2*a])
sage: W = DiagonalQuadraticForm(K,[-1,-a,2*a])
sage: L1 = V.Gram_det().support()
sage: L1
[Fractional ideal (a + 1), Fractional ideal (a)]
sage: L 2 =W.Gram_det().support()
sage: L2
[Fractional ideal (a + 1), Fractional ideal (a)]
sage: L1+L2
[Fractional ideal (a + 1),
 Fractional ideal (a),
 Fractional ideal (a + 1),
 Fractional ideal (a)]
sage: set().union(L1,L2)
{Fractional ideal (a + 1), Fractional ideal (a)}

And there is no need to declare L (but you might find it simpler) by doing

for p in set().union(L1,L2):
    ...

M and N are computed early but not used early. It would make sense to move there declarations since if the dimension differ (the first test) then there is no need to compute them. You can move them after the else in the case that the base ring is not QQ. You can also move the declaration of L1 and L2.

Could you add some tests for all the cases (starting from the Gram determinant being 0)?

More interesting: is there a way to return the transformation in case they are equivalent?

comment:13 Changed 4 years ago by git

  • Commit changed from 91c47046f8c18487b8e76469ece0618b868df1ef to 8b2f1aa042fae06af40366d50d86b02e17d6e66e

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

8b2f1aaMinor changes in syntax

comment:14 Changed 4 years ago by annahaensch

There is a way to return the transformation, in fact I have a student writing that as a separate function right now. I think it's best to keep it separate from this function, since in principle, his functions work for integral lattices as well, whereas this one is only applicable to fields. Nevertheless, I suppose I should open a trac ticket for that...

comment:15 in reply to: ↑ 12 Changed 4 years ago by vdelecroix

Replying to vdelecroix:

Could you add some tests for all the cases (starting from the Gram determinant being 0)?

You forgot this one. I would be happy with more specifications and degenerate tests. For example, you can copy paste the following

TESTS:

The diagonal form must have the same base ring otherwise a
`TypeError` is raised::

    sage: K1.<a> = QuadraticField(5)
    sage: K2.<b> = QuadraticField(7)
    sage: V = DiagonalQuadraticForm(K1,[1,a])
    sage: W = DiagonalQuadraticForm(K2,[1,b])
    sage: V.is_rationally_isometric(W)
    Traceback (most recent call last):
    ...
    TypeError: forms must have the same base ring.

Beyond that the code looks good to me. I am compiling the documentation right now to see how it looks.

Replying to annahaensch:

There is a way to return the transformation, in fact I have a student writing that as a separate function right now. I think it's best to keep it separate from this function, since in principle, his functions work for integral lattices as well, whereas this one is only applicable to fields. Nevertheless, I suppose I should open a trac ticket for that...

Nice! He or she might open the ticket. That is part of the learning curve ;-)

comment:16 follow-up: Changed 4 years ago by annahaensch

Too true, I'll have him start a ticket. I'm actually having difficult getting my local copy of sage to recognize the function is_rationally_isometric. I am on the branch 17425 and ran ./sage -b but it still says " 'Quadratic Form' has no attribute 'is_rationally_isometric', what step am I missing?

comment:17 in reply to: ↑ 16 Changed 4 years ago by vdelecroix

Replying to annahaensch:

Too true, I'll have him start a ticket. I'm actually having difficult getting my local copy of sage to recognize the function is_rationally_isometric. I am on the branch 17425 and ran ./sage -b but it still says " 'Quadratic Form' has no attribute 'is_rationally_isometric', what step am I missing?

What do you see if you do on the command line inside the sage repository

$ git status -sb
$ git log --oneline -10

(it is to get the name of the branch your on and the last 10 commits)

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

comment:18 Changed 4 years ago by annahaensch

This:

haenscha-ch:sage annahaensch$ git status -sb
## ticket/17425...trac/u/annahaensch/ticket/17425
 M src/sage/quadratic_forms/quadratic_form__equivalence_testing.py
?? build/make/
?? src/sage/libs/pari/auto_gen.pxi
?? src/sage/libs/pari/auto_instance.pxi

And this:

haenscha-ch:sage annahaensch$ git log --oneline -10
8b2f1aa Minor changes in syntax
91c4704 Removed isom_flag from code
8972c80 fixed two small typos
f7d2f4f Incorporated changes 1,2, and 4 from reviewer comments.
613901a Removed trailing whitespace
fa4812b Updated imports in quadratic_form.py
6e5a563 Adjusted preamble in quadratic_forms__equivalence_testing.py
57f6b6a Added is_rationally_isometric to library
76b4ac4 Updated Sage version to 6.4.1
f045b63 Trac #15316: Make gf2x respect SAGE_FAT_BINARY and use --libdir

comment:19 Changed 4 years ago by vdelecroix

It looks strange that you do not have access to the method! Note that you have pending modifications on the file quadratic_form__equivalence_testing.py as shown by git status (the M on the left). There might be something wrong with them. You can temporarily disable these with $ git stash. And then retry sage -b. You will be able to recover them later on by doing $ git stash pop.

sided note: your sage version is very old (but this is of no importance for this ticket since your modifications apply cleanly on the last version).

comment:20 Changed 4 years ago by annahaensch

The pending modification is the TEST that I pasted from your message above. I'm definitely running Sage 6.8, and that sage path that I reference above is actually the clone that I build from git, so it should be very new.

It's not technically the correct way to do things, but if you just give me the text from the test that you want (like you did above), I can just paste them into my patch and then commit and push that. Otherwise, well, I'm not really sure how to do it.

comment:21 follow-up: Changed 4 years ago by vdelecroix

Your ticket is based over sage-6.4.1! What tells you sage -version? You have only one version of sage installed?

comment:22 Changed 4 years ago by vdelecroix

I guess that what is wrong is that the source code that you currently seeing and editing has nothing to do with your binary that you are executing. sage -b is not enough to rebuild sage from different version (here 6.8 agains 6.4.1).

The safest way to proceed would be to merge your changes with the last version of sage. First discard your changes with $ git stash. Then, do you know the name of the branch with the last version? Otherwise you should be able to guess it from $ git branch (should be either develop or master and you can check with git log MAIN_BRANCH that the last commit says something like update to version 6.8). Then just do

$ git merge MAIN_BRANCH

That will fusion your modifications with sage-6.8. Then you should be able to run sage -b and get it work.

comment:23 in reply to: ↑ 21 Changed 4 years ago by annahaensch

Replying to vdelecroix:

Your ticket is based over sage-6.4.1! What tells you sage -version? You have only one version of sage installed?

I have 6.8 and 6.4 installed, but I am doing everything through the clone that I building off of git (that is sage 6.8). I am working on a different computer now than I was 8 months ago when I first wrote the patch, so I wasn't even working with my original code.

I currently have two branches here: master and ticket/17425

comment:24 Changed 4 years ago by vdelecroix

You should be on ticket/17425 (as was said before by $ git status -sb). Check the version in master with $ git log master -1 (the -1 is to get the last commit only) and do

git merge master
Last edited 4 years ago by vdelecroix (previous) (diff)

comment:25 Changed 4 years ago by annahaensch

I am on ticket/17425. When I run git log master -1 it returns (as expected) "Updated Sage version 6.8"

Now I tried to run git merge master and it says

fatal: You have no concluded your merge (MERGE_HEAD exists).
Please commit your changes before you can merge. 

I think this is because I tried to merge earlier and got stuck in a vi window and couldn't get out...oops. What do I do?

Thanks for your help!

comment:26 Changed 4 years ago by vdelecroix

Do

git merge --continue

In the vim window there should be an automatic message already written. Then just enter :wq (w for write and q for quit). For later on you can configure the editor you wish, see this page.

comment:27 Changed 4 years ago by vdelecroix

You might need to commit your changes (sorry). Do $ git stash to discard them. That would be simpler. And then do $ git merge --continue.

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

comment:28 Changed 4 years ago by vdelecroix

The other option is to cancel the merge that you interrupted with $ git merge --abort. And then you can start again a fresh merge.

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

comment:29 follow-up: Changed 4 years ago by annahaensch

Ok, now I've added the tests, merged with the main, staged the commits. But I'm getting an error when I try to push to trac. I've uploaded by ssh key (did it again just now, to be sure), but I'm getting an error

Push to remote branch? [Yes/no] Yes
GitError: git exited with a non-zero exit code (128).
This happened while executing "git push
ssh://git@trac.sagemath.org:2222/sage.git
ticket/17425:u/annahaensch/ticket/17425".
git printed nothing to STDOUT.
git printed the following to STDERR:
ssh: connect to host trac.sagemath.org port 2222: Connection refused
fatal: Could not read from remote repository.
Please make sure you have the correct access rights
and the repository exists.

Any ideas?

comment:30 in reply to: ↑ 29 Changed 4 years ago by vdelecroix

Hi,

Replying to annahaensch:

Ok, now I've added the tests, merged with the main, staged the commits.

Cool.

But I'm getting an error when I try to push to trac. I've uploaded by ssh key (did it again just now, to be sure), but I'm getting an error ...

Why did you upload again the ssh key? Did you have some trouble before that?

In order to test your access to the git server you can run $ ssh git@trac.sagemath.org info. If it tells you who you are this is fine. Otherwise, there is an identification problem.

comment:31 Changed 4 years ago by git

  • Commit changed from 8b2f1aa042fae06af40366d50d86b02e17d6e66e to 17c277600a085dcc04437ec614cfe60aaa4e5fff

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

4f362baMerge branch 'master' into ticket/17425
17c2776Added Tests

comment:32 Changed 4 years ago by annahaensch

Nevermind, I sorted it out, I guess I just needed to reinstall the git trac command. But the most recent commits should have everything. I added several tests, but let me know if this is what you had in mind! -Anna

comment:33 Changed 4 years ago by vdelecroix

Argh! You reintroduced a lot of trailing whitespaces.

Perhaps in the TESTS section, you can add

sage: K.<a> = NumberField(x^5 - x + 2, 'a')
sage: Q = QuadraticForm(K,3,[a,1,0,-a**2,-a**3,-1])
sage: m = Q.matrix()
sage: for _ in range(5):
....:     t = random_matrix(ZZ,3,algorithm='unimodular')
....:     m2 = t*m*t.transpose()
....:     Q2 = QuadraticForm(K, 3, [m2[i,j] / (2 if i==j else 1)
....:                               for i in range(3) for j in range(i,3)])
....:     print Q.is_rationally_isometric(Q2)
True
True
True
True
True

I had some trouble going from the matrix to the quadratic form. There might be a simpler way.

EDIT: there was a type m[i,j] had to be replaced with m2[i,j]... otherwise the equivalence tested would have been between a quadratic form and itself!

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

comment:34 Changed 4 years ago by git

  • Commit changed from 17c277600a085dcc04437ec614cfe60aaa4e5fff to 31a3d9331afff8d167d3e084060b53af6e9f67be

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

bc81f92Remove trailing white space
31a3d93Remove trailing white space

comment:35 Changed 4 years ago by git

  • Commit changed from 31a3d9331afff8d167d3e084060b53af6e9f67be to 324f92d2fdb841ff239181e453a6896a646590a5

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

324f92dAdded test with matrix

comment:36 Changed 4 years ago by git

  • Commit changed from 324f92d2fdb841ff239181e453a6896a646590a5 to 862b8a0a6cd95938361ee2941f1833394df63de3

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

862b8a0Fix typo in TEST

comment:37 Changed 4 years ago by annahaensch

Ack! That trailing white space, I always forget. I should be gone. I added your test and then fixed the typo in a second commit.

comment:38 Changed 4 years ago by vdelecroix

There should be no need to import hasse_invariant. Could you remove the line

from quadratic_form__local_field_invariants import hasse_invariant

that you added?

comment:39 Changed 4 years ago by git

  • Commit changed from 862b8a0a6cd95938361ee2941f1833394df63de3 to 26d73c90698392a8be39971b85b25b62c8866749

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

26d73c9Remove unnecessary hasse_invariant import

comment:40 Changed 4 years ago by vdelecroix

  • Status changed from needs_review to needs_work

I got a doctest failure

sage: K.<a>=QuadraticField(3)
sage: V=DiagonalQuadraticForm(K,[1,2])
sage: W=DiagonalQuadraticForm(K,[1,0])
sage: V.is_rationally_isometric(W)
...
NotImplementedError: This only tests regular forms

The output should be

Traceback (most recent call last):
...
NotImplementedError: This only tests regular forms

You can check that the tests pass with sage -t NAME_OF_THE_FILE.

comment:41 Changed 4 years ago by git

  • Commit changed from 26d73c90698392a8be39971b85b25b62c8866749 to 0e0d462674ff9153cae6beaeca689232e11c8560

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

0e0d462Edited doctest

comment:42 Changed 4 years ago by vdelecroix

Did you run the test on the file with sage -t? I am pretty sure that the colon is needed at the end of the first line.

comment:43 Changed 4 years ago by git

  • Commit changed from 0e0d462674ff9153cae6beaeca689232e11c8560 to 729976e5b068df72836f6700b71e8fdddc524949

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

729976eAdded colon in test

comment:44 Changed 4 years ago by annahaensch

So right, that should do it.

comment:45 follow-up: Changed 4 years ago by vdelecroix

  • Status changed from needs_work to positive_review

All right. The test pass for me! Let this ticket go.

comment:46 in reply to: ↑ 12 ; follow-up: Changed 4 years ago by jdemeyer

Replying to vdelecroix:

More interesting: is there a way to return the transformation in case they are equivalent?

I'm also (weakly) interested in that. It's certainly something which is on my Sage TODO list (even though I don't yet have a ticket for it). I currently have several quadratic_form tickets in "needs_review" right now, and the conflicts would be annoying.

comment:47 in reply to: ↑ 45 Changed 4 years ago by annahaensch

Replying to vdelecroix:

All right. The test pass for me! Let this ticket go.

Vincent, thanks so much for your review and assistance with this! -Anna

comment:48 in reply to: ↑ 46 Changed 4 years ago by annahaensch

Replying to jdemeyer:

Replying to vdelecroix:

More interesting: is there a way to return the transformation in case they are equivalent?

I'm also (weakly) interested in that. It's certainly something which is on my Sage TODO list (even though I don't yet have a ticket for it). I currently have several quadratic_form tickets in "needs_review" right now, and the conflicts would be annoying.

Good news, you can take it off your TODO list, because I actually have a student working on exactly that right now. His ticket should be up soon.

comment:49 Changed 4 years ago by vbraun

  • Branch changed from u/annahaensch/ticket/17425 to 729976e5b068df72836f6700b71e8fdddc524949
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.