text:
\section{Statistical Query Lower Bound for Getting \texorpdfstring{$\mathsf{OPT} + \epsilon$}{OPT + eps}}
\label{sec:sq}

In this section we make an intriguing connection between evolvability as defined by Valiant \cite{valiant2009evolvability} and PAC learning under Massart noise. To the best of our knowledge, it appears that this connection has been overlooked in the literature. As our main application, we use an existing lower bound from the evolvability literature \cite{feldman2011distribution} to deduce a super-polynomial statistical query lower bound for learning halfspaces under Massart noise to error $\mathsf{OPT} + \epsilon$ for sub-constant $\epsilon$. This answers an open question from \cite{diakonikolas2019distribution}.

Formally, we show the following:

\begin{theorem}\label{thm:sq_main}
    There is an absolute constant $0 < c < 1$ such that for any sufficiently large $k\in\N$, the following holds. Any SQ algorithm that can distribution-independently PAC learn any halfspace to error $\mathsf{OPT} + 2^{-k}/12$ in the presence of $2^{-ck}$ Massart noise must make $(n/8k)^{k/9}$ statistical queries of tolerance $(n/8k)^{-k/9}$.
\end{theorem}

In Section~\ref{subsec:csq_defs}, we review basic notions of evolvability and statistical query learning. In Section~\ref{subsec:csq_implies_massart} we show that if a concept class is distribution-independently evolvable, then it can be distribution-independently PAC-learned to error $\mathsf{OPT} + \epsilon$. In Section~\ref{subsec:partial_reverse} we show a partial reverse implication, namely that certain kinds of lower bounds against evolvability of concept classes imply lower bounds even against PAC-learning those concepts under \emph{specific distributions} to error $\mathsf{OPT} + \epsilon$ in the presence of Massart noise. In Section~\ref{subsec:feldman}, we describe one such lower bound against evolvability of halfspaces due to \cite{feldman2011distribution} and then apply the preceding machinery to conclude Theorem~\ref{thm:sq_main}.

\subsection{Statistical Query Learning Preliminaries}
\label{subsec:csq_defs}

\begin{definition}
	Let $\tau > 0$. In the \emph{statistical query model} \cite{kearns1998efficient}, the learner can make queries to a \emph{statistical query oracle} for target concept $f: \R^n\to\brc{\pm 1}$ with respect to distribution $\calDx$ over $\R^n$ and with \emph{tolerance} $\tau$. A query takes the form of a function $F:\R^n\times\brc{\pm 1}\to \brk{-1,1}$, to which the oracle may respond with any real number $z$ for which $\abs{\E[\calDx]{F(\vx,f(\vx))} - z} \le \tau$. We say that a concept class $\calC$ is SQ learnable over a distribution $\calDx$ if there exists an algorithm which, given $f\in\calC$, PAC learns $f$ to error $\epsilon$ using $\poly(1/\epsilon,n)$ SQ queries with respect to $\calDx$ with tolerance $\poly(\epsilon,1/n)$.

	A \emph{correlational statistical query} (CSQ) is a statistical query $F$ of the form $F(\vx,y)\triangleq G(\vx)\cdot y$ for some function $G:\R^n\to\brk{-1,1}$. We say that a concept class $\calC$ is CSQ learnable if it is SQ learnable with only correlational statistical queries.
\end{definition}

Valiant \cite{valiant2009evolvability} introduced a notion of learnability by random mutations that he called \emph{evolvability}. A formal definition of this notion would take us too far afield, so the following characterization due to \cite{feldman2008evolvability} will suffice:

\begin{theorem}[\cite{feldman2008evolvability}, Theorems 1.1 and 4.1]\label{thm:evolvability}
	A concept class is CSQ learnable over a class of distributions $\calDx$ if and only if it is evolvable with Boolean loss over that class of distributions.
\end{theorem}

Henceforth, we will use the terms \emph{evolvable} and \emph{CSQ learnable} interchangeably.

\subsection{Evolvability Implies Massart Learnability}
\label{subsec:csq_implies_massart}

We now show the following black-box reduction which may be of independent interest, though we emphasize that this result will not be needed in our proof of Theorem~\ref{thm:sq_main}.

\begin{theorem}\label{thm:csq_to_massart}
	Let $\calC$ be a concept class for which there exists a CSQ algorithm $\calA$ which can learn any $f\in\calC$ to error $\epsilon$ over any distribution $\calDx$ running in time $T$ and using at most $N$ correlational statistical queries with tolerance $\tau$. Then for any $\eta \in [0,1/2)$, given any distribution $\calD$ arising from $f$ with $\eta$ Massart noise, \textsc{MassartLearnFromCSQs}($\calD,\calA,\epsilon,\delta$) outputs $\hypo$ satisfying $\Pr[\calD]{\hypo(\vx)\neq y} \le \mathsf{OPT} + 2\epsilon$ with probability at least $1 - \delta$. Furthermore it draws at most $M = N\cdot \poly(1/\epsilon,1/(1 - 2\eta),1/\tau)\cdot \log(N/\delta)$ samples and runs in time $T + M$.
\end{theorem}

By Theorem~\ref{thm:evolvability}, one consequence of Theorem~\ref{thm:csq_to_massart} is that functions which are distribution-independently evolvable with Boolean loss are distribution-independently PAC learnable in the presence of Massart noise.

The main ingredient in the proof of Theorem~\ref{thm:csq_to_massart} is the following basic observation.

