35
$\begingroup$

Fix a prime $p$. What is the smallest integer $n$ so that there is a simplicial complex on $n$ vertices with $p$-torsion in its homology?

For example, when $p=2$, there is a complex with 6 vertices (the minimal triangulation of the real projective plane) with 2-torsion in its homology. I'm pretty sure that it's the smallest possible: with 5 or fewer vertices, there should be no torsion at all. When $p=3$, there is a complex with 9 vertices (a triangulation of the mod 3 Moore space, for instance) with 3-torsion. Is there one with 8 vertices? With $p=5$, there is a complex with 11 vertices, found by randomly testing such complexes on my computer.

We can refine this: fix $p$ and also a positive integer $d$. What's the smallest $n$ so that there is a simplicial complex $K$ on $n$ vertices with $p$-torsion in $H_d(K)$? Or we can turn it around: for fixed $n$, what kinds of torsion can there be in a simplicial complex on $n$ vertices?

(A paper by Soulé ("Perfect forms and the Vandiver conjecture") quotes a result by Gabber which leads to a bound on the size of the torsion for a fixed number $n$ of vertices; however, this bound is far from optimal, at least for small $n$.)

$\endgroup$
1
  • $\begingroup$ Unless my third comment to damiano's answer has a flaw, you should be able to find a simplicial complex on 8 vertices with 3-torsion. $\endgroup$
    – j.p.
    Mar 11, 2010 at 13:36

5 Answers 5

16
$\begingroup$

UPDATE This version is substantially improved from the one posted at 8 AM.

I now think I can achieve $\mathbb{Z}/p$ using $O( \log p)$ vertices. I'm not trying to optimize constants at this time.

Let $B$ be a simplicial complex on the vertices $a$, $b$, $c$, $a'$, $b'$, $c'$ and $z_1$, $z_2$, ..., $z_{k-3}$, containing the edges $(a,b)$, $(b,c)$, $(c,a)$, $(a',b')$, $(b',c')$ and $(c',a')$ and such that $H^1(B) \cong \mathbb{Z}$ with generator $(a,b)+(b,c)+(c,a)$ and relation

$$2 {\large (} (a,b)+(b,c)+(c,a) {\large )} \equiv (a',b') + (b',c') + (c',a').$$

I think I can do this with $k=6$ by taking damiano's construction with $p=2$ and adding three simplices to make the hexagon $(h_1, h_2, \ldots, h_6)$ homologous to the triangle $(h_1, h_3, h_5)$.

Let $B^n$ be a simplicial complex with $3+nk$ vertices $a^i$, $b^i$, $c^i$, with $0 \leq i \leq n$, and $z^i_j$ with $0 \leq i \leq n-1$ and $1 \leq j \leq k-3$. Namely, we build $n$ copies of $B$, the $r$-th copy on the vertices $a^r$, $b^r$, $c^r$, $a^{r+1}$, $b^{r+1}$, $c^{r+1}$ and $z^r_1$, $z^r_2$, ..., $z^r_{k-3}$. Let $\gamma_i$ be the cycle $(a^i,b^i) + (b^i, c^i) + (c^i, a^i)$.

Then $H^1(B^n) = \mathbb{Z}$ with generator $\gamma_0$ and relations $$\gamma_n \equiv 2 \gamma_{n-1} \equiv \cdots \equiv 2^n \gamma_0$$

Let $p = 2^{n_1} + 2^{n_2} + \cdots + 2^{n_s}$.

Glue in an oriented surface $\Sigma$ with boundary $\gamma_{n_1} \sqcup \gamma_{n_2} \sqcup \cdots \sqcup \gamma_{n_s}$, genus $0$, and no internal vertices.

In the resulting space, $\sum \gamma_{n_i} \equiv 0$ so $p \gamma_0 \equiv 0$, and no smaller multiple of $\gamma_0$ is zero. We have use $3 + k \log_2 p$ vertices. This is the same order of magnitude as Gabber's bound.

