text:
\begin{document}
\title{Mathematical Analysis of Melodies: Slope and Discrete Fr\'{e}chet distance}
\author{Fumio HAZAMA\\Tokyo Denki University\\Hatoyama, Hiki-Gun, Saitama JAPAN\\
e-mail address:hazama@mail.dendai.ac.jp\\Phone number: (81)49-296-2911}
\date{\today}
\maketitle
\thispagestyle{empty}

\begin{abstract}
A directed graph, called an {\it M-graph}, is attached to every melody. Our chief concern in this paper is to investigate (1) how the positivity of the slope of the M-graph is related to {\it singability} of the melody, (2) when the M-graph has a symmetry, and (3) how we can detect a similarity between two melodies. For the third theme, we introduce the notion of {\it transposed discrete Fr\'{e}chet distance}, and show its relevance in the study of similarity detection among an arbitrary set of melodies.
\end{abstract}

\section{Introduction}
In the article [2], the authors introduced a method of attaching a graph to an arbitrary melody. We call it here the {\it M-graph} of the melody. By using the M-graph of melody as a main ingredient, we investigate in this paper (1) how the positivity of the slope of the M-graph is related to {\it singability} of the melody, (2) when the M-graph has a symmetry, and (3) how we can detect a similarity between two melodies. Accordingly we divide the paper into three parts. In the first part we focus on the slope of the M-graph, which is defined by the  method of least squares, and investigate how the slope is related to  musical characteristics of the original melody. For example, among melodies which are composed of six notes {C4, D4, E4, F4, G4, A4} and begin with C4, the largest slope is attained by (C4, D4, E4, F4, G4, A4) with slope 0.986 and the smallest slope is attained by (C4, A4, D4, G4, E4, F4)) with slope -0.729. One can see that the latter is harder to sing than the former. Through the analysis of several data including this example, we will show that the positivity of the slope is strongly related to its singability. One word of caution: We do not assert that positivity of the slope is related to its goodness. For example, the first phrase of the most famous nocturne (in E$\flat$ major) by Chopin has a (slightly) negative slope -0.089, but cannot be claimed that it is a bad melody accordingly. We see, however, that all of the fifteen other nocturnes by Chopin have positive slopes (see Table 8). We also consider how the slope of the M-graph is changed under transposition, inversion, and retrograde of the original melody. In the second part of the paper, we investigate how a symmetry of the M-graph is reflected to the character of the melody. We invite the reader to have a look at Fig. 2, which is the M-graph of the basic twelve-tone row of the string quartet Op. 28 by Webern. This amazing example leads us to the main theorem (Theorem 2.1) of the second part, which characterizes the melodies with symmetric M-graph in terms of a certain arithmetic property. In the third part of the paper we propose a distance, called {\it transposed discrete Fr\'{e}chet distance}, and show its relevance for similarity detection through several examples. The data in the final subsection come from the author's questionnaire to the students in a class on discrete geometry. The national anthem of Israel, "Twinkle, twinkle, little star", and the Japanese classical song "Kojo no Tsuki", which constitute the nearest cluster, are found to be sung simultaneously and quite harmoniously. This surprise motivated him to write this paper.\\

\section{Slope of M-graph}
\subsection{Definition of M-graph}
 In order to express a melody by a definite sequence of integers, we let C4 (middle C) correspond to 0, C$\#$4 to 1, and so on. In this way we can associate a sequence of integers with each melody. For example the melody "C4, D4, F4, E4", which is the main theme of the fourth movement of the Jupiter symphony by Mozart, corresponds to the sequence "0, 2, 5, 4". From now on we identify a melody of finite length with the sequence of integers of finite length which is constructed by this rule. Furthermore,to any sequence $\mathbf{a}=(a_1,a_2,\cdots,a_n)$ of integers, we attach a sequence of points $\mathbf{p}=(p_1,p_2,\cdots,p_{n-1})$ with $p_i\in\mathbf{R}^2\hspace{1mm}(1\leq i\leq n-1)$ by the following rule:
 \begin{eqnarray*}
 p_1=(a_1,a_2), p_2=(a_2,a_3),\cdots, p_{n-1}=(a_{n-1},a_n).
 \end{eqnarray*}
Let $G(\mathbf{a})=(V(\mathbf{a}),E(\mathbf{a}))$ be the directed graph with the set of vertices
\begin{eqnarray*}
V(\mathbf{a})=(p_1,p_2,\cdots,p_{n-1}),
\end{eqnarray*}
and the set of edges
\begin{eqnarray*}
E(\mathbf{a})=\{(p_1,p_2),(p_2,p_3), \cdots, (p_{n-2},p_{n-1})\}.
\end{eqnarray*}
We call $G(\mathbf{a})$ the {\it M-graph} associated to the melody $\mathbf{a}$. ("M" stands for \underline{m}elody.) When $\mathbf{a}=(0,2,5,4)$, for example, its M-graph $G(\mathbf{a})$ is depicted as follows:

\newpage
\begin{figure}[ht]
\centering
\includegraphics{melody_cluster_paper_ver2_fig1_gr1.eps}
  \caption{M-graph of Jupiter}
 \end{figure}

\noindent
The line which cuts through the M-graph in this figure is obtained by the least squares fitting. Its slope will be referred as {\it the slope} of the melody, and denoted by $s(\mathbf{a})$. In this case we see that $s(\mathbf{a})=0.342$.\\

\noindent
Remark. A formula for the slope in the method of least squares will be recalled in Proposition 1.1.

\subsection{Distribution of slopes of M-graphs}
We will show that there exists a correlation between the slope of a melody and its {\it singability}. Let us look at the set
\begin{eqnarray*}
M_4=\{(0,2,4,5), (0,2,5,4), (0,4,2,5), (0,4,5,2), (0,5,2,4), (0,5,4,2)\},
\end{eqnarray*}
which collects all the melodies consisting of C4, D4, E4, F4 beginning with C4. The slopes of these are computed as follows:

\newpage
\begin{table}[ht]
 \begin{center}
  \begin{tabular}{llc}
   \hline
   melody & note names & slope  \\
   \hline \hline
   (0,2,4,5) & (C,D,E,F) & 0.750\\
   (0,2,5,4) & (C,D,F,E) & 0.342\\
   (0,4,2,5) & (C,E,D,F) & -0.500\\
   (0,4,5,2) & (C,E,F,D) & -0.214\\
   (0,5,2,4) & (C,F,D,E) & -0.605\\
   (0,5,4,2) & (C,F,E,D) & -0.357\\
   \hline
  \end{tabular}
  \end{center}
  \caption{Slopes of four-tone melodies}
\end{table}

\noindent
Notice here that our friend (C,D,F,E) has the second highest slope among the melodies in $M_4$, and that the other melodies, except the simplest melody (C,D,E,F), have negative slopes. In order to understand what is going on, we take next the set $M_5$ of melodies consisting of C4, D4, E4, F4, G4 beginning with C4. The top three melodies with largest slope and the bottom three with smallest slope are tabulated below:
\begin{table}[ht]
 \begin{center}
  \begin{tabular}{lllc}
   \hline
   ranking & melody & note names & slope  \\
   \hline \hline
   1st & (0,2,4,5,7) & (C,D,E,F,G) & 0.915\\
   2nd & (0,2,5,4,7) & (C,D,F,E,G) & 0.576\\
   3rd & (0,2,4,7,5) & (C,D,E,G,F) & 0.467\\
   \hline
  \end{tabular}
  \end{center}
  \caption{Largest three slopes}
\end{table}\\
\begin{table}[ht]
 \begin{center}
  \begin{tabular}{lllc}
   \hline
   ranking & melody & note names & slope  \\
   \hline \hline
   -1st & (0,7,2,5,4) & (C,G,D,F,E) & -0.655\\
   -2nd & (0,7,2,4,5) & (C,G,D,E,F) & -0.617\\
   -3rd & (0,7,4,5,2) & (C,G,E,F,D) & -0.538\\
   \hline
  \end{tabular}
  \end{center}
  \caption{Smallest three slopes}
\end{table}

\noindent
The next table shows the top three and the worst three of slopes among melodies which consists of six notes C4, D4, E4, F4, G4, A4 and begins with C4:

\newpage
\begin{table}[ht]
 \begin{center}
  \begin{tabular}{lllc}
   \hline
   ranking & melody & note names & slope  \\
   \hline \hline
   1st & (0,2,4,5,7,9) & (C,D,E,F,G,A) & 0.98630\\
   2nd & (0,2,5,4,7,9) & (C,D,F,E,G,A) & 0.81507\\
   3rd & (0,2,4,7,5,9) & (C,D,E,G,F,A) & 0.64384\\
   3rd & (0,4,2,5,7,9) & (C,E,D,F,G,A) & 0.64384\\
   \hline
  \end{tabular}
  \end{center}
  \caption{Largest three slopes}
\end{table}
\begin{table}[ht]
 \begin{center}
  \begin{tabular}{lllc}
   \hline
   ranking & melody & note names & slope  \\
   \hline \hline
   -1st & (0,9,2,7,4,5) & (C,A,D,G,E,F) & -0.72932\\
   -2nd & (0,7,4,5,2,9) & (C,G,E,F,D,A) & -0.72603\\
   -3rd & (0,9,2,7,5,4) & (C,A,D,G,F,E) & -0.69925\\
   \hline
  \end{tabular}
  \end{center}
  \caption{Smallest three slopes}
\end{table}

\noindent
As the reader may notice in these examples, melodies with large (positive) slope tend to be easy to sing and those with small (negative) slope are hard to sing. The table below describes the numbers of melodies with positive, negative, or zero slope in each category:

\begin{table}[ht]
 \begin{center}
  \begin{tabular}{lccc}
   \hline
  constituent & positive & negative & zero  \\
   \hline \hline
  \{C,D,E,F,G\} & 8 & 16 & 0\\
  \{C,D,E,F,G,A\} & 45 & 75 & 0\\
  \{C,D,E,F,G,A,B\} & 262 & 457 & 1\\
   \hline
  \end{tabular}
  \end{center}
  \caption{Distribution of slopes}
\end{table}

\noindent
We notice that, in each category, the number of melodies with negative slope is about twice the number of those with positive slope. Therefore we may assert that composers choose instinctively melodies with positive slope, which constitue rather a minor part in the world of melodies, in order to make their works singable ones. \\

Keeping these observations in mind, we examine the slopes of actual melodies composed by two great composers, Schumann  and Chopin. Table 7 shows the slopes of the first phrases of the sixteen songs in "Dichterliebe" by Schumann:

\newpage
\begin{table}[ht]
 \begin{center}
  \begin{tabular}{lllllllll}
   \hline
  No. & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8  \\
   \hline
  slope & 0.183 & 0.302 & 0.951 & 0.553 & 0.545 & 0.712 & 0.438 & 0.584 \\
   \hline
  \end{tabular}
  \end{center}
\end{table}
\begin{table}[ht]
 \begin{center}
  \begin{tabular}{lllllllll}
   \hline
  No. & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16  \\
   \hline
  slope & 0.691 & 0.543 & 0.656 & 0.316 & 0.929 & -0.572 & 0.450 &0.666 \\
   \hline
  \end{tabular}
  \end{center}
  \caption{Distribution of slopes in the song cycle Dichterliebe}
\end{table}

\noindent
Among these songs, only one song has a negative slope. It is the fourteenth song, titled  "Alln\"{a}chtlich im Traume seh' ich dich," whose slope is -0.572. The fact that, when we listen to the song cycle as a whole, we feel a certain soothing effect at this 14-th song, might be related to the negativity of its slope. \\

The following table shows the slopes of all the Nocturnes composed by Chopin:\\

\newpage
\begin{table}[ht]
 \begin{center}
  \begin{tabular}{lllllllll}
   \hline
  No. & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8  \\
   \hline
  slope & 0.980 & -0.089 & 0.371 & 0.508 & 0.860 & 0.667 & 0.496 & 0.677 \\
   \hline
  \end{tabular}
  \end{center}
\end{table}
\begin{table}[ht]
\begin{center}
  \begin{tabular}{lllllllll}
   \hline
  No. & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16  \\
   \hline
  slope & 0.419 & 0.641 & 0.673 & 0.650 & 0.970 & 0.520 & 0.293 &0.099 \\
   \hline
  \end{tabular}
  \end{center}
  \caption{Distribution of slopes in Nocturnes}
\end{table}

\noindent
Among these nocturnes, only the second one has a negative slope. This nocturne also has a kind of soothing effect, which might be one of the reasons why this is widely regarded as the most popular Nocturne by Chopin. On the other hand the largest and the second largest slopes are attained by the first one (in B$\flat$ minor) and 13-th one (in C minor), respectively. Both pieces move us (or at least the author) with their distinctive deep sorrow.\\

\subsection{Slopes under transformations}
In this subsection we consider what occurs to the slope of a melody if it is transposed, inverted, or reversed.\\

For an arbitrary melody $\mathbf{x}=(x_1,\cdots,x_{n+1})$ and for any $t\in\mathbb{Z}$, let $\mathbf{x}+t=(x_1+t,\cdots,x_{n+1}+t)$, the transposition by $t$. Furthermore we denote the inversion $(-x_1,\cdots,-x_{n+1})$ by $\mathbf{x}^i$, and the retrograde $(x_{n+1},\cdots,x_1)$ by $\mathbf{x}^r$. Here we recall the formula for the slope of a point data based on the method of least squares:

\begin{prp}
Let $P$ denote a set of points $(x_1,y_1),\cdots,(x_N,y_N)$ on $\mathbb{R}^2$. Then the slope $s(P)$ obtained through the method of least squares is given by the formula
\begin{eqnarray}
s(P)=\frac{N\sum_{i=1}^Nx_iy_i-\sum_{i=1}^Nx_i\sum_{i=1}^Ny_i}{N\sum_{i=1}^Nx_i^2-\left(\sum_{i=1}^Nx_i\right)^2}.
\end{eqnarray}
\end{prp}

\noindent
(I) Transposition: The M-graph of transposition $M(\mathbf{x}+t)$ consists of the points $(x_i+t, x_{i+1}+t)\hspace{1mm}(1\leq i \leq n)$. Hence we have $M(\mathbf{x}+t)=M(\mathbf{x})+(t,t)$, namely all of the points in $M(\mathbf{x+t})$ are translations of the ones in $M(\mathbf{x})$ by one and the same point $(t,t)$. Therefore by the very definition of the method of least squares we have the following:

\begin{prp}
For any melody $\mathbf{x}$, we have
\begin{eqnarray*}
s(M(\mathbf{x}+t))=s(M(\mathbf{x})).
\end{eqnarray*}
\end{prp}

\noindent
Remark. One can prove this by a direct computation of the slope on the right hand side by using the formula (1.1).\\

\noindent
(II) Inversion: Since the numerator and the denominator of the right hand side of (1.1) are homogeneous polynomials of degree two in the variables $x_i, y_i\hspace{1mm}(1\leq i\leq N)$, both of them are invariant under the transformation $x_i\mapsto -x_i, y_i\mapsto -y_i\hspace{1mm}(1\leq i\leq N)$. Hence we have the following:

\begin{prp}
For any melody $\mathbf{x}$, we have
\begin{eqnarray*}
s(M(\mathbf{x}^i))=s(M(\mathbf{x})).
\end{eqnarray*}
\end{prp}

\noindent
Combination of Proposition 1.2 and 1.3 yields the following:

\begin{cor}
For any melody $\mathbf{x}$ and for any $t\in\mathbb{Z}$, we have
\begin{eqnarray*}
s(M(\mathbf{x}^i+t))=s(M(\mathbf{x})).
\end{eqnarray*}
\end{cor}

\noindent
For example, if $\mathbf{x}=$(A4, C5, B4, A4, E5)$=(9,12,11,9,16)$ (Paganini), then $\mathbf{x}^i+17=(8,5,6,8,1)=$(A$\flat$4, F4, G$\flat$4, A$\flat$4, D$\flat$4) (Rachmaninov). It follows from Corollary 1.1 that their slopes coincide. Actually one can see that $s(M(\mathbf{x}))=-1.333<0$, and passingly that $s(M($B$\flat$3, C4, D$\flat$4, A$\flat$3))$=-1.071<0$, but that  their concatenation satisfies $s(M($A$\flat$4, F4, G$\flat$4, A$\flat$4, D$\flat$4, B$\flat$3, C4, D$\flat$4, A$\flat$3))=0.668 . Thus Rachmaninov composed this fascinating melody with positive slope by combining the two parts with negative slope.\\

\noindent
(III) Retrograde: It turns out to be essential to deal with the numerator and the denominator of the slope separately. Accordingly we set for any melody $\mathbf{x}=(x_1,\cdots,x_{n+1}),$
\begin{eqnarray*}
N(\mathbf{x})&=&n\sum_{i=1}^nx_ix_{i+1}-\sum_{i=1}^nx_i\sum_{i=2}^{n+1}x_i,\\
D(\mathbf{x})&=&n\sum_{i=1}^nx_i^2-\left(\sum_{i=1}^nx_i\right)^2,
\end{eqnarray*}
which are obtained by setting $y_i=x_{i+1}\hspace{1mm}(i=1,\cdots,n)$ and $N=n$ in (1.1). Let us put $\mathbf{x}^r=(x_1',\cdots,x_{n+1}')$ so that $x_i'=x_{n+2-i}\hspace{1mm}(1\leq i\leq n+1)$. First we look at the numerator $N(\mathbf{x})$:

\begin{prp}
For any melody $\mathbf{x}$, we have
\begin{eqnarray*}
N(\mathbf{x}^r)=N(\mathbf{x}).
\end{eqnarray*}
\end{prp}

\noindent
{\it Proof}. This can be proved by the following straightforward computation:
\begin{eqnarray*}
N(\mathbf{x}^r)&=&n\sum_{i=1}^nx'_ix'_{i+1}-\sum_{i=1}^nx'_i\sum_{i=2}^{n+1}x'_i\\
&=&n\sum_{i=1}^nx_{n+2-i}x_{(n+2)-(i+1)}-\sum_{i=1}^nx_{n+2-i}\sum_{i=2}^{n+1}x_{n+2-i}\\
&&(by\hspace{1mm}letting\hspace{1mm}i'=n+1-i)\\
&=&n\sum_{i'=1}^nx_{i'+1}x_{i'}-\sum_{i'=1}^nx_{i'+1}\sum_{i'=0}^{n-1}x_{i'+1}\\
&=&N(\mathbf{x}).
\end{eqnarray*}
\qed\\

\noindent
The denominator is, however, not invariant under the retrograde transformation:

\begin{prp}
For any melody $\mathbf{x}$, we have
\begin{eqnarray*}
D(\mathbf{x}^r)=D(\mathbf{x})
\end{eqnarray*}
if and only if
\begin{eqnarray*}
x_1=x_{n+1}\hspace{1mm}\mbox{or}\hspace{1mm}(n+1)(x_{n+1}+x_1)=2\sum_{i=1}^{n+1}x_i.
\end{eqnarray*}
\end{prp}

\noindent
{\it Proof}. We compute the difference $D(\mathbf{x}^r)-D(\mathbf{x})$:
\begin{eqnarray*}
D(\mathbf{x}^r)-D(\mathbf{x})&=&\left(n\sum_{i=1}^n(x'_i)^2-\left(\sum_{i=1}^nx'_i\right)^2\right)\\
&&-\left(n\sum_{i=1}^nx_i^2-\left(\sum_{i=1}^nx_i\right)^2\right)\\
&=&\left(n\sum_{i=2}^{n+1}x_i^2-\left(\sum_{i=2}^{n+1}x_i\right)^2\right)\\
&&-\left(n\sum_{i=1}^nx_i^2-\left(\sum_{i=1}^nx_i\right)^2\right)\\
&=&n(x_{n+1}^2-x_1^2)+\left(\left(\sum_{i=1}^nx_i\right)^2-\left(\sum_{i=2}^{n+1}x_i\right)^2\right)\\
&=&n(x_{n+1}-x_1)(x_{n+1}+x_1)\\
&&+\left(\sum_{i=1}^nx_i-\sum_{i=2}^{n+1}x_i\right)\left(\sum_{i=1}^nx_i+\sum_{i=2}^{n+1}x_i\right)\\
&=&n(x_{n+1}-x_1)(x_{n+1}+x_1)\\
&&+(x_1-x_{n+1})\left(2\sum_{i=1}^{n+1}x_i-x_1-x_{n+1}\right)\\
&=&(x_{n+1}-x_1)\left((n+1)(x_{n+1}+x_1)-2\sum_{i=1}^{n+1}x_i\right).
\end{eqnarray*}
Hence the assertion follows.
\qed\\

\noindent
Combining Propositions 1.4 and 1.5, we have the following:

\begin{cor}
When a melody $\mathbf{x}$ begins and ends with one and the same note, $\mathbf{x}$ and its retrograde have the same slope.
\end{cor}

\subsection{Locality of the slope function}
In this subsection we will see that the slope of a melody is determined by the slopes of its parts. More precisely we show the following:

\begin{prp}
For any melody $\mathbf{x}=(x_1,\cdots,x_{n+1})$ and for any $k$ with $1\leq k\leq n-1$, let $\mathbf{x}^k$ denote the triple $(x_k,x_{k+1},x_{k+2})$ and let $s_k=s(M(\mathbf{x}^k))$. Then the slope $s(M(\mathbf{x}))$ of the whole melody is a rational function in $s_1,\cdots,s_{n-1}$.
\end{prp}

\noindent
{\it Proof}. It follows from Corollary 1.1 that $s(M(\mathbf{x}))=s(M(\mathbf{x}-x_1)$. Hence if we put $y_i=x_{i+1}-x_i\hspace{1mm}(1\leq i\leq n)$, then we have
\begin{eqnarray*}
s(M(\mathbf{x}))&=&s(M(0,y_1,y_1+y_2,\cdots,\sum_{i=1}^ny_i)\\
&=&\frac{N(0,y_1,y_1+y_2,\cdots,\sum_{i=1}^ny_i)}{D(0,y_1,y_1+y_2,\cdots,\sum_{i=1}^ny_i)},
\end{eqnarray*}
the rightmost side being the ratio of homogeneous quadratic polynomials in $y_1,\cdots,y_n$. Hence dividing the numerator and the denominator by $y_1^2$, we see that $s(M(\mathbf{x}))$ is a quotient of quadratic polynomials in $y_2/y_1, y_3/y_1, \cdots, y_n/y_1$. Hence it is a rational function in $y_2/y_1, y_3/y_2, \cdots, y_n/y_{n-1}$. On the other hand, we see that
\begin{eqnarray*}
s_k=s(M(\mathbf{x}^k))&=&s(\{(x_k,x_{k+1}), (x_{k+1},x_{k+2})\})\\
&=&\frac{x_{k+2}-x_{k+1}}{x_{k+1}-x_k}\\
&=&\frac{y_{k+1}}{y_k}
\end{eqnarray*}
holds for any $k$ with $1\leq k\leq n-1$. This completes the proof.\qed\\

\noindent
Example 3.1. When $\mathbf{x}=(x_1,x_2,x_3,x_4)$ is a melody of length 4, we have
\begin{eqnarray*}
s(M(\mathbf{x}))&=&\frac{3(x_1x_2+x_2x_3+x_3x_4)-(x_1+x_2+x_3)(x_2+x_3+x_4)}{3(x_1^2+x_2^2+x_3^2)-(x_1+x_2+x_3)^2}\\
&=&\frac{y_2^2+2y_1y_2+y_1y_3+2y_2y_3}{2(y_1^2+y_1y_2+y_2^2)}\\
&=&\frac{(y_2/y_1)^2+2(y_2/y_1)+(y_3/y_1)+2(y_2/y_1)(y_3/y_1)}{2(1+(y_2/y_1)+(y_2/y_1)^2)}\\
&=&\frac{s_1^2+2s_1+s_1s_2+2s_1^2s_2}{2(1+s_1+s_1^2)}.
\end{eqnarray*}

\noindent
Remark. For an arbitrary finite set of points $P$ in the plane, the slope $s(P)$ is \underline{not} necessarily a function in the slopes of consecutive segments. For example, let $P=\{(0,0), (1,0), (2,1)\}$. Then the slopes of consecutive segments are 0 and 1, and the whole slope is computed to be
\begin{eqnarray*}
s(P)=\frac{3\cdot2-3\cdot 1}{3\cdot 5-3^2}=\frac{1}{2}.
\end{eqnarray*}
On the other hand if we put $P'=\{(0,0), (1,0), (3,2)\}$, then the consecutive slopes are 0 and 1, and hence the local slopes coincide with those of $P$. The whole slope, however, turns out to be
\begin{eqnarray*}
s(P')=\frac{3\cdot6-4\cdot 2}{3\cdot 10-4^2}=\frac{5}{7}.
\end{eqnarray*}
Thus the slope $s(P)$ is not generally a function of local slopes.\\

\noindent
\section{Symmetry of M-graphs}
In this section we investigate for what kind of melodies their associated M-graphs have reflective symmetries.\\

For a line $\ell$ in the plane $\mathbb{R}^2$, let $ref_{\ell}:\mathbb{R}^2\rightarrow\mathbb{R}^2$ denote the reflection with the line $\ell$ as a set of fixed points. We introduce the following:

\begin{df}
For any melody $\mathbf{x}=(x_1,\cdots,x_{n+1})$, let $M(\mathbf{x})=(p_1,\cdots,p_n)$ be its M-graph so that $p_i=(x_i,x_{i+1})$ for $i=1,\cdots,n$. The melody $\mathbf{x}$ is said to have a reflective symmetry if there exists a line $\ell$ such that $ref_{\ell}(p_i)=p_{n+1-i}$ holds for any $i\in[1,n]$.
\end{df}

\noindent
For example, when $\mathbf{x}=(0,1,2,\cdots,n)$, then one can see that $\mathbf{x}$ has a reflective symmetry with respect to the line $y=-x+n$. We want to characterize the set of melodies with reflective symmetry. For this purpose we need a transformation formula. When $\ell$ is defined by the equation $y=ax+b$, we have
\begin{eqnarray}
ref_{\ell}(x,y)=\left(\frac{(1-a^2)x+2ay-2ab}{1+a^2},\frac{2ax-(1-a^2)y+2b}{1+a^2}\right).
\end{eqnarray}
On the other hand, when $\ell$ is parallel to the $y$-axis and hence defined by the equation $x=c$, we have
\begin{eqnarray*}
ref_{\ell}(x,y)=(-x+2c,y).
\end{eqnarray*}

\noindent
In the present paper we restrict our attention to the melodies without repetition, namely those with pairwise distinct entries.
First we deal with the melodies of even length $2n$, and we denote a general melody by indexing it as
\begin{eqnarray*}
\mathbf{x}=(x_{-n},x_{-(n-1)},\cdots,x_{-1},x_1,\cdots,x_{n-1},x_n).
\end{eqnarray*}
 This will ease our description of an inductive argument. We start with the case $n=2$.\\

\begin{prp}
A melody $\mathbf{x}=(x_{-2},x_{-1},x_1,x_2)$ without repetition has a reflective symmetry if and only if the following condition is satisfied:\\
\begin{eqnarray}
&&{\rm (I)}\hspace{2mm}x_2=-x_{-2}+x_{-1}+x_1,\\
&&\mbox{or}\nonumber\\
&&{\rm (II)}\hspace{2mm}x_2=x_{-2}-x_{-1}+x_1.
\end{eqnarray}
The respective axis of symmetry is given by
\begin{eqnarray}
&&{\rm (I)}\hspace{2mm}y=-x+x_{-1}+x_1,\\
&&{\rm (II)}\hspace{2mm}y=\frac{x_{-2}-x_1}{x_{-2}-2x_{-1}+x_1}x-\frac{(x_{-1}-x_1)(x_{-2}+x_1)}{x_{-2}-2x_{-1}+x_1}.
\end{eqnarray}
\end{prp}

\noindent
{\it Proof}. Let $\ell$ be the axis of symmetry. Then the following two conditions must be met:
\begin{eqnarray}
ref_{\ell}(x_{-2},x_{-1})&=&(x_1,x_2),\\
ref_{\ell}(x_{-1},x_1)&=&(x_{-1},x_1).
\end{eqnarray}

\noindent
By our assumption we have $x_{-1}\neq x_2$, and hence the condition (2.6) implies that $\ell$ is not parallel to the $y$-axis. Let $y=ax+b$ be its defining equation. It follows from the formula (2.1) that the condition (2.6) leads us to the following simultaneous equation
\begin{eqnarray}
  \left\{
    \begin{array}{l}
      \frac{(1-a^2)x_{-2}+2ax_{-1}-2ab}{1+a^2} = x_1 \\
      \frac{2ax_{-2}-(1-a^2)x_{-1}+2b}{1+a^2} = x_2
    \end{array}
  \right.
\end{eqnarray}
By multiplying $1+a^2$ on both sides of these equations, we have
\begin{eqnarray}
  \left\{
    \begin{array}{l}
     (x_{-2}+x_1)a^2-2x_{-1}a+2ab-x_{-2}+x_1=0 \\
    (x_{-1}-x_2)a^2+2x_{-2}a+2b-x_{-1}-x_2=0
    \end{array}
  \right.
\end{eqnarray}
By subtracting the first equation from the second equation multiplied by $a$, we obtain
\begin{eqnarray*}
(x_{-1}-x_2)a^3+(x_{-2}-x_1)a^2+(x_{-1}-x_2)a+(x_{-2}-x_1)=0,
\end{eqnarray*}
namely we have
\begin{eqnarray*}
(a^2+1)((x_{-1}-x_2)a+(x_{-2}-x_1))=0.
\end{eqnarray*}
Since $a$ is a real number and $x_{-1}-x_2\neq 0$, we see that
\begin{eqnarray}
a=\frac{x_{-2}-x_1}{-x_{-1}+x_2}.
\end{eqnarray}
Inserting this expression into the second equation of (2.9), we find that
\begin{eqnarray}
b=\frac{x_{-2}^2+x_{-1}^2-x_1^2-x_2^2}{2(x_{-1}-x_2)}.
\end{eqnarray}
Furthermore the condition (2.7) with these values for $a$ and $b$ is expressed as the equalities
\begin{eqnarray*}
&&x_{-2}^3-x_{-1} x_{-2}^2-x_1 x_{-2}^2+x_{-1}^2 x_{-2}-x_1^2 x_{-2}-x_2^2 x_{-2}+2 x_1 x_2
   x_{-2}\\
&&+x_{-1}^3+x_1^3+x_{-1} x_1^2+x_{-1} x_2^2+x_1 x_2^2-x_{-1}^2 x_1-2 x_{-1}^2 x_2-2 x_1^2
   x_2\\
&&=(x_{-2}^2-2 x_1 x_{-2}+x_{-1}^2+x_1^2+x_2^2-2 x_{-1} x_2)x_{-1},\\
&&x_{-1}^3-2 x_{-2} x_{-1}^2+x_1
   x_{-1}^2-x_2 x_{-1}^2+x_{-2}^2 x_{-1}-x_1^2 x_{-1}-x_2^2 x_{-1}\\
&&+2 x_{-2} x_2 x_{-1}+x_1^3+x_2^3-2 x_{-2}
   x_1^2-x_1 x_2^2+x_{-2}^2 x_1-x_{-2}^2 x_2+x_1^2 x_2\\
&&=(x_{-2}^2-2 x_1
   x_{-2}+x_{-1}^2+x_1^2+x_2^2-2 x_{-1} x_2)x_1.
\end{eqnarray*}
These equations are factored, somewhat miraculously, as
\begin{eqnarray*}
(x_{-2}-x_1)(x_{-2}-x_{-1}-x_1+x_2)(x_{-2}-x_{-1}+x_1-x_2)&=&0,\\
(x_{-1}-x_2)(x_{-2}-x_{-1}-x_1+x_2)(x_{-2}-x_{-1}+x_1-x_2)&=&0.
\end{eqnarray*}
Since $x_{-1}-x_2\neq 0$, the second equation implies that  $x_{-2}-x_{-1}-x_1+x_2=0$ or $x_{-2}-x_{-1}+x_1-x_2=0$, and both alternatives satisfy the first equation. Hence we have
\begin{eqnarray}
{\rm (I) }\hspace{1em}x_2=-x_{-2}+x_{-1}+x_1,\mbox{ {\rm or (II)} }x_2=x_{-2}-x_{-1}+x_1.
\end{eqnarray}
In case of (I), the slope $a$ and the $y$-intercept $b$ are found through (2.10) and (2.11) to be
\begin{eqnarray*}
a&=&\frac{x_{-2}-x_1}{-x_{-1}+(-x_{-2}+x_{-1}+x_1)}=\frac{x_{-2}-x_1}{-x_{-2}+x_1}=-1,\\
b&=&\frac{x_{-2}^2+x_{-1}^2-x_1^2-(-x_{-2}+x_{-1}+x_1)^2}{2(x_{-1}-(-x_{-2}+x_{-1}+x_1))}\\
&=&\frac{-2x_1^2+2(x_{-2}x_{-1}+x_{-2}x_1-x_{-1}x_1)}{2(x_{-2}-x_1)}\\
&=&\frac{2(x_{-2}-x_1)(x_{-1}+x_1)}{2(x_{-2}-x_1)}\\
&=&x_{-1}+x_1.
\end{eqnarray*}
This shows that the axis of symmetry in this case is given by (2.4), and the reflection map is given by
\begin{eqnarray*}
ref_{\ell}:(x,y)\mapsto (-y+x_{-1}+x_1, -x+x_{-1}+x_1).
\end{eqnarray*}
Therefore the condition (2.2) is also sufficient for the reflective symmetry of $\mathbf{x}$. In case of (II), a similar computation based on (2.10) and (2.11) shows that (2.5) holds true. Furthermore we notice the following interesting phenomenon in this case: the triangle $p_1p_2p_3$ is a isoceles right triangle with $\angle p_1p_2p_3=90^{\circ}$. For we have
\begin{eqnarray*}
p_2-p_1&=&(x_{-1}-x_{-2},x_1-x_{-1}),\\
p_3-p_2&=&(x_1-x_{-1},x_2-x_1)=(x_1-x_{-1},x_{-2}-x_{-1}),
\end{eqnarray*}
which are transversal and have equal lengths. Therefore the melody $\mathbf{x}=(x_{-2},x_{-1},x_1,x_{-2}-x_{-1}+x_1)$ has a reflective symmetry with the bisector of $\angle p_1p_2p_3$ as the axis of symmetry.
It follows that the condition (2.3) is also sufficient for the melody $\mathbf{x}=(x_{-2},x_{-1},x_1,x_2)$ to have a reflective symmetry. This completes the proof. \qed\\

\noindent
The following corollary can be deduced easily from Proposition 2.1, but it will facilitate our inductive argument later:

\begin{cor}
If a melody $\mathbf{x}=(x_{-2},x_{-1},x_1,x_2)$ has a reflective symmetry, then we have
\begin{eqnarray*}
x_2-x_1=x_{-1}-x_{-2}\mbox{ or }x_2-x_1=x_{-2}-x_{-1}.
\end{eqnarray*}
\end{cor}

Next we consider the melodies with six notes.
\begin{prp}
A melody $\mathbf{x}=(x_{-3},x_{-2},x_{-1},x_1,x_2,x_3)$ without repetition has a reflective symmetry if and only if
\begin{eqnarray*}
x_{-i}+x_i\mbox{ is constant for }i=1,2,3.
\end{eqnarray*}
The axis of symmetry is given by
\begin{eqnarray*}
y=-x+x_{-1}+x_1,
\end{eqnarray*}
and the reflection map  is given by
\begin{eqnarray*}
(x,y)\mapsto (-y+x_{-1}+x_1,-x+x_{-1}+x_1).
\end{eqnarray*}
\end{prp}

\noindent
{\it Proof}. Since the submelody $(x_{-2},x_{-1},x_1,x_2)$ also has a reflective symmetry, we are in the cases (I) or (II) in Proposition 2.1. \\

\noindent
(I) The case when $x_2=-x_{-2}+x_{-1}+x_1$ : The reflection in this case is given by
\begin{eqnarray*}
ref_{\ell}(x,y)=(-y+x_{-1}+x_1,-x+x_{-1}+x_1),
\end{eqnarray*}
and hence we must have
\begin{eqnarray*}
ref_{\ell}(x_{-3},x_{-2})=(-x_{-2}+x_{-1}+x_1,-x_{-3}+x_{-1}+x_1)=(x_2,x_3)
\end{eqnarray*}
Therefore we have $x_{-3}+x_3=x_{-1}+x_1$.\\

\noindent
(II) The case when $x_2=x_{-2}-x_{-1}+x_1$: Let $q_{24}$ (resp. $q_{15}$) denote the midpoint of $p_2p_4$ (resp. $p_1p_5$). Recalling that
\begin{eqnarray*}
&&p_1=(x_{-3},x_{-2}),\hspace{2mm}p_2=(x_{-2},x_{-1}),\\
&&p_4=(x_1,x_{-2}-x_{-1}+x_1),\hspace{2mm}p_5=(x_{-2}-x_{-1}+x_1,x_3),
\end{eqnarray*}
we have
\begin{eqnarray*}
&&q_{24}=(\frac{x_{-2}+x_1}{2},\frac{x_{-2}+x_1}{2}),\\
&&q_{15}=(\frac{x_{-3}+x_{-2}-x_{-1}+x_1}{2},\frac{x_{-2}+x_3}{2}).
\end{eqnarray*}
Hence we have
\begin{eqnarray}
&&\overrightarrow{p_3q_{24}}=(\frac{x_{-2}-2x_{-1}+x_1}{2},\frac{x_{-2}-x_1}{2}),\\
&&\overrightarrow{q_{24}q_{15}}=(\frac{x_{-3}-x_{-1}}{2},\frac{-x_1+x_3}{2}).
\end{eqnarray}
Note that these vectors are nonzero by our assumption. Furthermore, since these two vectors have the same direction with the axis of symmetry, the equality
\begin{eqnarray}
\overrightarrow{p_3q_{24}}=k\overrightarrow{q_{24}q_{15}}
\end{eqnarray}
holds for some $k\in\mathbb{R}^*$. Since the submelody $(x_{-3},x_{-2},x_2,x_3)$ must have the same axis of symmetry as the one for $(x_{-2},x_{-1},x_1,x_2)$, it follows from Corollary 2.1 that we necessarily have
\begin{eqnarray}
x_3-x_2=x_{-3}-x_{-2},
\end{eqnarray}
or
\begin{eqnarray}
x_3-x_2=x_{-2}-x_{-3}.
\end{eqnarray}
Accordingly we divide our argument further into two cases.\\

\noindent
Case (II.A): The case when $x_3-x_2=x_{-3}-x_{-2}$. Since we are in the case when $x_2=x_{-2}-x_{-1}+x_1$, we have
\begin{eqnarray*}
x_3-(x_{-2}-x_{-1}+x_1)=x_{-3}-x_{-2},
\end{eqnarray*}
which implies that
\begin{eqnarray*}
x_3-x_1=x_{-3}-x_{-1}.
\end{eqnarray*}
Hence we have
\begin{eqnarray*}
\overrightarrow{q_{24}q_{15}}=(\frac{x_{-3}-x_{-1}}{2},\frac{-x_1+x_3}{2})=\frac{x_{-3}-x_{-1}}{2}(1,1).
\end{eqnarray*}
This implies by (2.15) and (2.14) that the $x$-coordinate and the $y$-coordinate of $\overrightarrow{p_3q_{24}}$ must coincide, and hence it follows from (2.13) that
\begin{eqnarray*}
x_{-2}-2x_{-1}+x_1=x_{-2}-x_1.
\end{eqnarray*}
This implies that $x_{-1}=x_1$, which contradicts to our assumption. \\

\noindent
Case (II.B): The case when $x_3-x_2=x_{-2}-x_{-3}$: Note that the vector $\overrightarrow{p_1p_5}$ and the vector $\overrightarrow{p_3q_{24}}$ are transversal by symmetry assumption. Since in our case
\begin{eqnarray*}
\overrightarrow{p_1p_5}&=&(x_2,x_3)-(x_{-3},x_{-2})=(x_2-x_{-3})\cdot (1,1)\neq (0,0),\\
\end{eqnarray*}
it follows from (2.13) that the inner product of $\overrightarrow{p_1p_5}$ and $\overrightarrow{p_3q_{24}}$, which is equal to
\begin{eqnarray*}
&&\frac{x_2-x_{-3}}{2}((x_{-2}-2x_{-1}+x_1)+(x_{-2}-x_1))\\
&=&(x_2-x_{-3})(x_{-2}-x_{-1}),
\end{eqnarray*}
must become zero. This, however, contradicts to our assumption. Hence both of Case (II.A) and Case (II.B) cannot occur, and the proof is completed. \qed\\

Now we can generalize Proposition 2.2 to an arbitrary melody of even length:

\begin{thm}
For any integer $n\geq 3$, a melody $\mathbf{x}=(x_{-n},\cdots,x_{-1},x_1,\cdots,x_n)$ without repetition of length $2n$ has a reflective symmetry if and only if it satisfies the following condition:
\begin{eqnarray*}
{\rm (I)}_n:\hspace{1mm}x_{-i}+x_i\mbox{ is constant for }i=1,\cdots,n.
\end{eqnarray*}
When this condition is met, the axis $\ell$ of symmetry is the line defined by $y=-x+x_{-1}+x_1$, and the reflection map is given by
\begin{eqnarray*}
ref_{\ell}: (x,y)\mapsto (-y+x_{-1}+x_1,-x+x_{-1}+x_1).
\end{eqnarray*}
\end{thm}

\noindent
{\it Proof}. We prove this by induction on $n$. When $n=3$, this is Proposition 2.2 itself. When $n\geq 4$, suppose that  a melody $\mathbf{x}=(x_{-n},\cdots,x_{-1},x_1,\cdots,x_n)$ has a reflective symmetry. Then the submelody $(x_{-(n-1)},\cdots,x_{-1},x_1,\cdots,x_{n-1})$ also has a reflective symmetry. Then by the induction hypothesis, the assertion ${\rm (I)}_{n-1}$ holds true. Then we have
\begin{eqnarray}
x_{-(n-1)}+x_{n-1}=x_{-1}+x_1.
\end{eqnarray}
Since the reflection in this case is given by
\begin{eqnarray*}
ref_{\ell}(x,y)=(-y+x_{-1}+x_1,-x+x_{-1}+x_1),
\end{eqnarray*}
we must have
\begin{eqnarray*}
ref_{\ell}(x_{-n},x_{-(n-1)})&=&(-x_{-(n-1)}+x_{-1}+x_1,-x_{-n}+x_{-1}+x_1)\\
&=&(x_{n-1},x_n).
\end{eqnarray*}
The equality of the first entries is assured by (2.18), and that for the second entries is equivalent to
\begin{eqnarray}
x_{-n}+x_n=x_{-1}+x_1.
\end{eqnarray}
Hence the assertion ${\rm (I)}_n$ holds. Conversely, suppose that the condition ${\rm (I)}_n$ holds, and let $\ell$ be the line defined by $y=-x+x_{-1}+x_1$. Then the reflection map with the axis of symmetry $\ell$ is given by
\begin{eqnarray*}
ref_{\ell}: (x,y)\mapsto (-y+x_{-1}+x_1,-x+x_{-1}+x_1).
\end{eqnarray*}
If follows that, for any $k\in [1,n]$, we have
\begin{eqnarray*}
ref_{\ell}(x_{-k},x_{-(k-1)})&=&(-x_{-(k-1)}+x_{-1}+x_1,-x_{-k}+x_{-1}+x_1)\\
&=&(x_{k-1},x_k),
\end{eqnarray*}
which shows that the melody $\mathbf{x}$ has a reflective symmetry with the axis of symmetry $\ell$. This completes the proof. \qed\\

\noindent
Remark. For a melody of odd length without repetition, we can show the following result: When $n\geq 2$, a melody $\mathbf{x}=(x_{-n},\cdots,x_{-1},x_0,x_1,\cdots,x_n)$ without repetition has a reflective symmetry if and only if $x_{-i}+x_i=2x_0$ for any $i\in [1,n]$. This can be proved in a similar way to that for Theorem 2.1, so we omit the proof.\\

\noindent
Example. 2.1. Webern based his string quartet Op. 28 on the following row:
\begin{eqnarray*}
M_W=(7,6,9,8,12,13,10,11,15,14,17,16).
\end{eqnarray*}
Amazingly, this melody of length twelve turns out to satisfy the condition ${\rm (I)}_{6}$ in Theorem 2.1. Hence it must have a reflective symmetry. We illustrate below the M-graph of its transposition
\begin{eqnarray*}
M_{W'}=(1,0,3,2,6,7,4,5,9,8,11,10).
\end{eqnarray*}
(Note that transposing does not change the reflective property of the original melody.)

\begin{figure}[ht]
\centering
\includegraphics{melody_cluster_paper_ver2_fig2_gr1.eps}
  \caption{String quartet Op. 28 by Webern}
 \end{figure}

\noindent
The dashed line is the axis of symmetry of $M_{W'}$ and is defined by the equation $y=-x+11$.\\

\noindent
Example. 2.2. The following row is used in Ode to Napoleon Op.41 by Sh\"{o}nberg:
\begin{eqnarray*}
M_S=(1,0,4,5,9,8,3,2,6,7,11,10).
\end{eqnarray*}
Here again we are surprised that this melody satisfies the condition ${\rm (I)}_{6}$ in Theorem 2.1. Hence it has a reflective symmetry:

\newpage
\begin{figure}[ht]
\centering
\includegraphics{melody_cluster_paper_ver2_fig3_gr1.eps}
  \caption{Ode to Napoleon Op.41 by Sh\"{o}nberg}
 \end{figure}

\noindent
The dashed line is the axis of symmetry of $M_S$ and is defined by the equation $y=-x+11$.\\

\noindent
It is needless to say that every twelve-tone row does not have a reflective symmetry. Thus these two composers arrived at the above symmetrical rows through their musical intellect and instinct.

\section{Transposed Discrete Fr\'{e}chet distance}
In this section we introduce the notion of {\it transposed discrete Fr\'{e}chet distance}, abbreviated as TDFD. This is based on the discrete Fr\'{e}chet distance, abbreviated as DFD. We will show the relevance of TDFD for similarity detection among a given set of melodies. \\

\subsection{Definition of DFD and TDFD}
First we recall the definition of DFD for the convenience of the reader. (See [1], [3] for details.) Let $P=(p_1,p_2,\cdots,p_n)$ and $Q=(q_1,q_2,\cdots,q_m)$ be a pair of sequences of points in $\mathbb{R}^2$. A {\it coupling} $L$ between $P$ and $Q$ is a sequence
\begin{eqnarray*}
(p_{a_1},q_{b_1}), (p_{a_2},q_{b_2}), \cdots, (p_{a_k},q_{b_k})
\end{eqnarray*}

\noindent
of distinct pairs from $P\times Q$ such that $a_1=b_1=1, a_k=n, b_k=m$, and for any $i=1,\cdots,k-1$, we have $a_{i+1}=a_i$ or $a_{i+1}=a_i+1$, and $b_{i+1}=b_i$ or $b_{i+1}=b_i+1$. The {\it length} $||L||$ of the coupling $L$ is defined by
\begin{eqnarray*}
||L||={\rm max}_{i=1,\cdots,k}d(p_{a_i},q_{b_i}),
\end{eqnarray*}

\noindent
where $d(*,*)$ denotes the Euclid distance on $\mathbf{R}^2$. The discrete Fr\'echet distance $d_F(P,Q)$ between the sequences of points $P$ and $Q$ is defined to be
\begin{eqnarray*}
d_{F}(P,Q)={\rm min}\{||L||;\text {$L$ is a coupling between $P$ and $Q$}\}
\end{eqnarray*}

\noindent
Intuitively this can be defined as follows. A man is walking a dog on a leash. The man can move on the points in the sequence $P$, and the dog in the sequence $Q$, but backtracking is not allowed. The discrete Fr\'echet distance $d_F(P,Q)$ is the length of the shortest leash that is sufficient for traversing both sequences. For a pair of melodies $\mathbf{a}, \mathbf{b}$, we define the discrete Fr\'echet distance $d_F(\mathbf{a},\mathbf{b})$ to be $d_F(V(\mathbf{a}),V(\mathbf{b}))$. Furthermore taking into account the fact that any transposition of a melody does not change its essential feature, we define the transposed discrete Fr\'echet distance $d_{F}^{tr}(\mathbf{a},\mathbf{b})$ by the following rule:
\begin{eqnarray}
d_{F}^{tr}(\mathbf{a},\mathbf{b})=\min_{t\in\mathbb{Z}}d_F(\mathbf{a},\mathbf{b}+t)
\end{eqnarray}

\noindent
where $\mathbf{b}+t$ denotes the transposed melody $(b_1+t,\cdots,b_m+t)$. In an actual computation of $d_{F}^{tr}(\mathbf{a},\mathbf{b})$, we can choose a bound $B$ such that the minimum on the right hand side of (2.1) lies in $[-B,B]$. \\

\noindent
Example 3.1. Let $\mathbf{a}_1=(0,2,4,5,2,2,0)$ and $\mathbf{b}_1=(0,2,5,2,1)$. The point sequences which correspond to these melodies are
\begin{eqnarray*}
V(\mathbf{a}_1)=(p_1, p_2, \cdots, p_6),
\end{eqnarray*}
with
\begin{eqnarray*}
p_1=(0,2), p_2=(2,4), p_3=(4,5), p_4=(5,2), p_5=(2,2), p_6=(2,0)),
\end{eqnarray*}
and
\begin{eqnarray*}
V(\mathbf{b}_1)=(q_1, q_2, \cdots, q_4),
\end{eqnarray*}
with
\begin{eqnarray*}
q_1=(0,2), q_2=(2,5), q_3=(5,2), q_4=(2,1).
\end{eqnarray*}

\noindent
The coupling $L$ which attains the minimum of $||L||$ is found to be
\begin{eqnarray*}
L=((p_1, q_1), (p_2, q_2), (p_3, q_2), (p_4, q_3), (p_5,q_4),(p_6,q_4))
\end{eqnarray*}
with $||L||=2$. Note that when the man Paul (for $P$) goes to $p_3$, his dog Queen (for $Q$) must remain at $q_2$, because if Queen moves to $q_3$, then $d(p_3,q_3)=\sqrt{10}>2=d(p_3,q_2)$. I recommend the reader to take a walk with Queen several times, then he will be convinced that the above coupling $L$ is the best choice.\\

\noindent
Example 3.2. Let
\begin{eqnarray*}
\mathbf{a}_2&=&(0,2,4,5,7)=(C4, D4, E4, F4, G4),\\
\mathbf{b}_2&=&(2,9,7,6,4)=(D4, A4, G4, F\#4, E4).
\end{eqnarray*}
 The discrete Fr\'{e}chet distances between $\mathbf{a}_2$ and $\mathbf{b}_2+t$ with $t=-5, -4, \cdots, 0, 1$ are tabulated as follows:\\

\begin{table}[ht]
 \begin{center}
  \begin{tabular}{cl}
   \hline
  $t$ & $d_F(\mathbf{a}_2, \mathbf{b}_2+t)$\\
   \hline \hline
 -5 & 8.944\\
 -4 & 7.616\\
 -3 & 6.325\\
 -2 & 5.099\\
 -1 & 6.083\\
 0 & 7.280\\
 1 & 8.544\\
    \hline
  \end{tabular}
  \end{center}
  \caption{discrete Fr\'{e}chet distances}
\end{table}

\noindent
It follows that $d_{F}^{tr}(\mathbf{a}_2,\mathbf{b}_2)=d_F(\mathbf{a}_2,\mathbf{b}_2-2)=5.099$. This seems to be natural, since the melody $\mathbf{a}_2$ is in C major, the melody $\mathbf{b}_2$ in D major, and $C4-D4=0-2=-2$. The next example, however, shows us that the situation is not so simple.\\

\noindent
Example 3.3. Let
\begin{eqnarray*}
\mathbf{a}_3&=&(0,2,4,5,7)=(C4, D4, E4, F4, G4),\\
\mathbf{b}_3&=&(0,4,7,12)=(C4, E4, G4, C5).
\end{eqnarray*}
The discrete Fr\'{e}chet distances between $\mathbf{a}_3$ and $\mathbf{b}_3+t$ with $t=-5, -4, \cdots, 0, 1$ are tabulated as follows:\\

\newpage
\begin{table}[ht]
\begin{center}
  \begin{tabular}{cl}
   \hline
  $t$ & $d_F(\mathbf{a}_3, \mathbf{b}_3+t)$\\
   \hline \hline
 -5 & 5.831\\
 -4 & 4.472\\
 -3 & 3.162\\
 -2 & 3.000\\
 -1 & 4.123\\
 0 & 5.385\\
 1 & 6.708\\
    \hline
  \end{tabular}
  \end{center}
  \caption{discrete Fr\'{e}chet distances}
\end{table}

\noindent
It follows that $d_{F}^{tr}(\mathbf{a}_3,\mathbf{b}_3)=d_F(\mathbf{a}_3,\mathbf{b}_3-2)=3.000$. This time both melodies are in C major, but they require a transposition by -2. Indeed the arithmetic mean of the entries in the melody $\mathbf{a}_3$ is 3.600, that for $\mathbf{b}_3$ is 5.750, and their difference is equal to $-2.15\approx -2$. \\

\noindent
In Example 3.2, the arithmetic mean of $\mathbf{a}_2$ is 3.600, that of $\mathbf{b}_2$ is 5.600, and their difference is equal to -2. This together with Example 3.3 shows that the relevance of difference of the arithmetic means of two melodies when we compute the transposed Fr\'{e}chet distance.@These phenomena lead us to consider the DTFD's between a melody and its permutations. Note that in this case their arithmetic means are one and the same. \\

\noindent
Example 3.4. Let us fix $\mathbf{a}_4=(0,2,4)=(C2, D4, E4)$ and let $\mathbf{b}_4$ runs in the set of permutations of $\{0,2,4\}$. The following table displays the values of $t$ for which $d_F(\mathbf{a}_4,\mathbf{b}_4+t)$ attains the minimum:\\

\newpage
\begin{table}[ht]
 \begin{center}
  \begin{tabular}{llcc}
   \hline
  $\mathbf{a}_4$ & $\mathbf{b}_4$ & $t$ with minimum $d_F(\mathbf{a}_4, \mathbf{b}_4+t)$ & distance\\
   \hline \hline
 (0,2,4) & (0,2,4) & 0 & 0\\
 (0,2,4) & (0,4,2) & 0 & 2.828\\
 (0,2,4) & (2,0,4) & 0 & 2.828\\
 (0,2,4) & (2,4,0) & 1 & 4.243\\
 (0,2,4) & (4,0,2) & -1 & 4.243\\
 (0,2,4) & (4,2,0) & 0 & 4.000\\
    \hline
  \end{tabular}
  \end{center}
  \caption{transposed discrete Fr\'{e}chet distances}
\end{table}

\noindent
These examples teach us a lesson that the difference of the arithmetic means is a tentative value for us to find what value of $t$ gives us the minimum of TFD.

\subsection{Cluster analysis based on TDFD}
In this subsection we analyze the cluster structure of some instances of melodies by using TDFD.\\

As samples we choose several national anthems. The following table shows the names of countries, their national anthems in terms of numbers, and their slopes:

\begin{table}[ht]
 \begin{center}
  \begin{tabular}{lllc}
   \hline
   & name of country & national anthem & slope\\
   \hline \hline
 1 & Austria & (12,10,9,10,12,14,12,12,10,10) & 0.460\\
 2 & Bulgaria & (4,9,9,11,12,11,9,4,9,9,11,12,11,9) & 0.257\\
 3 & Canada & (7,10,10,3,5,7,9,10,12,5) & 0.110\\
 4 & China & (7,11,14,14,16,14,11,7,14,14,14,11,7) & 0.285\\
 5 & Germany & (7,9,11,9,12,11,9,6,7,16,14,12,11,9,11,7,14) & 0.131\\
 6 & Hungary & (2,3,5,10,5,3,2,7,5,3,2,0,2,3) & 0.359\\
 7 & Israel & (0,2,3,5,7,7,7,8,7,8,12,7,5,5,5,3,5,3,2,0,2,3,0) & 0.743\\
 8 & Japan & (2,0,2,4,7,4,2,4,7,9,7,9,14,11,9,7) & 0.729\\
 9 & Morocco & (10,12,10,7,8,10,3,5,7,7,8,0,7,8,5) & 0.165\\
 10 & New Zealand & (7,6,7,2,11,11,9,7,4,12,2,11,9,7,6,4,2) & -0.197\\
    \hline
  \end{tabular}
  \end{center}
  \caption{slopes of national anthems}
\end{table}

\noindent
For these melodies we apply clustering by using group average method. As a result, we find that the melody 1 (Austria) and the melody 6 (Hungary) is the closest pair. Furthermore the following table reveals a fascinating fact:

\newpage
\begin{table}[ht]
 \begin{center}
  \begin{tabular}{cl}
   \hline
  $t$ & $d_F("Austria", "Hungary"+t)$\\
   \hline \hline
 4 & 7.211\\
 5 & 5.831\\
 6 & 4.472\\
 7 & 3.606\\
 8 & 4.123\\
 9 & 5.385\\
 10 & 6.708\\
    \hline
  \end{tabular}
  \end{center}
  \caption{DFD between "Austria " and transposed "Hungary"}
\end{table}

\noindent
The arithmetic mean of "Austria" is equal to 11.100 and that of "Hungary" is 3.714, and hence the difference is $7.386\approx 7$, which coincides the value of $t$ giving the minimum of DFD under transposition. Actually, "Austria" is in F major, and "Hungary" is in B$\flat$ major. Hence our TDFD detects the difference of their arithmetic means as well as the difference F$4-$B$\flat3=5-(-2)=7$, which is required to transpose "Hungary" to "Austria". Moreover, though they are in different time, one is in three-four time, the other in four-four, both melodies can be played at the same time quite harmoniously. \\

Next we consider how cluster structure changes if we add some other melodies to the above 10 national anthems. Let us choose "Twinkle Twinkle Little Star" as the 11-th melody:
\begin{eqnarray*}
11: {\rm Twinkle}=(0, 0, 7, 7, 9, 9, 7, 5, 5, 4, 4, 2, 2, 0): {\rm slope} = 0.690
\end{eqnarray*}

Here appears a new nearest pair (7: Israel, 11:Twinkle) with $d_F^{tr}(7,11)=3.606$, which is equal to TDFD between 1 and 6. Amazingly enough, the melodies 7 and 11 can be sung harmoniously under the condition that Twinkle is transposed to C minor. \\

Futhermore we add to the samples a Japanese song called "Kojo no Tsuki (Moon over the Ruined Castle)" as the 12-th melody:
\begin{eqnarray*}
12: {\rm Kojo}=(6, 6, 11, 13, 14, 13, 11, 7, 7, 6, 5, 6): {\rm slope} = 0.762
\end{eqnarray*}

Here appears a cluster (7: Israel, 11:Twinkle, 12:Kojo) where $d_F^{tr}(7,12)=d_F^{tr}(11,12)=2.828$. We are surprised again to find that these three melodies can be sung harmoniously if Twinkle and Kojo are transposed to C minor. \\

\subsection{Motivating example}
This subsection explains how the author came across the cluster (7: Israel, 11:Twinkle, 12:Kojo). In the fall term in 2013 he gave lessons in the discrete Fr\'{e}chet distance at his university, and in a class he sent out to the students questionnaire about their most favorite musics. However almost all of the 25 answers which they supplied were Japanese song, the above three melodies happened to be contained in them. By clustering of 25 melodies, he came across to a cluster of the three melodies as well as another cluster of "The Moldau" and "Ievan Polkka". This pair can be sung simultaneously too!.@These surprises in the result of questionaire motivated the author to study in this article the usefulness of the transposed discrete Fr\'echet distance.\\
\newpage
\noindent
References\\
$[1]$ T. Eiter, H. Mannila. Computing discrete Fr\'{e}chet distance. Technical Report CD-TR 94/64, Information Systems Department, Technical University of Vienna, 1994.\\
$[2]$ G. G\"{u}nd\"{u}z, U. G\"{u}nd\"{u}z, The mathematicas analysis of the structure of some songs, Physica A, $\mathbf{357}$(2005), 565-592.\\
$[3]$ A. Mosig, M. Clausen, Approximately matching polygonal curves with respect to the Fr\'{e}chet distance, Comput. Geom. $\mathbf{30}$(2005) 113-127.

 \end{document}


TITLE: Why does $\frac{dy}{dx} \propto y$ imply $x_1 - x_2$ is constant for $\frac{y_2}{y_1}$ constant where $(x_1, y_1)$ and $(x_2, y_2)$ can vary?
QUESTION [0 upvotes]: The time taken for the activity of a radioactive sample to halve is called the half-life. This is a constant.
More generally, given the curve $y=Ae^{-bx}$, given $y_1$ and $y_2 = ky_1$, then $\frac{y_2}{y_1}$ is always the same number for all choices of $y_1$.
I can justify this by writing $y_1 = Ae^{-bx_1}$ and $y_2 = Ae^{-bx_2}$ and then using $y_2 = ky_1$ to get $x_1 - x_2 = \frac{1}{b} \ln k$, which is a constant.
But is there anyway to justify this starting from the fact that we have a curve that satisfies $\frac{dy}{dx} \propto y$?

REPLY [2 votes]: $\frac{dy}{dx} \propto y \Rightarrow \frac{dy}{dx} = ky \ $   ($k$ is a constant)
Now you're provided with 2 arbitrary points $(x_1,y_1)$ and $(x_2,y_2)$.
So,
$\begin{align}&\int_{y_1}^{y_2}\frac{dy}{y} = k\int_{x_1}^{x_2} dx \\\Rightarrow \ & \ln\frac{y_2}{y_1} = k(x_2- x_1) \text{ or }  \boxed{x_1 - x_2 = \frac1k\ln\frac{y_1}{y_2}}\end{align}$
Now, $k$ and  $\frac{y_1}{y_2}$ are constats. So, $\boxed{x_1- x_2}$ is also constant


text:
\subsection{Expected vs Conditional FIM}\label{sec:block-diagonal}
While we have investigated the conditional FIM \eqref{align:cfim} so far, it will be curious to show how the obtained eigenvalue statistics could be related to those of the FIM \eqref{align:fim}.
We investigate the analysis of mean eigenvalues of both the conditional FIM and the usual FIM.
Analysis of the mean is easier than analysis of the maximum value, but is done to observe the effect of the dynamic isometry.
Now, we denote by $m_1(\mu)$ the mean of a distribution $\mu$ given by $m_1(\mu) = \int x \mu(dx)$.
We show that the mean of spectrum is $O(L)$ as $L \to \infty$.

Applying the decomposition formula of the free multiplicative convolution $m_1(\mu \boxtimes \nu)=m_1(\mu)m_1(\nu)$ to \cref{align:reccurence_spec}, we have the following recurrence formula of the mean:
\begin{align}
    m_1(\mu_{\ell + 1}) = q_\ell + \sigma_{\ell+1}^2 m_1(\nu_\ell) m_1(\mu_\ell).
\end{align}
Then we have the followings.
\begin{prop}\label{prop:expectation}
Under  \cref{assumption:simplify} and \ref{assumption:eps}, it holds that
\begin{align}
\lim_{L \to \infty}L^{-1} m_1(\mu_L)  =  q \frac{1-  \exp(-\eps_1 - \eps_2)}{\eps_1 + \eps_2},
\end{align}
where $q = \lim_{L\to\infty}q_L$. In particular, the limit has the expansion $ q (1 -  (\eps_1 + \eps_2)/2) + O( (\eps_1 + \eps_2)^2 )$ as  $\eps_1, \eps_2 \to 0$.
\end{prop}
\begin{proof}
We have $m_1(\mu_{L+1}) =  \sum_{\ell=0}^{L} q_\ell (\sigma_{\ell+1}^2 \alpha_\ell \gamma_\ell )^\ell =  q_L \sum_{\ell=0}^{L} (\sigma_{L+1}^2 \alpha_{L} \gamma_{L})^\ell $ by \cref{assumption:simplify}.
Set $x_L = L(1 - \sigma_{L+1}^2 \alpha_L \gamma_L)$. We have $\lim_{L \to \infty}x_L = \eps_1 + \eps_2$.
Then  $L^{-1}\sum_{\ell=0}^{L} (\sigma_{L+1}^2 \alpha_L \gamma_L)^\ell =   x_L^{-1}[ 1- (1 - x_L/L)^L] \to (\eps_1 + \eps_2)^{-1}( 1 - \exp(-\eps_1 - \eps_2))$. Then the assertion has been proven.
\end{proof}

Next, consider the usual FIM.
Fix $N \in \N$ and consider input vectors $x(1), \dots, x(N) \in \R^M$.
Set $\post^0(n)=x(n)$.
Since $\mc{I}(\theta) =  N^{-1}\sum_{n=1}^N \mc{I}(\theta | x(n))$, the FIM $\mc{I}(\theta)$ shares non-zero eigenvalues with the dual $\Theta$, which is the $N \times N$ matrix whose $(m,n)$-entry is given by the following $M \times M$ matrix:
\begin{align}
    \Theta(m,n) &= \frac{1}{N} \pp{ f_\theta(x(m))}{\theta} \pp{f_\theta(x(n))}{\theta}^\top,
\end{align}
where $m,n=1, \dots, N$.
For $\ell=1, \dots, L$, set recursively $\pre^\ell(n) = W_\ell \post^{\ell-1}(n)$, $\post^\ell(n) = \act^\ell(\pre^\ell(n) )$, and define $\delta_{L \to \ell}(n)$ in the same way.
Then $\Theta(m,n) =  MN^{-1} \sum_{\ell=1}^L \Sigma_\ell(m,n) \delta_{L \to \ell}(m) \delta_{L \to \ell}(n)^\top$, where $\Sigma_\ell(m,n) =  M^{-1}\sum_{i=1}^M x_{\ell,i}(m)x_{\ell,i}(n)$, and we have the following block-matrix representation:

\begin{align}
    \Theta= \frac{M}{N} \begin{bmatrix} H_L(x(1)) & * & \dots  & * \\
    * & H_L(x(2)) &  \cdots  &  * \\
    \vdots & \cdots & \ddots & \vdots \\
    * & * & \cdots  &  H_L(x(N))
    \end{bmatrix}
\end{align}

Hence for the $N$-sample, considering the collection of eigenvalues of the dual conditional FIMs $(H_L(x(n)))_{n=1}^N$ is equivalent to considering block-diagonal approximation of the (scaled)  dual FIM $ MN^{-1} \Theta$.
Even if it is not clear yet that the block-diagonal approximation behaves well,   the mean of eigenvalues of full matrix is exactly determined by the diagonal part as the following assertion.
\begin{cor} \label{cor:mean-full}
Denote by $m_{L,N}$ the wide limit  $M \to \infty$ of  the mean of eigenvalues of $\Theta/M$.
Then under the limit $L, N \to \infty$ with $L/N \to \alpha  < \infty$,   it holds that
\begin{align}
 m_{L,N} \to \alpha q \frac{1-  \exp(-\eps_1 - \eps_2)}{\eps_1 + \eps_2}.
\end{align}
\end{cor}
\begin{proof}
Fix $L, N$. The mean of eigenvalues of $\Theta/M$ is equal to $\mathrm{tr}(\Theta/M)$ and
$\mathrm{tr}(\Theta/M) =  \sum_{n=1}^N \mathrm{tr}(H_L(x(n)))/N^2 \to m_1(\mu_L)/N$. By \cref{prop:expectation}, the assertion follows.
\end{proof}

\cref{cor:mean-full} implies that the mean eigenvalue of $\Theta/M$ is close to $qLN^{-1}$ when $L$ and $N$  are of the same magnitude.
In the next section, we empirically examine the block-diagonal approximation.

config: arxiv


TITLE: Find the local maximum, minimum and saddle points of $f(x,y) = x + y + x^2y + xy^2$
QUESTION [0 upvotes]: Find the local maximum, minimum and saddle points of $f(x,y) = x + y + x^2y + xy^2$

$f_{xy} $ is not equal to $f_{yx} $, therefore nothing can be said about the critical points of this function.
Is this correct?

REPLY [0 votes]: We have:
$$\frac{\partial f}{\partial x}=1+2xy+y^2 \qquad \frac{\partial f}{\partial y}=1+2xy+x^2
$$
so
$$
\frac{\partial^2 f}{\partial x\,\partial y }=2x +2y \qquad \frac{\partial^2 f}{\partial y\,\partial x}=2x +2y
$$
so the mixed second derivative are equal and the problem does not exists.


TITLE: Ideal gas system with diathermic piston externally manipulated
QUESTION [0 upvotes]: I wanted to ask about the following problem:
An ideal monatomic gas is separated into two volumes $V_{1}$ and $V_{2}$ through a diathermic piston, such that each volume containing $N$ atoms and the two sides are at the same temperature $T_{0}$. The entire system is isolated from the outside by means of insulating walls.
The plunger is reversibly externally manipulated until the two gases are in thermodynamic equilibrium with each other.
After the problem has different questions, however, I have not been able to answer the following:
How is called the type of process? Ie is isothermal, adiabatic, etc. Show that $\Delta S_{1}$ = $-\Delta S_{2}$, where $\Delta S_{1}$ and $\Delta S_{2}$ are the changes in entropy of the two gases.

REPLY [0 votes]: There can be heat interactions between the two volumes themselves if you treat them as two seperate systems. So even though the entire system is isolated heat interactions are possible between the two volumes.


text:
\section{AMP algorithmic phase transition}\label{sec:matrixWalgo}

Approximate message passing (AMP) is a low complexity algorithm that  iteratively updates estimates of the unknown signal, which, in the case of the spiked Wigner model is $\bX$, from the noisy data $\bW$. The iterative estimates are denoted $\{\bx^t\}_{t \geq 1}$.  Let $\bA \equiv \bW/\sqrt{n}$ and initialize  with $f_0(\bx^{0})$ independent of $\bW$, such that $\langle f_0(\bx^{0}), \bX \rangle > 0$.  Then let $\bx^{1} = \bA  f_0(\bx^{0})$, and for $t \geq 1$, compute

\begin{equation}
\bx^{t+1} = \bA  f_t(\bx^{t}) - \mathsf{b}_t  f_{t-1}(\bx^{t-1}), \qquad \mathsf{b}_t  = \frac{1}{n} \sum_{i=1}^n f'_t(x^{t}_i),
\label{eq:AMP}
\end{equation}

where the scalar function $f_t: \mathbb{R} \rightarrow \mathbb{R}$ is applied elementwise to vector input, i.e., $f_t(\bx) = (f_t(x_1), \ldots, f_t(x_n))$ for a vector $\bx \in \mathbb{R}^n$, and its exact value is given in what follows (in \eqref{eq:denoiser}). We refer to the functions $\{f_t\}_{t\geq 0}$ as ``denoisers'', for reasons that will become clear momentarily. Notice that \eqref{eq:AMP} gives both matrix estimates $\hat{\bX} \hat{\bX}^\intercal = f_t(\bx^t) [f_t(\bx^t)]^\intercal$ and signal estimates $\hat{\bX} = f_t(\bx^t)$.

A key property of AMP is that, asymptotically as $n \rightarrow \infty$, a deterministic, scalar recursion referred to as \emph{state evolution} exactly characterizes its performance, in the sense that the estimates $x^t_i$ converge to random variables with mean and variance governed by the state evolution.  For the sub-linear sparsity regime, we introduce an $n$-dependent state evolution, reflecting that our sparsity level $\rho_n$ and signal strength $\lambda_n$ both now change as $n$ grows. We will show, based on measure concentration arguments, that the usual asymptotic characterization also gives a finite sample approximation, meaning that for any $n$ fixed but large, $x^t_i$ is \emph{approximately} distributed as a $x^t_i \overset{d}{\approx} \mu_t^n X_0^n + \sqrt{\tau^n_t} Z$ where $\mu_t^n$ and $\tau^n_t$ are characterized by the state evolution below with $X_0^n \sim P_{X, n}$ independent of standard gaussian $Z$.
The $n$-dependent state evolution is defined as follows: for $t \geq 1$,

\begin{align}
\mu^n_1 =  \sqrt{\lambda_n} \langle f_0(\bx^0), \bX \rangle/n, \qquad & \qquad \tau^n_1 = \| f_0(\bx^0) \|^2/n,
\label{eq:state_evolution_start} \\

\mu^n_{t+1}  = \sqrt{\lambda_n}\, \mathbb{E}\left\{X_0^n f_t\big(\mu^n_{t} X_0^n + \sqrt{\tau^n_t} Z\big)\right\}, \qquad & \qquad\tau^n_{t+1}  =  \mathbb{E}\Big\{\big[f_t\big(\mu^n_{t} X_0^n + \sqrt{\tau^n_t} Z\big)\big]^2\Big\},
\label{eq:state_evolution}
\end{align}

where we include the $n$ superscript to emphasize the dependence.

A well-motivated choice of denoiser functions $\{f_t\}_{t\geq 0}$ are the conditional expectation denoisers. Namely,  given that we have knowledge of the prior distribution of the signal elements, and considering the approximate characterization of the estimate $x^t_i$ via the state evolution, the Bayes-optimal way to update our signal estimate at any iteration is the following:

for $t \geq 1$,

\begin{equation}
 f_t(x) = \mathbb{E}\big \{X_0^n  \mid  \mu_t^n X_0^n + \sqrt{\tau^n_t} Z = x\big\},
\label{eq:denoiser}
\end{equation}

 with $X_0^n \sim P_{X, n}$ independent of standard gaussian $Z$. Strictly speaking, $ f_t(\cdot)$ also has an $n$-dependency, so to be consistent we should label $ f_t(\cdot) \equiv  f^n_t(\cdot)$, however we drop this for simplicity.  With this choice of denoiser function, the state evolution \eqref{eq:state_evolution} simplifies: by the Law of Total Expectation, $ \mathbb{E}\{X_0^n f_t(\mu^n_{t} X_0^n + \sqrt{\tau^n_t} Z)\} = \mathbb{E}\{[f_t(\mu^n_{t} X_0^n + \sqrt{\tau^n_t} Z)]^2\},$

 thus $ \mu_t^n = \sqrt{\lambda_n} \tau^n_{t}$, and so

\begin{equation}
\label{eq:state_evolution2}
\tau^n_{t+1} = \mathbb{E}\Big\{\big[ \mathbb{E}\big \{X_0^n \mid  \sqrt{\lambda_n} \tau^n_{t} X_0^n + \sqrt{\tau^n_t} Z\big\}\big]^2\Big\}.
\end{equation}

\begin{figure}[t!]
\centering
\includegraphics[trim={0 0 0 1.2cm},clip,width=0.45\linewidth]{./figures/allornothing_AMP_trans}
\includegraphics[trim={0 0 0 1.2cm},clip,width=0.45\linewidth]{./figures/allornothing_MMSE_vs_AMP}
 \caption{\footnotesize Left: The mean-square error towards which the suitably normalized matrix-MSE of the AMP algorithm, ${\rm MSE}_{\rm AMP}$, converges
for various sparsity levels, see theorem~\ref{AMP-theorem}. An all-or-nothing transition appears as $\rho=\rho_n\to0$ at $\lambda_{\rm AMP}(\rho)=1/(e \rho)^2$. Comparing to figure~\ref{fig:MMSEandMI} the transition becomes sharper much faster as $\rho$ decreases. Right: Horizontal axis is on a log scale. The statistical-to-algorithmic gap diverges as $\rho\to 0$.}
\label{fig:MMSEandMSEamp}
\end{figure}

The performance guarantees given by the state evolution are stated informally in what follows, with a more formal result given in appendix K. The proof
extends and refines\footnote{The result in  \cite{RushVenkataramanan} is a general AMP algorithm with a  ``rectangular'' structure that does not cover the ``symmetric'' AMP in \eqref{eq:AMP}. However, extensions of this result to the symmetric case are straightforward, as discussed in \cite[Section 1]{RushVenkataramanan}, but technical. Moreover, the dependence on $n$ for the state evolution requires that these values are tracked carefully through the proof, whereas this was not done in \cite{RushVenkataramanan}, as these values were assumed to be universal constants.  For simplicity of exposition in this document, we do not elaborate further on these technicalities at this point and put these details in appendix K.} the finite sample analysis of AMP given in \cite[Theorem 1]{RushVenkataramanan}. These guarantees concern the convergence of the empirical distribution of $x^t_i$ to its approximating distribution determined by the state evolution and specifically apply to the AMP algorithm using the denoiser in \eqref{eq:denoiser}.  For all order $2$ pseudo-Lipschitz functions\footnote{For any $n,m \in \mathbb{N}_{>0}$, a function $\phi : \mathbb{R}^n\to \mathbb{R}^m$ is \emph{pseudo-Lipschitz of order $2$} if there exists a constant $L>0$ such that $\left|\left|\phi(\bx)-\phi(\by)\right|\right|\leq L\left(1+ \|\bx\|+ \|\by\|\right) \|\bx-\by\|$ for $\bx, \by \in \mathbb{R}^n$.}, denoted $\psi: \mathbb{R}^2 \rightarrow \mathbb{R}$ with Lipschitz constant $L_{\psi}> 0$, we have that for $\epsilon \in (0,1)$ and $t \geq 1$,

 \begin{equation}
 \begin{split}
&\mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \psi(X_i, f_{t}(x^{t}_i))\! -\!  \mathbb{E}\Big\{\psi\big(X_0^n,  f_{t}(\mu^n_{t} X_0^n + \sqrt{\tau^n_t} Z)\big) \Big\} \Big| \geq \epsilon \Big)   \leq C C_{t} \exp\Big\{\frac{-c c_{t} n \epsilon^2}{L_{\psi}^2  \gamma_n^{t}}\Big\}
 \label{eq:finite_sample}
 \end{split}
 \end{equation}

 where $\bX = (X_1, \ldots, X_n)$ is the true signal and $C, C_t, c, c_t$ are universal constants not depending on $n$ or $\epsilon$, but with $C_t, c_t$ depending on the iteration $t$ and whose exact value is given in theorem~\ref{AMP-theorem}. Finally, $\gamma_n^{t}$ characterizes the way the bound depends on the state evolution parameters and its exact value is given in \eqref{eq:gamma_def}.

We want to consider, specifically, the vector-MSE and matrix-MSE of AMP, namely $\frac{1}{n}\|\bX -  f_t(\bx^t)\|^2$ and $\frac{1}{n^2}\|\bX \bX^\intercal -   f_t(\bx^t)[ f_t(\bx^t)]^\intercal\|_F^2$,  for any $t \geq 1$.

 \begin{thm}[Finite sample state evolution]\label{AMP-theorem}
Consider  AMP in \eqref{eq:AMP} using the conditional expectation denoiser in \eqref{eq:denoiser}. Then for $\epsilon \in (0,1)$ and $t \geq 1,$ let $\textsf{bound}_t \equiv C C_{t} \exp\{ {-c c_{t} n \epsilon^2}/{  \gamma_n^{t}}\},$ then

 \begin{align}
&\mathbb{P} \Big(\Big| \frac{1}{n}\|\bX -  f_{t}(\bx^{t})\|^2-  (\rho_n -  \tau^n_{t+1})\Big| \geq \epsilon \Big) \leq \textsf{bound}_t ,  \label{eq:finite_sample_vector1}\\
&\mathbb{P} \Big(\Big| \frac{1}{n^2}\|\bX \bX^\intercal -  f_{t}(\bx^{t}) [ f_{t}(\bx^{t})]^\intercal\|_F^2 -  ( \rho_n^2 -  (  \tau^n_{t+1})^2)\Big| \geq \epsilon \Big) \leq \textsf{bound}_t ,  \label{eq:finite_sample_matrix1}
 \end{align}

 where $X_0^n \sim P_{X, n}$ and $\tau_t^n$ is defined in \eqref{eq:state_evolution2}.  The values $C, c$ are universal constants not depending on $n$ or $\epsilon$ with $C_t, c_t$ given by
$C_t =C_1^{t} (t!)^{C_2},  c_t = [c_1^{t} (t!)^{c_2}]^{-1}$. Finally,

\begin{equation}
\begin{split}
\gamma_n^{t} &\equiv \lambda_n^{2t-1}  (\nu^n +  \tau^n_{1})  (\nu^n +  \tau^n_{1} +  \tau^n_{2})  \cdots  (\nu^n + \sum_{i=1}^{t} \tau^n_{i}) \\

&\hspace{4cm} \times \max\{1, \hat{\textsf{b}}_1\}  \max\{1, \hat{\textsf{b}}_2\} \cdots  \max\{1, \hat{\textsf{b}}_{t-1}\},
\label{eq:gamma_def}
\end{split}
\end{equation}

where $\nu^n$ is the variance factor of sub-Gaussian $\bX^n$ which equals $12 \rho_n$ for $P_{X, n}={\rm Ber}(\rho_n)$ (see lemma~\ref{lem:subgauss}) and $\hat{\textsf{b}}_t = \mathbb{E}\{f'_t(\mu^n_t X^n_0 + \sqrt{\tau_t^n} Z)\}$.
 \end{thm}

Theorem~\ref{AMP-theorem} follows from the finite sample guarantees given in \eqref{eq:finite_sample}, and, in appendix K, we discuss in more detail the proof of theorem~\ref{AMP-theorem} and result~\ref{eq:finite_sample}. We make a few remarks on the result here.

\textbf{Remark 1: $\rho_n$ normalization and all-or-nothing transition.}
To be consistent with the previously stated results, we could renormalize the MSEs as follows and the result still holds as

\begin{align*}
&\mathbb{P} \Big(\Big| \frac{1}{\rho_n n}\|\bX -  f_{t}(\bx^{t})\|^2-  \Big(1 - \frac{\tau^n_{t+1}}{ \rho_n} \Big)\Big| \geq \epsilon \Big) \leq C C_{t} \exp\{ {-c c_{t} n \rho_n^2 \epsilon^2}/{  \gamma_n^{t}}\}, \\
&\mathbb{P} \Big(\Big| \frac{1}{(\rho_n n)^2}\|\bX \bX^\intercal -  f_{t}(\bx^{t}) [ f_{t}(\bx^{t})]^\intercal\|_F^2 -  \Big(1 -  \Big(\frac{\tau^n_{t+1}}{ \rho_n}\Big)^2\Big)\Big| \geq \epsilon \Big) \leq C C_{t} \exp\{ {-c c_{t} n \rho_n^4 \epsilon^2}/{  \gamma_n^{t}}\}.
 \end{align*}

 In appendix G we show that $\tau^n_{t+1}/\rho_n \to 0$ for $\lambda_n\rho_n^{2} \to 0$ and $\tau^n_{t+1}/\rho_n \to 1$ for $\lambda_n\rho_n^{2} \to +\infty$. This is consistent with the numerics on figure~\ref{fig:MMSEandMSEamp} where we see a transition for
$\lambda_n \rho_n^{2} = 1/e^2$.

\textbf{Remark 2: AMP regime and statistical-to-algorithmic gap.}
We apply theorem~\ref{AMP-theorem} in the regime where  $t = o( \frac{\ln n}{\ln\ln n})$, which, as discussed in \cite{RushVenkataramanan}, is the regime where the state evolution predictions are meaningful with respect to the values of $C_t, c_t$ and the constraints they specify on how large $t$ can be compared to the dimension $n$.  In our work, we also have constraints related to the $ \gamma_n^{t}$ value in \eqref{eq:gamma_def} that appears in the denominator of the rate of concentration. Considering these constraints, we apply theorem~\ref{AMP-theorem} for signal strength and sparsity scaling like $\lambda_n \rho_n^2= w$
and $\rho_n = \Omega((\ln n)^{-\alpha})$ with $w, \alpha\in \mathbb{R}_{+}$, and  show that the above probabilities indeed tend to zero as $n\to +\infty$. Appendix L provides the details of this calculation.

{Note that since theorem~\ref{thm:ws} and corollary~\ref{Cor1:MMSEwigner} hold for $\rho_n=\Omega(n^{-\beta})$ and thus for $\rho_n = \Omega((\ln n)^{-\alpha})$ as well, then both the statistical and algorithmic transitions (and therefore the statistical-to-computational gap) are proven for $\rho_n=\Omega((\ln n)^{-\alpha})$.}

\textbf{Remark 3: $\lambda_n, \tau^n$ dependence.}
The $\lambda_n$ dependence in $\gamma_n^t$ defined in \eqref{eq:gamma_def} comes from the (pseudo-) Lipschitz constants $L_f$ in~\eqref{eq:finite_sample}. The dependence on the Lipschitz constants, and on the state evolution parameters $\tau^n_t$, was not stated explicitly in the original concentration bound in \cite[Theorem~1]{RushVenkataramanan} as the authors assume these values do not change with $n$ and, thus, can be absorbed into the universal constants.
By examining the proof of \cite[Theorem 1]{RushVenkataramanan}, one gets that the dependence takes the form in \eqref{eq:gamma_def}. More details on how we arrive at the rates in theorem~\ref{AMP-theorem} can be found in appendix~K.

\textbf{Remark 4: Algorithm initialization.} We assume that the AMP algorithm in \eqref{eq:AMP} was initialized  with $f_0(\bx^{0})$ independent of $\bW$ such that $\langle f_0(\bx^{0}), \bX \rangle > 0$.  The second condition ensures that $\mu^n_0 \neq 0$ (which would mean $\mu^n_t = 0$ for all $t \geq 0$). If $P_{X, n}$ is ${\rm Ber}(\rho_n)$, one could use, for example, $f_0(\bx^{0}) = \mathbf{1}$, since the mean of the signal elements is positive. However, if $P_{X, n}$ is Bernoulli-Rademacher, a more complicated initialization procedure is needed since initializing in this way would cause the algorithm to get stuck in an unstable fixed point.

We refer the reader to \cite{montanari2017estimation} for a discussion of an appropriate spectral initialization for this setting. However, such an initialization violates the assumption of independence with $\bW$. The theoretical idea in \cite{montanari2017estimation} that allows one to get around this dependence is to analyze AMP  in \eqref{eq:AMP} with a matrix $\widetilde{\bA}$ that is an \emph{approximate} representation of the conditional distribution of $\bA$ given the initialization, and then to show that with high probability the two algorithms will be close each other.  We believe that  incorporating these ideas with the finite sample guarantee in \eqref{eq:finite_sample} would be straightforward, and theorem~\ref{AMP-theorem} could be extended to the setting of AMP with a spectral initialization.


TITLE: Solve $x^{2}\equiv 24 \mod 125$
QUESTION [3 upvotes]: Here's a congruence I'm trying to solve:
$$x^2\equiv24 \mod 125$$
What are the techniques I could use to solve it? I know about Euler's phi function, Fermat's little theorem and Chinese remainder theorem but they all seem inapplicable here. Is there something else I could use?

REPLY [3 votes]: Hint $\,\ {\rm mod}\ 125\!:\,\ \overbrace{1000}^{\large 8\,\cdot\, 125}\equiv 0\,\overset{\large + 24\ }\Longrightarrow\, 24\equiv 1024\equiv 2^{10} = (2^5)^2$
Remark $\ $ Generally one can use Hensel's Lemma, as in lhf's answer, but that is a bit overkill in cases like this where the number is obviously congruent to a well-known power (which happens frequently for small moduli due to the law of small numbers).


TITLE: How to simplify nested summations when the summations are multiplied? (Super Auto Pets)
QUESTION [1 upvotes]: I am having trouble simplifying a summation I created. Let $S$ and $b_1$ be positive integers and the only given values. If you want to work out an example, have $S=5$ and $b_1 \geq 6$. Let $l(b_i, b_{i+1})$ be a function that outputs a positive integer.
$$\sum_{b_2=S}^{b_1-1} \left[l(b_1, b_2) \times \sum_{b_3=S-1}^{b_2-1} \left(l(b_2, b_3) \times \sum_{b_4=S-2}^{b_3-1} \left(l(b_3, b_4) \times \sum_{b_5=S-3}^{b_4-1} l(b_4, b_5) \right) \right)\right]$$
The problem is that the values in the index of one summation is necessary for the index of the next summation. It's similar to $\sum_{i=1}^{5}cx$, but $c$ is a summation instead of a given constant. Not only that, but I'm not completely sure it could be simplified, shown in
the apparent inability to simplify $\sum f(x)g(x)$ (Sigma Notation, Multiplication). I looked at a few resources, like Rules of Double Sums and another question that listed many properties that I am having trouble finding again, but they offered little guidance.
I wrote out an example for $b_1=7$ to find another interpretation, yet this did not help at all. I thought about
$$\prod_{i=1}^{S-1}\left[\sum_{b_{i+1}=S+1-i}^{b_i-1}l(b_i,b_{i+1})\right]$$
but that simplifies to
$$\sum_{b_2=S}^{b_1-1} l(b_1,b_2) \times \sum_{b_3=S-1}^{b_2-1}l(b_2,b_3) \times\sum_{b_4=S-2}^{b_3-1}l(b_3,b_4)\times \sum_{b_5=S-3}^{b_4-1}l(b_4,b_5)$$
which is close, but not quite. Each summation must finish before going to the next summation, which I do not want. For $i=2$, the upper bound would be $b_2-1=b_1-2$, as the upper bound for $\sum_{b_2=S}^{b_1-1}$ is $b_2=b_1-1$. The summation runs only once when it needs to run multiple times. What can put me on the right track?
P.S.: I am excluding some information regarding the sums for conciseness. I do not think they subtract much from the fundamental issue.
EDIT (1):
It turns out that this more complicated than I thought. I will consider changing my notation to what Matt Groff has, but not now. Some context about the problem. There is a video game called "Super Auto Pets" that's available on Steam for free. I thought it would be a fun and easy problem to count the number of ways your roster of pets can defeat an enemy's roster. My equation  stated at the top is only part of one term (five in total) that counts the rosters we can win against when you have one pet, not considering pet abilities. You can have a maximum of five pets, so this is the beginning.
I began my adventure on January 2, 2022, at 12:50 pm (I date and time everything). From January 10 onward, I've been working exclusively on this. Yes, it took me a month to find the top equation. Now, more information.
The "function" $l(b_i, b_{i+1})$ is actually the sequence (source: Notation for sequences)
$$l(b_i, b_{i+1}) = \left< \frac{b_i-b_{i+1}}{c_i} \in \mathbb{Z}:  b_{i+1} \in [S+1-i, b_i-1], c_i \in [1, 50]\right>.$$
When creating a sequence, you choose only one $b_{i+1}$ and then concatenate all the integers $c_i$. For example, if $b_1=7$, the sequence becomes
$$l(7, b_{2}) = \left< \frac{7-b_{2}}{c_i} \in \mathbb{Z}:  b_{2} \in [5, 6], c_i \in [1, 50]\right>.$$
It generates the following sequences:
$$l(7, 5) = \left< \frac{2}{c_1} \in \mathbb{Z}:  b_{2}=5, c_1 \in [1, 50]\right>$$
$$l(7, 6) = \left< \frac{1}{c_1} \in \mathbb{Z}:  b_{2}=6, c_1 \in [1, 50]\right>.$$
Writing out the sequences ($\phi$ is the empty set):
$$l(7, 5) = \left< \{2\}_{c_1=1}, \{1\}_{2}, \phi_{3}, \phi_{4}, \dotso, \phi_{50} \right>$$
$$l(7, 6) = \left< \{1\}_{c_1=1}, \phi_{2}, \phi_{3}, \phi_{4}, \dotso, \phi_{50} \right>.$$
Also, I'm not summing up the terms of the sequence. Rather, I'm summing the length (cardinality?) after the following operation:
$$|l(b_i, b_{i+1})-\left< \phi_{1}, \phi_{2}, \phi_{3}, \dotso, \phi_{50}\right>|.$$
When I'm subtracting, I mean the set difference, of a sort. Compare the $c_1$'th term of $l(b_1,b_2)$ and $\{\phi_{c_1}\}_{c_1=1}^{50}$. Then say "From the sequences $A$ and $B$, include the elements of $A$ that are not in $B$ at position $c_1$". So $\phi_{5}-\phi_{5}$ does not equal any mathematical object besides $\phi_{5}-\phi_{5}$, even $0$, $\phi$ and possibly $\phi_{6}-\phi_{6}$. It's like trying to simplify the number $0$. In fact, it destroys anything in that position, including the position itself. It's not mathematically accurate, but it's what I have. I'm trying to remove any instance of $\phi$. Continuing from my example,
$$|\left< \{2\}_{c_1=1}, \{1\}_{2}, \phi_{3}, \phi_{4}, \dotso, \phi_{50} \right>-\{\phi_{c_1}\}_{c_1=1}^{50}| = |\left< \{2\}_{c_1=1}, \{1\}_{2} \right>| = 2$$
$$|\left< \{1\}_{c_1=1}, \phi_{2}, \phi_{3}, \phi_{4}, \dotso, \phi_{50} \right>-\{\phi_{c_1}\}_{c_1=1}^{50}| = |\left< \{1\}_{1} \right>| = 1.$$
Observe that the result is always an integer. This is what I meant when I said, "Let $l(b_i, b_{i+1})$ be a function that outputs a positive integer." Hopefully this answers Matt Groff's question about the type of "function". I'm also worried about how I should finish my project, as I start college on Monday, January 31. I probably need six months, at least.
P.S.: Should I add the combinatorics tag?

REPLY [0 votes]: I thought that the following example may help, although there are some issues with it.  For instance, you need to be able to find the difference delta, or antidifference of the function with respect to each variable.
To see why we're interested in the antidifference, let's start with the function $f(x)$, and find the antidifference:
$$\Delta_x f(x) = f(x+1) - f(x) \tag{1}$$
Now sum over the antidifference:
$$\sum_{x=a}^b{(f(x+1) - f(x))}=$$
$$(-f(a) + \color{red}{f(a+1)}) + (\color{red}{-f(a+1)} + \color{blue}{f(a+2)}) + (\color{blue}{-f(a+2)}+f(a+3)) + \dots = $$
$$-f(a) + \color{red}{(f(a+1)-f(a+1))} + \color{blue}{(f(a+2)-f(a+2))} + \dots + f(b+1)=$$
$$-f(a) + f(b+1) \tag{2}$$

Two Variables
Let's now take a function of two variables, $f(x,y)$.
We'll nest the functions related to it in two functions.  Let's start by taking the antidifference of $f(x,y)$ with respect to $x$.  We write this as
$$\Delta_x f(x,y) = f(x+1,y) - f(x,y) \tag{3}$$
Next, we'll take the antidifference of $\Delta_x f(x,y)$ with respect to $y$
$$\Delta_y(\Delta_x f(x,y)) = \underbrace{(f(x+1,y+1) - f(x,y+1))}_{\Delta_x f(x,y+1)} - \underbrace{(f(x+1,y) - f(x,y))}_{\Delta_x f(x,y)} \tag{4}$$
So if we take this whole function, and sum over $x$ and $y$, we get:
$$\sum_x{ \sum_y { \Delta_y(\Delta_x f(x,y)) }} = f(x,y) \tag{5}$$


TITLE: Functional derivatives: Fréchet, Gateaux derivatives and Euler-Lagrange operators
QUESTION [2 upvotes]: What is the relationship between Fréchet derivatives, Gateaux derivatives and the usual Euler-Lagrange operator (ELO)? Is the ELO the Fréchet derivative, the Gateaux derivative or does it depends on the context and the theory/lagrangian we consider?
Remark: Just as the usual derivative is the rate of change of the function with respect to certain variable, I am waiting for a physical interpretation of the above 3 derivatives and their meaning. For instance, in several variables, the partial derivative is the rate of change of the variable that is being calculated or derived... By the way, some people refers to functional derivatives as Fréchet derivatives and, as some responses said, identify the EL operator as the Gateaux derivative. Is there any subtle point to say that the functional derivate is a Fréchet derivative instead a Gateaux derivative? Are both equivalent to the EL equation? If not in what circumstances are they equivalent and why?

REPLY [2 votes]: In the derivation of the Euler-Lagrange equations for a functional, one uses the Gateaux derivative/differential of a functional (this functional could be the „Lagrangian action” in point-particle mechanics/field theory).
Here it is denoted by „d”, but let us denote it by $d_G$.
Let $\{h_a (\tau)\}_{a=1,...,N}$ be N arbitrary real functions such as $h_a (\tau_1) = 0 = h_a (\tau_2)$. Let $u$ be a real number (called parameter).
Then we take the functional (deriving from the standard 1st order functional of Lagrange):
$$I[x_a + u h_a] :=\int_{\tau_1}^{\tau_2} d\tau ~ L\left(x_a (\tau) + u h_{a}(\tau), \dot{x}_a (\tau) + u \dot{h}_a(\tau), t\right)  $$
To this we define its Gateau derivative:
$$d_G I[x_a] := \left(\frac{d}{du} I[x_a + u h_a]\right)|_{u=0} $$
One then defines the functional derivative of $I$ as:
$$\begin{equation} d_G I[x_a] =: \int_{\tau_1}^{\tau_2} d\tau ~ h_a (\tau) \frac{\delta I}{\delta x_a (\tau)} \end{equation}$$
If we compute the Gateau derivative and equal it to $0$, we obtain the Euler-Lagrange equations for functionals/actions of 1st order in the derivative.


TITLE: Does $X^{C_2} \simeq * \simeq X/{C_2}$ imply $X \simeq *$?
QUESTION [4 upvotes]: What the title says. Let $C_2$ be the cyclic group of order 2, and $X$ be a topological space with a $C_2$-action (acting continuously) such that both the quotient space $X/{C_2}$ and the subspace of fixed points $X^{C_2}$ are contractible. Does that force $X$ itself to be contractible?

REPLY [2 votes]: Here is a counterexample, though it may not be very interesting to you because the space involved is not Hausdorff.  Let $X=\{a,b,c,d,e\}$, with topology generated by the sets $\{a\}$, $\{b\}$, $\{c\}$, $\{d,a,b,c\}$, and $\{e,a,b,c\}$.  Define $\sigma:X\to X$ by $\sigma(a)=b$, $\sigma(b)=a$, $\sigma(c)=c$, $\sigma(d)=e$, and $\sigma(e)=d$.  Then $\sigma$ is a homeomorphism and gives an action of $C_2$ on $X$.  The fixed points and quotient are contractible (the fixed points are just $\{c\}$ and the quotient has a point $[d]$ that is in the closure of every point), but $X$ is not contractible (in fact, it has the weak homotopy type of $S^1\vee S^1$).


TITLE: $SU(3)$ irreducible representations with tensor method
QUESTION [7 upvotes]: I am dealing with the tensor product representation of $SU(3)$ and I have some problems in understanding some decomposition.
1) Let's find the irreducible representation of $3\otimes\bar{3}$
we have that this representation trasforms like
$${T^\prime}^i_j=U^i_k {U^{\dagger}}^l_j T^k_l $$
hence I observe that
$$Tr(T)=\delta^j_iT^i_j$$
is an invariant and so
$$T^i_j=\left(T^i_j-\frac{1}{3}\delta^j_iT^i_j\right)+\frac{1}{3}\delta^j_iT^i_j$$
allows me to write
$$3\otimes\bar{3}=8\oplus1$$
Here comes my questions: I have heard that this $8$ representation is an "$8_{MA}$" where MA is for "mixed-antisymmetric". The meaning of "mixed-antisymmetric" shold be: "the tensor $\left(T^i_j-\frac{1}{3}\delta^j_iT^i_j\right)$ should be antisymmetric for an exchange of 2 particular indexes but not for a general exchange of 3 indexes". What does this mean? I see only 2 index in that tensor.
2) Consider this representation: $$3\otimes3\otimes3=3\otimes(6\oplus\bar{3})=3\otimes6_S\oplus3\otimes\bar{3}=3\otimes 6_S\oplus8_{MA}\oplus1$$
and now on my notes I have
$$3\otimes6_S=10_S\oplus8_{MS}$$
Where "MS" is for "mixed symmetric": symmetric for an exchange of 2 particular indexes but not for a general exchange of 3 indexes.
I could not demonstrate this last decomposition using tensor method.
I started noticeing that:
$$3\otimes6_S=q^iS^{k,l}$$
where $S^{k,l}$ is a symmetric tensor
But then I am not able to proceed in demonstrating the above decomposition (note: I would like to demonstrate this decomposition using only tensor properties, not Young tableaux).
I tried to look on Georgi, Hamermesh, Zee and somewhere online but I have not found any good reference which explains well this representatin decomposition...
EDIT:
the demonstration should not include the use of Young diagrams...my professor started the demonstration by writing $\epsilon_{\rho,i,k}q^i S^{k,l}=T'^l_\rho=8_{MS}$ and then stopped the demonstration.

REPLY [1 votes]: Since the accepted answer treats the problem through the point of view of Young diagrams and I was having some problems with tensor methods myself, I  believe it is worth to add the tensor approach in here.
Mixed Antisymmetric
Concerning the meaning of $MA$, recall that $SU(3)$ representations can be characterized in terms of "upstairs symmetrized indices" and "downstairs symmetrized indices" (see, for example, the beginning of Chapter V.2 of Zee's Group Theory in a Nutshell for Physicists). In other worlds, while $(^_−\frac{1}{3}^i_j ^k_k)$ does have only two indices, we could also raise the lower index with a Levi-Civita symbol, hence obtaining $(^_\epsilon^{jkl} −\frac{1}{3}\epsilon^{ikl}^k_k)$, which is now explicitly antisymmetric in two indices. The lesson here is that in $SU(3)$, thanks to the peculiar existence of a Levi-Civita symbol with three indices, we can write every tensor in terms of tensors with symmetrized indices, being these "upstairs" or "downstairs".
Computing $3 \otimes 6_S$
Let us then proceed to use tensor methods to write the tensor product of the representations. We have here a vector $q^i$ transforming in the fundamental representation, $3$, and a symmetric tensor $S^{jk}$ transforming in the $6_S$ representation. As you noticed, an object transforming in the $3 \otimes 6_S$ representation transforms as $q^i S^{jk}$. Since the representations of $SU(3)$ are characterized by symmetric tensors with indices upstairs or downstairs, our goal will be to separate the antissymetric parts in each index combination.
We can't antisymmetrize the indices of $S_{jk}$, since it is a symmetric tensor. We are left to antisymmetrize the index of $q^i$ with each of the indices of $S_{jk}$. Hence, we employ the Levi-Civita symbol to get
$$q^i S^{jk} = \frac{1}{3}\epsilon^{ijl}\epsilon_{lmn}q^mS^{nk} + \frac{1}{3}\epsilon^{ikl}\epsilon_{lmn}q^mS^{jl} + \left(q^i S^{jk} - \frac{1}{3}\epsilon^{ijl}\epsilon_{lmn}q^mS^{nk} - \frac{1}{3}\epsilon^{ikl}\epsilon_{lmn}q^mS^{jl}\right)$$
The coefficients are chosen so that the last term is fully symmetric in the three indices. Another possibility would be to pick the ansatz $S^{ijk} = q^i S^{jk} - a\epsilon^{ijl}\epsilon_{lmn}q^mS^{nk} - b\epsilon^{ikl}\epsilon_{lmn}q^mS^{jl}$ and impose the condition that $S^{ijk}$ is symmetric in all indices to get the correct coefficients.
Either, now the first term is symmetric under $j \leftrightarrow k$ and has no definite symmetry when $i$ is considered. The last term corresponds to a fully symmetric tensor, which has $10$ independent components, meaning it is a $10_S$. Hence, the first term has $8$ independent components and corresponds, as a consequence, to an $8_{MS}$, the $MS$ coming from mixed symmetry.
References

A. Zee, Group Theory in a Nutshell for Physicists (Princeton University Press: Princeton, 2016). Chapter V.2.


TITLE: Whether a set is Hausdorff
QUESTION [0 upvotes]: To prove:
A space $X$ is Hausdorff if and only if the set $\{(x,x)~|~x\in X\}$ is closed in $X\times X$.
If $X$ is Hausdorff then if a sequence $\{x_n\}_{n=1}^{\infty}$ of elements of $X$ converges in $X$, then the limit is unique. So a sequence in the given set, $\{(x_n,x_n)\}_{n=1}^{\infty}$ has to go to the point $(x,x)$ if $\lim_{n\rightarrow\infty}x_n=x$, and it will not converge if the sequence  $\{x_n\}_{n=1}^{\infty}$ doesn't. Hence the given set is closed.
How can I show the converse.

REPLY [1 votes]: Define:$$\Delta:=\{\langle x,x\rangle\mid x\in X\}$$
Let it be that $u,v\in X$ with $u\neq v$ or equivalently $\langle u,v\rangle\in\Delta^{\complement}$.
$\Delta^{\complement}$ is an open set in $X\times X$ so open sets $U,V$ must exists with $\langle u,v\rangle\in U\times V\subseteq\Delta^{\complement}$.
Now observe that $U\cap V=\varnothing$ while $u\in U$ and $v\in V$.


TITLE: Find extremizers using Lagrange multipliers
QUESTION [0 upvotes]: Using Lagrange multipliers,
$$\begin{array}{ll} \text{extremize} & x + y\\ \text{subject to} & x^{2} + y^{2} \leq 5\\ & x \geq 0\end{array}$$
Graphically, it comes that the maximiser is $(\sqrt{5}, 0)$, but the minimizer is unclear. How to find it? How should Lagrange multiplier looks like?

REPLY [1 votes]: For this simple problem you don't need Lagrange multipliers. Instead draw a figure.
The feasible domain $B$ is a right half disc of radius $\sqrt{5}$. The objective function has level lines $x+y=c$, which are lines descending with slope $45^\circ$. When $c$ gets larger the line is translated in  direction north-east. Now find out which is the most south-west such line meeting a point of $B$, and which is the most north-east such line meeting a point of $B$.
Note that one of the two points would not be found using Lagrange multipliers.


TITLE: Order of an element as a product
QUESTION [3 upvotes]: I apologise if this has been asked before, but I wasn't able to find it..
I am trying to prove that if $g\in G$, where $G$ is an arbitrary group,$|g| = n$, where $n = ab$, with $\gcd(a, b) = 1$, then there exist $h,k\in G$ such that $g = hk$, and $|h| = a$, $|k| = b$.
So far I have reasoned that the identity and $g$ itself would be suitable choices for $h$ and $k$.
However, I am asked to determine if there are more than one choice for $h$ and $k$.
It seems to me that if $G$ is cyclic, then there might me more than one choice for $h,k$ as in finite abelian groups, the product of two elements have order equal to the product of their order. But I am wondering if they would satisfy the $\gcd(a,b)=1$ criteria, and what happens when $G$ is not cyclic?
I hope someone might be able to help me out!

REPLY [2 votes]: Since $ gcd(a, b) = 1$ there are such $c,d$ that $ac+bd=1$. Set $h=g^{bd}, k=g^{ac}$.
The choice is unique. If we have another such pair $h_1,k_1$ then  $hk=h_1k_1$ implies  $h^{-1}h_1=k^{-1}k_1$. Denote this element by $x$, then $x^a=(h^{-1}h_1)^a=1$ and simlarly $x^b=1$. Again from  $ac+bd=1$ it follows $x=1$ etc.


TITLE: Popular Journals for Theoretical CS
QUESTION [4 upvotes]: Are there some popular journals in the field of theoretical CS that serve the kind of purpose that a journal like "Physics Today" does for the Physics community ?

REPLY [4 votes]: From the information I could find online, I assume that the purpose of "Physics Today" is to summarize the incredibly vast field of physics and promote results that are considered important enough to be known from researchers with a different specialization from the subject matter. The focus is also on newly published results, rather than re-examining classical ones or establishing a "must-know" basis.
With this assumption, I believe the answer is no. The field has embraced Web technologies to a degree where results are usually known months before their official publishing in conferences and years before the journal version is out, with preprints being available typically via arxiv and rigorous discussions being held in popular blogs (for example Lipton&Regan, Fortnow&Gasarch , Aaronson ), TCS+ and questions appearing on this site as well.
Perhaps the one that comes the closest is Journal of the ACM (JACM).
See also this question.


TITLE: Toy examples for Kan extensions
QUESTION [29 upvotes]: Background: If $\mathcal{C}$ is a cocomplete category and $f : I \to J$ is a functor between small categories, then $f^* : \mathrm{Hom}(J,\mathcal{C}) \to \mathrm{Hom}(I,\mathcal{C})$ has a left adjoint $\mathrm{Lan}(f)$, the left Kan extension along $f$. One may express this as the following coend:
$$\mathrm{Lan}(f)(F) = \int^i \hom(f(i),-) \otimes F(i).$$
What are some toy examples for left Kan extensions? I know that left Kan extensions are generalizations of colimits, that they are useful for constructing pullback functors of presheaves and the definition of left derived functors in the context of model categories as well as homological algebra. But I would like to see some specific easy examples which are perhaps not really important, but show what's going on.
Here is an example: Consider the inclusion $f : \{0,1\} \hookrightarrow \{0<1\}$. The left Kan extension corresponds to the functor $\mathcal{C} \times \mathcal{C} \to \mathrm{Mor}(\mathcal{C})$ which maps a pair of objects $(A,B)$ to the morphism $(A \to A \oplus B)$.
I am not looking for well-known general classes of examples (geometric realization, tensor products, etc.).

REPLY [4 votes]: If you like simplicial sets: We have an adjunction

where

$\mathrm{inj}$ is the functor sending $\star$ to $[0]$ and $\mathrm{id}_{\star}$ to $\mathrm{id}_{[0]}$.
$\mathrm{pr}$ is the unique functor from $\Delta$ to $\mathsf{pt}$.

Taking left/right Kan extensions then gives you the usual quadruple adjunction between $\mathsf{Sets}$ and $\mathsf{sSets}$:

You also have for each $n\in\mathbb{N}$ a functor $\mathrm{inj}_n\colon\mathsf{pt}\longrightarrow\Delta$ sending $\star$ to $[n]$ and $\mathrm{id}_{\star}$ to $\mathrm{id}_{[n]}$. Taking Kan extensions gives you a triple adjunction, where one of the functors (the precomposition one) is $\mathrm{ev}_n$, the functor sending a simplicial set $X_\bullet$ to $X_n$.


TITLE: Finding sum of power $5$ in polynomial
QUESTION [3 upvotes]: Consider the function $f(x)=x^4-2x^3-x^2+17x+6$ and another function $g(x)=x^5-3x^4+22x^2-18x-2$ and $f(x)=0$ has a roots $x_{1},x_{2},x_{3},x_{4}.$ Then $\sum^{4}_{k=1}g(x_{k})$ is
what i try
$x^4-2x^3-x^2+17x+6=(x-x_{1})(x-x_{2})(x-x_{3})(x-x_{4})$
$\displaystyle \sum x_{1}=2\;\;, \sum x_{1}x_{2}=-1\;\;,\sum x_{1}x_{2}x_{3}=-17$ and $\displaystyle \prod x_{1}=6$
$\displaystyle \sum^{4}_{k=1}g(x_{k})=\sum^{4}_{k=1}(x_{k})^5-3\sum^{4}_{k=1}(x_{k})^4+22\sum^{4}_{k=1}(x_{k})^2-18\sum^{4}_{k=1}(x_{k})-2\sum^{4}_{k=1}1$
$\displaystyle \sum^{4}_{k=1}g(x_{k}) = \sum^{4}_{k=1}(x_{k})^5-3\sum^{4}_{k=1}(x_{k})^4+22(4+2)-18(2)-2(4)$
How do i solve it Help me please

REPLY [1 votes]: HINT...Writing $$S_n=\sum_{i=1}^4x^n_i$$
You have $$S_0=4, S_1=2, S_2=6$$ And also $$S_{-1}=\frac{\Sigma\alpha\beta\gamma}{\alpha\beta\gamma\delta}=-\frac{17}{6}$$
Then, you can obtain $S_3$ from the equation itself because $$S_3-2S_2-S_1+17S_0+6S_{-1}=0$$
and then obtain $S_4$ from $$S_4-2S_3-S_2+17S_1+6S_0=0$$
and then obtain $S_5$ from $$S_5-2S_4-S_3+17S_2+6S_1=0$$
Alternatively, following Jyrki Lahtonen's suggestion, you sum the identity he gives so that $$\sum g(x_i)-0=-S_3+4S_2-7S_1+4S_0$$


TITLE: Flotation of a body which is submersed into a incompressible fluid using Archimedes principal
QUESTION [1 upvotes]: There is a small boat in a water tank and the boat is loaded with a huge piece of rock .The water tank is totally filled with water .If the rock is taken off from the boat and totally submerged in the tank water then what will happen to the water level of the tank?

REPLY [0 votes]: If the rock is completely submerged the water will not fill the tank.
If we assume that the rock, in the idealized boat, weights 4000 kg and its volume is 1 m^3 then the situation is equivalent to filling the boat with 4 m^3 of water or adding 4 m^3 of water in the tank.
If the rock is submerged then the situation is equivalent to adding just 1 m^3 of water when 4 m^3 are needed to fill the tank.


TITLE: How do we get definitions of fundamental terms from a formula like the Work-Energy Theorem?
QUESTION [0 upvotes]: I’m a senior taking AP Physics C, and I’m currently losing my mind over this question.
I get that work is essentially a measure of whether a force is “successful” or not in displacing an object in its direction. And, that if said force is successful, the velocity of the object must change in response and gain kinetic energy. I think that kinetic energy is just the ability to influence another object’s acceleration by motion. But here’s the thing. These definitions are completely reliant on the assumption that the “equals” sign in the Work-Energy Theorem makes both sides of the equation an “if then, then that” statement.
The closest I have come in this case is that energy is simply work yet to be done, but I still have no way of knowing if my intuition is correct or not from the equation. I was able to define force and momentum without relying on prior definitions, but with this, I’ve hit a roadblock. And that roadblock begs the question in the title.
Also, this is my first time using this site, so any tips on using the site to get the most viewers for a question possible would be very appreciated. Thanks in advance for answering the question!

REPLY [0 votes]: I take your question as a question about the nature of kinetic energy.
Let me recount some history:
In the development of mechanics, the study of motion of objects, there was a long period of strong contention as to what should be regarded as the true Quantity of Motion. This conflict arose because there are two candidates:
In modern notation:
$mv$
$\frac{1}{2}mv^2$
The first is of course the quantity 'momentum' and the second 'kinetic energy'.
Both these quantities comply with the principle of relativity of inertial motion.
The concept of kinetic energy can be visualized as follows: let's say you have a rolling ball, knocking over pins. The pins are arranged in a row, the ball is knocking them down one by one. Every time the ball knocks down a pin it loses some of its velocity. (Assume each pin receives the same impulse.) Given a particular starting velocity the ball will come to a stop after a certain number of pins has been knocked over.
Now compare two runs, and in the second run the ball is given twice as much velocity as in the first run. Then in the second run the ball will knock over 4 times as many pins as compared to the first run. This is of course due to the fact that when accelerating/decelerating distance covered is a quadratic function of time ($s = \frac{1}{2}at^2$)
I recommend thinking of kinetic energy in terms of the basic relation ($s = \frac{1}{2}at^2$) rather than in terms of some higher level concept such as 'ability to influence another object's acceleration'.
(finishing the history:
Over time the debate among scientist as to the true expression of Quantity of Motion evaporated. Today we use both, and they are regarded as equally important.)

Let me simplify to the case where the force is constant.
The effect of force is of course cumulative. If the duration of the force acting is twice as long it causes twice the amount of change of momentum. That is, change of momentum can be computed by multiplying force with time
Multiplying force with time feels very natural; force causes acceleration, the longer the duration of the acceleration the more velocity.

We regard kinetic energy as a good measure of quantity of motion, so we need an expression to relate force to kinetic energy.
The general definition of work done is an integral, but when the force is constant the calculation simplifies to multiplying the force with the distance traveled.
$F\Delta s = \Delta(\frac{1}{2}mv^2)$
For sure: multiplying force with distance doesn't have the natural feel of multiplying force with time.
It is what it is: work done is how you express the relation between force being exerted and kinetic energy. That is: the concept of kinetic energy is what gives the concept of work done meaning.


TITLE: For $f_n \in C^\infty (\mathbb{R})$, prove $xf_n(x) \to 0$ uniformly given some conditions on all derivatives.
QUESTION [2 upvotes]: Unnecessary context: I'm trying to show equivalence between two conditions for convergence in Schwartz space $\mathcal{S}(\mathbb{R}^d) = \{f \in C^\infty(\mathbb{R}^d) | x^\alpha D^\beta f \text{ is bounded for any multi-indices } \alpha,\beta \}$, and I've reduced it to the following problem (in one dimension):
If $(f_n)_{n=1}^\infty \subset C^\infty(\mathbb{R})$ satisfies $\forall l \in \mathbb{N}$ $f_n^{(l)} \to 0$ uniformly and $\forall k,l \in \mathbb{N}$ $\exists C_{k,l}>0$ such that $\forall x \in \mathbb{R}, n \in \mathbb{N}$ we have $|x^kf_n^{(l)}(x)| \leq C_{k,l}$, then $xf_n(x) \to 0$ uniformly (on $\mathbb{R}$).
In the above, $\mathbb{N}$ includes $0$. The fairly strong hypotheses are remnants of the more general condition I'm trying to show-- they're needed for the generalization, but I doubt we'll need the conditions on all derivatives or all powers of $x$ for the above result (if it holds). I've been considering this for a while and haven't been able to come up with a proof. Noting that we trivially have the needed bounds on $|xf_n(x)|$ for $x \in [-1,1]$, my thought is to consider the integral representation of $xf_n(x)$ for $x \neq 0$ as
$$ xf_n(x) = \int_{-\infty}^{x^2} f_n' \left( \frac{t}{x} \right) dt $$
(since $|f_n(t)| = \frac{|tf_n(t)|}{|t|} \leq \frac{C_{1,0}}{|t|} \to 0$ as $|t| \to \infty$). The integrand goes to $0$ uniformly by hypothesis, but the domain of integration is unbounded. My hope was to use the hypotheses to prove that the integration over the "ends" can be made arbitrarily small in a way independent of $|x|$, leaving only the bounded domain. However, the most straightforward approaches seem to be rigged to leave a factor of $|x|$ in the bound. For example,
$$ \left| \int_N^{\infty} f_n' \left( \frac{t}{x} \right) dt \right|
\leq \int_N^\infty \left| f_n' \left( \frac{t}{x} \right) \right|dt
\leq \int_N^\infty \frac{C}{1+(\frac{t}{x})^2} dt =C|x| \left( \frac{\pi}{2}-\tan^{-1} \left( \frac{N}{|x|} \right) \right)$$
for some $C>0$, and I cannot choose $N$ large enough such that this is less than some fixed $\epsilon$ for all $|x|>1$. Any hints, counterexamples, or pointers indicating that I'm missing something obvious would be much appreciated.

REPLY [1 votes]: Hint: Take a sequence $a_n $ for which $a_n \to \infty$ and $a_n\|f_n\|_\infty \to 0$ as $n\to\infty$. Then, for $x \le a_n$,
$$ |xf_n(x)| \le a_n \|f_n\|_\infty =o(1)$$
and for $|x|> a_n$,
$$ |xf_n(x)| \le C_{2,0}|x|^{-1} = O(a_n^{-1}). $$
Can you fill in the gaps and continue from here? Hope this helps.


TITLE: Probability of 2 discrete i.i.d. random variable to be 0.
QUESTION [0 upvotes]: If $X_1$ and $X_2$ are 2 random i.i.d. variables. What is the probability of $P(X_1 = X_2)$.
\begin{equation} P(X_1=X_2) = \sum_{i \in \mathbb{Z}} P_{X_1,X_2}(i,i) = \sum_{i \in \mathbb{Z}} P_{X_1}(i)^2.
\end{equation}
Similar question with same proof- Probability of iid random variables to be equal? But there doesn't seem to be a convincing answer for the discrete case for at least me in the thread. Or I couldn't understand it properly.

REPLY [0 votes]: We have
$  p\left( {{X_1} = {X_2}} \right) =   \\
  \sum\limits_{x \in {\Omega _{{X_1}}} \cap {\Omega _{{X_2}}}} {p\left( {{X_1} = {X_2} = x} \right)}  = \quad \quad \quad \quad \quad \quad {\text{by total probability}} \\
  \sum\limits_{x \in {\Omega _{{X_1}}} \cap {\Omega _{{X_2}}}} {p\left( {{X_1} = x,{X_2} = x} \right)}  = \quad \quad \quad \quad \quad {\text{by transitivity of equality}} \\
  \sum\limits_{x \in {\Omega _{{X_1}}} \cap {\Omega _{{X_2}}}} {p\left( {\left. {{X_1} = x} \right|{X_2} = x} \right)} p\left( {{X_2} = x} \right) = \quad {\text{by the product rule}} \\
  \sum\limits_{x \in {\Omega _{{X_1}}} \cap {\Omega _{{X_2}}}} {p\left( {{X_1} = x} \right)} p\left( {{X_2} = x} \right) = \quad \quad \quad \quad {\text{if }}{X_1}{\text{ and }}{X_2}{\text{ are independent}}  \\
  {\sum\limits_{x \in {\Omega _{{X_1}}} \cap {\Omega _{{X_2}}}} {p\left( {{X_1} = x} \right)} ^2}\quad \quad \quad \quad \quad \quad \quad \quad \;\;{\text{if }}{X_1}{\text{ and }}{X_2}{\text{ have same probability distribution}}
$