text:
\section{Proof of Theorem~\ref{thm:private_rnd}}\label{app_thm:private_rnd}

\subsection{Proof of Lemma~\ref{lem_no_cr}}
	Consider a $(n, \epsilon, \delta)$-$\crepic$ scheme with encoder $\phi$ and decoder $\psi_i$ at user $i : i \in [N]$.
	We show the existence of $w^* \in \cW$ such that conditioned $W = w^*$, the decoding error is at most $2\epsilon$ and privacy leakage is at most $2N\delta$.
	Define the events $\mathsf{Bad}^{dec}$ and $\mathsf{Bad}^{priv}_i: i \in [N]$ as follows.
	\begin{align*}
		\mathsf{Bad}^{dec} & \defeq \left\{w \in \cW : \exists i \in [N] \text{ such that } \pr{\widehat{\xv}_i \neq \xv_i | W = w} > 2\epsilon\right\},\\
		\mathsf{Bad}^{priv}_i & \defeq \left\{w \in \cW : I \left( \mv ; \xv_{[N] \setminus \a_i} \middle | \kv_{\ak_i}, \xv_{\s_i}, W = w \right) > 2nN\delta\right\}.
	\end{align*}
	Since the given scheme is $(n, \epsilon, \delta)$-$\crepic$, applying Markov's inequality to conditions~\eqref{Eq_Dec_gen} and~\eqref{Eq_Priv_gen}, respectively, we get,
	\begin{align*}
		\pr{\mathsf{Bad}^{dec}} < 1/2 \text{ and } \pr{\mathsf{Bad}^{priv}_i} < 1/2N \text{ for all } i \in [N].
	\end{align*}
	Taking a union bound of these events, it is seen that there exists $w^* \in \cW$ such that $w^* \notin \cup_{i \in [N]}\mathsf{Bad}^{priv}_i \cup \mathsf{Bad}^{dec}$.
	Define encoder $\phi'$ and decoders $\{\psi'_i\}_{i \in [N]}$ as follows
	\begin{align*}
		\phi'\left(\xv_{[N]}, \kv_{\ak}\right) & = \phi\left(\xv_{[N]}, \kv_{\ak}, W = w\right),\\
		\psi'_i\left(\mv, \xv_{\s_i}, \kv_{\ak_i}\right) & = \psi_i\left(\mv, \xv_{\s_i}, \kv_{\ak_i}, W = w\right).
	\end{align*}
	Clearly, the above scheme is $(n, 2\epsilon, 2N\delta)$-$\repic$.
	This proves the lemma.
\hfill{\rule{2.1mm}{2.1mm}}

