text:
\begin{document}

\begin{abstract}
Generalized associahedra were introduced by S. Fomin and A. Zelevinsky in connection to finite type cluster algebras. Following recent work of L.~Pournin in types~$A$ and~$B$, this paper focuses on geodesic properties of generalized associahedra. We prove that the graph diameter of the $n$-dimensional associahedron of type~$D$ is precisely~$2n-2$ for all~$n$ greater than~$1$. Furthermore, we show that all type~$BCD$ associahedra have the non-leaving-face property, that is, any geodesic connecting two vertices in the graph of the polytope stays in the minimal face containing both. This property was already proven by D.~Sleator, R.~Tarjan and W.~Thurston for associahedra of type $A$. In contrast, we present relevant examples related to the associahedron that do not always satisfy this property.

\smallskip
\noindent
{\sc keywords.}
Associahedron -- graph diameter -- pseudotriangulation -- flip graph.
\end{abstract}

\vspace*{-.8cm}

\maketitle

\vspace*{-.3cm}

\section{Introduction}

The associahedron is a convex polytope whose vertices are in correspondence with triangulations of a convex polygon and whose edges are flips among them.
Motivated by efficiency of repeated access and information update in binary search trees, D.~Sleator, R.~Tarjan and W.~Thurston~\cite{SleatorTarjanThurston} showed that the diameter of the $n$-dimensional associahedron is at most~$2n-4$ for~$n$ greater than~$9$, and used arguments in hyperbolic geometry to prove that this bound is tight when~$n$ is large enough. They also conjectured that the diameter is~$2n-4$ for all~$n$ greater than~$9$. This conjecture was recently settled using purely combinatorial arguments by L.~Pournin~\cite{Pournin}, who explicitly exhibited two triangulations realizing this maximal distance.

Associahedra are considered as one of the most important families of examples in polytope theory~\cite{LoeraRambauSantos,Ziegler1}. Besides their combinatorial beauty, they are of great importance in diverse areas in mathematics, computer science and physics~\cite{Stasheff, Stasheff-operads, TamariFestschrift}. One of the most significant appearances of associahedra is in the theory of cluster algebras initiated by S.~Fomin and A.~Zelevinsky~\cite{FominZelevinsky-ClusterAlgebrasI,FominZelevinsky-ClusterAlgebrasII}. They introduced a notion of generalized associahedra which extends the concept of associahedra to any Weyl group~\cite{FominZelevinsky-YSystems}. These essential objects encode the flip graphs of cluster algebras of finite type, and were realized as polytopes for the first time by F.~Chapoton, S.~Fomin and A.~Zelevinsky~\cite{ChapotonFominZelevinsky}. The concept of generalized associahedra was further extended to arbitrary Coxeter groups by N.~Reading in~\cite{Reading-CambrianLattices}. All these Coxeter associahedra, including those corresponding to Weyl groups, were realized as polytopes by C.~Hohlweg, C.~Lange and H.~Thomas~\cite{HohlwegLangeThomas} in connection with the Cambrian fans studied by N.~Reading and D.~Speyer in~\cite{ReadingSpeyer}.
Three interesting cases of generalized associahedra are the infinite families of type~$A$ (classical associahedra), of type~$B/C$ (cyclohedra), and of type~$D$.

In this paper, we show that the diameter of the $n$-dimensional associahedron of type~$D$ is precisely~$2n-2$ for all $n$ greater than~$1$. This is done using a convenient combinatorial model for type~$D$ associahedra in terms of centrally symmetric pseudotriangulations of a regular \mbox{$2n$-gon} with a small hole in the center. The same proof was presented independently by Y.~Lebrun in~\cite{Lebrun} using the combinatorial model in terms of decorated triangulations of the punctured $n$-gon arising from the work of S.~Fomin, M.~Shapiro and D.~Thurston~\cite{FominShapiroThurston}. As in~\cite{Pournin}, our methods are purely combinatorial and we explicitly describe two vertices of the polytope which are at maximal distance. In a recent preprint~\cite{Pournin-diameterTypeB}, L.~Pournin extends his method used in type~$A$ to derive the asymptotic diameter of type~$B$ associahedra: he shows that the diameter of the $n$-dimensional associahedron of type~$B$ is asymptotically~$5n/2$. As the type~$I_2(p)$ associahedron is a $(p+2)$-gon with diameter~${\lfloor p/2 \rfloor + 1}$, L.~Pournin's and our paper thus settle the problem of the graph diameters of generalized associahedra. For completeness, we gather in Table~\ref{table:asymptoticDiameters} the asymptotic diameters for type~$A$, $B/C$ and~$D$ associahedra, and in Table~\ref{table:smallDiameters} the precise diameters of the small rank generalized associahedra. The latter were reported in \cite{SleatorTarjanThurston} for type~$A$, in \cite{Pournin-diameterTypeB} for type~$B$, and were computed using C. Stump's Sage package on subword complexes for exceptional~types.

\begin{table}
    \centerline{
    \begin{tabular}{|l|c|c|c|}
    \hline
    \quad type & $A$ & $B/C$ & $D$ \\
    \quad asymptotic diameter$\quad$ & $\quad 2n-4 \quad $ & $\quad 5n/2 \quad$ & $\quad 2n-2 \quad$ \\
    \hline
    \end{tabular}
    }
    \bigskip
    \caption{Asymptotic diameters of type~$A$, $B/C$ and~$D$ associahedra.}
    \label{table:asymptoticDiameters}
\end{table}

\begin{table}
	\vspace{-.3cm}
    \centerline{
    \begin{tabular}{|p{1.4cm}|p{.1cm}p{.1cm}p{.1cm}p{.1cm}p{.1cm}p{.2cm}p{.2cm}p{.3cm}|p{.1cm}p{.1cm}p{.1cm}p{.1cm}p{.2cm}p{.2cm}p{.2cm}p{.2cm}p{.2cm}p{.2cm}p{.3cm}|c|p{.2cm}p{.2cm}p{.3cm}|p{.2cm}|p{.1cm}p{.3cm}|c|}
    \hline
    type & \multicolumn{8}{c|}{$A$} & \multicolumn{11}{c|}{$B/C$} & $D$ & \multicolumn{3}{c|}{$E$} & $F$ & \multicolumn{2}{c|}{$H$} & $I_2(p)$ \\
    rank & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ & $11$ & $12$ & $n$ & $6$ & $7$ & $8$ & $4$ & $3$ & $4$ & $2$ \\
    diameter & $2$ & $4$ & $5$ & $7$ & $9$ & $11$ & $12$ & $15$ & $3$ & $5$ & $7$ & $9$ & $11$ & $14$ & $16$ & $18$ & $21$ & $23$ & $25$ & $2n-2$ & $11$ & $14$ & $19$ & $8$ & $6$ & $10$ & $\lfloor p/2 \rfloor + 1$ \\
    \hline
    \end{tabular}
    }
    \bigskip
    \caption{Diameters of small rank associahedra of arbitrary finite types.}
    \label{table:smallDiameters}
\end{table}

In connection to this graph diameter question, we also show that all infinite families of associahedra of finite types have the non-leaving-face property, namely  every geodesic connecting two vertices in the graph of the polytope stays in the minimal face containing both. This is a known result of D.~Sleator, R.~Tarjan and W.~Thurston~\cite[Lemma~3]{SleatorTarjanThurston} for type $A$. Using similar \emph{normalization} ideas, we prove it type-by-type for types~$BCD$. By computer experiment with the computer software Sage~\cite{sage}, we also checked this property in the exceptional types~$E_6$,~$F_4$,~$H_3$ and~$H_4$. The remaining types~$E_7$ and~$E_8$ were still to be checked when N.~Williams announced a type-free proof of the non-leaving-face property for all generalized associahedra~\cite{Williams}. In contrast, we present five remarkable examples related to the associahedron which do not always satisfy this property: the pseudotriangulation polytopes, the multiassociahedra, the graph associahedra, the secondary polytopes, and the flip graphs on all triangulations of a point set.

\section{Pseudotriangulation model for type~$D$ associahedra}
\label{sec:Dmodel}

In this section, we present a combinatorial model for the type~$D_n$ associahedra~$\Asso(D_n)$ in terms of pseudotriangulations of a geometric configuration~$\configD_n$. The vertices of~$\Asso(D_n)$ correspond to centrally symmetric \emph{pseudotriangulations}, and its edges to \emph{flips} between them. In Remark~\ref{rem:typeD}, we compare our geometric interpretation to the classical models of type~$D$ cluster algebras presented by S.~Fomin and A.~Zelevinsky in~\cite[Section~3.5]{FominZelevinsky-YSystems}\cite[Section~12.4]{FominZelevinsky-ClusterAlgebrasII} and by S.~Fomin, M.~Shapiro and D.~Thurston in~\cite{FominShapiroThurston}.

\begin{figure}[b]
	\centerline{\includegraphics[scale=.8]{configurationDn} \quad \includegraphics[scale=.85]{flipPseudotriangulation}}
	\caption{The configuration~$\configD_3$ has $9$ centrally symmetric pairs of chords (left). A centrally symmetric pseudotriangulation~$T$ of~$\configD_3$ (middle). The centrally symmetric pseudotriangulation of~$\configD_3$ obtained from~$T$ by flipping the chords~$2^{\textsc r}$ and~$\bar 2^{\textsc r}$.}
	\label{fig:configurationDn&Flips}
\end{figure}

We consider a regular convex~$2n$-gon, together with a disk~$\disk$ placed at its center, whose radius is small enough such that~$\disk$ only intersects the long diagonals of the $2n$-gon. We denote by~$\configD_n$ the resulting configuration, see \fref{fig:configurationDn&Flips}.
The vertices of~$\configD_n$ are labeled by $0,1,\dots, n-1, \overline 0, \overline 1,\dots ,\overline{n-1}$ in counterclockwise direction, such that two vertices $p$ and $\overline p$ are symmetric with respect to the center of the polygon.
The \defn{chords} of~$\configD_n$ are all the diagonals of the $2n$-gon, except the long ones, plus all the segments tangent to the disk~$\disk$ and with one endpoint among the vertices of the \mbox{$2n$-gon}. Note that each vertex~$p$ is adjacent to two of the latter chords; we denote by~$\diagD{p}{L}$ (resp.~by~$\diagD{p}{R}$) the chord emanating from~$p$ which goes tangent on the left (resp.~right) to the disk~$\disk$, and we call these chords \defn{central}.
For example, the four central chords that appear in \fref{fig:configurationDn&Flips}\,(middle) are $\diagD{0}{R},\diagD{\bar 0}{R},\diagD{2}{R}$ and $\diagD{\bar 2}{R}$.
The faces of the type~$D_n$ associahedron can be interpreted geometrically on the configuration~$\configD_n$ as follows:
\begin{enumerate}[(i)]
\item Facets correspond to \defn{centrally symmetric pairs of (internal) chords} of the geometric configuration~$\configD_n$, see \fref{fig:configurationDn&Flips}\,(left).

\item Faces correspond to crossing-free centrally symmetric sets of chords. The face lattice corresponds to the reverse inclusion lattice on crossing-free centrally symmetric sets of chords.

\item Vertices correspond to \defn{centrally symmetric pseudotriangulations} of~$\configD_n$ (\ie inclusion maximal centrally symmetric crossing-free sets of chords of~$\configD_n$). Each pseudotriangulation of~$\configD_n$ contains exactly~$2n$ chords, and partitions $\conv(\configD_n) \ssm \disk$ into \defn{pseudotriangles}  (\ie interiors of simple closed curves with three convex corners related by three concave chains). See \fref{fig:configurationDn&Flips}\,(middle) and (right). We refer to~\cite{RoteSantosStreinu-survey} for a complete survey on pseudotriangulations, including their history, motivations, and applications.

\item \label{item:pseudoflip} Edges correspond to \defn{flips} of centrally symmetric pairs of chords between centrally symmetric pseudotriangulations of~$\configD_n$. A flip in a pseudotriangulation~$T$ replaces an internal chord~$e$ by the unique other internal chord~$f$ such that~$(T \ssm e) \cup f$ is again a pseudotriangulation of~$T$. Indeed, deleting~$e$ in~$T$ merges the two pseudotriangles of~$T$ incident to~$e$ into a pseudoquadrangle~$\pseudoquadrangle$ (\ie the interior of a simple closed curve with four convex corners related by four concave chains), and adding~$f$ splits the pseudoquadrangle~$\pseudoquadrangle$ into two new pseudotriangles. The chords~$e$ and~$f$ are the two unique chords which lie both in the interior of~$\pseudoquadrangle$ and on a geodesic between two opposite corners of~$\pseudoquadrangle$. We refer again to~\cite{RoteSantosStreinu-survey} for more details.

