Opened 5 years ago
Closed 4 years ago
#18133 closed enhancement (fixed)
Implement OrlikSolomon algebra of an arrangement
Reported by:  kcrisman  Owned by:  

Priority:  major  Milestone:  sage7.1 
Component:  geometry  Keywords:  hyperplane arrangements 
Cc:  tscrim, Stefan, yomcat, chaoxu  Merged in:  
Authors:  Travis Scrimshaw, William Slofstra  Reviewers:  Darij Grinberg 
Report Upstream:  N/A  Work issues:  
Branch:  48e46b6 (Commits)  Commit:  48e46b6f7e353ff48eaf357435993c6418c9a31d 
Dependencies:  Stopgaps: 
Description
The OrlikSolomon algebra is a fundamental invariant for an arrangement, which also enables computing scads of useful information about e.g. the complement. But it's purely algebraic. So we should have it (see also #17506).
Change History (38)
comment:1 Changed 5 years ago by
 Cc tscrim added
comment:2 Changed 5 years ago by
comment:3 Changed 5 years ago by
Sure, anything you want! I'm not actually implementing this ticket :) Basically anything in Orlik/Terao? is great, so much of it is computational  I was kind of hoping the matroid folks would see this too. Actually, I thought some of this stuff was going to be in a 'nextgen' book by Alex, Dan and others but all I could find was a draft at Hal Schenck's website. It would be great to get Sage "officially" in that book in the same way it's in the Toric Varieties book he coauthored.
comment:4 Changed 5 years ago by
 Branch set to public/algebras/orlik_solomon18133
 Commit set to 90a3fa0c5f88a5f67cecad0d2e93fe3bd015f2e8
 Milestone changed from sage6.6 to sage6.10
 Status changed from new to needs_review
Here is an implementation based upon code given to me by William Slofstra.
New commits:
90a3fa0  Implementation of OrlikSolomon algebras.

comment:5 Changed 5 years ago by
 Commit changed from 90a3fa0c5f88a5f67cecad0d2e93fe3bd015f2e8 to 9a305aacea6858683268a7734281f1bebb4c793d
Branch pushed to git repo; I updated commit sha1. New commits:
9a305aa  Doing a little more caching for speed.

comment:6 Changed 5 years ago by
 Commit changed from 9a305aacea6858683268a7734281f1bebb4c793d to b077d3177ecd534d157b31c549ec8120cdcf2926
comment:7 Changed 5 years ago by
 Cc Stefan yomcat chaoxu added
comment:8 Changed 4 years ago by
 Commit changed from b077d3177ecd534d157b31c549ec8120cdcf2926 to 49975643ea588dbe60fbda6e22c87f8d86b5cbf7
comment:9 Changed 4 years ago by
 Commit changed from 49975643ea588dbe60fbda6e22c87f8d86b5cbf7 to 241712977960b49fc83984c11d07462b045352cf
Branch pushed to git repo; I updated commit sha1. New commits:
2417129  more