\begin{fact}\label{fact:trivial_csq}
	Take any distribution $\calDx$ over $\R^n$ which has density $\calDx(\cdot)$, any function $f:\R^n\to\brc{\pm 1}$, and any correlational statistical query $F(\vx,y)\triangleq G(\vx)\cdot y$, and let $\calD$ be the distribution arising from $f$ with $\eta$ Massart noise. If $\calDx'$ is the distribution with density given by \begin{equation}\label{eq:csq_Z}
		\calDx'(\vx) \triangleq \frac{1}{Z}(1 - 2\eta(\vx))\calDx(\vx) \ \forall \ \vx\in\R^n, \qquad Z\triangleq \int_{\R^n} (1 - 2\eta(\vx))\calDx(\vx) d\vx,
	\end{equation} and $\calD'$ is the distribution over $(\vx,y)$ where $\vx\sim \calDx'$ and $y = f(\vx)$, then \begin{equation}
		\E[(\vx,y)\sim\calD]{F(\vx,y)} = Z\cdot\E[(\vx,y)\sim\calD']{F(\vx,y)}.\label{eq:csq_id}
	\end{equation}
\end{fact}

\begin{proof}
	This simply follows from the fact that $\E[(\vx,y)\sim\calD]{F(\vx,y)} = \E[\vx\sim\calDx]{f(\vx)G(\vx) (1 - 2\eta(\vx))}$.
\end{proof}

This suggests that given a CSQ algorithm for learning a concept $f$ over arbitrary distributions, one can learn $f$ over arbitrary distributions in the presence of Massart noise by simply brute-force searching for the correct normalization constant $Z$ in \eqref{eq:csq_Z} and simulating CSQ access to $\calD'$ using \eqref{eq:csq_id}. Formally, this is given in \textsc{MassartLearnFromCSQs}.

\begin{algorithm}
\DontPrintSemicolon
\caption{\textsc{MassartLearnFromCSQs}($\calD,\calA,\epsilon,\delta$)}
\label{alg:csq2massart}
	\KwIn{Sample access to distribution $\calD$ arising from $f\in\calC$ with $\eta$ Massart noise, algorithm $\calA$ which distribution-independently learns any concept in $\calC$ to error $\epsilon$ using at most $N$ CSQs with tolerance $\tau$, error parameter $\epsilon>0$, failure probability $\delta$}
	\KwOut{Hypothesis $\hypo$ for which $\Pr[(\vx,y)\sim\calD]{\hypo(\vx)\neq y} \le \mathsf{OPT} + 2\epsilon$}
		Set $\tau' \gets \tau(1 - 2\eta)^2/2$.\;
		\For{$\tilde{Z}\in[0,\tau',2\tau',...,1]$}{
			Simulate $\calA$: answer every correlational statistical query $F(\vx,y)\triangleq G(\vx)\cdot y$ that it makes with an empirical estimate of $\frac{1}{\tilde{Z}}\E[(\vx,y)\sim\calD]{F(\vx,y)}$ formed from $O(\frac{\log(N/\delta)}{(1 - 2\eta)^2\tau^2})$ samples.\;\label{step:simulate}
			Let $\hypo$ be the output of $\calA$.\;
			Empirically estimate $\Pr[(\vx,y)\sim\calD]{\hypo(\vx)\neq y}$ using $O(\log(1/\delta\tau(1-2\eta)^2/\epsilon^2)$ samples. If it is at most $\mathsf{OPT}+ 3\epsilon/2$, output $\hypo$.\;\label{step:01est}

		}
		Return $\mathsf{FAIL}$.\;
\end{algorithm}

\begin{proof}
	Let $\calDx',\calD',Z$ be as defined in Fact~\ref{fact:trivial_csq}, and let $\tau' = \tau(1 - 2\eta)^2/2$. First note that $Z$ defined in \eqref{eq:csq_Z} is some quantity in $\brk{1-2\eta,1}$. Let $\tilde{Z}$ be any number for which $Z \le \tilde{Z} \le Z + \tau'$. Note that this implies that $\abs{1/Z - 1/\tilde{Z}} \le \tau'/Z^2 \le \tau/2$. In particular, for any correlational statistical query $F(\vx,y)$, Fact~\ref{fact:trivial_csq} implies that \begin{equation}
		\abs*{\frac{1}{\tilde{Z}}\E[\calD]{F(\vx,y)} - \E[\calD']{F(\vx,y)}} \le \abs*{\frac{1}{Z} - \frac{1}{\tilde{Z}}}\cdot\abs{\E[\calD]{F(\vx,y)}} \le \tau/2.
	\end{equation} With $O\left(\frac{\log(2N/\delta)}{(1 - 2\eta)^2\tau^2}\right)$ samples, we can ensure that for this choice of $\tilde{Z}$ and this query $F$, the empirical estimate, call it $\hatE[\calD]{F(\vx,y)}$, formed in Step~\ref{step:simulate} satisfies \begin{equation}
		\frac{1}{\tilde{Z}}\abs*{\E[\calD]{F(\vx,y)} - \hatE[\calD]{F(\vx,y)}} \le \tau/2,
	\end{equation} with probability $1 - \delta/2N$. In particular, this implies that for this choice of $\tilde{Z}$ in the main loop of \textsc{MassartLearnFromCSQs}, all of our answers to the CSQs made by $\calA$ are correct to within error $\tau$ with probability $1 - \delta/2$, in which case the simulation is correct and the hypothesis $\hypo$ output by $\calA$ in that iteration of the loop satisfies $\Pr[\calDx']{\hypo(\vx)\neq f(\vx)} \le \epsilon$.

	So we have that \begin{equation}
		\epsilon\ge \Pr[\calDx']{\hypo(\vx)\neq f(\vx)} = \frac{1}{Z}\E[\calDx]{(1 - 2\eta(\vx))\cdot \bone{\hypo(\vx)\neq f(\vx)}}\ge \E[\calDx]{(1 - 2\eta(\vx))\cdot \bone{\hypo(\vx)\neq f(\vx)}},
	\end{equation} or equivalently, $\Pr[(\vx,y)\sim\calD]{\hypo(\vx)\neq y} \le \mathsf{OPT} + \epsilon$. $O(\log(1/\delta\tau(1-2\eta)^2)/\epsilon^2)$ samples are sufficient to ensure that the empirical estimates in Step~\ref{step:01est} are accurate in every iteration of the loop with probability $1 - \delta/2$, so we conclude that the hypothesis output by \textsc{MassartLearnFromCSQs} has error at most $\mathsf{OPT} + 2\epsilon$ with probability at least $1 - \delta$, as desired.
\end{proof}
\begin{remark}\label{rem:evol1}
The reduction from Theorem~\ref{thm:csq_to_massart} can be applied to study distribution-dependent learning of Massart halfspaces. If $\mathcal{D}_{\vx}$ is the distribution we want to learn Massart halfspaces over, it suffices to have a CSQ algorithm which succeeds over any distribution with a density over $\mathcal{D}_{\vx}$ valued in $[1 - 2\eta, \frac{1}{1 - 2\eta}]$.

As an example application of this reduction, we can combine it with the results of \cite{kanade2010evolution} to get a learning algorithm with error $O(\sqrt{\eta})$ for Massart conjunctions over the unit hypercube; this follows from the fact that their analysis is robust to a small amount of misspecification (related to the notion of drift in their work). This is somewhat weaker than our proper learner which can achieve $\eta + \epsilon$ error in the same setting.
\end{remark}
\subsection{A Partial Converse to Theorem~\ref{thm:csq_to_massart}}
\label{subsec:partial_reverse}

Next, we show a partial converse to Theorem~\ref{thm:csq_to_massart}, namely that in some cases, correlational statistical query lower bounds can imply distribution-specific SQ hardness of learning to error $\mathsf{OPT} + \epsilon$ in the presence of Massart noise.

\begin{theorem}\label{thm:massart_to_csq}
	Let $0\le \eta < 1/2$, and let $\calDx^*$ be a known distribution over $\R^n$ with density $\calDx^*(\cdot)$ and support $\calX$. Let $\calC$ be a concept class consisting of functions $\R^n\to\brc{\pm 1}$, and let $\calF$ be a family of distributions supported on $\calX$ for which the following holds:
	\begin{enumerate}
		\item For every $\vx\in\calX$ and $\calDx\in\calF$, $1 - \eta \le \frac{\calDx(\vx)}{\calDx^*(\vx)} \le 1 + \eta$.
		\item Any CSQ algorithm that can learn concepts in $\calC$to error $\epsilon$ over any distribution in $\calF$ must make more than $N$ correlational statistical queries with tolerance $\tau$.
	\end{enumerate}
	Then any SQ algorithm that can learn concepts in $\calC$ over $\calDx^*$ to error $\mathsf{OPT} + \epsilon$ in the presence of $\eta$ Massart noise requires more than $N$ statistical queries in with tolerance $\tau$.
\end{theorem}

\begin{proof}
	We will show the contrapositive. Let $\calA$ be an SQ algorithm for learning $\calC$ over $\calDx^*$ to error $\mathsf{OPT} + \epsilon$ in the presence of $\eta$ Massart noise.

	Take any $f\in\calC$ and any $\calDx\in\calF$ and consider the following distribution $\calD$ over $\calX\times\brc{\pm 1}$ arising from $f$ with $\eta$ Massart noise. For every $\vx\in\calX$, let $\eta(\vx)$ satisfy \begin{equation}\label{eq:flipdefs}
		1 - 2\eta(\vx) = \frac{\calDx(\vx)}{(1+\eta)\calDx^*(\vx)}.
	\end{equation} By assumption, the right-hand side is at most 1 and at least $\frac{1 - \eta}{1 + \eta} \ge 1 - 2\eta$, so $0\le \eta(\vx) \le \eta$. Let $\calD$ be the distribution over pairs $(\vx,y)$ where $\vx\sim\calDx^*$, and $y = f(\vx)$ with probability $1 - \eta(\vx)$ and $y = -f(\vx)$ otherwise.

	We will now show how to use $\calA$ to produce a CSQ algorithm $\calA'$ for learning any $f\in\calC$ over distribution $\calDx$. Suppose $\calA$ makes $N$ statistical queries $F_1(\vx,y),...,F_N(\vx,y)$ with tolerance $\tau$ and outputs $\hypo: \calX\to\brc{\pm 1}$ for which $\Pr[\calD]{\hypo(\vx)\neq y} \le \mathsf{OPT} + \epsilon$. Equivalently, we have that \begin{equation}
		\E[\vx\sim\calDx^*]{(1 - 2\eta(\vx))\cdot \bone{f(\vx) \neq \hypo(\vx)}} \le \epsilon.\label{eq:advantage}
	\end{equation}
	Note that this implies that \begin{equation}\label{eq:honD}
		\Pr[\vx\sim\calDx]{f(\vx)\neq \hypo(\vx)} \le (1 + \eta)\epsilon.
	\end{equation}
	The CSQ algorithm $\calA'$ proceeds as follows. Say $\calA$ makes query $F_i(\vx,y)$ with tolerance $\tau$. If $F_i$ only depends on $\vx$, then because $\calDx^*$ is a known distribution, this is just an average over $\R^n\times\{1\}$ that $\calA'$ can compute on its own, without making any correlational statistical queries. If $F_i$ depends on both $\vx$ and $y$, it can be decomposed as $F_i(\vx,y) = G_i(\vx)\cdot y + G'_i(\vx)$ for some functions $G_i, G'_i$. Again, $\calA'$ can compute $\E[\calDx]{G'_i(\vx)}$ on its own without making any correlational statistical queries, and it can make a query $\frac{1}{1 + \eta}G_i(\vx)\cdot y$ to the CSQ oracle over $\calDx$ with tolerance $\tau$ to get a $\tau$-close estimate of \begin{equation}\frac{1}{1+\eta}\E[\calDx]{G_i(\vx) f(\vx)} = \E[\calDx^*]{G_i(\vx) f(\vx)}\end{equation}
	By the guarantees on $\calA$ and by \eqref{eq:honD}, we know $\calA'$ makes at most $N$ correlational statistical queries and outputs a hypothesis $\hypo$ with error $(1+\eta)\epsilon$ relative to $f$, with respect to the distribution $\calDx$.
\end{proof}

\begin{remark}\label{remark:optvalue}
	By definition $\mathsf{OPT}$ in Theorem~\ref{thm:massart_to_csq} is given by $\mathsf{OPT} = \E[\calDx^*]{\eta(\vx)}$, so by \eqref{eq:flipdefs} we conclude that $1 - 2\mathsf{OPT} = \frac{1}{1 + \eta}$, so in particular, $\mathsf{OPT} = \frac{\eta}{2(1+\eta)}$.
\end{remark}

\begin{remark}\label{rem:evol2}
The following converse to Remark~\ref{rem:evol1} holds as a consequence of Theorem~\ref{thm:massart_to_csq}. Namely, known results for learning Massart halfspaces to error $\textsf{OPT} + \epsilon$ over a known base distribution can be implemented in SQ and therefore imply CSQ algorithms for tiltings of the base distribution in the absence of noise. Equivalently, by Theorem~\ref{thm:evolvability}, this yields evolutionary algorithms with some natural resistance to ``drift'' \cite{kanade2010evolution}.

This is the case for the algorithm of \cite{zhang2017hitting} for learning Massart halfspaces under the uniform measure on the sphere, which runs a Langevin gradient method directly on the (smoothed) zero-one loss; the zero-one loss is easily estimated by a CSQ query. In fact, since their algorithm is based on searching for local improvements to the zero-one loss, it can be more directly fit into the evolvability framework without using the reduction of \cite{feldman2008evolvability}, and can be viewed as a natural improvement to the drift-resistant halfspace evolvability results over the sphere established in \cite{kanade2010evolution}.
\end{remark}

\subsection{Instantiating Theorem~\ref{thm:massart_to_csq} for Halfspaces}
\label{subsec:feldman}

In this section we show that for $\calC$ the class of conjunctions of $k$ variables, there exists a family of distributions $\calF$ satisfying the hypotheses of Theorem~\ref{thm:massart_to_csq} for $\calDx^*$ the uniform distribution over $\brc{0,1}^n\times\{1\}$.

The construction is based on \cite{feldman2011distribution} which showed a super-polynomial lower bound against distribution-independently CSQ learning conjunctions, so we follow their notation closely. Fix parameter $k\in\N$. Let $U$ denote the uniform distribution over $\{0,1\}^n$. For every $S\subset[n]$ of size $k$, define the function $\theta_S$ as follows. First, let $t_S: \{0,1\}^n\to\brc{\pm 1}$ denote the conjunction on the bits indexed by $S$. This has Fourier expansion $t_S(\vx) = -1 + 2^{-k+1}\sum_{I\subseteq S}\chi_I(\vx)$, where $\chi_I(\vx)\triangleq \prod_{i\in I}\vx_i$. Define the function $\phi_S$ by zeroing out all Fourier coefficients of $t_S$ of size $1,...,k/3$: \begin{equation}
    \phi_S(\vx) = -1 + 2^{-k+1} + 2^{-k+1}\sum_{I\subseteq S: |I| > k/3}\chi_I(\vx).
\end{equation} Define $Z\triangleq \sum_{x\in\{0,1\}^n}|\phi_S(\vx)|$ and let $\calDx^S$ be the distribution given by $\calDx^S(\vx) = |\phi_S(\vx)|/Z$. Define the ``tilted'' conjunction $\theta_S(\vx) = 2^n\cdot \phi_S(\vx)/Z$.

\begin{fact}
There is an absolute constant $0<c<1$ such that for every $\vx\in[n]$, $|t_S(\vx) - \phi_S(\vx)| \le 2^{-ck}$. In particular, for $k$ sufficiently large, $t_S(\vx) = \sgn(\phi_S(\vx))$ for all $\vx\in\{0,1\}^n$, and therefore $\calDx^S(\vx)\cdot t_S(\vx) = U(\vx)\cdot \theta_S(\vx)$. \label{fact:bounded}
\end{fact}

\begin{proof}
\begin{equation}
2^{-k+1}\sum_{I\subset S: |I|\in[k/3]}\chi_I(\vx) \le 2^{-k+1}\sum_{j\in[k/3]}\binom{k}{j} \le 2\cdot \Pr{\Bin(k,1/2) \le k/3} \le 2^{-ck}
\end{equation}
for some absolute constant $0<c<1$, from which the the first part of the claim follows. The latter parts follow immediately by triangle inequality.
\end{proof}

Fact~\ref{fact:bounded} implies that the likelihood ratio between $\calDx^S$ and $U$ is bounded:

\begin{fact}
There is an absolute constant $0<c<1$ such that for every $\vx$, $|\calDx^S(\vx)/U(\vx) - 1| \le 2^{-ck}$.\label{fact:LR}
\end{fact}

\begin{proof}
By definition $\calDx^S(\vx)/U(\vx) = |\phi_S(\vx)|/\E[x]{|\phi_S(\vx)|}$. By Fact~\ref{fact:bounded}, $\phi_S(\vx) \in [1-2^{-ck}, 1 + 2^{-ck}]$, from which the claim follows.
\end{proof}

The following is implicit in \cite{feldman2011distribution}:

\begin{theorem}[\cite{feldman2011distribution}, Theorem 8 and Remark 9]
Let $\calC$ be the class of all conjunctions $t_S$ for $S\subset[n]$ of size $k$. Let $\calF$ be the family of distributions $\brc{\calDx^S}_{S\subseteq[n]: \abs{S} = k}$ defined above. Any CSQ algorithm for learning concepts in $\calC$ over any distribution from $\calF$ needs at least $(n/8k)^{k/9}$ queries with tolerance $(n/8k)^{-k/9}$.\label{thm:feldman}
\end{theorem}

For completeness, we give a self-contained proof below.

\begin{proof}
Let $\alpha\triangleq 1/\E[U]{|\phi_S(\vx)|}$, and define $\psi(\vx) \triangleq \alpha(2^{-1+k}-1)$. Let $A$ be any correlational SQ algorithm for the problem in the lemma statement. Simulate $A$ and let $F_1(\vx),...,F_q(\vx)$ be the sequence of correlational queries it makes given the oracle responds with $\langle F_i, \psi\rangle_U \triangleq \E[U]{F_i(\vx)\cdot \psi(\vx)}$ for each $i\in[q]$. Let $h_{\psi}$ be the hypothesis the algorithm outputs at the end.

For any $S\subseteq[n]$ of size $k$, at least one of the following must happen:
\begin{enumerate}
    \item There exists $i\in[q]$ for which $|\langle F_i, \psi\rangle_U - \langle F_i, t_S\rangle_{\calDx^S}| \ge \tau$.
    \item $\Pr[\calDx^S]{h_{\psi}(\vx) \neq t_S(\vx)} \le \epsilon$ for $\epsilon\triangleq 2^{-k}/6$.
\end{enumerate}
Indeed, if (1) does not hold, then from the perspective of the algorithm in the simulation, the responses of the CSQ oracle are consistent with the underlying distribution being $\calDx^S$ and the underlying concept being $t_S$, so it will correctly output a hypothesis $h_{\psi}(\vx)$ which is $\epsilon$-close to $t_S$, so (2) will hold.

We now devise a large packing over subsets $S$ of size $k$ for which (2) holds for at most one subset, and for which the number of subsets of the packing for which (1) can hold is upper bounded by $O(q/\tau^2)$ in terms of $q$, yielding the desired lower bound on the number of queries any CSQ algorithm must make to solve the learning problem.

The packing is simply the maximal family $\mathcal{F}$ of subsets $S\subset[n]$ of size $k$ whose pairwise intersections are of size at most $k/3$. By a greedy construction, such a family will have size at least $2^{-k}(n/k)^{k/3} = (n/8k)^{k/3}$.

To show that (2) holds for exactly one subset in $\mathcal{F}$, suppose there are two such subsets $S,T$. We have that \begin{equation}
    \Pr[U]{h_{\psi}(\vx) \neq t_S(\vx)} \le (1 + 2^{-ck})\Pr[\calDx^S]{h_{\psi}(\vx) \neq t_S(\vx)} \le 2\epsilon \le 2^{-k}/3,
\end{equation} where the first step follows by Fact~\ref{fact:LR}. Similarly, $\Pr[U]{h_{\psi}(\vx) \neq t_T(\vx)} \le 2^{-k}/3$. But $S\neq T$, so $\Pr[U]{t_S(\vx) \neq t_T(\vx)} \ge 2^{-k}$, a contradiction.

Finally, we upper bound the number of subsets of the packing for which (1) can hold. Recalling that $\calDx^S(\vx)t_S(\vx) = U(\vx)\theta_S(\vx)$ for every $\vx$, (1) is equivalent to the condition that there exists some $i\in[q]$ for which $|\langle F_i, \theta_S - \psi\rangle_U| \ge \tau$. But by construction \begin{equation}\psi(\vx) - \theta_S(\vx) = \frac{2^{-k+1}}{\E[U]{|\phi_S(\vx)|}}\sum_{I\subseteq S: |I| > k/3}\chi_I(\vx),\end{equation} from which it follows that \begin{equation}
    \tau \le \frac{2^{-k+1}}{\E[U]{|\phi_S(\vx)|}} \sum_{I\subseteq S: |I| > k/3}|\langle \chi_I, F_i\rangle_U|.
\end{equation} By averaging and recalling that $\E[U]{|\phi_S(\vx)|} \in [1 - 2^{-ck},1 + 2^{-ck}]$, we conclude that there exists some Fourier coefficient $I_S\subseteq S$ of size greater than $k/3$ for which $|\langle \chi_{I_S}, F_i\rangle_U| \ge \tau/4$. Furthermore, for $S\neq T$ in $\mathcal{F}$ for which (1) holds, clearly $I_S\neq I_T$ because $I_S\subseteq S, I_T\subseteq T$ are of size greater than $|S\cap T|$. On the other hand, for any $i\in[q]$, there are at most $16/\tau^2$ sets $I$ for which $|\langle \chi_I, F_i\rangle_U| \ge \tau/4$, as $\norm{F_i}^2_2 \le 1$. We conclude that there are most $16q/\tau^2$ sets $S\in\mathcal{F}$ for which (1) holds. The proof of the theorem upon taking $\tau = (n/8k)^{-k/9}$.
\end{proof}

We can now apply Theorem~\ref{thm:feldman} and Theorem~\ref{thm:massart_to_csq} to prove the main result of this section:

\begin{proof}[Proof of Theorem~\ref{thm:sq_main}]
    Let $\calDx^*$ be the uniform distribution over $\brc{0,1}^n\times\brc{1}$. We show the following stronger claim, namely that the theorem holds even if we restrict to instances where $\vx\sim\calDx^*$, and the unknown halfspace $\vw\in\R^{n+1}$ is promised to consist, in the first $n$ coordinates, of some bitstring of Hamming weight $k$ (corresponding to a conjunction of size $k$) and, in the last coordinate, the number $k$. By design, if $f$ is the conjunction corresponding to $\vw$, then $f(\vx) = \sgn(\vw,(\vx,1))$ for all $\vx\in\brc{0,1}^n$.

    Let $\calF$ be as defined in Theorem~\ref{thm:feldman}. By Theorem~\ref{thm:massart_to_csq} and Theorem~\ref{thm:feldman}, it is enough to show that for any $\calDx^S\in\calF$ and any $\vx\in\brc{0,1}^n\times\brc{1}$, $1 - \eta\le \frac{\calDx^S(\vx)}{\calDx^*} \le 1 + \eta$ for $\eta = 2^{-ck}$ for some $0<c<1$. But this was already shown in Fact~\ref{fact:LR}, completing the proof of the Theorem.

\end{proof}

Note that by Remark~\ref{remark:optvalue}, $\mathsf{OPT}$ is within a factor of 2 of $\eta$. On the one hand, this implies that our Theorem~\ref{thm:sq_main} is not strong enough to rule out efficient SQ algorithms for achieving $O(\mathsf{OPT}) + \epsilon$ for Massart halfspaces. On the other hand, one can also interpret Theorem~\ref{thm:sq_main} as saying that improving the accuracy guarantees of \cite{diakonikolas2019distribution} by even a constant factor will require super-polynomial statistical query complexity.


TITLE: Is tension a resistive force?
QUESTION [0 upvotes]: The normal force is thought of as being the resistive force that prevents two objects from occupying the same space. In a similar fashion, is it acceptable to think of tension as being the resistive force that opposes the stretching of a string, rope, or cable?

REPLY [1 votes]: Tension is a response to some other stimuli like an external force or perturbation. On the microsopic scale, it may be due to metallic bonding or crystal lattice structure that gives rise to these forces. You can think of it as being an inertial property of the object. Any change(eg: external stimuli) is prevented by this inertial property, which tends to maintain its current state.


TITLE: Lagrangian for Perfect fluid Stress-Energy tensor
QUESTION [8 upvotes]: The wiki article on the Einstein-Hilbert action for General Relativity says that the stress-energy tensor $T_{\mu\nu}$ is related to the Lagrangian of matter, $\mathcal{L}_M$, by
$$T_{\mu\nu}=-2\frac{\delta\mathcal{L}_M}{\delta g^{\mu\nu}}+g_{\mu\nu}\mathcal{L}_M.$$
In FRW cosmology, in the comoving frame, the stress-energy tensor $T^\mu{}_\nu$ for a perfect fluid is given by
$$T^\mu{}_\nu={\rm diag}(-\rho,p,p,p)$$
with equation of state
$$p=w\ \rho$$
and
$$\rho \propto a^{-3(1+w)},$$
where $w$ is a constant.
What is the Lagrangian $\mathcal{L}_M$ that leads to the FRW perfect fluid stress-energy tensor $T_{\mu\nu}$?

REPLY [1 votes]: An action principle for general relativistic perfect fluids is given in Section 5 of
Marsden, J. E., Montgomery, R., Morrison, P. J., & Thompson, W. B. (1986). Covariant Poisson brackets for classical fields. Annals of Physics, 169(1), 29-47.


text:
\begin{document}
\title{On the Fundamental Limits of Coded Caching Systems with Restricted Demand Types

}

\author{Shuo Shao, Jesús Gómez-Vilardebó, Kai Zhang, and Chao Tian\thanks{S. Shao is with Shanghai Jiao Tong University, SEIEE. (e-mail:shuoshao@sjtu.edu.cn)

J. Gómez-Vilardebó is with Centre Tecnològic de Telecomunicacions de Catalunya (CTTC/CERCA).

K. Zhang was with Texas A\&M University, Department of Electrical and Computer Engineering during this work and he is now with UTHealth School of Biomedical Informatics.

C. Tian are with Texas A\&M University, Department of Electrical and Computer Engineering.

This paper is published on IEEE Transaction on Communications, doi: 10.1109/TCOMM.2020.3038392.

The work of Shuo Shao was supported
by NSFC-61872149, NSFC-61901261 and 19YF1424200. The work of
J. Gómez-Vilardebó was supported in part by the Catalan Government under
Grant GR2017-1479, and in part by the Spanish Government under Grant
TI2018-099722-B-I00 (ARISTIDES). The work of K. Zhang and C. Tian
was supported in part by the National Science Foundation under Grants CCF-18-32309 and CCF-18-16546. }}

\maketitle
\begin{abstract}
 Caching is a technique to reduce the communication load in peak hours by prefetching contents during off-peak hours.
An information theoretic framework for coded caching was introduced by Maddah-Ali and Niesen in a recent work, where it was shown that significant improvement can be obtained compared to uncoded caching. Considerable efforts have been devoted to identify the precise information theoretic fundamental limits of the coded caching systems, however the difficulty of this task has also become clear.
One of the reasons for this difficulty is that the original coded caching setting allows all possible multiple demand types during delivery, which in fact introduces tension in the coding strategy. In this paper, we seek to develop a better understanding of the fundamental limits of coded caching by investigating systems with certain demand type restrictions. We first consider the canonical three-user three-file system, and show that, contrary to popular beliefs, the worst demand type is not the one in which all three files are requested. Motivated by these findings, we focus on coded caching systems where every file  must be requested by at least one user. A novel coding scheme is proposed, which can provide new operating points that are not covered by any previously known schemes.
\end{abstract}

\section{Introduction}
Caching is a technique to alleviate communication load during peak hours by prefetching certain contents to the memory of the end users during off-peak hours.
Maddah-Ali and Niesen \cite{MAN-14} proposed an information theoretic framework for caching systems, and showed that coded caching strategies can achieve significant improvement over uncoded caching strategies.
The system in the proposed framework, which has $N$ files and $K$ users, operates in two phases: during the {\em prefetching phase}, each user fills the cache memory of size $M$ with information on the files, and during the
{\em delivery phase}, the users first reveal their requests, then the central server broadcasts a message of size $R$ to all the users, and finally each user makes use of the received message together with the content in the cache memory to reconstruct the requested file.

The optimal tradeoff between $M$ and $R$ is of  fundamental importance in this setting, the characterization of which has attracted significant research effort. Several inner bounds have been obtained using strategies based on either uncoded prefetching or coded prefetching \cite{MAN-14,Yu-18,Shraei-16,T-C-18,Jesus-18,Chen-16,Kumar-19,Kumar-19-2,Amiri-17,Z-T-18,Cao-20}, and various outer bounds have also been discovered \cite{Tian-16,Tian-18,Yu-19,Ghasemi-17,Wang-18}. When the prefetched contents are required to be uncoded fragments of the original files, the optimal tradeoff between $M$ and $R$ was fully characterized in \cite{Yu-18}. However, it was also shown that in general, optimal tradeoff requires coded prefetching strategies \cite{MAN-14,Chen-16,Tian-18}. The fundamental limit of coded caching systems still remains largely unknown in general.

In the prefetching phase, the users have no prior knowledge on the demands in the delivery phase, the collection of which is jointly referred to as the demand vector. As such, the prefetched contents need to be properly designed to accommodate all possible demand vectors. In a recent work \cite{Tian-16} (see also \cite{Tian-18}), the notion of demand type was introduced to classify the possible demand vectors, which led to simplifications in studying outer bounds of the coded caching systems. From this perspective, the original setting of \cite{MAN-14} in fact allows all possible demand types, and it appears that one reason for the afore-mentioned difficulty is the tension among the coding requirements to accommodate these different demand types. Therefore, a natural question is how different demand types impact the optimal $(M,R)$ tradeoff.

To develop a better understanding of this issue, in this work we consider caching systems with restricted demand types, where during the prefetching phase, the users and the server know a priori that the demand vector in the delivery phase must be from a certain class of demand types. Such systems clearly have a more relaxed coding requirement than the original setting due to the prior knowledge on the possible demands, however, it is still highly nontrivial since each demand type would allow a rich set of possible demand vectors. Because of the relaxed coding requirement, any scheme designed to accommodate all possible demand types is valid for a system with restricted demand types, however, outer bounds for a system allowing all possible demand types may not hold for a system with restricted demand types.

We begin our study by first collecting the best known inner bounds and outer bounds in the literature for the canonical $(N,K)=(3,3)$ system, some of which are from very recent developments \cite{Jesus-18,Kumar-19,Kumar-19-2,Cao-20} in the area. This exercise reveals that although the setting where all files are requested by at least one user may pose a significant challenge for the optimal code design, a system where only such demand types are allowed can in fact achieve $(M,R)$ pairs that are strictly impossible for systems where certain other demand types are allowed. This is contrary to popular belief that such a demand type is the ``worst case", and also confirms the existence of a tension among the coding requirements for different demand types.

Given the observation above, we focus on one class of systems with restricted demand types, where it is known a prior that every file is requested by at least one user (implying that $K\geq N$).  We propose a novel code construction which provides improved performance to the known memory-rate tradeoff in the literature for such systems. The proposed scheme can be viewed as a novel approach to utilize the interference alignment technique \cite{Cadambe:08}, where some prefetched and transmitted symbols are aligned together to cancel certain interfering signal, in order for the desired signals to be recovered. Moreover, a novel pairwise transformation is introduced in the construction, in order to more efficiently take advantage of such alignment opportunities.

We note that the proposed construction generalizes the code recently proposed in \cite{Kumar-19}, however, in contrast to the code specifically designed for $N=K$ that yields a single $(M,R)$ pair in each case, our construction is for general $(N,K)$ where $K\geq N$, and it provides multiple new operating points for each case.

\section{Caching Systems with Restricted Demand Types}

In an $(N,K)$ coded caching system, there are $N$ mutually independent uniformly distributed files $(W_1,W_2,\dots,W_N)$, each of $F$ bits. There are $K$ users, each with a cache memory of capacity $MF$ bits; the set of all users  $\{1,2,\dots,K\}$ is denoted as $\mathcal{K}$. In the prefetching phase, user-$k$ stores some content, denoted as $Z_k$, in the local cache memory. Rigorously, we can define the prefetching process as follow.
\begin{definition}[Prefetching scheme] In an $(N,K)$ coded caching system, we define a prefetching scheme under a given cache memory capacity $M$ as $K$ caching encoding functions denoted as $\bm{\Phi}_M=(\phi_{M,1},\phi_{M,2},\dots,\phi_{M,K})$, where each encoding function $\phi_{M,k}:\{0,1\}^{NF} \rightarrow \{0,1\}^{\lfloor MF\rfloor}$ for $k=1,2,\dots,K$ maps the $N$ files to each user's cache memory content. That is to say,
\begin{equation*}
    Z_k=\phi_{M,k}(W_1,W_2,\dots,W_N)
\end{equation*}
for $k=1,2,\dots,K$;
\end{definition}

In the delivery phase, user-$k$, $k\in \mathcal{K}$, requests file $d(k)$. In this work, we consider the case that the demand vector $\bm{d}= ( d(1), d(2),\dots, d(K))$ belongs to a given set $\mathcal{D}$. With the given prefetching scheme $\bm{\Phi}_M$ and demand vector $\bm{d}$, the central server broadcasts a message $X_{\bm{\Phi}_M,\bm{d}}$ of $RF$ bits to every user, such that, together with the cached content, each user can decode the requested file, where $R$ is the rate of communication. We give the following rigorous definition of the communication rate.

\begin{definition}[Achievable broadcast rate]
In an $(N,K)$ coded caching system, a communication rate $R(\bm{\Phi}_M,\bm{d})$ is $\epsilon$-achievable for given prefetching scheme $\bm{\Phi}_M$ and demand vector $\bm{d} = ( d(1), d(2),\dots, d(K))$, if and only if there exists:
\begin{itemize}
\item An message encoding function $f_{\bm{\Phi}_M,\bm{d}}: \{0,1\}^{NF} \rightarrow \{0,1\}^{\lfloor R(\bm{\Phi}_M,\bm{d})F\rfloor}$ for given prefetching scheme $\bm{\Phi}_M$ and each possible demand vector $\bm{d}$ that maps the $N$ files into the broadcast messages based on $\bm{d}$, thus
\begin{equation*}
   X_{\bm{\Phi}_M,\bm{d}}=f_{\bm{\Phi}_M,\bm{d}}(W_1,W_2,\dots,W_N);
\end{equation*}

\item $K$ decoding functions $\psi_{\bm{\Phi}_M,\bm{d},k}: \{0,1\}^{\lfloor MF\rfloor}\times \{0,1\}^{\lfloor R(\bm{\Phi}_M,\bm{d})F\rfloor} \rightarrow \{0,1\}^F$ that map the caching content of user $k$ given by $\phi_{M,k}$ and the broadcast message to an $\epsilon$-error estimate of the requested file of user $k$ for all $k=1,2,\dots,K$, thus
\begin{align*}
    & Pr(W_{d(k)}\neq \psi_{\bm{\Phi}_M,\bm{d},k}(\phi_{M,k}(W_1,W_2,\dots,W_N),X_{\bm{\Phi}_M,\bm{d}}))\\
    & \leq \epsilon.\end{align*}
for all $k=1,2,\dots,K$.
\end{itemize}
\end{definition}

The communication rate $R$ of the $(N,K)$ coded caching systems, for a given cache memory capacity $M$ and demand vector set $D$, is defined as the rate of the best scheme who can minimize its worst case rate over all possible demand vectors. That is to say, the formal definition of $R$ is as follow.
\begin{definition}[Communication rate]
In an $(N,K)$ coded caching system with demand restriction set $\mathcal{D}$, the communication rate $R$ of the broadcast message in the delivery phase for the prefetching memory size $M$ is called achievable if
\begin{align*}
    R\geq \sup_{\epsilon>0}\inf_{F} & \min_{\bm{\Phi}_{M'}:M'\leq M} \max_{\bm{d}\in \mathcal{D}} \inf\{ R(\bm{\Phi}_{M'},\bm{d}):\\
    & R(\bm{\Phi}_{M'},\bm{d}) \text{is $\epsilon$-achievable}\}.
\end{align*}
\end{definition}

In the coded caching problem, the optimal tradeoff between $M$ and $R$ is the fundamental mathematical object of interest. In order to obtain some insight of this optimal tradeoff, we would like to introduce the notion of "demand type".
It was first introduced in \cite{Tian-16} (see also \cite{Tian-18}), which is restated below.
\begin{definition}[Demand types]
For a demand vector $\bm{d} = ( d(1), d(2),\dots, d(K))$ in an $(N,K)$ coded caching system, denote the number of users requesting file $W_n$ as $e_n$, where $n \in [1:N]$.  The demand type of $\bm{d}=( d(1), d(2),\dots, d(K))$ is the length-$n$ vector obtained by sorting the values $\bm{e}(\bm{d})=(e_1,e_2,\dots ,e_N)$ in a decreasing order, which is denoted $\vec{\bm{e}}(\bm{d})$.
\end{definition}

In this work, we consider caching systems with restricted demand types, i.e., it is known a priori that the demand vector must belong to a class of demand types. As a special case, if the class contains only one demand type, it will be referred to as a {\em single demand type system}. In this case, the demand vector set $\mathcal{D}=\mathcal{D}_{s}\triangleq\{\bm{d}:\vec{\bm{e}}(\bm{d})= \vec{\bm{e}}\}$ for some given demand type $\vec{\bm{e}}$. A second special case is when the class is restricted to be the demand types where all files are requested by at least one user, which is referred to as {\em the fully demanded system}. In this case, the demand vector set $\mathcal{D}=\mathcal{D}_{fd}\triangleq\{\bm{d}:\vec{\bm{e}}(\bm{d})~\text{such that}~e_i(\bm{d})>0, i=0,1,\ldots,N\}$. A third special case, where all possible demand vectors are allowed, is the original setting considered in \cite{MAN-14}, which will be referred to as the {\em fully mixed demand type system}. In this case, the demand vector set $\mathcal{D}=\mathcal{D}_{mixed}\triangleq\{1,2\dots,N\}^{K}$.

As an example, consider an $(N,K)=(3,3)$ system. When the demand vector $( d(1), d(2), d(3))=(2,2,1)$,  we have $\bm{e}(\bm{d})=(1,2,0)$ and $\vec{\bm{e}}(\bm{d})=(2,1,0)$. Therefore this demand vector belongs to the demand type $\bm{e}(\bm{d})=(2,1,0)$. More generally, demand type $\vec{\bm{e}}=(2,1,0)$ includes the following possible demand vectors in Table \ref{demand vectors}, which induce 6 different $\bm{e}(\bm{d})$ triples.

\begin{table}[h]
\centering
\caption{Demand vectors of demand type $(2,1,0)$ and the corresponding $\bm{e}(\bm{d})$}\label{demand vectors}
\scalebox{0.9}{
\begin{tabular}{|c|c|}
\hline
$\bm{e}(\bm{d})=(2,1,0)$ & $(1,1,2),(1,2,1),(2,1,1)$\\\hline
$\bm{e}(\bm{d})=(1,2,0)$ & $(2,2,1),(2,1,2), (1,2,2)$\\\hline
$\bm{e}(\bm{d})=(2,0,1)$ &$(1,1,3),(1,3,1),(3,1,1)$\\\hline
$\bm{e}(\bm{d})=(1,0,2)$ &$(3,3,1),(3,1,3), (1,3,3)$\\\hline
$\bm{e}(\bm{d})=(0,2,1)$ &$(2,2,3),(2,3,2),(3,2,2)$\\\hline
$\bm{e}(\bm{d})=(0,1,2)$ &$(3,3,2),(3,2,3)(2,3,3)$\\\hline
\end{tabular}}
\end{table}

\section{Mixed Demand Type and Single Demand Type Systems: The $(3,3)$ Case}

In this section, we consider the canonical $(N,K)=(3,3)$ system, and collect the best known inner bounds and outer bounds in the literature for different caching systems depending on the imposed demand type restrictions. This exercise reveals several important insights and fundamental differences between systems with different demand type restrictions.

\begin{figure}[tb]
\setlength{\belowcaptionskip}{-0.3cm}
  \centering
  \includegraphics[width=0.8\linewidth,draft=false]{Bound_for_3,32.pdf}\\
  \caption{Inner bounds and outer bounds for various $(3,3)$ systems.\label{figouterboundmix}}
\end{figure}

\subsection{The Fully Mixed Demand Type System}

The best known outer bound for this system can be found in \cite{Tian-18}, which are all the non-negative pairs of $(M,R)$ satisfying the constraints
\begin{gather*}
3M+R\geq 3,  6M+3R\geq 8,  M+R\geq 2,\\
2M+3R\geq 5, M+3R\geq 3.
\end{gather*}
The best known inner bound, on the other hand, is given by the lower convex hull of the points
\begin{align*}
(0,3),(1/3,2),(1/2,5/3),(3/5,3/2),(1,1),(2,1/3),(3,0),
\end{align*}
where the second and third points are achieved by the scheme in \cite{Jesus-18}, the fourth point is achieved by that in \cite{Cao-20}, while the others can be achieved by that in \cite{MAN-14}.

\subsection{Single Demand Type Systems}

Next we provide the best known results for the three single demand type systems.
\begin{enumerate}
    \item For the system with the demand type $(3,0,0)$, i.e., the same file is requested by all three users, the achievable region is all the non-negative $(M,R)$ such that
    \begin{align}
        M+3R\geq 3,
    \end{align}
    i.e., in this case, the inner bound and the outer bound match. The outer bound can be obtained by a simple cut-set argument \cite{MAN-14}, while the inner bound is trivial through a memory-sharing argument.
    \item For the system with the demand type $(2,1,0)$, the achievable region is all the non-negative $(M,R)$ such that
    \begin{equation*}
    M+ R \geq  2,  2M+ 3R\geq 5, M+ 3R \geq 3.
    \end{equation*}
    In this case, the corner points $(1,1)$ and $(2,1/3)$ can be achieved using the scheme in \cite{MAN-14}, and the points $(0,2)$ and $(3,0)$ are trivial. The outer bound was established in \cite{Tian-18}.
    \item For the system with the demand type $(1,1,1)$, the best known outer bound is given in \cite{Tian-18} as
    \begin{gather*}
3M+ R \geq3,6M+ 3R  \geq 8, M+ R  \geq2, \\
12M+ 18R  \geq29, 3M+ 6R  \geq8, M+ 3R  \geq 3.
\end{gather*}
The best known inner bound is given by the lower convex hull of the points
\begin{gather*}
   (0,3), (1/3,2), (1/2,5/3), (3/5,3/2), (1,1), \\
   (5/3,1/2), (2,1/3), (3,0).
\end{gather*}
The second and third points are achieved by the scheme in \cite{Jesus-18}, the point $(3/5,3/2)$ by that in \cite{Cao-20}, the point $(5/3,1/2)$ by that in \cite{Kumar-19}, and the others by that in \cite{MAN-14}.

\end{enumerate}

\subsection{Mixed Demand Types vs. Single Demand Type}

By comparing the rate regions of different demand type systems in Fig.\ref{figouterboundmix}, we make the following observations:
\begin{enumerate}
\item The point $(5/3,1/2)$, which is achievable for the system with the single demand type $(1,1,1)$ as shown in \cite{Kumar-19}, is in fact not achievable for the $(2,1,0)$ demand type system, thus also not achievable for the fully mixed demand type system.
\item Between mixed and single demand type systems, single demand type systems can indeed achieve lower rates than the fully mixed demand type system.
\item Different single demand type systems provide different outer bounds for the fully mixed demand type system, with the one with fewer files demanded produce better bounds at high memory regimes, while those with more files being better at low memory regimes.
\end{enumerate}

The first observation implies that the case when all files are requested is not necessarily the ``worst case", contrary to popular belief in the coded caching literature. Thus designing codes for this demand type alone is not sufficient to yield the optimal scheme for the fully mixed demand type systems. In fact, the optimal code design for fully demanded systems, though by itself already a challenging problem, can even be ``simpler'' than other cases. Motivated by the observations above and the code construction proposed in \cite{Kumar-19}, which only provided a single operating point when $N=K$, in the sequel we focus on fully demanded systems (implying that $N\leq K$), for general $(N,K)$ parameters.

\section{Main Results}

 Given a demand type $\vec{\bm{e}}$ which does not contain any zero elements, i.e., each file is being requested by at least one user, let $p_{\vec{\bm{e}}}$ be the number of ones in it, i.e., the number of files requested by only one user.
 The \textit{delivery rate compression saving factor}, $S(\vec{\bm{e}},r)$ for $r=\left\{ 0,...,K-1\right\}$, is defined as
\begin{align}
S(\vec{\bm{e}},r)=\frac{(K-p_{\vec{\bm{e}}})\binom{K-1-N}{r+1}+p_{\vec{\bm{e}}}\binom{K-1-(N-1)}{r+1}}{K\binom{K-1}{r}},
\end{align}
where we have taken the convention that $\binom{k}{n}=0$ when $k\leq n$. The \textit{delivery rate compression saving factor} accounts for the rate reduction in the transmission rate when linear dependence may be found among transmitted symbols in the delivery phase. Observe that $S(\vec{\bm{e}},r)=0$ when $K=N$, and it generally increases when $K$ increases.

The performance of the proposed scheme is summarized in the following theorem.

\begin{theorem}
\label{thm1 iq channel}
For an $(N,K)$ fully demand caching system (implying $N\leq K$) where only a single demand type $\vec{\bm{e}}$ is allowed, the following memory-rate pairs are achievable:

\begin{align}
\left(M,R(\vec{\bm{e})}\right)=\left(r\frac{N-1}{K-1}+\frac{r+1}{K},\frac{K-1-r}{r+1}-S(\vec{\bm{e}},r)\right)
\end{align}
for $r=\left\{ 0,...,K-1\right\}$.
\end{theorem}

The proof of theorem is given in the next section. It will be clear from the proposed code construction that the restriction on the demand types simplifies the design of the prefetching. More precisely, it is  effective to prefetch certain coded symbols involving all files, because any file will be requested eventually in such systems.

 Since in the proposed code construction, the prefetching strategy does not depend on the particular demand type, but only requires that all files are requested during the delivery phase, we can state the following theorem.

\begin{theorem}
\label{thm2 iq channel}
For an $(N,K)$ fully demanded caching system (implying $N\leq K$), the following memory-rate pairs are achievable:

\begin{align}
\left(M,R\right)=\left(r\frac{N-1}{K-1}+\frac{r+1}{K},\frac{K-1-r}{r+1}-S(\vec{\bm{e}^{\ast}},r)\right)

\end{align}
where the demand type $\vec{\bm{e}^{\ast}}$ is any that satisfies $p_{\vec{\bm{e}^{\ast}}}=\max(2N-K,0)$.

\end{theorem}

\begin{proof}
We will need to find the largest rate $R(\vec{\bm{e})}$ in Theorem \ref{thm1 iq channel}. The choice of $\vec{\bm{e}}$ that maximizes $R(\vec{\bm{e}})$ minimizes $S(\vec{\bm{e}},r)$, which in turn minimizes $p_{\vec{\bm{e}}}$, i.e., the number of files that are requested only by one user. If $K\geq2N$, we can set $p_{\vec{\bm{e}^{\ast}}}=0$ by choosing a demand type where every file is requested by at least two users. On the other hand, if $N\leq K<2N$, we minimize $p_{\bm{e}}$ by choosing a demand type where $N-p_{\vec{\bm{e}}}$ files are requested by one user and the other $N-p_{\vec{\bm{e}}}$ files are requested by two users, i.e., $p_{\vec{\bm{e}^{\ast}}}+2(N-p_{\vec{\bm{e}^{\ast}}})=K$.
\end{proof}

In an earlier version of this work \cite{SGZT-19}, we proposed a construction for $(N,K=N)$ systems, for which Theorem \ref{thm1 iq channel} provides a natural generalization. For $(N,K=N)$ fully demanded systems, by setting $r=K-2$, we recover the operating point given in \cite{Kumar-19}. In fact, our proposed construction in this work (sans the pairwise transformation) and that given in \cite{SGZT-19} essentially specialize to that in \cite{Kumar-19} by a proper relabeling of the file segments. On the other hand, setting $r=0$ gives the point in \cite{Chen-16} (see also \cite{T-C-18}). Operating points for other values of $r$ are previously unknown to be achievable.

The performance of the proposed construction is illustrated for $(N,K)=(4,6)$ and demand type $(3,1,1,1)$ in Fig. \ref{fig:46}; the operating points $(14/15,1.9)$, $(17/10,1)$, $(37/15,1/2)$ and $(97/30, 1/5)$ are previously unknown to be achievable in the existing literature.

As mentioned earlier, there exists a tension among the coding requirements of different demand types. Since our coding scheme is designed specifically for fully demanded systems, its performance naturally suffers when some files are not requested. In practice, this implies that the proposed code is more suitable when  with high probability all files will be requested. When it does occur that some files are not requested,  a straightforward solution is simply to use a higher rate of delivery. More precisely, the server can additionally transmit some parity check symbols of the files that are not being requested, and it can be shown that the additional communication cost in upper-bounded by $\frac{K}{r+1}-S(\vec{\bm{e}^{\ast}},r)$. Since the probability of these events happening is extreme low, the overall system performance would not be impacted significantly.
In other settings where some files are not being requested more frequently, the proposed code is less suitable; nevertheless, at the expense of losing some performance, the virtual user technique given in \cite{Jesus-18-1} can be evoked to accommodate such situations.

\begin{figure}[tb]

\centering

\includegraphics[width=0.8\linewidth]{figure.pdf}

\caption{Inner bounds for $(N,K)=(4,6)$ and demand type $(3,1,1,1)$.}
\label{fig:46}
\end{figure}

\section{Coding Scheme for Fully Demanded Coded Caching Systems}\label{general scheme}

The proposed code construction consists of multiple components which rely on each other to function as a whole. These components are: a novel file partition strategy, a prefetching strategy, a pairwise transformation, a delivery strategy, and a decoding strategy. The construction is parametrized by an integer $r$, whose meaning will become clear in the sequel. Throughout the section, we use $(N,K)=(3,6)$ and $r=1$ as our running example, and will provide details for this example whenever possible.

\subsection{A Novel File Partition Strategy}

\begin{table*}[htbp]
\caption{File partition of $W_1$ in $(N,K)=(3,6)$
code caching system when $r=1$}
\label{table: file partition}
\centering
\scalebox{0.85}{
\scriptsize{
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
\diagbox[dir=SE]{$s$}{$\mathcal{R}$}& $\mathcal{R}=\{1\}$ &$\mathcal{R}=\{2\}$ & $\mathcal{R}=\{3\}$ & $\mathcal{R}=\{4\}$ & $\mathcal{R}=\{5\}$ & $\mathcal{R}=\{6\}$\\\hline
\multirow{3}{*}{\begin{tabular}[c]{@{}c@{}} $s=1$ \end{tabular}}
&
&\textcolor{blue}{$W^{I}_{1,\{2\},1}$, $W^{Q}_{1,\{2\},1}$}
&\textcolor{blue}{$W^{I}_{1,\{3\},1}$, $W^{Q}_{1,\{3\},1}$}
&\textcolor{blue}{$W^{I}_{1,\{4\},1}$, $W^{Q}_{1,\{4\},1}$}
&\textcolor{blue}{$W^{I}_{1,\{5\},1}$, $W^{Q}_{1,\{5\},1}$}
&\textcolor{blue}{$W^{I}_{1,\{6\},1}$, $W^{Q}_{1,\{6\},1}$}\\
&
&\textcolor{blue}{$W^{I}_{2,\{2\},1}$, $W^{Q}_{2,\{2\},1}$}
&\textcolor{blue}{$W^{I}_{2,\{3\},1}$, $W^{Q}_{2,\{3\},1}$}
&\textcolor{blue}{$W^{I}_{2,\{4\},1}$, $W^{Q}_{2,\{4\},1}$}
&\textcolor{blue}{$W^{I}_{2,\{5\},1}$, $W^{Q}_{2,\{5\},1}$}
&\textcolor{blue}{$W^{I}_{2,\{6\},1}$, $W^{Q}_{2,\{6\},1}$}\\
&
&\textcolor{blue}{$W^{I}_{3,\{2\},1}$, $W^{Q}_{3,\{2\},1}$}
&\textcolor{blue}{$W^{I}_{3,\{3\},1}$, $W^{Q}_{3,\{3\},1}$}
&\textcolor{blue}{$W^{I}_{3,\{4\},1}$, $W^{Q}_{3,\{4\},1}$}
&\textcolor{blue}{$W^{I}_{3,\{5\},1}$, $W^{Q}_{3,\{5\},1}$}
&\textcolor{blue}{$W^{I}_{3,\{6\},1}$, $W^{Q}_{3,\{6\},1}$}\\
\hline
\multirow{3}{*}{\begin{tabular}[c]{@{}c@{}} $s=2$ \end{tabular}}
&\textcolor{red}{$W^{I}_{1,\{1\},2}$, $W^{Q}_{1,\{1\},2}$}
&
&$W^{I}_{1,\{3\},2}$, $W^{Q}_{1,\{3\},2}$ &$W^{I}_{1,\{4\},2}$, $W^{Q}_{1,\{4\},2}$ &$W^{I}_{1,\{5\},2}$, $W^{Q}_{1,\{5\},2}$ &$W^{I}_{1,\{6\},2}$, $W^{Q}_{1,\{6\},2}$\\
&\textcolor{red}{$W^{I}_{2,\{1\},2}$, $W^{Q}_{2,\{1\},2}$}
&
&$W^{I}_{2,\{3\},2}$, $W^{Q}_{2,\{3\},2}$ &$W^{I}_{2,\{4\},2}$, $W^{Q}_{2,\{4\},2}$ &$W^{I}_{2,\{5\},2}$, $W^{Q}_{2,\{5\},2}$ &$W^{I}_{2,\{6\},2}$, $W^{Q}_{2,\{6\},2}$\\
&\textcolor{red}{$W^{I}_{3,\{1\},2}$, $W^{Q}_{3,\{1\},2}$}
&
&$W^{I}_{3,\{3\},2}$, $W^{Q}_{3,\{3\},2}$ &$W^{I}_{3,\{4\},2}$, $W^{Q}_{3,\{4\},2}$ &$W^{I}_{3,\{5\},2}$, $W^{Q}_{3,\{5\},2}$ &$W^{I}_{3,\{6\},2}$, $W^{Q}_{3,\{6\},2}$\\
\hline
\multirow{3}{*}{\begin{tabular}[c]{@{}c@{}} $s=3$ \end{tabular}}
&\textcolor{red}{$W^{I}_{1,\{1\},3}$, $W^{Q}_{1,\{1\},3}$}
&$W^{I}_{1,\{2\},3}$, $W^{Q}_{1,\{2\},3}$
&
&$W^{I}_{1,\{4\},3}$, $W^{Q}_{1,\{4\},3}$ &$W^{I}_{1,\{5\},3}$, $W^{Q}_{1,\{5\},3}$ &$W^{I}_{1,\{6\},3}$, $W^{Q}_{1,\{6\},3}$\\
&\textcolor{red}{$W^{I}_{2,\{1\},3}$, $W^{Q}_{2,\{1\},3}$}
&$W^{I}_{2,\{2\},3}$, $W^{Q}_{2,\{2\},3}$
&
&$W^{I}_{2,\{4\},3}$, $W^{Q}_{2,\{4\},3}$ &$W^{I}_{2,\{5\},3}$, $W^{Q}_{2,\{5\},3}$ &$W^{I}_{2,\{6\},3}$, $W^{Q}_{2,\{6\},3}$\\
&\textcolor{red}{$W^{I}_{3,\{1\},3}$, $W^{Q}_{3,\{1\},3}$}
&$W^{I}_{3,\{2\},3}$, $W^{Q}_{3,\{2\},3}$
&
&$W^{I}_{3,\{4\},3}$, $W^{Q}_{3,\{4\},3}$ &$W^{I}_{3,\{5\},3}$, $W^{Q}_{3,\{5\},3}$ &$W^{I}_{3,\{6\},3}$, $W^{Q}_{3,\{6\},3}$\\
\hline
\multirow{3}{*}{\begin{tabular}[c]{@{}c@{}} $s=4$ \end{tabular}}
&\textcolor{red}{$W^{I}_{1,\{1\},4}$, $W^{Q}_{1,\{1\},4}$}
&$W^{I}_{1,\{2\},4}$, $W^{Q}_{1,\{2\},4}$
&$W^{I}_{1,\{3\},4}$, $W^{Q}_{1,\{3\},4}$
&
&$W^{I}_{1,\{5\},4}$, $W^{Q}_{1,\{5\},4}$ &$W^{I}_{1,\{6\},4}$, $W^{Q}_{1,\{6\},4}$\\
&\textcolor{red}{$W^{I}_{2,\{1\},4}$, $W^{Q}_{2,\{1\},4}$}
&$W^{I}_{2,\{2\},4}$, $W^{Q}_{2,\{2\},4}$
&$W^{I}_{2,\{3\},4}$, $W^{Q}_{2,\{3\},4}$
&
&$W^{I}_{2,\{5\},4}$, $W^{Q}_{2,\{5\},4}$ &$W^{I}_{2,\{6\},4}$, $W^{Q}_{2,\{6\},4}$\\
&\textcolor{red}{$W^{I}_{3,\{1\},4}$, $W^{Q}_{3,\{1\},4}$}
&$W^{I}_{3,\{2\},4}$, $W^{Q}_{3,\{2\},4}$
&$W^{I}_{3,\{3\},4}$, $W^{Q}_{3,\{3\},4}$
&
&$W^{I}_{3,\{5\},4}$, $W^{Q}_{3,\{5\},4}$ &$W^{I}_{3,\{6\},4}$, $W^{Q}_{3,\{6\},4}$\\
\hline
\multirow{3}{*}{\begin{tabular}[c]{@{}c@{}} $s=5$ \end{tabular}}
&\textcolor{red}{$W^{I}_{1,\{1\},5}$, $W^{Q}_{1,\{1\},5}$}
&$W^{I}_{1,\{2\},5}$, $W^{Q}_{1,\{2\},5}$
&$W^{I}_{1,\{3\},5}$, $W^{Q}_{1,\{3\},5}$
&$W^{I}_{1,\{4\},5}$, $W^{Q}_{1,\{4\},5}$
&
&$W^{I}_{1,\{6\},5}$, $W^{Q}_{1,\{6\},5}$\\
&\textcolor{red}{$W^{I}_{2,\{1\},5}$, $W^{Q}_{2,\{1\},5}$}
&$W^{I}_{2,\{2\},5}$, $W^{Q}_{2,\{2\},5}$
&$W^{I}_{2,\{3\},5}$, $W^{Q}_{2,\{3\},5}$
&$W^{I}_{2,\{4\},5}$, $W^{Q}_{2,\{4\},5}$
&
&$W^{I}_{2,\{6\},5}$, $W^{Q}_{2,\{6\},5}$\\
&\textcolor{red}{$W^{I}_{3,\{1\},5}$, $W^{Q}_{3,\{1\},5}$}
&$W^{I}_{3,\{2\},5}$, $W^{Q}_{3,\{2\},5}$
&$W^{I}_{3,\{3\},5}$, $W^{Q}_{3,\{3\},5}$
&$W^{I}_{3,\{4\},5}$, $W^{Q}_{3,\{4\},5}$
&
&$W^{I}_{3,\{6\},5}$, $W^{Q}_{3,\{6\},5}$\\
\hline
\multirow{3}{*}{\begin{tabular}[c]{@{}c@{}} $s=6$ \end{tabular}}
&\textcolor{red}{$W^{I}_{1,\{1\},6}$, $W^{Q}_{1,\{1\},6}$}
&$W^{I}_{1,\{2\},6}$, $W^{Q}_{1,\{2\},6}$
&$W^{I}_{1,\{3\},6}$, $W^{Q}_{1,\{3\},6}$
&$W^{I}_{1,\{4\},6}$, $W^{Q}_{1,\{4\},6}$
&$W^{I}_{1,\{5\},6}$, $W^{Q}_{1,\{5\},6}$
&\\
&\textcolor{red}{$W^{I}_{2,\{1\},6}$, $W^{Q}_{2,\{1\},6}$}
&$W^{I}_{2,\{2\},6}$, $W^{Q}_{2,\{2\},6}$
&$W^{I}_{2,\{3\},6}$, $W^{Q}_{2,\{3\},6}$
&$W^{I}_{2,\{5\},6}$, $W^{Q}_{2,\{5\},6}$
&$W^{I}_{2,\{6\},6}$, $W^{Q}_{2,\{6\},6}$
&\\
&\textcolor{red}{$W^{I}_{3,\{1\},6}$, $W^{Q}_{3,\{1\},6}$}
&$W^{I}_{3,\{2\},6}$, $W^{Q}_{3,\{2\},6}$
&$W^{I}_{3,\{3\},6}$, $W^{Q}_{3,\{3\},6}$
&$W^{I}_{3,\{4\},6}$, $W^{Q}_{3,\{4\},6}$
&$W^{I}_{3,\{5\},6}$, $W^{Q}_{3,\{5\},6}$
&\\
\hline
\end{tabular}
}}
\end{table*}

Let $r$ be a positive integer in the set $\{0,1,\ldots,K-1\}$, and let $|\mathcal{C}|$ be the cardinality of the set $\mathcal{C}$. In the proposed partition strategy, each file is partitioned into a total of $2(K-r)\binom{K}{r}$ segments, resulting in file segments denoted as $W^{A}_{f,\mathcal{R},s}$, through three steps. In the first step, each file $W_f$ is partitioned into $\binom{K}{r}$ equal-sized sub-files, resulting in the corresponding subscript label $\mathcal{R}\subset \mathcal{K}$ and $|\mathcal{R}|=r$.
In the second step, each such subfile is further partitioned into $(K-r)$ small subfiles of equal size, resulting in the corresponding subscript label $s\in \mathcal{K}\setminus \mathcal{R}$. In the third step, each small subfile is finally partitioned into two equal-sized segments, which are called the ``I channel" segment and ``Q channel" segments, resulting in the superscript label $A\in \{I,Q\}$.

Consider our running example $(N,K)=(3,6)$ and $r=1$: here each file is partitioned into $2*(6-1)\binom{6}{1}=60$ segments, which are listed in Table \ref{table: file partition}.

\subsection{Prefetching}\label{prefetching}

In the prefetching phase, the I-channel and the Q-channel are prefetched in the same manner for each user $k\in \mathcal{K}$, independent of each other; for conciseness, we will use $A$ to denote either  $I$ or $Q$.

\subsubsection{Uncoded content} The uncoded segments $W^{A}_{f,\mathcal{R},s}$ are placed into the cache memory of user $k$, for every $f\in\mathcal{F}$, every $\mathcal{R}$ such that $k\in \mathcal{R}$, every $s \notin \mathcal{R}$, and every $A\in \{I,Q\}$. A total of $m_1=2N\binom{ K-1}{r-1}( K-r)$ such segments are prefetched at user $k$. For our running example $(N,K)=(3,6)$ and $r=1$, the segments labeled red in Table \ref{table: file partition} are directly placed in the cache of user-$1$ in the uncoded form.

\subsubsection{Coded content}

The coded content prefetched by user $k$ can be conveniently viewed as the parities of a product code \cite{Lin:01}: the segments with the same index $s=k$ (and the same channel) are placed in a matrix, where each row contains the segments of the same file index (i.e., the same $f$ index), and each column contains the segments of the same  $\mathcal{R}$ index.  For our running example, this matrix is shown in Table \ref{table: product code} in blue for user-1, which correspond to the elements in Table \ref{table: file partition}  that are also labeled blue. The coded symbols are then prefetched using this matrix as follows.

\begin{table*}[htbp]
\centering
\caption{Designing encoded prefetching via a product code}
\label{table: product code}
\scalebox{0.6}{
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
 & \multirow{2}{*}{\begin{tabular}[c]{@{}c@{}} $\mathcal{R}=\{2\}$ \end{tabular}}
 & \multirow{2}{*}{\begin{tabular}[c]{@{}c@{}} $\mathcal{R}=\{3\}$ \end{tabular}}
 & \multirow{2}{*}{\begin{tabular}[c]{@{}c@{}} $\mathcal{R}=\{4\}$ \end{tabular}}
 & \multirow{2}{*}{\begin{tabular}[c]{@{}c@{}} $\mathcal{R}=\{5\}$ \end{tabular}}
 & \multirow{2}{*}{\begin{tabular}[c]{@{}c@{}} $\mathcal{R}=\{6\}$ \end{tabular}}
 & Row \\
 & & & & & & parity check
 \\
\hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}} $f= 1$ \end{tabular}}
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  \textcolor{blue}{$W^A_{1,\{2\},1}$} \end{tabular}}
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  \textcolor{blue}{$W^A_{1,\{3\},1}$} \end{tabular}}
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  \textcolor{blue}{$W^A_{1,\{4\},1}$} \end{tabular}}
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  \textcolor{blue}{$W^A_{1,\{5\},1}$} \end{tabular}}
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  \textcolor{blue}{$W^A_{1,\{6\},1}$} \end{tabular}}
&\dout{\textcolor{brown}{$Z^A_{1,\emptyset,1}=$}}

\\
& & & & & &
\dout{\textcolor{brown}{$\bigoplus_{r\in [2:6]} W^A_{1,\{r\},1} $}}

\\
\hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  $f=2$ \end{tabular}}
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  \textcolor{blue}{$W^A_{2,\{2\},1}$} \end{tabular}}
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  \textcolor{blue}{$W^A_{2,\{3\},1}$} \end{tabular}}
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  \textcolor{blue}{$W^A_{2,\{4\},1}$} \end{tabular}}
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  \textcolor{blue}{$W^A_{2,\{5\},1}$} \end{tabular}}
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  \textcolor{blue}{$W^A_{2,\{6\},1}$} \end{tabular}}
&\textcolor{brown}{$Z^A_{2,\emptyset,1}=$} \\
& & & & & &
\textcolor{brown}{$\bigoplus_{r\in [2:6]} W^A_{2,\{r\},1} $}\\
\hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}} $f = 3$ \end{tabular}}
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  \textcolor{blue}{$W^A_{3,\{2\},1}$} \end{tabular}}
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  \textcolor{blue}{$W^A_{3,\{3\},1}$} \end{tabular}}
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  \textcolor{blue}{$W^A_{3,\{4\},1}$} \end{tabular}}
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  \textcolor{blue}{$W^A_{3,\{5\},1}$} \end{tabular}}
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  \textcolor{blue}{$W^A_{3,\{6\},1}$} \end{tabular}}
&\textcolor{brown}{$Z^A_{3,\emptyset,1}=$} \\
& & & & & &
\textcolor{brown}{$\bigoplus_{r\in [2:6]} W^A_{3,\{r\},1} $}\\
\hline
Column
& \textcolor{purple}{$Z^A_{\{2\},1}=$}
&\textcolor{purple}{$Z^A_{\{3\},1}=$}
&\textcolor{purple}{$Z^A_{\{4\},1}=$}
&\textcolor{purple}{$Z^A_{\{5\},1}=$}
&\textcolor{purple}{$Z^A_{\{6\},1}=$}
&\\
parity check
& \textcolor{purple}{$\bigoplus_{f\in [1:3]} W^A_{f,\{2\},1} $}
&\textcolor{purple}{$\bigoplus_{f\in [1:3]} W^A_{f,\{3\},1} $}
&\textcolor{purple}{$\bigoplus_{f\in [1:3]} W^A_{f,\{4\},1} $}
&\textcolor{purple}{$\bigoplus_{f\in [1:3]} W^A_{f,\{5\},1} $}
&\textcolor{purple}{$\bigoplus_{f\in [1:3]} W^A_{f,\{6\},1} $}
&\\
\hline
\end{tabular}
}
\end{table*}

