Des. Codes Cryptogr. (2017) 84:451–461 DOI 10.1007/s10623-016-0280-x

Classification of partial difference sets in Abelian groups of order 4 p2 Stefaan De Winter1

· Zeying Wang1

Received: 16 May 2016 / Revised: 31 August 2016 / Accepted: 1 September 2016 / Published online: 22 September 2016 © Springer Science+Business Media New York 2016

Abstract In this article we provide a complete classification of regular partial difference sets in Abelian groups of order 4 p 2 , p an odd prime. It turns out that the known examples are the only examples. These are, up to complements, the trivial examples, the PCP examples, and a sporadic example in Z22 × Z23 . Keywords Partial difference set · Local multiplier theorem · Characteristic matrix Mathematics Subject Classification 05E30 · 05B10 · 05C50

1 Introduction Partial difference sets (PDS) play an important and interesting role in discrete mathematics. They provide a tool to construct strongly regular Cayley graphs, they generalize projective two-weight sets from elementary Abelian groups to more general groups,…Standard references are [5,6]. The study of PDS is typically carried out using the group ring. However, recently the authors used linear algebra to prove a “local” multiplier theorem for PDS in Abelian groups, and used this to show non-existence of PDS for several parameter sets where (non)-existence was open (see [3]). Two of the cases dealt with in [3] were in a group of order 100 = 4 × 52 , and 4 cases were in a group of order 196 = 4 × 72 . In this article we use the local multiplier theorem to obtain an elegant representation of regular PDS in Abelian groups of order 4 p 2 , p an odd prime, as a 4 × ( p + 1) (0, 1)-matrix. We then proceed by classifying all such matrices, henceforth obtaining a complete classification of regular PDS in Abelian

Communicated by D. Jungnickel.

B

Stefaan De Winter [email protected] Zeying Wang [email protected]

1

Michigan Technological University, Houghton, MI, USA

123

452

S. De Winter, Z. Wang

groups of order 4 p 2 . It is worthwhile to notice that only a few classification results for PDS are known. In most cases classifications are based on some parameter restrictions, see for example [1,7]. In that sense our approach is slightly different in that we put a restriction on the groups, but not on the parameters of the PDS. In graph theoretic language our result is equivalent with the classification of strongly regular Cayley graphs with 4 p 2 vertices arising from an Abelian group. Apart of being interesting in its own right the technique we introduce for studying these PDS seems to be suited for generalization.

2 Preliminary results Let G be a finite Abelian group of order v. Then D is a (v, k, λ, μ)-partial difference set in G if D is a k-subset of G with the property that the expressions gh −1 , g, h ∈ D, represent each non-identity element in D exactly λ times, and each non-identity element of G not in D exactly μ times. Further assume that D(−1) = D (where D(s) = {g s : g ∈ D} ) and e ∈ / D, where e is the identity of G, then D is a called a regular partial difference set. It is well-known (see e.g. [5]) that the Cayley graph G : =(G, D) of a PDS D is a strongly regular graph with parameters srg(v, k, λ, μ). Also, if λ  = μ then D(−1) = D is automatically fulfilled (see [5]). If D is a (v, k, λ, μ)-PDS and e ∈ D, then D \ {e} is a (v, k, λ − 2, μ)-PDS. It follows that the condition of being regular is not an actual condition if λ  = μ. A regular PDS is called trivial if D ∪ {e} or G \ {D} is a subgroup of G. If this subgroup is isomorphic to a group H , we will say that D is of type H . A PDS for which λ = μ is called a difference set, and is typically studied in its own right (see e.g. Chapter 6 of [2]). Whenever D is a difference set the condition D(−1) = D is not automatically fulfilled. Difference sets for which this condition holds are called reversible. In this article we will only study regular PDS. We also notice that if D is a regular PDS, then so is D = G \ (D ∪ {e}). We will call D the complement of D. Two regular PDS D and L in a group G are said to be isomorphic if there is an automorphism φ of G such that φ(D) = L. We now provide an important example of PDS, the so-called PCP partial difference sets (see [5]). Let G be an Abelian group of order n 2 . Let Ui , i = 1, . . . , k be a set of subgroups of G of order n with the property that Ui ∩ U j = {e} for all i  = j. Then D = ∪i Ui \ {e} is a regular PDS in G with parameters (n 2 , k(n − 1), n − 2 + (k − 1)(k − 2), k(k − 1)). We will say that D is of k-PCP type. The following result, due to S.L. Ma, is of great importance for us. Theorem 1 ([5]) No non-trivial PDS exists in – an Abelian group G with a cyclic Sylow- p-subgroup and o(G)  = p; – an Abelian group G with a Sylow- p-subgroup isomorphic to Z ps × Z pt where s  = t. We have immediately the following corollary. Corollary 1 If a non-trivial PDS exists in an Abelian group G of order 4 p 2 , p an odd prime, then G ∼ = Z22 × Z2p . We next mention the so-called local multiplier theorem (LMT) that was proved by the authors in [3]. Theorem 2 [LMT] Let D be a regular (v, k, λ, μ)-PDS in the Abelian group G. Furthermore assume (λ − μ)2 + 4(k − μ) is a perfect square. Let g ∈ G be an element of order r . Assume gcd(s, r ) = 1. Then g ∈ D if and only if g s ∈ D.

