Amending flawed "proof" that homology groups are zero

Question

I am trying to prove a certain statement that seems true based on computational data, and there is a nice argument that proves it, assuming all cycles are the simplest ones (e.g., when the only 1-cycles are triangles and never squares, pentagons, etc.). In real life these are not the only cycles, so this is not a real proof. I'll state the proposition and the "proof" to begin with.

First some definitions. A set $S$ of integers is said to be coprime-free if for all $i,j\in S$ with $i\ne j$, $\gcd(i,j)>1$. A coprime-free subset $S\subseteq [n]$ is said to be maximal if $S\cup \{x\}$ is not coprime free for all $x\in [n]\setminus S$. Let $\Delta_n$ be the simplicial complex whose vertices are the maximal coprime-free subsets of $n$, with a face for every set of vertices with nonempty intersection. In the following, when we speak of homology of $\Delta_n$ and write $H_k(\Delta_n)$, we mean homology over ${\bf Z}$.

Proposition. For all $k\ge 1$, $H_k(\Delta_n)=0$.

"Proof". Let $k\ge 1$ be given and suppose that $x_1,x_2,\ldots,x_{k+2}$ are vertices in $\Delta_n$ such that $\{x_1,\ldots,x_{k+2}\}$ is not a face but for all $1\le i \le k+2$, the set $F_i = \{x_1,\ldots,x_{k+2}\}\setminus\{x_i\}$ does form a face. In other words, $\bigcap_{i=1}^{k+2} x_i = \emptyset$, but for all $i$, the set $\bigcap F_i$ does contain some element, call it $a_i$. Now consider the set $A=\{a_1,\ldots,a_m\}$. If for some pair $i\ne j$ we have $\gcd(a_i,a_j) = 1$ for some $i$ and $j$, then we use the fact that $k+2\ge 3$ to pick $t\in [k+2]\setminus\{i,j\}$ and note that $a_i$ and $a_j$ are both in $x_t$, which would imply that $x_t$ is not coprime-free. So we conclude that $a_i$ and $a_j$ are not coprime for all $i\ne j$. Thus $\{a_1,\ldots,a_{k+2}\}$ is a subset of some maximal coprime-free subset of $[n]$, call it $x$. The above reasoning shows that $\{x,x_1,\ldots,x_{k+2}\}$, viewed as a simplicial subcomplex of $\Delta_n$, is a $(k+2)$-simplex missing its interior as well as exactly one of its $(k+1)$-faces, namely $\{x_1,\ldots,x_{k+2}\}$. The $k$th homology of this simplicial subcomplex is zero, so the $(k+2)$-tuple $(x_1,\ldots,x_{k+2})$ contributes nothing to the $k$th homology of $\Delta_n$. Since $x_1,\ldots,x_{k+2}$ were arbitrary, we are done."▮"

In the general case where a $k$-cycle may be formed by more than $k+2$ vertices (in the way that a square is still a $1$-cycle, being a formal sum of two triangles), I am wondering if there is some way of taking this result that we have and stacking it upon itself in some way. Or if there is some other way of amending the proof above. The reason that I would like to amend the proof above rather than start from scratch is that, under some delusion many months ago, I wrote some other "proofs" just like the one above, forgetting about the general case of $k$-cycles, and it is a naive hope of mine that there is some general schema for taking all of my false homology proofs and promoting them to real ones.

Sorry if the second part of my question is a bit wobbly and ill-defined, but really any help on this would be much appreciated. Thanks in advance!

Edit. I think I was able to prove it using the nerve complex that Andy Putman suggested below. Here is what I have. The part about retracting simplices down I feel is correct, but perhaps I have not expressed it rigorously enough. Any feedback on this proof would be much appreciated.

Applying Borsuk's nerve theorem to Andy Putman construction and observations,$\Delta_n$ is homotopy equivalent to the simplicial complex $X_n$ whose vertex set is $[n]$ and in which a subset $J\subseteq [n]$ is a face if and only if $J$ is coprime-free. We also know that $X_n$ has $C(n)+2$ connected components, $C(n)+1$ of which are singletons. The nontrivial connected component, call it $X_n'$, consists of all primes in the range $[2,n/2]$ as well as all composite numbers in $[n]$. The claim is that $X_n'$ is contractible.

We will construct the deformation retraction to a single point in steps. First note that the set $V_2$ all even vertices, viewed as a subcomplex of $X_n'$, is a simplex, so we may retract this down to a point without altering the homotopy of $X_n'$. Call this point $\bar 2$. Now in this new complex, consider the set $V_3$ of all vertices whose smallest prime divisor is $3$ ($V_3$ includes all remaining multiples of $3$, since all multiples of $6$ were retracted to the point $\bar 2$). The subcomplex on $V_3\cup \{\bar 2\}$ is a simplex, since in the original complex $X_n'$, the set of vertices divisible by $3$ was a simplex, and all we have done is retract some subsimplex consisting of vertices divisible by $6$ to a point, call it $\bar 3$. The same will be possible when we define the set $V_5$ of all integers whose smallest prime divisor is $5$, and then consider $V_5\cup \{\bar 3\}$. Continuing this reasoning, we may perform a retraction for every prime $p\in [2,p/2]$ until all we are left with is a single point.

