TITLE: Change of variables in canonical probability density
QUESTION [2 upvotes]: In K. Huang's book Statistical Mechanics, par. 7.2, the author writes the canonical partition function in a different way:
$$Q = \frac{1}{N! h^{3N}} \int dp dq \ e^{-\beta H(p,q)} = \int_0^{\infty} dE \ \omega (E) e^{-\beta E}$$
where $\omega(E)$ is the microcaninical density of states,
$$\omega(E)=e^{S(E)/k}$$
So that we have
$$Q=\int_0^{\infty} dE e^{\beta(TS(E)-E)} = \int_0^{\infty} dE e^{-\beta F(E)} $$
where I have just used the fact that $E-TS=F$ (Helmoltz free energy).
So basically we have performed a change of variables: from the canonical $(p,q)$ variables to the energy variable $E$:
$$\rho(p,q) = \frac{e^{-\beta H(p,q)}}{ N! h^{3N}Q} \rightarrow \rho_E(E) = \frac{e^{-\beta E}}{Q} \omega(E)$$
My question is: How can we do this in general? We have seen what form the canonical probability density takes if expressed as a function of energy: what form will it take if we express it as a function of a set of variables (continuous or discrete), $\{\alpha\}$, different from the canonical variables $(p,q)$?
My guess is that we will obtain something in the form
$$\rho_{\{\alpha\}}(\{\alpha\}) = \frac{e^{-\beta H_\text{eff}(\{\alpha\})}}{Q} \Omega(\{\alpha\})$$
where $H_\text{eff} (\{\alpha\})$ is some kind of effective hamiltonian, but I can't figure out how to determine $H_\text{eff}$ and $\Omega$.

