Characterising bimodal collections of sets in finite groups
Sophie Huczynska Maura B. Paterson

A Quantum Monte Carlo algorithm for out-of-equilibrium Green's functions at long times
    Xavier Waintal
    December 30, 2023
======================================================================================


A collection of disjoint subsets A={A_1,A_2,…,A_m} of a finite abelian group is said to have the bimodal property if, for any non-zero group element δ, either δ never occurs as a difference between an element of A_i and an element of some other set A_j, or else for every element a_i in A_i there is an element a_j∈ A_j for some j≠ i such that a_i-a_j=δ.  This property arises in various familiar situations, such as the cosets of a fixed subgroup or in a group partition, and has applications to the construction of optimal algebraic manipulation detection (AMD) codes.  In this paper,  we obtain a structural characterisation for bimodal collections of sets.




§ INTRODUCTION

Let G be a finite abelian group of order n, written additively, with identity 0. Let A={A_1,A_2,…,A_m} be a collection of disjoint subsets of G.  Then A is said to have the bimodal property if, for any non-identity element δ of G, either δ never occurs as a difference between an element of A_i and an element of some other set A_j, or else for every element a_i in A_i there is an element a_j∈ A_j for some j≠ i such that a_i-a_j=δ.

Let k_i=|A_i| for i=1,2,…,m.  For each δ∈ G∖{0}, we let

    N_i(δ)=|{(a_i,a_j): δ=a_i-a_j, a_i∈ A_i, a_j∈ A_j, i≠ j}|.
  
Then A has the bimodal property if N_i(δ)∈{0,k_i} for i=1,2,…,m.  

Although this is a very natural property which occurs in many familiar settings, it seems that the property has not received attention until now.  It has applications to cryptography, having been defined by Huczynska and Paterson <cit.> in the context of studying reciprocally-weighted external difference families (RWEDFs), which were shown to exhibit this property in certain parameter situations.   RWEDFs correspond to optimal Algebraic Manipulation Detection (AMD) codes <cit.>, and better understanding of this property can lead to new constructions for such codes.

Perhaps the most natural occurrence of this property is as follows:

Let H be a subgroup of an abelian group G.  If C={C_1, …, C_m } is a collection of cosets of H, then C has the bimodal property.  


For fixed i and 1 ≤ j ≤ m with i ≠ j, the sets C_i-C_j comprise m-1 distinct cosets of H.  For any δ∈ C_i-C_j and every x ∈ C_i there exists a unique y ∈ C_j such that x-y= δ.  For any δ∈ G ∖∪_j ≠ i (C_i-C_j), the element δ occurs zero times as a difference out of C_i.



Let G=ℤ_10, H={0,5} and let C_1={1,6}, C_2={3,8} and C_3={4,9}.  We observe that N_3(1)=N_3(3)=N_3(6)=N_3(8)=2=k_3, whereas N_3(2)=N_3(4)=N_3(5)=N_3(7)=N_3(9)=0.  A similar check of the values of N_1(δ) and N_2(δ) for δ∈ℤ_10∖{0} shows that A={A_1,A_2,A_3} has the bimodal property.


This is such a natural setting in which the bimodal property occurs, that one might initially suspect that cosets of a fixed subgroup are the only nontrivial collections of sets with this property. However, we shall show that this is not in fact the case, and that a much richer structure arises.

In Section <ref> of this paper we make some fundamental observations about properties of bimodal collections of sets, and give examples and techniques for creating new from old.  In Section <ref> we classify bimodal collections of sets by considering certain subgroups associated to them, and we demonstrate that every such collection can be constructed in a suitable group.  





§ TOOLS AND CONSTRUCTIONS

The bimodal property is defined in terms of differences between elements lying in distinct members of a collection A={A_1,A_2,…,A_m} of disjoint subsets of a group G (external differences).  

