text:
\label{appendix:proof}

\subsection{Gordon's result and proofs}
\label{appendix:proof:gordon}

We consider in this section that the data have been generated by a teacher \eqref{appendix:teacher_model} with Gaussian weights
\begin{align}
	\vec{w}^\star \sim P_{\w^\star}(\vec{w}^\star) = \mN_{\vec{w}^\star}\(\vec{0},\rho_{\w^\star} \rI_{\ndim}\) ~~\text{ with }~~ \rho_{\w^\star} \equiv \EE\[ (w^\star)^2 \] \,.
	\label{appendix:model:gaussian_weights}
\end{align}

\subsubsection{For real outputs - Regression with $\rL_2$ regularization}

In what follows, we prove a theorem that characterizes the asymptotic performance of empirical risk minimization
\begin{equation}\label{eq:erm_l2}
\hat{\vec{w}}_{\rm erm} =  \argmin_{\vec{w}} \sum_{i=1}^\nsamples l\(y_i , \tfrac{1}{\sqrt{d}}\vec{x}_i^\intercal \vec{w} \) +   \frac{\lambda \norm{\vec{w}}^2}{2},
\end{equation}
where $\{y_i\}_{1 \le i \le n}$ are general real-valued outputs (that are not necessarily binary), $l(y, z)$ is a loss function that is convex with respect to $z$, and $\lambda > 0$ is the strength of the $\rL_2$ regularization. Note that this setting is more general than the one considered in Thm.~\ref{main:thm:gordon_fixed_points:classification} in the main text, which focuses on binary outputs and loss functions in the form of $l(y, z) = \ell(yz)$ for some convex function $\ell(\cdot)$.

\begin{theorem}[Regression with $\rL_2$ regularization]
	\label{apppendix:thm:gordon_fixed_points:classification}
As $\nsamples, \ndim \to \infty$ with $\nsamples/ \ndim = \alpha = \Theta(1)$, the overlap parameters $m, q$ concentrate to
\begin{align}
m & \underlim{\ndim}{\infty} \sqrt{\rho_{\w^\star}} \mu^\ast\,, && q \underlim{\ndim}{\infty} (\mu^\ast)^2 + (\delta^\ast)^2\,,
\end{align}
where the parameters $\mu^\ast, \delta^\ast$ are the solutions of
\begin{equation}\label{eq:pot_func_general}
(\mu^\ast, \delta^\ast) = \underset{\mu, \delta \ge 0}{\arg\min} \ \sup_{\tau > 0} \left\{\frac{\lambda(\mu^2 + \delta^2)}{2} - \frac{\delta^2}{2\tau} + \alpha \EE_{g, s} \mM_{\tau}[l(\varphi_{\out^\star}(\sqrt{\rho_{\w^\star}} s),.)](\mu s + \delta g)\right\}.
\end{equation}
Here, $\mM_{\tau}[l(,.)](x)$ is the Moreau-Yosida regularization defined in \eqref{appendix:definitions:moreau}, and $g, s$ are two \iid standard normal random variables.
\end{theorem}
\begin{proof}
	\label{appendix:proof:gordon_regression}
Since the teacher weight vector $\vec{w}^\star$ is independent of the input data matrix $\mat{X}$, we can assume without loss of generality that
\begin{align*}
\vec{w}^\star = \sqrt{d} \rho_d \vec{e}_1,
\end{align*}
where $\vec{e}_1$ is the first natural basis vector of $\bbR^d$, and $\rho_d = \norm{\vec{w}^\star}/\sqrt{d}$. As $d \to \infty$, $\rho_d \to \sqrt{\rho_{\w^\star}}$. Accordingly, it will be convenient to split the data matrix into two parts:
\begin{equation}\label{eq:X_split}
\mat{X} = \begin{bmatrix}
\vec{s} & \mat{B}
\end{bmatrix},
\end{equation}
where $\vec{s} \in \bbR^{n \times 1}$ and $\mat{B} \in \bbR^{n \times (d-1)}$ are two sub-matrices of \iid standard normal entries. The weight vector $\vec{w}$ in \eqref{eq:erm_l2} can also be written as $\vec{w} = [\sqrt{d} \mu, \vec{v}^\intercal]^\intercal$, where $\mu \in \bbR$ denotes the projection of $\vec{w}$ onto the direction spanned by the teacher weight vector $\vec{w}^\star$, and $\vec{v} \in \bbR^{d-1}$ is the projection of $\vec{w}$ onto the complement subspace. These representations serve to simplify the notations in our subsequent derivations. For example, we can now write the output as
\begin{equation}\label{eq:s2y}
y_i = \varphi_{\out^\star}(\rho_d s_i),
\end{equation}
where $s_i$ is the $i$th entry of the Gaussian vector $\vec{s}$ in \eqref{eq:X_split}.

Let $\Phi_d$ denote the cost of the ERM in \eqref{eq:erm_l2}, normalized by $d$. Using our new representations introduced above, we have
\begin{equation}\label{eq:Phi}
\Phi_d = \min_{\mu, \vec{v}} \frac{1}{d}\sum_{i=1}^\nsamples l\(y_i, \mu s_i + \tfrac{1}{\sqrt{d}}\vec{b}_i^\intercal \vec{v} \) +   \frac{\lambda (d\mu^2 + \norm{\vec{v}}^2)}{2d},
\end{equation}
where $\vec{b}_i^\intercal$ denotes the $i$th row of $\mat{B}$. Since the loss function $l(y_i, z)$ is convex with respect to $z$, we can rewrite it as
\begin{equation}\label{eq:conjugate}
l(y_i, z) = \sup_q \{q z - l^\ast(y_i, q)\},
\end{equation}
where $l^\ast(y_i, q) = \sup_z \{qz - l(y_i, z)\}$ is its convex conjugate. Substituting \eqref{eq:conjugate} into \eqref{eq:Phi}, we have
\begin{equation}\label{eq:Phi_o}
\Phi_d = \min_{\mu, \vec{v}} \, \sup_{\vec{q}}  \left\{\frac{\mu \vec{q}^\intercal \vec{s}}{d} + \frac{1}{d^{3/2}} \vec{q}^\intercal \mat{B} \vec{v} - \frac{1}{d} \sum_{i=1}^n l^\ast(y_i, q_i) + \frac{\lambda \(d\mu^2 + \norm{\vec{v}}^2\)}{2d}\right\}.
\end{equation}

Now consider a new optimization problem
\begin{equation}\label{eq:Phi_s}
\widetilde{\Phi}_d = \min_{\mu, \vec{v}} \, \sup_{\vec{q}}  \left\{\frac{\mu \vec{q}^\intercal \vec{s}}{d} + \frac{\norm{\vec{q}}}{\sqrt{d}} \frac{\vec{h}^\intercal \vec{v}}{d} + \frac{\norm{\vec{v}}}{\sqrt{d}} \frac{\vec{g}^\intercal \vec{q}}{d} - \frac{1}{d} \sum_{i=1}^n l^\ast(y_i, q_i) + \frac{\lambda \(d\mu^2 + \norm{\vec{v}}^2\)}{2d}\right\},
\end{equation}
where $h \sim \mN\(\vec{0},\rI_{\ndim-1}\)$ and $g \sim  \mN\(\vec{0},\rI_{n}\)$ are two independent standard normal vectors. It follows from Gordon's minimax comparison inequality (see, \emph{e.g.}, \cite{pmlr-v40-Thrampoulidis15}) that
\begin{equation}\label{eq:cgmt}
\mathbb{P}(\abs{\Phi_d - c} \ge \epsilon) \le 2 \mathbb{P}\(\abs{\widetilde{\Phi}_d-c} \ge \epsilon\)
\end{equation}
for any constants $c$ and $\epsilon > 0$. This implies that $\widetilde{\Phi}_d$ serves as a surrogate of $\Phi_d$. Specifically, if $\widetilde{\Phi}_d$ concentrates around some deterministic limit $c$ as $d \to \infty$, so does $\Phi_d$. In what follows, we proceed to solve the surrogate problem in \eqref{eq:Phi_s}. First, let $\delta = \norm{\vec{v}}/\sqrt{d}$. It is easy to see that \eqref{eq:Phi_s} can be simplified as
\begin{align*}
\widetilde{\Phi}_d &= \min_{\mu, \delta \ge 0} \, \sup_{\vec{q}}  \left\{\frac{\vec{q}^\intercal (\mu\vec{s} + \delta \vec{g})}{d} - \delta \frac{\norm{\vec{q}}}{\sqrt{d}} \frac{\norm{\vec{h}}}{\sqrt{d}}  - \frac{1}{d} \sum_{i=1}^n l^\ast(y_i, q_i) + \frac{\lambda (\mu^2 + \delta^2)}{2}\right\}\\
&\overset{(a)}= \min_{\mu, \delta \ge 0} \, \sup_{\tau > 0} \, \sup_{\vec{q}} \left\{-\frac{\tau \norm{\vec{q}}^2}{2d} - \frac{\delta^2 \norm{\vec{h}}^2}{2\tau d} +\frac{\vec{q}^\intercal (\mu\vec{s} + \delta \vec{g})}{d}- \frac{1}{d} \sum_{i=1}^n l^\ast(y_i, q_i) + \frac{\lambda (\mu^2 + \delta^2)}{2}\right\}\\
&=\min_{\mu, \delta \ge 0} \, \sup_{\tau > 0}\left\{ \frac{\lambda (\mu^2 + \delta^2)}{2}-\frac{\delta^2 \norm{\vec{h}}^2}{2\tau d} - \frac{\alpha}{n}\inf_{\vec{q}} \Big[\frac{\tau \norm{\vec{q}}^2}{2} - \vec{q}^\intercal (\mu\vec{s} + \delta \vec{g})+ \sum_{i=1}^n l^\ast(y_i, q_i)\Big]\right\}\\
&\overset{(b)}=\min_{\mu, \delta \ge 0} \, \sup_{\tau > 0}\left\{ \frac{\lambda (\mu^2 + \delta^2)}{2}-\frac{\delta^2 \norm{\vec{h}}^2}{2\tau d} - \frac{\alpha}{n}\sum_{i=1}^n \mM_{\tau}[l(y_i,.)](\mu s_i + \delta g_i)\right\}.
\end{align*}
In $(a)$, we have introduced an auxiliary variable $\tau$ to rewrite $- \delta \frac{\norm{\vec{q}}}{\sqrt{d}} \frac{\norm{\vec{h}}}{\sqrt{d}}$ as
\begin{align*}
- \delta \frac{\norm{\vec{q}}}{\sqrt{d}} \frac{\norm{\vec{h}}}{\sqrt{d}} = \sup_{\tau > 0} \left\{-\frac{\tau \norm{\vec{q}}^2}{2d} - \frac{\delta^2 \norm{\vec{h}}^2}{2\tau d}\right\}\,,
\end{align*}
and to get $(b)$, we use the identity
\begin{align*}
\inf_q \left\{\frac{\tau}{2} q^2 - q z + \ell^\ast(q)\right\} = - \inf_x \left\{\frac{(z-x)^2}{2\tau} + \ell(x)\right\}
\end{align*}
that holds for any $z$ and for any convex function $\ell(x)$ and its conjugate $\ell^\ast(q)$. As $d \to \infty$, standard concentration arguments give us $\frac{\norm{\vec{h}}^2}{d} \to 1$ and $\frac{1}{n}\sum_{i=1}^n \mM_{\tau}[l(y_i,.)](\mu s_i + \delta g_i) \to \mathbb{E}_{g, s} \mM_{\tau}[l(y,.)](\mu s + \delta g)$ locally uniformly over $\tau, \mu$ and $\delta$. Using \eqref{eq:cgmt} and recalling \eqref{eq:s2y}, we can then conclude that the normalized cost of the ERM $\Phi_d$ converges to the optimal value of the deterministic optimization problem in \eqref{eq:pot_func_general}. Finally, since $\lambda > 0$, one can show that the cost function of \eqref{eq:pot_func_general} has a unique global minima at $\mu^\ast$ and $\delta^\ast$. It follows that the empirical values of $(\mu, \delta)$ associated with the surrogate optimization problem \eqref{eq:Phi_s} converge to their corresponding deterministic limits $(\mu^\ast, \delta^\ast)$. Finally, the convergence of $(\mu, \delta)$ associated with the original optimization problem \eqref{eq:Phi_o} towards the same limits can be established by evoking standard arguments (see, \emph{e.g.}, \cite[Theorem 6.1, statement (iii)]{Thrampoulidis16}).
\end{proof}

\subsubsection{For binary outputs - Classification with $\rL_2$ regularization}

In what follows, we specialize the previous theorem to the case of binary classification, with a convex loss function in the form of $l(y, z) = \ell(yz)$ for some function $\ell(\cdot)$.

\begin{theorem}[Thm.~\ref{main:thm:gordon_fixed_points:classification} in the main text. Gordon's min-max fixed point - Classification with $\rL_2$ regularization]
\label{appendix:thm:gordon_fixed_points:classification}
As $\nsamples, \ndim \to \infty$ with $\nsamples/ \ndim = \alpha = \Theta(1)$, the overlap parameters $m, q$ concentrate to
\begin{align}
m & \underlim{\ndim}{\infty} \sqrt{\rho_{\w^\star}} \mu^\ast\,, && q \underlim{\ndim}{\infty} (\mu^\ast)^2 + (\delta^\ast)^2\,,
\end{align}
where parameters $\mu^\ast, \delta^\ast$ are solutions of
\begin{equation}\label{appendix:eq:pot_func}
(\mu^\ast, \delta^\ast) = \underset{\mu, \delta \ge 0}{\arg\min} \ \sup_{\tau > 0} \left\{\frac{\lambda(\mu^2 + \delta^2)}{2} - \frac{\delta^2}{2\tau} + \alpha \EE_{g, s} \mM_\tau[\delta g + \mu s \varphi_{\out^\star}(\sqrt{\rho_{\w^\star}} s)]\right\},
\end{equation}
and $g, s$ are two \iid standard normal random variables. The solutions $(\mu^\ast, \delta^\ast, \tau^\ast)$ of \eqref{appendix:eq:pot_func} can be reformulated as a set of fixed point equations

\begin{align}
\begin{aligned}
	\mu^\ast &= \frac{\alpha}{\lambda \tau^\ast + \alpha } \EE [s \cdot \varphi_{\out^\star}(\sqrt{\rho_{\w^\star}} s) \cdot \mP_{\tau^\ast}(\delta^\ast g+ \mu^\ast s \varphi_{\out^\star}(\sqrt{\rho_{\w^\star}} s))]\,, \spacecase
	\delta^\ast &= \frac{\alpha}{\lambda \tau^\ast + \alpha -1} \EE [g \cdot \mP_{\tau^\ast}(\delta^\ast g+ \mu^\ast s \varphi_{\out^\star}(\sqrt{\rho_{\w^\star}} s))]\,,\spacecase
	(\delta^\ast)^2 &= \alpha \EE [\(\delta^\ast g + \mu^\ast s \varphi_{\out^\star}(\sqrt{\rho_{\w^\star}} s) - \mP_{\tau^\ast}(\delta^\ast g + \mu^\ast s \varphi_{\out^\star}(\sqrt{\rho_{\w^\star}} s)) \)^2] \,,
\label{appendix:fixed_point_equations_gordon}
\end{aligned}

\end{align}
where $\mM_\tau$ and $\mP_\tau$ denote the Moreau-Yosida regularization and the proximal map of a convex loss function $(y, z) \mapsto \ell(yz)$:
\begin{align*}
\mM_\tau(z) = \min_x \left\{\ell(x) + \frac{(x-z)^2}{2\tau}\right\}, \qquad \mP_\tau(z) = \underset{x}{\arg\,\min} \left\{\ell(x) + \frac{(x-z)^2}{2\tau}\right\}.
\end{align*}
\end{theorem}
\begin{proof}
	\label{appendix:proof:gordon_classification}
We start by deriving \eqref{appendix:eq:pot_func} as a special case of \eqref{eq:pot_func_general}. To that end, we note that
\begin{align*}
\mM_{\tau}[l(y,.)](z) &= \min_x \left\{l(y; x) + \frac{(x-z)^2}{2\tau}\right\}\\
&= \min_x \left\{\ell(yx) + \frac{(x-z)^2}{2\tau}\right\}\\
&=\min_x \left\{\ell(x) + \frac{(x-yz)^2}{2\tau}\right\} = \mM_\tau(yz),
\end{align*}
where to reach the last equality we have used the fact that $y \in \{\pm 1\}$. Substituting this special form into \eqref{eq:pot_func_general} and recalling \eqref{eq:s2y}, we reach \eqref{appendix:eq:pot_func}.

Finally, to obtain the fixed point equations \eqref{appendix:fixed_point_equations_gordon}, we simply take the partial derivatives of the cost function in \eqref{appendix:eq:pot_func} with respect to $\mu, \delta, \tau$, and use the following well-known calculus rules for the Moreau-Yosida regularization \cite{hiriartUrruty1993}:
\begin{align*}
\frac{\partial \mM_\tau(z)}{\partial z} &= \frac{z - \mP_\tau(z)}{\tau}\,,\\
\frac{\partial \mM_\tau(z)}{\partial \tau} &= -\frac{(z - \mP_\tau(z))^2}{2\tau^2}.
\end{align*}
\end{proof}

\subsection{Replica's formulation}
\label{appendix:proof:replicas_formulation}
The replica computation presented in Sec.~\ref{appendix:replicas} boils down to the characterization of the overlaps $m,q$ in the high-dimensional limit $\nsamples, \ndim \to \infty$ with $\alpha = \frac{\nsamples}{\ndim} = \Theta(1)$, given by the solution of a set of, in the most general case, six fixed point equations over $m, q, Q, \hat{m}, \hat{q}, \hat{Q}$.  Introducing the natural variables $\Sigma \equiv Q - q$, $\hat{\Sigma} \equiv \hat{Q} +  \hat{q}$, $\eta \equiv \frac{m^2}{\rho_{\w^\star}q}$ and $\hat{\eta} \equiv \frac{\hat{m}^2}{\hat{q}}$, the set of fixed point equations for arbitrary $P_{\w^\star}, P_{\out^\star}$, convex loss $l(y,z)$ and regularizer $r(w)$, is finally given by

\begin{align}
\begin{aligned}
	m&= \EE_{\xi} \[ \mZ_{\w^\star} \(\sqrt{\hat{\eta}}  \xi , \hat{\eta} \) f_{\w^\star}\(\sqrt{\hat{\eta}}  \xi , \hat{\eta} \) f_{\w} \(  \hat{q}^{1/2}\xi  , \hat{\Sigma} \)   \]\,, \\
	q &= \EE_{\xi} \[ \mZ_{\w^\star}\( \sqrt{\hat{\eta}}  \xi , \hat{\eta}  \) f_{\w} \(  \hat{q}^{1/2}\xi  , \hat{\Sigma} \)^2   \]\,, \\
	\Sigma &=  \EE_{\xi} \[ \mZ_{\w^\star}\( \sqrt{\hat{\eta}}  \xi , \hat{\eta}  \)  \partial_\gamma f_{\w} \(  \hat{q}^{1/2}\xi  , \hat{\Sigma} \) \]\,, \\
	\hat{m} &= \alpha \EE_{y, \xi } \[ \mZ_{\out^\star}(.) \cdot f_{\out^\star} \(y,  \sqrt{\rho_{\w^\star} \eta} \xi, \rho_{\w^\star}\(1 - \eta\)\)   f_{\out} \( y,  q^{1/2}\xi, \Sigma \) \]\,, \\
	\hat{q} &= \alpha \EE_{y, \xi } \[ \mZ_{\out^\star} \( y,  \sqrt{\rho_{\w^\star} \eta} \xi, \rho_{\w^\star}\(1 - \eta\)  \)   f_{\out} \( y,  q^{1/2}\xi, \Sigma \)^2 \]\,, \\
	\hat{\Sigma} &=  - \alpha \EE_{y, \xi } \[ \mZ_{\out^\star} \( y,  \sqrt{\rho_{\w^\star} \eta} \xi, \rho_{\w^\star}\(1 - \eta\)  \)  \partial_\omega f_{\out} \( y,  q^{1/2}\xi, \Sigma \) \]\,.
\end{aligned}
\label{appendix:fixed_point_replicas}

\end{align}
The above equations depend on the Bayes-optimal partition functions $\mZ_{\w^\star}, \mZ_{\out^\star}$ defined in eq.~\eqref{appendix:definitions:update_bayes}, the updates $f_{\w^\star}$, $f_{\out^\star}$ in eq.~\eqref{appendix:definitions:update_functions_bayes} and the ERM updates $f_{\w}$, $f_{\out}$ eq.~\eqref{appendix:definitions:update_functions_map}.

\subsection{Equivalence Gordon-Replica's formulation - $\rL_2$ regularization and Gaussian weights}
\label{appendix:proof:equivalence_gordon_replicas_formulation_l2}
\subsubsection{Replica's formulation for $\rL_2$ regularization}
The proximal for the $\rL_2$ penalty with strength $\lambda$ can be computed explicitly in eq.~\eqref{appendix:definitions:application:L2} and the corresponding denoising function is simply given by $f_{\w}^{\rL_2, \lambda} \(\gamma , \Lambda \) =\frac{\gamma}{\lambda + \Lambda }$.
Therefore, for a Gaussian teacher \eqref{appendix:model:gaussian_weights} already considered in Thm.~\eqref{appendix:fixed_point_equations_gordon} with second moment $\rho_{\w^\star}$, using the denoising function \eqref{appendix:definitions:application:gaussian},
	the fixed point equations over $m,q,\Sigma$ can be computed analytically and lead to
\begin{align}
\begin{aligned}
	m &= \frac{\rho_{\w^\star}\hat{m}}{\lambda + \hat{\Sigma}}\,, \hhspace \hhspace
	&& q = \frac{\rho_{\w^\star}\hat{m}^2+\hat{q}}{(\lambda + \hat{\Sigma})^2}\,, \hhspace \hhspace
	&& \Sigma =   \frac{1}{\lambda + \hat{\Sigma}}\,.
\end{aligned}
\end{align}
Hence, removing the \emph{hat} variables in eqs.~\eqref{appendix:fixed_point_replicas}, the set of fixed point equations can be rewritten in a more compact way leading to the Corollary.~\ref{main:corollary:equivalence_gordon_replicas_formulation_l2} that we recall here:

\begin{corollary}[Corollary.~\ref{main:corollary:equivalence_gordon_replicas_formulation_l2} in the main text. Equivalence Gordon-Replicas]
\label{appendix:corollary:equivalence_gordon_replicas_formulation_l2}

The set of fixed point equations \eqref{appendix:fixed_point_equations_gordon} in Thm.~\ref{appendix:thm:gordon_fixed_points:classification} that govern the asymptotic behaviour of the overlaps $m$ and $q$ is equivalent to the following set of equations, obtained from the heuristic replica computation:

\begin{align}
	m &= \alpha \Sigma \rho_{\w^\star} \cdot \EE_{y, \xi } \[ \mZ_{\out^\star}\(.\) \cdot f_{\out^\star} \(y,  \sqrt{\rho_{\w^\star}\eta} \xi, \rho_{\w^\star}\(1 - \eta\)\) \cdot f_{\out} \( y,  q^{1/2}\xi, \Sigma \)    \]  \nonumber \\
	q &= m^2/\rho_{\w^\star} + \alpha \Sigma^2 \cdot \EE_{y, \xi } \[ \mZ_{\out^\star} \( y,  \sqrt{\rho_{\w^\star}\eta} \xi, \rho_{\w^\star}\(1 - \eta\)  \)  \cdot f_{\out} \( y,  q^{1/2}\xi, \Sigma \)^2    \]   \label{appendix:fixed_point_equations_replicas} \\
	\Sigma &=   \(\lambda - \alpha \cdot \EE_{y, \xi } \[ \mZ_{\out^\star} \( y,  \sqrt{\rho_{\w^\star}\eta} \xi, \rho_{\w^\star}\(1 - \eta\)  \) \cdot  \partial_\omega f_{\out} \( y,  q^{1/2}\xi, \Sigma \)    \] \)^{-1} \nonumber

\end{align}
with $\eta \equiv \frac{m^2}{\rho_{\w^\star}q}$, $\xi \sim \mN(0,1)$ and $\EE_y$ the continuous or discrete sum over all possible values $y$ according to $P_{\out^\star}$.
\end{corollary}
\begin{proof}[Proof of Corollary.~\ref{appendix:corollary:equivalence_gordon_replicas_formulation_l2}(Corollary.~\ref{main:corollary:equivalence_gordon_replicas_formulation_l2})]
For the sake of clarity, we use the abusive notation $\mP_V(y, \omega) = \mP_{V}[l(y,.)](\omega)$, and we remove the $\ast$.
\item
\paragraph{Dictionary}
We first map the Gordon's parameters ($\mu, \delta, \tau)$ in eq.~\eqref{appendix:fixed_point_equations_gordon} to ($m,q,\Sigma$) in eq.~\eqref{appendix:fixed_point_equations_replicas}:
\begin{align*}
	&\sqrt{\rho_{\w^\star}} \mu \leftrightarrow m\,, && \mu^2 + \delta^2 \leftrightarrow q \,,  && \tau \leftrightarrow \Sigma\,.
\end{align*}
so that
\begin{align*}
	\eta &= \frac{m^2}{\rho_{\w^\star}q} = \frac{\mu^2}{\mu^2 + \delta^2}\,, && 1-\eta = \frac{\delta^2}{\mu^2 + \delta^2}\,.
\end{align*}
From eq.~\eqref{appendix:definitions:update_bayes}, we can rewrite the channel partition function $\mZ_{\out^\star}$ and its derivative
\begin{align}
\begin{aligned}
	\mZ_{\out^\star}\(y, \omega, V\) &= \EE_{z} \[ P_{\out^\star}\(y| \sqrt{V} z + \omega \)  \],\\
	\partial_\omega \mZ_{\out^\star}\(y, \omega, V\) &= \frac{1}{\sqrt{V}} \EE_{z} \[ z P_{\out^\star}\(y| \sqrt{V} z + \omega \)  \]\,,
\end{aligned}
\label{appendix:proof:channel_reformulation}
\end{align}
where $z$ denotes a standard normal random variable.
\item
\paragraph{Equation over $m$}
Let us start with the equation over $m$ in eq.~\eqref{appendix:fixed_point_equations_replicas}:
\begin{align*}
	m &= \Sigma \alpha \rho_{\w^\star} \EE_{y, \xi } \[ \mZ_{\out^\star} \(y,  \sqrt{\rho_{\w^\star}\eta} \xi, \rho_{\w^\star}\(1 - \eta\)\) f_{\out^\star} \(y,  \sqrt{\rho_{\w^\star}\eta} \xi, \rho_{\w^\star}\(1 - \eta\)\)  \right. \\
	&  \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad  \left. \times  f_{\out} \( y,  q^{1/2}\xi, \Sigma \)    \]\\
	&= \Sigma \alpha \frac{\sqrt{\rho_{\w^\star}}}{\sqrt{1-\eta}}  \EE_{y, \xi, z} \[  z  P_{\out^\star}\(y| \sqrt{\rho_{\w^\star}} \(\sqrt{1-\eta} z + \sqrt{\eta} \xi\) \)   \Sigma^{-1} ( \mP_{\Sigma} \(y, \sqrt{q}\xi\) - \sqrt{q}\xi) \] \tag{Using eq.~\eqref{appendix:proof:channel_reformulation}} \\
	\Leftrightarrow  \mu  &= \frac{\sqrt{\mu^2 + \delta^2}}{\delta}  \alpha \EE_{y, \xi, z} \[  z  P_{\out^\star}\[y \vert \sqrt{\rho_{\w^\star}}\frac{\delta z + \mu \xi}{\sqrt{\mu^2 + \delta^2}}  \]  \( \mP_{\tau} \(y, \sqrt{\mu^2 + \delta^2}\xi\) - \sqrt{\mu^2 + \delta^2}\xi \) \] \tag{Dictionary} \\
	&= \frac{\sqrt{\mu^2 + \delta^2}}{\delta} \alpha \EE_{\xi, z} \[  z \( \mP_{\tau} \( \varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}}\frac{ \delta z + \mu \xi}{\sqrt{\mu^2 + \delta^2}} \), \sqrt{\mu^2 + \delta^2}\xi\) - \sqrt{\mu^2 + \delta^2}\xi\)     \] \tag{Integration over $y$}\\
	&= \alpha \EE_{s, g} \[ \(s- \frac{\mu}{\delta} g \) \( \mP_{\tau} \( \varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}} s \), \delta g + \mu s\)  - (\delta g + \mu s)\)      \] \tag{Change of variables $(\xi, z) \to (g, s)$} \\
	&= \alpha \EE_{s, g} \[ \(s - \frac{\mu}{\delta} g \) \( \mP_{\tau} \( \varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}} s \), \delta g + \mu s\) \)  \]\tag{Gaussian integrations} \\
	\Leftrightarrow  \mu &=  \frac{\alpha \EE_{s, g} \[ s \cdot   \mP_{\tau} \( \varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}}  s \), \delta g + \mu s\)  \] }{1 + \frac{\alpha }{\delta}  \EE_{s, g} \[ g \cdot \mP_{\tau} \( \varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}}  s \), \delta g + \mu s\)       \]  } \\
	&= \frac{\alpha}{ \lambda \tau + \alpha } \EE_{s, g} \[ s \cdot \varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}} s \)  \( \mP_{\tau} \( \delta g + \mu s\) \varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}} s \) \)    \]\tag{Second fixed point equation}\,,