$\endgroup$
4
  • $\begingroup$ I have not checked the details, but I also thought that it might be possible to improve the earlier results by using the more economical presentation of the cyclic group of order $n$ obtained by using roughly $\log n$ generators, each being the double of the next (not the last one, of course!). Btw, I cannot remember if this is the case or not, but this presentation might be known to be the one for which the sum of the lengths of all the relations is asymptotically smallest. On the other hand, at the moment, I have no idea of how to find lower bounds for the initial question... $\endgroup$
    – damiano
    Mar 11, 2010 at 14:08
  • $\begingroup$ Nice construction! You can take k=3 using my 3rd comment to damiano's answer, almost. You just have to pay attention that you can still glue in $\Sigma$ at without problems (i.e., trying to add double simplices) at the end. Instead of $\frac{3}{\ln 2}\cdot \ln p$ one can also achieve $\frac{k+1}{\ln k}\cdot \ln p$ when taking two $k$-gons glued together where one step is the first is identified by taking $k-1$ steps in the other. (same caution as for taking $k=3$). $\endgroup$
    – j.p.
    Mar 11, 2010 at 14:52
  • $\begingroup$ (should read "two $(k+1)$-gons" and "taking $k$ steps" in my last comment) $\endgroup$
    – j.p.
    Mar 11, 2010 at 14:54
  • $\begingroup$ This does look nice. I'm happy to see an answer with the same order of magnitude as Gabber's bound. $\endgroup$ Mar 11, 2010 at 20:58
15
$\begingroup$

Andrew Newman just posted a preprint to the arXiv, showing that for every prime $p$ and $d \ge 2$, you can get $p$-torsion in homology $H_{d-1}(K)$ with only $O(\log^{1/d} p)$ vertices. (The implied constant depends on $d$, but not on $p$.) This is best possible, up to a constant factor.

His construction starts with something similar to what Speyer describes above, which gets you a complex with $O( \log p)$ vertices. Then he applies the probabilistic method, taking a certain carefully chosen random quotient of the complex, gluing together vertices in a random way. This doesn't affect torsion in homology. The problem is that it might not result in a simplicial complex. But Newman uses the Lovász local lemma to show that with positive probability, it does. Hence there exists a vertex identification that works.

$\endgroup$
2
  • $\begingroup$ That's interesting. I suppose the next step in this parametrized complexity ladder would be to ask how big your complex needs to be to get $p^k$-torsion in $H_n$. $\endgroup$ Apr 1, 2022 at 17:55
  • $\begingroup$ Newman answers this question as well. His paper actually shows that every finite abelian group $G$ is the torsion subgroup of homology $H_{d-1}(K)$ for a simplicial complex $K$ on $n$ vertices, where $n = O \left(log^{1/d} |G| \right)$. $\endgroup$ Apr 2, 2022 at 17:58
8
$\begingroup$

Gil Kalai has a beautiful paper from 1983 where he shows that, on average, $\mathbb{Q}$-acyclic $d$-dimensional simplicial complexes $S$ with complete $(d-1)$-skeleton on $n$ vertices have $$| H_{d-1}(S, \mathbb{Z}) | \ge \exp (c n^d) $$ for some constant $c > 0$ depending only on $d$ and not on $n$.

These results are for the total size of the torsion group, and not for $p$-torsion specifically. But for $d=2$ this at least gives that torsion group can grow exponentially in $n^2$, rather than in $n$.

Now the more speculative part. My best guess for the structure of $H_{d-1}(S, \mathbb{Z})$, for a suitable measure on random $\mathbb{Q}$-acyclic complexes $S$, would be Cohen-Lenstra heuristics --- the idea that the probability that a random finite abelian group is isomorphic to $G$ is proportional to the size of the automorphism group of $G$.

If something like this holds, then with probability bounded away from zero, $H_{d-1}(S, \mathbb{Z}) $ is cyclic. If anything like this is the case, we should expect that there exist $2$-dimensional simplicial complexes on $n$ vertices with $p$-torsion, where $p$ is of order $\exp (cn^2)$.

Linial, Meshulam, and Rosenthal recently provided new examples of $\mathbb{Q}$-acyclic complexes, by defining complexes symmetrically on vertex set $\mathbb{Z} / p$ and then analyzing the Fourier transform of homology.

I did a little experimenting with their examples in SAGE and found a $2$-dimensional simplicial complex $S$ on $31$ vertices with $$| H_1(S, \mathbb{Z}) | = 736712186612810774591.$$

This is a product of distinct primes, so it is necessarily a cyclic group. (The largest prime factor is $408437$.)

$\endgroup$
5
$\begingroup$

I can build the lens space $L(p,q)$ with $16p+8$ vertices; this has $H_1$ (and $\pi_1$) equal to $\mathbb{Z}/p$.

We'll start by building some triangulations of $S^3$. Take two $2p$-gons, with vertices $(x_1, x_2, \ldots, x_{2p})$ and $(y_1, y_2, \ldots, y_{2p})$. Let $J$ be their join. This is a three dimensional triangulated manifold whose maximal faces are $(x_i, x_{i+1}, y_j, y_{j+1})$ for $1 \leq i,j \leq 2p$ (all indices are cyclic modulo $2p$.) Topologically, $J$ is the sphere $S^3$. Let $B$ be the first barycentric subdivision of $J$. $B$ has $$4p + \left( 4p + 4 p^2 \right) + 8 p^2 + 4 p^2 = 8p + 16 p^2$$ vertices.