The following notation will be used throughout the paper.  Let A=⋃_i=1^m A_i, and for j with 1≤ j ≤ m let B_j=A∖ A_j.  So for each 1 ≤ j ≤ m, A= A_j ⊔ B_j (where the notation S⊔ T denotes the union of disjoint sets S and T).  Then 

    N_j(δ)=|{(a,b):δ=a-b, a∈ A_j, b∈ B_j}|.
  
We will also find it useful to consider differences between elements within the same subset (internal differences).  

Let A_i be a subset of a finite abelian group G.  We define the internal difference group H_i of A_i to be the subgroup of G generated by all elements of the form x-y with x,y∈ A_i.


In Section <ref> we saw a bimodal collection of sets where each set was a coset of a subgroup H of G.  In this case we have H_i=H for each set A_i in the collection.  

The group H_i has the property that A_i is contained in a single coset of H_i, and is the smallest subgroup of G with this property.  In the case where |A_i|=1, the group H_i={0} and its cosets are the singleton sets. 


We may view singleton sets as cosets of the identity subgroup; throughout what follows we will take this approach.  

For any element a ∈ A_i we have that a+H_i is the coset of H_i containing A_i.  Throughout what follows we will select an arbitrary element a_i∈ A_i for i=1,2,…,m and represent the coset of H_i containing A_i by a_i+H_i.


The following useful characterisation of bimodal collections of sets was established in <cit.>.

Let G be a finite abelian group and let A={A_1,A_2,…,A_m} be a collection of disjoint subsets of G.  Then A has the bimodal property if and only if for each i the set B_i is a union of cosets of the subgroup H_i.


Theorem <ref> tells us that if an element v is contained in B_j for some j with 1≤ j≤ m then B_j contains the entire coset v+H_j, i.e. we have that v+h_j∈ B_j for all h_j∈ H_j.





  (i)  A family of disjoint subsets of an abelian group G in which all subsets have size 1 is bimodal by Theorem <ref>.  

  (ii) A family consisting of a single subset of an abelian group G is trivially bimodal.



We now exhibit a non-trivial example of a bimodal collection of sets that appeared in <cit.>, which may at first seem surprising.  It is very different in structure to our coset example, but also represents a classic and much-studied group theory situation. For a group G we will let G^* denote the set of nonzero elements of G.


Let G be a finite group.  If G has subgroups S_1,S_2,…, S_m with the property that S_1^*,S_2^*,… , S_m^* partition G^*, then the collection of subgroups S_1,S_2,…, S_m is called a group partition of G.  A group partition is called trivial if m=1. 


Let the collection of subgroups { S_1, …, S_m} be a group partition of an abelian group G where |S_i|>2 for each i.  Then the collection of sets C={S_1^*, …, S_m^*} has the bimodal property. 


For each i, the internal difference group of S_i^* is S_i.  It follows directly that the union ⋃_j ≠ i S_j^* is G ∖ S_i, a union of cosets of S_i.

 Let G=ℤ_3 ×ℤ_3.  Let A_1={(1,1), (2,2)}, A_2={(0,1), (0,2)}, A_3={(1,2), (2,1)} and A_4={(1,0), (2,0)}.  Observe that for each A_i, the subgroup H_i is precisely A_i ∪{0}.  Then the collection A ={ A_1, A_2, A_3, A_4 } is bimodal. 


The topic of group partitions has been studied extensively; see Zappa <cit.> for a comprehensive survey.  In the abelian case, the groups which possess non-trivial group partitions are completely characterised as the elementary abelian p-groups.  These can be viewed as partitions of vector spaces over ℤ_p, and have been widely studied in this context; for example, see Heden <cit.>.



In fact the construction of Lemma <ref> may be extended to give examples in more general groups:


Let A be a collection A={A_1, …, A_m} of disjoint subsets of an abelian group G that partition G^* and have the property that any A_i with |A_i|>1 is of the form S^* for some subgroup S≤ G.  Then A is bimodal.


Let G=ℤ_12.  Then G has a subgroup {0,4,8} of order 3 and a subgroup {0,3,6,9} of order 4.  The sets {4,8}, {3,6,9}, {1}, {2}, {5}, {7}, {10}, {11} form a bimodal collection.


