Nested resolvable designs and associated uniform designs: the 2013 paper, reproduced and generalised

This vignette reproduces, with the current version of PGM2, all the worked examples and both parameter tables of the paper that the package implements (Boudraa, Gheribi-Aoulmi, and Laib 2013):

The paper states its theory for a projective geometry \(PG(m, p)\) over a Galois field \(GF(p)\) of any prime order \(p\), but versions \(\le\) 1.2 of the package implemented only \(p = 2\). Version 2.0 implements the general prime case, so both Table 1 (\(p = 2\)) and Table 2 (\(p = 3\)) of the paper can now be regenerated by the package — as done at the end of this vignette.

The construction in brief

A balanced incomplete block design (\(BIB\)) with parameters \((v, b, r, k, \lambda)\) arranges \(v\) treatments into \(b\) blocks of size \(k < v\) so that every treatment occurs in \(r\) blocks and every pair of treatments concurs in \(\lambda\) blocks. The method of the paper identifies treatments with the points of \(PG(m, p)\) and blocks with its hyperplanes (Dugué 1958), and then recurses:

Stage 1 — the hyperplanes of \(PG(m,p)\) form a symmetric \(BIB\) of the first generation (BIB).
Next generations — deleting a block (a sub-variety \(V(i_1)\)) and intersecting it with the remaining blocks yields the \(BIB\) of \(PG(m-1, p)\), the second generation (Gen), and so on recursively.
Resolvable designs — deleting a block together with its treatments leaves a resolvable \(BIB\) (Resolvable): its blocks partition into \(r\) parallel classes of \(p\) blocks each (this is the design of the affine geometry \(AG(m,p)\) (Bose 1942)).
Uniform designs — each resolvable design is converted into a symmetric uniform design \(U(p^m, p^{r})\) by the correspondence of Fang, Lu, et al. (2004; see also Fang, Ge, et al. 2004): parallel classes become factors and block membership within a class gives the level (Uniform).

The driver Steps runs the whole recursion and returns the designs of all stages.

Example 1 of the paper: \(PG(3,2)\)

Step 1 gives the first-generation \(BIB\) with parameters \(v_1 = b_1 = 15\), \(r_1 = k_1 = 7\), \(\lambda_1 = 3\); step 2 gives second-generation designs with parameters \((7, 3, 1)\):

X <- BIB(3)
c(V = X$V, B = X$B, R = X$R, K = X$K, Lambda = X$Lambda)
#>      V      B      R      K Lambda 
#>     15     15      7      7      3

X2 <- Gen(1, X$BIB)
c(V = X2$V, B = X2$B, R = X2$R, K = X2$K)
#> V B R K 
#> 7 7 3 3

Example 2 of the paper: the chain \(BIB \to RBIB \to UD\)

The paper’s Example 2 (its pages 174–175) builds, from \(PG(3,2)\), the \(BIB(15, 7, 3)\), extracts the \(RBIB(8, 14, 7, 4, 3)\) and converts it into the uniform design \(U(8, 2^7)\):

bib <- BIB(3)$BIB
bib
#>       [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#>  [1,]    2    4    6    8   10   12   14
#>  [2,]    1    4    5    8    9   12   13
#>  [3,]    3    4    7    8   11   12   15
#>  [4,]    1    2    3    8    9   10   11
#>  [5,]    2    5    7    8   10   13   15
#>  [6,]    1    6    7    8    9   14   15
#>  [7,]    3    5    6    8   11   13   14
#>  [8,]    1    2    3    4    5    6    7
#>  [9,]    2    4    6    9   11   13   15
#> [10,]    1    4    5   10   11   14   15
#> [11,]    3    4    7    9   10   13   14
#> [12,]    1    2    3   12   13   14   15
#> [13,]    2    5    7    9   11   12   14
#> [14,]    1    6    7   10   11   12   13
#> [15,]    3    5    6    9   10   12   15

resolvable <- Resolvable(1, bib)
resolvable$RBIB
#>       [,1] [,2] [,3] [,4]
#>  [1,]    1    5    9   13
#>  [2,]    3    7   11   15
#>  [3,]    1    3    9   11
#>  [4,]    5    7   13   15
#>  [5,]    1    7    9   15
#>  [6,]    3    5   11   13
#>  [7,]    1    3    5    7
#>  [8,]    9   11   13   15
#>  [9,]    1    5   11   15
#> [10,]    3    7    9   13
#> [11,]    1    3   13   15
#> [12,]    5    7    9   11
#> [13,]    1    7   11   13
#> [14,]    3    5    9   15