\begin{itemize}
\item Column parity checks: These coded symbols $Z^{A}_{\mathcal{R},k}$'s are the parities for the column indexed by $\mathcal{R}$, i.e.,
\begin{align}
Z^{A}_{\mathcal{R},k}=\bigoplus_{f\in\mathcal{F}}W^{A}_{f,\mathcal{R},k}
\end{align}
for all possible set $\mathcal{R}$ satisfying $k\notin\mathcal{R}$. Clearly, there are $m_2=2\binom{ K-1}{r}$ such symbols, where the factor $2$ is due to the dual $I,Q$ channels.

\item Row parity checks:

For the row corresponding to file index $f$, there will be multiple row parities, and let us focus on one fixed $f$, i.e., one row. For each $\mathcal{R}^{-}\subseteq \mathcal{K} \backslash \{k\}$ where $|\mathcal{R}^{-}|=r-1$, a row parity $Z^{A}_{f,\mathcal{R}^{-},k}$ is given by
\begin{align}
  Z^{A}_{f,\mathcal{R}^{-},k}=\bigoplus_{u\in\mathcal{ K\backslash}(\mathcal{R}^{-}\cup \{k\})} W^{A}_{f,\{u\}\cup\mathcal{R}^{-},k}.
\end{align}

Due to the inherent linear dependency in product codes, only some of these row parities need to prefetched. More precisely, let
\begin{eqnarray*}
l_k & \triangleq & \begin{cases}
2 & \text{if $k=1$}\\
1 & \text{otherwise}\\
 \end{cases},
