# Holey Perfect Mendelsohn Designs of Type2nu1 with Block Size Four

Authors: Hantao Zhang
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

Let 4-HPMD denote aholey perfect Mendelsohn design with block size four. The existence of 4-HPMDs with n holes of size 2 and one hole of size 3, that is, of type 2n31, was established by Bennett et al. in 1997. In this paper, we investigate the existence of 4-HPMDs of type 2nu1 for 1≤u≤16: a 4-HPMD(2nu1) exists if and only if n≥max(4,u+1), except possibly for (n,u)=(7,5), (7, 6), (11, 9), (11, 10). We also investigate the existence of 4-HPMD(2nu1) for general u and prove that there exists a 4-HPMD(2nu1) for all n≥⌈5u/4⌉+4. Moreover, if u≥35, then a 4-HPMD(2nu1) exists for all n≥⌈5u/4⌉+1; if u≥95, then a 4-HPMD(2nu1) exists for all n≥⌈5u/4⌉−2.


---

## Body

## 1. Introduction

Letv,k be positive integers, a (v,k,λ)-Mendelsohn design, briefly (v,k,λ)-MD, is a pair (X,ℬ), where X is a v-set (of points) and ℬ is a collection of cyclically ordered k-subset of X (called blocks) such that every ordered pair of points of X are consecutive in exactly λ blocks of ℬ. If for all t=1,2,…,k-1, every ordered pair of points of X is t-apart in exactly λ blocks of ℬ, then the (v,k,λ)-MD is called perfect and is denoted by (v,k,λ)-PMD.The existence of a(v,4,1)-PMD is equivalent to the existence of an idempotent quasigroup (Q,·) satisfying the identity, called Stein's third law,
(1)(y·x)·(x·y)=x
for all x,y∈Q. Let ℬ={(x,x·y,y,y·x):x,y∈Q,x≠y}. Then (Q,ℬ) is a (|Q|,4,1)-PMD.For the existence of(v,4,1)-PMD, we have the following theorem from [1–3].Theorem 1.
A(v,4,1)-PMD exists if and only if v≡0,1(mod4) and v≠4,8.In this paper, we are only interested in PMDs whereλ=1. A holey perfect Mendelsohn design (briefly HPMD) is a triple (X,ℋ,ℬ) which satisfies the following properties. (1)
ℋ is a partition of X into subsets called holes.(2)
ℬ is a family of cyclically ordered k-subset of X (called blocks) such that a hole and a block contain at most one common point.(3)
Every ordered pair of points from distinct holes aret-apart in exactly one block for t=1,2,…,k-1.The type of the HPMD is the multiset {|H|:H∈ℋ} and is described by an exponential notation. Throughout this paper, we shall use HPMD(s1n1s2n2⋯stnt) to describe a PMD of the type in which si occurs ni times, 1≤i≤t.In graph theoretic terminology, an HPMD is a decomposition of a complete multipartite directed graph DK(n1,n2,…,nh) into k-circuits such that for any two vertices x and y from different components, there is one circuit along which the directed distance from x to y is t, where 1≤t≤k-1.Another class of designs related to HPMDs isgroup divisible design (GDD). A GDD is a 4-tuple (X,𝒢,ℬ,λ) which satisfies the following properties. (1)
𝒢 is a partition of X into subsets called groups.(2)
ℬ is a family of subsets of X (called blocks) such that a group and a block contain at most one common point.(3)
Every pair of points from distinct groups occurs in exactlyλ blocks.The type of the GDD is the multiset {|G|:G∈𝒢} and we will also use an “exponential” notation for the type of GDD. We also use the notation GDD(K,M;λ) to denote the GDD when its block sizes belong to K and group sizes belong to M. In particular, a GDD({k},{2,u*},1), where there is only one group of size u, is denoted by k-GDD of type 2nu1.Theorem 2 (see [4, 5]).
There exists a4-GDD of type 2nu1 for each n≥6, n≡0(mod3) and u≡2(mod3) with 2≤u≤n-1, except for (n,u)=(6,5) and possibly excepting (n,u)∈{(21,17),(33,23),(33,29),(39,35),(57,44)}.IfM={1}, then the GDD becomes a pairwise balanced design (PBD) [6]. If K={k}, M={n} and the type is nk, then the GDD becomes a transversal design, TD(k,n). The following results are well known (see [7, 8], e.g.).Theorem 3.
(a) There exists a TD(4,m) for any positive integer m,m∉{2,6}.
(b) There exists a TD(5,m) for every positive integer m∉{2,3,6,10}.
(c) There exists a TD(6,m) for m≥5 and m∉{6,10,14,18,22},
(d) There exists a TD(7,m) for m≥7 and m∉{10,14,15,18,20,22,26,30,34,38,46,60}.It is well known that the existence of a TD(k,n) is equivalent to the existence of k-2 mutually orthogonal Latin squares, denoted by (k-2)-MOLS(n). It is easy to see that if we ignore the direction of elements in the blocks, an HPMD becomes a GDD with λ=3. But the converse may be not true. It is proved in [9] that a 4-GDD of type hu and index λ=3 exists if and only if h2u(u-1)≡0(mod4). However, for the existence of HPMDs with block size four (briefly 4-HPMDs), the following results are known ([8, 10–14]).Theorem 4.
(a) A 4-HPMD(hu) exists if and only if h2u(u-1)≡0(mod4) with the exception of types 14, 24, 18 and h4 for odd h.
(b) Foru≥2, a 4-HPMD(1nu1) exists if and only if n(n-2u-1)≡0(mod4) and n≥2u+1, except (n,u)=(5,2) and except possibly (n,u)=(17,2).
(c) A 4-HPMD(2n31) exists if and only if n≥4.
(d) There exist HPMDs of type2nu1 for 4≤n≤8 and 0≤u≤4, except (n,u)=(4,0),(4,4).
(e) For0≤u≤32, a 4-HPMD(4nu1) exists if and only if n≥max(4,⌈u/2⌉+1), except possibly for (n,u)=(12,1), and n=19 and u∈{29,30,31,32}.In this paper, we consider the existence of a 4-HPMD(2nu1) and extend the results in Theorems 4(c) and 4(d). It is fairly well known that the Latin square corresponding to a quasigroup satisfying Stein's third law is a self-orthogonal Latin square (briefly SOLS). So the existence of a 4-HPMD(2nu1) will imply the existence of a holey SOLS of the same type. Accordingly, the necessary condition for the existence of holey SOLS is also a necessary condition for the existence of 4-HPMD(2nu1), which can be stated as follows (see, e.g., [15, 16]).Lemma 5.
If a 4-HPMD(2nu1) exists, then n≥max(4,u+1).The main result of our investigation is the following theorem.Theorem 6.
(a) For1≤u≤16, a 4-HPMD(2nu1) exists if and only if n≥4, n≥u+1, with the possible exception of (n,u)∈{(7,5),(7,6),(11,9),(11,10)}.
(b) Foru≥1, a 4-HPMD(2nu1) exists if n≥⌈5u/4⌉+4. Moreover, if u≥35, then a 4-HPMD(2nu1) exists for all n≥⌈5u/4⌉+1; if u≥95, then a 4-HPMD(2nu1) exists for all n≥⌈5u/4⌉-2.For convenience in what follows, we shall simply refer to a 4-HPMD as an HPMD, where it is to be understood that that blocks are of size four.


