TITLE: A question regarding Eigenvalues
QUESTION [2 upvotes]: Note: $\psi,\psi^{\dagger} :\Bbb{R} \to \Bbb{C}$ and $x, \lambda_i , \hbar, m \in \Bbb{R}$
Say we know that $\lambda_1$ is a solution to the eigenvalue equation: $$\hat{\Pi}\psi(x)= \lambda_1 \psi(x) .$$ Now for the complex conjugate of $\psi$, to be denoted as $\psi^{\dagger}$, is the eigenfunction for the eigenvalue problem
$$\hat{\Pi}\psi^{\dagger}(x)=\lambda_2\psi^{\dagger}(x)$$  the same as the first, or its negative, or totally different? In other words, is
$$\lambda_1=\lambda_2 \text{ ?}$$
Thank you!
This is in reference to a quantum mechanics problem, in which I try to prove the following:
Given  $$j(x,t)=\frac{\hbar}{2 i m} \left[ \psi(x)^{\dagger}\frac{\partial \psi(x)}{\partial x}-\psi(x)\frac{\partial \psi(x)^{\dagger}}{\partial x } \right]$$
Show it can be represented in the form
$$j(x,t) =\operatorname{Re} \left[ \psi(x)^{\dagger}\frac{\hbar}{i m}\frac{\partial \psi(x)}{\partial x} \right]$$
This is related because the momentum operator is defined as  $\hat{P}= -i \hbar \hat{\nabla}=-i \hbar \dfrac{\partial}{\partial x}$  in one dimension, and this can be substituted into the Eigenvalues problem and simplified.

REPLY [1 votes]: What you really need for your problem is the following: if $z$ is a complex number, then
$$
\frac{z + z^\dagger}{2} = \text{Re}(z), \qquad \frac{z - z^\dagger}{2i} = \text{Im}(z), \qquad \text{Im}(z) = \text{Re}(\tfrac{z}{i}).
$$
See if you can prove these by writing $z = a + bi$, where $a,b \in \mathbb R$, and performing the indicated operators.
Turning to your equation for probability current, we can set $z = \psi^\dagger(x)\tfrac{\partial \psi(x)}{\partial x}$, so $z^\dagger = \psi(x) \tfrac{\partial \psi^\dagger(x)}{\partial x}$. Then
$$
j(x,t) = \frac{\hbar}{2 i m} (z - z^\dagger) = \frac{\hbar}{m} \cdot \frac{z - z^\dagger}{2i} = \frac{\hbar}{m} \text{Im}(z) = \frac{\hbar}{m} \text{Re}\left(\frac{z}{i}\right) = \text{Re}\left( \frac{\hbar}{mi} z \right) = \text{Re}\left( \frac{\hbar}{mi} \psi^\dagger(x) \frac{\partial \psi(x)}{\partial x} \right)
$$
as desired.


TITLE: An approximation of the ordered Bell numbers
QUESTION [1 upvotes]: So my problem is the following: I have $n$ ice-cream flavors and I must rank them, allowing that I can place more than one flavor in some ranks. So for example if I have 4 flavors, I can put in the first place chocolate and vanilla because I like them equally, and then strawberry and in the last place mint. So I made a rank with three spots in which I just placed 4 flavors.
If $a_n$ is the number of ways I can do this, I have to find its generating function and then with it compute $a_3$. I already know the answer for both of these questions, but I got them separately, as follows:
So we separate the number of ways we can rank $n$ flavors into a $k$-rank and then add them all together. For this purpose, we use the Stirling numbers of the second kind. If we label each flavor with an element of the set $[n]$, we can partition this set into $k$ equal parts in $S(n,k)$ ways, then we can label the $k$ ranks with labels of $[k]$ in $k!$ different ways. So this expression is $k!\cdot S(n,k)$, and therefore, $$a_n=\sum_{k=1}^n k!\cdot S(n,k)$$
It is easy to see here that $a_3=13$.
On the other hand, the expression above looks like the ordered Bell numbers, and I also found that its generating function is $$A(x)=\frac{1}{2-e^x}$$But I do not know how to further link these two expressions and with the generating function, find $a_3$. What am I missing/doing wrong? I can think maybe using asymptotic analysis? (I am not very familiar with this, but I think I can try, but if there is an easier reasoning, I will take it haha)

REPLY [1 votes]: James has already answer your question(+1) but i will introduce some ideas that will clarify the "I do not know how to further link these two expressions". If you are asking for intuition in between the expressions, the right place for it is called "Combinatorial species". Notice that $$\frac{1}{2-e^x}=\frac{1}{1-(e^x-1)}.$$ It should be clear from the geometric series that this means taking sequences (in your context this are the orders!) of whatever $e^x-1$ counts. Notice then that what $e^x-1=\sum _{n\geq 1}\frac{x^n}{n!}$ does is it creates a sequence without order (because you are dividing by $n!$) Notice that this nonempty(because we are taking out the case $n=0$) without order is what people call blocks from a partition(in your case is when the ice cream flavor is in the same rank, you do not need to order them).


TITLE: A Property of the Dirac Delta Function
QUESTION [4 upvotes]: I can't seem to prove the following property of te $\delta$- function.

Please help.

