TITLE: Four elevators stop on floors $1$ to $8$; a separate elevator stops on $1$ and $4$. Suppose you want to get from $1$ to $4$ ...
QUESTION [5 upvotes]: I recently encountered an interesting math problem at the hospital. The hospital had two elevator banks. The first one had four elevators that went to any of the floors, 1 through 8. While the second elevator bank was for expecting mothers, only had one elevator, and only stopped on floors 1 and 4 (as floor 4 was the birthing unit).

Assuming you're traveling to level 4 from level 1, so you can use either elevator bank, are you more likely to receive an elevator first in the elevator bank with one or four elevators? What's the average time it would take to receive an elevator in each bank?

Let's assume each elevator takes 1 second to travel each floor, whichever elevator is closests to level 1 will arrive first, each elevator is equally likely to be on any of its possible floors when you call it, and you're the only one riding the elevators at the time.
I thought I would need some sort of factorial combinatorics equation to solve this, but I'm struggling to put it together.

REPLY [1 votes]: Let's look at the second bank first. The elevator there is either at floor $4$ or floor $1$ with equal probability, so the average time for this bank is
$$
t_2=\frac{1}{2}\cdot 0 + \frac{1}{2}\cdot 3=1.5
$$
The first bank is more complicated. What I'm assuming is that the person calls all $4$ elevators at once and the closest one descends (I don't know how realistic this is). Each of the four elevators is on one of the floors from $1$ through $8$ and the probability of any particular arrangement of elevators is therefore $1/8^4$. Let's say the elevators are on floors $f_1,f_2,f_3,f_4$. Then the time it will take for one to arrive is $\min(f_1,f_2,f_3,f_4)-1$ and so the average time is
$$
t_1=2^{-12}\sum (\min(f_1,f_2,f_3,f_4)-1)=\left(2^{-12}\sum \min(f_1,f_2,f_3,f_4)\right)-1
$$
The sum is taken over all allowed $4$-tuples of the $f_i$. It is easy to calculate directly using a computer, the sum comes out to be $8772$. So
$$
t_1=\frac{8772}{4096}-1=\frac{1169}{1024}=1.1416015625
$$
If you want a less computational approach, the sum can be dealt with by hand. Suppose $\min(f_1,f_2,f_3,f_4)=m$. Then all elevators are at floors $m$ or higher and at least one is at floor $m$. Denote the number of such $4$-tuples by $N(m)$. The number of all $4$-tuples where all $f_i\geq m$ is $(9-m)^4$ whereas the number of all $4$-tuples where all $f_i> m$ is $(8-m)^4$. Then $N(m)=(9-m)^4-(8-m)^4$ since the $4$-tuples we are interested in are precisely the ones remaining after we remove all $4$-tuples which have no elevator on floors $\leq m$. Finally, the sum in question will be:
$$
\sum \min(f_1,f_2,f_3,f_4)=\sum_{m=1}^8mN(m)=\sum_{m=1}^8m((9-m)^4-(8-m)^4)=\sum_{m=1}^8m^4
$$
This involves much less calculation and is perfectly tractable by hand. It also straightforwardly generalises if the number of floors isn't $8$, since the sum can be computed explicitly using the formulas for sums of powers $\sum_k k^r$.


text:
\begin{document}
\maketitle
\begin{abstract}
Coloring the faces of a two-dimensional square lattice with $k$ distinct colors such that no two adjacent faces have the same color is considered by establishing connection between the $k$-coloring problem and a generalized vertex model. Associating the colors with $k$ distinct species of particles with an infinite repulsive force between nearest neighbors of the same type and zero chemical potential $\mu$ associated with each species, the number of ways $[W(k)]^N$ for large $N$ is related to the entropy of the {\it{hard square lattice gas}} at close packing of the lattice, where $N$ is the number of lattice sites. We discuss the evaluation of $W(k)$ using transfer matrix method with non-periodic boundary conditions imposed along at least one direction, and, show the characteristic Toeplitz block structure of the transfer matrix. Using this result, we present some analytical calculations for non-periodic models that remain finite in one dimension. The case $k = 3$ is found to approach the exact result obtained by Lieb for the residual entropy of ice with periodic boundary conditions. Finally, we show, by explicit calculation of the contribution of subgraphs and the series expansion of $W(k)$, that the generalized Pauling type estimate (which is based on mean-field approximation) dominates at large values of $k$. We thus also provide an alternative series expansion for the chromatic polynomial of a regular square graph.
\end{abstract}

\noindent
Keywords: vertex model; coloring problem; transfer matrix; entropy

\section{Introduction}

Ice has a residual entropy at low temperatures that cannot be explained by any conceivable lattice vibrations \cite{pauling1,pauling2,lieb}. Pauling \cite{pauling1,pauling2,bernal,lieb} suggested that this is because the O-O bond length (2.76 \AA) is more than twice the O-H bond length (0.95 \AA) and thus the hydrogen atom has two possible positions on each of the O-O bond. ``In the gas molecule the O-H distance is 0.95 \AA , and the  magnitudes of the changes in properties from steam to ice are not sufficiently great to permit us to assume that this distance is increased to 1.38 \AA ", writes Pauling \cite{pauling1}. Furthermore, he writes ``The concentration of $(\text{OH})^-$ and $(\text{H}_3\text{O})^+$ ions in water is very small and we expect the situation to be unchanged in ice. Thus each oxygen atom must be surrounded by two oxygen atoms near it and two on the far side" \cite{pauling1,bernal,lieb}.  Associating with each hydrogen atom near (far from) an oxygen atom an arrow pointing towards (away from) the oxygen atom , the problem can be transformed into an interesting graph-theoretic problem of determining the number of ways of arranging arrows on the edges of square lattice such that the number of arrows going into a vertex is equal to that coming out of the vertex \cite{thompson}. Lenard(according to \cite{lieb}) has shown that, aside from a factor of three, the problem is isomorphic to the three colorings of the square lattice. The problem of residual entropy of ice and related problems has been discussed extensively in the literature\cite{pauling1,pauling2,baxter1,baxter2,runnels,lieb,thompson,stillinger,nagle}. Lieb \cite{lieb} found the exact value for the exponent $W(3)$ for a toroidal lattice as:
\begin{equation*}
 W(3)={\left(\frac{4}{3}\right)}^{3/2}\approx 1.5396\ldots
\end{equation*}
Baxter \cite{baxter1,baxter2} found the grand canonical partition function for the 3-coloring of the square lattice where the activities $z_1,z_2,z_3$ are associated with each color and every configuration at a vertex has zero energy, which is equivalent to a general case of the close packed hard square lattice gas mentioned before. Thus Lieb's result \cite{lieb} is recovered when $z_1=z_2=z_3=1$. Pauling \cite{pauling2} made an approximation for $W$ based on the assumption that the lattice bonds and vertex configurations are independent. If there are $N$ lattice sites, then the total number of ways of placing arrows,  were there no restrictions,  would be $2^{2N}$, because there are $2N$ bonds in the lattice. Because of the ice condition, only 6 out of 16 possible configurations are allowed at each vertex. Thus the number of ways is:
\begin{equation*}
W_N \approx 2^{2N}\left(\frac{6}{16}\right)^N
\end{equation*}
and thus \begin{equation*}
W=\lim_{N\rightarrow\infty}{W_N}^{1/N}\approx\frac{3}{2}=1.5
\end{equation*}
The above estimate is due to Pauling. Nagle \cite{nagle} improved the methods of Stillinger et al. \cite{stillinger} to obtain the series expansion of $W$:\begin{equation*}
W=\frac{3}{2}\left(1+\frac{1}{3^4}+\frac{4}{3^6}+\frac{22-4}{3^8}+\ldots \right)
\end{equation*}
In this paper, we construct a vertex model which maps to the $k$ coloring of the square lattice. We begin by discussing transfer matrix method which incorporates the interaction of two rows of a lattice. The transfer matrix for chains with {\it non-periodic} boundary condition imposed on the rows is found to have Toeplitz block structure. We also show that the maximum eigenvalue of the transfer matrix for non-periodic boundary conditions approaches the result obtained by \cite{lieb} for $k=3$ for toroidal ice, as expected. Analytical values of open and cylindrical square lattices that remain finite in only one dimension is derived (for the case $k=3$) without resorting to the method of diagonalizing the transfer matrix. We illustrate the $k$-coloring problem by considering in detail the case of $k = 4$ for brevity where we find a 21-vertex model. Graph theoretical methods \cite{stillinger} and matrix methods \cite{nagle} are generalized to obtain a series expansion of $W(k)$ in terms of $k$. The first term of the series is the generalized Pauling estimate and subsequent terms are $\mathcal{O}({1/{k^n}})$. The results of \cite{nagle} is recovered for the special case of $k=3$, corresponding to the six-vertex model.

\section{The transfer matrix approach}
Consider a square lattice with $m$ rows, each having $p$ lattice sites. The last lattice site of each row is connected to the first lattice site via a bond and the $m^{th}$ row is connected to the first row via $p$ bonds. Thus, while considering the assignment of arrows on the bonds of the lattice, we have $m$ rows of $p$ up-down arrows and $p$ left-right arrows. Let $\phi$ denote a possible configuration of a row of $p$ vertical bonds. For two adjacent rows of vertical bonds having configurations $\phi$ and $\phi'$, define $B(\phi,\phi')$ to be the number of ways of arranging horizontal arrows on the row of horizontal bonds common to these two rows. Thus $B$ is a $2^p \times 2^p$ matrix called the transfer matrix \cite{baxter2} and the number of ways $Z$ of arranging the arrows on the lattice is:

