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:  sage8.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: 
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
Branch:  → u/annahaensch/minkowski_reduction___returns_wrong_output 

comment:2 Changed 4 years ago by
Commit:  → 12012c5ebc97d9571ecfb5c39468a7eee224e929 

Status:  new → needs_review 
comment:3 Changed 4 years ago by
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 = [x1 for x in a_first] + [1] + [0 for k in range(n1j)] e_j = [0 for k in range(n)]
to
for a_first in mrange([3] * j]): y = [x1 for x in a_first] + [1] + [0] * (n1j) e_j = [0] * n
for better readability.
comment:4 Changed 4 years ago by
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
Commit:  12012c5ebc97d9571ecfb5c39468a7eee224e929 → 4e500e412eb8f6d95935a4d24e7b5f9c9751daea 

Branch pushed to git repo; I updated commit sha1. New commits:
4e500e4  Edit documentaion to conform to PEP8

comment:6 Changed 4 years ago by
Reviewers:  → Stephan Ehlen 

Status:  needs_review → positive_review 
The code works as expected. The code agrees with the algorithm given in the reference by SchulzePillot. All documentation and all test are completed without errors.
comment:7 followup: 8 Changed 4 years ago by
Status:  positive_review → needs_info 

Actually (I'm sorry), I take it back. I think there is a typo in SchulzePillot'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 Changed 4 years ago by
Replying to ehlen:
Actually (I'm sorry), I take it back. I think there is a typo in SchulzePillot'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
Commit:  4e500e412eb8f6d95935a4d24e7b5f9c9751daea → 9c6999a5bc44ea98440b728e8beed30bf39511bc 

Branch pushed to git repo; I updated commit sha1. New commits:
9c6999a  Adds NotImplimentedError for dimension > 4

comment:10 Changed 4 years ago by
Status:  needs_info → needs_review 

comment:11 followup: 13 Changed 4 years ago by
you should add a doctest in dimension 5, raising the NotImplementedError
comment:12 Changed 4 years ago by
Commit:  9c6999a5bc44ea98440b728e8beed30bf39511bc → cf82604362118faf02af16991759b3f6a5a86a2f 

Branch pushed to git repo; I updated commit sha1. New commits:
cf82604  Adds example of high dimension NotImplementedError to documentation

comment:13 Changed 4 years ago by
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
Status:  needs_review → positive_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
Branch:  u/annahaensch/minkowski_reduction___returns_wrong_output → cf82604362118faf02af16991759b3f6a5a86a2f 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
raise error for indefinite forms
Updated code to return proper Q
Added examples