3
$\begingroup$

Question 1. A PL $n$-sphere is a pure simplicial complex that is a triangulation of the $n$-sphere. I'm looking for a computer algorithm that gives a Yes/No answer to whether a given simplicial complex is a PL sphere. Does anyone know of this?

Question 2. I am also looking for an algorithm that finds a wedge-sum decomposition $K = K_1 \vee K_2$ of a given simplicial complex $K$. I am happy to assume that $K$ is a flag complex, meaning that $K$ is the maximal simplicial complex among other simplicial complexes sharing the 1-skeleton of $K$.

Question 3. Similarly to Question 2, I am interested in other algorithms that attempts to find decompositions like $K = K_1 * K_2$ (join), $K = K_1 \wedge K_2$ (smash product), $K = K_1 \times K_2$ (Cartesian product).

Remark. There are several bottlenecks to investigations such as the above. Recognising whether a given 3-dimensional simplicial complex is collapsible is NP-complete (Tancer 2015). Enumerating PL $n$-spheres with at most $n+4$ vertices takes GPU to work out for $n \le 11$ (Choi-Jang-Vallee 2024). I am attempting this with a beginner's adventurous spirit, so I'm happy to learn more about anything related.

Improve this question
$\endgroup$
10
  • 3
    $\begingroup$ This might be undecidable because it is already undecidable whether a finitely presented group is trivial (and the simplicial complex gives you a finite presentation of its $\pi_1$). I'm just not sure whether one can build homology spheres whose $\pi_1$ is undecidably trivial (that would tell you that your problem is undecidable). $\endgroup$
    – Achim Krause
    Commented Jun 23 at 9:01
  • 2
    $\begingroup$ @AchimKrause: A necessary and sufficient condition for a finitely presentable group to be the fundamental group of a homology sphere is for it to have vanishing $H_1$ and $H_2$. See Kervaire’s paper “Smooth homology spheres and their fundamental groups”. I assume that you can’t solve the triviality problem for groups with vanishing $H_2$, but I don’t know for certain. $\endgroup$
    – Andy Putman
    Commented Jun 23 at 9:26
  • 2
    $\begingroup$ I definitively heard a talk one explaining that it is possible to construct homology spheres with undeciably trivial $\pi_1$. Googling gave me the answer mathoverflow.net/a/98617/3969 $\endgroup$
    – HenrikRüping
    Commented Jun 23 at 10:11
  • 2
    $\begingroup$ @Andy: You only need one missing ingredient: the universal central extension of a perfect group $G$ has $H_2=0$, and can be written down algorithmically from a finite presentation for $G$. (Cf. §3.2 here: arxiv.org/abs/1003.5117 .) Combined with Kervaire's theorem and the Adyan--Rabin theorem, it follows that $n$-spheres are not recognisable for $n\geq 5$. $\endgroup$
    – HJRW
    Commented Jun 23 at 14:52
  • 1
    $\begingroup$ @HJRW: Ah, that’s a nice trick! $\endgroup$
    – Andy Putman
    Commented Jun 23 at 14:56

1 Answer 1

Reset to default
13
$\begingroup$

To answer question 1:

  • There are fast (and easy to implement) algorithms to recognize the zero-, one-, and two-dimensional spheres.
  • Recognising the three-sphere is fast in practice. An algorithm to do this is implemented in the program Regina, written by Burton. The problem is known to lie in NP (Schleimer, Ivanov) and co-NP (Lackenby).
  • The problem of recognizing the four-sphere is open. Also, this problem feels uncomfortably close to the smooth Poincaré conjecture.
  • The problem of recognizing the five-sphere (or any sphere in higher dimensions) is undecidable.

Discussion of the state-of-the-art in dimensions four and higher can be found here.

Improve this answer
$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.