\section{Introduction}
Communication networks get overburdened with data traffic during peak hours and underutilized in off-peak hours. Caching is a technique to alleviate the high transmission load of a server in a communication network during peak hours, and it involves prefetching popular content and storing it nearer to or at the user's device during off-peak hours. Depending on the limitations on memory, a part of these files would be prefetched and once the user makes a demand, the rest of the requested file will be transmitted. The fundamental problem in caching is the optimal trade-off between the cache memory with each user versus the transmission load.

Maddah-Ali and Niesen had shown in their seminal paper that coding can achieve significant gain over uncoded caching by making use of multicast opportunities \cite{maddah2014fundamental}.
They showed their scheme to be order optimal with an information-theoretic lower bound on the number of files needed to be transmitted (known as \textit{rate}).
This scheme achieves a \textit{coding gain} (also known as \textit{global caching gain}) in addition to the \textit{caching gain}.
Asymptotically, its coding gain is proportional to the number of users and that results in a rate independent of the number of users.
A version of Maddah-Ali-Niesen (M-N) scheme, optimal for uncoded prefetching, was presented in \cite{yu2017exact}. Though the exact capacity expression for rate of coded caching is still an open problem, several bounds have been presented in  \cite{sengupta2015improved,ghasemi2017improved,wang2016new,yu2018characterizing,wan2016optimality}. The problem has been studied in several settings like decentralized caching \cite{maddah2015decentralized}, non-uniform demands \cite{niesen2016coded}, hierarchical caching \cite{karamchandani2016hierarchical}, coded prefetching \cite{chen2016fundamental, tian2018caching, gomez2018fundamental}, content security \cite{sengupta2014fundamental,ravindrakumar2016fundamental}, demand privacy \cite{wan2020coded,aravind2020subpacketization,kamath2020demand} to name a few.

An important parameter of interest in coded caching is \textit{subpacketization}. It is the number of parts a file will be split into, for the purpose of coding.
In the standard Maddah-Ali-Niesen scheme \cite{maddah2014fundamental}, the subpacketization, denoted $f$, grows exponentially with $K$ {and is given by $f= \binom{K}{KM/N} \approx 2^{K H\left(M/N\right)}$}.
This limits the utility of the scheme in practical scenarios where there may be a large number of users (large $K$). Hence, reducing subpacketization is important in coded caching schemes.
It was shown in \cite{shangguan2018centralized} that for rate independent of the number of users, the subpacketization should be superlinear in the number of users.
A few other bounds relating subpacketization with other parameters were proposed in \cite{cheng2017coded,chittoor2020subexponential}.
The pursuit towards lower subpacketization had lead to formulating coded caching in combinatorial frameworks.  
Under certain constraints, the coded caching problem is equivalent to the design of {placement delivery arrays} \cite{yan2017placement}, caching matrices \cite{agrawal2019coded}, partial Latin {rectangles} with Blackburn property \cite{shangguan2018centralized,wanless2004partial}, certain 3-uniform 3-partite hypergraphs \cite{shangguan2018centralized}, resolvable designs from linear block codes \cite{tang2018coded}, induced matchings of a Ruzsa-Szeméredi graph \cite{shanmugam2017coded,shanmugam2017unified}, strong edge coloring of the bipartite graph \cite{yan2017bipartite} or a clique cover for the complement of the square of the associated line graph \cite{krishnan2018coded}.
These frameworks require the cache contents to be uncoded and symmetric with respect to all files.
When the number of users is very large, rate of $O(K^\delta)$ for small $\delta$ is achievable with linear subpacketization (in $K$) from schemes based on dense Ruzsa-Szeméredi graphs \cite{alon2012nearly,shanmugam2017coded}.
For reducing subpacketization in practical scenarios, a few families of constructions have been built based on the combinatorial frameworks we have discussed.
Some of these schemes are summarised in Table~\ref{tab:schemes}.

\begin{table}[t]
\caption{Parameters of some known coded caching schemes.}
\label{tab:schemes}
\centering
\adjustbox{max width=\textwidth}{
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\textbf{Construction}                                                                & $\boldsymbol{K}$    & $\boldsymbol{M/N}$                             & $\boldsymbol{R}$                          & $\boldsymbol{f}$           & \textbf{Constraints}                                       \\ \hline
Maddah-Ali-Niesen \cite{maddah2014fundamental}                                                                   & $K$    & $\frac{t}{K}$                          & $\approx \frac{N}{M}$                 & $\approx 2^{K H(M/N)}$ &    $K,t \in \mathcal{Z}^+, K>t$                                                        \\ \hline
    Grouping by Shanmugam \textit{et al.} \cite{shanmugam2016finite}    & $ck$     & $\frac{t}{k}$                          & $\approx c\frac{N}{M}$                 & $\approx 2^{k H(M/N)}$ &    $c,k,t \in \mathcal{Z}^+, k>t$                                                        \\ \hline
Tang-Ramamoorthy   \cite{tang2018coded}                                                                  & $qn$            & $\frac{1}{q}$                                      & $\frac{(q-1)n}{k}+1$                  & $q^k$                  &                                                            \\ \hline
Shangguan \textit{et al.}   \cite{shangguan2018centralized}                                        & $\binom{n}{b}$  & $\frac{\binom{n}{a}-\binom{n-b}{a}}{\binom{n}{a}}$ & $\frac{\binom{n}{a+b}}{\binom{n}{a}}$ & $\binom{n}{a}$         &                                                            \\ \hline
\multirow{2}{*}{Agrawal \textit{et al.} \cite{agrawal2019coded}                }                           & $v$  & $1-\frac{k}{v}$ & $\frac{k(k-1)}{v-1}$ & $\frac{v(v-1)}{k(k-1)}$         & $\exists$ a $(v,k,1)$-BIBD.  
     \\ \cline{2-6}
& $v$  & $1-\frac{k-1}{v}$ & $1$ & $kv$         &       $\exists$ a simple symmetric $(v,k,2)$-BIBD.
               \\ \hline
    Alon \textit{et al.} \cite{alon2012nearly}, Shanmugam \textit{et al.} \cite{shanmugam2017coded}
 & $\ge K(\delta)$ & $\ge K^{-\epsilon(\delta)}$ & $K^\delta$ & $K$ & $\epsilon(\delta) \rightarrow 0$ and $K(\delta) \rightarrow \infty$ as $\delta \rightarrow 0$.
 \\ \hline
\end{tabular}}
\end{table}

In this work, we present a few construction schemes for placement delivery arrays.
\textit{Placement delivery array} or PDA developed by Yan \textit{et al.} captures the placement and delivery schemes as non-integer and integer entries in an array that satisfies some conditions \cite{yan2017placement}.
The number of columns of a PDA indicates the number of users while the number of rows indicates the subpacketization.
We focus on PDAs where the number of rows is linear with the number of columns.
Drawing inspiration from the lifting constructions for low-density parity-check codes \cite{thorpe2003low}, we propose lifting constructions for PDAs, where we use PDAs of small size to obtain larger PDAs.
We introduce a new technical notion of Blackburn-compatibility for PDAs that enable these lifting constructions. We propose a variety of constructions for PDAs which satisfy this constraint. This includes algebraic and randomized constructions. With the lifting constructions using these PDAs, we obtain good memory-rate tradeoffs with linear subpacketization. In particular, when the number of users has many divisors or is a power of $2$, the memory-rate tradeoffs are close to that of the standard Maddah-Ali and Niesen scheme. The random construction ensures PDAs satisfying Blackburn compatibility with good performance for arbitrary parameters. Our methods perform well both in terms of obtaining good coding gains and versatility.
Our specific contributions are as follows:
\begin{compactenum}[i)]
\item We propose construction schemes for $2$-regular placement delivery arrays for a wide range of parameters. The coded caching schemes from these PDAs are efficient in low memory regimes. This also gives a family of base PDAs for the subsequent lifting constructions.
\item We present a basic lifting construction that takes any two PDAs to construct larger PDAs with higher coding gain.
\item We propose the notion of Blackburn compatibility between PDAs and present a general lifting construction that uses a base PDA and a set of Blackburn compatible PDAs.
\item We present several constructions of Blackburn compatible PDAs for the lifting constructions which includes both algebraic and randomized constructions.
\item Using a combination of the constructions we propose, we demonstrate that significant coding gain and good memory-rate tradeoffs can be achieved with linear subpacketization.
\end{compactenum}
{The coded caching schemes that are constructed target the moderate (non-asymptotic) regime of parameters and are shown to be competitive with other existing schemes, particularly in terms of subpacketization.} We recently became aware of some existing works \cite{zhong2020placement,michel2019placement} that use the idea of combining PDAs to obtain new PDAs. Our constructions are more general in nature and follow a different approach.

The rest of the paper is organized as follows.
In Section~\ref{sec:ps}, we describe the system setup and the problem statement. 
We present the constructions for $2$-PDAs for a range of parameters in Section~\ref{sec:construction}.
In Section~\ref{sec:lifting}, we propose the lifting constructions for placement delivery arrays  from which we can construct coded caching schemes with low subpacketization. In Section~\ref{sec:blackburn}, we propose several constructions for Blackburn compatible PDAs which are the building blocks for the lifting constructions.
We present our results and compare them with existing works in Section~\ref{sec:results} and conclude with a brief summary of our work in Section~\ref{sec:conc}. An earlier version of this paper also contained some additional material on demand privacy and other algebraic constructions. Interested readers may refer to \cite{aravind2020coded}.

\section{Lifting or protograph-type constructions}\label{sec:lifting}
Constructions of PDAs with coding gain 2 and low subpacketization were briefly described in the previous section. To increase coding gain and obtain $g$-regular PDAs for $g>2$ without a significant increase in subpacketization, we employ the idea of lifting or protograph construction. Similar to the popular notion of protograph or lifted LDPC codes, we start with a base PDA, and replace each entry with another PDA. The PDAs that replace an integer or a $\Asterisk$ in the base PDA are called as \emph{constituent} PDAs. 

An important requirement when lifting PDAs is that we have to ensure that the Blackburn property is preserved during the lifting.
For this purpose, we define a constraint called \emph{Blackburn compatibility} which needs to be satisfied by the constituent PDAs for the lifting to be valid. 

We propose several deterministic and a randomized construction for lifting of PDAs and compare them with other existing PDAs in terms of their memory-rate tradeoff and subpacketization.  

\subsection{Notation for PDAs}\label{sec:notation}
The following PDAs are used repeatedly in lifting constructions.
\begin{enumerate}
    \item For an integer $t$, $I_n(t)$ denotes the $(n,n,n-1,1)$ PDA with the integer $t$ on the main diagonal and $\Asterisk$ in all other cells. $\tilde{I}_n(t)$ denotes the $(n,n,n-1,1)$ PDA with the integer $t$ on the main anti-diagonal and $\Asterisk$ in all other cells. For example, 
    \begin{align}
    I_3(1)=\begin{pmatrix}
    1  & \Asterisk & \Asterisk \\
    \Asterisk & 1  & \Asterisk \\
    \Asterisk & \Asterisk & 1
    \end{pmatrix},\quad \tilde{I}_3(0)=\begin{pmatrix}
    \Asterisk & \Asterisk & 0  \\
    \Asterisk & 0  & \Asterisk \\
    0  & \Asterisk & \Asterisk
    \end{pmatrix}.\label{eq:It}
    \end{align}
    \item For a set $\mathcal{S}=\{s_1,\ldots,s_{n(n-1)/2}\}$ of $n(n-1)/2$ integers, the PDAs $G_n(\mathcal{S})$ and $H_n(\mathcal{S})$ are as defined in Lemma \ref{lm:diagPDA}.
    \item For a set $\mathcal{S}=\{s_1,\ldots,s_{n^2}\}$ of $n^2$ integers, $J_n(\mathcal{S})$ denotes the $(n,n,0,\mathcal{S})$ PDA obtained by filling all the cells in the array with distinct integers from $\mathcal{S}$ row-wise in the specified order. For example,
    \begin{align}
    J_3([9])=\begin{pmatrix}
    0  & 1  & 2 \\
    3  & 4  & 5 \\
    6  & 7  & 8
    \end{pmatrix}.\label{eq:JS}
    \end{align}
\end{enumerate}
\subsection{Basic lifting}
In the first lifting method, we start with a base PDA and replace $\Asterisk$'s with an all-$\Asterisk$ array, and replace integers with PDAs that contain disjoint sets of integers. 
\begin{theorem}[Basic lifting]\label{th:basicTiling}
Let $P_b$ be a $(K,f,Z,\mathcal{S}_b)$ PDA. Let $\mathcal{P}=\{P_i:i\in\mathcal{S}_b\}$, where $P_i$ is an $(m,n,e,\mathcal{S}_i)$ PDA and $\mathcal{S}_i$, $\mathcal{S}_j$ are disjoint if $i\ne j$. Let an array $B_{\mathcal{P}}(P_b)$ be defined as follows:
\begin{enumerate}
    \item Each $\Asterisk$ in $P_b$ is replaced by a $n\times m$ all-$\Asterisk$ array.
    \item Each integer $i\in\mathcal{S}_b$ is replaced by $P_i\in\mathcal{P}$.
\end{enumerate}
Then, $B_{\mathcal{P}}(P_b)$ is a $(Km,fn,Zn+(f-Z)e,\mathcal{S})$ PDA, where $\mathcal{S}=\bigcup_{i\in\mathcal{S}_b}\mathcal{S}_i$. 
\end{theorem}
\begin{proof}
See the proof of a more general version in Theorem \ref{th:generalTiling}.
\end{proof}
 
\begin{example}
Two PDAs obtained using Theorem~\ref{th:basicTiling} are shown in Table \ref{tab:basicTiling}. The first one is with ${P_{b_1}}=\begin{pmatrix}
0&1&2\\
3&4&5\\
6&7&8
\end{pmatrix}$ and integer $i$ replaced with $I_3(i)$ resulting in a 3-regular $(9,9,6,9)$ PDA. The second one uses ${P_{b_2}}=\begin{pmatrix}
\Asterisk&0&1\\
0&\Asterisk&2\\
1&2&\Asterisk
\end{pmatrix}$ with 0 replaced by $G_3(\{0,1,2\})$, 1 replaced by $H_3(\{3,4,5\})$ and 2 replaced by $G_3(\{6,7,8\})$ resulting in a 4-regular $(9,9,5,9)$ PDA.
\begin{table}[htb]
    \centering
    \caption{Examples of lifting using Lemma \ref{th:basicTiling}. {The PDAs shown below are obtained by lifting $P_{b_1}$ and $P_{b_2}$ respectively.}}
    \label{tab:basicTiling}
    \begin{tabular}{?c+c+c?c+c+c?c+c+c?}
\Xhline{2\arrayrulewidth}
0 & $\Asterisk$ & $\Asterisk$ & \cellcolor{gray!50} 1 & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} $\Asterisk$ & 2 & $\Asterisk$ & $\Asterisk$ \\ \hline
$\Asterisk$ & 0 & $\Asterisk$ & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} 1 & \cellcolor{gray!50} $\Asterisk$ & $\Asterisk$ & 2 & $\Asterisk$ \\ \hline
$\Asterisk$ & $\Asterisk$ & 0 & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} 1 & $\Asterisk$ & $\Asterisk$ & 2 \\ \Xhline{2\arrayrulewidth}
\cellcolor{gray!50} 3 & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} $\Asterisk$ & 4 & $\Asterisk$ & $\Asterisk$ & \cellcolor{gray!50} 5 & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} $\Asterisk$ \\ \hline
\cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} 3 & \cellcolor{gray!50} $\Asterisk$ & $\Asterisk$ & 4 & $\Asterisk$ & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} 5 & \cellcolor{gray!50} $\Asterisk$ \\ \hline
\cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} 3 & $\Asterisk$ & $\Asterisk$ & 4 & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} 5 \\ \Xhline{2\arrayrulewidth}
6 & $\Asterisk$ & $\Asterisk$ & \cellcolor{gray!50} 7 & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} $\Asterisk$ & 8 & $\Asterisk$ & $\Asterisk$ \\ \hline
$\Asterisk$ & 6 & $\Asterisk$ & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} 7 & \cellcolor{gray!50} $\Asterisk$ & $\Asterisk$ & 8 & $\Asterisk$ \\ \hline
$\Asterisk$ & $\Asterisk$ & 6 & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} 7 & $\Asterisk$ & $\Asterisk$ & 8
\\ \Xhline{2\arrayrulewidth}
\end{tabular}
\hspace{0.5cm}
\begin{tabular}{?c+c+c?c+c+c?c+c+c?}
\Xhline{2\arrayrulewidth}
$\Asterisk$ & $\Asterisk$ & $\Asterisk$ & \cellcolor{gray!50} 0 & \cellcolor{gray!50} 1 & \cellcolor{gray!50} $\Asterisk$ & $\Asterisk$ & 3 & 4 \\ \hline
$\Asterisk$ & $\Asterisk$ & $\Asterisk$ & \cellcolor{gray!50} 2 & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} 1 & 3 & $\Asterisk$ & 5 \\ \hline
$\Asterisk$ & $\Asterisk$ & $\Asterisk$ & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} 2 & \cellcolor{gray!50} 0 & 4 & 5 & $\Asterisk$ \\ \Xhline{2\arrayrulewidth}
\cellcolor{gray!50} 0 & \cellcolor{gray!50} 1 & \cellcolor{gray!50} $\Asterisk$ & $\Asterisk$ & $\Asterisk$ & $\Asterisk$ & \cellcolor{gray!50} 6 & \cellcolor{gray!50} 7 & \cellcolor{gray!50} $\Asterisk$ \\ \hline
\cellcolor{gray!50} 2 & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} 1 & $\Asterisk$ & $\Asterisk$ & $\Asterisk$ & \cellcolor{gray!50} 8 & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} 7 \\ \hline
\cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} 2 & \cellcolor{gray!50} 0 & $\Asterisk$ & $\Asterisk$ & $\Asterisk$ & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} 8 & \cellcolor{gray!50} 6 \\ \Xhline{2\arrayrulewidth}
$\Asterisk$ & 3 & 4 & \cellcolor{gray!50} 6 & \cellcolor{gray!50} 7 & \cellcolor{gray!50} $\Asterisk$ & $\Asterisk$ & $\Asterisk$ & $\Asterisk$ \\ \hline
3 & $\Asterisk$ & 5 & \cellcolor{gray!50} 8 & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} 7 & $\Asterisk$ & $\Asterisk$ & $\Asterisk$ \\ \hline
4 & 5 & $\Asterisk$ & \cellcolor{gray!50} $\Asterisk$ & \cellcolor{gray!50} 8 & \cellcolor{gray!50} 6 & $\Asterisk$ & $\Asterisk$ & $\Asterisk$
\\ \Xhline{2\arrayrulewidth}
\end{tabular}
\end{table}
As a comparison, a $9\times 9$ PDA constructed using Corollary \ref{lem:modify_odd} has parameters $(9,9,5,18)$ and is 2-regular. The $(9,9,5,9)$ PDA using basic lifting is 4-regular and provides a lower rate coded caching scheme at the same memory when compared to the $(9,9,5,18)$ PDA.
\label{ex:basic}
\end{example}
The requirements imposed by Theorem \ref{th:basicTiling} on $P_i$ are strictly not necessary for the lifting to result in a valid PDA. Firstly, $P_i$ need not be valid PDAs by themselves. Secondly, the $P_i$ need not contain disjoint integers. A simple example is the lifting of $P_b=\begin{pmatrix}
    0\\
    1