\end{align*}
where we used the fact that $P_{\out^\star}\(y|z\) = \delta(y-\varphi_{\out^\star}(z))$,  the change of variables
\begin{align}
\begin{cases}
	s = \frac{\mu \xi + \delta z}{\sqrt{\mu^2 + \delta^2}} \spacecase
	g = \frac{\delta \xi - \mu z}{\sqrt{\mu^2 + \delta^2}}
\end{cases}
\Leftrightarrow
\begin{cases}
	\xi = \frac{\delta g+ \mu s}{\sqrt{\mu^2+\delta^2}} \spacecase
	z=  \frac{\delta s -\mu g}{\sqrt{\mu^2+\delta^2}}
\end{cases}\,,
\end{align}
and finally in the last equality the definition of the second fixed point equation in eqs.~\eqref{appendix:fixed_point_equations_gordon}:
\begin{align}
	\delta = \alpha \frac{\EE_{s, g} \[ g  \cdot \mP_{\tau} \( \varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}} s \), \delta g + \mu s\)  \]}{\lambda \tau + \alpha - 1}\,.
	\label{appendix:equivalence:Sigma}
\end{align}
\item
\paragraph{Equation over $q$}
Let us now compute the equation over $q$ in eq.~\eqref{appendix:fixed_point_equations_replicas}:
\begin{align*}
	q- m^2/\rho_{\w^\star} &= \Sigma^2 \alpha \EE_{y, \xi } \[ \mZ_{\out^\star} \( y,  \sqrt{\rho_{\w^\star}\eta} \xi,\rho_{\w^\star}\(1 - \eta\)  \)   f_{\out} \( y,  q^{1/2}\xi, \Sigma \)^2    \] \\
	&= \Sigma^2 \alpha \EE_{y, \xi, z } \[ P_{\out^\star}\(y| \sqrt{\rho_{\w^\star}}\(\sqrt{1-\eta} z + \sqrt{\eta}\xi\) \)  \frac{1}{\Sigma^2} \(p_{\Sigma}\(y, \sqrt{q}\xi\)  - \sqrt{q}\xi  \)^2 \] \tag{Using eq.~\eqref{appendix:proof:channel_reformulation}}\\