REPLY [0 votes]: After quite some thought, I have come to the conclusion that my question is more a mathematical question than a physical one.
What I am looking for is actually a formula for a change of variables for a probability density function.
For example, if we have the random variable $X$ with probability density $\rho_X(x)$ and another random variable $Y=f(X)$, the probability density of $Y$ will be given by the following formula:
$$\rho_Y(y) = \int \rho_X(x) \ \delta(y-f(x)) \ dx$$
So in our case, when we consider the energy, we should have
$$\rho_E(E) = \int \rho(p,q)\ \delta(E-H(p,q)) \ dp dq = \frac{e^{-\beta E}}{Q} \omega(E)$$
And indeed, even if the integral is not trivial to evaluate, we see that this makes sense, because
$$\int \delta(E-H(p,q)) \ dp dq \sim \omega(E) $$
(see for example M. Tuckerman, Statistical Mechanics: Theory and Molecular Simulation, par 4.3)
So if we consider a single variable
$$\alpha=f(p,q)$$
we obtain
$$\rho_\alpha (\alpha) = \int \rho(p,q) \ \delta(\alpha-f(p,q)) \ dp dq$$
If we consider a discrete set of variables $\{\alpha_i = f_i(p,q)\}$, I think we will obtain something like
$$\rho_{\{\alpha\}} (\{\alpha\}) = \int \rho(p,q) \ \prod_i \delta(\alpha_i-f_i(p,q)) \ dp dq$$
But I still haven't been to come out with a formula for the case in which we consider a continuous set of variables.
We could also define an effective hamiltonian in the following way (let's take the simple case of a single variable):
$$e^{-\beta H_\text{eff}(\alpha)} = \int e^{-\beta H(p,q)} \ \delta(\alpha-f(p,q)) \ dp dq$$
The exact same relation in the case of $\alpha=$magnetization vector can be found in G. Parisi's Statistical Field Theory, par. 3.1, and I find this very encouraging.


TITLE: area under parametric curve
QUESTION [2 upvotes]: I have difficulty on how to eliminate parameter especially the equation involved trigonometry equation.
The question is asking for the area bounded by the curve , the 2 axes and the line $y=1$.
$x=4 \sin t$
$y=\cot t$
where $t$ is in the range $(0, \pi)$.
I have tried to use the trigonometric formula
$1+ \cot^2 t =\csc^2 t$
but I got the wrong answer.The answer given is 4ln[(square root 2)+1].

REPLY [1 votes]: The Desmos plot of the relevant part of the curve looks like this:

The desired area is simply the area "under" (to the left of) the curve from $y=0$ to $y=1$.
We now express $x$ in terms of $y$. Since $1+\cot^2t=\csc^2t=\frac1{\sin^2t}$ and thus $\frac1{1+\cot^2t}=\sin^2t$, we have
$$x=4\sin t=\frac4{\sqrt{1+\cot^2t}}=\frac4{\sqrt{1+y^2}}$$
So the desired area is
$$\int_0^1\frac4{\sqrt{1+y^2}}\,dy=4[\sinh^{-1}y]_0^1=4\sinh^{-1}1=4\ln(1+\sqrt2)$$
The last equality is well-known; see e.g. OEIS A091648.


TITLE: Solving a recursive relationship
QUESTION [1 upvotes]: I was wondering whether the following relationship could be solved.
$$S_0= 100, C=(0.05, 0.15,...), P = (0.03, 0.05, ...), D = 120, R = 0.08\\
S_1 = S_0(1-C_1)\left(1-P_1-\frac{1}{D + 1}-(1-R)\right)\\
S_2 = S_1(1-C_2)\left(1-P_2-\frac{1}{D + 1}-(1-R)\right)\\
S_3 = ...$$
Notice that the $C_1$ refers to the first element in the $C$ vector and $P_1$ refers to the first element in the $P$ vector, while $D$ and $R$ are constants.
I have tried to come up with a part, but I can't seem to solve the latter part, which is in the latter brackets.
$$S_n=S_0\cdot\Pi_{i=1}^{n}(1-C_i)\cdot ...$$
But the latter part, I am not sure how to do it, except just writing it out, but then I am still stuck unfortunately. I have the feeling that it can be solved, but I am not sure how.
Please do not solve the $C$ and $P$ they can be random and are considered user input, so they can vary arbitrary.

REPLY [1 votes]: I think it might be possible to solve this recurrence relation. The first thing to do is find out an expression for $C_n$ and one for $P_n.$ I get
\begin{align*}
C_{n+1}&=0.05+0.1n \\
P_{n+1}&=0.03+0.02n.
\end{align*}
The recurrence relation we can write as
\begin{align*}
S_{n+1} &= S_n(1-C_{n+1})\left(1-P_{n+1}-\frac{1}{D + 1}-(1-R)\right) \\
&=S_n(1-(0.05+0.1n))\left(1-(0.03+0.02n)-\frac{1}{121}-0.92\right) \\
&=S_n(0.95-0.1n)\left(0.05-0.02n-\frac{1}{121}\right).
\end{align*}
This is a difficult recurrence relation to solve, but Mathematica comes through with the following:
$$S_n=\frac{1919}{121}\, 4^{-n} 125^{1-n}
    \left(-\frac{17}{2}\right)_{n-1}
    \left(-\frac{263}{242}\right)_{n-1}, $$
where the symbol $\displaystyle\left(-\frac{17}{2}\right)_{n-1} $ is the Pochhammer symbol.


TITLE: Physical Constraints of Very Large Humanoids
QUESTION [2 upvotes]: I loved Godzilla movies when I was a kid (still do), but ever since Pacific Rim came out, I have been pondering just how implausible really large humanoids would be given the laws of physics.
For the sake of this question lets say we have the following:

Humanoid figure, proportional to an average human male
30 meters tall
Movements have similar timing to average human male
Everything takes place on Earth

How strong would its body have to be to withstand the force of simply moving around? Is there any physical material we know of that could accomplish this?
What would happen to the environment around such an entity exerting such forces? Would the ground simply give too much to make quick movements like running impossible?
I am very interested in the math behind all of this.

REPLY [0 votes]: This is the line I have been working on, but using Male African Elephants,
and Dinosaurs with " n " Elephant Volumes , where the surface gravity of the
Earth is inversely proportional to the cube root of the n E.V. ( Elephant Volumes ).
n is limited to less than or equal to 13.0 E.V.  The number has been getting smaller
over the last 252 million years, which mean that the maximum allowable size of
animals is gradually getting less and less as time passes.
There are still some conundrums.
Why does a Dinosaur of 8 Elephant Volumes in a surface gravity of 0.5 g ( now )
only have twice the surface area of the bottom of its four feet ?
The downward force is 8 x 0.5 = 4, but the force per unit area ( pressure )
is 4 / 2 = 2 times the unit force of an Elephant. So why did they not get stuck
in the Mud?
Any way, to answer your questions, Humans are no where near the maximum allowable
limits of animal sizes in the current surface gravity, but there are some limits.
Limits: The size of the Pump ( heart ) , and the hydraulic pressure required to
pump blood to the brain, without bursting blood vessels in the legs and feet.
Structural Limits: The Elephant is at the Maximum allowed ( 40 % muscle mass )
and ( 27 % bone mass ). The upper limit is 67 %. The other 33% is for all the
other non structural stuff ( all the organs, fluids, brain, nerves, connective tissues
and lots of other stuff ).
There is a tendency to maximize size in some animals, but this comes with a price.
The price is it takes lots of food to keep big animals big.  If the food becomes scarce,
the biggest animals in a species die off, while some smaller individual animals
still survive.
When you look at the pictures of the skeletons of large extinct humans, look for
telltale signs.  The relative dimension will change, the leg bones will be abnormally
long and robust, and the ends of the leg bones will be larger in comparison to the
cross-section at the mid height of the leg bones. The spine and head will be more
robust, and the arm bones also longer and more robust.
If the picture looks too skinny, or slender, it is a fake.  The overall proportions
need to look more like long cow legs, or bison legs, with large joints, especially the
Knee joints, and hip joints.
If you double the Height of a Human to 12 feet, then it will weight more like
8 times the weight of a current big human ( 250 lbs to 300 lbs ) becomes
2000 lbs to 2400 lbs.  This is not impossible, but the structural requirements of the
bones, muscles, ligaments, and tendons have to be reflected in an appropriately
robust skeleton that would support this kind of weight.
You might also find spinal problems ( curved spines ). Short life spans ?
Low Population numbers ?  This would be an interesting thing to study.
They may have been quite possible before we hunted out the largest food
source animals around 8,000 to 10,000 years ago, and the climate changed
dramatically.
Food for thought.


text:
Consider a population matrix $\bP$ of the form $\bP=\rho\bGamma\bTheta \bB\bTheta^T\bGamma$, with $\bGamma\in\mathbb{R}_{>0}^{n\times n}$ being a positive diagonal matrix, $\bTheta\in\mathbb{R}_{\geq 0}^{n\times K}$ a community-membership matrix, and $\bB\in\mathbb{R}_{\geq0}^{K\times K}$ a cross-community connection matrix.
We will make the following assumptions which are common in the literature:
\begin{assumption}
(a) {\em Pure nodes:} Each community has at least one ``pure'' node, which belongs solely to that community.
(b) {\em Non-zero rows:} No row of $\bTheta$ is identically $0$.
(c) $\bB$ is full rank.
\label{assume1}
\end{assumption}
The form of the population matrix $\bP$, alongside Assumption~\ref{assume1}, induces a conic structure on the rows of the eigenvectors of $\bP$.
\begin{lem}\label{lem:vtheta}
  Let there be $K$ communities ($\rank(\bP)=K$), and let $\mathcal{I}$ be indices of $K$ pure nodes, one from each community.
	Let $\bP=\bV\bE\bV^T$ be the top-$K$ eigen-decomposition of $\bP${, where columns of $\bV\in\mathbb{R}^{n\times K}$ are the $K$ principal eigenvectors and $\bE\in\mathbb{R}^{K\times K}$ is a diagonal matrix of the $K$ principal eigenvalues}.
  Then,
	$\bV = \bGamma \bTheta \bGamma_P^{-1}\bV_P$, where $\bV_P = \bV(\mathcal{I}, :)$ is full rank and $\bGamma_P = \bGamma(\mathcal{I}, \mathcal{I})$.
\end{lem}
Since $(\bGamma\bTheta\bGamma_P^{-1})_{ij}\geq 0$ for all $(i,j)$, the rows of $\bV$ fall within a cone with corners $\bV_P$.
This suggests the following idealized problem:
\begin{problem}[Ideal cone problem]
We are given a matrix $\bZ \in \mathbb{R}^{n\times m}$ such that $\bZ = \bM \bY_P$, where $\bM\in\mathbb{R}_{\geq 0}^{n\times K}$, no row of $\bM$ is $0$, and
$\bY_P\in\mathbb{R}^{K \times m}$
corresponds to $K$ (unknown) rows of $\bZ$, each scaled to unit $\ell_2$ norm.
Infer $\bM$ from $\bZ$.
\end{problem}
The rows of $\bY_P$ are unit vectors representing the corner rays of the cone.
Each row of $\bZ$ is constructed from a non-negative weighted combination of these unit vectors, with the weights being given by the corresponding rows of $\bM$.
Rows of $\bZ$ that lie on some corner correspond to rows of $\bM$ that have zero in all but one component.
Observe that $\bM$ is invariant to the choice of $K$ corner rows of $\bZ$ used to construct $\bY_P$.

Now consider solving the ideal cone problem with the eigenvector matrix, i.e., $\bZ=\bV$.
From Lemma~\ref{lem:vtheta}, the corner rows correspond to the pure nodes.
Choosing one such row from each corner gives us a set of pure node indices $\mathcal{I}$.
Hence, $\bM=\bGamma\bTheta\bGamma_P^{-1}\bN_P^{-1}$, where $\bN$ is a diagonal matrix with $\bN_{ii}=1/\|\be_i^T\bZ\|$ and $\bN_P=\bN(\mathcal{I},:)$.
We also have the identity $\rho\bGamma_P \bB \bGamma_P = \bV_P \bE \bV_P^T$.
Coupled with model-specific identifiability conditions ({details are provided in \supp}), these can be used to infer $\bTheta$ and $\rho\bB$ ($\bGamma$ are typically considered nuisance parameters).

In practice, we only have an observation matrix $\bA$ that is stochastically generated from the population matrix $\bP$.
Hence, we must actually solve:
\sloppy
\begin{problem}[Empirical cone problem]
We are given a matrix $\hat{\bZ} \in \mathbb{R}^{n\times m}$ such that $\max_{i\in[n]} \|\be_i^T(\bY - \hat{\bY}) \|_2 \leq \epsilon$, where $\bY = \bN\bZ$ is the row-normalized version of $\bZ$, and $\hat{\bY}$ is constructed similarly from $\hat{\bZ}$.
Again, $\bZ = \bM \bY_P$, where $\bM\geq 0$, no row of $\bM$ is $0$, and $\bY_P=\bY(\mathcal{I},:)$ corresponds to $K$ (unknown) rows of $\bY$ with indices $\mathcal{I}$.
Infer $\bM$ from $\hat{\bZ}$.
\end{problem}
\fussy

We will first present the solution to the ideal cone problem.
We will then show that the same algorithm with some post-processing solves the empirical cone problem up to $O(\epsilon)$ error.
Finally, we apply our algorithm to infer parameters for a variety of models, and present error bounds for each.

\noindent
{\bf Notation:} We shall refer to the $i^{th}$ row of $\bZ$ as $\bz_i^T$ {\em expressed using a column vector}, i.e., $\bz_i = \bZ^T\be_i$.
The same pattern will be used for rows $\bbm_i^T$ of $\bM$, and other matrices as well.

\subsection{The Ideal Cone Problem}
Observe that given the corner indices $\mathcal{I}$ (i.e., given $\bY_P$), finding $\bM$ such that $\bZ=\bM \bY_P$ is a simple regression problem.
Thus, the only difficulty is in finding the corner indices.

Our key insight is that under certain conditions, the ideal cone problem can be solved easily by a {\bf one-class SVM applied to the rows of $\bY$}.
Figure~\ref{fig1} plots the normalized rows $\by_i$ of $\bY$ for an example cone.
Observe that a hyperplane through the corners separates all the points from the origin.
This suggests that the normalized corners are the support vectors found by a one-class SVM:
\begin{equation}
\text{maximize }\  b\quad \text{ s.t. } \bw^T \by_i \geq b \;(\text{for } i=1, \ldots, n) \text{ and } \|\bw\|_2 \leq 1.
\label{eq:SVM}
\end{equation}
We show next that this intuition is correct.
Define the following condition.
\begin{cond}
The matrix $\bY_P$ satisfies $(\bY_P\bY_P^T)^{-1}\bone > 0$.
\label{cond:pop}
\end{cond}
\begin{thm}
Each support vector selected by the one-class SVM (Eq.~\ref{eq:SVM}) is a corner of \bZ.
Also, if Condition~\ref{cond:pop} holds, there is at least one support vector for every corner.
\end{thm}
Thus, under Condition~\ref{cond:pop}, we can get all the corners from the support vectors, and then find $\bM$ via regression of $\bZ$ on $\bY_P$.
Condition~\ref{cond:pop} is always satisfied for our problem setting, as shown next.
\begin{thm}\label{thm:dcmmsb_condition_true}
Let $\bP$ be a population matrix satisfying Assumption~\ref{assume1}.
Let $\bZ=\bV$, where $\bV$ is the rank-$K$ eigenvector matrix.
Let $\bY=\bN\bZ$ as defined above.
Then, Condition~\ref{cond:pop} is true.
\label{thm:condpopHolds}
\end{thm}
Thus, the ideal cone problem is easily solved by a one-class SVM.
Next, we show that the same method suffices for the empirical cone problem too.

\subsection{The Empirical Cone Problem}
Now, instead of the normalized eigenvector rows $\bY$, we are given the empirical matrix $\hat{\bY}$ with rows $\hat{\bz}_i^T/\|\hat{\bz}_i\|$, where $\max_i \|\be_i^T (\hat{\bY} - \bY)\|\leq \epsilon$.
Once again, we focus on finding the corner indices, using which $\bM$ can be inferred by regression.
We will show that running a one-class SVM on the rows of $\hat{\bY}$ yields ``near-corners,'' after some post-processing.
We will need a stronger form of Condition~\ref{cond:pop}:
\begin{cond}
The matrix $\bY_P$ satisfies {${(\bY_P\bY_P^T)^{-1}\bone} \geq \eta\bone$ }
 for some constant $\eta>0$.
\label{cond:emp}
\end{cond}
It is easy to show that the solution $(\bw, b)$ of the population SVM under Condition~\ref{cond:pop} is given by
\begin{align}
\bw &= b^{-1}\cdot \bY_P^T \bbeta &
b&=\left(\bone^T (\bY_P\bY_P^T)^{-1}\bone \right)^{-1/2} &
\bbeta &= \dfrac{(\bY_P\bY_P^T)^{-1}\bone}{\bone^T (\bY_P\bY_P^T)^{-1}\bone}.
\label{eq:bbeta}
\end{align}
Thus, Condition~\ref{cond:pop} implies that $\bw$ is a convex combination of the corners, while Condition~\ref{cond:emp} additionally requires a minimum contribution from each corner.

\begin{lem}[SVM solution is nearly ideal]
Let $(\hat{\bw}, \hat{b})$ be the solution for the one-class SVM (Eq.~\ref{eq:SVM}) applied to the rows of $\hat{\bY}$.
Under Condition~\ref{cond:emp},
we have $|\hat{b}-b|\leq\epsilon$ and $\|\hat{\bw}-\bw\|\leq \zeta\epsilon$, for $\zeta=\frac{4}{\eta b^2\sqrt{\lambda_K(\tmtxP_P\tmtxP_P^T)}}\leq \frac{4K}{\eta(\lambda_K(\tmtxP_P\tmtxP_P^T))^{1.5}}$.
\label{lem:bw}
\end{lem}

Unlike the ideal cone scenario, the rows $\hat{\bY}_P$ corresponding to the corners need not be support vectors for the empirical cone.
However, they are not far off.
\begin{lem}[Corners are nearly support vectors]
The corners of the population cone are close to the supporting hyperplane:
$\mbox{$\hb\bone\leq\tmtxSp\hww\leq\hb\bone+(\zeta+2)\epsilon\bone$}$.
\label{lem:cornerNearSV}
\end{lem}
This suggests that we should consider all points that are up to $(\zeta+2)\epsilon$ away from the supporting hyperplane when searching for corners.
The next Lemma shows that each such point is a ``near-corner.''

Recall that each row $\hat{\by}_i^T$ is a noisy version of a population row $\by_i^T = \bbm_i^T \bY_P/\|\bbm_i^T \bY_P\|$, which can be rewritten as a scaled convex combination of the normalized corners: ${\by_i^T = r_i \rowcvxY_i^T \bY_P}$, where $\rowcvxY_i^T\bone=1$.
Specifically, $r_i =  \frac{\bbm_i^T \bone}{\|\bbm_i^T\bY_P\|}$ and $\rowcvxY_i = \frac{\bbm_i}{\bbm_i^T \bone}$.
For a corner, $r_i=1$ and $\rowcvxY_i=\be_j$ for some $j$.
We now show that every point $i$ that is close to the supporting hyperplane is nearly a corner of the ideal cone.
\begin{lem}[Points close to support vectors are near-corners]
	If $\hww^T\trowS_i\leq \hb + (\zeta+2)\epsilon$ for some point $i\in [n]$, then
  $\mbox{$1\leq r_i\leq 1+ \frac{(\zeta+4)\epsilon}{b-\epsilon}$}$
  and
  $\elecvxY_{ij}\geq 1- \frac{2\zeta\epsilon}{b\lambda_K(\tmtxPp\tmtxPp^T)}$ for some $j\in[K]$.
  \label{lem:nearCorner}
\end{lem}

Consider the set of points $S_c=\{i\mid \hww^T\trowS_i\leq \hb + (\zeta+2)\epsilon\}$ that are close to the supporting hyperplane.
Lemmas~\ref{lem:cornerNearSV} and~\ref{lem:nearCorner} show that $S_c$ contains all corners, and possibly other points that are all near-corners.
This suggests that we can cluster the vectors $\{\trowS_i\mid i\in S\}$ into $K$ clusters, each corresponding to one corner and possibly extra near-corners close to that corner.
Randomly selecting one point from each cluster gives us the set of inferred corners.
\begin{lem}[Each corner has its own cluster]
	There exist exactly $K$ clusters in $S_c$, as long as
  $\epsilon\leq c_{\epsilon}\frac{\eta(\lambda_K(\tmtxPp\tmtxPp^T))^3}{K^{1.5}\sqrt{\kappa(\tmtxPp\tmtxPp^T)}}$,
  for some global constant $c_{\epsilon}$.
\label{lem:Kclusters}
\end{lem}

Let $C$ be the indices of the near-corners picked by this clustering step.
Since $\bZ = \bM\bY_P$, this suggests $\bM$ can be obtained via regression: $\bM \approx \mtxS\tmtxS_C^T(\tmtxS_C\tmtxS_C^T)^{-1}\bpi$,
where ${\tmtxS_C:=\tmtxS(C,:)}$ and $\bpi$ is a permutation matrix that matches the ordering of ideal corners and the empirical near-corners.
\begin{thm}\label{thm:M_row_bound}
If Condition~\ref{cond:emp} and the condition on $\epsilon$ in Lemma~\ref{lem:Kclusters} holds, then for any $i\in[n]$,
	${
		\|\be_i^T(\cvxP - \mtxS\tmtxS_C^T(\tmtxS_C\tmtxS_C^T)^{-1}\bpi)\| \leq \frac{c_M\kappa(\tmtxPp\tmtxPp^T)\|\be_i^T\mtxP\|{K\zeta}}{(\lambda_K(\tmtxPp\tmtxPp^T))^{2.5}} \epsilon,
	}$
where $c_M$ is a global constant, {and $\kappa(.)$ is the ratio of the largest and smallest nonzero singular values of a matrix.}
  \label{thm:M}
\end{thm}

Algorithm~\ref{algo:inferCone} shows all the steps of our method (\svmcone).
The algorithm requires an estimate of $\delta:=(\zeta+2)\epsilon$, and returns the inferred $\bM$ and near-corners $C$.
When the row-wise error bound $\epsilon$ is unknown, we can start with $\delta=0$ and incrementally increase it until $K$ distinct clusters are found.

\begin{algorithm}[H]
	\caption{SVM-cone}
	\label{algo:inferCone}
	\begin{algorithmic}[1]
		\REQUIRE $\mtxS \in \R^{n\times m}$, number of corners $K$, estimated distance of corners from hyperplane $\delta$
		\ENSURE  Estimated conic combination matrix $\hat{\bM}$ and near-corner set $C$
		\STATE Normalize rows of $\mtxS$ by $\ell_2$ norm to get $\tmtxS$ with rows $\hat{\by}_i^T$
		\STATE Run one-class SVM on $\hat{\by}_i$ to get the normal $\hww$ and distance $\hb$ of the supporting hyperplane
    \STATE Cluster points $\{\hat{\by}_i\mid \hww^T\trowS_i\leq \hb + \delta\}$ that are close to the hyperplane into $K$ clusters
    \STATE Pick one point from each cluster to get near-corner set $C$
    \STATE $\hat{\bM} =\mtxS\tmtxS_C^T(\tmtxS_C\tmtxS_C^T)^{-1}$
	\end{algorithmic}
\end{algorithm}

\section{Applications}
Many network models and topic models have population matrices of the form $\bP=\rho\bGamma \bTheta \bB \bTheta^T \bGamma$.
We have already shown that in such cases, the eigenvector matrix $\bV$ forms an ideal cone (Lemma~\ref{lem:vtheta}), and that Condition~\ref{cond:pop} holds.
It is easy to see that the same holds for $\bV\bV^T$ as well.
This suggests that \svmcone can be applied to the matrix $\hat{\bV}\hat{\bV}^T$, where $\hat{\bV}$ is the empirical top-$K$ eigenvector matrix.
We shall show that this yields {\em per-node error bounds} in estimating community memberships and {\em per-word error bounds} for word-topic distributions.

\subsection{Network models}
Define a ``DCMMSB-type'' model as a model with population matrix $\bP=\rho\bGamma\bTheta\bB\bTheta^T\bGamma$ and an empirical adjacency matrix $\bA$ with $\bA_{ji}=\bA_{ij} \sim \text{Bernoulli}(\bP_{ij})$ for all $i>j$. Assume that rows of $\bTheta$ have unit $\ell_p$ norm, for $p=1$ (DCMMSB) or $p=2$ (OCCAM~\citep{zhang2014detecting}).

Let $\bv_i=\bV^T\be_i$, $\hvv_i=\hv^T\be_i$, $\trowP_i=\bV\bv_i/\|\bV\bv_i\|$, and $\trowS_i=\hv\hvv_i/\|\hv\hvv_i\|$. Denote $\gamma_{\max}=\max_i\bGamma_{ii}$ and $\gamma_{\min}=\min_i\bGamma_{ii}$.
\sloppy
\begin{thm}[Small row-wise error in Network Models]
	Consider a DCMMSB-type model with $\btheta_i\sim\mathrm{Dirichlet}(\balpha)$, and $\alpha_0:=\balpha^T\bone$.
	If $\bal:= \dfrac{\alpha_0}{\alpha_{\min}}\leq   \dfrac{\min( \sqrt{\frac{n}{27\log n}}, {\frac{\gamma_{\min}^2}{\gamma_{\max}^2}n\rho})}{2(1+\alpha_0)}$, ${\dfrac{\lambda^*(\bB)}{\nu}\geq \dfrac{8(1+\alpha_0)(\log n)^{\xi}}{\gamma_{\min}^2\sqrt{n\rho}}}$ for some constant $\xi>1$, $\kappa(\bTheta^T\bGamma^2 \bTheta)=\Theta(1)$,   and $\alpha_0=O(1)$, then
	\bas{
		\epsilon=\max_i \|\trowP_i-\trowS_i\| = \epsilonMMSB
	}
	with probability at least $1-O(Kn^{-2})$.
  Here $\lambda^*(\bB)$ is the smallest singular value of $\bB$.
  \label{thm:row_wise_vvt1}
\end{thm}
\fussy
Similar results for the non-Dirichlet case follow easily as long as $n\rho=\Omega((\log n)^{2\xi})$, $\lambda_K(\bP)=\Omega(\sqrt{n\rho}(\log n)^\xi)$, and $\max_i \|\bV(:,i)\|=O(\sqrt{\rho})$ with high probability.
This shows that the rows of $\hat{\bV}\hat{\bV}^T$ are close to those of $\bV\bV^T$, and the latter forms an ideal cone satisfying Condition~\ref{cond:pop}.
Hence, the conic combination for each node can be recovered by Algorithm~\ref{algo:inferCone} applied to $\hat{\bV}\hat{\bV}^T$.
In fact, we can run the algorithm on $\hat{\bV}$ itself; the output depends only on the SVM dual variables $\bbeta$ (Eq.~\ref{eq:bbeta}), which are the same whether the input is $\hat{\bV}$ or $\hat{\bV}\hat{\bV}^T$.
The output is the same conic combination matrix $\hat{\bM}$ and the same set $C$ of nearly-pure nodes.

For \textbf{identifiability} of $\bTheta$, we need another condition.
We will assume that $\sum\bGamma_{ii}=n$ and all diagonal entries of $\bB$ are equal ({details are provided in \supp}).

The next theorem shows that \svmcone can be used to consistently infer the parameters of DCMMSB as well as OCCAM~\cite{zhang2014detecting}.

\begin{thm}[Consistent inference of community memberships for each node]\label{thm:theta_bound}
  Consider DCMMSB-type models
  where the conditions of Theorem~\ref{thm:row_wise_vvt1} are satisfied and ${\kappa(\bTheta^T\bGamma^2 \bTheta)=\Theta(1)}$.
  Let $\hat{\bD}$ be a diagonal matrix with entries $\hat{\bD}_{ii} = \sqrt{\be_i^T\tmtxS_C\hv\hat{\bE}\hv^T\tmtxS_C^T\be_i}$.
  Let $\hat{\bTheta} = \hat{\bF}^{-1}\hat{\bM}\hat{\bD}$, where $\hat{\bF}$ is a diagonal matrix with entries $\hat{\bF}_{ii}=\|\be_i^T\hat{\bM}\hat{\bD}\|_1$ (for DCMMSB) and ${\hat{\bF}_{ii}=\|\be_i^T\hat{\bM}\hat{\bD}\|_2}$ (for OCCAM~\cite{zhang2014detecting}).
  Then there exists a permutation matrix $\bpi$ such that
	\bas{
		{\|\be_i^T(\bTheta-\hat{\bTheta}\bpi)\|}
    &= \ThetaErrorDCMMSBtype

	}
	with probability at least $1-O(Kn^{-2})$.

\end{thm}
\begin{rem}
	The error bound is small when the clusters are well separated (large $\lambda^*(\bB)$), the network is dense (large $\rho$), there are few blocks (small $K$), and the membership vectors $\bTheta$ are drawn from a balanced Dirichlet distribution (small $\nu$, and hence small $\kappa(P)$), which leads to balanced block sizes.

\end{rem}
\begin{rem}
	For DCMMSB-type models,  $\eta\geq\frac{\gamma_{\min}^2\min_i(\be_i^T\bTheta^T\bone)}{{\lambda_1(\bTheta^T\bGamma^2 \bTheta)}}$. Also, under the conditions of Theorem~\ref{thm:row_wise_vvt1}, $\eta\geq\frac{\gamma_{\min}^2}{3\nu\gamma_{\max}^2}$ with high probability. Proofs are in \supp.
\end{rem}
Observe that these are {\bf per-node error bounds}, as against a simpler bound on $\|\bTheta-\hat{\bTheta}\|$.
Clearly, the same results extend to the special case of

the Mixed Membership Stochastic Blockmodel~\cite{airoldi2008mixed} and the Stochastic Blockmodel~\cite{holland_stochastic_1983}
as well (the assumption of equal diagonal entries of $\bB$ is no longer needed, since $\bGamma_{ii}=1$ is enough for parameter identifiability~\cite{mao2017estimating}).

\subsection{Topic Models}
Let $\bT\in\mathbb{R}_{\geq 0}^{V\times K}$ be a matrix of the word to topic probabilities with unit column sum, and let $\bH\in\mathbb{R}_{\geq 0}^{K\times D}$ be the topic to document matrix.
Then $\W:=\bT\bH$ is the probability matrix for words appearing in documents.
The actual counts of words in documents are assumed to be generated iid as $\w_{ij}\sim \text{Binomial}(N,\W_{ij})$ for $i\in [V], j\in [D]$.

The word co-occurrence probability matrix is given by $\W\W^T/D = \bT (\bH\bH^T/D) \bT^T$.
Setting $\bGamma_{ii}=\|\bT(i,:)\|_1$, $\bTheta=\bGamma^{-1}\bT$, and $\bB=\bH\bH^T/D$, we find that $\W\W^T/D = \bGamma\bTheta\bB\bTheta^T\bGamma$ with $\bTheta\bone=\bone$.
This clearly matches the form of $\bP$ in the DCMMSB model.
Hence, its eigenvector matrix has the desired conic structure with weight matrix $\bM = \bT\bGamma_P^{-1}\bN_P^{-1}$, with the ``pure nodes'' being {\em anchor words} that only occur in a single topic.
We now show that the row-wise error between the empirical and population eigenvector matrices decays with increasing number of documents $D$ and number of words in a document $N$.

\begin{assumption}\label{assumption:topic}
	Let $g_{ik}=\be_i^T\W\W^Te_k$. We assume that when it is not zero, it goes to infinity, in particular, $g_{ik}\geq N\log \gikD$, which gives $D/N\rightarrow \infty$. We also assume that $\lambda_i(\bH\bH^T)=\Theta(D)$,  for $i\in [K]$, and $\kappa(\bT\bT^T)=\Theta(1)$.
\end{assumption}
These assumptions are similar to ones made in other theoretical literature on topic models~\cite{ke2017topic}.

We will construct a matrix $\w_1\w_2^T$, where $\w_1$ and $\w_2$ are obtained by dividing the words in each document uniformly randomly in two equal parts. This ensures that $\uE[\w_1\w_2^T]=\W\W^T$, which in turn helps establishing concentration of empirical singular vectors as shown in the following lemma. For simplicity denote $N_1=N/2$.
\begin{lem}[Small row-wise error in Topic Models]\label{lem:topic_eigen_bound}
\label{lem:topic_eigen_bound1}
Let $\hat{\bV}$ denote the matrix of the top-$K$ singular vectors of $\bU=\w_1\w_2^T/N_1^2$,
and let the population counterpart of this be $\bV$.
Let $\bv_i=\bV^T\be_i$, $\hvv_i=\hv^T\be_i$, $\trowP_i=\bV\bv_i/\|\bV\bv_i\|$, and $\trowS_i=\hv\hvv_i/\|\hv\hvv_i\|$.
Under Assumption~\ref{assumption:topic}, we have:
\bas{
	\epsilon=\max_i \|\trowP_i-\trowS_i\| = \topicRowwiseEigenspaceBoundSimplified

}

with probability at least $1-O(1/D^2)$.
\end{lem}
Thus, Algorithm~\ref{algo:inferCone} run on $\hat{\bV}\hat{\bV}^T$ (or equivalently, just $\hat{\bV}$) can be used to find the conic combination weights $\hat{\bM}\approx\bM$.
Since $\bM$ being the product of $\bT$ with a diagonal matrix where $\bT$ has unit column sum, we can extract $\hat{\bT}=\hat{\bM}\hat{\bD}^{-1}$, where $\hat{\bD}$ is a diagonal matrix with $\hat{\bD}_{ii}=\|\hat{\bM}(:,i)\|_1$.
\begin{thm}[Consistent inference of word-topic probabilities for each word]\label{thm:topic_error_bound}
Under Assumption~\ref{assumption:topic}, there exists a permutation matrix $\bpi$ such that
\bas{
	 \frac{\|\be_i^T(\hT-\bT\bpi^T)\|}{\|\be_i^T\bT\|}=
		\topicTbounds
}with probability at least $1-O(1/D^2)$.
\end{thm}

\begin{rem}
	For topic models,
	$\eta\geq {\min_i\|\be_i^T\bT\|_1}/{{\lambda_1(\bT^T \bT)}} \geq {\min_i\|\be_i^T\bT\|_1}/{{K}}$. Proofs are in \supp.
\end{rem}

config: arxiv


TITLE: Conclusions from the ratio test for sequences?
QUESTION [0 upvotes]: For the test I know if $\frac{x_{n+1}}{x_n}$ converges to $L$ and $L<1$, then xn converges to 0. Does this still apply if L is negative, and what about if $L\ge1$? Is it the same for series where if $L=1$ the test is ambiguous, and if $L>1$, the sequence will diverge?

REPLY [0 votes]: Take your $$L=\frac{x_{n+1}}{x_n}$$
For $x_0=k$, with $L$ tending to its final value, your sequence becomes roughly
$$k,Lk,L^2k,L^3k...$$
If $L=1$, this means that $$x_{n+1}=x_n$$
Hence your sequence becomes $k,k,k,k,k,k,k,k....$
If $L<1$, note that $L^{n+1}<L^n$ for $n\ge1,n\in \Bbb Z$
Hence via our general form, $\lim_{n\to\infty}{(L^nk)}=0$
For $L>1$, our inequality reverses. We get $L^{n+1}>L^n$ for $n\ge1,n\in \Bbb Z$
And so $\lim_{n\to\infty}{(L^nk)}=\infty$ and this diverges


text:
Modern machine learning models often consist of multiple layers.

For example, consider a feed-forward deep neural network that defines a prediction function
\begin{align*}
\vect{x} \mapsto f(\vect{x}; \mat{W}^{(1)},\ldots,\mat{W}^{(N)}) = \mat{W}^{(N)}\phi(\mat{W}^{(N-1)}\cdots\mat{W}^{(2)}\phi(\mat{W}^{(1)}\vect{x})\cdots),
\end{align*}
where $\mat{W}^{(1)},\ldots,\mat{W}^{(N)}$ are weight matrices in $N$ layers, and $\phi\left(\cdot\right)$ is a point-wise \emph{homogeneous} activation function such as Rectified Linear Unit (ReLU) $\phi(x) = \max\{x, 0\}$.
A simple observation is that this model is \emph{homogeneous}: if we multiply a layer by a positive scalar $c$ and divide another layer by $c$, the prediction function remains the same, e.g. $f(\vect{x}; c\mat{W}^{(1)},\ldots,\frac{1}{c}\mat{W}^{(N)}) = f(\vect{x}; \mat{W}^{(1)},\ldots,\mat{W}^{(N)})$.

A direct consequence of homogeneity is that a solution can produce small function value while being unbounded, because one can always multiply one layer by a huge number and divide another layer by that number.
Theoretically, this possible unbalancedness poses significant difficulty in analyzing first order optimization methods like gradient descent/stochastic gradient descent (GD/SGD), because when parameters are not a priori constrained to a compact set via either coerciveness\footnote{A function $f$ is coercive if $\norm{\vect x} \to \infty$ implies $f(\vect x) \to \infty$.} of the loss or an explicit constraint, GD and SGD are not even guaranteed to converge \citep[Proposition 4.11]{lee2016gradient}. In the context of deep learning, \cite{shamir2018resnets} determined that the primary barrier to providing algorithmic results is in that the sequence of parameter iterates is possibly unbounded.

Now we take a closer look at asymmetric matrix factorization, which is a simple two-layer homogeneous model.

Consider the following formulation for factorizing a low-rank matrix:
\begin{align}
	\min_{\mat{U} \in \mathbb{R}^{d_1 \times r},\mat{V} \in \mathbb{R}^{d_2 \times r}} f\left(\mat{U},\mat{V}\right) = \frac{1}{2}\norm{\mat{U}\mat{V}^\top -\mat{M}^*}_F^2, \label{eqn:intro_mf_obj}
\end{align} where $\mat{M}^* \in \mathbb{R}^{d_1 \times d_2}$ is a matrix we want to factorize.
We observe that due to the homogeneity of $f$, it is not smooth\footnote{A function is said to be smooth if its gradient is $\beta$-Lipschitz continuous for some finite $\beta>0$.} even in the neighborhood of a globally optimum point.
To see this, we compute the gradient of $f$:
\begin{align}
	\frac{\partial f\left(\mat{U},\mat{V}\right)}{\partial \mat{U}} = \left(\mat{U}\mat{V}^\top - \mat{M}^*\right)\mat{V}, \qquad 	\frac{\partial f\left(\mat{U},\mat{V}\right)}{\partial \mat{V}} = \left(\mat{U}\mat{V}^\top - \mat{M}^*\right)^\top\mat{U}. \label{eqn:mf_gradient}
\end{align}
Notice that the gradient of $f$ is not homogeneous anymore.
Further, consider a globally optimal solution $(\mat U, \mat V)$ such that $\norm{\mat{U}}_F$ is of order $\epsilon$ and $\norm{\mat{V}}_F$ is of order $1/\epsilon$ ($\epsilon$ being very small).

A small perturbation on $\mat{U}$ can lead to dramatic change to the gradient of $\mat{U}$.
This phenomenon can happen for all homogeneous functions when the layers are unbalanced.
The lack of nice geometric properties of homogeneous functions due to unbalancedness makes first-order optimization methods difficult to analyze.

A common theoretical workaround is to artificially  modify the natural objective function as in \eqref{eqn:intro_mf_obj} in order to prove convergence.
In~\citep{tu2015low, ge2017no}, a regularization term for balancing the two layers is added to \eqref{eqn:intro_mf_obj}:\begin{align}
\min_{\vect{U}\in\mathbb{R}^{d_1 \times r},\vect{V}\in\mathbb{R}^{d_2 \times r}} \frac12 \norm{\mat{U}\mat{V}^\top-\mat{M}}_F^2 + \frac{1}{8}\norm{\mat{U}^\top\mat{U}-\mat{V}^\top\mat{V}}_F^2. \label{eqn:intro_mf_reg_obj}
\end{align}
For problem~\eqref{eqn:intro_mf_reg_obj}, the regularizer removes the homogeneity issue and the optimal solution becomes unique (up to rotation).
\citet{ge2017no} showed that the modified objective \eqref{eqn:intro_mf_reg_obj} satisfies (i) every local minimum is a global minimum, (ii) all saddle points are strict\footnote{A saddle point of a function $f$ is strict if the Hessian at that point has a negative eigenvalue.}, and (iii) the objective is smooth. These imply that (noisy) GD finds a global minimum \citep{ge2015escaping, lee2016gradient, panageas2016gradient}.

\begin{figure*}[t!]
	\centering
	\begin{subfigure}[t]{0.45\textwidth}
		\includegraphics[width=\textwidth]{./figs/regVSnot.pdf}
		\caption{Comparison of convergence rates of GD for objective functions~\eqref{eqn:intro_mf_obj} and~\eqref{eqn:intro_mf_reg_obj}.
			}
		\label{fig:mf_converge}
	\end{subfigure}
	\quad
	\begin{subfigure}[t]{0.45\textwidth}
		\includegraphics[width=\textwidth]{./figs/regVSnot_ratio.pdf}
		\caption{
			Comparison of quantity $\norm{\mat{U}}_F^2 / \norm{\mat{V}}_F^2$ when running GD for objective functions~\eqref{eqn:intro_mf_obj} and~\eqref{eqn:intro_mf_reg_obj}.
		}
					\label{fig:balanced_norm}
	\end{subfigure}
	\caption{Experiments on the matrix factorization problem with objective functions~\eqref{eqn:intro_mf_obj} and~\eqref{eqn:intro_mf_reg_obj}.
		Red lines correspond to running GD on the objective function~\eqref{eqn:intro_mf_obj}, and
		blue lines correspond to running GD on the objective function~\eqref{eqn:intro_mf_reg_obj}.
	}
	\label{fig:homogeneity}
\end{figure*}

On the other hand, empirically, removing the homogeneity is not necessary.
We use GD with random initialization to solve the optimization problem~\eqref{eqn:intro_mf_obj}.
Figure~\ref{fig:mf_converge} shows that even \emph{without} regularization term like in the modified objective~\eqref{eqn:intro_mf_reg_obj} GD with random initialization converges to a global minimum and the convergence rate is also competitive.
A more interesting phenomenon is shown in Figure~\ref{fig:balanced_norm} in which we track the Frobenius norms of $\mat{U}$ and $\mat{V}$ in all iterations. The plot shows that the ratio between norms remains a constant in all iterations.
Thus the unbalancedness does not occur at all!
In many practical applications, many models also admit the homogeneous property (like deep neural networks) and first order methods often converge to a balanced solution.
A natural question arises: \begin{center}
\textbf{Why does GD balance multiple layers and converge in learning homogeneous functions?}
\end{center}

In this paper, we take an important step towards answering this question.
Our key finding is that the gradient descent algorithm provides an implicit regularization on the target homogeneous function.
First, we show that on the gradient flow (gradient descent with infinitesimal step size)  trajectory induced by any differentiable loss function, for a large class of homogeneous models, including fully connected and convolutional neural networks with linear, ReLU and Leaky ReLU activations, the differences between squared norms across layers remain invariant.
Thus, as long as at the beginning the differences are small, they remain small at all time.
Note that small differences arise in commonly used initialization schemes such as  $\frac{1}{\sqrt{d}}$ Gaussian initialization or Xavier/Kaiming initialization schemes~\citep{glorot2010understanding,he2016deep}.

Our result thus explains why using ReLU activation is a better choice than sigmoid from the optimization point view.

For linear activation, we prove an even stronger invariance for gradient flow: we show that $\mat{W}^{(h)} (\mat{W}^{(h)})^\top  - (\mat{W}^{(h+1)})^\top \mat{W}^{(h+1)} $ stays invariant over time, where $\mat{W}^{(h)}$ and $\mat{W}^{(h+1)}$ are weight matrices in consecutive layers with linear activation in between.

Next, we go beyond gradient flow and consider gradient descent with positive step size.
We focus on the asymmetric matrix factorization problem~\eqref{eqn:intro_mf_obj}.
Our invariance result for linear activation indicates that $\mat{U}^\top \mat{U} - \mat{V}^\top\mat{V}$ stays unchanged for gradient flow.
For gradient descent,  $\mat{U}^\top \mat{U} - \mat{V}^\top\mat{V}$ can change over iterations.
Nevertheless we show that if the step size decreases like $\eta_t = O\left(t^{-\left( \frac12+\delta\right)} \right)$ ($0<\delta\le\frac12$), $\mat{U}^\top \mat{U} - \mat{V}^\top\mat{V}$ will remain small in all iterations.
In the set where $\mat{U}^\top \mat{U} - \mat{V}^\top \mat{V}$ is small, the loss is coercive, and gradient descent thus ensures that all the iterates are bounded.
Using these properties, we then show that gradient descent converges to a globally optimal solution.
Furthermore, for rank-$1$ asymmetric matrix factorization, we give a finer analysis and show that randomly initialized gradient descent with \emph{constant} step size converges to the global minimum at a globally linear rate.

\subsection{Related Work}
\label{sec:rel} \input{rel.tex}

\subsection{Paper Organization}
The rest of the paper is organized as follows.

In Section~\ref{sec:conserved}, we present our main theoretical result on the implicit regularization property of gradient flow for optimizing neural networks.
In Section~\ref{sec:mf}, we analyze the dynamics of randomly initialized gradient descent for asymmetric matrix factorization problem with unregularized objective function~\eqref{eqn:intro_mf_obj}.
In Section~\ref{sec:exp}, we empirically verify the theoretical result in Section~\ref{sec:conserved}.
We conclude and list future directions in Section~\ref{sec:con}.
Some technical proofs are deferred to the appendix.

\subsection{Notation}
We use bold-faced letters for vectors and matrices.
For a vector $\vect x$, denote by $\vect x[i]$ its $i$-th coordinate.
For a matrix $\vect A$, we use $\mat A[i, j]$ to denote its $(i, j)$-th entry, and use $\mat A[i, :]$ and $\mat A[:, j]$ to denote its $i$-th row and $j$-th column, respectively (both as column vectors).
We use $\norm{\cdot}_2$ or $\norm{\cdot}$ to denote the Euclidean norm of a vector, and use $\norm{\cdot}_F$ to denote the Frobenius norm of a matrix.
We use $\langle \cdot, \cdot \rangle$ to denote the standard Euclidean inner product between two vectors or two matrices.
Let $[n] = \{1, 2, \ldots, n\}$.


TITLE: How to get this result of integral?
QUESTION [1 upvotes]: Statement
\begin{equation}
\int_{\mathbb R} \exp \left( -2\pi (\frac{x}{\sqrt{2}})^2 \right) \exp\left( -i2 \pi \frac {x}{\sqrt{2}} \cdot f \right) dx
= \exp \left( -\pi f^{2} / 2 \right)
\end{equation}
My attempt based on J.G.'s tips
Call the integral I(f).
\begin{equation}
I(f) = \int_{\mathbb R} \left( -\pi x^{2} - i \sqrt{2} \pi x f \right) dx
\end{equation}
Integration by parts: $dv = dx$, $u = I(f)$, $v = x$, and $du = \delta I / \delta f$ so
\begin{equation}
\int_{\mathbb R} u dv = I(f) \cdot x - \int_{\mathbb R} x \frac{\delta I}{\delta f}
\end{equation}

How can you get the second power in the final result in the integration?

REPLY [2 votes]: We are computing here the Fourier transform of a Gaussian. It is a basic fact of Fourier theory that the result is again a Gaussian, appearing as a function of the "frequency variable". This can be proven using residue calculus, or applying Green's theorem to a suitable setup in ${\mathbb R}^2$. In this way one obtains, e.g.,
$$\int_{-\infty}^\infty e^{-x^2/2}\>\cos(\lambda x)\>dx=\sqrt{2\pi}\>e^{-\lambda^2/2}\ .$$
The rest is symmetry and scaling variables.


TITLE: Determine a subspace in R^5
QUESTION [0 upvotes]: I'm having trouble with this question:
For (c) obviously I can prove that by the "Closed under scalar multiplication"
But the other two I am a bit confused. Hope someone might shed some light on this.Thank you.
For each of the following subsets $S$ of $\mathbb{R}^5$
, determine if $S$ is a subspace. If yes, prove so (for
example by checking the three properties). If no, show by example that one of the properties
fails.
(a) $S$ the set of all vectors with all entries rational numbers.
(b) $S = \{v \in \mathbb{R}^5
|v · (4, −1007, 0, −1, 356) = 0\}$
(c) $S = \{v \in \mathbb{R}^5
|v · v ≥ 0\}$

REPLY [0 votes]: So this gets answered:
a) No, a simple counterexample is $(1,0,0,0,0)$ and the scalar $e\in\mathbb{R}$.
b) As $0\cdot v=0$ for any $v\in\mathbb{R}^5$, zero is in there. For $v,w\in S$ we have $(v+w)\cdot(4,-1007,0,-1,356)=v\cdot(4,-1007,0,-1,356)+w\cdot(4,-1007,0,-1,356)=0+0=0$. Any scalar multiple comes out of the dot product, so $\lambda v\cdot(-4,1007,0,-1,356)=0$, hence this is a subspace.
c) For any $v\in\mathbb{R}^n$ we have $v\cdot v\ge0$ and $v\cdot v=0$ iff $v=0$, so this is a subspace which is equal to $\mathbb{R}^5$.


