#19595 closed enhancement (fixed)
Implement a check that a hyperplane arrangement is free
Reported by:  tscrim  Owned by:  tscrim 

Priority:  major  Milestone:  sage7.2 
Component:  geometry  Keywords:  free, hyperplane arrangement 
Cc:  vbraun, chapoton, mmarco  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  Miguel Marco, Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  5c3c9b7 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  #19892 #19855  Stopgaps: 
Description (last modified by )
We follow Barakat and Cuntz in arXiv:1011.4228 to check if a hyperplane arrangement is free.
Change History (43)
comment:1 Changed 5 years ago by
 Branch set to public/hyperplanes/check_free19595
 Cc vbraun chapoton added
 Commit set to ca31fa9d4d55a5ed1093b5f46790ca9994a0926b
 Description modified (diff)
 Status changed from new to needs_review
comment:2 Changed 5 years ago by
 Commit changed from ca31fa9d4d55a5ed1093b5f46790ca9994a0926b to 05385db408dd73295ed477ee874c1478823f1349
comment:3 Changed 5 years ago by
 Commit changed from 05385db408dd73295ed477ee874c1478823f1349 to b3db54c53f3a571f7408e14b7274ed9c9f00feaf
Branch pushed to git repo; I updated commit sha1. New commits:
b3db54c  Changing the output format of derivation_module_basis and added some more doc.

comment:4 followup: ↓ 6 Changed 5 years ago by
 do you check for "freeness" or some stronger "inductive freeness" ?
 in
to_symmetric_space
return S.sum(G[i]*c for i,c in enumerate(self.coefficients()[1:]))
why is there [1:]
?
 maybe you should rather write
chordality is equivalent to freeness
and name the files "check_freeness
"
comment:5 Changed 5 years ago by
 Milestone changed from sage6.10 to sage7.0
comment:6 in reply to: ↑ 4 ; followup: ↓ 8 Changed 5 years ago by
Replying to chapoton:
 do you check for "freeness" or some stronger "inductive freeness" ?
As I understand it, this is just freeness, but I will make a detailed reading and doublecheck this.
 in
to_symmetric_space
return S.sum(G[i]*c for i,c in enumerate(self.coefficients()[1:]))why is there
[1:]
?
Because the first coefficient of a hyperplane is the constant part (as the arrangements do not need to be central, i.e., they are allowed to be affine hyperplanes).
 maybe you should rather write
chordality is equivalent to freeness
and name the files "check_freeness
"
Will change.
comment:7 Changed 5 years ago by
 Commit changed from b3db54c53f3a571f7408e14b7274ed9c9f00feaf to 05d7517656a9d911f6d97cc875bd82afb9f30f07
comment:8 in reply to: ↑ 6 Changed 5 years ago by
Replying to tscrim:
Replying to chapoton:
 do you check for "freeness" or some stronger "inductive freeness" ?
As I understand it, this is just freeness, but I will make a detailed reading and doublecheck this.
This does not check inductive freeness because it does not check both the exponent condition and the freeness of the restriction. However this would make for a good followup.
 in
to_symmetric_space
return S.sum(G[i]*c for i,c in enumerate(self.coefficients()[1:]))why is there
[1:]
?Because the first coefficient of a hyperplane is the constant part (as the arrangements do not need to be central, i.e., they are allowed to be affine hyperplanes).
In my recent push, I now forbid affine hyperplanes since I don't believe they make sense in the symmetric space.
 maybe you should rather write
chordality is equivalent to freeness
and name the files "check_freeness
"Will change.
Done.
comment:9 Changed 5 years ago by
 Commit changed from 05d7517656a9d911f6d97cc875bd82afb9f30f07 to b10a0c819f1b50869ba620be849bbd12d199c146
Branch pushed to git repo; I updated commit sha1. New commits:
b10a0c8  trac #1959 correct import

