Small simplicial complexes with torsion in their homology?

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.

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.

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