123

Partial difference sets in Abelian groups of order 4 p 2

453

We note that (λ − μ)2 + 4(k − μ) is always a perfect square, unless when D is a v−5 v−1 (v, v−1 2 , 4 , 4 )-PDS, with v not a perfect square. Hence, whenever D is a regular 2 (4 p , k, λ, μ)-PDS the value (λ − μ)2 + 4(k − μ) is always a perfect square, and the LMT applies. As mentioned in the introduction, the aim of this paper is to provide a complete classification of regular PDS in Abelian groups of order 4 p 2 . We first describe the known non-trivial examples. Recall that the group is always Z22 × Z2p . – 2-PCP type PDS in Z22 × Z2p . It is easy to see that all PDS of this type are isomorphic. – 3-PCP type PDS in Z22 × Z2p . It is easy to see that all PDS of this type are isomorphic. – Let G be a 3-PCP in Z22 × Z23 , and let g be an element of order 2. Set L = g G . Then L is a reversible (36, 15, 6)-difference set and D = L \ {e} is a regular (36, 14, 4, 6)-PDS. We will say D is of type S. All PDS of this type are isomorphic (this will also follow from our classification result). Our main result is as follows: Theorem 3 If D is a non-trivial regular PDS in an Abelian group of order 4 p 2 , p an odd prime, then D is (up to complement) either of 2-PCP type, of 3-PCP type, or of type S. An immediate consequence of this theorem is the non-existence of Abelian (100, 33, 8, 12) -PDS, (100, 36, 14, 12)-PDS, (196, 60, 14, 20)-PDS, (196, 65, 24, 20)-PDS, (196, 75, 26, 30)-PDS and (196, 78, 32, 30)-PDS that was recently proved by the authors in [3]. These parameter sets belonged to the list of 18 hypothetical regular Abelian PDS with k < 100 for which (non)-existence had not been determined (see [3,5,6]). The techniques used in [3] strongly depend on knowing the parameters of the hypothetical PDS. However, the number of cases in Abelian groups of order 4 p 2 for which existence has not been determined grows rapidly with p, and no nice closed formula for the parameters of those cases is available. As a consequence we needed to develop a new technique to prove Theorem 3. Finally we want to note that the situation in the non-Abelian case is quite different: for instance, Jørgensen and Klin [4] found regular PDS not of the PCP type in non-Abelian groups of order 100.

3 The characteristic matrix From here on let G = Z22 × Z2p , and let D be a regular PDS in G. Though perhaps somewhat unintuitive we will denote the identity of G by g1 , and the three elements of order two by g2 , g3 and g4 respectively. Furthermore, let H1 , H2 , . . . , H p+1 denote the p + 1 subgroups of order p in G, and set Si j = gi H j \ {gi }, for i = 1, 2, 3, 4 and j = 1, 2, . . . , p + 1. Lemma 1 If h ∈ D and h ∈ Si j , then Si j ⊂ D. Proof If h ∈ Si j then h = gi h j for some h j ∈ H j \ {g1 }. If i = 1 then h has order p and by the LMT all powers of h distinct from the identity belong to D. If i  = 1, then h has order 2 p. By the LMT h k , where k is odd and not divisible by p, belongs to D. It follows that gi h kj = (gi h j )k = h k belongs to D. For l even and not divisible by p we have, gi h lj = (gi h j )l+ p = h l+ p , and hence gi h lj belongs to D. It is now obvious that Si j ⊂ D.

Lemma 1 turns out to be extremely useful, as it allows us to represent the PDS by means of a simple (0, 1)-matrix.

123

454

S. De Winter, Z. Wang

