%What do you think? Any comments? And where should it go? I was1%thinking perhaps _Discrete_Math_.2%---------------------3%last modified 1999/9/18 -was4\documentclass[11pt]{article}5\usepackage{amssymb}6\newtheorem{lemma}{Lemma}7\newtheorem{theorem}{Theorem}8\newtheorem{corollary}{Corollary}9\newenvironment{proof}{\noindent {\sc Proof:}}{$\Box$ \vspace{2 ex}}10\newcommand{\pow}[1]{{\mathcal P}(#1)}11\newcommand{\F}{\mbox{\bf F}}12\newcommand{\Ftwo}{\mathbf{F}_2}13\newcommand{\defn}[1]{{\em #1}}14\newcommand{\bij}{\varphi}15\title{Classification of parity structures on finite sets}16\author{David Petrie Moulton\\17Department of Mathematics\\18University of Wisconsin\\19Madison, WI 53706\\20\and21William A.\ Stein\\22Department of Mathematics\\23University of California\\24Berkeley, CA 94720}25\date{\today}2627\begin{document}28\maketitle2930\begin{abstract}31Let~$S$ be a finite set, and consider a subset~$T$ of the power set of~$S$.32We say that~$T$ is a \defn{parity structure} for~$S$ if, for33each subset~$b$ of~$S$ of odd cardinality, the number of subsets of~$b$34that lie in~$T$ is even. We classify parity structures using generating35functions from a free boolean ring.36We also show that~$T$ is a parity structure if and only if, for each37subset~$b$ of~$S$ of even size, the number of subsets of~$b$ of odd size38that lie in~$T$ is even.39%Furthermore, we obtain refinements of the40%defining property and this resultant property by41%restricting to subsets of the~$b$'s of particular sizes.42\end{abstract}4344\section{Introduction}45We were led to consider parity structures while searching for46new classes of simplicial complexes. We classified parity47structures; however, the first proof is based on a48technical induction using binomial coefficients.49Later we found a more conceptual proof that uses50generating functions obtained from a free boolean algebra51over the finite field~$\Ftwo$ of order~$2$.52The conceptual proof and classification also yields53additional properties of parity structures.5455\section{Free boolean algebras and generating functions}56Call a finite set \defn{even} or \defn{odd}57according to the parity of its cardinality.58Let~$S$ be a finite set, and let~$T$ be any subset of the59power set~$\pow S$ of~$S$.60We say that~$T$ is a \defn{parity structure} for~$S$ if, for each61odd subset~$b$ of~$S$, the intersection $T \cap \pow b$ is even.62Thus each odd subset~$b$ has an even number of subsets63that lie in~$T$.6465In order to study parity structures for~$S$, we introduce a66ring whose elements correspond naturally to elements of $\pow{\pow S}$.67Let~$R_{S}$ denote the free commutative boolean algebra over~$\Ftwo$68generated by idempotents corresponding to the elements of~$S$;69equivalently,70$$71R_{S} := \frac{\Ftwo[x_{s}\, :\, s \in S]}{(x_{s}^{2}- x_{s}\, : \, s \in S)}.72$$73Because~$\Ftwo$ has characteristic~$2$, every element74of the right hand side is idempotent.75Associate to any subset of~$S$ the monomial that is the product of76the variables corresponding to the elements of the subset.77A sum of monomials represents a collection of subsets78of~$S$. This defines a bijection~$\bij$ from79$\pow{\pow{S}}$ to $R_{S}$ defined by80$$81\bij : T \mapsto \sum_{b \in T} \,\prod_{s \in b} x_{s}.82$$83Under this bijection, each subset of~$S$ maps to a monomial,84and each subset of~$\pow S$ maps to the sum of the images85of its elements, as indicated above.8687We distinguish the element88$\sigma := 1 + \sum_{s \in S} x_{s}$ of~$R_S$;89it corresponds under~$\bij$ to90the collection of subsets of~$S$ of cardinality at most~$1$.91Using~$R_{S}$ we obtain a ring-theoretic characterization of92the parity structures.93\begin{theorem}94Let~$S$ be a finite set, and let~$T$ be a subset of~$\pow{S}$.95Then~$T$ is a parity structure for~$S$ if and only if~$\bij(T)$96is in the ideal generated by~$\sigma$. The97elements~$t \sigma$, with~$t$ a monomial in an even number98of the generators~$x_{s}$, form a basis99for this ideal as a vector space over~$\Ftwo$.100\end{theorem}101\begin{proof}102If $S$ is empty, then all subsets of $\pow S$ are parity structures,103and $\sigma = 1$ generates $R_{S}$ as an ideal, so the theorem holds.104Hence we may assume that $S$ has positive size~$n$.105Let~$P$ be the set of all images under $\bij$ of parity structures106for~$S$.107108We first show that~$P$ is closed under addition.109Let $\bij(T)$ and $\bij(T')$ be elements of~$P$,110where~$T$ and~$T'$ are parity structures.111Because addition in $R_{S}$ is computed modulo~$2$,112the element $\bij(T) + \bij(T')$ is the image113under~$\bij$ of the symmetric difference $T \oplus T^{\prime}$.114Since~$T$ and~$T'$ are parity structures, for any odd subset~$b$115of~$S$, the number of subsets of~$b$ lying in~$T$ is even,116as is the number lying in $T'$, so the number117of subsets of~$b$ lying in $T \oplus T'$ is also even.118Hence $T \oplus T'$ is a parity structure, so119$\bij(T) + \bij(T') = \bij(T \oplus T^{\prime})$ is in~$P$.120121Next we verify that $P$ contains the ideal~$I$ generated by122$\sigma = 1 + \sum_{s\in S} x_s$.123Consider a monomial~$t$ in~$R_{S}$, and124let~$U$ be the subset of $\pow S$ that corresponds125to $\sigma t = t + \sum_{s \in S} x_{s} t$.126Let $c$ be the subset of~$S$ such that $t=\bij(c)$. In the sum127$\sigma t$, if $s\in c$, then~$x_{s} t$ equals~$t$;128otherwise, it equals $\bij(c \cup \{s\})$.129Thus~$U$ consists of each subset of~$S$ obtained by adding130another element to~$c$, together with~$c$ itself exactly131if~$c$ is even.132Consider an odd subset $b\subset S$. If $c\not\subset b$, then133an even number, namely zero, of subsets of~$b$ are elements of~$U$.134If $c\subset b$, then the number of subsets135of~$b$ in~$U$ is $|b| - |c|$ or $|b| - |c| + 1$,136as~$c$ is odd or even, respectively.137Since~$b$ is odd, there are an even number of subsets of~$b$ in~$U$.138It follows that~$U$ is a parity structure,139so $\sigma t = \bij(U)\in P$.140Since~$P$ is closed under addition, and $R_{S}$ is generated141additively by the elements~$t$, it follows that~$I$142is a subset of~$P$.143144The next step is to verify that~$I$ and~$P$145have the same size, hence must be equal.146Take any subset $N$ of $\pow S$147containing only even subsets of $S$; we claim that148there is a unique parity structure for $S$ that we can obtain by adding149odd subsets of $S$ to $N$. We will examine the odd subsets of $S$ in150order of increasing size to see which ones must be added to $N$ to151obtain a parity structure $T$. For each subset $b$ of $S$ of size $1$,152we must include $b$ in $T$ if and only if an odd number of the proper153subsets of $b$ are already in $T$ (which at this point happens exactly154if the empty set is in $N$). Once we have determined which subsets of155size $1$ to include, we consider subsets of $S$ of size $3$. Again, we156can tell exactly which ones we must include, based on which smaller sets157are already in $T$. Continuing in this way, we determine the158unique parity structure $T$ of the required type. Since $S$ has159$n \geq 1$ elements, there are $2^{n-1}$ even subsets of $S$,160and there are $2^{2^{n-1}}$ possibilities for the collection $N$.161As each of these collections can be extended to exactly one162parity structure by adding odd sets,163we see that there are exactly $2^{2^{n-1}}$ parity structures for $S$.164Hence $P$ has size $2^{2^{n-1}}$.165166Let $J$ be the ideal $(1 + \sigma) R_{S}$.167Notice that $\sigma$ and $1 + \sigma$ are orthogonal idempotents168with sum $1$, so $R_{S}$ is the direct sum of $I$ and $J$ as rings.169Also, the linear map from $R_{S}$ to itself sending $x_{s_{0}}$ to170$x_{s_{0}} + 1$ (for some element $s_{0}$ of $S$) and fixing $x_{s}$171for all other values of $s$ is an automorphism of $R_{S}$ (since this172ring can be viewed as the free boolean algebra generated by173$x_{s_{0}} + 1$ and the other indeterminants $x_{s}$).174This automorphism interchanges $\sigma$ and $1 + \sigma$175and, hence, also $I$ and $J$, so $I$ and $J$ have the same dimension176as vector spaces over $\F_{2}$.177Since their sum, $R_{S}$, has dimension $2^{n}$, the ideals $I$178and $J$ have dimension $2^{n-1}$ and size $2^{2^{n-1}}$.179Thus $I$ and $P$ have the same size, and since $I$ is a subset of $P$,180they must be equal.181182Finally, for every even-degree monomial $t$, the product $\sigma t$183is the sum of $t$ and some odd-degree monomials, so these products,184with $t$ ranging over all even-degree monomials, are linearly185independent over $\F_{2}$. But there are $2^{n-1}$ such186products, and by the above calculations, the dimension of $P$ is187$2^{n-1}$, so the products form a basis for $P$ over $\F_{2}$.188This completes the proof of the theorem.189\end{proof}190191\section{A second parity property}192We now prove the alternate defining property of parity structures given193in the introduction.194\begin{theorem}195Let $S$ be a finite set and $T$ be a subset of $\pow S$.196Then $T$ is a parity structure for $S$ if and only if for each197subset $b$ of $S$ of even size, the number of subsets of $b$198of odd size that lie in $T$ is even.199\end{theorem}200\begin{proof}201First we prove that all parity structures satisfy this alternate202property. Notice that if the property holds for two parity203structures, then, as in the proof of the previous theorem, it will hold204for their symmetric difference. And since the image under $\bij$ of the205symmetric difference of two parity structures is the sum of their206images under $\bij$, it suffices to check the property for some207collection of parity structures whose images under $\bij$ form an208$\F_{2}$-basis for $R_{S}$. Thus by the previous theorem, it suffices209to check the property for parity structures of the form210$(\sigma t) \bij^{-1}$, with $t$ an even-degree monomial (in211distinct indeterminants).212213Such a monomial $t$ equals $\bij(c)$ for some even subset $c$ of $S$.214>From the definition of $\bij$, the parity structure215$T = (\sigma t) \bij^{-1}$ consists of $c$ together216with all subsets of $S$ obtained by adding one new element to $c$.217Now take any even subset $b$ of $S$. If $c$ is not a subset of $b$,218then the number of odd subsets of $b$ that lie in $T$ is zero, so we219may assume that $c$ is a subset of $b$. Then the odd subsets of $b$220that lie in $T$ are exactly those subsets of $b$ obtained by adding a221new element to $c$. But there are $|b| - |c|$ such subsets, and since222both $|b|$ and $|c|$ are even, the number of such subsets is even.223224To prove that any collection satisfying the property actually is a225parity structure, we note that a similar construction-and-counting226procedure to that in the previous theorem shows that there are227exactly $2^{2^{|S|-1}}$ subsets of $\pow S$ satisfying the property.228Since this is the same as the number of parity structures, and every229parity structure satisfies the property, the result follows. This230completes the proof of the theorem.231\end{proof}232233\section{Refinements of Results}234We can now show that parity structures have stronger forms of235both the defining property and the one given in the previous section.236These state not merely that some collection of sets is even, but that237when the collection is partitioned in some way according to sizes of238the sets involved, every part of the partition contains an even239number of sets.240\begin{corollary}241For any finite set $S$ and any subset $T$ of $\pow S$, the following242are equivalent:243\begin{enumerate}244\item[a)]245$T$ is a parity structure for $S$.246247\item[b)]248For every odd subset $b$ of $S$, there are an even number of subsets249of $b$ that lie in $T$.250251\item[c)]252For every odd subset $b$ of $S$ and every even natural number $k$, there253are an even number of subsets of $b$ of size $k$ or $k + 1$ that lie254in $T$.255256\item[d)]257For every even subset $b$ of $S$, there are an even number of odd258subsets of $b$ that lie in $T$.259260\item[e)]261For every even subset $b$ of $S$ and every odd natural number $k$,262there are an even number of subsets of $b$ of size $k$ that lie in263$T$.264\end{enumerate}265\end{corollary}266267\begin{proof}268Parts a) and b) are equivalent by definition, and the equivalence of269b) and d) is just the result of the previous theorem.270Parts b) and d) follow immediately from c) and e), respectively,271so it remains only to prove the converses of these last two implications.272As in the proofs of the previous theorems, it suffices to consider the273case when $T$ is of the form $\bij^{-1}(\sigma t) $ for some274even-degree monomial $t$. But then parts c) and e) follow from275b) and d), respectively, for $k$ equal to the degree of $t$ (plus $1$276for part e)), and they hold trivially for all other values of $k$.277\end{proof}278279\section{The Ideal $\sigma R_{S}$}280We would like to close with a few remarks pointing out another way to281think about the ideal mentioned in the proof of the first theorem.282It is straightforward to see that the ring $R_{S}$, with $S$ of size283$n$, is semisimple and is isomorphic to $\Ftwo^{n}$284via the set of (central) orthogonal idempotents285$\{\prod_{s \in S} (x_{s} + \epsilon_{s}) \,286| \, \epsilon_{s} \in \F_{2}\}$.287Since the ideals of $\F_{2}$ are just itself and $(0)$, the elements288of the ideal $\sigma R_{S}$ are just those elements of $R_{S}$289that have support on the coordinates corresponding to the290idempotents lying in $\sigma R_{S}$. An idempotent291$t = \prod (x_{s} + \epsilon_{s})$292will be in the ideal $\sigma R_{S}$ if and only if $t$ equals293$\sigma t = t + \sum_{s \in S} x_{s} t$. This happens exactly if an294even number of the terms in the summation equal $t$ (while the rest295vanish), which happens if and only if an even number of the field296elements $\epsilon_{s}$ equal $0$. To summarise, the elements297of $\sigma R_{S}$ are the $\F_{2}$-linear combinations of those298idempotents $\prod (x_{s} + \epsilon_{s})$299that have an even number of the elements $\epsilon_{s}$ equal to $0$,300which is the same as having the lowest-degree term have even degree.301302\section{Acknowledgment}303This work was done while the first author was a Research Fellow304at the University of California at Berkeley.305\end{document}306307308309