comment:10 followup: ↓ 15 Changed 4 years ago by
I didn't know that this algebra could be defined for any matroid! That's really nice.
On the other hand, I'm afraid the code doesn't properly iterate the reduction.
sage: M4 = matroids.CompleteGraphic(4) sage: OS = M4.orlik_solomon_algebra(QQ) sage: OS._reduce_broken_circuit(frozenset({2,3,4})) OS{1, 3, 4} + OS{1, 2, 3}  OS{1, 2, 4}
The result is malformed: {1, 3, 4} itself contains a broken circuit, so one of the monomials isn't actually a monomial. Now you could argue that this is an underscored method and might do with malformed results if the method calling it knows what it's doing, but first of all I'm not sure whether the CombinatorialFreeModule? framework will keep accepting such monomials in the future, and second I cannot guarantee that the multiplication as you implemented it still works with this implementation of _reduce_broken_circuit
.
The point is, reducing an element modulo the ideal J(M) is a multistep process, as clearing out one broken circuit might create another. If you do it until no more broken circuits remain, then I think your product is correct (though I'll have to take another look).
Another issue is the algebra_generators
: You're setting the i
th generator to be self.monomial(frozenset([i]))
, but this too might be malformed. (For example, if M
is a uniform matroid U_{n,1} = matroids.Uniform(1,n)
, then all basis elements are equal, which means that they cannot be distinct basis elements.)
I think both of these issues can be fixed at once. Let me do it.
comment:11 Changed 4 years ago by
 Commit changed from 241712977960b49fc83984c11d07462b045352cf to 6e2baab49d10865eb019f0ce0bf103a0949aa373
Branch pushed to git repo; I updated commit sha1. New commits:
6e2baab  properly implementing straightening rule

comment:12 Changed 4 years ago by
 Commit changed from 6e2baab49d10865eb019f0ce0bf103a0949aa373 to 48c8515db8a218362adb8665522dfa382eb63c8f
Branch pushed to git repo; I updated commit sha1. New commits:
48c8515  add an observation used in the algorithm

comment:13 followup: ↓ 16 Changed 4 years ago by
OK, the above points are done.
I am out of time now, so if anyone wants to take this over, feel free to do so. If not, I'll probably return to this in a week or so.
Meanwhile, here is one more question: Your implementation of the OrlikSolomon algebra for a hyperplane arrangement assumes that the base field of the algebra is that of the arrangement. Is that a reasonable assumption? (To me it sounds wrong  like studying the homology of real manifolds only with real coefficients.)
comment:14 Changed 4 years ago by
 Commit changed from 48c8515db8a218362adb8665522dfa382eb63c8f to a7bcbadf2efdd95ef76dd7d8b2744ae76b5d9f1a
Branch pushed to git repo; I updated commit sha1. New commits:
a7bcbad  postscript

comment:15 in reply to: ↑ 10 Changed 4 years ago by
Replying to darij:
On the other hand, I'm afraid the code doesn't properly iterate the reduction.
sage: M4 = matroids.CompleteGraphic(4) sage: OS = M4.orlik_solomon_algebra(QQ) sage: OS._reduce_broken_circuit(frozenset({2,3,4})) OS{1, 3, 4} + OS{1, 2, 3}  OS{1, 2, 4}The result is malformed: {1, 3, 4} itself contains a broken circuit, so one of the monomials isn't actually a monomial. Now you could argue that this is an underscored method and might do with malformed results if the method calling it knows what it's doing,
That was going to be my argument.
but first of all I'm not sure whether the CombinatorialFreeModule framework will keep accepting such monomials in the future,
It should because those checks are expensive and there has to be a way to tell this proposed CFM that you know what you're doing (especially in internal methods like _from_dict
).
and second I cannot guarantee that the multiplication as you implemented it still works with this implementation of
_reduce_broken_circuit
.The point is, reducing an element modulo the ideal J(M) is a multistep process, as clearing out one broken circuit might create another. If you do it until no more broken circuits remain, then I think your product is correct (though I'll have to take another look).
That is how the product was designed and why it worked. Although now you've basically pushed that into the recursive step. This also has an effect of making it recursive. Have you done some timing benchmarks between the two implementations?
Also this is bad:
if not type(S) == frozenset:
You should use the pythonic (and more robust if we replace it by some subclass of frozenset
):
if not isinstance(S, frozenset):
I can change this though.
Another issue is the
algebra_generators
: You're setting thei
th generator to beself.monomial(frozenset([i]))
, but this too might be malformed. (For example, ifM
is a uniform matroidU_{n,1} = matroids.Uniform(1,n)
, then all basis elements are equal, which means that they cannot be distinct basis elements.)
This is a good point. Good catch.
comment:16 in reply to: ↑ 13 Changed 4 years ago by
Replying to darij:
OK, the above points are done.
I am out of time now, so if anyone wants to take this over, feel free to do so. If not, I'll probably return to this in a week or so.
Thank you for taking a look at it and pushing some changes.
Meanwhile, here is one more question: Your implementation of the OrlikSolomon algebra for a hyperplane arrangement assumes that the base field of the algebra is that of the arrangement. Is that a reasonable assumption? (To me it sounds wrong  like studying the homology of real manifolds only with real coefficients.)
I can easily change this so the default is the base ring of the arrangement, but it can take another base ring as input. Although I think it carries less meaning in terms of studying the arrangement, but I'm not that much of an expert to know for certain.
comment:17 Changed 4 years ago by
I can easily change this so the default is the base ring of the arrangement, but it can take another base ring as input. Although I think it carries less meaning in terms of studying the arrangement, but I'm not that much of an expert to know for certain.
I don't have a copy of Orlik/Terao around to check but usually everything was complex anyway. But I did find this wherein the coefficients are in the field of two elements, though the definitions are not quite the same as just taking the OS algebra over two elements as its base field. Wikipedia says you can take any subring of the base field but I don't know I'd trust that without reading the final version of this a bit more. If one of you knows one of these guys one could ask; I haven't talked to any of them in quite a while.
comment:18 Changed 4 years ago by
The Proudfoot reference you linked makes it clear to me that the base ring of the algerba should not have anything to do with the base ring of the arrangement.
comment:19 Changed 4 years ago by
Technical question... can we rely on frozensets being indices of a combinatorial free module? They don't compare well:
sage: frozenset([2]) < frozenset([3]) False sage: frozenset([3]) < frozenset([2]) False sage: frozenset([3]) == frozenset([2]) False sage: frozenset([2]) > frozenset([3]) False
comment:20 Changed 4 years ago by
 Commit changed from a7bcbadf2efdd95ef76dd7d8b2744ae76b5d9f1a to 114516ca029fd9eaa005dd0c81bd156cda82fff2
Branch pushed to git repo; I updated commit sha1. New commits:
114516c  simplify product_on_basis (the reduction logic is now in subset_image)

comment:21 Changed 4 years ago by
 Commit changed from 114516ca029fd9eaa005dd0c81bd156cda82fff2 to 6b889214128ef37dc26467cbbc6cb0547b7327aa
Branch pushed to git repo; I updated commit sha1. New commits:
6b88921  correct my algorithm

comment:22 Changed 4 years ago by
 Commit changed from 6b889214128ef37dc26467cbbc6cb0547b7327aa to 28eb8c628b588d4067e3dda0accccf71f4c87496
Branch pushed to git repo; I updated commit sha1. New commits:
28eb8c6  allow choice of base ring for hyperplane arrangements

comment:23 Changed 4 years ago by
In other news, I've mathreviewed the ticket. What remains to be done:
 Better doctests, e.g., one that would have caught my bug in
subset_image
. We don't have any nonstandard orderings, and we don't have any interesting matroids. I'd like an example with a matroid given by a graph with 3 vertices and 2 edges between each two distinct vertices.
 The frozenset issue mentioned above. Maybe switch to sorted lists?
comment:24 Changed 4 years ago by
 Commit changed from 28eb8c628b588d4067e3dda0accccf71f4c87496 to 66a3be16592de768a2784e870c763c1310258d48
Branch pushed to git repo; I updated commit sha1. New commits:
989b6ea  Adding changes from #19821.

6358d53  Cythonized matrix_gp/group_element.py and simplified the class structure.

65ce465  Fixing modform_hecketriangle due to changes.

1110926  Fixing last doctests.

3efe9b6  Merge branch 'develop' into public/groups/cythonize_matrix_group_element19870

29f7253  Special case for dense matrices over ZZ and making sure the inverse is in the base ring.

75217a8  Merge branch 'public/algebras/orlik_solomon18133' of trac.sagemath.org:sage into public/algebras/orlik_solomon18133

66a3be1  Implementing term comparisons and adding more doctests.

comment:25 Changed 4 years ago by
 Commit changed from 66a3be16592de768a2784e870c763c1310258d48 to bd1b8d7e3ee25b6babddb6291d1dd84d0b156a10
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
bd1b8d7  Implementing term comparisons and adding more doctests.

comment:26 Changed 4 years ago by
 Commit changed from bd1b8d7e3ee25b6babddb6291d1dd84d0b156a10 to d736c5652730d0db933cd3112e1ee18c7e040f1b
Branch pushed to git repo; I updated commit sha1. New commits:
d736c56  Added OrlikSolomon algebra to the documentation.

comment:27 Changed 4 years ago by
 Milestone changed from sage6.10 to sage7.1
 Reviewers set to Darij Grinberg
Whoops, sorry; bad merge. You can safely ignore comment:24.
I fixed any issues with comparisons using frozenset
by implementing a term comparison function. I also added a few more doctests. Thanks for changing the behavior for creating the OrlikSolomon. I'm happy with the current version. If you are too (and there are no other objectios), then we can set a positive review.
comment:28 Changed 4 years ago by
 Commit changed from d736c5652730d0db933cd3112e1ee18c7e040f1b to cdc471a9ef1925e6f2aaacfb865cfae1265e7df2
Branch pushed to git repo; I updated commit sha1. New commits:
cdc471a  more doctests

comment:29 Changed 4 years ago by
Thanks! This fixes it.
The code looks good to me now. Feel free to set it to positive_review, or wait for others to comment, if you feel so inclined.
comment:30 Changed 4 years ago by
 Commit changed from cdc471a9ef1925e6f2aaacfb865cfae1265e7df2 to e51cb6d24408ada7797dcb8cf2ed7fd7d52a5f01
Branch pushed to git repo; I updated commit sha1. New commits:
e51cb6d  A last little bit of doc tweaks.

comment:31 Changed 4 years ago by
 Commit changed from e51cb6d24408ada7797dcb8cf2ed7fd7d52a5f01 to ce4a0cba05f4c593cc1942f9104cf4c7bf902951
Branch pushed to git repo; I updated commit sha1. New commits:
ce4a0cb  Moving things around slightly.

comment:32 Changed 4 years ago by
Back to you; if you're happy with my changes, then you can set a positive review. Thanks.
comment:34 Changed 4 years ago by
 Status changed from positive_review to needs_work
sage t long src/sage/matroids/matroid.pyx ********************************************************************** File "src/sage/matroids/matroid.pyx", line 2912, in sage.matroids.matroid.Matroid.orlik_solomon_algebra Failed example: OS = M.orlik_solomon_algebra(QQ) Expected: OrlikSolomon algebra of U(3, 4): Matroid of rank 3 on 4 elements with circuitclosures {3: {{0, 1, 2, 3}}} Got: <BLANKLINE> ********************************************************************** 1 item had failures: 1 of 3 in sage.matroids.matroid.Matroid.orlik_solomon_algebra [775 tests, 1 failure, 2.64 s]
comment:35 Changed 4 years ago by
 Commit changed from ce4a0cba05f4c593cc1942f9104cf4c7bf902951 to 48e46b6f7e353ff48eaf357435993c6418c9a31d
Branch pushed to git repo; I updated commit sha1. New commits:
48e46b6  Fixing trivial doctest failure.

comment:36 Changed 4 years ago by
 Status changed from needs_work to positive_review
Stupid me; trivial doctest fix.
comment:37 Changed 4 years ago by
Oops, that was me being stupid too. The only file I've run the tests on was orliksolomon.py...
comment:38 Changed 4 years ago by
 Branch changed from public/algebras/orlik_solomon18133 to 48e46b6f7e353ff48eaf357435993c6418c9a31d
 Resolution set to fixed
 Status changed from positive_review to closed
how about algebras generated by reciprocals of linear forms of hyperplanes of the arrangement (cf e.g. http://arxiv.org/abs/math/0105095) ?