Definition 1 The characteristic matrix χD of D is the 4 × ( p + 1)-matrix whose entry in position i j is a 1 iff Si j ⊂ D and a 0 otherwise. The extended characteristic matrix χ D of D is the 4 × ( p + 2)-matrix whose last p + 1 columns form the matrix χD , and whose entry in position i1 is a 1 iff gi ∈ D and a 0 otherwise. From this definition and the above lemma it is clear that knowing D is equivalent to knowing χ D . However, though the matrix χD does not contain all information (namely which elements of order two belong to D is not encoded in χD ), it turns out that this matrix is handier to work with. Below we present the extended characteristic matrix, up to equivalence, for the three non-trivial PDS in Z22 × Z2p : ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ 0 1 1 1 0 ··· 0 00100 0 1 1 0 ··· 0 ⎜0 0 0 0 ··· 0⎟ ⎜1 1 0 0 0 ··· 0⎟ ⎜0 0 1 1 1⎟ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎝1 1 0 0 ··· 0⎠, ⎝1 0 1 0 0 ··· 0⎠, ⎝1 0 0 1 0⎠. 1 0 1 0 ··· 0 1 0 0 1 0 ··· 0 10001 2-PCP 3-PCP type S For brevity of notation we will represent columns of χ as transposed row vectors throughout this paper. Let T be a subset of G not containing g1 with the property that for any set Si j (as defined above), we either have Si j ∩ T = ∅ or Si j ⊂ T . Then we can define the characteristic matrix χT in a similar way as χD , that is, χT is the 4 × ( p + 1)-matrix whose entry in position i j is a 1 iff Si j ⊂ T and a 0 otherwise. Let h be an element of order p or 2 p in G. We now note that the number of ways in which h can be written as a difference of elements in T only depends on the pair (i, j) such that h ∈ Si j , and not on the specific element h. If Si j ⊂ T we will write λi j for this number, if Si j does not belong to T we will denote it by μi j . Furthermore, it is easy to derive explicit formulas for these values as they depend only on what the jth column looks like. We explain this in greater detail below. We will say that an element of G belongs to row i if it belongs to some Si j . Denote by Ri , i = 1, 2, 3, 4 the ith row of χT , and by ri = Ri · Ri , that is, the number of entries equal to 1 in the ith row. Assume for a moment that T does not contain elements of order 2, and that the first column of χT equals (1, 1, 0, 0)T . Then we can compute – – – –

λ1,1 = 2 p + r12 + r22 + r32 + r42 − 3r1 − 3r2 − r3 − r4 ; λ2,1 = 2( p + r1 r2 + r3 r4 − r1 − r2 − R1 · R2 − R3 · R4 ); μ3,1 = 2(r1 r3 + r2 r4 − r3 − r4 − R1 · R3 − R2 · R4 ); μ4,1 = 2(r1 r4 + r2 r3 − r3 − r4 − R1 · R4 − R2 · R3 ).

We explain how the values for λ1,1 and λ2,1 were obtained. We first make the following observation which follows directly from elementary group theory. Observation 1 Consider Si j and Skl . And assume r is such that gi gk = gr . (i) If i = k and j = l, every element of S1 j can be written in exactly p − 2 ways as a difference of elements from Si j . (ii) If i = k and j  = l, every element of S1t , t ∈ / { j, l}, can be written in exactly 2 ways as a difference using elements from Si j ∪ Skl . (iii) If i  = k and j = l, every element of Sr j can be written in exactly 2( p − 2) ways as a difference using elements from Si j ∪ Skl .

123

Partial difference sets in Abelian groups of order 4 p 2

455

(iv) If i  = k and j  = l, every element of Sr t , t ∈ / { j, l}, can be written in exactly 2 ways as a difference using elements from Si j ∪ Skl . We now compute λ1,1 . In order to obtain an element h in S1,1 as a difference of two elements in T it is necessary that these two elements belong to the same row of χT . This brings us in the first and second case of the above observation. We obtain λ1,1 = [ p − 2 + (r1 − 1)(r1 − 2)] + [ p − 2 + (r2 − 1)(r2 − 2)] + [r3 (r3 − 1)] + [r4 (r4 − 1)], hence the formula for λ1,1 . The case λ2,1 is slightly more complicated, although the general idea is the same. In order to obtain an element h in S2,1 as a difference of two elements in T it is necessary that one of these elements belongs to row 1 and the other to row 2, or that one of these elements belongs to row 3 and the other to row 4 (this is because g1 g2 = g2 and g3 g4 = g2 ). This brings us in the third and fourth case of the above observation. Using elements of row 1 and 2, case (iii) occurs once and case (iv) occurs (r1 − 1)(r2 − 1) − R1 · R2 + 1 times. When using row 3 and row 4 case(iii) never occurs, and case (iv) occurs r3 r4 − R3 · R4 times. It follows that λ2,1 = 2( p − 2) + 2((r1 − 1)(r2 − 1) − R1 · R2 + 1) + 2(r3 r4 − R3 · R4 ), the desired formula. The reader may want to check the formulas for μ3,1 and μ4,1 . Similar arguments can be used for any other type of column. Whenever T contains elements of order 2, one can first use the above approach and then adjust the obtained formula for the number of differences that involve an element of order 2 (the latter is easily counted).

