Add a function "isometry" to the quadratic forms package.

[sagetrac-tgaona]

Adds a function "isometry" that returns an isometry from one rational quadratic form to another, provided that it exists.

CC: @annahaensch @sagetrac-tgaona

Component: quadratic forms

Keywords: isometry

Author: Tyler Gaona, Simon Brandhorst

Branch: ffa5295

Reviewer: Simon Brandhorst

Issue created by migration from https://trac.sagemath.org/ticket/19112

[sagetrac-tgaona]

Branch: u/tgaona/ticket/19112

[sagetrac-tgaona]

New commits:

0d32f4b	Implements a method to compute isometries between positive definite quadratic forms.
9e211fe	Adds a flag parameter to short_vector_list_up_to_length to pass to PARI's

[sagetrac-tgaona]

Commit: 9e211fe

[jdemeyer]

Changed work issues from needs implementation to none

[jdemeyer]

comment:3

This looks like it reinvents the already-existing method is_globally_equivalent_to. What does your code add?

[sagetrac-tgaona]

comment:4

Hi Jeroen,

Sorry for the slow response. This method should be able to return isometries for forms over fields, where I believe is_globally_equivalent_to just works over the ring of integers. For example:

sage: Q = DiagonalQuadraticForm(QQ, [1, 5])
sage: F = QuadraticForm(QQ, 2, [1, 12, 81])
sage: Q.is_globally_equivalent_to(F)
False
sage: Q.is_rationally_isometric(F)
True
sage: T = Q.isometry(F)
sage: T
[  1  -2]
[  0 1/3]
sage: Q.Gram_matrix() == T.transpose() * F.Gram_matrix() * T
True

So Q is equivalent to F over the rationals, but is_globally_equivalent_to doesn't recognize this. This method was intended to complement the is_rationally_isometric method, so perhaps it should be refactored to work in a similar manner as is_globally_equivalent_to, i.e, adding an optional flag to is_rationally_isometric to return the transition matrix for the isometry.

[jdemeyer]

comment:5

Right, I think it's better to mention this more clearly in the documentation (I always get confused when quadratic-form people talk about isomorphic/isometric/equivalent, I never know what they mean).

[jdemeyer]

comment:6

That being said, I think you are really over-complicating the algorithm.

Suppose one of the forms is given by the diagonal 5*x0^2 + .... Then really all you need to do in the first step is to find a vector v of "length" 5. This can be done with some algorithm based on PARI's qfsolve(): the only issue is that qfsolve() finds a projective point, but you really want an affine point.

So I suggest to do the following:

1. implement an affine version of qfsolve() to solve equations of the form Q(x) = C where Q is a quadratic form and C is a constant. Do this in a separate Sage ticket.
2. use this new function to implement isometry on this ticket.

This will have several major advantages:

1. your code will be a lot faster.
2. it will no longer run forever if there is isometry (which is unacceptable).
3. you can remove the assumption that your quadratic form is positive-definite.

[jdemeyer]

comment:7

Also, your branch is based on an old version of Sage. You should really develop from the latest beta version (currently 6.10.beta2).

[jdemeyer]

comment:8

Please follow http://doc.sagemath.org/html/en/developer/coding_basics.html#documentation-strings for the correct formatting of docstrings.

[sagetrac-tgaona]

comment:10

I will make it more clear in the documentation that the method returns a transformation matrix, as opposed to saying it returns an isometry.

As to your second point, I agree that a cleaner, more efficient replacement for the first step of the algorithm is very desirable. However, I have looked at the source for PARI's qfsolve() and it isn't clear to me how to adapt it to return an affine vector x such that Q(x) = C. I would appreciate it if you could offer more guidance here, otherwise, I'm not sure how to proceed.

2. it will no longer run forever if there is isometry (which is unacceptable).

I can fix this by throwing an exception when is_rationally_isometric() returns false for the two forms. The reason I didn't include this initially is that I was working off of Sage 6.8 but is_rationally_isometric() was added in 6.9.

I will fix the formatting in the docstring.

[jdemeyer]

Dependencies: #18669

[jdemeyer]

comment:11

Given that your new functionality relies on rational_diagonal_form(), it would be a lot better in fact to base your patch on top of #18669.

[jdemeyer]

comment:12

About solving quadratic forms:

Suppose you want to solve Q(x) = c. Consider the quadratic form Q(x) - c*z^2 = 0, where z is an extra variable. Find a solution (x,z) to this quadratic form using qfsolve().

Case 1: If z != 0, then Q(x/z) = c.

Case 2: We found a solution Q(x) = 0. Let e be any vector such that B(x,e) != 0, where B is the bilinear form corresponding to Q. To find e, just try all unit vectors (0,..0,1,0...0). Let a = (c - Q(e))/B(x,e) and let y = e + a*x. Then Q(y) = c.

It would be great if you could implement this on a separate ticket.

[sagetrac-tgaona]

Changed dependencies from #18669 to #18669 #19533

[sagetrac-tgaona]

comment:13

Thanks for the clear explanation. I've opened up a separate ticket for this, and will address the various changes you've suggested.

[sagetrac-git]

Changed commit from 9e211fe to afcd21b

[sagetrac-git]

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

51ba9f8	Adds isometry method for quadratic forms.
afcd21b	Merge branch 'research' into ticket/19112

[sagetrac-git]

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

8a040f3

Merge branch 'develop' into ticket/19112

[dimpase]

comment:56

the patchbot results look OK (apart from pyflake plugin, which might tell you how to improve the code).

[embray]

comment:57

Tickets still needing working or clarification should be moved to the next release milestone at the soonest (please feel free to revert if you think the ticket is close to being resolved).

[embray]

comment:58

Ticket retargeted after milestone closed

[mkoeppe]

comment:59

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[simonbrandhorst]

Changed branch from u/tgaona/ticket/19112 to u/sbrandhorst/ticket/19112

[simonbrandhorst]

Changed commit from 2b394f4 to ffa5295

[simonbrandhorst]

New commits:

cb76909	Merge branch 'develop' into t/19112/ticket/19112
ffa5295	is_rationally_equivalent_to cleanup

[simonbrandhorst]

Changed author from Tyler Gaona to Tyler Gaona, Simon Brandorst

[simonbrandhorst]

comment:63

I guess my contribution counts as a reviewer patch...

[vbraun]

Changed branch from u/sbrandhorst/ticket/19112 to ffa5295

[mkoeppe]

Changed author from Tyler Gaona, Simon Brandorst to Tyler Gaona, Simon Brandhorst

[mkoeppe]

Changed commit from ffa5295 to none