text:
\subsection{Bounds}\label{ssec:bounds}

One of the crucial steps in constructing the homomorphism between $RFH(H)$ and $RFH(H_0)$ is to establish $L^\infty$-bounds on $\mathcal{M}_{\operatorname{hyb}}(\Lambda_0,\Lambda)$.

To formulate the $L^\infty$-bounds in Proposition \ref{prop:hybBound} and Lemma \ref{lem:compact} we introduce the following notation: for a compact subset $N\subseteq \Sigma$ and a connected component $\Lambda_{0} \subseteq \Crit(\cA^{H_{0}})$ we denote
\begin{align*}
\mathcal{C}({\cA^{H}},N) & \coloneqq  \left\lbrace x\in \Crit(\mathcal{A}^H)\ \Big|\ |\mathcal{A}^H(x)|>0 \quad \textrm{or}\quad x\in N\times\{0\}\right\rbrace,
\label{eqn:CAHY}\\
\mathcal{N}_{\operatorname{hyb}}(\Lambda_0, N) & \coloneqq \left\lbrace (u_0,u) \in \mathcal{M}_{\operatorname{hyb}}(\Lambda_0,\Sigma{\times}\{0\})\ \Big|\ \lim_{s\to +\infty}u(s)\in N \right\rbrace,
\end{align*}
For a pair of connected components $(\Lambda_{0},\Lambda) \subseteq \Crit(\cA^{H_{0}}) \times\left(\Crit(\cA^H)\big\backslash (\Sigma{\times}\{0\})\right)$ we denote $\mathcal{N}_{\operatorname{hyb}}(\Lambda_0, \Lambda)\coloneqq \mathcal{M}_{\operatorname{hyb}}(\Lambda_0, \Lambda)$.