## 2. Construction Tools

To construct HPMDs directly, sometimes we usestarter blocks. Suppose the block set ℬ of an HPMD is closed under the action of some Abelian group G, then we are able to list only part of the blocks (starter or base blocks) which determines the structure of the HPMD. We can also attach some infinite points to an Abelian group G. When the group acts on the blocks, the infinite points remain fixed. Formally, let ℬ be the block set of an HPMD over the point set S=G∪X, where (G,+) is a group, X is a set of infinite points, G∩X=∅. The addition (+) is extended over X as follows: g+x=x+g=x for any g∈G and x∈X. A set 𝒜⊂ℬ is called starter blocks of ℬ if 𝒜 is a minimum subset of ℬ satisfying the following property: for any a∈𝒜 and any g∈G, a+g∈ℬ, and for any b∈ℬ, there exist a∈𝒜 and g∈G such that b=a+g, where a+g=(a1+g,a2+g,a3+g,a4+g) when a=(a1,a2,a3,a4). In the following example x1,x2,…, are infinite points.Example 7.
An HPMD(2941)points:Z18∪{xi:1≤i≤4}holes:{{i,i+9}:0≤i≤8}∪{{xi:1≤i≤4}}starter blocks(+1mod18): (x1,0,14,16), (x2,0,17,7), (x3,0,3,1), (x4,0,5,12), (0,1,14,6), (0,4,10,7).In this example, the entire set of 108 blocks are developed from the starter blocks by addinga∈Z18 to each point of the starter blocks. To check the starter blocks, we need only to calculate whether the differences xi-xi+1 from all pairs (xi,xi+1), 0≤i≤3, in each of the starter blocks are precisely G∖S, where S is the set of the differences of the holes. For the above example, the set of differences from the six blocks is exactly Z18∖{0,8}. This is also true for the set of the differences xi-xi+2.The above idea of starter blocks can be generalized: instead of addingg∈G to each point of the starter blocks, we may have to add kg, where k>1, to develop the block set; we refer to this as the +k method. In this case, for a set 𝒜 to be starter blocks, we require that for any a∈𝒜 and any g∈G, a+kg∈ℬ. For quasigroups, we require that for all x,y,z∈Q,x*y=z if and only if (x+kg)*(y+kg)=(z+kg) for any g∈G [17, 18].Example 8.
An HPMD(2651)points:Z12∪{xi:1≤i≤5}holes:{{i,i+6}:0≤i≤5}∪{{xi:1≤i≤5}}starter blocks:(+4mod12): (x1,0,5,3), (x1,1,3,4), (x1,2,0,10), (x1,3,6,1), (x2,0,1,4), (x2,1,8,5), (x2,2,10,11), (x2,3,7,2), (x3,0,2,1), (x3,1,0,11), (x3,2,11,4), (x3,3,1,10), (x4,0,4,11), (x4,1,6,10), (x4,2,5,1), (x4,3,11,8), (x5,0,3,5), (x5,1,5,6), (x5,2,4,0), (x5,3,2,7).By adding4g, where g∈Z12, to the 20 starter blocks, we obtain a set of 60 blocks.Next, we state several recursive constructions of HPMDs, which are commonly used in other block designs [8]. The following construction comes from the weighting construction of GDDs [6].Construction 1 (Weighting).
Suppose(X,ℋ,ℬ) is a GDD with λ=1 and let w:X↦Z+∪{0}. Suppose there exist HPMDs of type {w(x):x∈B} for every B∈ℬ. Then there exists an HPMD of type {∑x∈Hw(x):H∈ℋ}.Lemma 9.
There exists an HPMD(2nu1) for each n≥6, n≡0(mod3) and u≡2(mod3) with 2≤u≤n-1, except for (n,u)=(6,5) and possibly excepting (n,u)∈{(21,17),(33,23),(33,29),(39,35),(57,44)}.Proof.
From Theorem2, there exist 4-GDDs of the same type. So we can give all points of this GDD weight one to get the desired HPMD(2nu1) by Construction 1.Using Theorem3(a), if we give every point of an HPMD weight m and input TD(4,m) to each block of the HPMD, we can obtain the following construction.Construction 2.
Suppose there exists an HPMD of type(h1n1h2n2⋯hknk), then there exists an HPMD((lh1)n1(lh2)n2⋯(lhk)nk), where l≠2,6.The next construction may be called “filling in holes,” which is used commonly in constructing designs.Construction 3.
Suppose there exist an HPMD of type{si:1≤i≤k} and HPMDs of type {hij:1≤j≤ni}∪{a}, where ∑j=1nihij=si and 1≤i≤k-1, then there exists an HPMD of type {hij:1≤j≤ni,1≤i≤k-1}∪{sk+a}.Lemma 10.
If there exists an HPMD(2mk1), there exists an HPMD(23m(2m+k)1).Proof.
By Theorem4(a), there exists an HPMD((2m)4) for any m≥4. We adjoin k points to this HPMD((2m)4) and fill three holes of size 2m with an HPMD(2mk1), leaving one hole of size 2m+k. The result is the desired HPMD(23m(2m+k)1).Lemma 11.
If there exists HPMD(2ms1), then there exists an HPMD(24mt1) for 4s+1≤t≤4s+3.Proof.
Applying Construction2 with l=4 to the HPMD(2ms1), we have an HPMD of type 8m(4s)1. Add k points, 1≤k≤3, to this HPMD and fill an HPMD(24k1), which exists by Theorem 4(d), into the holes of size 8, we have an HPMD(24m(4s+k)1), where 1≤k≤3.Lemma 12.
If an HPMD(2ms1) exists, then an HPMD(25mt1) exists for 5s≤t≤5s+4.Proof.
Applying Construction2 with l=5 to the HPMD(2ms1), we obtain an HPMD of type 10m(5s)1. To this HPMD we adjoin t points, where 0≤t≤4, and fill the holes of size 10 with an HPMD(25t1), which exists by Theorem 4(d), we obtain an HPMD(25m(5s+t)1).Lemma 13.
If there exists a TD(5,m), then there exists an HPMD((2m)4s1), where m≤s≤3m.Proof.
Give weight 2 to each point of first four groups of a TD(5,m). Give weight 1, 2 or 3 to the m points of the fifth group so that the total is s. Since there exist HPMDs of type 24t1, t=1,2,3, from Theorem 4(d), we obtain the desired HPMD by Construction 1.Lemma 14.
If there exists a TD(6,m), then there exist(a)
HPMD((2m)4(2k)1s1), where 0≤k≤m and m≤s≤3m,(b)
HPMD(24m+ks1) for k=0,1,5,6,…,m and m≤s≤3m.Proof.
(a) We will use Construction1: give weight 2 to each point of first four groups of a TD(6,m); give weight 2 to the k points of the fifth group and give weight 1, 2, or 3 to the m points of the sixth group so that the total is s. Since there exist HPMDs of type 2nt1 for n=4,5 and t=1,2,3 from Theorem 4(d), we obtain the HPMD of type (2m)4(2k)1s1.
(b) Take the HPMD((2m)4(2k)1s1) from (a), where m≤s≤3m, we fill the holes of sizes 2m and 2k with an HPMD(2m) and an HPMD(2k), to obtain an HPMD(24m+ks1), where m≤s≤3m.Lemma 15.
If there exist a TD(6,m), an HPMD(2mt1), and an HPMD(2kt1), where 4≤k≤m, then there exists an HPMD(24m+ks1) for m+t≤s≤3m+t.Proof.
Take the HPMD((2m)4(2k)1u1) from Lemma 14(a), where 0≤k≤m and m≤u≤3m, we first adjoin t points to the HPMD((2m)4(2k)1u1) and then fill the holes of sizes 2m and 2k with an HPMD(2mt1) and an HPMD(2kt1), we obtain an HPMD(24m+k(u+t)1) where m+t≤u+t≤3m+t.Lemma 16 (see [8, Lemma 6.3]).
If there exists a TD(7,m), then there exist(a)
HPMD((2m)5(2k)1s1) for 0≤k≤m and 0≤s≤4m,(b)
HPMD(25m+ks1) for k=0,1,5,6,…,m and 0≤s≤4m.Proof.
(a) Give weight 2 to each points of five groups of the TD(7,m), give weight 2 to k points of the sixth group and weight 0 to the remainder points of this group, and give weight t, where 0≤t≤4, to the points of the seventh group such that the sum of these weights is equal to u. As there exists an HPMD(2nt1) for n=5,6 and 0≤t≤4, we obtain an HPMD((2m)5(2k)1u1).
(b) Take the HPMD((2m)5(2k)1u1) from (a), we obtain an HPMD(25m+ku1) by filling HPMDs of types 2m and 2k into the holes of sizes 2m and 2k.Lemma 17.
If there exist a TD(7,m), an HPMD(2mt1), and an HPMD(2kt1), where 4≤k≤m, then there exists HPMD(25m+ks1) for t≤s≤4m+t.Proof.
We adjoint points to the HPMD((2m)5(2k)1u1) from Lemma 16(a), where 0≤u≤4m and fill the holes of sizes 2m and 2k with an HPMD(2mt1) and an HPMD(2kt1), we obtain an HPMD(25m+k(u+t)1), where t≤u+t≤4m+t.Lemma 18.
An HPMD(124t1) exists for 4≤t≤16.Proof.
We start with a TD(5,4). In the first four groups of the TD, we give all the points weight 3. In the last group we give the points a weight of 1, 2, 3, or 4 for a total weight of t. We need HPMDs of type (34k1), where 1≤k≤4. For k=3, the design is given in Theorem 4(a); for k=1,2,4, they are given in Appendix J. The resulting design is an HPMD(124t1) by Construction 1.