Having seen some examples of constructions of bimodal collections of sets, we now introduce some approaches to constructing new collections from old, which we exploit in Section <ref>.  First we observe that a bimodal collection can undergo a shift without its bimodality being affected.


Let A={A_1,A_2,…,A_m} be a bimodal collection of disjoint subsets of an abelian group G. Then the collection A^' given by { A_1+g, A_2+g, …, A_m+g} where g ∈ G is also bimodal.


The bimodal property is defined entirely in terms of differences between elements in different sets of the collection.  The value of a difference a_i-a_j does not change if g is added to both a_i and a_j, and hence the result follows immediately.


We may also replace a coset by a partition of that coset into smaller cosets, a process we will refer to as subdivision:




Let A={A_1,A_2,…,A_m} be a bimodal collection of disjoint subsets of an abelian group G.  Suppose that A_i is a coset of H_i for some i.  Let A_i^1,A_i^2, …, A_i^r be disjoint subsets partitioning A_i, having internal difference groups H_i^1,H_i^2, …, H_i^r respectively, and which possess the property that for j=1,2,…, r the set A_i^j is a coset of H_i^j.  Then the collection A^'={A_1,A_2,…,A_i-1,A_i^1,A_i^2,…,A_i^r ,A_i+1,…,A_m} satisfies the bimodal property.  We shall refer to A^' as a subdivision of A.


The union of elements in the collection is not changed by subdivision, so for sets A_j with j≠ i it is still the case that B_j is a union of cosets of H_j.  Consider a set A_i^t; we will denote A ∖ A_i^t by B_i^t.   We note that H_i^t≤ H_i, and so any coset of H_i is a union of cosets of H_i^t.  Now, B_i^t=(A_i∖ A_i^t) ∪ B_i.  We have that B_i is a union of cosets of H_i^t since it is a union of cosets of H_i, and A_i∖ A_i^t is a union of cosets of H_i^t as A_i is a union of cosets of H_i and A_i^t is itself a coset of H_i^t.  Thus we deduce that the collection is bimodal as required.

We observe that subdivision can be applied repeatedly if desired, and the resulting collection will still be bimodal.


Let G be the elementary abelian group of order 8.  Write it as G=ℤ_2 ×ℤ_2 ×ℤ_2, +).  Then by Example <ref>, A={ G} is trivially bimodal.  We can apply subdivision to obtain A^', as follows. 
Define the following subgroups of G:

    S_1={ (0,0,0), (0,0,1)};


    S_2= { (0,0,0), (1,0,0)};


    S_3={ (0,0,0), (0,1,1)};


    S_4={ (0,0,0), (1,1,0) }.

Then G may be partitioned as:

    A_1=S_1={ (0,0,0), (0,0,1)};


    A_2=(0,1,0)+S_2={ (0,1,0), (1,1,0)};


    A_3=(1,0,0)+S_3={ (1,0,0), (1,1,1)};


    A_4=(0,1,1)+S_4={ (0,1,1), (1,0,1)}.
  
Take A^'={ A_1, A_2, A_3, A_4}.  This is bimodal by Theorem <ref>.  To see this directly, observe that the differences out of A_1 comprise every element 2 times except the elements of S_1 which occur zero times; and in general the differences out of A_i  comprise every element twice except the elements of S_i which occur 0 times.  This means that, for δ∈ G^*, if δ is one of the four non-zero elements of ∪_1 ≤ i ≤ 4S_i then N_i(δ)=0 for precisely one value of i ∈{1,2,3,4}, whereas if δ is one of the three elements of G^* not in ∪_1 ≤ i ≤ 4S_i, then N_i(δ)>0 for all i.






§ CLASSIFICATION OF BIMODAL COLLECTIONS OF SETS

