Jonah Saks and I have uploaded our paper “Alternating-sum statistics for certain sets of integers” to the arXiv. We show that if ${\cal F}$ is a set family in our class, then a certain alternating-sum statistic is constant. This constant equals $-1$ in the case where ${\cal F}$ is the set of all finite primitive sets. Towards the end of the paper, we generalise the notion of primitive sets to $s$-multiple sets and show that if $s\ge 2$, then the alternating-sum statistic we study is not constant, but as $n$ increases it equals $(-1)^s {n-2\choose s-1}$.

### Arithmetic constraints on finite sets

As a starting point, consider the following definitions. A set $S$ of integers is said to be

*primitive*if for any two distinct $i,j\in S$, $i$ does not divide $j$;*pairwise coprime*if any two distinct $i,j\in S$ have $\gcd(i,j) = 1$; and*product-free*if for any $i,j\in S$ not necessarily distinct, $ij\notin S$.

We consider only finite sets in this post, and as a first observation, we note that taking $S$ to be any subset of the primes, we satisfy all three conditions. Let’s talk about primitive sets first. We will count the number of primitive subsets of \([n] = \{1,2,\ldots,n\}\) that have size exactly $k$, for $0\le k\le n$. Letting $P_{n,k}$ be the number of such sets, here is a table for small $n$:

For example, \(P_{6,3} = 3\) because there are three primitive subsets of \(\{1,\ldots,6\}\) that have size exactly $3$, namely, \(\{2,3,5\}\), \(\{3,4,5\}\), and \(\{4,5,6\}\). Taking the alternating sum of this whole row corresponding to $n=6$, we have a value of $1-6+7-3 = -1$, and if you stare at the table, you’ll notice that the alternating sum of each row (except the first one) equals $-1$. Now look at the table for $Q_{n,k}$, the number of pairwise coprime subsets of $[n]$ of cardinality $k$:

This time, the alternating sums equal $0$. Lastly, letting $R_{n,k}$ be the number of product-free subsets of $[n]$ of size $k$, we see that the alternating sums are $0$ in this case as well:

The sequences $P_{n,k}$, $Q_{n,k}$, and $R_{n,k}$ are in the OEIS as A355145, A355146, and A355147, respectively. Miscellaneous facts about these quantities were collected in the following proposition of our paper (this post follows the paper’s numbering).

**Proposition 3.** *For $n\ge 2$ we have*

*$P_{n,1} = Q_{n,1} = n$ and $R_{n,1} = n-1$;**$P_{n,2} = \sum_{i=2} (i-d(i))$, where $d(i)$ counts the number of divisors of $i$;**$Q_{n,2} = \sum_{i=2}^n \varphi(i)$, where $\varphi$ is Euler’s totient function;**$R_{n,2} = {n\choose 2} - n -\lceil \sqrt n\rceil + 2$; and**for any $p$ prime and $k\ge 3$, $F(p,k) = F(p-1,k) + F(p-1, k-1)$, where $F$ can be any of $P$, $Q$, or $R$.*

### Partition-intersecting families

To unify the three examples above, we now introduce the class of set families mentioned in the top of
the post. Let ${\cal F}$ be a family of finite sets of positive integers. Let $F_{n,k}$ be the
number of elements of cardinality $k$ in \({\cal F}_n = {\cal F}\cap 2^{[n]}\). We would like to study
the alternating sum $\sum_{k=0}^n (-1)^k F_{n,k}$. We will say that an element $S$ of \({\cal F}_n\) is *maximal*
if for all $x\in [n]\setminus S$, \(S\cup \{x\}\notin {\cal F}_n\).

Now for the actual definition. We say that a set family \({\cal F}\) is *\(m\)-partition-intersecting* if
for all $n\ge 2$, the following three conditions are satisfied (condition 2 does not depend on $n$ but conditions
1 and 3 do):

- $[n]\notin {\cal F}_n$.
- {\cal F} is
*downward closed*; that is, for every $S\in {\cal F}$, every subset $T$ of $S$ is also in ${\cal F}$. - The set \(M_n\subseteq {\cal F}_n\) of maximal elements can be partitioned into $m$ disjoint nonempty classes $M_n = C_1 \sqcup \cdots\sqcup C_m$ such that for all $i$, the intersection $\bigcap_{S\in C_i} S$ is nonempty, and for all $i\ne j$ and any $S\in C_i$ and $T\in C_j$, $S\cap T = \emptyset$.

We are now able to state the main theorem.

**Theorem 1.** *Let \({\cal F}\) be $m$-partition-intersecting and let $n\ge 2$. For $0\le k < n$,
let \(F_{n,k}\) be the number of \(S\in {\cal F}_n = {\cal F}\cap 2^{[n]}\) with $|S|=k$. Then*

The proof of this theorem uses some basic results from enumerative combinatorics, relating the Möbius function of a poset to the homology of a certain simplicial complex.

From here, we just need to show that primitive sets, pairwise coprime sets, and product-free sets are all families that fit in our class:

**Corollary 4.** _For $n\ge 2$,

- $\sum_{k=0}^n (-1)^k P_{n,k} = -1$;
- $\sum_{k=0}^n (-1)^k Q_{n,k} = 0$; and
- $\sum_{k=0}^n (-1)^k R_{n,k} = 0$.

### A generalisation of primitive sets

A primitive set is a set that does not contain more than one multiple of any integer. We make this definition more general by forbidding sets with more than $s$ multiples of any given integer, and when $s=1$ we recover the definition of a primitive set. For $s\ge 2$, the family of $s$-multiple sets is not $m$-partition-intersecting for any $m$, but we still have the following theorem.

**Theorem 5.** *Let $s\ge 2$ be an integer, let $n>s$, and let \(P_{s,n,k}\) denote the number of
$s$-multiple subsets of $[n]$ with cardinality exactly $k$. We have*

The proof of this also goes through the homology groups of a certain simplicial complex, but this time the calculations involved are more technical.