Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#19595 closed enhancement (fixed)

Implement a check that a hyperplane arrangement is free

Reported by: tscrim Owned by: tscrim
Priority: major Milestone: sage-7.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) Commit:
Dependencies: #19892 #19855 Stopgaps:

Description (last modified by tscrim)

We follow Barakat and Cuntz in arXiv:1011.4228 to check if a hyperplane arrangement is free.

Change History (43)

comment:1 Changed 4 years ago by tscrim

  • Branch set to public/hyperplanes/check_free-19595
  • Cc vbraun chapoton added
  • Commit set to ca31fa9d4d55a5ed1093b5f46790ca9994a0926b
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

ca31fa9Initial implementation of a freeness check for hyperplane arrangements.

comment:2 Changed 4 years ago by git

  • Commit changed from ca31fa9d4d55a5ed1093b5f46790ca9994a0926b to 05385db408dd73295ed477ee874c1478823f1349

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

0ec78f7Merge branch 'public/hyperplanes/check_free-19595' of trac.sagemath.org:sage into public/hyperplanes/check_free-19595
05385dbMultiplication order was backwards for derivation_module_basis.

comment:3 Changed 4 years ago by git

  • Commit changed from 05385db408dd73295ed477ee874c1478823f1349 to b3db54c53f3a571f7408e14b7274ed9c9f00feaf

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

b3db54cChanging the output format of derivation_module_basis and added some more doc.

comment:4 follow-up: Changed 4 years ago by chapoton

  • 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 4 years ago by chapoton

  • Milestone changed from sage-6.10 to sage-7.0

comment:6 in reply to: ↑ 4 ; follow-up: Changed 4 years ago by 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 double-check 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 4 years ago by git

  • Commit changed from b3db54c53f3a571f7408e14b7274ed9c9f00feaf to 05d7517656a9d911f6d97cc875bd82afb9f30f07

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

cb93a15Merge branch 'public/hyperplanes/check_free-19595' of trac.sagemath.org:sage into public/hyperplanes/check_free-19595
05d7517Moving file and being more restrictive on to_symmetric space.

comment:8 in reply to: ↑ 6 Changed 4 years ago by tscrim

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 double-check 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 4 years ago by git

  • Commit changed from 05d7517656a9d911f6d97cc875bd82afb9f30f07 to b10a0c819f1b50869ba620be849bbd12d199c146

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

b10a0c8trac #1959 correct import

comment:10 Changed 4 years ago by 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?

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 follow-up: Changed 4 years ago by mmarco

Another question: is this granted to work for non crystalographic arrangements?

comment:12 Changed 4 years ago by mmarco

  • Cc mmarco added

comment:13 in reply to: ↑ 11 Changed 4 years ago by tscrim

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 not-necessarily-free 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)
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?

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 follow-up: Changed 4 years ago by 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?

comment:15 in reply to: ↑ 14 Changed 4 years ago by tscrim

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 4 years ago by mmarco

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 4 years ago by git

  • Commit changed from b10a0c819f1b50869ba620be849bbd12d199c146 to 38923f5933b6745a2506cfa71ce7368b9287dcad

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

180373aMerge branch 'public/hyperplanes/check_free-19595' of trac.sagemath.org:sage into public/hyperplanes/check_free-19595
38923f5Implemented backtracking in Barakat-Cuntz algorithm and a version using Singular.

comment:18 Changed 4 years ago by git

  • Commit changed from 38923f5933b6745a2506cfa71ce7368b9287dcad to dda0ab3d40972798cf18394d91eabf56418f36e5

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

dda0ab3Use the standard copyright template.

comment:19 Changed 4 years ago by tscrim

  • Milestone changed from sage-7.0 to sage-7.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 A3 and B3), 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 follow-up: Changed 4 years ago by 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.

Let me think about it for a few days.

comment:21 in reply to: ↑ 20 Changed 4 years ago by tscrim

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 4 years ago by mmarco

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 4 years ago by tscrim