\Leftrightarrow \delta^2 &=  \alpha \EE_{y, \xi, z } \[ P_{\out^\star}\(y| \sqrt{\rho_{\w^\star}} \frac{\delta z + \mu \xi}{\sqrt{\mu^2 + \delta^2}} \)  \(p_{\tau}\(y, \sqrt{\mu^2 + \delta^2}\xi\)  - \sqrt{\mu^2 + \delta^2}\xi  \)^2 \] \tag{Dictionary} \\
	&=  \alpha \EE_{\xi, z} \[ \(p_{\tau}\(\varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}}\frac{ \delta z + \mu \xi}{\sqrt{\mu^2 + \delta^2}}\), \sqrt{\mu^2 + \delta^2}\xi \)  - \sqrt{\mu^2 + \delta^2}\xi  \)^2 \]\tag{Integration over $y$} \\
	&= \alpha \EE_{g, s} \[ \(p_{\tau}\(\varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}}s\), \delta g + \mu s \)  - \(\delta g + \mu s\)  \)^2 \] \tag{Change of variables $(\xi, z) \to (g, s)$}
\end{align*}

\item
\paragraph{Equation over $\Sigma$}
Let us conclude with the equation over $\Sigma$ in eq.~\eqref{appendix:fixed_point_equations_replicas} that we encountered in eq.~\eqref{appendix:equivalence:Sigma}. Let us first compute
\begin{align*}
&\alpha \EE_{y, \xi } \[ \mZ_{\out^\star} \( y,  \sqrt{\rho_{\w^\star}\eta} \xi, \rho_{\w^\star}\(1 - \eta\)  \)  \partial_\omega f_{\out} \( y,  q^{1/2}\xi, \Sigma \)    \]\\
&= \alpha \EE_{y, \xi, z } \[ P_{\out^\star}\(y| \sqrt{\rho_{\w^\star}}\(\sqrt{1-\eta} z + \sqrt{\eta}\xi \)\)  \frac{1}{\Sigma} \( \partial_\omega p_{\Sigma}\(y, \sqrt{q}\xi\)  - 1  \) \] \tag{Using eq.~\eqref{appendix:proof:channel_reformulation}}\\
	&=  \frac{\alpha}{\tau}  \EE_{y, \xi, z } \[ P_{\out^\star}\(y|  \sqrt{\rho_{\w^\star}}\frac{\delta z + \mu \xi}{\sqrt{\mu^2 + \delta^2}}\)  \(\partial_\omega \mP_{\tau}\(y, \sqrt{\mu^2 + \delta^2}\xi\)  - 1  \) \] \tag{Dictionary} \\
	&=  \frac{\alpha}{\tau} \EE_{\xi, z} \[ \partial_\omega \mP_{\tau}\(\varphi_{\out^\star}\( \sqrt{\rho_{\w^\star}}\frac{\delta z + \mu \xi}{\sqrt{\mu^2 + \delta^2}}\), \sqrt{\mu^2 + \delta^2}\xi \)    \] - \frac{\alpha}{\tau} \tag{Integration over $y$} \\
	&= \frac{1}{\tau} \alpha \( \EE_{g, s} \[ \partial_\omega \mP_{\tau}\(\varphi_{\out^\star}\( \sqrt{\rho_{\w^\star}}s\), \delta g + \mu s \)  \] -1 \)  \tag{Change of variables $(\xi, z) \to (g, s)$}