For example, the two pseudotriangulations of \fref{fig:configurationDn&Flips} are related by a centrally symmetric pair of flips. We have represented different kinds of flips between centrally symmetric pseudotriangulations of the configuration~$\configD_n$ in \fref{fig:typeDflip}. Finally, \fref{fig:typeD3associahedron} shows the flip graph on centrally symmetric pseudotriangulations of~$\configD_3$, and Figures~\ref{fig:typeD4associahedron} and~\ref{fig:42pseudotriangulationsHorizontal} the one~for~$\configD_4$.

\enlargethispage{.3cm}
\begin{figure}[b]
	\centerline{\includegraphics[width=.92\textwidth]{typeDflip}}
	\caption{Different kinds of flips in type~$D$.}
	\label{fig:typeDflip}
\end{figure}

\begin{figure}
	\centerline{\includegraphics[width=.6\textwidth]{typeD3associahedron}}
	\caption{The type~$D_3$ flip graph interpreted geometrically with centrally symmetric pseudotriangulations of~$\configD_3$. Note that this graph is the $1$-skeleton of the $3$-dimensional associahedron since~$D_3 = A_3$.}
	\label{fig:typeD3associahedron}
\end{figure}
\end{enumerate}

\begin{remark}
\label{rem:typeD}
Our geometric interpretation of type~$D$ associahedra slightly differs from that of S.~Fomin and A.~Zele\-vinsky in~\cite[Section~3.5]{FominZelevinsky-YSystems}\cite[Section~12.4]{FominZelevinsky-ClusterAlgebrasII}. Namely, to obtain their interpretation, we can just remove the disk in the configuration~$\configD_n$ and replace the centrally symmetric pairs of chords~$\{\diagD{p}{L}, \diagD{\bar p}{L}\}$ and~$\{\diagD{p}{R}, \diagD{\bar p}{R}\}$ by long diagonals~$\diag{p}{\bar p}$ colored in red and blue respectively.
Another classical model for the type~$D$ cluster algebra is given by the decorated triangulations of the punctured $n$-gon from the work of S.~Fomin, M.~Shapiro and D.~Thurston~\cite{FominShapiroThurston}. We can obtain this model by folding our $2n$-gon around its central symmetry. In~\cite{Lebrun}, Y.~Lebrun gives the same proof of the diameter of the type~$D$ associahedron presented in the next section using this punctured $n$-gon model.
\end{remark}

\section{Diameter}

In this section, we present an explicit formula for the diameter of type~$D$ associahedra.

\begin{theorem}
\label{theo:diameter}
The diameter of the $n$-dimensional associahedron of type~$D$ is exactly~$2n-2$~for~all~$n$ greater than~$1$.
\end{theorem}

Define the \defn{left star}~$\starL$ to be the pseudotriangulation formed by all left central chords~$\diagD{p}{L}$ for~${p \in [n] \cup [\bar n]}$. Similarly, the \defn{right star}~$\starR$ is formed by all right central chords~$\diagD{p}{R}$ for~$p \in [n] \cup [\bar n]$.

\begin{lemma}
\label{lem:distanceStars}
The flip distance between the left star~$\starL$ and the right star~$\starR$ is precisely~$2n-2$.
\end{lemma}

\begin{proof}
We first claim that there is a path of exactly $2n-2$ flips between~$\starL$ and~$\starR$. This path is illustrated in \fref{fig:stars}, where the label on each arrow records the number of flips used to pass from one pseudotriangulation to the next one. Consider an arbitrary pair of opposite points~$\{p, \bar p\}$ of~$\configD_n$. Starting from~$\starL$, we successively flip the chord~$\diagD{(p+i)}{L}$ to the chord~$\diag{p}{p+i+1}$ for~$i \in [n-2]$, then the chord~$\diagD{p}{L}$ to the chord~$\diagD{(p-1)}{R}$, then the chord~$\diagD{(p-1)}{L}$ to the chord~$\diagD{\bar p}{R}$, and finally we successively flip the chord~$\diag{p}{\bar p - i}$ to the chord~$\diagD{(\bar p - i - 1)}{R}$ for~$i \in [n-2]$. Of course, we perform simultaneously the centrally symmetric flips of those just described. We thus used $(n-2)+1+1+(n-2) = 2n-2$ flips to transform~$\starL$ into~$\starR$.

\begin{figure}[h]
	\centerline{\includegraphics[width=1\textwidth]{stars}}
	\caption{The distance between the two stars~$\protect \starL$ and~$\protect \starR$ is $2n-2$.}
	\label{fig:stars}
\end{figure}

We now show that it is impossible to use less flips to transform~$\starL$ into~$\starR$. Observe that a pair of left central chords~$\{\diagD{p}{L}, \diagD{\bar p}{L}\}$ crosses any pair of right central chords~$\{\diagD{q}{R}, \diagD{\bar q}{R}\}$ except when~$p = q$. Therefore, if a centrally symmetric pseudotriangulation has strictly more than two pairs of left central chords then none of the possible flips produces a pair of right central chords. This means that we need to apply at least $n-2$ flips to the left star until we are able to make a flip that produces a pair of right central chords. Since the right star has $n$ pairs of right central chords, we need at least $n$ additional flips to produce it. This proves that any path between~$\starL$ and~$\starR$ uses at least $(n-2)+n= 2n-2$ flips.
\end{proof}

\begin{lemma}
\label{lem:distanceToStars}
Let~$T$ be a centrally symmetric pseudotriangulation of~$\configD_n$.
\begin{enumerate}[(i)]
\item If~$T$ contains~$\ell \ge 1$ centrally symmetric pairs of left central chords~$\{\diagD{p}{L}, \diagD{\bar p}{L}\}$, then~$T$ is precisely at distance~$n-\ell$ from the left star~$\starL$ and precisely at distance~$n+\ell-2$ from the right star~$\starR$.
\item If~$T$ contains~$r \ge 1$ centrally symmetric pairs of right central chords~$\{\diagD{p}{R}, \diagD{\bar p}{R}\}$, \mbox{then~$T$ is precisely} at distance~$n-r$ from the right star~$\starR$ and precisely at distance~$n+r-2$ from the left star~$\starL$.
\end{enumerate}
\end{lemma}

\begin{proof}
We prove Point (i) of the lemma, the other point follows by symmetry. Assume thus that~$T$ contains~$\ell \ge 1$ centrally symmetric pairs of left central chords.

Every non-left-central pair of chords in~$T$ needs to be flipped at least once in a path connecting~$T$ and~$\starL$. Moreover, it is possible to flip them one at a time such that each flip produces a pair of left central chords: at each step, flip a pair of centrally symmetric internal diagonals incident to a pseudotriangle touching the central disk. This shows that $T$ is precisely at distance~$n-\ell$ from the left star~$\starL$.

The proof that~$T$ is at distance~$n+\ell-2$ from~$\starR$ uses similar arguments to those in the proof of Lemma~\ref{lem:distanceStars}. If $\ell=1$, then~$T$ has exactly one pair of right central chords. In this case, the distance between~$T$ and~$\starR$ is~$n+\ell-2=n-1$ as desired. A geodesic between~$T$ and~$\starR$ can be obtained by successively flipping the $n-1$ non-right-central pairs of chords in $T$ such that each flip produces a pair of right central chords. If $\ell \geq 2$, then we need to apply at least~$\ell-2$ flips to~$T$ until we are able to make a flip that produces a pair of right central chords. Since the right star has~$n$ pairs of right central chords, we need at least~$n$ additional flips to produce it. Hence, the distance between~$T$ and~$\starR$ is~$n+\ell-2$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{theo:diameter}]
By Lemma~\ref{lem:distanceStars}, the diameter of the $n$-dimensional associahedron of type~$D$ is at least~$2n-2$. It remains to show that the distance between any two centrally symmetric pseudotriangulations~$T$ and~$\widetilde T$ is at most~$2n-2$. Let~$\ell$ and~$\widetilde \ell$ (resp.~$r$ and~$\widetilde r$) be the number of left (resp.~right) central pairs of chords in~$T$ and~$\widetilde T$ respectively. If~$T$ and~$\widetilde T$ contain a central pair of chords of the same kind, say left, then they can be connected by a path passing through the left star~$\starL$ of length
\[n-\ell+n-\widetilde \ell \leq 2n-2.\]
If not, we can assume without loss of generality that $\ell\geq 1$ and $\widetilde r\geq 1$. By Lemma~\ref{lem:distanceToStars}, there are two paths connecting $T$ and $\widetilde T$ passing through the star triangulations~$\starL$ and~$\starR$ respectively~of~length
\[
(n-\ell) + (n+\widetilde r-2)=2n-2-\ell+\widetilde r \qquad \text{and}\qquad (n+\ell-2)+(n-\widetilde r)=2n-2+\ell-\widetilde r.
\]
Clearly, one of these two numbers is less than or equal to $2n-2$.
\end{proof}

\section{Non-leaving-face property}

\enlargethispage{.4cm}
This section is devoted to the following natural property related to diameter and graph distance on polytopes.

\begin{definition}
A polytope~$P$ has the \defn{non-leaving-face property} if any geodesic connecting two vertices in the graph of~$P$ stays in the minimal face of~$P$ containing both.
\end{definition}

Many classical polytopes have the non-leaving-face property:
\begin{enumerate}[(i)]
\item the $n$-gon: proper faces are segments;
\item the simplex: any two vertices are at distance~$1$;
\item any simplicial polytope: any two vertices belonging to a proper face are at distance~$1$;
\item the $n$-cube: the distance between any two vertices is the Hamming distance between them (\ie the number of coordinates where they differ);
\item the permutahedron: the distance between two permutations~$\sigma, \widetilde \sigma$ in the permutahedron is the number of inversions of~$\sigma^{-1}\widetilde \sigma$, and the minimal face containing~$\sigma$ and~$\widetilde \sigma$ is the ordered partition~$\set{\sigma([n_{i+1}] \ssm [n_i])}{i \in [p]}$, where~$0 = n_0 < n_1 < \dots < n_p = n$ is the finest subdivision of~$[n]$ such that~$\sigma([n_{i+1}] \ssm [n_i]) = \widetilde \sigma([n_{i+1}] \ssm [n_i])$ for all~$i \in [p]$; leaving the minimal face containing~$\sigma$ and~$\widetilde \sigma$ thus introduces useless inversions and therefore lengthen the way from~$\sigma$ to~$\widetilde \sigma$;
\item the associahedron: see~\cite[Lemma~3]{SleatorTarjanThurston} and Theorem~\ref{thm:nonLeavingFaceProperty};
\item the cyclohedron (which we refer to as type~$B/C$ associahedron): see Theorem~\ref{thm:nonLeavingFaceProperty}.
\end{enumerate}
However, there are also many examples of polytopes that do not satisfy the non-leaving-face property, for example a pyramid over a hexagon. Other examples related to associahedra are presented in Section~\ref{sec:ctrexms}.

Note that the non-leaving-face property implies the classical non-revisiting property (between any two vertices, there exists a path which does not leave and revisit any facet), which in turn implies the Hirsch bound on the diameter of the polytope~\cite{Klee}, see also~\cite{Santos-surveyHirsch}. The reverse implications are wrong, consider \eg a pyramid over a square. The Hirsch bound for generalized associahedra also follows from their vertex-decomposability~\cite{CeballosLabbeStump}, or from general results on flag polytopes by K.~Adiprasito and B.~Benedetti~\cite{AdiprasitoBenedetti}. We focus here on the non-leaving-face property and refer to~\cite{Santos-surveyHirsch} for further details.

In this section, we show that all associahedra of type~$A$, $B/C$, or $D$ have the non-leaving-face property. This property was proven in type~$A$ by D.~Sleator, R.~Tarjan, and W.~Thurston~\cite[Lemma~3]{SleatorTarjanThurston}. We generically use the term ``triangulation'' to refer to the geometric model for clusters in type~$A$, $B/C$ or~$D$: classical triangulations of the $(n+3)$-gon in type~$A_n$, centrally symmetric triangulations of the $2n$-gon in type~$B_n/C_n$, and centrally symmetric pseudotriangulations of the configuration~$\configD_n$ in type~$D_n$. Similarly, ``diagonal'' refers to a diagonal in type~$A_n$, to a centrally symmetric pair of diagonals or a long diagonal in type~$B_n/C_n$, and to a centrally symmetric pair of chords of the configuration~$\configD_n$ in type~$D_n$.

\begin{theorem}
\label{thm:nonLeavingFaceProperty}
All associahedra of type~$A$, $B/C$, $D$ have the non-leaving-face property. In other words, no common diagonal between two triangulations~$T, \widetilde T$  is flipped in a geodesic between~$T$~and~$\widetilde T$.
\end{theorem}