\end{pmatrix}$ with $\mathcal{P}=\{P_0=\begin{pmatrix}
    0&\Asterisk\\
    \Asterisk&\Asterisk
\end{pmatrix}, P_1=\begin{pmatrix}
    \Asterisk&\Asterisk\\
    \Asterisk&0
\end{pmatrix}\}$, which results in a trivial 2-regular $(2,4,3,1)$ PDA. While for simplicity of general constructions and for dense base PDAs, constituent PDAs with disjoint sets of integers appear to be a good choice, further optimizations of the lifted PDAs will be possible for improving parameters and trade-offs. 
\subsubsection{Regular basic lifting}
The basic lifting construction is simple, and provides PDAs of various sizes with higher coding gains in a direct manner. The simplest $g$-regular construction by basic lifting is captured in the following corollary to Theorem~\ref{th:basicTiling}.
\begin{corollary}
Let $P_b$ be a $g_b$-regular $(K_b,f_b,Z_b,\frac{K_b(f_b-Z_b)}{g_b})$ PDA. Let $P_l$ be a $g_c$-regular $(m,n,e,\frac{m(n-e)}{g_c})$ PDA, and $\mathcal{P}=\{P_i:i\in[\frac{K_b(f_b-Z_b)}{g_b}]\}$, where $P_i$ are copies of $P_l$ with its integers replaced by another disjoint set of integers. Then, $B_{\mathcal{P}}(P_b)$, which is denoted simply as $B_{P_l}(P_b)$ in this case, is a $g_bg_c$-regular $(K_bm,f_bn,Z_bn+(f_b-Z_b)e,\frac{K_b(f_b-Z_b)}{g_b}\frac{m(n-e)}{g_c})$ PDA.
\label{cor:basicreg}
\end{corollary}
\begin{proof}
See proof of a more general case in Corollary \ref{cor:genreg}.
\end{proof}
As stated earlier, 1-PDAs and 2-PDAs are the easiest to construct and use as base PDAs and constituent PDAs in lifting. Let 1-PDA$(n,z)$ denote a $(n,n,z,n(n-z))$ 1-PDA, and let 2-PDA$(n,z)$ denote the $(n,n,z,n(n-z)/2)$ 2-PDA obtained using Corollaries \ref{lem:modify_even} and \ref{lem:modify_odd} for applicable values of $n,z$.

In Corollary \ref{cor:basicreg}, using a 1-PDA as $P_b$ or $P_l$, we do not obtain an increase in coding gain. An increase in coding gain is obtained if we consider 2-PDAs as $P_b$ and $P_l$. 
\begin{example}[2-PDA to 4-PDA]
In Corollary \ref{cor:basicreg}, let $P_b$ be 2-PDA$(K_b,Z_b)$ and $P_l$ be 2-PDA$(n,e)$, where $z$ and $e$ are chosen so that the 2-PDAs exist (see Corollaries \ref{lem:modify_even} and \ref{lem:modify_odd}). $B_{P_l}(P_b)$ is a $(K_bn,K_bn,Z_bn+(K_b-Z_b)e,K_bn(K_b-Z_b)(n-e)/4)$ 4-PDA. 
\end{example}
While each $P_i$ in $\mathcal{P}$ being regular is sufficient for the lifted PDA to be regular, it is not strictly necessary. To see this through an example, let $\mathcal{P}_3=\{P_0,P_1\}$ be the set of PDAs defined as
\begin{align}
    P_0 = \left(
        \begin{array}{ccc}
            \Asterisk & 0 & 2 \\
            0 & \Asterisk & 1 \\
            3 & 1 & \Asterisk
        \end{array}
        \right),\quad
    P_1 = \left(
        \begin{array}{ccc}
            1 & 2 & \Asterisk \\
            3 & \Asterisk & 2 \\
            \Asterisk & 3 & 0
        \end{array}
        \right).
        \label{eq:A3ex}
\end{align}
For $P_b=\begin{pmatrix}
0&\Asterisk\\
\Asterisk&1
\end{pmatrix}
$, $B_{\mathcal{P}_3}(P_b)$ is 3-regular, while neither $P_0$ nor $P_1$ are individually regular. 
\subsubsection{Recursive basic lifting}
Recursive application of basic lifting is useful in obtaining multiple lifted PDAs with different coding gains. This procedure is particularly effective if the final target number of users $K$ can be factored into a product of $r$ numbers as $K=K_1K_2\cdots K_r$, and is captured in the following lemma for reference (proof is skipped).
\begin{lemma}[Recursive basic lifting for $K=K_1K_2\cdots K_r$ users]\label{lm:recTiling}
Let $P_b^{(1)}$ be a $K_1\times K_1$ $g_1$-PDA, and let $P_l^{(i)}$ for $i=2,\ldots,r$ be $K_i\times K_i$ $g_i$-PDAs. Consider the recursion $P_b^{(i)}=B_{P_{l}^{(i)}}(P_b^{(i-1)})$ for $i=2,\ldots,r$. The result of the recursion $P_b^{(r)}$ is a $(g_1\cdots g_r)$-regular $K\times K$ PDA. 
\end{lemma}
We illustrate the above lemma with 1-PDAs and/or 2-PDAs used as constituent PDAs.
\begin{example}[1-PDA and 2-PDA recursive basic lifting  for $K=K_1K_2\cdots K_r$ users]
Let $g_i\in\{1,2\}$ for $i=1,\ldots,r$. If $g_i=1$, let $z_i\in[K_i]$. If $g_i=2$, let $z_i\in\{1,2,\ldots,K_i-1\}$ if $K_i$ is even, or let $z_i\in\{1,3,\ldots,K_i-2\}$ if $K_i$ is odd. Let $P_b^{(1)}$ be a $K_1\times K_1$ $g_1$-PDA, and let $P_l^{(i)}$ for $i=2,\ldots,r$ be $K_i\times K_i$ $g_i$-PDAs (these PDAs exist by Corollaries \ref{lem:modify_even} and \ref{lem:modify_odd}). Consider the recursion $P_b^{(i)}=B_{P_{l}^{(i)}}(P_b^{(i-1)})$ for $i=2,\ldots,r$. The number of $\Asterisk$s per column of $P_b^{(i)}$, denoted $Z_i$, is given by the recursion 
\begin{equation}
Z_i=Z_{i-1}K_i+(K_1\cdots K_{i-1}-Z_{i-1})z_i,\, i=2,\ldots,r,
\label{eq:zrecbasic}
\end{equation}
initialised with $Z_1=z_1$. The result of the recursive lifting $P_b^{(r)}$ is a $(g_1\cdots g_r)$-regular $K\times K$ PDA with $Z_r$ given by \eqref{eq:zrecbasic}.

\begin{figure}[H]
\begin{subfigure}{0.32\textwidth}
    \centering
    \input{figures_tex/fig_3a_basic24}
    \caption{$K=24$}
\end{subfigure}%
~
\begin{subfigure}{0.32\textwidth}
    \centering
    \input{figures_tex/fig_3a_basic64}
    \caption{$K=64$}
\end{subfigure}%
~
\begin{subfigure}{0.32\textwidth}
    \centering
    \input{figures_tex/fig_3a_basic250}
    \caption{$K=250$}
\end{subfigure}
        
\caption{Memory-rate tradeoff for $K=24,64,250$ obtained using Lemma~\ref{lm:recTiling}. The points related to PDAs with minimum $Z$ for a coding gain $g$ are highlighted in red and are labelled using $(Z,g)$.}
\label{fig:tiling24}
\end{figure}

\end{example}
\subsection{General lifting}
In basic lifting, every $\Asterisk$ in the base PDA is replaced with the all-$\Asterisk$ array. We next consider a generalized version of basic lifting by allowing more general PDAs to replace a $\Asterisk$. For coded caching schemes with low cache memory, since we need the number of $\Asterisk$s in each column in the lifted PDA to be low, replacing $\Asterisk$ in the base PDA with non-trivial PDAs is beneficial. However, to ensure that the Blackburn property for the lifted PDA is not violated, the constituent PDAs that are used to replace the integers and $\Asterisk$s need to satisfy some additional constraints.
We introduce the notion of Blackburn compatibility of PDAs to capture such constraints on the constituent PDAs.

\subsubsection{Blackburn compatibility}
Two $n\times n$ PDAs $P_0=[p^{(0)}_{ij}]$ and $P_1=[p^{(1)}_{ij}]$ are said to be \emph{Blackburn-compatible} with respect to (w.r.t.) a third $n\times n$ PDA $P_{\Asterisk}=[p^{({\Asterisk})}_{ij}]$ if, whenever  $p^{(0)}_{i_1j_1}{=}p^{(1)}_{i_2j_2}{\ne}\Asterisk$, we have  $p^{({\Asterisk})}_{i_1j_2}{=}p^{({\Asterisk})}_{i_2j_1}=\Asterisk$. In other words, if two entries in $P_0$ and $P_1$ are a common integer $s$, the \emph{mirrored} locations of $s$ in $P_*$ are $\Asterisk$s. For $g\ge2$, we say $P_0,\ldots,P_{g-1}$ are Blackburn compatible w.r.t. $P_*$ when they are pairwise Blackburn compatible with $P_*$. 

To see the connection between Blackburn compatibility and lifting, consider an integer $s$ occurring $g$ times in a base PDA. The rows and columns containing $s$ in the PDA, after permutations, can be rearranged into the PDA $I_g(s)$. So, any valid lifting of the base PDA needs to necessarily include a valid lifting of $I_g(s)$. Validity of a certain lifting of $I_g(s)$ and Blackburn compatibility are shown to be equivalent in the following lemma. 
\begin{lemma}[{Equivalence between Blackburn-compatibility and lifting}]
Suppose $P_*,P_0,\ldots,P_{g-1}$ are PDAs of the same size. Let $P_*^{(i,j)}$ for $i,j=0,1,2,\ldots$ be copies of $P_*$ containing integers that are disjoint from each other and from the integers in $P_0,\ldots,P_{g-1}$. Then, the set $\mathcal{P}=\{P_0,\ldots,P_{g-1}\}$ is a set of PDAs Blackburn-compatible w.r.t. $P_*$ if and only if the following lifting of $I_g$ is a valid PDA. 
$$L_{\mathcal{P},P_*}(I_g)\triangleq\begin{pmatrix}
    P_0&P_*^{(0,1)}&\cdots&P_*^{(0,g-1)}\\
    P_*^{(1,0)}&P_1&\cdots&P_*^{(1,g-1)}\\
    \vdots&\vdots&\ddots&\vdots\\
    P_*^{(g-1,0)}&P_*^{(g-1,1)}&\cdots&P_{g-1}
\end{pmatrix},$$ 
\end{lemma}
\begin{proof}
The conditions for validity of the above PDA and the definition of Blackburn compatibility are readily seen to be equivalent. Because of the disjointness properties of the integers in $P_*^{(i,j)}$, no additional conditions arise.
\end{proof}
The above lemma, beyond establishing the connection between lifting and Blackburn compatibility, provides a way to visualize the mirrored locations and aids in constructions of Blackburn-compatible PDAs.  

We see that any two PDAs are Blackburn-compatible w.r.t. the trivial all-$\Asterisk$ PDA. If $P_*$ is not all $\Asterisk$, the Blackburn compatibility needs to be established more carefully. Before presenting tests for Blackburn compatibility and general constructions, we show some illustrative examples. 
\begin{example}
$P_0=\begin{pmatrix}
    0&1\\
    3&4
\end{pmatrix}$, $P_1=\begin{pmatrix}
    4&1\\
    3&0
\end{pmatrix}$ are Blackburn-compatible w.r.t. $I_2(t)=\begin{pmatrix}
    t&\Asterisk\\
    \Asterisk&t
\end{pmatrix}$ for $t\notin\{0,1,3,4\}$. We see that
\begin{align*}
L_{\{P_0,P_1\},I2}(I_2)=\left(\begin{array}{cc:cc}
    0&1&2&\Asterisk\\
    3&4&\Asterisk&2\\ \hdashline
    5&\Asterisk&4&1\\
    \Asterisk&5&3&0
\end{array}\right)
\end{align*}
is the $(4,4,1,6)$ 2-PDA that we have earlier denoted as $G_4([6])$.
\end{example}
\begin{example}
$P_0=\begin{pmatrix}
    \Asterisk&0&2\\
    0&\Asterisk&1\\
    3&1&\Asterisk
\end{pmatrix}$, $P_1=\begin{pmatrix}
    1&2&\Asterisk\\
    3&\Asterisk&2\\
    \Asterisk&3&0
\end{pmatrix}$ are Blackburn-compatible w.r.t. $I_3(t)$ for $t\notin[4]$. We see that
\begin{align*}
L_{\{P_0,P_1\},I_3}(I_2)=\left(\begin{array}{ccc:ccc}
    \Asterisk&0&2&4&\Asterisk&\Asterisk\\
    0&\Asterisk&1&\Asterisk&4&\Asterisk\\
    3&1&\Asterisk&\Asterisk&\Asterisk&4\\\hdashline
    5&\Asterisk&\Asterisk&1&2&\Asterisk\\
    \Asterisk&5&\Asterisk&3&\Asterisk&2\\
    \Asterisk&\Asterisk&5&\Asterisk&3&0
\end{array}\right)
\end{align*}
is a $(6,6,3,6)$ 3-PDA.
\end{example}
\begin{example}
Consider the following rectangular arrays.
\begin{align}
    P_0 = \begin{pmatrix}
        0 & \Asterisk & \Asterisk & 1 & 6\\
        2 & 1 & \Asterisk & \Asterisk & 7\\
        \Asterisk & 5 & 2 & \Asterisk & 3\\
        \Asterisk & 4 & 9 & 3 & \Asterisk\\
        \Asterisk & \Asterisk & 0 & 5 & 4\\
        \Asterisk & \Asterisk & 1 & \Asterisk & 8\\
        9 & \Asterisk & \Asterisk & 7 & \Asterisk\\
        3 & 8 & \Asterisk & \Asterisk & \Asterisk\\
        4 & \Asterisk & 6 & \Asterisk & \Asterisk\\
        \Asterisk & 0 & \Asterisk & 2 & \Asterisk        
    \end{pmatrix},
    P_1 = \begin{pmatrix}
        \Asterisk & \Asterisk & \Asterisk & 1 & 6\\
        2 & \Asterisk & \Asterisk & \Asterisk & 7\\
        \Asterisk & 5 & \Asterisk & \Asterisk & 3\\
        \Asterisk & 4 & 9 & \Asterisk & \Asterisk\\
        \Asterisk & \Asterisk & 0 & 5 & \Asterisk\\
        5 & \Asterisk & 1 & \Asterisk & 8\\
        9 & 6 & \Asterisk & 7 & \Asterisk\\
        3 & 8 & 7 & \Asterisk & \Asterisk\\
        4 & \Asterisk & 6 & 8 & \Asterisk\\
        \Asterisk & 0 & \Asterisk & 2 & 9        
    \end{pmatrix},
    P_{\Asterisk}(\{s,t\}) = \begin{pmatrix}
        s & \Asterisk & \Asterisk & \Asterisk & \Asterisk \\
        \Asterisk & s & \Asterisk & \Asterisk & \Asterisk \\
        \Asterisk & \Asterisk & s & \Asterisk & \Asterisk \\
        \Asterisk & \Asterisk & \Asterisk & s & \Asterisk \\
        \Asterisk & \Asterisk & \Asterisk & \Asterisk & s \\
        t & \Asterisk & \Asterisk & \Asterisk & \Asterisk \\
        \Asterisk & t & \Asterisk & \Asterisk & \Asterisk \\
        \Asterisk & \Asterisk & t & \Asterisk & \Asterisk \\
        \Asterisk & \Asterisk & \Asterisk & t & \Asterisk \\
        \Asterisk & \Asterisk & \Asterisk & \Asterisk & t \\
    \end{pmatrix}.
\label{eq:10by5}
\end{align}
We can check that $P_0$ and $P_1$ are Blackburn-compatible w.r.t. $P_*(\{s,t\})$ for $s,t\notin[10]$ by confirming that all mirrored locations of integers 0 to 9 are $\Asterisk$s. Also, $$L_{\{P_0,P_1\},P_*}(I_2)=\begin{pmatrix}
    P_0&P_*(\{10,11\})\\
    P_*(\{12,13\})&P_1
\end{pmatrix}$$
is a $(10,20,13,14)$ 5-PDA. 
\end{example}
\begin{example}
Given,
\begin{align}
     P_*(\{t_0,t_1,t_2,t_3\})=\begin{pmatrix}
         I_3(t_0)\\
         I_3(t_1)\\
         I_3(t_2)\\
         I_3(t_3)
     \end{pmatrix}, P_0=\begin{pmatrix}
         J_3(0:8)\\
         H_{3,0}(9,13,17)\\
         H_{3,1}(10,14,15)\\
         H_{3,2}(11,12,16)
     \end{pmatrix}, P_1=\begin{pmatrix}
         J_3(9:17)\\
         H_{3,0}(0,4,8)\\
         H_{3,1}(1,5,6)\\
         H_{3,2}(2,3,7)
     \end{pmatrix}
\label{eq:12by3}
\end{align}
$P_0$ and $P_1$ are Blackburn-compatible w.r.t. $P_*(\{t_0,t_1,t_2,t_3\})$ for $t_0,t_1,t_2,t_3 \notin [18]$ and
$$L_{\{P_0,P_1\},P_*}(I_2)=\begin{pmatrix}
    P_0&P_*(\{18,19,20,21\})\\
    P_*(\{22,23,24,25\})&P_1
\end{pmatrix}$$
is a $(6,24,11,26)$ 3-PDA.
\end{example}
The above examples are for two PDAs Blackburn-compatible w.r.t. a third non-trivial PDA. When $P_*$ is all-$\Asterisk$, an arbitrary number of copies of a PDA, $\{P,P,\ldots\}$, are Blackburn-compatible w.r.t. the all-$\Asterisk$ array, and this is used in the basic lifting of Theorem \ref{th:basicTiling}. However, for a general $P_*$, we require integer-disjoint copying of PDAs to ensure Blackburn compatibility. Since this is a repeatedly occurring step in constructions, we record it as a lemma.
\begin{lemma}[{Replication of Blackburn-comptabible PDAs}]\label{lm:bcReplicate}
Given a set $\mathcal{P}$ of $b$ PDAs Blackburn-compatible w.r.t. $P_*$, the set of $mb$ PDAs formed by $m$ integer-disjoint copies of the PDAs in $\mathcal{P}$ is Blackburn-compatible w.r.t. $P_*$, for any integer $m > 0$.
\end{lemma}
\begin{proof}
The proof is immediate by the disjointness of the integers.
\end{proof}
The use of integer-disjoint copying in the above lemma results in a multiplicative increase in the number of integers with every replication. If a decrease in the number of integers is desirable (to change the memory-rate trade-off), other methods have to be considered.
\subsubsection{General lifting theorem}
Using Blackburn-compatible PDAs, a generalization of basic lifting is presented in the following theorem.
\begin{theorem}[General lifting]\label{th:generalTiling}
Let $P_b$ be a $(K,f,Z_b,\mathcal{S}_b)$ PDA. Let $g_s$ be the frequency of integer $s$ in $P_b$.
For $s\in \mathcal{S}_b$ and $t\in\{1,\ldots,g_s\}$, let $P_{s,t}$ be an $(m,n,Z_c,\mathcal{S}_{s,t})$ PDA such that for any $s$, $P_{s,1}, \ldots , P_{s,g_s}$ are Blackburn compatible w.r.t. an $(m,n,Z_*,\mathcal{S}_*)$ PDA $P_*$, and, for distinct integers $s,s'\in\mathcal{S}_b$, $\mathcal{S}_{s,t}$ and $\mathcal{S}_{s',t'}$ are disjoint.
Let $P_{*,r}$, $r\in[KZ_b]$, be integer-disjoint copies of $P_*$, which are integer-disjoint with $P_{s,t}$ as well.
Let an array $P$ be defined as follows:
\begin{enumerate}
    \item $r$-th $\Asterisk$ in $P_b$ is replaced by $P_{\Asterisk,r}$ for $r\in[KZ_b]$.
    \item $t$-th occurrence of integer $s\in\mathcal{S}_b$ in $P_b$ is replaced by $P_{s,t}$ for $t=1,\ldots,g_s$.