Let $\mathbb{Z}/p$ act on $J$ by translating $2$ steps around the first $2p$-gon and $2q$ steps around the other. This induces an action on $B$, and the quotient $L$ is, by definition, $L(p,q)$. There are $(8p+16p^2)/p$ vertices in $L$.

I leave it to the reader to check that $L$ is a simplicial complex. (You need to check that there is no edge joining a vertex to itself, and that any set of vertices is contained in at most one face. This isn't true if you use $p$-gons instead of $2p$-gons, so be careful!)

$\endgroup$
2
  • $\begingroup$ I had a second construction here, which was supposed to realize p+6. I deleted it because it has a pair of vertices with multiple edges between them. $\endgroup$ Mar 11, 2010 at 5:22
  • $\begingroup$ I think you can triangulate the mod n Moore space with $2n+3$ vertices. $\endgroup$ Mar 11, 2010 at 21:04
5
$\begingroup$

You might be able to do slightly better than with David's construction, but still with a number of vertices linear in $p$. Namely, you present the group $\mathbb{Z}/p\mathbb{Z}$ by a single generator $a$ and a single relation $a^p$. Now you triangulate the CW complex obtained by glueing a disk to a circle by a $p:1$ map along the boundary (this is the standard trick to produce a CW complex having as fundamental group any group given in terms of a presentation). Let me be more explicit; in the construction I will give, I need $3p+4$ vertices, though it might be possible to reduce this number by a more clever subdivision (using triangles, instead of squares, for instance). Let $a_0,a_1,a_2$ be the vertices of a triangle and let $b_0,\ldots,b_{3p-1}$ be the vertices of a $3p$-gon. Add (triangulations of) the squares $a_i , a_{i+1} , b_{3k+i} , b_{3k+i+1}$ for $0 \leq k \leq p-1$ and $0 \leq i \leq 2$, where, obviously, indices are taken modulo the respective numbers. This achieves the identification of the boundary $b_0,\ldots,b_{3p-1}$ of the two-cell with the fixed circle $a_0,a_1,a_2$. Now we need to cone off the boundary of the two-cell: simply add a new vertex $v$ and all the triangles $v,b_i,b_{i+1}$ where $0 \leq i \leq 3p-1$. Thus we have a simplicial complex with $3+3p+1$ vertices whose fundamental group is $\mathbb{Z}/\mathbb{Z}p$.

Finally, one more comment on the second part of your question. Denote by $m(p,d)$ the minimum number of vertices $n$ needed to construct a simplicial complex with $n$ vertices and non-trivial $p$-torsion in degree $d$ homology. There is an obvious inequality: $m(p,d) \leq m(p,d-1)+2$. This follows at once from the fact that you can suspend a simplicial complex by adding two vertices; the effect of suspending is that you shift the (reduced) homology groups up one step.

$\endgroup$
5
  • $\begingroup$ You can reduce the number of vertices by 1 if you simply add the simplex $\{a_1, a_2, a_3\}$ to your construction instead of "coning it off". Maybe you should also make clear that you start taking only the boundary of the triangle and the $3p$-gon. $\endgroup$
    – j.p.
    Mar 11, 2010 at 12:19
  • $\begingroup$ Rather, don't add $(a_1, a_2, a_3)$ but, instead, triangulate the $3p$-gon without adding a new internal vertex. $\endgroup$ Mar 11, 2010 at 12:36
  • $\begingroup$ @David: You are right, I set the wrong path to zero. $\endgroup$
    – j.p.
    Mar 11, 2010 at 12:44
  • $\begingroup$ Another idea to leave out (almost) every 2nd vertex of the $3p$-gon: use just the simplices $\{b_i, b_{i+1}, a_{2i+1\pmod 3}\}$, $\{b_i, a_{2i-1\pmod 3}, a_{2i\pmod 3}\}$ and $\{b_i, a_{2i\pmod 3}, a_{2i+1\pmod 3}\}$ to glue the triangle to the "$(3p+1)/2$"-gon. This way we "make two steps" on the triangle for "each step" on the now "$(3p+1)/2$"-gon. (Needs of course a correct treatment of $i=0$ rsp. $i=(3p+1)/2$). $\endgroup$
    – j.p.
    Mar 11, 2010 at 13:05
  • $\begingroup$ @jp: This might be correct, but I do not see the point in editing it in, given the better argument below! d $\endgroup$
    – damiano
    Mar 11, 2010 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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