We will now develop a complete characterisation of bimodal collections of sets, through a series of results that classify them according to the relationship between their sets A_i and the corresponding internal difference groups H_i. 


 For a bimodal collection A={A_1,A_2,…,A_m} of disjoint subsets of an abelian group G we have
 |A_i|≤ |H_i| for each i.  Without loss of generality, we suppose that the sets are labelled so that for i=1,2,…,r__ A we have |A_i|<|H_i|, and for i=r__ A+1,r__ A+2,…, m we have |A_i|=|H_i|, i.e. A_i fills the coset a_i+H_i for i>r__ A.



The following technical lemma will be useful in what follows.


Let A be a collection A_1,A_2,…,A_m of disjoint subsets of G that has the bimodal property.  Then A_k ∩ (a_j+H_j) = ∅ for any k≠ j.
 

B_j is a union of cosets of H_j, which does not include the coset a_j+H_j.  For k≠ j, we have A_k⊆ B_j, and so A_k∩ (a_j+H_j)=∅. 

In other words, not only is A_k disjoint from A_j when k≠ j, it is also disjoint from the entire coset of H_j that contains A_j.



 §.§ The case when r__ A≥ 2 

We will consider three cases: the situation when there are at least two sets A_i that do not fill a_i+H_i (i.e. r__ A≥ 2), the case when precisely one A_i does not fill a_i+H_i (i.e. r__ A=1), and the case when each of the sets in A fills the coset of H_i that contains it (r__ A=0).


Let A={A_1,A_2,…,A_m} be a bimodal collection of disjoint subsets of an abelian group G with r__ A≥ 2.  Then for i,j≤ r__ A with i≠ j we have that H_i is not a subgroup of H_j and H_j is not a subgroup of H_i.


Let A={A_1,A_2,…,A_m} be a bimodal collection of disjoint subsets of an abelian group G with r__ A≥ 2, and suppose that for some i,j≤ r__ A with i≠ j we have H_i≤ H_j.   Since |A_i|<|H_i| there are elements of a_i+H_i⊆ a_i+H_j that are not contained in B_j, and by Lemma <ref> these elements are not contained in any other set in A.  It follows that B_j is not a union of cosets of H_j, and so A is not bimodal.



Let A={A_1,A_2,…,A_m} be a bimodal collection of disjoint subsets of an abelian group G with r__ A≥ 2.  Then there exists a nonempty subset D__ A⊆ G such that:


  * a_i+H_i=A_i⊔ D__ A for i≤ r__ A;

  * (a_i+H_i)∩ (a_j+H_j)=D__ A for any i,j∈ 1,2,…, r__ A with i≠ j;

  * D__ A is itself a coset of a subgroup of G.






  *  Let D__ A=(a_1+H_1)∖ A_1.  We will show that D__ A=(a_i+H_i)∖ A_i for each i with 1≤ i≤ r__ A.  Let v∈ D__ A.  We observe that v∉ A, by Lemma <ref>; in particular, v∉ A_i for any i≠ 1.  For i with 2≤ i≤ r__ A there exists h_i∈ H_i with h_i∉ H_1, by Lemma <ref>.  As a_1∈ B_i, we have that a_1+h_i∈ B_i.  But a_1+h_i∉ A_1, so we also have a_1+h_i+h_1∈ B_1 for any h_1∈ H_1.  Taking h_1=v-a_1, we deduce that v+h_i∈ B_1.  

We claim that v+h_i∈ A_i.  For, if it were in B_i this would imply that v∈ B_i, which contradicts the fact that v∉ A.  In turn, this implies v∈ a_i+H_i. As v∉ A we conclude that v∈ (a_i+H_i)∖ A_i.  This shows that D__ A⊆(a_i+H_i)∖ A_i; repeating the above argument starting with v^'∈ (a_i+H_i)∖ A_i allows us to show that (a_i+H_i)∖ A_i⊆ D__ A.


  * Follows immediately from <ref>.

  * The set D__ A is precisely the intersection of all cosets a_i+H_i with i≤ r__ A.  This implies that D__ A is a coset of the subgroup obtained by taking the intersection of H_i for all i≤ r__ A.


