Opened 4 years ago

Closed 4 years ago

#25110 closed defect (fixed)

minkowski_reduction() returns wrong output

Reported by: Anna Haensch Owned by:
Priority: major Milestone: sage-8.2
Component: quadratic forms Keywords:
Cc: Merged in:
Authors: Anna Haensch Reviewers: Stephan Ehlen
Report Upstream: N/A Work issues:
Branch: cf82604 (Commits, GitHub, GitLab) Commit: cf82604362118faf02af16991759b3f6a5a86a2f
Dependencies: Stopgaps:

Status badges

Description

Currently, the function in quadratic_form_reduction_theory.py to Minkowski reduce a basis returns an incorrect output. For example:

sage: Q=QuadraticForm(ZZ,3,[1,-2,0,2,0,2])
sage: Q.Gram_matrix()

[ 1 -1  0]
[-1  2  0]
[ 0  0  2]
sage: Q.minkowski_reduction()

(
Quadratic form in 3 variables over Integer Ring with coefficients: 
[ 1 -2 0 ]                                                         
[ * 2 0 ]                                                          
[ * * 2 ]                                                          ,

[1 0 0]
[0 1 0]
[0 0 1]
)

But this is by definition (see for example Cassels "Rational Quadratic Forms" p. 255) not Minkowski reduced, since

Q(1,1,0) < Q(0,1,0).

A correct Minkowski reduced matrix equivalent to the one given, would be

Quadratic form in 3 variables over Integer Ring with coefficients: 
[ 1 0 0 ]
[ * 1 0 ]
[ * * 2 ]

There is also a problem that this function runs on an infinite loop (rather than raising an error flag) when an indefinite quadratic form is entered.

Change History (15)

comment:1 Changed 4 years ago by Anna Haensch

Branch: u/annahaensch/minkowski_reduction___returns_wrong_output

comment:2 Changed 4 years ago by Anna Haensch

Commit: 12012c5ebc97d9571ecfb5c39468a7eee224e929
Status: newneeds_review

New commits:

3ee5d1braise error for indefinite forms
500bc0eUpdated code to return proper Q
12012c5Added examples

comment:3 Changed 4 years ago by Samuel Lelièvre

Sorry I can't do a full review, but for the sake of PEP8 please change

Q=QuadraticForm(ZZ,4,[1,-2,0,0,2,0,0,2,0,2])

to

Q = QuadraticForm(ZZ, 4, [1, -2, 0, 0, 2, 0, 0, 2, 0, 2])

and consider simplifying

for a_first in mrange([3  for i in range(j)]):
    y = [x-1 for x in a_first] + [1] + [0 for k in range(n-1-j)]
    e_j = [0  for k in range(n)]

to

for a_first in mrange([3] * j]):
    y = [x-1 for x in a_first] + [1] + [0] * (n-1-j)
    e_j = [0] * n

for better readability.

comment:4 Changed 4 years ago by Anna Haensch

Thanks, I updated the documentation as you recommend. I left the code in its original form. The edits you suggest introduced a build error, and rather than troubleshoot that, I think it's easier just to leave it as it's been.

comment:5 Changed 4 years ago by git

Commit: 12012c5ebc97d9571ecfb5c39468a7eee224e9294e500e412eb8f6d95935a4d24e7b5f9c9751daea

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

4e500e4Edit documentaion to conform to PEP8

comment:6 Changed 4 years ago by Stephan Ehlen

Reviewers: Stephan Ehlen
Status: needs_reviewpositive_review

The code works as expected. The code agrees with the algorithm given in the reference by Schulze-Pillot. All documentation and all test are completed without errors.

comment:7 Changed 4 years ago by Stephan Ehlen

Status: positive_reviewneeds_info

Actually (I'm sorry), I take it back. I think there is a typo in Schulze-Pillot's paper. Where it says m>=4 in the algorithm it should really say m<= 4. I'm not convinced that the algorithm implemented here works for more that 4 variables. It seems to me that the coefficients s_i are taken in {0,-1,1} but this should only work for at most 4 variables. I haven't thought about this a lot and so I'm changing the status to 'needs info' first. But I suspect that this actually needs work...

comment:8 in reply to:  7 Changed 4 years ago by Anna Haensch

Replying to ehlen:

Actually (I'm sorry), I take it back. I think there is a typo in Schulze-Pillot's paper. Where it says m>=4 in the algorithm it should really say m<= 4. I'm not convinced that the algorithm implemented here works for more that 4 variables. It seems to me that the coefficients s_i are taken in {0,-1,1} but this should only work for at most 4 variables. I haven't thought about this a lot and so I'm changing the status to 'needs info' first. But I suspect that this actually needs work...

I think you're correct. I looked more closely at the 1979 Donaldson paper (see bottom of page 203) and it looks like the problem of finding the s_i grows difficult very quickly as the dimension increases. For the moment, I think we should just call this an algorithm for forms with dimension less than or equal to 4 and raise a NotImplimentedError? otherwise. I just pushed a commit to that effect. Let me know what you think. Thanks!

comment:9 Changed 4 years ago by git

Commit: 4e500e412eb8f6d95935a4d24e7b5f9c9751daea9c6999a5bc44ea98440b728e8beed30bf39511bc

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

9c6999aAdds NotImplimentedError for dimension > 4

comment:10 Changed 4 years ago by Anna Haensch

Status: needs_infoneeds_review

comment:11 Changed 4 years ago by Frédéric Chapoton

you should add a doctest in dimension 5, raising the NotImplementedError

comment:12 Changed 4 years ago by git

Commit: 9c6999a5bc44ea98440b728e8beed30bf39511bccf82604362118faf02af16991759b3f6a5a86a2f

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

cf82604Adds example of high dimension NotImplementedError to documentation

comment:13 in reply to:  11 Changed 4 years ago by Anna Haensch

Replying to chapoton:

you should add a doctest in dimension 5, raising the NotImplementedError

Thanks, I just added that.

comment:14 Changed 4 years ago by Stephan Ehlen

Status: needs_reviewpositive_review

Everything works as expected. The documentation is fine. Merging with the latest development branch (8.3beta7) works fine, compiles fine and all tests pass.

comment:15 Changed 4 years ago by Volker Braun

Branch: u/annahaensch/minkowski_reduction___returns_wrong_outputcf82604362118faf02af16991759b3f6a5a86a2f
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.