## 3. HPMD(2nu1) for Some Specific n

From the results in the previous section, we can obtain the following results.Lemma 19.
There exists an HPMD(2n11) for any n≥4.Proof.
For4≤n≤8, we have Theorem 4(d). For 9≤n≤15 except n=14, please see Appendix A. For n=14,17,18,19, we can obtain the design from an HPMD(2n-491) given in Appendix G, by filling the hole of size 9 with an HPMD(2411). For n=16, we take an HPMD(84) from Theorem 4(a), adjoin one point to this HPMD, and fill each hole of size 8 with an HPMD(2411).
Forn≥20, let n=4m+t, where m≥5 and 0≤t≤3. For t=0,1, we apply Construction 2 with l=4 on an HPMD(2m) (Theorem 4(a)) to get an HPMD(8m). Adjoin one point to this HPMD and fill the holes of size 8 with an HPMD(2411), we obtain an HPMD(24m11). If we adjoin 3 points to the HPMD(8m) and fill m-1 holes of size 8 with an HPMD(2431) and the remaining hole with an HPMD(2511), we obtain an HPMD(24m+111).
Fort=2,3, because an HPMD(2m-131) exists for any m≥5 by Theorem 4(c), we have an HPMD(8m-1121) by Construction 2 with l=4. Adjoin k points, where k=1,3, to this HPMD, and fill the holes of size 8 with an HPMD(24k1), the hole of size 12 with an HPMD(2611) if k=1 and an HPMD(2711) if k=3, we obtain an HPMD(24m+t11), where t=2,3.Combining Theorems4(a) (with h=2) and 4(c), and the above lemma, we have the following.Lemma 20.
An HPMD(2nu1) exists for all n≥4 and 1≤u≤3.Now we show the existence of some HPMD(2nu1) for n∈{17,18,19,21,22,23,26,27,29,31,37}.Lemma 21.
An HPMD(217u1) exists for 1≤u≤16.Proof.
For1≤u≤3, we apply Lemma 20. For 4≤u≤8 please see Appendices B–F. For 9≤u≤11, we first get an HPMD(84101) by applying Lemma 13 with m=4 and s=10. Adjoin k points, where 1≤k≤3, to this HPMD, and fill three holes of size 8 with an HPMD(24k1) and the hole of size 10 with an HPMD(25k1), we obtain an HPMD(212+5(8+k)1) for 1≤k≤3. For 12≤u≤16, please see Appendix I, except u=14, which is given in [8].Lemma 22.
An HPMD(218u1) exists for 1≤u≤17.Proof.
For1≤u≤3, we apply Lemma 20. For u=4,6,7, please see Appendices B, D, and E. For u=5,8, we apply Lemma 9.
For9≤u≤11, we first get an HPMD(84121) by applying Lemma 13 with m=4,s=12. Adjoin k points, where 1≤k≤3, to this HPMD, and fill three holes of size 8 with an HPMD(24k1) and the hole of size 12 with an HPMD(26k1), we obtain an HPMD(212+6(8+k)1) for 1≤k≤3.
For12≤u≤17, we obtain an HPMD(2nu1) by Lemma 10 with m=6, because an HPMD(26k1) exists for 0≤k≤4 by Theorem 4(d) and an HPMD(2651) is given in Example 8.Lemma 23.
An HPMD(219u1) exists for 1≤u≤16.Proof.
For1≤u≤3, we apply Lemma 20. For 4≤u≤9, please see Appendices B–G. For 11≤u≤13, we first get an HPMD(10481) by applying Lemma 13 with m=5, s=8. Adjoin k points, where 1≤k≤3, to the HPMD, and fill three holes of size 10 with an HPMD(25k1) and the hole of size 8 with an HPMD(24k1), we obtain an HPMD(219(10+k)1) for 1≤k≤3. For u=10 or 14≤u≤16, please see Appendix I.Lemma 24.
An HPMD(221u1) exists for 1≤u≤20.Proof.
For1≤u≤3, we apply Lemma 20. For u=4, we first obtain an HPMD(84121) from HPMD(2431) by Construction 2 with l=4. Add two points to this HPMD and fill the holes of size 8 with an HPMD(2421) and the hole of 12 with an HPMD(2541), we obtain an HPMD(22141).
For5≤u≤15, from Lemma 14(b) with m=5, k=1, we have HPMD(2nu1). For 16≤u≤18, we apply Lemma 10 with m=7 and k=2,3,4. For u=19, please see Appendix I. For u=20, we apply Lemma 9.Lemma 25.
An HPMD(222u1) exists for 1≤u≤16.Proof.
For1≤u≤3, we apply Lemma 20. For u=4, we take the HPMD(217141) from Lemma 21 and fill the hole of size 17 with an HPMD(2541). For 5≤u≤8, please see Appendices C–F.
Foru=9, we generate an HPMD(85121) from an HPMD(2531) (Theorem 4(c)) by Construction 2 with l=4. To this HPMD, we adjoin one point, fill four holes of size 8 by an HPMD(2411) and one hole of size 12 by an HPMD(2611), we obtain an HPMD(222(8+1)1).
For10≤u≤14, we first get an HPMD(104141) by applying Lemma 13 with m=5,s=14. Adjoin k points, where 0≤k≤4, to this HPMD, and fill three holes of size 10 with an HPMD(25k1) and the hole of size 14 with an HPMD(27k1), we obtain an HPMD(222(10+k)1) for 0≤k≤4.
Foru=15, we take an HPMD(12481) from Lemma 18. Adjoin three points to this HPMD and fill three holes of size 12 with an HPMD(2631) and one hole of size 8 with an HPMD(2431), we obtain an HPMD(222(12+3)1).
Finally foru=16, please see Appendix I.Lemma 26.
An HPMD(223u1) exists for 1≤u≤17.Proof.
For1≤u≤3, we apply Lemma 20. For u=4, we add 2 points to an HPMD(124) and fill in three holes with an HPMD(2621) and one hole with an HPMD(2541), to obtain an HPMD(22341). For 5≤u≤8, please see Appendices C–F.
For9≤u≤11, we take the HPMD(85141) from Appendix J, adjoin k points, 1≤k≤3, to the HPMD, and fill four holes of size 8 with an HPMD(24k1) and one hole of size 14 with an HPMD(27k1), we obtain an HPMD(223(8+k)1).
For12≤u≤16, we take an HPMD(124101) from Lemma 18. Adjoin k points, where 0≤k≤4, to this HPMD, and fill three holes of size 12 with an HPMD(26k1) and the hole of size 10 with an HPMD(25k1) (Theorem 4(d)), we obtain an HPMD(223(12+k)1) for 0≤k≤4.
Foru=17, please see Appendix I.Lemma 27.
An HPMD(226u1) exists for 0≤u≤18.Proof.
For0≤u≤14, we first apply Lemma 14(a) with m=5 and s=12 to get an HPMD(104(2k)1121), where 0≤k≤5. Adjoin t points, where 0≤t≤4, to this HPMD, and fill the holes of sizes 10 and 12 with an HPMD(25t1) and an HPMD(26t1), respectively. The result is an HPMD(226(2k+t)1), where 0≤2k+t≤14.
For14≤u≤18, we first get an HPMD(144101) by applying Lemma 13 with m=7, s=10. Adjoin k points, where 0≤k≤4, to this HPMD, and fill three holes of size 14 with an HPMD(27k1) and the hole of size 10 with an HPMD(25k1), we obtain an HPMD(226(14+k)1) for 0≤k≤4.Lemma 28.
An HPMD(227u1) exists for 0≤u≤26.Proof.
For0≤u≤14, we first apply Lemma 14(a) with m=5 and s=14 to get an HPMD(104(2k)1141), where 0≤k≤5, then adjoin t points, where 0≤t≤4, to this HPMD, and fill the holes of sizes 10 and 14 with an HPMD(25t1) and an HPMD(27t1), respectively. The result is an HPMD(227(2k+t)1), where 0≤2k+t≤14.
For14≤u≤18, we first get an HPMD(144121) by applying Lemma 13 with m=7, s=12. Adjoin k points, where 0≤k≤4, to this HPMD, and fill three holes of size 14 with an HPMD(27k1) and the hole of size 12 with an HPMD(26k1), we obtain an HPMD(227(14+k)1) for 0≤k≤4.
For18≤u≤26, we start with an HPMD(184), adjoin k points to this HPMD, and fill in the first three holes of size 18, where 0≤k≤8, with an HPMD(29k1). The resulting design is an HPMD of type 227(18+k)1, where 18≤18+k≤26, and this completes the proof of the lemma.Lemma 29.
An HPMD(229u1) exists for 1≤u≤21.Proof.
Foru=1,2,3, we apply Lemma 20. For u=4, we take an HPMD(124141) from Lemma 18 and fill the holes of sizes 12 and 14 with an HPMD(26) and an HPMD(2541), respectively. For u=5, we take an HPMD(223171) from Lemma 26 and fill the hole of size 17 with an HPMD(2651). For u=6, please see Appendix D. For 7≤u≤21, we can get the designs from Lemma 14(b) with m=7 and k=1.Lemma 30.
An HPMD(231u1) exists for 1≤u≤21.Proof.
For1≤u≤5, we can get an HPMD(225(12+u)1) from Lemma 12 with n=5, s=2 and k=2,3,4, and s=3 and k=1,2. Fill the hole of size (12+u) with an HPMD(26u1), we have an HPMD(231u1).
For6≤u≤18, we form a {6,7}-GDD of type 67 by deleting one block from a TD(7,7). In the first five groups of this GDD, we give all of the points weight 2. In the fifth group, we give one point of weight 2 and the other points weight 0. In the last group, we give the points a weight of 1, 2, or 3 for a total weight of u where 6≤u≤18. Since there are HPMDs of types 2n for n=5,6,7 and 2nk1 for n=4,5,6 and k=1,2,3 by Theorem 4(c), we get an HPMD of type 12521u1 for 6≤u≤18. To this HPMD, we fill the holes of size 12 with an HPMD(26) and obtain an HPMD(231u1) for 6≤u≤18.
For7≤u≤21, we use a TD(8,7): in the first four groups of the TD(8,7), we give all of the points a weight of two. In the fifth, sixth, and seventh groups, we give one point weight two and the other points weight zero. In the last group, we give the points a weight of 1, 2, or 3, for a total weight of u. Since we have HPMDs of types 2nk1 for n=4,5,6,7 and k=1,2,3, we get an HPMD of type 14423u1 for 7≤u≤21. By filling in the holes of size 14 with an HPMD(27), the resulting design is an HPMD(231u1) for 7≤u≤21.Lemma 31.
An HPMD(237u1) exists for 1≤u≤28.Proof.
We will use a TD(8,7): in the first five groups of the TD(8,7), we give all of the points a weight of two. In the sixth and seventh groups, we give one point weight two and the other points weight zero. In the last group, we give the points a weight of 0, 1, 2, 3, or 4, for a total weight of u. Since we have HPMDs of types 2nk1 for n=5,6,7 and 0≤k≤4, we get an HPMD of type 14522u1 for 0≤u≤28. By filling in the holes of size 14 with an HPMD(27), the resulting design is an HPMD(237u1) for 1≤u≤28.