\end{align*}
therefore, the last equation over $\Sigma$ in eq.~\eqref{appendix:fixed_point_equations_replicas}  reads
\begin{align*}
	\Sigma &=  \( \lambda - \alpha \EE_{y, \xi } \[ \mZ_{\out^\star} \( y,  \sqrt{\rho_{\w^\star} \eta} \xi, \rho_{\w^\star}\(1 - \eta\)  \)  \partial_\omega f_{\out} \( y,  q^{1/2}\xi, \Sigma \)    \] \)^{-1}\\
	& \Leftrightarrow\\
	\tau &= \(\lambda - \frac{1}{\tau} \alpha \( \EE_{g, s} \[ \partial_\omega \mP_{\tau}\(\varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}}s\), \delta g + \mu s \)  \] -1 \)  \)^{-1} \\
	&\Leftrightarrow\\
	\alpha & \EE_{g, s} \[ \partial_\omega \mP_{\tau}\(\varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}}s\), \delta g + \mu s \)  \]  = \tau \lambda + \alpha -1\,.
\end{align*}
Noting that
\begin{align*}
	&\EE_{g, s} \[ \partial_\omega \mP_{\tau}\(\varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}}s\), \delta g + \mu s \) \] = \frac{1}{\delta} \EE_{g, s} \[ d \partial_\omega \mP_{\tau}\(\varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}}s\), \delta g + \mu s  \) \]\\
	&= \frac{1}{\delta} \EE_{g, s} \[ \partial_g \mP_{\tau}\(\varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}}s\), \delta g + \mu s \) \] = \frac{1}{\delta} \EE_{g, s} \[ g \mP_{\tau}\(\delta g + \mu s\varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}}s\) \) \] \tag{Stein's lemma}
\end{align*}
where we used the Stein's lemma in the last equality, we finally obtain
\begin{align*}
	&\alpha  \EE_{g, s} \[ \partial_\omega \mP_{\tau}\(\varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}}s\), \delta g + \mu s \)  \]  = \tau \lambda + \alpha -1\\
	\Leftrightarrow & \delta =\frac{\alpha}{\tau \lambda + \alpha -1 } \EE_{g, s} \[ g \cdot \mP_{\tau}\(\varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}}s\), \delta g + \mu s \) \]\,.