comment:10 Changed 5 years ago by
I have just given a very quick look at the code, but it seems to me that you are actually computing a free resolution of the logarithmic derivation module. Or at least the first steps of it. Is that correct?
If this is the case, maybe it would be worth doing so by using Singular, which already has this implemented.
Something like
sage: R.<x,y,z,t> = QQ[] sage: f = x^3 + y^3 +z^3+ t^3 sage: I = f.jacobian_ideal() sage: IS = I._singular_() sage: res = IS.mres(0) sage: res [1]: _[1]=t^2 _[2]=z^2 _[3]=y^2 _[4]=x^2 [2]: _[1]=z^2*gen(1)t^2*gen(2) _[2]=y^2*gen(1)t^2*gen(3) _[3]=y^2*gen(2)z^2*gen(3) _[4]=x^2*gen(1)t^2*gen(4) _[5]=x^2*gen(2)z^2*gen(4) _[6]=x^2*gen(3)y^2*gen(4) [3]: _[1]=y^2*gen(1)z^2*gen(2)+t^2*gen(3) _[2]=x^2*gen(1)z^2*gen(4)+t^2*gen(5) _[3]=x^2*gen(2)y^2*gen(4)+t^2*gen(6) _[4]=x^2*gen(3)y^2*gen(5)+z^2*gen(6) [4]: _[1]=x^2*gen(1)y^2*gen(2)+z^2*gen(3)t^2*gen(4) sage: len(res) 4
should give you a minimal free resolution of the logarithmic derivation module of every homogenous polynomial f, so it would be free iff len(res)<=2 .
For the non homogenous case, one might need to work a little bit with the homogenization of the polynomial, but it can also be done.
Could you please compare the timings of your code with the singular method?
comment:11 followup: ↓ 13 Changed 5 years ago by
Another question: is this granted to work for non crystalographic arrangements?
comment:12 Changed 5 years ago by
 Cc mmarco added
comment:13 in reply to: ↑ 11 Changed 5 years ago by
Replying to mmarco:
Another question: is this granted to work for non crystalographic arrangements?
Barakat and Cuntz say explicitly at the beginning of Section 6 "free central arrangement". So it works well beyond inversion arrangements.
Replying to mmarco:
I have just given a very quick look at the code, but it seems to me that you are actually computing a free resolution of the logarithmic derivation module. Or at least the first steps of it. Is that correct?
From some quick Googling (your paper no less) and my (relatively small) understanding of this area of math, I believe so.
If this is the case, maybe it would be worth doing so by using Singular, which already has this implemented.
I am not surprised, but a lot of Singular does not seem to be (well) exposed with good interface classes. (Actually, AFAIK this is the first implementation of a notnecessarilyfree module in Sage.) I came across Singular's free resolution code after I had made this, but I was lazy. This did what I wanted and I didn't want to figure out the Singular interface and write the wrappers.
Something like
sage: R.<x,y,z,t> = QQ[] sage: f = x^3 + y^3 +z^3+ t^3 sage: I = f.jacobian_ideal() sage: IS = I._singular_() sage: res = IS.mres(0) sage: len(res) 4should give you a minimal free resolution of the logarithmic derivation module of every homogenous polynomial f, so it would be free iff len(res)<=2 .
For the non homogenous case, one might need to work a little bit with the homogenization of the polynomial, but it can also be done.
Could you please compare the timings of your code with the singular method?
I am all but certain your code works faster when the arrangement is not free. I could (should) optimize my code by doing a backtracking algorithm too; at least that would make it a more fair comparison. On my next push, I will include an option for both algorithms.
comment:14 followup: ↓ 15 Changed 5 years ago by
Yes, we should probably write some parent class for these kinds of modules. And maybe also one for resolutions. Maybe a good fit for GSoC?
comment:15 in reply to: ↑ 14 Changed 5 years ago by
Replying to mmarco:
Yes, we should probably write some parent class for these kinds of modules. And maybe also one for resolutions. Maybe a good fit for GSoC?
I agree, and also another (strongly correlated) one would be exposing more from Singular. I would also be willing to (help) mentor this project too.
comment:16 Changed 5 years ago by
I added a draft of the proposal to the wiki in https://wiki.sagemath.org/GSoC/2016 . Feel free to modify it.
comment:17 Changed 5 years ago by
 Commit changed from b10a0c819f1b50869ba620be849bbd12d199c146 to 38923f5933b6745a2506cfa71ce7368b9287dcad