A collection of sets F_1,F_2,… F_k with the property that F_i∩ F_j=D for all i≠ j is said to be a k-star with kernel D <cit.>.  Using this terminology, Proposition <ref> shows that for i with 1≤ i ≤ r__ A the collection of cosets a_i+H_i form an r__ A-star with kernel D__ A.


By Lemma <ref>, a bimodal collection of sets may undergo a shift without affecting its bimodality and so we can choose to shift a collection A with r__ A≥ 2 by an element of D__ A.  This will allow us to assume, without loss of generality, that D__ A is in fact a subgroup of G.


A bimodal collection A={A_1,A_2,…,A_m} of disjoint subsets of an abelian group G with r__ A≥ 2 will be said to be in canonical position if it has been shifted so that D__ A is  a subgroup of G.


We observe that if A={A_1,A_2,…,A_m} is a bimodal collection of subsets with r__ A≥ 2 in canonical position we have


  * D__ A is the subgroup ∩_i=1^r__ A H_i;

  * for i=1,2,…,r__ A we have that A_i=H_i∖ D__ A;

  * the subgroups H_1,H_2,…, H_r__ A form an r__ A-star with kernel D__ A.
 

We have thus seen that the sets A_1 to A_r__ A of a bimodal collection with r__ A≥ 2 occur together in a very structured way.  In fact, we will see that these sets also impose considerable structure on the remaining members of A.

Let A={A_1,A_2,…,A_m} be a bimodal collection of disjoint subsets of an abelian group G with r__ A≥ 2, in canonical position. Then 

    (H_1+H_2+…+H_r__ A) ∖ D__ A

is contained in A=∪_i=1^m A_i.


We begin by showing that (H_1+H_2)∖ D__ A⊆ A.  Let h∈ (H_1+H_2)∖ D__ A.  Then h=h_1+h_2 for some h_1∈ H_1 and h_2∈ H_2.  If h_1∈ D__ A then h_1+h_2∈ H_2 and hence in A_2⊆ A as h_1+h_2∉ D__ A.  Otherwise, h_1∈ A_1⊆ B_2.  This implies that h_1+h_2 is also in B_2⊆ A, by Remark <ref>.

Now consider h∈ (H_1+H_2+H_3)∖ D__ A, so h=h_1+h_2+h_3 with h_1∈ H_1, h_2∈ H_2 and h_3∈ H_3.  Suppose h_1+h_2∈ D__ A.  Then h_1+h_2+h_3∈ H_3 and hence h_1+h_2+h_3∈ A_3 as h_1+h_2+h_3∉ D__ A.  In the case where h_1+h_2∉ D__ A, the above argument shows that h_1+h_2∈ A=A_3∪ B_3.  Now, if h_1+h_2∈ B_3 then by Remark <ref> we have that h_1+h_2+h_3∈ B_3⊂ A.  If, however, h_1+h_2∈ A_3, then h_1+h_2+h_3∈ H_3 and hence h_1+h_2+h_3∈ A_3.

Proceeding analogously for all r__ A summands yields the desired result.

In some circumstances it may be the case that all elements of (H_1+H_2+…+ H_r__ A)∖ D__ A are contained in the union of the sets A_1,A_2,…,A_r__ A, but in general this will not be true, and there may be other sets A_i with i>r__ A  containing elements of H_1+H_2+… +H_r__ A.  Furthermore, there may also be elements of A that do not lie in H_1+H_2+… + H_r__ A. The following proposition tells us more about the sets A_i with i>r__ A.

Let A={A_1,A_2,…,A_m} be a bimodal collection of disjoint subsets of an abelian group G with r__ A≥ 2, in canonical position.  Then for A_i with i ≥ r__ A+1, the group H_i is a subgroup of D__ A.