\end{eqnarray*}
then the prefetched row parities are $Z^{A}_{f,\mathcal{R}^{-},k}$ where $f\in\mathcal{F}\backslash \{1\}$ and $\mathcal{R}^{-}\subseteq \mathcal{K} \backslash \{k,l_k\}$ such that
$\left|\mathcal{R}^{-}\right|=r-1$.

It is clear that the total number of prefetched row parities is $m_3=2(N-1)\binom{ K-2}{r-1}$.

\end{itemize}

 The column and row parities at user-1 in our running example are given in Table \ref{table: product code}. The column parities are labeled purple, and the row parity bits are labeled brown, where $Z^A_{1,\emptyset,1}$ is not prefetched (strikethrough in the table). Since in this case $\mathcal{R}^{-}$ can only be the empty set, there is only one parity per row.

Collecting all the prefetched content, it is seen that the normalized cache size is
\begin{align}
M  =  \frac{m_1+m_2+m_3}{2K\binom{ K-1}{r}}=r\frac{N-1}{K-1}+\frac{r+1}{K}.
\end{align}

The linear dependence among the coded parities is made more precise in the following lemma.
\begin{lemma}\label{lemma: linear dependence}
Consider a fixed user $k$ and subset $\mathcal{R}^-_*\subset \mathcal{K}\setminus\{k\}$, where $l_k\in\mathcal{R}^-_*$ and $|\mathcal{R}^-_*|=r-1$, then for any $f\in \mathcal{F}$,

