Implement Orlik-Solomon algebra of an arrangement

[kcrisman]

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]

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]

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]

Author: Travis Scrimshaw, William Slofstra

[tscrim]

Commit: 90a3fa0

[tscrim]

comment:4

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

---

New commits:

90a3fa0

Implementation of Orlik-Solomon algebras.

[tscrim]

Branch: public/algebras/orlik_solomon-18133

[sagetrac-git]

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

9a305aa

Doing a little more caching for speed.

[sagetrac-git]

Changed commit from 90a3fa0 to 9a305aa

[sagetrac-git]

Changed commit from 9a305aa to b077d31

[sagetrac-git]

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.

[sagetrac-git]

Changed commit from b077d31 to 4997564

[sagetrac-git]

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

1ee0f5a	Merge branch
4997564	some doc improvements

[sagetrac-git]

Changed commit from 4997564 to 2417129

[sagetrac-git]

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

2417129

more

[darijgr]

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.

[sagetrac-git]

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

6e2baab

properly implementing straightening rule

[sagetrac-git]

Changed commit from 2417129 to 6e2baab

[sagetrac-git]

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

48c8515

add an observation used in the algorithm

[sagetrac-git]

Changed commit from 6e2baab to 48c8515

[darijgr]

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

[sagetrac-git]

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

a7bcbad

postscript

[sagetrac-git]

Changed commit from 48c8515 to a7bcbad

[tscrim]

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.

[sagetrac-git]

Changed commit from 66a3be1 to bd1b8d7

[sagetrac-git]

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

d736c56

Added Orlik-Solomon algebra to the documentation.

[sagetrac-git]

Changed commit from bd1b8d7 to d736c56

[tscrim]

Reviewer: Darij Grinberg

[tscrim]

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.

[sagetrac-git]

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

cdc471a

more doctests

[sagetrac-git]

Changed commit from d736c56 to cdc471a

[darijgr]

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.

[sagetrac-git]

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

e51cb6d

A last little bit of doc tweaks.

[sagetrac-git]

Changed commit from cdc471a to e51cb6d

[sagetrac-git]

Changed commit from e51cb6d to ce4a0cb

[sagetrac-git]

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

ce4a0cb

Moving things around slightly.

[tscrim]

comment:32

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

[darijgr]

comment:33

Perfect!

[vbraun]

comment:34

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:
    Orlik-Solomon algebra of U(3, 4): Matroid of rank 3 on 4 elements
     with circuit-closures
     {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]

[sagetrac-git]

Changed commit from ce4a0cb to 48e46b6

[sagetrac-git]

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

48e46b6

Fixing trivial doctest failure.

[tscrim]

comment:36

Stupid me; trivial doctest fix.

[darijgr]

comment:37

Oops, that was me being stupid too. The only file I've run the tests on was orlik-solomon.py...

[vbraun]

Changed branch from public/algebras/orlik_solomon-18133 to 48e46b6