\begin{prop}\label{prop:hybBound}
Consider a compact subset $N\subseteq \Sigma$ and a pair of connected components $(\Lambda_{0},\Lambda) \subseteq \Crit(\cA^{H_{0}}) \times\mathcal{C}(\cA^{H},N)$,
such that $a \leq \cA^{H_{0}}(\Lambda_0)\leq\cA^{H}(\Lambda)\leq b$.
Then the corresponding moduli space  $\mathcal{N}_{\operatorname{hyb}}(\Lambda_0, \Lambda)$ admits uniform $L^\infty$-bounds, which depend only on $a,b$ and $N$.
\end{prop}
\begin{proof}
First observe that by adapting the result in \cite[Prop.\ 6.2]{pasquotto2017} to the hybrid problem we obtain
\begin{equation}
\sup\left\lbrace \|u^\pm(\pm s)\|_{L^2(S^1)\times\R}\ \Big|\  (u^-,u^+)\in\mathcal{N}_{\operatorname{hyb}}(\Lambda_0, \Lambda),\ s\geq 0\right\rbrace<+\infty.\label{L2bounds}
\end{equation}
Moreover, there exists $\varepsilon_0>0$, such that
\begin{align}
\sup\left\lbrace \begin{array}{c|c}
& (u^-,u^+)\in\mathcal{N}_{\operatorname{hyb}}(\Lambda_0, \Lambda),\ s\leq 0,\\
{\smash{\raisebox{.5\normalbaselineskip}{ $\|u^-(s)\|_{L^\infty\times\R}$}}} &
\|\nabla_{J_0} \mathcal{A}^{H_0}(u^-(s))\|< \varepsilon_0
\end{array}
\right\rbrace<+\infty,\label{EpsiBnds1}\\
\sup\left\lbrace \begin{array}{c|c}
& (u^-,u^+)\in\mathcal{N}_{\operatorname{hyb}}(\Lambda_0, \Lambda),\ s\geq 0,\\
{\smash{\raisebox{.5\normalbaselineskip}{ $\|u^+(s)\|_{L^\infty\times\R}$}}} &
\|\nabla_J \mathcal{A}^{H}(u^+(s))\|< \varepsilon_0
\end{array}
\right\rbrace<+\infty. \label{EpsiBnds2}
\end{align}
and all the bounds depend only on $a,b$ and $N$.