\begin{remark}
Since the type~$I_2(n)$ associahedra are all polygons, this proposition proves that all infinite families of associahedra have the non-leaving-face property.
We also checked this property for the exceptional types~$E_6$, $F_4$, $H_3$ and~$H_4$. We use a variant of breadth first search algorithm to compute all geodesics from a given point and we check along the way that these geodesics stay in the smallest face containing their endpoints. For concrete computations, we use the subword complex model for finite type cluster algebras~\cite{CeballosLabbeStump} as implemented by C.~Stump in Sage~\cite{sage}. This time-consuming verification (about half a day for~$E_6$) was still to be done on types~$E_7$ and~$E_8$ when N.~Williams announced a type-free proof of the non-leaving-face property for all generalized associahedra~\cite{Williams} using sortable elements and Cambrian lattices~\cite{Reading-CambrianLattices}. Below, we stick to our original type-by-type proof which involves more geometric arguments.
\end{remark}

Theorem~\ref{thm:nonLeavingFaceProperty} is a consequence of the following stronger statement. In fact Proposition~\ref{prop:enteringFaceProperty} even shows that any path leaving the minimal face containing two vertices has at least~$2$ more steps than the geodesic connecting them.

\begin{proposition}
\label{prop:enteringFaceProperty}
Let~$T$ and~$\widetilde T$ be two triangulations of type~$A$, $B/C$, or $D$, and~$\chi$ be a diagonal in~$T \ssm \widetilde T$. If the flip of~$\chi$ in~$T$ produces a diagonal that belongs to~$\widetilde T$, then there exists a geodesic between~$T$ and~$\widetilde T$ which starts by the flip of~$\chi$.
\end{proposition}

The proof of Proposition~\ref{prop:enteringFaceProperty} relies on a normalization argument, generalizing the normalization of~\cite[Lemma~3]{SleatorTarjanThurston} for classical triangulations. We first introduce the normalization on triangulations of types~$A$, $B/C$ and~$D$, and then return to the proof of Theorem~\ref{thm:nonLeavingFaceProperty} and Proposition~\ref{prop:enteringFaceProperty} in Section~\ref{subsec:proofs}.

\subsection{Normalization}

A normalization is a useful tool to transform a geodesic between two triangulations into a geodesic starting with a prescribed flip. In particular, it is a projection from the graph of the associahedron to the graph of one of its facets. Recall that we use the terms ``triangulation'' and ``diagonal'' generically for the corresponding geometric models in types~$A$, $B/C$, and~$D$.