Uniform(resolvable$RBIB)$UD
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#> [1,]    1    1    1    1    1    1    1
#> [2,]    2    1    2    1    2    1    2
#> [3,]    1    2    2    1    1    2    2
#> [4,]    2    2    1    1    2    2    1
#> [5,]    1    1    1    2    2    2    2
#> [6,]    2    1    2    2    1    2    1
#> [7,]    1    2    2    2    2    1    1
#> [8,]    2    2    1    2    1    1    2

The matrices above coincide (up to the point numbering, which version 2.0 keeps identical to versions \(\le\) 1.2 for \(p = 2\)) with the listings printed in the paper.

Example 3 of the paper: a more economic resolvable design

The paper’s Example 3 unites the second-generation designs of \(PG(3,2)\) obtained by deleting each block in turn, removes the treatments of a chosen first-generation block, and converts the result — an \(RBIB(8, 28, 7, 2, 1)\) — into the uniform design \(U(8, (2^2)^7)\) with four-level factors:

bib <- BIB(3)$BIB
mat <- NULL
for (i in 1:15) mat[[i]] <- Gen(i, bib)$BIB2
x <- Reduce("rbind", mat)
e <- dim(x)[1]; b <- dim(x)[2]
v <- bib[1, ]
for (i in 1:e) for (j in 1:b) if (any(x[i, j] == v)) x[i, j] <- 0
for (i in e:1) if (all(x[i, ] == 0)) x <- x[-i, ]
s <- x[1, ]; s <- s[s > 0]
x1 <- matrix(nrow = dim(x)[1], ncol = length(s))
for (i in 1:dim(x)[1]) x1[i, ] <- x[i, ][x[i, ] > 0]
A <- unique(x1)
A
#>       [,1] [,2]
#>  [1,]    1    9
#>  [2,]    5   13
#>  [3,]    1    5
#>  [4,]    9   13
#>  [5,]    1   13
#>  [6,]    5    9
#>  [7,]    3   11
#>  [8,]    7   15
#>  [9,]    3    7
#> [10,]   11   15
#> [11,]    3   15
#> [12,]    7   11
#> [13,]    1    3
#> [14,]    9   11
#> [15,]    1   11
#> [16,]    3    9
#> [17,]    5    7
#> [18,]   13   15
#> [19,]    5   15
#> [20,]    7   13
#> [21,]    1    7
#> [22,]    9   15
#> [23,]    1   15
#> [24,]    7    9
#> [25,]    3    5
#> [26,]   11   13
#> [27,]    5   11
#> [28,]    3   13

ud <- Uniform(A)
ud$UD
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#> [1,]    1    1    1    1    1    1    1
#> [2,]    3    3    3    1    2    3    4
#> [3,]    2    1    2    3    3    3    3
#> [4,]    4    3    4    3    4    1    2
#> [5,]    1    2    2    2    2    2    2
#> [6,]    3    4    4    2    1    4    3
#> [7,]    2    2    1    4    4    4    4
#> [8,]    4    4    3    4    3    2    1

All stages at once: `Steps`

s <- Steps(4, 1)
names(s)
#> [1] "BIB1"        "BIBg"        "Resolvables" "UDs"
sapply(s$UDs, function(u) c(runs = u$n, factors = u$F))
#>         [,1] [,2] [,3]
#> runs      16    8    4
#> factors   15    7    3

Reproducing Table 1 (\(p = 2\)) and Table 2 (\(p = 3\)) of the paper

The helper below extracts, for each geometry \(PG(m,p)\), the parameters of the first-generation \(BIB\), of the \(RBIB\) and of the associated uniform design — the first three rows of each table of the paper:

table_rows <- function(p, ms) {
  out <- NULL
  for (m in ms) {
    X <- BIB(m, p)
    Y <- Resolvable(1, X$BIB)
    U <- Uniform(Y$RBIB)
    out <- rbind(out, data.frame(
      geometry = sprintf("PG(%d,%d)", m, p),
      BIB = sprintf("(%d, %d, %d)", X$V, X$K, X$Lambda),
      RBIB = sprintf("(%d, %d, %d, %d, %d)", Y$V, Y$B, Y$R, Y$K, X$Lambda),
      UD = sprintf("U(%d, %d^%d)", U$n, p, U$F)))
  }
  out
}

knitr::kable(table_rows(2, 2:4), caption = "Paper, Table 1 (p = 2)")

Paper, Table 1 (p = 2)
geometry	BIB	RBIB	UD
PG(2,2)	(7, 3, 1)	(4, 6, 3, 2, 1)	U(4, 2^3)
PG(3,2)	(15, 7, 3)	(8, 14, 7, 4, 3)	U(8, 2^7)
PG(4,2)	(31, 15, 7)	(16, 30, 15, 8, 7)	U(16, 2^15)

knitr::kable(table_rows(3, 2:4), caption = "Paper, Table 2 (p = 3)")