4 The classification From here on let D be a regular PDS in G. As it is sufficient to determine D up to complement, we can restrict ourselves to the case where Z22 ∩ D = ∅ or |Z22 ∩ D| = 1. We will treat the two cases separately. In each case our aim is to classify the possible characteristic matrices. To simplify notation we denote χD by χ. We note that the automorphism group of G, in its natural action on the columns of χ, acts 3-transitively.

4.1 The case Z22 ∩ D = ∅ We start by deriving an interesting relationship between the rows of χ. Lemma 2 It holds that R1 · R2 + R3 · R4 = R1 · R3 + R2 · R4 = R1 · R4 + R2 · R3 . Furthermore μ = 2( p − 1)(R1 · R2 + R3 · R4 ). Proof If μg2 , respectively μg3 and μg4 , denotes the number of ways g2 , respectively g3 and g4 , can be represented as a difference of elements in D we easily see that μg2 = 2( p −1)(R1 · R2 + R3 · R4 ), μg3 = 2( p − 1)(R1 · R3 + R2 · R4 ), and μg4 = 2( p − 1)(R1 · R4 + R2 · R3 ). As we assume D is a PDS it follows that these three values must be equal.

We next prove a lemma that reduces the possible types of columns that can appear in χ. Lemma 3 The only column of odd weight that can appear in χ is (1, 0, 0, 0)T . Proof Assume χ would contain a column (0, 1, 0, 0)T . Without loss of generality we can assume this is the first column. Computing μ1,1 yields μ1,1 = p − 2 + r1 (r1 − 1) + (r2 − 1)(r2 − 2) + r3 (r3 − 1) + r4 (r4 − 1) which is clearly odd, contradicting the fact that μ is even (by Lemma 2). In the same way χ cannot contain a column (0, 0, 1, 0)T or (0, 0, 0, 1)T .

123

456

S. De Winter, Z. Wang

Next assume χ would contain (1, 1, 1, 0)T as first column. Computing λ1,1 yields λ1,1 = 3( p − 2) + (r1 − 1)(r1 − 2) + (r2 − 1)(r2 − 2) + (r3 − 1)(r3 − 2) + r4 (r4 − 1) which is clearly odd. On the other hand λ2,1 = 2 p + 2(r1 r2 + r3 r4 − r1 − r2 − r4 − R1 · R2 − R3 · R4 ) which obviously is even, a contradiction. In exactly the same way χ cannot contain a column (1, 1, 0, 1)T or (1, 0, 1, 1)T . Finally assume that χ would contain (0, 1, 1, 1)T as first column. Computing μ1,1 yields μ1,1 = 3( p − 2) + r1 (r1 − 1) + (r2 − 1)(r2 − 2) + (r3 − 1)(r3 − 2) + (r4 − 1)(r4 − 2) which is odd, contradicting Lemma 2.

A case by case analysis will now allow us to determine the allowable characteristic matrices. Case 1 The characteristic matrix contains a column (1, 0, 0, 0)T . Lemma 4 In this case χ cannot contain a column of weight 2 or 4. Proof Assume without loss of generality that (1, 0, 0, 0)T is the first column in χ. Then λ1,1 = p − 2 + (r1 − 1)(r1 − 2) + r2 (r2 − 1) + r3 (r3 − 1) + r4 (r4 − 1), which is clearly odd. Assume χ also contains a column (1, 1, 1, 1)T , say, without loss of generality, as its second column. We compute that λ1,2 = 4( p − 2) + (r1 − 1)(r1 − 2) + (r2 − 1)(r2 − 2) + (r3 − 1)(r3 − 2) + (r4 − 1)(r4 − 2), which is clearly even. As D is a PDS we need λ1,1 = λ1,2 , yielding a contradiction. Similarly, computing any λ-value for a column with even weight yields an even value, and hence a contradiction. This proves the lemma.

We now know that the characteristic matrix, up to permutation of columns, has the following shape, where a is the number of columns (1, 0, 0, 0)T :  ⎛ 1 ⎜0 χ=⎜ ⎝0 0

a



p+1−a



··· ··· ··· ···

1 0 0 0

0 0 0 0

⎞ 0 0⎟ ⎟. 0⎠ 0

··· ··· ··· ···

Lemma 5 It holds that either a = 1 or a = p + 1. Proof Assume by way of contradiction that 1 < a < p + 1. From Lemma 2 it follows that μ = 0. However, computing μ1, p+1 (note that without loss of generality χ1, p+1 = 0 if a < p + 1) yields μ1, p+1 = a(a − 1) > 0. A contradiction.

Proposition 1 The only regular PDS that can occur in this case are of type Z p and Z p × Z p . Proof This follows immediately from the previous lemma that provides the classification of characteristic matrices in this case.

Case 2 The characteristic matrix does not contain a column (1, 0, 0, 0)T . In this case we know that the characteristic matrix has, up to permutation of columns, the following shape: ⎛

a b c d e f g h                

