Implement simplicial sets

[jhpalmieri]

As the summary says...

For possible follow-up tickets:

• simplicial abelian groups and Eilenberg-Mac Lane spaces.
• effective homology and related computations that Kenzo can do but we can't yet.
• mapping spaces.
• Discrete Morse theory.
• universal covering spaces for classifying spaces, support for maps between infinite simplicial sets.

CC: @tscrim @sagetrac-jeremy-l-martin @cnassau

Component: algebraic topology

Keywords: days74

Author: John Palmieri

Branch: 35790d2

Reviewer: Christian Nassau

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

[jhpalmieri]

comment:1

Here is an initial implementation. It is not ready for review.

---

New commits:

b63026d	simplicial sets, initial implementation
de4e351	simplicial sets: construct CP^n using Kenzo output.

[jhpalmieri]

Branch: u/jhpalmieri/simplicial_sets

[jhpalmieri]

Commit: de4e351

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

7e8f261

Simplicial sets: delete code for pushouts: it is incomplete and broken.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from de4e351 to 7e8f261

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7e8f261 to 05bf228

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

9bc215b	Simplicial sets: pushouts, etc.
05bf228	Merge branch 'develop' into t/20745/simplicial_sets

[jhpalmieri]

comment:4

Pushouts are now fixed.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

b3eb08e

Simplicial sets: full-fledged pushouts and pullbacks

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 05bf228 to b3eb08e

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b3eb08e to c5f3a75

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

23ae53e	Merge branch 'develop' into t/20745/simplicial_sets
c5f3a75	simplicial sets: trivial changes to nerve construction

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c5f3a75 to 37f505e

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

5f73a44	simplicial sets: fix stupidity
bbee5f8	Simplicial sets: implement possibly infinite simplicial sets.
37f505e	Simplicial sets: simplicial model for the Hopf fibration.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

7d4e7e5

Simplicial sets: simplicial model for the Hopf fibration.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 37f505e to 7d4e7e5

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

4fa2921	Simplicial sets: define the constant map between pointed simplicial sets.
b9d40ee	Simplicial sets: iterator (slow!) for sets of morphisms.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7d4e7e5 to b9d40ee

[jhpalmieri]

comment:11

I'm marking this as "needs review" now. One possible future development: mapping spaces for simplicial sets: given simplicial sets K and L, you can view Hom(K,L) as a simplicial set. This would be another example of an infinite simplicial set, so any computations would be done using an appropriate n-skeleton.

[jhpalmieri]

Author: John Palmieri

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b9d40ee to 899e569

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

899e569

Fix some Sphinx references.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1230ce1

Simplicial sets: products and coproducts of maps.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 899e569 to 1230ce1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1230ce1 to 9fbfee6

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a518237	Add is_connected method to generic cell complexes.
8b615cd	simplicial sets: start to improve implementation for infinite simplicial sets
d0b13d9	merging with 7.3.beta9
c1ddea1	Simplicial sets: improve implementation for infinite simplicial sets.
56620b7	simplicial sets: make smash product class inherit from Factors.
d41a256	simplicial set: change a little terminology.
456eb80	fix some whitespace
ac7f6ea	simplicial sets: minor editing of docstrings, some reorganization
e628254	simplicial sets: documentation in categories/simplicial_sets.py
9fbfee6	Simplicial sets: make Pushout, Pullback, etc., inherit from UniqueRepresentation:

[jhpalmieri]

comment:18

I'm marking this as "needs_review" now.

[jhpalmieri]

Description changed:

--- 
+++ 
@@ -1 +1,8 @@
 As the summary says...
+
+For possible follow-up tickets:
+
+- simplicial abelian groups and Eilenberg-Mac Lane spaces.
+- effective homology and related computations that Kenzo can do but we can't yet.
+- mapping spaces.
+

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9fbfee6 to bcb0332

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

bcb0332

disambiguate two references

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from bcb0332 to 94c21df

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

8522c66	Merge branch 'develop' into simplicial_sets
94c21df	disambiguate two references

[cnassau]

comment:21

This looks like a lot of very nice and very useful code! I have just started to play around with it and have two quick comments:

• SimplicialSets is not in the global namespace, whereas SimplicialComplex is globally available per default.