\end{align*}
\item
\paragraph{Gauge transformation}
We still remain to prove that
\begin{align}
\begin{aligned}
	\EE_{s, g} \[ g  \cdot \mP_{\tau} \( \varphi_{\out^\star}\( \sqrt{\rho_{\w^\star}} s \), \delta g + \mu s\)  \]&= \EE_{s, g} \[ g  \cdot \mP_{\tau} \( \delta g + \mu s \varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}} s \)\)  \]\\
	\EE_{s, g} \[ s \cdot  \mP_{\tau} \( \varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}} s \), \delta g + \mu s\)  \] &= \EE_{s, g} \[ s \cdot  \mP_{\tau} \( \delta g + \mu s \varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}} s \) \)  \]\\
	\EE_{g, s} \[ \(p_{\tau}\(\varphi_{\out^\star}\( \sqrt{\rho_{\w^\star}}s\), \delta g + \mu s \)  - \(\delta g + \mu s\)  \)^2 \] &= \EE_{g, s} \[ \right. \\
	& \qquad \left.  \(\(p_{\tau} - \id \)\(\delta g + \mu s \varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}}s\) \) \)^2 \]
\end{aligned}
\end{align}
As $\varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}} s \) = \pm 1$, we can transform $s \to s \varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}} s \)=\td{s}$. It does not change the distribution of the random variable $\td{s}$ that is still a normal random variable. Finally denoting
$\mP_{\tau}\(1, \delta g + \mu s \varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}} s \) \) = \mP_{\tau}\(\delta g + \mu s \varphi_{\out^\star}\(\sqrt{\rho_{\w^\star}} s \) \)$, we obtain the equivalence with eq.~\eqref{appendix:fixed_point_equations_gordon}, which concludes the proof.

\end{proof}


TITLE: An intrinsic supergeometric description of the Green–Schwarz supersymmetric action
QUESTION [3 upvotes]: The Green-Schwarz action is a natural supersymmetric extension of the Polyakov action (with a $B$-field which I will omit in what follows since it is not relevant to the question).
For a morphism $X:\Sigma\to M$ from a worldsheet $X$ endowed with a (pseudo-)Riemannian metric $h$ to a stacetime $M$ endowed with a (pseudo-)Riemannian metric $g$, the Polyakov action is usually written in Physics textbooks as
$$
S_P[X,h]=\int_\Sigma d\sigma^2 \sqrt{h} h^{ab}\partial_aX^\mu\partial_bX^\nu g_{\mu\nu}
$$
It is very simple to rewrite this in a completely intrinsic way. Namely, the differential of the smooth map $X$ is a morphism $dX:T\Sigma\to X^*TM$ of vector bundles over $\Sigma$, while the metric $h$ induces a canonical volume form $dvol_\Sigma$ and a cometric $\gamma_h$, which is a section of $T\Sigma\otimes T\Sigma$. Finally, $X^*g$ is a morphism $X^*(TM)\otimes X^*(TM)\to \mathbb{R}_\Sigma$ and the Polyakov action is intrinsically given by
$$
S_P[X,h]=\int_\Sigma dvol_\Sigma \, X^*g((dX\otimes dX)(\gamma_h))
$$
Equivalently, and possibly more nicely, one can rewrite this in terms of the Hodge star operator $\star_h$ for the metric $h$ as
$$
S_P[X,h]=\int_\Sigma  X^*g(dX\wedge\star_h dX)
$$
The differential $dX$, as an element in $\Omega^1(\Sigma;X^*TM)$ can actually be seen as the pullback via $X$ of the canonical 1-form $E$ in $\Omega^1(M,TM)$ corresponding to the identity morphism of $TM$ over $M$. That is, $dX=X^*(E)$ and the action becomes
$$
S_P[X,h]=\int_\Sigma dvol_\Sigma \, X^*(g(E\otimes E))(\gamma_h)=
\int_\Sigma  X^*g(X^*(E)\wedge\star_h X^*(E))
$$
Written this way, the action is immediately translated in what physicists call the vielbein formalism: if $\{e_1,e_2,\dots\}$ is a local orthonormal frame for $TM$ then $X^*E$ is written locally as $E^\mu_\nu e_\mu dX^\nu$ so that if one adopts the shorthand notation $E^\mu_a$ for $E^\mu_\nu \partial_a X^\mu$ the action reads
$$
S_P[X,h]=\int_\Sigma d\sigma^2 \sqrt{h} h^{ab}E_a^\mu E_b^\nu \eta_{\mu\nu}
$$
which is another of the forms one often finds the action written in textbooks.
Then the action is promoted to its supersymmetric version simply by replacing the vielbein $E_a^\mu$ with the "supervielbein" $\tilde{E}_a^\mu$ (whatever it is: this is something I have not clearly understood, yet).
My question is: what is the supergeometry behind this?
I would expect one has some supermanifold $\tilde{\Sigma}$ with underlying classical manifold $\Sigma$ and $\tilde{M}$ with underlying classical manifold $M$, as well as a map $\tilde{X}: \tilde{\Sigma}\to \tilde{M}$ coming into play, together with supermetrics $\tilde{h}$ and $\tilde{g}$, but I'm unable to find a reference presenting the action directly in these geometric terms, nor to guess exactly which the precise supergeometrical picture should be from the supervielbein description of the action (the only thing I'm reasonably sure about is that $\tilde{M}$ should be the supermanifold associated with some spinor bundle over $M$).

REPLY [2 votes]: Maybe I have solved: looking at the description of the coordinates above equation (1) in Superstrings in D=10 from supermembranes in D=11 by Duff-Howe-Inami-Stelle, it is manifest that there is no $\tilde{\Sigma}$ or, more precisely, that $\tilde{\Sigma}=\Sigma$ is just an ordinary manifold. This was actually the point most confusing me: what $\tilde{\Sigma}$ should be, and instead it was the most trivial one. Once this is settled, everything else follows easily: one takes as $\tilde{M}$ the supermanifold corresponding to a spinor bundel $\mathbb{S}\to M$ together with its canonical supermetric $\tilde{g}$, and considers a morphism of supermanifolds $X\colon \Sigma\to \tilde{M}$; one denotes by $\tilde{E}$ the canonical 1-form on $\tilde{M}$ with coefficients in $T\tilde{M}$ corresponding o the identity of $T\tilde{M}$ and one is done: the action is
$$
S_{GS}[X,h]=\int_\Sigma dvol_\Sigma X^*(\tilde{g}(\tilde{E}\otimes\tilde{E}))(\gamma_h)=
\int_\Sigma  X^*(\tilde{g})(X^*\tilde{E}\wedge \star_h X^*\tilde{E})
$$
which in super-coordinates precisely reads
$$
S_{GS}[X,h]=\int_\Sigma d\sigma^2\sqrt{h} h^{ab} \tilde{E}_a^\mu\tilde{E}_b^\mu \eta_{\mu\nu}
$$
Now that I write it I see the answer was the most obvious and I don't understund how this can have been puzzling me so much. I will let the admins decide whether this question and its answer may be worth be left here for the sake of possibly interested readers or it is better to just delete them.