\begin{align}
  Z^{A}_{f,\mathcal{R}^{-}_*,k}
  =\bigoplus_{h\in\mathcal{K}\setminus(\{k\}\cup \mathcal{R}^-_*)} Z^{A}_{f, (\mathcal{R}^-_*\setminus\{l_k\})\cup\{h\},k}.\label{eq: linear dependence 1}
\end{align}

Moreover, we have
\begin{align}
  Z^{A}_{1,\mathcal{R}^{-},k}=   \bigoplus_{\mathcal{R}: \mathcal{R}^{-}\subseteq \mathcal{R}, k\notin \mathcal{R}}
Z^{A}_{\mathcal{R},k}\oplus \bigoplus_{f\in \mathcal{F}\backslash\{1\}} Z^{A}_{f,\mathcal{R}^{-},k}.
  \label{eq: linear dependence 2}
\end{align}
\end{lemma}

The proof of this lemma can be found in Appendix \ref{Appendix remark}. Essentially, this lemma states that all the row parities can be computed using only the prefetched parities. Consider again our running example. The parity $Z^{A}_{1,\emptyset,1}$ can be computed according to \eqref{eq: linear dependence 2} in Lemma \ref{lemma: linear dependence} as
\begin{align*}
  Z^{A}_{1,\emptyset,1}

= & \bigoplus_{t\in \{2,3,4,5,6\}} Z^{A}_{\{t\},1} \oplus \bigoplus_{f\in \{2,3\}}  Z^{A}_{f,\emptyset,1}.
\end{align*}

\subsection{Pairwise Transformation for Delivery}\label{transformation}

In our previous work \cite{SGZT-19} where $N=K$, a delivery strategy was provided to cancel certain interference symbols in the coded prefetched symbols to improve the delivery efficiency.
However, when $K \geq N$ and some file $W_n$ is requested by an even number of users, this interference cancellation strategy would not succeed. In order to create the same cancellation effect in such cases, we have to create such an opportunity by increasing the dimension of the message space. This process is reminiscent of the interference alignment technique \cite{Jafar-08} in channel coding, where vector space techniques are essential.
The I/Q channel structure and the corresponding pairwise transformation are therefore introduced for this purpose, which we provide next.

The delivery process will go through all $s\in\mathcal{K}$, and in the following we shall discuss a fixed $s$. For a demand $\bm{d}$, we denote $K_{f}$ as the number of users requesting file $W_{f}$. Correspondingly, denote the set of indices of these users as $\mathcal{K}_f$. For any $s\in\mathcal{K}$, denote its complement set as
\begin{align}
\mathcal{C}_s \triangleq \mathcal{K}\backslash \{s\}. \label{eqn:U}
\end{align}
Among the users $\mathcal{C}_s$ that request file $W_f$, let the lowest indexed user be the \textit{leader} in $\mathcal{K}_f$, denoted as $u_{f}$.
The transformed segment pair $(W_{ d(t),\mathcal{R},s}^{(T),I},W_{ d(t),\mathcal{R},s}^{(T),Q})$ for $t,s\in\mathcal{K}$ is given by
\begin{align} \label{eq:defofTForW}
    \begin{bmatrix}W_{ d(t),\mathcal{R},s}^{(T),I}\\W_{ d(t),\mathcal{R},s}^{(T),Q} \end{bmatrix} =\mathbf{T}_{t,s}  \begin{bmatrix}W_{ d(t),\mathcal{R},s}^{I}\\W_{ d(t),\mathcal{R},s}^{Q} \end{bmatrix},
\end{align}
where $\mathbf{T}_{t,s}$ is given next.
If $ d(t)= d(s)$, then define
\begin{eqnarray}
\mathbf{T}_{t,s} \triangleq \begin{cases}
\begin{bmatrix}1 & 0\\0 & 1 \end{bmatrix}
 \vspace{0.3cm}
 & \text{if \ensuremath{K_{d(t)}\text{ is odd}}}\\
 \vspace{0.3cm}
 \begin{bmatrix}1 & 1\\1 & 0 \end{bmatrix}  & \text{if \ensuremath{K_{d(t)}\text{ is even and $t\neq s$}}}.\\
  \begin{bmatrix}0 & 1\\1 & 1 \end{bmatrix}  & \text{if \ensuremath{K_{d(t)}\text{ is even and $t= s$}}}
 \end{cases}\label{eq:1}
