A generalization of parity structures

We now give a generalization of the notion of parity structures, and we discuss some of our results above that can be extended to this situation. In order to motivate our generalization, we note that a subset T of the power set of S is a parity structure if and only if for every subset b of S, the product  $\vert b\vert \, \vert{\mathcal P}(b) \cap T\vert$ is even.

Let m be a positive integer, S be a finite set, and T be a multiset whose elements are subsets of S, each having a multiplicity less than m. We say that T is a mod-m parity multistructure for S if, for each subset b of S, the number m divides  $\vert b\vert \, \vert{\mathcal P}(b) \cap T\vert$, where, in this intersection, each subset of b is counted as many times as it occurs in T. If T actually is a set (that is, has all multiplicities at most 1), then we say that it is a mod-m parity structure.

In order to understand mod-m parity multistructures, we use the ring

$$R_{S,m} := \frac{{\bf Z}/m{\bf Z}[x_{s}\, :\, s \in S]}{(x_{s}^{2}- x_{s}\, : \, s \in S)}.$$

We define a map $\varphi$ from the collection of multisets of subsets of S to R_S,m just as before, by sending a subset a of S to  $\prod_{s \in a} x_{s}$ and extending linearly. In this ring R_S,m we define $\sigma$ to be  $\sum_{\vert a\vert < m} \prod_{s \in a} (-x_{s})$. Notice that both of these definitions agree with our earlier ones in the case where m is 2. As in the proof of Theorem 1, we can show that the images under $\varphi$ of mod-m parity multistructures form the ideal  $\sigma R_{S,m}$. If S has size n, then, as in Corollary 1, there will be a total of  $m^{\sum_{i=0}^{\lfloor n/m \rfloor} {n \choose mi}}$ mod-m parity multistructures. However, as we lack the automorphism of R_S interchanging the ideals corresponding to I and J from the proof of Theorem 1, we do not obtain a formula as simple as the one from that theorem.

We can also generalize Theorem 2 and Corollary 2. Again, the proofs are similar to the ones we have for parity structures, but for the second, there is a bit of calculation with binomial coefficients.

Theorem 3   For every mod-m parity multistructure T for a finite set S and every subset b of S of size divisible by m, the number of subsets of b of size relatively prime to m that lie in T is a multiple of m.

For a collection T of subsets of a finite set S and a sequence of natural numbers  $a_{1}, a_{2}, \ldots, a_{k}$, write  $\vert T\vert _{a_{1}, a_{2}, \ldots, a_{k}}$ for the number of elements of T having size equal to a_i for some value of i.

Theorem 4   Let T be a mod-m parity multistructure for a finite set S.

a)

For any subset b of S and any multiple k of m, the number m divides  $\vert b\vert \, \vert{\mathcal P}(b) \cap T\vert _{k, k+1, \ldots, k+m-1}$.

b)

For any subset b of S of size divisible by m and any natural number k, the number m divides  $(m,k) \, \vert{\mathcal P}(b) \cap T\vert _{k}$, where (m,k) is the greatest common divisor of m and k.

It is harder, on the other hand, to understand mod-m parity structures. We know of two basic families: For any subset c of S of size congruent to 1 modulo m, the collection of subsets of S obtained by adding m-1 new elements to c forms a mod-m parity structure. And for any subset c of S of size congruent to 2 modulo m, the collection of subsets of S obtained by adding either m-2 or m-1 new elements to c forms a mod-m parity structure. Of course, any disjoint unions of collections of the above types will also be mod-m parity structures, but for m greater than 2, these are the only examples we know. It would be nice to know whether there are more, and we pose the following open problem:

Question 1   How many mod-m parity structures are there on a set of size n?