## 4. HPMD(2nu1) for 1≤u≤16

Lemma 32.
An HPMD(2nu1) exists for 1≤u≤16 and u+1≤n≤25, except possibly (n,u)∈{(7,5),(7,6),(11,9),(11,10)}.Proof.
For1≤u≤3, we apply Lemma 20.
For4≤u≤16, let us consider u≤n≤15 first. For 5≤n≤8 and u=4, an HPMD(2nu1) exists by Theorem 4(d). For n=9,12,15 and u=5,8,11,14, we apply Lemma 9 when u<n. For n=12 and 9≤u≤11, we obtain an HPMD(2nu1) by Lemma 10 with m=4, because an HPMD(24k1) exists for k=1,2,3. For n=15 and 10≤u≤14, we obtain an HPMD(2nu1) by Lemma 10 with m=5, because an HPMD(25k1) exists for k=0,1,2,3,4. Besides an HPMD(2651) in Example 8 and an HPMD(2941) in Example 7, an HPMD(2n111) for n=13,14 can be found in [8]. The other designs for u≤n≤15 are given in Appendices B–H, except (n,u)∈{(7,5),(7,6),(11,9),(11,10)}.
Now let us consider4≤u≤16 and 16≤n≤25. For n=16,24, 4≤u≤15, and u≠4,8,12, by Lemma 11, we have an HPMD(2nu1). For n=16 and u=4,8,12, let t=u-2, we obtain first an HPMD(84t1) by Lemma 13 with m=4 and s=t when t≥4; for t=2, we have an HPMD(84t1) in Appendix J. To the HPMD(84t1), we adjoin 2 points and fill the holes of size 8 with an HPMD(2421), to obtain an HPMD(216u1) for u=4,8,12. For n=24 and u=4, we adjoin 4 points to an HPMD(124) and fill the holes of size 12 with an HPMD(2641). For n=24 and u=8,12,16, we get them from Lemma 15 with m=5,k=4 and 1≤t≤3. The cases of n=17,18,19,21,22,23 are covered by Lemmas 21, 22, 23, 24, 25, and 26, respectively. For n=20,25 and 4≤u≤19, we can get an HPMD(2nu1) from Lemma 12 with m=4,5, 1≤s≤3 and t=u.Lemma 33.
An HPMD(2nu1) exists for 1≤u≤18 and 26≤n≤32.Proof.
Forn=26,27,29, and 31, we have Lemmas 27, 28, 29, and 30 to cover these cases, respectively.
Forn=28,32 and u≠8,12,16, the designs are provided by Lemma 11 with m=7,8. For n=28,32 and u=8,12,16, we get these designs from Lemma 14(b) with m=7,8 and k=0.
Forn=30, we apply Lemma 12 with m=6, 1≤s≤4, and t=u.Lemma 34.
An HPMD(2nu1) exists for 1≤u≤24 and 33≤n≤40.Proof.
Forn=33,34 and 1≤u≤6, we obtain at first an HPMD(225t1) by Lemma 12 with m=5, s=4, and t=u+16, u+18. Fill an HPMD(28u1) and an HPMD(29u1) into the holes of sizes u+16 and u+18, we obtain an HPMD(233u1) and an HPMD(234u1), respectively. For n=33,34 and 7≤u≤24, an HPMD(2nu1) exists by Lemma 15 with m=7, k=5,6, 1≤t≤3.
Forn=35,36,40, the designs come from Lemma 16(b) with m=7,k=0,1,5. For n=37, the designs are provided by Lemma 31.
Forn=38 and 1≤u≤7, we first apply Lemma 12 with m=6, s=4, and t=u+16, to get an HPMD(230(u+16)1). Fill the hole of size u+16 by an HPMD(28u1), we obtain an HPMD(238u1). For n=38 and 8≤u≤24, we have an HPMD(2nu1) by Lemma 14(b) with m=8 and k=6. Finally for n=39, we apply Lemma 17 with m=7, k=4, 1≤t≤3.Lemma 35.
An HPMD(2nu1) exists for 1≤u≤30 and 41≤n≤49.Proof.
Forn=41,42,44 and 1≤u≤31, an HPMD(2nu1) exists by Lemma 17 with m=7 and k=6,7, and m=8 and k=4, and 1≤t≤3.
Forn=43 and 1≤u≤7, there exists an HPMD(235(u+16)1) by Lemma 12 with m=7, 0≤s≤6, and t=u+16. Fill an HPMD(28u1) into the hole of size u+16, we obtain an HPMD(243u1). For n=43 and u=8, because we have an HPMD(2871), by Construction 2 with l=4, we have an HPMD(88281). Add two points to this design and fill an HPMD(2421) into the holes of size 8 and an HPMD(21181) into the hole of size 28, we obtain an HPMD(24381). For n=43 and u=9, an HPMD(2nu1) exists by Lemma 14(b) with m=9 and k=7. For n=43 and 10≤u≤30, an HPMD(2nu1) exists by Lemma 15 with m=9, k=7, and 1≤k≤3.
Forn=45,46,47,48 and 1≤u≤35, the designs come from Lemma 17 with m=8, k=5,6,7,8 and 1≤t≤3.
Forn=49 and 0≤u≤32, because an HPMD(27t1) exists for 0≤t≤4, we get an HPMD(147(7t)1) from Construction 2 with l=7. Add k points to this design, 0≤k≤4, and fill an HPMD(27k1) into the holes of size 14, we obtain an HPMD(249(7t+k)1) for 0≤7t+k≤32.Lemma 36.
An HPMD(2nu1) exists for 1≤u≤39 and 50≤n≤66.Proof.
For50≤n≤54 and 1≤u≤39, we apply Lemma 17 with m=9, 5≤k≤9 and 1≤t≤3. For n=55,56 and 1≤u≤44, we apply Lemma 16(b) with m=11 and k=0,1.
Forn=57,58 and 1≤u≤11, by Lemma 16(b) with m=9 and k=0,1, there exist HPMD(2s(u+24)1) for s=45,46 and 1≤u≤11. Fill in the hole of size u+24 with an HPMD(212u1), we obtain an HPMD(2s+12u1) for s=45,46. For n=57,58 and 12≤u≤39, an HPMD(2nu1) exists from Lemma 15 with m=12 and k=9,10.
For59≤n≤66 and 1≤u≤47, an HPMD(2nu1) exists by Lemma 17 with m=11, 4≤k≤11, and 1≤t≤3.Lemma 37.
An HPMD(2nu1) exists for 1≤u≤20 and n∈{21,25,29,33,37,45,59}.Proof.
The cases ofn=21,29,37 are covered by Lemmas 24, 29, and 31, respectively. The cases of n=33,45,59 are covered by Lemmas 34, 35, and 36, respectively. For n=25, we apply Lemma 12 with m=5 and 1≤s≤4 because HPMDs of type 25s1 exist for all 1≤s≤4.Lemma 38.
An HPMD(2nu1) exists for 1≤u≤51 and 67≤n≤87.Proof.
For67≤n≤78 and 1≤u≤51, an HPMD(2nu1) exists by by Lemma 17 with m=12 and 7≤k≤12, and m=13 and 8≤k≤13, and 1≤t≤3.
Forn∈{79,82,83} and 1≤u≤15, by Lemma 17 with m=11 and k=8, and m=12 and k=6,7, and 1≤t≤3. there exist HPMD(2s(u+32)1) for s=63,66,67. Fill in the hole of size u+32 with HPMD(216u1) in HPMD(2s(u+32)1), we obtain an HPMD(2nu1) for n∈{79,82,83}. For n=79 and 16≤u≤67, we apply Lemma 15 with m=16 and k=15, and 1≤k≤3. For n=82,83 and u=16, we apply Lemma 14(a) with m=18, k=8 and s=2t, where t=10,11, to obtain an HPMD(364161(2t)1). Fill the holes of sizes 36 and 2t with an HPMD of types 218, 2t, respectively, we obtain an HPMD(272+t161) for t=10,11. For n=82,83 and 17≤u≤54, we apply Lemma 15 with m=17, k=14,15, 1≤t≤3.
For80≤n≤81 and 1≤u≤64, we apply Lemma 16(b) with m=16 and k=0,1. Finally for 84≤n≤87 and 1≤u≤67, we apply Lemma 17 with m=16, 4≤k≤7, and 1≤t≤3.The required HPMDs of type2kt1 for the application of Lemmas 15 and 17 in the above proof as well as in the proofs of the next two lemmas come from either Lemma 32 or Lemma 37.Lemma 39.
An HPMD(2nu1) exists for 88≤n≤116 and 1≤u≤⌊4n/5⌋.Proof.
Letμ(n)=⌊4n/5⌋.
For88≤n≤92, μ(92)=73, let n=5s+k, where s=16 and 8≤k≤12. Because an TD(7,16) exists, using Lemma 17 with m=16, 8≤k≤12, 1≤t≤k-3, we obtain an HPMD(2nu1) for 1≤u≤k+61 and 8≤k≤12.
For93≤n≤102, μ(102)=81, let n=5s+k, where s=17 and 8≤k≤17. using Lemma 17 with m=17, 8≤k≤17, 1≤t≤k-3, we obtain an HPMD(2nu1) for 1≤u≤k+65 and 8≤k≤17.
For103≤n≤114, μ(114)=91, let n=5s+k, where s=19 and 8≤k≤19. using Lemma 17 with m=19, 8≤k≤19, 1≤t≤k-3, we obtain an HPMD(2nu1) for 1≤u≤k+73 and 8≤k≤19.
For115≤n≤116, μ(116)=92, we apply Lemma 16(b) with m=23 and k=0,1 to obtain an HPMD(2nu1) for 1≤u≤92.Lemma 40.
An HPMD(2nu1) exists for n≥117 and 1≤u≤⌊4n/5⌋+2.Proof.
Letn=5s+j, where 12≤j≤16. Since n≥117, we have s≥21. If there exists a TD(7,s), then using Lemma 17 with m=s, k=j, 1≤t≤k-1, we obtain an HPMD(2nu1) for 1≤u≤4s+k-1. Because k=j=n-5s and s≥(n-16)/5, we have u≤⌊4n/5⌋+2.
Fors∈M7={22,26,30,34,38,46,60}, we do not have a TD(7,s). However, since a TD(7,s-1) exists, we may use Lemma 17 with m=s-1,17≤k≤21, 1≤t≤k-1, where k=j+5, to obtain an HPMD(2nu1) for 1≤u≤4(s-1)+k-1=4s+j. Because j=n-5s and s≥(n-21)/5, we have u≤⌊4n/5⌋+3. The required HPMDs of type 2kt1 in the above proof come from Lemma 37.As a summary of Lemma5, Theorem 4(c), and Lemmas 19, 32–40, we have the following result.Theorem 41.
For1≤u≤16, an HPMD(2nu1) exists if and only if n≥4 and n≥u+1, except possibly (n,u)∈{(7,5),(7,6),(11,9),(11,10)}.