Next, we use a maximum principle argument to prove uniform bounds on the fragment of the Floer trajectories, where the action derivation is greater than $\varepsilon_0$.

For $(u^-,u^+)=((v^-,\eta^-),(v^+,\eta^+))\in\mathcal{N}_{\operatorname{hyb}}(\Lambda_0, \Lambda)$ define a function
\begin{align*}
 r & \hspace{2pt} \colon    (-\infty,0]\times S^1 \to \mathbb{R},\\
r (s,t) &  \coloneqq  \frac{1}{4}\left( \|v^-(s,t)\|^2+\|v^+(-s,t)\|^2\right).
\end{align*}
Using the function $F$ defined as $\frac{1}{4}\|\cdot\|^2$ we can rewrite $r$ as
\[
r(s,t)= F\circ v^-(s,t)+F \circ v^+(-s,t).
\]
The function $F$ is plurisubharmonic, which means that $-dd^\mathbb{C}F=\omega$.

By \eqref{EpsiBnds1} and \eqref{EpsiBnds2} we know that there exists $c_0>0$, such that for every $(s,t)\in r^{-1}([c_0,+\infty))$ we have
\begin{equation}
\|\nabla_{J_0} \cA^{H_0}(u^-(s))\| \ge \varepsilon_0, \qquad  \|\nabla_J \cA^{H}(u^+(-s))\| \geq \varepsilon_0.
\label{NablaBound}
\end{equation}
On the other hand, by Lemma \ref{energy} we have the following bound:
\[
b-a\geq E(u^-,u^+)=\int_{-\infty}^0\|\nabla_{J_0} \cA^{H_0}(u^-(s))\|^2ds+\int_0^{\infty}\|\nabla_J \cA^{H}(u^+(s))\|^2ds.
\]
Therefore, for every connected component $\Omega \subseteq r^{-1}([c_0,+\infty))$ there exist $s_0,s_1 \geq 0$, such that
\[
\Omega \subseteq [s_0,s_1]\times S^1\quad \textrm{and}\quad |s_1-s_0|\leq \frac{b-a}{2\varepsilon_0^2}.
\]
Since \eqref{L2bounds} and \eqref{NablaBound} are both satisfied, we can use \cite[Thm.\ 7.1]{pasquotto2017} and conclude that there exists a function $f \colon  (-\infty,0]\times S^1 \to \mathbb{R}$, such that $\triangle r \geq f$ and the $L^2$-norm of $f$ is bounded on $\Omega$ and the bound depends only on $a,b$ and $N$.

Now, if $\partial \Omega \cap (\{0\}{\times} S^1)=\emptyset$, then we can apply the Aleksandrov Maximum Principle \cite[Thm.\ 9.1]{gilbarg1998} to deduce that there exists $c_1>0$, such that
\begin{equation}
\sup_\Omega r \leq \sup_{\partial \Omega}r+c_1\|f\|_{L^{2}(\Omega)}=c_0+c_1\|f\|_{L^{2}(\Omega)}<+\infty, \label{limit}
\end{equation}
and the bound depends only on $a,b$ and $N$.

However, if $\partial \Omega \cap \big(\{0\}{\times} S^1\big)\neq\emptyset$ then we need to check an additional assumption. More precisely we would like to show that $\partial_sr \geq 0$ on $\partial \Omega \cap (\{0\}{\times} S^1)$ to be able to apply the Aleksandrov Maximum Principle for half cylinders \cite[Thm.\ 2.8]{Abbon2009} for \eqref{limit}.

Denote
\[
\sigma(v^+)=: (v_0,v_1)\in C^\infty\left(\R\times S^1, T^*\R^k\right)\times C^\infty\left(\R\times S^1,T^*\R^{n-k}\right),
\]
where $\sigma$ is the splitting from \eqref{splitting}. Then (with a slight abuse of notation of $F$)
\begin{equation}\label{dRho}
\partial_sr= dF(\partial_s v^-)-dF(\partial_sv_0)-dF(\partial_sv_1).
\end{equation}
By the coupling condition \eqref{coupling} we have $\eta^-(0)=\eta^+(0)$ and $\partial_tv^-(0,t)=\partial_t v_0(0,t)$. Since $J_0\in \scrJ_\star^k$ and $ J\in \scrJ_\star^n$, we can assume without loss of generality that for $(s,t)\in r^{-1}([c_0,+\infty))$, one has
\[
J_0(u^-(s,t),t) \equiv \mathbb{J}_k, \qquad J(u^+(-s,t),t) \equiv \mathbb{J}_n.
\]
Therefore by \eqref{Floer} we have
\[
\partial_s v_0(0)=\nabla_{\mathbb{J}_k} \cA^{H_0}(v_0(0))=\nabla_{\mathbb{J}_k} \cA^{H_0}(v^-(0))=\partial_s v^-(0).
\]
As a result, the first and second term in \eqref{dRho} cancel each other.

To calculate the last term let us make the following observation:
\begin{align}
dF(\partial_s v_1(0)) & = dF\left(\nabla \cA^{H_1}(v_1(0))\right)\nonumber \\
& = - d^{\mathbb{C}} F\left(\partial_t v_1(0)-\eta^+(0)X_{H_1}(v_1(0))\right). \label{dFC}
\end{align}
By \eqref{coupling} we have that $v_1(0)$ lies in the $0$-section $\chi_0$ and
$$
d^{\mathbb{C}}F\big|_{T\chi_0}=\frac{1}{2}\left(qdp -pdq\right)\big|_{T\chi_0}=0,
$$
thus the first term in \eqref{dFC} vanishes. For the second term of \eqref{dFC} observe that
\[
d^\mathbb{C}F(X_{H_1})=\langle \nabla H_1, \nabla F\rangle = H_1.
\]
As $H_1$ also vanishes on $\chi_0$, the whole third term in \eqref{dRho} vanishes and we conclude that $\partial_sr=0$ on $\{0\}\times S^1$. This allows us to apply the Aleksandrov Maximum Principle for half cylinders and prove \eqref{limit} also in case where $\partial \Omega \cap (\{0\}\times S^1)\neq\emptyset$.
\end{proof}


text:
\begin{document}

\title{Topological Entropy for Shifts of Finite Type Over $\mathbb{Z}$ and Tree}

\author[J-C Ban]{Jung-Chao Ban}
\address[Jung-Chao Ban]{Department of Mathematical Sciences, National Chengchi University, Taipei 11605, Taiwan, ROC.}
\address{Math. Division, National Center for Theoretical Science, National Taiwan University, Taipei 10617, Taiwan. ROC.}
\email{jcban@nccu.edu.tw}

\author[C-H Chang]{Chih-Hung Chang}

\address[Chih-Hung Chang]{Department of Applied Mathematics, National University of Kaohsiung, Kaohsiung 81148, Taiwan, ROC.}
\email{chchang@nuk.edu.tw}

\author[W-G Hu]{Wen-Guei Hu}
\address[Wen-Guei Hu]{College of Mathematics, Sichuan University, Chengdu, 610064, China}
\email{wghu@scu.edu.cn}

\author[Y-L Wu]{Yu-Liang Wu}
\address[Yu-Liang Wu]{Department of Applied Mathematics, National Chiao Tung University, Hsinchu 30010, Taiwan, ROC.}
\email{s92077.am08g@nctu.edu.tw}

\keywords{tree-SFT; topological entropy}
\subjclass[2010]{Primary 37B40}
\thanks{Ban and Chang are partially supported by the Ministry of Science and Technology, ROC (Contract No MOST 107-2115-M-259 -001 -MY2 and 107-2115-M-390 -002 -MY2). Hu is partially supported by the National Natural Science Foundation of China (Grant No.11601355).}

\date{June 15, 2020}

\baselineskip=1.2\baselineskip

\begin{abstract}
We study the topological entropy of hom tree-shifts and show that, although the topological entropy is not conjugacy invariant for tree-shifts in general, it remains invariant for hom tree higher block shifts. In \cite{PS-TCS2018, PS-DCDS2020}, Petersen and Salama demonstrated the existence of topological entropy for tree-shifts and $h(\mathcal{T}_X) \geq h(X)$, where $\mathcal{T}_X$ is the hom tree-shift derived from $X$. We characterize a necessary and sufficient condition when the equality holds for the case where $X$ is a shift of finite type. In addition, two novel phenomena have been revealed for tree-shifts. There is a gap in the set of topological entropy of hom tree-shifts of finite type, which makes such a set not dense. Last but not least, the topological entropy of a reducible hom tree-shift of finite type is equal to or larger than that of its maximal irreducible component.
\end{abstract}
\maketitle

\section{Introduction}

A $\mathbb{Z}^d$ shift space $X$ over alphabet $\mathcal{A}$ is a set of configurations which avoid any patterns labeled by $\mathcal{A}$ from some set $\mathcal{F}$; $X$ is a \emph{shift of finite type} (SFT) if $\mathcal{F}$ is finite. The study of $\mathbb{Z}^d$ SFTs is rife with numerous undecidability issues whenever $d \geq 2$. For instance, it is not even decidable if $X$ is nonempty. We refer the reader to \cite{Berger-MAMS1966, Kari-DM1996, Robinson-IM1971} for example.

In view of the complex dynamics of $\mathbb{Z}^d$ shift spaces as well as inspired by the physical models, the elucidation of \emph{hom-shifts} is imperative. A hom-shift is a nearest neighbor SFT which is symmetric and isotropic; more explicitly, if $a, b \in \mathcal{A}$ are forbidden to sit next to each other in some coordinate direction, then they are forbidden to sit next to each other in all coordinate directions. Many important SFTs, such as the hard square shift and the $n$-colored chessboard, arise as hom-shifts. Chandgotia and Marcus \cite{CM-PJM2018} investigated the mixing properties of hom-shifts and related them to some question in graph theory therein.

Tree-shifts, which are shift spaces defined on free semigroups, have received extensive attention recently since they exhibit the natural structure of one-dimensional symbolic dynamics while equipped with multiple directional shift transformations. The dynamical phenomena of shift spaces on trees is fruitful since they constitute an intermediate class of symbolic dynamics between $\mathbb{Z}$ and $\mathbb{Z}^{d}$, $d\geq 2$. See \cite{AB-TCS2012, AB-TCS2013, BC-JMP2017, BC-TAMS2017, CCF+-TCS2013, FF-2012} and the references therein for instance.

Aside from the elucidation of $\mathbb{Z}^d$ hom-shifts, investigating the hom tree-shifts is an alternative path on the study of abstract tree-shifts of finite type. Mairesse and Marcovici \cite{MM-IJFCS2017} constructed a stationary Markov measure, which is a uniform measure, for hom-shifts on binary tree. Petersen and Salama \cite{PS-TCS2018, PS-DCDS2020} demonstrated that the topological entropy of arbitrary tree-shift exists as the infimum of the growth rate of $n$-blocks. In addition, they revealed that the topological entropy of $X$ is no larger than the topological entropy of the hom tree-shift derived from $X$.

This paper, inspired by \cite{PS-TCS2018, PS-DCDS2020}, aims at the relations between $\mathbb{Z}$-SFT $X$ and its associated hom tree-shift $\mathcal{T}_X$, especially on the discussion of topological entropy. Theorem \ref{thm:irr_H_condition} characterizes a necessary and sufficient condition for the equality of topological entropy of $X$ and $\mathcal{T}_X$ when $X$ is Markovian. Although the topological entropy is not conjugacy invariant for tree-shifts in general (see \cite{Bowen-2019} for a brief survey), Theorem \ref{thm:n_block_entropy_inv} reveals that the topological entropy remains the same for hom tree-shifts arose from higher block shifts; this, together with Theorem \ref{thm:irr_H_condition}, gives a criterion for the equality of topological entropy of $X$ and $\mathcal{T}_X$ for general SFTs. In the mean time, there are interesting phenomena, such as the existence of an SFT $X$ and $n \in \mathbb{N}$ such that $\mathcal{T}_X \ncong \mathcal{T}_{X^{[n]}}$ (Proposition \ref{prop:homTSFT-higher-block-not-conjugate}), there are SFTs $X, Y$ with $X \cong Y$ but $h(\mathcal{T}_X) \neq h(\mathcal{T}_Y)$ (Proposition \ref{prop:counterexamples}), which remain to give deeper investigation.

Aside from the elucidation of relations between $X$ and $\mathcal{T}_X$, two novel phenomena in tree-shifts are also of interest. It is well-known that the set of topological entropy of SFTs is dense in the closed interval $[0, \log |\mathcal{A}|]$ (cf.~\cite{Des-IM2006} and the references therein) and the topological entropy of $X$ is attained by its maximal irreducible component (cf.~\cite{LM-1995}). Proposition \ref{prop:entropy_gap} specifies a gap in the set of topological entropy of hom tree-SFTs, and Proposition \ref{prop:entropy_large_irred_component} addresses that $\mathcal{T}_X$ has larger topological entropy than that of any of its irreducible components in general.

