TITLE: Maximal Albanese variety
QUESTION [9 upvotes]: I am looking for a proof for the following statement

A smooth projective variety $X$ has maximal Albanese dimension if and
  only if the cotangent bundle of $X$ is generically generated by its
   global sections, that is,$$ H^0(X,\Omega_X^1)\otimes\mathcal O_X\to
 \mathcal \Omega_X^1$$ is surjective at the generic point of $X$.

REPLY [9 votes]: In characteristic $0$ that follows from Sard's theorem / generic smoothness.  In characteristic $p$, I believe that this is false (I still need to check how double point singularities, $\text{Zero}(x_1^2 + \dots + x_{n-1}^2+x_n^2 + x_{n+1}^p)$, affect the cotangent sheaf).
Characteristic  0.In characteristic $0$, the map of sheaves above is the pullback map, $$d(\text{alb}_X)^\dagger: \text{alb}_X^*\Omega_{\text{Alb}_X/k} \to \Omega_{X/k}.$$  Since the Albanese morphism from $X$ to its image, $\text{alb}_X(X)$, is generically smooth, the dimension of the image equals the rank of $d\text{alb}_X^\dagger$ at a generic point of $X$.
Positive characteristic. However, this seems to be false in positive characteristic. Here is an e-mail that I wrote a few years ago about positive characteristic counterexamples to a similar question.  I added some TeX formatting to the e-mail.
"Dear Chris,
I saw Davesh today, and we talked more about the issue we were discussing on Friday regarding purely inseparable covers of Abelian varieties.  I now believe that there are serious problems whenever the dimension is $> 1.$ Let $k$ be an algebraically closed field of characteristic $p > 0$.  Let $A$ be an Abelian variety of dimension $g > 1$.  For a "generic" element $f$ in $k(A)$, the corresponding rational transformation $f : A \dashrightarrow \mathbb{P}^1$ "regularizes" on a blowing up, $u : A' \to A$, such that $A'$ is smooth over $k$.  Now consider the following Cartesian diagram, $$ \begin{array}{rrl} X & \xrightarrow{i} & A' \\ g~\downarrow & & \downarrow~f \\ \mathbb{P}^1 &\xrightarrow{F}& \mathbb{P}^1\end{array}$$ where the bottom horizontal $k$-morphism $\mathbb{P}^1 \to \mathbb{P}^1$ is the arises from the Frobenius morphism .  The purely inseparable morphism to consider is $i$.
The issue is this: for $f$ generic, the "critical" points of $f$ are just finitely many ordinary double points (I am assuming that $p$ is different from $2$).  If $\text{dim}(A) = 1$, then the points of $X$ above such critical points are non-normal.  When you normalize, then $X$ is smooth, and your previous argument is valid, i.e., $X$ is an elliptic curve.  However, if $\text{dim}(A) > 1$, then the points of $X$ above these finitely many critical points are, in fact, already normal.  Thus, $X$ is normal yet singular.  So $X$ cannot be an Abelian variety.
Best regards,
Jason"
By construction, the morphism $i$ is finite.  Thus, $X$ has maximal Albanese dimension.  By construction $H^0(A',\Omega_{A'/k})$ generically generates $\Omega_f$, and thus the $i$-pullback also generically generates $\Omega_g$.  If the dimension of the Albanese of $X$ were strictly greater than $\text{dim}(A)$, then there would be more etale $\ell$-sheeted covers of $X$ than there are of $A$, for $\ell$ prime to the characteristic.  Yet, since $i$ is purely inseparable, the pullback map on etale fundamental groups is an isomorphism.  If the Albanese morphism of $X$ were different from $i$, it would be a generically finite morphism that factors $i$.  Since $i$ has prime degree $p$, that is impossible.  Thus, $i$ is the Albanese morphism.
Since $i$ is purely inseparable, the rank of $d(\text{alb}_X)^\dagger$ at a general point is at most $\text{dim}(A)-1$.  Finally, since $\Omega_i$ is the pullback of $\Omega_F$, i.e., the pullback of $\mathcal{O}_{\mathbb{P}^1}(-2)$, there are no nonzero global sections of $\Omega_i$.  Thus, from the usual exact sequence, $$0 \to \text{Image}(d(\text{alb}_X)^\dagger) \to \Omega_{X/k} \to \Omega_i \to 0,$$ it follows that the rank of the following sheaf homomorphism at a general point of $X$ equals $\text{dim}(A)-1$, $$H^0(X,\Omega_{X/k})\otimes_k \mathcal{O}_X \to \Omega_{X/k}.$$


TITLE: Covering space is path-connected if the action of $\pi_1$ on a (single) fiber is transitive
QUESTION [6 upvotes]: Let $p\colon X\to Y$ be a covering map. Suppose that $Y$ is path-connected, locally path-connected and semi-locally simply connected. Let $x,x'\in X$ be two points of $X$.

$\textbf{Question:}$Is it true that $\pi_1(Y,p(x))$ acts transitively on $p^{-1}(p(x))$ if and only if $\pi_1(Y,p(x'))$ acts transitively on $p^{-1}(p(x'))$?
  Equivalently, is $X$ path-connected if there exists some $x\in X$ such that $\pi_1(Y,p(x))$ acts transitively on $p^{-1}(p(x))$?