TITLE: Find a recurrence relation for the number of ternary strings that do not contain consecutive symbols that are the same.
QUESTION [0 upvotes]: I tried to solve this question by subtracting the number of strings that contain consecutive symbols that are same from the total number of symbols possible of length n.
Let bn denote the number of strings of length n, with consecutive symbols that are same. Then bn can be obtained by 3*bn-1 , since there are 3 choices for appending the string of length n-1 to form a string of length n. So if an denotes the number of strings of length n that do not contain consecutive symbols that are same then, an = 3n - bn-1 . But I am stuck, how do I go from here ? How to solve such problems without generating the sequence and guessing ? I am having a hard time doing so.

REPLY [0 votes]: HINT
Well, if $a_n$ denotes the number of ternary strings without consecutive symbols, and you are given such a string of length $n-1$, you can form an $n$-string by attaching $0,1,2$ at the end except you must make sure not to duplicate the last symbol. In other words you have 2 choices for the last character.
Can you finish this?


TITLE: Pascal's law misunderstanding
QUESTION [0 upvotes]: I have a weird misunderstanding about liquid pressure.  On the diagram, I have two weightless and frictionless pistons on the two openings of the container. There is the same atmospheric pressure on both of them. So one piston has area A1 (the smaller one) and the other has the area A2 (the bigger one). Since the atmospheric pressure is equal for both the pistons and one has a bigger area than the other, the force on the larger piston would be greater than the smaller one. Then the larger piston should move down and the smaller piston should move up. But that doesn't happen. So where did I misunderstand?

REPLY [1 votes]: First, let's consider a weightless scenario to demonstrate that, for the fluid to be in balance, forces $F_1$ and $F_2$ do not have to be equal.
In the weightless case, according to the Pascal's law, the pressure everywhere in the fluid should be the same.

If we apply force $F_1=P_0A_1$ to the left piston, while the right piston is fixed, it is easy to see that the same pressure $P_0$ will be at points $A$, $B$ or $C$. The pressure force of the fluid acting on the right piston, $F_2=P_0A_2$ will be determined by the pressure under the piston, $P_0$, and the area of the right piston. So, it won't depend on the area of the left piston and will be different than $F_1$, while the fluid will be in balance.
If we add gravity, the weight of the fluid will cause the pressure increase with depth, but, at any given depth, according to the Pascal's law, the pressure will still be the same. We can also see, that, if the horizontal pressure was not the same, the fluid would move from higher pressure areas to lower pressure areas. It should be rather obvious then, that to maintain the same pressure at any given depth everywhere, the heights of the left and right columns, which determine the pressure under them, would also have to be the same. Hence, the pistons have to be at the same level.

My last point should answer your implied question: how come we have two unequal forces, $F_1$ and $F_2$, acting on the fluid "from two different directions" and the fluid does not move? Is it a violation of the Newton's second law? It is not, if we consider all forces acting on the fluid, including the reaction forces from the walls. This should be clear from the diagram below and should be easy to prove, since we know the pressure at all points.


TITLE: Hereditary substitution with a universe hierarchy
QUESTION [11 upvotes]: I've read about hereditary substitution for the Simple Lambda Calculus and for The Logical Framework with distinct terms and types.
I'm wondering, are there any examples of hereditary substitution in a dependently typed system with a universe hierarchy? i.e. where $ True : Set_0 : Set_1:Set_2$ etc.
I'm wondering in particular how to establish an induction measure in such a system. The simply typed version is structurally decreasing in the type of the variable being replaced. This doesn't work work with dependent types, to for LF the paper I linked uses the simply-typed erasure of the terms, performing induction on the shape of the type.
However, erasing to simple types doesn't work with a universe hierarchy, since if you have something like this:

$ f : (x : Set_1)\to x \to True$ implies that
$ f\ ((y : True) \to True \to True ): True \to True \to True$

i.e. applying a function resulted in a structurally larger type.
I'm assuming the solution has something to do with the universe indexes, but if there's an existing technique for establishing that the induction is well founded, I'd prefer to cite it rather than coming up with something up on my own.

REPLY [9 votes]: As of November 2018, how to do this for dependent type theories with large eliminations is an open question.
Establishing that the recursion is well-founded is not too bad; you can use Pataraia's theorem to prove the fixed point you want exists. See Robert Harper's *Constructing Type Systems Over an Operational Semantics for a how-to. (You can also do this via an inductive-recursive definition.)
The hard part is actually formulating the hereditary substitution in a nice way -- the natural direction leads you towards substituting not one term, but an entire substitution for a context, and this raises a lot of questions about when and how to establish properties of things like compositions of (hereditary) substitutions.
If it turned out to be impossible, I would be utterly shocked. However, at present no one has done it. If you want to work on this, I would suggest getting in touch with Andreas Abel, Dan Licata and Mike Shulman. (Or me, for that matter.)

REPLY [8 votes]: Here's a reference for predicative System F. The measure indeed includes the multiset of universe levels in a type. I can't say much about whether this approach generalizes to predicative dependent type theory.


