Sharedwww / Tables / parity.dviOpen in CoCalc
����;� TeX output 1999.10.27:0117������m�܍���3$�(�܍��'���D�n�>D��tG�G�cmr17�P��qarit�y�7tstructures�and�generating�functions�from������|Bo�s�olean�7trings��lύ�����\g�0X�Qcmr12�Da��rvid��P�etrie�Moulton�����2��K�cmsy8���������K�(�Departmen��rt��of�Mathematics������WB�Univ��rersit�y��of�Wisconsin������bXMadison,��WI�53706���������^�William��A.�Stein�������4�Departmen��rt��of�Mathematics��������Univ��rersit�y��of�California������
n�Berk��reley��V,��CA�94720������B{�����Octob�S�er��27,�1999��4lύ�����#�"V

cmbx10�Abstract��@��``�K�`y

cmr10�Let����
�b>

cmmi10�S�M~�b�Ge�a�nite�set�and��T���b�e�a�subset�of�the�p�o���w�er���set�of��S����.�=�Call��T����Q`�a���!�':

cmti10�p��}'arity��&structur�e��for��S�'��if,���for�eac���h�subset��b��of��S��of�o�Gdd�size,���the�n���um�b�Ger����Q`of��Rsubsets�of��b��that�lie�in��T�_�is�ev���en.�TW��*�e�classify�parit�y�structures�using����Q`generating���functions�from�a�free�b�Go�olean���ring.�-�W��*�e�also�sho���w�that�if��T��!�is����Q`a��
parit���y�structure,��then,�for��
eac�h�subset��b��of��S�Y��of�ev�en�size,��the�n�um�b�Ger����Q`of���subsets�of��b��of�o�Gdd�size�that�lie�in��T�>�is�ev���en.�w�W��*�e�then�giv�e�sev�eral����Q`other�UUprop�Gerties�of�parit���y�structures�and�discuss�a�generalization.��"�A���6�<��N�ffcmbx12�1��NL�In���tro�s3duction��q���6�'K�`y
�3
cmr10�W��ee��cw��!ere�led�to�consider�parit�y�structures�while�searc�hing�for�a�new�class�of��
����6simplicial���complexes.���W��ee�classied�parit��!y�structures,���but�our�original�pro�M�of����6w��!as��kbased�on�a�tec�hnical�induction�using�binomial�co�M�ecien�ts.�s�Later�w�e����6found��a�more�conceptual�pro�M�of�that�uses�generating�functions�obtained�from����6a���free�b�M�o�olean���algebra�o��!v�er���the�eld���,�"V
�3
cmbx10�F���mL��z�|{Ycmr8�2���2�of�order�2.��\In�Section�2�w��!e�describ�M�e����6ho��!w�9�to�view�parit�y�structures�as�elemen�ts�of�this�b�M�o�olean�9�algebra,�^land�w�e����6use�
bthis�iden��!tication�to�classify�parit�y�structures.�		�W��ee�should�p�M�oin�t�out����6that�GFour�classication�can�b�M�e�form��!ulated�and�pro�v�ed�without�this�b�M�o�olean����6ring�jwith�a�comparable�amoun��!t�of�w�ork,��but�w�e�nd�our�metho�M�d�more����6in��!teresting�m�and�more�instructiv�e.�3�In�Section�3�w�e�use�the�classication�to��6�ff�ff��p�
L͍���Q
��-=�q�%cmsy6�����a�o���		cmr9�This��6w��9ork�w�as�done�while�the�rst�author�w�as�a�Researc�h�F��:�ello�w�at�the�Univ�ersit�y�of���California�Tat�Berk��9eley��:�.������C3�1����*�m�܍���3$�(�܍���3$��6�nd���another�prop�M�ert��!y�of�parit�y�structures.��W��ee�then�pro�v�e�in�Section�4�that��
����6parit��!y�[Vstructures�satisfy�stronger�v�ersions�of�b�M�oth�the�dening�prop�ert��!y�and����6this���new�one.���Finally��e,�ƣin�Sections�5�and�6�w��!e�discuss�some�related�issues����6in��!v�olving��an�ideal��(�b>
�3
cmmi10��d�R������2cmmi8�S��/��w��!e�dene�b�M�elo�w,�l�and�w�e�giv�e�a�generalization�of����6parit��!y��fstructures.��!�U���6�2��NL�F���free�ffb�s3o�olean�algebras�and�generating�functions��q���6�Call�o9a�nite�set��*�':
�3
cmti10�even��or��o��p�dd��according�to�the�parit��!y�of�its�size.�v$Let��S���b�M�e�a�nite����6set,�Y�and�Falet��T�˷�b�M�e�an��!y�subset�of��)!",�
�3
cmsy10�P��|�(�S����),�the�p�M�o��!w�er�Faset�of��S����.���W��ee�sa��!y�that��T�˷�is�a����6�p��p�arity�pEstructur�e�!�for��S�©�if,�;�for�eac��!h�o�M�dd�subset��b��of��S����,�the�in��!tersection��P��|�(�b�)�dO�\��T����6�is���ev��!en;��<that�is,���if�eac�h�o�M�dd�subset��b��has�an�ev�en�n�um�b�M�er�of�subsets�that�lie����6in����T��V�.���A���logician�migh��!t�imagine�that��T�5�consists�of�the�subsets�of��S�QK�that�are����6in�zEsome�mo�M�del,��so�that��P��|�(�b�)���\��T����is�zEthe�p�o��!w�er�zEset�of��b��within�the�mo�del.��'W��ee����6are�V�simply�requiring�then�that,���in�this�mo�M�del,�ev��!ery�o�M�dd�set�ha�v�e�an�ev�en����6n��!um�b�M�er��vof�subsets.��
(This�analogy�is�not�p�erfect,���of�course,�since��b��need�not����6b�M�e�خin��T��V�,��and��\�T�^�is�not�necessarily�closed�under�unions,�but�it�is�an�in��!teresting����6p�M�oin��!t��fof�view�to�tak�e.)����GIn��order�to�study�parit��!y�structures�for��S����,�r�w�e�in�tro�M�duce�a�ring�whose����6elemen��!ts�0�corresp�M�ond�naturally�to�subsets�of��P��|�(�S����).�|YLet��R�����S��
Nq�denote�the�free����6(comm��!utativ�e)�7[b�M�o�olean�algebra�o��!v�er���F���
#ş�z�2��$�generated�b�y�idemp�M�oten�ts�corre-����6sp�M�onding��fto�the�elemen��!ts�of��S����;�that�is,�dene��X���� J�R�����S��	(��:=����������Q:�F���=���z�2�����[�x���z�s��	L�:����s�
��2��S����]��=ڟ�ȉfeR;ʟ
t�(�x����0��2���ύ�s���.���n��x���z�s��	L�:����s�
��2��S����)�����W���:�����6�(Note��5that�this�is�similar�to,��)but�dieren��!t�from,�the�denition�of�a�Stanley-����6Reisner�>Nring,�dHin�whic��!h�w�e�tak�e��x������2���A��s������=��0,�dHrather�than��x������2���A��s����=���x���z�s��n<�.)���Since��R�����S��
\0�is����6spanned�r�b��!y�idemp�M�oten�ts�and�has�c�haracteristic�2,���it�follo�ws�that�all�of�its����6elemen��!ts��fare�idemp�M�oten�ts.���Dene�a�map��'��from��P��|�(�P��(�S����))��fto��R�����S��	�H�b�y��2M���9�T��V'�
��=�������C0���u

cmex10�X���|���b�2�T������Z��C0�Y���|����s�2�b���%.��x���z�s��n<�:��0���6�Under�6�this�map,�Meac��!h�subset�of��S��N�maps�to�the�monomial�that�is�the�pro�M�duct����6of�CWthe�indeterminan��!ts�corresp�M�onding�to�the�elemen�ts�of�the�subset,�W'and�eac�h����6subset���of��P��|�(�S����)�maps�to�the�sum�of�the�images�of�its�elemen��!ts.��oAs��R�����S��
���is����6spanned��fb��!y�its�monomials,��'��is�a�bijection.����GW��ee�adistinguish�the�elemen��!t���Q
�:=��z1��
+����C0�P���$H��8�s�2�S���G�x���z�s��	�V�of�a�R�����S����;�>sit�corresp�M�onds����6under�3�'��to�the�collection�of�subsets�of��S� ��of�size�at�most�1.�hEUsing��R�����S��
��w��!e����6obtain��fa�ring-theoretic�c��!haracterization�of�the�parit�y�structures�for��S����.������C32����
��m�܍���3$�(�܍���3$����6�Theorem�2�1���w>M�L��p�et����S��|�b�e�a�nite�set.���鍍���=YK(a)����Q`A���subset����T�|��of��P��|�(�S����)��is�a�p��p�arity�structur�e�for��S��$�if�and�only�if��T��V'��is�in��
����Q`the���ide��p�al���d�R�����S����.��+T�����=�(b)����Q`The���elements���d�t�,�with��t��a�monomial�in�an�even�numb��p�er�of�the�gener-����Q`ators����x���z�s��n<�,�form�an���F����T��z�2���X�-b��p�asis�for�the�ide�al���d�R�����S����.��Nƍ�6�c�-�
�3
cmcsc10�cPr���oof:����Let��S����ha��!v�e�size��n�,�'�write��R���for��R�����S����,�and�let��P��V�b�M�e�the�set�of�all�images����6under�	�'��of�parit��!y�structures�for��S����.��If��S����is�empt�y��e,�!�then�all�subsets�of��P��|�(�S����)����6are��parit��!y�structures,��*and����>�=���1�generates��R����as�an�ideal,�so�the�theorem����6holds.���Hence��fw��!e�ma�y�assume�that��n��is�p�M�ositiv�e.����GW��ee�?rst�translate�the�set-theoretic�condition�for�the�subset��T��s�of��P��|�(�S����)�to����6b�M�e�ɏa�parit��!y�structure�in�to�an�algebraic�condition�on��T��V'�.�GXF��eor�an�y�elemen�t��t����6�of����R����and�an��!y�subset��b��of��S����,�9write��t�(�b�)�for�the�v��dDalue�of�the�p�M�olynomial��t����6�with�treac��!h�indeterminan�t��x���z�s����set�equal�to�1�if��s��is�in��b��and�set�to�0�otherwise.����6This�{�can�b�M�e�though��!t�of�as�the�ev��dDaluation�of��t��on�the�c�haracteristic�v�ector����6of�f��b�.��F��eor�eac��!h�subset��b��of��S���and�eac�h�elemen�t��c��of��T��V�,��the�term��c'��of��T�'����6�will���v��dDanish�on��b��if��c��is�not�a�subset�of��b��and�will�giv��!e�the�v�alue�1�otherwise.����6Hence��s(�T��V'�)(�b�)�giv��!es�the�parit�y�of�the�n�um�b�M�er�of�subsets�of��b��that�lie�in��T��V�.����6Therefore,�c}�T����is�a�parit��!y�structure�if�and�only�if,�p�for�ev�ery�o�M�dd�subset��b��of��S����,����6the��fv��dDalue�of�(�T��V'�)(�b�)�is�0.����GSince�4Kp�M�olynomial�sp�ecialization�giv��!es�ring�homomorphisms,�Kfor�eac�h�o�M�dd����6subset����b��of��S����,���the�map����Ȯ�b����from��R��~�to���F����@��z�2��j�giv��!en�b�y��t��Ȯ�b�����=�h��t�(�b�)�is�a�homomor-����6phism��of�rings.���And,�Las�the�previous�remarks�sho��!w�that��P�s��is�the�in�tersection����6of��7the�k��!ernels�of�these�maps�for�all�suc�h�subsets��b�,���w�e�see�that��P���is�an�ideal����6of����R���.�s8No��!w�order�the�o�M�dd�subsets�of��S�$l�b�y�increasing�size�(with�an�y�order����6c��!hosen�ԉfor�subsets�of�the�same�size)�as��b���z�1����;��1b���z�2���;��:�:�:��l�;�b��_n�2������;�cmmi6�n���Aa�cmr6�1���O��.���Then�ԉthe�2�����n��1��O����3�2�����n��1�����6�matrix�Fwwith�(�i;��1j��v�)-en��!try�equal�to�(�b���z�i��d��'�)���Ȯ�b��8:�j���T.�is�upp�M�er�triangular�with�1's�on�the����6main���diagonal,���so�the�homomorphisms����Ȯ�b�����are�linearly�indep�M�enden��!t�o�v�er���F���y0��z�2��94�.����6Hence��f�P�+��has�dimension�2�����n��<��n��2�����n��1���s�=�
�2�����n��1��+2�as�an���F�����z�2��R��-v��!ector�space.����GNext��nw��!e�v�erify�that��P�v��con�tains�the�ideal��I��f�generated�b�y���o:�=�
�1��+����C0�P����8��8�s�2�S��7�x���z�s��n<�.����6If���b��is�an��!y�o�M�dd�subset�of��S����,�.�then��b��has��j�b�j�C��+�1��subsets�of�size�0�or�1,�and��j�b�j�C��+�1����6is�u�ev��!en.�K�Hence�the�collection�of�subsets�of��S�:�of�size�at�most�1�is�a�parit�y����6structure,��aand��bas�the�image�of�this�collection�under��'��is���d��,�w��!e�ha�v�e������2�S��P��V�.����6Since��f�P�+��is�an�ideal,�it�con��!tains��I��^�as�a�subset.����GNo��!w���w�e�sho�w�that��I�]��and��P���ha�v�e�the�same�size,��Zhence�m�ust�b�M�e�equal.����6Let��A�J����b�M�e�the�ideal�(1�u~+���d��)�R���.��oNotice��Athat�����and�1�u~+����are��Aorthogonal�idem-����6p�M�oten��!ts�&ywith�sum�1,�F~so��R�<!�is�the�direct�sum�of��I�q�and��J�4�as�rings.�^Also,�the����6linear�:�map�from��R�Pb�to�itself�sending��x���z�s��q�0���ӝ�to�1���+��x���z�s��q�0����(for�:�some�elemen��!t��s���z�0�����of��S����)������C33����]�m�܍���3$�(�܍���3$��6�and�v�xing��x���z�s���	�for�all�other�v��dDalues�of��s��is�an�automorphism�of��R��u�(since��R��can��
����6b�M�e�9view��!ed�as�the�free�b�o�olean�algebra�generated�b��!y�1��-+��x���z�s��q�0������and�9the�other�in-����6determinan��!ts�P^�x���z�s��n<�).��0This�automorphism�in�terc�hanges������and�1���+����and,�a�hence,����6also�k��I�G��and��J�
��,�w�so��I��and��J�y��ha��!v�e�k�the�same�dimension�as�v��!ector�spaces�o�v�er���F���Xc��z�2��g�.����6Since�their�sum��R���has�dimension�2�����n���P�,�"�the�ideals��I����and��J���ha��!v�e�dimension�2�����n��1�����6�o��!v�er��O��F���<g��z�2���k�.��Th�us�O��I�+��and��P��S�ha��!v�e�O�the�same���F���<g��z�2���-dimension,�aEand�since��I�+��is�a�subset����6of��f�P��V�,�they�m��!ust�b�M�e�equal.���This�completes�the�pro�of�of�part�(a).����GFinally��e,��6w��!e�w�pro�v�e�part�(b).��_F��eor�ev�ery�ev�en-degree�monomial��t�,��6the�pro�M�d-����6uct�
���d�t��is�the�sum�of��t��and�some�o�M�dd-degree�monomials,�$so�these�pro�ducts,����6with�k��t��ranging�o��!v�er�k�all�ev��!en-degree�monomials,��%are�linearly�indep�M�enden�t����6o��!v�er���q�F����۟�z�2�����.���But��qthere�are�2�����n��1��m=�suc��!h�pro�M�ducts,���and�b�y�the�ab�M�o�v�e�calculations,����6the��dimension�of��P��C�is�2�����n��1�����,�-8so�the�pro�M�ducts�form�a�basis�for��P��o��!v�er����F���
�W��z�2���[�.��_This����6completes��fthe�pro�M�of�of�the�theorem.����/Tq�
�3
lasy10�2��v��G�This���result�allo��!ws�us�to�coun�t�immediately�the�parit�y�structures�for�a����6nite��fset.�������6�Corollary�2�1���y�n�F��)or����n�
����1�,�a�set�of�size��n��has��2�����2���-:�n��1���:��p��p�arity�structur�es.����6�cPr���oof:�+�Theorem�C
1�sho��!ws�that�the�parit�y�structures�are�in�bijection�with��
����6an���f�F����П�z�2��R��-v��!ector��fspace�of�dimension�2�����n��1�����.����2��+�/���6�3��NL�Another�ffprop�s3ert���y�of�parit�y�structures��q���6�No��!w�m�w�e�in�tro�M�duce�another�prop�ert��!y�of�subsets�of�the�p�o��!w�er�set�of��S����,���this����6time�1�one�in��!v�olving�1�o�M�dd�subsets�of�ev��!en�subsets�of��S����.��W��ee�sa�y�that�a�subset��T����6�of�"�the�p�M�o��!w�er�"�set�of��S��q�is�a��quasi-p��p�arity�H�structur�e�"��for��S��if,���for�ev��!ery�ev�en����6subset�x��b��of��S����,��0the�n��!um�b�M�er�x�of�o�dd�subsets�of��b��that�lie�in��T����is�ev��!en.�T�This����6term��fis�justied�b��!y�our�next�theorem.�������6�Theorem�2�2���w>M�Every�O�p��p�arity�structur�e�for�a�nite�set�is�also�a�quasi-p�arity����6structur��p�e���for�that�set.����6�cPr���oof:����Supp�M�ose�hethat��T���and��T���V����0�����are�b�oth�quasi-parit��!y�structures�for�a�nite����6set�q�S����.��Then�for�an��!y�ev�en�subset��b��of��S����,�{�the�n�um�b�M�er�of�o�dd�subsets�of��b��that����6lie�W�in��T��(�is�ev��!en,��-as�is�the�n�um�b�M�er�that�lie�in��T���V����0��S��.��"Th�us�the�same�holds�for����6their���symmetric�dierence.���And�since�the�image�under��'��of�the�symmetric����6dierence��of��T����and��T���V����0��m�is�the�sum�of�their�images�under��'�,�5�it�suces�to�c��!hec�k����6the��result�for�some�collection�of�parit��!y�structures�whose�images�under��'��form������C34����)�m�܍���3$�(�܍���3$��6�an��O��F���<��z�2����-basis�O�for��R�����S����.�٨Hence�b��!y�the�previous�theorem,�y�it�is�enough�to�sho�w��
����6that�k�parit��!y�structures�of�the�form�(��d�t�)�'������1��\|�,�w�with��t��an�ev�en-degree�monomial����6(in��fdistinct�indeterminan��!ts)�are�quasi-parit�y�structures.����GSuc��!h�osa�monomial��t��equals��c'��for�some�ev�en�subset��c��of��S����.�9>F��erom�the����6denition�h�of��'�,�t�the�parit��!y�structure��T����=�
�(��d�t�)�'������1����consists�of��c��together�with����6all�osubsets�of��S���obtained�b��!y�adding�one�new�elemen�t�to��c�.�7�No�w�tak�e�an�y����6ev��!en�zsubset��b��of��S����.��If��c��is�not�a�subset�of��b�,���then�the�n�um�b�M�er�of�o�dd�subsets����6of�:��b��that�lie�in��T��M�is�zero,�`so�w��!e�ma�y�assume�that��c��is�a�subset�of��b�.���Then����6the���o�M�dd�subsets�of��b��that�lie�in��T�"�are�exactly�those�subsets�of��b��obtained�b��!y����6adding�4sa�new�elemen��!t�to��c�.��But�there�are��j�b�j�͟�j�c�j�4s�suc�h�subsets,�W�and�since����6b�M�oth���j�b�j��and��j�c�j��are�ev��!en,�0�the�n�um�b�M�er�of�suc�h�subsets�is�ev�en.�)OTh�us��T��7�is�a����6quasi-parit��!y��fstructure.���This�completes�the�pro�M�of�of�the�theorem.��2��v��G�It���is�w��!orth�noting�that�the�con�v�erse�of�Theorem�2�is�false.�?HSince�the����6denition�r�of�a�quasi-parit��!y�structure�refers�only�to�those�elemen�ts�of��T����that����6are��Do�M�dd�subsets�of��S����,��;an��!y�collection�of�ev�en�subsets�of��S�;��will�b�M�e�a�quasi-����6parit��!y��Wstructure.�ȯOn�the�other�hand,�ݒthe�collection�consisting�of�just�the����6empt��!y���set�will�not�b�M�e�a�parit�y�structure,��Eunless��S�'O�is�empt�y��e.���More�generally�,����6since��%quasi-parit��!y�structures�are�closed�under�taking�symmetric�dierences,����6the�Ռsymmetric�dierence�of�an��!y�parit�y�structure�and�an�y�collection�of�ev�en����6subsets�.�of��S���will�b�M�e�a�quasi-parit��!y�structure,�P�and�it�can�b�e�sho��!wn�that�all����6quasi-parit��!y�	=structures�are�of�this�form.�	bMoreo�v�er,�a�for��n�Z���2,�there�	=are����6exactly��f2�����3��2���-:�n��2������quasi-parit��!y�structures�for��S����.��"IP���6�4��NL�Renemen���ts�ffof�results��q���6�W��ee��no��!w�sho�w�that�parit�y�structures�satisfy�stronger�v�ersions�b�M�oth�of�the����6dening��condition�and�of�the�condition�in�the�denition�of�a�quasi-parit��!y����6structure.���These�:renemen��!ts�state�not�merely�that�some�collection�of�sets����6is�Kev��!en,�3�but�that�when�the�collection�is�partitioned�in�some�w�a�y�according����6to��bsizes�of�the�sets�in��!v�olv�ed,���ev�ery��bpart�of�the�partition�con��!tains�an�ev�en����6n��!um�b�M�er��fof�sets.��;�����6�Corollary�2�2���y�n�L��p�et����S��|�b�e�any�nite�set�and��T�[email protected]�b�e�any�p�arity�structur�e�for��S����.��vA�����A�|a)����Q`F��)or��zevery�o��p�dd�subset��b��of��S�<�and�every�even�natur�al�numb�er��k�X?�,��^ther�e����Q`ar��p�e���an�even�numb�er�of�subsets�of��b��of�size��k�C)�or��k��+�+�n�1��that�lie�in��T��V�.��%�����Bb�b)����Q`F��)or��zevery�even�subset��b��of��S�<�and�every�o��p�dd�natur�al�numb�er��k�X?�,��^ther�e����Q`ar��p�e���an�even�numb�er�of�subsets�of��b��of�size��k�C)�that�lie�in��T��V�.������C3�5����73�m�܍���3$�(�܍���3$��6�cPr���oof:�k��As��Din�the�pro�M�of�of�Theorem�2,���it�suces�to�consider�the�case�when��T��
����6�is�� of�the�form��'������1��\|�(��d�t�)�for�some�ev��!en-degree�monomial��t�.��But�then�parts�a)����6and�8cb)�follo��!w�from�Theorems�1�and�2,�Ndresp�M�ectiv�ely��e,�for�8c�k����equal�to�the�degree����6of�7��t��or�this�degree�plus�1,�M�and�they�hold�trivially�for�all�other�v��dDalues�of��k�X?�.���2��v��G�Of�pLcourse,���giv��!en�the�fact�that�ev�ery�quasi-parit�y�structure�is�the�sym-����6metric�wQdierence�of�a�parit��!y�structure�and�a�collection�of�ev�en�sets,���it�easily����6follo��!ws�2Gthat�quasi-parit�y�structures�also�satisfy�the�condition�in�part�b)�of����6Corollary��f2.��" ����6�5��NL�The�ffideal��:��g�ffcmmi12���DR��(��S�����and�the�ring��9X�Qffcmr12�2����=�
!",�

cmsy10�P��}�(�S����)���q���6�W��ee�k:should�lik��!e�to�mak�e�a�few�remarks�p�M�oin�ting�out�another�w�a�y�to�think����6ab�M�out���the�ideal�men��!tioned�in�the�pro�of�of�Theorem�1.�<PIt�is�straigh��!tforw�ard����6to���see�that�the�ring��R� O�=�
��R�����S����,��Jwith��S�^�of�size��n�,�is�semisimple�and�is�isomorphic����6to��{J�F�����]��g��n��
���g��2����N�via�{Jthe�set�of�primitiv��!e�(cen�tral)�orthogonal�idemp�M�oten�ts��f���C0�Q���	qɟ�8�s�2�S��(��(�x���z�s�����+����6����z�s��n<�)��1�j�����z�s��x��2��
��F���
���z�2����g�.�~�Since���the�ideals�of���F���
v
��z�2�����are�just�itself�and�(0),�–the�elemen��!ts�of�the����6ideal��w��d�R���are�just�those�elemen��!ts�of��R��that�ha��!v�e��wsupp�M�ort�on�the�co�ordinates����6corresp�M�onding���to�the�idemp�oten��!ts�lying�in���d�R���.���An�idemp�oten��!t��t�
��=����C0�Q��|p�(�x���z�s���I�+�^
����z�s��n<�)����6will��Rb�M�e�in�the�ideal���d�R����if�and�only�if��t��equals���t�
��=��t����+����C0�P���+��8�s�2�S����x���z�s��n<�t�.��,This��Rhapp�M�ens����6exactly��if�an�ev��!en�n�um�b�M�er�of�the�terms�in�the�summation�equal��t��(while����6the�-�rest�v��dDanish),�O�whic��!h�happ�M�ens�if�and�only�if�an�ev�en�n�um�b�M�er�of�the�eld����6elemen��!ts�rq����z�s����equal�0.�A�T��eo�summarize,��sthe�elemen�ts�of���d�R���are�the���F���^۟�z�2����-linear����6com��!binations�|�of�those�idemp�M�oten�ts����C0�Q���j�(�x���z�s�����+�c����z�s��n<�)�that�ha�v�e�an�ev�en�n�um�b�M�er�of����6the�delemen��!ts�����z�s���Y�equal�to�0,���whic�h�is�the�same�as�ha�ving�the�lo�w�est-degree����6term��fb�M�e�of�ev��!en�degree.����GW��ee�Y�no��!w�p�M�oin�t�out�a�relationship�b�M�et�w�een�the�ring��R�����S��	w��used�in�our�pro�M�ofs����6ab�M�o��!v�e�r�and�a�similar�b�o�olean�ring�Halmos�discusses�in�his�b�o�olean�algebra����6b�M�o�ok�%�[�1��y�].�[�F��eor�a�set��U�1��,�E�he�considers�the�ring�2�����U��?��of�functions�from��U�WO�to���F�����z�2�����6�with�cco�M�ordinatewise�addition�and�m��!ultiplication.��2Notice�that�the�sum�of�the����6c��!haracteristic��^functions�of�t�w�o�subsets�of��U����is�the�c�haracteristic�function�of����6their�symmetric�dierence,��while�the�pro�M�duct�is�the�c��!haracteristic�function����6of��their�in��!tersection.���This�construction�can,�[of�course,�b�M�e�applied�with�the����6p�M�o��!w�er��set�of��S��~�in�place�of��U�2��to�obtain�the�ring�2�����P��+�(�S�r}�)��V��.��nW��ee�can�iden��!tify�the����6elemen��!ts���of�eac�h�of�the�rings��R�����S��	�r�and�2�����P��+�(�S�r}�)��b�with�collections�of�subsets�of��S����,����6and�6\in�eac��!h�ring,�L�addition�corresp�M�onds�to�taking�the�symmetric�dierence�of����6t��!w�o�R�collections.��Multiplication,�c�ho�w�ev�er,�has�R�dieren�t�in�terpretations�in�the����6t��!w�o���rings.���In��R�����S����,��it�corresp�M�onds�to�taking�all�unions�of�a�subset�from�the�rst����6collection��and�a�subset�from�the�second�collection�(coun��!ted�with�appropriate������C36����D~�m�܍���3$�(�܍���3$��6�m��!ultiplicities�&nmo�M�dulo�2),�@while�in�2�����P��+�(�S�r}�)��V��,�it�corresp�M�onds�to�taking�the�subsets��
����6that�
ko�M�ccur�in�b�oth�collections.��Both�rings,�',ho��!w�ev�er,�are�
kfree�b�M�o�olean�
krings����6of��fthe�same�dimension�o��!v�er���f�F����П�z�2��R��,��fand�so�are�isomorphic.����GAs��indicated�ab�M�o��!v�e,�0�the��primitiv�e�orthogonal�idemp�M�oten�ts�of�the�ring��R�����S�����6�are��R(with�our�usual�notation)�all�pro�M�ducts�of�the�form����C0�Q����mۍ�5�n��U]��5i�=1���vq�(�x���z�i��
��+�������z�i��d��)�with�eac��!h����6term�������z�i����an�elemen��!t�of���F���q��z�2��1�.�ҟA���bit�of�calculation�no�w�sho�ws�that�sending�suc�h����6an��idemp�M�oten��!t�to�the�function��x���z�i��o��7!�
�����z�i��W��and�extending�linearly�giv�es�a�natural����6isomorphism�}from��R�����S��
/_�to�2�����P��+�(�S�r}�)��V��.�"Finally��e,�,Cthe�elemen��!t���v�is�the�sum�of�those����6idemp�M�oten��!ts�Gpwith�an�ev�en�n�um�b�M�er�of�the�terms�����z�i���J�equal�to�0,�Znso�corresp�onds����6in���2�����P��+�(�S�r}�)����to�the�sum�of�the�c��!haracteristic�functions�of�the�co-ev�en�subsets����6of��f�S�G��(those�with�ev��!en�complemen�t�in��S����).��"�A���6�6��NL�A�ffgeneralization�of�parit���y�structures��q���6�W��ee�(�no��!w�giv�e�a�generalization�of�the�notion�of�parit�y�structures,��-and�w�e����6discuss�some�of�our�results�ab�M�o��!v�e�that�can�b�e�extended�to�this�situation.�мIn����6order��Rto�motiv��dDate�our�generalization,��
w��!e�note�that�a�subset��T�R��of�the�p�M�o�w�er����6set�wof��S��	�is�a�parit��!y�structure�if�and�only�if�for�ev�ery�subset��b��of��S����,�|zthe����6pro�M�duct��f�j�b�j��1jP��|�(�b�)�n��\��T��V�j��is�ev��!en.����GLet�Y��m��b�M�e�a�p�ositiv��!e�in�teger,��S��t�b�M�e�a�nite�set,�i0and��T��8�b�e�a�m��!ultiset�whose����6elemen��!ts�"}are�subsets�of��S����,�A�eac�h�ha�ving�a�m�ultiplicit�y�less�than��m�.�R!W��ee�sa�y����6that��}�T�%��is�a��mo��p�d-�m��z�p�arity�multistructur�e��}�for��S�B�if,���for�eac��!h�subset��b��of��S����,�the����6n��!um�b�M�er�lZ�m��divides��j�b�j��1jP��|�(�b�)����\��T��V�j�,�w�where,�in�lZthis�in��!tersection,�w�eac�h�lZsubset�of��b����6�is�scoun��!ted�as�man�y�times�as�it�o�M�ccurs�in��T��V�.��7If��T����actually�is�a�set�(that�is,�%�has����6all�7�m��!ultiplicities�at�most�1),�M�then�w�e�sa�y�that�it�is�a��mo��p�d-�m����p�arity�structur�e�.����GIn��forder�to�understand�mo�M�d-�m��parit��!y�m�ultistructures,�w�e�use�the�ring���ٍ���F�R�����S���;m�����:=���������=��Z�=m�Z�[�x���z�s��	L�:����s�
��2��S����]��=ڟ�ȉfeU�~�
t����(�x����0��2���ύ�s���.���n��x���z�s��	L�:����s�
��2��S����)�����[T��:���Q��6�W��ee��^dene�a�map��'��from�the�collection�of�m��!ultisets�of�subsets�of��S�c��to��R�����S���;m�����6�just�Was�b�M�efore,�f�b��!y�sending�a�subset��a��of��S����to����C0�Q������8�s�2�a��8��x���z�s���[�and�extending�linearly��e.����6In��this�ring��R�����S���;m��*;�w��!e�dene�����to�b�M�e����C0�P���[email protected]��8�j�a�j�<m���'�d��C0�Q���1U-��8�s�2�a��?���(��x���z�s��n<�).��Notice�that�b�oth�of����6these�[�denitions�agree�with�our�earlier�ones�in�the�case�where��m��is�2.���As����6in���the�pro�M�of�of�Theorem�1,��w��!e�can�sho�w�that�the�images�under��'��of�mo�M�d-�m����6�parit��!y��xm�ultistructures�form�the�ideal���d�R�����S���;m���6�.��If��S�N
�has�size��n�,���then,�as�in�����6Corollary��?1,���there�will�b�M�e�a�total�of��m����R>�P����� ��
�;�b�n=m�c��%��
�;�i�=0������"_����(�����j��(�:�n�����&�mi����/ލ���)�����85�mo�d-�m��parit��!y�m�ultistruc-����6tures.��MHo��!w�ev�er,��as���w�e�lac�k�the�automorphism�of��R�����S��	��in�terc�hanging�the�ideals������C37����TB�m�܍���3$�(�܍���3$��6�corresp�M�onding��ito��I��a�and��J���from�the�pro�of�of�Theorem�1,��jw��!e�do�not�obtain�a��
����6form��!ula��fas�simple�as�the�one�from�that�theorem.����GW��ee�f�can�also�generalize�Theorem�2�and�Corollary�2.��Again,�� the�pro�M�ofs����6are���similar�to�the�ones�w��!e�ha�v�e�for�parit�y�structures,��Ibut�for�the�second,����6there��fis�a�bit�of�calculation�with�binomial�co�M�ecien��!ts.��Pԍ���6�Theorem�2�3���w>M�F��)or�M�every�mo��p�d-�m��p�arity�multistructur�e��T��3�for�a�nite�set��S��o�and����6every���subset��b��of��S��{�of�size�divisible�by��m�,��the�numb��p�er�of�subsets�of��b��of�size����6r��p�elatively���prime�to��m��that�lie�in��T�[email protected]�is�a�multiple�of��m�.����G�F��eor��/a�collection��T�^��of�subsets�of�a�nite�set��S�z��and�a�sequence�of�natural����6n��!um�b�M�ers�m��a���z�1����;��1a���z�2���;��:�:�:��l�;�a��Ȯ�k��#��,��write�m��j�T��V�j���z�a��q�1��*��;a��q�2���;�:::��\;a��i?�k���-�;�for�the�n��!um�b�M�er�m�of�elemen��!ts�of��T����6�ha��!ving��fsize�equal�to��a���z�i��@�for�some�v��dDalue�of��i�.������6�Theorem�2�4���w>M�L��p�et����T�[email protected]�b�e�a�mo�d-�m��p�arity�multistructur�e�for�a�nite�set��S����.��\������A�|a)����Q`F��)or��any�subset��b��of��S��a�and�any�multiple��k�x�of��m�,�mthe�numb��p�er��m��di-����Q`vides����j�b�j��1jP��|�(�b�)�n��\��T��V�j��Ȯ�k�6�;k��+1�;�:::��\;k��+�m��1��@o��.���X�����Bb�b)����Q`F��)or��any�subset��b��of��S�!��of�size�divisible�by��m��and�any�natur��p�al�numb�er��k�X?�,����Q`the�W numb��p�er��m��divides��(�m;��1k�X?�)��jP��|�(�b�)��V�\��T��V�j��Ȯ�k��#��,�r-wher�e�W �(�m;��1k�X?�)��is�the�gr�e�atest����Q`c��p�ommon���divisor�of��m��and��k�X?�.����G�It�o�is�harder,�z�on�the�other�hand,�to�understand�mo�M�d-�m��parit��!y�structures.����6W��ee���kno��!w�of�t�w�o�basic�families:�֩F��eor�an�y�subset��c��of��S�9��of�size�congruen�t�to�1����6mo�M�dulo����m�,�Dthe�collection�of�subsets�of��S�uw�obtained�b��!y�adding��m�7����1���new����6elemen��!ts�=�to��c��forms�a�mo�M�d-�m��parit�y�structure.���And�for�an�y�subset��c��of��S����6�of�˩size�congruen��!t�to�2�mo�M�dulo��m�,��the�collection�of�subsets�of��S�m;�obtained����6b��!y���adding�either��m��o���2���or��m��o���1���new�elemen�ts�to��c��forms�a�mo�M�d-�m��parit�y����6structure.���Of�Wcourse,��8an��!y�disjoin�t�unions�of�collections�of�the�ab�M�o�v�e�t�yp�M�es����6will�0also�b�M�e�mo�d-�m��parit��!y�structures,�%nbut�for��m��greater�than�2,�these�are�the����6only��&examples�w��!e�kno�w.�+It�w�ould�b�M�e�nice�to�kno�w�whether�there�are�more,����6and��fw��!e�p�M�ose�the�follo�wing�op�M�en�problem:������6�Question�2�1���v�v�How��<many�mo��p�d-�m��p�arity�structur�es�ar�e�ther�e�on�a�set�of�size��n�?��"tэ�6�References��q�����6�[1]���G�P��!aul��fHalmos,��+p�0J
�3
cmsl10�Lectures�on�Bo�M�olean�Algebras�,�Springer-V��eerlag,�1970.������C38����c����;�m���	�c�-�
�3
cmcsc10�>D��tG�G�cmr17�<��N�ffcmbx12�:��g�ffcmmi12�9X�Qffcmr12�0X�Qcmr12�/Tq�
�3
lasy10�,�"V
�3
cmbx10�+p�0J
�3
cmsl10�*�':
�3
cmti10�)!",�
�3
cmsy10�(�b>
�3
cmmi10�'K�`y
�3
cmr10�#�"V

cmbx10�!�':

cmti10�o���		cmr9��K�cmsy8��2cmmi8�|{Ycmr8�q�%cmsy6�;�cmmi6��Aa�cmr6�
!",�

cmsy10�
�b>

cmmi10�K�`y

cmr10���u

cmex10�op�������