0 ⎜0 χ=⎜ ⎝0 0

123

··· ··· ··· ···

0 0 0 0

1 1 0 0

··· ··· ··· ···

1 1 0 0

1 0 1 0

··· ··· ··· ···

1 0 1 0

1 0 0 1

··· ··· ··· ···

1 0 0 1

0 1 1 0

··· ··· ··· ···

0 1 1 0

0 1 0 1

··· ··· ··· ···

0 1 0 1

0 0 1 1

··· ··· ··· ···

0 0 1 1

1 1 1 1

··· ··· ··· ···

⎞ 1 1⎟ ⎟. 1⎠ 1

Partial difference sets in Abelian groups of order 4 p 2

457

Here the overbrace labels will denote both the type of a column and the number of such columns. Clearly the number of ways in which an element of Si j can be written as a difference of elements of D only depends on whether the elements of Si j belong to D and on the column type of column j. We will denote this number by λi,t , t ∈ {a, b, . . . , h}, if the i jth entry of χ is a 1 and column j is of type t, and by μi,t , t ∈ {a, b, . . . , h}, if the i jth entry of χ is a 0 and column j is of type t. Corollary 2 It holds that b + g = c + f = d + e. Proof This is simply a restatement of the result R1 · R2 + R3 · R4 = R1 · R3 + R2 · R4 = R1 · R4 + R2 · R3 from Lemma 2.

Lemma 6 It holds that be = cg = d f = 0. Proof Assume to the contrary that b > 0 and e > 0. We compute λ2,b = 2( p + r1 r2 + r3 r4 − r1 − r2 − R1 · R2 − R3 · R4 ) and λ2,e = 2(r1 r2 + r3 r4 − r1 − r4 − R1 · R2 − R3 · R4 ). Setting λ2,b = λ2,e yields r2 − r4 = p. On the other hand, using Corollary 2, r2 − r4 = (b + e) − (d + g) = 2(b − d), contradicting that p is odd. It follows that be = 0. The other equalities follow by symmetry (or a similar computation).

Lemma 7 It holds that b = c = d = 0 and e = f = g. Proof If b > 0, we have e = 0. Using Corollary 2 and Lemma 6 this implies c, d > 0, and f = g = 0. First assume h > 0. Then λ1,h = 4 p + r12 + r22 + r32 + r42 − 3(r1 + r2 + r3 + r4 ). Computing λ1,b we obtain λ1,b = 2 p+r12 +r22 +r32 +r42 −(3r1 +3r2 +r3 +r4 ). As D is a PDS we need λ1,h = λ1,b , that is, 2 p = 2r3 + 2r4 or p = r3 + r4 . However, r3 + r4 = 2b + 2h, which would imply that p is even, a contradiction. Secondly assume that h = 0. We compute μ2,c = 2(r1 r2 + r3 r4 − r2 − r4 − R1 · R2 − R3 · R4 ) = 2b(4b − 3). Using Lemma 2 this implies that p − 1 = 4b − 3, and hence that p is even, a contradiction. Hence b = 0 and by Corollary 2 g = c + f = d + e. If c > 0 then g > 0 and so cg > 0, contradicting Lemma 6. Hence c = 0. If d > 0 then f > 0 and so d f > 0, a contradiction. Hence d = 0. Using Corollary 2 this implies e = f = g.

Proposition 2 The PDS D is the complement of a PDS either of type Z2 × Z2 , of type Z2 × Z2 × Z p , or of type 3-PCP. Proof First assume that e = f = g = 0. If h = 0, D is the empty set. If a = 0 and h > 0 it follows that D is the complement of a PDS of type Z2 × Z2 . If a > 0 and h > 0 we compute μ1,a = 4h(h − 1). On the other hand, by Lemma 2 μ = 2( p − 1)2h. As D is a PDS and h > 0 this yields h = p. It follows that D is the complement of a PDS of type Z2 × Z2 × Z p . Secondly assume e = f = g > 0. If h = 0 we compute μ1,e = 2 p + r12 + r22 + r32 + r42 − r1 −3r2 −3r3 −r4 = 2 p +12e2 −14e. Setting this equal to the value for μ = 2( p −1)e from Lemma 2, we see that p prime implies that e = 1. As p + 1 = a + 3e = a + 3 and p > 2, it follows that a > 0. Finally we compute μ1,a = r12 + r22 + r32 + r42 − r1 − r2 − r3 − r4 = 6. It follows (using μ = 2( p − 1)e) that p − 1 = 3, or that p = 4, a contradiction. If h > 0 we compute λ2,h = 4 p + 2(r1 r2 + r3 r4 − r1 − r2 − r3 − r4 − R1 · R2 − R3 · R4 ) and compare with λ2,e = 2(r1 r2 + r3 r4 − r1 − r4 − R1 · R2 − R3 · R4 ). As D is a PDS we need λ2,h = λ2,e , that is, 4 p = 2r2 + 2r3 or r2 + r3 = 2 p. As f, g > 0 implies that r2 , r3 ≤ p, it follows that necessarily r2 = r3 = r4 = p, and hence that e = f = g = 1 and a = 0. Consequently χ has the shape of the complement of a 3-PCP.