\end{eqnarray}

On the other hand,  if $ d(t)\neq d(s)$, define
 \begin{equation}
 \mathbf{T}_{t,s}\triangleq\begin{cases}
  \vspace{0.3cm}
 \begin{bmatrix}1 & 0\\0 & 1 \end{bmatrix} & \text{if \ensuremath{\ensuremath{\mathcal{K}_{ d(t)}}} is odd}\\
  \vspace{0.3cm}
 \begin{bmatrix}1 & 1\\1 & 0 \end{bmatrix} & \text{if \ensuremath{\mathcal{K}_{ d(t)}} is even and \ensuremath{t\neq u_{d(t)}}}\\
 \begin{bmatrix}0 & 1\\1 & 1 \end{bmatrix} & \text{if \ensuremath{\mathcal{K}_{ d(t)}} is even and \ensuremath{t=u_{d(t)}}}
 \end{cases}.\label{eq:2}
 \end{equation}

In other words, when file $W_{f}$ is requested by an odd number of users, the transformed pair  $(W_{f,\mathcal{R},s}^{(T),I},W_{f,\mathcal{R},s}^{(T),Q})$ are identical to the orginal segment pair $(W_{f,\mathcal{R},s}^{I},W_{f,\mathcal{R},s}^{Q})$; when file $W_{f}$ is requested by an even number of users, an invertible transformation is applied.

In our running example, when the demand vector is $(1,1,1,1,2,3)$, consider the case $t=2$, $s=1$, and $\mathcal{R}=\{3\}$. Since $d(t)=d(s)$ and $K_1=4$, the \textcolor{black}{transformed segments} are given as
\begin{align*}
  &W_{d(t),\mathcal{R},s}^{(T),I}|_{t=2,s=1,\mathcal{R}=\{3\}}= W_{1,\{3\},1}^I\oplus W_{1,\{3\},1}^Q,\\
  &W_{d(t),\mathcal{R},s}^{(T),Q}|_{t=2,s=1,\mathcal{R}=\{3\}}= W_{1,\{3\},1}^I,
\end{align*}
by \eqref{eq:1}. Next consider another case where $t=2$, $s=5$, and $\mathcal{R}=\{3\}$. Since $d(s)\neq d(t)$, $K_{d(t)}=K_1=4$, and the leader of $\mathcal{K}_1$ is $u_{d(t)}=1$, we have $t\neq u_{d(t)}$. Hence,
\eqref{eq:2} gives
\begin{align*}
  &W_{d(t),\mathcal{R},s}^{(T),I}|_{t=2,s=5,\mathcal{R}=\{3\}}= W_{1,\{3\},5}^I\oplus W_{1,\{3\},5}^Q,\\
  &W_{d(t),\mathcal{R},s}^{(T),Q}|_{t=2,s=5,\mathcal{R}=\{3\}}= W_{1,\{3\},5}^I.
\end{align*}
Table \ref{table: intermediate} shows all the transformed segments for $s=1$.
\begin{table}[tb]
\centering
\caption{Transformed segments for $s=1$ \label{table: intermediate}}
\scalebox{0.9}{
\begin{tabular}{|c|c|c|}
\hline
$t\in \mathcal{K}\backslash \{1\}$  &  $W_{d(t),\mathcal{R},1}^{(T),I}$    &   $W_{d(t),\mathcal{R},1}^{(T),Q}$\\ \hline
2 & $W_{1,\mathcal{R},1}^{I}\oplus W_{1,\mathcal{R},1}^{Q}$& $W_{1,\mathcal{R},1}^{I}$ \\ \hline
3 & $W_{1,\mathcal{R},1}^{I}\oplus W_{1,\mathcal{R},1}^{Q}$& $W_{1,\mathcal{R},1}^{I}$  \\ \hline
4 & $W_{1,\mathcal{R},1}^{I}\oplus W_{1,\mathcal{R},1}^{Q}$& $W_{1,\mathcal{R},1}^{I}$  \\ \hline
5 & $W_{2,\mathcal{R},1}^{I}$ & $W_{2,\mathcal{R},1}^{Q}$ \\ \hline
6 & $W_{3,\mathcal{R},1}^{I}$ & $W_{3,\mathcal{R},1}^{Q}$  \\ \hline
\end{tabular}}
\end{table}

\subsection{Delivery Strategy}
\label{delivery}
The delivery strategy has certain similarity to that in \cite{MAN-14} and \cite{Yu-18}. For an arbitrary $s\in \mathcal{K}$ and set $\mathcal{R}^{+} \subseteq \mathcal{K}\backslash \{s\}$ with $r+1$ users, i.e., $\left|\mathcal{R}^{+}\right|=r+1$, the message $Y^{A}_{\mathcal{R}^{+},s}$ is defined as
\begin{eqnarray}\label{eq:delivery}
Y^{A}_{\mathcal{R}^{+},s} & = & \bigoplus_{t\in\mathcal{R}^{+}}W^{(T),A}_{ d(t),\mathcal{R}^{+}\backslash t,s} \label{allY}
\end{eqnarray}
for both $A=I$ and $Q$. In our running example with demand $\bm{d} = (1,1,1,1,2,3)$, these coded symbols for $s=1$ are shown in Table \ref{table:IQ2}.

Due to the inherent linear dependence,  not all of the coded symbols given above are transmitted. Recall the definition of $\mathcal{C}_s$ in (\ref{eqn:U}), and we further define the leader set to be
\begin{align*}
    \mathcal{L}_s = \{u_{d(t)}: t \in \mathcal{C}_s\}.
\end{align*}
If some $\mathcal{R}^+$ satisfies that $\mathcal{R}^+ \subseteq \mathcal{C}_s$ and $\mathcal{R}^+ \cap \mathcal{L}_s = \emptyset$,

then the corresponding encoded segments $Y^{A}_{\mathcal{R}^{+},s}$ are not transmitted for both $A=I$ and $Q$. This is similar to the improved delivery strategy in \cite{Yu-18}, and the following lemma makes this linear dependence among $Y^{A}_{\mathcal{R}^{+},s}$'s more precise.
\begin{lemma}\label{lemma:redundancy}

For given $s\in \mathcal{K}$ and subset $\mathcal{B}$ such that $\mathcal{L}_s\subset \mathcal{B} \subseteq \mathcal{C}_s$ and $|\mathcal{B}|=|\mathcal{L}_s|+r+1$, let $\mathcal{V}_F$ be a superset of all subsets $\mathcal{V}$ of $\mathcal{B}$ such that each file is requested by exactly one user in $\mathcal{V}$. Then
\begin{align*}
\bigoplus_{\mathcal{V} \in \mathcal{V}_F} Y_{\mathcal{B} \backslash \mathcal{V},s}^I = 0, \quad\bigoplus_{\mathcal{V} \in \mathcal{V}_F} Y_{\mathcal{B} \backslash \mathcal{V},s}^Q = 0.
\end{align*}
\end{lemma}
Lemma \ref{lemma:redundancy} can be proved in an almost identical manner as that in \cite[Lemma 1]{Yu-18}. The only difference is that in our setting, the dependence is considered for each fixed index $s\in \mathcal{K}$, and we operate on the transformed segments instead of the original segments. Therefore, we omit the details of the proof, and readers can refer to \cite{Yu-18} directly.

By Lemma \ref{lemma:redundancy}, for any non-leader users set $\mathcal{R}^+$ such that $\mathcal{R}^+ \subseteq \mathcal{C}_s$ and $\mathcal{R}^+ \cap \mathcal{L}_s = \emptyset$, $Y_{\mathcal{R}^{+},s}^I$ and $Y_{\mathcal{R}^{+},s}^Q$ can be computed using the transmitted symbols
\begin{align*}
    Y_{\mathcal{R}^{+},s}^I = \bigoplus_{\mathcal{V} \in \mathcal{V}_F \backslash \{\mathcal{L}_s\}} Y_{\mathcal{B} \backslash \mathcal{V},s}^I \\
    Y_{\mathcal{R}^{+},s}^Q = \bigoplus_{\mathcal{V} \in \mathcal{V}_F \backslash \{\mathcal{L}_s\}} Y_{\mathcal{B}\backslash \mathcal{V},s}^Q.
\end{align*}
We shall directly assume that all the symbols in (\ref{allY}) are available at users from here on.

 In our running example, for $s=1$ we have $\mathcal{C}_1=\{2,3,4,5,6\}$ and $\mathcal{L}_1=\{2,5,6\}$. If $\mathcal{R}^+=\{3,4\}$, obviously $\mathcal{R}^+\cap \mathcal{L}_s= \emptyset$. Hence the messages $(Y^I_{\{3,4\},1},Y^Q_{\{3,4\},1})$ are not transmitted, which is indicated by the strikethrough in Table \ref{table:IQ2}. These two symbols can be computed as
\begin{align*}
    Y^{A}_{\{3,4\},1}=Y^{A}_{\{2,3\},1}\oplus Y^{A}_{\{2,4\},1},\quad A\in \{I,Q\}.
\end{align*}

\begin{table}[tb]
\centering
\caption{Delivery for Demand $\bm{d} = (1,1,1,1,2,3)$, $s=1$}
\label{table:IQ2}
\scalebox{0.75}{
\begin{tabular}{|c|c|c|}
\hline
& I-channel & Q-channel                                                                          \\ \hline
$Y^{A}_{\{2,3\},1}$ & $W_{1,\{3\},1}^I\oplus W_{1,\{3\},1}^Q \oplus W_{1,\{2\},1}^I\oplus W_{1,\{2\},1}^Q$ &  $W_{1,\{3\},1}^I \oplus W_{1,\{2\},1}^I$                        \\ \hline
$Y^{A}_{\{2,4\},1}$ & $W_{1,\{4\},1}^I\oplus W_{1,\{4\},1}^Q \oplus W_{1,\{2\},1}^I\oplus W_{1,\{2\},1}^Q$ &  $W_{1,\{4\},1}^I \oplus W_{1,\{2\},1}^I$     \\ \hline
$Y^{A}_{\{2,5\},1}$ & $W_{1,\{5\},1}^I\oplus W_{1,\{5\},1}^Q \oplus W_{2,\{2\},1}^I$             &  $W_{1,\{5\},1}^I \oplus W_{2,\{2\},1}^Q$  \\ \hline
$Y^{A}_{\{2,6\},1}$ & $W_{1,\{6\},1}^I\oplus W_{1,\{6\},1}^Q \oplus W_{3,\{2\},1}^I$             &  $W_{1,\{6\},1}^I \oplus W_{3,\{2\},1}^Q$                       \\ \hline
*$Y^{A}_{\{3,4\},1}$ &  \dout{$W_{1,\{4\},1}^I\oplus W_{1,\{4\},1}^Q \oplus W_{1,\{3\},1}^I\oplus W_{1,\{3\},1}^Q$}             &  \dout{$W_{1,\{4\},1}^I \oplus W_{1,\{3\},1}^I$}     \\ \hline
$Y^{A}_{\{3,5\},1}$ & $W_{1,\{5\},1}^I\oplus W_{1,\{5\},1}^Q \oplus W_{2,\{3\},1}^I$             &  $W_{1,\{5\},1}^I \oplus W_{2,\{3\},1}^Q$     \\ \hline
$Y^{A}_{\{3,6\},1}$ & $W_{1,\{6\},1}^I\oplus W_{1,\{6\},1}^Q \oplus W_{3,\{3\},1}^I$             &  $W_{1,\{6\},1}^I \oplus W_{3,\{3\},1}^Q$                         \\ \hline
$Y^{A}_{\{4,5\},1}$ & $W_{1,\{5\},1}^I\oplus W_{1,\{5\},1}^Q \oplus W_{2,\{4\},1}^I$             &  $W_{1,\{5\},1}^I \oplus W_{2,\{4\},1}^Q$     \\ \hline
$Y^{A}_{\{4,6\},1}$ & $W_{1,\{6\},1}^I\oplus W_{1,\{6\},1}^Q \oplus W_{3,\{4\},1}^I$             &  $W_{1,\{6\},1}^I \oplus W_{3,\{4\},1}^Q$     \\ \hline
$Y^{A}_{\{5,6\},1}$ & $W_{2,\{6\},1}^I \oplus W_{3,\{5\},1}^I$             &  $W_{2,\{6\},1}^Q \oplus W_{3,\{5\},1}^Q$   \\ \hline
\end{tabular}}
\end{table}

For each $s \in \mathcal{K}, |\mathcal{C}_s| = K-1 $ and the number of leaders among users $\mathcal{C}_s$ is exactly $|\mathcal{L}_s|=N-1$ if user $s$ is the only user that request file $W_{d(s)}$ and $|\mathcal{L}_s|=N$ other wise. The number of skipped $Y_{\mathcal{R}^{+},s}^A$ symbols is $\binom{K-1-|\mathcal{L}_s|}{r+1}$. Hence, the communication rate $R$ is
\begin{eqnarray}
R = \frac{T}{2K\binom{ K-1}{r}},
\end{eqnarray}
where
\begin{align*}
T&=   2K\binom{K-1}{r+1} - 2\sum_{s \in \mathcal{K}}\binom{K-1-|\mathcal{L}_s|}{r+1}\\
&= 2K\binom{K-1}{r+1}-2(K-p_{\vec{\bm{e}}(\bm{d})})\binom{K-1-N}{r+1}\\
&-2p_{\vec{\bm{e}}(\bm{d})}\binom{K-1-(N-1)}{r+1}\\
&= 2K\binom{K-1}{r+1} -2K\binom{ K-1}{r} S(\vec{\bm{e}}(\bm{d}),r)
\end{align*}
matching the rate expression in Theorem \ref{thm1 iq channel}.

\subsection{Decoding}\label{decoding theory}
User $k$ needs $W_{ d(k),\mathcal{R},s}^A$ for all $s\in  \mathcal{K} $, $\mathcal{R} \subseteq  \mathcal{K} \backslash \{s\}, \left|\mathcal{R}\right|=r$, and $A \in \{I, Q\}$. Among all these segments, $W_{ d(k),\mathcal{R},s}^A$, where $k\in \mathcal{R}$, can be directly obtained from user-$k$'s cache in an uncoded form. The remaining required segments can be categorized into two classes:
\begin{enumerate}
\item $(W_{d(k),\mathcal{R},s}^{I},W_{d(k),\mathcal{R},s}^{Q})$ pairs where $k\notin \mathcal{R}$ and $k\neq s$,
\item $(W_{d(k),\mathcal{R},k}^{I},W_{d(k),\mathcal{R},k}^{Q})$ pairs where $k\notin \mathcal{R}$ (i.e., $k=s$ in  $W_{d(k),\mathcal{R},s}$),
\end{enumerate}
which are mutually exclusive and will be decoded as follows.

\subsubsection{Decoding by individual symbol elimination}

We decode the first class of segments listed above using the same method as that in \cite{MAN-14}, but in the transformed domain.
Notice that
\begin{align}
&W_{ d(k),\mathcal{R},s}^{(T),A}\nonumber\\
  = & W_{ d(k),\mathcal{R},s}^{(T),A}
  \oplus\bigoplus_{j\in\mathcal{R}}W^{(T),A}_{ d(j), \mathcal{R}\cup \left\{k\right\} \backslash \{j\},s}
  \oplus\bigoplus_{i\in\mathcal{R}}W^{(T),A}_{ d(i), \mathcal{R}\cup\left\{ k\right\} \backslash \{i\},s}\nonumber\\
  = & \bigoplus_{j\in\mathcal{R}\cup k}W^{(T),A}_{ d(j), \mathcal{R}\cup\left\{ k\right\} \backslash \{j\},s}\oplus\bigoplus_{i\in\mathcal{R}}W^{(T),A}_{ d(i), \mathcal{R}\cup\left\{ k\right\} \backslash \{i\},s}\nonumber\\
  = & Y^{A}_{\mathcal{R}\cup\left\{ k\right\},s}\oplus\bigoplus_{i\in\mathcal{R}}W^{(T),A}_{ d(i), \mathcal{R}\cup\left\{ k\right\} \backslash \{i\},s},\quad A\in \{I,Q\}.\label{decode by cancellation}