\subsection{Notations and Definitions}
Let $d \geq 2$ and $\Sigma = \{0, 1, \ldots, d-1\}$. The $d$-tree $\Sigma^* = \cup_{n \geq 0} \Sigma^n$ is the set of all finite words on $\Sigma$ and is naturally visualized as the Cayley graph of the free semigroup on $d$ generators. The empty word $\epsilon$ is the only word of zero length and corresponds to the root of the tree and the identity element of the semigroup. Let $\mathcal{A}$ be a finite alphabet. A \emph{labeled tree} is a function $t: \Sigma^* \to \mathcal{A}$. For each node $w \in \Sigma^*$, $t_w := t(w)$ refers to the label attached to $w$. Denote by $\Delta_n := \cup_{i=0}^{n}\Sigma^i$ the initial subtree of the $d$-tree. An \emph{$n$-block} is a function $u : \Delta_n \rightarrow \mathcal{A}$. We say that a block $u$ appears in a labeled tree $t$ if there is a node $s \in \Sigma^*$ such that $t_{s w}=u_w$ for all $w \in \Delta_n$; otherwise, $t$ avoids $u$. A \emph{tree-shift} is a set $\treeshift{} \subseteq \mathcal{A}^{\Sigma_k^*}$ of labeled trees which avoid all of a certain set of forbidden blocks.

For each binary matrix $A$ indexed by $\mathcal{A}$, there associate a Markov shift $\mathsf{X}_A$ and a hom Markov tree-shift $\mathcal{T}_A$ defined as
$$
\mathsf{X}_A = \{x \in \mathcal{A}^{\mathbb{N}}: A_{x_i, x_{i+1}} = 1 \text{ for all } i \in \mathbb{N}\}
$$
and
$$
\mathcal{T}_A = \{t \in \mathcal{A}^{\Sigma^*}: A_{t_w, t_{wi}} = 1 \text{ for all } w \in \Sigma^*, i \in \Sigma\},
$$
respectively. As the topological entropy of $\mathsf{X}_A$,
$$
h(\mathsf{X}_A) = \lim_{n \to \infty} \frac{\log |B_n(\mathsf{X}_A)|}{n},
$$
measures the growth rate of feasible $n$-words with respect to their support, the topological entropy of $\mathcal{T}_A$,
$$
h(\mathcal{T}_A) = \lim_{n \to \infty} \frac{\log |B_n(\mathcal{T}_A)|}{|\Delta_n|},
$$
is defined analogously; herein, $B_n (\mathcal{T}_A)$ refers to the set of $n$-blocks appearing in $\mathcal{T}_A$. Notably, we abuse $B_n(\mathsf{X}_A)$ and $B_n(\mathcal{T}_A)$ to represent the sets of $n$-blocks in $\mathsf{X}_A$ and $\mathcal{T}_A$, respectively, if there is no confusion.

\section{Hom Tree-Shift of Finite Type with Larger Topological Entropy}

Suppose $A$ is a binary matrix indexed by the alphabet $\mathcal{A}$. Although $|\Delta_n| \gg n$, Peteren and Salama \cite{PS-TCS2018} revealed a quite interesting property that $h(\mathsf{X}_A) \leq h(\mathcal{T}_A)$. It is of interest whether there is a criterion for the equality. Let
$$
M:=\max_{i} \sum_j A_{i,j}
\quad \text{and} \quad
m:= \min_{i} \sum_j A_{i,j}
$$
be the maximal and minimal row sum of $A$, respectively. Theorem \ref{thm:irr_H_condition} yields a necessary and sufficient condition for determining when the equality holds.

\begin{theorem} \label{thm:irr_H_condition}
Suppose $\mathcal{T}_A$ is a hom Markov tree-shift induced by $A$ and $A$ is irreducible. Then, $h(\mathsf{X}_A)=h(\mathcal{T}_A)$ if and only if $M=m$.
\end{theorem}

Estimation of growth rate of $n$-blocks in $\mathcal{T}_A$ is essential for the calculation of topological entropy. The following lemmas demonstrate that the condition $M>m$ yields a subset of $\mathbb{N}$, that is of positive lower Banach density. For $n_1 \leq n_2 \in \mathbb{N}$, denote by
$$
[n_1, n_2] = \{n \in \mathbb{N}: n_1 \leq n \leq n_2\}
$$
the set of integers between $n_1$ and $n_2$.

\begin{lemma} \label{lem:universal_gap_property}
Suppose $A \in \{0,1\}^{k \times k}$ is an irreducible matrix with $M > m$, and $x(n) = (x_1(n), x_2(n), \ldots, x_k(n)) \in \mathbb{N}^k$ is the vector such that $x_i(n)$ refers to the number of elements in the set $\{u \in B_n (\mathcal{T}_{A}): u_\epsilon=i\}$. For each $\varepsilon \in (0,(\frac{M}{m})^{\frac{1}{d+1}}-1)$, let
$$
S=S(\varepsilon):=\{n \in \mathbb{N}: \max_{i_1,i_2} \frac{(A x(n))_{i_1}}{(A x(n))_{i_2}} > 1+\varepsilon\}.
$$
Then, there exists $N \in \mathbb{N}$ such that $[n, n+N] \cap S \neq \varnothing$ for every $n \ge 0$.
\end{lemma}
\begin{proof}
Since $\varepsilon \in (0,(\frac{M}{m})^{\frac{1}{d+1}}-1)$, there exists $N \in \mathbb{N}$ such that $[\frac{M}{m} (\frac{1}{1+\varepsilon})^{d+1}]^{N} > (1+\varepsilon)^2$. We prove this $N$ satisfy the requirement by contradiction. Suppose there exists $n \in \mathbb{N}$ such that $[n,n+N] \subset \mathbb{N} \setminus S$, i.e.,
\begin{equation*}
\max_{i_1,i_2} \frac{(A x(n))_{i_1}}{(A x(n))_{i_2}} = \frac{\max_{i} \sum_{j=1}^k A_{i,j} x_j(n)}{\min_{i} \sum_{j=1}^k A_{i,j} x_j(n)} \le (1+\varepsilon).
\end{equation*}
Suppose $i_1^*, i_2^* \in \mathcal{A}$ such that $M = \sum_{j} A_{i_1^*,j}$ and $m = \sum_{j} A_{i_2^*,j}$. Then
\begin{align*}
&\frac{(A x(n+N))_{i_1^\ast}}{(A x(n+N))_{i_2^\ast}} = \frac{\sum_{j=1}^k A_{i_1^\ast,j} (\sum_{l=1}^k A_{j,l} x_l(n+N-1))^d}{\sum_{j=1}^k A_{i_2^\ast,j}(\sum_{l=1}^k A_{j,l} x_l(n+N-1))^d} \\
\ge & \frac{\sum_{j=1}^k A_{i_1^\ast,j} \min_i (\sum_{l=1}^k A_{i,l} x_l(n+N-1))^{d-1}( \sum_{l=1}^k A_{i_1^\ast,l} x_l(n+N-1))/(1+\varepsilon)}{\sum_{j=1}^k A_{i_2^\ast,j}\max_i (\sum_{l=1}^k A_{i,l} x_l(n+N-1))^{d-1}( \sum_{l=1}^k A_{i_2^\ast,l} x_l(n+N-1))(1+\varepsilon)}\\
\ge & \left[\frac{M}{m} \left(\frac{1}{1+\varepsilon}\right)^{d+1}\right] \frac{(A x(n+N-1))_{i_1^\ast}}{(A x(n+N-1))_{i_2^\ast}} \\
\ge & \left[\frac{M}{m} \left(\frac{1}{1+\varepsilon}\right)^{d+1}\right]^{N} \frac{(A x(n))_{i_1^\ast}}{(A x(n))_{i_2^\ast}} \\
\ge & \left[\frac{M}{m} \left(\frac{1}{1+\varepsilon}\right)^{d+1}\right]^{N} \frac{1}{1+\varepsilon} > 1+\varepsilon,
\end{align*}
which is a contradiction. The proof is thus complete.
\end{proof}

\begin{remark}
For every $\varepsilon \in (0,(\frac{M}{m})^{\frac{1}{d+1}}-1)$ and $n \in S(\varepsilon)$, express the components of $A x(n)$ in ascending order as
$$
(A x(n))_{i_1} \leq (A x(n))_{i_2} \leq \ldots \leq (A x(n))_{i_k}.
$$
The pigeonhole principle indicates that there exists $1 \leq l \leq k-1$ such that $\frac{(A x(n))_{i_{l+1}}}{(A x(n))_{i_{l}}} > (1+\varepsilon)^{\frac{1}{k-1}}$.
\end{remark}

\begin{lemma} \label{lem:holder_strict_inequality}
Suppose $\{v_i\}_{i=1}^k \subset (0,1)$ is given such that $\sum_{i=1}^k v_i = 1$. There exists a strictly increasing function $C:[1, \infty) \to [1, \infty)$ satisfying the following:
\begin{enumerate}
    \item $C(1)=1$,
    \item $\frac{\sum_{i=1}^k a_i^d w_i}{(\sum_{i=1}^k a_i w_i)^d} \ge C(\frac{a_{l+1}}{a_l}) \ge 1$ for all $1 \le l \le k-1$ and $0 < a_1 \le a_2 \le \ldots \le a_k$,
\end{enumerate}
where $\{w_i\}_{i=1}^k$ is an arbitrary permutation of $\{v_i\}_{i=1}^k$.
\end{lemma}
\begin{proof}
Suppose $\mathbf{w} = \{w_i\}_{i=1}^k$ is a permutation of $\{v_i\}$. Let $J_{\mathbf{w}} = J_{\mathbf{w}}(a_1, a_2, \ldots, a_k) := \sum_{i=1}^k a_i^d w_i$ and $I_{\mathbf{w}} = I_{\mathbf{w}}(a_1, a_2, \ldots, a_k) :=\sum_{i=1}^k a_i w_i$. By H\"{o}lder's inequality, we have
$$\frac{J_{\mathbf{w}}}{I_{\mathbf{w}}^d} \ge \frac{\sum_{i=1}^k a_i^d w_i}{(\sum_{i=1}^k (a_i w_i^{\frac{1}{d}})^d)(\sum_{i=1}^k (w_i^{\frac{d-1}{d}})^{\frac{d}{d-1}})^{d-1}} \ge 1.
$$
Observe that the partial differentiation of $\frac{J_{\mathbf{w}}}{I_{\mathbf{w}}^d}$ with respect to $a_j$,
\[
\frac{\partial }{\partial a_j} \frac{J_{\mathbf{w}}}{I_{\mathbf{w}}^d} = \frac{d \cdot I_{\mathbf{w}}^{d-1} w_j \cdot \sum_{i=1}^k a_i (a_j^{d-1} - a_i^{d-1}) w_i}{I_{\mathbf{w}}^{2 d}},
\]
is non-positive if $j=k$ and is non-negative if $j=1$. Hence, we have
\begin{equation} \label{eq:1}
\begin{aligned}
\frac{J_{\mathbf{w}}}{I_{\mathbf{w}}^d} & = \frac{a_1^d w_1 + a_2^d w_2 + \ldots + a_{k-1}^d w_{k-1} + a_k^d w_k}{(a_1 w_1 + a_2 w_2 + \ldots + a_{k-1} w_{k-1} + a_k w_k)^d} \\
& \ge \frac{a_1^d w_1 + a_2^d w_2 + \ldots + a_{k-1}^d (w_{k-1} + w_k)}{(a_1 w_1 + a_2 w_2 + \ldots + a_{k-1} (w_{k-1} + w_k))^d},
\end{aligned}
\end{equation} \label{eq:2}
and
\begin{equation}
\frac{J_{\mathbf{w}}}{I_{\mathbf{w}}^d} \ge \frac{a_2^d (w_1+w_2) + a_3^d w_3 + \ldots + a_k^d w_k}{(a_2 (w_1+w_2) + a_3 w_3 + \ldots + a_k w_k)^d}.
\end{equation}
Inductively, we derive from \eqref{eq:1} and \eqref{eq:2} that
\begin{align*}
\frac{J_{\mathbf{w}}}{I_{\mathbf{w}}^d} & \ge \frac{a_l^d (w_1 + w_2 + \ldots + w_l) + a_{l+1}^d (w_{l+1} + w_{l+2} + \ldots w_k)}{(a_l (w_1 + w_2 + \ldots + w_l) + a_{l+1} (w_{l+1} + w_{l+2} + \ldots w_k))^d}
\end{align*}
for $1 \leq l \leq k-1$. Define
\begin{equation*}
C_{l,\mathbf{w}}(x):=\frac{(w_1 + w_2 + \ldots + w_l) + x^d (w_{l+1} + w_{l+2} + \ldots w_k)}{((w_1 + w_2 + \ldots + w_l) + x (w_{l+1} + w_{l+2} + \ldots w_k))^d}.
\end{equation*}
Then $C_{l, \mathbf{w}}(x)$ is strictly increasing on $[1,\infty)$ such that
\begin{equation*}
C_{l,\mathbf{w}}(1)=1,
\end{equation*}
and
\begin{equation*}
\frac{J_{\mathbf{w}}}{I_{\mathbf{w}}^d} \ge C_{l,\mathbf{w}}(\frac{a_{l+1}}{a_l}), \forall 1 \le l \le k-1.
\end{equation*}
The proof is thus complete by defining the function $C(x)$ as
\begin{equation*}
C(x):=\inf_{l,\mathbf{w}} C_{l,\mathbf{w}}(x).
\end{equation*}
\end{proof}

With the introduction of Lemmas \ref{lem:universal_gap_property} and \ref{lem:holder_strict_inequality}, we are in a position of proving Theorem \ref{thm:irr_H_condition}.