## 5. HPMD(2nu1) for General u

In this section, we will provide a general result regarding the existence of HPMD(2nu1). That is, we will show the existence of HPMD(2nu1) for any u and all n≥⌈5u/4⌉+4. Let us start with a lemma.Lemma 42.
An HPMD(279u1) exists for 1≤u≤62.Proof.
Foru≤16, the designs are provided by Theorem 41. For 17≤u≤62, we obtain first an HPMD(324301t1) from Lemma 14(a) with m=16, k=15, and s=t, where 17≤t≤48. Adjoin k points to this HPMD, where 0≤k≤14, and fill the holes of sizes 32 and 30 with HPMDs of types 216k1, 215k1, respectively, we obtain an HPMD(279(t+k)1) for 16≤t+k≤62.In the proofs of the remaining lemmas in this section, the required HPMDs of type2kt1 for the application of Lemmas 15 and 17 come from Theorem 41.Lemma 43.
There exists an HPMD(2nu1) for all u≥1 and ⌈5u/4⌉+4≤n≤44.Proof.
For1≤u≤16, Theorem 41 applies. Now we assume u≥17, it must be the case that n≥26 because n≥⌈5u/4⌉+4. For the same reason, we have u≤⌊4n/5⌋-3. Table 1 shows the existence of an HPMD(2nu1) for 26≤n≤44 and 17≤u≤⌊4n/5⌋-3.Table 1
Existence proof of HPMD(2nu1) for Lemma 43.
n
u
Justification
26
17-18
Lemma27
27
17–26
Lemma28
28, 29
17–21
Lemma14(b) with m=7 and k=0,1
30
17–21
Lemma12 with m=6, s=3,4, and t=17-21
31
17–21
Lemma30
32, 33
17–24
Lemma14(b) with m=8, k=0,1
34
17–26
Lemma15 with m=7, k=6, and 1≤t≤5
35, 36
17–28
Lemma16(b) with m=7, k=0,1
37, 38
17–28
Lemma15 with m=8, k=5,6, and 1≤t≤k-1
39–41
17–31
Lemma17 with m=7, k=4,5,6, and 1≤t≤k-1
42, 44
17–32
Lemma15 with m=9, k=6,8, and 1≤t≤k-1
43
17–31
Lemma15 with m=9, k=7, and 1≤t≤k-3Lemma 44.
An HPMD(2nu1) exists for 45≤n≤87 and 1≤u≤⌊4n/5⌋-1.Proof.
For1≤u≤16, Theorem 41 applies. Let μ(n)=⌊4n/5⌋-1.
For45≤n≤48, μ(48)=37, we apply Lemma 17 with m=8, 5≤k≤8, and 1≤t≤k-3 to obtain an HPMD(2k+40u1) where 1≤u≤k+29 and 5≤k≤8.
For49≤n≤54, μ(54)=42 and we use Lemma 17 with m=9, 4≤k≤9, and 1≤t≤k-3 to obtain an HPMD(2k+45u1) where 1≤u≤k+33 and 4≤k≤9.
For55≤n≤56, μ(56)=43 and we apply Lemma 16(b) with m=11 and k=0,1 to obtain an HPMD(2nu1) where 0≤u≤44.
Forn=57,58, μ(58)=45 and we apply Lemma 15 with m=12, k=9,10, and 0≤t≤k-1, to obtain an HPMD(248+ku1), where k=9,10 and 12≤u≤35+k.
For59≤n≤66, μ(66)=51 and an HPMD(2nu1) exists by Lemma 17 with m=11, 4≤k≤11 and 1≤t≤k-3. to obtain an HPMD(2k+55u1) where 4≤k≤11 and 1≤u≤k+41.
For67≤n≤72, μ(72)=56 and an HPMD(2nu1) exists by Lemma 17 with m=12, 7≤k≤12 and 1≤t≤k-3, to obtain an HPMD(2k+60u1) where 7≤k≤12 and 1≤u≤k+45.
For73≤n≤78, μ(78)=61 and an HPMD(2nu1) exists by Lemma 17 with m=13, 8≤k≤13 and 1≤t≤k-3, to obtain an HPMD(2k+65u1) where 8≤k≤13 and 1≤u≤k+49.
Forn=79, the case is covered by Lemma 42. For n=80,81, μ(81)=63, we apply Lemma 16(b) with m=16 and k=0,1, to obtain an HPMD(2nu1) where 0≤u≤64.
Forn=82,83, μ(83)=65 and we apply Lemma 15 with m=17, k=14,15, 1≤t≤k-1, to obtain an HPMD(268+ku1) where k=14,15 and 17≤u≤k+50.
For84≤n≤87, μ(87)=68 and we apply Lemma 17 with m=16, 4≤k≤7, 1≤t≤k-3, to obtain an HPMD(2k+80u1) where 4≤k≤7, 1≤u≤k+61.Theorem 45.
There exists an HPMD(2nu1) for u≥1 and n≥⌈5u/4⌉+4.Proof.
For1≤u≤16, Theorem 41 applies. Now assume that u≥17, it must be the case that n≥26 because n≥⌈5u/4⌉+4. For 26≤n≤44, the theorem holds by Lemma 43. For the case of n≥45, the theorem holds by Lemmas 44, 39, and 40, because u≤⌊4n/5⌋-3 implies n≥⌈5u/4⌉+4.Actually, Lemmas44, 39, and 40 can be used to prove a stronger result when u≥35.Theorem 46.
There exists an HPMD(2nu1) if u≥35 and n≥⌈5u/4⌉+1 or u≥95 and n≥⌈5u/4⌉-2.Proof.
Whenu≥35, n≥⌈5u/4⌉+1≥45, so Lemmas 44, 39, and 40 apply. From u≤⌊4n/5⌋-1, we obtain n≥⌈5u/4⌉+1. When u≥95, n≥⌈5u/4⌉-2≥117, so Lemma 40 applies. From u≤⌊4n/5⌋+2, we obtain n≥⌈5u/4⌉-2.