\end{align}

Thus these transformed segments $W_{d(k),\mathcal{R},s}^{(T),A}$ can be decoded by using one delivered symbol $Y^{A}_{\mathcal{R}\cup\left\{ k\right\},s}$ and $r$ prefetched symbol $W^{(T),A}_{ d(i), \mathcal{R}\cup\left\{ k\right\} \backslash \{i\},s}$ (after applying the pairwise transformation). Since the pairwise transformation is invertible, user $k$ can indeed recover the first class of segments $(W_{ d(k),\mathcal{R},s}^{I},W_{ d(k),\mathcal{R},s}^{Q})$.

In our running example, consider recovering the segments $(W_{ 1,\{2\},3}^I,W_{ 1,\{2\},3}^Q)$ at user 1, which are not prefetched. By substituting $\mathcal{R}=\{2\}$, $s=3$ and $k=1$ into \eqref{decode by cancellation}, we have
\begin{align*}
W_{ 1,\{2\},3}^{(T),I}=Y^I_{\{1,2\},3}\oplus W_{ 2,\{1\},3}^{(T),I},
\end{align*}
and
\begin{align*}
W_{ 1,\{2\},3}^{(T),Q}=Y^Q_{\{1,2\},3}\oplus W_{ 2,\{1\},3}^{(T),Q}.
\end{align*}
These two equations hold trivially since
\begin{align*}
    Y^A_{\{1,2\},3}=W^{(T),A}_{1,\{2\},3}\oplus W^{(T),A}_{1,\{1\},3}
\end{align*}
for $A=\{I,Q\}$. Therefore, $(W_{ 1,\{2\},3}^{I},W_{ 1,\{2\},3}^{Q})$ can be decoded by inverting pairwise transformation.

\subsubsection{Decoding by interference alignment}

The second class of file segments to be recovered is those $(W_{d(k),\mathcal{R},k}^I,W_{d(k),\mathcal{R},k}^Q)$ at user $k$ where $\mathcal{R}\subseteq \mathcal{K}\backslash \{k\}$. The following lemma provides the key instrument for the decoding process, again in the transformed domain.
\begin{lemma}\label{decoding intermediate}
For user $k$, $W_{ d(k),\mathcal{R},k}^{(T),A}$ can be computed as
\begin{align}
W_{ d(k),\mathcal{R},k}^{(T),A}&=Z^{A}_{\mathcal{R},k}\oplus \bigoplus_{t\in\mathcal{R} }  Z^{(T),A}_{d(t),\mathcal{R}\backslash\{t\},k}\nonumber\\
&\oplus
\bigoplus_{\mathcal{R}^{+}: \mathcal{R}\subset\mathcal{R}^{+},k\notin\mathcal{R}^{+}} Y^{A}_{\mathcal{R}^{+},k}  \label{decoding result}
\end{align}
for $A\in \{I,Q\}$ and $\mathcal{R}\subseteq  \mathcal{K}\backslash \{k\}$, where $Z^{(T),A}_{d(t),\mathcal{R}\backslash\{t\},k}$ is defined as
\begin{align}
    \begin{bmatrix}Z^{(T),I}_{d(t),\mathcal{R}\backslash\{t\},k}\\Z^{(T),Q}_{d(t),\mathcal{R}\backslash\{t\},k}\end{bmatrix} \triangleq \mathbf{T}_{t,k}  \begin{bmatrix}Z^{I}_{d(t),\mathcal{R}\backslash\{t\},k}\\Z^{Q}_{d(t),\mathcal{R}\backslash\{t\},k}\end{bmatrix},
\end{align}
in which $\mathbf{T}_{t,k}$ is defined in \eqref{eq:1} and \eqref{eq:2}.
\end{lemma}

The proof of Lemma \ref{decoding intermediate} is given in Appendix \ref{decode}. By Lemma \ref{decoding intermediate}, any symbol in the second class can be written as an XOR of symbols on the right hand side of (\ref{decoding result}), each of which is either prefetched, can be computed, or delivered to user-$k$. Since the pairwise transformation is invertible, the second class of $(W_{d(k),\mathcal{R},k}^I,W_{d(k),\mathcal{R},k}^Q)$ can indeed be recovered from $(W_{ d(k),\mathcal{R},k}^{(T),I}, W_{ d(k),\mathcal{R},k}^{(T),Q})$. The right hand side of (\ref{decoding result}) can be viewed as aligning multiple interference signals $Z^{(T),A}_{d(t),\mathcal{R}\backslash\{t\},k}$ and $Y^{A}_{\mathcal{R}^{+},k}$ such that it can be removed from $Z^{A}_{\mathcal{R},k}$ to recover
$W_{ d(k),\mathcal{R},k}^{(T),A}$.

Consider in our running example the decoding process of the original segments $W_{1,\{2\},1}^{I}$ and $W_{1,\{2\},1}^{Q}$ at user 1. In this case $\mathcal{R}=\{2\}$ and $k=1$, and we decode the transformed segments $W_{1,\{2\},1}^{(T),A}$ for $A\in \{I,Q\}$. Since $t\in \mathcal{R}$, $t$ can only take value of $2$, hence $d(k)=d(t)$ and according to \eqref{eq:1} and \eqref{eq:2}, we have
\begin{align*}
& \begin{bmatrix}
\bigoplus_{t\in\mathcal{R} }Z^{(T),I}_{d(t),\mathcal{R}\backslash\{t\},k} \\
\bigoplus_{t\in\mathcal{R} }Z^{(T),Q}_{d(t),\mathcal{R}\backslash\{t\},k}
\end{bmatrix}
_{\mathcal{R}=\{2\},k=1}=
\begin{bmatrix}
Z^{(T),I}_{d(2),\emptyset,1} \\
Z^{(T),Q}_{d(2),\emptyset,1}
\end{bmatrix} \\
= & \mathbf{T}_{2,1}
\begin{bmatrix}
Z_{1,\emptyset,1}^I \\
Z_{1,\emptyset,1}^Q
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\
1 & 0 \\
\end{bmatrix}
\begin{bmatrix}
Z_{1,\emptyset,1}^I \\
Z_{1,\emptyset,1}^Q
\end{bmatrix}
=
\begin{bmatrix}
Z_{1,\emptyset,1}^I \oplus Z_{1,\emptyset,1}^Q \\
Z_{1,\emptyset,1}^I
\end{bmatrix}.
\end{align*}
Moreover, since $\mathcal{R}^{+}\supset \mathcal{R}$, it can be $\{2,3\},\{2,4\},\{2,5\}$, or $\{2,6\}$. Therefore, by substituting all variables,  \eqref{decoding result} becomes
\begin{align*}
W_{ 1,\{2\},1}^{(T),I}=  &Z^{I}_{\{2\},1}\oplus Z^{I}_{1,\emptyset,1} \oplus Z^{Q}_{1,\emptyset,1} \\
&\oplus Y^I_{\{2,3\},1} \oplus  Y^I_{\{2,4\},1} \oplus  Y^I_{\{2,5\},1}\oplus  Y^I_{\{2,6\},1}
\end{align*}
and
\begin{align*}
W_{ 1,\{2\},1}^{(T),Q}=  &Z^{Q}_{\{2\},1}\oplus Z^{I}_{1,\emptyset,1} \\
&\oplus Y^Q_{\{2,3\},1}\oplus  Y^Q_{\{2,4\},1} \oplus  Y^Q_{\{2,5\},1}\oplus  Y^Q_{\{2,6\},1},
\end{align*}
where $Z^{A}_{\{2\},1}$, $Z^{A}_{1,\emptyset,1}$ and $Y^A_{\mathcal{R}^+,1}$ can be found in Table \ref{table: product code} and Table \ref{table:IQ2}, from which the correctness of the two equations above can be verified. By inverting \eqref{eq:1} and \eqref{eq:2},  $(W_{ 1,\{2\},1}^{I},W_{ 1,\{2\},1}^{Q})$ can then be recovered.

\section{Conclusion}
In this paper, we consider coded caching systems with restricted demand types. We first showed that fully demanded systems may not be the worst case demand, contrary to popular beliefs. We then proposed a novel code construction for $(N,K)$ when $K \geq N$ and it is known a priori that all files are requested. The proposed code construction can achieve new operating corner points that are not covered by known constructions in the literature.

\begin{appendices}

      \section{Proof of Lemma \ref{lemma: linear dependence}}\label{Appendix remark}

Define $\mathcal{R}_*^- \triangleq \mathcal{S} ^{-}\cup \{l_k\}$, where $|\mathcal{S} ^{-}|=r-2$. To prove (\ref{eq: linear dependence 1}), we can write

\begin{align}
&Z^{A}_{f, \mathcal{R}_*^-,k}=\bigoplus_{h\in\mathcal{ K\backslash}\left(\mathcal{S}^{-}\cup\{l_k,k\}\right)}W^{A}_{f, \mathcal{S} ^{-}\cup \{l_k, h\},k}\nonumber\\
&\quad\overset{(a)}{=}\bigoplus_{h\in\mathcal{ K\backslash}\left(\mathcal{S}^{-}\cup\{l_k,k\}\right)}W^{A}_{f, \mathcal{S} ^{-}\cup \{l_k, h\},k}\nonumber\\
&\quad\qquad\oplus \bigoplus_{h_1,h_2\in \mathcal{K} \backslash\left(\mathcal{S}^{-}\cup\{l_k,k\}\right), h_1\neq h_2}W^{A}_{f, \mathcal{S} ^{-}\cup \{h_1,h_2\},k} \notag\\
&\quad=\bigoplus_{h\in\mathcal{ K\backslash}\left(\mathcal{S}^{-}\cup\{l_k,k\}\right)}W^{A}_{f, \mathcal{S} ^{-}\cup \{l_k,h\},k}\nonumber\\
&\quad\oplus \bigoplus_{h_1\in\mathcal{ K\backslash}\left(\mathcal{S}^{-}\cup\{l_k,k\}\right)}\bigoplus_{h\in\mathcal{ K\backslash}\left(\mathcal{S}^{-}\cup\{l_k,k,h_1\}\right)}W^{A}_{f, \mathcal{S} ^{-}\cup \{h_1,h_2\},k} \nonumber\\

&\quad=\bigoplus_{h_1\in\mathcal{ K\backslash}\left(\mathcal{S}^{-}\cup\{l_k,k\}\right)}\bigoplus_{h_2\in \mathcal{K} \backslash( \mathcal{S}^{-}\cup\{h_1,k\})} W^{A}_{f, \mathcal{S} ^{-}\cup \{h_1,h_2\},k} \nonumber\\
&\quad= \bigoplus_{h_1\in\mathcal{ K\backslash}\left(\mathcal{S}^{-}\cup\{l_k,k\}\right)} Z^{A}_{f, \mathcal{S} ^{-}\cup \{h_1\},k},
\end{align}
where $(a)$ is because
\begin{align}
\bigoplus_{h_1,h_2\in \mathcal{K} \backslash\left(\mathcal{S}^{-}\cup\{l_k,k\}\right), h_1\neq h_2}W^{A}_{f, \mathcal{S} ^{-}\cup \{h_1,h_2\},k}=0
\end{align}
as each $W^{A}_{f, \mathcal{S} ^{-}\cup \{h_1\}\cup\{ h_2\},k}$ appears twice due to the symmetry between $h_1$ and $h_2$.

To prove (\ref{eq: linear dependence 2}), we can write
\begin{align*}
 Z^{A}_{1,\mathcal{R}^{-},k}=&\bigoplus_{h\in\mathcal{ K\backslash}(\mathcal{R}^{-}\cup\{k\})} W^{A}_{1,\{h\}\cup\mathcal{R}^{-},k}\nonumber\\
=& \bigoplus_{f\in \mathcal{F}} \bigoplus_{h\in\mathcal{ K\backslash}(\mathcal{R}^{-}\cup\{k\})} W^{A}_{f,\{h\}\cup\mathcal{R}^{-},k}\nonumber\\
&\qquad\oplus \bigoplus_{f\in \mathcal{F}\backslash\{1\}} \bigoplus_{h\in\mathcal{ K\backslash}(\mathcal{R}^{-}\cup\{k\})} W^{A}_{f,\{h\}\cup\mathcal{R}^{-},k}\nonumber\\
=&  \bigoplus_{h\in\mathcal{ K\backslash}(\mathcal{R}^{-}\cup\{k\})}
\bigoplus_{f\in \mathcal{F}}W^{A}_{f,h\cup\mathcal{R}^{-},k}\nonumber\\
&\qquad\oplus \bigoplus_{f\in \mathcal{F}\backslash\{1\}} \bigoplus_{h\in\mathcal{ K\backslash}(\mathcal{R}^{-}\cup\{k\})} W^{A}_{f,h\cup\mathcal{R}^{-},k}\nonumber\\
=& \bigoplus_{h\in\mathcal{ K\backslash}(\mathcal{R}^{-}\cup\{k\})}
Z^{A}_{h\cup\mathcal{R}^{-},k}\oplus \bigoplus_{f\in \mathcal{F}\backslash\{1\}} Z^{A}_{f,\mathcal{R}^{-},k}\nonumber\\
=& \bigoplus_{\mathcal{R}:  \mathcal{R}^{-}\subset \mathcal{R}, k\notin \mathcal{R}}
Z^{A}_{\mathcal{R},k}\oplus \bigoplus_{f\in \mathcal{F}\backslash\{1\}} Z^{A}_{f,\mathcal{R}^{-},k}.
\end{align*}
The proof is complete.
\IEEEQEDhere

\section{Proof of Lemma \ref{decoding intermediate}}\label{decode}

We need the following instrumental lemma in the proof.
\begin{lemma}\label{z2}
For any $\bm{d}$, $s\in \mathcal{K}$, $\mathcal{R}\subseteq \mathcal{K}\backslash \{s\}$ where $|\mathcal{R}|=r$, and $A\in \{I,Q\}$,
\begin{align}
 \bigoplus_{t\in \mathcal{K}} W^{(T),A}_{d(t),\mathcal{R},s}=   \bigoplus_{f\in \mathcal{F} } W^{A}_{f,\mathcal{R} ,s} =Z^{A}_{\mathcal{R},s}.  \label{eq: lemma for decoding}
\end{align}

\end{lemma}
The proof of Lemma \ref{z2} can be found in Appendix \ref{appendix: transformed segments}.

\begin{IEEEproof}[Proof of Lemma \ref{decoding intermediate}]

We first write the following chain of equalities
\begin{align}
&W^{(T),A}_{ d(k),\mathcal{R},k}= \bigoplus_{s\in \mathcal{K} }W^{(T),A}_{d(s),\mathcal{R} ,k} \oplus  \bigoplus_{s\in \mathcal{K}\backslash\{k\} }W^{(T),A}_{d(s),\mathcal{R} ,k} \nonumber\\
&\quad\overset{(a)}{=} Z^{A}_{\mathcal{R},k} \oplus  \bigoplus_{v \in \mathcal{K}\backslash\{k\} }W^{(T),A}_{ d(v),\mathcal{R} ,k} \nonumber\\
&\quad\overset{(b)}{=} Z^{A}_{\mathcal{R},k} \oplus  \bigoplus_{v \in \mathcal{R} } W^{(T),A}_{ d(v),\mathcal{R} ,k}  \oplus  \bigoplus_{v \in \mathcal{K} \setminus (\mathcal{R}\cup \{k\})}W^{(T),A}_{ d(v),\mathcal{R} ,k} \nonumber\\
 &\qquad\quad\oplus  \bigoplus_{v \in \mathcal{K} \setminus (\mathcal{R}\cup \{k\})} \bigoplus_{t\in\mathcal{R} \cup \left\{ v \right\}} W^{(T),A}_{ d(t), \mathcal{R} \cup \left\{ v \right\} \backslash \{t\} ,k}\nonumber\\
 &\qquad\quad\oplus  \bigoplus_{v \in \mathcal{K} \setminus (\mathcal{R}\cup \{k\})} \bigoplus_{t\in\mathcal{R} \cup \left\{ v \right\}} W^{(T),A}_{ d(t), \mathcal{R} \cup \left\{ v \right\} \backslash \{t\} ,k}\nonumber\\