123

458

S. De Winter, Z. Wang

4.2 The case |Z22 ∩ D| = 1 As mentioned before, we may suppose without loss of generality that g2 is the unique element of order 2 in D in this case. We will follow a similar approach as in the previous subsection, however, some care is necessary as not all permutations of rows 2, 3 and 4 yield equivalent PDS. Only interchanging row 3 and 4 yields equivalent PDS. Lemma 8 It holds that R1 · R3 + R2 · R4 = R1 · R4 + R2 · R3 . Furthermore λ = 2( p − 1)(R1 · R2 + R3 · R4 ) and μ = 2( p − 1)(R1 · R3 + R2 · R4 ). Proof This is proved in exactly the same way as Lemma 2.

Lemma 9 The characteristic matrix can only contain even weight columns. Proof If the first column of χ would be (1, 0, 0, 0)T , (1, 1, 1, 0)T , (1, 1, 0, 1)T or (1, 0, 1, 1)T then one computes λ1,1 and always finds an odd value, contradicting Lemma 8. If the first column of χ would be (0, 1, 0, 0)T , (0, 0, 1, 0)T , (0, 0, 0, 1)T or (0, 1, 1, 1)T then one computes μ1,1 and always finds an odd value, again contradicting Lemma 8.

We now know that the characteristic matrix has the following shape ⎛

a b c d e f g h                

0 ⎜0 χ=⎜ ⎝0 0

··· ··· ··· ···

0 0 0 0

1 1 0 0

··· ··· ··· ···

1 1 0 0

1 0 1 0

··· ··· ··· ···

1 0 1 0

1 0 0 1

··· ··· ··· ···

1 0 0 1

0 1 1 0

··· ··· ··· ···

0 1 1 0

0 1 0 1

··· ··· ··· ···

0 1 0 1

0 0 1 1

··· ··· ··· ···

0 0 1 1

1 1 1 1

··· ··· ··· ···

⎞ 1 1⎟ ⎟. 1⎠ 1

As before the overbrace labels will denote both the type of a column and the number of such columns. We will continue to use the same notation as introduced in the previous subsection. With this notation we immediately have the following. Corollary 3 It holds that c + f = d + e. Proof This is simply expressing that R1 · R3 + R2 · R4 = R1 · R4 + R2 · R3 which was the conclusion of Lemma 8.

Lemma 10 It holds that ce = 0 and d f = 0. Proof Assume by way of contradiction that c > 0 and e > 0. We compute λ3,c = 2 p + 2(r1 r3 +r2 r4 −r1 −r3 − R1 · R3 − R2 · R4 ), and λ3,e = 2(r1 r3 +r2 r4 −r1 −r4 − R1 · R3 − R2 · R4 ). Setting both values equal results in p = r3 − r4 . On the other hand, using Corollary 3, r3 − r4 = (c + e) − (d + f ) = 2(c − d), contradicting that p is odd. It follows that ce = 0. The equality d f = 0 can be proved similarly by comparing μ3,d and μ3, f .

Lemma 11 It holds that c = d and e = f . Proof From Corollary 3 it follows that c − e = d − f . Squaring and using ce = d f = 0 this implies that (c + e)2 = (d + f )2 . As c + e and d + f are both nonnegative it follows that c + e = d + f . Combining this with Corollary 3 proves the result.



123

Partial difference sets in Abelian groups of order 4 p 2

459

Corollary 4 It holds that r3 = r4 . We will base our classification of PDS on whether χ contains columns of type b and h. We start with the following lemma. Lemma 12 It holds that bh = 0. Proof Assume b > 0 and h > 0. We compute λ1,b = 2 + 2 p + r12 + r22 + r32 + r42 − (3r1 + 3r2 + r3 + r4 ) and λ1,h = 2 + 4 p + r12 + r22 + r32 + r42 − 3(r1 + r2 + r3 + r4 ). As D is a PDS we need λ1,h = λ1,b , that is, 2 p = 2r3 + 2r4 or p = r3 + r4 . However, r3 = r4 by Corollary 4. Hence p is even, a contradiction.