\subsection{Proof of Lemma~\ref{lem_0_err}}
	By Corollary~\ref{cor_nocrd}, it is sufficient to show that if the rate $(R, R_{\b} : \b \in \ak)$ is achievable using $\repic$ schemes then for all $\delta > 0$, rate $(R + \delta, R_{\b} : \b \in \ak)$ can be achieved using zero-error $\repic$ schemes.
	Fix $\delta > 0$, $\epsilon > 0$.
	For an appropriately chosen block-length $n$, using an $(n, \epsilon, \epsilon)$-$\repic$ scheme of rate $(R, R_{\b} : \b \in \ak)$, we construct a $(n, \epsilon')$-zero-error $\repic$ scheme of rate $(R + \delta, R_{\b} : \b \in \ak)$, where $\epsilon' = (3 + N)\epsilon$.
	Clearly, such a construction proves the lemma.
	A formal description such a construction and its analysis follows.

	For $\epsilon > 0$, choose $n$ large enough such that the following properties are satisfied.
	\begin{enumerate}
		\item There exits a $(n, \epsilon, \epsilon)$-$\repic$ scheme with encoder $\phi$ and decoders $\{\psi_i\}_{i \in [N]}$.
		\item Since transmission rate $(R, R_{\b} : \b \in \ak)$ is achievable using $\repic$ schemes, by Theorem~\ref{thm:priv_nopriv}, there exists a zero-error index code of rate $R$ for large enough block-length $k$.
		\item $n \ge \max \left(\frac{3}{\delta} kR, \frac{3}{\delta}, \frac{1}{\epsilon}\right)$.
	\end{enumerate}
	Recall that when $x^n \in \cX^n$, the co-ordinate $i$ of $x^n$ is denoted by $x^{(i)}$.
	For $x^{n} \in \cX^{n}$ and $1 \le j \le \lceil \frac{n}{k}\rceil$, define
	\begin{align*}
		\mathrm{block}_j(x^{n}) \defeq \begin{cases}
		(x^{(k(j - 1) + 1)}, \ldots, x^{(kj)}) \text{ for } 1 \le j < \lceil \frac{n}{k} \rceil,\\
		(x^{(k(j - 1) + 1)}, \ldots, x^{(n)}, 0, \ldots, 0) \text{ if } j = \lceil \frac{n}{k} \rceil.
		\end{cases}
	\end{align*}
	Consider a \emph{non-private} zero-error index coding scheme of block-length $k$ and rate $R$ with encoder $\alpha$ and decoders $\beta_{i}$ for user $i \in [N]$.
	From this scheme, we construct a zero-error index coding scheme of block-length $n$ with encoder $\alpha'$ and decoders $\beta'_i$ for user $i \in [N]$ as follows.
	For $x_i^{n} \in \cX^{n} : i \in [N]$,
	\begin{align*}
		\alpha'\left(x_{[N]}^{n}\right) = (m_1, m_2, \ldots, m_{\lceil \frac{n}{k} \rceil}) \text{ where } m_j = \alpha\left(\left(\mathrm{block}_j(x_{\ell}^{n})\right)_{\ell \in [N]}\right) \text{ for } 1 \le j \le {\lceil \frac{n}{k} \rceil},\\
		\beta'_i\left(m_1, \ldots, m_{\lceil \frac{n}{k} \rceil}, x^{n}_{\s_i}\right) = (\widehat{\mathrm{block}_1(x_i^{n})}, \ldots, \widehat{\mathrm{block}_{\lceil \frac{n}{k} \rceil}(x_i^{n})}) \text{ where } \widehat{\mathrm{block}_j(x_i^n)} = \beta_i\left(m_j, \left(\mathrm{block}_j(x_{\ell}^n)\right)_{\ell \in \s_i}\right).
	\end{align*}
	The index code for block-length $n$ is the concatenation of $\lceil \frac{n}{k} \rceil$ copies of zero-error index code for block-length $k$, hence it is also a zero-error index code.
	The rate of this scheme is $\frac{k \cdot \lceil \frac{n}{k} \rceil \cdot R}{n} \le \frac{R}{n} \cdot (n + k) \le R + \delta/3$.

	The $(n, \epsilon')$ zero-error $\repic$ with encoder $\phi'$ and decoders $\psi'_i$ for user $i \in [N]$, is a hybrid of the above mentioned $(n, \epsilon, \epsilon)$-$\repic$ scheme and the $n$ block-length index coding scheme.
	Intuitively, the new scheme falls back to the zero-error index coding whenever the $\repic$ scheme is found to make an error at any of the decoders.
	A formal description follows.
	For files $x_j^n \in \cX^n$ for $j \in [N]$ and keys $k_{\b} \in \mathbb{F}^{nR_{\b}}$ for $\b \in \ak$ and private randomness $w_{\phi} \in \cW_{\phi}$ of encoder $\phi'$ (which is identical to the private randomness of encoder $\phi$), when $m = \phi(x_{[N]}^n, k_{\ak}, w_{\phi})$
	\begin{align}
		& \phi'\left(x_{[N]}^n, k_{\ak}, w_{\phi}\right) = (\theta, \hat{m}, \text{zeros}_{\theta}) \text{ where }
		\begin{cases}
		\theta = 0 \text{ and } \hat{m} \defeq m \text{ if } \psi_i(m, x^n_{\s_i}, k_{\ak_i}) = x_i^n, \forall i \in [N],\\
		\theta = 1 \text{ and } \hat{m} \defeq \alpha'(x_{[N]}^n) \text{ otherwise.}
		\end{cases}\label{eq_0repic_enc}
	\end{align}
	$\text{zeros}_{\theta}$ is the appropriate length of zero padding needed to keep the transmission at $R + \delta$.
	The encoder uses the $(n, \epsilon)$-$\repic$ scheme whenever it can be correctly decoded at all users, if not, it uses the zero-error index coding scheme whenever the $\repic$ scheme commits an error.
	The value of $\theta$ records the used scheme.
	That the transmission can be made $R + \delta$ (by zero padding) follows from the fact that $(\theta, \hat{m})$ is at most $1 + n(R + \frac{\delta}{3})$ long since rate of the index code being being at most $R + \delta/3$; recollect that $\frac{1}{n} \le \frac{\delta}{3}$.
	For $i \in [N]$,
	\begin{align}
		& \psi'_i : \left(\theta, \hat{m}, \text{zeros}_{\theta}, x_{\s_i}^n, k_{\ak_i}\right) =
		\begin{cases}
		\psi_i(\hat{m}, x_{\s_i}^n, k_{\ak_i}) \text{ if } \theta = 0,\\
		\beta'_i(\hat{m}, x_{\s_i}^n) \text{ otherwise}.
		\end{cases}\label{eq_0repic_dec}
	\end{align}
	We will establish that this is a $(n, \epsilon')$-zero-error $\repic$ scheme of rate $(R + \delta, R_{\b} : \b \in \ak)$.
	By construction, it has block-length $n$ and rate $(R + \delta, R_{\b} : \b \in \ak)$.
	It is easy to observe that it also guarantees zero-error decoding at all receivers.
	Next we show that its privacy parameter is $\epsilon'$, completing the proof of the lemma.

	For files $\xv_{[N]}$ and keys $\kv_{\ak}$, let $\Theta$ and $\hat{\mv}$, respectively, represent the random variables corresponding to values of $\theta$ and $\hat{m}$ at the output of the encoder $\phi'$ (See~\eqref{eq_0repic_enc}).
	The privacy condition at user $i$ is,
	\begin{align}
	I \left( \hat{\mv},  \Theta ;\xv_{[N] \setminus \a_i} \middle | \kv_{\ak_i}, \xv_{\s_i} \right) & = I \left( \Theta ;\xv_{[N] \setminus \a_i} \middle | \kv_{\ak_i}, \xv_{\s_i} \right) + I \left( \hat{\mv} ;\xv_{[N] \setminus \a_i} \middle | \kv_{\ak_i}, \xv_{\s_i}, \Theta \right) \nonumber\\
	& \le H(\Theta) +  I \left( \hat{\mv} ;\xv_{[N] \setminus \a_i} \middle | \kv_{\ak_i}, \xv_{\s_i}, \Theta \right) \label{lem1_priv_eq}.
	\end{align}
	Second term in the RHS can be bounded as follows.
	\begin{align}
	I \left( \hat{\mv} ;\xv_{[N] \setminus \a_i} \middle | \kv_{\ak_i}, \xv_{\s_i}, \Theta \right) & = \pr{\Theta = 0} I \left( \hat{\mv} ;\xv_{[N] \setminus \a_i} \middle | \kv_{\ak_i}, \xv_{\s_i}, \Theta = 0 \right)  \nonumber\\
	& \qquad + \pr{\Theta = 1} I \left( \hat{\mv} ;\xv_{[N] \setminus \a_i} \middle | \kv_{\ak_i}, \xv_{\s_i}, \Theta = 1 \right) \nonumber\\
	&\le \pr{\Theta = 0} I \left( \hat{\mv} ;\xv_{[N] \setminus \a_i} \middle | \kv_{\ak_i}, \xv_{\s_i}, \Theta = 0 \right) + \epsilon H\left(\xv_{[N]}\right) \label{lem1_priv_eq_t1}.
	\end{align}
	By the definition of $\Theta$ in~\eqref{eq_0repic_enc}, $\pr{\Theta = 1} \leq \epsilon$ since the decoding error of $(n, \epsilon)$-$\repic$ scheme is at most $\epsilon$.
	Hence, the inequality~\eqref{lem1_priv_eq_t1} follows from $I\left(\hat{\mv} ;\xv_{[N] \setminus \a_i} \middle | \kv_{\ak_i}, \xv_{\s_i}, \Theta = 1 \right) \leq H\left(\xv_{[N]}\right)$.
	When $\Theta = 0$, $\hat{\mv} = \phi\left(\xv_{[N]}, \kv_{\ak}\right)$. Then,
	\begin{align}
	\pr{\Theta = 0} \cdot I\left( \hat{\mv} ;\xv_{[N] \setminus \a_i} \middle | \kv_{\ak_i}, \xv_{\s_i}, \Theta = 0 \right) & =  \pr{\Theta = 0} \cdot I \left(\phi\left(\xv_{[N]}, \kv_{\ak}\right) ;\xv_{[N] \setminus \a_i} \middle | \kv_{\ak_i}, \xv_{\s_i}, \Theta = 0 \right)  \nonumber\\
	& \le I\left( \phi\left(\xv_{[N]}, \kv_{\ak}\right) ;\xv_{[N] \setminus \a_i} \middle | \kv_{\ak_i}, \xv_{\s_i}, \Theta \right) \nonumber\\
	& \le I\left( \phi\left(\xv_{[N]}, \kv_{\ak}\right), \Theta ;\xv_{[N] \setminus \a_i} \middle | \kv_{\ak_i}, \xv_{\s_i} \right) \nonumber\\
	& \le I\left( \phi\left(\xv_{[N]}, \kv_{\ak}\right) ;\xv_{[N] \setminus \a_i} \middle | \kv_{\ak_i}, \xv_{\s_i} \right) + H(\Theta)  \nonumber \\
	& \leq n \epsilon + H(\Theta). \label{lem1_priv_eq_t2}
	\end{align}
	The last inequality follows from the scheme with encoder $\phi$ and decoders $\{\psi_i\}_{i \in [N]}$ being a $(n, \epsilon)$-$\repic$ scheme.
	Since $H\left(\xv_{[N]}\right) = nN$ in \eqref{lem1_priv_eq_t1} and $H(\Theta) \leq 1$ in \eqref{lem1_priv_eq}~and~\eqref{lem1_priv_eq_t2}, by substituting \eqref{lem1_priv_eq_t2} in \eqref{lem1_priv_eq_t1}, and \eqref{lem1_priv_eq_t1} in \eqref{lem1_priv_eq}, and using $n > \frac{1}{\epsilon}$, we get
	\begin{align}
	I \left(\hat{\mv}, \Theta ;\xv_{[N] \setminus \a_i} \middle | \kv_{\ak_i}, \xv_{\s_i} \right) \le n(1 + N)\epsilon + 2 \le n \epsilon'. \label{Eq_priv_uppr}
	\end{align}
\hfill{\rule{2.1mm}{2.1mm}}

\subsection{Proof of Claim~\ref{clm:in_lem_det}}
		The encoder $\phi$ can be thought of as a channel from $\left( \xv_{[N]}, \kv_{\ak} \right)$ to $\mv \defeq \phi\left(\xv_{[N]}, \kv_{\ak}, W_{\phi}\right)$, with the private randomness of the encoder $W_{\phi}$ being the randomness of the channel.
		Between a sender and receiver, this channel can be simulated (asymptotically) using a channel simulation scheme that uses only common randomness between the sender and the users (and no private randomness at the sender).
		Below we state a result from channel simulation, modified for our purposes.
		\begin{theorem}~\cite[Theorem 10]{cuff}\label{thm_cuff}
			Consider random variables $(U, V)$ jointly distributed over $\cU \times \cV$.
			For any $\epsilon, \delta > 0$, there is a large enough $m$, $\beta \le I(U ; V) + \delta$, common randomness $W$ distributed uniformly over a finite set $\cW$, and deterministic maps $\mathsf{Enc}$ and $\mathsf{Dec}$ such that, when the operator $\lVert . \rVert$ denotes total variation distance,
			\begin{align*}
			\mathsf{Enc} : \cU^m \times \cW \rightarrow 2^{m\beta}, \;
			\mathsf{Dec} : 2^{m\beta} \times \cW \rightarrow \cV^m, \text{ and }
			\left \lVert  \left( U^m, V^m\right)
			- \left(U^m, \mathsf{Dec}\left(Enc(U^m, W\right), W \right) \right \rVert \le \epsilon.
			\end{align*}
		\end{theorem}

		In the sequel, to avoid confusion, for each $\b \in \ak$, the random variable for the keys (of rate $nR_{\b}$) used in the $(n, \epsilon)$-zero-error-$\repic$ scheme is denoted by $\bl{\k}{n}_{\b}$ and the transmitted message is denoted by $\bl{\m}{n}$.
		Furthermore, $m$ i.i.d. copies of $\xv_i : i \in [N]$ is denoted by $\iid{\x}{n, m}$, and $m$ i.i.d. copies of $\bl{\k}{n}_{\b} : \b \in \ak$ and $\bl{\m}{n}$ are denoted by $\iid{\k}{n, m}$ and $\iid{\m}{n, m}$, respectively.
		For $1 \le j \le m$, the $j^{th}$, $n$-sized block in $\iid{\x}{n, m}_i, \iid{\k}{n, m}_{\b}$ and $\iid{\m}{n, m}$ are denoted by $\iid{\x}{n, (j)}_i, \iid{\k}{n, (j)}_{\b}$ and $\iid{\m}{n, (j)}$, respectively.

		Substituting $\left(\xv_{[N]}, \bl{\k}{n}_{\ak}\right)$ and $\bl{\m}{n}$ for $U$ and $V$, respectively, in above theorem we can conclude that there exists a large enough $m$, common randomness $W$, and functions $\mathsf{Enc}$ and $\mathsf{Dec}$ such that the image of $\mathsf{Enc}$ is $\mathbb{F}^{m\beta}$, where
	\begin{align}
	& m \beta \le m \left( I\left(\iid{\x}{n}_{[N]}, \iid{\k}{n}_{\ak}; \iid{\m}{n}\right) + n \cdot \min(\epsilon, \delta)\right) \le mn (R + \min(\epsilon, \delta)), \text{and}\label{eq_rate}\\
	& \bigg \lVert \left(\iid{\x}{n, m}_{[N]}, \iid{\k}{n, m}_{\ak}, \iid{\m}{n, m}\right) - \left(\iid{\x}{n, m}_{[N]}, \iid{\k}{n, m}_{\ak}, \mathsf{Dec}\left(J, W\right) \right) \bigg \rVert \le \epsilon, \text{ where } J \defeq \mathsf{Enc}\left(\left(\iid{\x}{n, m}_{[N]}, \iid{\k}{n, m}_{\ak}\right), W\right). \label{eq_det_norm}
	\end{align}
	Since $\mathsf{Dec}\left(J, W\right)$ is statistically close to $\iid{\m}{n, m}$, we will denote it by $\widehat{\iid{\m}{n, m}}$.

	Below, we define a $mn$ block-length scheme with encoder $\phi'$ and decoders $\{\psi_i\}_{i \in [N]}$ that use common randomness $W$ and \emph{no private randomness at encoder or decoders}.
	\begin{align*}
		& \phi'\left(\iid{\x}{n, m}_{[N]}, \iid{\k}{n, m}_{\ak}, W \right) = \mathsf{Enc} \left(\iid{\x}{n, m}_{[N]}, \iid{\k}{n, m}_{\ak}, W \right) = J,\\
		& \psi'_i\left(J, \iid{\x}{n, m}_{\s_i}, \iid{\k}{n, m}_{\ak_i}, W \right) = \left(\widehat{\iid{\x}{n, (1)}_i}, \ldots, \widehat{\iid{\x}{n, (m)}_i}\right), \text{where } \widehat{\iid{\x}{n, (j)}_i} \defeq \psi_i\left(\widehat{\iid{\m}{n, (j)}}, \iid{\x}{n, (j)}_{\s_i}, \iid{\k}{n, (j)}_{\ak_i}\right).
	\end{align*}
	This is a $mn$ block-length scheme and form~\eqref{eq_rate} it follows that its rate is $(R + \delta, R_{\b} : \b \in \ak)$.
	If $\epsilon < \delta$, the transmission rate can be made $R + \delta$ by zero-padding.
	Next, we establish that the decoding error of this scheme is at most $\epsilon$.
	The decoding error of is given by the expression,
	\begin{align*}
	1 - \pr{\widehat{\iid{\x}{n, (j)}_i} = \iid{\x}{n, (j)}_i, \forall i \in [N], j \in [m]}.
	\end{align*}
	Inequality~\eqref{eq_det_norm} implies that
	\begin{align*}
		\bigg \lVert \left(\iid{\m}{n, (j)}, \iid{\x}{n, (j)}_{\s_i}, \iid{\k}{n, (j)}_{\ak_i}\right)_{j \in [m], i \in [N]} - \left(\widehat{\iid{\m}{n, (j)}}, \iid{\x}{n, (j)}_{\s_i}, \iid{\k}{n, (j)}_{\ak_i}\right)_{i \in [m], j \in [N]} \bigg \rVert \le \epsilon.
	\end{align*}
	Hence, by the definition of statistical distance,
	\begin{multline*}
	\pr{\psi'_i \left( \widehat{\iid{\m}{n, (j)}}, \iid{\x}{n, (j)}_{\s_i}, \iid{\k}{n, (j)}_{\ak_i} \right) = \iid{\x}{n, (j)}_i, i \in [N], j \in [m]}\\
	\ge \pr{\psi_i \left( \iid{\m}{n, (j)}, \iid{\x}{n, (j)}_{\s_i}, \iid{\k}{n, (j)}_{\ak_i} \right) = \iid{\x}{n, (j)}_i, i \in [N], j \in [m]} - \epsilon.
	\end{multline*}
	Since the scheme with encoder $\phi$ and decoders $\psi_i$ for user $i \in [N]$ is a zero-error $\repic$ scheme,
	\begin{align*}
	\pr{\psi_i \left( \iid{\m}{n, (j)}, \iid{\x}{n, (j)}_{\s_i}, \iid{\k}{n, (j)}_{\ak_i} \right) = \iid{\x}{n, (j)}_i, i \in [N], j \in [m]} = 1.
	\end{align*}
	Hence the decoding error the new scheme with encoder $\phi'$ and decoders $\psi'_i$ for user $i \in [N]$ is at most $\epsilon$.

	To analyze the privacy parameter, we use the following lemma that claims that two distributions that are statistically close are also close in their entropies.
	\begin{lemma}~\cite[Lemma 2.7]{csiszar}\label{lem:csiszar}
		If $P, Q$ are two distributions on a finite set $\cX$ such that $\left \lVert P - Q \right \rVert \le \epsilon$, then
		\begin{align*}
		\left | H\left(P\right) - H\left(Q\right) \right | \le \epsilon(\log{\left|\cX\right|} - \log{\epsilon}).
		\end{align*}
	\end{lemma}
	The privacy condition at user $i \in [N]$ is given by the mutual information,
	\begin{align}
	I \left( J ; \iid{\x}{n, m}_{[N] \setminus \a_i} \middle | \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i}, W \right) \le I \left( J , W; \iid{\x}{n, m}_{[N] \setminus \a_i} \middle | \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i} \right). \label{Eq_priv_mutl_info}
	\end{align}
	Since $\widehat{\iid{\m}{n, m}}$ is a function of $(J, W)$, the above inequality implies that,
	\begin{multline}
	I \left( J ; \iid{\x}{n, m}_{[N] \setminus \a_i} \middle | \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i}, W \right) \le I \left( J, W, \widehat{\iid{\m}{n, m}} ; \iid{\x}{n, m}_{[N] \setminus \a_i} \middle | \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i} \right)\\ = I \left( \widehat{\iid{\m}{n, m}} ; \iid{\x}{n, m}_{[N] \setminus \a_i} \middle | \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i} \right) + I \left( J, W ; \iid{\x}{n, m}_{[N] \setminus \a_i} \middle | \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i}, \widehat{\iid{\m}{n, m}} \right).
	\label{Eq_priv_mutl_info2}
	\end{multline}
	The first term in the RHS of~\eqref{Eq_priv_mutl_info2} is upper bounded using the following observation.
	Using Lemma~\ref{lem:csiszar},
	\begin{multline}\label{Eq_priv_mutl_info3}
	I \left( \widehat{\iid{\m}{n, m}} ; \iid{\x}{n, m}_{[N] \setminus \a_i} \middle | \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i} \right) - I \left( \iid{\m}{n, m} ; \iid{\x}{n, m}_{[N] \setminus \a_i} \middle | \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i} \right)\\
	= I \left( \widehat{\iid{\m}{n, m}}, \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i}  ; \iid{\x}{n, m}_{[N] \setminus \a_i} \right) - I \left( \iid{\m}{n, m}, \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i} ; \iid{\x}{n, m}_{[N] \setminus \a_i} \right).
	\end{multline}
	This follows from $I \left( \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i}  ; \iid{\x}{n, m}_{[N] \setminus \a_i} \right) = 0$ as the files and keys are independently distributed.
	The RHS can be expanded as,
	\begin{multline*}
	H \left( \widehat{\iid{\m}{n, m}}, \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i} \right) - \left(H \left( \widehat{\iid{\m}{n, m}}, \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i}, \iid{\x}{n, m}_{[N] \setminus \a_i} \right) - H \left(\iid{\x}{n, m}_{[N] \setminus \a_i} \right)\right) \\
	- H \left( \iid{\m}{n, m}, \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i} \right) + \left(H\left( \iid{\m}{n, m}, \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i}, \iid{\x}{n, m}_{[N] \setminus \a_i} \right) - H\left(\iid{\x}{n, m}_{[N] \setminus \a_i} \right)\right).
	\end{multline*}
	Since,
	\begin{align*}
		\bigg \lVert \left(\iid{\m}{n, m}, \iid{\x}{n, m}_{[N]}, \iid{\k}{n, m}_{\ak}\right) - \left(\widehat{\iid{\m}{n, m}}, \iid{\x}{n, m}_{[N]}, \iid{\k}{n, m}_{\ak}\right) \bigg \rVert \le \epsilon,
	\end{align*}
	by Lemma~\ref{lem:csiszar}, the above expression can be bounded as,
	\begin{multline}\label{Eq_priv_mutl_info4}
	H \left( \widehat{\iid{\m}{n, m}}, \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i} \right) - H \left( \widehat{\iid{\m}{n, m}}, \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i}, \iid{\x}{n, m}_{[N] \setminus \a_i} \right) \\
	- H \left( \iid{\m}{n, m}, \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i} \right) + H\left( \iid{\m}{n, m}, \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i}, \iid{\x}{n, m}_{[N] \setminus \a_i} \right)\\
	\le 2\epsilon\left(\log{\mathsf{support}\left( \iid{\m}{n, m}, \iid{\x}{n, m}_{[N]}, \iid{\k}{n, m}_{\ak}\right)} - \log{\epsilon}\right)
	\le 2\epsilon\left( mn \left( R + N + \sum_{\b \in \ak} R_b \right) + \log{\frac{1}{\epsilon}}\right).
	\end{multline}
	From~\eqref{Eq_priv_mutl_info3}~and~\eqref{Eq_priv_mutl_info3}, we can conclude that,
	\begin{multline}
	I \left( \widehat{\iid{\m}{n, m}} ; \iid{\x}{n, m}_{[N] \setminus \a_i} \middle | \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i} \right)\\
	\le I \left( \iid{\m}{n, m} ; \iid{\x}{n, m}_{[N] \setminus \a_i} \middle | \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i} \right) + 2\epsilon\left( mn \left( R + N + \sum_{\b \in \ak} R_b \right) + \log{\frac{1}{\epsilon}}\right) \\
	= m \cdot I \left( \bl{\m}{n} ; \iid{\x}{n}_{[N] \setminus \a_i} \middle | \bl{\k}{n}_{\ak_i}, \iid{\x}{n}_{\s_i} \right) + 2\epsilon\left( mn \left( R + N + \sum_{\b \in \ak} R_b \right) + \log{\frac{1}{\epsilon}}\right) \\
	\le mn\epsilon + 2\epsilon\left( mn \left( R + N + \sum_{\b \in \ak} R_b \right) + \log{\frac{1}{\epsilon}}\right).\label{Eq_uppr_bnd_first}
	\end{multline}
	Here, the last inequality follows from the privacy condition at user $i$ for the given block-length $n$ scheme.
	The second term in the RHS of~\eqref{Eq_priv_mutl_info2} can be bounded as
	\begin{multline}
	I \left( J, W ; \iid{\x}{n, m}_{[N] \setminus \a_i} \middle | \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i}, \widehat{\iid{\m}{n, m}} \right) \\
	\le I \left( J, W ; \iid{\x}{n, m}_{[N]}, \iid{\k}{n, m}_{\ak} \middle | \widehat{\iid{\m}{n, m}} \right)
	= I \left( J, W, \widehat{\iid{\m}{n, m}} ; \iid{\x}{n, m}_{[N]}, \iid{\k}{n, m}_{\ak} \right) - I \left( \widehat{\iid{\m}{n, m}} ; \iid{\x}{n, m}_{[N]}, \iid{\k}{n, m}_{\ak} \right).\label{eq_priv_bound}
	\end{multline}
	We upper bound the RHS of~\eqref{eq_priv_bound} by upper bounding  the first term and lower bounding  the second term.
	The first term can be upper bounded as follows.
	\begin{multline}
	I \left( J, W, \widehat{\iid{\m}{n, m}} ; \iid{\x}{n, m}_{[N]}, \iid{\k}{n, m}_{\ak} \right) \stackrel{(a)}{=} I \left( J, W ; \iid{\x}{n, m}_{[N]}, \iid{\k}{n, m}_{\ak} \right) \stackrel{(b)}{=} I \left( J ; \iid{\x}{n, m}_{[N]}, \iid{\k}{n, m}_{\ak} \middle | W \right) \\
	\le H(J) \stackrel{(c)}{\le} m\beta \stackrel{(d)}{\le} m\left(I\left(\iid{\m}{n} ; \iid{\x}{n}_{[N]}, \iid{\k}{n}_{\ak}\right) + n\epsilon\right) = I\left(\iid{\m}{n, m} ; \iid{\x}{n, m}_{[N]}, \iid{\k}{n, m}_{\ak}\right) + mn\epsilon. \label{Eq_mutl_uppr_bnd}
	\end{multline}
	Here, (a) follows from $\widehat{\iid{\m}{n, m}}$ being a deterministic function of $J, W$, (b) follows from the independence between $W$ and $\iid{\x}{n, m}, \iid{\k}{n, m}_{\ak}$, (c) follows from the range of $\mathsf{Enc}$ being $\mathbb{F}^{m\beta}$, and finally, (d) follows from~\eqref{eq_rate}.
	Similar to the bound~\eqref{Eq_uppr_bnd_first} obtained on the first term in the RHS of~\eqref{Eq_priv_mutl_info2}, using Lemma~\ref{lem:csiszar}, we bound the second term in the RHS of~\eqref{eq_priv_bound} as
	\begin{align}
	I\left(\widehat{\iid{\m}{n, m}} ; \iid{\x}{n, m}_{[N]}, \iid{\k}{n, m}_{\ak}\right) \ge I\left(\iid{\m}{n, m} ; \iid{\x}{n, m}_{[N]}, \iid{\k}{n, m}_{\ak}\right) - 2\epsilon\left( mn \left( R + N + \sum_{\b \in \ak} R_b \right) + \log{\frac{1}{\epsilon}}\right). \label{Eq_mutl_low_bnd}
	\end{align}
	By substituting \eqref{Eq_mutl_low_bnd} and \eqref{Eq_mutl_uppr_bnd} in \eqref{eq_priv_bound}, we get
	\begin{align}
	I \left( J, W ; \iid{\x}{n, m}_{[N] \setminus \a_i} \middle | \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i}, \widehat{\iid{\m}{n, m}} \right)
	\leq mn\epsilon + 2\epsilon\left( mn \left( R + N + \sum_{\b \in \ak} R_b \right) + \log{\frac{1}{\epsilon}}\right).\label{Eq_uppr_mutl_eps}
	\end{align}
	Using the bounds~\eqref{Eq_uppr_mutl_eps} and~\eqref{Eq_uppr_bnd_first} in~\eqref{Eq_priv_mutl_info2}, for all $i \in [N]$,
	\begin{multline}
	I \left( J ; \iid{\x}{n, m}_{[N] \setminus \a_i} \middle | \iid{\k}{n, m}_{\ak_i}, \iid{\x}{n, m}_{\s_i}, W \right) \le 2mn\epsilon + 4\epsilon\left( mn \left( R + N + \sum_{\b \in \ak} R_b \right) + \log{\frac{1}{\epsilon}}\right)\le mn\epsilon',\\
	\text{where } \epsilon' = 4\epsilon\left(\frac{1}{2} + R + N + \sum_{\b \in \ak}R_{\b} + \frac{1}{mn} \cdot \log{\frac{1}{\epsilon}}\right). \label{eq_det_priv}
	\end{multline}
	Hence, the new scheme has privacy error $\epsilon'$.
	The common randomness $W$ used in the scheme can be fixed to an appropriate value (see Lemma~\ref{lem_no_cr}) to obtain a $(mn, 2\epsilon, 2N\epsilon')$-$\pic$ scheme.
	This proves the claim as $\epsilon' \rightarrow 0$ as $\epsilon \rightarrow 0$.

\subsection{Proof of Lemma~\ref{lem:priv_linear}}
Consider perfect private linear index coding scheme for $N$ users of block-length $n$ and rate $R$, that uses private randomness at the encoder.
Let $\bX_i$ denote the row-vector corresponding to $\xv$, $\bK_{\b}: \b \in \ak$, denote the key uniformly distributed in $\mathbb{F}^{nR_{\b}}$ and let $\bP$ denote the private randomness uniformly distributed in $\mathbb{F}^{p}$ for some number $p$.
Since $\ak$ is the same as $\{1, \ldots, 2^N - 2\}$, in the sequel, we will often represent $\b$ as a number between $1$ and $2^N - 2$.
A linear encoder of the scheme may be described as follows.
\begin{align*}
	\bM &= \sum_{i \in [N]} G_i \bX_i^T + \sum_{1 \le \b \le 2^N - 2} H_{\b} \bK_{\b}^T + H' \bP\\
	&= \begin{bmatrix}
		G_1 & \ldots & G_N & H_{1} & \ldots & H_{2^N - 2} & H'
	\end{bmatrix}
	\begin{bmatrix}
		\bX_1 & \ldots & \bX_N & \bK_{1} & \ldots & \bK_{2^N - 2} & \bP
	\end{bmatrix}^T\\
	&\defeq \Psi
	\begin{bmatrix}
		\bX_1 & \ldots & \bX_N & \bK_{1} & \ldots & \bK_{2^N - 2} & \bP
	\end{bmatrix}^T
\end{align*}
where $G_i \in \mathbb{F}^{nR \times n}$, $H_{\b} \in \mathbb{F}^{nR \times nR_{\b}}$ and $H' \in \mathbb{F}^{nR \times np}$ and $\Phi$ is the generator matrix of the encoder.
For $i \in [N]$, by the zero-error decoding condition, there exists $L^i \in \mathbb{F}^{n \times nR}$, $S^i_j \in \mathbb{F}^{n \times n}$ where $j \in \s_i$ and $T^i_{\b} \in \mathbb{F}^{n \times nR_{b}}$ where $\b \in \ak_i$ such that
\begin{align}\label{eq:priv_linear_dec}
	\bX_i = L^i \bM + \sum_{j \in \s_i} S^i_j \bX_i^T + \sum_{\b \in \ak_i} T^i_{\b} \bK_{\b}^T.
\end{align}
Hence, $L^i \bM$ is determined by $\bX_i, i \in \a_i$ and $\bK_{\b}, \b \in \ak_i$ and it is independent of $\bP$.
Consider the encoding scheme
\begin{align*}
	\begin{bmatrix}
		\bM^1 & \ldots & \bM^N
	\end{bmatrix}^T =
	\begin{bmatrix}
		(L^1)^T & \ldots & (L^N)^T
	\end{bmatrix}^T \Phi.
	\begin{bmatrix}
		\bX_1 & \ldots & \bX_N & \bK_{1} & \ldots & \bK_{2^N - 2} & \bP
	\end{bmatrix}^T.
\end{align*}
It follows from the above observation that this encoder does not use private randomness.
The actual encoding will use a row-reduced form of the matrix $\left[(L^1)^T \; \ldots \; (L^N)^T\right]^T \Phi$; \emph{i.e.,} after removing the independent rows.
Clearly, this encoding scheme is private since $\Psi$ is private.
It follows from~\eqref{eq:priv_linear_dec} that
\begin{align*}
	\bX_i = \bM^i + \sum_{j \in \s_i} S^i_j \bX_i^T + \sum_{\b \in \ak_i} T^i_{\b} \bK_{\b}^T.
\end{align*}
Hence, we have obtained a linear private index coding scheme that does not use private randomness.
Since the rank of $[(L^1)^T \; \ldots \; (L^N)^T]^T \Phi$ is at most the rank of $\Phi$, the rate of this scheme is at most the rate of the given scheme.
This proves the lemma.
\hfill{\rule{2.1mm}{2.1mm}}


TITLE: $T_2$-spaces with order-isomorphic topologies
QUESTION [3 upvotes]: Suppose $X\neq \emptyset$ is a set. Let $\tau_1, \tau_2$ be Hausdorff topologies on $X$ with the property that the partially ordered sets $(\tau_1,\subseteq)$ and $(\tau_2,\subseteq)$ are order-isomorphic.
Does this imply that $(X,\tau_1)\cong (X,\tau_2)$ as topological spaces?

If Hausdorffness is dropped, then there are easy counterexamples, for instance $X = \omega$ and $\tau_1 = \{\emptyset,\{0\},\omega\}, \tau_2 = \{\emptyset, \omega\setminus\{0\},\omega\}$.

REPLY [3 votes]: If $h:(\tau_1, \subseteq) \to (\tau_2, \subseteq)$ is an order isomorphism.
Define $M(\tau_1) = \{O \in \tau_1: O \neq X \land \forall O' \in \tau_1: O \subseteq O' \implies O' = X\}$, the "submaximal" elements.
Because the definition is purely order theoretical, $h[M(\tau_1)] = M(\tau_2)$.
Then all $O \in M(\tau_1)$ are of the form $X\setminus \{p\}$ for some $p \in X$ when $X$ is a $T_1$ space: if $|X \setminus O| \ge 2$ pick $x$ in this complement, and $O \subseteq X\setminus \{x\} \subseteq X$, where the middle set is open by $T_1$-ness, this shows $O \notin M(\tau_1)$. So $\forall O \in M(\tau_1): |X \setminus O| =1$. Also, all sets of the form $X\setminus \{p\}$ are in $M(\tau_1)$.
So the above implies that if both topologies are $T_1$, we can define $f: X \to X$ by
$\{f(x)\} = X\setminus h(M\setminus \{x\})$.
One can now check that $f$ is the required homeomorphism, using that $h$ is an order isomorphism.


text:
\begin{document}

\thispagestyle{empty}
\title{On the motive of some hyperK\"ahler varieties} \author{Charles Vial}

\thanks{2010 {\em Mathematics Subject Classification.} 14C25, 14C15,
  53C26, 14J28, 14K99}

\thanks{{\em Key words and phrases.} Hyperk\"ahler manifolds,
  Irreducible holomorphic symplectic varieties, K3 surfaces, abelian
  varieties, Hilbert schemes of points, Motives, Algebraic cycles,
  Chow ring, Chow--K\"unneth decomposition, Bloch--Beilinson
  filtration}

\thanks{}

\thanks{The author is supported by EPSRC Early Career Fellowship
  number EP/K005545/1.}

\address{DPMMS, University of Cambridge, Wilberforce Road, Cambridge
  CB3 0WB, UK} \email{c.vial@dpmms.cam.ac.uk}

\date{\today}

\begin{abstract} We show that the motive of the Hilbert scheme of
  length-$n$ subschemes on a K3 surface or on an abelian surface
  admits a decomposition similar to the decomposition of the motive of
  an abelian variety obtained by Shermenev, Beauville, and Deninger and Murre.
\end{abstract}

\maketitle

\section*{Introduction}

In this work, we fix a field $k$ and all varieties are defined over
this field $k$. Chow groups are always meant
with rational coefficients and $\HH^*(-,\Q)$ is Betti cohomology with
rational coefficients.  Up to replacing Betti cohomology with a suitable Weil
cohomology theory (for example $\ell$-adic cohomology), we may and we will
assume that $k$ is a subfield of the complex numbers $\C$. We use freely the
language of (Chow) motives as
is described in \cite{manin}. \medskip

Work of Shermenev \cite{shermenev}, Beauville \cite{beauville1}, and
Deninger and Murre \cite{dm} unravelled the structure of the motives
of abelian varieties~:

\begin{thm3} [Beauville, Deninger--Murre, Shermenev] Let $A$ be an
  abelian variety of dimension $g$. Then the Chow motive $\h(A)$ of
  $A$ splits as
\begin{equation} \label{eq CK} \h(A) = \bigoplus_{i=0}^{2g} \h^i(A)
\end{equation}
 with the following
  properties~:
\begin{enumerate}[(i)]
\item $\HH^*(\h^i(A),\Q) = \HH^i(A,\Q)$ ;
\item the multiplication $\h(A)\otimes \h(A) \rightarrow \h(A)$
  (\emph{cf.} \eqref{eq mult}) factors through $\h^{i+j}(A)$ when
  restricted to $\h^i(A)\otimes \h^j(A)$~;
\item the morphism $[n]^* : \h^i(A) \rightarrow \h^i(A)$ induced by
  the multiplication by $n$ morphism $[n] : A \rightarrow A$ is
  multiplication by $n^i$. Here, $n$ is an integer. In particular, $\h^i(A)$ is
an eigen-submotive for the action of $[n]$.
\end{enumerate}
\end{thm3}

For an arbitrary smooth projective variety $X$, it is expected that a
decomposition of the motive $\h(X)$ as in \eqref{eq CK} satisfying
\emph{(i)} should exist ; see \cite{murre}. Such a decomposition is
called a \emph{Chow--K\"unneth decomposition}. However, in general,
there is no analogue of the multiplication by $n$ morphisms, and the
existence of a Chow--K\"unneth decomposition of the motive of $X$
satisfying \emph{(ii)} (in that case, the Chow--K\"unneth
decomposition is said to be \emph{multiplicative}) is very
restrictive. We refer to \cite[Section 8]{sv} for some discussion on
the existence of such a multiplicative decomposition.

Nonetheless, inspired by the seminal work of Beauville and Voisin
\cite{bv}, \cite{beauville2} and \cite{voisin2}, we were led
to ask in \cite{sv} whether the motives of hyperK\"ahler varieties
admit a multiplicative decomposition similar to that of the motive of
abelian varieties as in the theorem of Beauville, Deninger and Murre,
and Shermenev. Here, by hyperK\"ahler variety we mean a simply
connected smooth projective variety $X$ whose space of global
$2$-forms $\HH^0(X,\Omega_X^2)$ is spanned by a nowhere degenerate
$2$-form. When $k=\C$, a hyperK\"ahler variety is nothing but a
projective irreducible holomorphic symplectic manifold \cite{beauvillec1}.

\begin{conj2} \label{conj} Let $X$ be a hyperK\"ahler variety of
  dimension $2n$. Then the Chow motive $\h(X)$ of $X$ splits
  as $$\h(X) = \bigoplus_{i=0}^{4n} \h^i(X)$$ with the property that
\begin{enumerate}[(i)]
\item $\HH^*(\h^i(X),\Q) = \HH^i(X,\Q)$ ;
\item the multiplication $\h(X)\otimes \h(X) \rightarrow \h(X)$
  (\emph{cf.} \eqref{eq mult}) factors through $\h^{i+j}(X)$ when
  restricted to $\h^i(X)\otimes \h^j(X)$.
\end{enumerate}
\end{conj2}

An important class of hyperK\"ahler varieties is given by the Hilbert
schemes $S^{[n]}$ of length-$n$ subschemes on a K3 surface $S$ ; see
\cite{beauvillec1}. The following theorem shows in particular that the
motive of $S^{[n]}$ for $S$ a K3 surface admits a decomposition with
properties \emph{(i)} and \emph{(ii)} and thus answers affirmatively
the question raised in Conjecture \ref{conj} in that case.

\begin{thm2} \label{thm main} Let $S$ be either a K3 surface or an
  abelian surface, and let $n$ be a positive integer. Then the Chow
  motive $\h(S^{[n]})$ of $S^{[n]}$ splits as $$\h(S^{[n]}) =
  \bigoplus_{i=0}^{4n} \h^i(S^{[n]})$$ with the property that
\begin{enumerate}[(i)]
\item $\HH^*(\h^i(S^{[n]}),\Q) = \HH^i(S^{[n]},\Q)$ ;
\item the multiplication $\h(S^{[n]})\otimes \h(S^{[n]}) \rightarrow
  \h(S^{[n]})$ factors through $\h^{i+j}(S^{[n]})$ when restricted to
  $\h^i(S^{[n]})\otimes \h^j(S^{[n]})$.
\end{enumerate}
\end{thm2}

Theorem 6 of \cite{sv} can then be improved by including the Hilbert
schemes of length-$n$ subschemes on K3 surfaces.
Theorem
\ref{thm main} is due for $S$ a K3 surface and $n=1$ to Beauville and
Voisin \cite{bv} (see \cite[Proposition 8.14]{sv} for the link between
the original statement of \cite{bv} (recalled in Theorem \ref{thm bv}) and the
statement given here), and
was established in \cite{sv} for $n=2$. Its proof in full generality
is given in Section 3. Note that, as explained in Section 1, the
existence of a Chow--K\"unneth decomposition for the Hilbert scheme
$S^{[n]}$ of any smooth projective surface $S$ goes back to de Cataldo
and Migliorini \cite{dCM} (the existence of such a decomposition for
$S$ is due to Murre \cite{murre2}).
Our main contribution is the claim
that by choosing the Beauville--Voisin decomposition of K3 surfaces \cite{bv},
the induced Chow--K\"unneth decomposition of Hilbert schemes of K3 surfaces
established by de Cataldo and Migliorini \cite{dCM} is
multiplicative, i.e. it satisfies \emph{(ii)}.\medskip

Let us then define for all $i\geq 0$ and all $s \in \Z$
$$\CH^i(S^{[n]})_s := \CH^i(\h^{2i-s}(S^{[n]})).$$
We have the following corollary to Theorem \ref{thm main}~:

\begin{thm2} \label{thm bigrading} The Chow ring $\CH^*(S^{[n]})$
  admits a multiplicative bigrading
 $$\CH^*(S^{[n]}) = \bigoplus_{i,s} \CH^i(S^{[n]})_s$$
 that is induced by a Chow--K\"unneth decomposition of the diagonal
 (as defined in \S 1).  Moreover,
 the Chern classes $c_i(S^{[n]})$ belong to the graded-zero part
 $\CH^i(S^{[n]})_0$ of $\CH^i(S^{[n]})$.
\end{thm2}

Theorem \ref{thm bigrading} answers partially a question raised by
Beauville in \cite{beauville2}~: the  filtration $F^\bullet$ defined by
$\mathrm{F}^l\CH^i(X) :=
\bigoplus_{s\geq l}\CH^i(X)_s$ is a filtration on the Chow ring $\CH^*(S^{[n]})$
that is split. Moreover, this filtration is expected to be the one predicted by
Bloch and Beilinson (because it is induced
by a Chow--K\"unneth decomposition -- conjecturally all such
filtrations coincide). For this filtration to be of Bloch--Beilinson type, one
would need to establish Murre's conjectures, namely that $\CH^i(S^{[n]})_s = 0$
for $s<0$ and that $\bigoplus_{s>0} \CH^i(S^{[n]})_s$ is exactly the kernel of
the cycle class map $\CH^i(S^{[n]}) \rightarrow \HH^{2i}(S^{[n]},\Q)$.
Note that for $i=0,1,2n-1$ or $2n$, it is indeed the case that $\CH^i(S^{[n]})_s = 0$
for $s<0$ and that $\bigoplus_{s>0} \CH^i(S^{[n]})_s = \mathrm{Ker} \, \{\CH^i(S^{[n]}) \rightarrow \HH^{2i}(S^{[n]},\Q)\}$. Therefore, we have
\begin{cor2}\label{cor main}
Let $i_1,\ldots, i_m$ be positive integers such that $i_1 + \cdots + i_m = 2n-1$ or $2n$, and let $\gamma_l$ be cycles in $\CH^{i_l}(S^{[n]})$ for $l=1,\ldots, m$ that sit in $\CH^{i_l}(S^{[n]})_0$ for the grading induced by the decomposition of Theorem \ref{thm main}. Then, $[\gamma_1]\cdot [\gamma_2] \cdots  [\gamma_m] = 0$ in $\HH^*(S^{[n]},\Q)$ if and only if  $\gamma_1\cdot \gamma_2 \cdots \gamma_m = 0$ in $\CH^*(S^{[n]})$.
\end{cor2}
 \medskip

Let us mention that Theorem \ref{thm main} and Theorem \ref{thm
  bigrading} (and a fortiori Corollary \ref{cor main}) are also valid for hyperK\"ahler varieties that are
birational to $S^{[n]}$, for some K3 surface $S$. Indeed, Riess \cite{greiner}
showed that birational hyperK\"ahler varieties have isomorphic Chow rings and
isomorphic Chow motives (as algebras in the category of Chow motives) ; see also
\cite[Section 6]{sv}. As for more
evidence as why Conjecture \ref{conj} should be true, Mingmin Shen and
I showed \cite{sv} that the variety of lines on a very general cubic
fourfold satisfies the conclusions of Theorem \ref{thm
  bigrading}. \medskip

Finally, we use the notion of multiplicative Chow--K\"unneth
decomposition to obtain new decomposition results in the spirit of
\cite{voisin k3} ; see Theorem \ref{thm dec}.

\subsection*{Notations} A morphism denoted $pr_r$ will always denote
the projection on the $r^\mathrm{th}$ factor and a morphism denoted
$pr_{s,t}$ will always denote the projection on the product of the
$s^\mathrm{th}$ and $t^\mathrm{th}$ factors. The context will usually
make it clear which varieties are involved.  Chow groups $\CH^i$ are
with rational coefficients. If $X$ is a variety, the cycle class map
sends a cycle $\sigma \in \CH^i(X)$ to its cohomology class $[\sigma]
\in \HH^{2i}(X,\Q)$.  If $Y$ is another variety and if $\gamma$ is a
correspondence in $\CH^i(X \times Y)$, its transpose ${}^t\gamma \in
\CH^i(Y \times X)$ is the image of $\gamma$ under the action of the
permutation map $X \times Y \rightarrow Y \times X$. If
$\gamma_1,\cdots, \gamma_n$ are correspondences in $\CH^*(X \times
Y)$, then the correspondence $\gamma_1 \otimes \cdots \otimes \gamma_n
\in \CH^*(X^n\times Y^n)$ is defined as $\gamma_1 \otimes \cdots
\otimes \gamma_n := \prod_{i=1}^n (pr_{i,n+i})^*\gamma_i$.

\vspace{10pt}
\section{Chow--K\"unneth decompositions}

A Chow motive $M$ is said to have a \emph{Chow--K\"unneth
  decomposition} if it splits as $M=\bigoplus_{i \in \Z} M^i$ with
$\HH^*(M^i,\Q) = \HH^i(M,\Q)$. In other words, $M$ admits a K\"unneth
decomposition that lifts to rational equivalence. Concretely, if
$M=(X,p,n)$ with $X$ a smooth projective variety of pure dimension $d$
and $p \in \CH^d(X\times X)$ an idempotent and $n$ an integer, then
$M$ has a Chow--K\"unneth decomposition if there exist finitely many
correspondences $p^i \in \CH^d(X \times X)$, $i \in \Z$, such that
$p=\sum_i p^i$, $p^i \circ p^i = p^i$, $p\circ p^i = p^i \circ p =
p^i$, $p^i \circ p^j = 0$ for all $i \in \Z$ and all $j \neq i$ and
such that $p^i_*\HH^*(X,\Q) = p_*\HH^{i+2n}(X,\Q)$.

A smooth projective variety $X$ of dimension $d$ has a Chow--K\"unneth
decomposition if its Chow motive $\h(X)$ has a Chow--K\"unneth
decomposition, that is, there exist correspondences $\pi^i \in \CH^d(X\times X)$
such that $\Delta_X = \sum_{i=0}^{2d} \pi^i$, with
$\pi^i \circ \pi^i = \pi^i$, $\pi^i \circ \pi^j = 0$ for $i \neq j$
and $\pi^i_*\HH^*(X,\Q) = \HH^i(X,\Q)$. A Chow--K\"unneth decomposition
$\{\pi^i, 0 \leq i \leq 2d\}$ of $X$ is said to be \emph{self-dual} if
$\pi^{2d-i} = {}^t\pi^i$ for all $i$.

If $\o$ is the class of a rational point on $X$ (or more generally a
zero-cycle of degree $1$ on $X$), then $\pi^0 := pr_1^*\o = \o \times
X$ and $\pi^{2d} = pr_2^*\o = X \times \o$ define mutually orthogonal
idempotents such that $\pi^0_*\HH^*(X,\Q) = \HH^0(X,\Q)$ and
$\pi^{2d}_*\HH^*(X,\Q) = \HH^{2d}(X,\Q)$.  Note that pairs of
idempotents with the property above are certainly not unique~: a
different choice (modulo rational equivalence) of zero-cycle of degree
$1$ gives different idempotents in the ring of correspondences
$\CH^d(X \times X)$. From the above, one sees that every curve $C$
admits a Chow--K\"unneth decomposition~: one defines $\pi^0$ and
$\pi^2$ as above and then $\pi^1$ is simply given by $\Delta_C - \pi^0
- \pi^2$. It is a theorem of Murre \cite{murre2} that every smooth
projective surface $S$ admits a Chow--K\"unneth decomposition
$\Delta_S = \pi_S^0 + \pi_S^1 + \pi_S^2 + \pi_S^3 + \pi_S^4$.

The notion of Chow--K\"unneth decomposition is significant because
when it exists it induces a filtration $\mathrm{F}^l\CH^i(X) :=
\bigoplus_{s\geq l}\CH^i(X)_s$ on the Chow group $\CH^*(X)$ which
should not depend on the choice of the Chow--K\"unneth decomposition
$\Delta_X = \sum_{i=0}^{2d} \pi^i$ and which should be of
Bloch--Beilinson type ;
\emph{cf.} \cite{jannsen, murre}. \\

Let now $S^{[n]}$ denote the Hilbert scheme of length-$n$ subschemes on a
smooth projective surface $S$. By Fogarty \cite{fogarty}, the scheme $S^{[n]}$
is in fact a
smooth projective variety, and it comes equipped with a morphism
$S^{[n]} \rightarrow S^{(n)}$ to the $n^\mathrm{th}$ symmetric product
of $S$, called the \emph{Hilbert--Chow morphism}.  De Cataldo and
Migliorini \cite{dCM} have given an explicit description of the motive
of $S^{[n]}$. Let us introduce some notations related to this
description. Let $\mu = \{A_1, \ldots, A_l\}$ be a partition of the
set $\{1,\ldots, n\}$, where all the $A_i$'s are non-empty. The
integer $l$, also denoted $l(\mu)$, is the \emph{length} of the
partition $\mu$. Let $S^\mu \simeq S^l \subseteq S^n$ be the
set $$\{(s_1,\ldots,s_n) : s_i = s_j \mbox{ if } i,j \in A_k \mbox{
  for some } k\}$$ and let $$\Gamma_\mu := (S^\mu \times_{S^{(n)}}
S^{[n]})_{red} \subset S^\mu \times S^{[n]},$$ where the subscript $red$ means
the  underlying
reduced scheme. It is known that $\Gamma_\mu$
is irreducible of dimension $n+l(\mu)$.  The subgroup
$\mathfrak{S}_\mu$ of $\mathfrak{S}_n$ that acts on $\{1,\ldots,n\}$
by permuting the $A_i$'s with same cardinality acts on the first
factor of the product $ S^\mu \times S^{[n]}$, and the correspondence
$\Gamma_\mu$ is invariant under this action. We can therefore
define $$\hat{\Gamma}_\mu := \Gamma_\mu / \mathfrak{S}_\mu \in
\CH^*(S^{(\mu)} \times S^{[n]}) = \CH^*(S^\mu \times
S^{[n]})^{\mathfrak{S}_\mu} ,$$ where $S^{(\mu)} :=
S^\mu/\mathfrak{S}_\mu$. Since for a variety $X$ endowed with the
action of a finite group $G$ we have $\CH^*(X/G) = \CH^*(X)^G$ (with
rational coefficients), the calculus of correspondences and the theory
of motives in the setting of smooth projective varieties endowed with
the action of a finite group is similar in every way to the usual case
of smooth projective varieties. We will therefore freely consider
actions of correspondences and motives of quotient varieties by the action of a
finite group.

The symmetric groups $\mathfrak{S}_n$ acts naturally on the set of partitions of
$\{1, \ldots, n\}$. By choosing one element in each orbit for the above action,
we may define a subset $\mathfrak{B}(n)$ of the set of partitions of $\{1,
\ldots, n\}$. This set is isomorphic to the set of partitions of the integer
$n$.

\begin{thm}[de Cataldo and Migliorini \cite{dCM}] \label{thm dcm}
Let $S$ be a smooth
  projective surface defined over an arbitrary field. The morphism
\begin{equation}
\label{eq dCM}
\bigoplus_{\mu \in \mathfrak{B}(n)} {}^t\hat{\Gamma}_\mu \ : \
\h(S^{[n]})
\stackrel{\simeq}{\longrightarrow} \bigoplus_{\mu \in \mathfrak{B}(n)}
\h(S^{(\mu)})(l(\mu)-n)
\end{equation}
is an isomorphism of Chow motives. Moreover, its inverse is given by
the correspondence $\sum_{\mu \in \mathfrak{B}(n)} \frac{1}{m_\mu}
\hat{\Gamma}_\mu$ for some non-zero rational numbers $m_\mu$.
\end{thm}

Let now $\Delta_S = \pi_S^0 + \pi_S^1 + \pi_S^2 + \pi_S^3 + \pi_S^4$
be a Chow--K\"unneth decomposition of $S$. For all non-negative integers $m$,
the correspondences
\begin{equation}
\label{eq CKSm}
\pi^i_{S^m} := \sum_{i_1+\ldots + i_m = i} \pi_S^{i_1} \otimes \cdots
\otimes \pi_S^{i_m} \quad \mbox{in } \CH^{2m}(S^m \times S^m)
\end{equation}
define a Chow--K\"unneth decomposition of $S^m$ that is clearly
$\mathfrak{S}_m$-equivariant. Therefore, these correspondences can be
seen as correspondences of $\CH^{2m}(S^{(m)} \times S^{(m)})$ and they
do define a Chow--K\"unneth decomposition of the $m^\mathrm{th}$
symmetric product $S^{(m)}$.  Let us denote this
decomposition $$\Delta_{S^{(m)}} = \pi^0_{S^{(m)}} + \cdots +
\pi^{4m}_{S^{(m)}} \quad \mbox{in } \CH^{2m}(S^{(m)} \times
S^{(m)}).$$ Since
$S^l$ is endowed with a $\mathfrak{S}_l$-equivariant
Chow--K\"unneth decomposition as above and since $\mathfrak{S}_\mu$ is
a subgroup of $\mathfrak{S}_l$, $S^\mu \simeq S^l$ is endowed with a
$\mathfrak{S}_\mu$-equivariant Chow--K\"unneth
decomposition. Therefore $S^{(\mu)}$ is endowed with a natural
Chow--K\"unneth decomposition $$\Delta_{S^{(\mu)}} = \pi^0_{S^{(\mu)}}
+ \cdots + \pi^{4l}_{S^{(\mu)}} \quad \mbox{in } \CH^{2l}(S^{(\mu)}
\times S^{(\mu)})$$ coming from that of $S$. In particular, the
isomorphism of de Cataldo and Migliorini gives a natural
Chow--K\"unneth decomposition for the Hilbert scheme $S^{[n]}$ coming
from that of $S$. Precisely, this Chow--K\"unneth decomposition is
given by
\begin{equation}
\label{eq CKhilb}
\pi_{S^{[n]}}^i = \sum_{\mu \in \mathfrak{B}(n)} \frac{1}{m_\mu}
\hat{\Gamma}_\mu
\circ \pi^{i-2n+2l(\mu)}_{S^{(\mu)}} \circ {}^t\hat{\Gamma}_\mu.
\end{equation}
Note that if the Chow--K\"unneth decomposition $\{\pi_S^i\}$ of $S$ is
self-dual, then the Chow--K\"unneth decomposition $\{\pi_{S^{[n]}}^i\}$ of
$S^{[n]}$ is also self-dual.

We will show that when $S$ is either a K3 surface or an abelian
surface the Chow--K\"unneth decomposition above induces a
decomposition of the motive $\h(S^{[n]})$ that satisfies the
conclusions of Theorem \ref{thm main} for an appropriate choice of
Chow--K\"unneth decomposition for $S$.

\section{Multiplicative Chow--K\"unneth decompositions} \label{sec mult}

Let $X$ be a smooth projective variety of dimension $d$ and let
$\Delta_3 \in \CH_d(X \times X \times X)$ be the small diagonal, that
is, the class of the subvariety $$\{(x,x,x) : x \in X\} \subset X
\times X \times X.$$ If we view $\Delta_3$ as a correspondence from $X
\times X$ to $X$, then $\Delta_3$ induces the \emph{multiplication
  morphism}
\begin{equation} \label{eq mult}
\h(X) \otimes \h(X) \rightarrow \h(X).
\end{equation}
Note that if $\alpha$ and $\beta$ are cycles in $\CH^*(X)$, then
$(\Delta_3)_*(\alpha \times \beta) = \alpha \cdot \beta$ in $\CH^*(X)$.

If $X$ admits a Chow--K\"unneth decomposition
\begin{equation}\label{eq ckh}
\h(X) = \bigoplus_{i=0}^{2d} \h^i(X),
\end{equation}
 then this decomposition is said to be
\emph{multiplicative} if the multiplication morphism $\h^i(X) \otimes
\h^j(X) \rightarrow \h(X)$ factors through $\h^{i+j}(X)$ for all $i$
and $j$. For a variety to be endowed with a multiplicative
Chow--K\"unneth decomposition is very restrictive ; we refer to
\cite{sv}, where this notion was introduced, for some
discussions. Examples of varieties admitting a multiplicative
Chow--K\"unneth decomposition are provided by \cite[Theorem 6]{sv} and
include hyperelliptic curves, K3 surfaces, abelian varieties, and their Hilbert
squares.

If one writes $\Delta_X = \pi_X^0 + \ldots + \pi_X^{2d}$ for the
Chow--K\"unneth decomposition \eqref{eq ckh} of $X$, then by definition this
decomposition is multiplicative if $$\pi_X^k \circ \Delta_3 \circ
(\pi_X^i \otimes \pi_X^j) = 0 \mbox{ in } \CH_d(X^3) \mbox{ for all }
k \neq i+j,$$ or equivalently if
$$({}^t\pi_X^i \otimes {}^t\pi_X^j \otimes \pi_X^k)_*\Delta_3 =  0
\mbox{ in } \CH_d(X^3) \mbox{ for all } k \neq i+j.$$
 If the Chow--K\"unneth decomposition $\{\pi_X^i\}$ is self-dual, then it is
multiplicative if
 $$(\pi_X^i \otimes \pi_X^j \otimes \pi_X^k)_*\Delta_3 =  0
 \mbox{ in } \CH_d(X^3) \mbox{ for all } i+j+k \neq 4d.$$
   Note that the
above three relations always hold modulo homological
equivalence.\medskip

Given a multiplicative Chow--K\"unneth decomposition $\pi^i_S$ for a
surface $S$, one could expect the Chow--K\"unneth decomposition
\eqref{eq CKhilb} of $S^{[n]}$ to be multiplicative. This was answered
affirmatively when $n=2$ for any smooth projective variety $X$ with a self-dual
Chow--K\"unneth decomposition (under some additional assumptions on the Chern
classes of $X$) in \cite{sv}, and a similar result when $n=3$ will appear in
\cite{sv2}. (For $n>3$, $X^{[n]}$ is no longer smooth if $X$ is smooth of
dimension $> 2$). Here we deal with the case when $S$ is a K3 surface or an
abelian surface and will prove Theorem \ref{thm main}. By the
isomorphism \eqref{eq dCM} of de Cataldo and Migliorini, it is enough
to check that
$$(\hat{\Gamma}_{\mu_1} \otimes \hat{\Gamma}_{\mu_2} \otimes
\hat{\Gamma}_{\mu_3})^* (\pi^i_{S^{[n]}} \otimes \pi^j_{S^{[n]}}
\otimes \pi^k_{S^{[n]}})_*\Delta_3 = 0$$ for all $i+j+k \neq 8n$ and
for all partitions $\mu_1, \mu_2$ and $\mu_3$ of $\{1,\ldots,n\}$, or
equivalently for all $i,j,k$ such that $(\pi^i_{S^{[n]}} \otimes
\pi^j_{S^{[n]}} \otimes \pi^k_{S^{[n]}})_*[\Delta_3] = 0$ in
$\HH^*(S^{[n]} \times S^{[n]} \times S^{[n]}, \Q)$ and all partitions
$\mu_1, \mu_2$ and $\mu_3$. By \eqref{eq CKhilb}, it is even enough to
show that
\begin{equation} \label{eq 1} \left(\hat{\Gamma}_{\mu_1} \otimes
    \hat{\Gamma}_{\mu_2} \otimes \hat{\Gamma}_{\mu_3}\right)^* \left(
    \left(\hat{\Gamma}_{\nu_1} \circ \pi^i_{S^{(\nu_1)}} \circ
      {}^t\hat{\Gamma}_{\nu_1} \right) \otimes
    \left(\hat{\Gamma}_{\nu_2} \circ \pi^j_{S^{(\nu_2)}} \circ
      {}^t\hat{\Gamma}_{\nu_2} \right) \otimes
    \left(\hat{\Gamma}_{\nu_3} \circ \pi^k_{S^{(\nu_3)}} \circ
      {}^t\hat{\Gamma}_{\nu_3} \right) \right)_* \Delta_3
\end{equation}
is zero in $\CH^*(S^{(\mu_1)} \times S^{(\mu_2)} \times S^{(\mu_3)})$
for all partitions $\mu_1, \mu_2, \mu_3$, and all partitions $\nu_1,
\nu_2, \nu_3$ and all $i,j,k$ such that
$$ \left( \left(\hat{\Gamma}_{\nu_1} \circ \pi^i_{S^{(\nu_1)}} \circ
    {}^t\hat{\Gamma}_{\nu_1} \right) \otimes
  \left(\hat{\Gamma}_{\nu_2} \circ \pi^j_{S^{(\nu_2)}} \circ
    {}^t\hat{\Gamma}_{\nu_2} \right) \otimes
  \left(\hat{\Gamma}_{\nu_3} \circ \pi^k_{S^{(\nu_3)}} \circ
    {}^t\hat{\Gamma}_{\nu_3} \right) \right)_* [\Delta_3] =0 \mbox{ in
} \HH^*((S^{[n]})^3,\Q).$$ Note that the expression \eqref{eq 1} is
equal to
$$ \left[ \left( {}^t\hat{\Gamma}_{\mu_1} \otimes
    {}^t\hat{\Gamma}_{\mu_2} \otimes {}^t\hat{\Gamma}_{\mu_3} \right)
  \circ \left( \hat{\Gamma}_{\nu_1} \otimes \hat{\Gamma}_{\nu_2}
    \otimes \hat{\Gamma}_{\nu_3} \right) \circ \left(
    \pi^i_{S^{(\nu_1)}} \otimes \pi^j_{S^{(\nu_2)}}
    \otimes\pi^k_{S^{(\nu_3)}} \right) \circ \left(
    {}^t\hat{\Gamma}_{\nu_1} \otimes {}^t\hat{\Gamma}_{\nu_2} \otimes
    {}^t\hat{\Gamma}_{\nu_3} \right) \right]_*\Delta_3.$$
    But it is clear from Theorem \ref{thm dcm} that
$$\left( {}^t\hat{\Gamma}_{\mu_1} \otimes  {}^t\hat{\Gamma}_{\mu_2}
  \otimes {}^t\hat{\Gamma}_{\mu_3} \right) \circ \left(
  \hat{\Gamma}_{\nu_1} \otimes \hat{\Gamma}_{\nu_2} \otimes
  \hat{\Gamma}_{\nu_3} \right) = \left\{
  \begin{array}{lr}
    0 & \mbox{if} \ (\nu_1,\nu_2,\nu_3) \neq (\mu_1,\mu_2,\mu_3)\\
    m_{\mu_1} m_{\mu_2} m_{\mu_3} \, \Delta_{S^{(\mu_1)} \times
      S^{(\mu_2)}
      \times S^{(\mu_3)}} & \mbox{if} \ (\nu_1,\nu_2,\nu_3)
    = (\mu_1,\mu_2,\mu_3).
  \end{array}
\right. $$ Thus we have proved the following criterion for the
Chow--K\"unneth decomposition \eqref{eq CKhilb} to be multiplicative~:

\begin{prop} \label{prop reduction} The Chow--K\"unneth decomposition
  \eqref{eq CKhilb} is multiplicative (equivalently, the motive of
  $S^{[n]}$ splits as in Theorem \ref{thm main}) if for all partitions
  $\mu_1, \mu_2$ and $\mu_3$ of the set $\{1,\ldots,n\}$ $$\left(
    \pi^i_{S^{\mu_1}} \otimes \pi^j_{S^{\mu_2}}
    \otimes\pi^k_{S^{\mu_3}} \right)_* \left({\Gamma}_{\mu_1} \otimes
    {\Gamma}_{\mu_2} \otimes {\Gamma}_{\mu_3} \right)^*\Delta_3 = 0
  \mbox{ in } \CH^*(S^{\mu_1} \times S^{\mu_2} \times S^{\mu_3})$$ as
  soon as $$\left( \pi^i_{S^{\mu_1}} \otimes \pi^j_{S^{\mu_2}}
    \otimes\pi^k_{S^{\mu_3}} \right)_* \left({\Gamma}_{\mu_1} \otimes
    {\Gamma}_{\mu_2} \otimes {\Gamma}_{\mu_3} \right)^*[\Delta_3] = 0
  \mbox{ in } \HH^*(S^{\mu_1} \times S^{\mu_2} \times S^{\mu_3},\Q). $$
  \vspace{-18pt}

  \qed
\end{prop}

\section{Proof of Theorem \ref{thm main} and Theorem \ref{thm bigrading}}

The proof is inspired by the
proof of Claire Voisin's \cite[Theorem 5.1]{voisin diag}. In fact,  because of
\cite[Proposition 8.12]{sv}, Theorem \ref{thm main} for K3 surfaces implies
\cite[Theorem 5.1]{voisin diag}. The first
step towards the proof of Theorem \ref{thm main} is to understand the
cycle $\left({\Gamma}_{\mu_1} \otimes {\Gamma}_{\mu_2} \otimes
  {\Gamma}_{\mu_3} \right)^*\Delta_3$. The following proposition, due
to Voisin \cite{voisin diag} (see also \cite{voisin2}), builds on the
work of Ellingsrud, G\"ottsche and Lehn \cite{egl}. Here, $S$ is a
smooth projective surface and $\Delta_k$ is the class of the small
diagonal inside $S^k$ in $\CH_2(S^k)$.

\begin{prop} [Voisin, Proposition 5.6 in \cite{voisin diag}] \label{prop voisin}

For any set of partitions $\boldsymbol\mu :=
  \{\mu_1,\ldots,\mu_k \}$ of $\{1,\ldots,n\}$, there exists a
  universal (i.e., independent of $S$) polynomial $P_{\boldsymbol\mu}$
  with the following property~:
$$({\Gamma}_{\mu_1} \otimes \ldots \otimes {\Gamma}_{\mu_k})^*\Delta_k
= P_{\boldsymbol\mu}(pr_r^*c_2(S), pr_{r'}^*K_S, pr_{s,t}^*\Delta_S)
\quad \mbox{in} \ \CH^*(S^{\boldsymbol\mu}),$$ where the $pr_r$'s are
the projections from $S^{\boldsymbol\mu} := \prod_i S^{\mu_i} \simeq
S^N$ to its factors, and the $pr_{s,t}$'s are the projections from
$S^{\boldsymbol\mu}$ to the products of two of its factors. \qed
\end{prop}

In fact, Proposition \ref{prop voisin} is a particular instance of \cite[Theorem
5.12]{voisin diag}. Another consequence of  \cite[Theorem 5.12]{voisin diag},
which will be used to prove Theorem \ref{thm bigrading}, is

\begin{prop} [Voisin] \label{prop voisin2}
    For any partition $\mu$ of $\{1,\ldots,n\}$ and any polynomial $P$ in the
Chern classes of $S^{[n]}$, the cycle $(\Gamma_\mu)^*P$ of $S^\mu$ is a
      universal (i.e., independent of $S$) polynomial in the variables
$pr_r^*c_2(S), pr_{r'}^*K_S, pr_{s,t}^*\Delta_S$,  where the $pr_r$'s are
    the projections from $S^\mu\simeq
    S^N$ to its factors, and the $pr_{s,t}$'s are the projections from
    $S^{\mu}$ to the products of two of its factors. \qed
\end{prop}

We first prove Theorems \ref{thm main} \& \ref{thm bigrading} for $S$ a K3
surface and then
for $S$ an abelian surface. Note that clearly a multiplicative Chow--K\"unneth
decomposition $\{\pi^i_{S^{[n]}}, 0\leq i \leq 4n\}$ induces a multiplicative
bigrading on the  Chow ring $\CH^*(S^{[n]})$ :
 $$\CH^*(S^{[n]}) = \bigoplus_{i,s} \CH^i(S^{[n]})_s, \quad \mbox{where }
\CH^i(S^{[n]})_s = (\pi^{2i-s}_{S^{[n]}})_*\CH^i(S^{[n]}).$$
Thus once Theorem \ref{thm main} is established it only remains to show that the
Chern classes of $S^{[n]}$ sit in $\CH^*(S^{[n]})_0$ in order to conclude.

\subsection{The Hilbert scheme of points on a K3 surface} Let $S$ be a
smooth projective surface and let $\o$ be a zero-cycle of degree $1$
on $S$.  Let $m$ be a positive integer and consider the $m$-fold
product $S^m$ of $S$. Let us define the idempotent
correspondences
\begin{equation} \label{eq CK surface}
\pi_S^0 := pr_1^*\o = \o \times S, \quad \pi_S^{4} =
pr_2^*\o = S \times \o, \quad \mbox{and} \quad \pi_S^2 := \Delta_S -
\pi_S^0-\pi_S^4.
\end{equation}
(Note that $\pi^2_S$ is not quite a Chow--K\"unneth projector, it projects onto
$\HH^1(S,\Q) \oplus \HH^2(S,\Q) \oplus \HH^3(S,\Q)$.)
 In this case, the idempotents $\pi_{S^m}^i :=
\sum_{i_1+\ldots + i_n = i} \pi_S^{i_1} \otimes \cdots \otimes
\pi_S^{i_n}$ given in \eqref{eq CKSm} are clearly sums of monomials of
degree $2m$ in $pr_r^*\o$ and $pr_{s,t}^*\Delta_S$. By Proposition
\ref{prop voisin}, it follows that for any smooth projective surface
$S$ and any zero-cycle $\o$ of degree $1$ on $S$
$$\left( \pi^i_{S^{\mu_1}} \otimes \pi^j_{S^{\mu_2}}
  \otimes\pi^k_{S^{\mu_3}} \right)_* \left({\Gamma}_{\mu_1} \otimes
  {\Gamma}_{\mu_2} \otimes {\Gamma}_{\mu_3} \right)^*\Delta_3$$ is a
polynomial $Q_{\boldsymbol \mu, i, j, k}$ in the variables
$pr_r^*c_2(S), pr_{r'}^*K_S, pr_{r''}^*\o$ and $pr_{s,t}^*\Delta_S$.

We now have the following key result which is due to Claire Voisin
\cite[Corollary 5.9]{voisin diag} and which relies in an essential way
on a theorem due to Qizheng Yin \cite{yin} that describes the
cohomological relations among the cycles $pr_{r,s}^*\pi^2_S$.
\begin{prop}[Voisin \cite{voisin diag}] \label{prop key} For all
  smooth projective surfaces $S$ and any degree-$1$ zero-cycle $\o$ on
  $S$, let $P$ be a polynomial (independent of $S$) in the variables
  $pr_r^*[c_2(S)]$, $pr_{r'}^*[K_S], pr_{r''}^*[\o]$ and
  $pr_{s,t}^*[\Delta_S]$ with value an algebraic cycle of $S^n$. If $P$ vanishes
for all smooth projective
  surfaces with $b_1(S)=0$, then the polynomial $P$ belongs to the
  ideal generated by the relations :
\begin{enumerate}[(a)]
\item $[c_2(S)] = \chi_{top}(S)[\o]$ ;
\item $[K_S]^2 = \deg(K_S^2) [\o]$ ;
\item $[\Delta_S] \cdot pr_1^*[K_S] = pr_1^*[K_S] \cdot pr_2^*[\o] +
  pr_1^*[\o] \cdot pr_2^*[K_S]$ ;
\item $[\Delta_3] = pr_{1,2}^*[\Delta_S]\cdot pr_3^*[\o] +
  pr_{1,3}^*[\Delta_S]\cdot pr_2^*[\o] + pr_{2,3}^*[\Delta_S]\cdot
  pr_1^*[\o] - pr_1^*[\o]\cdot pr_2^*[\o] - pr_1^*[\o]\cdot pr_3^*[\o]
  - pr_2^*[\o]\cdot pr_3^*[\o]$ ;
\item $[\Delta_S]^2 = \chi_{top}(S)\, pr_1^*[\o]\cdot pr_2^*[\o]$ ;
\item $[\Delta_S]\cdot pr_1^*[\o] = pr_1^*[\o]\cdot pr_2^*[\o]$. \qed
\end{enumerate}
\end{prop}

We may then specialize to the case where $S$ is a K3 surface.
Consider then a K3 surface $S$ and let $\o$ be the class of a point
lying on a rational curve of $S$.  Note that by definition of a K3 surface
$K_S=0$. The following theorem of Beauville and Voisin shows that the
relations (a)--(f) listed above actually hold modulo rational
equivalence.
\begin{thm}[Beauville--Voisin \cite{bv}] \label{thm bv} Let $S$ be a
  K3 surface and let $\o$ be a rational point lying on a rational
  curve on $S$. The following relations hold :
 \begin{enumerate}[(i)]
\item $c_2(S) = \chi_{top}(S) \o \ (=24\o)$ in $\CH^2(S)$ ;
\item $\Delta_3 = pr_{1,2}^*\Delta_S\cdot pr_3^*\o +
  pr_{1,3}^*\Delta_S\cdot pr_2^*\o + pr_{2,3}^*\Delta_S\cdot pr_1^*\o
  - pr_1^*\o\cdot pr_2^*\o - pr_1^*\o\cdot pr_3^*\o - pr_2^*\o\cdot
  pr_3^*\o$ in $\CH_2(S \times S \times S)$.
 \end{enumerate}
 \end{thm}

 The proof of Theorem \ref{thm main} in the case when $S$ is a K3
 surface is then immediate~: by the discussion above if the cycle
 $\delta:= \left( \pi^i_{S^{\mu_1}} \otimes \pi^j_{S^{\mu_2}}
   \otimes\pi^k_{S^{\mu_3}} \right)_* \left({\Gamma}_{\mu_1} \otimes
   {\Gamma}_{\mu_2} \otimes {\Gamma}_{\mu_3} \right)^*\Delta_3$ is
 zero in $\HH^*(S^{\mu_1} \times S^{\mu_2} \times S^{\mu_3},\Q)$, then by
 Proposition \ref{prop key} it belongs to the ideal generated by the
 relations (a)--(f). By Theorem \ref{thm bv}, the relations (a)--(f)
 actually hold modulo rational equivalence. Therefore, the cycle
 $\delta$ is zero in $\CH^*(S^{\mu_1} \times S^{\mu_2} \times S^{\mu_3})$. We
 may then conclude by invoking Proposition \ref{prop reduction}.

 It remains to prove that the Chern classes $c_i(S^{[n]})$ sit in
$\CH^{i}(S^{[n]})_0$. It suffices to show that $(\pi^j_{S^{[n]}})_*c_i(S^{[n]})
= 0$ in $\CH^i(S^{[n]})$ as soon as $(\pi^j_{S^{[n]}})_*[c_i(S^{[n]})] = 0$ in
$\HH^{2i}(S^{[n]},\Q)$ (equivalently as soon as $j \neq 2i$).
 By de Cataldo and Migliorini's theorem, it is enough to show for all partitions
$\mu$ of $\{1,\ldots,n\}$ that $(\Gamma_\mu)^*(\pi^j_{S^{[n]}})_*c_i(S^{[n]}) =
0$ in $\CH^*(S^{\mu})$ as soon as
$(\Gamma_\mu)^*(\pi^j_{S^{[n]}})_*[c_i(S^{[n]})] = 0$ in $\HH^{*}(S^{\mu},\Q)$.
  Proceeding as in section \ref{sec mult}, it is even enough to show that, for
all  partitions $\mu$ of $\{1,\ldots,n\}$,
$(\pi^j_{S^{\mu}})_*(\Gamma_\mu)^*c_i(S^{[n]}) = 0$ in $\CH^*(S^{\mu})$ as soon
as $(\pi^j_{S^{\mu}})_*(\Gamma_\mu)^*[c_i(S^{[n]})] = 0$ in
$\HH^{*}(S^{\mu},\Q)$.

   By Proposition \ref{prop voisin2}, $(\Gamma_\mu)^*c_i(S^{[n]})$ is a
universal polynomial in the variables $pr_r^*c_2(S), pr_{r'}^*K_S,
pr_{s,t}^*\Delta_S$. It follows that
$(\pi^j_{S^{\mu}})_*(\Gamma_\mu)^*c_i(S^{[n]})$ is also a universal polynomial
in the variables $pr_r^*c_2(S), pr_{r'}^*K_S, pr_{s,t}^*\Delta_S$.
   We can then conclude thanks to Proposition \ref{prop key} and Theorem
\ref{thm bv}.  \qed

\subsection{The Hilbert scheme of points on an abelian surface}
Let $A$ be an abelian surface. In that case, the Chow--K\"unneth
projectors $\{\pi_A^i\}$ given by the theorem of Deninger and Murre are
\emph{symmetrically distinguished} in the Chow ring $\CH^*(A \times A)$ in
the sense of O'Sullivan \cite{o'sullivan}. (We refer to \cite[Section 7]{sv} for
a summary of O'Sullivan's theory of symmetrically distinguished cycles on
abelian varieties.) Let us mention that the identity element $O_A$ of $A$ plays
the role of the Beauville--Voisin cycle $\o$ in the case of K3 surfaces,
\emph{e.g.} $\pi^0_A = O_A \times A$.
By O'Sullivan's theorem, the Chow--K\"unneth projectors $\pi^i_{A^m}$ given in
\eqref{eq CKSm} are symmetrically distinguished  for all positive
integers $m$. By Proposition
\ref{prop voisin}, the cycle $\left({\Gamma}_{\mu_1} \otimes
  {\Gamma}_{\mu_2} \otimes {\Gamma}_{\mu_3} \right)^*\Delta_3$ is a
polynomial in the variables $pr_r^*c_2(A)$, $pr_{r'}^*K_A $ and
$pr_{s,t}^*\Delta_A$. Since $c_2(A) = 0 $ and $ K_A=0$, this cycle is
in fact symmetrically distinguished. It immediately follows
that $$\left( \pi^i_{A^{\mu_1}} \otimes \pi^j_{A^{\mu_2}}
  \otimes\pi^k_{A^{\mu_3}} \right)_* \left({\Gamma}_{\mu_1} \otimes
  {\Gamma}_{\mu_2} \otimes {\Gamma}_{\mu_3} \right)^*\Delta_3$$ is
symmetrically distinguished. Thus by O'Sullivan's theorem
\cite{o'sullivan}, this cycle is rationally trivial if and only if it
is numerically trivial. By Proposition \ref{prop reduction}, we
conclude that $A^{[n]}$ has a multiplicative Chow--K\"unneth
decomposition. The proof of Theorem \ref{thm main} is now
complete.

 It remains to prove that the Chern classes $c_i(A^{[n]})$ sit in
$\CH^{i}(A^{[n]})_0$. As in the case of K3 surfaces, it suffices to show that,
for all  partitions $\mu$ of $\{1,\ldots,n\}$,
$(\pi^j_{A^{\mu}})_*(\Gamma_\mu)^*c_i(A^{[n]}) = 0$ in $\CH^*(A^{\mu})$ as soon
as $(\pi^j_{A^{\mu}})_*(\Gamma_\mu)^*[c_i(A^{[n]})] = 0$ in
$\HH^{*}(A^{\mu},\Q)$.
By Proposition \ref{prop voisin2}, $(\Gamma_\mu)^*c_i(A^{[n]})$ is a
polynomial in the variables $pr_r^*c_2(A) = 0, pr_{r'}^*K_A = 0,
pr_{s,t}^*\Delta_A$. It follows that the cycle
$(\pi^j_{A^{\mu}})_*(\Gamma_\mu)^*c_i(A^{[n]})$ is symmetrically distinguished.
    We can then conclude thanks to O'Sullivan's theorem.  \qed

\section{Decomposition theorems for the relative Hilbert scheme of
  abelian surface schemes and of families of K3 surfaces}

In this section, we generalize Voisin's decomposition theorem
\cite[Theorem 0.7]{voisin k3} for families of K3 surfaces to families
of Hilbert schemes of points on K3 surfaces or abelian surfaces.

Let $\pi : \mathcal{X} \rightarrow B$ be a smooth projective
morphism. Deligne's decomposition theorem states the following~:
\begin{thm}[Deligne \cite{deligne}]
  In the derived category of sheaves of $\Q$-vector spaces on $B$,
  there is a decomposition (which is non-canonical in general)
\begin{equation} \label{eq deligne}
R\pi_*\Q \cong \bigoplus_i R^i\pi_*\Q[-i].
\end{equation}
\end{thm}
Both sides of \eqref{eq deligne} carry a cup-product~: on the
right-hand side the cup-product is the direct sum of the usual
cup-products $R^i\pi_*\Q \otimes R^j\pi_*\Q \rightarrow R^{i+j}\pi_*\Q
$ defined on local systems, while on the left-hand side the derived
cup-product $R\pi_*\Q \otimes R\pi_*\Q \rightarrow R\pi_*\Q $ is such
that it induces the usual cup-product in cohomology. As explained in
\cite{voisin k3}, the isomorphism \eqref{eq deligne} does not respect
the cup-product in general. Given a family of smooth projective
varieties $\pi : \mathcal{X} \rightarrow B$, Voisin \cite[Question
0.2]{voisin k3} asked if there exists a decomposition as in \eqref{eq
  deligne} which is multiplicative, \emph{i.e.}, which is compatible
with cup-product. By Deninger--Murre \cite{dm}, there does exist such
a decomposition for an abelian scheme $\pi : \mathcal{A} \rightarrow
B$. The main result of \cite{voisin k3} is~:

\begin{thm}[Voisin \cite{voisin k3}] \label{thm dec voisin} For any
  smooth projective family $\pi : \mathcal{X} \rightarrow B$ of K3
  surfaces, there exist a decomposition isomorphism as in \eqref{eq
    deligne} and a nonempty Zariski open subset $U$ of $B$, such that
  this decomposition becomes multiplicative for the restricted family
  $\pi|_U : \mathcal{X}|_U \rightarrow U$.
\end{thm}

Our main result in this section is the following extension of Theorem
\ref{thm dec voisin}~:
\begin{thm} \label{thm dec} Let $\pi : \mathcal{X} \rightarrow B$ be
  either an abelian surface over $B$ or a smooth projective family of
  K3 surfaces. Consider $\pi^{[n]} : \mathcal{X}^{[n]} \rightarrow B$
  the relative Hilbert scheme of length-$n$ subschemes on $\mathcal{X}
  \rightarrow B$. Then there exist a decomposition isomorphism for
  $\pi^{[n]} : \mathcal{X}^{[n]} \rightarrow B$ as in \eqref{eq
    deligne} and a nonempty Zariski open subset $U$ of $B$, such that
  this decomposition becomes multiplicative for the restricted family
  $\pi^{[n]}|_U : \mathcal{X}^{[n]}|_U \rightarrow U$.
\end{thm}
\begin{proof}
The proof follows the original approach of Voisin \cite{voisin k3} (after
reinterpreting, as in \cite[Proposition 8.14]{sv}, the vanishing of the modified
diagonal cycle of Beauville--Voisin \cite{bv} as the multiplicativity of the
Beauville--Voisin Chow--K\"unneth decomposition).

  First, we note that there exist a nonempty Zariski open subset $U$
  of $B$ and relative Chow--K\"unneth projectors $\Pi^i :=
  \Pi^i_{\mathcal{X}^{[n]}|_U/U} \in \CH^{2n}(\mathcal{X}^{[n]}|_U
  \times_U \mathcal{X}^{[n]}|_U)$, which means that
  $\Delta_{\mathcal{X}|_U/U} = \sum_i \Pi^i$, $\Pi^i \circ \Pi^i =
  \Pi^i$, $\Pi^i \circ \Pi^j = 0$ for $i\neq j$, and $\Pi^i$ acts as
  the identity on $R^i(\pi^{[n]}|_U)_*\Q$ and as zero on
  $R^j(\pi^{[n]}|_U)_*\Q$ for $j\neq i$. Indeed, Let $X$ be the
  generic fiber of $\pi : \mathcal{X} \rightarrow B$. If $X$ is a K3
  surface, then we consider the degree $1$ zero-cycle $\o :=
  \frac{1}{24} c_2(X) \in \CH_0(X)$. We then have a Chow--K\"unneth
  decomposition for $X$ given by $\pi^0_X := pr_1^*\o, \pi^4_X :=
  pr_2^*\o$ and $\pi_X^2 := \Delta_X - \pi_X^0 - \pi_X^4$. If $X$ is
  an abelian surface, we may consider the Chow--K\"unneth
  decomposition of Deninger--Murre \cite{dm}. In both cases, these
  Chow--K\"unneth decompositions induce as in \eqref{eq CKhilb} a
  Chow--K\"unneth decomposition $\Delta_{X^{[n]}} = \sum_i
  \pi^i_{X^{[n]}}$ of the Hilbert scheme of points $X^{[n]}$. By
  spreading out, we obtain the existence of a sufficiently small but
  nonempty open subset $U$ of $B$ such that this Chow--K\"unneth
  decomposition spreads out to a relative Chow--K\"unneth
  decomposition $\Delta_{\mathcal{X}|_U/U} = \sum_i \Pi^i$.

  By \cite[Lemma 2.1]{voisin k3}, the relative idempotents $\Pi^i$
  induce a decomposition in the derived category $R\pi_*\Q \cong
  \bigoplus_{i=0}^{4n} \HH^i(R\pi_*\Q)[-i] = \bigoplus_{i=0}^{4n}
  R^i\pi_*\Q[-i]$ with the property that $\Pi^i$ acts as the identity
  on the summand $\HH^i(R\pi_*\Q)[-i]$ and acts as zero on the
  summands $\HH^j(R\pi_*\Q)[-j]$ for $j \neq i$.  Thus, in order to
  show the existence of a decomposition as in \eqref{eq deligne} that
  is multiplicative, it is enough to show, up to further shrinking
  $U$ if necessary, that the relative Chow--K\"unneth decomposition $\{\Pi^i\}$
above
  satisfies
  \begin{equation} \label{eq multderived} \Pi^k \circ \Delta_3 \circ
    (\Pi^i \otimes \Pi^j) = 0 \quad \mbox{in} \
    \CH^{4n}((\mathcal{X}^{[n]} \times_B \mathcal{X}^{[n]} \times_B
    \mathcal{X}^{[n]})|_U) \quad \mbox{for all} \ k\neq i+j.
\end{equation}
Here, $\Delta_3$ is the class of the relative small diagonal inside
$\CH^{4n}(\mathcal{X}^{[n]} \times_B \mathcal{X}^{[n]} \times_B
\mathcal{X}^{[n]})$. But then, by Theorem \ref{thm main}, the relation
\eqref{eq multderived} holds generically. Therefore, by spreading out,
\eqref{eq multderived} holds over a nonempty open subset of $B$. This
concludes the proof of the theorem.
\end{proof}

config: arxiv


TITLE: Set inclusion question
QUESTION [1 upvotes]: Suppose I want to show ${\{\begin{bmatrix} 1 \\ 2 \\ 0  \end{bmatrix}\}\ ^{\perp}=span\{{\begin{bmatrix} 2 \\ -1 \\ 0  \end{bmatrix},\begin{bmatrix} 0 \\ 0 \\ 1  \end{bmatrix}\\}}\}$
If I do this with set inclusions, for the forward direction I would start with $x\in \{\begin{bmatrix} 1 \\ 2 \\ 0  \end{bmatrix}\}\ ^{\perp}$, and by definition,only  $\begin{bmatrix} 0 \\ 0 \\ a \end{bmatrix}$ and $\begin{bmatrix} 2b \\ -b \\ 0 \end{bmatrix}$ would be in $\{\begin{bmatrix} 1 \\ 2 \\ 0  \end{bmatrix}\}\ ^{\perp}$ because their inner product with $\{\begin{bmatrix} 1 \\ 2 \\ 0  \end{bmatrix}\}$ is $0$, and so it is the span of of the right hand side. My question is, how do I do the inclusion formally? Like starting from $x\in \{\begin{bmatrix} 1 \\ 2 \\ 0  \end{bmatrix}\}\ ^{\perp}$ and ending at $x \in span\{{\begin{bmatrix} 2 \\ -1 \\ 0  \end{bmatrix},\begin{bmatrix} 0 \\ 0 \\ 1  \end{bmatrix}\\}\}$? I have no clue when dealing the above with an  "$x$"

REPLY [1 votes]: Let $a= \begin{bmatrix} 1 \\ 2 \\ 0  \end{bmatrix}$, $b= \begin{bmatrix} 2 \\ -1 \\ 0  \end{bmatrix}$ and  $c=\begin{bmatrix} 0 \\ 0 \\ 1  \end{bmatrix}$
$V:=\{\begin{bmatrix} 1 \\ 2 \\ 0  \end{bmatrix}\} ^{\perp} $ and $ U:={span\{{\begin{bmatrix} 2 \\ -1 \\ 0  \end{bmatrix},\begin{bmatrix} 0 \\ 0 \\ 1  \end{bmatrix}\\}}\}$

Now,take any $x\in V$ then $x= m\cdot a$ so: $$\langle x,b\rangle  = m\langle a,b\rangle =0$$ and $$\langle x,c\rangle  = m\langle a,c\rangle =0$$ so $x\in U$ and thus $\boxed{V\subseteq U}$.

For converse, take any $x\in U$, then $x= m\cdot b+n\cdot c$ and we have $$\langle a,x\rangle  = m\langle a,b\rangle +n\langle a,c\rangle  = 0$$  so $x\in V$ and thus $\boxed {U\subseteq V}$ and so $U=V$.


TITLE: Log-likelihood function
QUESTION [5 upvotes]: I'm not sure if this could be asked here, or in math overflow...
In the following paper

Cho, Jin Seo, and Halbert White. "Testing for regime switching." Econometrica 75.6 (2007): 1671-1720. doi: 10.1111/j.1468-0262.2007.00809.x

on page 1675, there is the following formula:
$$ \log(P(X_1,\dots,X_n))= \log\left(\boldsymbol{\pi}'\cdot \prod^n_{i=1} P F_i(\theta)\cdot \mathbf{1}\right)$$
The $\lbrace X_i\rbrace$ is a hidden Markov chain, where the $\lbrace S_i\rbrace$ is the Markov chain associated with it.
How do I prove it?
$$\displaystyle P(X_2|X_1)=E(P(X_2|X_1,S_1,S_2))=E(E(P(X_2|X_1,S_1,S_2)|S_1))$$
$$=E(F(X_2|X_1,S_1,\theta_1)\cdot p_{i1}+F(X_2|X_1,S_1,\theta_2)\cdot p_{i2})$$
$$\displaystyle =\sum^2_{i=1}\left(F(X_2|X_1,S_1,\theta_1)\cdot p_{i1}+F(X_2|X_1,S_1,\theta_2)\cdot p_{i2} \right)\cdot P(S_1=i)=\boldsymbol{\pi}'\cdot \boldsymbol{PF}_2(\theta)\cdot \mathbf{1}$$
where $(P(S_1=1)P(S_1=2))= \boldsymbol{\pi}'$, $\boldsymbol{P}$ is the 2x2 transition matrix as in the paper. \
Using a analogous reasoning we get:
$$P(X_n|X_{n-1},\dots,X_1)=E(E(P(X_n|X_{n-1},\dots,X_1,S_{n-1},S_n)|S_{n-1}))$$
$$=(P(S_{n-1}=1)P(S_{n-1}=2))'\cdot \boldsymbol{PF}_n(\theta)\cdot \mathbf{1}=\boldsymbol{\pi}'\cdot \boldsymbol{P}^{n-1} \boldsymbol{F}_n(\theta)\cdot \mathbf{1}$$
Also, we have:
$$P(X_2,\dots,X_n|X_1)=P(X_n|X_{n-1},\dots,X_1)\cdot P(X_{n-1}|X_{n-2},\dots,X_1)\cdot \dots \cdot P(X_2|X_1) $$
$$\displaystyle Log(P(X_2,\dots,X_n|X_1)= Log( \prod^{n}_{i=1}\boldsymbol{\pi}'\cdot \boldsymbol{P}^{i-1} \boldsymbol{F}_i(\theta)\cdot \mathbf{1})$$
Which is,however, different from what is on the paper:
$$\displaystyle Log(P(X_2,\dots,X_n|X_1)= Log(\boldsymbol{\pi}'\cdot \prod^n_{i=1} \boldsymbol{P F}_i\cdot \mathbf{1})$$
So, where have I gone wrong?

REPLY [3 votes]: Copying my answer from MO... There is an improper marginalization in the equation that defines your overall strategy:
$$P(X_2,\dots,X_n|X_1)=P(X_n|X_{n-1},\dots,X_1)\cdot P(X_{n-1}|X_{n-2},\dots,X_1)\cdot \dots \cdot P(X_2|X_1)?$$
For simplicity, take $n=3$:
$$P(X_2,X_3|X_1)=P(X_3|X_2,X_1) \cdot P(X_2|X_1)?$$
Now remember that each $P$ above is really a marginal over the $S_i$:
Now remember that each $P$ above is really a marginal over the $S_i$:
$$\sum_{S_1,S_2,S_3}P(X_2,X_3,S_1,S_2,S_3|X_1)=\sum_{S_1,S_2,S_3}P(X_3, S_1,S_2,S_3|X_2,X_1) \cdot \sum_{S_1',S_2',S_3'}P(X_2,S_1',S_2',S_3'|X_1)?$$
But that's not right. Applying the definition of $P(X_2,X_3|X_1)$ gives us only a single summation on the right side:
$$\sum_{S_1,S_2,S_3}P(X_2,X_3,S_1,S_2,S_3|X_1)=\sum_{S_1,S_2,S_3}P(X_3, S_1,S_2,S_3|X_2,X_1) \cdot P(X_2,S_1,S_2,S_3|X_1).$$
More to the point, we can apply similar reasoning to $P(X_1,X_2,X_3)$, eventually getting:
$$P(X_1,X_2,X_3)=\sum_{S_1,S_2,S_3}P(X_3|S_3)P(S_3|S_2)P(X_2|S_2)P(S_2|S_1)P(X_1|S_1)P(S_1).$$
CAVEAT: In the above equation and what follows, I assume that the $X_t$ are conditionally independent given $S_t$. This assumption makes the formulas more compact, but it isn't essential. To revoke the assumption, just replace $P(X_2|S_2)$ with $P(X_2|X_1,S_2)$ and so on.
And that's the matrix product given in the article! To build up the product manually, work from right to left:
$$P(S_1)
=\left(\begin{array}{c}P(S_1=1)\\P(S_1=2)\end{array}\right)
=\boldsymbol{\pi}
=\boldsymbol{P}'\boldsymbol{\pi}$$
$$P(X_1|S_1)P(S_1)=\boldsymbol{F}_1\boldsymbol{P}'\boldsymbol{\pi}$$
$$\sum_{S_1}P(S_2|S_1)P(X_1|S_1)P(S_1)=\boldsymbol{P}'\boldsymbol{F}_1\boldsymbol{P}'\boldsymbol{\pi}$$
$$\sum_{S_1}P(X_2|S_2)P(S_2|S_1)P(X_1|S_1)P(S_1)=\boldsymbol{F}_2\boldsymbol{P}'\boldsymbol{F}_1\boldsymbol{P}'\boldsymbol{\pi}$$
$$\sum_{S_1,S_2}P(S_3|S_2)P(X_2|S_2)P(S_2|S_1)P(X_1|S_1)P(S_1)=\boldsymbol{P}'\boldsymbol{F}_2\boldsymbol{P}'\boldsymbol{F}_1\boldsymbol{P}'\boldsymbol{\pi}$$
$$\sum_{S_1,S_2}P(X_3|S_3)P(S_3|S_2)P(X_2|S_2)P(S_2|S_1)P(X_1|S_1)P(S_1)=\boldsymbol{F}_3\boldsymbol{P}'\boldsymbol{F}_2\boldsymbol{P}'\boldsymbol{F}_1\boldsymbol{P}'\boldsymbol{\pi}$$
$$\sum_{S_1,S_2,S_3}P(X_3|S_3)P(S_3|S_2)P(X_2|S_2)P(S_2|S_1)P(X_1|S_1)P(S_1)=\boldsymbol\iota'\boldsymbol{F}_3\boldsymbol{P}'\boldsymbol{F}_2\boldsymbol{P}'\boldsymbol{F}_1\boldsymbol{P}'\boldsymbol{\pi}$$
I think it makes more sense to keep the product in that order, although you can take the transpose of the whole thing to get the article's expression. (Recall that $\boldsymbol{F}_t=\boldsymbol{F}_t'$.) Such minutiae aren't really too important. The big-picture takeaway is that this matrix product is not a product of scalar likelihoods for each $t$. It is sensitive to long-term correlations between the $S_t$, which supposedly can and should be ignored for the authors' purposes.


text:
\begin{document}

\maketitle

\begin{abstract}
We develop a framework for convexifying a fairly general class of optimization problems. Under additional assumptions, we analyze the suboptimality of the solution to the convexified problem relative to the original nonconvex problem and prove additive approximation guarantees. We then develop algorithms based on stochastic gradient methods to solve the resulting optimization problems and show bounds on convergence rates.
We then extend this framework to apply to a general class of discrete-time dynamical systems. In this context, our convexification approach falls under the well-studied paradigm of risk-sensitive Markov Decision Processes. We derive the first known model-based and model-free policy gradient optimization algorithms with guaranteed convergence to the optimal solution. Finally, we present numerical results validating our formulation in different applications.
\end{abstract}

\section{INTRODUCTION}
It has been said that the ``the great watershed in optimization isn't between linearity and nonlinearity, but convexity and nonconvexity''. In this paper, we describe a framework for convexifying a fairly general class of optimization problems (section \ref{sec:SoftCOpt}), turning them into problems that can be solved with efficient convergence guarantees. The convexification approach may change the problem drastically in some cases, which is not surprising since most nonconvex optimization problems are NP-hard and cannot be reduced to solving convex optimization problems. However, under additional assumptions, we can make guarantees that bound the suboptimality of the solution found by solving the convex surrogate relative to the optimum of the original nonconvex problem (section \ref{sec:SubOpt}). We adapt stochastic gradient methods to solve the resulting problems (section \ref{sec:Algorithms}) and prove convergence guarantees that bound the distance to optimality as a function of the number of iterations. In section \ref{sec:Control}, we extend the framework to arbitrary dynamical systems and derive the first known (to the best of our knowledge) policy optimization approach with guaranteed convergence to the global optimum. The control problems we study fall under the classical framework of risk-sensitive control and the condition required for convexity is a natural one relating the control cost, risk factor and noise covariance. It is very similar to the condition used in path integral control \citep{Fleming82,Kappen05} and subsequent iterative algorithms (the $\mathrm{PI}^2$ algorithm \citep{Theodorou2010}). In section \ref{sec:Numerical}, we present numerical results illustrating the applications of our framework to various problems.

\subsection{RELATED WORK}

Smoothing with noise is a relatively common approach that has been used extensively in various applications to simplify difficult optimization problems. It has been used in computer vision \citep{Rangarajan90generalisedgraduated} heuristically and formalized in recent work \citep{mobahi2012phd} where it is shown that under certain assumptions, adding sufficient noise eventually leads to a convex optimization problem. In this work, however, we show that for any noise level, one can choose the degree of risk-aversion in order to obtain a convex problem. In the process, one may destroy minima that are not robust to perturbations, but in several applications, it makes sense to find a robust solution, rather than the best one. Our work can be extended to control of dynamical systems (section \ref{sec:Control}). In this setting, the condition for convexity is closely related to the one that arises in path-integral control \citep{Fleming82,Kappen05}. Closely related work for  discrete-time was developed in \citep{Todorov09} and extensions and applications have been proposed in subsequent papers \citep{Theodorou2010,KappenRisk,Dvijotham2011,Toussaint09}.

\section{NOTATION}
Gaussian random variables are denoted by $\noise \sim \Gauss{\mu}{\Sigma}$, where $\mu$ is the mean and $\Sigma$ the covariance matrix. Given a random variable $\noise \in \Omega$ with distribution $P$ and a function $h: \Omega \mapsto \R$, the expected value of the random variable $h\br{\noise}$ is written as $\displaystyle\ExP{\noise \sim P}{h\br{\noise}}$. Whenever it is clear from the context, we will drop the subscript on the expected value and simply write $\ExP{}{h\br{\noise}}$. We differ from convention here slightly by denoting random variables with lowercase letters and reserve uppercase letters for matrices. We will frequently work with Gaussian perturbations of a function, so we denote:
\[\fpert{h}{\Sigma}{\theta}=\ExP{\noise \sim \Gauss{0}{\Sigma}}{h\br{\theta+\noise}},\fpertr{h}{\omega}{\theta}=h\br{\theta+\noise}-\fpert{h}{\Sigma}{\theta}.\]
$I_n$ denotes the $n \times n$ identity matrix. Unless stated otherwise, $\norm{\cdot}$ refers to the Euclidean $\ell_2$ norm. Given a convex set $\C$, we denote the projection onto $\C$ of $x$ by $\Proj{\C}{x}$: $\Proj{\C}{x}=\argmin_{y \in \C} \norm{y-x}$.
The maximum eigenvalue of a symmetric matrix $M$ is denoted by $\lama{M}$. Given symmetric matrices $A,B$, the notation $A \succeq B$ means that $A-B$ is a positive semidefinite matrix. Given a positive definite matrix $M \succ 0$, we denote the metric induced by $M$ as ${\|x\|}_M= \sqrt{\tran{x}M x}$.

\section{GENERAL OPTIMIZATION PROBLEMS}\label{sec:General}
\input{General.tex}
\section{ALGORITHMS AND CONVERGENCE GUARANTEES}\label{sec:Algorithms}
\input{Algorithms.tex}
\section{CONTROL PROBLEMS}\label{sec:Control}
\input{Controls.tex}
\section{NUMERICAL RESULTS}\label{sec:Numerical}
\input{Numerical.tex}

\section{CONCLUSION AND FUTURE WORK}
We have developed a general framework for convexifying a broad class of optimization problems, analysis that relates the solution of the convexified problem to the original one and given algorithms with convergence rate guarantees to solve the convexified problems. Extending the framework to dynamical systems, we derive the first approach to policy optimization with optimality and convergence rate guarantees. We validated our approach numerically on problems of binary classification and training neural networks. In future work, we will refine the suboptimality analysis for our convexification approach. Algorithmically, stochastic gradient methods could be slow if the variance in the gradient estimates is high, which is the case when using the exponentiated objective (as in section \ref{sec:Algorithms}). We will study the applicability of recent work on using better sampling algorithms with stochastic gradient \citep{StochasticProximal} to our convexified problems.

\begin{comment}
\subsection{SECOND LEVEL HEADING}

\subsubsection{Third Level Heading}

\subsection{CITATIONS, FIGURES, REFERENCES}

\subsubsection{Citations in Text}

Citations within the text should include the author's last name and
year, e.g., (Cheesman, 1985). Reference style should follow the style
that you are used to using, as long as the citation style is
consistent.

For the original submission, take care not to reveal the authors' identity through
the manner in which one's own previous work is cited.  For example, writing
``In (Bovik, 1970), we studied the problem of AI'' would be inappropriate, as
it reveals the author's identity.  Instead, write ``(Bovik, 1970) studied the
problem of AI.''

\subsubsection{Footnotes}

Indicate footnotes with a number\footnote{Sample of the first
footnote} in the text. Use 8 point type for footnotes.  Place the
footnotes at the bottom of the page on which they appear.  Precede the
footnote with a 0.5 point horizontal rule 1~inch (6~picas)
long.\footnote{Sample of the second footnote}

\subsubsection{Figures}

\begin{figure}[h]
\vspace{1in}
\caption{Sample Figure Caption}
\end{figure}

\subsubsection{Tables}

All tables must be centered, neat, clean, and legible. Table number
and title always appear above the table.  See
Table~\ref{sample-table}.

One line space before the table title, one line space after the table
title, and one line space after the table. The table title must be
initial caps and each table numbered consecutively.

\begin{table}[h]
\caption{Sample Table Title}
\label{sample-table}
\begin{center}
\begin{tabular}{ll}
\multicolumn{1}{c}{\bf PART}  &\multicolumn{1}{c}{\bf DESCRIPTION} \\
\hline \\
Dendrite         &Input terminal \\
Axon             &Output terminal \\
Soma             &Cell body (contains cell nucleus) \\
\end{tabular}
\end{center}
\end{table}

\newpage

\end{comment}

\section*{APPENDIX}

\input{Proofs.tex}

\bibliography{../../../Thesis/uwthesis/bibliography}
\bibliographystyle{plainnat}

\end{document}


TITLE: Poisson process with uniformly distributed corners
QUESTION [0 upvotes]: I'm not sure how to approach this mainly because the questions don't only depend on the number of green lights alone, but also where they occur. Since where they occur is uniformly distributed, I'm thinking that the probability for the first question would be $(1-\frac{1}{k-1})^2$,
ie $P$(does not occur at $i$ ) * $P$(does not occur at $j$) but I'm unsure if this is the correct way to do this.
For the 2nd question, I know there is an $exp(\lambda)$ time between jumps (or lights turning green) but once again where the jumps occur also matters. I don't know how to deal with this when solving these. Thanks in advance for any help.

REPLY [1 votes]: By properties of the Poisson process and uniform distribution, we can say that the lights at every corner turn green at a rate of $\lambda/k$. So the answer to the first question is the probability that by time $t$, the superhero's light hasn't turned green, and the villain's light hasn't turned green, i.e. $(e^{\lambda t/k})^2 = e^{2\lambda t/k}$
For the second, we can instead ask how many switches of the light it takes, on average, until the superhero's light is changed $i$ times more than the villain, or the villain's light is changed $k-i$ times more than the hero.
Keep track of the number of green lights for the superhero relative to the villain after $t$ light changes, call this $N_t$; when the superhero's light turns green, $N$ increases by $1$. When the villain's light turns green, $N$ decreases by $1$. Otherwise, $N$ is unchanged. The first two happen with probability $1/k$, and the third $(k-2)/k$.
You now have a random walk over the states $\{i-k,i-k+1,...,-1,0,1,...,i-1,i\}$, with the transition probabilities
$$
p_{j,j} = \frac{(k-2)}{k} \\
p_{j,j-1} = p_{j,j+1} = \frac{1}{k} \\
$$
and initial condition $N_0 = 0$. Find the expected time to hit either boundary, which is a textbook exercise, then multiply the answer by $1/\lambda$, which is the expected waiting time between every green light.


TITLE: Probability on different outcomes possible
QUESTION [0 upvotes]: I'm supposed to solve this for my homework, but i'm facing some problems so i hope to receive some advise.
Suppose that 10 ﬁsh are caught at a lake that contains 5 distinct types of ﬁsh.
How many different outcomes are possible, where an outcome specifies the numbers of caught ﬁsh of each of the ﬁve types?
Is it possible that i've caught zero of certain type of fish? Since i have 10 tries and 5 types to choose from each time, do i just use 5^10?

REPLY [0 votes]: Pay attention to the phrase: an outcome specifies the numbers of caught ﬁsh of each of the ﬁve types. The value $5^{10}$ calculates the total amount of permutations with repetition. This value supposes that the outcomes
$$(1,1,1,1,1,1,1,1,1,2) \text{ and } (2,1,1,1,1,1,1,1,1,1)$$
are different since the order here differ.
And according to the condition of the problem, they are the same. In both cases the first kind of fish is caught 9 times, and the second one is caught once, so it is the same outcome.
Therefore one should use combinations with repetition to calculate how many different outcomes are possible
$$
\binom{n+m-1}{n}=\binom{10+5-1}{10}.
$$
This value calculates the total number of outcomes, if one outcome is described by the numbers of caught ﬁsh of each of the ﬁve types. Say, here are possible outcomes:
$(10,0,0,0,0)$ - 10 fish of first kind, no other fish,
$(9,0,1,0,0)$ - 9 fish of first kind, one fish of third kind,
$(0,2,0,0,8)$ - 2 fish of second kind, 8 fish of last kind ans so on.

REPLY [0 votes]: Not quite.
There are indeed $5^{10}$ ways to draw ten fish of the five types if order is a distinction.   However the problem specified that an outcome is to be distinguished only by counts of fish of each type; so order is not a distinction.
That is that three trout then one catfish followed by a cod is the same outcome as a cod then three trout followed by a catfish, or any of the other $5!/3!$ arrangements.   Thus there are far fewer distinct outcomes when order is not a distinction.
When order is not a distinction the count of ways to select ten fish of the five types is the same as the count for placing ten indistinguishable balls into five distinct boxes.   That is :

 $$\binom{14}{10}$$


TITLE: Prove whether norm is or is not metric
QUESTION [1 upvotes]: Let $(X,d)$ be a metric space and $\left\lVert\cdot\right\rVert$ be a norm on $\mathbb{R}^2$. Define $\tilde{d}$ by $\tilde{d}((x_1,x_2),(y_1,y_2)) = \left\lVert(d(x_1,y_1),d(x_2,y_2))\right\rVert$. Is this $\tilde{d}$ a metric on $X \times X$? It quite clearly is when e.g. $\left\lVert\cdot\right\rVert$ is an $l^p$ norm, but how to prove or disprove it in the general case?

REPLY [1 votes]: Since $\|\cdot\|$ is a norm, clearly $\tilde{d}:X\times X\to [0,+\infty)$.
$\tilde{d}((x_1,x_2),(y_1,y_2)) = \left\lVert(d(x_1,y_1),d(x_2,y_2))\right\rVert=0\Leftrightarrow(d(x_1,y_1),d(x_2,y_2))=(0,0)\Leftrightarrow d(x_1,y_1)=0\land d(x_2,y_2)=0\Leftrightarrow x_1=y_1\land x_2=y_2\Leftrightarrow(x_1,x_2)=(y_1,y_2)$.
$\tilde{d}((x_1,x_2),(y_1,y_2)) = \left\lVert(d(x_1,y_1),d(x_2,y_2))\right\rVert=\|(d(y_1,x_1),d(y_2,x_2))\|=\tilde{d}((y_1,y_2),(x_1,x_2))$.
All the previous properties are valid in general. Unfortunately the last property we need, the triangle inequality, can fail:
Take $X=\Bbb R$ with $d(a,b)=|a-b|$ and consider the norm $\|(x,y)\|=|x|+|x-y|$ on $\Bbb R^2$. Then $\tilde{d}((2,0),(0,0))=\|(d(2,0),d(0,0))\|=\|(2,0)\|=4\nleq2=\|(1,1)\|+\|(1,1)\|=\|(d(2,1),d(0,1))\|+\|d(1,0),d(1,0))\|=\tilde{d}((2,0),(1,1))+\tilde{d}((1,1),(0,0))$.
However, we can require $\|\cdot\|$ to be monotone respect the following order: $(x_1,y_1)\le(x_2,y_2)$ iff $|x_1|\le |x_2|\land |y_1|\le |y_2|$, meaning that whenever $(x_1,y_1)\le(x_2,y_2)$ we have $\|(x_1,y_1)\|\le\|(x_2,y_2)\|$. The previous partial order can be interpreted as ordering by the distance to the origin, so we are demanding the norm to respect the "farness" of the points of $\Bbb R^2$. Here's a link mentioning this monotone norms and a characterisation.
In our case we don't need the absolute values in that partial order of $\Bbb R^2$, since $d$ is nonnegative, so if your norm $\|\cdot\|$ has that property then $\tilde{d}((x_1,x_2),(y_1,y_2))=\|(d(x_1,y_1),d(x_2,y_2))\|\le\|(d(x_1,z_1)+d(z_1,y_1),d(x_2,z_2)+d(z_2,y_2))\|=\|(d(x_1,z_1),d(x_2,z_2))+(d(z_1,y_1),d(z_2,y_2))\|\le\|(d(x_1,z_1),d(x_2,z_2))\|+\|(d(z_1,y_1),d(z_2,y_2))\|=\tilde{d}((x_1,x_2),(z_1,z_2))+\tilde{d}((z_1,z_2),(y_1,y_2))$.
So with that additional requirement $\tilde{d}$ would be a metric on $X\times X$.


TITLE: Inverting a quartic equation of state
QUESTION [2 upvotes]: I have the following equation (which is an adaptation of the Beattie-Bridgeman Equation of State):
$$ P = \frac{RT}{V} + \frac{B}{V^2} + \frac{C}{V^3} + \frac{D}{V^4} $$
This is a function of the form $P = f(V)$ as R, T, B, C and D are all constant with respect to P and V.
From this, my ultimate goal is to derive an equation for $dV/dP$. My first step is therefore to write the equation explicit in V, however I get stuck at:
$$ PV^4 - RTV^3 - BV^2 - CV - D = 0 $$
What steps am I missing in order to be able to write this in the form $V = f(P)$?

REPLY [1 votes]: Applying the technique of implicit differentiation, as Robert Israel recommended, you will get something like:
$$
V^4 + 4PV^3\frac{dV}{dP} + 3RTV^2\frac{dV}{dP} + 2BV\frac{dV}{dP} - C\frac{dV}{dP} = 0
$$
which you can solve to get $\frac{dV}{dP}$.
This assumes that $T$ is constant with respect to $P$, which others have suggested might be unrealistic.

REPLY [1 votes]: You have:
$$ P = {RT}{V^{-1}} + {B}{V^{-2}} + {C}{V^{-3}} + {D}{V^{-4}} $$
Now diffrentiate wrt $P$:
$$ 1 = {R{d{(TV^{-1}})\over dP}} + {B}{dV^{-2}\over dP} + {C}{dV^{-3}\over dP} + {D}{dV^{-4}\over dP} $$
On the RHS the last three terms are fine and you can take $dV\over dP$ common but the first term will also introduce a $dT\over dP$
So the approach to get $dV\over dP$ will be:

Take the original equation
$$ P = {RT}{V^{-1}} + {B}{V^{-2}} + {C}{V^{-3}} + {D}{V^{-4}} $$
and diffrentiate it wrt $P,V,T$ to get three equations.
These three equations will have 3 variables $dT\over dP$or $dP\over dT$ , $dP\over dV$ or $dV\over dP$ , $dT\over dV$or $dV\over dT$
Solve the three equations to get $dV\over dP$


TITLE: Simple proof that the arithmetic genus is non-negative
QUESTION [6 upvotes]: I take an irreducible and reduced closed curve $C\subseteq \mathbb{P}^n$, defined over an algebraically closed field $k$ and define the arithmetic genus $p_a(C)$ as the integer such that the Hilbert polynomial of $C$ (or of its ideal of polynomials vanishing on it) is
$$h_C(X)=\deg(C) X+1-p_a(C).$$
I would then like to have a simple proof that $p_a(C)\ge 0$. Of course, one may say that it is because it is the dimension of a vector space obtain using cohomology, but I would like a proof not involving cohomology, as it is for a master work and in my course of algebraic geometry I (unfortunately you will say) did not define the cohomology. It would then take a lot of time for the student to understand the cohomology just to prove this.
In the course, we defined the Hilbert Polynomial of any ideal, computed local intersections, Bézout theorem in $\mathbb{P}^n$ and studied blow-ups of surfaces. We also proved that $p_a(C)=g(C)$ when $C$ is smooth, where $g(C)$ is given by Riemann-Roch (the smallest integer such that $\ell(D)\ge \deg(D)+1-g$ for each divisor $D$ on $C$). I would like the student to use the fact that $p_a(C)\ge 0$ to bound the type of singularities of a plane curve and to show that one can have a resolution by blowing-up the singular points and repeating this process finitely many times.
Thanks for your help.

REPLY [2 votes]: Mumford (Complex Projective Varieties, section 7) has the following, reasonably simple proof.
Let $d$ be the degree of $\mathrm{C}$, $m$ big enough such that $h_{\mathrm{C}}(m)=\mathrm{dim}_{\mathbf{C}} (\mathbf{C}[\mathrm{T}_0,\ldots,\mathrm{T}_n]/\mathrm{I}(\mathrm{C}))_m$ and $md/2>p_a$. Embed $\mathrm{C}$ into $\mathbf{P}^N$ by the degree $m$ Veronese embedding; let $\mathrm{L}\subset\mathbf{P}^N$ be a linear space containing $\nu_m(\mathrm{C})$ such that $\nu_m(\mathrm{C})$ is nondegenerate in $\mathrm{L}$. Then $\dim(\mathrm{L})=h_\mathrm{C}(m)=md+1-p_a$, in other words $\mathrm{L}\simeq\mathbf{P}^{md-p_a}$, and the degree of $\nu_m(\mathrm{C})$ is $$md=\mathrm{deg}(\nu_m(\mathrm{C}))\geqslant\mathrm{codim}(\nu_m(\mathrm{C}))+1\geqslant md-p_a$$
since $\nu_m(\mathrm{C})$ is nondegenerate in $\mathrm{L}$.

REPLY [1 votes]: Maybe what follows should be modified depending on what is exactly assumed in the question; nevertheless, let me try.
We fix $m$ positive integer large enough so that $h_C(m)=dim H^0(C,\mathcal{O}_C(m))$. We have to show that $dim H^0(C,\mathcal{O}_C(m)) \leq deg(D)m +1$.
Let $H$ be a degree $m$ hypersurface of $\mathbb{P}^n$ intersecting $C$ in finitely many points of $C$, all smooth (such $H$ exists as $C$ is reduced and so has finitely many singular points). One can view the intersection $D:=H \cap C$ as an effective Weil divisor on the smooth part of $C$, we have $D=\sum_i a_i p_i$ with $p_i$ smooth point of $C$ and $a_i$ positive integer multiplicity. We have $\sum_i a_i =deg(C)m$.
The equation defining $H$ restricted to $C$ defines a rational trivialization of the line bundle $\mathcal{O}_C(m)$, singular along $D$. Therefore, sections of $C$ can be identified with rational functions $f$ on $C$ such that $div(f)+D \geq 0$ (remark that this makes sense as $D$ is made of smooth points of $C$). Concretely, $f$ is allowed to have a pole of order at most $a_i$ at the point $p_i$. Near each point $p_i$, fix a local coordinate and consider the polar part of the Laurent expansion of $p_i$ (terms with negative power of the local coordinate): it consists of $a_i$ coefficients. If $f$ and $g$ have the same polar parts at every $p_i$, then $f-g$ is a regular function on $C$ and so a constant as $C$ is reduced and irreducible. Therefore the kernel of the map from $H^0(C,\mathcal{O}_C(m))$ to the space of polar parts is one-dimensional and so $dim H^0(C,\mathcal{O}_C(m)) \leq (\sum_i a_i)+1=deg(C)m+1$.


TITLE: If mass is indeed invariant in Special Relativity, why do we still say things still have a "rest mass"?
QUESTION [1 upvotes]: My lecturer reaffirmed to us a classical misnomer that mass is relativistic, by pointing out that when considering relativistic momentum the Lorentz Factor is due to time dilation and thus a change in velocity, not mass.
$$\vec p = m(\gamma \vec v) \ne (\gamma m)\vec v$$
Why then, if mass is indeed invariant, due we say things have rest masses if its rest mass, should, in principle, not change?

REPLY [3 votes]: Mass is a concept that developed with Newtonian mechanics as an invariant additive quantity. It is correctly called the inertial mass, because it comes from the F=ma identification, the constant response to acceleration.
When special relativity came at first as a proposal and then validated by innumerable data, the E=mc^2  formula gave a handle to understanding the inertial mass , i.e the response to acceleration.
This is the mass that has to be used when trying to accelerate a space ship close to velocity of light, and it was impressive enough, because together with the quantum mechanical description of nuclei ( binding energy curve) it showed a connection of mass and energy.
So in the quantum and special relativity domain, mass is not a conserved quantity, only energy and momentum are conserved.
Clarity of mathematics shows that these are a fourvector, with an invariant to lorenz transformations value when added as four vectors.Rest masses are not additive, four vectors follow vector addition rules, so a system of particles has an invariant mass the length of the added four vectors.
For individual particles it is the "rest mass", at the limit of velocity equal to zero.
The relativistic mass is variable with velocity:

In particle physics the invariant/rest mass identifies one to one the particles in the elementary particles table . All other invariant masses in principle  are derivable using the four vector algebra.
So we call relativistic mass the famous mass in the formula E=mc^2 as a respect for the historical development, and invariant/rest mass the four vector "lengths" to stress the special relativity equations.

REPLY [1 votes]: Because most physicists learned special relativity in books that do use the concept of relativistic mass, in which "rest" mass and mass are different things. It will take some time for these words to vanish from
 vocabulary.