Opened 5 years ago

Closed 4 years ago

#18133 closed enhancement (fixed)

Implement Orlik-Solomon algebra of an arrangement

Reported by: kcrisman Owned by:
Priority: major Milestone: sage-7.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 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).

Change History (38)

comment:1 Changed 5 years ago by tscrim

  • Cc tscrim added

comment:2 Changed 5 years ago by dimpase

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

comment:3 Changed 5 years ago by kcrisman

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.

comment:4 Changed 5 years ago by tscrim

  • Authors set to Travis Scrimshaw, William Slofstra
  • Branch set to public/algebras/orlik_solomon-18133
  • Commit set to 90a3fa0c5f88a5f67cecad0d2e93fe3bd015f2e8
  • Milestone changed from sage-6.6 to sage-6.10
  • Status changed from new to needs_review

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


New commits:

90a3fa0Implementation of Orlik-Solomon algebras.

comment:5 Changed 5 years ago by git

  • Commit changed from 90a3fa0c5f88a5f67cecad0d2e93fe3bd015f2e8 to 9a305aacea6858683268a7734281f1bebb4c793d

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

9a305aaDoing a little more caching for speed.

comment:6 Changed 5 years ago by git

  • Commit changed from 9a305aacea6858683268a7734281f1bebb4c793d to b077d3177ecd534d157b31c549ec8120cdcf2926

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

2ae367fMerge branch 'public/algebras/orlik_solomon-18133' of trac.sagemath.org:sage into public/algebras/orlik_solomon-18133
b077d31A few little doc tweaks.

comment:7 Changed 5 years ago by tscrim

  • Cc Stefan yomcat chaoxu added

comment:8 Changed 4 years ago by git

  • Commit changed from b077d3177ecd534d157b31c549ec8120cdcf2926 to 49975643ea588dbe60fbda6e22c87f8d86b5cbf7

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

1ee0f5aMerge branch
4997564some doc improvements

comment:9 Changed 4 years ago by git

  • Commit changed from 49975643ea588dbe60fbda6e22c87f8d86b5cbf7 to 241712977960b49fc83984c11d07462b045352cf

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

2417129more

comment:10 follow-up: Changed 4 years ago by darij

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 git

  • Commit changed from 241712977960b49fc83984c11d07462b045352cf to 6e2baab49d10865eb019f0ce0bf103a0949aa373

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

6e2baabproperly implementing straightening rule

comment:12 Changed 4 years ago by git

  • Commit changed from 6e2baab49d10865eb019f0ce0bf103a0949aa373 to 48c8515db8a218362adb8665522dfa382eb63c8f

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

48c8515add an observation used in the algorithm

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

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

comment:14 Changed 4 years ago by git

  • Commit changed from 48c8515db8a218362adb8665522dfa382eb63c8f to a7bcbadf2efdd95ef76dd7d8b2744ae76b5d9f1a

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

a7bcbadpostscript

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

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

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

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

comment:17 Changed 4 years ago by kcrisman

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 darij

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 darij

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 git

  • Commit changed from a7bcbadf2efdd95ef76dd7d8b2744ae76b5d9f1a to 114516ca029fd9eaa005dd0c81bd156cda82fff2

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

114516csimplify product_on_basis (the reduction logic is now in subset_image)

comment:21 Changed 4 years ago by git

  • Commit changed from 114516ca029fd9eaa005dd0c81bd156cda82fff2 to 6b889214128ef37dc26467cbbc6cb0547b7327aa

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

6b88921correct my algorithm

comment:22 Changed 4 years ago by git

  • Commit changed from 6b889214128ef37dc26467cbbc6cb0547b7327aa to 28eb8c628b588d4067e3dda0accccf71f4c87496

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

28eb8c6allow choice of base ring for hyperplane arrangements

comment:23 Changed 4 years ago by darij

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?

comment:24 Changed 4 years ago by git

  • Commit changed from 28eb8c628b588d4067e3dda0accccf71f4c87496 to 66a3be16592de768a2784e870c763c1310258d48

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

989b6eaAdding changes from #19821.
6358d53Cythonized matrix_gp/group_element.py and simplified the class structure.
65ce465Fixing modform_hecketriangle due to changes.
1110926Fixing last doctests.
3efe9b6Merge branch 'develop' into public/groups/cythonize_matrix_group_element-19870
29f7253Special case for dense matrices over ZZ and making sure the inverse is in the base ring.
75217a8Merge branch 'public/algebras/orlik_solomon-18133' of trac.sagemath.org:sage into public/algebras/orlik_solomon-18133
66a3be1Implementing term comparisons and adding more doctests.

comment:25 Changed 4 years ago by git

  • Commit changed from 66a3be16592de768a2784e870c763c1310258d48 to bd1b8d7e3ee25b6babddb6291d1dd84d0b156a10

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

bd1b8d7Implementing term comparisons and adding more doctests.

comment:26 Changed 4 years ago by git

  • Commit changed from bd1b8d7e3ee25b6babddb6291d1dd84d0b156a10 to d736c5652730d0db933cd3112e1ee18c7e040f1b

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

d736c56Added Orlik-Solomon algebra to the documentation.

comment:27 Changed 4 years ago by tscrim

  • Milestone changed from sage-6.10 to sage-7.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 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.

comment:28 Changed 4 years ago by git

  • Commit changed from d736c5652730d0db933cd3112e1ee18c7e040f1b to cdc471a9ef1925e6f2aaacfb865cfae1265e7df2

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

cdc471amore doctests

comment:29 Changed 4 years ago by darij

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 git

  • Commit changed from cdc471a9ef1925e6f2aaacfb865cfae1265e7df2 to e51cb6d24408ada7797dcb8cf2ed7fd7d52a5f01

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

e51cb6dA last little bit of doc tweaks.

comment:31 Changed 4 years ago by git

  • Commit changed from e51cb6d24408ada7797dcb8cf2ed7fd7d52a5f01 to ce4a0cba05f4c593cc1942f9104cf4c7bf902951

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

ce4a0cbMoving things around slightly.

comment:32 Changed 4 years ago by tscrim

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

comment:33 Changed 4 years ago by darij

  • Status changed from needs_review to positive_review

Perfect!

comment:34 Changed 4 years ago by vbraun

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

comment:35 Changed 4 years ago by git

  • Commit changed from ce4a0cba05f4c593cc1942f9104cf4c7bf902951 to 48e46b6f7e353ff48eaf357435993c6418c9a31d

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

48e46b6Fixing trivial doctest failure.

comment:36 Changed 4 years ago by tscrim

  • Status changed from needs_work to positive_review

Stupid me; trivial doctest fix.

comment:37 Changed 4 years ago by darij

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

comment:38 Changed 4 years ago by vbraun

  • Branch changed from public/algebras/orlik_solomon-18133 to 48e46b6f7e353ff48eaf357435993c6418c9a31d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.