Let A={A_1,A_2,…,A_m} be a bimodal collection of disjoint subsets of an abelian group G with r__ A≥ 2, in canonical position, and suppose there exists i> r__ A for which H_i is not a subgroup of D__ A.  Then there exists h_i∈ H_i with h_i∉ D__ A.  We observe that there exists j≤ r__ A with h_i∉ H_j, as the only elements common to all of the groups H_t with t≤ r__ A are those of D__ A. As a_j∈ B_i we thus have a_j+h_i∈ B_i, and furthermore a_j+h_i∈ B_j.  Let v∈ D__ A.  Then v-a_j∈ H_j, and thus a_j+h_i+(v-a_j)=v+h_i∈ B_j.  

Now, A=A_i∪ B_i, and B_i is a union of cosets of H_i.  Since |A_i|=|H_i|, this implies that in fact A is a union of cosets of H_i.  However, we have just shown that v+h_i∈ A.  As we know that v∉ A (since v∈ D__ A,) this leads to a contradiction.


This implies that each set A_i with i> r__ A is a coset of a subgroup of D__ A, and hence is contained in a coset of D__ A.  Hence each such set is either wholly contained within H_1+H_2+… +H_r__ A∖ D__ A, or else lies completely outside H_1+H_2+… + H_r__ A. Thus we now know that the set H_1+H_2+… +H_r__ A∖ D__ A is entirely partitioned by sets from A.   We also know that any A_i occuring outside of this set is a coset of a subgroup of D__ A.  The following proposition characterises the union of these A_i.


Let A={A_1,A_2,…,A_m} be a bimodal collection of disjoint subsets of an abelian group G with r__ A≥ 2, in canonical position. Let H be the group H=H_1+H_2+…+H_r__ A.  If A∖ H is nonempty, then it consists of a union of cosets of H; further, the sets A_i which lie in A ∖ H arise from a subdivision of these cosets of H.


We must show that if there is an element x∈ A∖ H then x+h∈ A for all h∈ H.  First suppose h∈ H_i for some i≤ r__ A.  As x∈ A∖ H we have x∈ B_i, and so x+h∈ B_i. Otherwise, h has the form h_1+h_2+…+h_r__ A with h_1∈ H_1,…,h_r__ A∈ H_r__ A.  But x∈ B_1 so (x+h_1)∈ B_1⊂ A.  Furthermore, as x∉ H we have x+h_1∉ H.  Hence x+h_1∈ B_2⊂ A, from which we deduce x+h_1+h_2∈ B_2.  Continuing in this manner we conclude that x+h_1+h_2+…+h_r__ A∈ B_r__ A⊂ A as required.  So A ∖ H is a union of cosets of H.
Since by Proposition <ref>,  we have that H_i ≤ D__ A≤ H for all i ≥ r__ A+1,  each A_i in A ∖ H must be wholly contained in a single coset of H.





The following theorem fully summarises the structure that has been determined in the above propositions.


Let A={A_1,A_2,…,A_m} be a bimodal collection of disjoint subsets of an abelian group G with r__ A≥ 2, in canonical position. Then


  * The internal difference groups H_1,H_2,…,H_r__ A form an r__ A-star with kernel D__ A, and for each i with 1≤ i ≤ r__ A we have A_i=H_i∖ D__ A.

  * Any set A_i with i> r__ A is a coset of a subgroup of D__ A.

  * If H denotes the group H_1+H_2+…+H_r__ A, then H∖ D__ A is contained in A.  Furthermore, the sets in A can be labelled such that for some k with r__ A≤ k≤ m we have that H∖ D__ A is partitioned by A_1,A_2,…,A_k.

  * If k<m then the sets A_i with i>k arise from a subdivision of cosets of H.



We will see that not only are the conditions of Theorem <ref> necessary for a collection of sets to be bimodal, they are sufficient as well.  We present a technique for constructing a bimodal collection of sets with r__ A≥ 2.

Let G be an abelian group, and for t≥ 2 let H_1,H_2,…,H_t be distinct subgroups of G forming a t-star with kernel D, such that |H_i:D|>2 for i with 1≤ i ≤ t.  Let H=H_1+H_2+…+H_t. 