Actually, from my testing using inversion arrangements, the syzygy module often results in a non-square 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_basis-19595

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 as-is for now and do a follow-up ticket for finding a faster way to construct the basis?

comment:24 Changed 4 years ago by mmarco

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( x-z, y-z, 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 4 years ago by git

  • Commit changed from dda0ab3d40972798cf18394d91eabf56418f36e5 to c5aba60b99292490dabae3009eaf29f9c9a9898b

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

c5aba60Added Singular algorithm for constructing a basis.

comment:26 Changed 4 years ago by tscrim

That worked very well. As a safety precaution, I had it fallback to the Barakat-Cuntz algorithm if the Singular method failed to produce a basis but the arrangement was determined to be free.

comment:27 Changed 4 years ago by git

  • Commit changed from c5aba60b99292490dabae3009eaf29f9c9a9898b to 195bfbefce9bf0253f817e2034fbb53cc58e709f

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

195bfbeMinor reviewer changes

comment:28 Changed 4 years ago by mmarco

  • 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:

195bfbeMinor reviewer changes

comment:29 Changed 4 years ago by git

  • Commit changed from 195bfbefce9bf0253f817e2034fbb53cc58e709f to beb473a371b2d0adffe4d2f4c78864dca20c7a22

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

beb473aChecks for centrality

comment:30 Changed 4 years ago by git

  • Commit changed from beb473a371b2d0adffe4d2f4c78864dca20c7a22 to 1408d9ec3a57582dac739bbebe3626a296f5653b

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

1408d9eSome last little tweaks.

comment:31 Changed 4 years ago by git

  • Commit changed from 1408d9ec3a57582dac739bbebe3626a296f5653b to 1b6a6fc698646b0506631b0f3098a2106929eb4a

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

1b6a6fcForgot one of Frederic's comments.

comment:32 Changed 4 years ago by tscrim

  • 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 4 years ago by mmarco

  • Status changed from needs_review to positive_review

comment:34 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict, wait for the next beta...

comment:35 Changed 4 years ago by git

  • Commit changed from 1b6a6fc698646b0506631b0f3098a2106929eb4a to 7a960dba73d8d15e3a44d6047a7cf25284087bed

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

5087d23oops
cd730ffMerge branch 'public/ticket/19892' of trac.sagemath.org:sage into public/hyperplanes/check_free-19595
9a2632bAlways 'moebius' instead of 'mobius'.
478f706'moebius' instead of 'mobius'.
0cf597cCharset and ...-continuation.
3fa8102Another ...-continuation.
78da626Double 'encoding' line removed.
2099e8aNo ö for string constants.
e62a430Doctest corrections.
7a960dbMerge branch 'u/jmantysalo/ascii_version_of__m_bius___mobius_or_moebius_' of trac.sagemath.org:sage into public/hyperplanes/check_free-19595

comment:36 Changed 4 years ago by tscrim

  • 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 4 years ago by git

  • 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:

5c3c9b7Merge branch 'public/hyperplanes/check_free-19595' of trac.sagemath.org:sage into public/hyperplanes/check_free-19595

comment:38 Changed 4 years ago by tscrim

  • Status changed from needs_review to positive_review

comment:39 Changed 4 years ago by vbraun

  • Milestone changed from sage-7.1 to sage-7.2
  • Status changed from positive_review to needs_info

There was no conflict, but you changed the branch anyways. Why?

comment:40 Changed 4 years ago by tscrim

  • 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 4 years ago by vbraun

Please don't make changes to positively-reviewed 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 4 years ago by vbraun

  • Branch changed from public/hyperplanes/check_free-19595 to 5c3c9b7de7c522138cc634db1ad2dd5e269cd990
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:43 Changed 4 years ago by jdemeyer

  • Commit 5c3c9b7de7c522138cc634db1ad2dd5e269cd990 deleted
  • Reviewers changed from Miguel Marco, Frédéric Chapoton. to Miguel Marco, Frédéric Chapoton
Note: See TracTickets for help on using tickets.