• I tried TestSuite(RP7).run() and got lots of errors, presumably because an_element is not implemented.

I have no fixed opinion whether these observations count as faults or facts, though.

[jhpalmieri]

comment:23

Hi Christian, thanks for taking a look!

Replying to @cnassau:

This looks like a lot of very nice and very useful code! I have just started to play around with it and have two quick comments:

• SimplicialSets is not in the global namespace, whereas SimplicialComplex is globally available per default.

It is more fiddly to construct simplicial sets than simplicial complexes, to the point that I don't know if ordinary users will want to use SimplicialSet much. (With hindsight, I would also not have included DeltaComplex in the global namespace either.) My hope is that users will use the predefined simplicial sets (especially simplices and spheres) and build other simplicial sets from those using quotients, products, mapping cones, etc.

• I tried TestSuite(RP7).run() and got lots of errors, presumably because an_element is not implemented.

I didn't try that. It might be worth looking into.

[cnassau]

comment:24

I just tried (and eventually succeeded) to construct the quotient RP7/RP4 and to compute its cohomology. My first approach failed, since I found no way to define the inclusion map:

sage: RP4 = sage.homology.simplicial_set_catalog.RealProjectiveSpace(4)
sage: RP7 = sage.homology.simplicial_set_catalog.RealProjectiveSpace(7)
sage: X=Hom(RP4,RP7)
sage: X({i:i for i in RP4.nondegenerate_simplices()})
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
...
ValueError: this simplex is not in this simplicial set

Can this be done somehow?

A possibly related problem is that the ambient spaces are different; maybe they (and the projective spaces) should have unique representation?

sage: RP4.ambient_space() is RP7.ambient_space()
False

(Apologies if this is explained in the documentation somewhere - I usually only read documentation as a last resort.)

[jhpalmieri]

comment:25

I thought about unique representation; my conclusion was that it was the wrong thing to do. If you construct two 4-spheres, you want them to be different so you can take their disjoint union, etc. A related implementation detail is that when you construct an abstract n-simplex, it is always distinct from previously created ones.

The easiest way to do what you're talking about is

sage: RP7 = simplicial_sets.RealProjectiveSpace(7)
sage: RP4 = RP7.n_skeleton(4)
sage: RP4.inclusion_map()
...
sage: RP7.quotient(RP4)
...

Or I think you also do

sage: C2 = groups.misc.MultiplicativeAbelian([2])
sage: BC2 = simplicial_sets.ClassifyingSpace(C2)
sage: RP7 = BC2.n_skeleton(7)
sage: RP4 = BC2.n_skeleton(4)

to get a common ambient space.

[cnassau]

comment:26

Replying to @jhpalmieri:

I thought about unique representation; my conclusion was that it was the wrong thing to do. If you construct two 4-spheres, you want them to be different so you can take their disjoint union, etc. A related implementation detail is that when you construct an abstract n-simplex, it is always distinct from previously created ones.

I get your point and I now see that this is also very well explained in the documentation.

I don't understand the origin of the term f_vector: I can see that this is also used in the other cell complex related parts, but what might the "f" stand for? I'm just curious here...

[jhpalmieri]

comment:27

"f-vector" is standard in combinatorics, but I don't know what the "f" means. "face", I'm guessing?

[cnassau]

comment:28

I have just tried to implement the "Catalan simplicial set", modeled on your code for the nerve of a monoid. It seems to work fine, but I get this error from all_n_simplices:

sage: Cat.all_n_simplices(3)
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
...
NotImplementedError: this simplicial set may be infinite, so specify max_dim

I think this could be fixed by changing one line in the definition of all_n_simplices, i.e. change

 non_degen = [_ for _ in self.nondegenerate_simplices() if _.dimension() <= n]

to

 non_degen = [_ for _ in self.nondegenerate_simplices(max_dim=n) if _.dimension() <= n]

I have noted that the classifying spaces currently do not have an "all_n_simplices" method.

sage: X
Classifying space of Finite Field of size 3
sage: X.all_n_simplices(5)
...
AttributeError: 'Nerve_with_category' object has no attribute 'all_n_simplices'

Is this deliberate?