\begin{equation*}
Z=\sum_{\phi_{1}}\ldots \sum_{\phi_{m}}B(\phi_1,\phi_2)B(\phi_2,\phi_3)\ldots B(\phi_{m-1},\phi_m)B(\phi_m,\phi_1) = Tr[B^m].
\end{equation*}
For large $m$,
\begin{equation*}
Z=\Lambda^m.
\end{equation*}
where $\Lambda$ is the maximum eigenvalue of $B$.
\subsection{The {\it{non-toroidal}} ice}
Unlike Lieb\cite{lieb}, we consider a square lattice that is not toroidal, i.e., either it is a completely open square lattice or a cylindrical lattice with the last row connected to the first row.
\subsubsection{Cylindrical lattice}\label{cylindricalice}
For a cylindrical lattice, we have
\begin{equation*}
Z=\sum_{\phi_{1}}\ldots \sum_{\phi_{m}}B(\phi_1,\phi_2)B(\phi_2,\phi_3)\ldots B(\phi_{m-1},\phi_m)B(\phi_m,\phi_1) = Tr[B^m].
\end{equation*}
Note that the matrix $B$ is not the same as that for the toroidal ice because removing the cyclic boundary condition in each row would allow some of the configurations of two adjacent rows to have non-zero elements $B(\phi,\phi')$ which were zero for the cyclic rows.

Let $\mathcal{L}_p$ be an ordered set of all possible configurations of $p$ up-down arrows. Thus the size of $\mathcal{L}_p$ is $2^p$. Let
\begin{equation}
\mathcal{L}_1=\left\lbrace\uparrow,\downarrow\right\rbrace.
\end{equation}
The set $\mathcal{L}_p$ is constructed in the following manner: \begin{equation}
\text{If } \mathcal{L}_p=\left\lbrace\phi_1,\phi_2,\ldots,\phi_{2^p}\right\rbrace\text{, then } \mathcal{L}_{p+1}=\left\lbrace\uparrow\phi_1,\uparrow\phi_2,\ldots,\uparrow\phi_{2^p},\downarrow\phi_1,\downarrow\phi_2,\ldots,\downarrow\phi_{2^p}\right\rbrace.
\end{equation}
where $\uparrow\phi$ denotes a configuration of $p+1$ arrows whose first arrow is up and the rest are in configuration $\phi$, and similarly for $\downarrow\phi$. Note that the first $2^p$ elements of $L_{p+1}$ have their first arrow as $\uparrow$ and the next $2^p$ have their first arrow as $\downarrow$, and this observation is very crucial in the arguments that follow. Let $B_p(i,j)=B(\phi_i,\phi_j)$ where $\phi_i,\phi_j\in\mathcal{L}_p$ and $\phi_i$ is the $i^{th}$ element of $\mathcal{L}_p$. Also,
\begin{equation}\label{dcmp1}
B(\phi,\phi')=B(\downarrow\phi,\uparrow\phi')+B(\uparrow\phi,\downarrow\phi').
\end{equation}

\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{drawing-1.jpg}
\label{fig:arrow}
\caption{Configurations counted by $B(\downarrow\phi,\uparrow\phi')$ and $B(\uparrow\phi,\downarrow\phi')$}
\end{figure}
The proof of Equation \ref{dcmp1} is simple: the downarrow-uparrow in the first sites of two adjacent rows would force the horizontal arrow at the beginning of $\frac{\phi'}{\phi}$ to take the left position($\leftarrow$), which is counted by the first term of right hand side, the uparrow-downarrow in the first sites of two adjacent rows would force the horizontal arrow at the beginning of $\frac{\phi'}{\phi}$ to take the right position($\rightarrow$), which is counted by the second term(refer to Fig. 1). Since the horizontal arrow at the beginning of $\frac{\phi'}{\phi}$ can point either to the left or to the right, all possibilities are exhaustively counted by the right hand side of the equation.
Define\begin{equation}\label{dcmp}
B(\downarrow\phi,\uparrow\phi')=A(\phi,\phi').
\end{equation}
Let $A_p(i,j)=A(\phi_i,\phi_j)$ where $\phi_i,\phi_j\in\mathcal{L}_p$ and $\phi_i$ is the $i^{th}$ element of $\mathcal{L}_p$. Since $B(\phi,\phi')=B(\phi',\phi)$ \begin{equation}
B_p(i,j)=A_p(i,j)+A_p^T(i,j).
\end{equation}
 Now, we consider the four $2^p\times2^p$ block matrices of the $2^{p+1}\times2^{p+1}$ matrix $A_{p+1}$. For the upper left block ($1{\leq}i{\leq}2^p$ and $1{\leq}j{\leq2}^p$), we have: \begin{equation}
 A_{p+1}(i,j)=A(\uparrow\phi_i,\uparrow\phi_j)=B(\downarrow\uparrow\phi_i,\uparrow\uparrow\phi_j)=B(\downarrow\phi_i,\uparrow\phi_j)=A_p(i,j).
 \end{equation}
 where $\phi_i,\phi_j\in\mathcal{L}_p$.
 For the lower right block($2^p<i\leq2^{p+1}$ and $2^p<j\leq2^{p+1}$), we have:
 \begin{equation}
 A_{p+1}(i,j)=A(\downarrow\phi_{i-2^p},\downarrow\phi_{j-2^p})=B(\downarrow\downarrow\phi_{i-2^p},\uparrow\downarrow\phi_{j-2^p})=B(\downarrow\phi_{i-2^p},\uparrow\phi_{j-2^p})=A_p(i-2^p,j-2^p)
 \end{equation}
where $\phi_{i-2^p},\phi_{j-2^p}\in\mathcal{L}_p$. Thus the diagonal blocks of $A_{p+1}$ are the same as $A_p$. For the upper off-diagonal block($1{\leq}i{\leq}2^p$ and $2^p<j\leq2^{p+1}$), we have: \begin{equation}
 A_{p+1}(i,j)=A(\uparrow\phi_{i},\downarrow\phi_{j-2^p})=B(\downarrow\uparrow\phi_i,\uparrow\downarrow\phi_{j-2^p})=B(\uparrow\phi_i,\downarrow\phi_{j-2^p})=A_p^T(i,j-2^p).
 \end{equation}
 where $\phi_i,\phi_{j-2^p}\in\mathcal{L}_p$.
 By similar argument, the lower off-diagonal block has all elements $0$. Thus
 \begin{equation}\label{eq:turner}
 A_{p+1}=\begin{pmatrix}
 A_p & A_p^T \\
 0 & A_p
 \end{pmatrix}
 \end{equation}
 We have the $1\times1$ matrix $A_0=B(\downarrow,\uparrow)=[1].$  Eq. \eqref{eq:turner} sets up a recursive scheme whereby as $p$ increases, we can find the maximum eigenvalue, and recover the results by Lieb. For the triangular lattice also, arguments as above lead to block matrices and whence ensue the corresponding results by Baxter.

\subsection{Lieb's square ice constant for cylindrical chain}
From the matrices constructed in the previous section, it is clear that
\begin{equation*}
\lim_{p\rightarrow\infty}[\lambda_{max}(A_p+A_p^T)]^{1/p}
\end{equation*}
gives Lieb's result.
We performed the computation of $[\lambda_{max}(A_p+A_p^T)]^{1/p}$ till $p=10$ using MATHEMATICA and the values we found were the following:
\begin{center}
 \begin{tabular}{||c c||}
 \hline
 $p$ & $[\lambda_{max}(A_p+A_p^T)]^{1/p}$ \\ [0.5ex]
 \hline\hline
 1 & 3.00000 \\
 \hline
 2 & 2.13578 \\
 \hline
 3 & 1.91037 \\
 \hline
 4 & 1.80789\\
 \hline
 5 & 1.74955 \\
 \hline
 6 & 1.71195 \\
 \hline
 7 &  1.68573 \\
 \hline
 8 &  1.66641 \\
 \hline
 9&  1.65159 \\
 \hline
 10 & 1.63987 \\ [1ex]
 \hline
\end{tabular}
\end{center}
A plot of these data points is shown in Fig. 2. We fitted the data to the following functional form:
\begin{equation*}
a_0+a_1/x+a_2/{x^2}+\ldots+a_5/{x^5}
\end{equation*}
We obtained the asymptotic limit as $a_0=1.53967$, which is not too bad all things considered.

\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{drawing-7.jpg}
\caption{Plot of $[\lambda_{max}(A_p+A_p^T)]^{1/p}$ vs. $p$ for $p=1,2,3....,10$}
\end{figure}

 We prove two theorems involving the matrix $A_p$ that will be useful later.
 \newtheorem{theorem}{Theorem}
 \begin{theorem}
 $Tr[A_p^n]=2^p$ for all non-zero positive integers $n$ and $p$.
 \end{theorem}
 It is elementary to show that
 \begin{equation}
 A_{p+1}^n=\begin{pmatrix}
 A_p^n & X_n \\
 0 & A_p^n
 \end{pmatrix}
 \end{equation}
 where $X_n=\sum_{i=1}^nA_p^{n-i}A_p^TA_p^{i-1}$, with $A_p^0$ taken to be equal to $I_p$.
 Thus
 \begin{equation}
 Tr[A_{p+1}^n]=2Tr[A_{p}^n].
 \end{equation}
 Since $Tr[A_0^n]=1$, we get
 \begin{equation}
 Tr[A_p^n]=2^p.
 \end{equation}

 \begin{theorem}
 $Tr[A_p^nA_p^T]=(n+2)^p$ for all non-zero positive integers $n$ and $p$.
 \end{theorem}

 \begin{equation}
 A_{p+1}^T=\begin{pmatrix}
 A_p^T & 0\\
 A_p & A_p^T
 \end{pmatrix}.
 \end{equation}
 and thus
 \begin{equation}
 A_{p+1}^nA_{p+1}^T=\begin{pmatrix}
 A_p^nA_p^T+X_nA_p & X_nA_p^T\\
 A_p^{n+1} & A_p^nA_p^T
 \end{pmatrix}.
 \end{equation}
 It is trivial to show, by using cyclic property of trace of product of matrices, that
 \begin{equation}
 Tr[X_nA_p]=nTr[A_p^nA_p^T].
 \end{equation}
 We get the following iterative formula
 \begin{equation}
 Tr[A_{p+1}^nA_{p+1}^T]=(n+2)Tr[A_p^nA_p^T]
 \end{equation}
 since $Tr[A_0^nA_0^T]$=1, we have
 \begin{equation}
 Tr[A_p^nA_p^T]=(n+2)^p.
 \end{equation}
 Equipped with the block matrix structure and the above two theorems, we present the exact number of ways of satisfying the ice condition of a $2\times p$ and $3\times p$ cylindrical lattice in the Appendix, for illustrative purpose.

\subsection{The 4-coloring problem : ``warm up"}
The connection between the ice problem and the 3-coloring problem was argued by Andrew Lenard (it appears in \cite{lieb}). We present the case of four colors, which we hope will serve as an illustration for the general case discussed later.

\begin{figure}
\centering
\includegraphics[width=0.4\textwidth]{Fig3.jpg}
\caption{About a vertex v, we have four faces colored by A, B, C, D, each of these being one of the four colors (coded using numbers $\in \{ 1, 2, 3, 4 \}$). To assign a state to an edge 1 (for instance), we traverse about the vertex v in a clockwise direction and notice that C comes after B. Edge 1 is then in a state $(C - B) \mod 4$. With respect to the vertex v' though, the state of edge 1 will be $(B - C) \mod 4$, because while going clockwise around v', the color B comes after color C. This illustrates the two rules, \eqref{arrow}, \eqref{icecondition} for the case of 4-coloring. The marks 1, 2, 3, 4 in the figure denote the edges, not to be confused with colors or states of edges.}
\end{figure}

Let the four colors be given numbers: ${\mathbf S} = \{1, 2, 3, 4 \}$. The edges emanating from a given vertex can be assigned states by traversing in (say) clockwise direction about it, in terms of the two distinct colours on two sides of an edge. Precisely, $A, B, C, D$ are colors (they could be any $\in {\mathbf S}$ shown in the Fig. 3, with $D \neq A \neq B, B \neq C \neq D$. On traversing clockwise about the vertex $v$, we assign the number $(C - B) \mod 4$  to edge 1. Clearly, the state of edge 1 with respect to the vertex $v'$ is $(B - C) \mod 4$ in such a way that $(C - B) \mod 4 + (B - C) \mod 4 \equiv 0 \mod 4$. To abbreviate the notation, the states of edge 1 w.r.t. vertex $v$ ($v'$) are $e_1$ ($e_1'$). Let the states of edges 2,3 and 4 w.r.t. $v$ be $e_2$, $e_3$ and $e_4$ respectively. It is obvious now that, $e_1 + e_2 + e_3 + e_4 \equiv 0 \mod 4$ and $e_1+e_1'\equiv 0 \mod4$. These rules will hold at every vertex of the lattice. The edge states are uniquely specified for a given coloring, because the $\mod 4$ operation will always give us a unique number.(The positive remainder we get by dividing an integer by 4 is always unique). Corresponding to every assignment of states satisfying the two rules above, there are four ways of coloring the faces of the square lattice using four colors. Let us start with a face and color it by, say, $A$. We could have chosen any one of the four colors, and it is this freedom that gives us a factor of four. If we traverse about $v$ clockwise(where $v$ is one of the vertices of face colored $A$) and use the color $X$($X \neq A$) for the next face, sharing the edge, then $X$ must satisfy $(X - A) \mod 4 \equiv e_1$(where $e_1$ is the state of common edge w.r.t. $v$). That $X$ is unique can be immediately proved by assuming the contradiction that there are two colors, $X_1, X_2$ obeying
$(X_1 - A) \mod 4 \equiv e_1$ and $(X_2 - A) \mod 4 \equiv e_1$. Immediately, we have $X_1 = X_2$ as $(X_1 - X_2) \mod 4 \equiv 0$ and $X$'s can only take values from the set, ${\mathbf S}-\left\lbrace A \right\rbrace$. This also shows that if we take any two different $X$s and calculate the value $(X-A)\mod 4$ for these two $X$s, we will never get the same value. Thus out of all the three possibilities of $X$, one (and only one) will exist that will satisfy $(X-A)\mod 4=e_1$  In this way, we can color all the faces for a given edge state configuration.

Let us denote the number of ways of assigning edge states to a square lattice having $N$ lattice sites by $W_{\rm vertex}$, and, the number of ways of coloring the faces by $W_{\rm coloring}$. We see that $W_{\rm coloring} = 4W_{\rm vertex}$; however, the factor `4' is immaterial when we consider the quantity $\lim_{N \to \infty } W^{1/N}$.

The number of possible configurations such that $e_1 + e_2 + e_3 + e_4 \equiv 0 \mod 4$ is $(4-1)^3 - (4-1)^2 + (4-1) = 21$. Thus, we have established that 4-coloring of a square lattice is equivalent to a 21-vertex model (Fig. 4).

\begin{figure}
\centering
\includegraphics[width=1.0\textwidth]{21vertex.jpg}
\caption{21 vertex configurations corresponding to 4-coloring problem}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=0.8\textwidth]{sixvertex.jpg}
\caption{An illustrative instance showing equivalence between 3-coloring on a square lattice and six-vertex model. Here we have adopted the convention that if the state of an edge with respect to a vertex is 1(2), then we draw an arrow pointing towards(away from) that vertex.}
\end{figure}

\subsection{The $k$-coloring problem}\label{color}

 The generalization of the above scheme to $k$-coloring immediately follows. We number the colors as $\left\lbrace1,2,\ldots,k\right\rbrace$. We follow the same procedure for assigning edges states as for the 4 coloring problem but we replace the $\mod 4$ with $\mod k$ (For example edge 1 in Fig. 3 is assigned the state $(C-B)\mod k$ w.r.t. vertex $v$). By construction, the states of the edges will belong to the set $\mathcal{F}_k-\left\lbrace0\right\rbrace$, where $\mathcal{F}_k$ is a set such that
 \begin{equation*}
  \mathcal{F}_k=\left\lbrace0,1,2,\ldots,{k-1}\right\rbrace.
 \end{equation*}
 The states will then satisfy the following conditions:\\
 \begin{enumerate}

 \item If $v_1$ and $v_2$ are two vertices connected by an edge $e$, and $e_1$ and $e_2$ are the respective states of $e$ with respect to $v_1$ and $v_2$, then
 \begin{equation}\label{arrow}
 e_1+e_2=0\mod{k}
 \end{equation} where $e_1,e_2\in\mathcal{F}_k-\left\lbrace0\right\rbrace$.

 \item If $e_1,e_2,e_3$ and $e_4$ are the states (with respect to vertex $v$) of four edges emanating from the vertex $v$ (Fig. 3), then\begin{equation}\label{icecondition}
 e_1+e_2+e_3+e_4=0\mod{k}
 \end{equation}
 where $e_1,e_2,e_3,e_4\in\mathcal{F}_k-\left\lbrace0\right\rbrace$.
 \end{enumerate}
It is very easy to show that corresponding to every edge state configuration satisfying the above two conditions, there exists "$k$ possible $k$ coloring" of the faces.(Like in the case of 4 coloring, we can always find a unique color $X$($\neq A$) satisfying $(X-A)\mod k=e_1$, where $e_1\in\mathcal{F}_k-\left\lbrace0\right\rbrace$.)
 In fact, for $k=3$, the problem stated above is just the ice problem in disguise. To show how this works for the 3-coloring and associated six-vertex model, we show an example for illustrative purpose (Fig. 5).
 \subsubsection{The transfer matrix for open rows}
 The transfer matrix for the problem can be written in a similar manner as for the classic ice problem by Lieb. Consider two adjacent rows with $p$ lattice sites each, labelled $r_1$ and $r_2$ ($r_2$ above $r_1$). Let $\phi$ be a configuration of $p$ states of the row of vertical edges just below $r_1$ with respect to the corresponding lattice sites of $r_1$, and $\phi'$ be the configuration of $p$ states of the row just below $r_2$ with respect to the corresponding lattice sites of $r_2$. $B(\phi,\phi')$ is the number of ways of assigning states on the row of horizontal edges common to these two rows such that the conditions embodied in  \eqref{arrow} and \eqref{icecondition} are satisfied. We argue that it is possible to choose and fix configurations $\Phi(n)$ and $\Phi'(n)$ such that the state of the horizontal edge hanging out of the last lattice site of $\frac{\Phi'(n)}{\Phi(n)}$ will take the value $n$ and no other value, $n\in\mathcal{F}_k-\left\lbrace0\right\rbrace$ (refer to Fig. 4). Let $(a_i+b_i)\mod{k}=A_i$, $A_i\neq0\mod{k}$ for all $i$. The state of the second horizontal edge with respect to the second lattice site can have all possible states except $A_1$. The state of the third horizontal edge with respect to the third lattice site can have all possible states except $A_1+A_2$ and $A_2$. The state of the $i^{th}$ horizontal edge with respect to the $i^{th}$ lattice site can have all possible values except $(A_1+A_2+\ldots+A_{i-1}),(A_2+A_3+\ldots+A_{i-1}),\ldots,A_{i-1}$(all numbers are $\mod{k}$). Thus by suitably choosing the numbers $A_i$, it is possible to exclude $i-1$ states from the $i^{th}$ horizontal edge. Similarly, it is possible to exclude $i$ distinct states from the ${i+1}^{th}$ horizontal edge. Thus if $i=(k-2)$ and we suitably choose the numbers $A_i$, then we can exclude all states except $(k-n)$. Thus the state of the last horizontal edge in the figure with respect to the last lattice site can only have the state $n$, and our argument is complete.
 \begin{figure}
 \centering
 \includegraphics[width=0.7\textwidth]{drawing-5.jpg}
 \caption{Our premise for choosing $\Phi(n)=\left\lbrace a_1,a_2,\ldots a_i\right\rbrace$ and $\Phi'(n)=\left\lbrace b_1,b_2,\ldots,b_i\right\rbrace$ mentioned in the text}
 \end{figure}
 Define
 \begin{equation}
 A_n(\phi,\phi')=B(\Phi(n)\phi,\Phi'(n)\phi')
 \end{equation}
 which is the generalization of \eqref{dcmp}. Define $A_n(\phi,\phi')=0$ when $n=0\mod{k}$, because the state of an edge cannot be $0$ with respect to any vertex.
 $\Phi(n)\phi$ denotes configuration $\phi$ appended to $\Phi(n)$. The state of the last horizontal edge of $\frac{\Phi'(n)}{\Phi(n)}$ with respect to the first lattice site of $\frac{\phi'}{\phi}$ in $\frac{\Phi'(n)\phi'}{\Phi(n)\phi}$ is $-n\mod{k}=k-n$. As $n$ varies from $1$ to $k-1$, $k-n$ will vary from $k-1$ to $1$ and the state of the first horizontal edge of $\frac{\phi'}{\phi}$ with respect to the first lattice site of $\frac{\phi'}{\phi}$ will take all values in  $\mathcal{F}_k-\left\lbrace0\right\rbrace$ without any exclusion. Thus, the generalization of  \eqref{dcmp1} is
 \begin{equation}
 B(\phi,\phi')=\sum_{n=1}^{k-1}A_n(\phi,\phi').
 \end{equation}
 Let $\mathcal{L}_1=\left\lbrace1,2,\ldots,k-1\right\rbrace$. The set $\mathcal{L}_p$ for is constructed in the following manner: \\
 If $\mathcal{L}_p=\{ \phi_1,\phi_2,\ldots,\phi_{({k-1})^p}\} $, then
 \begin{equation*}
 \mathcal{L}_{p+1}=\{ 1\phi_1,1\phi_2,\ldots,1\phi_{({k-1})^p},2\phi_1,2\phi_2,\ldots,2\phi_{({k-1})^p},\ldots,(k-1)\phi_1,(k-1)\phi_2,\ldots,(k-1)\phi_{({k-1})^p}\}.
 \end{equation*}
 where $1\phi_1$ is a configuration of states of $p+1$ vertical edges such that the state of the first edge is $1$ and the rest are in configuration $\phi_1$, and so on.
 For the case $k=3$, the sets $\mathcal{L}_p$ are the same as those defined in Section \ref{cylindricalice} with $1$ replaced by $\uparrow$ and $2$ replaced by $\downarrow$. If $\phi_i, \phi_j$ are the $i^{th}$ and $j^{th}$ elements of $\mathcal{L}_p$, then let
 \begin{equation}
 A_{n_p}(i,j)=A_n(\phi_i,\phi_j).
 \end{equation}
 Thus $A_{n_p}$ is a $(k-1)^p\times(k-1)^p$ matrix. Consider the subdivision of the matrix $A_{n_{p+1}}$ into $(k-1)^2$ block matrices each of size $(k-1)^p\times(k-1)^p$.\\ The $(l,m)^{th}$ element of the $(i,j)^{th}$ block matrix is
 \begin{equation*}
 A_n(i\phi_l,j\phi_m)=A_{(-(k-n+k-j+i)\mod{k})}(\phi_l,\phi_m)=A_{[(n+j-i)\mod{k}]}(\phi_l,\phi_m)=A_{({(n+j-i)\mod{k})}_p}(l,m)
 \end{equation*}
 where $\phi_l,\phi_m \in \mathcal{L}_p$, and we have used  \eqref{arrow} and \eqref{icecondition}. Thus we get the following Toeplitz block structure
 \begin{equation}
 A_{n_{p+1}}=\begin{pmatrix}
 A_{n_p} & A_{{(n+1)}_p} & A_{{(n+2)}_p} & \ldots & \ldots & \ldots & \ldots & \ldots \\
 A_{{(n-1)}_p} & A_{n_p} & A_{{(n+1)}_p} & A_{{(n+2)}_p} & \ldots & \ldots & \ldots & \ldots \\
 A_{{(n-2)}_p} & A_{{(n-1)}_p} & A_{n_p} & A_{{(n+1)}_p} & A_{{(n+2)}_p} & \ldots & \ldots & \ldots \\
 \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\
 \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\
 \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\
 \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\
 \ldots & \ldots & \ldots & \ldots & \ldots & A_{{(n-2)}_p} & A_{{(n-1)}_p} & A_{n_p}
 \end{pmatrix},
 \end{equation}
 it being understood that the indices of the $A$ matrices are to be taken $\mod k$.

 \section{Graph-theoretical approach}

 Although graph-theoretical methods have been applied to the $k$-coloring problem (\cite{nagle,nagle1,avb}), the method we adopt for the $k$-coloring problem begins with the mapping between the $k$-coloring problem and the vertex model mentioned in  Section 2.4. Following  \cite{nagle}, $W_N$ is the number of ways of assigning states on the edges (of a very large two dimensional square lattice having $N$ lattice sites) consistent with the two rules \eqref{arrow} and \eqref{icecondition}:
 \begin{equation}
 W_N = \sum_{[\xi]}\prod_{i<j}A(\xi_i,\xi_j).
 \end{equation}
 $A(\xi_i,\xi_j)$ is the compatibility matrix relating two adjacent sites. $\xi_i$ and $\xi_j$ are the configurations at two adjacent vertices. $\sum_{[\xi]}$ denotes the "sum over all different combinations of $\xi$ arrangements at each vertex $i$, and $\prod_{i<j}$ is the product over nearest neighbours with each pair taken once" \cite{nagle}. If $e_1$ and $e_2$ are the states of the edge (with respect to the two lattice sites connected by it) common to the two adjacent sites having configuration $\xi_i$ and $\xi_j$, then
 \[A(\xi_i,\xi_j)=\begin{cases}
 1, & \text{if }e_1+e_2=0\mod{k} \\
 0, & \text{if }e_1+e_2\neq0\mod{k}
 \end{cases}
 \]

 The number of configurations ($M_k$, say) that a vertex can have is (here $|S|$ denotes the number of elements in set $S$)
 \begin{eqnarray*}
 M_k &=&\vert\left\lbrace(a_1,a_2,a_3,a_4):a_1+a_2+a_3+a_4=0\mod{k},a_1,a_2,a_3,a_4\in\mathcal{F}_k-\left\lbrace0\right\rbrace\right\rbrace\vert \nonumber \\
 &=&\vert\left\lbrace(a_1,a_2,a_3):a_1,a_2,a_3\in\mathcal{F}_k-\left\lbrace0\right\rbrace\right\rbrace\vert \nonumber \\ &-&  \vert\left\lbrace(a_1,a_2,a_3):a_1+a_2+a_3=0\mod{k},a_1,a_2,a_3\in\mathcal{F}_k-\left\lbrace0\right\rbrace\right\rbrace\vert
\nonumber \\
 &=& (k-1)^3-[(k-1)^2-\vert\left\lbrace(a_1,a_2):a_1+a_2=0\mod{k},a_1,a_2\in\mathcal{F}_k-\left\lbrace0\right\rbrace\right\rbrace\vert].
 \end{eqnarray*}
 So,
 \begin{equation}
 M_k=(k-1)^3-(k-1)^2+(k-1).
 \end{equation}
 Thus the Pauling estimate for the $k$-coloring problem is $\frac{M_k}{(k-1)^2}$ and $\sum_{[\xi]}$ means sum over all possible $M_k^N$ configurations of $N$ lattice sites.
 We do the following transformation
 \begin{equation}\label{condition1}
 W_N=\sum_{[\xi]}\prod_{i<j}(C+A(\xi_i,\xi_j)-C)=(M_kC^2)^N\sum_{[\xi]}\prod_{i<j}\frac{1}{\sqrt{M_k}}(1+a(\xi_i,\xi_j))
 \end{equation}
 where
 \begin{equation*}
 a(\xi_i,\xi_j)=\frac{1}{C}(A(\xi_i,\xi_j)-C).
 \end{equation*}
 Every term in the expansion of \eqref{condition1} can be assigned a graph (\cite{stillinger,nagle}). To cancel contributions from all open-ended graphs (\cite{stillinger,nagle}), the following condition must be satisfied
 \begin{equation}\label{condition}
 \sum_{\xi_i(\text{or } \xi_j)}a(\xi_i,\xi_j)=0.
 \end{equation}
 If we fix $\xi_i$, then the number of possible $\xi_j$'s that will be compatible with $\xi_i$ is (where $b$ is the state of the edge connecting $\xi_i$ and $\xi_j$ with respect to the vertex $\xi_i$ and $a_1, a_2, a_3$ are the states of three of the four edges emanating from $\xi_j$ other than that connecting $\xi_i$ and $\xi_j$)
 \begin{eqnarray*}
 &~&\vert \left\lbrace (a_1,a_2,a_3):a_1+a_2+a_3=b\mod{k}, a_1,a_2,a_3 \in \mathcal{F}_k- \left\lbrace 0 \right\rbrace \right\rbrace\vert
 \nonumber \\
 &=&\vert\left\lbrace(a_1,a_2):a_1,a_2\in\mathcal{F}_k-\left\lbrace0\right\rbrace\right\rbrace\vert-\vert\left\lbrace a_1+a_2=b\mod{k}, a_1,a_2\in\mathcal{F}_k-\left\lbrace0\right\rbrace\right\rbrace\vert
 \nonumber \\
 &=& (k-1)^2 - (k-2).
 \end{eqnarray*}

 \begin{figure}
 \centering
 \includegraphics[width=0.5\textwidth]{drawing.jpg}
 \caption{\label{fig:noneulerian}Three incident edges at the vertex having configuration $\xi_i$($e_j,e_l,e_m$ are the respective edge states with respect to vertices having configuration $\xi_j,\xi_l,\xi_m$ respectively).}
 \end{figure}

 Since the ones in $A(\xi_i,\xi_j)$ become $\frac{1-C}{C}$ in $a(\xi_i,\xi_j)$ and the zeros become $-1$,  \eqref{condition} gives
 \begin{equation*}
 \left(\frac{1-C}{C}\right)[(k-1)^2-(k-2)]-(M_k-(k-1)^2+(k-2))=0.
 \end{equation*}
 Letting $k-1=x$, the equation written above simplifies to \begin{equation*}
 \frac{1}{C}=x=k-1
 \end{equation*}
 and \begin{equation*}
 \frac{1-C}{C}=x-1=k-2
 \end{equation*}
 and thus we get the following
 \[a(\xi_i,\xi_j)=\begin{cases}
 (k-2), & \text{if }\xi_i \text{ and } \xi_j \text{ are compatible,} \\
 -1, & \text{if } \xi_i \text{ and } \xi_j \text{ are not compatible.}
 \end{cases}
 \]
 \subsection{Non-Eulerian cycles}
  We examine whether a generalization of a statement in \cite{nagle} that the contribution of non-Eulerian graphs, i.e., graphs having one or three incident edges at a vertex(\cite{nagle,berge}) have zero contribution, holds for a general $k$ or not. Graphs having one incident edge at a vertex have zero contribution because requirement \ref{condition} has already been fulfilled. Thus what remains to be examined(for a general $k$) is the value of the following expression for three incident edges
  \begin{equation*}
 \sum_{\xi_i}a(\xi_i,\xi_j)a(\xi_i,\xi_l)a(\xi_i,\xi_m).
 \end{equation*}
 For the sake of notation, let (refer to Fig. \ref{fig:noneulerian}) $e_j=l_1$, $e_m=l_2$ and $e_l=l_3$. We have the following statements ($a_1, a_2, a_3$ are the states of the three edges connecting $\xi_i$ with $\xi_j, \xi_m, \xi_l$ with respect to the lattice site having configuration $\xi_i$, $a$ is the state of the remaining edge).
 Note that in the statements that follow, $a_i \in\mathcal{F}_k-\left\lbrace 0,(k-l_{i})\right\rbrace$, $a\in\mathcal{F}_k-\left\lbrace0\right\rbrace$.

 \begin{enumerate}
 \item  Number of configurations $\xi_i$ that are compatible with all three lattice sites is $1$ if $l_1+l_2+l_3\neq 0 \mod{k}$ and is $0$ otherwise.
 \item Number of configurations that are compatible with any two of the three lattice sites, and not with the third one(say the one out of which $l_3$ is protruding) is
 \begin{equation*}
 \vert\left\lbrace(a_3,a):a_3+a=l_1+l_2\mod{k}\right\rbrace\vert
 =(k-2)-\vert\left\lbrace a_3:a_3=l_1+l_2\mod{k}\right\rbrace\vert.
 \end{equation*}
 \item Number of configurations that are compatible with only one lattice site(say the one out of which $l_1$ is protruding) is
 \begin{eqnarray*}
 \vert\{ (a_2,a_3,a)&:&a_2+a_3+a=l_1\mod{k}\}\vert
 \nonumber \\
 &=&(k-2)^2-\vert\left\lbrace a_2+a_3=l_1\mod{k}\right\rbrace\vert
 \nonumber \\
 &=& (k-2)^2-[(k-2)-\vert\left\lbrace a_2:a_2=l_1\mod{k} \text{ or } a_2=l_1+l_3\mod{k}\right\rbrace\vert].
 \end{eqnarray*}
 \item Number of configurations that are compatible with none of the three lattice sites are
 \begin{eqnarray*}
 &~&\vert \{ (a_1,a_2,a_3,a):a_1+a_2+a_3+a = 0\mod{k}\} \vert
 =(k-2)^3-[(k-2)^2 \nonumber \\ &-&[(2(k-2)-\vert\left\lbrace a_1=l_2\mod{k}\right\rbrace\vert-\vert\left\lbrace a_1=l_3\mod {k}\text{ or }a_1=l_2+l_3\mod{k}\right\rbrace\vert]].
 \end{eqnarray*}
 \end{enumerate}
 One can easily verify by the statements listed above that for the case $l_1+l_2+l_3=0\mod{k}$
 \begin{equation*}
 \sum_{\xi_i}a(\xi_i,\xi_j)a(\xi_i,\xi_l)a(\xi_i,\xi_m)=(k-2)-2(k-2)^2-(k-2)^3+2.
 \end{equation*}
 which is zero for $k=3$, which is Nagle's \cite{nagle} result, but for $k>3$, it is not zero.

 \subsection{Elementary Eulerian Cycles}

 Our next step is to compute the following
 \begin{equation*}
 \sum_{\xi_2, \xi_3, \ldots, \xi_{i-1}} a(\xi_1,\xi_2)a(\xi_2,\xi_3)\ldots a(\xi_{i-1},\xi_i) = a^{i-1}(\xi_1, \xi_i).
 \end{equation*}
 We use the symbol $a(\xi_i\leftrightarrow\xi_j)$ for $a(\xi_i, \xi_j)$, if $\xi_i$ and $\xi_j$ are compatible, otherwise we use $a(\xi_i \neq  \xi_j)$. The entries in the compatibility matrix $a$ clearly depend on the compatibility of the two adjacent sites, and the same is true for the higher powers of $a$. Thus we don't need to worry about what $\xi_i$ and $\xi_j$ are in $a(\xi_i \leftrightarrow \xi_j)$ or $a(\xi_i \neq \xi_j)$. We have the following recursion relation:
 \begin{eqnarray}
 a^i(\xi_i\leftrightarrow\xi_j) &=& \sum_{\xi_k}a^{i-1}(\xi_i,\xi_k)a(\xi_k,\xi_j) \nonumber \\
 &=&(k-1)a^{i-1}(\xi_1 \leftrightarrow \xi_2) a(\xi_1 \leftrightarrow \xi_2) + (k-2)^2 a^{i-1} (\xi_1 \leftrightarrow \xi_2) a(\xi_1 \neq \xi_2) \nonumber \\ &+& (k-2)^2 a^{i-1}(\xi_1 \neq \xi_2) a(\xi_1 \leftrightarrow \xi_2) + [(k-2)^3+(k-2)]a^{i-1}(\xi_1\neq\xi_2)a(\xi_1\neq\xi_2)\nonumber \\
 &=& (k-2)[a^{i-1}(\xi_1\leftrightarrow\xi_2)-a^{i-1}(\xi_1\neq\xi_2)].
 \end{eqnarray}
 Similarly, we have
 \begin{equation}
 a^i(\xi_1\neq\xi_2)=-(a^{i-1}(\xi_1\leftrightarrow\xi_2)-a^{i-1}(\xi_1\neq\xi_2))
 \end{equation}
 Fortunately, the recursion can be solved easily without resorting to any matrix method, and we get
 \begin{eqnarray*}
 a^i(\xi_1\leftrightarrow\xi_2) &=& (k-1)^{i-1}(k-2)
 \nonumber \\
 a^i(\xi_1\neq\xi_2) &=& -(k-1)^{i-1}
 \nonumber \\
 {\rm Tr}[a^i] &=& (k-1)^2a^i(\xi_1\leftrightarrow\xi_2)+[M_k-(k-1)^2]a^i(\xi_1\neq\xi_2)
\nonumber \\
 &=& (k-2)(k-1)^i.
 \end{eqnarray*}
 And so the contribution of elementary Eulerian cycle having $n$ vertices is
\begin{equation*}
\frac{Tr[a^n]}{M_k^n}=\frac{(k-2)(k-1)^n}{M_k^n}.
\end{equation*}
At large values of $k$, their contribution goes as $\mathcal{O}(1/k^{2n-1})$.

\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{drawing-6-5.jpg}
\caption{Lowest order non-zero correction to Pauling type estimate for the $k$-coloring problem is due to elementary Eulerian cycle having $4$ vertices, which is a square.}
\end{figure}

For any cycle, we can say that the contribution of that cycle must go as $\mathcal{O}(1/k^n)$ (for some $n>0$), because if it were not so, the asymptotic relation, $W(k) \sim k$ for large $k$  \cite{nagle1} would not hold good. Thus, at large values of $k$, the mean field approximation (which is Pauling's estimate) dominates (refer also to Fig. 8): \begin{equation}
W(k) \approx \frac{M_k}{(k-1)^2}(1+\frac{(k-2)(k-1)^4}{M_k^4})\approx\frac{(k-1)^3-(k-1)^2+(k-1)}{(k-1)^2}.
\end{equation}
One can see that the above approximation for $k = 4, 5, 6, 7$ agrees well with the values given in \cite{nagle1}.
Calculating the general algebraic expressions for contributions due to complicated cycles is tricky and can be another avenue of investigation.

\section{Summary}

We have established the connection between $k$-coloring problem of the square lattice and a vertex model which reduces to the ice-type model for $k = 3$. We have, for instance, explicitly shown that 4-coloring problem is in correspondence with a 21-vertex model. We have defined a transfer matrix for the $k$-coloring problem and showed its Toeplitz block structure for the non-periodic boundary conditions.

We have also calculated Lieb's square ice constant for cylindrical chain. Further, applying graph-theoretical methods to the vertex model corresponding to the $k$-coloring problem, we have shown  that the generalized Pauling estimate dominates for large values of $k$.

\section*{Appendix}

\noindent
{\bf Analytical results for some finite models}

 We present some simple analytical results for models that remain finite in one of the dimensions using theorems stated in Section 2.2.

\subsubsection*{A. ~$2\times p$ cylindrical lattice}

The number of ways, $Z_{2p}$ is

\begin{eqnarray}
Tr[B_p^2] &=& Tr[A_p^2+A_pA_p^T+A_p^TA_p+{A_p^T}^2] \nonumber \\ &=& 2(Tr[A_p^2]+Tr[A_pA_p^T]) = 2(2^p+3^p).
\end{eqnarray}
Thus, the maximum eigenvalue here is
\begin{equation}
\lim_{p\rightarrow\infty}Z_{2p}^{1/{2p}}=\sqrt{3}\approx 1.732 \ldots
 \end{equation}

 \subsubsection*{B. ~$3\times p$ cylindrical lattice}\label{3p}

The number of ways $Z_{3p}$ is
\begin{eqnarray}
Tr[B_p^3] &=& Tr[A_p^3+{A_p^T}^3+A_p^2A_p^T+A_pA_p^TA_p+A_p^TA_p^2+A_p{A_p^T}^2+A_p^TA_pA_p^T+{A_p^T}^2A_p] \nonumber \\ &=& 2Tr[A_p^3]+6Tr[A_p^2A_p^T].
\end{eqnarray}
Thus by using the two theorems, we get

\begin{equation}
Tr [B_p^3]=2^{p+1}+6\times 4^p.
\end{equation}
In this case, the maximum eigenvalue is
 \begin{equation}
 \lim_{p\rightarrow\infty}Z_{3p}^{1/{3p}}=4^{1/3}\approx1.5874.
 \end{equation}

Evaluating $Z$ for $m \times p $ lattices for $m > 3$  is possible in principle and we get coupled recursion while evaluating terms like $Tr[A_p^2{A_p^T}^2]$ and in general, terms like $Tr[A_p^{m_1}{A_p^T}^{m_2}A_p^{m_3}\ldots]$.  The coefficients of these coupled recursion become difficult to predict  analytically for very large $m$. We present the evaluation for a $4\times p$ lattice as an illustration.

\subsubsection*{C.~$4 \times p$ cylindrical lattice
}
Before embarking on $Z_{4p}$, we evaluate $Tr[A_p^2{A_p^T}^2]$.
 \begin{eqnarray*}
 A_{p+1}^2{A_{p+1}^T}^2 &=& \begin{pmatrix}
 A_p^2 & A_pA_p^T+A_p^TA_p\\
 0 & A_p^2
 \end{pmatrix}
 \begin{pmatrix}
 {A_p^T}^2 & 0\\
 A_pA_p^T+A_p^TA_p & {A_p^T}^2
 \end{pmatrix} \nonumber \\ \\
 &=& \begin{pmatrix}
 Y & A_p{A_p^T}^3+A_p^TA_p{A_p^T}^2\\
 A_p^3A_p^T+A_p^2A_p^TA_p & A_p^2{A_p^T}^2
 \end{pmatrix}
 \end{eqnarray*}
 where
\begin{equation*} Y=A_p^2{A_p^T}^2+A_pA_p^TA_pA_p^T+A_p{A_p^T}^2A_p+A_p^TA_p^2A_p^T+A_p^TA_pA_p^TA_p.
\end{equation*}
Thus we get
\begin{equation}\label{coupled1}
 Tr[A_{p+1}^2{A_{p+1}^T}^2]= Tr[Y]+Tr[A_p^2{A_p^T}^2]\\
 =4Tr[A_p^2{A_p^T}^2]+2Tr[A_pA_p^TA_pA_p^T].
\end{equation}
We also have
 \begin{eqnarray*}
 A_{p+1}A_{p+1}^TA_{p+1}A_{p+1}^T &=& \begin{pmatrix}
 A_p & A_p^T \\
 0 & A_p
 \end{pmatrix}
 \begin{pmatrix}
 A_p^T & 0\\
 A_p & A_p^T
 \end{pmatrix}
 \begin{pmatrix}
 A_p & A_p^T \\
 0 & A_p
 \end{pmatrix}
 \begin{pmatrix}
 A_p^T & 0\\
 A_p & A_p^T
 \end{pmatrix}
\nonumber \\ \\
 &=&\begin{pmatrix}
 A_pA_p^T+A_p^TA_p & {A_p^T}^2 \\
 A_p^2 & A_pA_p^T
 \end{pmatrix}
 \begin{pmatrix}
 A_pA_p^T+A_p^TA_p & {A_p^T}^2 \\
 A_p^2 & A_pA_p^T
 \end{pmatrix}
 \end{eqnarray*}
 Thus
 \begin{equation*}
Tr[A_{p+1}A_{p+1}^TA_{p+1}A_{p+1}^T] = Tr[(A_pA_p^T+A_p^TA_p)^2+{A_p^T}^2A_p^2]+Tr[A_p^2{A_p^T}^2+A_pA_p^TA_pA_p^T]
 \end{equation*}
 \begin{equation}\label{coupled2}
 =3Tr[A_pA_p^TA_pA_p^T]+4Tr[A_p^2{A_p^T}^2].
 \end{equation}
 Letting $x_p=Tr[A_p^2{A_p^T}^2]$ and $y_p=Tr[A_pA_p^TA_pA_p^T]$, Equations \ref{coupled1} and \ref{coupled2} reduce to the following coupled recursion
 \begin{equation*}
 x_0,y_0=1
 \end{equation*}
 \begin{equation*}
 x_{p+1}=4x_p+2y_p
 \end{equation*}
 \begin{equation}
 y_{p+1}=4x_p+3y_p.
 \end{equation}
 which is the same as
 \begin{equation*}
 \begin{pmatrix}
 x_{p+1}\\
 y_{p+1}
 \end{pmatrix} =
 \begin{pmatrix}
 4 & 2\\
 4 & 3
 \end{pmatrix}
 \begin{pmatrix}
 x_p\\
 y_p
 \end{pmatrix}
 \end{equation*}
 and we get
 \begin{equation}
 \begin{pmatrix}
 x_p \\
 y_p
 \end{pmatrix}=
 \begin{pmatrix}
 4 & 2\\
 4 & 3
 \end{pmatrix}^p
 \begin{pmatrix}
 1\\
 1
 \end{pmatrix}
 \end{equation}
 The $p^{th}$ power was calculated using MATHEMATICA and (since $\frac{7+\sqrt{33}}{2}$ and $\frac{7-\sqrt{33}}{2}$ are the eigenvalues of the matrix) we get the following
 \begin{equation*}
 \begin{pmatrix}
 x_p\\
 y_p
 \end{pmatrix}
 =\begin{pmatrix}
 a_1(\frac{7+\sqrt{33}}{2})^p+a_2(\frac{7-\sqrt{33}}{2})^p\\
 b_1(\frac{7+\sqrt{33}}{2})^p+b_2(\frac{7-\sqrt{33}}{2})^p
 \end{pmatrix}
 \end{equation*}
 where $a_1,a_2,b_1,b_2$ are constants independent of $p$.
 The $Z_{4p}$ for the lattice is given by
 \begin{equation*}
 Tr[B_p^4]=Tr[(A_p+{A_p^T})^4]=2Tr[A_p^4]+8Tr[A_p^3A_p^T]+4Tr[A_p^2{A_p^T}^2]+2Tr[A_pA_p^TA_pA_p^T].
 \end{equation*}
 and thus \begin{equation}
 \lim_{p\rightarrow\infty}Z_{4p}^{1/{4p}}=(\frac{7+\sqrt{33}}{2})^{1/4} \approx 1.589.
 \end{equation}
 \subsubsection*{D.~Open Lattice}
 The number of ways $Z$ for open lattice is\begin{equation}
 Z=\sum_{\phi_{1}}\ldots \sum_{\phi_{m}}B(\phi_1,\phi_2)B(\phi_2,\phi_3)\ldots B(\phi_{m-1},\phi_m)=\sum_{\phi_1,\phi_m}B^{m-1}(\phi_1,\phi_m).
 \end{equation}
 Calculating $Z_{m\times p}$ for finite $m$ is still possible in principle by constructing recursive formula for sum of the elements of matrix $B_p^{m-1}$ similar to the way it is done for cylindrical lattice, but for large values of $m$, it becomes too involved.

\section*{Acknowledgements}
SRJ is very grateful to John William Turner for many illuminating discussions on mathematical physics during his visits to the Universit\`{e} Libre de Bruxelles, Belgium. One of those discussions focussed on iterative Block matrices and their possible connection with vertex models.
This work was carried out when one of the authors (SKS) was visiting SRJ under the Summer Research Fellowship Programme organized by The Indian Academy of Sciences, The Indian National Science Academy and The National Academy of Sciences, India. SKS would like to thank the Academies for the support.

config: arxiv


TITLE: Why don't astronauts in orbit get stuck to the "ceiling"?
QUESTION [7 upvotes]: When a shuttle is in orbit, it is essentially rotating around the "centre" of the Earth at a great speed. So why does there seem to be no centrifugal force sticking them to the 'ceiling' of the shuttle?
Is it because the shuttle is not actually being rotated around a point but rather continuously falling or something else?
Thanks

REPLY [0 votes]: The Shuttle (or the ISS for a better example since the Shuttle isn't flying any more) isn't rotating at a great speed...it's rotating about once every 90 minutes, once every orbit. This does have an effect, but a very small one.
Its motion around the Earth doesn't produce any such effect because, as you guessed, it and everything in it are in free fall around Earth and are affected nearly equally by Earth's gravity (the very small differences due to different distances from Earth do produce tidal forces).


TITLE: Why are the Lyapunov and Lindeberg Central Limit Theorem conditions often satisfied in the real world?
QUESTION [6 upvotes]: Some background for the question.
I've been trying to understand why so many things have a Gaussian Distribution. There are a lot of questions about this on StackExchange but none of them were answered in sufficient detail to satisfy me.
First, I know often times people model phenomenal as Gaussian when they are not to make the math easier. I am not asking about these. I am wondering why so many phenomena actually are Gaussian or approximately Gaussian.
Second, people often say a Gaussian satisfies maximal entropy because energy is conserved and is quadratic (E=.5*mv^2). However, this only means that velocity distributions for systems in thermal equilibrium are Gaussian. However, many things besides velocity such as human height are also Gaussian in the real world.
Third, the Central Limit Theorem is often put as an explanation. People claim that the sum of independent random variables tends to have a Gaussian Distribution so long as it satisfies certain conditions. I believe they are referring to the Lyapunov and Lindeberg variants of the Central Limit Theorem.
Which brings me to my actual question: Why are the conditions of the Lyapunov and Lindeberg Central Limit Theorem often satisfied in the real world?

REPLY [2 votes]: There are many ways of looking at this problem. I think it can be broken up into a few separate but related questions:

Why do many things appear approximately normal? For example human height isn't normally distributed, but it still seems well-approximated by a normal distribution.
Does the CLT actually apply to most real-world distributions?
What is so special about maximum entropy distributions anyway?

I'll try to answer these questions. Let's start with 3. There are different schools of thought in probability; the subjectivist interpretation says that distributions are merely a reflection of our belief or uncertainty in something. If I say I am thinking of an integer between 1 and 10 and ask you to guess what it is, your degree of belief as to what number it is might be, for example, a uniform distribution. Given that you don't know anything else about it, the uniform distribution would be the best choice (it would give you the highest probability of being right). However, you might exploit the fact that humans aren't good random number generators, and so a distribution that weighs 5 or 6 higher than 1 might give you a better chance of winning. The point to all this is that distributions (according to subjectivism) represent your degree of belief, and nothing more.
As it so happens, the distribution with the maximum entropy given your knowledge about something is the one that gives you the highest probability of being right. And if you know nothing else about some measurement/number except that it follows these rules:

It is a real number.
It is not bounded from below or above.
It has an average value.
It has a certain degree of variance around this average value.

Then the distribution that gives you the highest chance of being right is the normal distribution. A lot of the time, you can even relax some of these assumptions. For example, if it's bounded, but the bounds are much larger than the variance (human height and weight would be good examples here), then the resulting maximum entropy distribution might be a truncated normal distribution, which looks pretty close to a normal distribution.
Which brings us to question 1. Why do so many distributions that aren't normal still appear approximately normal? For example, the Cauchy, Weibull, Student's t, and log-normal distributions all look approximately normal, for certain parameter values.
The best explanation I can think of for this is that they are all the maximum entropy distribution given some constraints, and the constraints are often similar to the constraints that give the normal distribution, so their shapes can wind up being similar to the normal distribution.
Note that just these few distributions together cover a huge range of systems. For example, the CLT says that if you have a bunch of different independent random variables and you sum them, you get something that looks normal. But if instead of adding, you multiply them, you get the log-normal! Which itself looks 'pretty close' to normal, especially if you only had a few sample measurements to go on.
Now finally, question 2. As others have pointed out, the CLT does seem to apply to a lot of real-world problems, but that's actually not that critical. Even if some of the assumptions of the CLT are relaxed a bit, the resulting distributions still come out looking normal. For example, even if the random variables that are summed are not completely independent, the sum can still come out looking normal, as long as there is some degree of randomness or uncertainty in the random variables. This is certainly the case for human height - the genes controlling height all have very inter-related effects. But the result still comes out looking very close to normal.


TITLE: Bundle Isomorphism Between The Tautological Bundle Of $G_1(\mathbb{R}^2)$ And The Mobius Bundle
QUESTION [1 upvotes]: Show that the tautological vector bundle over $G_1(\mathbb{R}^2)$ is smoothly isomorphic to the Mobius bundle

Recall that the tautological vector bundle over the Grassmanian $G_k(V)$ is the smooth rank-$k$ vector bundle of the form $T = \{(S,v) \in G_k(V) \times V | v \in S\}$, which has the property that the fibre over a point $S \in G_k(V)$ is isomorphic as a vector space to $S$.
I have a proof attempt below but I think the proof is wrong because it is not using any of the structures or properties specific to the tautological bundle or the Mobius bundle. It seems like the proof can be adapted to any two line bundles with homeomorphic base spaces:
Proof Attempt:
Let $T$ be the tautological bundle of $G_1(\mathbb{R}^2)$ and $E$ be the Mobius bundle. Note that by definition, $G_1(\mathbb{R}^2) = \mathbb{RP}^1$. Let $f$ be the homeomorphism between $\mathbb{RP}^1$ and $S^1$. Let $S \in \mathbb{RP}^1$. Then $\pi^{-1}_T(S) \cong S$ as vector spaces, since $T$ is the tautological bundle of $\mathbb{RP}^1$. Since $S$ is a $1$-dimensional subspace of $\mathbb{R}^2$, there is a single basis vector $s$ which spans $S$. Hence, every $v \in S$ can be written in the form $v = a_vs$, for some $a_v \in \mathbb{R}$. Now $f(S) \in S^1$, and so let $R = \pi^{-1}_E(f(S)$. Then since the Mobius bundle is a line bundle, $R$ is a $1$-dimensional vector space and thus there is a single basis vector $r$ which spans $R$. Hence, any $u \in \pi^{-1}_E(f(S))$ can be written in the form $u = b_ur$, for some $b_u \in \mathbb{R}$. Since $S$ and $R$ are vector spaces with the same dimension, there is an isomorphism between them. Hence, for every $v = a_vs \in S$, there is a unique linear correspondence to a vector $u = b_ur \in R$. Since every point of $T$ lies in the fibre of some point in $\mathbb{RP}^1$, define the following map fibre-wise:
\begin{gather*}
F: T \rightarrow E \\
v = a_vs \in \pi^{-1}_T(S) \mapsto u = b_ur \in \pi^{-1}_E(f(S))
\end{gather*}
Due to the isomorphism between $\pi^{-1}_T(S)$ and $\pi^{-1}_E(f(S))$, $F$ is a bijection and is linear when restricted to each fibre. What remains to show is that $F$ is smooth, which shouldn't be hard since $F$ is smooth at least between each fibre and hence should be smooth using the charts of $T$ and $E$.
End Of Proof Attempt
I would like to know whether this proof can be saved, what is going wrong with this proof, and what a better approach to this problem would be.

REPLY [1 votes]: Let $E\to M$ and $F\to M$ be vector bundles. This answer suggests ways to define bundle morphisms $E\to F$. The "iso" issue is less significant, as a bundle morphism is an isomorphism if and only if it is iso on each fiber, and the latter is usually easy to confirm.
First suggestion - relying on extra structure: As I wrote in my comment, there are many different ways to map a fiber of $E$ into a fiber of $F$. Sometimes, however, the base manifold and the bundles carry extra structure that can be used to specify a morphism. A basic example is using a Riemannian metric to construct an isomorphism between a bundle and its dual over a smooth manifold. Put simply, an inner product on a (real) vector space $V$ gives rise to a "natural" isomorphism between $V$ and $V^*$. Hence, if the bundle $E$ is equipped with a fiber metric, this can be used to identify $E$ with its dual, $E^*$. The fact that the metric changes continuously (or smoothly) along the base manifold guarantees that so does the isomorphism it yields.
Second suggestions - trivializations and transition maps: Let $\{U_\alpha\}_{\alpha\in I}$ be an open cover of $M$ which trivializes both $E$ and $F$. Let $\varphi^E_{\alpha\beta}$ and $\varphi^F_{\alpha\beta}$ denote the transition maps. This means that over both $U_\alpha$ and $U_\beta$ we identify $E$ with the trivial bundle, and we glue $E|_{U_\alpha}$ to $E|_{U_\beta}$ using $\varphi^E_{\alpha\beta}$: for a point $x\in U_\alpha\cap U_\beta$ and a vector $v\in\mathbb{R}^k,\; k$ being the rank of $E$, we declare that $(x,v)$ as a point in $E|_{U_\alpha}$ is identical to $(x,\varphi^E_{\alpha\beta}(x)\cdot v)$ as a point in $E|_{U_\beta}$. The same goes for $F$ and the $\varphi^F_{\alpha\beta}$'s. Then, constructing a bundle morphism $E\to F$ amounts to specifying a linear map $L_\alpha(x):\mathbb{R}^k\to\mathbb{R}^k$ over every point in each of the $U_\alpha$'s and making sure that these maps agree on the intersections. "Agree" means that for $x\in U_\alpha\cap U_\beta$ we have $$\varphi^F_{\beta\alpha}(x)\circ L_\beta(x)\circ\varphi^E_{\alpha\beta}(x)=L_\alpha(x).$$
Now, in your case this shouldn't be so hard to do, as your base manifold is a circle. This means that you can cover it by two open sets over which every vector bundle is trivial. Moreover, you are working with line bundles, and so, all linear maps involved are just multiplication by scalars.


TITLE: Possible matrix-determinant identity
QUESTION [1 upvotes]: Is $$\det(I+ ABB^*A^*C^{-1})=\det(I+ B^*A^*ABC^{-1})$$
where $I$ is identity matrix, $A,B,C$ are complex valued matrices. And $C$ is $(I+X)$ where $X$ is PSD.
I know that this makes $ABB^*A^*$ and $B^*A^*AB$ positive semi/definite. And I know for square matrices $X,Y,Z$ we have $\det(XYZ)=\det(YXZ)$ so $\det (ABB^*A^*C^{-1})=\det(B^*A^*ABC^{-1})$. And also $\det (I + ABB^*A^*C^{-1})=\det(I + B^*A^*ABC^{-1})$. Please comment if this is correct. I have a feeling I'm missing something since I didn't use properties of $C$.
Simulations seem to hold. At least when I used $A=\pmatrix{1&1\\ 0&0},\ B=I$ and $C=\pmatrix{2&0\\ 0&2}$ gave 2 in both sides.
Thanks a lot in advance.
PS. Not home work.

REPLY [2 votes]: Your test example is too specific: $B = I$, $C = 2I$, $C^{-1} = (1/2)I$. Of course that everything here commutes.
I tried the following random one (in Python3):
import numpy as np

A = np.array([[3,2,6],[4,1,5]])
B = np.array([[1,2],[3,4],[5,6]])
C = np.array([[2,1],[1,3]])

AB = np.dot(A, B)
Cinv = np.linalg.inv(C)

M1 = np.identity(2) + np.dot(np.dot(AB, AB.transpose()), Cinv)
M2 = np.identity(2) + np.dot(np.dot(AB.transpose(), AB), Cinv)
print("A =\n", A)
print("B =\n", B)
print("AB =\n", AB)
print("C =\n", C)
print("C^{-1} =\n", Cinv)
print("M1 =\n", M1)
print("M2 =\n", M2)
print("det M1 =", np.linalg.det(M1))
print("det M2 =", np.linalg.det(M2))

The output says that your statement is wrong:
A =
 [[3 2 6]
 [4 1 5]]
B =
 [[1 2]
 [3 4]
 [5 6]]
AB =
 [[39 50]
 [32 42]]
C =
 [[2 1]
 [1 3]]
C^{-1} =
 [[ 0.6 -0.2]
 [-0.2  0.4]]
M1 =
 [[ 1744.    535. ]
 [ 1451.2   446.6]]
M2 =
 [[  869.2   808.6]
 [ 1123.6  1047.8]]
det M1 = 2478.4
det M2 = 2204.8

Your proof is wrong because
$$\det\left( \prod_k M_k \right) = \det\left( \prod_k M_{p(k)} \right),$$
for all permutations $p$, but, generally,
$$\det\left( I + \prod_k M_k \right) \ne \det\left( I + \prod_k M_{p(k)} \right).$$
Even if you limit $A$ and $B$ to be square, the statement won't hold. For example, remove the third column/row from $A$ and $B$ above:
A = np.array([[3,2],[4,1]])
B = np.array([[1,2],[3,4]])
C = np.array([[2,1],[1,3]])

The result is:
det M1 = 172.0
det M2 = 151.0

As user1551 told you: try some random example first. Not "nice" ones like your example above, but completely random ones. If a statement is wrong, chances are that a random test will sink it.


TITLE: Subject of the equation
QUESTION [2 upvotes]: I have a homework question which I don't know if my solution is correct
I need to isolate $l$ to one side of the equation
$$M = \frac w2 (L - l^2)$$
MY SOLUTION
$2M = w (L - l^2)$
$2M = Lw - wl^2$
$wl^2 = Lw - 2M$
$l^2 = \frac{Lw - 2M}w$
$l = \sqrt{\frac{Lw - 2M}w}$
Thanks

REPLY [1 votes]: Your solution is OK, but I think you should rewrite the last term of the solution as: $$l = +\sqrt{\frac{Lw - 2M}w} \lor l = -\sqrt{\frac{Lw - 2M}w}$$


TITLE: Evaluating $\lim_{n \to \infty} \left ( \sqrt[n]{n} + \frac 1 n \right )^{\frac n {\ln n}}$
QUESTION [1 upvotes]: I have trouble evaluating this limit:
$$\lim_{n \to \infty} \left ( \sqrt[n]{n} + \frac 1 n \right )^{\frac n {\ln n}}$$
I cannot use series expansion... I also tried to rewrite it as $\large e^{\ln (\cdots)}$, without getting anywhere. It's the $\sqrt[n]{n}$ factor that troubles me the most. I can't get rid of it.

REPLY [2 votes]: Use the fact that if $a_n \rightarrow a$ then
$$\left(1+\frac{a_n}{n}\right)^n \rightarrow e^a$$
We write our expression as
$$\left(\sqrt[n]{n}+\frac{1}{n}\right)^{\frac{n}{\ln n}}=\left(1+\frac{n(\sqrt[n]{n}-1)+1}{n}\right)^{\frac{n}{\ln n}}=
\left(1+\frac{a_n}{n/\ln n}\right)^{\frac{n}{\ln n}}$$
where
$$a_n=\frac{n(\sqrt[n]{n}-1)+1}{\ln n}$$ so it is reduced to finding this last limit.
$\frac{1}{\ln n}\rightarrow 0$ so we want the limit of $\frac{n(\sqrt[n]{n}-1)}{\ln n}$
But this follows immediately from
$$\lim\limits_{x\rightarrow 0} \frac{e^x-1}{x}=1$$ let $x=\frac{\ln n}{n}$
 to get
$$\lim\limits_{n\rightarrow \infty } \frac{\sqrt[n]{n}-1}{\ln n/n}=1$$ therefore
$a_n \rightarrow 1$ and our limit for the original expression will be $e$. In agreement with the other answers.


TITLE: Is the set of powerful numbers piecewise syndetic?
QUESTION [8 upvotes]: Recall that a subset $A \subset \mathbb Z_+$ of positive integers syndetic if there exists a $d>0$ such that every positive integer has distance at most $d$ to an element of $A$. It is called piecewise syndetic if it is the intersection of a syndetic set with a subset of $[0,\infty)$ containing arbitrarily long intervals.
Let us call $n \in \mathbb Z_+$ powerful if for every prime $p$, the multiplicity $\nu_p(n) \neq 1$. (Or, equivalently: $n$ can be expressed as a product of a square and a cube.)
Here is the question: is the set of powerful numbers piecewise syndetic?

REPLY [14 votes]: The answer is no. A set $S$ to be piecewise syndetic iff there is an integer $d$ such that there exist intervals $I$ of arbitrary length such that distances between elements of $S\cap I$ are bounded by $d$. In particular, $|S\cap I|\geq\frac{1}{d}|I|$. I will show no such $d$ exists.
For any prime $p$, the fraction of those which are either not divisible by $p$ or divisible by $p^2$ is equal to $1-\frac{p-1}{p^2}$. Further, these conditions are independent - formally, if we consider take $P=p_1\dots p_k$, the product of first $k$ primes, then from the Chinese remainder theorem, in any interval $I$ of length $P^2$ the fraction of integers $n$ in $I$ such that $v_{p_i}(n)\neq 1$ for all $i$ is equal to
$$C:=\prod_{i=1}^k\left(1-\frac{p-1}{p^2}\right).$$
This gives an upper bound of $CP^2$ for the number of powerful numbers an interval of length $P^2$. Now, as $k$ tends to infinity, then $C$ tends to zero (this essentially follows from the fact sum of reciprocals of primes diverges), in particular for large enough $k$ it becomes smaller than $\frac{1}{d}$, so no interval $I$ of length $P^2$ contains more than $\frac{1}{d}|I|$ powerful numbers.


TITLE: What is the total derivative of a total derivative?
QUESTION [1 upvotes]: Suppose a function $y(t)$. Its total derivative is:
$$
d y(t)=y'(t)dt
$$
Now I want to take the total derivative again:
$$
d(dy(t))=d(y'(t)dt)=(dy'(t))dt+y'(t)d(dt)=y''(t)dt+y'(t)d(dt)
$$
What is $d(dt)$ - is it zero?

REPLY [0 votes]: It depends on what notation you are using.  Using standard notation, where the second derivative if $\frac{d^2y}{dt^2}$, this isn't actually possible.  However, if you use a more flexible notation, $d(dt) = d^2t$.  In this notation, the second derivative is
$$ \frac{d^2y}{dt^2} - \frac{dy}{dt}\frac{d^2t}{dt^2} $$
This notation allows for the algebraic manipulation of higher-order differentials, which the standard notation does not allow for.
Historically, many have considered $d(dt) = 0$ iff you believe $t$ to be moving at a constant rate.  This is where the origin of the more simplified version of the second derivative came from.  Basically, pre-relativity, we imagined time to be flowing constantly, so $dt$ was a constant, so its differential was zero.
However, if you are just dealing with equation manipulations like you are doing, then you need to use the expanded notation.
For more information, see my paper, "Extending the Algebraic Manipulability of Differentials".


TITLE: Let $G$ be a group of order $16$ with an element $g$ of order $4$. Prove that the subgroup of $G$ generated by $g^2$ is normal in $G$.
QUESTION [9 upvotes]: Question: Let $G$ be a group of order $16$ with an element $g$ of order $4$.  Prove that the subgroup of $G$ generated by $g^2$ is normal in $G$.
Thoughts: I keep getting stuck.  My most recent path is that since $G$ is solvable, then there is a subnormal series... so maybe I can get something to come out there?  But I just feel like a counterexample is throwing a wrench into everything I try.  Any help would be greatly appreciated.

REPLY [4 votes]: Verret's solution is very nice, and surely how it is meant to be done. But here is another way:
Note that we aim to prove that $g^2$ is central, so assume not. Let $H=C_G(g)$. If $H=G$ then $g\in Z(G)$, so $g^2\in Z(G)$, a contradiction. Since $Z(G)$ is non-trivial and contained in $H$, and does not contain $g^2$, $H$ must be $\langle g\rangle \times Z(G)$ (with $|Z(G)|=2$). (This is purely because $Z(G)$ centralizes $g$ and so forms a direct product.) But then $H$ is normal, so $G$ normalizes the set of squares of elements of $H$, i.e., $\{1,g^2\}$. Hence $H^2$ is a normal subgroup of $G$, and done.
Edit: Here's another proof, using a fact that everyone should know: any two elements of order $2$ generate a dihedral group.
Let $x=g^2$. Since $x$ is non-central, there is a conjugate $y$ of $x$ with $x\neq y$. Consider $H=\langle x,y\rangle$, a dihedral group. Since the reflections in dihedral groups aren't squares, $g\notin H$. Also, two generating reflections in a dihedral $2$-group, like $H$, are not conjugate in $H$. Thus $H\leq C_G(x)$. Thus, since $H$ and $g$ are contained in the proper subgroup $C_G(x)$, we have $|H|=4$, i.e., $x$ commutes with its conjugate $y$. Notice also that $g$ must commute with $y$ as well, so $\langle g,y\rangle=\langle g\rangle \times \langle y\rangle$. In this group, $y$ is not a square. But $y$ is conjugate to $x$, which is a square, so $y=h^2$ for some $h\in G$. But $h$ centralizes $x$ for the same reason that $g$ centralized $y$. Hence $C_G(x)> \langle g,y\rangle$, and is thus the whole group $G$.


TITLE: Uniqueness of product measure with sigma-finite measure spaces
QUESTION [2 upvotes]: I'm trying to understand the proof for problem 5A.10 in Axler's Measure Theory book. I don't understand the last paragraph of this proof. In my attempted proof, I'm not using $\sigma$-finiteness, so I know I'm missing something.
Problem

Partial Proof
Define
$$\mathcal M := \{ E \in \mathcal S \otimes \mathcal T : \omega(E) = \mu \times \nu(E) \}$$
We claim that $\mathcal M = \mathcal S \otimes \mathcal T$. By construction $\subset$ is obvious, so it remains to show the reverse inclusion. Clearly $\mathcal M$ contains the algebra of finite unions of measurable rectangles in $\mathcal S \otimes \mathcal T$ (since each of those unions can be written as a finite disjoint union of measurable rectangles). Now it suffices to show that $\mathcal M$ is a monotone class, and then apply the Monotone Class Theorem, which would imply that $\mathcal S \otimes \mathcal T \subset M$.
Suppose $E_1 \subset E_2 \subset \ldots \in \mathcal M$. Then $\omega(E_k) = \mu \times \nu(E_k)$ for each $k \in \mathbb N$. Now reformulate the sets to be disjoint:
$$
\tilde E_k = E_k - \bigcup_{j=1}^{k-1} E_j
$$
Then
\begin{align*}
\omega(\cup E_k) &= \omega (\cup \tilde E_k) \\
& = \sum \omega(\tilde E_k) \\
&= \sum \mu \times \nu(\tilde E_k) \\
&= \mu \times \nu(\cup \tilde E_k) \\
&= \mu \times \nu(\cup E_k)
\end{align*}
Hence, $\cup E_k \in \mathcal M$. Similarly, let $E_1 \supset E_2 \supset \ldots \in \mathcal M$. Because $X \times Y$ is a $\sigma$-finite space, let $\{F_k\}_{k \in \mathbb N} \subset \mathcal S \times \mathcal T$ be such that $X \times Y = \cup F_k$ and $\omega(F_k) < \infty$.  Define
$$
\hat E_{j, k} = E_j \cap F_k
$$
Then
\begin{align*}
\omega(\cap E_k) &= \omega (\bigcap_j \bigcup_k \hat E_{j, k}) \\
&= \text{???}
\end{align*}
(not proven: So $\cap E_k \in \mathcal M$, and $\mathcal M$ is a monotone class. Therefore $\mathcal M = \mathcal S \otimes \mathcal T$. $\square$)
Questions

Is my partial proof correct -- have a shown that $\mathcal M = \mathcal S \otimes \mathcal T$?
Why is this not sufficient to show that the product measure is unique? What am I missing? Again, the explanation here (final paragraph) confused me, so I need a bit more explanation.

Update 1

I believe I fixed the first part of my proof that $\mathcal M$ is a monotone class.

To show that $\omega (\cap E_k) = \lim_{k \to \infty} E_k$, I can't quite figure out how to use $\sigma$-finiteness here. Help on this last part would be much appreciated!

Update 2
Submitted a possible answer.
Update 3
Axler's Proof of Tonelli's Theorem (5.28, p. 129) provides a shorter, more elegant way of showing that $\mathcal M$ is a monotone class, using the monotone convergence theorem.

REPLY [0 votes]: Define
$$\mathcal M := \{ E \in \mathcal S \otimes \mathcal T : \omega(E) = \mu \times \nu(E) \}$$
We claim that $\mathcal M = \mathcal S \otimes \mathcal T$. By construction $\subset$ is obvious, so it remains to show the reverse inclusion. Clearly $\mathcal M$ contains the algebra of finite unions of measurable rectangles in $\mathcal S \otimes \mathcal T$ (since each of those unions can be written as a finite disjoint union of measurable rectangles). Now it suffices to show that $\mathcal M$ is a monotone class, and then apply the Monotone Class Theorem, which would imply that $\mathcal S \otimes \mathcal T \subset M$.
Suppose $E_1 \subset E_2 \subset \ldots \in \mathcal M$. Then $\omega(E_k) = \mu \times \nu(E_k)$ for each $k \in \mathbb N$. Now reformulate the sets to be disjoint (let $E_o = \emptyset)$:
$$
\tilde E_k = E_k - \bigcup_{j=1}^{k-1} E_j
$$
Then
\begin{align*}
\omega(\cup E_k) &= \omega (\sqcup \tilde E_k) \\
& = \sum \omega(\tilde E_k) \\
&= \sum \mu \times \nu(\tilde E_k) \\
&= \mu \times \nu(\sqcup \tilde E_k) \\
&= \mu \times \nu(\cup E_k)
\end{align*}
Hence, $\cup E_k \in \mathcal M$. Similarly, let $E_1 \supset E_2 \supset \ldots \in \mathcal M$. Because $X \times Y$ is a $\sigma$-finite space, let $\{F_k\}_{k \in \mathbb N} \subset \mathcal S \times \mathcal T$ be such that $X \times Y = \cup F_k$ and $\omega(F_k) < \infty$.  First note that
$$
\bigcap_k E_k = \bigcup_j \left( \bigcap_k E_k \right) \cap F_k = \bigcup_j \bigcap_k (E_k \cap F_j)
$$
So define
\begin{align*}
A_{j,k} &= E_k \cap F_j \\
\hat A_i &= \bigcup_{j \in \mathbb N - \{i\} } \bigcap_k A_{j,k}
\end{align*}
Note that
\begin{align*}
\bigcap_k E_k &= \bigcup_j \bigcap_k A_{j,k} \\
&= \bigcup_j \left( \bigcap_k A_{j,k} \right) - \hat A_j \\
&= \bigsqcup_j \bigcap_k (A_{j,k} - \hat A_j)
\end{align*}
Now observe that for each $j \in \mathbb N$, $\{ A_{j,k} - \hat A_j \}_{k \in \mathbb N}$ is a decreasing sequence that is finite at $k = 1$.
Then
\begin{align*}
\omega(\cap E_k) &= \omega (\bigsqcup_j \bigcap_k (A_{j,k} - \hat A_j)) \\
&= \sum_j \omega (\bigcap_k (A_{j,k} - \hat A_j)) \\
&= \sum_j \mu \times \nu(\bigcap_k (A_{j,k} - \hat A_j)) \\
&= \mu \times \nu(\bigsqcup_j \bigcap_k (A_{j,k} - \hat A_j)) \\
&= \mu \times \nu(\cap E_k)
\end{align*}
So $\cap E_k \in \mathcal M$, and $\mathcal M$ is a monotone class. Therefore $\mathcal M = \mathcal S \otimes \mathcal T$. $\square$


TITLE: Positive integers $x, y, z$ satisfy the equation $x^2+y=z^2+z$, how to pr0ve that $x\leq y$
QUESTION [0 upvotes]: I have come across the following question. There are positive integers $x, y, z$ that satisfy the equation $x^2+y=z^2+z$. How to prove that $x\leq y$?
I tried to start from the following $x^2 +y + \frac{1}{4}=(z+\frac{1}{2})^2$ but got stuck here. Could someone be so kind and give me any hint?
Thanks
Greg

REPLY [2 votes]: $$(y-x)=(z+x+1)(z-x)$$
If $x>y$ then $x>z$. Therefore $x^2+y\geq z^2+2z+1+y> z^2+z$


TITLE: In a model of annual demand of automobiles on its prices and annual average income,the following set of information is received.
QUESTION [1 upvotes]: In a model of annual demand of automobiles on its prices and annual average income,the following set of information is received. For regression during $1927-1941$, RSS$_1 = 0.1151$, and for regression during $1948-62$, RSS$_2=0.0544$.
For a regression on combined above mentioned years RSS$_3=0.2866$.
Is it reasonable to assume that pooling the entire dataset is a better option than stratifying them into two groups?
How can I test this?
Will I need to find the gain due to stratification for this?

REPLY [0 votes]: I had to look up that "RSS" is a fitness metric of the model. Please correct me if it means something different.
I recommend that you have a look at Bayesian Model Comparison. It solves your problem I think
You have two hypotheses:

$H_1$ - that each dataset came from a different distribution
$H_2$ - that both of your datasets came from the same distribution

In order to determine which hypothesis is more plausible, you would need to calculate model evidences for each case and find their ratio, then compare that ratio to a tabulated value. In short, this method should tell you whether the improved fitness of $H_1$ is sufficient to justify the larger number of fitted parameters as compared to $H_2$. Note that you have more parameters in $H_2$ because you fit parameters separately for each dataset.
Also note that BMS is one of the most robust methods of doing this analysis, but is also potentially more difficult to calculate. There are very simple but more hand-wavy model comparison metrics like AIC and BIC