Rational isometry test for quadratic forms over number fields

[annahaensch]

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

[annahaensch]

New commits:

​57f6b6a	Added is_rationally_isometric to library
​6e5a563	Adjusted preamble in quadratic_forms__equivalence_testing.py
​fa4812b	Updated imports in quadratic_form.py
​613901a	Removed trailing whitespace

[vdelecroix]

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.

2. 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], ...)

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

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

[git]

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

​f7d2f4f

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

[annahaensch]

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

[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!

[git]

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

​8972c80

fixed two small typos

[annahaensch]

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

[vdelecroix]

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

[git]

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

​91c4704

Removed isom_flag from code

[annahaensch]

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

[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?

[git]

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

​8b2f1aa

Minor changes in syntax

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

[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 ;-)

[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?

[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)

[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

[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).

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

[vdelecroix]

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

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

[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

[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

[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!

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

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

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

[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?

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

[git]

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

​4f362ba	Merge branch 'master' into ticket/17425
​17c2776	Added Tests

[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

[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!

[git]

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

​bc81f92	Remove trailing white space
​31a3d93	Remove trailing white space

[git]

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

​324f92d

Added test with matrix

[git]

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

​862b8a0

Fix typo in TEST

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

[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?

[git]

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

​26d73c9

Remove unnecessary hasse_invariant import

[vdelecroix]

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.

[git]

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

​0e0d462

Edited doctest

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

[git]

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

​729976e

Added colon in test

[annahaensch]

So right, that should do it.

[vdelecroix]

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

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

[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

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