Here is my try: Suppose $\pi_1(Y,p(x))$ acts transitively on $p^{-1}(p(x))$. Let $z'\in p^{-1}(p(x'))$. Since $Y$ is path-connected, we may choose a path $\gamma$ from $p(x')$ to $p(x)$. The monodromy functor then induces a map of sets $\phi\colon p^{-1}(p(x'))\to p^{-1}(p(x))$. Let $z=\phi(z')$. Then there exists a loop $\delta\in \pi_1(Y,p(x))$ and a point $\tilde{x}\in p^{-1}(p(x))$ such that the end point of a lift $\tilde{\delta}$ of $\delta$ beginning at $\tilde{x}$ is equal to $z$.
Now what I would like to do is to consider something like the conjugation of $\delta$ with respect to $\gamma$ and lifting $\gamma$ to $\tilde{\gamma}$ and then considering the composition $(\tilde{\gamma})^{-1} \tilde{\delta}\tilde{\gamma}$. However, this does not make sense in general sine we do not know $\tilde{\delta}(0)=\tilde{\gamma}(1)$. Moreover, this idea does not seem to use much of the relation between $z$ and $z'$, $\phi(z')=z$.
$\textbf{Edit:}$ The map $\phi$ can be described more explicitly. I will write that out and see how that helps.
In the notation from above $\phi(z')=z$ means that there exists a lift $\tilde{\gamma}$ of $\gamma$ starting at $z'$ and ending at $z$. We can do a similar thing with $\tilde{x}$, say $\psi(\tilde{x})=\tilde{z}$ and let $\epsilon$ be the used lifting, where $\psi\colon p^{-1}(p(x)) \to p^{-1}(p(x'))$ is induced by $\gamma^{-1}$ using the monodromy functor. Then $(\tilde{\gamma})^{-1}\tilde{\delta}\epsilon^{-1}=:\tilde{\omega}$ is path from $\tilde{z}$ to $z'$. Letting $\omega=p\tilde{\omega}$ we see that this is a loop at $p(x')$ since $\tilde{z},z' \in p^{-1}(p(x'))$. This proves $[\omega].\tilde{z}=z'$, i.e. $\pi_1(Y,p(x'))$ acts transitively on $p^{-1}(p(x')) $.
$\textbf{Edit:}$ Actually, this doesn't prove the transitivity. In fact, I had the wrong definition of transitivity in mind when writing the above. However, making a similar approach with the correct definition gives the result. I added an answer in the answer section.

REPLY [0 votes]: Since my edit in the question does not actually prove that the action is transitive, here is a (hopefully complete) proof. The idea, though, stays the same.
Suppose that $\pi_1(Y,p(x))$ acts transitively on $p^{-1}(p(x))$. We need to prove that the same is true for $x$ replaced with $x'$, i.e. for each pair $x_1,x_2 \in p^{-1}(p(x'))$ we need to find a loop $\omega$ at $p(x')$ and a lift $\tilde{\omega}$ starting at $x_1$ and ending at $x_2$.
Fix some path $\gamma\colon p(x')\to p(x)$. The monodromy functor induces a map $\phi\colon p^{-1}(p(x'))\to p^{-1}(p(x))$. Let $z_i=\phi(x_i)$ and let $\tilde{\gamma_i}$ denote the used lifting of $\gamma$, i.e. $\tilde{\gamma_i}(0)=x_i$ and $\tilde{\gamma_i}(1)=z_i$. By assumption, there exists a loop $\delta$ at $p(x)$ and a lifting $\tilde{\delta}\colon z_1\to z_2$. Defining $\tilde{\omega}:=(\tilde{\gamma_2})^{-1}\tilde{\delta}\tilde{\gamma_1}$ (this is a path from $x_1$ to $x_2$) and setting $\omega=p\tilde{\omega}$, the desired result follows.


text:
\begin{document}

\title{The Capacity of Private Information Retrieval with \\ Private Side Information Under Storage Constraints\thanks{This work was supported by NSF Grants CNS 13-14733, CCF 14-22111, CNS 15-26608 and CCF 17-13977.}}

\author{Yi-Peng Wei  \qquad Sennur Ulukus\\
	\normalsize Department of Electrical and Computer Engineering\\
	\normalsize University of Maryland, College Park, MD 20742 \\
	\normalsize {\it ypwei@umd.edu  \qquad \it ulukus@umd.edu} }

\maketitle

\begin{abstract}
We consider the problem of private information retrieval (PIR) of a single message out of $K$ messages from $N$ replicated and non-colluding databases where a cache-enabled user (retriever) of cache-size $S$ possesses side information in the form of uncoded portions of the messages that are unknown to the databases. The identities of these side information messages need to be kept private from the databases, i.e., we consider PIR with private side information (PSI). We characterize the optimal normalized download cost for this PIR-PSI problem under the storage constraint $S$ as $D^*=1+\frac{1}{N}+\frac{1}{N^2}+\dots+\frac{1}{N^{K-1-M}}+
\frac{1-r_M}{N^{K-M}}+\frac{1-r_{M-1}}{N^{K-M+1}}+\dots+\frac{1-r_1}{N^{K-1}}$, where $r_i$ is the portion of the $i$th side information message that is cached with $\sum_{i=1}^M r_i=S$. Based on this capacity result, we prove two facts: First, for a fixed memory size $S$ and a fixed number of accessible messages $M$, uniform caching achieves the lowest normalized download cost, i.e., $r_i=\frac{S}{M}$, for $i=1,\dots, M$, is optimum. Second, for a fixed memory size $S$, among all possible $K-\left \lceil{S} \right \rceil+1$ uniform caching schemes, the uniform caching scheme which caches $M=K$ messages achieves the lowest normalized download cost.
\end{abstract}

\section{Introduction}

We consider the private information retrieval (PIR) problem with private side information (PSI) for a cache-enabled user (retriever) under a cache storage size constraint. PIR refers to the problem where a user wishes to download a desired message from distributed replicated databases while keeping the identity of the desired message private against the databases. PSI refers to the setting where the user (retriever) possesses cached messages in its local storage, which it wants to utilize to decrease the download cost during PIR, but at the same time, keep their identities private against the databases. The goal of the PIR-PSI problem is to devise the most efficient retrieval scheme under the joint desired message and side information privacy constraints. The efficiency of a PIR-PSI scheme is measured by the normalized download cost which is the ratio of the number of total downloaded bits to the number of desired bits. In this work, we consider the PIR-PSI problem under a storage size constraint at the user, and investigate how best the fixed-size user cache can be utilized.

We introduce the PIR-PSI problem under a storage constraint using the example shown in Fig.~\ref{ex_intro}. Consider a user wanting to download a message from $N=3$ non-communicating databases, each storing the same set of $K=5$ messages. Assume that the user is already in possession of $M=3$ messages through some unspecified means; the user may have obtained these from another user, or it may have prefetched them from another database. The databases do not know the identities of these messages, but they know that the user has access to $M=3$ messages. (For this example, say these messages are $W_2$, $W_4$ and $W_5$.) However, the user has limited local storage with size $S=1$ message. What should the user keep in order to minimize the download cost of the desired message during the PIR phase while keeping the identities of both desired and cached messages private? Should the user keep $1$ full message in its cache and discard the other 2 messages, shown as caching option $1$ in Fig.~\ref{ex_intro}? Should the user choose $2$ messages, store half of each chosen message and discard the remaining 1 message, shown as caching option $2$ in Fig.~\ref{ex_intro}? Or, should the user keep all 3 messages and store a portion of each? In that case, what portions of messages should the user store? E.g., should it store $25\%$ of $W_2$, $25\%$ of $W_4$ and $50\%$ of $W_5$, shown as caching option $3$, or should it store $\frac{1}{3}$ of all 3 messages, shown as caching option $4$ in Fig.~\ref{ex_intro}?

Different caching schemes result in different download costs for the PIR-PSI problem. Intuition may say that if portions of many messages are kept in the cache, then the user will need to protect many identities from the databases due to the PSI requirement, which may seem disadvantageous. On the other hand, intuition may also say that keeping portions of many messages may improve the diversity of side information for the PIR phase, which may seem advantageous. What is the optimum way to utilize the user's limited cache memory? In this work, we characterize the optimal normalized download cost for any given caching strategy, and determine the optimal caching strategy under a given storage constraint.

\begin{figure}[t]
	\centering
	\epsfig{file=./intro.eps,width=0.75\textwidth}
	\caption{PIR-PSI under a storage constraint. Here $N=3$, $K=5$, $S=1$, and $M=3$.}
	\label{ex_intro}
\end{figure}

\textit{Related Work:} The PIR problem has originated in the computer science community \cite{ChorPIR, PIRsurvey2004, cachin1999computationally, ostrovsky2007survey, yekhanin2010private} and has drawn attention in the information theory society \cite{RamchandranPIR, unsynchonizedPIR, YamamotoPIR, VardyConf2015, RazanPIR, JafarConf2016} in recent years. In the classical setting of PIR, there are $N$ non-communicating databases, each storing the same set of $K$ messages. The user wishes to download one of these $K$ messages without letting the databases know the identity of the desired message. Sun and Jafar \cite{JafarPIR} have characterized the optimal normalized download cost for the classical PIR problem to be $\frac{D}{L}=\left( 1+\frac{1}{N}+\dots+\frac{1}{N^{K-1}}\right)$, where $L$ is the message size and $D$ is the total number of downloaded bits from the $N$ databases. After \cite{JafarPIR}, many interesting variants of the classical PIR problem have been investigated in \cite{JafarColluding, symmetricPIR, KarimCoded, arbmsgPIR, codedsymmetric, MultiroundPIR, codedcolluded, codedcolludedJafar, arbitraryCollusion, MPIRjournal, codedcolludingZhang, MPIRcodedcolludingZhang, BPIRjournal, tandon2017capacity, symmetricByzantine, tajeddine2017robust, wang2017linear, kadhe2017private, wei2017fundamental, chen2017capacity, wei2017capacity, wang2017secure, sun2017_computation, Kimcache2017, mirmohseni2017private, abdul2017private, wei2017jsac, banawan2018asymmetry, chen2018asymptotic, banawan2018private, d2018lifting, tajeddine2018private, wang2018secure}. The most closely related branch of PIR to our setting in this paper is cache-aided PIR in \cite{tandon2017capacity, kadhe2017private, wei2017fundamental, chen2017capacity, wei2017capacity, Kimcache2017, wei2017jsac}.

Cache-aided PIR is first considered in \cite{tandon2017capacity}, where the user has a local cache of storage $S$ messages ($SL$ bits) which can store any function of the $K$ messages, and the cache content of the user is perfectly known to all the $N$ databases. The optimal normalized download cost for this case is $D^*(S)= (1-\frac{S}{K})\left(1+\frac{1}{N}+\cdots+\frac{1}{N^{K-1}}\right)$, which indicates that the user should download the uncached part of the content via the optimum PIR scheme in \cite{JafarPIR}. The result is somewhat pessimistic since the user cannot further reduce the download cost by using the cache content. This has motivated subsequent works which have considered the case where the databases are completely unaware or partially unaware of the cache content \cite{kadhe2017private, wei2017fundamental, chen2017capacity, wei2017capacity, Kimcache2017, wei2017jsac}. Within this sub-branch of literature, references \cite{kadhe2017private,chen2017capacity,wei2017capacity} have considered PIR with PSI.

In \cite{kadhe2017private}, the authors considered the case where the user randomly chooses $M$ full messages out of $K$ messages to cache, and none of the databases is aware of the identities of the $M$ chosen messages. The user wishes to keep the identities of the $M$ chosen messages and the desired message private, which is coined as PIR with PSI. For the case of a single database, the optimal normalized download cost is settled in \cite{kadhe2017private}. For general number of databases, the optimal normalized download cost is characterized in \cite{chen2017capacity} as $D^*(M)= \left(1+\frac{1}{N}+\cdots+\frac{1}{N^{K-1-M}}\right)$. In \cite{wei2017capacity}, a more practical scenario is considered where each database is aware of the identities of the messages cached from that database only and unaware of the remaining identities of messages cached from other databases, which is coined as PIR with partially known PSI. Interestingly, the optimal normalized download cost for PIR with partially known PSI is the same as the optimal normalized download cost for PIR with PSI.

\textit{Coming back to our paper,} in this work, we consider PIR-PSI under a storage constraint. In the prefetching phase, the user can access $M$ messages, and has a local cache storage of $S$ messages ($SL$ symbols), where $S \leq M$. For each of these $M$ messages, the user caches the first $Lr_i$ symbols out of the total $L$ symbols for $i=1, \dots, M$. The caching scheme is subject to a memory size constraint, i.e., $\sum_{i=1}^M r_i=S$. Note that in \cite{wei2017fundamental, Kimcache2017, wei2017jsac}, for each message, the user randomly chooses $Lr$ symbols out of the total $L$ symbols to cache. In \cite{wei2017fundamental, Kimcache2017, wei2017jsac}, to reliably reconstruct the desired message, the user should record the indices of the cached symbols within each message. In contrast, here, we consider the case where the user caches the first $Lr_i$ symbols of each message instead of random $Lr_i$ symbols; this saves the user extra storage overhead. The databases are aware of the caching scheme, but do not know the identities of the cached messages, i.e., the databases know $M$ and $r_i$ for $i=1, \dots, M$, but do not know the identities of the cached messages. In the retrieval phase, the user wishes to jointly keep the identities of the cached messages and the desired message private. We call this model as PIR-PSI under a storage constraint.

For any given caching scheme, i.e., for given $M$ and $(r_1, r_2, \dots, r_M)$, we characterize the optimal normalized download cost to be $D^*=1+\frac{1}{N}+\frac{1}{N^2}+\dots+\frac{1}{N^{K-1-M}}
+\frac{1-r_M}{N^{K-M}}+\frac{1-r_{M-1}}{N^{K-M+1}}+\dots+\frac{1-r_1}{N^{K-1}}$, where without loss of generality $r_1 \geq r_2 \geq \dots \geq r_M$. Based on this capacity result, we prove two important facts: First, for a fixed memory size $S$ and fixed number of accessible messages $M$, uniform caching achieves the lowest normalized download cost, where uniform caching means $r_i=\frac{S}{M}$, for $i=1,\dots, M$. Second, for a fixed memory size $S$, among all the $K-\left \lceil{S} \right \rceil+1$ uniform caching schemes, the uniform caching scheme which caches $K$ messages achieves the lowest normalized download cost. That is, in order to optimally utilize the limited user cache memory, if the user has access to $M$ files, it should keep $SL/M$ bits (equal amounts) from each message in its cache memory; and second, if possible, the user should aim to have access to all $K$ messages, i.e., $M=K$ yields the lowest download cost.

\section{System Model}

We consider a system consisting of $N$ non-communicating databases and a user (retriever). Each database stores the same set of $K$ independent messages $W_1, \dots, W_K$, and each message is of size $L$ symbols, i.e.,
\begin{align}
H(W_1)=\dots=H(W_K)=L, \qquad H(W_1, \dots, W_K)=H(W_1)+\dots+H(W_K).
\end{align}
The user has a local cache memory which is of size $SL$ symbols, where $ S \in [0, K]$. There are two phases in the system: the prefetching phase and the retrieval phase.

In the prefetching phase, the user can randomly access $M$ messages out of total $K$ messages, where $M \geq S$. For each of the $M$ accessed messages, the user caches the first $Lr_i$ symbols out of the total $L$ symbols for $i=1, \dots, M$. The caching scheme is subject to a memory size constraint of $S$, i.e.,
\begin{align}
\sum_{i=1}^M r_i=S.
\end{align}
We denote the indices (identities) of the cached $M$ messages as $\mathbb{H}$, and denote $\mathcal{W}_\mathbb{H}$ as the cached messages. Therefore, $|\mathbb{H}|=M$, and $H(\mathcal{W}_\mathbb{H})=SL$.

Note that $M$ and $(r_1, \dots, r_M)$ specify a caching scheme. If $r_1=\dots=r_M$, we call this a uniform caching scheme. For fixed $S$, there are $K-\left \lceil{S} \right \rceil+1$ uniform caching schemes depending on the number of accessible messages since $M\geq S$. For instance, if there are $K=3$ messages in the databases and $S=1.5$, then since $M\geq S$, $M$ can take one of two possible values: either 2 or 3. Thus, there are two uniform caching schemes depending on the value of $M$. Note, $K-\left \lceil{S} \right \rceil+1=3-\left \lceil 1.5 \right \rceil +1=2$.

We assume that all the databases are aware of the caching scheme but are unaware of which messages are cached. For example, if $S=2$, $M=3$, and we say that the user has applied a uniform caching scheme, the databases know that the user has chosen $3$ messages out of the total $K$ messages to cache, and for each chosen message, the user has cached the first $\frac{2}{3}L$ symbols out of the total $L$ symbols. However, the databases do not know which messages are cached by the user.

In the retrieval phase, the user privately generates an index $\theta \in [K]=\{1, \dots, K\}$, and wishes to retrieve message $W_\theta$ such that it is impossible for any individual database to identify $\theta$. At the same time, the user also wishes to keep the indices of the $M$ cached messages private, i.e., in the retrieval phase the databases cannot learn which messages are cached. For random variables $\theta$, $\mathbb{H}$, and $W_1,\dots,W_K$, we have
\begin{align} \label{independency}
H\left(\theta, \mathbb{H}, W_1,\dots,W_K  \right)= H\left( \theta \right) + H\left( \mathbb{H} \right) + H(W_1)+\dots+H(W_K).
\end{align}

In order to retrieve message $W_\theta$, the user sends $N$ queries $Q_1^{[\theta, \mathbb{H}]}, \dots, Q_N^{[\theta, \mathbb{H}]}$ to the $N$ databases, where $Q_n^{[\theta, \mathbb{H}]}$ is the query sent to the $n$th database for message $W_\theta$. Note that the queries are generated according to $\mathbb{H}$, which are independent of the realization of the $K$ messages. Therefore,
\begin{align} \label{query_indep}
I(W_1, \dots, W_K;  Q_1^{[\theta, \mathbb{H}]}, \dots,  Q_N^{[\theta,\mathbb{H} ]}  ) =0.
\end{align}
Upon receiving the query $Q_n^{[\theta, \mathbb{H}]}$, the $n$th database replies with an answering string $A_n^{[\theta, \mathbb{H}]}$, which is a function of  $Q_n^{[\theta, \mathbb{H}]}$ and all the $K$ messages. Therefore, $\forall \theta \in [K], \forall n \in [N]$,
\begin{align} \label{answer_constraint}
H(A_n^{[\theta, \mathbb{H}]}|Q_n^{[\theta, \mathbb{H}]}, W_1, \dots, W_K)=0.
\end{align}
After receiving the answering strings $A_1^{[\theta, \mathbb{H}]}, \dots, A_N^{[\theta, \mathbb{H}]}$ from all the $N$ databases, the user needs to decode the desired message $W_\theta$ reliably. By using Fano's inequality, we have the following reliability constraint
\begin{align} \label{reliability_constraint}
H\left(W_\theta|\mathcal{W}_\mathbb{H}, \mathbb{H}, Q_1^{[\theta,\mathbb{H}]}, \dots, Q_N^{[\theta,\mathbb{H}]}, A_1^{[\theta,\mathbb{H}]}, \dots, A_N^{[\theta,\mathbb{H}]} \right) = o(L),
\end{align}
where $o(L)$ denotes a function such that $\frac{o(L)}{L} \rightarrow 0$ as $L \rightarrow \infty$.

To ensure that individual databases do not know which message is retrieved and to keep the $M$ cached messages private, we have the following privacy constraint, $\forall n \in [N]$, $\forall \theta, \theta' \in [K]$, $\forall \mathbb{H}, \mathbb{H}' \subset [K]$ such that $|\mathbb{H}|=|\mathbb{H}'|=M$,
\begin{align} \label{privacy_constraint}
(Q_n^{[\theta,\mathbb{H}]}, A_n^{[\theta,\mathbb{H}]}, W_1, \dots, W_K)  \sim (Q_n^{[\theta',\mathbb{H}']}, A_n^{[\theta',\mathbb{H}']}, W_1, \dots, W_K) ,
\end{align}
where $A \sim B$ means that $A$ and $B$ are identically distributed.

For a fixed $N$, $K$, $S$ and caching scheme $(r_1, \dots, r_M)$, a pair $\left(D,L\right)$ is achievable if there exists a PIR scheme for the message which is of size $L$ symbols satisfying the reliability constraint \eqref{reliability_constraint} and the privacy constraint \eqref{privacy_constraint}, where $D$ represents the expected number of downloaded bits (over all the queries) from the $N$ databases via the answering strings $A_{1:N}^{[\theta,\mathbb{H}]}$, where $A_{1:N}^{[\theta,\mathbb{H}]}=(A_1^{[\theta,\mathbb{H}]}, \dots, A_N^{[\theta,\mathbb{H}]} )$, i.e.,
\begin{align}
D=\sum_{n=1}^N H\left(A_n^{[\theta,\mathbb{H} ]} \right).
\end{align}
In this work, we aim at characterizing the optimal normalized download cost $D^*$, where
\begin{align}
D^*=\inf \left\{ \frac{D}{L}: \left(D, L \right) \text{ is achievable}  \right\}.
\end{align}

\section{Main Results and Discussions}

We characterize the exact normalized download cost for PIR-PSI under a storage constraint in the following theorem.

\begin{theorem} \label{Thm1}
In PIR-PSI under a storage constraint, the optimal normalized download cost is
\begin{align}
D^*=1+\frac{1}{N}+\frac{1}{N^2}+\dots+\frac{1}{N^{K-1-M}}+\frac{1-r_M}{N^{K-M}}+\frac{1-r_{M-1}}{N^{K-M+1}}
+\dots+\frac{1-r_1}{N^{K-1}} \label{eq_main2}
\end{align}
where $r_1 \geq r_2 \geq \dots \geq r_M$ without loss of generality.
\end{theorem}

The converse proof for Theorem~\ref{Thm1} is given in Section~\ref{Sec_Conv}, and the achievability proof for Theorem~\ref{Thm1} is given in Section~\ref{Sec_Achv}.

\begin{remark}
For $S=0$, by letting $r_i=0$, for $i=1, \dots, M$, \eqref{eq_main2} reduces to
\begin{align} \label{eq_PIR}
D^*= 1+\frac{1}{N}+\frac{1}{N^2}+\dots+\frac{1}{N^{K-1}},
\end{align}
which is the optimal normalized download cost of the original PIR problem as shown in \cite{JafarPIR}.
\end{remark}

\begin{remark}
For $S\in[K]$ and $M=S$, by letting $r_i=1$ for $i=1,\dots, M$, \eqref{eq_main2} reduces to
\begin{align} \label{eq_MDS_PIR}
D^*= 1+\frac{1}{N}+\frac{1}{N^2}+\dots+\frac{1}{N^{K-1-M}},
\end{align}
which is the optimal normalized download cost of the PIR with PSI problem as shown in \cite{chen2017capacity}. We can further generalize the result to the PIR with partially known PSI as shown in \cite{wei2017capacity}. Note further that for $M>S$, $(\frac{1-r_M}{N^{K-M}}+\frac{1-r_{M-1}}{N^{K-M+1}}+\dots+\frac{1-r_1}{N^{K-1}})$ is the penalty to the download cost under the storage constraint.
\end{remark}

\begin{corollary} \label{cor_1}
For fixed $M \geq S$, uniform caching scheme achieves the lowest normalized download cost.
\end{corollary}

\begin{Proof}
The user has access to $M$ messages. To achieve a low normalized download cost in \eqref{eq_main2}, we need to solve the following optimization problem,
\begin{align}
\min_{\alpha_i, i=1, \dots, M}& \quad \alpha_M \frac{1}{N^{K-M}} + \alpha_{M-1} \frac{1}{N^{K-M+1}} + \dots + \alpha_1 \frac{1}{N^{K-1}}  \notag \\
\text{s.t.} \quad & \quad  \alpha_M+\alpha_{M-1}+\dots + \alpha_1=M-S, \notag \\
           & \quad  1\geq \alpha_M\geq \alpha_{M-1} \geq \dots \geq \alpha_1 \geq 0,
           \label{opt-prob}
\end{align}
which is obtained by replacing $1-r_i$ in \eqref{eq_main2} with $\alpha_i$ for $i=1,\dots, M$. We prove by contradiction that the minimum is achieved when $\alpha_M=\alpha_{M-1}$. Suppose not, then we have optimum $\alpha^*_M>\alpha^*_{M-1}$. Choose $\delta=\frac{\alpha^*_M-\alpha^*_{M-1}}{3}$, and let $\alpha'_M=\alpha^*_M-\delta$, $\alpha'_{M-1}=\alpha^*_{M-1}+\delta$. Then, with $\alpha'_M$ and $\alpha'_{M-1}$, we achieve a lower normalized download cost than with $\alpha^*_M$ and $\alpha^*_{M-1}$, which gives a contradiction. Therefore, we have $\alpha_M=\alpha_{M-1}$. Intuitively, note that the coefficient of $\alpha_{M}$ is larger than the coefficient of $\alpha_{M-1}$ in the objective function in (\ref{opt-prob}). Therefore, in order to minimize the objective function, we need to choose $\alpha_{M}$ as small as possible. But, since $\alpha_M$ needs to be larger than $\alpha_{M-1}$ according to the constraint set of (\ref{opt-prob}), the smallest $\alpha_M$ we can choose is $\alpha_M=\alpha_{M-1}$. Using similar arguments, we also have $\alpha_{M-1}=\alpha_{M-2}=\dots=\alpha_{1}$. Therefore, uniform caching achieves the lowest normalized download cost for fixed $M$.
\end{Proof}

\begin{corollary} \label{cor_2}
For fixed $S$, among all the $K-\left \lceil{S} \right \rceil+1$ uniform caching schemes, the uniform caching scheme with $M=K$ achieves the lowest normalized download cost.
\end{corollary}

\begin{Proof}
For the uniform caching scheme $M$, the user caches the first $\frac{S}{M}L$ symbols of each chosen message. From \eqref{eq_main2}, the normalized download cost is
\begin{align}
D^*(M)=1+\frac{1}{N}+\frac{1}{N^2}+\dots+\frac{1}{N^{K-1-M}}+\left(1-\frac{S}{M}\right)\left(\frac{1}{N^{K-M}} +\dots + \frac{1}{N^{K-1}} \right).
\end{align}
Considering the difference of the normalized download costs between $D^*(M+1)$ and $D^*(M)$,
\begin{align}
&D^*(M+1)-D^*(M) \notag \\
&\qquad= 1+\frac{1}{N}+\frac{1}{N^2}+\dots+\frac{1}{N^{K-2-M}}+\left(1-\frac{S}{M+1}\right)\left(\frac{1}{N^{K-M-1}} +\dots + \frac{1}{N^{K-1}} \right) \notag \\
&\qquad~~ - \left[1+\frac{1}{N}+\frac{1}{N^2}+\dots+\frac{1}{N^{K-1-M}}
+\left(1-\frac{S}{M}\right)\left( \frac{1}{N^{K-M}} +\dots + \frac{1}{N^{K-1}}     \right)     \right]   \\
&\qquad= -\frac{S}{M+1} \left(\frac{1}{N^{K-M-1}} +\dots + \frac{1}{N^{K-1}} \right)
         +\frac{S}{M}\left( \frac{1}{N^{K-M}} +\dots + \frac{1}{N^{K-1}}     \right) \\
&\qquad= -\frac{S}{M+1}\times\frac{1}{N^{K-M-1}} +\left(\frac{S}{M}-\frac{S}{M+1}  \right)
\left( \frac{1}{N^{K-M}} +\dots + \frac{1}{N^{K-1}}     \right)        \\
&\qquad= \frac{S}{M(M+1)} \left( \frac{1}{N^{K-M}} +\dots + \frac{1}{N^{K-1}}     \right)
-\frac{S}{M(M+1)} \times\frac{M}{N^{K-M-1}} \\
&\qquad \leq 0.
\end{align}
Thus, the uniform caching scheme with $M=K$ achieves the lowest normalized download cost among all possible uniform caching schemes.
\end{Proof}

\begin{corollary}
For fixed $S$, among all possible caching schemes, the uniform caching scheme with $M=K$ achieves the lowest normalized download cost.
\end{corollary}

\begin{Proof}
From Corollary~\ref{cor_1}, we know that for fixed $M$, uniform caching scheme achieves the lowest normalized download cost. From Corollary~\ref{cor_2}, we know that among all uniform caching schemes, the uniform caching scheme with $M=K$ achieves the lowest normalized download cost. Combining these two corollaries, we conclude that among all possible caching schemes, the uniform caching scheme with $M=K$ achieves the lowest normalized download cost.
\end{Proof}

\section{Converse Proof} \label{Sec_Conv}

In this section, we provide a lower bound for PIR-PSI under a storage constraint. In the following, without loss of generality, we relabel the messages according to $\mathbb{H}$, such that $W_{1:M}$ are the messages accessed by the user in the prefetching phase, where $W_{1:M}=(W_1, W_2, \dots, W_M)$. Here, $W_{i}$ denotes the message whose first $Lr_i$ symbols are cached by the user, for $i=1, 2, \dots, M$, and without loss of generality, $r_1 \geq r_2 \geq \dots \geq r_M$.

We first need the following lemma, which develops a lower bound on the length of the undesired portion of the answering strings as a consequence of the privacy constraint.

\begin{lemma}[Interference lower bound]\label{lemma_converse1}
For PIR-PSI under a storage constraint, the interference from undesired messages within the answering strings, $D-L$, is lower bounded by,
\begin{align} \label{eq_L1}
D-L+o(L)\geq I\left(W_{1:K-1};Q_{1:N}^{[K,\mathbb{H}]},A_{1:N}^{[K,\mathbb{H}]}|\mathcal{W}_{\mathbb{H}},\mathbb{H},W_K \right).
\end{align}
\end{lemma}

If the privacy constraint is absent, the user downloads only $L$ symbols of the desired message, however, when the privacy constraint is present, it should download $D$ symbols. The difference between $D$ and $L$, i.e., $D-L$, corresponds to the undesired portion of the answering strings. Note that Lemma~\ref{lemma_converse1} is an extension of \cite[Lemma~5]{JafarPIR}, where $M=0$, i.e., the user has no PSI. Lemma~\ref{lemma_converse1} differs from its counterpart in \cite[Lemma~1]{wei2017fundamental} in two aspects; first, the left hand side is $D(r)-L(1-r)$ in \cite{wei2017fundamental} as the user requests to download the uncached bits only, and second,  \cite[Lemma~1]{wei2017fundamental} constructs $K-1$ distinct lower bounds by changing $k$, in contrast to only one bound here. In addition, we note that a similar argument to Lemma~\ref{lemma_converse1} can be implied from \cite{chen2017capacity} and \cite{wei2017capacity}. The main difference between Lemma~\ref{lemma_converse1} and \cite{chen2017capacity,wei2017capacity} is that $\mathcal{W}_{\mathbb{H}}$ refers to parts of messages here, while in \cite{chen2017capacity,wei2017capacity}, $\mathcal{W}_{\mathbb{H}}$ refers to full messages.

\begin{Proof}
We start with the right hand side of \eqref{eq_L1},
\begin{align}
I\left(W_{1:K-1};Q_{1:N}^{[K, \mathbb{H}]}, A_{1:N}^{[K, \mathbb{H}]}|\mathcal{W}_{\mathbb{H}},\mathbb{H},W_K \right)
\leq I\left(W_{1:K-1};Q_{1:N}^{[K,\mathbb{H}]},A_{1:N}^{[K,\mathbb{H}]},W_K|\mathcal{W}_{\mathbb{H}}, \mathbb{H} \right).  \label{eq_lemma_1}
\end{align}
For the right hand side of \eqref{eq_lemma_1}, we have
\begin{align}
& I\left(W_{1:K-1};Q_{1:N}^{[K,\mathbb{H}]},A_{1:N}^{[K,\mathbb{H}]},W_K|\mathcal{W}_{\mathbb{H}}, \mathbb{H} \right) \notag \\
&\qquad =I\left(W_{1:K-1};Q_{1:N}^{[K,\mathbb{H}]}, A_{1:N}^{[K, \mathbb{H}]}|\mathcal{W}_{\mathbb{H}}, \mathbb{H} \right)
 + I \left( W_{1:K-1}; W_K|Q_{1:N}^{[K, \mathbb{H}]}, A_{1:N}^{[K, \mathbb{H}]},\mathcal{W}_\mathbb{H}, \mathbb{H} \right) \\
&\qquad\label{eq_ILB_1}\stackrel{\eqref{reliability_constraint}}{=}
I\left(W_{1:K-1};Q_{1:N}^{[K,\mathbb{H}]}, A_{1:N}^{[K, \mathbb{H}]}|\mathcal{W}_{\mathbb{H}}, \mathbb{H} \right)+ o(L) \\
&\label{eq_ILB_2} \quad~\stackrel{\eqref{independency},\eqref{query_indep}}{=}
I\left(W_{1:K-1}; A_{1:N}^{[K, \mathbb{H}]} |\mathcal{W}_{\mathbb{H}}, \mathbb{H}, Q_{1:N}^{[K,\mathbb{H}]} \right) + o(L) \\
&\qquad= H\left( A_{1:N}^{[K, \mathbb{H}]} |\mathcal{W}_{\mathbb{H}}, \mathbb{H}, Q_{1:N}^{[K,\mathbb{H}]} \right)
  - H\left(A_{1:N}^{[K, \mathbb{H}]} |\mathcal{W}_\mathbb{H}, \mathbb{H}, Q_{1:N}^{[K,\mathbb{H}]},W_{1:K-1}  \right)   + o(L) \\
&\qquad\leq D- H\left(A_{1:N}^{[K, \mathbb{H}]} |\mathcal{W}_\mathbb{H}, \mathbb{H}, Q_{1:N}^{[K,\mathbb{H}]},W_{1:K-1}  \right)  + o(L) \label{eq_L1_1} \\
&\qquad\label{eq_ILB_3}\stackrel{\eqref{reliability_constraint}}{=}
D-H\left(A_{1:N}^{[K, \mathbb{H}]}, W_K |\mathcal{W}_\mathbb{H}, \mathbb{H}, Q_{1:N}^{[K,\mathbb{H}]},W_{1:K-1}  \right)+o(L) \\
&\qquad\label{eq_ILB_4}\leq D-H\left(W_K |\mathcal{W}_\mathbb{H}, \mathbb{H}, Q_{1:N}^{[K,\mathbb{H}]},W_{1:K-1}  \right)  + o(L) \\
&\quad~\label{eq_ILB_5}\stackrel{\eqref{independency},\eqref{query_indep}}{=} D-L + o(L)
\end{align}
where \eqref{eq_ILB_1}, \eqref{eq_ILB_3} follow from the decodability of $W_{K}$ given $\left(Q_{1:N}^{[K, \mathbb{H}]}, A_{1:N}^{[K, \mathbb{H}]},\mathcal{W}_\mathbb{H},\mathbb{H} \right)$, \eqref{eq_ILB_2}, \eqref{eq_ILB_5} follow from the independence of $W_{1:K}$ and $Q_{1:N}^{[K, \mathbb{H}]}$ given  $\mathbb{H}$, and \eqref{eq_L1_1} follows from the independence bound. Combining \eqref{eq_lemma_1} and \eqref{eq_ILB_5} yields \eqref{eq_L1}.
\end{Proof}

For the conditional mutual information term on the right hand side of \eqref{eq_L1}, we have
\begin{align}
I\left(W_{1:K-1};Q_{1:N}^{[K,\mathbb{H}]},A_{1:N}^{[K,\mathbb{H}]}|\mathcal{W}_{\mathbb{H}},\mathbb{H},W_K \right)
& = \sum_{h} p(h) I\left(W_{1:K-1};Q_{1:N}^{[K,h]},A_{1:N}^{[K,h]}|\mathcal{W}_h,h,W_K \right) \\
& = \sum_{h} p(h) I\left(W_{1:K-1};Q_{1:N}^{[K,h]},A_{1:N}^{[K,h]}|\mathcal{W}_h,W_{K} \right). \label{eq_conv_1}
\end{align}
where we have written the mutual information in \eqref{eq_L1} as an expectation over all possible caching scheme realizations, as the databases do not know which messages are cached.

In the following lemma, we develop an inductive relation for the mutual information term on the right hand side of \eqref{eq_conv_1}.

\begin{lemma}[Fractional induction lemma]\label{lemma_converse2}
For all $k\in \{1,\dots,K-1\}$, the mutual information term in \eqref{eq_conv_1} can be inductively lower bounded as,
\begin{align} \label{eq_L2}
&I\left( W_{1:k}; Q_{1:N}^{[k+1, h]}, A_{1:N}^{[k+1, h]} |\mathcal{W}_h, W_{k+1:K} \right) \notag \\
&\qquad\quad \geq \frac{1}{N}  I\left(W_{1:k-1} ;Q_{1:N}^{[k,h]}, A_{1:N}^{[k, h]}|\mathcal{W}_h, W_{k:K}  \right)  +\frac{L}{N}(1-r_k)- o(L),
\end{align}
where $r_k=0$ when $k>M$.
\end{lemma}

Lemma~\ref{lemma_converse2} is a generalization of \cite[Lemma~6]{JafarPIR} to our setting. The main difference between Lemma~\ref{lemma_converse2} and \cite[Lemma~6]{JafarPIR} is that the cached PSI results in a different induction relation.

\begin{Proof}
We start with the left hand side of \eqref{eq_L2},
\begin{align}
&I\left( W_{1:k}; Q_{1:N}^{[k+1, h]}, A_{1:N}^{[k+1, h]} |\mathcal{W}_h, W_{k+1:K} \right) \notag \\
&\qquad=\frac{1}{N} \times N \times I\left( W_{1:k}; Q_{1:N}^{[k+1, h]}, A_{1:N}^{[k+1, h]} |\mathcal{W}_h, W_{k+1:K} \right)  \\
&\qquad \geq \frac{1}{N}\sum_{n=1}^N I\left( W_{1:k}; Q_n^{[k+1, h]}, A_n^{[k+1, h]} |\mathcal{W}_h, W_{k+1:K} \right)  \label{eq_L2_1} \\
&\qquad \stackrel{\eqref{privacy_constraint}}{=}
\frac{1}{N} \sum_{n=1}^N I\left( W_{1:k}; Q_n^{[k, h]}, A_n^{[k, h]} |\mathcal{W}_h, W_{k+1:K} \right)   \label{eq_L2_2}\\
&\qquad \geq \frac{1}{N} \sum_{n=1}^N I\left( W_{1:k}; A_n^{[k, h]} |\mathcal{W}_h, W_{k+1:K}, Q_n^{[k, h]} \right) \label{eq_L2_3}  \\
&\qquad\stackrel{\eqref{answer_constraint}}{=}
\frac{1}{N}\sum_{n=1}^N H \left(A_n^{[k, h]} |\mathcal{W}_h, W_{k+1:K}, Q_n^{[k, h]} \right)\label{eq_L2_4}\\
&\qquad \geq \frac{1}{N}\sum_{n=1}^N  H \left(A_n^{[k, h]} |\mathcal{W}_h, W_{k+1:K}, Q_{1:N}^{[k, h]}, A_{1:n-1}^{[k, h]} \right)
\label{eq_L2_5}\\
&\qquad \stackrel{\eqref{answer_constraint}}{=}
\frac{1}{N}\sum_{n=1}^N I \left(W_{1:k}; A_n^{[k, h]} |\mathcal{W}_h, W_{k+1:K}, Q_{1:N}^{[k, h]}, A_{1:n-1}^{[k, h]} \right) \label{eq_L2_6}\\
&\qquad = \frac{1}{N} I \left(W_{1:k};  A_{1:N}^{[k, h]} |\mathcal{W}_h, W_{k+1:K}, Q_{1:N}^{[k, h]} \right) \\
&\quad~\stackrel{\eqref{independency},\eqref{query_indep}}{=}
\frac{1}{N} I \left(W_{1:k}; Q_{1:N}^{[k, h]},  A_{1:N}^{[k, h]} |\mathcal{W}_h, W_{k+1:K}  \right) \label{eq_L2_7}\\
&\qquad\stackrel{\eqref{reliability_constraint}}{=} \frac{1}{N}
I \left(W_{1:k};W_k, Q_{1:N}^{[k, h]},  A_{1:N}^{[k, h]} |\mathcal{W}_h, W_{k+1:K}  \right)  -o(L)   \label{eq_L2_8}\\
&\qquad = \frac{1}{N} I \left(W_{1:k}; W_k|\mathcal{W}_h, W_{k+1:K}  \right)
        + \frac{1}{N} I \left(W_{1:k}; Q_{1:N}^{[k, h]},  A_{1:N}^{[k, h]}|\mathcal{W}_h, W_{k:K}  \right)   -o(L) \\
&\qquad = \frac{1}{N} I \left(W_{1:k}; Q_{1:N}^{[k, h]},  A_{1:N}^{[k, h]}|\mathcal{W}_h, W_{k:K}  \right) +\frac{L}{N}(1-r_k) -o(L), \label{eq_L2_9}
\end{align}
where \eqref{eq_L2_1} and \eqref{eq_L2_3} follow from the chain rule and the non-negativity of mutual information, \eqref{eq_L2_2} follows from the privacy constraint,  \eqref{eq_L2_4}, \eqref{eq_L2_6} follow from the fact that answer strings are deterministic functions of the messages and the queries, \eqref{eq_L2_5} follows from the fact that conditioning reduces entropy, \eqref{eq_L2_7} follows from the independence of $W_{1:K}$ and $Q_{1:N}^{[k, h]}$, \eqref{eq_L2_8} follows from the reliability constraint on $W_k$, and \eqref{eq_L2_9} is due to the fact that $H\left(W_k|\mathcal{W}_h, W_{k+1:K}  \right)=L(1-r_k)$, where if $k\notin h$ then $r_k=0$.
\end{Proof}

By applying Lemma~\ref{lemma_converse2} recursively to the right hand side of \eqref{eq_conv_1}
\begin{align}
&I\left(W_{1:K-1};Q_{1:N}^{[K,h]},A_{1:N}^{[K,h]}|\mathcal{W}_h,W_{K} \right) \notag \\
&\qquad \stackrel{\eqref{eq_L2}}{\geq}
\frac{1}{N} I\left(W_{1:K-2} ;Q_{1:N}^{[K-1,h]}, A_{1:N}^{[K-1, h]}|\mathcal{W}_h, W_{K-1:K}  \right)+\frac{L}{N}- o(L) \label{eqc1} \\
&\qquad \stackrel{\eqref{eq_L2}}{\geq}
\frac{1}{N^2} I\left(W_{1:K-3} ;Q_{1:N}^{[K-2,h]}, A_{1:N}^{[K-2, h]}|\mathcal{W}_h, W_{K-2:K}  \right)+\frac{L}{N^2}+\frac{L}{N}- o(L) \\
&\qquad \stackrel{\eqref{eq_L2}}{\geq} \dots \\
&\qquad \stackrel{\eqref{eq_L2}}{\geq}
\frac{1}{N^{K-1-M}} I\left(W_{1:M} ;Q_{1:N}^{[M+1,h]}, A_{1:N}^{[M+1, h]}|\mathcal{W}_h, W_{M+1:K}  \right) \notag \\
&\qquad \qquad +\frac{L}{N^{K-1-M}} +\dots+ \frac{L}{N^2}+\frac{L}{N}- o(L) \label{eqc2} \\
&\qquad \stackrel{\eqref{eq_L2}}{\geq}
\frac{1}{N^{K-M}} I\left(W_{1:M-1} ;Q_{1:N}^{[M,h]}, A_{1:N}^{[M, h]}|\mathcal{W}_h, W_{M:K}  \right) +\frac{L}{N^{K-M}}(1-r_M) \notag \label{eqc3} \\
&\qquad \qquad +\frac{L}{N^{K-1-M}} +\dots+ \frac{L}{N^2}+\frac{L}{N}- o(L) \\
&\qquad \stackrel{\eqref{eq_L2}}{\geq} \dots \\
&\qquad \stackrel{\eqref{eq_L2}}{\geq}
\frac {L(1-r_1)}{N^{K-1}}+\dots+\frac{L(1-r_{M})}{N^{K-M}}+\dots+ \frac{L}{N^2}+\frac{L}{N}-o(L). \label{eqc4}
\end{align}
Note that in \eqref{eqc1} to \eqref{eqc2}, we apply the fractional induction lemma with $r=0$, since $W_{M+1:K}$ are not cached in $\mathcal{W}_h$. In \eqref{eqc3} to \eqref{eqc4}, $r_k>0$ for the fractional induction lemma, since $W_{1:M}$ are cached in $\mathcal{W}_h$ partially.

By combining \eqref{eq_L1}, \eqref{eq_conv_1}, and \eqref{eqc4}, and dividing by $L$ on both sides, we obtain a lower bound for the normalized download cost as
\begin{align}
D^* \geq 1+\frac{1}{N}+\frac{1}{N^2}+\dots+\frac{1}{N^{K-1-M}}+\frac{1-r_M}{N^{K-M}}+\frac{1-r_{M-1}}{N^{K-M+1}}+\dots+\frac{1-r_1}{N^{K-1}},
\end{align}
which proves \eqref{eq_main2}.

\section{Achievability Proof}\label{Sec_Achv}

Our achievability scheme is based on the PIR schemes in \cite{JafarPIR} and \cite{chen2017capacity}. For the portion of the messages not cached by the user, we use the PIR scheme in \cite{JafarPIR}, which applies the following three principles recursively: 1) database symmetry, 2) message symmetry within each database, and 3) exploiting undesired messages as side information. For the portion of the messages cached by the user, we use the PIR scheme in \cite{chen2017capacity}, which is based on MDS codes and consists of two stages: The first stage determines the systematic part of the MDS code according to the queries generated in \cite{JafarPIR}. In the second stage, the user reduces the download cost by downloading the parity part of the MDS code only. By applying the two PIR schemes, the user retrieves the desired message privately while keeping the cached messages private.

\subsection{Motivating Examples}

\subsubsection{$N=2$ Databases, $K=5$ Messages, $M=2$ Accessed Messages, and $S=1$ with Uniform Caching}

In this example, in the prefetching phase, the user randomly chooses two messages to cache, say $W_1$ and $W_4$. Since $S=1$ and the user uses uniform caching scheme, the user caches the first half of $W_1$ and the first half of $W_4$. We note that the databases are aware of the caching scheme, i.e., the databases know that two out of five messages are chosen by the user, and the first halves of the chosen messages are cached. However, the databases do not know which are the two chosen messages.

In the retrieval phase, assume that the user wishes to retrieve message $W_3$ privately. For the first half portion of the message, i.e., for the symbols in the interval $[0, \frac{L}{2}]$, since the user has cached messages $W_1$ and $W_4$, the user applies the PIR scheme in \cite{chen2017capacity} with $M=2$. The total download cost for the first half portion of the message, as shown in \eqref{eq_MDS_PIR}, is
\begin{align} \label{eq_ex1}
\frac{L}{2} \times \left(1+\frac{1}{2}+\frac{1}{2^{5-1-2}} \right).
\end{align}
For the remaining half portion of the message, i.e., for the symbols in the interval $[\frac{L}{2}, L]$, since the user has not cached any messages, the user applies the PIR scheme in \cite{JafarPIR}. The total download cost for the remaining half portion of the message, as shown in \eqref{eq_PIR}, is
\begin{align} \label{eq_ex2}
\frac{L}{2} \times \left(1+\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\frac{1}{2^{5-1}} \right).
\end{align}

The overall download cost is the sum of \eqref{eq_ex1} and \eqref{eq_ex2}. Therefore, the optimal normalized download cost is $\frac{59}{32}$, which can also be obtained through \eqref{eq_main2} by letting $r_1=\frac{1}{2}$ and $r_2=\frac{1}{2}$. Note that since we have applied the PIR scheme in \cite{chen2017capacity} to retrieve the first half portion of the message, the databases cannot learn which messages are cached by the user. In addition, both PIR schemes in \cite{JafarPIR} and \cite{chen2017capacity} keep the identity of the desired message private. Therefore, the combination of these two PIR schemes is a feasible PIR scheme for PIR-PSI a under storage constraint \cite{arbmsgPIR}.

\subsubsection{$N=2$ Databases, $K=5$ Messages, $S=1$, $M=3$ with $r_1=\frac{1}{2}$, and $r_2=r_3=\frac{1}{4}$}

\begin{figure}[t]
	\centering
	\epsfig{file=./ach.eps,width=0.5\textwidth}
	\caption{Achievable scheme: $K=5$, $S=1$, and $M=3$ with $r_1=\frac{1}{2}$, and $r_2=r_3=\frac{1}{4}$.}
	\label{ex_ach}
\end{figure}

In this example, see Fig.~\ref{ex_ach}, in the prefetching phase, since $r_1=\frac{1}{2}$, the user first randomly chooses one message to cache, say $W_3$, and the user caches the first half of $W_3$. Since $r_2=r_3=\frac{1}{4}$, the user then randomly chooses two other messages to cache, say $W_2$ and $W_5$, and the user caches the first $\frac{1}{4}$ portions of $W_2$ and $W_5$. Note that $S=1$ and $\frac{1}{2}\times 1 + \frac{1}{4}\times 2=1$, and the local cache memory size constraint is satisfied. We note that the databases are aware of the caching strategy, i.e., the databases know that three out of five messages are chosen by the user, and for one of the chosen message, the first half of the message is cached, and for the remaining two chosen messages, the first $\frac{1}{4}$ portions are cached. However, the databases do not know which three messages are chosen.

In the retrieval phase, assume that the user wishes to retrieve message $W_1$ privately. For the first $\frac{1}{4}$ portion of messages, i.e., for the symbols in the interval $[0, \frac{L}{4}]$, since the user caches messages $W_2$, $W_3$ and $W_5$, the user applies the PIR scheme in \cite{chen2017capacity} with $M=3$. The total download cost for the first $\frac{1}{4}$  portion of the message, as shown in \eqref{eq_MDS_PIR}, is
\begin{align} \label{eq_ex3}
\frac{L}{4} \times \left(1+\frac{1}{2^{5-1-3}}\right).
\end{align}
For the following $\frac{1}{4}$ portion of messages, i.e., for the symbols in the interval $[\frac{L}{4}, \frac{L}{2}]$, since the user caches message $W_3$, the user applies the PIR scheme in \cite{chen2017capacity} with $M=1$. The total download cost for the second $\frac{1}{4}$  portion of the message, as shown in \eqref{eq_MDS_PIR}, is
\begin{align} \label{eq_ex5}
\frac{L}{4} \times \left(1+\frac{1}{2}+\frac{1}{2^2}+ \frac{1}{2^{5-1-1}}\right).
\end{align}
For the last half portion of messages, i.e., for the symbols in the interval $[\frac{L}{2}, L]$, since the user has not cached any messages, the user applies the PIR scheme in \cite{JafarPIR}. The total download cost for the last half portion of the message, as shown in \eqref{eq_PIR}, is
\begin{align} \label{eq_ex4}
\frac{L}{2} \times \left(1+\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\frac{1}{2^{5-1}} \right).
\end{align}

The overall download cost is the sum of \eqref{eq_ex3}, \eqref{eq_ex5} and \eqref{eq_ex4}. Therefore, the optimal normalized download cost is $\frac{29}{16}$, which can also be obtained through \eqref{eq_main2} by letting $r_1=\frac{1}{2}$, and $r_2=r_3=\frac{1}{4}$. Note that by applying the PIR scheme in \cite{chen2017capacity} to retrieve the first $\frac{1}{4}$ portion and the middle $\frac{1}{4}$ portion of the message, the databases cannot learn which messages have been cached by the user. In addition, both PIR schemes in \cite{JafarPIR} and \cite{chen2017capacity} hide the identity of the desired message. Therefore, the combination of these two PIR schemes is a feasible PIR scheme for PIR-PSI under a storage constraint \cite{arbmsgPIR}.

\subsection{General Achievable Scheme}

We now describe the general achievable scheme for $r_1 \geq r_2 \geq \dots \geq r_M$. We first consider the first $r_M$ fraction of messages, i.e., for the symbols in the interval $[0, Lr_M]$. Since $r_1 \geq r_2 \geq \dots \geq r_M$, the user caches $M$ messages for this portion. The user applies the PIR scheme in \cite{chen2017capacity} which results in the download cost
\begin{align} \label{eq_ach_1}
L r_M \times \left( 1+\frac{1}{N}++\frac{1}{N^2} +\dots  +\frac{1}{N^{K-1-M}}   \right).
\end{align}
Following the same logic, for the symbols in the interval $[Lr_i, Lr_{i-1}]$, $i\geq2$, the user caches $i$ messages for this portion. The user applies the PIR scheme in \cite{chen2017capacity} which results in the download cost
\begin{align} \label{eq_ach_2}
L (r_{i-1}-r_i) \times \left( 1+\frac{1}{N}++\frac{1}{N^2} +\dots  +\frac{1}{N^{K-i }}   \right).
\end{align}
Lastly, for the symbols in the interval $[Lr_1, L]$, the user caches no messages for this portion. The user applies the PIR scheme in \cite{JafarPIR} which results in the download cost
\begin{align} \label{eq_ach_3}
L (1-r_1) \times \left( 1+\frac{1}{N}++\frac{1}{N^2} +\dots  +\frac{1}{N^{K-1}}   \right).
\end{align}

The overall download cost is the sum of \eqref{eq_ach_1}, \eqref{eq_ach_2} for $i=2,3,\dots, M$, and \eqref{eq_ach_3}, which is \eqref{eq_main2}. By applying the PIR scheme in \cite{chen2017capacity} to retrieve symbols in the interval of $[0, Lr_1]$, the databases cannot learn which messages have been cached by the user. In addition, both PIR schemes in \cite{JafarPIR} and \cite{chen2017capacity} protect the identity of the desired message. Therefore, the combination of these two PIR schemes is a feasible PIR scheme for PIR-PSI under a storage constraint \cite{arbmsgPIR}.

\section{Conclusion}

In this paper, we have introduced a new PIR model, namely PIR-PSI under a storage constraint. In this model, the user randomly chooses $M$ messages and caches the first $r_i$ portion of the chosen messages for $i=1, \dots, M$ subject to the memory size constraint $\sum_{i=1}^M r_i=S$. In the retrieval phase, the user wishes to retrieve a message such that no individual database can learn the identity of the desired message and the identities of the cached messages. For each caching scheme, i.e., $(r_1, \dots, r_M)$, we characterized the optimal normalized download cost to be $D^*=1+\frac{1}{N}+\frac{1}{N^2}+\dots+\frac{1}{N^{K-1-M}}+\frac{1-r_M}{N^{K-M}}+\frac{1-r_{M-1}}{N^{K-M+1}}+\dots+\frac{1-r_1}{N^{K-1}}$. In addition, we showed that, for a fixed memory size $S$, and a fixed number of accessible messages $M$, uniform caching achieves the lowest normalized download cost, where uniform caching means $r_i=\frac{S}{M}$, $i=1,\dots, M$. Then, we showed that, for a fixed memory size $S$, among all $K-\left \lceil{S} \right \rceil+1$ uniform caching schemes, the uniform caching scheme caching $M=K$ messages achieves the lowest normalized download cost. Finally, we conclude that for a fixed memory size $S$, the uniform caching scheme caching $K$ messages achieves the lowest normalized download cost.

config: arxiv


text:
\begin{document}

\pagestyle{plain}
\title{Representations of the Infinite-Dimensional Affine Group}

\date{}
\author{
  \textbf{Yuri Kondratiev}\\
Department of Mathematics, University of Bielefeld, \\
D-33615 Bielefeld, Germany,\\
Dragomanov  University, Kyiv, Ukraine\\
}
\begin{abstract}
We introduce an infinite-dimensional  affine group and construct its irreducible unitary representation. Our approach follows the one used by Vershik, Gelfand and Graev for the diffeomorphism group, but with modifications made necessary by the fact that the group does not act on the phase space. However it is possible to define its action on some classes of functions.
\end{abstract}

\maketitle

\vspace*{3cm}
\vspace{2cm}
{\bf Key words: } affine group; configurations; Poisson measure; ergodicity

\medskip
{\bf MSC 2010}. Primary: 22E66. Secondary: 60B15.

\medskip

\newpage
\section{Introduction}

Given a vector space $V$  the affine group  can be described concretely as the semidirect product of $V$ by $\mathrm{GL}(V)$, the general linear group of $V$:
$$
 \mathrm{Aff} (V)=V  \rtimes \mathrm{ GL} (V).
 $$
The action of $\mathrm{GL}(V)$ on $V$ is the natural one (linear transformations are automorphisms), so this defines a semidirect product.

Affine groups play important role in the geometry and its applications, see, e.g., \cite{Ar,Ly}. Several recent papers \cite{AJO,AK,EH,GJ,Jo,Ze} are devoted to representations of the real, complex and $p$-adic affine groups and their generalizations, as well as diverse applications, from wavelets and Toeplitz operators to non-Abelian pseudo-differential operators and $p$-adic quantum groups.

In the particular case of  field $V= \X$ the group $\mathrm{Aff}(\X)$ defined as following.

Consider a function $b:\X \to \X$  which is a step function on $\X$.
Take another  matrix valued function $A:\X\to L(\X) $ s.t. $A(x)=\mathrm{Id} +A_0(x)$,  $A(x)$ is invertible, $A_0$ is a matrix valued step function
on $\X$.  Introduce an
infinite dimensional affine group
$\Aff (\X)$ that is the set of all pairs $g=(A,b)$ with component satisfying assumptions above. Define the group
operation
$$
g_2 g_1=  (A_2,b_2) (A_1, b_1) = (A_1 A_2, b_1 +A_1 b_2).
$$
The unity in this group is $e=(\mathrm{Id} ,0)$.
For $g\in \Aff(\X)$ holds $g^{-1}= (A^{-1}, -A^{-1}b)$.
It is clear that for step mappings we use these definitions are correct.
Our aim is to construct irreducible representations of $\Aff (\X)$. As a rule, only special classes of irreducible representations can be constructed for infinite-dimensional groups. For various classes of such groups, special tools were invented; see \cite{Is,Ko} and references therein.

We will follow an approach by Vershik-Gefand -Graev \cite{VGG75} proposed in the case of
the group of diffeomorphisms.  A direct application of this approach meets certain difficulties
related with the absence of the possibility to define the action of the group $\Aff (\X)$ on a phase space
similar to \cite{VGG75}.  A method to overcome this problem is the main technical step in the present paper.
We wold like to mention that a similar approach was already used in \cite{PAFF} for the construction
of the representation for p-adic infinie dimensional affine group.

\maketitle

\section{Infinite dimensional   affine group}

In our definitions and studies of vector and matrix  valued functions on $\X$ we
will use as basic functional spaces collections of step mappings.
It means that each such mapping is a finite sum of indicator functions with measurable
bounded supports with constant vector/matrix coefficients. Such spaces of functions on
$\X$ are rather unusual in the framework of infinite dimensional groups but we will try
to show that their use is natural for the study of affine groups.

For $x\in\X$ consider the section $G_x= \{g(x)\; |\; g\in \Aff(\X)\}$.
It is an affine group with constant coefficients. Note that for a ball $B_N (0) \subset \X$ with the radius $N$
centered at zero we have $g(x)= (1,0), x\in B^c_N(0)$.

Define the action of $g$ on a point $x\in\X$ as
$$
gx= g(x)x =  A(x)^{-1} (x+b(x)).
$$
Denote the orbit $O_x=\{gx| g\in G_x\}\subset \X$.
Actually,  as a set $O_x=\X$ but elements of this set are
parametrized by $g\in G_x$.
For any element $y\in O_x$  and $h\in G_x$ we can define
$hy= h(gx)= (hg)x\in O_x$. It means that we have the group
$G_x$ action on the orbit $O_x$.

It gives

$$
(g_1g_2)(x) x= g_1(x)( g_2(x)x)
$$
 that corresponds to the group multiplication
 $$
 g_2 g_1=  (A_2,b_2) (A_1, b_1) = (A_1 A_2, b_1 +A_1 b_2)
 $$
 considered in the given point $x$.

\begin{Remark}
The situation we have is quite different w.r.t. the standard
group of motions on a phase space. Namely,
we have one fixed point $x\in\X$ and the section group
$G_x$  associated with this point. Then we have the motion of
$x$ under the action of $G_x$. It gives the group action on the
orbit $O_x$.
\end{Remark}

We will  use  the configuration space $\Ga(\X)$, i.e., the set of all locally finite
subsets of $\X$.

Each configuration may be identified with the measure
$$
\gamma(dx) = \sum_{x\in\gamma} \delta_x
$$
which is a positive  Radon measure on $\X$: $\gamma\in \M(\X)$.
We define the vague topology on $\Ga(\X)$ as the weakest topology for
which all mappings
$$
\Ga(\X) \ni \ga \mapsto <f,\gamma>\in \R,\;\; f\in C_0(\X)
$$
are continuous. The Borel $\sigma$-algebra for this topology denoted
$\B(\Ga(\X))$.

For $\ga\in \Ga(\X)$, $\ga=\{x\}\subset \X$ define
$g\gamma$ as a motion of the measure $\ga$:

$$
g\ga=\sum_{x\gamma} \delta_{g(x)x}\in \M(\X).
$$
Here we have the group action of $\Aff(\X)$ produced by individual transformations
of points from the configuration. Again, as above, we move a fixed configuration using
previously defined actions of $G_x$ on $x\in\ga$.

Note that $g\gamma$ is not more a configuration. More precisely, for some $B_N(0) $
the set $(g\ga)_N= g\ga\cap B_N^c(0)$ is a configuration in $B^c_N(0) $ but the finite part
of $g\ga$ may include multiple points.

For any $f\in \D(\X,\C)$ we have corresponding cylinder  function on $\Ga(\X)$:
$$
L_f(\ga)=  <f,\ga > = \int_{\X} f(x)\ga(dx) = \sum_{x\in \ga} f(x).
$$
Denote $\PC$ the set of all  cylinder polynomials generated by such functions.
More generally, consider functions of the form

\begin{equation}
\label{cyl}
F(\ga)= \psi(<f_1,\ga>,\dots, <f_n,\ga>),\; \ga\in\Ga(\X),  f_j\in \D(\X), \psi\in C_b(\R^n).
\end{equation}

These functions form the set $\CF_b(\Ga(\X))$ of all  bounded cylinder functions.

For any clopen set $\Lambda \in \mathcal{O}_b(\X)$ (also called a finite volume) denote
$\Ga(\Lambda)$ the set of all (with necessity finite) configurations
in $\La$.   We  have as before the vague topology on this space and
the Borel $\sigma$-algebra $\B(\Ga(\La))$ is generated by functions
$$
\Ga(\La)\ni\ga \mapsto <f,\ga>\in\R
$$
for $f\in C_0 (\La)$.  For any $\La\in \mathcal{O}_b(\X)$ and $T\in \B(\Ga(\La))$
define a cylinder set
$$
C(T)=\{\ga\in\Ga(\X)\;|\; \ga_{\La}=\ga \cap \La \in T\}.
$$
Such sets form a $\sigma$-algebra $\B_{\La}(\Ga(\X))$ of cylinder sets
for the finite volume $\La$.  The set of bounded functions on $\Ga(\X)$ measurable
w.r.t. $\B_{\La}(\Ga(\X))$  we denote $B_{\La}(\Ga(\X))$. That is a set of cylinder functions
on $\Ga(\X)$.  As a generating family for this set we can use the functions of the form
$$
F(\ga)= \psi(<f_1,\ga>,\dots, <f_n,\ga>),\; \ga\in\Ga(\X),  f_j\in C_0(\La), \psi\in C_b(\R^n).
$$

For so-called one-particle functions $f:\X\to\R, f\in\D(\X)$ consider
$$
(gf)(x)= f(g(x) x), x\in \X.
$$
 Then $gf\in \D(\X)$. Thus,
 we have the group action
 $$
 \D(\X)\in f \mapsto gf\in \D(\X),\;\;g\in\Aff
 $$
 of the infinite dimensional group $\Aff$ in the space of functions
 $\D(\X)$.

Note that due to our definition, we have
$$
<f, g\ga> = <gf,\ga>
$$
and it is reasonable to define for cylinder functions (\ref{cyl}) the action of the group $\Aff$
as
$$
(V_g F)(\ga)= \psi(<gf_1,\ga>,\dots <gf_n,\ga>.
$$
Obviously $V_g: \CF_b (\Ga(\X))\to \CF_b(\Ga(\X))$.

Denote $m(dx)$ the Haar measure on $\X$. The dual transformation to one-particle motion is defined
via the following relation
$$
\int_{\X} f(g(x)x) m(dx)=\int_{\X} f(x) g^\ast m(dx)
$$
if exists such measure $g^\ast m$ on $\X$.

\begin{Lemma}
\label{gm}

For each $g\in \Aff$
$$
g^\ast m(dx)=  \rho_{g}(x)  m(dx)
$$
where $\rho_g  = 1_{B_R^c(0) } + r_g^0,\;\; r_g^0\in \D(\X,\R_+).$
Here as above
$$
B_R^c(0)= \{x\in\X\;|\; |x|_p \geq R\}.
$$

\end{Lemma}

\begin{proof}
We have following representations for coefficients of $g(x)$:

$$
b(x)= \sum_{k=1}^{n} b_k 1_{B_k}(x) ,
$$
$$
a(x)= \sum_{k=1}^{n} a_k 1_{B_k}(x) + 1_{B^c_R(0)}(x)
$$
where $B_k$ are certain balls in $\X$.
Then
$$
\int_{\X} f(g(x)x) m(dx)= \sum_{k=1}^n \int_{B_k} f(\frac{x+b_k}{a_k}) m(dx) + \int_{B^c_R (0)} f(x) m(dx) =
$$
$$
\sum_{k=1}^{n} \int_{C_k} f(y) |a_k|_p m(dy) + \int_{B^c_R(0)} f(y) m(dy),
$$
where
$$
C_k= a_k^{-1}(B_k + b_k).
$$
Therefore,
$$g^\ast m= (\sum_{k=1}^n  |a_k|_p 1_{C_k} + 1_{B^c_R(0)}) m.
$$
Note that informally we can write
$$
(g^\ast m)(dx) = dm(g^{-1}x).
$$
\end{proof}

Note that by the duality we have the group action on the Lebesgue  measure. Namely,
for $f\in \D(\X)$ and $g_1, g_2\in \Aff$
$$
\int_{\X} (g_2 g_1) f(x)  m(dx)= \int_{\X} g_1 f (x)  (g_2^\ast m) (dx) =
$$
$$
\int_{\X} f(x) (g_1^\ast  g_2^\ast m)(dx)= \int_{\X} f(x) ((g_2 g_1)^\ast m)(dx).
$$
In particular
$$
(g^{-1})^\ast (g^\ast m)= m.
$$

\begin{Lemma} Let $F\in B_\La (\Ga(\X))$ and $g\in\Aff $ has the form
$g(x)=(1, h1_{B}(x))$ with certain $h\in \X$ and $B\in \mathcal{O}_b(\X)$ s.t. $\La\subset B$.
Then
$$
V_gF\in B_{\La -h} (\Ga(\X)).
$$

\end{Lemma}
\begin{proof}
Due to the formula for the action $V_gF$ we need to analyze the support
of functions $f_j (x+h1_B(x))$ for $\supp f_\subset \La$. If $x\in B^c$ then
$x\in \La^c$ and therefore $f_j (x+h1_B(x))=f_j(x)=0$. For $x\in B$
we have $f_j(x+h)$ and only for $x+h\in \La$ this value may be nonzero,
i.e., $\supp g f_j \subset \La- h$.

\end{proof}

Denote $\pi_m$ the Poisson measure on $\Ga(\X)$ with the intensity measure $m$.

\begin{Lemma}
\label{V}
For all $F \in \PC$ or $F\in \CF_b (\Ga(\X))$ and $g\in \Aff $ holds
$$
\int_{\Ga(\X)} V_g F d\pi_m = \int_{\Ga(\X)} Fd\pi_{g^\ast m} .
$$

\end{Lemma}

\begin{proof}
It is enough to show this equality for exponential functions
$$
F(\ga)= e^{<f,\ga>},\;\; f\in\D(\X).
$$

We have
$$
\int_{\Ga(\X)} V_g F d\pi_m = \int_{\Ga(\X)} e^{<gf, \ga>} d\pi_m(\ga)=
$$
$$
\exp[ \int_{\X} (e^{gf(x)} -1) dm(x)] = \exp[ \int_{\X} (e^{f(x)} -1) d(g^{\ast} m)(x)=
$$
$$
\int_{\Ga(\X)} F d\pi_{g^\ast m }.
$$

\end{proof}

\begin{Remark} For all functions $F,G\in \CF(\Ga(\X))$ a similar
calculation shows
$$
\int_{\Ga(\X)} V_g F  \; Gd\pi_m = \int_{\Ga(\X)} F  \; V_{g^{-1}} G d\pi_{g^\ast m} .
$$
\end{Remark}
Let $\pi_m$ be the Poisson measure on $\Ga(\X)$ with the intensity
measure $m$. For any $\La\in \mathcal{O}_b(\X)$ consider the distribution $\pi_m^\La$
of $\pi_m$ in $\Ga(\La)$ corresponding the projection $\ga\to \ga_\La$.
It is again a Poisson measure $\pi_{m_\La}$ in $\Ga(\La)$ with the intensity
$m_\La$ which is the restriction of $m$ on $\La$.  Infinite divisibility of
$\pi_m$ gives for $F_j\in B_{\La_j}(\Ga(\X)), j=1,2$ with $\La_1\cap \La_2=\emptyset$
$$
\int_{\Ga(\X)}  F_1(\ga) F_2(\ga) d\pi_m(\ga)= \int_{\Ga(\X)}  F_1(\ga) d\pi_m(\ga)
\int_{\Ga(\X)}  F_2(\ga) d\pi_m(\ga)=
$$
$$
\int_{\Ga(\La_1)} F_1 d\pi^{\La_1}_m \int_{\Ga(\La_2)} F_2 d\pi^{\La_2}_m.
$$

\begin{Lemma}

For any $F\in B_\La(\Ga(\X)$ and $g=(1, h1_B)\in \Aff $ with $\La \cap (B+h)=\emptyset$ holds
$$
\int_{\Ga(\X)} (V_g F)(\ga) d\pi_m(\ga)= \int_{\Ga(\X)} F(\ga)d\pi_m(\ga).
$$

\end{Lemma}

\begin{proof}
Due to our calculations above we have
$$
\int_{\Ga(\X)} (V_gF)(\ga) d\pi_m(\ga)= \int_{\Ga(\X)} F(\ga) d\pi_{g^{\ast}m}(\ga)=
$$
$$
\int_{\Ga(\La)} F(\eta) d\pi^{\La}_{g^{\ast}m} (\eta) =\int_{\Ga(\La)} F(\eta) d\pi_{ (g^{\ast}m)_\La} (\eta).
$$
But we have shown
$$
(g^{\ast}m)(dx)= (1+ 1_{B+h}(x)) m(dx) = m(dx)
$$
for $x\in \La$, i.e.,  $(g^{\ast}m)_\La =m$.

\end{proof}

\begin{Lemma}
\label{prod}
For any $F_1,F_2 \in \CF_b(\Ga(\X))$ there exists $g\in\Aff$ such that
$$
\int_{\Ga(\X)} F_1 \; V_g F_2  d\pi_m = \int_{\Ga(\X)} F_1 d\pi_m  \int_{\Ga(\X)} F_2 d\pi_m .
$$

\end{Lemma}

\begin{proof}
By the definition, $F_j\in B_{\La_j}(\Ga(\X)), j=1,2$ for some $\La_1,\La_2 \in \mathcal{O} (\X)$.

 Let us take $g=(1, h1_B)$ with the following assumptions:
 $$
 \La_2\subset B,\;\; \La_1\cap (\La_2-h) =\emptyset,\;\; \Lambda_2\cap (B+h) =\emptyset.
 $$
 Then accordingly to previous lemmas
$$
\int_{\Ga(\X)} F_1 V_g F_2 d\pi_m = \int_{\Ga(\X)} F_1 d\pi_m  \int_{\Ga(\X)} F_2 d\pi_m .
$$

\end{proof}

\section{$\Aff$ and Poisson measures}

For $F\in \PC $  or $F\in \CF_b (\Ga(\X))$, we consider the motion of $F$ by $g\in \Aff$ given by
the operator $V_g$.
Operators $V_g$   have the group property
defined point-wisely: for any $\ga \in \Ga(\X) $

$$
(V_h (V_gF))(\ga)= (V_{hg} F) (\ga).
$$
This equality is the consequence of  our definition of the group action of $\Aff$
on cylinder functions.

As above,
consider  $\pi_m$, the Poisson measure on $\Ga(\X)$ with the intensity measure $m$. For the transformation
$V_g$ the dual object is defined as the measure $V^\ast_g \pi_m$ on $\Ga(\X)$ given by the relation
$$
\int_{\Ga(\X)} (V_gF) (\ga) d\pi_m(\ga) =\int_{\Ga(\X)} F(\ga)  d(V^\ast_g \pi_m)(\ga),
$$
where $V^\ast_g \pi_m= \pi_{g^\ast m}$, see Lemma \ref{V}.

\begin{Corollary}
For any $g\in \Aff$ the  Poisson measure $V_g^\ast \pi_m$ is absolutely continuous
 w.r.t. $\pi_m$  with the Radon-Nykodim derivative
$$
R(g,\ga)= \frac{d\pi_{g^\ast m}(\ga)}{d\pi_{ m} (\ga)} \in L^1(\pi_m).
$$.

\end{Corollary}

\begin{proof}
Note that density $\rho_g  = 1_{B_R^c(0) } + r_g^0,\;\; r_g^0\in \D(\X,\R_+)$ of $g^\ast m$ w.r.t. $m$
may be equal zero on some part of $\X$ and, therefore, the equivalence of of considered
Poisson measures is absent. Due to \cite{LS03}, the Radon-Nykodim derivative
$$
R(g,\ga)= \frac{d\pi_{g^\ast m}(\ga)}{d\pi_{ m} (\ga)}
$$
exists if
$$
\int_{\X} |\rho_g(x)-1| m(dx)= \int_{B_R(0)} |1-r_g^0 (x)| m(dx) <\infty.
$$
\end{proof}

\begin{Remark}
As in the proof of Proposition 2.2 from \cite{AKR} we have an explicit formula for $R(g,\ga)$:

$$
R(g,\ga)= \prod_{x\in\ga} \rho_g (x) \exp(\int_{\X} (1-\rho_g(x)) m(dx).
$$
The point-wise existence of this expression is obvious.

\end{Remark}

This fact gives us the possibility to apply the Vershik-Gelfand-Graev approach realized by these authors for the case
of diffeomorphism group.

Namely, for $F\in \PC$ or $F\in \PC(\Ga(\X)$ and $g\in \Aff$ introduce operators
$$
(U_g F)(\ga) = (R(g^{-1} ,\ga) )^{1/2} (V_gF)(\ga).
$$

\begin{Theorem}

Operators   $U_g,\; g\in \Aff$ are unitary in $L^2 (\Ga(\X), \pi_m)$ and give an irreducible representation
of $\Aff$.

\end{Theorem}

\begin{proof}
Let us check the isometry property  of these operators.
We have using Lemmas \ref{V}, \ref{gm}
$$
\int_{\Ga(\X)} |U_g|^2 d\pi_m = \int_{\Ga(\X)} |V_g F|^2(\ga) d\pi_{(g^{-1})^\ast m} (\ga)=
$$
$$
\int_{\Ga(\X)} |F(\ga)|^2 d\pi_{(gg^{-1})\ast m}(\ga)= \int_{\Ga(\X)} |F(\ga)|^2 d\pi_{ m}(\ga).
$$
From Lemma \ref{V} follows that $U_g^\ast = U_{g^{-1}}.$

We need only to check irreducibility that shall
follow from the ergodicity of Poisson measures \cite{VGG75}. But to this end we need first of all to define the action of
 the group $\Aff$ on sets from $\B(\Ga(\X)$.  As we pointed out above, we can not define this
 action point-wisely. But we can define the action of     operators $V_g$ on the indicators $1_A(\ga)$ for
 $A\in \B(\Ga(Q))$. Namely, for given $A$ we take a sequence of cylinder sets $A_n, n\in \N$ such that
 $$
 \pi_{m}(A\Delta A_n) \to 0, n\to \infty.
 $$
 Then
 $$
 U_g 1_{A_n} =V_g 1_{A_n} (R(g^{-1} ,\cdot) )^{1/2}  \to G (R(g^{-1} ,\cdot) )^{1/2}  \in L^2(\pi_m), n\to\infty
 $$
 in $L^2(\pi_m)$. Each $V_g 1_{A_n} $ is an indicator of a cylinder set and
 $$
 V_g 1_{A_n}  \to G \;\; \pi_m - a.s., n\to \infty.
 $$
 Therefore,
 $G=1$ or $G=0$ $\pi_m$-a.s. We denote this function $V_g 1_A$.

 For the proof of the ergodicity of the measure $\pi_m$ w.r.t. $\Aff$ we need to show the following fact:
 for any $A\in \B(\Ga(\X))$ such that $\forall g\in\Aff\;\; V_g 1_A = 1_A\; \pi_m- a.s.$ holds $\pi_m(A)= 0$
 or $\pi_m(A)= 1$.

 Fist of all, we will show that for any pair of sets $A_1, A_2 \in \B(\Ga(Q))$ with $\pi_m(A_1)>0,\;\;
 \pi_m(A_2) >0$ there exists $g\in\Aff$ such that
 \begin{equation}
 \label{ineq}
 \int_{\Ga(\X)} 1_{A_1} V_g 1_{A_2} d\pi_m \geq \frac{1}{2} \pi_m(A_1) \pi_m(A_2).
 \end{equation}
 Because any Borel set may be approximated by cylinder sets, it is enough to show this fact
 for cylinder sets. But for such sets due to Lemma \ref{prod}  we can choose $g\in \Aff$ such that
$$
 \int_{\Ga(\X)} 1_{A_1} V_g 1_{A_2} d\pi_m =  \pi_m(A_1) \pi_m(A_2).
 $$
Then using an approximation we will have (\ref{ineq}).

 To finish the proof of the ergodicity, we consider any $A\in\B(\Ga(\X)$  such that
 $$
 \forall g\in \Aff\; V_g1_A = 1_A \;\;\pi_m - a.s.,\;\; \pi_m(A)>0.
 $$
 We will show that then $\pi_m(A)= 1$.  Assume $\pi_m(\Ga\setminus A) >0$.
 Due to the statement above, there exists $g\in \Aff$ such that
 $$
 \int_{\Ga(\X)} 1_{\Ga\setminus A} V_g 1_A >0.
 $$
 But due to the invariance of $1_A$  it means
 $$
 \int_{\Ga(\X)} 1_{\Ga\setminus A} 1_A d\pi_m >0
 $$
 that is impossible.
\end{proof}


TITLE: How find this minimum of the $q$, if such $\frac{95}{36}>\frac{p}{q}>\frac{96}{37}$
QUESTION [2 upvotes]: let $p,q$ is postive integer,and such
$$\dfrac{95}{36}>\dfrac{p}{q}>\dfrac{96}{37}$$
Find the minimum of the $q$
maybe can use
$$95q>36p$$
and $$37p>96q$$
and then find this minimum of the value?
before I find a
$$2.638\approx \dfrac{95}{36}>\dfrac{49}{18}\approx 2.722>\dfrac{96}{37}\approx 2.59 $$ is not such condition
idea 2: since
$$\dfrac{95}{36}=\dfrac{95\cdot 37}{36\cdot 37}=\dfrac{3515}{1332}$$
$$\dfrac{96}{37}=\dfrac{96\cdot 36}{36\cdot 37}=\dfrac{3456}{1332}$$
so
$$\dfrac{3515}{1332}>\dfrac{p}{q}>\dfrac{3456}{1332}$$
so
$$p\in(3456,3515),q=1332$$

REPLY [6 votes]: An interesting trick so solve such kind of problems is to consider the continued fraction of the LHS and the RHS. We have:
$$\frac{95}{36}=[2;1,1,1,3,3],\qquad \frac{96}{37}=[2;1,1,2,7]$$
hence
$$\frac{13}{5}=[2;1,1,2]$$
just lies between the LHS and the RHS, and it is the rational number with the smallest denominator lying in that interval.


text:
\subsection{The mixed eigenvalue problems in dimension 2:}
 For both the annular regions $\Om^\#$ and $\Om_\#,$ we denote the lengths of the interior parallels by $\overline{S}(\de)$.

\noi{\bf Proof of Theorem \ref{thm 3}.}\\
$(i)$ In this case, we consider the interior parallels from $\Ga_0.$ Thus we have $\overline{S}(\de)=|\Ga_0|-2\pi\de$. Further, we define
\[ \overline{V}(\de)=\int_0^\de \overline{S}(t) \dt,\, \de\in[0,R_1-R_0];\quad \overline{H}(\al)=\overline{S}\big(\overline{V}^{-1}(\al)\big),\, \al\in [0,|\Om|],\]
 As before, we obtain $ \overline{S}(\de)^2=|\Ga_0|^2-4\pi\overline{V}(\de),\, \de\in [0,R_1-R_0]$ and this yields
\[\overline{H}(\al)^2=|\Ga_0|^2-4\pi\al,\, \al\in [0,|\Om|].\]
From  Nagy's inequality, we have $s(\de)\le \overline{S}(\de)$ and this gives the following isoperimetric inequality
\[s(\de)^2\leq |\Ga_0|^2-4\pi v(\de), \, \de\in [0, \de_\Om].\] Therefore, $h(\al)^2\leq \overline{H}(\al)^2,\, \al \in [0,|\Om|].$  Now the proof follows using a similar set of arguments as in the second proof of part $(i)$ of Theorem \ref{thm 1}.\\
$(ii)$ For this case, we consider the interior parallels from $\Ga_1.$ Thus we have $\overline{S}(\de)=|\Ga_1|+2\pi\de, \, \de\in (0,\de_\Om)$ and Nagy's inequality gives $s(\de)\le \overline{S}(\de).$ Now define a parametrization as
\[\overline{T}(\de):=\int_0^\de \frac{\dt}{\overline{S}(t)^{\pr p -1}}, \, \de\in[0,\de_\Om].\]
Let $\overline{G}(\al)=\overline{S}\big(\overline{T}^{-1}(\al)\big),\, \al\in [0,T_\#].$ Now from $(ii)$ of Lemma \ref{Inner1}, we get $g(\al)\leq \overline{G}(\al),\, \al\in [0,T_\#].$ Now the rest of the proof is same as the proof of part $(i)$ of Theorem \ref{thm 2}.

\qed


TITLE: "Standard reference" for $C_c^\infty(\mathbb R)$ is dense in $C_c(\mathbb R)$
QUESTION [3 upvotes]: $C_c^\infty(\mathbb R)$ is dense in $C_c(\mathbb R)$. This can be shown by mollification. This is a well-known, widely used fact. However, I wasn't able to find any book which I could point in a reference to. Is there any kind of "standard reference" with a readable proof?

REPLY [0 votes]: I don't have a reference at hand. But one can prove this without too much trouble using the Weierstrass approximation theorem.
Suppose $f\in C_c$ with support contained in $[a,b].$ Let $\epsilon>0.$ Choose $a'<a$ and $b'>b.$  Then there exists a polynomial $p$ such that $|p-f|<\epsilon$ on  $[a',b'].$
Now there exists $g\in C^\infty_c(\mathbb R)$ with support in $[a',b']$ such that $0\le g\le 1$ everywhere, and $g=1$ on $[a,b].$ We then have $gp\in C^\infty_c(\mathbb R),$ and $|gp -f|<\epsilon$ everywhere. I'll leave the vefication of the last line to the reader; ask questions if you like.


text:
\section{Bentkus' Confidence Sequences}\label{sec:unif-conf-seq}
For any random variable $Y_i$ with mean $\mu$, $X_i = Y_i - \mu$ is mean zero and hence we will mostly restrict to the case of mean zero random variables. The result for general $\mu$ will readily follow; see Theorem~\ref{thm:empirical-Bentkus-arbitrary-mean}. We first discuss Bentkus' concentration inequality for bounded mean zero random variables. Afterwards, we present a refined confidence sequence through stitching. This confidence sequence is not readily actionable because it depends on the true variance of random variables. To address this, we present a practical version where we replace the true variance by an estimated upper bound. This provides an analog of the empirical Bernstein confidence sequence, and we call our method \emph{Empirical Bentkus Confidence Sequence}.

\paragraph{Assumptions.} Suppose $X_1, X_2, \ldots$ are independent random variables satisfying
\begin{equation}\label{eq:boundedness-conditions}
\mathbb{E}[X_i] = 0,\;\mbox{Var}(X_i) \le A^2_i,\;\mbox{and}\; \mathbb{P}(X_i > B) = 0,
\end{equation}
for all $i\ge1$.
We will first derive concentration inequalities under the one-sided bound assumption as in~\eqref{eq:boundedness-conditions} which only requires $X_i \le B$ almost surely.
To derive actionable versions of the concentration inequalities (with estimated variance), we will impose a two-sided bound assumption.

\subsection{Bentkus' Concentration Inequality for a fixed Sample Size}
We now present a near-optimal concentration inequality for $S_t = \sum_{i=1}^t X_i$ that holds uniformly over all sample sizes $t\le n$.
The main idea behind the optimality is to replace the exponential function used in the Cram{\'e}r-Chernoff technique with a slowly growing function.
Fix $\alpha \in [0, \infty]$, and set $(a)_+ = \max\{a, 0\}$. It is easy to verify that for all $\nu \in\mathbb{R}$,

\begin{equation}\label{eq:inequality_pinelis}\textstyle
\one\{\nu \geq 0\} ~\leq~ (1 + {\nu}/{\alpha})^{\alpha}_+ ~\le~ e^{\nu}.
\end{equation}

Taking $\nu = \lambda(S_n - u)$ for some $\lambda > 0$ in inequality~\eqref{eq:inequality_pinelis} and applying expectation, we obtain for all $u \in\mathbb{R}$,
\begin{equation}\label{eq:pinelis-implication}\textstyle
    \P(S_n \ge u)
    \leq \inf_{\lambda \geq 0} \E \left[ ( 1 + {\lambda(S_n - u)}/{\alpha})^{\alpha}_{+} \right].
\end{equation}
The second inequality in~\eqref{eq:inequality_pinelis} readily shows that~\eqref{eq:pinelis-implication} is better than the Cram{\'e}r-Chernoff bound.
Reparameterizing $\lambda = {\alpha}/({u - x})$ with $x \leq u$ in~\eqref{eq:pinelis-implication}, we obtain
\begin{equation}\label{eq:bentkus_prob_bound}
    \P(S_n \ge u)
    \leq \inf_{x \leq u} \frac{\E[(S_n - x)^\alpha_{+}]}{(u - x)^\alpha_+}, \quad \forall u \in \R.
\end{equation}
Next, we bound $\E[(S_n - x)^\alpha_{+}]$ for all random variables $X_i$'s satisfying~\eqref{eq:boundedness-conditions}. This should be done optimally in order to obtain a near-optimal concentration inequality. Surprisingly, for all $\alpha \ge 2$, $\E[(S_n - x)^\alpha_{+}]$ can be bounded in terms of a ``worst case'' two-point distribution satisfying~\eqref{eq:boundedness-conditions}.

Define independent random variables $G_i, i\ge 1$ as
\begin{equation}\label{eq:G_distribution}
\begin{split}
    \mathbb{P}\left(G_i = -A_i^2/B\right) ~&=~ {B^2}/{(A^2_i + B^2)},\\
    \mathbb{P}\left(G_i = B\right) ~&=~ {A^2_i}/{(A^2_i + B^2)}.
\end{split}
\end{equation}
These random variables satisfy~\eqref{eq:boundedness-conditions} and $G_i$'s are the worst case random variables

satisfying~\eqref{eq:boundedness-conditions}, in the sense that for all $n\ge1, \alpha \ge 2,$ and $x\in\mathbb{R}$,
\begin{equation}\label{eq:intermediate-optimality}

    \textstyle \mathbb{E}[\left(\sum_{i=1}^n G_i - x\right)_+^\alpha] = \displaystyle \sup_{X_i\sim\eqref{eq:boundedness-conditions}}
    \textstyle \,\mathbb{E}[\left(\sum_{i=1}^n X_i - x\right)_+^\alpha],
\end{equation}
where the supremum is over all distributions of $X_i$'s satisfying~\eqref{eq:boundedness-conditions}.
We refer the readers to~\citet[Eq. (11)]{bentkus2002remark} and~\citet[Theorem 2.1]{pinelis2006binomial} for the proof of~\eqref{eq:intermediate-optimality}. The definition of the ``worst-case'' distribution of $G_i$'s follows from finding the best quadratic function that upper bounds $t\mapsto(t - x)_+^{\alpha}$; see, e.g.,~\citet[Lemma 8]{burgess2019engineered}. \citet{pinelis2006binomial} proves that~\eqref{eq:intermediate-optimality} holds true when $t\mapsto(t - x)_+^{\alpha}$ is replaced with any function $t\mapsto f(t)$ that has a convex first derivative.

Inequality~\eqref{eq:bentkus_prob_bound} with $\alpha = 2$ and \eqref{eq:intermediate-optimality} show that\footnote{

The function $\alpha\mapsto(1 + \nu / \alpha)^\alpha_+$ increases as $\alpha$ increases,
so using the smallest possible $\alpha$ leads to the best bound. Because
\eqref{eq:intermediate-optimality} only holds for $\alpha \geq 2$,
$\alpha = 2$ is optimal in this context.
}
\begin{equation}\label{eq:bentkus_goal}
    \P(S_n \ge u) \leq \inf_{x \leq u} \frac{\E[(\sum_{i=1}^n G_n - x)^2_{+}]}{(u - x)^2_+},
\end{equation}
and we find $u$ such that the right hand side of \eqref{eq:bentkus_goal} is upper bounded by $\delta$.
Set $\mathcal{A} = \{A_1, A_2, \ldots\}$ as the collection of standard deviations and for $n\ge1$, define
\begin{equation}\label{eq:definition-P2-tilde}
\tilde{P}_{2,n}(u) ~:=~ \inf_{x \le u}\,\frac{\mathbb{E}[(\sum_{i=1}^n G_i - x)_+^2]}{(u - x)_+^2}.
\end{equation}
For $\delta\in[0,1]$, define $q(\delta; n, \mathcal{A}, B)$ as the solution to the equation $\tilde{P}_{2,n}(u) = \delta.$ In other words,
\begin{equation}\label{eq:quantile-A-B-2nd-version}
q(\delta; n, \mathcal{A}, B) = \tilde{P}_{2,n}^{-1}(\delta)
\end{equation}

The inverse exists uniquely for $\delta \ge \mathbb{P}(\sum_{i=1}^n G_i = nB)$ and is defined to be $nB+1$ if $\delta < \mathbb{P}(\sum_{i=1}^n G_i = nB)$.

The following result provides a refined concentration inequality for $S_n = \sum_{i=1}^n X_i$.

It is a ``maximal'' version of Theorem 2.1 of~\citet{bentkus2006domination}, see Appendix~\ref{appsec:proof-of-theorem-initial-maximal-ineq} for the proof.

\begin{thm}\label{thm:initial-maximal-ineq}
Fix $n\ge1$. If $X_1, X_2, \ldots, X_n$ are independent random variables satisfying~\eqref{eq:boundedness-conditions}, then

\begin{equation}\label{eq:maximal-inequality}
\mathbb{P}\left(\max_{1 \le t \le n}\,S_t \ge q(\delta; n, \mathcal{A}, B)\right) ~\le~ \delta,\;\forall \delta\in[0, 1].
\end{equation}
Further, if $A_1 = \cdots = A_n = A$ and if $\tilde{q}(\cdot; A, B)$ is a function such that $\mathbb{P}(\max_{1\le t\le n}\,S_t \ge n\tilde{q}(\delta^{1/n}; A, B)) \le \delta$ for all $\delta\in[0, 1]$

then $q(\delta; n, \mathcal{A}, B) \le n\tilde{q}(\delta^{1/n}; A, B)$.
\end{thm}

\emph{Remark.} The first part of Theorem~\ref{thm:initial-maximal-ineq} provides a finite sample valid estimate of the quantile. The second part implies that it is sharper than classical concentration inequalities such as Hoeffding, Bernstein, Bennett or Prokhorov inequalities. To see this fact, note that $\mathbb{P}(\max_{1\le t\le n}\,S_t \ge n\tilde{q}(\delta^{1/n}; A, B)) \le \delta$ for all $\delta \in[0, 1]$ is equivalent to the existence of a function $H(u; A, B)$ such that $\mathbb{P}(\max_{1\le k\le n}\, S_t \ge nu) \le H^n(u; A, B)$ for all $u$. The classical concentration inequalities mentioned above are all of this product from $H^n(u; A, B)$ for some $H$, hence weaker than our bound.

\subsection{Comparison to Classical bounds}
\begin{figure}[t]
    \centering
    \includegraphics[width=.55\textwidth]{pointwise_bernoulli_n2500.pdf}

    \caption{
        Comparison of the concentration bounds when $\delta=0.05$.
        $X_i$ are centered i.i.d. $\Bern{\frac14}$. We give the true standard deviation
        $A_i = \frac{\sqrt{3}}{4}$ and upper bound $B = \frac34$ to all the methods.
        The average failure frequencies across 300
        trials and $1 \leq n\le 3000$ are: Hoeffding $0.00205 \pm 0.00261$, Bernstein
        $0.00593 \pm 0.0044$, Bentkus $0.01411 \pm 0.00769$. The Bentkus’ bound is the least conservative.
    }
     \label{fig:Bernoulli-1/4}
\end{figure}
Most of the classical concentration inequalities including Hoeffding, Bernstein, Bennett, or Prokhorov inequalities~\cite{bentkus2002remark,wellner2017bennett} are derived based on the Cram{\'e}r--Chernoff technique. The Cram{\'e}r--Chernoff technique makes use of exponential moments unlike the positive part second moment used in Bentkus' concentration inequality. We have mentioned in~\eqref{eq:intermediate-optimality} that random variables $G_i$'s defined in~\eqref{eq:G_distribution} is worst case for the positive part second moment. Interestingly, the same random variables are also worst case for exponential moments too, i.e., for all $\lambda \ge 0$,
\[
   \textstyle \mathbb{E}\left[\exp\left(\lambda\sum_{i=1}^n G_i\right)\right]
=  \displaystyle \sup_{X_i\sim\eqref{eq:boundedness-conditions}}
   \textstyle\mathbb{E}\left[\exp\left(\lambda\sum_{i=1}^n X_i\right)\right].
\]
See~\citet[Page 42]{bennett1962probability} for a proof. Hence, the optimal Cram{\'e}r--Chernoff concentration inequality is given by
\begin{equation}\label{eq:optimal-cramer}
\textstyle\mathbb{P}(\sum_{i=1}^n X_i \ge u) \le \displaystyle\inf_{\lambda \ge 0}
\frac{\mathbb{E}\left[\exp(\lambda\sum_{i=1}^n G_i)\right]}{\exp(\lambda u)}.
\end{equation}
Furthermore, it can be proved that for all $u\in\mathbb{R}$,

\begin{equation}\label{eq:comparison-Bentkus-Cramer}

\tilde{P}_{2,n}(u) \le \inf_{\lambda \ge 0}\frac{\mathbb{E}\left[\exp(\lambda\sum_{i=1}^n G_i)\right]}{\exp(\lambda u)},
\end{equation}
see Eqns~\eqref{eq:inequality_pinelis}--\eqref{eq:pinelis-implication},~\eqref{eq:definition-P2-tilde}. This implies that Bentkus' concentration inequality is sharper than the optimal Cram{\'e}r--Chernoff inequality, and hence sharper than Hoeffding, Bernstein, Bennett, and Prokhorov inequalities.
Inequality~\eqref{eq:comparison-Bentkus-Cramer} only proves that Bentkus' inequality is an improvement but does not show how significant the improvement is. In order to describe the improvement, let us denote the right hand side of~\eqref{eq:comparison-Bentkus-Cramer} as $\tilde{P}_{\infty,n}(u)$. It can be proved that
\begin{equation}\label{eq:ratio-unbounded}
1~\le~ \lim_{n\to\infty}\sup_{u\in\mathbb{R}}\,\frac{\tilde{P}_{\infty,n}(u)}{\mathbb{P}(\sum_{i=1}^n G_i \ge u)} ~=~ \infty.
\end{equation}
See~\citet[Eq. (1.4)]{talagrand1995missing}. Moreover,\footnote{Because $G_i$'s satisfy assumption~\eqref{eq:boundedness-conditions}, inequality $(i)$ is trivial using~\eqref{eq:bentkus_goal}.
Inequality $(ii)$ holds for all $u$ in the support of $\sum_{i=1}^n G_i$; it holds for all $u\in\mathbb{R}$ if $\mathbb{P}(\sum_{i=1}^n G_i \ge u)$ is replaced by its log-linear interpolation; see~\citet{bentkus2002remark} for details. }

\begin{equation}\label{eq:main-optimality}

\hspace{-0.5pt}
\mathbb{P}\big(\sum_{i=1}^n G_i \ge u\big) \stackrel{(i)}{\le}\tilde{P}_{2,n}(u) \stackrel{(ii)}{\le}
\frac{e^2}{2} \mathbb{P}\big(\sum_{i=1}^n G_i \ge u\big).

\end{equation}
Inequalities in~\eqref{eq:main-optimality} show that our concentration inequalities based on the two-point random variables $G_i$ are sharp up to a constant factor $e^2/2$. Further, inequalities \eqref{eq:ratio-unbounded} and \eqref{eq:main-optimality} show that there exists a distribution for which Bentkus' inequality can be infinitely better than the optimal Cram{\'e}r--Chernoff bound.
See Figure~\ref{fig:Bernoulli-1/4} for an illustration and~\citet{bentkus2002remark,bentkus2004hoeffding, pinelis2006binomial} for further discussion.

\subsection{Computation of Bentkus' bound}
\begin{figure}[t]
    \centering
    \includegraphics[width=0.7\textwidth]{function_P2_n3}
    \caption{Examples function $P_2(x; Z_n)$ when $n=3$, $A=0.1$ and
        $B=1.0$. We plot $P_2(x;Z_n)$ in both linear (left) and log (right) scales on the y-axis.}
    \label{fig:function_P2}
\end{figure}
Computation of $q(\cdot; n, \mathcal{A}, B)$ is discussed in~\citet[Section 9]{bentkus2006domination} and we provide a detailed discussion in Appendix~\ref{appsec:computation-of-q-function}. In this respect, the following result describes the function in~\eqref{eq:definition-P2-tilde} as a piecewise smooth function in homoscedastic case, i.e., $A_1 = \ldots = A_n = A$.
\begin{prop}\label{prop:computation-P_2}
Set $\pab = A^2/(A^2 + B^2)$ and $Z_n = \sum_{i=1}^nR_i$ where $R_i\sim\Bern{\pab}$. Then for $u\in\mathbb{R}$,
\begin{equation}
    \tilde{P}_{2,n}(u) ~=~ P_2\left(n\pab + u(1 - \pab)/B
    ;\, Z_n \right),
\end{equation}
where $P_2(x; Z_n) = 1$ for $x \le n\pab$ and

\begin{align*}
&P_2\left(x; Z_n\right) :=\\ &
\begin{dcases}

    \frac{n\pab(1 - \pab)}{(x - n\pab)^2 + n\pab(1 - \pab)}, &\mbox{if }n \pab < x \le \Psi_0,\\
    \frac{v_{k}p_{k} - e_{k}^2}{x^2p_{k} - 2xe_{k} + v_{k}}, &\mbox{if }\Psi_{k-1} < x \le \Psi_k,\\
    \mathbb{P}\left(Z_n = n\right) = \pab^n, &\mbox{if }x~\ge~ \Psi_{n-1} = n.
\end{dcases}
\end{align*}
Here $p_k = \mathbb{P}(Z_n \ge k), e_k = \mathbb{E}[Z_n\mathds{1}\{Z_n \ge k\}]$, $v_k = \mathbb{E}[Z_n^2\mathds{1}\{Z_n \ge k\}]$, and $\Psi_k = {(v_k - ke_k)}/{(e_{k} - kp_k)}$.
\end{prop}
The function $P_2(\cdot; Z_n)$ is illustrated in Figure~\ref{fig:function_P2} for $n = 3$ in both linear and logarithmic scale.

Using
Proposition~\ref{prop:computation-P_2} and~\eqref{eq:quantile-A-B-2nd-version}, computation of $q(\cdot; n, A, B)$ follows. In Appendix~\ref{subsec:computation-of-quantile}, we also provide a similar piecewise description of $q(\cdot; n, A, B)$. It is worth pointing out that a similar expression for $P_2(\cdot; Z_n)$ can be derived when $A_i$'s are unequal.
Proposition~\ref{prop:computation-P_2} is stated for equal variances for simplicity and also because of the widely used i.i.d. assumption.

\subsection{Adaptive Bentkus' Concentration Inequality with Known Variance}
\begin{figure}[t]
    \centering
    \includegraphics[width=.55\textwidth]{adaptive_bernoulli.pdf}
    \caption{
        Comparison of the uniform concentration bounds when $\delta=0.05$.
        $X_i$ are centered i.i.d. $\Bern{\frac14}$. True standard deviation
        $A_i = {\sqrt{3}}/{4}$ and upper bound $B = 3/4$ are provided to all the methods.
        A-Bentkus is computed using $\eta = 1.1$, $h(k) =(k+1)^{1.1}
        \zeta(1.1)$. For 3000 trials, there is zero failure for Adaptive Hoeffding
        and Empirical Bernstein, but $3$ for A-Bentkus~\eqref{eq:adaptive-Bentkus}.
        All the bounds have failure frequency bounded above by $\delta$ but
        the Bentkus' bound is the least conservative. The differences between the bounds continue to grow as $n$ increases.
    }
    \label{fig:Bernoulli-1/4-unif-n}
\end{figure}

Although Theorem~\ref{thm:initial-maximal-ineq} leads to a uniform in sample size confidence sequence until size $n$, it is very wide for sample sizes much smaller than $n$. We now use the method of stitching to obtain a confidence sequence that is valid for all sample sizes and scales reasonably well with respect to the sample size. See~\citet[Section 3.2]{mnih2008empirical} and~\citet[Section 3.1]{howard2018uniform} for other applications.
The stitching method requires two user-chosen parameters:
\begin{enumerate}[topsep=0pt]
  \item[-] a scalar $\eta > 1$ that determines the geometric spacing.
  \item[-] a function $h:\mathbb{R}_+\to\mathbb{R}_+$ such that $\sum_{k=0}^{\infty} {1}/{h(k)} \le 1$. Ideally, $1/h(k), k\ge0$ adds up to $1$.
\end{enumerate}
The following result
(proved in Appendix~\ref{appsec:proof-of-theorem-uniform-in-n})
gives a uniform over $n$ tail inequality by splitting $\{n\ge1\}$ into $\bigcup_{k\ge1}\{\lceil\eta^k\rceil \le n \le \lfloor\eta^{k+1}\rfloor\}$ and then applying~\eqref{eq:maximal-inequality} within $\{\lceil\eta^k\rceil \le n\le \lfloor\eta^{k+1}\rfloor\}$.
For each $n\ge1$, set $k_n := \min\{k\ge0:\,\lceil\eta^k\rceil \le n \le \lfloor\eta^{k+1}\rfloor\}$ and $c_n := \lfloor\eta^{k_n + 1}\rfloor$.
\begin{thm}\label{thm:uniform-in-n}
If $X_1, X_2, \ldots$ are independent random variables satisfying~\eqref{eq:boundedness-conditions}, then for any $\delta\in[0,1]$,
\begin{equation}\label{eq:adaptive-Bentkus}
\mathbb{P}\left(\exists\, n \ge 1:\,S_n\ge q\left(\frac{\delta}{h(k_n)}; c_n, \mathcal{A}, B\right)\right) \le \delta.
\end{equation}

\end{thm}

The choice of the spacing parameter $\eta$ and stitching function $h(\cdot)$ determine
the shape of the confidence sequence and there is no universally optimal setting. The
growth rate of $h(\cdot)$ determines how the budget of $\delta$ is spent over sample
sizes; a quickly growing $h(\cdot)$ such as $2^k$ yield confidence intervals of
essentially $100\%$ confidence for larger sample sizes. The choice of $\eta$ determines
how conservative the bound is for small $n$ in $\{\lceil\eta^k\rceil \le n\le
\lfloor\eta^{k+1}\rfloor\}$; for $\eta$ too large the bound will be conservative for $n$
close to $\eta^k$. Eq.~\eqref{eq:main-optimality} shows that bound is tightest at $n =
\lfloor\eta^{k+1}\rfloor$ in each epoch. See Appendix~\ref{appsec:hyperparam_stitch} for the graphical
illustration. Throughout this paper, we use
$\eta = 1.1$ and $h(k) = \zeta(1.1)(k+1)^{1.1}$ where $\zeta(\cdot)$ is the Riemann zeta function.

The same stitching method used in Theorem~\ref{thm:uniform-in-n} can also be used with Hoeffding and Bernstein inequalities as done in~\citet{zhao2016adaptive} and~\citet{audibert2009exploration}, respectively. However, given that inequality~\eqref{eq:maximal-inequality} is sharper than Hoeffding and Bernstein inequalities, our bound~\eqref{eq:adaptive-Bentkus} is sharper for the same spacing parameter $\eta$ and stitching function $h(\cdot)$; see Figure~\ref{fig:Bernoulli-1/4-unif-n}. Stitched bounds as in Theorem~\ref{thm:uniform-in-n} are always piecewise constant but the Hoeffding and Bernstein versions from~\citet{zhao2016adaptive} and~\citet{mnih2008empirical} are smooth because they are upper bounds of the piecewise constant boundaries (obtained using $n \le c_n \le \eta n$ and $k_n \le \log_{\eta} n + 1$). For practical use, smoothness is immaterial and the piecewise constant versions are sharper.

\subsection{Adaptive Bentkus Confidence Sequence with Estimated Variance}\label{sec:empirical-Bentkus}
Theorem~\ref{thm:uniform-in-n} is impractical in its form because it involves the unknown sequence of $A_1, A_2, \ldots$. In the case where $A_1 = A_2 = \cdots = A$, one needs to generate an upper bound of $A$ (for a known $B$) and obtain an actionable version of Theorem~\ref{thm:uniform-in-n}. Finite-sample over-estimation of $A$ requires a two-sided bound on the $X_i$'s; one-sided bounds on the random variables do not suffice. This actionable version is a refined version of empirical Bernstein inequality that is uniform over the sample sizes.

We will assume that $\mathbb{P}(\underline{B} \le X_i \le B) = 1,\,\forall\,i$. It follows that $\mbox{Var}(X_i) = A^2 \le -B\underline{B}$~\cite{bhatia2000better}. Because $X_i$'s have mean zero, $\underline{B} \le 0$ and $B \ge 0$; this implies that $-\underline{B}B \ge 0$. If one wants to avoid variance estimation, then one can use this upper bound in Theorem~\ref{thm:uniform-in-n} to obtain an actionable confidence sequence. This sequence, however, will not have width scaling with the true variance.

Define $\widebar{A}_1(\delta) = (B - \underline{B})/2$ and for $n\ge2, \delta\in[0, 1]$
\begin{equation}\label{eq:variance-over-estimation}
\begin{split}
\widehat{A}_n^2 &:= \textstyle\lfloor n/2\rfloor^{-1}\sum_{i=1}^{\lfloor n/2\rfloor} {(X_{2i} - X_{2i - 1})^2}/{2},\\
\widebar{A}_n(\delta) &:= \sqrt{\widehat{A}_n^2 + g_{2,n}^2(\delta)} + {g_{2,n}(\delta)},
\end{split}
\end{equation}
where $g_{2,n}(\delta) := (2\sqrt{2}n)^{-1}\sqrt{\lfloor c_n/2\rfloor}(B - \underline{B})\times\Phi^{-1}\left(1 - {2\delta}/{(e^2h(k_n))}\right)$, for the distribution function $\Phi(\cdot)$ of a standard normal random variable.
We will write $\widebar{A}_n(\delta; B, \underline{B})$, when needed, to stress the dependence of $\widebar{A}_n(\delta)$ on $B, \underline{B}$.
Lemma~\ref{lem:uniform-in-n-variance} shows that $\widebar{A}_n(\delta)$ is a valid over-estimate of $A$ uniformly over $n$ and yields the following actionable bound. We defer the proof to Appendix~\ref{appsec:proof-of-lemma-variance-estimation}.

\begin{thm}\label{thm:uniform-in-n-empirical-Bentkus}
If $X_1, X_2, \ldots$ are mean-zero independent random variables satisfying $\mathrm{Var}(X_i) = A^2$ and $\mathbb{P}(\underline{B} \le X_i \le B) = 1$ for all $i\ge1$, then for any $\delta_1, \delta_2\in[0, 1]$, with probability at least $1 - \delta_1 - \delta_2$, simultaneously for all $n\ge1$,
\[
S_n \le q\left(\frac{\delta_1}{h(k_n)}; c_n, \widebar{A}_n^*(\delta_2), B\right)
\mbox{ and } A \le \widebar{A}_n^*(\delta_2, B, \underline{B}).
\]
Similarly, with probability at least $1-\delta_1 - \delta_2$, simultaneously for all $n\ge1$,
\[
S_n \ge -q\left(\frac{\delta_1}{h(k_n)}; c_n, \widebar{A}_n^*(\delta_2), -\underline{B}\right)
\mbox{ and } A \le \widebar{A}_n^*(\delta_2, B, \underline{B}).
\]
Here $\widebar{A}_n^*(\delta_2) := \min_{1\le s\le n}\,\widebar{A}_n(\delta_2, B, \underline{B})$, and $k_n, c_n$ are those defined before Theorem~\ref{thm:uniform-in-n}.
\end{thm}
Theorem~\ref{thm:uniform-in-n-empirical-Bentkus} is an analogue of the empirical Bernstein inequality~\citet[Eq. (5)]{mnih2008empirical}. The over-estimate of $A$ in~\eqref{eq:variance-over-estimation} can be improved by using non-analytic expressions, but we present the version above for simplicity; see Appendix~\ref{appsec:proof-of-lemma-variance-estimation} for details on how to improve $\widebar{A}_n(\delta)$ in~\eqref{eq:variance-over-estimation}.

Theorem~\ref{thm:uniform-in-n-empirical-Bentkus} can be used to construct a confidence
sequence as follows. Suppose $Y_1, Y_2, \ldots$ are independent random variables with
mean $\mu$, variance $A^2$, and satisfying $\mathbb{P}(L \le Y_i \le U) = 1$.
Then $X_i = Y_i - \mu$ is a zero mean random variable where $\P(L - \mu \leq X_i \leq U
- \mu) = 1$, and Theorem~\ref{thm:uniform-in-n-empirical-Bentkus} is directly applicable
with $B = -\underline{B} = U - L$.  An interesting observation is that we can refine the values of $\underline{B}$ and $B$
while we are updating the confidence interval for $\mu$. Suppose

with $n$ data points, we have:
$-q_n^\low \leq n\Ybar_n - n \mu  \leq q_n^\up$,
then

\[\textstyle
    \mu^\low_n := \Ybar_n  - n^{-1}{q_n^\up}  ~\leq~  \mu  ~\leq~ \Ybar_n  +
    n^{-1}{q_n^\low} =: \mu_n^\up,
\]
where $\Ybar_n$ is the empirical mean of $Y$. We thus have a valid estimate $[L - \mu_n^{\up}, U - \mu_n^{\low}]$ of the support of $X$,

and when we observe $Y_{n+1}$, we can use
$U - \mu_n^\low$ as $B$ and $L - \mu_n^\up$ as $\underline{B}$.
Importantly, as Theorem~\ref{thm:uniform-in-n-empirical-Bentkus} provides
a uniform concentration bound,
these recursively defined upper and lower bounds hold simultaneously too. This
leads to the following result,
proved in Appendix~\ref{appsec:proof-empirical-bentkus-arbitrary-mean}.

\begin{thm}\label{thm:empirical-Bentkus-arbitrary-mean}
If random variables $Y_1, Y_2, \ldots$ are independent with mean $\mu$, variance $A^2$
and satisfy $\mathbb{P}(L \le Y_i \le U) = 1$.
Define $\mu_0^\up := U$, $\mu_0^\low := L$, and for $n \geq 1$
\begin{equation}
    \begin{aligned}
        \mu_n^\up &= \Ybar_n + \frac{1}{n} q \left(\frac{\delta_1}{2h(k_n)}; c_n, \widebar{A}^*_n(\delta_2, U , L ),\, \mu_{n-1}^\up-L \right) \\
        \mu_n^\low  &= \Ybar_n -\frac{1}{n} q\left(\frac{\delta_1}{2h(k_n)}; c_n, \widebar{A}^*_n(\delta_2, U, L),\,  U - \mu_{n-1}^\low  \right)
    \end{aligned}
\end{equation}
Let $\mu_n^{\up*} = \min_{0\leq i \leq n} \mu_i^\up$ and $\mu_n^{\low*} = \max_{0\leq i \leq n} \mu_i^\low$.
Then for any $\delta_1, \delta_2\in[0, 1]$, with probability at least $1 - \delta_1 - \delta_2$, simultaneously for all $n\ge1$,
\begin{equation}\label{eq:empirical-bentkus-conf-seq}
    \mu \in[\mu_n^{\low*}, \mu_n^{\up*} ]\quad \mbox{and} \quad A \le
        \widebar{A}_n^*(\delta_2, U, L).
\end{equation}
\end{thm}

Because $\mu_0^{\up} = U, \mu_0^{\low} = L$, the confidence intervals $[\mu_n^{\low*}, \mu_n^{\up*}]$ is always a subset of $[L, U]$.