## 6. Conclusions

We have investigated the existence of HPMD(2nu1) for 1≤u≤16. We also provided a general result for all u≥1 and n≥⌈5u/4⌉+4. Most recursive constructions used in this paper are standard in combinatorial designs and many of the direct constructions of HPMDs in this paper are carried out by computer. From the previous sections, we obtain the main theorem of this paper while the existence problem of HPMD(2nu1) for 17≤u≤94 and u+1≤n≤⌈5u/4⌉+3, and u≥95 and u+1≤n≤⌈5u/4⌉-3 remains open. The main result of this paper can be summarized in the following theorem.Theorem 47.
(a) For1≤u≤16, an HPMD(2nu1) exists if and only if n≥4 and n≥u+1, with the possible exceptions of (n,u)∈{(7,5),(7,6),(11,9),(11,10)}.
(b) Foru≥1, an HPMD(2nu1) exists if n≥⌈5u/4⌉+4. Moreover, if u≥35, then there exists an HPMD(2nu1) for n≥⌈5u/4⌉+1; if u≥95, then there exists an HPMD(2nu1) for n≥⌈5u/4⌉-2.Proof.
(a) is a restatement of Theorem41; (b) is a combination of Theorems 45 and 46.



---

*Source: 672731-2013-02-06.xml*