Proposition 3 If b > 0 then D is a PDS of type Z2 × Z p or Z2 × Z p × Z p . Proof We first show that g = 0. Assume not, and compute μ1,g . We obtain μ1,g = 2 p +r12 + r22 + r32 + r42 − (r1 + r2 + 3r3 + 3r4 ). Using the value for λ1,b obtained above, one computes λ1,b − μ1,g = 2 − 2(r1 + r2 ) + 2(r3 + r4 ) = 2 − 4(g − b), which is congruent to 2 mod 4. However, by Lemma 8, λ − μ must be divisible by 2( p − 1), and hence by 4, a contradiction. Next we compute λ2,b = 2+2 p+2r1 r2 +2r3 r4 −2r1 −2r2 −2(R1 · R2 + R3 · R4 ). Using that r3 = r4 we obtain that 0 = λ1,b −λ2,b = r12 +r22 −2r1 r2 −r1 −r2 −2r3 +2(R1 · R2 + R3 · R4 ). Substituting r1 = b + 2c, r2 = b + 2 f , r3 = c + f , R1 · R2 + R3 · R4 = b, and simplifying yields c2 −c+ f 2 − f = 0, where we have used c f = ce = 0. It follows that c+ f ∈ {0, 1}. If c + f = 1 we compute λ1,b = 2b(b −1)+2 p which is congruent to 2 (mod 4). However, by Lemma 8 λ is divisible by 2( p−1), and hence by 4, a contradiction. It follows that c = f = 0. Finally, assume a > 0. Then μ1,a = r12 + r22 + r32 + r42 − (r1 + r2 + r3 + r4 ) = 2b2 − 2b. However, by Lemma 8 μ = 0. As b > 0 it follows that b = 1. So either a = p and b = 1 or a = 0 and b = p + 1. The result follows.

Lemma 13 If h > 0 then – it holds that a = 0; – it holds that c + e ∈ {0, 1}; – it holds that (r1 − r3 )(r2 − r3 ) + c + e − g = 0. Proof We start by showing that a = 0. Assume not, and compute λ1,h − μ1,a = 2 + 4 p − 2(r1 + r2 + r3 + r4 ) = 2 + 4 p − 2(2c + 2d + 2e + 2 f + 2g + 4h), which is 2 mod 4, contradicting Lemma 8. Next we show that (c + e)(c + e − 1) = 0. We have λ1,h = 2 + 4 p + r12 + r22 + r32 + r42 − 3(r1 +r2 +r3 +r4 ), and λ2,h = 2+4 p+2(r1 r2 +r3 r4 −r1 −r2 −r3 −r4 − R1 · R2 − R3 · R4 ). We compute, using r3 = r4 , that λ1,h − λ2,h = (r1 −r2 )2 − (r1 +r2 + 2r3 ) + 2(R1 · R2 + R3 · R4 ). Substituting r1 = 2c + h, r2 = 2e + h, r3 = c + e + g + h, R1 · R2 = h, and R3 · R4 = g + h, yields 4(c + e)(c + e − 1) = 0. Finally we have λ3,h = 2 + 4 p + 2(r1 r3 + r2 r4 − r1 − r2 − r3 − r4 − R1 · R3 − R2 · R4 ). Using r3 = r4 , R1 · R2 + R3 · R4 = g + 2h and R1 · R3 + R2 · R4 = c + e + 2h it follows that λ2,h −λ3,h = 2(r1 r2 +r32 −r1 r3 −r2 r3 − g +c +e). Hence (r1 −r3 )(r2 −r3 )+c +e − g = 0.

Proposition 4 If h > 0 then D is the complement of a PDS of type 2-PCP, or D is the complement of a PDS of type S. Proof We start by noting that r1 = 2c + h, r2 = 2e + h, and r3 = r4 = c + e + g + h. Based on the previous lemma we will consider the following cases: (c, e) = (1, 0), (c, e) = (0, 1), and (c, e) = (0, 0).

123

460

S. De Winter, Z. Wang

If (c, e) = (1, 0) the last part of the previous lemma yields g(g − 1) = 0. Hence either g = 0 or g = 1. When g = 0 it follows that h = p − 1. We compute λ1,c = 2 p + r12 + r22 + r32 + r42 − (3r1 + r2 + 3r3 + r4 ) = 4 p 2 − 6 p. On the other hand, by Lemma 8, λ = 2( p − 1)(2 p − 2). Hence p = 2, a contradiction. When g = 1 it follows that h = p − 2. It follows that λ1,h = 4 p 2 −12 p+12. On the other hand, by Lemma 8, λ = 2( p−1)(2 p−3). Setting both values equal yields p = 3, and hence h = 1. It follows that D is the complement of a PDS of type S. If (c, e) = (0, 1) we find just as above that either g = 0 or g = 1. When g = 0 it follows that h = p − 1 and D is the complement of a PDS of type 2-PCP. When g = 1 it follows that h = p − 2. It follows that λ1,h = 4 p 2 − 12 p + 12. On the other hand, by Lemma 8, λ = 2( p − 1)(2 p − 3). Setting both values equal yields p = 3, and hence h = 1 and μ = 12 (by Lemma 8). However μ1,e = 14, a contradiction. If (c, e) = (0, 0) we once again obtain that g is either 0 or 1, and that g + h = p + 1. When g = 0 we find λ1,h = 4 p 2 − 6, whereas the value for λ obtained from Lemma 8 is λ = 4( p 2 − 1), a contradiction. When g = 1 we find λ1,h = 4 p 2 − 4 p − 2, whereas the value for λ obtained from Lemma 8 is λ = 2( p − 1)(2 p + 1), a contradiction.