\begin{proof}[Proof of Theorem \ref{thm:irr_H_condition}]
Suppose $M = m$. It follows that the spectral radius of $A$ is $\rho_A = M$ and $x_i(2) = M^d$ for all $i$. Hence,
$$
h_{top}(\mathcal{T}_A) = \lim_{n \to \infty} \frac{\log (k M^{d + d^2 + \cdots + d^n})}{|\Delta_n|} = \log M = h_{top}(X_A).
$$

Conversely, suppose $M > m$. Let $\varepsilon \in (0,(\frac{M}{m})^{\frac{1}{d+1}}-1)$ be fixed and let $S=S(\varepsilon)$ be defined as in Lemma \ref{lem:universal_gap_property}. Since $A$ is irreducible, there exists a probability eigenvector $v=(v_1, v_2, \ldots, v_k)$ such that $v^T A = \rho(A) v^T$ with $v_i > 0$ for all $1 \le i \le k$. For every $n \in \mathbb{N}$, let $1 \leq l \leq k$ such that $\frac{(A x(n))_{i_{l+1}}}{(A x(n))_{i_1}} > (1+\varepsilon)^{\frac{1}{k-1}}$, and let $\mathbf{w}$ be the permutation $\{w_j\}_{j=1}^k=\{v_{i_j}\}_{j=1}^k$. It follows from Lemma \ref{lem:holder_strict_inequality} that there exists a strictly increasing function $C:[1,\infty) \to [1,\infty)$ with $C(1)=1$ satisfying
\begin{equation*}
    \frac{J_{\mathbf{w}}((A x(n))_{i_1},(A x(n))_{i_2},\ldots,(A x(n))_{i_k})}{I_{\mathbf{w}}^d((A x(n))_{i_1},(A x(n))_{i_2},\ldots,(A x(n))_{i_k})} \ge C\left(\frac{(A x(n))_{i_{l+1}}}{(A x(n))_{i_l}}\right) \ge C((1+\varepsilon)^{\frac{1}{k-1}}).
\end{equation*}
By writing
\begin{equation*}
\gamma(n):= \begin{cases}
C((1+\varepsilon)^{\frac{1}{k-1}}), & \text{if } n \in S;\\
1 & \text{if } n \notin S,
\end{cases}
\end{equation*}
we deduce that
\begin{equation*}
\frac{\sum_{i=1}^k [(A x(n))_i]^d v_i}{\left(\sum_{i=1}^k (A x(n))_i v_i \right)^d} = \frac{J_{\mathbf{w}}((A x(n))_{i_1},(A x(n))_{i_2},\ldots,(A x(n))_{i_k})}{I_{\mathbf{w}}^d((A x(n))_{i_1},(A x(n))_{i_2},\ldots,(A x(n))_{i_k})} \ge \gamma(n).
\end{equation*}
Furthermore,
\begin{align*}
& \hphantom{\ = } \sum_{i=1}^k x_i(n) v_i = \sum_{i=1}^k [(A x(n-1))_i]^d v_i \\
& = \frac{\sum_{i=1}^k [(A x(n-1))_i]^d v_i}{\left(\sum_{i=1}^k (A x(n-1))_i v_i \right)^d} \cdot \rho(A)^d \cdot \left(\sum_{i=1}^k x_i(n-1) v_i \right)^d  \\
& \ge \gamma(n-1) \cdot\rho(A)^d \cdot \left(\sum_{i=1}^k x_i(n-1) v_i \right)^d \\
& \ge \gamma(n-1) \gamma(n-2)^{d} \cdot\rho(A)^{d+d^2} \cdot \left(\sum_{i=1}^k x_i(n-2) v_i \right)^{d^2} \\
& \ge \gamma(n-1) \gamma(n-2)^{d} \ldots \gamma(0)^{d^{n-1}}\rho(A)^{d+d^2+\cdots+d^n} \cdot \left(\sum_{i=1}^k x_i(0) v_i \right)^{d^n} \\
& = \gamma(n-1) \gamma(n-2)^{d} \ldots \gamma(0)^{d^{n-1}}\rho(A)^{d+d^2+\cdots+d^n}.
\end{align*}
Now we know that
\begin{equation*}
\frac{\log B_n (\mathcal{T}_{\mathbf{A}})}{|\Delta_n|} \ge \frac{|\Delta_n| \cdot \log\rho(A)}{|\Delta_n|} -\frac{\log\rho(A)}{|\Delta_n|} + \frac{\sum_{i \in S \cap [0,n-1]} d^{n-1-i}}{\sum_{0\le i \le n} d^i} \log C((1+\varepsilon)^{\frac{1}{k-1}}).
\end{equation*}
By letting $n$ tend to inifinity on both sides we derive $h(\mathcal{T}_{A}) > h_{top} (X_A)$, since $S$ is of positive lower Banach density.
\end{proof}

\section{Conjugacy Invariant of Topological Entropy of Tree-Shifts}

As an application of results of the previous section, we consider the topological conjugacy and topological entropy for hom tree-shifts of finite type. Shift spaces $X$ and $Y$ are topological conjugate, denoted by $X \cong Y$, if there exists a one-to-one correspondence $\phi: X \to Y$ induced by a block map $\Phi: B_m(X) \to \mathcal{A}(Y)$ for some $m \in \mathbb{N}$. For $n \in \mathbb{N}$, the $n$th higher block shift of $X$ is
$$
X^{[n]} = \{(y_i)_{i \in \mathbb{N}} \in (\mathcal{A}(X)^{n})^{\mathbb{N}}: \text{ $\exists x \in X$ such that } y_i = x_i \cdots x_{i+n-1} \forall~i \in \mathbb{N}\}.
$$
It is easy to see that $X \cong X^{[n]}$ for all $n$ (cf.~\cite{LM-1995}). Similarly, two tree-shifts $\mathcal{T}$ and $\mathcal{S}$ are topological conjugate if there is a one-to-one correspondence $\psi: \mathcal{T} \to \mathcal{S}$ induced by a block map $\Psi: B_m(\mathcal{T}) \to \mathcal{A}(\mathcal{S})$ for some $m \in \mathbb{N}$. Ban and Chang \cite{BC-TAMS2017} demonstrated that $\mathcal{T}^{[n]} \cong \mathcal{T}$ for each $n \in \mathbb{N}$, where
$$
\mathcal{T}^{[n]} = \{t' \in B_n(\mathcal{T})^{\Sigma^*}: \text{ there exists $t \in \mathcal{T}$ such that } t'_w = t_{w\Delta_n} \forall~w \in \Sigma^*\}
$$
is the $n$th higher block tree-shift of $\mathcal{T}$.

A subset $\mathbf{s}=\{s_i\}_{i \in  \mathbb{N}} \subset \Sigma^*$ is called a \emph{chain} if $s_1 = \epsilon$ and $s_{i+1} \in s_i \Sigma$ for all $i \geq 1$; in other words, $\mathbf{s}$ is an infinite path initiated at the root. Define $\pi_{\mathbf{s}}: \mathcal{A}^{\Sigma^*} \to \mathcal{A}^{\mathbb{N}}$ as $(\pi_{\mathbf{s}} t)_i = t_{s_i}$ for $i \in \mathbb{N}$. For each shift space $X \subseteq \mathcal{A}^{\mathbb{N}}$, the corresponding hom tree-shift $\mathcal{T}_X$ is defined as
$$
\mathcal{T}_X = \{t \in \mathcal{A}^{\Sigma^*}: \pi_{\mathbf{s}} (t) \in X \text{ for every chain } \mathbf{s}\}.
$$
Although the topological entropy of tree-shifts is not conjugacy invariant in general (see \cite{Bowen-JAMS2010} for instance), Theorem \ref{thm:n_block_entropy_inv} indicates that it is invariant for hom tree higher block shifts. Notably, we call $\mathcal{T}_Y$ a \emph{hom tree higher block shift} if $Y = X^{[m]}$ is a higher block shift of some shift space $X$; a hom tree higher block shift may not be a higher block tree-shift generally.

\begin{theorem} \label{thm:n_block_entropy_inv}
Suppose $X$ is a shift space and $m \in \mathbb{N}$. Let $X^{[m]}$ be a higher block shift of $X$. Then $h(\mathcal{T}_X) = h(\mathcal{T}_{X^{[m]}})$.
\end{theorem}
\begin{proof}
Define $f: \mathcal{A}^m \to \mathcal{A}$ as $f(a_1, \ldots, a_m) = a_m$. Let $f_n: (\mathcal{A}^m)^{\Delta_n} \to \mathcal{A}^{\Delta_n}$ be defined as $(f_n(v))_w = f(v_w)$ for all $w \in \Delta_n$. We claim that $f_n(B_n(\mathcal{T}_{X^{[m]}})) \subseteq B_n(\mathcal{T}_X)$, and that $|B_n(\mathcal{T}_{X^{[m]}})| \le (|\mathcal{A}|)^{m-1} |B_n(\mathcal{T}_X)|$.

For every $v \in B_n(\mathcal{T}_{X^{[m]}})$, write $a_1 \ldots a_{m-1} \in \mathcal{A}^{m-1}$ such that $v_\epsilon = (a_1 a_2 \ldots a_{m-1} a)$ for some $a \in \mathcal{A}$. This implies $f_n(v) \in B_n(\mathcal{T}_X)$, since for all $s_1, \ldots, s_i \in \Sigma$ there is an admissible block $v_{s_1} v_{s_1 s_2} \ldots v_{s_1 s_2 \ldots s_i} \in B(X^{[m]})$ such that $f(v_{s_1}) f(v_{s_1 s_2}) \ldots f(v_{s_1 s_2 \ldots s_i}) \in B(X)$. Therefore, $f_n(B_n(\mathcal{T}_{X^{[m]}})) \subseteq B_n(\mathcal{T}_X)$ and $|B_n(\mathcal{T}_{X^{[m]}})| \le |\mathcal{A}|^{m-1} \cdot |B_n(\mathcal{T})|$. Hence, we have
\begin{align*}
    h(\mathcal{T}_{X^{[m]}}) & = \lim_{n \to \infty} \frac{\log |B_n(\mathcal{T}_{X^{[m]}})|}{|\Delta_n|} \\
    & \le \lim_{n \to \infty} \frac{(m-1) \log |\mathcal{A}| + \log |B_n(\mathcal{T}_X)|}{|\Delta_n|} = h(\mathcal{T}_X).
\end{align*}

On the other hand, for every $\overline{w} \in \Sigma^{m-1}$, define $g_{\overline{w},n}: B_n(\mathcal{T}_X) \to B_{n-m+1}(\mathcal{T}_{X^{[m]}})$ for $n \ge m$ as
\[
    (g_{\overline{w},n}(u))_{w} = (u_{\overline{w}_i} \ldots u_{\overline{w}_{m-1}} u_{w_1} \ldots u_{w_i}),
\]
where $w=w_1 w_2 \ldots w_i \in \Sigma^i$ and $\overline{w}_0=\epsilon$. It is seen that
\[
|B_n(\mathcal{T}_X)| \le {|\mathcal{A}|}^{|\Delta_{m-1}|} \sum_{\overline{w} \in \Sigma^{m-1}} |g_{\overline{w},n} (B_n(\mathcal{T}_X))| \le {|\mathcal{A}|}^{|\Delta_{m-1}|} {|B_{n-m+1}(\mathcal{T}_X)|}^{d^{m-1}}.
\]
Hence,
\begin{align*}
    h(\mathcal{T}_X) & = \lim_{n \to \infty} \frac{|B_n(\mathcal{T}_X)|}{|\Delta_n|} \\
    & \le \lim_{n \to \infty} \frac{|\Delta_{m-1}| \log |\mathcal{A}| + {d^{m-1}} \log |B_{n-m+1}(\mathcal{T}_X)|}{|\Delta_n|} = h(\mathcal{T}_{X^{[m]}}).
\end{align*}
This finishes the proof.
\end{proof}

\begin{remark}\label{rmk:intro_HBS}
Petersen and Salama \cite{PS-DCDS2020} indicated that $h(\mathcal{T}_X) \geq h(X)$ for any shift space $X$. It is of interest when the equality holds. Theorems \ref{thm:irr_H_condition} and \ref{thm:n_block_entropy_inv} provide a necessary and sufficient condition for the case where $X$ is an irreducible shift of finite type. More explicitly, each SFT $X$ is topological conjugate with its higher block shift $X^{[n]}$ which is Markovian for some $n \in \mathbb{N}$ (cf.~\cite{LM-1995}). Let $A^{[n]}$ be the adjacency matrix of $X^{[n]}$. Theorem \ref{thm:irr_H_condition} indicates whether $h(\mathcal{T}_{X^{[n]}}) = h(X^{[n]})$.
\end{remark}

\begin{proposition} \label{prop:converse_conjugacy}
	Suppose $X$ and $Y$ are shift spaces. If $\mathcal{T}_{X} \cong \mathcal{T}_{Y}$, then $X \cong Y$.