\end{enumerate}
Then, $P$ is a $(Km,fn,Z_bZ_*+(f-Z_b)Z_c,\mathcal{S})$ PDA, where $\mathcal{S}=\left(\bigcup_{r\in[KZ_b]}\mathcal{S}_{*,r}\right)\bigcup\left(\bigcup_{s\in\mathcal{S}_b}\bigcup_{t\in[g_s]}\mathcal{S}_{s,t}\right)$.
\end{theorem}
\begin{proof}
Clearly, $P$ is an $fn\times Km$ array. Each column of $P_b$ has $Z_b$ $\Asterisk$'s and $f-Z_b$ integers. So, each column of $P$ has $Z_bZ_*+(f-Z_b)Z_c$ $\Asterisk$'s satisfying \ref{cond:equalZ}. 

Since $P_b$ is a PDA, $P$ has all integers in $\mathcal{S}$ occurring at least once, satisfying \ref{cond:everysOnce}.

Finally, we need to verify the Blackburn property for $P$. Let $p_{i,j}$ and $q_{i,j}$ denote the $(i,j)$-th elements of $P_b$ and $P$, respectively. Let $i/n$ denote the quotient when $i$ is divided by $n$, and let $j/m$ be defined similarly. If $q_{i_1,j_1}=q_{i_2,j_2}=s$ in the lifted PDA $P$, we necessarily have that $p_{i_1/n,j_1/m}=p_{i_2/n,j_2/m}$ in the base PDA $P_b$ because different integers are expanded to PDAs containing disjoint sets of integers. So, we have $p_{i_1/n,j_2/m}=p_{i_2/n,j_1/m}=\Asterisk$ by the Blackburn property. Since an $\Asterisk$
 is replaced by $P_{0,t}$ and an entry in $P_{0,t}$ is $\Asterisk$ iff the corresponding entry in $P_{0}$ is $\Asterisk$, $q_{i_1,j_2}=q_{i_2,j_1}=\Asterisk$ in $P$ due to the Blackburn compatibility of the PDAs replacing an integer w.r.t $P_{\Asterisk}$. Hence, the Blackburn property (\ref{cond:blackburn}) is satisfied.
\end{proof}
Clearly, basic lifting is a special case of general lifting, where $P_*$ is the all-$\Asterisk$ array and $P_{s,t}$ are arbitrary PDAs. However, if a non-trivial $P_*$ is to be used, then we require as many Blackburn-compatible PDAs w.r.t. $P_*$ as the largest integer frequency of the base PDA. We will see general methods to construct Blackburn-compatible PDAs in the next sections.

To obtain regular lifted PDAs, the constituent PDAs and the base PDAs will need to be chosen more carefully. The following corollary of the above general lifting theorem presents a sufficient condition for regular lifting using Blackburn compatibility.
\begin{corollary}[{General regular lifting}]\label{co:regularTiling}
Let $P_b$ be a $(K_b,f_b,Z_b,K_b(f_b-Z_b)/g_b)$ $g_b$-PDA. Let $P_*$ be an $(m,n,Z_*,m(n-Z_*)/g)$ $g$-PDA. Let  $\mathcal{P}=\{P_0, P_1, \ldots,P_{g_b-1}\}$ be a set of
$n\times m$ PDAs satisfying the following conditions: 
\begin{itemize}
    \item the number of $\Asterisk$s in every column of every $P_i$ is equal to $e$,
    \item an integer occurring in any one $P_i$ occurs a total of $g$ times across all $P_i$'s,
    \item $\mathcal{P}$ is Blackburn-compatible w.r.t. $P_*$.
\end{itemize}
For $s\in[K(f-Z_b)/g_b]$, let $\mathcal{P}_s=\{P_{s,0},\ldots,P_{s,g_b-1}\}$ be an integer-disjoint copy of $\mathcal{P}$. Let the lifting of $P_b$ using Theorem \ref{th:generalTiling} with $P_{s,t}$ as constituent PDAs be denoted $L_{\mathcal{P},P_*}(P_b)$.

Then, $L_{\mathcal{P},P_*}(P_b)$ is a $g$-regular $(K_bm,f_bn,Z_bZ_*+(f_b-Z_b)e,\frac{K_bm(f_bn-Z_bZ_*-(f_b-Z_b)e)}{g})$ PDA.
\label{cor:genreg}
\end{corollary}
\begin{proof}
Only the parameters of $L_{\mathcal{P},P_*}(P_b)$ need to be established. Clearly, $L_{\mathcal{P},P_*}(P_b)$ is a $f_bn\times K_bm$ array. An integer in $P_b$ occurs $g_b$ times and the $i$-th occurrence is replaced by $P_i$. So, the number of times an integer occurs in $L_{\mathcal{P},P_*}(P_b)$ is $g$. Every column of $P_b$ contains $Z_b$ $\Asterisk$s and $f_b-Z_b$ integers. Since $\Asterisk$ is replaced by a copy of $P_*$ and an integer is replaced by a copy of $P_i$, the number of $\Asterisk$s per column after lifting is $Z_bZ_*+(f_b-Z_b)e$. 
\end{proof}

A crucial requirement for lifting with $P_*$ not being all-$\Asterisk$ is sets of Blackburn-compatible PDAs. Integer-disjoint copying is one simple method for constructing any number of Blackburn-compatible PDAs w.r.t. any $P_*$. For specific choices of $P_*$, other methods of construction could improve upon integer-disjoint copying, and we consider such constructions next.

\section{Constructions of Blackburn-compatible PDAs}\label{sec:blackburn}
We will present some general constructions for Blackburn-compatible PDAs using the following ideas - (1) permutation of integer elements and blocks to ensure mirrored locations are $\Asterisk$s, (2) tiling of identity/regular PDAs, (3) recursive methods, and (4) a randomized construction. 