Answer 1

Let $G_n$ be the graph with vertex set $\{2,\ldots,n\}$ in which there is an edge $ij$ if and only if $\mathrm{gcd}(i,j)>1$. The simplicial complex mentioned in Andy Putman's answer, as well as in your other StackExchange question is flag, and it is the clique complex $\mathrm{Cl}(G_n)$ of this graph (modulo the isolated one-point components of primes $p>n/2$). Ie. the simplices of the complex are the cliques (complete subgraphs) of the graph.

The homotopy type of $\mathrm{Cl}(G_n)$ can be analyzed using some standard techniques for flag complexes. Let $N_G[v]$ denote the closed neighborhood of $v$ in $G$, that is the set of vertices adjacent to $v$ plus also $v$ itself. If $N_G[v]\subseteq N_G[u]$ for two different vertices $u,v$ then $\mathrm{Cl}(G)$ collapses to $\mathrm{Cl}(G\setminus v)$, in particular they are homotopy equivalent. This is because the link of $v$ in $\mathrm{Cl}(G)$ is a cone with apex $u$, hence contractible. In Barmak and Minian's papers this would be called a strong collapse and the vertex $v$ would be called dominated by $u$. We can use that terminology.

Our graph $G_n$ is very susceptible to strong collapsing because it has a lot of dominating vertex pairs. If the set of primes dividing $i$ is a subset of the set of primes dividing $j$ then $i$ is dominated by $j$ (every number not-coprime to $i$ is not-coprime to $j$), so $i$ can be removed without affecting the homotopy type of the clique complex by the above discussion. We can easily implement the iterative procedure of finding if there is a dominated vertex and removing it in a few lines in any programming language. I will not include it because it is not very illuminating and also it is better is you write your own to have an independent check.

Using this we find a collapsing sequence of the main component of $\mathrm{Cl}(G_n)$ to a point for $n\leq 142$. For $n=143=11\cdot 13$ we collapse to something nontrivial: the graph induced by $$\{2\cdot 3\cdot 7,\ 2\cdot 3\cdot 11,\ 2\cdot 3\cdot 13,\ 7\cdot 11,\ 7\cdot 13,\ 11\cdot 13\}$$ (Actually we may end up with other numbers, like $2^2\cdot 3\cdot 11$, but only the prime number matter and not their exponents, so we can just as well stick to this). This graph is the complement of the matching on three coprime pairs of numbers, so its clique complex is the 2-dimensional cross-polytope on 6 vertices, or the surface of the octahedron. (This is the smallest that a nontrivial generator of $H_2$ in a flag complex can be).

So, up to a bunch of isolated points, $\mathrm{Cl}(G_{143})$ is homotopy equivalent (collapses, strongly collapses) to $S^2$, so $n=143$ is the first counterexample to your claim.

Side remark: here is a little funny "sanity check". One could ask why not replace this example with a example using smaller primes, namely the cross-polytope induced by $$\{2\cdot 3\cdot 5,\ 2\cdot 3\cdot 7,\ 2\cdot 3\cdot 11,\ 5\cdot 7,\ 5\cdot 11,\ 7\cdot 11\}$$ which would give us a class already in $H_2(\mathrm{Cl}(G_{77}))$. The reason is that $2\cdot 5\cdot 7=70$ is adjacent to all those 6 numbers and therefore cones this sphere off in $\mathrm{Cl}(G_{77})$, trivializing it in homology. On the other hand in $G_{143}$ the analogous attempt with $2\cdot 7\cdot 11=154$ does not work because $154>143$!

Answer 2

This is too long for a comment, but isn't an answer. It gives a complex that is homotopy equivalent to $\Delta_n$ and appears to me to be easier to think about.

Define $[n]' = \{2,\ldots,n\}$. Since a coprime-free set cannot contain $1$, each vertex $S$ of $\Delta_n$ is contained in $[n]'$. For $k \in [n]'$, let $X_k$ be the full subcomplex of $\Delta_n$ on the vertices $S$ with $k \in S$. The $X_k$ cover $\Delta_n$.