Proposition 5 If b = h = 0 then D is of type Z2 . Proof We start by showing that g = 0. By way of contradiction, assume that g > 0. If a > 0, then μ1,g = 2( p−2)+r1 (r1 −1)+r2 (r2 −1)+(r3 −1)(r3 −2)+(r4 −1)(r4 −2) should equal μ1,a = r1 (r1 − 1) + r2 (r2 − 1) + r3 (r3 − 1) + r4 (r4 − 1), implying that p = r3 + r4 = 2r3 , a contradiction. It follows that a = 0. Now 2c + 2e + g = p + 1, and hence g is even. If c > 0, then e = 0, and r1 = 2c, r2 = 0, and r3 = r4 = c + g. Simplifying the expression for μ1,g yields μ1,g = 2( p − 2) + 2c(2c − 1) + 2(c + g)(c + g − 1) which should be divisible by 4. It follows that c is odd. On the other hand λ1,c = 2( p −2)+2(c −1)(2c −1)+2(c + g −1)2 . As c is odd and λ1,c ≡ 0 (mod 4), it follows that c + g − 1 is odd, a contradiction given that g is even. Hence c = 0. If e > 0, then r1 = 0, r2 = 2e, and r3 = r4 = e + g. Setting μ1,g equal to μ1,e = 2+2( p−2)+r1 (r1 −1)+(r2 −1)(r2 −2)+(r3 −1)(r3 −2)+r4 (r4 −1) and simplifying yields e = g + 1. Substituting in the formula for μ1,g gives μ1,g = 2( p − 1) + 12g 2 + 2g. On the other hand, by Lemma 8, μ = 2( p − 1)e = 2( p − 1)(g + 1). It follows that p = 6g + 2, a contradiction. Thus c = e = 0, and g = p + 1. One readily checks that this does not yield a PDS. So from now on we may assume that g = 0. We next need to show that c = e = 0. We proceed by contradiction. First assume c > 0 (and hence e = 0). Then r1 = 2c, r2 = 0, and r3 = r4 = c. We compute λ1,c = 2 p+6c2 −10c. On the other hand, using Lemma 8, we have λ = 0. This yields a contradiction, and hence c = 0. If e > 0, then r1 = 0, r2 = 2e, and r3 = r4 = e. We compute λ2,e = 2e2 − 2e. On the other hand, using Lemma 8, we have λ = 0. This yields e = 0 or e = 1. If e = 0, we see that χ is the all-zero-matrix, and we are done. If e = 1, we have a > 0 and we compute μ1,a = 2, contradicting μ = 2( p − 1) as obtained from Lemma 8. This concludes the proof.



5 Conclusion Proof of Theorem 3 Combining the results of Propositions 1, 2, 3, 4 and 5 proves the theorem.



123

Partial difference sets in Abelian groups of order 4 p 2

461

It is worthwhile to note that the concept of characteristic matrix can easily be extended to include regular PDS in groups Zsp × Zqt for p and q distinct primes. However, obvious difficulties arise when trying to classify these matrices if p, q > 2 and/or s, t > 2. Nevertheless, we believe that the characteristic matrix will play an important role in the further study of PDS in these groups.

References 1. Arasu K.T., Jungnickel D., Ma S.L., Pott A.: Strongly regular Cayley graphs with λ − μ = −1. J. Comb. Theory Ser. A 67, 116–125 (1994). 2. Beth T., Jungnickel D., Lenz H.: Design Theory, 2nd edn. Cambridge University Press, Cambridge (1999). 3. De Winter S., Kamischke E., Wang Z.: Automorphisms of strongly regular graphs with applications to partial difference sets. Des. Codes Cryptogr. 79, 471–485 (2016). 4. Jørgensen L.K., Klin M.: Switching of edges in strongly regular graphs. I. A family of partial difference sets on 100 vertices. Electron. J. Comb. 10, R17 (2003). 5. Ma S.L.: A survey of partial difference sets. Des. Codes Cryptogr. 4, 221–261 (1994). 6. Ma S.L.: Some necessary conditions on the parameters of partial difference sets. J. Stat. Plan. Inference 62, 47–56 (1997). 7. McFarland R.L.: Sub-difference sets of Hadamard difference sets. J. Comb. Theory Ser. A 54, 112–122 (1990).

123