{One strategy to construct Blackburn-compatible PDAs is to use existing PDAs from Section~\ref{sec:notation} for $P_*$ and $P_0$ and obtain the rest of $P_i$'s by transforming $P_0$ using permutations, transpose etc.}
{In Corollary~\ref{cor:genreg}, when $P_*$ is $g$-regular and each $P_i\in\mathcal{P}$ is $g_i$-regular with same set of integers, we have $g=g_bg_i$.
One natural choice for $P_*$ is $I_g(t)$ since it is a linear PDA with high coding gain.}
In most cases, we will consider the choice of $P_*$ as $I_g(t)$.
The following lemma provides a test for Blackburn compatibility of PDAs with respect to $I_g(t)$.
\begin{lemma}[Test for compatibility w.r.t. $I_g(t)$] \label{lm:InCompatible}
Two $g\times g$ PDAs $P_0$ and $P_1$ are Blackburn compatible with $I_g(t)$ for $t$ not appearing in $P_0$ or $P_1$ iff $p^{(0)}_{i_0j_0}{=}p^{(1)}_{i_1j_1}{\ne}\Asterisk$ implies $i_0 \ne j_1$ and $i_1 \ne j_0$. In words, mirrored locations of integers should be off-diagonal.
\end{lemma}
\begin{proof}
If $p^{(0)}_{i_0j_0}{=}p^{(1)}_{i_1j_1}{\ne}\Asterisk$ implies $i_0 \ne j_1$ and $i_1 \ne j_0$, then for no $i\in [g]$ we need $p_{i,i}^{(0)}=\Asterisk$. Hence $P_0$ and $P_1$ are Blackburn compatible w.r.t. any $g\times g$ PDA which has integers only in its diagonal. Now, let $P_0$ and $P_1$ are Blackburn compatible w.r.t. $I_g(t)$. Assume that $\exists s\in \mathcal{S}_0\cap \mathcal{S}_1$ such that $p^{(0)}_{i_0j_0}{=}p^{(1)}_{i_1j_1}=s$ and $i_0 = j_1$. This implies that cell $(i_0,i_0)$ of $I_g(t)$ is $\Asterisk$, But this is a contradiction. Hence $i_0 \ne j_1$. Similarly we can prove that $i_1 \ne j_0$.
\end{proof}

\subsection{Permutation constructions} 
{Now we introduce two permutation operations to obtain $P_i$'s for $i>0$ from $P_0$ when $P_0$ is either a $1$-PDA or a $2$-PDA as defined in Section~\ref{sec:notation}.
These $P_i$'s will be Blackburn compatible w.r.t. $I_g(t)$.}
The first permutation construction uses \emph{cyclic rotation of diagonal or anti-diagonal elements}, for which, we need the following notation. Given an $n\times n$ PDA $P=[p_{ij}]$, where $i$ and $j$ take values from $0$ to $n-1$, a PDA $\pi_{D,1}(P)$ is defined as
$$\pi_{D,1}(P)=\begin{pmatrix}
p_{n-1,n-1}&p_{0,1}&\cdots&p_{0,n-1}\\
p_{1,0}&p_{0,0}&\cdots&p_{1,n-1}\\
\vdots&\vdots&\ddots&\vdots\\
p_{n-1,0}&\cdots&\cdots&p_{n-2,n-2}
\end{pmatrix}.$$
Basically, $\pi_{D,1}(P)$ is identical to $P$ except for the diagonal entries, which are circularly shifted down by one position. For an integer $l$, $\pi^l_{D,1}(P)$ denotes the PDA obtained by $l$ applications of $\pi_{D,1}$ on $P$. For negative $l$, the diagonal entries are shifted up $l$ times.  
A similar cyclic rotation of anti-diagonal elements in $P$ is denoted by $\pi_{AD,1}(P)$, where $(i,j)$ on the anti-diagonal goes to $(i-1,j+1)\mod n$ and all other locations are retained. 

Given a $2n\times 2n$ PDA $P=\begin{pmatrix}P_{11}&P_{12}\\P_{21}&P_{22}\end{pmatrix}$, where $P_{ij}$ are $n\times n$ blocks, a PDA $\pi_{D,2}(P)$ is defined as
$$\pi_{D,2}(P)=\begin{pmatrix}
\pi_{D,1}(P_{11})&P_{12}\\
P_{21}&\pi^{-1}_{D,1}(P_{22})
\end{pmatrix}.$$
$\pi_{D,2}(P)$ is identical to $P$ except for the $2n$ diagonal entries - the first $n$ are circularly shifted down by one position, and the second $n$ are circularly shifted up by 1 position. A similar cyclic rotation of anti-diagonal elements in $P$ is denoted by $\pi_{AD,2}(P)$.

\begin{lemma}[Cyclic rotation]\label{lm:bc12pdas}
\begin{enumerate}
    \item (Construction C1) 
    \begin{enumerate}
        \item Given a 1-PDA $P$, $\{P,\pi_{D,1}(P)\}$ is Blackburn-compatible w.r.t. $I_g(t)$, and $\{P,\pi_{AD,1}(P)\}$ w.r.t. $\tilde{I}_g(t)$. 
        \item Letting $P=J_g([g^2])$, $\mathcal{P}_D=\{P,\pi_{D,1}(P),\ldots,\pi_{D,1}^{g-1}(P)\}$ is a set of $g$ $1$-PDAs Blackburn compatible w.r.t $I_g(t)$, and $\mathcal{P}_{AD}=\{P,\pi_{AD,1}(P),\ldots,\pi_{AD,1}^{g-1}(P)\}$ w.r.t. $\tilde{I}_g(t)$. 
        \item $L_{\mathcal{P}_D,I_g}(I_g)$ and $L_{\mathcal{P}_{AD},\tilde{I}_g}(I_g)$ are $g$-regular $(g^2,g^2,g^2-2g+1,g(2g-1))$ PDAs.
    \end{enumerate}
    \item (Construction C2) 
    \begin{enumerate}
        \item Letting $Q_0=G_{2g}([g(2g-1)])$ and $Q_1=H_{2g}([g(2g-1)])$, $\{Q_0,\pi_{D,2}(Q_0)\}$ is Blackburn-compatible w.r.t. $I_{2g}(t)$, and $\{Q_1,\pi_{AD,2}(Q)\}$ w.r.t. $\tilde{I}_{2g}(t)$. 
        \item Then $\mathcal{Q}_D=\{Q_0,\pi_{D,2}(Q_0),\ldots,\pi_{D,2}^{g-1}(Q_0)\}$ is a set of $g$ 2-PDAs Blackburn compatible w.r.t $I_{2g}(t)$, and $\mathcal{Q}_{AD}=\{Q_1,\pi_{AD,2}(Q_1),\ldots,\pi_{AD,2}^{g-1}(Q_1)\}$ w.r.t. $\tilde{I}_{2g}(t)$. 
        \item $L_{\mathcal{Q}_D,I_{2g}}(I_g)$ and $L_{\mathcal{Q}_{AD},\tilde{I}_{2g}}(I_g)$ are $2g$-regular $(2g^2,2g^2,2g^2-3g+2,g(3g-2))$ PDAs.
    \end{enumerate}
\end{enumerate}
The integer $t$ is chosen to be disjoint from the integers in $P$, $Q_0$ or $Q_1$.
\end{lemma}
\begin{proof}
We prove Part 1(a) as follows. Suppose $[P]_{ij}=[\pi_{D,1}(P)]_{ij}\ne\Asterisk$ for $i\ne j$ (off-diagonal). Then, the corresponding mirrored $(i,j)$-th entry of $I_g(t)$ for $i\ne j$ is a $\Asterisk$. Suppose $[P]_{ii}=[\pi_{D,1}(P)]_{jj}\ne\Asterisk$ (diagonal). Then, $i\ne j$ because of the rotation, and the mirrored $(i,j)$-th entry of $I_g(t)$ for $i\ne j$ is a $\Asterisk$. The claim for $P$ and $\pi_{AD,1}(P)$ can be proved in a similar fashion. Part 1(b) uses Part 1(a) with $P=J_g([g^2])$. Part 1(c) can be verified by a straight-forward calculation.

For Construction C2, the above proof can be modified in a minor way and we skip the details.
\end{proof}
\begin{example}
For $g=3$, a set of 3 PDAs $\mathcal{P}_3=\{P_1,P_2,P_3\}$ that are pairwise Blackburn-compatible w.r.t. $P_{\Asterisk}=I_3(t)$ constructed using C1 is shown below.
\begin{align}
\label{eq:1gP3}
\begin{split}
    P_{\Asterisk} = I_3(t) &= \left(
        \begin{array}{ccc}
            t & \Asterisk & \Asterisk \\
            \Asterisk & t & \Asterisk \\
            \Asterisk & \Asterisk & t
        \end{array}
        \right),\,
    P_0 = J_3([9]) = \left(
        \begin{array}{ccc}
            0 & 1 & 2 \\
            3 & 4 & 5 \\
            6 & 7 & 8
        \end{array}
        \right),\,\\
    P_1 &= \left(
        \begin{array}{ccc}
            8 & 1 & 2 \\
            3 & 0 & 5 \\
            6 & 7 & 4
        \end{array}
        \right),\,
    P_2 = \left(
        \begin{array}{ccc}
            4 & 1 & 2 \\
            3 & 8 & 5 \\
            6 & 7 & 0
        \end{array}
        \right).
\end{split}
\end{align}
Integer-disjoint copying would have resulted in 27 integers across $P_0$, $P_1$ and $P_2$, while the above construction uses 9. The lifted PDA $L_{\mathcal{P}_3,I_3}(I_3)$ is a 3-regular $(9,9,4,15)$ PDA.
\end{example}
\begin{example}
For $g=2$, a set of 2 PDAs $\mathcal{Q}_2=\{Q_0,Q_1\}$ that are Blackburn compatible w.r.t. $I_4(t)$ constructed using C2 is shown below.
\begin{align}
    Q_{\Asterisk}=I_4(t) = \left(
        \begin{array}{cccc}
            t & \Asterisk & \Asterisk & \Asterisk \\
            \Asterisk & t & \Asterisk & \Asterisk \\
            \Asterisk & \Asterisk & t & \Asterisk \\
            \Asterisk & \Asterisk & \Asterisk & t
        \end{array}
        \right),\,
    Q_0 = \left(
        \begin{array}{cccc}
            0 & 1 & 2 & \Asterisk \\
            3 & 4 & \Asterisk & 2 \\
            5 & \Asterisk & 4 & 1 \\
            \Asterisk & 5 & 3 & 0
        \end{array}
        \right),\,
    Q_1 = \left(
        \begin{array}{cccc}
            4 & 1 & 2 & \Asterisk \\
            3 & 0 & \Asterisk & 2 \\
            5 & \Asterisk & 0 & 1 \\
            \Asterisk & 5 & 3 & 4
        \end{array}
        \right).
        \label{eq:2gP4}
\end{align}
The lifted PDA $L_{\mathcal{Q}_2,I_4}(I_2)$ is a 4-regular $(8,8,4,8)$ PDA.
\end{example}

Next, we provide two transpose constructions for pairs of 1-PDAs Blackburn-compatible w.r.t. a $P_*$ with $\Asterisk$s on one or more diagonals.
\begin{lemma}[Transpose construction]\label{lm:bcTranspose}
For a $g\times g$ PDA $P$, the $i$-th diagonal of $P$ is the set of locations $\{(x,y): y=x+i\text{ mod }g\}$, $i\in[g]$. The $0$-th diagonal is the main diagonal. 
\begin{enumerate}[nosep]
    \item (Construction T1) A $g\times g$ 1-PDA $P$ and its transpose $P^T$ are Blackburn-compatible w.r.t. a $g\times g$ PDA $P_*$ with $\Asterisk$ on the diagonal cells.
    \item (Construction T2) For integers $g$ and $i$, a $g\times g$ 1-PDA $P$ and a cyclic permutation of its transpose $\pi^i_{AD,1}(P^T)$ are Blackburn-compatible w.r.t. a $g\times g$ PDA $P_*$ with $\Asterisk$ on the main and $i$-th diagonal cells.
\end{enumerate}
The integers in $P_*$ are assumed to be disjoint from those in $P$.
\end{lemma}
\begin{proof}
For proving T1, let $P_1=P$ and $P_2=P_1^T$. Since $p^{(1)}_{i_1j_1}{=}p^{(2)}_{i_2j_2}{\ne}\Asterisk$ implies $i_1 = j_2$ and $i_2 = j_1$ by construction and all diagonal entries in $P_*$ are $\Asterisk$, Blackburn compatibility is established.

For proving T2, let $P_1=P$ and $P_2=\pi^i_{AD,1}(P_1^T)$. If $p^{(1)}_{i_1j_1}{=}p^{(2)}_{i_2j_2}{\ne}\Asterisk$, there are two cases to consider. 
\begin{enumerate}
    \item $(i_1,j_1)$ is not on the anti-diagonal, which implies $i_1=j_2$ and $i_2=j_1$. So, the mirrored locations $(i_1,j_2)$ and $(i_2,j_1)$ are main diagonal entries of $P_*$, which are $\Asterisk$.
    \item $(i_1,j_1)$ is on the anti-diagonal, which implies $(i_2,j_2)$ is also on the anti-diagonal - transposed and cyclically rotated $i$ times. So, $i_2=j_1-i, j_2=i_1+i$ ($\text{mod } g$). So, the mirrored locations $(i_1,i_1+i\text{ mod }g)$ and $(j_1-i\text{ mod }g,j_1)$ are $i$-th diagonal entries of $P_*$, which are $\Asterisk$.
\end{enumerate}
This establishes Blackburn compatibility of $P$ and $\pi^i_{AD,1}(P^T)$ w.r.t. $P_*$ with $\Asterisk$ on the main and $i$-th diagonals.
\end{proof}
An example of the above lemma (T1) for $n=3$ is shown below.
\begin{align}
    P_* = \left(
        \begin{array}{ccc}
            \Asterisk & t_0 & t_1 \\
            t_0 & \Asterisk & t_2 \\
            t_1 & t_2 & \Asterisk 
        \end{array}
        \right),\,
    P_0 = \left(
        \begin{array}{ccc}
            0 & 1 & 2  \\
            3 & 4 & 5 \\
            6 & 7 & 8
        \end{array}
        \right),\,
    P_1 = \left(
        \begin{array}{ccc}
            0 & 3 & 6  \\
            1 & 4 & 7 \\
            2 & 5 & 8
        \end{array}
        \right)
        \label{eq:2P3}\\
L_{\mathcal{P},P_*}(I_2) = \begin{array}{c}
     (6,6,1,15) \textrm{ PDA} \\
\begin{sysmatrix}{cccccc}
             6 &  7 &  8 & \Asterisk & 0 & 1\\
             9 & 10 & 11 & 0 & \Asterisk & 2\\
            12 & 13 & 14 & 1 & 2 & \Asterisk\\
            \Asterisk & 3 & 4   & 6 & 9 & 12\\
            3 & \Asterisk & 5   & 7 & 10 & 13\\
            4 & 5 & \Asterisk   & 8 & 11 & 14 
\end{sysmatrix}
\end{array} 
\end{align}


{So far, we have seen constructions where we transform the elements of a PDA to achieve Blackburn compatibility. We will show that transformations can be applied at a block level to achieve the same.}
We now consider the case where $P_*$ is a tiling or block-concatenation of multiple PDAs. Specifically, for integers $g$ and $d$ with $d\mid g$, $P_*^{(g,d)}=B_{\tilde{I}_{2d}}(J_{g/d}([(g/d)^2]))$ (regular basic lifting from Corollary \ref{cor:basicreg}) is a $2g\times 2g$ PDA, which is a $g/d\times g/d$ block-concatenation of $\tilde{I}_{2d}(t)$, $t=1,\ldots,(g/d)^2$. In this case, we construct PDAs Blackburn-compatible w.r.t. $P_*^{(g,d)}$ block-wise with a combination of suitable transpositions and cyclic permutations.
\begin{lemma}[Construction BW1]\label{lm:bw1}
For positive integers $g$ and $d$ such that $d\mid g$, there exist 
a set $\mathcal{P}$ of $d$ $(2g,2g,1,g(2g-1))$ PDAs that are Blackburn compatible w.r.t $P_*^{(g,d)}=B_{\tilde{I}_{2d}}(J_{g/d}([(g/d)^2]))$ 
such that $L_{\mathcal{P},P_*^{(g,d)}}(I_{d})$ is a $2d$-regular $(2gd,2gd,2gd-3g+g/d+1,g(3g-g/d-1))$ PDA.
\end{lemma}
\begin{proof}
Consider the $2g\times 2g$ $2$-regular PDA $P_0=H_{2g}([g(2g-1)])$ with $\Asterisk$s along the diagonal. This PDA is partitioned into $2g/d\times 2g/d$ blocks $P_0^{(j,k)}$, $j,k\in[d]$ such that the diagonal blocks ($j=k$) are $2$-PDAs and others ($j\ne k$) are $1$-PDAs. Note that $P_0^{(j,k)}=(P_0^{(k,j)})^T$ when $j\ne k$. 

Construct $P_i$, $i=1,\ldots,d-1$, as a block-wise concatenation of $P_i^{(j,k)}$ defined as follows.
\begin{align*}
    P_i^{(j,k)}=\begin{cases}
    \pi_{AD,2}^i(P_0^{(j,j)}), & j=k,\\
    \pi_{AD,1}^{2i}(P_0^{(j,k)}), & j>k,\\
    (P_i^{(k,j)})^T, & j<k.
    \end{cases}
\end{align*}
We claim that $\mathcal{P}=\{P_0,\ldots,P_{d-1}\}$ is the desired set. Within $P_i$, Blackburn compatibility between $P_i^{(j,k)}$ and $P_i^{(k,j)}$ w.r.t. $P_i^{(j,j)}$ and $P_i^{(k,k)}$ is satisfied by Construction T1.
{An integer appearing in a diagonal block of $P_{i}$ will appear in a diagonal block of $P_{i'}$ whereas that appearing in a non-diagonal block will appear in two non-diagonal blocks of $P_{i'}$.}
Between $P_i$ and $P_{i'}$, Blackburn compatibility is satisfied for (1) diagonal blocks $\{P_i^{(j,j)},P_{i'}^{(j,j)}\}$ by Construction C2, (2) non-diagonal blocks $\{P_i^{(j,k)},P_{i'}^{(j,k)}\}$ by Construction C1, and (3) non-diagonal blocks $\{P_i^{(j,k)},P_{i'}^{(k,j)}\}$ by Construction T2. 
\end{proof}
\begin{example}
For $g=4$ and $d=2$ we have,
\begin{align*}
    P_* &= B_{\tilde{I}_4}(J_2[4]) = \left(\begin{array}{cccc:cccc}
\Asterisk & \Asterisk & \Asterisk & t_0 & \Asterisk & \Asterisk & \Asterisk & t_1 \\
\Asterisk & \Asterisk & t_0 & \Asterisk & \Asterisk & \Asterisk & t_1 & \Asterisk \\
\Asterisk & t_0 & \Asterisk & \Asterisk & \Asterisk & t_1 & \Asterisk & \Asterisk \\
t_0 & \Asterisk & \Asterisk & \Asterisk & t_1 & \Asterisk & \Asterisk & \Asterisk \\ \hdashline
\Asterisk & \Asterisk & \Asterisk & t_2 & \Asterisk & \Asterisk & \Asterisk & t_3 \\
\Asterisk & \Asterisk & t_2 & \Asterisk & \Asterisk & \Asterisk & t_3 & \Asterisk \\
\Asterisk & t_2 & \Asterisk & \Asterisk & \Asterisk & t_3 & \Asterisk & \Asterisk \\
t_2 & \Asterisk & \Asterisk & \Asterisk & t_3 & \Asterisk & \Asterisk & \Asterisk 
    \end{array}\right), 
\end{align*}
\begin{align*}
    P_0 &= 
{\left(\begin{array}{cc}
    P_0^{(0,0)} & P_0^{(0,1)} \\
    P_0^{(1,0)} & P_0^{(1,1)}
\end{array}\right)} =
\left(\begin{array}{cccc:cccc}
\Asterisk & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
0 & \Asterisk & 7 & 8 & 9 & 10 & 11 & 12 \\
1 & 7 & \Asterisk & 13 & 14 & 15 & 16 & 17 \\
2 & 8 & 13 & \Asterisk & 18 & 19 & 20 & 21 \\ \hdashline
3 & 9 & 14 & 18 & \Asterisk & 22 & 23 & 24 \\
4 & 10 & 15 & 19 & 22 & \Asterisk & 25 & 26 \\
5 & 11 & 16 & 20 & 23 & 25 & \Asterisk & 27 \\
6 & 12 & 17 & 21 & 24 & 26 & 27 & \Asterisk 
    \end{array}\right),\\ 
    P_1 &= 
{\left(\begin{array}{cc}
    \pi_{AD,2}(P_0^{(0,0)}) & (P_1^{(1,0)})^T \\
    \pi_{AD,1}^{2}(P_0^{(1,0)}) & \pi_{AD,2}(P_0^{(1,1)})
\end{array}\right)} =
\left(\begin{array}{cccc:cccc}
\Asterisk & 0 & 1 & 7 & 3 & 4 & 5 & 15 \\
0 & \Asterisk & 2 & 8 & 9 & 10 & 18 & 12 \\
1 & 2 & \Asterisk & 13 & 14 & 6 & 16 & 17 \\
7 & 8 & 13 & \Asterisk & 11 & 19 & 20 & 21 \\ \hdashline
3 & 9 & 14 & 11 & \Asterisk & 22 & 23 & 25 \\
4 & 10 & 6 & 19 & 22 & \Asterisk & 24 & 26 \\
5 & 18 & 16 & 20 & 23 & 24 & \Asterisk & 27 \\
15 & 12 & 17 & 21 & 25 & 26 & 27 & \Asterisk
    \end{array}\right) 
\end{align*}
The dashed lines show the block-wise construction. $\{P_0^{(j,j)},P_1^{(j,j)}\}$, $j=0,1$, satisfies Construction C2, while $\{P_0^{(j,1-j)},P_1^{(j,1-j)}\}$ satisfies Construction C1 and $\{P_0^{(j,1-j)},P_1^{(1-j,j)}\}$, $j=0,1$ satisfies Construction T2. 
\end{example}

In the previous construction, the blocks of $P_*$ were $\tilde{I}_g$, which has one integer per column. In the next block-wise construction, we will consider $P_*$ with diagonal blocks containing multiple integers per column and off-diagonal blocks as copies of $\tilde{I}_g$. 
This results in a higher integer density, and requires rotation of diagonal blocks in addition to the permutations employed in Lemma \ref{lm:bw1}. To describe $P_*$ precisely, we define a $2d\times 2d$ 2-PDA $T_{d^2}$ as follows:
\begin{equation}
    T_{d^2} = \begin{pmatrix}
    \tilde{I}_2(0)&\cdots&\tilde{I}_2(d-1)\\
    \tilde{I}_2(d)&\cdots&\tilde{I}_2(2d-1)\\
    \vdots&\vdots&\vdots\\
    \tilde{I}_2(d^2-d)&\cdots&\tilde{I}_2(d^2-1)
    \end{pmatrix},
\end{equation}
which can be alternatively defined as a basic regular lifting of the 1-PDA $J_d([d^2])$ by $\tilde{I}_2$, i.e. $T_{d^2}=B_{\tilde{I}_2}(J_d([d^2]))$. Cyclic rotations of the anti-diagonal of $T_{d^2}$ results in the set $\mathcal{T}_{d^2}=\{\pi_{AD,1}^{2i}(T_{d^2}):i\in[d]\}$ of $d$ PDAs, which are Blackburn-compatible w.r.t. $\tilde{I}_{2d}$ by an extension of Construction C1. 

For positive integers $g$, $d$ such that $d^2\mid g$, let $P_b^{(g,d^2)}=\begin{pmatrix}
I_d(0)&\cdots&\Asterisk_{d\times d}\\
\vdots&\ddots&\vdots\\
\Asterisk_{d\times d}&\cdots&I_d(g/d^2-1)
\end{pmatrix}$ be a $g/d\times g/d$ diagonal $d$-PDA.

$P_*^{(g,d^2)}={L}_{\mathcal{T}_{d^2},\tilde{I}_{2d}}(P_b^{(g,d^2)})$ is obtained by a general regular lifting (Corollary \ref{co:regularTiling}) of the $d$-PDA $P_b^{(g,d^2)}$ using the $d$ Blackburn-compatible PDAs in $\mathcal{T}_{d^2}$. The diagonal blocks of $P_*^{(g,d^2)}$ are 2-PDAs with $\Asterisk$s at the even diagonals, i.e. at $\{(i,j): i-j=0\mod 2\}$. Off-diagonal blocks of $P_*$ are $\tilde{I}_{2d}$, which has $\Asterisk$s at all even diagonals. For example, with $g=4$ and $d=2$, we get
\begin{align}
    P_*^{(4,2^2)} &= 
{\left(\begin{array}{cc}
    T_{d^2} & \tilde{I}_4(t_0) \\
    \tilde{I}_4(t_1) & \pi_{AD,1}^{2}(T_{d^2})
\end{array}\right)} =
\left(\begin{array}{cccc:cccc}
\Asterisk & t_2 & \Asterisk & t_4 & \Asterisk & \Asterisk & \Asterisk & t_0 \\
t_2 & \Asterisk & t_4 & \Asterisk & \Asterisk & \Asterisk & t_0 & \Asterisk \\
\Asterisk & t_3 & \Asterisk & t_5 & \Asterisk & t_0 & \Asterisk & \Asterisk \\
t_3 & \Asterisk & t_5 & \Asterisk & t_0 & \Asterisk & \Asterisk & \Asterisk \\ \hdashline
\Asterisk & \Asterisk & \Asterisk & t_1 & \Asterisk & t_2 & \Asterisk & t_3 \\
\Asterisk & \Asterisk & t_1 & \Asterisk & t_2 & \Asterisk & t_3 & \Asterisk \\
\Asterisk & t_1 & \Asterisk & \Asterisk & \Asterisk & t_4 & \Asterisk & t_5 \\
t_1 & \Asterisk & \Asterisk & \Asterisk & t_4 & \Asterisk & t_5 & \Asterisk
    \end{array}\right).
    \label{eq:Pstarg4d2}
\end{align}
\begin{lemma}[Construction BW2]\label{lm:bw2}
Let $g$ and $d$ be positive integers such that $d^2\mid g$. There exist a set $\mathcal{P}$ of $d$ $(2g,2g,1,g(2g-1))$ PDAs that are Blackburn-compatible w.r.t $P_*^{(g,d^2)}={L}_{\mathcal{T}_{d^2},\tilde{I}_{2d}}(P_b^{(g,d^2)})$, such that $L_{\mathcal{P},P_*}(I_{d})$ is a $2d$-regular $(2gd,2gd,2gd-3g+g/d+2d-d^2,g(3g-g/d-2d+d^2))$ PDA.
\end{lemma}
\begin{proof}
Consider the $2g\times 2g$ $2$-PDA $P_0$ defined in the proof of Lemma \ref{lm:bw1} and its $2g/d\times 2g/d$ blocks $P_0^{(j,k)}$, $j,k\in[d]$. Construct $P_i$, $i=0,\ldots,d-1$ as a blockwise concatenation of $P_i^{(j,k)}$ defined as follows.
\begin{align*}
    P_i^{(j,k)}=\begin{cases}
    \pi^i_{AD,2}(P_0^{(\tilde{j},\tilde{j})}), & j=k, \tilde{j}=j-i\text{ mod } d,\\
    \pi^{2i}_{AD,1}(P_0^{(j,k)}), & j>k\\
    (P_i^{(k,j)})^T, & j<k.
    \end{cases}
\end{align*}
The main difference, when compared to Construction BW1, is the rotation of the diagonal blocks.

We claim that $\mathcal{P}=\{P_0,\ldots,P_{d-1}\}$ is the desired set. Within $P_i$, Blackburn compatibility is satisfied by Construction T1. Between $P_i$ and $P_{i'}$, we consider the diagonal case and two off-diagonal cases separately: (1) Two diagonal blocks $P_i^{(j,j)}$ and $P_{i'}^{(j',j')}$ share the same set of integers only when $j\ne j'$, which means that the mirrored locations fall in an off-diagonal block $\tilde{I}_{2d}$ of $P_*$. So, by Construction C1, Blackburn compatibility is satisfied for diagonal blocks. (2) Two off-diagonal blocks $P_i^{(j,k)}$ and $P_{i'}^{(k,j)}$, $j\ne k$, share the same set of integers and have mirrored locations falling on diagonal blocks of $P_*$, which have $\Asterisk$s on all even diagonals. So, by Construction T2, Blackburn compatibility is satisfied. (3) Two off-diagonal blocks $P_i^{(j,k)}$ and $P_{i'}^{(j,k)}$, $j\ne k$, share the same set of integers, and the mirrored locations fall in an off-diagonal block $\tilde{I}_{2d}$ of $P_*$. So, by Construction C1, Blackburn compatibility is satisfied.
\end{proof}
\begin{example}
Let $g=4$ and $d=2$. $P_*$ is given in \eqref{eq:Pstarg4d2}.
\begin{align*}
    P_0 &= 
{\left(\begin{array}{cc}
    P_0^{(0,0)} & P_0^{(0,1)} \\
    P_0^{(1,0)} & P_0^{(1,1)}
\end{array}\right)} =
\left(\begin{array}{cccc:cccc}
\Asterisk & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
0 & \Asterisk & 7 & 8 & 9 & 10 & 11 & 12 \\
1 & 7 & \Asterisk & 13 & 14 & 15 & 16 & 17 \\
2 & 8 & 13 & \Asterisk & 18 & 19 & 20 & 21 \\ \hdashline
3 & 9 & 14 & 18 & \Asterisk & 22 & 23 & 24 \\
4 & 10 & 15 & 19 & 22 & \Asterisk & 25 & 26 \\
5 & 11 & 16 & 20 & 23 & 25 & \Asterisk & 27 \\
6 & 12 & 17 & 21 & 24 & 26 & 27 & \Asterisk 
    \end{array}\right),
\end{align*}
\begin{align*}
    P_1 &= 
{\left(\begin{array}{cc}
    \pi_{AD,2}(P_0^{(1,1)}) & (P_1^{(1,0)})^T \\
    \pi_{AD,1}^{2}(P_0^{(1,0)}) & \pi_{AD,2}(P_0^{(0,0)})
\end{array}\right)} =
\left(\begin{array}{cccc:cccc}
\Asterisk & 22 & 23 & 25 & 3 & 4 & 5 & 15 \\
22 & \Asterisk & 24 & 26 & 9 & 10 & 18 & 12 \\
23 & 24 & \Asterisk & 27 & 14 & 6 & 16 & 17 \\
25 & 26 & 27 & \Asterisk & 11 & 19 & 20 & 21 \\ \hdashline
3 & 9 & 14 & 11 & \Asterisk & 0 & 1 & 7 \\
4 & 10 & 6 & 19 & 0 & \Asterisk & 2 & 8 \\
5 & 18 & 16 & 20 & 1 & 2 & \Asterisk & 13 \\
15 & 12 & 17 & 21 & 7 & 8 & 13 & \Asterisk
    \end{array}\right).
\end{align*}
\end{example}
For the next blockwise construction, we consider $P_*=B_{H_{g/d}}(I_d)$ to be a $g\times g$ PDA constructed by basic lifting of $I_d$ using $H_{g/d}([\frac{g}{2d}(\frac{g}{d}-1)])$, for integers $g,d$ such that $d|g$. Therefore, it has $H_{g/d}$ repeated along the diagonal blocks and all-$\Asterisk$ blocks appearing in the off-diagonal blocks.

\begin{lemma}[Construction BW3]\label{lm:bw3}
For positive integers $g$ and $d$ such that $d\mid g$, there exist 
a set $\mathcal{P}$ of $d$ $2$-regular $(g,g,1,\allowbreak g(g-1)/2)$ PDAs that are Blackburn compatible w.r.t $P_*=B_{H_{g/d}}(I_{d})$
such that $L_{\mathcal{P},P_*}(I_d)$ is a $2d$-regular $(gd,gd,gd+d-2g+g/d,g(2g-d-g/d)/2)$ PDA.
\end{lemma}
\begin{proof}
Consider the $g\times g$ $2$-PDA $P_0=H_g([g(g-1)/2])$ and its $g/d\times g/d$ blocks $P_0^{(j,k)}$, $j,k\in[d]$. Construct $P_i$, $i=0,\ldots,d-1$ as a blockwise concatenation of $P_i^{(j,k)}$ defined as follows.
\begin{align*}
    P_i^{(j,k)}=\begin{cases}
    P_0^{(\tilde{j},\tilde{j})}, & j=k, \tilde{j}=j-i\text{ mod } d,\\
    P_0^{(j,k)}, & j\ne k.
    \end{cases}
\end{align*}
We claim that $\mathcal{P}=\{P_0,\ldots,P_{d-1}\}$ is the desired set, and skip the proof details, which are largely similar to the previous proof of Construction BW2.
\end{proof}
\begin{example}
Let $g=6$ and $d=2$.
\begin{align*}
    P_* &= 
{B_{H_{3}}(I_{2})} =
\left(\begin{array}{ccc:ccc}
\Asterisk & 0 & 1 & \Asterisk & \Asterisk & \Asterisk \\
0 & \Asterisk & 2 & \Asterisk & \Asterisk & \Asterisk \\
1 & 2 & \Asterisk & \Asterisk & \Asterisk & \Asterisk \\ \hdashline
\Asterisk & \Asterisk & \Asterisk & \Asterisk & 0 & 1 \\
\Asterisk & \Asterisk & \Asterisk & 0 & \Asterisk & 2 \\
\Asterisk & \Asterisk & \Asterisk & 1 & 2 & \Asterisk
    \end{array}\right),
\end{align*}
\begin{align*}
    P_0 &= 
{\left(\begin{array}{cc}
    P_0^{(0,0)} & P_0^{(0,1)} \\
    P_0^{(1,0)} & P_0^{(1,1)}
\end{array}\right)} =
\left(\begin{array}{ccc:ccc}
\Asterisk & 0 & 1 & 2 & 3 & 4 \\
0 & \Asterisk & 5 & 6 & 7 & 8 \\
1 & 5 & \Asterisk & 9 & 10 & 11 \\ \hdashline
2 & 6 & 9 & \Asterisk & 12 & 13 \\
3 & 7 & 10 & 12 & \Asterisk & 14 \\
4 & 8 & 11 & 13 & 14 & \Asterisk
    \end{array}\right),\\
    P_1 &= 
{\left(\begin{array}{cc}
    P_0^{(1,1)} & P_0^{(0,1)} \\
    P_0^{(1,0)} & P_0^{(0,0)}
\end{array}\right)} =
\left(\begin{array}{ccc:ccc}
\Asterisk & 12 & 13 & 2 & 3 & 4 \\
12 & \Asterisk & 14 & 6 & 7 & 8 \\
13 & 14 & \Asterisk & 9 & 10 & 11 \\ \hdashline
2 & 6 & 9 & \Asterisk & 0 & 1 \\
3 & 7 & 10 & 0 & \Asterisk & 5 \\
4 & 8 & 11 & 1 & 5 & \Asterisk 
    \end{array}\right).
\end{align*}
\end{example}
In the final block-wise construction, we will consider $P_*$ with diagonal blocks containing one $\Asterisk$ per column and off-diagonal blocks as copies of $\tilde{I}_g$. Letting $T=H_{2n}([n(2n-1)])$ be the $2n\times 2n$ 2-PDA as defined in Lemma \ref{lm:diagPDA}, we set
\begin{equation}
    P_*^{(n)}=\begin{pmatrix}
    T&\tilde{I}_{2n}(t_{0,1})&\ldots&\tilde{I}_{2n}(t_{0,n-1})\\
    \tilde{I}_{2n}(t_{1,0})&\pi_{AD,2}(T)&\ldots&\tilde{I}_{2n}(t_{1,n-1})\\
    \vdots&\vdots&\vdots&\vdots\\
    \tilde{I}_{2n}(t_{n-1,0})&\ldots&\tilde{I}_{2n}(t_{n-1,n-1})&\pi^{n-1}_{AD,2}(T)
    \end{pmatrix},
    \label{eq:Pstarn}
\end{equation}
where $t_{i,j}$ are integers. All the diagonal blocks of $P_*^{(n)}$ have $\Asterisk$s on the diagonals, all off-diagonal blocks have $\Asterisk$s on all even diagonals, and every column has $1+(n-1)(2n-1)=2n^2-3n+2$ $\Asterisk$s.

The construction of Blackburn-compatible PDAs is presented in the following Lemma.
\begin{lemma}\label{lm:bw4}
(Construction BW4) For an integer $n$, there exist a set $\mathcal{P}$ of $2n$ $(2n^2, 2n^2, 0, 4n^4)$ 1-PDAs that are Blackburn-compatible w.r.t. $P_*^{(n)}$ defined in \eqref{eq:Pstarn} such that  $L_{\mathcal{P},P_*^{(n)}}(I_{2n})$ is a $2n$-regular $(4n^3,4n^3,4n^3-8n^2+7n-2,2n^2(8n^2-7n+2))$ PDA.
\end{lemma}
\begin{proof}
Consider the $2n^2\times 2n^2$ 1-PDA $P_0$ defined as a blockwise concatenation of $2n\times 2n$ blocks. The $(j,k)$-th block, $j,k\in[n]$, $P_0^{(j,k)}=J_{2n}(S_{jk})$, where $S_{jk}=\{4n^2(nj+k),4n^2(nj+k+1)-1\}$ is a partition of the set $[4n^4]$ consisting of disjoint subsets of $4n^2$ consecutive integers.

Construct $P_i$, $i=1,\ldots,n-1$, as a blockwise concatenations of $2n\times 2n$ PDAs $P_i^{(j,k)}$, $j,k\in[n]$, defined as follows:
$$
P_i^{(j,k)} = \begin{cases}
\pi^2_{AD,1}(P_{i-1}^{(j-1\text{ mod }n,j-1\text{ mod }n)}),&j=k,\\
\pi^2_{AD,1}(P_{i-1}^{(j,k)}),&j\ne k.
\end{cases}
$$
When going from $P_{i-1}$ to $P_i$, a diagonal block is cyclically shifted down, and its anti-diagonal is cyclically shifted twice. An off-diagonal block has its anti-diagonal cyclically shifted twice.

Construct $\tilde{P}_i$, $i\in[n]$, as
$$\tilde{P}_i^{(j,k)} = \begin{cases}
(P_i^{(j,j)})^T,&j=k,\\
\pi_{AD,1}(P_i^{(j,k)}),&j\ne k.
\end{cases}$$
When going from $P_i$ to $\tilde{P}_i$, diagonal blocks are transposed. An off-diagonal block has its anti-diagonal cyclically shifted once.

We claim that $\mathcal{P}=\{P_0,\ldots,P_{n-1},\tilde{P}_0,\ldots,\tilde{P}_{n-1}\}$ is Blackburn-compatible w.r.t. $P_*^{(n)}$. To prove the claim, we will consider multiple cases where two blocks of the PDAs in $\mathcal{P}$ share integers. (1) $P_i^{(j,k)}$ and $P_{i'}^{(j,k)}$, $i\ne i'$, share integers if $j\ne k$. $P_i^{(j,j)}$ and $P_{i'}^{(j',j')}$, $i\ne i'$, share integers only if $j\ne j'$. In both cases, the mirrored locations are an off-diagonal block of $P_*$, which is $\tilde{I}_{2n}$. By Construction C1, Blackburn compatibility follows. The same argument holds when $P$ is replaced with $\tilde{P}$ in this case. (2) $P_i^{(j,j)}$ and $\tilde{P}_{i}^{(j,j)}$ share integers. Mirrored locations are on diagonal blocks of $P_*$, which have $\Asterisk$s on the diagonal. Blackburn compatibility follows by Construction T1. (3) $P_i^{(j,k)}$ and $\tilde{P}_{i'}^{(j,k)}$ share integers if $j\ne k$. $P_i^{(j,j)}$ and $\tilde{P}_{i'}^{(j',j')}$, $i\ne i'$, share integers only if $j\ne j'$. Mirrored locations are an off-diagonal block of $P_*$, which is $\tilde{I}_{2n}$. By Construction C1, Blackburn compatibility follows.  
\end{proof}

\begin{example}
For $n=2$, the following set of $8\times 8$ Blackburn PDAs can be constructed using BW4.
\begin{align*}
    P_* &= 
{\left(\begin{array}{cc}
    H_4([2,7]) & \tilde{I}_4(0) \\
    \tilde{I}_4(1) & \pi_{AD,2}(H_4([2,7]))
\end{array}\right)} =
\left(\begin{array}{cccc:cccc}
\Asterisk & 4 & 3 & 6 & \Asterisk & \Asterisk & \Asterisk & 0 \\
4 & \Asterisk & 2 & 5 & \Asterisk & \Asterisk & 0 & \Asterisk \\
3 & 2 & \Asterisk & 7 & \Asterisk & 0 & \Asterisk & \Asterisk \\
6 & 5 & 7 & \Asterisk & 0 & \Asterisk & \Asterisk & \Asterisk \\ \hdashline
\Asterisk & \Asterisk & \Asterisk & 1 & \Asterisk & 4 & 3 & 2 \\
\Asterisk & \Asterisk & 1 & \Asterisk & 4 & \Asterisk & 6 & 5 \\
\Asterisk & 1 & \Asterisk & \Asterisk & 3 & 6 & \Asterisk & 7 \\
1 & \Asterisk & \Asterisk & \Asterisk & 2 & 5 & 7 & \Asterisk 
    \end{array}\right)
\end{align*}
\begin{align*}
    P_0 &= 
{\left(\begin{array}{cc}
    P_0^{(0,0)} & P_0^{(0,1)} \\
    P_0^{(1,0)} & P_0^{(1,1)}
\end{array}\right)} =
\left(\begin{array}{cccc:cccc}
0 & 1 & 2 & 3 & 16 & 17 & 18 & 19 \\
4 & 5 & 6 & 7 & 20 & 21 & 22 & 23 \\
8 & 9 & 10 & 11 & 24 & 25 & 26 & 27 \\
12 & 13 & 14 & 15 & 28 & 29 & 30 & 31 \\ \hdashline
32 & 33 & 34 & 35 & 48 & 49 & 50 & 51 \\
36 & 37 & 38 & 39 & 52 & 53 & 54 & 55 \\
40 & 41 & 42 & 43 & 56 & 57 & 58 & 59 \\
44 & 45 & 46 & 47 & 60 & 61 & 62 & 63
    \end{array}\right),
\end{align*}
\begin{align*}
    \tilde{P}_0 &= 
{\left(\begin{array}{cc}
    (P_0^{(0,0)})^T & \pi_{AD,1}(P_0^{(0,1)}) \\
    \pi_{AD,1}(P_0^{(1,0)}) & (P_0^{(1,1)})^T
\end{array}\right)} =
\left(\begin{array}{cccc:cccc}
0 & 4 & 8 & 12 & 16 & 17 & 18 & 22 \\
1 & 5 & 9 & 13 & 20 & 21 & 25 & 23 \\
2 & 6 & 10 & 14 & 24 & 28 & 26 & 27 \\
3 & 7 & 11 & 15 & 19 & 29 & 30 & 31 \\ \hdashline
32 & 33 & 34 & 38 & 48 & 52 & 56 & 60 \\
36 & 37 & 41 & 39 & 49 & 53 & 57 & 61 \\
40 & 44 & 42 & 43 & 50 & 54 & 58 & 62 \\
35 & 45 & 46 & 47 & 51 & 55 & 59 & 63
    \end{array}\right),
\end{align*}
\begin{align*}
    P_1 &= 
{\left(\begin{array}{cc}
    \pi_{AD,1}^{2}(P_0^{(1,1)}) & \pi_{AD,1}^{2}(P_0^{(0,1)}) \\
    \pi_{AD,1}^{2}(P_0^{(1,0)}) & \pi_{AD,1}^{2}(P_0^{(0,0)})
\end{array}\right)} =
\left(\begin{array}{cccc:cccc}
48 & 49 & 50 & 57 & 16 & 17 & 18 & 25 \\
52 & 53 & 60 & 55 & 20 & 21 & 28 & 23 \\
56 & 51 & 58 & 59 & 24 & 19 & 26 & 27 \\
54 & 61 & 62 & 63 & 22 & 29 & 30 & 31 \\ \hdashline
32 & 33 & 34 & 41 & 0 & 1 & 2 & 9 \\
36 & 37 & 44 & 39 & 4 & 5 & 12 & 7 \\
40 & 35 & 42 & 43 & 8 & 3 & 10 & 11 \\
38 & 45 & 46 & 47 & 6 & 13 & 14 & 15
    \end{array}\right),
\end{align*}
\begin{align*}
    \tilde{P}_1 &= 
{\left(\begin{array}{cc}
    (P_1^{(0,0)})^T & \pi_{AD,1}(P_1^{(1,0)}) \\
    \pi_{AD,1}(P_1^{(1,0)}) & (P_1^{(1,1)})^T
\end{array}\right)} =
\left(\begin{array}{cccc:cccc}
48 & 52 & 56 & 54 & 16 & 17 & 18 & 28 \\
49 & 53 & 51 & 61 & 20 & 21 & 19 & 23 \\
50 & 60 & 58 & 62 & 24 & 22 & 26 & 27 \\
57 & 55 & 59 & 63 & 25 & 29 & 30 & 31 \\ \hdashline
32 & 33 & 34 & 44 & 0 & 4 & 8 & 6 \\
36 & 37 & 35 & 39 & 1 & 5 & 3 & 13 \\
40 & 38 & 42 & 43 & 2 & 12 & 10 & 14 \\
41 & 45 & 46 & 47 & 9 & 7 & 11 & 15
    \end{array}\right).
\end{align*}
\end{example}

\subsection{Tiling construction} 
The next lemma provides a tiling construction for regular Blackburn-compatible PDAs, and characterizes a tradeoff between the number of $\Asterisk$s per column and the number of integers.
\begin{lemma}[Tiling]\label{lm:BCboundZ}
For a positive integer $g$ and a divisor $d$ of $g$, there exists a set $\mathcal{P}$ of $d$ $(g,g,g-d,d^2)$ $(g/d)$-PDAs that are Blackburn compatible w.r.t. $I_g(t)$ (when $t$ does not appear in any PDA in $\mathcal{P}$). $L_{\mathcal{P},I_g}(I_d)$ is a $g$-regular $(dg,dg,dg-2d+1,d(2d-1))$ PDA.
\end{lemma}
\begin{proof}
Let $P_0,\ldots,P_{d-1}$ be $(d,d,0,d^2)$ $1$-PDAs Blackburn compatible w.r.t. $I_d(t)$ obtained using the first part of Lemma~\ref{lm:bc12pdas}. Each of these PDAs has $d$ integers per column.

Let $q=g/d$. Replace an integer $s$ in $P_i$ with $I_q(s)$ to obtain a $(g,g,g-d,d^2)$ $q$-PDA, which we denote as $\tilde{P}_i$. It is easy to see that $\tilde{\mathcal{P}}=\{\tilde{P}_0,\ldots,\tilde{P}_{d-1}\}$ is a set of PDAs Blackburn-compatible w.r.t. $I_g(t)$. 

$L\triangleq L_{\tilde{\mathcal{P}},I_g}(I_d)$ has $\tilde{P}_i$, $i=0,\ldots,d-1$, on the diagonal and $P_*=I_g$ as off-diagonal blocks. Each integer in $[d^2]$ occurs $q$ times in every $P_i$, which adds up to a total of $qd=g$ times in $L$. $I_g$, by definition, contains one integer appearing $g$ times. Each column of $L$ has $P_i$ with $d$ integers on the diagonal and $I_g$ with one integer on $d-1$ off-diagonal positions. So, each column has $d+d-1=2d-1$ integers, or $gd-(2d-1)$ $\Asterisk$s. So, we see that the parameters of $L$ are as claimed.
\end{proof}
The PDAs in the above lemma are visualized as ``tilings'' of the identity PDA as seen in the example below.
\begin{example}
Let $g=6$, $d=3$. Since $q=2$, we obtain the PDAs given below by lifting the Blackburn compatible PDAs from ~\eqref{eq:1gP3} with $I_2(t)$.
\begin{align}
\label{eq:2gP6}
    P_0 = \begin{pmatrix}
        I_2(0)&I_2(1)&I_2(2)\\
        I_2(3)&I_2(4)&I_2(5)\\
        I_2(6)&I_2(7)&I_2(8)
    \end{pmatrix},
    P_1 = \begin{pmatrix}
        I_2(8)&I_2(1)&I_2(2)\\
        I_2(3)&I_2(0)&I_2(5)\\
        I_2(6)&I_2(7)&I_2(4)
    \end{pmatrix},
    P_2 = \begin{pmatrix}
        I_2(4)&I_2(1)&I_2(2)\\
        I_2(3)&I_2(8)&I_2(5)\\
        I_2(6)&I_2(7)&I_2(0)
    \end{pmatrix}.
\end{align}
$L_{\{P_0,P_1,P_2\},I_6}(I_3)$ is an $(18,18,13,15)$ 6-PDA.
\end{example}
Using integer-disjoint copying, the $d$ PDAs obtained from Lemma \ref{lm:BCboundZ} can be replicated to obtain a set of $md$ $(g,g,g-d,d^2)$ $(g/d)$-PDAs. This idea is captured in the following corollary.
\begin{corollary}[Tiling]\label{cor:BCboundZ}
For positive integers $g,b$ and $d=\gcd(g,b)$, there exists a set $\mathcal{P}$ of $b$ $(g,g,g-d,d^2)$ $(g/d)$-PDAs that are Blackburn compatible w.r.t. $I_g(t)$ (when $t$ does not appear in any PDA in $\mathcal{P}$). $L_{\mathcal{P},I_g}(I_b)$ is a $g$-regular $(bg,bg,bg-b-d+1,b(b+d-1))$ PDA.
\end{corollary}
\begin{proof}
Obtain $d$ PDAs using Lemma \ref{lm:BCboundZ}. Since $b$ is a multiple of $d$, the $d$ PDAs can be replicated with disjoint sets of integers to obtain $b$ PDAs with the same parameters.

The parameters of $L_{\mathcal{P},I_g}(I_b)$ are easy to verify.
\end{proof}
\begin{example}
For $n=6$, $b=4$, we have $d=2$ and $q=3$. Using Lemma~\ref{lm:bc12pdas} obtain PDAs $Q_0'$ and $Q_1'$ which are Blackburn-compatible w.r.t. $I_2(t)$. Obtain $Q_2'$ and $Q_3'$ by replacing integers in $Q_0'$ and $Q_1'$ with a new disjoint set. Lift these PDAs using $I_3(t)$ to obtain the required set $\mathcal{Q}=\{Q_0,Q_1,Q_2,Q_3\}$ shown below.
 \begin{align}
\label{eq:4gP6}
    Q_0 = \begin{pmatrix}
        I_3(0)&I_3(1)\\
        I_3(2)&I_3(3)
    \end{pmatrix},
    Q_1 = \begin{pmatrix}
        I_3(3)&I_3(1)\\
        I_3(2)&I_3(0)
    \end{pmatrix},
    Q_2 = \begin{pmatrix}
        I_3(4)&I_3(5)\\
        I_3(6)&I_3(7)
    \end{pmatrix},
    Q_3 = \begin{pmatrix}
        I_3(7)&I_3(5)\\
        I_3(6)&I_3(4)
    \end{pmatrix}.
\end{align}
Note that $L(\mathcal{Q},I_6)$ is a 6-regular $(24,24,19,20)$ PDA.
\end{example}

\subsection{Recursive construction} 
Repeated application of lifting can result in larger Blackburn-compatible PDAs starting from small-sized base PDAs. The following lemma is an important step in such recursive constructions.
\begin{lemma}\label{lem:recursive}
    Let $\mathcal{P}=\{P_0,\dots,P_{g-1}\}$ be a set of $g$ $n\times n$ PDAs Blackburn compatible w.r.t. a PDA $P_*$ with $\mathcal{S}$ as its set of integers. For sets of disjoint integers $\mathcal{S}_j,j\in[g(g-1)]\cup \{t\}$, with $|\mathcal{S}_j|=|\mathcal{S}|$, let $P_*(\mathcal{S}_j)$ indicate the PDA constructed by replacing integers in $P_*$ with those in $\mathcal{S}_j$. Let $\pi(l)=(l+1)\;\text{mod}\;g$ be the cyclic shift permutation on $[g]$. For $i\in[g]$, let 
\begin{equation}
    P_{i}' = \left(\begin{array}{cccc}
        P_{\pi^i(1)} & P_*(\mathcal{S}_0) & \dots & P_*(\mathcal{S}_{g-2})  \\
        P_*(\mathcal{S}_{g-1}) & P_{\pi^i(2)} & \dots & P_*(\mathcal{S}_{2g-3})\\
        \vdots & & \ddots & \vdots \\
        P_*(\mathcal{S}_{(g-1)^2}) &  & \dots & P_{\pi^i(g)}
    \end{array}\right),\quad
    P_{\Asterisk}' = \left(\begin{array}{cccc}
        P_*(\mathcal{S}_t) & \Asterisk_{n\times n} & \dots & \Asterisk_{n\times n} \\
        \Asterisk_{n\times n} & P_*(\mathcal{S}_t) & \dots & \Asterisk_{n\times n} \\
        \vdots &  & \ddots & \vdots \\
        \Asterisk_{n\times n} & \Asterisk_{n\times n} & \dots & P_*(\mathcal{S}_t)
    \end{array}\right).
\label{eq:recursive}
\end{equation}
Then, $\mathcal{P}'=\{P'_0,\ldots,P'_{g-1}\}$ is a set of $g$ $ng\times ng$ PDAs  Blackburn-compatible w.r.t. $P'_{\Asterisk}$. If $L_{\mathcal{P},P_*}(I_g)$ is a $g_b$-regular $ng\times ng$ PDA, then $L_{\mathcal{P}',P'_*}(I_g)$ is a $gg_b$-regular $ng^2\times ng^2$ PDA.
\end{lemma}
\begin{proof}
A $P_*(S_j)$ block appears off-diagonal at the same location in all $P'_i$. This does not violate Blackburn compatibility w.r.t. $P'_*$, which has all-$\Asterisk$ arrays as off-diagonal blocks.  

A block that appears in the diagonal of $P_i'$ at its $k$-th position will be $P_{\pi^i(k)}$ and that of $P_j'$ will be  $P_{\pi^j(k)}$. Since $\pi^i(k)\ne \pi^j(k)$ for $i\ne j$, these blocks do not violate Blackburn compatibility with $P'_*$.

Finally, we prove the regularity claim. If $L_{\mathcal{P}}(I_g(s))$ is $g_b$-regular, then $P_*(\mathcal{S})$ is $g_b$-regular, and so is $P_*(\mathcal{S}_i)$ for every $i$. So, $P'_*$ is $gg_b$-regular, which implies that $L_{\mathcal{P}'}(I_g(s))$ is $gg_b$-regular in the off-diagonal blocks. Since every $P'_i$ is a diagonal-block-permuted version of $L_{\mathcal{P}}(I_g(s))$, $P'_i$ (which is a diagonal block in $L_{\mathcal{P}'}(I_g(s))$) is $g_b$-regular as well. Since the same set of integers appear in every $P'_i$, the diagonal blocks of $L_{\mathcal{P}'}(I_g(s))$ together are $gg_b$-regular.  
\end{proof}
We will now illustrate how to apply the above lemma repeatedly to construct larger PDAs. Consider the two $1$-PDAs, denoted $A_2(x)$ and $A'_2(x)$, which are Blackburn-compatible w.r.t. $I_2(t)$ for $t\notin\{x,x+1,x+2,x+3\}$ and obtained using Lemma \ref{lm:bc12pdas} (first part) for $n=2$. They are given by
\begin{equation}
    A_{2}(x) = \left(\begin{array}{cc}
        x & x+1 \\
        x+2 & x+3
    \end{array}\right),
    \,
    A_{2}'(x) = \left(\begin{array}{cc}
        x+3 & x+1 \\
        x+2 & x
    \end{array}\right).\label{eq:A2}
\end{equation}
\begin{lemma}\label{lem:A2r_compatibility}
Consider the following $2^r \times 2^r$ PDAs for $r> 1$.
\begin{equation}
\resizebox{.9\hsize}{!}{
    $A_{2^r}(x) = \left(\begin{array}{cc}
        I_{2^{r-1}}(x) & A_{2^{r-1}}(x+2) \\
        A_{2^{r-1}}'(x+2) & I_{2^{r-1}}(x+1) 
    \end{array}\right),
    \,
    A_{2^r}'(x) = \left(\begin{array}{cc}
        I_{2^{r-1}}(x+1) & A_{2^{r-1}}(x+2) \\
        A_{2^{r-1}}'(x+2) & I_{2^{r-1}}(x) 
    \end{array}\right)$,}\label{eq:A2r}
\end{equation} 
where $A_2(x)$ and $A_2'(x)$ are as defined in \eqref{eq:A2}. Let $\mathcal{S}$ be the set of integers in $A_{2^r}(x)$ and $A_{2^r}'(x)$. For $r\ge 1$ and $t \not\in \mathcal{S}$, $\mathcal{A}=\{A_{2^r}(x),A_{2^r}'(x)\}$ is a set of two Blackburn-compatible PDAs w.r.t. $I_{2^r}(t)$, and $L_{\mathcal{A}}(I_2(s))$ is a $2^r$-regular $(2^{r+1},2^{r+1},2^{r+1}-r-2,2r+4)$ PDA.
\end{lemma}
\begin{proof}
Start with $P_*=I_2$, $P_2=A_2(x)$, $P_1=A_2'(x)$ and apply Lemma~\ref{lem:recursive} $(r-1)$ times recursively.
\end{proof}

{A summary of the above constructions is given in Table~\ref{tab:summary}.} The final parameters of a lifted PDA can be calculated using Corollary~\ref{cor:genreg}.
\afterpage{%
    \clearpage%
    \thispagestyle{empty}%
    \begin{landscape}%
        \centering %
\vspace*{\fill}
        \captionof{table}{Summary of constructions of Blackburn compatible PDAs.}\label{tab:summary}
\begin{adjustbox}{max width=\linewidth}
\hspace{-1.5cm}
\begin{tabular}{cccccccccccccc}
    \toprule
    {\textbf{Construction}} & {\textbf{Condition}} & {\textbf{$g_b$}} & {\textbf{$K_c$}} & {\textbf{$f_c$}} & {\textbf{$P_i$}} & $Z_i$ & $S_i$ & $g_i$ & {\textbf{$P_*$}} & $Z_*$ & $S_*$ & $g_*$ \\ \midrule
    C1 &  & $g$ & $g$ & $g$ & $\pi_{D,1}^{i}(J_g([g^2])), i\in [g]$ & $0$ & $g^2$ & $1$ & $I_g(t)$ & $g-1$ & $1$ & $g$ \\\\ 
    C2 &  & $g$ & $2g$ & $2g$ & $\pi_{D,2}^{i}(G_{2g}([g(2g-1)])), i\in [g]$ & $1$ & $g(2g-1)$ & $2$ & $I_{2g}(t)$ & $2g-1$ & $1$ & $2g$ \\\\
    T1 &  & $2$ & $g$ & $g$ & $\{J_g([g^2],J_g([g^2]^T)\}$ & $0$ & $g^2$ & $1$ & $H_g([\frac{g(g-1)}{2}])$ & $1$ & $\frac{g(g-1)}{2}$ & $2$ \\\\ 
    T2 &  & $2$ & $g$ & $g$ \\\\
    BW1 & $d|g$ & $d$ & $2g$ & $2g$ & \makecell[c]{$P_0=H_{2g}([g(2g-1)])$\\$P_i^{(j,k)}=\begin{cases}
    \pi_{AD,2}^i(P_0^{(j,j)}), & j=k,\\
    \pi_{AD,1}^{2i}(P_0^{(j,k)}), & j>k,\\
    (P_i^{(k,j)})^T, & j<k.
    \end{cases}$\\where $i\in[d]\setminus \{0\}$ and $j,k\in[d]$} & $1$ & $g(2g-1)$ & $2$ & $B_{\tilde{I}_{2d}}(J_{g/d})$ & $2g-\frac{g}{d}$ & $(\frac{g}{d})^2$ & $2d$ \\\\ 
    BW2 & $d^2|g$ & $d$ & $2g$ & $2g$ & \makecell[c]{$P_0=H_{2g}([g(2g-1)])$\\$P_i^{(j,k)}=\begin{cases}
    \pi^i_{AD,2}(P_0^{(\tilde{j},\tilde{j})}), & j=k, \tilde{j}=j-i\text{ mod } d,\\
    \pi^{2i}_{AD,1}(P_0^{(j,k)}), & j>k\\
    (P_i^{(k,j)})^T, & j<k.
    \end{cases}$\\where $i\in[d]\setminus \{0\}$ and $j,k\in[d]$} & $1$ & $g(2g-1)$ & $2$ & ${L}_{\mathcal{T}_{d^2},\tilde{I}_{2d}}(P_b^{(g,d^2)})$ & $2g-\frac{g}{d}-d+1$ & $\frac{g}{d}(\frac{g}{d}+d-1)$ & $2d$ \\\\
    BW3 & $d|g$ & $d$ & $g$ & $g$ & \makecell[c]{$P_0=H_g([g(g-1)/2])$\\$P_i^{(j,k)}=\begin{cases}
    P_0^{(\tilde{j},\tilde{j})}, & j=k, \tilde{j}=j-i\text{ mod } d,\\
    P_0^{(j,k)}, & j\ne k.
    \end{cases}$\\where $i\in[d]\setminus \{0\}$ and $j,k\in[d]$} & $1$ & $\frac{g(g-1)}{2}$ & $2$ & $B_{H_{g/d}}(I_{d})$ & $g+1-\frac{g}{d}$ & $\frac{g}{2d}(\frac{g}{d}-1)$ & $2d$ \\\\ 
    BW4 &  & $2n$ & $2n^2$ & $2n^2$ & \makecell[c]{$P_0=J_{2n^2}([4n^4])$\\$P_i^{(j,k)} = \begin{cases}
\pi^2_{AD,1}(P_{i-1}^{(j-1\text{ mod }n,j-1\text{ mod }n)}),&j=k,\\
\pi^2_{AD,1}(P_{i-1}^{(j,k)}),&j\ne k.
\end{cases}$\\$\tilde{P}_i^{(j,k)} = \begin{cases}
(P_i^{(j,j)})^T,&j=k,\\
\pi_{AD,1}(P_i^{(j,k)}),&j\ne k.
\end{cases}$\\where $i\in[n]\setminus \{0\}$ and $j,k\in[n]$} & $0$ & $4n^4$ & $1$ & ${L}_{\{\pi^{i}_{AD,2}(H_{2n}): i\in[n]\},\tilde{I}_{2n}}(I_n)$ & $2n^2-3n+2$ & $n(3n-2)$ & $2n$ \\\\
Tiling & $d|g$ & $d$ & $g$ & $g$ & $B_{I_{g/d}}(\pi_{D,1}^{i}(J_d)), i\in [d]$ & $g-d$ & $d^2$ & $\frac{g}{d}$ & $I_g(t)$ & $g-1$ & $1$ & $g$ \\\\
$2^r$-lifting & & $2$ & $2^r$ & $2^r$ & $\{A_{2^r}(x),A_{2^r}'(x)\}$ & $2^r-r-1$ & $2+2r$ & $2^{r-1}$ & $I_{2^r}(t)$ & $2^r-1$ & $1$ & $2^r$ \\
\bottomrule
\end{tabular}
\end{adjustbox}
\vspace*{\fill}
    \end{landscape}
    \clearpage
}

\subsection{Randomized construction}
For positive integers $b$, $r$, $e$, $\alpha$ and $\eta$, we propose a randomised algorithm $\text{RandBC}^{b,r}_{e,\alpha,\eta}$ that, when successful, will construct $\eta r \times \alpha r$ PDAs $P_i$, $i=0,\ldots,b-1$, satisfying the following conditions:
\begin{itemize}
    \item every $P_i$ contains $e$ $\Asterisk$s per column,
    \item the set $\{P_0,\ldots,P_{b-1}\}$ is Blackburn-compatible w.r.t. $P_*=\begin{pmatrix}
        I_r(t_{1,1})&\cdots&I_r(t_{1,\alpha})\\
        \vdots&\ddots&\vdots\\
        I_r(t_{\eta,1})&\cdots&I_r(t_{\eta,\alpha})
    \end{pmatrix}$, where $t_{j,k}$ are integers not occurring in the $P_i$'s,
    \item $L_{\{P_0,\ldots,P_{b-1}\},P_*}(I_b)$ is $r$-regular.
\end{itemize}
 A psuedocode for the random construction is given in Algorithm~\ref{alg:random}. 
\begin{algorithm}[H]
\caption{$\text{RandBC}^{b,r}_{e,\alpha,\eta}$}\label{alg:random}
\begin{algorithmic}[1]
\State \textbf{function} CHECK($[P_i]_{x,y}\gets v$): \textbf{return} TRUE, \textbf{if} setting $(x,y)$-th position of $P_i$ as $v$ does not violate PDA, number of $\Asterisk$s per column and Blackburn compatibility conditions, \textbf{else} \textbf{return} FALSE 
\State \textbf{define} $\text{FREE}(P_i,v)=\{(x,y): [P_i]_{x,y}=\Asterisk, \text{CHECK}([P_i]_{x,y}\gets v)=\text{TRUE}\}$ 
\State $P_i\gets$ all-$\Asterisk$ for all $i$, $s\gets b\alpha(\eta r-e)$ ($s$: number of integers occurring in all $P_i$)
\State $i=0$ (start with $P_0$)
\For{$v\in\{1,\ldots,s\}$}
    \Loop $\ r$ times
        \State \textbf{if} $\text{FREE}(P_i,v)$ is empty \textbf{then} declare FAILURE and \textbf{exit}
        \State For $(x,y)\in \text{FREE}(P_i,v)$, $\text{PENALTY}(x,y)=N_r+N_c+w_r+w_c$, where (1) $N_r$ and $N_c$ are the number of rows and columns of all other $P_j$, $j\ne i$, invalidated under Blackburn compatibility by setting $(x,y)$-th position of $P_i$ as $v$, respectively, (2) $w_r$ and $w_c$ are the number of integers in the $x$-th row and $y$-th column of $P_i$, respectively. 
        \State $(x^*,y^*)=\arg\min_{(x,y)\in \text{FREE}(P_i,v)}\text{PENALTY}(x,y)$ (if multiple, pick one at random)
        \State Set $[P_i]_{x^*,y^*}\gets v$, Move to next $i=i+1\mod b$
    \EndLoop
\EndFor
\end{algorithmic}
\end{algorithm}
The algorithm cycles through the $P_i$, starting with $P_0$, and adds integer $v$, one at a time, starting with $v=1$. Each integer is added $r$ times. Free locations for adding $v$ in $P_i$ are identified, and a penalty term is calculated for each free location. The penalty tends to favour locations that minimize ``wasting" of cells in other $P_j$, $j\ne i$, and those that improve column and row spread of the integers in $P_i$. If no free locations are found at any point, the algorithm fails. Since all conditions are maintained throughout, the algorithm outputs the required PDAs, if successful.

Results of successful runs of $\text{RandBC}^{b,r}_{e,\alpha,\eta}$ are given in Table \ref{tab:rndres}.

\begin{table}[hbt]
    \centering
    \caption{Examples of successful random generation of $b$ $\eta r\times\alpha r$ PDAs with $e$ $\Asterisk$s per column in each PDA and each integer occurring $r$ times across all PDAs.}
    \label{tab:rndres}
    \begin{tabular}{|c|c|c|c|}
    \hline
        $\eta$ & $\alpha$ & $(r,e)$               & $b$  \\
        \hline
1 & 1 & \makecell[c]{(3,2), (4,1), (5,3), (6,4), (8,5), (10,8), (12,9), (15,14), (16,14),\\(20,18), (25,24), (30,28), (32,30), (50,48), (125,124)} & 2 \\ 
1 & 1 & (4,2), (5,3), (8,6), (10,8), (20,18), (25,23), (50,49) & 3 \\ 
1 & 1 & (3,0), (4,0), (5,0), (6,3), (10,6), (12,9), (25,22) & 5 \\ 
1 & 1 & (3,1), (5,1), (6,1), (25,21) & 10 \\ 
1 & 1 & (3,2) & 20 \\ 
1 & 1 & (5,1) & 50 \\ \hline 
2 & 1 & (5,6), (10,16), (25,47), (125,248) & 2 \\ 
2 & 1 & (5,5), (10,15), (25,46), (50,98) & 3 \\ 
2 & 1 & (5,1), (10,11), (25,44), (50,98) & 5 \\ 
2 & 1 & (5,2), (25,42) & 10 \\ 
2 & 1 & (5,4), (10,12) & 25 \\ 
2 & 1 & (5,1) & 50 \\ \hline 
4 & 1 & (5,12), (10,32), (25,96), (50,196), (125,496) & 2 \\ 
4 & 1 & (5,2), (10,21), (25,89), (50,194) & 5 \\ 
4 & 1 & (5,3), (25,83) & 10 \\ 
4 & 1 & (5,8), (10,21) & 25 \\ 
4 & 1 & (5,2) & 50 \\        \hline
    \end{tabular}
\end{table}
From the table, we observe that the randomized algorithm succeeds for a wide range of parameters of interest.
\section{2-regular PDAs}\label{sec:construction}
In this section, we will present some methods for constructing 2-regular PDAs.
Most of these constructions are direct and, in some cases, they are special cases of other known constructions. We include them here for reference as we use them later as ingredients in lifting constructions.

We will consider $(n,n,Z,\mathcal{S})$-PDAs that are $2$-regular. The corresponding $(K,N;M,R)$ coded caching scheme can have arbitrary number of files $N$, $K=n$ users, $M=(NZ/n)$, and the rate $R=(n-Z)/2$ (using Eq.~\eqref{eq:regularPdaRate}). 
We begin with a direct construction of a $2$-regular PDA corresponding to the Maddah-Ali-Niesen scheme \cite{niesen2016coded} for $t=\frac{KM}{N}=1$. 
\begin{lemma}[Dense 2-regular PDAs]\label{lm:diagPDA}
For an integer $n \geq 2$, there exists a $2$-regular $(n,n,1,n(n-1)/2)$ PDA.
\end{lemma}
\begin{proof}
Take an $n \times n$ array. Set all diagonal (or anti-diagonal) entries to $\Asterisk$. There are $S=n(n-1)/2$ cells below the diagonal. Fill them with the integers from 0 to $S-1$. Symmetrically fill the cells above the diagonal. 
\end{proof}
For a set $\mathcal{S}=\{s_1\,\ldots,s_{n(n-1)/2}\}$ of $n(n-1)/2$ integers, we let $G_n(\mathcal{S})$ and $H_n(\mathcal{S)}$ denote the $(n,n,1,\mathcal{S})$ PDAs obtained using Lemma \ref{lm:diagPDA} with anti-diagonal and diagonal cells set as $\Asterisk$, respectively. The integers in $\mathcal{S}$ are arranged row-wise in the specified order above the anti-diagonal in $G_n(\mathcal{S})$ or below the diagonal in $H_n(\mathcal{S})$. For example,
    \begin{align}
    G_3(\{4,6,5\})=\begin{pmatrix}
    4  & 6  & \Asterisk \\
    5  & \Asterisk & 6  \\
    \Asterisk & 5  & 4
    \end{pmatrix}, G_3(\{6,4,5\})=\begin{pmatrix}
    6  & 4  & \Asterisk \\
    5  & \Asterisk & 4  \\
    \Asterisk & 5  & 6
    \end{pmatrix},
    H_3(\{3,2,1\})=\begin{pmatrix}
    \Asterisk & 3 & 2 \\
    3 & \Asterisk & 1 \\
    2 & 1 & \Asterisk
    \end{pmatrix}.\label{eq:GS}
    \end{align}

We now provide methods to modify a 2-regular PDA $P$ from Lemma \ref{lm:diagPDA} to lower $|\mathcal{S}|$, while retaining regularity of 2. The basic idea is to replace integers in $P$ with $\Asterisk$ without affecting regularity. 
For this purpose, given a 2-regular $(n,n,Z,\mathcal{S})$ PDA $P$ with rows/columns indexed from 0 to $n-1$ and $s\in \mathcal{S}$ at locations $(i_1(s),j_1(s))$ and $(i_2(s),j_2(s))$, we associate a graph $G(P)=(V,E)$ with vertex set $V=\{0,1,\ldots,n{-}1\}$ representing the columns of $P$ and edge set $E=\{(j_2(s),j_1(s)):s\in S\}$. We refer the reader to \cite{Harary1969} for definitions and basic results in graph theory. The edge $e(s)=(j_2(s),j_1(s))\in E$ is labelled with the triple $(i_1(s),i_2(s),s)$. For a symmetric PDA $P$ (such as the one from Lemma \ref{lm:diagPDA}), since $i_2(s)=j_1(s)$ and $j_2(s)=i_1(s)$, we have $e(s)=(i_1(s),j_1(s))$ and the edge label is shortened to $s$.
\begin{lemma}
Let $P$ be the 2-regular $(n,n,1,n(n-1)/2)$ PDA from Lemma \ref{lm:diagPDA}. Then, the associated graph $G(P)$ is equal to $K_n$, the complete graph on $n$ vertices.
\label{lem:completegraphPDA}
\end{lemma}
\begin{proof}
By symmetry, the first column of $P$ is equal to the first row, if diagonal is set to $\Asterisk$, or {the reverse of} the last row, if anti-diagonal is set to $\Asterisk$. So, in $G(P)$, vertex 1 is connected to all other vertices $\ge 2$.
Now, delete the first column and its corresponding first or last symmetric row, and see that vertex 2 is connected to vertices $\ge 3$. Proceed iteratively to complete the proof.
\end{proof}
A spanning subgraph has the same vertex set as the original graph and a subset of its edges with no isolated vertices. A graph or subgraph is said to be $r$-regular if every vertex has degree equal to $r$. An $r$-regular spanning subgraph is very useful for modifying PDAs as shown in the following lemma. 
\begin{theorem}
Consider a 2-regular $(n,n,z,\mathcal{S})$ PDA $P$ with associated graph $G(P)$. Suppose $G(P)$ has an $r$-regular spanning subgraph with its $nr/2$ edges being $\{e(s):s\in \mathcal{S}_r\}$, where $\mathcal{S}_r\subset\mathcal{S}$. The array obtained by setting $s\in\mathcal{S}_r$ as $\Asterisk$ in $P$ is a 2-regular $(n,n,z+r,\mathcal{S}\setminus\mathcal{S}_r)$ PDA.
\label{lem:rregular}
\end{theorem}
\begin{proof}
Since the subgraph is spanning and $r$-regular, exactly $r$ integers in $\mathcal{S}_r$ are present in each column of $P$. Setting the integers in $\mathcal{S}_r$ to $\Asterisk$ results in the modified PDA as claimed.
\end{proof}
To find regular spanning subgraphs, the notions of 1-factors and 1-factorization are useful \cite{wallis2013one}. A matching in a graph is a set of non-intersecting (or parallel) edges. A matching is said to be a 1-factor if it covers all vertices. A 1-factor is clearly a 1-regular spanning subgraph.

A complete graph $K_n$, for $n$ even, has multiple 1-factors each with $n/2$ edges \cite{wallis2013one}. A 1-factorization of $K_n$, $n$ even, is a partition of its $n(n{-}1)/2$ edges into $n{-}1$ edge-disjoint 1-factors. It is well known that 1-factorizations exist for $K_n$ when $n$ is even \cite{factorizationsurvey85}. The union of $r$ different 1-factors in a 1-factorization is clearly an $r$-regular spanning subgraph of $K_n$, which can be used in Lemma \ref{lem:rregular} as follows.
\begin{corollary}
Let $P$ be the 2-regular $(n,n,1,n(n{-}1)/2)$ PDA from Lemma \ref{lm:diagPDA} with associated graph $K_n$, $n$ even. Let $\{M_1,M_2,\ldots,M_{n-1}\}$ be a 1-factorization of $K_n$ with the $i$-th 1-factor $M_i=\{e(s_{ij}): j\in\{1,2,\ldots,n/2\}\}$. For $z\in\{1,2,\ldots,n{-}2\}$, let $P_z$ be the array obtained by setting $s_{ij}$ to $\Asterisk$ in $P$ for $1\le i\le z$ and $j\in\{1,2,\ldots,n/2\}$. Then, $P_z$ is a 2-regular $(n,n,z+1,n(n{-}z{-}1)/2)$ PDA. 
\label{lem:modify_even}
\end{corollary}
\begin{proof}
Since $M_1\cup M_2\cup\cdots\cup M_z$ is a $z$-regular spanning subgraph of $K_n$, the result follows by the use of Lemma \ref{lem:rregular}.
\end{proof}
For $n=4$, consider the $(4,4,1,6)$ PDA $H_4([6])$. A 1-factorization for the associated graph is $M_1=\{e(0),e(5)\}$, $M_2=\{e(1),e(4)\}$, $M_3=\{e(2),e(3)\}$ as shown in Fig.~\ref{fig:pda_graph}. The modified PDAs obtained using this 1-factorization in Lemma \ref{lem:modify_even} are easy to write down.
\begin{figure}
    \centering
    \includegraphics{figures/fig_2a_pda_graph.pdf}
    \caption{A 1-factorization of the graph associated with the $(4,4,1,6)$ PDA $H_4([6])$.}
    \label{fig:pda_graph}
\end{figure}
For $n$ odd, there are no 1-factors in $K_n$, and the smallest regular spanning subgraph is a Hamiltonian cycle, which is a cycle with $n$ edges passing through all $n$ vertices \cite{Harary1969}. It is well-known that $K_n$ for $n$ odd can be decomposed into $(n-1)/2$ edge-disjoint Hamiltonian cycles \cite{wallis2013one,AlspachWalecki08}. This decomposition leads to the following lemma.
\begin{corollary}
Let $P$ be the 2-regular $(n,n,1,n(n{-}1)/2)$ PDA from Lemma \ref{lm:diagPDA} with associated graph $K_n$, $n$ odd. Let $\{H_1, H_2,\allowbreak \ldots, H_{(n-1)/2}\}$ be a set of edge-disjoint Hamiltonian cycles of $K_n$ with $H_i=\{e(s_{ij}): j\in\{1,2,\ldots,n\}\}$. For $z\in\{1,2,\ldots,(n{-}3)/2\}$, let $P_z$ be the array obtained by setting $s_{ij}$ to $\Asterisk$ in $P$ for $1\le i\le z$ and $j\in\{1,2,\ldots,n\}$. Then, $P_z$ is a 2-regular $(n,n,2z+1,n(n{-}2z{-}1)/2)$ PDA.
\label{lem:modify_odd}
\end{corollary}
\begin{proof}
Since $H_1\cup H_2\cup\cdots\cup H_z$ is a $2z$-regular spanning subgraph of $K_n$, the result follows by the use of Lemma \ref{lem:rregular}.
\end{proof}
For $n=5$, consider the $(5,5,1,10)$ PDA in $H_5([10])$. A Hamiltonian cycle decomposition for the associated graph is $H_1=\{e(0),e(1),e(5),e(6),e(7)\}$,  $H_2=\{e(2),e(8),e(9),e(4),e(3)\}$. The modified PDAs obtained using this decomposition in Cor.~\ref{lem:modify_odd} are easy to write down.

We remark that the cache memory versus rate trade-off obtained by the 2-PDAs of Corollaries \ref{lem:modify_even} and \ref{lem:modify_odd} are the same as those obtained by memory-sharing between the full-storage scheme corresponding to the all-$\Asterisk$ $(n,n,n,0)$ PDA and the $(n,n,1,n(n-1)/2)$ PDA of Lemma \ref{lm:diagPDA}. However, explicit 2-PDAs that achieve the same trade-off without memory-sharing have not appeared earlier in the literature. In addition, the connection between PDAs and graphs appears to be new as well, and this connection could possibly lead to some interesting generalizations.
\section{Preliminaries}\label{sec:ps}
\subsection{Coded caching}
Consider a server, holding $N$ files $W_i$, $i\in[N]=\{0,1,\ldots, N-1\}$, of $F$ bits each, connected to $K$ users via a multicast link. 
User $k$, $k\in [K]$, has a cache $Z_k$ of size $MF$ bits.
Coded caching works in two phases. In the first phase, called the \textit{placement phase}, the cache $Z_k$ of User $k$ is populated with content by the server, while being unaware of the files demanded by the users. 
In the second phase, called the \textit{delivery phase}, User $k$ demands file $D_k \in [N]$ from the server.
Let $\boldsymbol{D}= (D_0, D_1, \ldots, D_{K-1})$. 
Based on the demands and stored cache contents, the server multicasts packets of the same size.
The entire multicast transmission from the server is denoted $X^{\boldsymbol{D}}$ for a demand vector $\boldsymbol{D}$, and we suppose that the length of $X^{\boldsymbol{D}}$ is $RF$ bits. 
The quantities $M$ and $R$ are measures of cache size and rate of transmission, respectively. 

The main requirement in a coded caching scheme is that User~$k$ should be able to decode the file $W_{D_k}$ using $Z_k$ and $X^{\boldsymbol{D}}$. 
We denote a coded caching scheme with $K$ users, $N$ files, local cache size $M$, and rate $R$ as a $(K,N;M,R)$ coded caching scheme, or as a $(K,N)$ scheme.

\subsection{Coded caching schemes from PDAs}
We use the framework of placement delivery arrays for centralized coded caching schemes \cite{yan2017placement}. 
For positive integers $K$, $f$, $Z$ and a set of integers $\mathcal{S}$, a $(K, f, Z, \mathcal{S})$ \textit{placement delivery array} is an $f\times K $ matrix  $P=[p_{j,k}]$, $j\in[f],k\in[K]$, containing either a ``$\Asterisk$'' or integers from $\mathcal{S}$ in each array cell such that they satisfy the following conditions.
\begin{enumerate}[label=C\arabic*., ref=C\arabic*]
    \item The symbol $\Asterisk$ appears $Z$ times in each column.\label{cond:equalZ}
    \item Each integer $s\in \mathcal{S}$ occurs at least once in the array.\label{cond:everysOnce}
    \item (Blackburn property) If the entries in two distinct cells $p_{j_1,k_1}$ and $p_{j_2,k_2}$ are the same integer $s\in\mathcal{S}$, then $p_{j_{1},k_{2}}=p_{j_{2},k_{1}}=\Asterisk$.\label{cond:blackburn}
\end{enumerate}
If there is no ambiguity, we will use the notation $(K,f,Z,S)$, where $S$ is a positive integer, for a PDA implicitly assuming $\mathcal{S}=\{0,1,\ldots,S-1\}$. The construction of a coded caching scheme from a PDA was proved by Yan \textit{et al.} \cite{yan2017placement}, and is reproduced below for reference.
\begin{theorem}[Coded caching schemes from PDAs \cite{yan2017placement}]\label{th:yanpda}
For a given $(K,f,Z,\mathcal{S})$ PDA, $P = [p_{j,k}]_{f\times K}$,
there exists a corresponding  $(K,N;M,R)$ caching system with subpacketization $f$, $M/N = Z/f$ and $R = |\mathcal{S}|/f$.
\end{theorem}
In the caching scheme corresponding to a PDA, each file $W_i$ is split into $f$ subfiles $W_{i,j}$, $i\in[N]$, $j\in[f]$. Each row of the PDA corresponds to a subfile label and if $p_{j,k}=\Asterisk$, then User~$k$'s cache is loaded with the $j$-th subfile of every file. So the cache $Z_k$ of User $k$ is given by
\begin{align}
    Z_k = \{W_{i,j}:\forall i\in [N], p_{j,k}=\Asterisk \}.
\end{align}
For the demand vector $\boldsymbol{D}=\{D_k: k \in [K] \}$, the server transmits
\begin{align}
    X^{\boldsymbol{D}}=\left\{\bigoplus_{j\in [f], k\in [K], p_{j,k}=s} W_{D_k,j}: s\in \mathcal{S}\right\}.
\end{align}
In the packet of $X^{\boldsymbol{D}}$ corresponding to $s$, User~$k_0$ has all the subfiles occurring in the XOR in its cache except $W_{D_{k_0},j_0}$, where  $j_0$ is such that $p_{j_0,k_0}=s$. This is because, if $p_{j,k}=s$ for $k\ne k_0$, then $j\ne j_0$ and $p_{j,k_0}=\Asterisk$ by \ref{cond:blackburn}. So, User $k_0$ recovers $W_{D_{k_0},j}$ whenever $p_{j,k_0}\ne\Asterisk$.
In this manner, each user can recover the entire file demanded using cache contents and transmissions.

A placement delivery array P is said to be a $g$-regular $(K,f,Z,\mathcal{S})$ PDA or $g$-$(K,f,Z,\mathcal{S})$ PDA or $g$-PDA for short, if each integer in $\mathcal{S}$ appears $g$ times in $P$. This implies that $|\mathcal{S}|g=K(f-Z)=$ number of integer cells in the PDA, or $|\mathcal{S}|=K(f-Z)/g$. The constant $g$, called the \textit{coding gain} \cite{yan2017placement} (or \textit{global caching gain} in \cite{maddah2014fundamental}), indicates the number of users that recover a subfile from a single transmission. 
The rate of the coded caching scheme obtained from a $g$-regular PDA is
\begin{align}
    R &= \frac{|\mathcal{S}|(F/f)}{F} = \frac{K(f-Z)}{fg}. \label{eq:regularPdaRate}
\end{align}
In terms of parameters, our focus is on the regime where subpacketization $f$ is linear in $K$, i.e. $f=mK$ for a positive integer $m$, and the number of users $K$ is \emph{moderately} high. In this regime, we provide explicit constructions for $(K,f,Z,\mathcal{S})$ PDAs that achieve different trade-offs between the per-file cache size $Z/f$ and the rate $|\mathcal{S}|/f$. 

\section{Results}\label{sec:results}
We present lifted PDAs and corresponding coded caching schemes using the Blackburn-compatible PDAs constructed in the previous sections. To bring out the versatility of the lifting procedure, we present lifted PDAs constructed for a given number of users $K$ and a wide range of memory sizes and rates.
\subsection{$K$ is a power of $2$}
Starting with 2-PDAs, we consider lifting to obtain PDAs with a coding gain of $2^r$, $r=2,3,\ldots$.
\begin{theorem}[$2^r$-lifting]\label{lem:lifting2r}
\begin{enumerate}[nosep]
    \item Given a $2$-regular $(K_b,f_b,Z_b,\mathcal{S}_b)$ PDA $P_b$, there exists an $2^r$-regular $(2^rK_b,2^rf_b,(2^r-r-1)f_b\allowbreak+rZ_b,(2+2r)|\mathcal{S}_b|+K_bZ_b)$ PDA.
    \item For coded caching with $K$ users, if $2^r\mid K$ for an integer $r$, the memory-rate pair $\big(\frac{N}{K}(K(1-2^{-r}(r+1))+r),2^{-2r}K(r+1)\allowbreak-2^{-r}r\big)$ is achievable with linear subpacketizattion.
\end{enumerate}
\end{theorem}
\begin{proof}
For the first part, use Corollary~\ref{co:regularTiling} to lift the given 2-regular base PDA $P_b$ using the Blackburn-compatible PDAs obtained from Lemma \ref{lem:A2r_compatibility} as constituent PDAs. Since $I_{2^r}(t)$ has $(2^r-1)$ $\Asterisk$'s per column and $A_{2^r}(x_i)$, $A'_{2^r}(x_i)$ have $(2^r-r-1)$ $\Asterisk$'s per column, the number of $\Asterisk$ in each column of the lifted PDA is $(Z)(2^r-1)+(f_b-Z_b)(2^r-r-1)=(2^r-r-1)f+rZ$. The other parameter values are easy to establish.

For the second part, let $q=\frac{K}{2^r}$. Construct a $(q,q,1,q(q-1)/2)$ $2$-PDA using Lemma~\ref{lm:diagPDA}. Lift this PDA using the above first part of the theorem to obtain a $(K,K,K(1-(r+1)2^{-r})+r,2^{-2r}K^2(r+1)-2^{-r}Kr)$ $2^r$-PDA. This would result in the memory-rate pair as claimed.
\end{proof}
If $n$ is a multiple of certain specific powers of 2, then the following theorem provides recursive lifting constructions for $n\times n$ PDAs.
\begin{theorem}\label{th:nested2g}
For $q,r \in \mathbb{Z}^+$ and $q\ge 2$, if $n=2^{\frac{r(r+1)}{2}-1} q$, then there exists a $2^r$-regular $(n,n,Z_r,S_r)$ PDA where $Z_r$ and $S_r$ are given by the following recursive relations:
\begin{align*}
    Z_i &= (2^{i}-2)Z_{i-1}+n_{i-1},\qquad\qquad\quad Z_1=1 \\
    S_i &= \frac{2^i(2^i-1)}{2}S_{i-1}+n_{i-1}Z_{i-1},\qquad S_1=\frac{q(q-1)}{2}.
\end{align*}
with $n_i=2^{\frac{i(i+1)}{2}-1} q$.
\end{theorem}
\begin{proof}
Let $P_1$ be a $2$-regular $(q,q,1,\frac{q(q-1)}{2})$ PDA constructed using Lemma~\ref{lm:diagPDA}. For $i>1$, let $L_i(\cdot)$ denote the lifting using Corollary \ref{co:regularTiling} of a $2^{i-1}$-regular PDA to a $2^i$-regular PDA using the set of $2^{i-1}$ $(2^i,2^i,1,2^{i-1}(2^i-1))$ PDAs obtained using C2. 

Let $P_i=L_i(P_{i-1})))$. Now, $P_{i-1}$ is an $(n_{i-1},n_{i-1},Z_{i-1},S_{i-1})$ PDA with $n_1=q$. Each integer in $P_{i-1}$ is replaced by a $(2^i,2^i,1,2^{i-1}(2^i-1))$ PDA (1 $\Asterisk$ per column) and each $\Asterisk$ is replaced by $I_{2^i}$ ($2^i-1$ $\Asterisk$s per columns). So, in one column of the lifted PDA, there are $Z_{i-1}(2^i-1)+(n_{i-1}-Z_{i-1})=(2^i-2)Z_{i-1}+n_{i-1}$. Clearly, $n_i=2^i n_{i-1}=2^{2+\cdots+(i-1)}q=2^{\frac{i(i-1)}{2}-1}q$.

Then $P_r$ is a $2^r$-regular $(n,n,Z_r,S_r)$ PDA as claimed. 
\end{proof}
The above theorem helps to obtain integer-dense PDAs since the base PDA and constituent PDAs are 2-PDAs with a single $\Asterisk$ per column. It can be used to obtain $8$-regular PDAs when $n$ is divisible by $32$, $16$-regular PDAs when $n$ is divisible by 512 and so on.

The memory-rate and memory-subpacketization tradeoff for $K=64$ using the lifting schemes BW2, C2 and $2^r$-lifting is compared with some known schemes in Figs.~\ref{fig:K64} and \ref{fig:K64sub}. The line between the achievable memory-rate pairs in Fig.~\ref{fig:K64} is obtained using memory sharing. In addition, memory-rate tradeoff of lifting schemes for $K=256$ is shown in Fig. \ref{fig:K256}. 
Minimum values of $Z$ obtained for each coding gain $g$ are highlighted in red and are labelled using $(Z,g)$.
For the points highlighted in solid red, the constructions are provided in Table~\ref{tab:samplecon}.

\begin{figure}[htb]
\begin{subfigure}[b]{0.4\textwidth}
    \input{figures_tex/rateNewComparison_64}
    \caption{Rate vs memory, $K=64$.}
    \label{fig:K64}
\end{subfigure}\hfill
\begin{subfigure}[b]{0.4\textwidth}
\input{figures_tex/fig_4_lifting256}
\caption{Rate vs memory, $K=256$.}
\label{fig:K256}
\end{subfigure}

\begin{subfigure}[b]{0.4\textwidth}
\input{figures_tex/SubpnComparison_64}
\caption{Subpacketization, $K=64$.}
\label{fig:K64sub}
\end{subfigure}
    \caption{Results: $K$ is a power of 2.}
    \label{fig:comparisonPlot}
\end{figure}
We see that the lifting scheme has better rate than the grouping scheme with $c=8$ for all memory. For memory ratios $0.71<M/N<1$, lifting has better rate than grouping with $c=4$. In Fig.~\ref{fig:K64sub}, we see that for most values of cache memory ratio, the subpacketization of lifting schemes is noticeably better than other comparable schemes, except for the grouping scheme with $c=8$.
Also, our schemes are flexible to provide a wide range of intermediate points without an increase in subpacketization.

\subsection{$K$ with many divisors}
When $K$ has many small divisors, lifting can be applied in multiple ways. A good approach is to consider as many possibilities of lifting as possible and find constructions that achieve the best tradeoff between cache memory and rate. In this section, we present such results for $K=24, 60, 240, 250$. The same procedures can be employed for other such values of $K$ to generate PDAs. 

The memory-rate tradeoffs of various different lifting constructions for $K=24,60,240,250$ are shown in Fig.~\ref{fig:lifting24}.
\begin{figure}[htb]
\begin{subfigure}{0.5\textwidth}
    \centering
    \input{figures_tex/fig_4_lifting24}
    \caption{$K=24$}
    \label{fig:first}
\end{subfigure}%
~
\begin{subfigure}{0.5\textwidth}
    \centering
    \input{figures_tex/fig_4_lifting60}
    \caption{$K=60$}
    \label{fig:second_a}
\end{subfigure}\\
\begin{subfigure}{0.5\textwidth}
    \centering
    \input{figures_tex/fig_4_lifting240}
    \caption{$K=240$}
    \label{fig:third_a}
\end{subfigure}
~
\begin{subfigure}{0.5\textwidth}
    \centering
    \input{figures_tex/fig_4_lifting250}
    \caption{$K=250$}
    \label{fig:third}
\end{subfigure}
\caption{Memory-rate tradeoff for $K=24,64,240,250$.}
\label{fig:lifting24}
\end{figure}
For $K=24$, memory-rate tradeoff of the coded caching schemes obtained from our constructions is compared with uncoded and Maddah-Ali-Niesen (MN) schemes. 
Our PDA-based schemes are close to the MN scheme at different parts of the rate versus memory trade-off curve.
Some selected points in the plots are highlighted in darker shade of red. For these selected points, we provide a complete description of the lifting construction in the table below. The notation $(K_b,f_b)_{Z_b}^{g_b}\xrightarrow[X]{(m,n)_{Z_c,Z_*}} (K,f)_{Z}^{g}$ denotes the lifting of a $g_b$-regular $(K_b,f_b,Z_b,\frac{K_b(f_b-Z_b)}{g_b})$ PDA to a $g$-regular $(K,f,Z,\frac{K(f-Z)}{g})$ PDA using a set of $m\times n$ Blackburn-compatible PDAs having $Z_c$ $\Asterisk$'s per column and $P_*$ having $Z_*$ $\Asterisk$'s per column. $X$ denotes the construction method.

\medskip
\begin{table}[]
    \centering
    \caption{Lifting constructions of some of the PDAs from Fig.~\ref{fig:comparisonPlot} and \ref{fig:lifting24}.}
    \label{tab:samplecon}
\begin{tabular}{|c|l|l|}
\hline
    $K$ & Example 1 & Example 2 \\
    \hline
    24  & $(4,4)_{1}^{2}\xrightarrow[BW3]{(6,6)_{1,4}} (24,24)_{7}^{4}$ & $(3,3)_{1}^{2}\xrightarrow[2^r \mathrm{ Lifting}]{(8,8)_{4,7}} (24,24)_{15}^{8}$\\
    \hline
    60  & $(5,5)_{1}^{2}\xrightarrow[\mathrm{Randomized}]{(12,12)_{9,11}} (60,60)_{47}^{12}$ & $(3,3)_{1}^{2}\xrightarrow[C2]{(4,4)_{1,3}} (12,12)_{5}^{4}\xrightarrow[\mathrm{Basic Lifting}]{(5,5)_{4,5}} (60,60)_{53}^{20}$\\
    \hline
    64  & $(8,8)_{1}^{2}\xrightarrow[BW2]{(8,8)_{1,5}} (64,64)_{12}^{4}$ & $(2,2)_{1}^{2}\xrightarrow[C2]{(4,4)_{1}} (8,8)_{4}^{4}\xrightarrow[C2]{(8,8)_{1}} (64,64)_{32}^{8}$\\
    \hline
    240 & $(5,5)_{1}^{2}\xrightarrow[BW3]{(6,6)_{1,4}} (30,30)_{8}^{4}\xrightarrow[C2]{(8,8)_{1,7}} (240,240)_{78}^{8}$ & $(4,4)_{1}^{2}\xrightarrow[\mathrm{Eq. \scriptsize{\eqref{eq:12by3}}}]{(3,12)_{3,8}} (12,48)_{17}^{3}\xrightarrow[\mathrm{Basic Lifting}]{(4,4)_{1,4}}(48,192)_{99}^{6}$\\
    &&\multicolumn{1}{r|}{$\xrightarrow[\mathrm{Basic Lifting}]{(5,5)_{1,5}} (240,960)_{588}^{12}$}\\
    \hline
    250 & $(5,5)_{1}^{2}\xrightarrow[BW3]{(50,50)_{1,26}} (250,250)_{30}^{4}$ & $(2,2)_{1}^{2}\xrightarrow[\mathrm{Eq. \scriptsize{\eqref{eq:10by5}}}]{(5,10)_{5,8}} (10,20)_{13}^{5}\xrightarrow[\mathrm{Tiling}]{(25,25)_{20,24}} (250,500)_{452}^{25}$\\
    \hline
    256 & $(4,4)_{1}^{2}\xrightarrow[BW2]{(8,8)_{1,5}} (32,32)_{8}^{4}\xrightarrow[C2]{(8,8)_{1,7}} (256,256)_{80}^{8}$ & $(2,2)_{1}^{2}\xrightarrow[2^r \mathrm{ Lifting}]{(128,128)_{120,127}} (256,256)_{247}^{128}$\\
    \hline
\end{tabular}
\end{table}

Table~\ref{tab:samplecon} provides a sample of how a multitude of lifting sequences are possible when $K$ has many small divisors. For instance, in Example 1 for $K=240$, a $2$-regular $5\times 5$ base PDA is first lifted to a $4$-regular $30\times 30$ PDA, which is in turn lifted to an $8$-regular $240 \times 240$ PDA. The two liftings use Blackburn-compatible PDAs from Constructions BW3 and C2, respectively.


\subsection{Randomized construction: $f=K$, $f=2K$, $f=4K$}
To obtain subpacketization as a small multiple of the number of users, randomized construction of Blackburn-compatible PDAs shown in Algorithm~\ref{alg:random} can be used. For $K=250$ and $K=256$, Table~\ref{tab:random} shows some of the resulting lifting constructions. 
\begin{table}[htb]
    \centering
    \caption{Randomized construction.}\label{tab:random}
\begin{tabu}{ccccccc}
    \toprule
    $K$ & $f$ & Gain & Construction && $M/N$ & $R$\\
    \midrule 
250 & 250 & 125 & $(2,2)_{1}^{2}\xrightarrow{(125,125)_{124,124}}(250,250)_{248}^{125}$ && 0.992 & 0.016 \\ 
250 & 250 & 25 & $(2,2)_{1}^{2}\xrightarrow{(5,5)_{3,4}}(10,10)_{7}^{5}\xrightarrow{(25,25)_{22,24}}(250,250)_{234}^{25}$ && 0.936 & 0.64 \\ 
250 & 250 & 10 & $(5,5)_{1}^{2}\xrightarrow{(5,5)_{3,4}}(25,25)_{16}^{5}\xrightarrow{(10,10)_{6,9}}(250,250)_{198}^{10}$ && 0.792 & 5.2 \\ 
250 & 250 & 5 & \makecell[c]{$(2,2)_{1}^{2}\xrightarrow{(5,5)_{3,4}}(10,10)_{7}^{5}\xrightarrow{(5,5)_{0,4}}$\phantom{000000}\\\phantom{000000}$(50,50)_{28}^{5}\xrightarrow{(5,5)_{0,4}}(250,250)_{112}^{5}$} && 0.448 & 27.6 \\ 
256 & 256 & 4 & $(64,64)_{2}^{2}\xrightarrow{(4,4)_{1,3}}(256,256)_{66}^4$ && 0.2578 & 47.5\\
250 & 500 & 125 & $(2,4)_{2}^{2}\xrightarrow{(125,125)_{124,124}}(250,500)_{496}^{125}$ && 0.992 & 0.016 \\ 
250 & 500 & 25 & $(2,2)_{1}^{2}\xrightarrow{(5,10)_{6,8}}(10,20)_{14}^{5}\xrightarrow{(25,25)_{22,24}}(250,500)_{468}^{25}$ && 0.936 & 0.64 \\ 
250 & 500 & 10 & $(5,5)_{4}^{5}\xrightarrow{(5,5)_{0,4}}(25,25)_{16}^{5}\xrightarrow{(10,20)_{11,18}}(250,500)_{387}^{10}$ && 0.774 & 5.65 \\ 
250 & 500 & 5 & \makecell[c]{$(2,2)_{1}^{2}\xrightarrow{(5,10)_{6,8}}(10,20)_{14}^{5}\xrightarrow{(5,5)_{0,4}}$\phantom{000000}\\\phantom{000000}$(50,100)_{56}^{5}\xrightarrow{(5,5)_{0,4}}(250,500)_{224}^{5}$} && 0.448 & 27.6 \\ 
256 & 512 & 4 & $(64,128)_{2}^{2}\xrightarrow{(4,4)_{1,3}}(256,512)_{132}^4$ && 0.2578 & 47.5\\
250 & 1000 & 125 & $(2,8)_{4}^{2}\xrightarrow{(125,125)_{124,124}}(250,1000)_{992}^{125}$ && 0.992 & 0.016 \\ 
250 & 1000 & 25 & $(2,4)_{2}^{2}\xrightarrow{(5,10)_{6,8}}(10,40)_{28}^{5}\xrightarrow{(25,25)_{22,24}}(250,1000)_{936}^{25}$ && 0.936 & 0.64 \\ 
250 & 1000 & 10 & $(5,5)_{4}^{5}\xrightarrow{(5,5)_{0,4}}(25,25)_{16}^{5}\xrightarrow{(10,40)_{21,36}}(250,1000)_{765}^{10}$ && 0.765 & 5.875 \\ 
250 & 1000 & 5 & \makecell[c]{$(2,4)_{2}^{2}\xrightarrow{(5,10)_{6,8}}(10,40)_{28}^{5}\xrightarrow{(5,5)_{0,4}}$\phantom{000000}\\\phantom{000000}$(50,200)_{112}^{5}\xrightarrow{(5,5)_{0,4}}(250,1000)_{448}^{5}$} && 0.448 & 27.6 \\ 
256 & 1024 & 4 & $(64,256)_{2}^{2}\xrightarrow{(4,4)_{1,3}}(256,1024)_{264}^4$ && 0.2578 & 47.5\\ 
\bottomrule
    \end{tabu}
\end{table}
The memory-rate tradeoffs are shown in Fig.~\ref{fig:random}.  


\begin{figure}[!htb]
\minipage{0.32\textwidth}
    \begin{tikzpicture}[scale=0.6]
      \begin{axis}[
        title={$K=250$ and $f=250$},
        xmin=0,
        ymin=0,
        ylabel=$R$,
        xlabel=$M/N$,]
        \addplot coordinates {(1,0) (0.996, 0.004) (0.992, 0.016) (0.964, 0.18) (0.936, 0.64) (0.792, 5.2) (0.448, 27.6) (0.2578125, 47.5) (0.004, 124.5) (0, 250)};
\addplot [color=red]
  table[row sep=crcr]{%
0	256\\
0.00390625	127.5\\
0.2578125	47.5\\
0.51171875	15.625\\
0.703125	4.75\\
0.83203125	1.34375\\
0.9140625	0.34375\\
0.96484375	0.0703125\\
0.99609375	0.00390625\\
1	0\\
};
      \end{axis}
    \end{tikzpicture}
\endminipage\hfill
\minipage{0.32\textwidth}
    \begin{tikzpicture}[scale=0.6]
      \begin{axis}[
        title={$K=250$ and $f=500$},
        xmin=0,
        ymin=0,
        ylabel=$R$,
        xlabel=$M/N$,]
        \addplot coordinates {(1,0) (0.996, 0.004) (0.992, 0.016) (0.964, 0.18) (0.936, 0.64) (0.774, 5.65) (0.448, 27.6) (0.2578125, 47.5) (0.004, 124.5) (0, 250)};
      \end{axis}
    \end{tikzpicture}
\endminipage\hfill
\minipage{0.32\textwidth}%
    \begin{tikzpicture}[scale=0.6]
      \begin{axis}[
        title={$K=250$ and $f=1000$},
        xmin=0,
        ymin=0,
        ylabel=$R$,
        xlabel=$M/N$,]
        \addplot coordinates {(1,0) (0.996, 0.004) (0.992, 0.016) (0.964, 0.18) (0.936, 0.64) (0.765, 5.875) (0.448, 27.6) (0.2578125, 47.5) (0.004, 124.5) (0, 250)};
      \end{axis}
    \end{tikzpicture}
\endminipage
\caption{Memory-rate tradeoff for coded caching schemes from PDAs lifted using randomly constructed Blackburn compatible PDAs. The red curve added for comparison in the first plot is the MR tradeoff obtained using $2^r$-lifting for $K=f=256$.}\label{fig:random}
\end{figure}
We observe that a wide variety of memory vs rate tradeoffs are obtained by lifting with Blackburn compatible PDAs obtained using the randomized algorithm. For $K=f=250$, we have added the memory-rate tradeoff obtained by deterministic $2^r$-lifting for $K=f=256$ (red line) for comparison. We see that the randomized method provides tradeoffs that are comparable with the deterministic one. 

To summarize, in this results section, we have clearly demonstrated the versatility of the lifting construction. For a given number of users, we have shown how the idea of lifting can readily provide multiple lifting constructions for PDAs offering a range of tradeoffs between cache memory size and rate at very low subpacketization.












\section{Conclusion}\label{sec:conc}
We propose several constructions for coded caching schemes with subpacketization linear with the number of users using the framework of placement delivery arrays. We presented a general scheme to construct PDAs with a coding gain of 2. 
We introduced the notion of Blackburn compatibility of PDAs and used this concept for a several lifting constructions of PDAs with higher coding gains. We showed that Blackburn-compatible PDAs can be built from existing sets of Blackburn compatible PDAs through our blockwise and recursive constructions. We also proposed an algorithm to randomly construct Blackburn compatible PDAs for any arbitrary setting. In many regimes, our lifting constructions are shown to perform better compared to other existing schemes for lower subpacketization.