\begin{proposition}
\label{prop:normalization}
For any type~$A$, $B/C$ or~$D$, and for any diagonal~$\chi$, there exists a \defn{normalization}~$\normalize_\chi$, that is, a map~$T \mapsto \normalize_\chi(T)$ satisfying the following properties:
\begin{enumerate}[(P1)]
\setcounter{enumi}{-1}
\item for any triangulation~$T$, the normalization~$\normalize_\chi(T)$ is a triangulation containing~$\chi$;
\item if~$\chi \in T$, then~$\normalize_\chi(T) = T$;
\item if~$T, T'$ are two adjacent triangulations, then~$\normalize_\chi(T)$ and~$\normalize_\chi(T')$ coincide or are adjacent;
\item if~$T, T'$ are two adjacent triangulations with~$\chi \in T' \ssm T$, then~${\normalize_\chi(T) = \normalize_\chi(T') = T'}$.
\end{enumerate}
\end{proposition}

We prove this proposition type-by-type using the geometric models in types~$A$, $B/C$, and~$D$. We refer to the recent preprint of N.~Williams~\cite{Williams} for a type-free proof.

\para{Type~$A$}
We use the same definition as~\cite[Lemma~3]{SleatorTarjanThurston}. The normalization~$\normalize_\chi$ with respect to a diagonal~$\chi \eqdef \diag{p}{q}$ transforms a triangulation~$T$ to the triangulation~$\normalize_\chi(T)$ obtained by deleting all diagonals of~$T$ crossing~$\chi$ and filling in the resulting empty region~$R_\chi(T)$ by the triangulation where all diagonals are incident to~$p$. \fref{fig:typeANormalization} illustrates this normalization.

\begin{figure}[h]
	\centerline{\includegraphics[scale=.61]{typeANormalization}}
	\caption{Normalization map for type~$A$.}
	\label{fig:typeANormalization}
\end{figure}

Properties~(P0) and~(P1) are clear by construction. For Properties~(P2) and~(P3), consider two adjacent triangulations~$T$ and~$T'$, let~$\delta \in T$ and~$\delta' \in T'$ be such that~$T \ssm \{\delta\} = T' \ssm \{\delta'\}$, and let~$Q$ denote the quadrangle with diagonals~$\delta$ and~$\delta'$. If $\chi$ crosses both~$\delta$ and~$\delta'$, then the quadrangle~$Q$ lies in the retriangulated region~$R_\chi(T) = R_\chi(T')$, so that~$\normalize_\chi(T) = \normalize_\chi(T')$. If~$\chi$ crosses neither~$\delta$ nor~$\delta'$, then the quadrangle~$Q$ is disjoint from the retriangulated region~${R_\chi(T) = R_\chi(T')}$ and~${\normalize_\chi(T) \ssm \{\delta\} = \normalize_\chi(T') \ssm \{\delta'\}}$. If~$\chi$ crosses~$\delta$ but not~$\delta'$, and~$\chi \ne \delta'$, then~$\normalize_\chi(T) = \normalize_\chi(T')$ if~$p$ is an endpoint of~$\delta'$, and~$\normalize_\chi(T) \ssm \{\diag{p}{x}\} = \normalize_\chi(T') \ssm \{\delta'\}$ otherwise, where~$x$ denotes the endpoint of~$\delta$ separated from~$\chi$ by~$\delta'$. Finally, if~$\chi = \delta'$, then~$R_\chi(T) = Q$ while~$R_\chi(T') = \varnothing$, so that~$\normalize_\chi(T) = \normalize_\chi(T') = T'$.

To extend~$\normalize_\chi$ to types~$B/C$ and~$D$, it is convenient to consider the following equivalent description of this normalization: imagine that all diagonals of~$T$ are rubber bands attached to their endpoints and pull the rubber bands crossed by $\chi$ along~$\chi$ towards~$p$ to obtain~$\normalize_\chi(T)$. In other words, each diagonal~$\diag{x}{y}$ of~$T$ crossing~$\chi$ is replaced by~$\diag{x}{p}$ and~$\diag{p}{y}$.

\para{Type~$B/C$}
For type~$B/C$, we distinguish whether or not~$\chi$ is a long diagonal to define the normalization~$\normalize_\chi$:
\begin{itemize}
\item The normalization~$\normalize_\chi$ with respect to a centrally symmetric pair~$\chi \eqdef \{\diag{p}{q}, \diag{\bar p}{\bar q}\}$ of distinct diagonals transforms a centrally symmetric triangulation~$T$ into the centrally symmetric triangulation~$\normalize_\chi(T)$ obtained by deleting all diagonals of~$T$ crossing~$\chi$ and filling the resulting empty region~$R_\chi(T)$ by a centrally symmetric triangulation where all diagonals are incident to the points~$p$ and~$\bar p$ (note that the region~$R_\chi(T)$ need not be connected). To define the triangulation replacing~$T$ inside~$R_\chi(T)$, imagine that all diagonals of~$T$ are rubber bands attached to their endpoints and pull the rubber bands crossed by $\chi$ along~$\chi$ towards~$p$ and~$\bar p$ to obtain~$\normalize_\chi(T)$. In other words, each diagonal~$\diag{x}{y}$ of~$T$ crossing~$\chi$ is replaced by:
\begin{itemize}
\item $\diag{x}{p}$ and~$\diag{p}{y}$ if it only crosses~$\diag{p}{q}$ (and similarly with~$\diag{\bar p}{\bar q}$);
\item $\diag{x}{p}$, $\diag{p}{\bar p}$, and~$\diag{p}{y}$ if it crosses both~$\diag{p}{q}$ and~$\diag{\bar p}{\bar q}$, and~$\diag{p}{q}$ separates~$x$ from the origin while~$\diag{\bar p}{\bar q}$ separates~$y$ from the origin.
\end{itemize}
\item The normalization with respect to a long diagonal~$\chi \eqdef \diag{p}{\bar p}$ of the $2n$-gon transforms a centrally symmetric triangulation~$T$ to the centrally symmetric triangulation~$\normalize_\chi(T)$ obtained by deleting all diagonals of~$T$ crossing~$\chi$ and filling in the resulting empty region~$R_\chi(T)$ by the triangulation where all vertices clockwise between $p$ and~$\bar p$ are connected to~$\bar p$, while all vertices clockwise between $\bar p$ and~$p$ are connected to~$p$.
\end{itemize}
\fref{fig:typeBNormalization} illustrates this normalization, where the three leftmost pictures correspond to the first situation, while the two rightmost correspond to the second situation. As in type~$A$, a straightforward case analysis shows that~$\normalize_\chi$ indeed defines a normalization in both situations.

\begin{figure}[h]
	\centerline{\includegraphics[scale=.61]{typeBNormalization}}
	\caption{Normalization map for type~$B/C$.}
	\label{fig:typeBNormalization}
\end{figure}

\para{Type~$D$}
For type~$D$, we distinguish whether or not~$\chi$ is a pair of central chords to define the normalization~$\normalize_\chi$:
\begin{itemize}
\item The normalization~$\normalize_\chi$ with respect to a centrally symmetric pair~$\chi \eqdef \{\diag{p}{q}, \diag{\bar p}{\bar q}\}$ of diagonals of the $2n$-gon transforms a centrally symmetric pseudotriangulation~$T$ into the centrally symmetric pseudotriangulation~$\normalize_\chi(T)$ obtained by deleting all chords of~$T$ crossing~$\chi$ and filling the resulting empty region~$R_\chi(T)$ by a centrally symmetric pseudotriangulation where all diagonals are incident to the point~$p$ and~$\bar p$ (note that the region~$R_\chi(T)$ needs not be connected). To define the pseudotriangulation replacing~$T$ inside~$R_\chi(T)$, imagine that all chords of~$T$ are rubber bands attached to their endpoints and pull the rubber bands crossed by $\chi$ along~$\chi$ towards~$p$ and~$\bar p$ to obtain~$\normalize_\chi(T)$. In other words, each diagonal~$\diag{x}{y}$ of~$T$ crossing~$\chi$ is replaced by:
\begin{itemize}
\item $\diag{x}{p}$ and~$\diag{p}{y}$ if it only crosses~$\diag{p}{q}$ and~$\bar p \notin \{x,y\}$ (and similarly exchanging~$p$~and~$\bar p$);
\item $\diag{x}{p}$, $\diagD{p}{R}$ and~$\diagD{\bar p}{L}$ if it only crosses~$\diag{p}{q}$, if~$x$ is on the right of the line from~$p$ to~$\bar p$, and if~$y = \bar p$ (and similarly exchanging~$p$~and~$\bar p$, or left and right);
\item $\diag{x}{p}$, $\diagD{p}{R}$, $\diagD{\bar p}{L}$, and~$\diag{\bar p}{y}$ if it crosses both~$\diag{p}{q}$ and~$\diag{\bar p}{\bar q}$, if~$\diag{p}{q}$ separates~$x$ from the origin while~$\diag{\bar p}{\bar q}$ separates~$y$ from the origin, and if the origin is on the left of the line from~$x$ to~$y$ (and similarly exchanging left and right).
\end{itemize}
Similarly, each left central chord~$\diagD{x}{L}$ (resp.~$\diagD{x}{D}$) of~$T$ crossing~$\chi$ is replaced by~$\diag{x}{p}$ and~$\diagD{p}{L}$ (resp.~$\diagD{p}{D}$) if it crosses~$\diag{p}{q}$ (and similarly for~$\diag{\bar p}{\bar q}$).
\item The normalization~$\normalize_\chi$ with respect to a centrally symmetric pair~$\chi$ of central chords transforms a centrally symmetric pseudotriangulation~$T$ into the centrally symmetric pseudotriangulation~$\normalize_\chi(T)$ obtained by deleting all chords of~$T$ crossing~$\chi$ and filling the resulting empty region~$R_\chi(T)$ by the left star~$\starL$ (resp.~right star~$\starR$) on this region if~$\chi$ is a pair of left (resp.~right) central chords.
\end{itemize}
\fref{fig:typeDNormalization} illustrates this normalization, where the three leftmost pictures correspond to the first situation, while the two rightmost correspond to the second situation. The same case analysis as in type~$A$, replacing the quadrangle~$Q$ by the pseudoquadrangle formed by glueing the two pseudotriangles of~$T$ incident to~$\delta$ (or equivalently the two pseudotriangles of~$T'$ incident to~$\delta'$) shows that~$\normalize_\chi$ indeed defines a normalization in both situations.

\begin{figure}[h]
	\centerline{\includegraphics[scale=.61]{typeDNormalization}}
	\caption{Normalization map for type~$D$.}
	\label{fig:typeDNormalization}
\end{figure}

\subsection{Proof of Theorem~\ref{thm:nonLeavingFaceProperty} and Proposition~\ref{prop:enteringFaceProperty}}
\label{subsec:proofs}

Using the normalization introduced in the previous section, we are ready to prove the non-leaving-face property.

\begin{proof}[Proof of Proposition~\ref{prop:enteringFaceProperty}]
Consider two triangulations~$T$ and~$\widetilde T$ and a diagonal~$\chi$ in~$T \ssm \widetilde T$, such that the flip of~$\chi$ in~$T$ produces a diagonal~$\chi'$ that belongs to~$\widetilde T$. Let~$T = T_0, T_1, \dots, T_k = \widetilde T$ be an arbitrary geodesic between~$T$ and~$\widetilde T$. Consider the sequence~$T = T_0, \normalize_{\chi'}(T_0), \normalize_{\chi'}(T_1), \dots, \normalize_{\chi'}(T_k)$. By Property~(P1) above, the last triangulation in this sequence is~$\widetilde T$. By Property~(P3), the first two triangulations are connected by a flip. Since there exists at least one~$i$ such that~${\chi' \in T_{i+1} \ssm T_i}$, Property~(P3) also ensures that~$\normalize_{\chi'}(T_i) = \normalize_{\chi'}(T_{i+1})$. Finally, Property~(P2) asserts that any two consecutive triangulations in the remaining sequence either coincide or are adjacent. Erasing duplicated consecutive triangulations in this sequence gives a normalized path from~$T$ to~$\widetilde T$, which starts by the flip of~$\chi$, and is a geodesic since it is not longer than the geodesic~${T = T_0, T_1, \dots, T_k = \widetilde T}$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:nonLeavingFaceProperty}]
Let~$T$ and~$\widetilde T$ be two triangulations. Consider a path~$\pi$ from~$T$ to~$\widetilde T$ which flips a common chord of~$T$ and~$\widetilde T$. Let~$T_1$ be the first triangulation along~$\pi$ which does not contain~$T \cap \widetilde T$, and let~$T_0$ the previous triangulation along~$\pi$. By Proposition~\ref{prop:enteringFaceProperty}, there exists a geodesic~$\pi'$ from~$T_1$ to~$\widetilde T$ starting with~$T_0$. Combining the subpath of~$\pi$ from~$T$ to~$T_0$ with the subpath of~$\pi'$ from~$T_0$ to~$\widetilde T$ produces a path from~$T$ to~$\widetilde T$ shorter than~$\pi$. It follows that no common chord of~$T$ and~$\widetilde T$ can be flipped along a geodesic between~$T$ and~$\widetilde T$.
\end{proof}

\section{Further examples related to the associahedron}
\label{sec:ctrexms}

To conclude, we survey five relevant generalizations of the flip graph on triangulations of a convex polygon. The diameter of these flip graphs is not precisely determined but we present some known asymptotic bounds. Interestingly, these five families contain specific examples that do not always satisfy the non-leaving-face property.

\subsection{Pseudotriangulation polytope}
\label{subsec:ctrexmPseudotriangulations}

A (pointed) \defn{pseudotriangulation} of a point set~$P$ in general position in the plane is a maximal set of edges of~$P$ which is crossing-free and pointed (any vertex is adjacent to an angle wider than~$\pi$). Flips between pseudotriangulations are defined as in item~(\ref{item:pseudoflip}) in Section~\ref{sec:Dmodel}.
We refer to~\cite{RoteSantosStreinu-survey} for a survey on pseudotriangulations and their properties. Using rigidity properties of pseudotriangulations and the expansive motion polyhedron, G.~Rote, F.~Santos and I.~Streinu showed in~\cite{RoteSantosStreinu-pseudotriangulationPolytope} that the flip graph on pseudotriangulations of~$P$ can be realized as the graph of the \defn{pseudotriangulation polytope}. This polytope is a realization of the type~$A$ associahedron when~$P$ is in convex position.

The diameter of the pseudotriangulation polytope of~$P$ is known to be bounded between~$|P|$ and~$|P| \cdot \log(|P|)$, see~\cite{Bereg} and~\cite{RoteSantosStreinu-survey}. These are the best current bounds to our knowledge.

O.~Aichholzer~\cite{Aichholzer} observed that not all pseudotriangulation polytopes satisfy the non-leaving-face property. His example is represented in \fref{fig:ctrexmPseudotriangulations}. The point set~$P$ is formed by a small downward triangle~$\triangledown$ together with a big upward triangle whose vertices are replaced by convex chains with~$m = 6$ points. \fref{fig:ctrexmPseudotriangulations} shows a path of~$3m+4 = 22$ flips from the top left pseudotriangulation~$T$ to the bottom left pseudotriangulation~$\widetilde T$, flipping common edges of~$T$ and~$\widetilde T$. In contrast, any path from~$T$ to~$\widetilde T$ which preserves their common edges has length at least~$4m-1 = 23$. Indeed, if the edges of~$T \cap \widetilde T$ are preserved, no flip produces an edge of~$\widetilde T$ before all but one edge incident to one vertex of the small downward triangle~$\triangledown$ have been flipped. We thus need at least~$m-1$ flips before a flip can create edges of~$\widetilde T \ssm T$, and then at least $3m$ flips to create them all.

\begin{figure}[h]
	\centerline{\includegraphics[width=1\textwidth]{ctrexmPseudotriangulations}}
	\caption{A geodesic (of length~$3m+4 = 22$) between two pseudotriangulations that flips common edges between them.}
	\label{fig:ctrexmPseudotriangulations}
\end{figure}

\subsection{Multiassociahedron}
\label{subsec:ctrexmMultitriangulations}

A \defn{$k$-triangulation} of a convex $m$-gon is a maximal set of diagonals not containing a $(k+1)$-crossing, \ie a set of $k+1$ pairwise crossing diagonals. In a $k$-triangulation, every $k$-relevant diagonal (\ie with at least~$k$ vertices of the $m$-gon on each side) can be flipped to obtain a new $k$-triangulation. We refer to~\cite{PilaudSantos-multitriangulations} for a local description of this operation. The question whether the flip graph can be realized as the graph of a convex polytope remains open, except for very particular cases including the classical $n$-dimensional associahedron when~$k=1$ and~$m = n+3$. We can however study the diameter of the flip graph and the properties of its geodesics.

The best known bounds for the diameter~$\delta(m,k)$ of the flip graph on $k$-triangulations of the $m$-gon are given by
\[
\big( k+\frac{1}{2} \big) \cdot m - (k+1)^2 \; \le \; \delta(m,k) \; \le \; 2k \cdot m - 2k(4k+1).
\]
The upper bound, due to T.~Nakamigawa~\cite{Nakamigawa}, holds for all~$m \ge 4k^2(2k+1)$. Observe that it is tight when~$k=1$ by the result of~\cite{SleatorTarjanThurston, Pournin} on the associahedron. The lower bound, proved in~\cite[Lemma~2.39]{Pilaud-these}, holds for all~$m \ge 4k+2$. We refer to~\cite[Section~2.3.2]{Pilaud-these} for a summary of known properties on the diameter of the multiassociahedron.

We now show that the multiassociahedron does not satisfy the non-leaving-face property, \ie that not all $k$-triangulations along a geodesic between two $k$-triangulations always contain their common diagonals for large enough values of~$k$ and~$m$. We can argue using the universality property of multitriangulations~\cite[Proposition~5.6]{PilaudSantos-brickPolytope}. This property ensures in particular that the flip graph on pseudotriangulations of any planar point set in general position can be embedded as a subgraph induced by all $k$-triangulations containing a certain subset of diagonals in the flip graph on $k$-triangulations of an $m$-gon for large enough~$k$ and~$m$. The path of \fref{fig:ctrexmPseudotriangulations} thus results in a path in the flip graph on $k$-triangulations of the $m$-gon which contradicts the non-leaving-face property.

In fact, computer experiments with the software Sage~\cite{sage} provided us with a much smaller example illustrated on \fref{fig:ctrexmMultitriangulations}. This figure shows a path of~$4$ flips between the leftmost $2$-triangulation~$T$ and the rightmost $2$-triangulation~$\widetilde T$ of the octagon, such that a common diagonal is flipped along the sequence. In each $2$-triangulation, the blue dashed edge is inserted by the previous flip while the red bold edge is deleted by the next flip. Alternatively, it might help the reader to visualize these flips on the pseudoline arrangements represented below (see~\cite[Section~3.3]{PilaudPocchiola}). To see that the path represented in this figure is a geodesic, observe that~$T \ssm \widetilde T$ contains $3$ edges whose flip in~$T$ all produce an edge not in~$\widetilde T$.

\begin{figure}[h]
	\centerline{\includegraphics[width=1\textwidth]{ctrexmMultitriangulations}}\bigskip
	\centerline{
		\begin{overpic}[width=.19\textwidth]{sortingNetwork1}
			\put(0,12){\footnotesize $14$}
			\put(22,12){\footnotesize $25$}
			\put(42,12){\footnotesize $36$}
			\put(65,12){\footnotesize $47$}
			\put(79,12){\footnotesize $58$}
			\put(7,36){\footnotesize $15$}
			\put(27,36){\footnotesize $26$}
			\put(49,36){\footnotesize $37$}
			\put(73,36){\footnotesize $48$}
			\put(14,60){\footnotesize $16$}
			\put(34,60){\footnotesize $27$}
			\put(57,60){\footnotesize $38$}
		\end{overpic}
		\multido{\n=2+1}{4}{\;\;\includegraphics[width=.19\textwidth]{sortingNetwork\n}}
	}
	\caption{A geodesic between two $2$-triangulations of the octagon that flips a common edge between them.}
	\label{fig:ctrexmMultitriangulations}
\end{figure}

\subsection{Graph associahedron}
\label{subsec:ctrexmGraphAssociahedron}

Fix a finite connected graph~$G$. A \defn{nested set} on~$G$ is a set of \defn{tubes} (proper connected induced subgraphs) of~$G$ which are pairwise nested, or disjoint and non-adjacent in~$G$. The simplicial complex of all nested sets on~$G$ is called \defn{nested complex} and has been realized as the boundary complex of the \defn{$G$-associahedron}~\cite{CarrDevadoss}. Two maximal nested sets are connected by a \defn{flip} if one can be obtained from the other by replacing a tube with the unique other tube that produces a new nested set. Specific families of graph-associahedra provide relevant families of polytopes: path associahedra are classical type~$A$ associahedra, cycle associahedra are cyclohedra (or type~$B/C$ associahedra), star associahedra are stellohedra, and complete graph associahedra are type~$A$ permutahedra.

Graph properties of graph associahedra are studied by T.~Manneville and V.~Pilaud in~\cite{MannevillePilaud}. They show that the diameter~$\delta(G)$ of the $G$-associahedron is a non-decreasing function of the graph~$G$, meaning that~$\delta(G) \le \delta(G')$ if~$G$ is a subgraph of~$G'$. Combining this non-decreasing property with the diameter of the permutahedron on the one hand, and the analysis of the diameter~$\delta(T)$ for trees on the other hand (based on~\cite{Pournin}), they obtain that the diameter~$\delta(G)$ is bounded by
\[
\max(2n - 20, m) \; \le \; \delta(G) \; \le \; \binom{n}{2},
\]
where~$n$ and~$m$ denote the number of vertices and edges of~$G$.

Concerning the non-leaving-face property, they observed the following facts:
\begin{enumerate}[(i)]
\item Not all graph associahedra satisfy the non-leaving-face property. \fref{fig:ctrexmGraphAssociahedron} reproduces their example. It shows a path of length~$2n$ between two maximal nested sets~$N, \widetilde N$ on the star with~$n$ branches. In contrast, the minimal face containing~$N$ and~$\widetilde N$ is an $n$-dimensional permutahedron and the graph distance between~$N$ and~$\widetilde N$ in this face is~$\binom{n}{2}$. Therefore, the corresponding graph associahedron (stellohedron in this case) does not satisfy the non-leaving-face property when~$n \ge 5$.

\begin{figure}[h]
	\centerline{\includegraphics[width=1\textwidth]{ctrexmGraphAssociahedron}}
	\caption{A geodesic (of length~$2n$) between two maximal nested sets of the star that flips a common nested set.}
	\label{fig:ctrexmGraphAssociahedron}
\end{figure}

\item Any geodesic between two maximal nested sets~$N, \widetilde N$ on~$G$ remains in the face of the \mbox{$G$-asso}\-ciahedron corresponding to all common tubes of~$N$ and~$\widetilde N$ which are not contained in tubes of~$N \ssm \widetilde N$.
\end{enumerate}

\subsection{Secondary polytopes}
\label{subsec:ctrexmSecondaryPolytope}

The \defn{secondary polytope} of a point set~$P \subset \R^d$ is a polytope whose face lattice is isomorphic to the refinement poset of \defn{regular subdivisions} of~$P$, \ie polyhedral subdivisions of~$P$ which can be obtained as the vertical projection of the lower convex hull of the points of~$P$ lifted by an arbitrary height function. In particular, the graph of the secondary polytope of~$P$ has one vertex for each regular triangulation of~$P$ and one edge for each regular flip. See~\cite{LoeraRambauSantos} for a detailed presentation of this polytope. For example, the classical associahedron is the secondary polytope of a convex point set in the plane. The secondary polytope of a \mbox{$d$-dimen}\-sional configuration of~$n$ points has dimension~$n-d-1$, and it is known that its diameter cannot exceed
\[
\min\left( (d+2)\binom{n}{\left\lfloor \frac{d}{2} + 1 \right\rfloor}, \binom{n}{d+2} \right),
\]
see~\cite[Corollary~5.3.11]{LoeraRambauSantos}.

As observed by F.~Santos~\cite{Santos-Oberwolfach}, the secondary polytope of two dilated copies of the standard $(n-1)$-dimensional simplex is combinatorially equivalent to the graph associahedron of the star with $n$ leaves (stellohedron) discussed in Section~\ref{subsec:ctrexmGraphAssociahedron}. For example, \fref{fig:stellohedra} illustrates the correspondence between the secondary polytope of the ``mother of all examples''~\cite[Example~2.2.5]{LoeraRambauSantos} and the graph associahedron of the tripod. As illustrated in \fref{fig:ctrexmGraphAssociahedron}, the stellohedron of dimension~$n \ge 5$ does not satisfies the non-leaving-face property. Therefore, not all secondary polytopes satisfy the non-leaving-face property.

\begin{figure}
	\centerline{\includegraphics[width=\textwidth]{stellohedra}}
	\caption{The secondary polytope of two dilated copies of the standard simplex (left) is combinatorially equivalent to the stellohedron (right).}
	\label{fig:stellohedra}
\end{figure}

\subsection{Flip graph on all triangulations}
\label{subsec:ctrexmAllTriangulations}

Our last example is the flip graph on all triangulations (regular or not) of the point set $P$. This graph is not always connected~\cite{Santos}, but it is connected for point sets in the plane, in which case the diameter is at most~$4n$~\cite[Corollary~3.4.4]{LoeraRambauSantos}. This bound assumes that flips that insert or delete a vertex are allowed. Otherwise, the diameter can be become quadratic as illustrated by the ``double chain" example in~\cite[Example~3.4.5]{LoeraRambauSantos} reproduced in \fref{fig:ctrexmTriangulations}. This example also shows that geodesics between two triangulations in the flip graph delete and reinsert common edges between them.

\begin{figure}[h]
	\centerline{\includegraphics[width=.75\textwidth]{ctrexmTriangulations}}
	\caption{Two triangulations of the double chain.}
	\label{fig:ctrexmTriangulations}
\end{figure}

\section*{Acknowledgments}

We are grateful to Oswin Aichholzer, to Thibault Manneville, and to Francisco Santos for letting us present the examples of Section~\ref{sec:ctrexms} and for interesting discussions related to them. We also thank Nantel Bergeron and Thibault Manneville for useful comments and suggestions on a preliminary draft. We thank Thomas Brustle for pointing out the work of Yannick Lebrun~\cite{Lebrun} to our attention. Finally, we are indebted to two anonymous referees for their careful reading and patient comments and suggestions which significantly improved the presentation and accuracy of the paper.

\bibliographystyle{alpha}
\bibliography{CeballosPilaud_diameterTypeDAssociahedron}
\label{sec:biblio}

\begin{landscape}
\pagestyle{empty}

\begin{figure}[p]
	\vspace*{-2.5cm}
	\centerline{\includegraphics[width=1.45\textwidth]{typeD4associahedron}}
	\caption{The type~$D_4$ flip graph. We have represented some of the corresponding centrally symmetric pseudotriangulations of~$\configD_4$ on this picture, while the others can be found on \fref{fig:42pseudotriangulationsHorizontal}. In each pseudotriangulation, the number at the center of the disk is its label in the flip graph, and each pair of chords is labeled with the pseudotriangulation obtained when flipping it. The underlying graph used for the representation is a Schlegel diagram of the type~$D_4$ associahedron~\cite{ChapotonFominZelevinsky, HohlwegLangeThomas, PilaudStump-brickPolytope}.}
	\label{fig:typeD4associahedron}
\end{figure}

\begin{figure}[p]
	\vspace*{-2.5cm}
	\centerline{\includegraphics[width=1.45\textwidth]{42pseudotriangulationsHorizontal}}
	\caption{The remaining~$42$ centrally symmetric pseudotriangulations of the configuration~$\configD_4$. See \fref{fig:typeD4associahedron} for the other~$8$ centrally symmetric pseudotriangulations, the flip graph and the explanation of the labeling conventions.}
	\label{fig:42pseudotriangulationsHorizontal}
\end{figure}

\end{landscape}

\end{document}

config: arxiv


TITLE: Exponential continuous growth $\ln a$ vs. $r$? Huh?
QUESTION [2 upvotes]: So, given a simple population continuous growth problem, it seems that the entirety of the internet uses $P=P_0e^{rt}$ where $P$ is the population over time, $P_0$ is the initial population, $r$ is the percentage of change, and $t$ is time.
But this class is asserting that $P=P_0e^{(\ln a)(t)}$  where $a = 1+r$, and everything else stays the same.
So lets say a population starts at $10,000$ with $10%$ continuous growth rate.  What is the population in $10$ years?
The internet says that $P=10,000e^{(.10)(10)}=27,182$
But the class says that $P=10,000e^{(\ln1.10)10} = 25,937$  ($a = 1 + r$ which is $1.10$)
but that equals the usual constant growth of $P=P_0{a^t} = 25937$
What the heck?  What am I missing?

REPLY [1 votes]: Let us start from what everybody agrees on. The population $P(t)$ at time $t$ is given by
$$P(t)=P(0)e^{\lambda t},\tag{1}$$
where $\lambda$ is a constant.
Suppose that the population increases by $10\%$ in one year. Then putting $t=1$ in Equation (1), and using $P(1)=1.1P(0)$, we obtain
$$1.1P(0)=P(0)e^{\lambda}.$$
From this we obtain that $1.1=e^{\lambda}$. Taking natural logarithms, we find that $\lambda=\ln(1.1)$. Thus
$$P(t)=P(0)e^{(\ln(1.1))(t)}.$$


text:
\begin{document}

\title{Shannon Meets Carnot:\\Mutual Information Via Thermodynamics}

\author{Ori~Shental\thanks{O. Shental is with the Center for Magnetic Recording Research (CMRR), University of California, San Diego (UCSD), 9500 Gilman Drive, La Jolla, CA 92093, USA (e-mail: oshental@ucsd.edu).} and
        Ido~Kanter\thanks{I. Kanter is with the Minerva Center and Department of Physics, Bar-Ilan University, Ramat-Gan 52900, Israel (e-mail: kanter@mail.biu.ac.il).}
}

\maketitle

\date{}

\maketitle

\begin{abstract} In this contribution, the Gaussian channel is represented as an equivalent thermal system allowing to express its input-output mutual information in terms of thermodynamic quantities. This thermodynamic description of the mutual information is based upon a generalization of the $2^{nd}$ thermodynamic law and provides an alternative proof to the Guo-Shamai-Verd\'{u} theorem, giving an intriguing connection between this remarkable theorem and the most fundamental laws of nature - the laws of thermodynamics.
\end{abstract}

\textbf{Index Terms:} Thermodynamics, mutual information, Gaussian channel, Guo-Shamai-Verd\'{u} theorem, minimum mean-square error.
\newline

\renewcommand{\thefootnote}{\arabic{footnote}}
\setcounter{footnote}{0}

\section{Introduction}

The laws of thermodynamics describe the transport of heat and work in macroscopic (\ie, large scale) processes and play a fundamental role in the physical sciences. The theory of thermodynamics is primarily an intellectual achievement of the $19^{th}$ century. The first analysis of heat engines was given by the French engineer Sadi Carnot in his seminal 1824 publication (`\textit{Reflections on the Motive Power of Fire and on Machines Fitted to Develop that Power}'~\cite{BibDB:Carnot,BibDB:Carnot2}), laying the foundations to the $2^{nd}$ law of thermodynamics. This paper marks the start of thermodynamics as a modern science~\cite{BibDB:HistoryOfThermo}.

The classical theory of thermodynamics was formulated in consistent form by giants like Joule, Clausius, Lord Kelvin, Gibbs and others. The atomic, or microscopic (\ie, small scale) approach to statistical thermodynamics was mainly developed through the pioneering work of Clausius, Maxwell, Boltzmann and Gibbs, laying the foundations to the more general discipline of statistical mechanics~\cite{BibDB:StatPhys}.

In particular, the $2^{nd}$  thermodynamic law, for quasi-static processes, linearly relates the change in the entropy, $dS$, to the amount of heat, $\dbar Q$, absorbed to a system at equilibrium, $\dbar Q=TdS$, where $T$ is the temperature of the system. However, the $2^{nd}$ law, in its classical formulation, is suited only for systems with energy Hamiltonian (function), $\mathcal{E}$, which is \emph{not} an explicit function of the temperature and fails to capture the physical behavior of systems with temperature-dependent energy levels. While such temperature-dependent energy function is uncommon in the study of natural and artificial systems in physics, it surprisingly does arise in modeling communication channels, like the popular Gaussian-noise communication channel~\cite{BibDB:BookCover,BibDB:BookProakis,BibDB:BookGallager2008}, as a (quasi-static) thermal system~\cite{BibDB:Sourlas,BibDB:Rujan,BibDB:BookNishimori}.

In this contribution, we generalize the $2^{nd}$ thermodynamic law to encompass systems with temperature-dependent Hamiltonian and obtain the generalized law \mbox{$\dbar Q=TdS+<d\mathcal{E}/dT>dT$}, where $<\cdot>$ denotes averaging over the standard Boltzmann distribution. Consequently, it allows for an alternative physical description to the Shannon-theoretic notions of information entropy and mutual information~\cite{BibDB:Shannon} via the thermodynamic  quantities of energy and temperature. As an example, the correct expressions for the mutual information of a Gaussian channel with Bernoulli-1/2 input and Gaussian input are computed from the thermodynamic representation, where the latter corresponds to the Shannon capacity.

Guo, Shamai and Verd\'{u}~\cite{BibDB:GSV} have recently revealed a simple, yet powerful relationship
(hereinafter termed GSV theorem) between information and
estimation theories. This cross-theory theorem bridges over the notions of
Shannon's mutual information and minimum mean-squre error (MMSE)
for the common additive white Gaussian noise channel.
Based on the thermodynamic expression of mutual information, the GSV theorem is naturally re-derived. This directly links the GSV theorem to the most profound laws of nature and gives the physical origin to this remarkable formula.

The paper is organized as follows. The thermodynamic background is discussed in Sections~\ref{sec_classical} and~\ref{sec_statistical}. In Section~\ref{sec_Gaussian} the Gaussian channel is represented through an equivalent thermal system giving a thermodynamic expression to the notions of information entropy and mutual information. In Section~\ref{sec_GSV} the GSV theorem is proven via thermodynamics. We conclude the paper in Section~\ref{sec_conclusion}.

We shall use the following notations. $P(\cdot)$ is used to
denote either a probability mass function (pmf), $\Pr(\cdot)$, or a
probability density function (pdf), $p(\cdot)$, depending on the random
variable having either discrete or continuous support, respectively.
Random variables are denoted by upper case letters and their
values denoted by lower case letters. The symbol $\mathbb{E}_{X}\{\cdot\}$ denotes expectation of the random object within the brackets with respect
to the subscript random variable. The natural logarithm, $\log$, is used.
The support of a variable $X$ is denoted by $\mathcal{X}$.

\section{Classical Thermodynamics}\label{sec_classical}
In this section we concisely summarize the fundamental results of classical
thermodynamics, essential to our discussion. The interested reader is
strongly encouraged to find a thorough introduction to thermodynamics in one
of numerous textbooks (\eg,~\cite{BibDB:Thermo}).

A thermodynamic system is defined as the part of the universe under
consideration, separated from the rest of the universe, referred to as
environment, surroundings or reservoir, by real or imaginary boundary. A
non-isolated thermodynamic system can exchange energy in the form of heat or
work with any other system. Heat is a process by which energy is added to a
system from a high-temperature source, or lost to a low-temperature sink. Work refers to forms of energy
transfer which can be accounted for in terms of changes in the macroscopic physical variables of the system (\eg, volume or pressure). For example, energy
which goes into expanding the volume of a system against an external
pressure, by driving a piston-head out of a cylinder against an external
force. Hereinafter we consider a thermal system which does not perform work,
mechanical or other. This thermal system is assumed to be in equilibrium,
that is all the descriptive macroscopic parameters of the system are
time-independent. We also assume that the process of exchanging heat is
infinitesimally quasi-static, \ie, it is carried out slowly enough that the
system remains arbitrarily close to equilibrium at all stages of the
process.

The underlying laws of thermodynamics consist of purely macroscopic
statements which make no reference to the microscopic properties of the system, \ie, to the molecules or particles of which they
consist. In the following statements we present the thermodynamic laws in a
form relevant to the thermal system under consideration.\footnote{For
conciseness the $0^{th}$ law's statement is omitted.}

\begin{LOT}
\begin{first}
   (conservation of energy) A system in equilibrium can be characterized by
a quantity $U$, called the `internal energy'. If the system is not isolated,
interact with another system and no work is done by it, the resulting change
in the internal energy can be written in the form
      \BE
      dU=\dbar Q,
      \EE where $\dbar Q$ is the amount of heat absorbed by the
system.\footnote{The  infinitesimal heat is denoted by $\dbar$ rather than
$d$ because, in mathematical terms, it is not an exact differential. The
integral of an inexact differential depends upon the particular path taken
through the space of (thermodynamic) parameters while the integral of an
exact differential depends only upon the initial and final states.
}
\end{first}
\begin{second} (definition of temperature) A system in equilibrium can be
characterized by a quantity $S$, called the `thermodynamic entropy'. If the
system is not isolated and undergoes a quasi-static infinitesimal process in
which it absorbs heat $\dbar Q$, then \BE\label{eq_second_law} dS=\frac{\dbar Q}{T},\EE where $T$
is a quantity characteristic of the system and is called the `absolute
temperature' of the system.
\end{second}
\begin{third} (zero entropy) The thermodynamic entropy $S$ of a system has a
limiting property that
      \BE
        \textrm{as } T\rightarrow 0_{+},\quad S\rightarrow S_{0}
      ,\EE where $S_{0}$ is a constant (usually $0$ in case of non-degenerate ground state energy) independent of all
parameters of the particular system.
\end{third}
\end{LOT}

Incorporating the three laws of thermodynamics together, a combined law describing the
thermodynamic entropy as an integration function over the temperature is obtained
\BE\label{eq_S}
S(T)=\int_{0}^{T}\frac{1}{\gamma}dU(\gamma)=\int_{0}^{T}\frac{1}{\gamma}\fd{U(\gamma)}{\gamma}d\gamma=\int_{0}^{T}\frac{C_{V}(\gamma)}{\gamma}d\gamma,
\EE where \BE C_{V}(T)\triangleq\frac{dU(T)}{dT} \EE is known as the heat
capacity (at constant volume $V$). The heat capacity is a non-negative
temperature-dependent measurable quantity describing the amount of heat
required to change the system's temperature by an infinitesimal degree.

Let us now define the inverse temperature
\mbox{$\beta\triangleq(k_{B}T)^{-1}$}, where the constant $k_{B}$ is the
Boltzmann constant. In this contribution we arbitrarily set $k_{B}=1$, thus
\mbox{$\beta=1/T$}. Hence, the entropy integral~(\ref{eq_S}) can be
rewritten in terms of the inverse temperature as \BE\label{eq_S_beta}
S(\beta)=-\int_{\beta}^{\infty}\gamma C_{V}(\gamma)d\gamma,
\EE where \BE C_{V}(\beta)\triangleq\frac{dU(\beta)}{d\beta}=-T^{2}C_{V}(T).
\EE

\section{Statistical Thermodynamics}\label{sec_statistical}
Moving to the microscopic perspective of statistical
thermodynamics~\cite{BibDB:Thermo,BibDB:Huang}, the probability, $P(X=x)$, of finding
the system in any one particular microstate, $X=x$, of
energy level $\mathcal{E}(X=x)$ is dictated according to the canonical Boltzmann
distribution~\cite{BibDB:StatPhys} \BE\label{eq_Boltzmann}
    P(X=x)=\frac{1}{\mathcal{Z}}\exp{\big(-\beta \mathcal{E}(X=x)\big)},
\EE where \BE
\mathcal{Z}\triangleq{\sum_{x\in\mathcal{X}}\exp{\big(-\beta
    \mathcal{E}(X=x)\big)}}
\EE is the partition (normalization) function, and the sum extends over all possible microstates of the system.

Applying the Boltzmann distribution, the macroscopic quantities of internal energy and entropy can be described microscopically as the average energy and the average $\{-\log P(X)\}$, respectively. Explicitly,
\BEA
U&=&\mathbb{E}_{X}\{\mathcal{E}(X)\}\label{eq_U},\\
S&=&\mathbb{E}_{X}\{-\log P(X)\},
\EEA and it can be easily verified that the following relation holds
\BE\label{eq_identity}
\log\mathcal{Z}=-\beta U+S.
\EE

\section{The Gaussian Channel As A Thermal System}\label{sec_Gaussian}
Consider a real-valued channel with input and output random variables $X$
and
$Y$, respectively, of the form \BE\label{eq_channel}
    Y=X+N,
\EE where \mbox{$N\sim\mathcal{N}(0,1/\snr)$} is a Gaussian noise
independent
of $X$, and $\snr\geq0$ is the channel's signal-to-noise ratio (SNR). The
input is taken from a probability distribution $P(X)$ that satisfies
$\mathbb{E}_{X}\{X^{2}\}<\infty$.\footnote{Similarly to the formulation in~\cite{BibDB:GSV} for $\mathbb{E}_{X}\{X^{2}\}=1$, $\snr$ follows
the usual notion of SNR. For $\mathbb{E}_{X}\{X^{2}\}\neq1$, $\snr$ can be
regarded as the gain in the output SNR due to the
channel.}

The Gaussian channel~(\ref{eq_channel}) (and any other communication channel) can be also viewed as a physical
system, operating under
the laws of thermodynamics. The microstates of the thermal system are
equivalent to the hidden values of the channel's input $X$. A comparison of
the channel's a-posteriori probability
distribution, given by \BEA
P{(X=x|Y=y)}&=&\frac{P(X=x)p(Y=y|X=x)}{p(Y=y)}\\&=&\frac{\sqrt{\snr}P(X=x)}{\sqrt{2\pi}p(Y=y)}\exp{\Big(-\frac{\snr}{2
}(y-x)^{2}\Big)}\\&=&\frac{\exp{\big(-\snr(-xy+\frac{x^{2}}{2}-\frac{\log
P(X=x)}{\snr})\big)}}{\sum_{x\in\mathcal{X}}\exp{\big(-\snr(-xy+\frac{x^{2}}{2}-\frac{\log
P(X=x)}{\snr})\big)}}\label{eq_denom},
\EEA with the Boltzmann distribution law~(\ref{eq_Boltzmann}) yields the
following
mapping of the inverse temperature and energy of the equivalent thermal
system \BEA\label{eq_snr_map}
    \snr&\rightarrow&\beta,\\
    -xy+\frac{x^{2}}{2}-\frac{\log P(X=x)}{\beta}&\rightarrow&
\mathcal{E}(X=x|Y=y;\beta).\label{eq_energy_map}
\EEA

Note that the temperature (\ie, the noise variance according to the
mapping~(\ref{eq_snr_map})) can be increased gradually from the absolute zero to its
target value $T=1/\beta$ in infinitesimally small steps, thus the
Gaussian channel system can remain arbitrarily close to equilibrium at all
stages of this process. Hence, the equivalent thermal system exhibits a
quasi-static infinitesimal process. Interestingly, the notion of
quasi-statics is reminiscent to the concept of Gaussian pipe in the SNR-incremental
Gaussian channel approach taken by Guo~\etal~\cite[Section \mbox{II-C}]{BibDB:GSV}.
Thus, we can apply the entropy integral~(\ref{eq_S_beta}) obtained from thermodynamics to the thermal system being equivalent to the Gaussian channel, yielding \BEA\label{eq_S_final}
S(\beta)=S(X|Y=y;\beta)=-\int_{\beta}^{\infty}\gamma
C_{V}(\gamma)d\gamma
=-\int_{\beta}^{\infty}\gamma\frac{dU(Y=y;\gamma)}{d\gamma}d\gamma,
\EEA where following~(\ref{eq_U}) the internal energy, $U(Y=y;\beta)=\mathbb{E}_{X|Y}\{\mathcal{E}(X|Y=y)\}$,
is the energy averaged over all possible values of $X$, given $y$.

The posterior information (Shannon) entropy, $H(X|Y;\beta)$, (in nats) of the channel
can be expressed via the thermodynamic entropy conditioned on $Y=y$, $S(X|Y=y;\beta)$~(\ref{eq_S_final}), as
\BEA\label{eq_S_XgivenY}
H(X|Y;\beta)=\mathbb{E}_{Y}\{S(X|Y=y;\beta)\}=-\mathbb{E}_{Y}\Bigg\{\int_{\beta}^{\infty}\gamma\frac{dU(Y;\gamma)}{d\gamma}d\gamma\Bigg\}. \EEA
The input's entropy can also be reformulated in a similar manner, since $H(X)=H(X|Y;\beta=0$). Hence,
\BEA
H(X)&=&-\mathbb{E}_{Y}\Bigg\{\int_{0}^{\infty}\gamma\frac{dU(Y;\gamma)}{d\gamma}d\gamma\Bigg\}.
\EEA

Now, the input-output mutual information can be described via thermodynamic
quantities, namely the energy, $\mathcal{E}$, and inverse temperature, $\beta$, as \BEA\label{eq_I}
I(X;Y)&=&I(\beta)\triangleq H(X)-H(X|Y;\beta)\\&=&-\mathbb{E}_{Y}\Bigg\{\int_{0}^{\beta}\gamma\frac{dU(Y;\gamma)}{d\gamma}d\gamma\Bigg\}\\
&=&-\big[\gamma\mathbb{E}_{Y}\{U(Y;\gamma)\}\big]_{0}^{\beta}+\mathbb{E}_{Y}\Bigg\{\int_{0}^{\beta}U(Y;\gamma)d\gamma\Bigg\}\label{eq_rhs}, \label{eq_MI_integral}\EEA
where~(\ref{eq_rhs}) is obtained using integration by parts.

Note that this thermodynamic interpretation to the mutual information holds
not only for the Gaussian channel, but also for any channel which can be
described by a thermal system exhibiting quasi-static heat transfer. In the following we illustrate the
utilization of~(\ref{eq_rhs}) by re-deriving the correct expression for the mutual information of a
Gaussian channel with Bernoulli-1/2 input.\\\,

\textbf{\emph{Example: Gaussian Channel with Bernoulli-$1/2$ Input}}

Since the input $X$ in this case is binary and equiprobable, \ie\, $P(X=1)=P(X=-1)=1/2$, the $X^{2}/2=1/2$ and $\log P(X=x)/\beta$ terms of the
Gaussian channel's energy~(\ref{eq_energy_map}) are independent of $X$ and can be dropped\footnote{Cancelled out by the same terms from the denominator in~(\ref{eq_denom}).}, leaving us
with the expression, independent of $\beta$,
\BE
\mathcal{E}(X=x|Y=y)=-xy.
\EE The a-posteriori probability mass function gets the form \BE
\Pr(X=x|Y=y)=\frac{\exp{(x\beta y)}}{\exp{(\beta y)}+\exp{(-\beta y)}},\quad
x\in\pm1.
\EE Hence, the internal energy is \BE
U(Y=y;\beta)=\mathbb{E}_{X|Y}\{\mathcal{E}(X|Y=y)\}=-y\tanh(\beta y). \EE The marginal pdf
of the output is then given by \BE
p(Y=y)=\frac{\sqrt{\beta}}{2\sqrt{2\pi}}\Bigg(\exp{\Big(-\frac{\beta}{2}(y-1)^{2}\Big)}+\exp{\Big(-\frac{\beta}{2}(y+1)^{2}\Big)}\Bigg).
\EE Thus, \BEA
-\beta\mathbb{E}_{Y}\{U(Y;\beta)\}&=&-\int_{-\infty}^{\infty}y\tanh
(\beta y)p(Y=y)dy\\&=&-\frac{\beta}{2\sqrt{2\pi}}\int_{-\infty}^{\infty}y\Bigg(
\exp{\Big(-\frac{\beta}{2}(y-1)^{2}\Big)}-\exp{\Big(-\frac{\beta}{2}(y+1)^{2}\Big)}\Bigg)dy\\&=&\frac{\beta}{2}(1-(-1))=\beta
\EEA and \BEA
\mathbb{E}_{Y}\Bigg\{\int_{0}^{\beta}U(Y;\gamma)d\gamma\Bigg\}&=&\int_{-\infty}^{\infty}p(Y=
y)\int_{0}^{\beta}U(Y=y;\gamma)d\gamma
dy\\&=&-\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\exp{\bigg(-\frac{y^{2
}}{2}\bigg)}\log\cosh{(\beta-\sqrt{\beta}y)}dy
\EEA giving, based on~(\ref{eq_rhs}), \BE
I(\beta)=\beta-\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\exp{\bigg(-\frac{y^{2
}}{2}\bigg)}\log\cosh{(\beta-\sqrt{\beta}y)}dy,
\EE which is identical to the known Shannon-theoretic result (see, \eg,~\cite[eq.
(18)]{BibDB:GSV} and~\cite[p. 274]{BibDB:BookBlahut}). \qed

\subsection{Generalized $2^{nd}$ Law}
When trying to repeat this exercise for a Gaussian input one finds
that~(\ref{eq_MI_integral}) fails to reproduce $I(\snr)=1/2\log(1+\snr)$,
which is the celebrated formula for the Shannon capacity of the Gaussian channel. This observation
can be explained as follows. The $2^{nd}$ thermodynamic law, as stated
above, holds only for systems with an energy function, $\mathcal{E}$, which is \emph{not} a
function of the temperature. While the temperature-independence of $\mathcal{E}$ is a
well-known conception in the investigation of both natural and artificial systems in
thermodynamics, and physics at large, such independence does not necessarily hold for communication channels and particularly for the Gaussian channel.
Actually, one can easily observe that the Gaussian channel's
energy~(\ref{eq_energy_map}) is indeed an explicit function of the
temperature via the $\log P(X=x)/\beta$ term, unless this term can be dropped by absorbing it into the partition function, as happens for equiprobable input distributions, like the discrete Bernoulli-1/2
or the continuous uniform distributions. This is exactly the reason why~(\ref{eq_MI_integral})
does succeed to compute correctly the mutual information for the particular case of a Bernoulli-$1/2$ input source.

In order to capture the temperature-dependent nature of the energy in systems like the communication channel, we generalize the formulation of the $2^{nd}$ law of
thermodynamics $dS=\dbar Q/T$.
\begin{second_G} (redefinition of temperature) If the thermal system is not isolated and undergoes a
quasi-static infinitesimal process in which it absorbs heat $\dbar Q$, then
\BE\label{eq_G_second_law} dS=\frac{\dbar Q}{T}-\frac{1}{T}\mathbb{E}_{X}\bigg\{\fd{\mathcal{E}(X)}{T}\bigg\}dT.\EE
\end{second_G}
\begin{proof}
The differential of the partition function's logarithm, $\log\mathcal{Z}$, can be written as
\BE
d\log\mathcal{Z}=\fd{\log\mathcal{Z}}{\beta}d\beta.
\EE Utilizing the identity~(\ref{eq_identity}), one obtains
\BE
dS=d(\beta U)+\fd{\log\mathcal{Z}}{\beta}d\beta.
\EE Since for $T$-dependent energy
\BE
\fd{\log\mathcal{Z}}{\beta}=-U-\beta\mathbb{E}_{X}\bigg\{\fd{\mathcal{E}(X)}{\beta}\bigg\},
\EE we get \BE
dS=d(\beta U)-Ud\beta-\beta\mathbb{E}_{X}\bigg\{\fd{\mathcal{E}(X)}{\beta}\bigg\}d\beta=\beta dU-\beta\mathbb{E}_{X}\bigg\{\fd{\mathcal{E}(X)}{\beta}\bigg\}d\beta,
\EE where the r.h.s. results from Leibniz's law (product rule). Recalling that according to the $1^{st}$ law $dU=\dbar Q$ concludes the proof.
\end{proof}

The generalized $2^{nd}$ law of thermodynamics~(\ref{eq_G_second_law}) has a clear physical interpretation. For simplicity, let us assume that the examined system is characterized by a comb of discrete energy levels $\mathcal{E}1,\mathcal{E}2,\ldots$ . The heat absorbed into the $T$-dependent system has the following dual effect: A first contribution of the heat, $dU-\mathbb{E}_{X}\{d\mathcal{E}(X)/dT\}dT$, increases the temperature of the system while the second contribution, $\mathbb{E}_{X}\{d\mathcal{E}(X)/dT\}dT$, goes for shifting the energy comb.  However, the shift of the energy comb does \emph{not} affect the entropy, since the occupation of each energy level remains the same, and the entropy is independent of the energy values which stand behind the labels $\mathcal{E}1,\mathcal{E}2,\ldots$. The change in the entropy can be done only by moving part of the occupation of one tooth of the energy comb to the neighboring teeth, and this can be achieved only by changing the temperature. Hence, the effective heat contributing to the entropy is $\dbar Q-\mathbb{E}_{X}\{d\mathcal{E}(X)/dT\}dT$, and this is the physical explanation to the generalized $2^{nd}$ law~(\ref{eq_G_second_law}). Note that for $T$-independent energy, the classical $2^{nd}$ law~(\ref{eq_second_law}) is immediately obtained.

Note also, that the $1^{st}$ law remains unaffected, $dU=\dbar Q$, since both ways of heat flow absorption into the system are eventually contributing to the average internal energy $U$. The generalized $2^{nd}$ law specifies the trajectory, the weight of each one of the two possible heat flows, at a given temperature.

The temperature, originally defined by the $2^{nd}$ law as $T=\dbar Q/dS$, is redefined now as\BE
\frac{1}{T}=\frac{dS/\dbar Q}{1-\frac{\mathbb{E}_{X}\{d\mathcal{E}(X)/dT\}}{\dbar Q/dT}}=\frac{dS/\dbar Q}{1-\frac{\mathbb{E}_{X}\{d\mathcal{E}(X)/dT\}}{C_{V}(T)}}.
\EE This redefinition has a more complex form and involves an implicit function of $T$ since the temperature appears on both sides of the equation.

Based on the generalized $2^{nd}$ law, the thermodynamic expression for the
mutual information~(\ref{eq_I}) of quasi-static (\eg, Gaussian) communication channels can be reformulated as  \BEA\label{eq_I2}
I(X;Y)&=&-\mathbb{E}_{Y}\Bigg\{\int_{0}^{\beta}\gamma\Big(dU(Y;\gamma)+\mathbb{E}_{X|Y}\bigg\{\fd{\mathcal{E}(
X|Y;\gamma)}{\gamma}\bigg\}d\gamma\Big)\Bigg\}\\&=&-\mathbb{E}_{Y}\Bigg\{\int_{0}^{\beta}\gamma\Big(\fd{U(Y;\gamma)}{\gamma}+\mathbb{E}_{X|Y}\bigg\{\fd{\mathcal{E}(
X|Y;\gamma)}{\gamma}\bigg\}\Big)d\gamma\Bigg\}\label{eq_I_beta}\\
&=&-\big[\gamma\mathbb{E}_{Y}\{U(Y;\gamma)\}\big]_{0}^{\beta}
+\mathbb{E}_{Y}\Bigg\{\int_{0}^{\beta}\Big(U(Y;\gamma)+\gamma\mathbb{E}_{X|Y}\bigg\{\fd{\mathcal{E}(X|Y;\gamma)}{\gamma}\bigg\}\Big)d\gamma\Bigg\}.
\label{eq_MI_integral2}\EEA
Again, the example of a Gaussian channel with, this time, standard Gaussian input is used to illustrate the
utilization of~(\ref{eq_MI_integral2}) for the correct derivation of the mutual information.\\\,

\textbf{\emph{Example: Gaussian Channel with $\mathcal{N}(0,1)$ Input}}

Since in this case $\log(P(X))/\beta=-x^{2}/(2\beta)$, the energy~(\ref{eq_energy_map})
of the Gaussian channel system becomes an explicit function of $\beta$,
given by
\BE
\mathcal{E}(X=x|Y=y;\beta)=-xy+\frac{x^{2}}{2}\bigg(\frac{1+\beta}{\beta}\bigg),
\EE and the derivative of this function with respect to $\beta$ yields \BE
\pd{\mathcal{E}(X=x|Y=y;\beta)}{\beta}=-\frac{x^{2}}{2\beta^{2}}. \EE The a-posteriori
probability density function is
\BE
p(X=x|Y=y;\beta)=\mathcal{N}\bigg(\frac{\beta
y}{1+\beta},\frac{1}{1+\beta}\bigg).
\EE Hence, the internal energy is \BE
U(Y=y;\beta)=\mathbb{E}_{X|Y}\{\mathcal{E}(X|Y=y;\beta)\}=-\frac{y^{2}\beta}{2(1+\beta)}+\frac{1}{2\beta}, \EE and the derivative of the energy averaged over all
possible inputs is \BE
\mathbb{E}_{X|Y}\Bigg\{\pd{\mathcal{E}(X|Y=y;\beta)}{\beta}\Bigg\}=-\frac{1}{2\beta^{2}}\bigg(\frac{1}{1+\beta}+\frac{\beta^{2}y^{2}}{(1+\beta)^{2}}\bigg).
\EE
The marginal pdf of the output is given by \BE
    p(Y=y)=\mathcal{N}\Bigg(0,\frac{1+\beta}{\beta}\Bigg).
\EE Thus, \BEA
    &&-\big[\gamma\mathbb{E}_{Y}\{U(Y;\gamma)\}\big]_{0}^{\beta}=\frac{\beta}{2}-\frac{1}{2}-\Big(-\frac{1}{2}\Big)=\frac{\beta}{2},
\EEA and \BEA
&&\mathbb{E}_{Y}\Bigg\{\int_{0}^{\beta}\Big(U(Y;\gamma)+\gamma\mathbb{E}_{X|Y}\bigg\{\fd{\mathcal{E}(X|Y;\gamma)}{\gamma}\bigg\}\Big)d\gamma\Bigg\} \\&&=\mathbb{E}_{Y}\Bigg\{\bigg[-\frac{1+\gamma}{2}+\frac{1+\gamma}{2\gamma}\log(1+\gamma)+\frac{1}{2}\log(1+\gamma)-\frac{Y^{2}}{2}\log(1+\gamma)-\frac{Y^{2}}{2(1+\gamma)}\bigg]_{0}^{\beta}\Bigg\}\\&&=
\mathbb{E}_{Y}\Bigg\{-\frac{\beta}{2}+\frac{1+\beta }{2\beta}\log(1+\beta)-\frac{1}{2}+\frac{1}{2}\log(1+\beta)-\frac{Y^{2}}{2}\log(1+\beta)-\frac{Y^{2}}{2(1+\beta)}+\frac{Y^{2}}{2}\Bigg\}\nonumber\\\\
&&=-\frac{\beta}{2}+\frac{1}{2}\log{(1+\beta)}
\EEA giving, based on~(\ref{eq_MI_integral2}), \BE
I(X;Y)=\frac{1}{2}\log{(1+\beta)}
\EE and the Shannon capacity~\cite{BibDB:Shannon} is derived from the perspective of thermodynamics.

\section{Guo-Shamai-Verd\'{u} Theorem}\label{sec_GSV}
In this section we prove the Guo-Shamai-Verd\'{u} (GSV) theorem from the $2^{nd}$ law
of thermodynamics for systems with $T$-dependent energy and the resulting thermodynamic representation of the mutual information. Thus, we show that this fascinating relation between
information theory and estimation theory is actually an evolution of the most
profound laws of nature.

To start with, let us restate the GSV theorem.
Consider a Gaussian channel of the form \BE\label{eq_channel_GSV}
    Y=\sqrt\snr X+N,
\EE where
\mbox{$N\sim\mathcal{N}(0,1)$} is a standard Gaussian noise independent
of $X$. The mutual information, $I(\snr)$~(\ref{eq_I}), and the minimum mean-square error, defined as \BEA \mmse(X|\sqrt\snr
X+N)&=&\mmse(\snr)=\mathbb{E}_{X,Y}\{(X-\mathbb{E}_{X|Y}\{X|Y;\snr\})^2\}, \EEA are both a function of $\snr$ and maintain the following relation.
\begin{GSV}{\cite[Theorem 1]{BibDB:GSV}}
For every input distribution $P(X)$ that satisfies
$\mathbb{E}_{X}\{X^{2}\}<\infty$, \BE\label{eq_GSV1}
    \fd{}{\snr}I(X;\sqrt{\snr}X+N)=\frac{1}{2}\mmse(X|\sqrt{\snr}X+N).
    \EE
\end{GSV}

Note that the GSV-based expression of the mutual information, \BE\label{eq_I_GSV}
I(X;\sqrt{\snr}X+N)=\frac{1}{2}\int_{0}^{\snr}\mmse(X|\sqrt{\gamma}X+N)d\gamma,
\EE resembles its thermodynamic expression~(\ref{eq_I_beta}) in the sense that both are an outcome of integration with respect to SNR (or inverse temperature, $\beta$). Hence, the roots of this integration in the GSV theorem may be attributed to the $2^{nd}$ law of thermodynamics. Note however to the opposite order of integration in the two expressions, where in the GSV expression~(\ref{eq_I_GSV}) the inner integration (within the definition of MMSE) is over $y$ and the outer integration is over SNR, and vice versa for the thermodynamic expression~(\ref{eq_I_beta}). Exchanging the order of integration in the latter (which is not trivial since $p(Y=y)$ is itself a function of $\beta$) yields, as we shall see, an integrand of $d\beta$ which is equal to $\mmse(\beta)/2$.
In the following proof Lemma~$1$ from~\cite{BibDB:GSV}, which underlines the main proof of the GSV theorem in~\cite{BibDB:GSV}, is proven directly from the thermodynamic description of the mutual information~(\ref{eq_I2}).

\begin{proof}
Adopting the SNR-incremental channel approach~\cite[Eq. (30)-(41)]{BibDB:GSV} and mapping again $\snr\rightarrow\beta$
\BE
\fd{I(X;Y)}{\beta}=\frac{I(X;Y_{1})-I(X;Y_{2})}{\delta}=\frac{I(\beta+\delta)-I(\beta)}{\delta}=\frac{I(X;Y_{1}|Y_{2
})}{\delta},
\EE where $I(X;Y_{1}|Y_{2})$ is the mutual information of the incremental
Gaussian channel \BE\label{eq_inc_channel}
Y_{1}=\sqrt{\delta}X+N,
\EE where $N$ is a standard Gaussian noise, $X$ is taken from the conditional probability $P(X|Y_{2})$,
$\delta\rightarrow0$ and \BE\label{eq_Y2} Y_{2}=X+\mathcal{N}(0,1/\beta) \EE with $X\sim P(X)$. Hence, we have to prove
\BE
\frac{I(X;Y_{1}|Y_{2})}{\delta}=\frac{1}{2}\mmse(\beta).
\EE Now, the principles of thermodynamics come into action. For this incremental channel~(\ref{eq_inc_channel}), the energy and its derivative are given by
\BEA
\mathcal{E}(X=x|Y_{1}=y_{1},Y_{2}=y_{2};\delta,\beta)&=&-\frac{xy_{1}}{\sqrt{\delta}}+\frac{x^{
2}}{2}-\frac{\log{P(X=x|Y_{2}=y_{2};\beta)}}{\delta}\EEA and \BEA
&&\fd{}{\delta}\mathcal{E}(X=x|Y_{1}=y_{1},Y_{2}=y_{2};\delta,\beta)=\frac{xy_{1}\delta^{-\frac{3}{2}}}{2}+\frac{\log{P(X=x|Y_{2}=y_{2};\beta)}}{\delta^{2}}.
\EEA
Using the thermodynamic expression for the mutual information~(\ref{eq_I2}) and recalling
that $\delta\rightarrow0$, one gets \BEA
I(X;Y_{1}|Y_{2}=y_{2})&=&-\mathbb{E}_{Y_{1}|Y_{2}}\Bigg\{\int_{0}^{\delta}\gamma
\Big(dU(Y_{1}|Y_{2}=y_{2};\gamma,\beta)+\mathbb{E}_{X|Y_{1},Y_{2}}\bigg\{\pd{}{\gamma}{\mathcal{E}(X|Y_{1},Y_{2}=y_{2};\gamma,\beta)}\bigg\}d\gamma\Big)\Bigg\}
\nonumber\\\\&=&-\mathbb{E}_{Y_{1}|Y_{2}}\Bigg\{
\mathbb{E}_{X|Y_{1},Y_{2}}\bigg\{\delta \mathcal{E}(X|Y_{1},Y_{2}=y_{2};\delta,\beta)+\delta^{2}\fd{}{\delta}{\mathcal{E}(X|Y_{1},Y
_{2}=y_{2};\delta,\beta)}\bigg\}\Bigg\}
\\&=&-\mathbb{E}_{Y_{1}|Y_{2}}\Bigg\{-\frac{\mathbb{E}_{X|Y_{1},Y_{2}}\{X|Y_{1},Y_{2}=y_{2}\}Y_{1}\sqrt{\delta}}{2}+\frac{\delta
\mathbb{E}_{X|Y_{1},Y_{2}}\{X^{2}|Y_{1},Y_{2}=y_{2}\}}{2}\Bigg\}\\&=&
-\mathbb{E}_{Y_{1}|Y_{2}}\Bigg\{-\frac{\sqrt{\delta}}{2}Y_{1}\mathbb{E}_{X|Y_{2}}\{X|Y_{2}=y_{2}\}+\frac{\delta}{2}\mathbb{E}_{X|Y_{2}}\{{X^{2}|Y_{2}=y_{2}}\}\Bigg\}
\label{eq_move1}\\&=&\frac{\delta}{2}\Big(-\mathbb{E}_{X|Y_{2}}^{2}\{X|Y_{2}=y_{2}\}+\mathbb{
E}_{X|Y_{2}}\{X^{2}|Y_{2}=y_{2}\}\Big)\label{eq_move2}
\\&=&\frac{\delta}{2}\mathbb{E}_{X|Y_{2}}\{(X-\mathbb{E}_{X|Y_{2}}\{X|Y_{2}=y_{2}\})^{2}|Y_{2}=y_{2}
\},\EEA where~(\ref{eq_move1}) is based on the fact that for an infinitesimal $\snr$, $\delta\rightarrow0$, the expectation \mbox{$\mathbb{E}_{X|Y_{1},Y_{2}}\rightarrow\mathbb{E}_{X|Y_{2}}$}, while~(\ref{eq_move2}) results from the independence of $N$~(\ref{eq_inc_channel}) with $Y_{2}$~(\ref{eq_Y2})~\cite[Section II-C]{BibDB:GSV}.
Averaging over $Y_{2}$ on both sides of the equation, we obtain the desired result
\BE
I(X;Y_{1}|Y_{2})=\frac{\delta}{2}\mathbb{E}_{X,Y_{2}}\{(X-\mathbb{E}_{X|Y_{2}}\{X|Y_{2}\})^{2}\}
=\frac{\delta}{2}\mmse(\beta).
\EE
\end{proof}

\section{conclusion}\label{sec_conclusion}
In this paper, the mutual information of Gaussian channels is described via thermodynamic terminology. As a byproduct, an intimate link is revealed between the GSV theorem and the basic laws of thermodynamics.
More generally, the revised $2^{nd}$ law for thermal systems with temperature-dependent energy levels enables to quantitatively bridge between the realm of thermodynamics and information theory for quasi-static systems. It is anticipated that this substantial theoretical connection between the foundation laws of thermodynamics and information theory will open a horizon for new discoveries and development in the study of both artificial and natural systems, towards a possibly more synergetic foundation to these two vital disciplines.


TITLE: Why is the z =z' when using Milne-Thomson Method for determining a holomorphic function?
QUESTION [5 upvotes]: When we use Milne-Thomson method, we substitute $x$ and $y$ with $\frac{z+z^*}2$ and $\frac{z-z^*}{2i}$. This gives us...
$f(z) = u(x,y) + iv(x,y) = u(\frac{z+z^*}2, \frac{z-z^*}{2i}) + i v(\frac{z+z^*}2, \frac{z-z^*}{2i})$
$z^*$ represents the conjugate of $z$.
We then proceed to say that for the above relation $z=z^*$.
Why did we we do that? And how can we say that? I mean, this seems like a massive over-simplification.

REPLY [1 votes]: There is a bit of trickery involved in that you start sticking complex arguments into the functions $u$ and $v$. But suppose that this is not a problem, meaning $x$ and $y$ can be treated as complex variables. You are then looking at the equation
$$
f(x+i y) = u(x,y) + i v(x,y)
$$
over the complex numbers. You see that the left-hand side only depends on the linear combination of $x$ and $y$, and a change of variables
$$
z = x + i y, w = x - i y
$$
produces an expression where the l.h.s. is independent of $w$:
$$
f(z) = u((z+w)/2,(z-w)/2i) + i v((z+w)/2,(z-w)/2i)
$$
That means in particular that the r.h.s. holds whatever the choice of $w$. To make the expression as simple as possible, one can pick $w = z$:
$$
f(z) = u(z,0) + i v(z,0)
$$
This works only because it was assumed that $f$ is a holomorphic function: If not, the l.h.s. depends on $x - i y = w$ as well.


TITLE: simplest possible way to prove chain rule for second derivative
QUESTION [0 upvotes]: Given $\phi=\phi(u)$ and $u=u(x)$
What is the simplest possible way to prove
$$
\frac{d^2\phi}{dx^2}=\bigg(\frac{du}{dx}\bigg)^2.\frac{d^2\phi}{du^2}+\frac{d^2u}{dx^2}.\frac{d\phi}{du}
$$

REPLY [2 votes]: by repeated application of the chain rule:
$$
\frac{d^2\phi}{dx^2}=\frac{d}{dx}\big(\frac{d\phi}{dx}\big)=\frac{d}{dx}\big(\frac{d\phi}{du}\frac{du}{dx}\big)=\frac{d}{dx}\big(\frac{d\phi}{du}\big)\frac{du}{dx}+\frac{d\phi}{du}\frac{d^2u}{dx^2}=\frac{du}{dx}\frac{d}{du}\big(\frac{d\phi}{du}\big)\frac{du}{dx}+\frac{d\phi}{du}\frac{d^2u}{dx^2}=\frac{d^2\phi}{du^2}\big(\frac{du}{dx}\big)^2+\frac{d\phi}{du}\frac{d^2u}{dx^2}
$$
where $\frac{d}{dx}=\frac{du}{dx}\frac{d}{du}$


TITLE: Topological Hausdorff Group: $ A$ closed, $B$ compact $\Longrightarrow AB$ closed
QUESTION [6 upvotes]: I'm dealing with a puzzling problem and hope some of you can help me.
Let be $(G,\cdot ) $ be a Hausdorff-group and let $A,B \subseteq G$. Show that if $A$ is closed and $B$ is compact, then $AB$ is closed.
Due to I'm considering a topological Hausdorff-group, we have two continous maps:
$\psi: G \times G \rightarrow G, (x,y) \mapsto xy$  and  $ \phi: G \times G \rightarrow G, (x,y) \mapsto x{y}^{-1} $
My idea was to show that $(AB)^{c}$ is open instead.
First we observe, that if $A$ is closed, then $A^{c}$ is open and due to $\phi$ is continous $\phi^{-1}(A^{c})$ is also open.
Now let's choose an arbitrary $x \in (AB)^{c}$. We see that $\forall y \in B: \phi(x,y)=xy^{-1} \in A^{c}$. (because if it wasn't it would be in $A$ we could conclude $\psi(xy^{-1},y)=xy^{-1}y \in AB$, what would be opposed to the chosen x)
So we know that $\phi(x,y)=xy^{-1} \in A^{c} \Rightarrow (x,y) \in \phi^{-1}(A^{c})$, which is open.
Then we find neighbourhoods $U$ from $x$ and $V$ from $y$ such that:
$\forall y \in B \exists U_{y} \exists V : (x,y) \in U_{y} \times V \subseteq \phi^{-1}(A^{c})$
If I could manage to show, that $U:= \cap_{y \in B} U_{y}$ is open (I don't know this, because it might be an infinite intersection) i think my proof is complete.
Because then I can show that $U \subseteq (AB)^{c}$, so that for arbitrary $x$ $(AB)^{c}$ is a neighbourhood of x. This means that $(AB)^{c}$ is open.
Can anybody give me a hint how I can show, that this intersection is finite? I suppose it must follow from the compactness of B, because I haven't used it yet, but I have no clue how?
Thank you!

REPLY [0 votes]: I think we can use the Tube Lemma to solve this:
Consider the continuous function $\phi:(x,y)\mapsto xy^{-1}$. Suppose $c\notin AB$, then $c\times B\subset \phi^{-1}(A^c)$. Since $B$ is compact, there is some neighborhood $W$ of $c$ s.t. $W\times B\subset\phi^{-1}(A^c)$, whence $WB^{-1}\subset A^c$.