\end{proposition}
\begin{proof}
	Let $\phi: X \to Y$ and $\psi: Y \to X$ be maps induced by the block maps $\Phi:B_n(\mathcal{T}_{X}) \to \mathcal{A}(\mathcal{T}_{Y})$, $\Psi:B_m(\mathcal{T}_{Y}) \to \mathcal{A}(\mathcal{T}_{X})$ respectively, satisfying $\psi \circ \phi = Id_{\mathcal{T}_{X}}$ and $\psi \circ \phi = Id_{\mathcal{T}_{Y}}$. We first claim that if $t \in \mathcal{T}_{X}$ such that $t_w = t_s$ for all $w,s \in \Sigma^k$ and for all $k \ge 0$, then $(\phi(t))_{w} = (\phi(t))_{s}$ for all $w,s \in \Sigma^k$ and for all $k \ge 0$. Indeed, it follows from the fact $\phi$ is a sliding block code that
	\begin{equation*}
		(\phi(t))_w = (\sigma_w \phi(t))_\epsilon = (\phi(\sigma_w t))_\epsilon = (\psi(\sigma_s t))_\epsilon = (\sigma_s \phi(t))_\epsilon = (\phi(t))_w.
	\end{equation*}
	Note that this property is also share by $\psi$ since it is also a sliding block code.

	Now suppose $u=(u_0 u_1 \cdots u_n) \in B_{n+1}(X)$ (respectively, $B_{m+1}(Y)$). We denote by $\overline{u} \in B_n(\mathcal{T}_{X})$ (respectively, $B_m(X)$) the block such that $\overline{u}_w := u_{\norm{w}}$ for all $w \in s(u)$. We define block maps $\Phi':B_{n+1}(X) \to \mathcal{A}(Y)$, $\Psi':B_{m+1}(Y) \to \mathcal{A}(X)$ on $X$ and $Y$ respectively as
	\begin{align*}
	\Phi'(u):=\Phi(\overline{u}),
	\end{align*}
	and
	\begin{align*}
	\Psi'(u):=\Psi(\overline{u}).
	\end{align*}
	It follows from our claim that the induced sliding block code $\phi':X \to Y$ and $\psi':Y \to X$ of $\Phi'$ and $\Psi'$ are well-defined, both injective, $\psi \circ \phi = Id_X$ and $\phi \circ \psi = Id_Y$. This finishes the proof.
\end{proof}

Proposition \ref{prop:converse_conjugacy} demonstrates that $\mathcal{T}_X \cong \mathcal{T}_Y$ is followed by $X \cong Y$. The next proposition indicates further that, not only the inverse is false in general, but there is a Markov shift such that its associated hom tree-shift is not topological conjugate to its hom tree higher block shift.

\begin{proposition} \label{prop:homTSFT-higher-block-not-conjugate}
There exist an SFT $X$ and $m \in \mathbb{N}$ such that $ \mathcal{T}_X \ncong  \mathcal{T}_{X^{[m]}}$.
\end{proposition}
\begin{proof}
Let $X=\mathsf{X}_{\mathcal{F}} \subset \{0,1\}^{\mathbb{N}}$ with $\mathcal{F}=\{000,011,110,101,111\}$ and $Y=\mathsf{X}_{\mathcal{F}'}\subset \{a,b,c\}^{\mathbb{N}}$ with $\mathcal{F}'=\{aa,ac,ba,bb,cb,cc\}$, i.e., $X=\{(100)^{\infty},(001)^{\infty},(010)^{\infty}\}$ and $Y=\{(abc)^{\infty},(bca)^{\infty},(cab)^{\infty}\}$. Note that $Y \cong X^{[2]}$ by a 2-block map $\Phi:B_2 (X) \to \{a,b,c\}$ defined as $\Phi(00)=a$, $\Phi(01)=b$, $\Phi(10)=c$. Since $X$ is irreducible, $Y$ is also irreducible, and so is $\mathcal{T}_Y$. However, for the admissible patterns
\begin{equation*}
	u:=1, v:=\vcenter{\hbox{\begin{tikzpicture}[
	scale = 0.6, transform shape, thick,
	every node/.style = {minimum size = 5mm},
	grow = down,
	level 1/.style = {sibling distance=2cm},
	level 2/.style = {sibling distance=1cm},
	level distance = 1.5cm]
	\node[]  (a) {0} [grow'=down]
	child {node[] {0}
		child{node[] {1}}
		child{node[] {1}}
	}
	child {node[] {1}
	child{node[] {0}}
		child{node[] {0}}
	};
	\end{tikzpicture}}},
\end{equation*}
there is no tree $t \in \mathcal{T}_X$ that accept both $u_1$ and $u_2$, which illustrates that $\mathcal{T}_X$ is not irreducible. This leads to a contradiction and hence $\mathcal{T}_{Y} \ncong \mathcal{T}_{X}$.
\end{proof}

Proposition \ref{prop:counterexamples} shows that, even for hom tree-shifts, topological entropy is not conjugacy invariant in general.

\begin{proposition}\label{prop:counterexamples}
There exist SFTs $X$ and $Y$ such that $X \cong Y$ but $h(\mathcal{T}_X) \neq h(\mathcal{T}_Y)$.
\end{proposition}
\begin{proof}
Let $A, B$ be given as
$$
A = \begin{pmatrix}
1 &1 &0 \\
0 &0 &1 \\
1 &1 &1
\end{pmatrix}
\quad \text{and} \quad
B = \begin{pmatrix}
1 &1 \\
1 &1
\end{pmatrix}.
$$
Observe that $A$ is strongly shift equivalent to $B$ since $A = RS$ and $B = SR$, where
$$
R = \begin{pmatrix}
1 &0 \\
0 &1 \\
1 &1
\end{pmatrix}
\quad \text{and} \quad
S = \begin{pmatrix}
1 &1 &0 \\
0 &0 &1
\end{pmatrix}.
$$
Hence, $\mathsf{X}_A \cong \mathsf{X}_B$. However, Theorem \ref{thm:irr_H_condition} demonstrates that
$$
h(\mathcal{T}_A) > h(\mathsf{X}_A) = h(\mathsf{X}_B) = h(\mathcal{T}_B).
$$
\end{proof}

\section{Further Discussion and Conclusion}

Aside from the discussion of conjugacy invariant of topological entropy for hom tree-SFTs, there are fruitful novel phenomena which have not been seen in $\mathbb{Z}^d$ shift spaces. This section illustrates, last but not least, two of our observations. Recall that each SFT is conjugate with a Markov shift that is its higher block shift (Remark \ref{rmk:intro_HBS}), this section considers only Markov shifts and hom Markov tree-shifts without loss of generality.

\subsection{Reducible Tree-Shifts of Finite Type}

Suppose $A$ is reducible with irreducible components $A_1, \ldots, A_r$. It is well-known that $h(\mathsf{X}_A) = \sup h(\mathsf{X}_{A_i})$ (see \cite{LM-1995} for more details). In addition, the collection of topological entropy of SFTs over $\mathcal{A}$ is dense in $[0, \log |\mathcal{A}|]$, we refer to \cite{Des-IM2006} for more general results. This section reveals that both the properties fail due to the topological structure of trees.

A binary matrix $A$ is called \emph{essential} if $A$ has no zero rows and zero columns. Every nonzero matrix $A \in \{0, 1\}^{k \times k}$ can be reduced to its associated essential matrix $A^e \in \{0, 1\}^{l \times l}$, $1 \le l \le k$, by repeating the following process whenever it is needed: if the $i$th row or column of $A$ is zero, then delete the $i$th row and $i$th column of $A$. It is easily seen that $h(\mathcal{T}_A)=h(\mathcal{T}_{A^e})$. Hence, in studying $h(\mathcal{T}_A)$ we always assume that $A$ is essential.

The following proposition shows that for any $A \in \{0, 1\}^{k \times k}$, $h(\mathcal{T}_A)$ is either $0$ or not less than $\frac{\log 2}{2}$. It follows immediately that the set of topological entropy of hom tree-SFTs is not dense in $[0, \log |\mathcal{A}|]$.

\begin{proposition} \label{prop:entropy_gap}
	Suppose $A$ is an essential binary matrix and $A \neq 0$. Let $M$ be the maximal row sum of $A$.
\item[(i)] If $M = 1$, then $h(\mathcal{T}_A) = 0$.
\item[(ii)] If $M \ge 2$, then $h(\mathcal{T}_A) \ge \frac{d-1}{d} \log M \ge \frac{1}{2} \log 2$.
\end{proposition}
\begin{proof}
(i) If $M = 1$, it is cleat that $|B_n(\mathcal{T}_A)| \le k$. Then, $h(\mathcal{T}_A) = 0$ follows immediately.

(ii) If $M \ge 2$, there exist $1 \le i' \le k$ and $1 \le j_1 < j_2 < \ldots < j_M \le k$  such that $\sum_{j=1}^k a_{i',j} = \sum_{l=1}^M a_{i',j_l} = M$. Then, for any pattern $u:\Sigma^n \to \{j_1, j_2, \ldots, j_M\}$, there exists an $n$-block $u': \Delta_n \to \mathcal{A}$ such that $u'_w=u_w$ for all $w \in \Sigma^n$. More specifically, since $A$ is essential, there exists an $(n-1)$-block $u'' \in B_{n-1}(\mathcal{T}_A)$ such that $u''_w = i'$ for every $w \in \Sigma^{n-1}$, and the desired $u'$ can be obtained through a proper extension of $u''$. Therefore, $|B_n(\mathcal{T}_A)| \ge M^{d^n}$, which implies $h(\mathcal{T}_A) \ge \frac{d-1}{d} \log M$. The proof is complete.
\end{proof}

\begin{problem}
Is the set of topological entropy of hom tree-SFTs over $\mathcal{A}$ dense in $[\frac{d-1}{d} \log 2, \log |\mathcal{A}|]$?
\end{problem}

The following proposition, as an application of Proposition \ref{prop:entropy_gap}, shows that the topological entropy of a reducible hom Markov tree-shift could be larger than that of any of its irreducible components.

\begin{proposition}\label{prop:entropy_large_irred_component}
Suppose $A$ is reducible with irreducible components $A_1, \ldots, A_r$. Then $h(\mathcal{T}_A) \geq \sup \{h(\mathcal{T}_{A_i})\}$, and the equality does not hold in general.
\end{proposition}
\begin{proof}
Obviously, $h(\mathcal{T}_A) \geq \sup \{h(\mathcal{T}_{A_i})\}$ since $|B_n(\mathcal{T}_A)| \geq |B_n(\mathcal{T}_{A_i})|$ for all $n \in \mathbb{N}$ and $1 \leq i \leq r$.

Consider $A = \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 1\\0 & 0 & 1 & 1\\0 & 0 & 1 & 0  \end{bmatrix}$ with the irreducible components $A' = A_1 = A_2 = \begin{bmatrix} 1 & 1\\1 & 0  \end{bmatrix}$ on $2$-tree. Proposition \ref{prop:entropy_gap} (ii) indicates that $h(\mathcal{T}_A) \ge \log 2$. Petersen and Salama \cite{PS-TCS2018} proved that
\[h(\mathcal{T}_{A'})  = \inf_n \frac{\log |B_n(\mathcal{T}_{A'})|}{|\Delta_n|} \le \frac{\log |B_1(\mathcal{T}_{A'})|}{3} = \frac{\log 5}{3} < \log 2 \le h(\mathcal{T}_A).
\]
So in general, for reducible matrix $A$, $h(\mathcal{T}_A) \ge \sup h(\mathcal{T}_{A_i})$, where $A_i$ denotes the $i$-th irreducible component of the system defined by $A$.
\end{proof}

On the other hand, there is a nontrivial example such that $h(\mathcal{T}_A) = \sup \{h(\mathcal{T}_{A_i})\}$, where $A_1. A_2, \ldots, A_r$ are the irreducible components of $A$.

\begin{example}
Denote by $x(n) = |B_{n}(\mathcal{T}_{A})|$, where $A = \begin{bmatrix} 1 & 1 & 0\\ 0 & 1 & 1\\0 & 1 & 1  \end{bmatrix}$. It is calculated in the following that $h(\mathcal{T}_{A}) = \log 2$. Denote $x_i(n)=\{u \in B_{n}(\mathcal{T}_{A}):u_\epsilon = i\}$ for $i=0,1,2$ and derive the following recursive equations:
\begin{align*}
    &x_0(n)=(x_0(n-1)+x_1(n-1))^d; \\
    &x_1(n)=2^{d + d^2 + \ldots + d^n};\\
    &x_2(n)=2^{d + d^2 + \ldots + d^n},
\end{align*}
with initial conditions $x_0(0)=x_1(0)=x_2(0)=1$. By mathematical induction one may observe that $x_0(n)=x_1(n)=x_2(n)=2^{d + d^2 + \ldots + d^n}$, and $h(\mathcal{T}_{A})=\log 2$ follows as a result.
\end{example}

\begin{problem}
Suppose $A$ is reducible with irreducible components $A_1, \ldots, A_r$. Under what condition the equality $h(\mathcal{T}_{A}) = \sup \{h(\mathcal{T}_{A_i})\}$ holds?
\end{problem}

\subsection{Conclusion}

This paper focuses on the topological entropy of hom tree-SFTs. In the following list of main results of this elucidation, many of them, rather than consequences, are just the beginning of further investigation.
\begin{enumerate}
    \item Suppose $\mathcal{T}_X$ is the hom tree-SFT induced by the SFT $X$. Then $h(\mathcal{T}_X) = h(X)$ if and only if $\sum_j A_{i, j} = \sum_j A_{i', j}$ for all $i, i'$, where $A$ is the adjacency matrix of the graph representation of $X$ (Theorems \ref{thm:irr_H_condition} and \ref{thm:n_block_entropy_inv}.)
    \item Suppose $X$ and $Y$ are shift spaces. Then $\mathcal{T}_X \cong \mathcal{T}_Y$ is sufficient but not necessary for $X \cong Y$ (Propositions \ref{prop:converse_conjugacy} and \ref{prop:homTSFT-higher-block-not-conjugate}).
    \item The set $\{h(\mathcal{T}_X)\}$ of topological entropy of hom tree-SFTs is not dense in $[0, \log |\mathcal{A}|]$ (Proposition \ref{prop:entropy_gap}).
    \item There is a hom Markov tree-shift that has strictly larger topological entropy than shifts formed by any of its irreducible components (Proposition \ref{prop:entropy_large_irred_component}).
\end{enumerate}

\bibliographystyle{amsplain}
\bibliography{grece}

\end{document}