Let A consist of the following subsets of G:


  * all subsets of the form A_i=H_i∖ D for i with 1≤ i ≤ t;

  * all cosets of D that are subsets of H, but are not in ∪_i=1^t H_i;

  * for any number of cosets of H, all the cosets of D that lie within those cosets of H.
 
Then A is a bimodal collection of subsets of G with r__ A=t in canonical position.


We will prove this result by applying Theorem <ref> to each of the internal difference groups of the sets in A. For any subset which is a coset of D, its internal difference group is the subgroup D itself.  For any A_i with 1 ≤ i ≤ t, its internal difference group is H_i: since the index of D in H_i is greater than 2, we know that A_i contains at least 2 distinct cosets of D.
Fix an element x ∈ A_i and consider all differences between x and the elements of A_i; these will give all elements of H_i except for those in the coset x+D.  Now, pick an element y ∈ A_i such that x and y lie in different cosets of D.  Taking all differences between y and the elements of A_i yields all elements of H_i except those in y+D.  Hence all elements of H_i lie in the internal difference group of A_i, as required. 


We observe that every set in A is a union of cosets of D.  Thus for any set whose internal difference group is D, the union of the remaining sets is a union of cosets of D, as required.  For A_i with 1 ≤ i ≤ t, we note that A_i ∪ D=H_i by construction, so B_i consists of H ∖ H_i together with a union of cosets of H, and is therefore a union of cosets of H_i.



By Theorem <ref>, new bimodal collections can be obtained by subdividing those subsets in the above construction that are cosets of D.  Comparing this construction with Theorem <ref>, we see that all bimodal collections of sets with r__ A≥ 2 arise in this way.










 §.§ The case when r__ A =1 


We now consider the situation where r__ A=1, i.e. when precisely one of the sets A_i does not fill the coset of H_i which contains it.


Let A={A_1,A_2,…,A_m} be a bimodal collection of disjoint subsets of an abelian group G with r__ A=1.  Then


  * for all i with 2≤ i ≤ m, A_i is a coset of H_i and H_i is a subgroup of H_1; 

  * A_1 is a proper subset of a coset of H_1, and consists of a union of cosets of the group D=H_2+H_3+…+H_m.






  * Suppose that for some i with 2≤ i ≤ m there exists h_i∈ H_i with h_i∉ H_1.  Let u∈ (a_1+H_1)∖ A_1, and let v be in A_1.  Then u-v∈ H_1. We have v∈ B_i, so v+h_i∈ B_i.  Since h_i∉ H_1 we have that v+h_i∈ B_1.  This implies that v+h_i+(u-v)∈ B_1, i.e. that u+h_i∈ B_1⊆ A.  Since A_i consists of a coset of H_i, we know that A=A_i⊔ B_i is a union of cosets of H_i.  This implies that if u+h_i∈ A then u∈ A.  However, by Lemma <ref> we know that no element of (a_1+H_1)∖ A_1 lies in A, which gives a contradiction.


  * Let x∈ A_1.  We want to show that for any d∈ D we have x+d∈ A_1.  Now d=h_2+h_3+…+h_m where h_i∈ H_i for 2≤ i ≤ m.  Since x∈ B_2 we have x+h_2∈ B_2.  However, by <ref> we know H_2≤ H_1, and so x+h_2∈ B_2 ∩ (a_1+H_1)=A_1.  This implies x+h_2∈ B_3, whence x+h_2+h_3∈ B_3.  Proceeding in this manner we determine that x+d∈ A_1 as required.





A bimodal collection A={A_1,A_2,…,A_m} of disjoint subsets of an abelian group G with r__ A=1 will be said to be in canonical position if it has been shifted so that A_1 ⊆ H_1 and the subgroup D=H_2+H_3+…+H_m is contained in H_1 ∖ A_1.


We summarise the structural properties of the situation.

