How to triangulate real projective spaces (as simplicial complexes in Mathematica)?

Question

Hello!

I have written a program in Mathematica 7, which calculates for a (finite abstract) simplicial complex all its homology groups. I would really like to test it on the projective spaces, but cannot find a way to triangulate them. There seem to be very few articles on this matter and none of them states directly how the actual triangulations might be achieved, so I turn to MO for help.

How can the real projective spaces $$RP^n \approx B^n/_{x\:\sim-x;\;\; x\in\partial B^n}$$ be triangulated as simplicial complexes? A simplicial complex is presented as a list of simplices that aren't a face of any bigger simplex (the "main simplices"). Each k-simplex is just an ordered list of some k+1 integers.

For example, {0,1,2} is a 2-simplex, as is {1,3,15}, etc. Examples of simplicial complexes: {{0,...,n}} is a n-dimensional ball, {{1,2},{1,3},{2,3}} is an empty triangle, skeleton[{Range[n+2]},n] is a n-sphere, etc.

I have already found a concrete triangulation for the real projective plane, but nothing more general.

It would also be appreciated, that the actual triangulation is reasonably small (not necessarily minimal), so that the program calculates homology groups fast enough. Also, answers in code / pseudocode are much desirable (projectiveSpace[n_]:=???).

P.S. I have already written some functions, which can be used (sc...simplicial complex):

1. skeleton[sc,k] ...list of all k-faces of all simplices
2. sum[sc1,sc2]...topological sum (disjoint union)
3. connected sum[sc1,sc2] ...removes two k-simplicices and adds a tunnel between them
4. product[sc1,sc2]...staircase triangulation of a product (reorders the vertices)
5. cone[sc]
6. suspension[sc]

Answer 1

If you want code, see the patch for Sage at http://trac.sagemath.org/sage_trac/attachment/ticket/9125/trac_9125-projective-space.patch. This patch also includes references for triangulations of $\mathbf{R}P^n$, but I'll summarize the results here, too. For $n=3$, every triangulation must have at least 11 vertices, and the code gives an 11-vertex triangulation as described by Lutz in http://arxiv.org/abs/math/0506372. For $n=4$, every triangulation must have at least 16 vertices, and the code gives such a triangulation, also given by Lutz.

For $n>4$, I think that no minimal examples are known, or at least they weren't a year ago. But to get a triangulation of $\mathbf{R}P^n$, take the $n$-sphere as $\partial \Delta^{n+1}$, the boundary of an $(n+1)$-simplex. Barycentrically subdivide once; the resulting complex $K$ is still a sphere, but with vertices in one-to-one correspondence with the non-empty faces of $\partial \Delta^{n+1}$, which is to say in one-to-one correspondence with the nonempty proper subsets of $T= (0, 1, 2, ..., n+1)$. (I'm not sure why I can't get curly braces to show up here...). This triangulation $K$ of the sphere has a simplicial $\mathbf{Z}/2\mathbf{Z}$-action: on vertices (which correspond to nonempty proper subsets of $T$), send the vertex corresponding to a set $S$ to the vertex corresponding to $T-S$. The quotient space is a triangulation of $\mathbf{R}P^n$, with $2^{n+1}-1$ vertices.

Answer 2

(This should be a comment, but it is too long to be comfortably edited there)

According to a theorem of Arnoux and Marin [Arnoux, Pierre; Marin, Alexis. The Kühnel triangulation of the complex projective plane from the view point of complex crystallography. II. Mem. Fac. Sci. Kyushu Univ. Ser. A 45 (1991), no. 2, 167--244. MR1133113)], a triangulation of $\mathbb RP^d$ has at least $(d+1)(d+2)/2$ vertices. Triangulations were explicitely constructucted by Kühnel [Kühnel, W. Minimal triangulations of Kummer varieties. Abh. Math. Sem. Univ. Hamburg 57 (1987), 7--20. MR0927159, with $2^{d+1}-1$ vertices and $\frac12(d+1)!$ simplices.

Having lower bounds for the number of vertices $n$, makes it useful to know that there exist lower and upper bounds for the $f$-vectors (i.e., for the number of simplices) in terms of $d$ and $n$. Two nice ones are those of Kalai and Gromov for a lower bound (MR0877009)], and of Novik for an upper bound (MR1669325).

Our fellow MOer Gil could probably tell us about the state of the art :)

Answer 3

I've managed to find my mistake and here is the final (if I'm not mistaken) correct solution.