comment:18 Changed 5 years ago by
 Commit changed from 38923f5933b6745a2506cfa71ce7368b9287dcad to dda0ab3d40972798cf18394d91eabf56418f36e5
Branch pushed to git repo; I updated commit sha1. New commits:
dda0ab3  Use the standard copyright template.

comment:19 Changed 5 years ago by
 Milestone changed from sage7.0 to sage7.1
The Singular code rips my implementation to shreads. It at least 2x faster (often times much more so) in the cases I tested (inversion arrangements for types A_{3} and B_{3}), so I am making that the default. However, I am still using it to construct the basis, but if you know how to pull that from Singular's resolution, I would be happy to include that as well.
I implemented by backtracking in a recursive fashion since I didn't want to deal with managing my own stack, and if you're doing something with 1000 hyperplanes (reaching Python's recursion depth limit), then you are probably better off waiting for the universe to implode. It is possible there are further optimizations to be done with that code, but since Singular does the biggest thing, checking for freeness, really fast, I'm inclined to leaving it alone for now.
comment:20 followup: ↓ 21 Changed 5 years ago by
Hmmm, usually when I want to compute a basis I do so by taking the syzygy module of the jacobian ideal of the polynomial. This procedure has always given me a basis, but now I am not sure if it is granted to work always.
Let me think about it for a few days.
comment:21 in reply to: ↑ 20 Changed 5 years ago by
Replying to mmarco:
Hmmm, usually when I want to compute a basis I do so by taking the syzygy module of the jacobian ideal of the polynomial. This procedure has always given me a basis, but now I am not sure if it is granted to work always.
I am pretty sure you're right. I will add this and check.
comment:22 Changed 5 years ago by
If you add this method, unless you have a proof that grants to get the correct result, there should be a check. Saito criterion seems like the fastest way to check if something is a basis. That way we can fall back to other implementation if this happen to fail.
comment:23 Changed 5 years ago by
Actually, from my testing using inversion arrangements, the syzygy module often results in a nonsquare matrix (even after passing it through less_generators
). So I don't think this is a viable method. I did push the code to the branch
u/tscrim/check_free_with_basis19595
if you want to take a look (and I'm not sure if I got Saito's criterion correct either).
Perhaps we should just include this asis for now and do a followup ticket for finding a faster way to construct the basis?
comment:24 Changed 5 years ago by
There is a singular command called mstd, that produces a minimal set of generators of an ideal of module. Try something like:
sage: H.<x,y,z> = HyperplaneArrangements(QQ) sage: A = H( xz, yz, x+y, x+z, y+z, x, y, z) sage: f = A.defining_polynomial() sage: I = f + f.jacobian_ideal() sage: IS = I._singular_() sage: ISS = IS.syz() sage: MSTD = ISS.mstd() sage: M = MSTD[2]._sage_().transpose().submatrix(0,1) sage: M [ x y z] [ 0 x^2*y  y^3 x^2*z  z^3] [ 0 x*y^3 + y^4  x*y*z^2  y^2*z^2 0] sage: M.determinant()/f 1
comment:25 Changed 5 years ago by
 Commit changed from dda0ab3d40972798cf18394d91eabf56418f36e5 to c5aba60b99292490dabae3009eaf29f9c9a9898b
Branch pushed to git repo; I updated commit sha1. New commits:
c5aba60  Added Singular algorithm for constructing a basis.

comment:26 Changed 5 years ago by
That worked very well. As a safety precaution, I had it fallback to the BarakatCuntz algorithm if the Singular method failed to produce a basis but the arrangement was determined to be free.
comment:27 Changed 5 years ago by
 Commit changed from c5aba60b99292490dabae3009eaf29f9c9a9898b to 195bfbefce9bf0253f817e2034fbb53cc58e709f
Branch pushed to git repo; I updated commit sha1. New commits:
195bfbe  Minor reviewer changes

comment:28 Changed 5 years ago by
 Reviewers set to Miguel Marco
In some point (either the methods of the arrangement class, or the auxilar functions they call) there should be a check that the arrangement is central. Otherwise all these algorithms might not make sense. Right now things might fail at the to_symmetric_space
function, but a more informative error would be nice. I am adding it now.
Otherwise, it looks good. Let me pass the testsuite and check that the documentation builds correctly, and, if you are ok with my corrections, we can call it a day.
New commits:
195bfbe  Minor reviewer changes

comment:29 Changed 5 years ago by
 Commit changed from 195bfbefce9bf0253f817e2034fbb53cc58e709f to beb473a371b2d0adffe4d2f4c78864dca20c7a22
Branch pushed to git repo; I updated commit sha1. New commits:
beb473a  Checks for centrality

comment:30 Changed 5 years ago by
 Commit changed from beb473a371b2d0adffe4d2f4c78864dca20c7a22 to 1408d9ec3a57582dac739bbebe3626a296f5653b
Branch pushed to git repo; I updated commit sha1. New commits:
1408d9e  Some last little tweaks.

comment:31 Changed 5 years ago by
 Commit changed from 1408d9ec3a57582dac739bbebe3626a296f5653b to 1b6a6fc698646b0506631b0f3098a2106929eb4a
Branch pushed to git repo; I updated commit sha1. New commits:
1b6a6fc  Forgot one of Frederic's comments.

comment:32 Changed 5 years ago by
 Reviewers changed from Miguel Marco to Miguel Marco, Frédéric Chapoton.
That is good with me. I made some other little tweaks:
 Since we are removing the trailing whitespace, I changed the indentation to make things easier to read.
 I made the errors Python3 compatible and capitalized correctly (since they are not full sentences).
If you're happy with my changes, then positive review.
Thank you for doing the review.
comment:33 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:34 Changed 5 years ago by
 Status changed from positive_review to needs_work
Merge conflict, wait for the next beta...
comment:35 Changed 5 years ago by
 Commit changed from 1b6a6fc698646b0506631b0f3098a2106929eb4a to 7a960dba73d8d15e3a44d6047a7cf25284087bed
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
5087d23  oops

cd730ff  Merge branch 'public/ticket/19892' of trac.sagemath.org:sage into public/hyperplanes/check_free19595

9a2632b  Always 'moebius' instead of 'mobius'.

478f706  'moebius' instead of 'mobius'.

0cf597c  Charset and ...continuation.

3fa8102  Another ...continuation.

78da626  Double 'encoding' line removed.

2099e8a  No ö for string constants.

e62a430  Doctest corrections.

7a960db  Merge branch 'u/jmantysalo/ascii_version_of__m_bius___mobius_or_moebius_' of trac.sagemath.org:sage into public/hyperplanes/check_free19595

comment:36 Changed 5 years ago by
 Dependencies set to #19892 #19855
 Status changed from needs_work to positive_review
I looked at and merged in any ticket that was closed or on positive review that could have had a conflict with this one. Can you check again to see if this merges with your beta branch?
comment:37 Changed 5 years ago by
 Commit changed from 7a960dba73d8d15e3a44d6047a7cf25284087bed to 5c3c9b7de7c522138cc634db1ad2dd5e269cd990
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
5c3c9b7  Merge branch 'public/hyperplanes/check_free19595' of trac.sagemath.org:sage into public/hyperplanes/check_free19595

comment:38 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:39 Changed 5 years ago by
 Milestone changed from sage7.1 to sage7.2
 Status changed from positive_review to needs_info
There was no conflict, but you changed the branch anyways. Why?
comment:40 Changed 5 years ago by
 Status changed from needs_info to positive_review
Because it showed up as red on trac, and I wanted to make sure there would be no conflict with your branch.
comment:41 Changed 5 years ago by
Please don't make changes to positivelyreviewed tickets unless there is a real issue next time. If you don't get a conflict while merging then do not push.
comment:42 Changed 5 years ago by
 Branch changed from public/hyperplanes/check_free19595 to 5c3c9b7de7c522138cc634db1ad2dd5e269cd990
 Resolution set to fixed
 Status changed from positive_review to closed
comment:43 Changed 5 years ago by
 Commit 5c3c9b7de7c522138cc634db1ad2dd5e269cd990 deleted
 Reviewers changed from Miguel Marco, Frédéric Chapoton. to Miguel Marco, Frédéric Chapoton
New commits:
Initial implementation of a freeness check for hyperplane arrangements.