Let A={A_1,A_2,…,A_m} be a bimodal collection of disjoint subsets of an abelian group G with r__ A=1, in canonical position. Let D=H_2+H_3+…+H_m.  Then


  * A_1 ⊆ H_1 ∖ D and A_1 is a union of cosets of D;

  * Each set A_i with 2≤ i ≤ m is a coset of H_i, and A_2,…,A_m arise from a subdivision of cosets of H_1.



We give a concrete example of a bimodal collection of sets with r__ A=1.

Let G=ℤ_36.  The collection A of subsets defined by
A_1={12,15,30,33},A_2={1,19},A_3={4,22},A_4={7,25},A_5={10,28},A_6={13},A_7={16},A_8={31},A_9={34} is bimodal.
We observe that H_1=⟨3⟩={0,3,6,9,12,15,18,21,24,27,30,33}, and H_2=H_3=H_4=H_5=⟨18⟩={0,18}, so H_2+H_3+H_4+H_5+H_6+H_7+H_8+H_9=⟨18⟩<H_1.  Note also that ∪_i=2^9 A_i is the coset 1+H_1, and that A_1 is a union of cosets of ⟨ 18 ⟩.  Here we have  A_1⊂ H_1, and we note that the set H_1∖ A_1 is not in fact a group.  (This is in contrast to the behaviour of bimodal collections of sets with r__ A≥ 2.)
 










We will see that not only are the conditions of the above theorem necessary for a collection of sets to be bimodal, they are sufficient as well.  We present a technique for constructing a bimodal collection of sets.

Suppose we have an abelian group G, a subgroup H_1 of G and a proper subset A_1 of H_1 whose internal differences generate H_1.


  * Let S be the set of all subgroups J ≤ G with the property that A_1 is a union of cosets of J.  


  * For any number of cosets of H_1, partition these cosets of H_1 using only cosets of subgroups from S.


  * Take A to consist of A_1 together with the sets in the above partition.  

Then A forms a bimodal collection of subsets of G with r__ A=1.



The bimodality of A is immediate, upon applying Theorem <ref> to each of the internal difference groups of the sets in A.



  


 §.§ The case when r__ A =0 

Finally, we consider the situation when each set A_i in A fills its own coset of H_i.


Let A={A_1,A_2,…,A_m} be a bimodal collection of disjoint subsets of an abelian group G with r__ A=0.  Let H be the group H=H_1+H_2+…+H_m.  Then each A_i (1 ≤ i ≤ m) is a coset of H_i, and these sets arise from a subdivision of cosets of H. 


We first prove that A is a union of cosets of H.  For each i, A_i is a coset of H_i and B_i is a union of cosets of H_i, hence A is a union of cosets of H_i for all i.
Let x∈ A and let h∈ H.  Then h has the form h_1+h_2+…+h_m with h_i∈ H_i for i with 1≤ i ≤ m.  As x∈ A we thus have x+h_1∈ A.  In turn this implies x+h_1+h_2∈ A and so on, so we deduce x+h∈ A, as required.  Since H_i ≤ H for all 1 ≤ i ≤ m, every A_i is wholly contained in a single coset of H, so A is a subdivision of the cosets of H.



By applying subdivision to the construction of Lemma <ref>, we obtain a bimodal collection of subsets in which each of the sets is a coset of its internal difference group, i.e. a bimodal collection with r__ A=0.  We note that the above theorem shows that every such collection arises in this manner.




§ FURTHER QUESTIONS

Now that we understand the full range of possible structures of bimodal collections of sets in abelian groups, we are led to some natural further questions.  The bimodal property arose in the context of studying external difference families corresponding to R-optimal AMD codes; it would be interesting to explore the potential for wider applications of this concept in related areas.   Group partitions, and particularly vector space partitions, also have a range of applications, and it would be of interest to investigate the role played by the bimodality of these structures in these applications.

Group partitions are known to exist for certain classes of nonabelian group, such as Frobenius groups, and these have been shown to give rise to bimodal collections of sets <cit.>.  It would be natural to seek to develop a comparable understanding of bimodality in a nonabelian context, although care must be taken to refine the relevant definitions where appropriate.




  





  