&\quad= Z^{A}_{\mathcal{R},k} \oplus  \bigoplus_{v \in \mathcal{R} } W^{(T),A}_{ d(v),\mathcal{R} ,k} \nonumber\\
 &\,\oplus  \bigoplus_{v \in \mathcal{K} \setminus (\mathcal{R}\cup \{k\})} \left(\bigoplus_{t\in\mathcal{R} \cup \left\{ v \right\}} W^{(T),A}_{ d(t), \mathcal{R} \cup \left\{ v \right\} \backslash \{t\} ,k}\oplus W^{(T),A}_{ d(v),\mathcal{R} ,k}\right)\nonumber\\
 &\qquad\quad\oplus  \bigoplus_{v \in \mathcal{K} \setminus (\mathcal{R}\cup \{k\})} \bigoplus_{t\in\mathcal{R} \cup \left\{ v \right\}} W^{(T),A}_{ d(t), \mathcal{R} \cup \left\{ v \right\} \backslash \{t\} ,k}\nonumber\\
&\quad = Z^{A}_{\mathcal{R},k} \oplus  \bigoplus_{v \in \mathcal{R} } W^{(T),A}_{ d(v),\mathcal{R} ,k} \nonumber\\
 &\qquad\quad\oplus  \bigoplus_{v \in \mathcal{K} \setminus (\mathcal{R}\cup \{k\})} \bigoplus_{t\in\mathcal{R} } W^{(T),A}_{ d(t), \mathcal{R} \cup \left\{ v \right\} \backslash \{t\} ,k}\nonumber\\
 &\qquad\quad\oplus  \bigoplus_{v \in \mathcal{K} \setminus (\mathcal{R}\cup \{k\})} \bigoplus_{t\in\mathcal{R} \cup \left\{ v \right\}} W^{(T),A}_{ d(t), \mathcal{R} \cup \left\{ v \right\} \backslash \{t\} ,k}\nonumber\\
&\quad\overset{(c)}{=} Z^{A}_{\mathcal{R},k} \oplus  \bigoplus_{t \in \mathcal{R} } W^{(T),A}_{ d(t),\mathcal{R} ,k} \nonumber\\
 &\qquad\quad\oplus   \bigoplus_{t\in\mathcal{R} } \bigoplus_{v \in \mathcal{K} \setminus (\mathcal{R}\cup \{k\})} W^{(T),A}_{ d(t), \mathcal{R} \cup \left\{ v \right\} \backslash \{t\} ,k}\nonumber\\
 &\qquad\quad\oplus  \bigoplus_{v \in \mathcal{K} \setminus (\mathcal{R}\cup \{k\})} \bigoplus_{t\in\mathcal{R} \cup \left\{ v \right\}} W^{(T),A}_{ d(t), \mathcal{R} \cup \left\{ v \right\} \backslash \{t\} ,k}\notag\\
 &\quad\overset{(d)}{=}Z^{A}_{\mathcal{R},k} \oplus  \bigoplus_{t\in\mathcal{R} }\bigoplus_{v\in\mathcal{K} \backslash (\mathcal{R}\backslash\{t\}\cup\{k\})} W^{(T),A}_{d(t),v\cup\mathcal{R}\backslash\{t\},k}\nonumber\\
 &\qquad\quad\oplus  \bigoplus_{v \in \mathcal{K} \setminus (\mathcal{R}\cup \{k\})} \bigoplus_{t\in\mathcal{R} \cup \left\{ v \right\}} W^{(T),A}_{ d(t), \mathcal{R} \cup \left\{ v \right\} \backslash \{t\} ,k}\notag\\
&\quad\overset{(e)}{=} Z^{A}_{\mathcal{R},k} \oplus  \bigoplus_{t\in\mathcal{R} }\bigoplus_{v\in\mathcal{K} \backslash (\mathcal{R}\backslash\{t\}\cup\{k\})} W^{(T),A}_{d(t),v\cup\mathcal{R}\backslash\{t\},k}\notag\\
&\qquad\quad\oplus \bigoplus_{\mathcal{R}^{+}: \mathcal{R}\subset \mathcal{R}^{+},k\notin \mathcal{R}^{+}} Y^{(T),A}_{\mathcal{R}^{+},k},\label{eqn:partlemma3}
\end{align}
where the steps can be justified as follows
\begin{enumerate}[label=(\alph*)]
\item Holds due to Lemma \ref{z2};
\item By splitting $\mathcal{K}\backslash\{ k\}$ into two mutually exclusive sets $\mathcal{R}$ and $\mathcal{K}\backslash (\mathcal{R}\cup \{k\})$, and then adding the same terms twice;

\item By exchanging the order of summations;
\item Due to the fact that for $t\in \mathcal{R}$
\begin{align*}

&\bigoplus_{v\in\mathcal{K} \backslash(\mathcal{R}\cup \left\{ k \right\})} W^{(T),A}_{ d(t), \mathcal{R} \cup \left\{ v \right\} \backslash \{t\} ,k}\oplus W^{(T),A}_{ d(t),\mathcal{R} ,k}\nonumber\\
&\quad=   \bigoplus_{v\in\mathcal{K} \backslash(\mathcal{R}\cup \left\{ k \right\})\cup \{t\}} W^{(T),A}_{ d(t), \mathcal{R} \cup \left\{ v \right\} \backslash \{t\} ,k}\nonumber\\
&\quad=  \bigoplus_{v\in\mathcal{K} \backslash (\mathcal{R}\backslash\{t\}\cup\{k\})}W^{(T),A}_{d(t),v\cup\mathcal{R}\backslash\{t\},k};

\end{align*}
\item By letting $\mathcal{R}^{+}=\mathcal{R} \cup \left\{ v \right\}$, from which it follows that
\begin{align*}
 & \bigoplus_{v \in \mathcal{K} \setminus (\mathcal{R}\cup \{k\})} \bigoplus_{t\in\mathcal{R} \cup \left\{ v \right\}} W^{(T),A}_{ d(t), \mathcal{R} \cup \left\{ v \right\} \backslash \{t\} ,k}\\
&\qquad=\bigoplus_{\mathcal{R}^{+}: \mathcal{R}\subset \mathcal{R}^{+},k\notin \mathcal{R}^{+}} \bigoplus_{t\in\mathcal{R}^{+}}W^{(T),A}_{ d(t),\mathcal{R}^{+}\backslash \{t\},k}\\
&\qquad=\bigoplus_{\mathcal{R}^{+}: \mathcal{R}\subset \mathcal{R}^{+},k\notin \mathcal{R}^{+}}Y^{(T),A}_{\mathcal{R}^{+},k}.
\end{align*}
\end{enumerate}

Comparing (\ref{decoding result}) and (\ref{eqn:partlemma3}), it is clear that it only remains to show that
\begin{align}\label{eq:ZTA}
Z^{(T),A}_{d(t),\mathcal{R}\backslash\{t\},k}=\bigoplus_{v\in\mathcal{K} \backslash (\mathcal{R}\backslash\{t\}\cup\{k\})}W^{(T),A}_{d(t),v\cup\mathcal{R}\backslash\{t\},k}.

\end{align}

To see this, note that by the definition of $ Z^{A}_{f,\mathcal{R}^{-},k}$
\begin{align}
    &\begin{bmatrix}Z^{(T),I}_{d(t),\mathcal{R}\backslash\{t\},k}\\Z^{(T),Q}_{d(t),\mathcal{R}\backslash\{t\},k}\end{bmatrix} =\mathbf{T}_{t,k}  \begin{bmatrix}Z^{I}_{d(t),\mathcal{R}\backslash\{t\},k}\\Z^{Q}_{d(t),\mathcal{R}\backslash\{t\},k}\end{bmatrix}\notag\\
    &\quad= \mathbf{T}_{t,k}\begin{bmatrix}
    \bigoplus_{u\in\mathcal{ K\backslash}(\mathcal{R}\setminus\{t\}\cup \{k\})} W^{I}_{d(t),\{u\}\cup(\mathcal{R}\setminus\{t\}),k}\\
    \bigoplus_{u\in\mathcal{ K\backslash}(\mathcal{R}\setminus\{t\}\cup \{k\})} W^{Q}_{d(t),\{u\}\cup(\mathcal{R}\setminus\{t\}),k}
    \end{bmatrix}\notag\\
    &\quad = \bigoplus_{u\in\mathcal{ K\backslash}(\mathcal{R}\setminus\{t\}\cup \{k\})} \left(\mathbf{T}_{t,k}\begin{bmatrix}W^{I}_{d(t),\{u\}\cup(\mathcal{R}\setminus\{t\}),k}\\
     W^{Q}_{d(t),\{u\}\cup(\mathcal{R}\setminus\{t\}),k}
    \end{bmatrix}\right)\notag\\
    &\quad = \bigoplus_{u\in\mathcal{ K\backslash}(\mathcal{R}\setminus\{t\}\cup \{k\})}\begin{bmatrix}W^{(T),I}_{d(t),\{u\}\cup(\mathcal{R}\setminus\{t\}),k}\\
    W^{(T),Q}_{d(t),\{u\}\cup(\mathcal{R}\setminus\{t\}),k}
    \end{bmatrix},
\end{align}
which completes the proof.\end{IEEEproof}

\section{Proof of Lemma \ref{z2}} \label{appendix: transformed segments}
We claim that for any $f\in \mathcal{F}$, when $K_f\neq \emptyset$,
\begin{align}
\bigoplus_{t\in \mathcal{K}_f} W^{(T),A}_{d(t),\mathcal{R},s}  =   W^{A}_{f,\mathcal{R},s}, \label{fact}
\end{align}
from which the lemma follows trivially.

When $K_f$ is odd, \eqref{fact} holds true trivially. We only need to consider the case when $K_f$ is even.
\begin{itemize}
\item $f=d(s)$ and $A=I$:
\begin{align}
&\bigoplus_{t\in \mathcal{K}_{f}} W^{(T),I}_{d(t),\mathcal{R},s}=\bigoplus_{t\in \mathcal{K}_{f}} W^{(T),I}_{f,\mathcal{R},s} \notag\\
&\,\,=\bigoplus_{t\in \mathcal{K}_{f}\backslash \{s\}}\left( W^{I}_{f,\mathcal{R},s}\oplus W^{Q}_{f,\mathcal{R},s}\right)\oplus  W^{Q}_{f,\mathcal{R},s}\notag\\
&\,\,\overset{(a)}{=} W^{I}_{f,\mathcal{R},s}\oplus W^{Q}_{f,\mathcal{R},s}\oplus W^{Q}_{f,\mathcal{R},s}=W^{I}_{f,\mathcal{R},s},
\end{align}
where (a) is true because $K_f$ is even.

\item $f=d(s)$ and $A=Q$:
\begin{align}
&\bigoplus_{t\in \mathcal{K}_{f}} W^{(T),Q}_{d(t),\mathcal{R},s} =\bigoplus_{t\in \mathcal{K}_{f}} W^{(T),Q}_{f,\mathcal{R},s} \notag\\
&\quad= \bigoplus_{t\in \mathcal{K}_{f}\backslash \{s\}} W^{I}_{f,\mathcal{R},s}\oplus  W^{I}_{f,\mathcal{R},s}\oplus  W^{Q}_{f,\mathcal{R},s}\notag\\
&\quad= W^{I}_{f,\mathcal{R},s}\oplus  W^{I}_{f,\mathcal{R},s}\oplus  W^{Q}_{f,\mathcal{R},s}= W^{Q}_{f,\mathcal{R},s},
\end{align}
for the same reason as in the previous case.

\item $f\neq d(s)$ and $A=I$:
\begin{align}
&\bigoplus_{t\in \mathcal{K}_{f}} W^{(T),I}_{d(t),\mathcal{R},s}=\bigoplus_{t\in \mathcal{K}_{f}} W^{(T),I}_{f,\mathcal{R},s} \notag\\
&\,\,=\bigoplus_{t\in \mathcal{K}_{f}\backslash \{u_f\}}\left( W^{I}_{f,\mathcal{R},s}\oplus W^{Q}_{f,\mathcal{R},s}\right)\oplus  W^{Q}_{f,\mathcal{R},s}\notag\\
&\,\,= W^{I}_{f,\mathcal{R},s}\oplus W^{Q}_{f,\mathcal{R},s}\oplus W^{Q}_{f,\mathcal{R},s}=W^{I}_{f,\mathcal{R},s},
\end{align}
\item $f\neq d(s)$ and $A=Q$:
\begin{align}
&\bigoplus_{t\in \mathcal{K}_{f}} W^{(T),Q}_{d(t),\mathcal{R},s} =\bigoplus_{t\in \mathcal{K}_{f}} W^{(T),Q}_{f,\mathcal{R},s} \notag\\
&\quad= \bigoplus_{t\in \mathcal{K}_{f}\backslash \{u_f\}} W^{I}_{f,\mathcal{R},s}\oplus  W^{I}_{f,\mathcal{R},s}\oplus  W^{Q}_{f,\mathcal{R},s}\notag\\
&\quad= W^{I}_{f,\mathcal{R},s}\oplus  W^{I}_{f,\mathcal{R},s}\oplus  W^{Q}_{f,\mathcal{R},s}= W^{Q}_{f,\mathcal{R},s}.
\end{align}
\end{itemize}
Lemma \ref{z2} is thus proved. \IEEEQEDhere

\end{appendices}

\bibliographystyle{ieeetr}

config: arxiv


TITLE: Absolute Value equations in 2 variables ($|x-y|+|x+y|=\sqrt5$)
QUESTION [1 upvotes]: I'm struggling a lot figuring out how to sketch the following
$$|x-y|+|x+y|=\sqrt5$$
This is what I know
for$|x-y|$

$x-y \geq 0$ then $y \leq x$ so $|x-y|= x-y$
$x-y < 0$ then $y >x$ so $|x-y|= -(x-y)$

for$|x+y|$

$x+y \geq 0$ then $y \geq -x$ so $|x+y|= x+y$
$x+y < 0$ then $y <-x$ so $|x+y|= -(x+y)$

but even after knowing this, I still don't know how to sketch it.
The result should look something like this:

If you could help me it would be very much appreciated.

REPLY [0 votes]: You can totally avoid the sign discussion by using this definition of the absolute value: $$|u|=\max(u,-u)$$
Along with this property of the maximum:
$$\max(a,b)+\max(c,d)=\max(a+c,a+d,b+c,b+d)$$

$|x-y|=\max(x-y,y-x)$
$|x+y|=\max(x+y,-x-y)$
$|x-y|+|x+y|=\max(2x,-2y,2y,-2x)=2\max(|x|,|y|)=\sqrt{5}$

We get that $$\max(|x|,|y|)=\frac {\sqrt{5}}2$$ and it is then straightforward to figure out the square shape.


TITLE: Properties of Positive Real Functions
QUESTION [0 upvotes]: I am trying to understand the properties of positive real (PR) and strictly positive real (SPR) transfer functions. If given a transfer function I know how to determine whether or not the function is PR/SPR, however I'm not sure how to approach the following example.
Say we are given two positive real transfer functions:
$G_{1}(s)$ and $G_{2}(s)$
How can I tell if the sum $$ G_{1}(s) + G_{2}(s)$$
or the product $$ G_{1}(s) * G_{2}(s)$$
is PR/SPR?
Intuitively, I think the sum is SPR, but as for the product I am uncertain. Either way, is there a framework I can use to approach this or does anyone know of a proof I could look at?

REPLY [1 votes]: At any given $s$ the two transfer functions give you two complex numbers $\rho_1+i\,\sigma_1$ and $\rho_2+i\,\sigma_2$, with the constraints that $\rho_1,\rho_2\geq0$.
For the summation you only have that it is strictly positive real iff $\rho_1$ and $\rho_2$ are not both simultaneously zero. For example $G_1(s)=\alpha\,G_2(s)$ with $\alpha>0$ would not satisfy this, or the transfer functions already need to be strictly positive real.
For the multiplication the real part would become $\rho_1\,\rho_2 - \sigma_1\,\sigma_2$. Therefore, the fact that $G_1(s)$ and $G_2(s)$ are positive real does not give you enough information about their imaginary parts to tell if the result is even positive real.