Implement Orlik-Solomon algebra of an arrangement

kcrisman commented 9 years ago

The Orlik-Solomon 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).

CC: @tscrim @sagetrac-Stefan @sagetrac-yomcat @chaoxu

Component: geometry

Keywords: hyperplane arrangements

Author: Travis Scrimshaw, William Slofstra

Branch/Commit: 48e46b6

Reviewer: Darij Grinberg

Issue created by migration from https://trac.sagemath.org/ticket/18133

dimpase commented 9 years ago

comment:2

how about algebras generated by reciprocals of linear forms of hyperplanes of the arrangement (cf e.g. http://arxiv.org/abs/math/0105095) ?

kcrisman commented 9 years ago

comment:3

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 'next-gen' 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.

tscrim commented 9 years ago

Author: Travis Scrimshaw, William Slofstra

tscrim commented 9 years ago

Commit: 90a3fa0

tscrim commented 9 years ago

comment:4

Here is an implementation based upon code given to me by William Slofstra.

New commits:

90a3fa0 Implementation of Orlik-Solomon algebras.

tscrim commented 9 years ago

Branch: public/algebras/orlik_solomon-18133

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

9a305aa Doing a little more caching for speed.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 90a3fa0 to 9a305aa

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 9a305aa to b077d31

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

`2ae367f`	`Merge branch 'public/algebras/orlik_solomon-18133' of trac.sagemath.org:sage into public/algebras/orlik_solomon-18133`
`b077d31`	`A few little doc tweaks.`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from b077d31 to 4997564

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

`1ee0f5a`	`Merge branch`
`4997564`	`some doc improvements`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 4997564 to 2417129

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

2417129 more

darijgr commented 8 years ago

comment:10

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

6e2baab properly implementing straightening rule

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 2417129 to 6e2baab

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

48c8515 add an observation used in the algorithm

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 6e2baab to 48c8515

darijgr commented 8 years ago

comment:13

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 Orlik-Solomon 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.)

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

a7bcbad postscript

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 48c8515 to a7bcbad

tscrim commented 8 years ago

comment:15

Replying to @darijgr:

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 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.)

This is a good point. Good catch.

tscrim commented 8 years ago

comment:16

Replying to @darijgr:

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 Orlik-Solomon 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.

kcrisman commented 8 years ago

comment:17

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.

darijgr commented 8 years ago

comment:18

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.

darijgr commented 8 years ago

comment:19

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

114516c simplify product_on_basis (the reduction logic is now in subset_image)

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from a7bcbad to 114516c

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

6b88921 correct my algorithm

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 114516c to 6b88921

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

28eb8c6 allow choice of base ring for hyperplane arrangements

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 6b88921 to 28eb8c6

darijgr commented 8 years ago

comment:23

In other news, I've math-reviewed 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?

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 28eb8c6 to 66a3be1

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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_element-19870`
`29f7253`	`Special case for dense matrices over ZZ and making sure the inverse is in the base ring.`
`75217a8`	`Merge branch 'public/algebras/orlik_solomon-18133' of trac.sagemath.org:sage into public/algebras/orlik_solomon-18133`
`66a3be1`	`Implementing term comparisons and adding more doctests.`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

bd1b8d7 Implementing term comparisons and adding more doctests.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 66a3be1 to bd1b8d7

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

d736c56 Added Orlik-Solomon algebra to the documentation.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from bd1b8d7 to d736c56

tscrim commented 8 years ago

Reviewer: Darij Grinberg

tscrim commented 8 years ago

comment:27

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 Orlik-Solomon. I'm happy with the current version. If you are too (and there are no other objectios), then we can set a positive review.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

cdc471a more doctests

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from d736c56 to cdc471a

darijgr commented 8 years ago

comment:29

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

e51cb6d A last little bit of doc tweaks.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from cdc471a to e51cb6d

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from e51cb6d to ce4a0cb

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

ce4a0cb Moving things around slightly.

tscrim commented 8 years ago

comment:32

Back to you; if you're happy with my changes, then you can set a positive review. Thanks.

sagemath / sage

Implement Orlik-Solomon algebra of an arrangement #18133