TITLE: Real Analysis problem concerning recursive sequence limit.
QUESTION [2 upvotes]: Define $$a_1=1$$, and define
$$
a_{n+1} = \left\{\begin{aligned}
&a_n+1/n &&: a_n^2\leq 2\\
&a_n-1/n &&: a_n^2>2
\end{aligned}
\right.$$
I am then asked to show that $$|a_n-\sqrt{2}|<2/n$$ for all indices n in order to show convergence by comparison.
My initial thought was to use induction but my algebra during the inductive step doesn't go very far. Any thoughts would be greatly appreciated.

REPLY [6 votes]: Induction works. Suppose $|a_n - \sqrt 2| < 2/n$, i.e.
\begin{equation*}
(1) \quad \sqrt 2 - 2/n < a_n < \sqrt 2 + 2/n.
\end{equation*}
There are two cases:
Case 1. If $a_n^2 \le 2$, i.e. $a_n \le \sqrt 2$, we can refine (1) to
\begin{equation*}
\sqrt 2 - 2/n < a_n \le \sqrt 2.
\end{equation*}
And we have $a_{n + 1} = a_n + 1/n$, so by adding $1/n$ to this inequality, we get
\begin{equation*}
\sqrt 2 - 1/n < a_{n + 1} \le \sqrt 2 + 1/n,
\end{equation*}
i.e. $|a_{n + 1} - \sqrt 2| < 1/n$.
Case 2. If $a_n^2 \ge 2$, i.e. $a_n \ge \sqrt 2$, we can refine (1) to
\begin{equation*}
\sqrt 2 < a_n \le \sqrt 2 + 2/n.
\end{equation*}
And we have $a_{n + 1} = a_n - 1/n$, so by subtracting $1/n$ from this inequality, we get
\begin{equation*}
\sqrt 2 - 1/n < a_n \le \sqrt 2 + 1/n,
\end{equation*}
i.e. $|a_{n + 1} - \sqrt 2| < 1/n$.
Either way, we have $|a_{n + 1} - \sqrt 2| < 1/n$. And for all $n \ge 1$, we have $1/n \le 2/(n + 1)$.
(Proof of the last inequality:
\begin{equation*}
2/(n + 1) - 1/n = (2n - n - 1)/(n(n + 1)) = (n - 1)/(n^2 + n),
\end{equation*}
which is nonnegative).


TITLE: selecting two students(males) at random
QUESTION [2 upvotes]: two students are selected at random one after the other without replacement, from a group of 10 students. there are 6 male students.
given that the second selected student is a male, what's the probability of the first selected student is male?
since they have said the second student is male,
the probability of picking a male student for the second time is
 P(b2) = 6/10 * 5/9 + 4/10 * 6/9 = 54/90
cause the first student isn't mentioned I took as it could be either a girl or a boy
both selected students being boys, i took it as
P(b1 AND b2) = 6/10 *5/9 = 30/90
so the first boy being a boy given that second one is a boy
P(b1/b2) = 5/9
this is the answer i got. can someone please tell me whether this is the correct answer and the correct way of solving this problem?

REPLY [2 votes]: two students are selected at random one after the other without replacement, from a group of 10 students. there are 6 male students. given that the second selected student is a male, what's the probability of the first selected student is male?

Under the condition that one of the six males is the second selected student, there remain five males among the nine, all of whom have equal probability to have been the first selected student.
Clearly the conditional probability is $5/9$.

If you wish to use Bayes' Rule to confirm:
$$\mathsf P(M_1\mid M_2)=\dfrac{\mathsf P(M_1\cap M_2)}{\mathsf P(M_2)}=\dfrac{\tfrac 6{10}\tfrac {5}{9}}{\tfrac 6{10}\tfrac 59+\tfrac 4{10}\tfrac 69}=\dfrac 59$$


TITLE: Let $f: (\mathbb{R}, d) \to (\mathbb{R}, d')$ where $d$ is the usual metric and $d'$ is the discrete. Determine if $f(x)=x^2$ is continuous.
QUESTION [1 upvotes]: Let $f: (\mathbb{R}, d) \to (\mathbb{R}, d')$ where $d$ is the usual metric and $d'$ is the discrete. Determine if $f(x)=x^2$ is continuous.

In order for $f$ to be continuous I have to have that $$d'(f(x),f(y)) \ < \varepsilon, \text{ when } d(x,y) < \delta, \text{ for $\varepsilon, \delta >0.$}$$
Now $d(x,y) = |x-y|$ and from the discrete metric we have that $d'(f(x),f(y)) \ < \varepsilon$ is only true when $f(x)=f(y)$ which would imply that $d'(f(x),f(y)) = 0$ otherwise we would need to pick $\varepsilon >1$ which wont' work since it's supposed to work for all $\varepsilon$.
We have some cases where the continuity seems to hold for example when $x=2, y=-2$ we have that $f(x)= f(2) = f(-2)=f(y) = 4$, but I'm not sure that the continuity holds for all points. I feel like it doesn't, but I'm not sure how to show this?

REPLY [1 votes]: No.  $f^{-1}(0)=0$ is not open.  But in the discrete topology points are open.

Or, you could use the definition that the inverse image of any closed set has to be closed.  Take an open interval in the discrete topology.  It's closed (everything is).  But it's preimage is not closed, as you can check.  For instance, $f^{-1}((0,1))=(-1,0)\cup(0,1)$.


text:
\chapter{Wheeling}\label{chap:wheeling}

Now that we have reviewed the basic theory of Vassiliev invariants,
the proof of Theorem~\ref{thm:wheeling} is relatively straightforward.
In Section~\ref{sec:phi} we will show how to interpret the Hopf link
$\OpenHopf$ of Figure~\ref{fig:One} as a map $\Phi: \cB\rightarrow\cA$
by taking its
Kontsevich integral in $\cA(\vert \circledast)$ and gluing the legs on
the bead to the diagram in $\cB$.
In Section~\ref{sec:multiplicativity} we will see how the equation
``$1+1=2$'' of Figure~\ref{fig:OneOneTwo} implies that $\Phi$ is
multiplicative.  Briefly, we interpret both sides of the
equation as maps from $\cB \otimes \cB$ to $\cA$.  The ``$1+1$'' side
takes $(X, Y)$ to $\Phi(X) \connect \Phi(Y)$ and the ``$2$'' side
takes $(X, Y)$ to $\Phi(X \udot Y)$.  The fact that the two links are
isotopic implies that the two maps are equal.  In
Section~\ref{sec:phi0} we relate this map $\Phi$ to the
wheeling map $\Upsilon$ of Section~\ref{sec:upsilon} by showing that
the lowest degree term
$\Phi_0$ of $\Phi$
is also multiplicative and is the same as the Duflo map with possibly
different coefficients of the wheels $\omega_n$.  To fix the coefficients, it
suffices to do a small computation for some Lie algebra; we do the
computation for $\sltwo$ in Appendix~\ref{app:coefficients}.

\section{The map $\Phi$}\label{sec:phi}
We start by defining a kind of inner product on the space $\cB$.

\begin{definition}\label{def:diagram-inner} For a diagrams $C, C' \in
\cB$ so that $C$ has no struts, the {\em inner product} of $C$ and $C'$ is
\ssp
\[ \cA(\emptyset) \contains \langle C, C' \rangle =\begin{cases}
    \parbox{2.2in}{
      the sum of all ways of gluing all the legs of $C$ to all
      legs of $D$
    }\quad & \parbox{1.7in}{if $C$ and $C'$ have
			    the same number of legs} \\[3pt]
    0 & \text{otherwise}
  \end{cases}
\]
\dsp
We will sometimes want to fix $C$ and consider $\langle
C\comma\cdot\rangle$ as a map from
$\cB$ to $\cA(\emptyset)$; we will denote this map $\iota(C)$.  This
definition works equally well in the presence of other skeleton
components or to glue several components.  We
will use subscripts to indicate which ends are glued.
\end{definition}

As in Definition~\ref{def:diagram-differential}, the restriction that
$C$ not have struts is to guarantee convergence and avoid closed
circles.

There are two dualities relating
$\langle\cdot\comma\cdot\rangle$ with other operations we have
defined.

\begin{lemma}\label{lem:mult-comult-dual}
Multiplication and comultiplication in $\cB$ are dual
in the sense that
\[
\langle C, D_1 \udot D_2 \rangle =
	\langle \Delta_{xy} C, (D_1)_x \otimes (D_2)_y\rangle_{xy}.
\]
Similar statements hold in the presence of other ends.
\end{lemma}
\begin{proof} The glued diagrams are the same on the two sides; we
either combine the legs of $D_1$ and $D_2$ into one set and then glue
with $C$, or we split the legs of $C$ into two pieces which are then
glued with $D_1$ and $D_2$. (Note that there are no combinatorial
factors to worry about: in both cases, we take the sum over all
possibilities.)
\end{proof}

\begin{lemma}\label{lem:mult-diffop-dual} Multiplication by a diagram
$B \in\cB$ and applying $B$ as a diagrammatic differential operator
are adjoint in the sense that
\[
\langle A \udot B, C\rangle = \langle A, \partial_B(C) \rangle.
\]
\end{lemma}
\begin{proof}
As before, the diagrams are the same on both sides.
\end{proof}

The map $\Phi$ of the paper is constructed from the bead on a wire in
Figure~\ref{fig:One}.  We start with its Kontsevich integral:
\[
Z(\openhopf{x}{z}) \in \cA(\uparrow_z, \directedcircle_x).
\]
We then symmetrize on legs attached to the bead $x$ as explained in
Section~\ref{sec:diagrams2}:
\[
\chi^{-1}_x Z(\openhopf{x}{z}) \in \cA(\uparrow_z, \circledast_x).
\]
Finally, we use the inner product operation along the legs
$x$ to get a map from $\cB$ to $\cA$:
\[
\Phi = \iota_x \chi^{-1}_x Z(\openhopf{x}{z}): \cB \rightarrow \cA
\]
In this last step, there are two things we have to check.  First, we
must see that $\chi^{-1}Z(\OpenHopf)$ has no struts.
By Lemma~\ref{lem:struts}, this follows from the fact that we took the
bead with the zero framing.  Second,
we need to check that the inner product descends modulo the link
relations on $x$ in $\cA(\uparrow_z,\circledast_x)$.

\begin{lemma}\label{lem:glue-welldef}
The inner product $\langle\cdot\comma\cdot\rangle_x:\cA(\ast_x\cup X)
\otimes \cA(\ast_x)\rightarrow\cA(X)$ descends to a map
$\langle\cdot\comma\cdot\rangle_x:\cA(\circledast_x\cup X)
\otimes \cA(\ast_x) \rightarrow \cA(X)$.
\end{lemma}

\begin{proof} We use a sliding argument similar to the one in the
proof of Lemma~\ref{lem:line-circle}.  Link relations in
$\cA(\circledast_x\udot X)$ can be slid over diagrams in
$\cA(\ast_x)$, as shown in Figure~\ref{fig:phi-welldef}.
\end{proof}

\begin{figure}[htbp]
\[
\mathcenter{\fig{phi-welldef-a}{0.28}}=
\mathcenter{\fig{phi-welldef-b}{0.28}}= 0.
\]
\caption{The proof that $\Phi(D)$ is well-defined modulo link
relations on $Z(\OpenHopf)$: link relations in $Z(\OpenHopf)$ can be
slid over $D$.}
\label{fig:phi-welldef}
\end{figure}

\section{Multiplicativity of $\Phi$}\label{sec:multiplicativity} We
now come to the key lemma in the proof of Theorem~\ref{thm:wheeling}.

\begin{lemma}\label{lem:phi-multiplicative} The map $\Phi: \cB
\rightarrow \cA$ is an algebra map.
\end{lemma}

\begin{proof}
As advertised, we use the equality of links ``$1+1=2$''.  Let
us see what this equality of links says about the Kontsevich integral
of the Hopf link.  On the ``$1+1$'' side, we see the connected sum of
two open Hopf links; by Section~\ref{sec:connect-sum}, the invariant
of the connected sum is the connected sum of the invariants.  To write
this conveniently, let $H(z;x)$ be $Z(\OpenHopf) \in\cA(\uparrow_z,
\circledast_x)$, with the wire labelled by $z$ and the bead labelled
by $x$.  Then
\[
Z(\OpenHopf \connect \OpenHopf) = H(z; x_1) \connect_z H(z; x_2)
  \in \cA(\uparrow_z, \circledast_{x_1}, \circledast_{x_2}).
\]
On the ``$2$'' side, we see the disconnected cable of a Hopf link.  By
Section~\ref{sec:disconn-cable}, this becomes the coproduct $\Delta$:
\[
Z(\DCable(\OpenHopf)) = \Delta^x_{x_1x_2}H(z;x).
  \in \cA(\uparrow_z, \circledast_{x_1}, \circledast_{x_2}).
\]
Since the two tangles are isotopic, we have
\[
H(z; x_1, x_2) \overset{\text{def}}{=}
	H(z;x_1) \connect_z H(z;x_2) = \Delta^x_{x_1x_2}H(z;x)
  \in \cA(\uparrow_z, \circledast_{x_1}, \circledast_{x_2}).
\]

Now consider the map
\[
\Xi = \iota_{x_1}\iota_{x_2}H(z; x_1, x_2): \cB \otimes \cB \rightarrow \cA;
\]
in other words, in $\Xi(D_1 \otimes D_2)$ glue the $x_1$ and $x_2$
legs of $H(z;x_1,x_2)$ to $D_1$ and $D_2$ respectively.  This descends
modulo the two different link relations in $\cA(\uparrow, \circledast,
\circledast)$ by the argument of Figure~\ref{fig:phi-welldef}, applied
to $D_1$ and $D_2$ separately.  We have two different expressions for
this map from the two different expressions for $H(z; x_1, x_2)$.  On
the ``$1+1$'' side, the gluing does not interact with the connected
sum and we have
\[
\Xi(D_1, D_2) = \Phi(D_1) \connect \Phi(D_2).
\]
See Figure~\ref{fig:glue-1+1}.
For the ``$2$'' side, we use Lemma~\ref{lem:mult-comult-dual} to see that
\begin{align}
\Xi(D_1, D_2) &= \langle \Delta^x H(z; x), D_1 \otimes D_2 \rangle \\
	      &= \langle H(z; x), D_1 \udot D_2 \rangle \\
	      &= \Phi(D_1 \udot D_2).
\end{align}
See Figure~\ref{fig:glue-2}.

\ssp
\begin{figure}[tbp]
\begin{center}
\fig{glue-1+1}{0.28}
\end{center}
\caption{Gluing $Z(\OpenHopf\connect\OpenHopf)$ to $D_1 \otimes
           D_2$.}\label{fig:glue-1+1}
\end{figure}
\begin{figure}[tbp]
\begin{center}
\[
\figcent{glue-2a}{0.28} = \figcent{glue-2b}{0.28}
\]
\end{center}
\caption{Gluing $Z(\DCable\OpenHopf)$ to $D_1 \otimes D_2$ in two
equivalent ways.}
	\label{fig:glue-2}
\end{figure}
\dsp

Combining the two, we find
\[
\Phi(D_1) \connect \Phi(D_2) = \Phi(D_1 \udot D_2).
\]
\end{proof}

\section{Mapping degrees and the Duflo isomorphism}\label{sec:phi0}
We have successfully constructed a multiplicative map from $\cB$ to
$\cA$.  We will see later (see Section~\ref{sec:Hopf}) that this map $\Phi$
is the Duflo map, but we cannot yet see this.  Instead we will
consider the lowest degree term $\Phi_0$ of $\Phi$.

\begin{definition}\label{def:mapping-degree}
The {\em mapping degree} of a diagram $D \in \cA(\uparrow_z,
\circledast_x)$ with respect to $x$ is the amount $\iota_x D: \cB
\rightarrow \cA$ shifts the degree.  Explicitly, it is the degree
of~$D$ minus the number of $x$ legs of~$D$.
\end{definition}

Since there are no $x$-$x$ struts in $H(z;x)$, every $x$ leg of $H$
must be attached to another vertex (either internal or on the interval
$z$).  Furthermore, if two $x$ legs are attached to the same interal
vertex, the diagram vanishes by antisymmetry.  Therefore there are at
least as many other vertices as $x$ legs in $H$ and the mapping degree
is $\ge 0$.

\begin{definition}\label{def:phi0}
$H_0(z;x)$ is the part of $H(z;x)$ of mapping degree 0 with respect to
$x$.  $\Phi_0$ is $\iota_x H_0(z;x)$.
\end{definition}

$\Phi_0$ is still multiplicative, since the multiplications in $\cA$
and $\cB$ both preserve degrees.  (For homogeneous diagrams $D_1$ and
$D_2$ of degrees $n_1$ and $n_2$, $\Phi_0(D_1 \udot D_2)$ is the piece
of $\Phi(D_1 \udot D_2)$ of degree $n_1+n_2$ and likewise for
$\Phi_0(D_1) \connect \Phi_0(D_2)$.)

The diagrams that appear in $H_0$ are very restricted, since every
vertex that is not an $x$ leg must connect to an $x$ leg; since these
vertices are trivalent, the other two incident edges form a
1-manifold.  The possible diagrams are $x$ wheels and $x-z$ struts, as
shown in Figure~\ref{fig:wheels-struts}.
The linking number between the bead and the wire in the link
$\OpenHopf$ is 1, so the coefficient of the $x$-$z$ strut is 1.
Combined with the fact that the Kontsevich integral is grouplike, we
find that
\begin{align*}
H_0(z;x) &= \exp(\strutv{x}{z}) \udot \exp(\Omega') \\
\Omega' &= \sum_n a_{2n}\omega_{2n}
\end{align*}
for some coefficients $a_n$.  Note that the right hand side is
written in $\cA(\uparrow, \ast)$ (with a strange mixed product), since
there is no algebra structure on $\cA(\uparrow, \circledast)$.

\begin{figure}\label{fig:wheels-struts}
\begin{center}
\fig{wheels-struts}{0.75}
\end{center}
\caption{The only diagrams in $\cA(\uparrow_z, \circledast_x)$ of
mapping degree 0 with respect to $x$ are wheels and struts.}
\end{figure}

By the following lemma, we now have a multiplicative map very similar
to our desired map~$\Upsilon$.

\begin{lemma}
$\Phi_0 = \chi \circ \partial_\Omega'$.
\end{lemma}

\begin{proof}
Using Lemma~\ref{lem:mult-diffop-dual} and noting that
gluing with $\exp(\strutv{x}{z})$ takes the legs of a diagram in $\cB$
and averages over all ways of ordering them, as in the definition of
$\chi$, we see that
\[
\Phi_0(D) = \langle \exp(\strutv{x}{z} \udot \Omega', D \rangle
	  = \langle \exp(\strutv{x}{z}, \partial_\Omega'(D) \rangle
	  = \chi(\partial_\Omega'(D)).
\]
\end{proof}

To see that $\Phi_0 = \Upsilon$, we only need to check that $\Omega =
\Omega'$.  This is proved in Proposition~\ref{prop:coefficients}.

config: arxiv


TITLE: game of 2 players on an ultrafilter $\cal U$ on $\omega$ in which neither player has a winning strategy
QUESTION [0 upvotes]: There is a game of 2 players (I and II) with an ultrafilter $\cal U$ on $\omega$ such that neither player has a winning strategy. I would like to understand in this game where in which part of the solution of example $9.$ it is used that $\cal U$ is non-principal.

REPLY [1 votes]: When they say "$[0,n_1)\cup [n_2,n_3)\cup\ldots$ does not belong to $\mathcal U$," hence the set "$[0,n_0)\cup[n_1,n_2)\cup\ldots$" must belong to $\mathcal U$." Those sets aren't complements of each other! Particularly, if $\mathcal U$ is a principal ultrafilter generated by a number in $[n_0,n_1),$ then it doesn't work. Nonprincipal-ness allows us to ignore the segment $[n_0,n_1)$ since it's finite.
More concretely, if the ultrafilter is the principal ultrafilter generated by $100,$ and player 1 sets $n_0=1,$ player 2 could set $n_1=101$ and win. Of course player 1 could prevent this by picking $n_0=101$ instead and winning.
So the proof could be modified to show that player 2 has no winning strategy regardless of whether the ultrafilter is principal. Of course, when you do the similar proof that player 1 has no winning strategy, you will see that it is unavoidable to assume the ultrafilter is nonprincipal.

The game and proof are easier to think about this way:
There is a queue of all the natural numbers, and we each take turns popping an arbitrary finite number off and taking them. After $\omega$ rounds, we've exhausted the naturals and whoever's subset lands in the ultrafilter wins.
Nonprinicipal-ness implies any finite amount of stuff that has happened so far is irrelevant to who wins... only the tail of the game matters.
So, how could either player have a winning strategy? The game is symmetric, in the sense that aside from playing order, both players follow the exact same rules and have the exact same goal. Since what happened previously doesn't matter, either player could begin using any purported winning strategy at any time and win... but they can't both win, so such such a strategy can't exist.


text:
{\bf Problem.} Nine people sit down at random seats around a round table. Four of them are math majors, three others are physics majors, and the two remaining people are biology majors. What is the probability that all four math majors sit in consecutive seats?
{\bf Level.} Level 5
{\bf Type.} Counting & Probability
{\bf Solution.} There are $\binom{9}{4}=126$ ways to choose the seats for the four math majors. Of these ways, there are only 9 where the four math majors sit in consecutive seats. Therefore, the probability that the math majors sit in consecutive seats is $\frac{9}{126}=\boxed{\frac{1}{14}}$.

set_name: MATH


text:
\begin{definition}[Definition:Order Type]
Let $\left({S, \preceq_1}\right)$ and $\left({T, \preceq_2}\right)$ be [[Definition:Totally Ordered Set|totally ordered sets]].
Then $S$ and $T$ '''have the same (order) type''' {{iff}} they are [[Definition:Order Isomorphism|order isomorphic]].
\end{definition}

config: wiki