What I claim is that $\Delta_n$ is homotopy equivalent to the nerve of the cover $\{X_k\}_{k \in [n]'}$. For this, it is enough to prove that every intersection of finitely many $X_k$ is either empty or contractible. Consider $I \subset [n]'$, and let $X_I$ be the intersection of the $X_k$ as $k$ ranges over $I$. Thus $X_k$ is the full subcomplex on the vertices $S$ of $\Delta_n$ with $I \subset S$. If this is nonempty, then all the vertices $S$ of $X_I$ intersect, so by the definition of $\Delta_n$ the complex $X_I$ is actually the simplex on its vertices (and in particular is contractible).

Now, if $I$ is not coprime-free then clearly $X_I$ is empty. However, if $I$ is coprime-free then $I$ must be contained in a maximal coprime-free set, so $X_I$ is nonempty and hence contractible.

It follows that the nerve of the $X_I$ is the simplicial complex whose vertices are elements of $[n]' = \{2,\ldots,n\}$ and where a set $I$ of vertices forms a simplex precisely when $I$ is coprime-free. To my mind, this complex seems easier to think about than $\Delta_n$.

Answer 3

Edit: this is answering the wrong question (coprime subsets rather than coprime-free subsets), but in case it's useful, I will leave it here.

I believe that this simplicial complex should be a simplex, therefore contractible. I should probably have known about Bertrand's postulate before this, but it says that for any $k$, there is a prime number $p$ with $k < p < 2k$. If $n$ is even, let $n=2k$ and find such a $p$. If $n$ is odd, say $n=2k-1$, then find $p$ with $k<p<2k$, and so we have $n/2 < k < p \leq n$.

Once you have such a prime, it is contained in every maximal coprime subset, and so the intersection of all of those sets will be nonempty: every vertex in the simplicial complex is contained in a single simplex.

Answer 4

Following Andy Putman's suggestion that we use the nerve complex, I believe I have found an inductive proof that $H_1(X_n) = 0$ for all $n$. Please point out errors if you see any!

Let $X_n$ denote the nerve complex as described in Andy Putman's answer, though for simplicity's sake we make the vertex set $[n]$. (So $\{1\}$ is always an isolated vertex of $X_n$.) All homologies below are reduced, but I'll write $H_k$ instead of $\tilde H_k$ to be lazy.

A note on notation. $X_n$ here is not the same as $X_k$ from Andy Putman's answer. Apologies for my unfortunate choice of letter. Here $X_n$ is the simplicial complex with $[n]$ as its vertex set, and a face for every set of vertices that is coprime-free.

We'll need this following fact later on, so I'll state it here, but I'll omit its proof. (It's not too difficult.)

Proposition. We have $$H_0(X_1) = 0,\qquad H_0(X_2) = {\bf Z},\qquad\hbox{and}\ H_0(X_3)={\bf Z}^2.$$ For $n\ge 4$, the vertex $1$ is isolated in $X_n$, and there is also an isolated vertex in $X_n$ for each prime in the range $(n/2,n]$. The rest of the vertices are in one connected component. In other words, $H_0(X_n) = {\bf Z}^{C(n)+1}$, where $C(n)$ is the number of primes in the range $(n/2,n]$. ▮

We'll also use the Mayer--Vietoris sequence, which for reduced homology states that

$$\eqalign{ \cdots \to H_s(A)\oplus H_s(B) \to H_s(X)\to H_{s-1}(A\cap B) \to H_{s-1}(A)\oplus H_{s-1}(B)\to\cr \cdots\to H_0(A\cap B) \to H_0(A)\oplus H_0(B) \to H_0(X) \to 0,\cr }$$

whenever $A$ and $B$ are subsimplicial complexes whose interiors cover $X$, and $A\cap B$ is nonempty.

Proof that $H_1(X_n)=0$ for $n\ge 1$. We begin the induction on $n$. For $n=1$ it is clear that $H_k(X_1)$ is $0$ for all $k$.

Now let $n>1$. If $n$ is prime, then $X_n$ is simply the union of $X_{n-1}$ and a new isolated vertex, so $H_0(X_n) = H_0(X_{n-1}) \oplus {\bf Z}$, but all other homologies remain unchanged, so by the induction hypothesis, $H_k(X_n) = 0$ for all $k>1$.

If $n$ is not prime, we let $A$ be the cone of the vertex $n$ in $X_n$, and let $B = X_{n-1}$, considered as a subset of $X_n$. The relevant section of the Mayer Vietoris sequence is

$$\cdots \to H_1(A)\oplus H_1(B) \to H_1(X_n) \to H_0(A\cap B) \to H_0(A)\oplus H_0(B) \to H_0(X_n) \to 0$$

Note that $A$, being the cone of a vertex, is contractible. Applying the proposition above, we have $H_0(X_n) = C(n)+1$ and $H_0(B) = C(n-1)+1$. By the induction hypothesis, $H_1(B) = 0$. Lastly, note that $A\cap B$ is a subset of the big connected component, unless $n/2$ is prime, in which case it also contains the isolated vertex $n/2$, which is isolated in $B$. Hence $$ \hbox{rank}(H_0(A\cap B)) = {\bf 1}_{[n/2\text{ is prime}]}.$$

Putting all these facts into the exact sequence above, we have

$$\cdots \to 0 \to H_1(X_n) \to {\bf Z}^{{\bf 1}_{[n/2\text{ is prime}]}} \to 0 \oplus {\bf Z}^{C(n-1)+1}\to {\bf Z}^{C(n)+1} \to 0$$

But since $n$ is composite, we have $$C(n) = \cases{C(n-1)-1, & if $n/2$ is prime;\cr C(n-1), & otherwise.}$$ Thus we conclude that $H_1(X_n) = 0$. ▮

I feel like this Mayer--Vietoris idea is very close to showing that $H_k(X_n) = 0$ for $k>1$ as well. Since $H_k(A) \oplus H_k(B) = 0$ for all $k>1$, we have $$H_k(X_n) = H_{k-1}(A \cap B)$$ for $k>1$, but it is not immediate to me that the homologies of the intersection are all trivial.