REPLY [2 votes]: Note that in the vicinity of a zero $t_i$, the function $h(t)$ can be approximated by
$$h(t)\approx h'(t_i)(t-t_i)\tag{1}$$
With $(1)$, the given integral can be written as
$$\int_{-\infty}^{\infty}f(t)\delta(h(t))dt=\sum_i\int_{t_i-\epsilon}^{t_i+\epsilon}f(t)\delta(h'(t_i)(t-t_i))dt\tag{2}$$
with some small $\epsilon>0$. Substituting $u=h'(t_i)(t-t_i)$ in $(2)$ gives
$$\begin{align}\int_{-\infty}^{\infty}f(t)\delta(h(t))dt&=\sum_i\frac{1}{h'(t_i)}\int_{-\epsilon h'(t_i)}^{\epsilon h'(t_i)}f\left(\frac{u}{h'(t_i)}+t_i\right)\delta(u)du\\&=\sum_i\frac{1}{|h'(t_i)|}\int_{-\epsilon |h'(t_i)|}^{\epsilon |h'(t_i)|}f\left(\frac{u}{h'(t_i)}+t_i\right)\delta(u)du\\&=\sum_i\frac{f(t_i)}{|h'(t_i)|}\tag{3}\end{align}$$
from which the result follows.
Note that we've assumed that the roots $t_i$ are simple, and that $h'(t_i)\neq 0$.


TITLE: super commutation of matrices
QUESTION [0 upvotes]: Let $M_{p|q}(\mathbb{C}) = M_{p|q}(\mathbb{C})_0 \oplus M_{p|q}(\mathbb{C})_1$ be the super algebra of all $(p+q) \times (p+q)$ matrices.
Let $A, B \in M_{p|q}(\mathbb{C})$ (not necessarily homogeneous), If anybody can help me with finding the necessary and sufficient condition for $A$ and $B$ to super commute, that would be very helpful to me.
Super commutator is defined as $[X,Y] = XY - (-1)^{|X||Y|}XY \,\forall\, X,Y \in M_{p|q}(\mathbb{C})_0 \sqcup M_{p|q}(\mathbb{C})_1$ and extend this definition bilinearly to full $M_{p|q}(\mathbb{C})$. $|X| = \text{homogeneous degree of X}$
Thanks for your thoughts.
Have a good day.

REPLY [1 votes]: If $$A~=~A_0+A_1\qquad\text{and}\qquad B~=~B_0+B_1,\tag{1}$$ then the supercommutator
$$[A,B]~=~[A,B]_0+[A,B]_1 \tag{2}$$
decomposes as
$$[A,B]_0~=~[A_0,B_0]+[A_1,B_1]\qquad\text{and}\qquad [A,B]_1~=~[A_0,B_1]+[A_0,B_1].\tag{3}$$
In particular$$ A\text{ and }B\text{ supercommute}\quad\Leftrightarrow\quad
[A,B]~=~0\quad\Leftrightarrow\quad [A,B]_0~=~0~~\wedge~~[A,B]_1 ~=~0,\tag{4}$$
cf. OP's question.


text:
\begin{document}

\maketitle

\begin{abstract}
Unsupervised learning from continuous visual streams is a challenging problem that cannot be naturally and efficiently managed  in the classic batch-mode setting of computation. The information stream must be carefully processed accordingly to an appropriate spatio-temporal distribution of the visual data, while most approaches of learning commonly assume uniform probability density. In this paper we focus on unsupervised learning for transferring  visual information in a truly online setting by using a computational model that is inspired to the principle of least action in physics. The maximization of the mutual information is carried out by a temporal process which yields online estimation of  the entropy terms. The model, which is based on second-order differential equations, maximizes the information transfer from the input to a discrete space of symbols related to the visual features of the input, whose computation is supported by hidden neurons. In order to better structure the input probability distribution, we use a human-like focus of attention model that, coherently with the information maximization model, is also based on second-order differential equations. We provide experimental results to support the theory by showing that the spatio-temporal filtering induced by the focus of attention allows the system to globally transfer more information from the input stream over the focused areas and, in some contexts, over the whole frames with respect to the unfiltered case that yields uniform probability distributions.
\end{abstract}

\section{Introduction}
\label{sec:intro}

Nowadays the most popular benchmarks in the machine learning community are composed of batches of data that are commonly processed in an offline manner using stochastic updates of the model parameters, periodically shuffling the available samples \citep{ILSVRC15,CIFAR,Damen2018EPICKITCHENS}. A smaller effort has been devoted by the research community to the direction of focusing on a single, potentially life-long video, in which the model continuously processes a stream of frames, that is a very natural setting resembling the flow of information that hits the eyes of each human \cite{betti-nn}.

An important feature of the human visual system that is frequently neglected in several algorithms is the attention mechanism that drives the gaze over different spatial regions of the input stimulus. As a matter of fact, it is implicitly assumed that all the pixels equally contribute to the learning process, assuming a uniform probability distribution of their coordinates over the retina. In the last few years, a lot of importance has been devoted to attention in neural models, for example in learning to play games \cite{zhang2019attention}, in learning task-specific attention \cite{taskspecificlearnedattentionNIPS2014_5542}, or in mixing bottom-up and top-down attention \cite{bottomuptopdownintegratedXiao_2015_CVPR}. A different research direction, closer to Neuroscience, is the one that specifically studies saliency in the context of the human visual attention systems \cite{borji2012state}, where dynamic models of visual attention have been recently proposed, able to predict in an online manner the trajectory of the attention \cite{NIPS2017_6972,zanca2019gravitational}.

In this paper, we cast the problem of processing a visual stream in a truly online setting, motivated by recent studies that connected learning over time and classical mechanics \cite{betti-nn,betti-tnnls,betti-ijcai}.
The framework proposed in \cite{betti-nn} naturally deals with learning problems in which time plays a crucial role, and it is well-suited to learn from streams of visual data in a principled way.
The temporal trajectories of the variables of the learning problem are modeled by the so called 4th order Cognitive Action Laws (CALs) that come from stationarity conditions of a functional, as it happens for generalized coordinates in classical mechanics.
We intersect these ideas with the recent human-like attention model of \cite{zanca2019gravitational}, that has shown state-of-the art results in focus estimation. Motion and visual features are treated as a mass distribution in the gravitational field that determines the trajectory of the focus of attention.
The focus of attention implements a filtering procedure on the input video, allowing the system to deal only with those areas that would attract the human attention.
We propose a 2nd order model that, under some mild conditions, leads to a simplified and more manageable instance of the CALs, yielding ODEs of same order of the ones that drive the attention.

With the goal of studying the impact of the focus of attention dynamics in videos, we consider the problem of transferring information from the input visual stream to the output space of a neural architecture that performs pixel-wise predictions \cite{betti-tnnls,betti-ijcai}. This problem consists in maximizing the Mutual Information (MI) index \cite{betti-nn}.
One of the key issues with MI maximization over time, especially when focusing the attention on a few pixels, is the fact that stochastic updates of the model parameters do not keep track of the entropy of the output space due to the data processed so far, leading to poorly informed updates. We investigate the case in which the global changes in the entropy of the output space are approximated by introducing a specific constraint or a moving average. It turns out that, when learning over the focus trajectory, the MI index grows more significantly  over the focused areas with respect to the unfiltered case, and, in some configurations, it is also larger than considering other distributions of the pixel coordinates. This suggests that filtering the information by a bottom-up attention model helps the system in transferring information from the whole stream.

The topic of MI maximization has recently attracted the attention of several researches \cite{belghazi2018mutual, hjelm2018learning,tian2019contrastive,oord2018representation,tschannen2019mutual}. Most of the recent works are about customized MI-based criteria to learn representations for downstream tasks, that is not the case of this paper. Moreover, \cite{hjelm2018learning,tian2019contrastive} are based on surrogate functions that loosely approximate \cite{tschannen2019mutual} the continuous MI formulation, while here we directly consider the discrete MI index, that, for instance, has been previously used as criterion to relate different views of the input data \cite{hu2017learning} or in clustering \cite{melacci2012unsupervised}. The information transferred by multi-layer networks is discussed in the context of the popular information bottleneck principle by Naftali Tishby and other authors as a mean to study deep network internal dynamics \cite{7133169,shwartz2017opening,saxe2019information}.

In summary, the contributions of this paper are: (1) we study human-like attention mechanisms in conjunction with learning in video data, (2) considering a new 2nd order differential model and (3) evaluating the impact of different criteria to approximate the entropy estimate over the whole stream.

This paper is organized as follows. Section~\ref{sec:time} describes the learning framework, 2nd order models, and the problem of MI maximization. Section~\ref{sec:foa} is about injecting the focus of attention dynamics, while experiments are reported in Section~\ref{sec:exp}. Section~\ref{sec:concl} concludes the paper with ideas for future work.

\section{Learning over Time}
\label{sec:time}
We consider the problem of processing a stream of data over time and, in particular, a stream of video frames
$t\mapsto u(t)$
from a target source, being $u(t)$ the frame at time $t$ in the time horizon $[0,T]$.
The stream is processed by a neural network whose weights and biases at time $t$ are represented by the generic vector variable $w(t)$, while $\dot{w}(t)$, $\ddot{w}(t)$ are respectively its first
and second derivatives.
Our work is rooted in the ideas presented in \cite{betti-nn,betti-tnnls,betti-ijcai}, where learning is described in analogy with classical mechanics, as a variational problem whose objective is to find a stationary point of the following functional ${\Gamma}^{(\xi)}$ of the maps $t\mapsto w(t)\in\R^n$,
\begin{equation}
{\Gamma}^{(\xi)}(w) := \int_{0}^{T} L(t,w(t),\dot{w}(t),\ddot{w}(t))\, dt = \int_{0}^{T} h(t) \bigl(K(\dot{w}(t),\ddot{w}(t)) - \xi V(w(t),u(t)) \bigl)\, dt .
\label{eq:fun}
\end{equation}
The Lagrangian $L$ is composed of a kinetic energy $K$ and a potential energy $V$, while $h(t)$, when appropriately chosen, is responsible of introducing energy dissipation. The term $\xi \in \{-1,1\}$ is selected in function of the way $K$ is implemented (see \cite{betti-tnnls} for details\footnote{In this paper we changed the notation w.r.t. \cite{betti-tnnls} in order to simplify the description of our approach.}). In particular, in \cite{betti-tnnls,betti-ijcai,betti-nn} we have $\xi=-1$, $h(t) = e^{\theta t}$, $V$ is composed of the loss function $U$ of the considered problem and a quadratic regularizer on $w(t)$, and $K$ includes the squared norm  of the derivatives plus their dot product, leading to
\begin{equation}
\medmuskip-2mu
\Gamma^{(-1)}(w)\equiv \Gamma(w) = \int_{0}^{T} e^{\theta t} \left(\frac{\alpha}{2}|\ddot{w}(t)|^2 + \frac{\beta}{2}|\dot{w}(t)|^2 + {\gamma} \dot{w}(t)\cdot\ddot{w}(t) + \frac{k}{2}|w(t)|^2 + U(w(t),u(t)) \right)\, dt ,
\label{eq:fun2}
\end{equation}
where $\theta\in\R$ and $\alpha$, $\beta$, ${\gamma}$, $k$ are custom positive scalars, $|\cdot|$ is the Euclidean norm in $\R^n$ and
$\,\cdot\,$ is the standard scalar product in $\R^n$, being $n$ the size of $w(t)$.

The Euler-Lagrange (EL) equations of Eq.~(\ref{eq:fun2}) yield the Cognitive Action Laws (CALs), 4th order differential equations that, when integrated, allows $w$ to be updated over time. In particular, they are\footnote{We removed the time index to simplify the notation. We will do it occasionally also in the rest of the paper.}
\begin{equation}
\alpha w^{(4)} + 2\theta \alpha w^{(3)} + (\theta^2\alpha+\theta{\gamma} - \beta)\ddot{w} + (\theta^2{\gamma} - \theta \beta)\dot{w} + kw + \nabla U(w,u) = 0,
\label{eq:cal}
\end{equation}
being $w^{(4)}$ and $w^{(3)}$ the fourth and third derivatives of $w$, respectively, and $\nabla U$ is the gradient
of $U$ with respect to its first argument. Cauchy's initial conditions can be provided on $w$ and $\dot w$, while stationarity conditions of $\Gamma$ prescribe that Eq.~(\ref{eq:cal}) must be paired with boundary conditions on the right border ($t=T$). Thus, in order to solve the problem of determining $w(t)$ in a causal way
(i.e. in such a way that the solution $w$ at time $t$ does not depend on values in $(t,T]$), the fulfilment of the boundary conditions in $t=T$ is approximated in \cite{betti-tnnls} by introducing a mechanism that sets (
``resets'') to zero all the derivatives up to $w^{(3)}$, whenever their norms become too large. See \cite{betti-tnnls} for more details on CALs.

\subsection{Second-Order Laws}
\label{sec:2nd}
Despite their robust principled formulation, the main drawbacks of the 4th order CALs is the difficulty in tuning the parameters that weigh the contribute of the derivatives, and the computational/memory burden due to the integration  of a 4th order ODE. Moreover, the theoretical guarantees on the stability of Eq.~(\ref{eq:cal}) are experimentally shown to not be necessarily needed, mostly due to the aforementioned derivative reset procedure \cite{betti-tnnls}.
For these reasons, in this paper we will use the CAL theory in a particular {\it causal} regime of the parameters
for which two important simplifications are attained. First, the dynamics of the weights are described by a 2nd order ODE (instead of Eq.~\eqref{eq:cal}). Second, we get direct causality without the need of any reset mechanisms.

The limiting procedure that leads to the 2nd order laws is based on a conjecture by De Giorgi~\cite{ambrosio2006ennio} which has been subsequently proved and studied in~\cite{50,49,37}.
In detail, we consider a reparametrization in terms of $\eps>0$ of the $\Gamma$ functional, where
$\theta\to -1/\eps$, $\alpha\to \eps^2\alpha$, $\beta\to \eps\beta$.
This allows us to rewrite Eq.~(\ref{eq:fun2}) in line with De Giorgi's functional,
\begin{equation}
{\Gamma}_{\eps}(w) := \int_{0}^{T} e^{-t/\eps} \left(\frac{\alpha\eps^2}{2}|\ddot w(t)|^2 + \frac{\beta\eps}{2}|\dot w(t)|^2 + \frac{k}{2}|w(t)|^2 + U(w(t),u(t)) \right)\,dt,
\label{eq:fun3}
\end{equation}
where we also chose, for simplicity, $\gamma=0$.
Letting $\eps\to0$, the minima of the functional $\Gamma_\eps$ with fixed initial conditions on $w$ and $\dot w$ converges to the solution of a Cauchy problem based on a 2nd order differential equation, thus gaining full
causality, i.e., $\eps$ measures the ``degree of causality''
of the solution.
Notice that the factor $e^{-t/\eps}$ in Eq.~\eqref{eq:fun3} becomes peaked on $t=0$ as $\eps\to 0$,
and the minimization procedure of $\Gamma_\eps$
will be mainly concerned in the minimization of the loss calculated at $t=0^+$.
At a first glance, this might seem counter-intuitive. However, it becomes a useful feature when considered in conjunction with the properties of the input signal $u(t)$. Let us indicate with $\tau>0$ the temporal scale of $u(t)$, that is a small time span under which the variations of $u(t)$ are semantically negligible. The
whole temporal interval $[0,T]$ can be partitioned into $\lceil{T/\tau}\rceil$ disjoint intervals $[0,\tau),[\tau,2\tau),\dots [(\lceil{T/\tau}\rceil-1)\tau,T)$,
in each of which the aforementioned picky behaviour is not critical due to the temporal scale of $u(t)$. The minimization of Eq.~(\ref{eq:fun3}) can be iteratively defined by minimizing $\Gamma_\eps$ in each interval, where the conditions on the left boundary are given by the
solution of the minimization in the previous interval. When $\eps\ll\tau$, the minimization problem can be well interpreted
in terms of the value of $U(\cdot, u(\kappa\tau))$, for $\kappa=0,\dots,\lceil{T/\tau}\rceil-1$.

To introduce the EL equations of the newly introduced problem, for simplicity, we will describe the limiting procedure
in the interval $[0,T]$, that applies to each of the $\lceil{T/\tau}\rceil$ previously described intervals.

The EL equations for the minimizer of $\Gamma_\eps$ with initial conditions $w(0)=w^0$ and $\dot w(0)=w^1$ are
\begin{equation}
\left\{
\begin{aligned}
&\eps^2 \alpha w^{(4)}(t) - 2\eps \alpha w^{(3)}(t) + (\alpha \epsilon^2- \eps \beta)\ddot{w}(t) + \beta\dot{w}(t) + kw(t) + \nabla U(w(t),u(t)) = 0;\\
&w(0)=w^0,\quad \alpha\dot w(0)=\alpha w^1,\quad \alpha\ddot w(T)=0,\quad \alpha\eps w^{(3)}(T)=\beta\dot w(T),
 \end{aligned}\right.
\label{EL-strong-time-dep}
\end{equation}
and the following theorem holds:
\begin{theorem}\label{theorem:1}
The solution of the problem~\eqref{EL-strong-time-dep} converges (weakly in $H^1((0,T),\R^n)$ to the
solution of
\begin{equation}
\begin{cases}
\alpha\woo(t)+\beta\wo(t)+kw(t)+\nabla U(w(t),t)=0;&\\
w(0)=w^0,\qquad \wo(0)=w^1.&\\
\end{cases}
\label{limit-solution-time-dep}
\end{equation}
\end{theorem}

Equations~(\ref{limit-solution-time-dep}) are 2nd order CALs. They are simpler than the 4th order CALs of Eq.~({\ref{eq:cal}}), even if they maintain their principled nature. See the supplementary material for formal proofs and further details.

\subsection{Mutual Information in Video Streams}
\label{sec:mi}
We consider the problem of transferring information from an input visual stream to the output space of a multi-layer convolutional network with $\ell$ layers, that processes each frame and yields $m$ \textit{pixel-wise} predictions. This corresponds to the maximization of the Mutual Information (MI) from the pixels of the input frames to the $m$-dimensional output space yielded by the $m$ units of the last layer, being $m$ the size of the filter bank in layer $\ell$. Hyperbolic tangent is used as activation function in each layer $j < \ell$, while the last layer is equipped with a softmax activation, generating $m$ probabilities
$p(w,x,u)=(p_1(w,x,u),\ldots,p_{m}(w,x,u))$, being $x$ a pair of pixel coordinates and $u$ the processed frame.
This problem is studied in \cite{betti-nn} and related papers \cite{betti-ijcai,betti-tnnls}, where single-layer models (or stacks of sequentially trained single-layer models) are considered, while, in this paper, we exploit a deep network trained end-to-end. Previous approaches based on kernel machines can be found in \cite{gori2016semantic,10.1007/978-3-642-33783-3_62}.

In order to define the MI index, we consider a generic, time independent weight configuration $\omega\in\R^n$.
We introduce the average output activation on the video portion between time instants $t_1$ and $t_2$,
\begin{equation}
P(\omega,t_1,t_2) \equiv  \int_{t_1}^{t_2} \overline{P}(\omega,t)dt := \int_{t_1}^{t_2} \int_{\Retina} p(\omega,x,u({t}))\mu(x,{t})dxdt,
\label{eq:quantities}
\end{equation}
where $\mu(x,t)$ is a \textit{spatio-temporal} density and $\Retina$ is the set of points that
constitute the retina.
The MI index over the video portion $[t_1,t_2]$, is defined as
\begin{eqnarray}
\nonumber \hskip-2mm \MI(X,Y;\omega;t_1,t_2) &\hskip-2mm=\hskip-2mm& - H(Y|X;\omega;t_1,t_2) + H(Y;\omega;t_1,t_2)   \\
&\hskip-55mm=\hskip-2mm&\hskip-28mm  -\sum_{j=1}^{m} \int_{t_1}^{t_2}  \hskip-2.5mm\int_{X}\hskip-1mm p_j(\omega,x,u({t}))\log p_j(\omega,x,u({t}))\,\mu(x,{t})dxdt +\sum_{j=1}^{m}{P}_j(\omega,t_1,t_2) \log {P}_j(\omega,t_1,t_2)
\label{eq:mi}
\end{eqnarray}
where $H$ is the entropy function, and $X$ and $Y$ are random variables ($Y$ is discrete) associated with the
input\footnote{Since we are dealing with convolutional feature a realization of the random variable $X$ is specified
by the coordinates of a point $x\in\Retina$, the value of the temporal instant $t$ and the value of the video $u(t)$.}
and output space, respectively\footnote{When selecting a $\log$ in base $m$, the MI is in $[0,1]$, that is what we will assume in the rest of the paper.}. When no further information is available, $\mu$ is commonly assumed to be uniform in time and space and it is normalized such that $\int_{t_1}^{t_2}\int_\Retina \mu(x,t)dxdt= 1$.

Performing maximum-MI-based online learning of $w$ using the CALs in the time horizon $[t_1=0,t_2=T]$ is not straightforward. Once we restore the dependency of $w$ on time, by inserting $w(t)$ in place of $\omega$, we cannot simply plug (minus) the MI index as a potential loss $U$ in the Lagrangian due to the lack of temporal locality. As a matter of fact, in order to implement online learning dynamics, $U$ must be temporally local, i.e., it should depend on $w$ and $u$ at time $t$ only. For this reason, the authors of \cite{betti-nn} compute the MI index at time $t$, and not in an interval; the approximation of the MI in $[0,T]$ is yielded by the outer integration in the functional of Eq.~(\ref{eq:fun3}) (or, equivalently, in the one of  Eq.~(\ref{eq:fun2})).
A drawback of this formulation is that, due to this temporal assumption, it could lead to a loose approximation of the original term $H(Y;\cdot;\cdot,\cdot)$ of Eq.~(\ref{eq:mi}), for which the inner integration on time (Eq.~(\ref{eq:quantities})) is lost, and replaced by the outer integration of the functional. In order to better cope with the optimization dynamics, the two entropy terms are commonly weighted by positive scalars $\lambda_c$, $\lambda_e$.
In addition to the plain-vanilla case we just described (referred to as \textsc{PLA}), we explore two other alternative criteria to mitigate the impact of time locality, that we will evaluate in Section~\ref{sec:exp}. The first one (\textsc{VAR}) consists in introducing an additional auxiliary variable $s(t)$, that is used to replace $P$ of Eq.~(\ref{eq:quantities}), while its variation, $\dot{s}(t)$, is constrained to be almost equivalent to $\overline{P}(w(t),t)$. The Lagrangian is augmented with $\lambda_s |\dot{s}(t) - \overline{P}(w(t),t)|^2$, a soft-constraint that enforces $s(t)$ to approximate the case in which the probability estimate is not limited to the current frame ($\lambda_s>0$).\footnote{Probabilistic normalization must be enforced after every update of $s(t)$.}
This idea is presented in \cite{betti-nn} but not followed-up in any experimentation. As a second criterion (\textsc{AVG}), we propose to replace $P$ with the outcome $\nu$ of an averaging operation that keeps track of the past activation of the output units, i.e., $\nu(t) = \zeta_s \nu(t') + (1-\zeta_s) \overline{P}(w(t),t)$, for two consecutive time instants $t>t'$.

\section{Focus of Attention}
\label{sec:foa}

The way video data is commonly processed by machines usually lacks a key property of the human visual perception, that is the capability of exploiting eye movements to perform shifts in selective visual attention. High visual acuity is restricted to a small area in the center of the retina (fovea), and the purpose of the Focus Of Attention (FOA) is to selectively orient the gaze toward relevant areas with high information, filtering out irrelevant information from cluttered visual scenes \cite{McMains2009, kowler2010attention,zanca2019gravitational}.

In the context of Section~\ref{sec:mi}, we consider a visual stream and a neural architecture with $m$ output dimensions (per pixel), and we aim at developing the network weights $w$ such that the MI index is maximized as strongly as possible with respect to the model capacity.
Of course, restricting the attention to a subset of the spatio-temporal coordinates of the video, due to a FOA mechanism, seems to inherently carry less information than when considering the whole video. However, in the latter case, the processed data will be characterized by a larger variability, mixing up noisy/background information with what could be more useful to understand the video. Such mixture of data could be harder to disentangle by a learning model than well-selected information coming from a human-like FOA trajectory, leading to a worse MI estimate. Curiously, the learning process restricted to the FOA trajectory could end-up in facilitating the development of the weights, so that the MI computed on the whole frame area could be larger than when learning without restrictions.

Following the notation of Eq.~(\ref{eq:mi}), the MI maximization, for each $t$, is based on the spatial distribution ${\mu}(x,t)$ . Such distribution models the relevance of each coordinate $x$ when learning from frame $u(t)$. In \cite{betti-tnnls,betti-ijcai}, ${\mu}(x,t)$ is assumed to be uniform over the frame area, while in \cite{betti-nn} it is also described the idea of considering ${\mu}$ ($f$ in \cite{betti-nn}) as the most natural candidate for implementing a FOA-based mechanism. Let us assume that $a(t)$ are the spatial coordinates of the FOA at time $t$, then we define
\begin{equation}
\mu(x,t) := g(x - a(t)),
\label{eq:foa}
\end{equation}
being $g$ a function that is peaked on $a(t)$.

Following this parametrization of $\mu$, we borrow a state-of-the art model for scanpath $a(t)$ prediction defined in \cite{zanca2019gravitational}, that shares a physics-inspired formulation as CALs.
Such FOA model has been proven to be strongly human-like in free-viewing conditions \cite{DBLP:journals/corr/abs-2002-04407}. It is based on the intuition that the attention emerges as a gravitational process, in which  both low-level (gradient, contours, motion) or high-level features (objects, context) may act as gravitational masses. In particular, given the gravitational field $E(t,a(t))$, the law that drives the attention is
\begin{equation}
\ddot{a}(t) + \rho \dot{a}(t) -E(t,a(t)) = 0,
\label{eq:geymol}
\end{equation}
that is indeed another 2nd order model as the one we proposed in Section~\ref{sec:2nd} (see \cite{zanca2019gravitational} for more details). The dissipation is controlled by $\rho>0$, and the importance of each mass can also be tuned. Interestingly, Eq.~(\ref{eq:geymol}) describes the dynamics of the FOA, and it is not based on pre-computed or given saliency maps.
In this paper, following \cite{zanca2019gravitational},  we consider two basic (low-level) perceptive features as masses, the spatial gradient of the brightness and the strength of the motion field. The trajectories simulated by the model show the same patterns of movement characteristic of human eyes: \textit{fixations}, when the gaze remains still in a location of interest; \textit{saccades}, rapid movement to reallocate attention on a new target; \textit{smooth pursuit}, slow movements performed in the presence of a visual feedback with the purpose of tracking a stimulus.

Different choices on $g$ are possible. In Section~\ref{sec:exp} we will consider the extreme case in which $g(x-a(t))$ is a Dirac delta on the coordinates $a(t)$ (we will refer to it as \textsc{FOA}), so that $\mu(x,t)$ is essentially a mono-dimensional signal. A less extreme setting is the one in which $g$ is  a squared window centered in $a(t)$ that covers a small fraction of the frame (\textsc{FOAW}), while the most-relaxed setting is when $g$ is simply uniform on the whole frame (\textsc{UNI}), i.e., $a(t)$ is not used.

\section{Experimental Results}
\label{sec:exp}
\par
We evaluated the amount of information transferred from different video streams with 2nd order laws of Section~\ref{sec:2nd}, using multiple instances of the deep convolutional network described in  Section~\ref{sec:mi}. A PyTorch-based implementation can be downloaded as supplementary material.

\textbf{Models.} Architectures are referred to as \textsc{S} (Small), \textsc{D} (Deeper), \textsc{DL} (Deeper and with a Larger number of neurons), and they are based on $5\times 5$ filters (except for the last layer -- $7\times 7$ filters), $\ell=3$ (\textsc{S}) or $\ell=7$ (\textsc{D}, \textsc{DL}) layers, and either $m=10$ (\textsc{S}, \textsc{D}) or $m=32$ (\textsc{DL}) filters in layer $\ell$.
Networks \textsc{S} and \textsc{D} are composed of $20$ filters in each hidden layer, while \textsc{DL} has $32$ filters in each hidden layer.
Following Section~\ref{sec:foa}, we compared 3 potential terms based on 3 different input probability densities $\mu(x,t)$, named \textsc{UNI}, \textsc{FOA}, \textsc{FOAW} (uniform, foa-restricted, and foa-window-restricted, respectively -- window edge is $15\%$ of the min frame dimension).
For each of them, we tested the 3 criteria of Section~\ref{sec:mi} to extend the temporal locality, \textsc{PLA}, \textsc{VAR}, \textsc{AVG} (fully local, variable-based, average).
\par
\textbf{Setting \& Data.} We considered three visual streams with $105k$ frames each. The first $100k$ frames are the ones on which learning is performed, integrating the CALs. Then, the developed weights $w(T)$ are used to measure the MI index over the following $5k$ frames, directly applying the MI formulation of Eq.~(\ref{eq:mi}), i.e., $\MI(X,Y;w(T);100000,105000)$, that is what we report in the results of this section. For all the models, independently on the probability density used in their potentials, we measured the MI index using $\mu(x,t)$ in the \textsc{UNI}, \textsc{FOA}, \textsc{FOAW} cases.
\begin{wrapfigure}{r}{7.5cm}

    \centering
    \includegraphics[height=2cm]{fig/sparseMNIST.pdf}
    \includegraphics[height=2cm]{fig/carpark.pdf}
    \includegraphics[height=2cm]{fig/skypecall.pdf}
    \caption{Sample frames taken from the \textsc{SparseMNIST}, \textsc{Carpark}, \textsc{Call} streams,   left-to-right.}
    \label{fig:streams}
    \vskip -0.4cm

\end{wrapfigure}
This means that, for example, a model trained following the FOA trajectory is then evaluated in the 5k test frames either considering the whole frame area, the FOA trajectory, or the window-based FOA trajectory.
The three streams (Fig.~\ref{fig:streams}), have different properties.
The first one, \textsc{SparseMNIST}, is composed of a static frame ($280\times 280$) in which 10 digits from the MNIST data are sparsely located over a dark background. The second video, \textsc{Carpark}, is taken from a fixed camera monitoring a car parking area in front of a building. The last video, \textsc{Call}, is a recording taken from a webcam during a video call. Videos are repeated until the target number of frames is reached. The last two videos are processed at $240\times 180$ pixels per frame, grayscale, $\approx 30$ frames per second.
\begin{figure}[!hb]
    \centering
    \includegraphics[height=1.7cm]{fig/kde_mnist_regular.pdf}
    \includegraphics[height=1.7cm,trim={0 0 10mm 0},clip]{fig/scatter_mnist_regular.pdf}\hskip 2mm
    \includegraphics[height=1.7cm]{fig/kde_carpark_regular.pdf}
    \includegraphics[height=1.7cm,trim={0 0 10mm 0},clip]{fig/scatter_carpark_regular.pdf}    \hskip 2mm
    \includegraphics[height=1.7cm]{fig/kde_skypecall_regular.pdf}
    \includegraphics[height=1.7cm,trim={0 0 10mm 0},clip]{fig/scatter_skypecall_regular.pdf}
    \caption{For each stream, we show (\textit{left}) the areas mostly covered by FOA (blue: largest attention), and (\textit{right}) the scatterplots of the fixation points, with hue denoting the magnitude of the FOA velocity (blue: slower; yellow: faster). Low-speed movements happen on the most informative areas (e.g., digits, busy roads, human presence/movement, respectively).
    \label{fig:heatmaps}}
\end{figure}

\par
\textbf{Parameters.} The FOA trajectory was generated by weighing the two gravitational masses $0.1$ (frame details) and $1.0$ (motion), respectively, and adjusting $\rho \in [0.1,0.5]$ in order to adapt it to the each video. We analyze the behaviour of the FOA trajectories in Fig.~\ref{fig:heatmaps}.
After a first experimentation in which we qualitatively observed the behaviour of the 2nd order laws, we set $\alpha=0.01$, $\beta=0.1$, $k=10^{-8}$. For each model we considered multiple weighing schemes of the parameters $\lambda_c \in \{10, 100, 200, 1000\}$, $\lambda_e \in \{20, 200, 400, 2000, 4000\}$, $\lambda_s \in \{10, 100, 1000  \}$, $\zeta_s \in \{ 0.01, 0.05, 0.07\}$, selecting the ones that returned the largest MI.
As a general rule of thumb, using a lower value of the conditional entropy weighing term $\lambda_c$ w.r.t. the entropy weight $\lambda_e$, helps the model to exploit all the available output symbols.

The network weights $w(0)$ were randomly initialized, enforcing the same initialization to all the compared model.

\par
\textbf{Main result.} Our main results are highlighted in Tab. \ref{tab:exp_mi_main}.
\begin{table}
\centering
\footnotesize
\caption{Main result. Mutual Information (MI) index in three video streams, considering three neural architectures (\textsc{S}, \textsc{D}, \textsc{DL}). Each column (starting from the third one) is about the results of network trained using an input probability densities taken from \{\textsc{UNI}, \textsc{FOA}, \textsc{FOAW}\}, and tested measuring the MI index in all the three density cases (labeled in column
``Test'').}
\vskip 1mm
\resizebox{0.98\textwidth}{!}{
\begin{tabular}{ccccc|ccc|ccc}
\toprule

 \multicolumn{2}{c}{} &  \multicolumn{3}{c}{S} & \multicolumn{3}{c}{D} & \multicolumn{3}{c}{DL}  \\
\cmidrule(l){3-5}    \cmidrule(l){6-8}  \cmidrule(l){9-11}
Stream &  \multicolumn{1}{c}{Test} & 	UNI & FOA & FOAW  & 	UNI & FOA & FOAW  & 	UNI & FOA & FOAW \\
\toprule
 &    UNI   & 0.017 &  \textbf{0.112} &  0.078 &  0.004 &  \textbf{0.144} &  0.020 &  0.012 &  \textbf{0.132} &  0.026 \\
SparseMNIST & FOA & 0.239 &  \textbf{0.486} &  0.391 &  0.103 &  \textbf{0.431} &  0.229 &  0.146 &  \textbf{0.350} &  0.194\\
& FOAW & 0.154 &  \textbf{0.209} &  0.197 &  0.144 &  \textbf{0.255} &  0.157 &  0.117 &  \textbf{0.215} &  0.131 \\
\midrule

& UNI & \textbf{0.776} &  0.601 &  0.695 &  0.653 &  0.556 & \textbf{0.745} &  0.445 &  0.292 &  \textbf{0.496}  \\
Carpark   &   FOA & \textbf{0.742} &  0.675 &  0.694 &  0.678 &  0.639 &  \textbf{0.768} &  0.477 &  0.315 &  \textbf{0.529}  \\
& FOAW & \textbf{0.719} &  0.629 &  0.671 &  0.653 &  0.601 &  \textbf{0.721} &  0.501 &  0.357 &  \textbf{0.532} \\

\midrule
& UNI &  \textbf{0.329} &  0.314 &  0.315 &  0.339 &  \textbf{0.556} &  0.350 &  0.208 &  \textbf{0.304} &  0.218  \\
Call &   FOA   & \textbf{0.405} &  \textbf{0.405} & 0.371 &  0.430 &  \textbf{0.582} &  0.492 &  0.246 &  \textbf{0.365} &  0.270  \\  & FOAW & \textbf{0.429} & 0.420 &  0.413 &  0.442 &  \textbf{0.566} &  0.457 &  0.304 &  \textbf{0.374} &  0.310  \\
\bottomrule
\end{tabular}}
\label{tab:exp_mi_main}
\end{table}
Each column, starting from the third one, is about a model, defined by the pair (\textit{architecture}, \textit{density used in the training potential}). For each model, the MI index is reported when measured using different spatio-temporal densities (they are labeled in column ``Test''). We used the temporal locality criterion that led to the best results.

Overall, the models trained on FOA-based densities (columns \textsc{FOA}, \textsc{FOAW}) usually perform better than the ones that were exposed to a uniform $\mu(x,t)$ over the frame area (columns \textsc{UNI}). This is particularly noticeable in the \textsc{SparseMNIST} and \textsc{Call} streams, characterized by a still and not-much-detailed background and few regions of interest, i.e. the digits or the moving speaker, respectively. The filtering approach induced by the attention in the training stage highly improves the information transfer over most of the considered test measurements, with just a few exceptions.
These considerations holds at a lesser degree also in the \textsc{Carpark} stream, in which frames are more detailed.
The focus is attracted by a busy road or by people parking their cars. However, also the immediate surroundings of those regions contain much information, so that training with FOAW density achieves the best results in architectures \textsc{D} and \textsc{DL}, while the more extreme FOA approach do not compete with models trained considering the whole frame (UNI).
In both the \textsc{Carpark} and \textsc{Call} streams, the \textsc{S} architecture does not benefit from learning over the attention trajectory. We motivate this result by considering that \textsc{S} is a shallower model, that inherently learns lower level features that the other ones. These features are more common to different frame location, making the impact of attention less evident. In the case of \textsc{SparseMNIST}, the dark-uniform background dominates the frame, and learning over $a(t)$ induces a largest information transfer also in network \textsc{S}.
\par
\textbf{Temporal locality.} In order to evaluate the impact of the temporal locality criteria (\textsc{PLA}, \textsc{AVG}, \textsc{VAR}),
we restrict our analysis to models trained with a FOA-restricted probability density. In this case, we describe each model by the pair (\textit{architecture}, \textit{temporal locality criterion}), and we report results in Tab.~\ref{tab:exp_mi_temporal_mifoa}.
In general, the moving average criterion (\textsc{AVG}) achieves the best performances in all settings, with some exceptions.
The \textsc{Carpark} stream has temporal dynamics that are pretty repetitive and periodic (e.g., cars crossing the same crossroad etc.). Hence, the addition of a criterion to better keep track of the temporal information turns out to be less necessary.
We notice higher value of MI index in the fully temporally local case (\textsc{PLA)} in architecture \textsc{DL}.
This may be due to the fact that \textsc{DL} has a larger number parameters and units than the other nets, and it has intrinsically more capacity to memorize the temporal information. The MI index is lower that the one of the other architectures due to the largest size of the output space.
\begin{table}[!h]
\centering
\caption{Temporal locality. Mutual Information (MI) index in three video streams, considering three neural architectures (\textsc{S}, \textsc{D}, \textsc{DL}). Each column (starting from the third one) is about the results of network trained using the \textsc{FOA} trajectory with a temporal locality criterion taken from \{\textsc{PLA}, \textsc{AVG}, \textsc{VAR}\}, and tested measuring the MI index in all the three density cases (labeled in column
``Test'').}
\vskip 1mm
\resizebox{0.91\textwidth}{!}{
\begin{tabular}{ccccc|ccc|ccc}
\toprule

& &  \multicolumn{3}{c}{S} & \multicolumn{3}{c}{D} & \multicolumn{3}{c}{DL}  \\
\cmidrule(l){3-5}    \cmidrule(l){6-8}  \cmidrule(l){9-11}
Stream &  \multicolumn{1}{c}{Test} & 	PLA & AVG & VAR  & 		PLA & AVG & VAR   &	PLA & AVG & VAR  \\
\toprule
 &    UNI  & 0.071 &  \textbf{0.112} &  0.102 &  0.006 &  0.054 &  \textbf{0.144} &  0.028 &  \textbf{0.132} &  0.080  \\ SparseMNIST & FOA & 0.425 &  \textbf{0.486} &  0.298 &  0.149 &  0.321 &  \textbf{0.431} &  0.119 &  \textbf{0.350} &  0.184 \\
 & FOAW & 0.183 &  \textbf{0.209} &  0.208 &  0.146 &  0.184 &  \textbf{0.255} &  0.127 &  \textbf{0.215} &  0.176 \\

\midrule
 &    UNI   & \textbf{0.601} &  0.486 &  0.371 &  0.422 &  \textbf{0.556} &  0.315 &  \textbf{0.292} &  0.289 &  0.204 \\ Carpark & FOA & \textbf{0.675} &  0.521 &  0.401 &  0.458 &  \textbf{0.639} &  0.326 &  \textbf{0.315} &  0.307 &  0.209  \\

 & FOAW & \textbf{0.629} &  0.548 &  0.447 &  0.489 &  \textbf{0.601} &  0.389 &  \textbf{0.357} &  \textbf{0.357} &  0.277 \\
\midrule

 &    UNI   &  0.289 &  \textbf{0.314} &  0.267 &  0.259 &  \textbf{0.556} &  0.369 &  \textbf{0.304} &  0.189 &  0.200 \\ Call & FOA & 0.326 &  \textbf{0.405} &  0.265 & 0.328 &  \textbf{0.582} &  0.459 &  \textbf{0.365} &  0.214 &  0.260  \\  & FOAW & 0.383 &  \textbf{0.420} &  0.373 &   0.368 &  \textbf{0.566} &  0.443 &  \textbf{0.374} &  0.274 &  0.275 \\
\bottomrule
\end{tabular}}
\label{tab:exp_mi_temporal_mifoa}
\end{table}
\par
\textbf{Random scanpaths.}
We are left with the open question on whether the largest information transfer we experienced is due to the state-of-the art attention model we used or it is only due the reduction of the size of the input data. We compared models trained on the  FOA trajectories used so far with the same networks trained randomly sampling $a(t)$ from a uniform distribution over the retina.

The results of Fig.~\ref{fig:rndvsregular} show that the human-like trajectory estimated by the selected attention model has a clear positive impact in the information transfer.
Interestingly, in the \textsc{Carpark} case we sometimes observe that fixations which explore random coordinates highly foster information transfer.
This confirms our previous statements regarding the large amount of information in whole the frame area.
\par
\textbf{Learning dynamics.} We investigate the behaviour of the models during the training stage, in the case of architecture \textsc{D} and a single training/test probability density, \textsc{FOA}.
The plots of Fig.~\ref{fig:train_plots}, for each value $t$ of the $x$-axis, shows the MI index computed in the interval $[0,t]$ along the FOA trajectory, for different temporal criteria (\textsc{PLA}, \textsc{AVG}, \textsc{VAR}). The variable-based (\textsc{VAR}) model tends to quickly find a stationary condition of the estimated MI index value. Both \textsc{PLA} and  \textsc{AVG} incur in an initial stage with evident fluctuations before becoming more stable, usually in larger values than \textsc{VAR}. The models have to deal with pretty varied conditions at the first stages of learning, which is limited to a single location in each frame. As long as time passes and a largest portion of stream is processed, fluctuations are mitigated reaching more stable configurations.
\begin{figure}[!hb]
    \centering
    \includegraphics[width=0.32\textwidth]{fig/rnd_SparseMNIST.pdf}
    \includegraphics[width=0.32\textwidth]{fig/rnd_carpark.pdf}
    \includegraphics[width=0.32\textwidth]{fig/rnd_call.pdf}
     \vskip 0mm
    \caption{Comparison between models trained on a regular trajectory of the attention and on a random trajectory (suffix \textsc{-Rnd}), for architectures \textsc{S}, \textsc{D}, \textsc{DL}. Each bar is about a different training probability density, and the height of the bar is the test MI index along the regular FOA trajectory.}
    \label{fig:rndvsregular}
\end{figure}
\begin{figure}[!h]
    \centering
    \includegraphics[height=3cm]{fig/train_mnist.pdf}
    \includegraphics[height=3cm]{fig/train_carpark.pdf}
    \includegraphics[height=3cm]{fig/train_call.pdf}
    \caption{Learning dynamics (model \textsc{D}-\textsc{FOA}, different temporal criteria). The MI index is shown at different time instants. The index at time $t$ is evaluated along the \textsc{FOA} trajectory in the interval $[0,t]$.}
    \vskip -2mm
    \label{fig:train_plots}
\end{figure}

\section{Conclusions and Future Work}
\label{sec:concl}
In this work we delved into a novel approach to Mutual Information (MI) maximization rising from the conjunction of online entropy estimation mechanisms and human-like focus of attention.
We introduced a 2nd order differential model, providing insightful experimental results to support
the intuition that using the focus of attention to drive the learning dynamics fosters an increment of the globally transferred information from the input stream.
Future work will be devoted to enforcing coherence over the predictions performed on the focus trajectory to develop high-level representations.

\section*{Broader Impact}
Our work is a foundational study. We believe that there are neither ethical aspects nor future societal consequences that should be discussed.

\begin{ack}
This work was partly supported by the PRIN 2017 project RexLearn, funded by the Italian Ministry of Education, University and Research (grant no. 2017TWNMH2)
\end{ack}

{\small\bibliographystyle{plainnat}
\bibliography{biblio}}

\clearpage
\appendix
\setcounter{page}{1}
\setcounter{equation}{0}
\begin{center}
\Large\textbf{Supplementary Material}
\end{center}
\section{Proof of Theorem~\ref{theorem:1}}
In order to prove Theorem~\ref{theorem:1} we first describe a technical hypothesis on the potential $U$. In detail, for all $\delta$ positive there exists two positive integrable
functions
$c_\delta(t)$ and $\kappa_\delta(t)$ such that for every $z\in \R^n$ and for
all $t\in [0,T]$ we have
\begin{equation}\vert\nabla U(z,t)\vert\le \delta(U(z,t)+\vert z\vert^2)+c_\delta(t),\quad
\vert\del_t U(z,t)\vert\le \delta(U(z,t)+\vert z\vert^2)+\kappa_\delta(t) \ .
\label{growth-U}\end{equation}
Notice that here, in order to simplify the notation,  we use the same symbol for $U$ and for $\hat U(z,t):=U(z,u(t))$. We will also denote
with $w_\eps$ the solution of problem~\eqref{EL-strong-time-dep}.

As it is also remarked below the proof articulates as follow: first of all we
asses the convergence of $w_\eps\to w$ by compactness arguments,
basically by performing an estimate on the solution $w_\eps$; then the
uniform estimate on the $L^2$ norm of $\dot w_\eps$ is
 used to check that the limit
$w$ actually solves the problem~\eqref{limit-solution-time-dep}.

\begin{proof}
The proof of this theorem follows the spirit of Theorem 4.2
of~\cite{49}. We will start with an uniform (in $\eps$) estimate of $\Vert
\dot w_\eps\Vert^2_{L^2}$ and then we will use this estimate in weak form of the
Euler equation to show the convergence of $w_\eps$ to the solution
of~\eqref{limit-solution-time-dep}. We will prove the theorem in the case
$\alpha>0$ and $\beta=0$.
\par\noindent  {\sl Uniform Estimate.} Start form the differential equation
in~\eqref{EL-strong-time-dep} and scalar multiply it by $(w'_\eps-w^1)$:
\[\eps^2\alpha
\woooo_\eps\cdot(w'_\eps-w^1)-2\eps\alpha\wooo\cdot(w'_\eps-w^1)
+\alpha\woo\cdot(w'_\eps-w^1)+\nabla U\cdot(w'_\eps-w^1)=0,\]
then integrate this equation on the interval $(0,t)$, and using the boundary
conditions~\eqref{EL-strong-time-dep} integrate by parts to obtain
\[\begin{aligned}
&\eps^2\alpha\wooo_\eps(t)\cdot(w'_\eps-w^1)-\frac{\eps^2\alpha}{2}
\vert\woo_\eps(t)\vert^2 +\frac{\eps^2\alpha}{2}
\vert\woo_\eps(0)\vert^2\\
-&2\eps\alpha\wooo_\eps(t)\cdot(\wo_\eps(t)-w^1)
+2\eps\alpha\int_0^t\vert\wo_\eps(s)\vert^2\, ds +\frac{\alpha}{2}
\vert\wo_\eps(t)-w^1\vert^2\\
+&U(w_\eps(t),t)-U(w^0,0)-\int_0^t\nabla U(w_\eps(s),s)\cdot w^1\, ds
-\int_0^t\del_t U(w_\eps(s),s)\, ds.
\end{aligned}\]
Now let us integrate this equality again in the interval $(0,T)$, therefore
obtaining
\[\begin{aligned}
&\left(2\eps-\frac{3}{2}\eps^2\right)\int_0^T\alpha \vert \woo_\eps(s)\vert\, ds
+\frac{\eps^2(1+T)}{2}\alpha\vert\woo_\eps(0)\vert+\left(\frac{1}{2}-\eps\right)
\alpha\vert\wo_\eps(T)-w^1\vert^2\\
+&2\eps\alpha\int_0^T\int_0^\tau \woo_\eps(s)\, dsd\tau+\frac{\alpha}{2}\int_0^T
\vert\wo_\eps(s)-w^1\vert^2\, ds+U(w_\eps(T),T)\\
+&\int_0^T U(w_\eps(s),s)\, ds=\int_0^T\nabla U(w_\eps(s),s)\cdot w^1 +
\int_0^T\int_0^\tau\nabla U(w_\eps(s),s)\cdot w^1\, dsd\tau\\
+&(1+T)U(w^0,0)+\int_0^T\int_0^\tau\del_t U(w_\eps(s),s)\, dsd\tau.\end{aligned}\]
Now we can take all the positive (for $\eps$ small enough) terms to the right
hand side to obtain
\[\begin{aligned}
\frac{\alpha}{2}\int_0^T\vert\wo_\eps-w^1\vert^2\, dt +\int_0^T U(w_\eps(t),t)\,
dt\le &(1+T) U(w^0,0)\\
&+(1+T)\vert w^1\vert\int_0^T\vert\nabla U(w_\eps(t),t)\vert\, dt\\
&+T\int_0^T\vert\del_t U(w_\eps(t),t)\vert\, dt.
\end{aligned}\]
Now using Eq.~\eqref{growth-U} we can choose $\delta$ to
further reduce this inequality down to
\begin{equation}\label{eq:estimate1}
\frac{\alpha}{2}\int_0^T\vert\wo_\eps-w^1\vert^2\, dt +\int_0^T U(w_\eps(t),t)\,
dt\le c(T)+C(T)\int_0^T \vert w_\eps(t)\vert^2\, dt,\end{equation}
where $c(T)$ and $C(T)$ are constant with respect to the parameter $\eps$.
Using Peter-Paul inequality we have that $\vert\wo_\eps-w^1\vert^2\ge
(1-\eta')\vert \wo_\eps\vert^2+(1-1/\eta')\vert w^1\vert^2$ for all $\eta'>0$.
Similarly since $w_\eps\in H^2$, we can write $w_\eps(t)=w^0+\int_0^t
\wo_\eps$ and using Peter-Paul and Cauchy-Schwartz we also end up with the
estimate $\vert w_\eps-w^0\vert\ge (1-\eta)\vert w_\eps\vert+
(1-1/\eta)\vert w^0\vert$ for all $\eta>0$, which implies
\begin{equation}\label{eq:estimate2}
\int_0^T \vert w_\eps(t)\vert^2\, dt\le T\frac{1/\eta-1}{1-\eta}\vert
w^0\vert^2+\frac{T^2}{1-\eta}\int_0^T\vert \wo_\eps(t)\vert^2\, dt.\end{equation}
Putting together Eq.~\eqref{eq:estimate1} and~\eqref{eq:estimate2} we finally obtain
the wanted uniform bound $\alpha\Vert\wo_\eps\Vert_{L^2}\le k(T)$, where
$k(T)$ is a constant with respect to the parameter $\eps$.
\par\noindent  {\sl Convergence.} Once we have this uniform bound we can
complete the proof by arguing along the very same lines of the proof of
Section~3.2 of~\cite{49} to obtain the thesis.
\end{proof}

\iffalse
\section{Experimental setup}

\begin{figure}[h]
    \centering
    \includegraphics[width=0.4\textwidth]{fig/heatmap_sparseMNIST_regular.pdf}
    \includegraphics[width=0.4\textwidth]{fig/heatmap_carpark_regular.pdf}
    \includegraphics[width=0.4\textwidth]{fig/heatmap_skypecall_regular.pdf}

    \caption{Heatmaps (obtained via histograms) of the focus of attention on the given datasets.}
    \label{fig:heatmaps}
\end{figure}
\fi

\end{document}

config: arxiv


TITLE: When can 1-forms be written as the differential of a coordinate map?
QUESTION [0 upvotes]: So it is well known that given a smooth vector field $X$ on a smooth manifold $M$, at each point $p\in M$ we can find coordinates $(U,x)$ such that $X = \frac{\partial}{\partial x^1}$ in these coordinates.
My question is, does there exist a similar statement for $1$-forms? i.e, given a one form $\omega \in \Omega^1(M)$, does there exist a chart $(U,x)$ around $p$ so that $\omega = dx^1$.
At the moment I'm unsure but I'm leaning towards it not being true in general.
So far I have that if $\ker\omega$ is integrable locally around $p$, then I feel this is sufficient for the existence of such a chart, since we can just take the frobenius chart and scale it as necessary. However, a counterexample or proof for the general case eludes me.
Any help to clear this up for me is greatly appreciated.

REPLY [0 votes]: If the form is not closed, then it cannot be of that form (and if it is closed,  then its kernel is involutive and you can use Frobenius's theorem.)


TITLE: Torsion on $y^2=x^3+d$
QUESTION [9 upvotes]: A question that I am stuck on is: prove that the $\mathbb{Q}$-torsion subgroup of the elliptic curve $y^2=x^3+d$ has  order dividing 6. Any hints on how to start would be nice. I tried saying something about the reduced curve, but the lack of information about $d$ was a problem. I guess it amount to trying to say something about the Jacobi symbol $\big( \frac{x^3+d}{p}\big)$ for $p\nmid 6d$, but I can't see it.

REPLY [8 votes]: You can see it in this way: for all but finitely many primes $p$, there is an injective morphism of groups $E(\mathbb Q)_{tors}\to E(\mathbb F_p)$. Now take $p\equiv -1\bmod 6$. Then there are no elements of order $3$ in $\mathbb F_p^*$ and this tells you that $x\to x^3+d$ is a bijection of $\mathbb F_p$. Therefore for such $p$'s you must have $|E(\mathbb F_p)|=p+1$. Now since $m=|E(\mathbb Q)_{tors}|\mid p+1$ for all these $p$'s, you must have that all but finitely many primes $\equiv -1\bmod 6$ are $\equiv -1\bmod m$, and this is possible iff $m\mid 6$ because of Dirichlet's theorem on primes in arithmetic progression.


TITLE: Is there a introductory, but also rigorous text in Integral transforms?
QUESTION [2 upvotes]: I'm looking for a introductory textbook in integral transforms, especially Laplace and Fourier transforms.
While i'm looking for a introductory textbook, i also look for a textbook that have a good (not necessarily analysis) level of rigor. Do you know any text of this kind?
Thanks in advance.

REPLY [1 votes]: There are various different points of view on the subject, and it is impossible to be sure which you're looking for given how little you've said.
The book by Dym & McKean on Fourier series and integrals contains a great variety of applications in geometry, physics, number theory, probability, and other things. It is somewhat rigorous. It has some chapters on material in analysis on which it relies, but that is better learned from other books. One oddity for which it can reasonable be criticized is the lack of use of generalized functions (Dirac's delta and its relatives), and I suspect that's because presenting the theory of those rigorously would have been too onerous. Many books go into the use of generalized functions in this topic without attempting to be rigorous at all.


TITLE: How can $G$ a simple group always be isomorphic to $Z_p$ for some prime $p$?
QUESTION [6 upvotes]: Is it not a necessary condition that the order of two groups must be equal for them to be isomorphic?
Does "$G$ is a simple group of odd order" somehow imply "$|G|$ is prime"?"
If not, I don't see how it can't be the case that $|G|$ is some odd composite number, so it couldn't be isomorphic to any $Z_p$ where $p$ is prime.

REPLY [2 votes]: Is it not a necessary condition that the order of two groups must be
  equal for them to be isomorphic?

It is. Any two isomorphic groups have the same order.

Does "$G$ is a simple group of odd order" somehow imply "$\lvert G \rvert$ is prime"?"

Yes it does. This is equivalent to the Feit-Thompson theorem that every finite group of odd order is solvable, as discussed in the question Every simple group of odd order is isomorphic to $\mathbb{Z}_{p} $ iff every group of odd order is solvable.
That theorem was proved in the 255-page 1963 paper Solvability of groups of odd order.


TITLE: Prove that $ \binom{n}{d} \binom{n}{a} \geq \binom{n}{d+a}$
QUESTION [1 upvotes]: I'm working on a project involving monomials and I need to prove the following preposition:
Given a set of all possible monomials that can be generated up to a degree $D$ for a set of variables, the number of ways to multiply monomials of degree $d$ and degree $a$ together is greater than the total number of monomials of degree $d+a$, if $ d+a \leq n \leq D$, where $n$ is the number of variables.
For instance, if I have the set of monomials generated by 5 variables, $<v,w,x,y,z>$, I can select all degree 2 monomials and put them in this great big set, call in $U$. So something like $vx \subset U$ will be true. I can generate all monomials of degree 3 and put in this set $V$. There will be $5 \choose 2$ ways and $5 \choose 3$ ways to do this respectively.
What I wish to show is if I take every element of $U$ and $V$ and do a multiply them together, there will be repeats that can be cancelled off. For instance, $xy, wz \subset U$ and $vwz, vxy \subset V$, but multiplying their respective elements together give the same degree 5 monomial.
More specifically, I'm trying to prove that for any $n, d, a \geq 0$, $$ \binom{n}{d} \binom{n}{a} \geq \binom{n}{d+a}$$
Intutively, this seems true. But how do I go about proving it? I've tried doing it via induction but result that was unexpected:
My induction over $n$ is:
Assume $ n \choose
 d$*$n \choose a$ $\geq$ $n \choose {d+a}$ is true.
Then we need to prove: $ n+1 \choose
 d$*$n+1 \choose a$ $\geq$ $n+1 \choose {d+a}$ is true.
This means $$\frac{((n+1)!)^2}{d!a!(n+1-d)!(n+1-a)!} \geq \frac{(n+1)!}{(d+a)!(n+1-d-a)!}$$
$$\frac{(n+1)^2(n!)^2}{d!a!(n+1-d)(n-d)!(n+1-a)(n-a)!} \geq \frac{(n+1)(n!)}{(d+a)!(n+1-d-a)(n-d-a)!}$$
$$\frac{(n+1)^2}{(n+1-a)(n+1-d)}\binom{n}{d}\binom{n}{a} \geq \frac{n+1}{n+1-d-a}\binom{n}{d+a}$$
Which means that if I can prove,
$$\frac{(n+1)^2}{(n+1-a)(n+1-d)} \geq \frac{n+1}{n+1-d-a}$$
the proof will be complete.
Simplifying:
$$ \frac{(n+1)(n+1-d-a)}{(n+1-a)(n+1-d)} \geq 1$$
$$ \frac{n^2+2n+1-an-dn-a-d}{n^2+2n+1-an-dn-a-d+ad} \geq 1$$
$$ \frac{-ad}{n^2+2n+1-an-dn-a-d+ad} \geq 0$$
This obviously doesn't prove anything. Is there another way to prove this hypothesis?
Any abstract math proofs are welcome too.

REPLY [5 votes]: Hint: Let $S_k$ denote the set of subsets of $\{1,\dots,n\}$ of size $k$.  The function $f:S_d \times S_a \to \mathcal P(\{1,\dots,n\})$ given by
$$
f(A,B) = A \cup B
$$
is a map whose image contains $S_{d+a}$.


TITLE: $X$ local compact metric space contains countable dense subset $\Rightarrow X=\cup_{j=1}^{\infty} K_j$, $K_1\subset K_2\subset…$ compact
QUESTION [1 upvotes]: Let $X$ be locally compact metric space, that is every point is surrounded by a compact neighbourhood. Show that

If $X$ contains a countable dense subset $T$, then there are compact subsets $K_1\subset K_2\subset…$ so that $X=\cup_{j=1}^{\infty} K_j$

Let $t_i$ be elements of $T$, since $X$ is locally compact there is $\epsilon>0$ so that $\overline{B_{\epsilon}(t_i)}$ is compact and $X=\cup \{\overline{B_{\epsilon}(t_i)}|\epsilon\in \mathbb{Q}\}$. But how can I create an increasing sequences of compact sets?

REPLY [1 votes]: If we're in a metric space, a countable dense set means there is a countable base.
This means there is also a countable base $\{B_n\}$ so that $\overline{B_n}$ are all compact (follows from this).
Then apply the fact that finite unions of compact sets are compact to easily modify this to an increasing sequence of compacta.


TITLE: the one with the greatest
QUESTION [0 upvotes]: Show that among all the triangles with base b and prefixed perimeter p, the one with the greatest area is the corresponding isosceles triangle.
As an idea to carry out this demonstration I have used Heron's formula
$$ A = \sqrt{s(s-l1)(s-l2)(s-b)} $$
where b is the base, and l1 and l2 the other sides of the triangle. And the goal is to prove that l1 = l2, but I can't get to the result.
Can you give me a hand?

REPLY [1 votes]: The locus for the third vertex is an ellipse with the base vertices as focal points. To maximise area, we have to maximise height …


text:
\section{Combinatorial Objects and Labeling Cosets}\label{sec:comb:objs:and:lab:cos}

\paragraph{Labeling Cosets}
A \emph{labeling coset} of $V$
is set of bijective mappings
$\Delta\rho=\{\delta\rho\mid \delta\in\Delta\}$,
where $\rho$ is a
bijection from $V$ to $\{1,\ldots,|V|\}$
and $\Delta$ is a subgroup of $\sym(V)$.
Let $\rho:V\to\{1,\ldots,|V|\}$ be a bijection.
We write $\lab(V)$ for
the labeling coset $\sym(V)\rho=
\{\sigma\rho\mid \sigma\in\sym(V)\}$.
We say that $\Theta\tau$ is a \emph{labeling subcoset}
of a labeling coset $\Delta\rho$, written $\Theta\tau\leq\Delta\rho$,
if $\Theta\tau$ is a subset of $\Delta\rho$
and $\Theta\tau$ again forms a labeling coset.
For a labeling coset $\Delta\rho\leq\lab(V)$
and a $\Delta$-invariant set $A\subseteq V$, we define
the restriction of $\Delta\rho$ to $A$ as $(\Delta\rho)|_A
:=\{\lambda|_A\mid \lambda\in\Delta\rho\}$.
Observe that $(\Delta\rho)|_A$ is not necessarily a
labeling coset again since
the image of $\tilde\lambda\in(\Delta\rho)|_A$ might be a set
of natural numbers different from $\{1,\ldots,|A|\}$.
Let $\kappa$ be the unique bijection from
$\rho(A)$ to $\{1,\ldots,|A|\}$ that preserves the standard
ordering ``$<$'' of natural numbers.
We define the \emph{induced
labeling coset} of $\Delta\rho$ on $A\subseteq V$ as
$(\Delta\rho) \downarrow_A:=(\Delta\rho)|_A\kappa$.
Similarly, for a labeling coset $\Theta\tau\leq\lab(A)$,
we define the \emph{lifted
labeling coset} of $\Theta\tau$ to $V\supseteq A$ as
$(\Theta\tau)\uparrow^V:=\{\gamma\in\lab(V)\mid \gamma|_A\in\Theta\tau\}$.

\paragraph{Hereditarily Finite Sets and Combinatorial Objects}

We inductively define \emph{hereditarily finite sets}
over a ground set $V$.
Each vertex $X\in V$ and each
labeling coset $Y=\Delta\rho\leq\lab(V)$ is called an \emph{atom} and is in particular a hereditarily finite set.
Inductively, if $X_1,\ldots,X_t$ are hereditarily finite sets,
then $\CX=\{X_1,\ldots,X_t\}$ and also
$\CX=(X_1,\ldots,X_t)$ are hereditarily finite sets where $t\in\NN\cup\{0\}.$
A \emph{(combinatorial) object} is a pair~$(V,\CX)$ where~$\CX$ is a
hereditarily finite set over~$V$. The set of all (combinatorial) objects over~$V$ is denoted by $\obj(V)$. In the following, we will usually assume that~$V$ is apparent from context and identify~$\CX$ with the object~$(V,\CX)$, not distinguishing between hereditarily finite sets and combinatorial objects.

We say that an object is \emph{ordered} if the ground set $V$ is a linearly
ordered set.
An object is \emph{unordered}
if $V$ is an (unordered) set.
The linearly ordered ground sets considered in this paper are always
subsets of $\NN$ with their standard ordering ``$<$''. Additionally, we will never
consider partially ordered sets in which some but not all elements of $V$ are in
$\NN$.

The expressiveness of the object formalism is quite extensive.
In particular, we can view graphs $G=(V,E)$ with~$E\subseteq\binom{V}{2}$, hypergraphs
$X=(V,H)$ with~$H\subseteq 2^V$, and relational structures $Y=(V,R_1,\ldots,R_t)$ with~$R_i\subseteq V^{k_i}$
as unordered objects (over $V$).
A function $f:V\to V'$ can be encoded as a set
of pairs $\{(v,f(v))\mid v\in V\}$ and is thus an object.
Note that a labeling coset could in principle also be represented as a set of maps, and thus
as an object in which all atoms are of the type $X\in V$.
However, we want to succinctly represent labeling cosets via generating sets rather than as a set of labelings.
This is precisely the reason why we model them as a second kind of atom.

\paragraph{Applying Functions to Unordered Objects}
Let $V$ and $V'$ be ground sets where $V$ is unordered
and $V'$ is either unordered or ordered.
Let $\mu:V\to V'$ be a bijection.
For an object $\CX\in\obj(V)$,
the image of $\CX$ under $\mu$,
written $\CX^\mu$, is an object over $V'$ defined as follows.
For a vertex $X=v\in V$, we define $X^\mu:=\mu(v)$.
For a labeling coset $Y=\Delta\rho\leq\lab(V)$, we
define $Y^\mu=(\Delta\rho)^\mu:=\mu^{-1}\Delta\rho$.
Inductively,
for an object $\CX=\{X_1,\ldots,X_t\}$,
we define
$\CX^\mu:=\{X_1^\mu,\ldots,X_t^\mu\}$.
Analogously, for an object $\CX=
(X_1,\ldots,X_t)$, we define
$\CX^\mu:=(X_1^\mu,\ldots,X_t^\mu)$.
For example, the image of a graph $G=(V,E)$
under $\mu$
is a graph
$G^\mu=(V',E^\mu)$ that has
an edge $\{\mu(v),\mu(u)\}$,
if and only if $G$ has the edge $\{v,u\}$.

\paragraph{Automorphisms of Unordered Objects}
Two unordered objects $\CX\in\obj(V)$ and $\CX'\in\obj(V')$
are \emph{isomorphic}, written $\CX\cong\CX'$, if
there is a bijection $\phi:V\to V'$ such that
$\CX^\phi=\CX'$.
In this case, $\phi$ is called an \emph{isomorphism}.
The set of all isomorphisms
from $\CX$ to $\CX'$ is denoted by $\iso(\CX;\CX')$.
Note that we defined
isomorphism only for unordered objects\footnote{
If we wanted to have a definition of isomorphisms for objects in
general,
we should require that an isomorphisms of an object must also preserve the
order of the corresponding ground set, which is consistent with the
framework.}.
The automorphism group of
an unordered object $\CX$, written $\aut(\CX)$, consists of those
$\sigma\in\sym(V)$ for which $\CX^\sigma=\CX$. For unordered objects,
the automorphism group $\aut(\CX)$
often has a natural meaning,
e.g.,
$\aut((\Theta\tau,\Delta\rho))=\Theta\cap\Delta$ and
$\aut((A,\Delta\rho))=\stab_\Delta(A)$
where $A\subseteq V$ and
$\Theta\tau,\Delta\rho\leq\lab(V)$.

The set $\iso(V;V')$ simply consists of all
bijections from $V$ to $V'$.
However, instead of talking about bijections, we use the notation $\iso(V;V')$
to indicate and stress that both $V$ and $V'$ are unordered sets
and that for every object~$\CX$, every map~$\phi \in \iso(V;V')$ is an
isomorphism from~$\CX$ to $\CX^\phi$.

\paragraph{Canonical Forms of Unordered Objects}
A \emph{canonical form} is a function $\cf$ that
assigns each unordered object $\CX\in\obj(V)$
an ordered object $\cf(\CX)\in\obj(\{1,\ldots,|V|\})$ such that:

\begin{enumerate}[(\textnormal{CF}1)]
   \item\label{ax:cf2} $\CX\cong\CY$ implies
  $\cf(\CX)=\cf(\CY)$ for all objects $\CX,\CY$, and
  \item\label{ax:cf1} $\cf(\CX)=\CX^\lambda$
  for some $\lambda\in\lab(V)$.
\end{enumerate}

Condition (CF1) is called \emph{isomorphism invariance}
and is equivalent to $\cf(\CX)=\cf(\CX^\phi)$
for all $\phi\in\iso(V;V')$
\footnote{If we wanted to define an action of~$\phi$ on ordered objects, we
should define it to act trivially. In that case isomorphism invariance could
also be written as
$\cf(\CX)^\phi=\cf(\CX^\phi)$, which is more consistent with definitions that
follow.}.
Intuitively,
Condition (CF2) means that $\CX$ and $\cf(\CX)$ are isomorphic
if we would forget about the linear ordering of the ground set of $\cf(\CX)$.

\paragraph{Canonical Labelings of Unordered Objects}
A \emph{canonical labeling function} $\can$ is
a function that assigns each unordered object
$\CX\in\obj(V)$ a labeling coset $\can(\CX)=\Lambda\leq\lab(V)$
such that:

\begin{enumerate}[(\textnormal{CL}1)]
  \item\label{ax:cl1} $\can(\CX)=\phi\can(\CX^\phi)$
  for all $\phi\in\iso(V;V')$ and,
  \item\label{ax:cl2} $\can(\CX)=\aut(\CX)\pi$
  for some (and thus for all) $\pi\in\can(\CX)$.
\end{enumerate}

Again, Condition (CL1)
is called \emph{isomorphism invariance}.
Note that (CL1) is equivalent to
$\can(\CX)^\phi=\can(\CX^\phi)$.
Roughly speaking, this means that $\can$
is compatible with isomorphisms.
More precisely, this means that the following diagram commutes.
\begin{center}
\begin{tikzcd}
\CX \arrow{r}{\phi} \arrow{d}{\can} & \CX^\phi \arrow{d}{\can} \\
\can(\CX)\arrow{r}{\phi} & \can(\CX)^\phi
\end{tikzcd}
\end{center}
Condition (CL2) means that $\CX^\lambda$
for an arbitrary labeling $\lambda\in\can(\CX)$
does not depend on the choice of $\lambda$.

We give a connection
between isomorphisms, canonical forms
and canonical labelings.
Deciding isomorphism reduces to computing a canonical form.
The computation of a canonical form in turn
reduces to computing canonical labelings as seen next.
We claim that
$\cf(\CX):=\CX^\lambda$, where $\lambda\in\can(\CX)$ is
an arbitrary labeling, defines a canonical
form.
First, observe that the canonical form
is well defined and
does not depend on the choice of $\lambda\in\can(\CX)$
since (CL2) holds.
Next, we check (CF1) and (CF2).
Condition (CF2) holds by definition.
For (CF1) we need to show that
$\cf(\CX)=\cf(\CX^\phi)$
for all $\phi\in\iso(V;V')$.
Because of (CL1), we have
that for all $\lambda\in\can(\CX)$
there is a $\lambda'\in\can(\CX^\phi)$
such that $\lambda=\phi\lambda'$.
Therefore, $\cf(\CX)=X^\lambda=(\CX^\phi)^{\lambda'}=\cf(\CX^\phi)$ which was to
show.

The notion of canonical forms and canonical labelings can
be defined naturally also for an isomorphism-closed class of objects (e.g., all hypergraphs).
In a bootstrapping manner, we will devise canonical labeling algorithms for
certain classes of combinatorial objects
until we finally give an algorithm for objects in general.
We will in each instance state specifically what the requirements of (CL1) and
(CL2) are.\footnote{We remark that in some papers on canonization there is a
Condition~(CL3) which we do not require in our framework as we
see labeling cosets as objects themselves.}

\paragraph{Representation of Objects}
For an object $\CX\in\obj(V)$, we define
the \emph{transitive closure} of~$\CX$, written $\tranCl(\CX)$,
as all objects recursively occurring in $\CX$, i.e.,
$\tranCl(X):=\{X\}$ for $X=v\in V$
or $X=\Delta\rho\leq\lab(V)$.
And we define
$\tranCl(\CX):=\{\CX\}\cup \bigcup_{i\in[t]} \tranCl (X_i)$
for $\CX=\{X_1,\ldots,X_t\}$ or
$\CX=(X_1,\ldots,X_t)$.
As mentioned in the preliminaries, we represent labeling cosets
efficiently using generating sets.
An object itself can be efficiently represented
as colored directed acyclic graph over
the elements in its transitive closure.
With this representation,
the input size (i.e., encoding length)
of an object $\CX$ is polynomial in $|\tranCl(\CX)|+|V|+t_{\operatorname{max}}$
where $t_{\operatorname{max}}$ is the maximal length of a tuple appearing in
$\tranCl(\CX)$.

\paragraph{The Linear Ordering of Ordered Objects}
In contrast to
the previous paragraphs,
we will now consider ordered objects where
$V\subseteq\NN$.
Such objects appear in the following context.
When evaluating a canonical form, the resulting object is
ordered.
In order to compare canonical forms,
it will be an important task
to sort ordered objects in polynomial time.
To do so, we define a linear order ``$\prec$''
on objects over the natural numbers.
For two natural numbers (atoms) $X,Y\in\NN$,
we adapt the natural ordering, i.e.,
$X\prec Y$ if $X<Y$.
We inductively extend our definition.
For two sets $\CX=\{X_1,\ldots,X_s\}$ and
$\CY=\{Y_1,\ldots,Y_t\}$, we assume that the order ``$\prec$''
is already defined for the elements $X_i$ and $Y_j$.
Then we say $\CX\prec\CY$ if
$|\CX|< |\CY|$ or if $|\CX|=|\CY|$ and the smallest
element in $\CX\setminus\CY$ is smaller
than the smallest element in $\CY\setminus\CX$.
Let $\CX=(X_1,\ldots,X_s)$ and
$\CY=(Y_1,\ldots,Y_t)$
be two tuples for which ``$\prec$'' is already defined
for the entries. We say $\CX\prec\CY$
if $s$ is smaller than~$t$
or if~$s=t$ and for the smallest $i\in[t]$ for which
$X_i\neq Y_i$, we have that
$X_i\prec Y_i$.
We extend the order to labelings
over natural numbers.
For two permutations $\sigma_1,\sigma_2\in\sym(\{1,\ldots,|V|\})$
we say $\sigma_1\prec \sigma_2$ if there
is an $i\in \{1,\ldots,|V|\}$ such that $\sigma_1(i) <\sigma_2(i)$
and $\sigma_1(j)=\sigma_2(j)$ for all $1\leq j<i$.
Last but not least, we extend the definition to
labeling cosets $\Delta\rho,\Theta\tau\leq\lab(\{1,\ldots,|V|\})$.
We adapt the definition for sets, i.e.,
$\Delta\rho\prec\Theta\tau$ if
$|\Delta\rho|\leq|\Theta\tau|$ or if
$|\Delta\rho|=|\Theta\tau|$ and
the smallest element of $\Delta\rho\setminus \Theta\tau$
is smaller than the smallest element
of $\Theta\tau \setminus \Delta\rho$.
It is known that for
two labeling cosets $\Delta\rho,\Theta\tau\leq\lab(\{1,\ldots,|V|\})$
given by generating sets, the order
``$\prec$'' can be computed in time polynomial in $|V|$
(\cite{tree-width}, Corollary 22).
For completeness, we define
$X\prec Y\prec \CX\prec \CY$ for all integers $X\in\NN$,
all labeling cosets $Y=\Delta\rho\leq\lab(\{1,\ldots,|V|\})$,
all tuples $\CX$ and all sets~$\CY$.
We write $\CX\preceq\CY$ if $\CX=\CY$ or $\CX\prec\CY$.

\begin{lem}\label{lem:prec}
The ordering ``$\prec$'' on pairs of ordered objects can be computed in polynomial time.
\end{lem}

Having defined an ordering for ordered objects
that can be efficiently evaluated, we can use it as follows.
While we may not be able to distinguish non-isomorphic objects $\CX$ and $\CY$ per se, whenever we are given labelings $\lambda\in\can(\CX)$
and $\gamma\in\can(\CY)$, we can order the objects by
ordering the ordered versions $\CX^\lambda$ and $\CY^{\gamma}$
w.r.t. ``$\prec$''.


TITLE: Calculate the characteristic function of $S_n = X_1 + X_2 + . . . + X_n$
QUESTION [0 upvotes]: Let $X_1, X_2, . . . , X_n$ be mutually independent copies of X. Calculate the
characteristic function of $S_n = X_1 + X_2 + . . . + X_n$. Determine how $S_n$ is
distributed.
I am trying to solve the above question. However, I do not know how should I start. I understand that the definition of a characteristic function is
$$ϕ(t) = Ee^{itX} = \int e^{itX(w)}P(dw) $$
I have tried to find $E(S_n) = \bar{X}, $ but I do not know how can I continue.
Can anyone help please?  Thanks!

REPLY [0 votes]: Note that
$$
Ee^{itS_n}=E\prod_{i=1}^ne^{itX_i}=\prod_{i=1}^nEe^{tX_i}=\prod_{i=1}^nEe^{tX_1}=\phi_{X_1}(t)^n
$$
where in the second equality we use independence and in the third use identically distributed. Here $\phi_{X_1}(t)$ is the characteristic function of $X_1$.


TITLE: probability question on characteristic function
QUESTION [1 upvotes]: I got a big problem with my exam practice question on characteristic function. Here are two.

Let $X$, $Y$ be two independent random variables with the following characteristic functions:    $$\Phi_X(\theta)=\tfrac{1}{4}e^{i\theta}  + \tfrac{3}{4}e^{2i\theta} , \quad \Phi_Y(\theta)=\exp(e^{i\theta}-1). $$
(a) Find $E[X^2]$.
  (b) Find $P(X+Y)=2$.
  (c) Does $X+Y$ admit a Lebesgue density?

Defined on some common probability space,
  two random variables $X$, $Y$ have the
  following joint characteristic function:
  $$\Phi_{X,Y}(\theta,\eta) = \frac{1}{1+\theta^2} \cdot \exp(-i\eta-\eta^2)$$
(a) Find $\Phi_X(\theta)$ and $E[X]$ and $E[X^2]$.
(b) Find $\Phi_{X+Y}(\theta)$ and $\operatorname{Var}(X+Y)$.
(c) Prove or disprove that $X+Y$ is absolutely continuous.

Unfortunately, the lecture notes are quite poor. I am wondering if anyone can give me a link of some good notes on this part (characteristic function and convolution). Thanks and regards.

REPLY [1 votes]: A few hints.
Hint 1: Since the characteristic function
$$
\Phi_X(\theta)=\int_{-\infty}^\infty e^{it\theta}\phi(t)\,\mathrm{d}t
$$
If we take the first derivative with respect to $\theta$ and evaluate at $0$, we get
$$
-i\Phi_X^{\prime}(0)=\int_{-\infty}^\infty t\phi(t)\,\mathrm{d}t=\mathrm{E}[X]
$$
If we take the second derivative with respect to $\theta$ and evaluate at $0$, we get
$$
-\Phi_X^{\prime\prime}(0)=\int_{-\infty}^\infty t^2\phi(t)\,\mathrm{d}t=\mathrm{E}[X^2]
$$
Hint 2: the characteristic function of the sum of two random variables is the product of their characteristic functions.
Hint 3: The Riemann-Lebesgue Lemma


TITLE: Probability of having X more heads than tails for N tosses.
QUESTION [0 upvotes]: Giving a a fair coin, and tossing it N times, in how many possible outcomes would there be a point wherein there were more heads than tails tossed, ie, net heads.

REPLY [0 votes]: Tossing a coin N times is a binomial distribution and you want to solve the for the CDF=0.5.
You can work it out from the formula in the article but as a short cut ...
The chance of more heads is half the chance of unequal results.
If N is odd the chance of equal results is 0, so the chance of more heads is 0.5.
If N is even the probability of getting equal results is ${N \choose \frac{N}{2}}\frac{1}{2^N}$, so the chance of more heads is $\frac{1-{N \choose \frac{N}{2}}\frac{1}{2^N}}{2}$.


TITLE: Why doesn't this method of calculating Gaussian curvature of a sphere work?
QUESTION [2 upvotes]: Suppose we have a sphere defined as $x^2 + y^2 + z^2 = 9$. With radius of 3, we know the Gaussian Curvature should be $\frac{1}{9}$ at every point on the surface.
Since this defines a level set, the gradient gives the normals. So, the normals should be
$$\begin{bmatrix}
 2x \\\\
 2y \\\\
 2z
\end{bmatrix}$$
We can then normalize these normals, giving
$$\begin{bmatrix}
 \frac{2x}{\sqrt{4x^2+4y^2+4z^2}} \\\\
 \frac{2y}{\sqrt{4x^2+4y^2+4z^2}} \\\\
 \frac{2z}{\sqrt{4x^2+4y^2+4z^2}} \\\\
\end{bmatrix}$$
By my understanding, this gives us the surface normals on the unit sphere (the Gauss Map).
According to Wolfram MathWorld's article on Gauss Map, if we take the partial derivatives of the Gauss Map function, and then take the determinant of that matrix, we should get the curvature. The matrix in question is
$$\begin{bmatrix}
 \frac{y^2+z^2}{{(x^2+y^2+z^2)}^{\frac{3}{2}}} & \frac{-xy}{{(x^2+y^2+z^2)}^{\frac{3}{2}}} & \frac{-xz}{{(x^2+y^2+z^2)}^{\frac{3}{2}}} \\\\
 \frac{-xy}{{(x^2+y^2+z^2)}^{\frac{3}{2}}} & \frac{x^2+z^2}{{(x^2+y^2+z^2)}^{\frac{3}{2}}} & \frac{-yz}{{(x^2+y^2+z^2)}^{\frac{3}{2}}} \\\\
 \frac{-xz}{{(x^2+y^2+z^2)}^{\frac{3}{2}}} & \frac{-yz}{{(x^2+y^2+z^2)}^{\frac{3}{2}}} & \frac{x^2+y^2}{{(x^2+y^2+z^2)}^{\frac{3}{2}}}
\end{bmatrix}$$
However, if we pick a point on the sphere, (0,3,0), then the resulting determinant is zero when we plug in that point. Where am I going wrong? The result should be $\frac{1}{9}$.

REPLY [2 votes]: First observe that your normalization simplifies greatly since $x^2 + y^2 + z^2 = 9$.  So really the unit normal vector is just $\frac{1}{3} (x,y,z)$.  Now the Gauss map takes the sphere to the unit sphere and the differential of this in coordinates should be a two by two matrix since this is a map between surfaces.  Locally we can choose any two of $x,y,z$ to serve as coordinates on the sphere.  Then the differential of the Gauss map in such coordinates is just 1/3 times the (2x2) identity matrix so the determinant is 1/9.


TITLE: Cat and Mice puzzle!
QUESTION [7 upvotes]: I was studying an Iranian olympiad book problems then I faced a very intersting puzzle, I wanted to solve this but faced lots of problems. I'd like to share this with you and know your mind.
We have divided the following figure garden into two areas with fences.We have drawn the fences on a simple and closed curve.
Only three parts of the garden are known and the rest of the garden is covered with trees.
Three cats are waiting for the mice.
All three are in the outer area and can not cross the fence. How many mice might be trapped? (Iranan Math Olympiad).

REPLY [5 votes]: Hint:
The walls form a closed curve, so every time you cross a wall you go from the outside area to the inside area, or vice versa.

REPLY [4 votes]: Since the fence is a simple closed curve, and the cats are on the outside, we can tell which  mice are on the inside by counting how fences a nearby cat has to cross to reach a particular mouse.
Every time you cross a fence, you go from the inside of the curve to the outside, or the reverse. If a cat and a mouse are separated by an odd number of fence sections, the mouse is safe; if by an even number the mouse may be caught.
By inspection, only one mouse is vulnerable.