ClearAll[faces, skeleton, subseteq, subset, sBarycentricSubdivision, \
scBarycentricSubdivision, sphere, projectiveSpace]
faces[s_, k_] := Reverse@Subsets[s, {k + 1}]
skeleton[sc_, k_] := Union[Sort /@ Flatten[faces[#, k] & /@ sc, 1]]

subseteq[{},A_List] := True
subseteq[{x_,y___}, A_List] := MemberQ[A, x] && subset[{y}, A]
subseteq[A_List,B_List, C__List] := subset[A,B] && subset[B,C]
subset[A_List, B_List] := subseteq[A, B] && Complement[B, A]!={}
subset[A_List, B_List, C__List] := subset[A, B] && subset[B, C]

sBarycentricSubdivision[{x_Integer}] := {{{x}}}
sBarycentricSubdivision[s_List] := 
 Subsets[s, {1, Length@s}] //Subsets[#,{Length@s}]& //
  Select[#,subset@@#&]& 
scBarycentricSubdivision[sc_List] := 
 Flatten[sBarycentricSubdivision /@ sc, 1]

sphere[n_Integer]  := skeleton[{Range[n+2]},n]

projectiveSpace[n_Integer] := Module[
  {sc1, vertices1, k, identification, sc2, vertices2, sc3},
  sc1 = scBarycentricSubdivision[sphere[n]];
  vertices1 = 
   Sort@DeleteDuplicates@
     Flatten[sc1, 
      1]; (*the vertices (lists) are ordered antipodally with respect \
to complement, ie. vertices1[i]={1,...,n+2}-vertices1[-i]*)
  k = Length@vertices1;
  identification = 
   Table[vertices1[[-i]] -> vertices1[[i]], {i, 1, k/2}];
  sc2 = DeleteDuplicates[Sort /@ (sc1/.identification)];
  vertices2 = Flatten[sc2, 1] //Sort //DeleteDuplicates;
  sc3 = Map[Position[vertices2, #][[1, 1]] &, sc2, {2}] //Sort //
    DeleteDuplicates;
  sc3
  ]

And now, the command projectiveSpace[2] indeed returns a triangulation of the projective plane with 7 vertices and 12 faces. Also, the homology groups of $RP^0$,..., $RP^3$ all seem to be correct.

Thank you, mr. Palmieri, greetings from Slovenia.

Answer 4

OK, I've managed to write the whole thing, but it doesn't work quite right. Here is the code (s...simplex, sc...simplicial complex):

ClearAll[faces, skeleton, subseteq, subset,
barycentricSubdivisionOfSimplex, barycentricSubdivision, sphere,
projectiveSpace]
faces[s_, k_] := Reverse@Subsets[s, {k + 1}]
skeleton[sc_, k_] := Union[Sort /@ Flatten[faces[#, k] & /@ sc, 1]]

subseteq[{}, A_List] := True
subseteq[{x_, y___}, A_List] := MemberQ[A, x] && subset[{y}, A]
subseteq[A_List, B_List, C__List] := subset[A, B] && subset[B, C]
subset[A_List, B_List] := subseteq[A, B] && Complement[B, A] != {}
subset[A_List, B_List, C__List] := subset[A, B] && subset[B, C]

barycentricSubdivisionOfSimplex[{x_Integer}] := {{{x}}}
barycentricSubdivisionOfSimplex[s_List] := 
 Subsets[s, {1, Length@s}] // Subsets[#, {Length@s}] & // 
  Select[#, subset @@ # &] & 
barycentricSubdivision[sc_List] := 
 Flatten[barycentricSubdivisionOfSimplex /@ sc, 1]

sphere[n_Integer]  := skeleton[{Range[n + 2]}, n]

projectiveSpace[n_Integer] := Module[{sc1, sc2, vertices, sc3},
  sc1 = barycentricSubdivision[sphere[n]];
  sc2 = Map[
    Which[Length[#] <= Quotient[n + 2, 2], #, True, 
      Complement[Range[n + 2], #]] &, sc1, {2}];
  vertices = Flatten[sc2, 1] // Sort // DeleteDuplicates;
  sc3 = Sort /@ Map[Position[vertices, #][[1, 1]] &, sc2, {2}] // 
     Sort // DeleteDuplicates;
  Which[n == 0, {{1}}, True, sc3]
  ]

I basically followed the instructions of mr. Palmieri. The problem is, that the homology of my projectiveSpace[n] for n=0,...,4 returns

{{1}, {{}}}
{{1, 1}, {{}, {}}}
{{1, 0, 3}, {{}, {2}, {}}}
{{1, 0, 0, 1}, {{}, {2}, {}, {}}}
{{1, 0, 0, 0, 10}, {{}, {2}, {}, {2}, {}}}

which is obviously incorrect for n=2,4 (the first list represents the betti numbers, the second the torsion coefficients). However, quite a few betti numbers and torsion coefficients seem to be correct, so I'm guessing the error is minor.

Any help would be much appreciated.