[jhpalmieri]

comment:29

This isn't deliberate. I think it's a good idea to make the change you suggest and to implement all_n_simplices for classifying spaces. I'm testing this right now; I'll push the change if it works.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 94c21df to 8dac891

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

6eb29f4	Merge branch 'develop' into simplicial_sets
8dac891	simplicial sets: move all_n_simplices from the class of finite

[cnassau]

comment:31

It seems there are some other calls to nondegenerate_simplices(...) that should have an approriate max_dim value: if I try to compute the homology of this Catalan simplicial set I otherwise get an error:

sage: Cat.chain_complex(dimensions=range(5))
...
NotImplementedError: this simplicial set may be infinite, so specify max_dim

I'm attaching my code so that you can see what I'm doing.

One strange thing is that my Cat has a couple of useful methods (e.g. homology) that are missing from the classifying spaces. The only relevant difference that I'm aware of is their categories, though that should add more methods, not hide them:

sage: Cat.categories()
[Category of simplicial sets,
 Category of sets,
 Category of sets with partial maps,
 Category of objects]
sage: simplicial_sets.ClassifyingSpace(GF(3)).categories()
[Category of pointed simplicial sets,
 Category of simplicial sets,
 Category of sets,
 Category of sets with partial maps,
 Category of objects]

I think something like

simplicial_sets.ClassifyingSpace(GF(3)).betti(3)

should probably work out of the box (i.e. without explicitly taking a skeleton).

[cnassau]

implementation of the catalan simplicial set

[jhpalmieri]

comment:32

Attachment: catalan.py.gz

Replying to @cnassau:

It seems there are some other calls to nondegenerate_simplices(...) that should have an approriate max_dim value: if I try to compute the homology of this Catalan simplicial set I otherwise get an error:

The issue here is that your Cat inherits from SimplicialSet:

sage: sage.homology.simplicial_set.SimplicialSet?
Init signature: sage.homology.simplicial_set.SimplicialSet(self, data, base_point=None, name=None, check=True, category=None)
Docstring:     
   A finite simplicial set.

   ...

So it is assumed to be finite, which means it has more methods defined for it, like chain_complex, which are not defined for (for example) classifying spaces. Classifying spaces instead inherit from SimplicialSet_arbitrary. Note that SimplicialSet is just an alias for SimplicialSet_finite, and we could get rid of this alias and delete SimplicialSet if it would be clearer that way.

I think something like

simplicial_sets.ClassifyingSpace(GF(3)).betti(3)

should probably work out of the box (i.e. without explicitly taking a skeleton).

Methods like betti come from the class GenericCellComplex, and those are assumed to be finite. So we would need to implement betti for SimplicialSet_arbitrary, which we could do. Maybe also chain_complex and n_chains.

[tscrim]

Description changed:

--- 
+++ 
@@ -5,4 +5,5 @@
 - simplicial abelian groups and Eilenberg-Mac Lane spaces.
 - effective homology and related computations that Kenzo can do but we can't yet.
 - mapping spaces.
+- Discrete Morse theory.

[tscrim]

comment:33

At some point, we should lift up some of the things I did for Hochschild (co)homology to the chain complex and homology method to handle infinite-dimensional complexes (with each dimension a finite complex). Although, off-hand I can't think of a good way to handle the cases when there are an infinite number of cells in a given dimension.

[cnassau]

comment:34

I'm puzzled by the following output: the zeroeth cohomology only comes out right once:

sage: X=simplicial_sets.ClassifyingSpace(GF(3)) ; X
Classifying space of Finite Field of size 3
sage: X.cohomology(0)
Z
sage: X.cohomology((0,))
{0: 0}
sage: X.cohomology(range(4))
{0: 0, 1: 0, 2: 0, 3: 0}

I could imagine that this is a pointed vs. non-pointed issue, but I see the same behaviour for my Catalan set, which has no basepoint.

PS: I now see that the documentation specifies reduced homology, but the answer seems inconsistent nonetheless...

[jhpalmieri]

comment:35

That's a bug in the simplicial set chain complex code. Here is a patched version, which also implements chain_complex and n_chains for arbitrary simplicial sets, not just finite ones.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 8dac891 to 1443151