Paper, Table 2 (p = 3)
geometry	BIB	RBIB	UD
PG(2,3)	(13, 4, 1)	(9, 12, 4, 3, 1)	U(9, 3^4)
PG(3,3)	(40, 13, 4)	(27, 39, 13, 9, 4)	U(27, 3^13)
PG(4,3)	(121, 40, 13)	(81, 120, 40, 27, 13)	U(81, 3^40)

Both agree with the published tables: for \(p=2\) the designs \(BIB(7,3,1)\), \(BIB(15,7,3)\), \(BIB(31,15,7)\) with resolvable designs \((4,6,3,2,1)\), \((8,14,7,4,3)\), \((16,30,15,8,7)\); for \(p=3\) the designs \(BIB(13,4,1)\), \(BIB(40,13,4)\), \(BIB(121,40,13)\) with resolvable designs \((9,12,4,3,1)\), \((27,39,13,9,4)\), \((81,120,40,27,13)\).

The reduced designs \(Q^*_n\) directly: `Qn`

The manual juxtaposition of Example 3 is automated by Qn(m, n, p), which builds the reduced resolvable design \(Q^*_n\) and its uniform design \(U(p^m, (p^n)^{r})\) for any stage. Its parameters match the paper’s tables, e.g. \(Q^*_2(16, 140, 35, 4, 7)\) for \(PG(4,2)\):

Q <- Qn(4, 2)
c(V = Q$V, B = Q$B, R = Q$R, K = Q$K, Lambda = Q$Lambda)
#>      V      B      R      K Lambda 
#>     16    140     35      4      7

identical(dim(Qn(3, 2)$UD), dim(ud$UD))  # the design of Example 3
#> [1] TRUE

Any two distinct runs of a Qn design coincide in exactly Lambda factors (the designs are equidistant), so every stage attains the discrete-discrepancy lower bound of Fang et al. (2003), and levels refine coherently across stages.

Beyond the paper: any prime order

Nothing restricts the recursion to the orders tabulated in the paper — any prime works:

Z <- BIB(2, p = 5)          # BIB(31, 6, 1): the projective plane of order 5
W <- Resolvable(1, Z$BIB)   # RBIB(25, 30, 6, 5, 1): AG(2, 5)
Uniform(W$RBIB)$UD          # U(25, 5^6)
#>       [,1] [,2] [,3] [,4] [,5] [,6]
#>  [1,]    1    1    1    1    1    1
#>  [2,]    5    1    5    4    3    2
#>  [3,]    3    1    3    5    2    4
#>  [4,]    4    1    4    2    5    3
#>  [5,]    2    1    2    3    4    5
#>  [6,]    1    5    5    5    5    5
#>  [7,]    1    3    3    3    3    3
#>  [8,]    1    4    4    4    4    4
#>  [9,]    1    2    2    2    2    2
#> [10,]    5    5    4    3    2    1
#> [11,]    3    3    5    2    4    1
#> [12,]    4    4    2    5    3    1
#> [13,]    2    2    3    4    5    1
#> [14,]    4    5    3    1    4    2
#> [15,]    5    3    2    1    5    4
#> [16,]    2    4    5    1    2    3
#> [17,]    3    2    4    1    3    5
#> [18,]    3    5    2    4    1    3
#> [19,]    2    3    4    5    1    2
#> [20,]    5    4    3    2    1    5
#> [21,]    4    2    5    3    1    4
#> [22,]    2    5    1    2    3    4
#> [23,]    4    3    1    4    2    5
#> [24,]    3    4    1    3    5    2
#> [25,]    5    2    1    5    4    3

References

Bose, Raj Chandra. 1942. “A Note on the Resolvability of Balanced Incomplete Block Designs.” Sankhyā 6: 105–10.

Boudraa, Abla, Zebida Gheribi-Aoulmi, and Mohamed Laib. 2013. “Recursive Method for Construction of Resolvable Nested Designs and Uniform Designs Associated.” International Journal of Research and Reviews in Applied Sciences 17 (2): 167–76. https://web.archive.org/web/20131228061100/http://www.arpapress.com/Volumes/Vol17Issue2/IJRRAS_17_2_04.pdf.

Dugué, Daniel. 1958. Traité de Statistique Théorique Et Appliquée. Paris: Masson et Cie.

Fang, Kai-Tai, Gen-Nian Ge, Min-Qian Liu, and Hong Qin. 2004. “Construction of Uniform Designs via Super-Simple Resolvable t-Designs.” Utilitas Mathematica 66: 15–32.

Fang, Kai-Tai, Xuan Lu, Yu Tang, and Jianxing Yin. 2004. “Constructions of Uniform Designs by Using Resolvable Packings and Coverings.” Discrete Mathematics 274: 25–40. https://doi.org/10.1016/S0012-365X(03)00100-6.