TITLE: Computing left cosets in 10ℤ and dihedral group
QUESTION [0 upvotes]: There is a subgroup H of a group G, and pairs of elements $(x,y)$ of $G$. Determine if they belong to the same left $H$-cosets. I'm simply to provide a yes or no answer.

So I know what cosets are and I understand how to compute but I'm not sure how with these groups specifically.
For the first one, $\mathbb{Z}, H = 10\mathbb{Z}$, I'm not sure what H is exactly. Is it just every member of the integers left multiplied by 10 i.e $\{10, 20, 30, 40, ...\}$. If that's the case how can any of the pairs belong to the same left coset as they never contain the same integers?
And for the second, I'm not sure how the definition of $a^6 = b^2 = e$ and $ba = a^{6-1}b$ comes into play. $H = <a^1b^0>$, but how do we determine the left coset with these elements? Better yet, how would I determine what cyclic group that even defines...?
Would appreciate some help with these computational questions.

REPLY [1 votes]: $10\mathbb{Z} = \{\ldots,-20,-10,0,10,20\ldots\}$ and the coset associated with $x$ would look like $\{\ldots,x-20, x-10, x, x+10, x+20,\ldots\}$. So for example, $4$ and $14$ are in the same coset $\{\ldots,-6, 4, 14, 24, \ldots\}$, while $3$ and $5$ are not. (Can you give a plain English description for what it means to be in the same coset in this example?)

For the dihedral group, it seems like you are struggling with the definition of the dihedral group. You should probably review your notes about it. For this particular dihedral group, you can think of it as isometries of a regular hexagon. Then $a$ can represent the counterclockwise rotation by $60^\circ$, while $b$ can be the reflection across one of its diagonals. Then $H$ is the cyclic group generated by the rotations.


TITLE: Functional equation - unique solution
QUESTION [3 upvotes]: A twice differentiable function $f:\mathbb{R} \to \mathbb{R}$ is given such thah $f(0) = 1$, $f(\mathbb{R}) = \mathbb{R}$ and $f(f(x)) = 4x - 1$ for all $x \in \mathbb{R}$. One such function is $f(x) = -2x + 1$. I wonder if there is another function satisfying the given equation and conditions. Can anyone help?

REPLY [3 votes]: The solution is in the comments. I'll just put them together.
$f^2$ is injective. From that it's easy to show that $f$ is also injective. $f(1)=f(f(0))=-1<f(0)$, this along with being injective says that $f$ is strictly decreasing. Since $f$ is differentiable it follows that  for all x
\begin{equation}
f'(x) \leq 0  \hspace{4cm} (1)
\end{equation}
Now differentiating $f(f(x))=4x-1$ with respect to $x$
\begin{equation}
f'(f(x))f'(x)=4  \hspace{2.6cm} (2)
\end{equation}
Replacing $x$ with $f(x)$ in $(2)$ we get
\begin{equation}
f'(4x-1)f'(f(x))=4  \hspace{1.7cm} (3)
\end{equation}
From $(2)$ and $(3)$ one get $f'(x)=f'(4x-1)$ where again substituting $x$ by $\frac{x+1}{4}$ we get
\begin{align}
 f'(x)&=f'(\frac{x}{4}+\frac{1}{4}) \\
      &=f'(\frac{x}{4^2}+\frac{1}{4^2}+\frac{1}{4}) \\
      &=f'(\frac{x}{4^3}+\frac{1}{4^3}+\frac{1}{4^2}+\frac{1}{4}) \\
      &= \cdots ~~\cdots ~~\cdots \\
      &=f'(\frac{x}{4^n}+\sum_{i=1}^n \frac{1}{4^i})~~~~~~~~~~~(\textit{after the}~n^{th}\textit{th}~\textit{equality})
\end{align}
Now taking limit as $n \rightarrow \infty$, since $f'$ is continuous we obtain for all $x$ that $f'(x)=f'(\frac{1}{3})=a'$ $\hspace{0.5cm}$ (say). This implies (by integrating) $f(x)=a'x+b'$  for some real constant $b'$. From $(1)~~~f'(x) \leq 0$ and  $f(0)=1$ implies $a' \leq 0$ and $b'=1$. $a'=0$ is not an option since we have $f^2(x)=4x-1$. Let $a'=-a$ where $a>0$. Then $f(x)=-ax+1$. Now $f(f(x))=4x-1$ gives (equating coefficient of $x$ and the constant term) $a=2$.  So $f(x)=-2x+1$ is the unique function with the said properties.


text:
\begin{document}

\maketitle
\thispagestyle{empty}
\pagestyle{empty}

\begin{abstract}
This paper attempts to develop a graph-theoretic multi-agent perspective of population games to study the \quotes{truncation} behavior. The proposed method considers fitness of the population	as a dynamical system to address the issue of restrictive description of this behavior which pertains to the underlying population dynamic. The fitness dynamic resembles an agreement protocol that enables comments on the steady-state characteristics of the graph that represents the population structure. The structural attributes of the underlying graph and the truncation behavior are emphasized by exploiting the spectral properties of the associated Laplacian matrix. The asymptotic stability of the fitness agreement protocol has been shown to be sufficient in concluding the stability of population dynamics. Simulation results validating the proposed hypothesis have been discussed.
\end{abstract}

\section{Introduction}
\indent Evolutionary game theory has emerged from behavioral ecology, a field that formally analyzes the influence of ecological factors on the evolution of different species or populations in their behavioral contexts. Their evolution pertains to how they revise strategies under certain protocols. The central idea of evolutionary games is to model the evolution of the Nash equilibrium (NE) of strategic form games using a set of differential equations that define the strategy revision protocol. The population games belong to a class of evolutionary games which model strategic interactions among the populations with a key assumption that these populations only occasionally receive opportunities to revise their strategies. It is apropos to consider \cite{von2007theory,nash1951non,basar1999dynamic,narahari2014game,haurie2012games} for a comprehensive literature survey on game theory. The literature on evolutionary games, population games and various revision protocols is spanned over last four decades \cite{smith1974theory,taylor1978evolutionary,weibull1997evolutionary,hofbauer2003evolutionary,hofbauer2009stable,sandholm2015population}; surveying this literature is beyond the scope of this paper.

\subsection{Relevant literature}
Population games have lately inspired a wide range of the distributed optimization problem-solving techniques in multi-agent systems. A decently recent work on the application of these games to multi-agent systems includes \cite{ marden2009cooperative,ramirez2010population,pantoja2012distributed,pantoja2011dispatch,barreiro2014constrained,mojica2014dynamic,obando2014building, 7172156,barreiro2016distributed}. An application of population games to a certain class of cooperative control problems is demonstrated in \cite{ marden2009cooperative}. Most of the distributed optimization problems in multi-agent systems can be pursued as dynamic resource allocation problems. To this end, researchers have sought to exploit the distributed version of a strategy revision protocol known as distributed replicator dynamic (DRD) \cite{ ramirez2010population,pantoja2012distributed,pantoja2011dispatch,barreiro2014constrained,mojica2014dynamic,obando2014building,7172156,barreiro2016distributed}. The DRD overcomes the drawback of classic replicator dynamic by considering only local-level mutual interactions among the neighboring agents. To elaborate further, \cite{pantoja2012distributed} demonstrates the application of the DRD to control the luminance of several lighting zones with electrical power as a resource under consideration. A similar but more appealing approach is considered in \cite{pantoja2011dispatch} for optimal dispatch of distributed generators in a microgrid.

\subsection{Motivation}
Authors' interest in the graph-theoretic analysis of population games is motivated by observation of the \quotes{truncation} behavior of agents \cite{pantoja2011dispatch}. The truncation behavior occurs when the population-share associated with the agent has fitness below the average fitness at equilibrium. The fitness may be regarded as the payoff an agent receives for playing a particular strategy\cite{sandholm2010population}. If one considers a graph that depicts the structure of a finite population in the game, then as the population-shares associated with different agents undergo strategy revisions, the interconnection structure of the graph gets significantly influenced. For example, the population-share associated with an agent, can render it fit or unfit for survival, based on its strategy being profitable or nonprofitable as observed  by the revision protocol.\cite{sandholm2010population}. This scenario is theoretically explained in \cite{pantoja2011dispatch}. However, it appears that the subject still lacks a detailed mathematical analysis.

In population games, an agent may refer to a strategy shared by a subset of the total population. However, in context of the reported work, it is referred to as the fitness associated with the corresponding subset of the population. The population dynamic (distributed replicator dynamic in this case) does not describe the evolution of fitness of the agents. Hence it is insufficient for understanding how the agents converge to the agreement value. It only uses the fitness function as an argument and describes the evolution of the population state. As truncation is the behavior an agent may exhibit at a steady-state, it is more appropriate to define the fitness dynamic to understand how this behavior emerges. The proposed dynamic describes the evolution of the fitness values. The approach of the reported work provides a graph-theoretic explanation to the truncation behavior of the agents with a few more contributions stated below.
\subsection{Contributions}
\indent  The main objective of this paper is to seek an analytical rationale of the \quotes{truncation} behavior of the agents using spectral properties of the graph theory. To the best of authors' knowledge, no significant contribution is seen towards analyzing this behavior in population games by exploiting rich spectral properties of the interaction graph of the game. The contributions of the present work as follows:
\begin{enumerate}
	\item The formulation of the fitness dynamic of the agents and its realization as a linear parameter-varying dynamic agreement protocol that allows analyzing these games from the perspective of the multi-agent systems.
	\item Analysis of truncation behavior of the agents using spectral properties of the graph-Laplacian matrix.
	\item A graph-theoretic approach to ensure the stability of the Nash equilibrium of the potential games from a graph-theoretic perspective.
\end{enumerate}
\subsection{Organization of the paper}
\indent The rest of the paper is organized as follows: Some preliminaries on graph theory and potential games are presented in Section \ref{sec2}. Section \ref{sec3} explains the network model of the distributed replicator dynamic and the fitness agreement protocol. The sufficient conditions for the existence of solutions of the distributed replicator dynamic and the fitness dynamic are presented in Subsection \ref{sec4}. Subsection \ref{sect5} and Subsection \ref{sec5.b} elaborate on the existence of Nash equilibrium and its stability, respectively. Section \ref{sim} presents the simulation examples while Section \ref{con} concludes the paper.

\section{Preliminaries}\label{sec2}

\subsection{Graph theory}\label{sec2.a}
An (undirected) graph $\mathcal{G}$ is defined by the couple $\mathcal{G}=(\mathcal{N}, \mathcal{E})$ with $n$ nodes (or agents) $\mathcal{N}= \{1, 2, \ldots, n\}$ and a number of edges in the set $\mathcal{E} \subseteq \mathcal{N} \times \mathcal{N}$. The neighbor set of the $i^{\rm th}$ node is $\mathcal{N}_i=\{j\in \mathcal{N}| (j,i) \in \mathcal{E} \}$, where $i\in\{1,2,\ldots,n\}$. The number of nodes~$n$ is the cardinality of the graph.

\subsection{Population games}\label{sec2.b}

A population game is characterized by a continuous vector-valued payoff function $f = (f_1,\dots,f_n) :\Re^n_+ \rightarrow \Re^n$. The agents of the population game choose their strategies from a pure strategy set $\mathcal{S}=\{1,2,\ldots,n\}$ and their aggregate behavior is described as a population state $p(t) = \{p_1(t), \ldots, p_n(t)\}$ that belongs to a simplex $\bigtriangleup$ for all $t\geq 0$ such that
\begin{equation}
\bigtriangleup=\{p(t) \in \Re^n_+:\sum_{i=1}^{n}p_i(t)=P_{\mathrm{tot}}\}, \label{simplex}
\end{equation}
where $P_{\mathrm{tot}}$ is the total population of the game\cite{sandholm2010population}. For the sake of notational simplicity, here onwards the dependence on $t$ is dropped wherever it is obvious. The scalar $p_i$ denotes the number of agents choosing the pure strategy $i$ and $f_i$ denotes the payoff to strategy $i$.

\indent Given a population game $f$, a Nash equilibrium $p^*$ of $f$ is defined as given below\cite{barreiro2016distributed,sandholm2010population}:
\begin{definition}\label{nef}
	Given a population game $f$, the set of Nash equilibria is defined as follows:
	\begin{align}
	\begin{split}
	NE(f) = \{p\in\bigtriangleup:p_i>0\implies f_i(p)\geq f_j(p),\\
	~\forall i,j \in \mathcal{S}\}. \label{nepsi}
	\end{split}
	\end{align}
\end{definition}
Further, $f$ is a {\em potential game\/} if there exists a continuously differentiable potential function $V:\Re^n_+ \rightarrow \Re$ such that $f(p)=\nabla V(p)$. It is assumed that $V(p)$ is strictly quadratic concave, i.e. $V(p)=-p^T H p + b^Tp +c$ with $H>0$. We replace \quotes{payoff} by \quotes{fitness} throughout.

\section{Problem Formulation}\label{sec3}
\indent This section first introduces the classic and distributed versions of the replicator dynamic and proceeds towards the problem formulation and main results of the paper.

\subsection{Replicator dynamic}
The replicator dynamic is a strategy revision protocol which describes the aggregate behavior of the agents through the evolution of the population state $p(t)$. Assuming that there exists a network of agents such that each agent receives a certain share of the total population $p$, then the classic replicator dynamic describes how the population-shares associated with these agents vary with respect to time. It is given by
\begin{equation}
\dot p_i (t) = p_i(t) \, [f_i(p(t))-\bar{f}(p(t))],\label{cp}
\end{equation}
where the average fitness of the population is
\begin{equation}
\bar{f}(p)=\frac{1}{P_{\rm tot}}\sum_{j=1}^{n}p_jf_j(p_j).\label{af}
\end{equation}
According to \eqref{cp}, the population-share associated with the agent whose fitness is above the average fitness tends to increase, while the population-share associated with the agent whose fitness is below the average fitness tends to decrease. Thus the total population stays constant.

\subsection{Network model of distributed replicator dynamic} \label{3b}

\begin{figure}
	\centering
	\includegraphics[width=2.5in]{png_g11}
	\caption{An example of the interaction graph $\mathcal{G}(\mathcal{N},{\mathcal{E}})$ of a finite population of the potential game $f$.}
	\label{graph1}
\end{figure}
Let an undirected graph $\mathcal{G}=\{\mathcal{N},{\mathcal{E}}\}$ depict a network of agents as shown in the example of Fig. \ref{graph1} such that each agent has a nonzero population-share at $t = 0$, where $\mathcal{N}$ denotes the set of agents and $\mathcal{E}$ denotes the set of edges of the graph. Each agent in the network is characterized by the population-share associated with it, which receives a certain fitness for choosing a certain strategy. Henceforth, we allow the fitness scalar to represent the agent wherever necessary. The distributed version of the replicator dynamic \eqref{cp} for the agent is given by\cite{bravo2015distributed,barreiro2016distributed}
\begin{equation}
\dot{p}_i = \sum_{j\in \mathcal{N}_i} p_i p_j [f_i(p) - f_j(p)],					\label{lre}
\end{equation}
where the difference of fitness between adjacent agents enters into play.

Note that the simplex introduced in \eqref{simplex} remains invariant under \eqref{cp} and \eqref{lre}.

Introducing the Laplacian matrix $L(p)$ of the graph, i.e.
\begin{equation}
L(p)=\begin{cases}
l_{i,j}=-p_ip_j, \forall (i,j) \in \mathcal{E},\\
l_{i,j}=0, \forall (i,j) \not\in \mathcal{E},\\
l_{i,i}=-\sum_{j\in \mathcal{N}_i}l_{i,j}, \label{aii}
\end{cases}
\end{equation}
where $|l_{i,j}|$ is treated as the weight of the edge connecting $i^{\mathrm{th}}$ and $j^{\mathrm{th}}$ agents on the graph $\mathcal{G}$. Below we write the dynamic \eqref{lre} in a stacked form as
\begin{eqnarray}
\dot{p} = L(p)f(p) \label{nw}
\end{eqnarray}
which represents the replicator dynamic of the population state $p(t)$.
In view of its definition, the Laplacian $L(p)$ is a parameter-varying, real and symmetric matrix which is differentiable and uniformly continuous in $p$. As a consequence, the following holds.
\begin{statement}\label{as1}
	There exists $\Lambda > 0$ such that the spectral norm $\| L(p) \| < \Lambda,\forall p \in \bigtriangleup,\forall t \geq 0$.
\end{statement}
\begin{statement}\label{as2}
	The gradient of $L(p)$ with respect to $p$ is bounded above by some scalar $\eta$,

	$\left\| \nabla L (p) \right\| \leq \eta, p\in \bigtriangleup.$

\end{statement}

\subsection{Fitness agreement protocol}\label{sec3.c}
The fitness dynamic of the population is derived from the dynamic \eqref{nw} as shown below,

\begin{align*}
\dot{f}(p)&=\nabla f(p)\dot{p},					 \\
&=\nabla^2 V(p)\dot{p},\\
&= - H L(p)f(p),\\
&= - M(p)f(p),	\numberthis		\label{aut}
\end{align*}

where $M(p) = H L(p)$ is a positive semidefinite matrix, i.e. $M(p)\geq 0$ [see Theorem 2.2,\cite{wu1988products}]. Notice that $L(p)\boldsymbol{1_n}=0$ which implies $M(p)\boldsymbol{1_n}=0$, where $\boldsymbol{1_n}\in \Re^{n\times 1}$ is a vector containing all ones. That being the case the dynamic \eqref{aut} attains a steady state exactly when all fitnesses are equal. Hence the fitness dynamic \eqref{aut} resembles an agreement protocol\cite{mesbahi2010graph}.

\subsection{Existence and uniqueness of solution to fitness agreement protocol}\label{sec4}
There exists a unique solution to the dynamic \eqref{nw}\cite{sandholm2010population}. The Hessian matrix $H$ is bounded because $V(p)$ is continuously differentiable and $L(p)$ is also bounded. Consequently, the fitness agreement protocol \eqref{aut} has a unique solution.

\subsection{Convergence of the DRD to the NE}\label{sect5}
The definition \eqref{nef} straightforwardly extends to potential games, however, for such games the NE is unique seeing that the potential function $V(p)$ is strictly quadratic concave.

The convergence of the population state $p(t)$ to the NE of the potential game may also be described from the graph-theoretic perspectives. In what follows, we provide our main results that link the graph theory with the population games and show that the existence of the NE $p^*$ is strongly associated with the connectedness of the interaction graph $\mathcal{G}$.

\subsection{Main results: Part A} \label{sec5.a}

\begin{lemma}\label{5.1}
	In the potential game $f$, all agents receive equal fitness if and only if $\lambda_2(L(p(t)))>0,\forall t \geq 0$.
\end{lemma}
\begin{proof}
	Since the edge-weights $|l_{i,j}|$ are dynamic, for the graph $\mathcal{G}$ to stay connected, one must ensure that $l_{i,j}<0,\forall i,j \in \mathcal{E}, \forall t\geq 0$. This condition can also be stated directly in terms of the second smallest eigenvalue of $L(p(t))$\cite{mesbahi2010graph}. Assuming that $\mathcal{G}$ is initially connected, the necessary and sufficient condition for $\mathcal{G}$ to stay connected throughout the game play is that $\lambda_2(L(p(t))) >0,\forall t \geq 0$. $\lambda_2(L(p(t)))>0,\forall t \geq 0$ ensures that $\lambda_2(M(p(t)))>0,\forall t \geq 0$ since $H>0$. Hence,  $\lambda_2(L(p(t)))>0,\forall t \geq 0$ is necessary and sufficient to prove that the agreement protocol \eqref{aut} converges to the agreement value.
\end{proof}

\indent In line with the previous Lemma \ref{5.1}, we derive the next result on the convergence of the dynamic given in \eqref{nw} to the NE of the game.

\begin{theorem}\label{5.2}
	If $\lambda_2(L(p(t)))>0,\forall t \geq 0$ then the fixed point of the dynamic \eqref{nw} coincides with the NE $p^{*}$.
\end{theorem}
\begin{proof}
	Note $\lambda_2(L(p(t)))>0,\forall t \geq 0$ implies that all edges have non-zero weights for all time. Since $l_{i,j}=-p_i(t)p_j(t)$, it further implies that the population-shares associated with all agents remain non-zero (i.e $p_i(t)>0, \forall t>0$). Secondly, as a consequence of Lemma \ref{5.1} and the fact that $M(p)\boldsymbol{1_n}=0$, the dynamic \eqref{nw} reaches a fixed point, say $p^s$ that qualifies to be the NE $p^*$ of the potential game, as mentioned in Definition \eqref{nef}. Hence proved.
\end{proof}

\indent Lemma \ref{5.1} and Theorem \ref{5.2} provide the next corollary.

\begin{corollary}\label{cor}
	The condition $\lambda_2(L(p(t)))>0,\forall t \geq 0$ is a sufficient condition for the fixed point $p^s$ to be the NE $p^*$ of the potential game $f$.
\end{corollary}
A direct consequence of Corollary \ref{cor} provides the following result.

\begin{theorem} \label{5.3}
	Let
	\begin{equation*}
	\sigma^0=\{\lambda_k(L(p^s))= 0, \forall k=2,\ldots,n\}
	\end{equation*} for $p^s \not=p^*$, then $\sigma^0\not=\emptyset$ indicates the existence of singleton graphs.
\end{theorem}
\begin{proof}
	It is obvious that $|\sigma^0|+1$ is the algebraic multiplicity of the eigenvalue $\lambda_1(p)=0$, which is equal to the number of connected components in  $\mathcal{G}$. If $\lim_{t \rightarrow \infty}l_{i,j} = 0$ for some $(i,j) \in \mathcal{E}$ then there must be either $\lim_{t \rightarrow \infty}p_i=0$ or $\lim_{t \rightarrow \infty}p_j=0$, or both; which indicates that the population-share associated with either agent $i$ or agent $j$, or both $i^{\mathrm{th}}$ and $j^{\mathrm{th}}$ agents tend to decline. Let $\mathcal{K}$ be a set of such agents then there must be $|\mathcal{K}|\leq |\sigma^0|$ number of isolated agents in the graph $\mathcal{G}$. These isolated agents represent singleton graphs. Hence proved.
\end{proof}
\subsection{Observations on truncation behavior of agents:}
\indent This subsection is in line with the  truncation behavior discussed in \cite{pantoja2011dispatch}. Here we introduce the singleton graphs which lie at the center of the truncation phenomenon. Let $\mathcal{G}^c \in \mathcal{K},\forall c=1,\ldots,|\mathcal{K}|$ be singleton graphs as defined earlier.

If $f_i(p^s)$ is a fitness corresponding to the population-share $p^s_i=0$ for some $i \in \mathcal{N}$ then we have two following cases.

\subsubsection*{Case 3.1. When agent $f_i(p^s)$ is an end-point of $\mathcal{G}(\mathcal{N},{\mathcal{E}})$}
\label{case1}
The population-share $p^s_i=0$ implies that eventually $l_{i,j}=0, \forall j\in \mathcal{N}_i$ or $\mathcal{N}_i=\emptyset$, following which $\mathcal{G}_c=\{f_i(p^s)\}$. Since $f_i(p^s)$ is being the end-point in $\mathcal{G}(\mathcal{N},{\mathcal{E}})$, its isolation renders the connectedness of the remaining part of $\mathcal{G}$ unaffected i.e., as shown in the example of Fig. \ref{graph2}.

\begin{figure}
	\centering
	\includegraphics[width=2.65in]{png_g22}
	\caption{Interaction graph $\mathcal{G}(\mathcal{N},\mathcal{E})$ from Fig. \ref{graph1} depicting Case 3.1: Agent $f_8$ is an end-point.}
	\label{graph2}
\end{figure}

\begin{figure}
	\centering
	\includegraphics[width=2.5in]{png_g33}
	\caption{Interaction graph $\mathcal{G}(\mathcal{N},\mathcal{E})$ from Fig. \ref{graph1} depicting Case 3.2: Agent $f_4$ is a cut-point.}
	\label{graph3}
\end{figure}

\subsubsection*{Case 3.2. When agent $f_i(p^s)$ is the cut-point of $\mathcal{G}(\mathcal{N},{\mathcal{E}})$}
This scenario is depicted in Fig. \ref{graph3}, if the agent $i$ holds the position in $\mathcal{G}$ such that $\mathcal{G}' \cap \mathcal{G}''=\{f_i(p^s)\}$ for any two components, say $\mathcal{G'}$, and $\mathcal{G''}$ in $\mathcal{G}$; then the edges that have isolated $f_i(p^s)$ also separate $\mathcal{G'}$ and $\mathcal{G''}$ from each other.

\subsection{Stability analysis of dynamics \eqref{nw} and \eqref{aut}}\label{sec5.b}
\indent Here we show that the stability of the fitness agreement protocol \eqref{aut} and the dynamic \eqref{nw} share a common platform. Before proceeding further, it is worth considering certain notions of the dynamic \eqref{nw} \cite{sandholm2015population} stated subsequently.
\begin{enumerate}
	\item Positive Correlation (PC):
	\begin{equation}
	\dot{p}(t)\neq0 \implies \dot{p}(t)^Tf(p)>0. \label{cond5.1}
	\end{equation}
	\item Nash Stationarity (NS):
	\begin{equation}
	\dot{p}(t)=0 \Longleftrightarrow p \in NE(f). \label{cond5.2}
	\end{equation}
\end{enumerate}
\indent Conditions \eqref{cond5.1} and \eqref{cond5.2} strongly imply that the potential function $V(p)$ attains the maximum at $p^*$. The asymptotic stability of the NE $p^*$ of the potential game is bound by these conditions as stated in \cite{sandholm2015population}.
A similar approach has been considered for the asymptotic stability of the distributed replicator dynamic in \cite{barreiro2016distributed}. The analysis considers that the graph is connected. In essence, the stability analysis is restricted to only $p^*$. However, it does not imply that the distributed replicator dynamic has an unstable equilibrium state when the graph loses the connectivity. In this scenario, it is more convincing to analyze the stability of the fitness agreement protocol \eqref{aut} instead of the dynamic \eqref{nw}. In what follows, we intend to prove that the stability of the fitness agreement protocol \eqref{aut} implies the stability of the dynamic \eqref{nw}.
\subsubsection{Main results: Part B}
\begin{theorem}\label{thm5.6}
	Let $W(p):\Re^n \times \Re \rightarrow \Re_{\geq0}$ be a candidate Lyapunov function chosen such that $\dot{W}(p)\leq -\lambda_2(L(p))f^T(p)f(p)$ then the fitness agreement protocol \eqref{aut} is asymptotically stable.
\end{theorem}
\begin{proof} Since $H$ is a symmetric positive definite matrix, it is invertible. Let the candidate Lyapunov function for the system \eqref{aut} be,
	\begin{equation}
	W(p)=\frac{1}{2}f^T(p)H^{-1}f(p).\label{vdot}
	\end{equation}
	Differentiating \eqref{vdot} along the trajectories of the fitness vector yields,
	\begin{subequations}
		\begin{eqnarray}
		\dot{W}(p)=-f^T(p)L(p)f(p). \label{vdot1}
		\end{eqnarray}
	\end{subequations}
	Now, if the graph $\mathcal{G}$ remains connected $\forall t \geq 0$, then we have \begin{equation*}
	f^T(p)L(p)f(p) \geq \lambda_2(L(p))f^T(p)f(p).
	\end{equation*}
	Using this inequality in \eqref{vdot1}, we get
	\begin{eqnarray}
	\dot{W}(p)\leq-\lambda_2(L(p))f^T(p)f(p).\label{lvdot}
	\end{eqnarray}
	Hence proved.
\end{proof}

\begin{theorem}\label{3.2}
	The asymptotic stability of the fitness dynamic \eqref{aut} implies the asymptotic stability of the dynamic \eqref{nw} and vice versa.
\end{theorem}
\begin{proof}
	The proof simply follows from the equation \eqref{vdot1}. We have,
	\begin{subequations}
		\begin{eqnarray}
		\dot{W}(p)&=&-f^T(p)\{L(p)f(p)\},\\
		&=&-f^T(p)\dot{p},\label{rela}\\
		&\leq&0.\label{inv}
		\end{eqnarray}
	\end{subequations}
	Comparing the equation \eqref{rela} to the inequality \eqref{cond5.2}, we assert that the positive correlation holds between $f^t(p)$ and $\dot{p}$, and along with the condition $\lambda_2(L(p(t)))>0,\forall t \geq 0$, the Nash stationarity also holds. Hence, the dynamic \eqref{nw} is also asymptotically stable. Hence proved.
\end{proof}
\begin{corollary}\label{cor3.8}
	Every connected component in $\mathcal{G}$ exhibits asymptotically stable dynamics.
\end{corollary}
\begin{proof}
	If $p^s\not=p^*$ then there exist $|\sigma^0|$ connected components in $\mathcal{G}$ and each connected component, i.e. $\mathcal{G}_q,~\forall q=1,\ldots,|\sigma^0|$ has an associated Laplacian $L_q(p)$; owing to which the graph-Laplacian $L(p)$ assumes a block diagonal form:
	\begin{equation}
	L(p)=\left(\begin{array}{ccccc}
	L_1(p) & \hfill & \hfill & \hfill & \hfill\\
	\hfill & L_2(p) & \hfill & \hfill & \hfill\\
	\hfill & \hfill &  \ddots & \hfill & \hfill\\
	\hfill & \hfill & \hfill & L_{|\sigma^0|-1}(p) & \hfill\\
	\hfill & \hfill & \hfill & \hfill & L_{|\sigma^0|}(p)\\
	\end{array}\right).
	\end{equation}
	\indent Apparently, each connected component has a $0$ eigenvalue of algebraic multiplicity equal to 1. Also, each $\mathcal{G}$ has a subset of agents having their population and fitness dynamics. In line with this, the stability analyses discussed in Theorems \ref{thm5.6} and \ref{3.2} readily apply to the connected components in $\mathcal{G}$.
\end{proof}
\section{Simulation results}\label{sim}
All simulations are performed using the {MATLAB-SIMULINK} software. The population graphs are plotted using ``wgPlot.m" and ``gplotwl.m" matlab routines. We first consider a population dynamic of 5 agents. A simple nearest-neighbor interconnection is considered as shown in Fig. \ref{graph9}. Initially, the total population is equally distributed among all agents ($p_i(0)=0.2,\forall i \in \mathcal{N}$), owing to which all the edges initially have equal weights as indicated by the blue color associated with them. The vertical color map indicates the weight associated with each agent i.e., the value of the fitness scalar which is also correlated with the size of its dot. Initially, the fitness scalar have been assigned different weights. As fitness agreement protocol evolves, all fitness scalars except $f_5$ converge to the agreement value as can be seen from Fig. \ref{graph4}. It is due to the fact that the population state $p_5$ belonging to the $5^{\mathrm{th}}$ agent tends to decline and eventually goes to 0 as shown in Fig. \ref{graph5}. This results in removal of the edges $|l_{1,5}|$ and $|l_{4,5}|$ as reflected in Fig. \ref{graph7}. As a consequence of the this, at a steady state, the graph $\mathcal{G}$ comprises two connected components, i.e. the one that retains the agents $f_1$ to $f_4$ and the other one being singleton graph that contains $f_5$. Fig. \ref{graph8} confirms the existence of 2 connected components in $\mathcal{G}$. The population structure at the steady state is manifested in Fig. \ref{graph10} wherein the edge-weights are associated with specific color shades on the horizontal color map whose numeric values are also indicated alongside the respective edges. Fig. \ref{graph6} verifies that the simplex \eqref{simplex} remains invariant.

In a similar way, we also consider a random network of 20 agents as shown in Fig. \ref{graph16}. Initially, the total population is equally distributed among all agents and the fitness scalars are calculated to have different values.
The connected components in $\mathcal{G}$ are highlighted by boxed regions in Fig. \ref{graph17}, the graph comprises 2 connected components and 9 isolated agents.
\begin{figure}[t!]
	\centering
	\includegraphics[width=3.65in]{initial_graph.eps}
	\caption{The graph $\mathcal{G}$ consisting 5 agents at time $t_0$.}
	\label{graph9}
\end{figure}
\begin{figure}[t!]
	\centering
	\includegraphics[width=3.65in]{fit.eps}
	\caption{Evolution of fitness of the agents on the graph $\mathcal{G}$ from Fig. \ref{graph9}.}
	\label{graph4}
\end{figure}
\begin{figure}[t!]
	\centering
	\includegraphics[width=3.65in]{pop.eps}
	\caption{Evolution of population of the agents on the graph $\mathcal{G}$ from Fig. \ref{graph9}.}
	\label{graph5}
\end{figure}
\begin{figure}[t!]
	\centering
	\includegraphics[width=3.65in]{popi.eps}
	\caption{Invariance of population of the agents on the graph $\mathcal{G}$ from Fig. \ref{graph9}.}
	\label{graph6}
\end{figure}
\begin{figure}[t!]
	\centering
	\includegraphics[width=3.65in]{edges.eps}
	\caption{Evolution of the edges of the graph $\mathcal{G}$ from Fig. \ref{graph9}.}
	\label{graph7}
\end{figure}
\begin{figure}[t!]
	\centering
	\includegraphics[width=3.65in]{eigen.eps}
	\caption{Evolution of eigenvalues of the Laplacian $L(p)$ of the graph $\mathcal{G}$ from Fig. \ref{graph9}.}
	\label{graph8}
\end{figure}

\begin{figure}[t!]
	\centering
	\includegraphics[width=3.65in]{final_graph.eps}
	\caption{The graph $\mathcal{G}$ from Fig. \ref{graph9} at steady state.}
	\label{graph10}
\end{figure}

\begin{figure}[t!]
	\centering
	\includegraphics[width=3.65in]{initial_graph20.eps}
	\caption{The graph $\mathcal{G}$ consisting 20 agents at time $t_0$.}
	\label{graph16}
\end{figure}
\begin{figure}[t!]
	\centering
	\includegraphics[width=3.65in]{final_graph20.eps}
	\caption{The graph $\mathcal{G}$ from Fig. \ref{graph16} at steady state.}
	\label{graph17}
\end{figure}
\section{Conclusions}\label{con}
A macroscopic behavior of the distributed replicator dynamic is analyzed using graph theory. The fitness dynamic is shown to resemble a linear parameter-varying dynamic agreement protocol. A comprehensive analysis of truncation behavior in the distributed replicator dynamic is put forth using spectral graph theory. It is proved that the existence and asymptotic stability of the Nash equilibrium of the population games are dependent on the eigenvalue spectrum of the graph-Laplacian matrix of the underlying network. Also, it is shown that with a right choice of a Lyapunov function for the fitness dynamic; the asymptotic stability of the fitness dynamic implies the asymptotic stability of the distributed replicator dynamic.

\bibliographystyle{unsrt}

\bibliography{tran_updated}
\end{document}

config: arxiv


TITLE: How to show that these two versions of Farkas lemma are equal?
QUESTION [1 upvotes]: One version of Farkas lemma is that

Let $A$ be a real $m\times n$ matrix and $b$ an $m$-dimensional real vector. Then,
  exactly one of the following statements are true.

There exists an $x \in \mathbb{R}^n$ such that $Ax=b$ and $x\ge 0.$
There exists a $y \in \mathbb{R}^m$ such that $y^TA \le 0,\ y^Tb >0$.

Then my book says it uses a slightly modified version that says that if:

$Ax=b$ doesn't have a solution.

Then

there is a vector $y$ such that $y^TA=0$, and $y^Tb > 0$.

I have two questions:

How does the last implication follow from Farkas lemma?
Is the last thing I wrote actually an equivalence? That is is it so that either $Ax=b$ has a solution or $y^TA=0,\ y^Tb>0$ has a solution, but not both?

REPLY [2 votes]: The trick is to apply Farkas lemma with modified matrix $\tilde A$ and vector $\tilde b$ that are constructed from $A,b$.
Let $A,b$ such that $Ax=b$ has no solution. Then the system
$$
A x_1 - Ax_2 = b, \ x_1 \ge 0,\ x_2 \ge0
$$
has no solution, or, equivalently
$$
\begin{bmatrix} A & -A \end{bmatrix}x = b, \ x\ge 0
$$
is not solvable. Then by Farkas lemma as cited in the question, it follows that there is a vector $y$ such that
$$
y^T\begin{bmatrix} A & -A \end{bmatrix} \le 0, \ y^Tb>0.
$$
This implies $y^TA\le0$ and $-y^TA\le0$, hence $y^TA=0$. This proves the implication (1) $\Rightarrow$ (2).
Now assume there is $y$ such that $y^TA=0$ and $y^Tb>0$. Suppose there is $x$ with $Ax=b$.
$$
0= (y^TA)x = y^Tb>0,
$$
a contradiction. This proves (2) $\Rightarrow$ (1).


TITLE: Identifying cosets of normal subgroups in $UT_2(\mathbb{R})$.
QUESTION [3 upvotes]: From Artin's Algebra (problem 2.10.1):

Let $G$ be the group of invertible real upper triangular $2\times 2$ matrices. Determine whether or not the following conditions describe normal subgroups $H$ of $G$. If they do, use the First Isomorphism Theorem to identify the quotient group $G/H$.
  (a) $a_{11}=1$ (b) $a_{12}=0$ (c) $a_{11}=a_{22}$ (d) $a_{11}=a_{22}=1$.

I determined that $H\trianglelefteq G$ in the case of (a), (c), and (d). Moreover, in the case of (a) and (c), I found that $G/H\cong \mathbb{R}^\times$.
I'm a little bit confused about what it means to use the FIT to identify $G/H$. Does this mean I need to find a surjective homomorphism $\varphi$ from $G$ to some other group $Z$ such that $H=\ker\varphi$ so that $\varphi:G/H\to Z$ is an isomorphism (and hence $G/H\cong Z$)? I'm not quite sure because this only identifies $G/H$ up to isomorphism, but not explicitly.
This is what I did for (a) and (c). For (a) I let $\varphi$ be the surjective map $\varphi:G\to\mathbb{R}^\times$ where $\varphi(A)=a_{11}$. For (c), I let $\varphi$ be the surjective map $\varphi:G\to\mathbb{R}^\times$ where $\varphi(A)=a_{11}a_{22}^{-1}$.
I came up with these maps by thinking about the explicit descriptions of the cosets of $H$.
I haven't quite identified $G/H$ in (d), but I suspect that $G/H\cong \mathbb{R}^\times\times\mathbb{R}^\times$. As $A,B\in G$ are in the same coset of $H$ if and only if $a_{11}=b_{11}$ and $a_{22}=b_{22}$.
EDIT: For some reason I can't leave comments, so they are part of the edit.
-My question is: Is this approach of finding surjective homorphisms in order to identify $G/H$ up to isomorphism what Artin is asking me to do? This seems odd to me as describing the cosets explicitly is easy. (So I guess I'm also asking what the point of this exercise is.)

REPLY [3 votes]: As you suggested, I think $\varphi:G \to \mathbb{R}^\times \times \mathbb{R}^\times$ defined by $\varphi(A) = (a_{11}, a_{22})$ works for (d). Just be sure to verify that it is indeed a homomorphism.
When we "identify" or "classify" groups, we usually mean "find the isomorphism class" of the group. You express a concern that we identify $G/H$ up to isomorphism but not explicitly, but we are primarily concerned with the group structure, not what elements are used to represent the group elements.
Identifying the cosets explicitly is a good first step. For (d), I see that you notice that it is "matrices that share the same upper-left and bottom-right entries." However, how do you know that as a result, the group structure of $G/H$ is the same as that of $\mathbb{R}^\times \times \mathbb{R}^\times$? Without the isomorphism theorem, you can't just conclude that.
Disclaimer: this is my first year taking algebra, so please correct me if I have said anything inaccurate/incorrect.


TITLE: Prove $Ax = \frac{1}{2}x$ only has the trivial solution where $A$ has all integer entries.
QUESTION [1 upvotes]: Prove $Ax = \frac{1}{2}x$ only has the trivial solution where $A$ is a $n \times n$ matrix with integer entries and $x = (x_1, \ldots , x_n)$.
I am a bit rusty on my linear algebra and trying to review. I tried using the Invertible Matrix theorem. The problem was I couldn't seem to gain any traction with any of the equivalent statements.
Here is the link for anyone that needs a refresher: Invertible Matrix Theorem
Looking for hints rather than a specific solution.

REPLY [3 votes]: Write it as $x=2Ax$. If this has a nonzero solution, it has a nonzero rational solution and indeed a nonzero integer solution. But if $x$ has integer entries,
$x=2Ax$ has even entries. So then $x=2Ax$ has entries divisible by $4$, etc.....


TITLE: Intuition behind process of solving for eigenvalues and eigenvectors
QUESTION [0 upvotes]: I think I have a basic understanding of the intuition behind what eigenvalues and eigenvectors are themselves, but I'm struggling to understand why the process I've found online to solve for them actually works. I feel like I'm just going through the motions and have no idea why this process actually works.
Would it be possible for someone to provide me with some intuition behind the process in plain english? If there isn't any easy-to-explain intuition behind this process and as a linear algebra novice I'm better off just memorizing the steps, just tell me that. This is the process I'm referring to:

REPLY [2 votes]: An eigenvector for an endomorphism of a finite dimensional vector space $V$,  represented by a square matrix $A$ is a non-zerovector $v$ such that $Av$ is collinear to $v$, i.e a vector $v\ne 0$ such that $Av=\lambda v$ for some scalar $\lambda$. This translates into the homogeneous linear system:
$$(A-\lambda I)v=0.$$
As $v $ has to be non-zero, this implies the matrix $A$ is not invertible. This is characterised by the condition
$$\det(A-\lambda I)=0.$$
This determinant is a polynomial in $\lambda$, of degree equal to the dimension of $V$: the characteristic polynomial of the endomorphism (or of the matrix $A$.
Once you've solved for the roots of the characteristic polynomial (the eigenvalues of $A$), you have to find the non-trivial solutions of each linear system $(A-\lambda_iI)v=0$ (the eigenspace $V_{\lambda_i}$ associated to the eigenvalue $\lambda_i$), and more precisely, a basis of these eigenspaces.


text:
\begin{document}
\title[Diffusion on an Ising chain with kinks]{Diffusion on an Ising chain with kinks}
\author{Alioscia Hamma}
\affiliation{Massachusetts Institute of Technology, Research
Laboratory of Electronics, Cambridge MA 02139, USA}
\email{ahamma@perimeterinstitute.ca}
\author{Toufik Mansour}
\affiliation{Department of Mathematics, University of Haifa, Haifa 31905, Israel}
\email{toufik@math.haifa.ac.il}
\author{Simone Severini}
\affiliation{Institute for Quantum Computing and Department of Combinatorics \&
Optimization, University of Waterloo, Waterloo N2L 3G1, ON Canada}
\email{simoseve@gmail.com}
\begin{abstract}
We count the number of histories between the two degenerate minimum energy
configurations of the Ising model on a chain, as a function of the length $n$
and the number $d$ of kinks that appear above the critical temperature. This
is equivalent to count permutations of length $n$ avoiding certain
subsequences depending on $d$. We give explicit generating functions and
compute the asymptotics. The setting considered has a role when describing dynamics induced by quantum Hamiltonians with deconfined quasi-particles.
\end{abstract}
\maketitle

\section{Introduction}

Consider a chain with Ising variables $\sigma_{i}$ that can take the values
$\pm1$ on $n$ sites. The Ising model is described by the following action:
$S=U\sum_{i=1}^{n}(1-\sigma_{i}\sigma_{i+1})$, where $U>0$. This model has two
degenerate minimum energy configurations. Indeed, both the configurations
$\Sigma_{1,2}\equiv\{\sigma_{i}=\mp1$, for every $i\}$ minimize the energy for
this system with a value $S=0$. Every other configuration can be obtained by
flipping the $\sigma_{i}$ variables starting from either $\Sigma_{1}$ or
$\Sigma_{2}$: we see that flipping one variable costs an energy $4U$. We say that a variable is a
\emph{kink} if the adjacency variables have a different value. Flipping an
adjacent variable $\sigma_{i\pm1}$ will not change the total energy of the
system. However, if we flip a second variable $i\pm k$ with $k\geq2$,
\emph{i.e.}, we create another kink, then the cost in energy will be $8U$.
The total energy of a certain configuration $\{\sigma_{i}:i=1,...,n\}$ will be
given by $S=4U(d+1)$, where $d$ is the number of kinks, not including the
initial one.

It is obvious that the two minimum energy configurations $\Sigma_{1}$ and
$\Sigma_{2}$ are only separated by configurations that have energy $4U$. In
fact, we can start from, say $\Sigma_{1}$, pick a site $i$ and flip the
variable $\sigma_{i}$ from $-1$ to $+1$. In this way we keep staying in a
configuration with energy $4U$. Then, from there we can reach the
configuration $\Sigma_{2}$ by flipping only adjacent variables. We say that
kinks can propagate \emph{freely}, that is, without paying energy. The kink is
made of the walls of a domain with all variables of the same value. In one
dimension, making the domain larger does not change the domain walls. In
statistical mechanics, this implies that the Ising model in one dimension has
a critical temperature $T=0$. At every temperature $T>0$, some kinks will be
created, and once created, a\ kink can propagate freely and connect the two
minima (see, \emph{e.g.}, \cite{Kogut:79}). For this reason, at every $T>0$,
there is only one minimum energy configuration; there are two only when $T=0$.

We call \emph{history} the permutation on $n$ objects that indicate the
sequence of the flips connecting $\Sigma_{1}$ to $\Sigma_{2}$. So, for
instance, a history is given by the string $(i_{1},i_{2},...,i_{n})$ in which
we flip first the variable $\sigma_{1}$, then $\sigma_{2}$ and so on. As we
have pointed out, this history requires an energy $4U$. However, every time we
create a kink, we pay an energy $4U$. The energy of a history is therefore the
number $4U(d+1)$, where $d$ is number of kinks created during the entire
history, without including the first one. It is easy to compute the total
number of histories: since we must flip $n$ Ising variable, we can do it in
$n!$ possible ways, \emph{i.e.}, the number of permutations of length $n$. In
the present paper we count the total number of histories given the parameters
$n$ and $d$. We exhibit generating functions for the sequences and observe
that these numbers are asymptotically $2^{n-2d-1}(d+1)^{n}$. Our technique is
the one of generating trees (see, \emph{e.g.}, \cite{W1,W2}).

This scenario is related to all those models in condensed matter and
statistical mechanics, where two minima are separated by excitations that can
propagate freely (or quasi-freely). Even if the propagation is not free,
\emph{i.e.}, if we add a \textquotedblleft tension\textquotedblright\ to the
domains, there is a difference between propagating an excitation and creating
a new kink \cite{Kogut:79}.

Recently such a setting has become important again in the subject of
topological quantum computation \cite{Kitaev:03}. In this context, we have
quantum Hamiltonians with deconfined quasi-particles. The quasi-particles are
ends of strings. The quantum memory is encoded in the expectation value of
large, topological observables in a degenerate ground state. A crucial problem
is whether in this model quantum memory is stable for temperature higher than
absolute zero \cite{Dennis:02}. As soon as the temperature is greater than
zero, some kinks will be created with some density of probability in time, and
will start to propagate. If the total time to connect two degenerate ground
states will scale with the size of the system, the quantum memory will be
considered robust, otherwise it will be considered fragile. A precise
computation will require a knowledge about the number of all possible
histories for this process.

We will deal with a purely combinatorial framework. Let us consider a network
modeled by a chain with a finite number $n$ of nodes. In the network, the
first node is adjacent to second one; the second to the first and the third
one, and so on. To begin with, let us assume that there is a unique node of
the network having a special property. For example, the node possesses some
information, which has to be \emph{diffused} to the entire network. When the
clock ticks, the node passes the information to one its neighbors. The
process carries on, and at each time step, a single node passes the
information. It is clear that it takes exactly $n$ time steps for the
information to be transferred to the entire network.

In how many different ways this can be done? Summing over all possible initial
nodes, the answer to this question is $2^{n-1}$. This corresponds to the case
with a single kink introduced at the beginning of the process. In Figure~\ref{figS}
represented all the $2^{3-1}=4$ possible different histories, when
the number of nodes is $n=3$ (see the vertices $123$, $213$, $231$ and $321$).
The time steps of the diffusion are represented from left to right. In
this case $d=0$ because the only kink is the initial one.

Following the above description, let us now consider a variant in which we
introduce extra kinks. Again, at each time step a single node passes the
information, as we have seen before. We assume however that during the process
there are exactly $d$ nodes acquiring the information not from an adjacent
node. Additionally, these special nodes are not pairwise adjacent to each
other. The total number of ways in which the information can be propagated to
the entire network is the number of histories.

The paper is organized as follows: in Section 2 we introduce the notation and
formalize the problem; in Section 3 we state and prove the results. Section 4 is a brief conclusion.

\section{Set-up}

The graph $P_{n}=(V,E)$, where $V=\{1,2,...,n\}$ and edges
$E=\{\{1,2\},\{2,3\},...,\{n-1,n\}\}$, is called $n$\emph{-path}. We will
define below a procedure to assign labels to the vertices of $n$-paths. The
procedure will satisfy the specific conditions, giving the diffusion dynamics
which we have described in Introduction. For each integer $0\leq t\leq n$, we
define a function $f_{t}:V\longrightarrow\{+,-\}$. This gives the ordered set
$f_{t}=(f_{t}(1),f_{t}(2),...,f_{t}(n))$, specifying the image of the function
at time $t$. When $t=0$ and $t=n$, we assume that $f_{0}=(-,-,...,-)$ and
$f_{n}=(+,+,...,+)$, respectively. When $t=1$, we chose a vertex $v\in V$ and
set $f_{1}(v)=+$. In other words we designate a vertex to be a kink. At each
time step $t\geq2$, we chose a vertex $w$ such that
\begin{equation}
\begin{tabular}
[c]{lllll}
$f_{t}(w)=+$ & $\qquad$only if$\qquad$ & $f_{t-1}(z)=+$ & $\qquad$and$\qquad$
& $\{w,z\}\in E.$
\end{tabular}
\ \ \ \ \label{reg}
\end{equation}
The described rule allows us to \emph{transform }$f_{0}$ into $f_{n}$ in
exactly $n$ steps. To each one of the ordered sets $f_{0},f_{1},...,f_{n}$, we
can naturally associate a permutation $\pi$ of the set of $n$ points
$[n]=\{1,2,...,n\}$. A permutation $\pi$ is interpreted as a word of length
$n$ over the alphabet $[n]$, in which every symbol of $[n]$ appears exactly
once. Specifically, $\pi(i)=j$ if $f_{i}(j)=+$ and $f_{i-1}(j)=-$. Moreover,
by following Eq. (\ref{reg}) we have $\pi(i)=j$ if there is $k<i$, such that
$\pi(k)=j-1$ or $\pi(k)=j+1$.

Let $F_{n}$ be the set of all permutations of $[n]$ satisfying the above
conditions. The $k$-th permutation $\pi^{(k)}\in F_{n}$ is associated to the
ordered set $(f_{1}^{(k)},f_{2}^{(k)},...,f_{n}^{(k)})$. Notice that $k$ is
simply an index to distinguish between maps in $F_{n}$, being $F_{n}$ an
unordered set. An an example, the table below includes all elements of $F_{4}
$. The left column represents $(f_{1}^{(k)},f_{2}^{(k)},...,f_{3}^{(k)})$. It
is superfluous to include $f_{0}^{(k)}$ and $f_{4}^{(k)}$, since $f_{0}
^{(k)}=(-,-,-,-)$ and $f_{4}^{(k)}=(+,+,+,+)$ for every $k$. The right column
contains $\pi^{(k)}$. The first row is then $f_{1}^{(1)}=\left(
+,-,-,-\right)  ,f_{2}^{(1)}=\left(  +,+,-,-\right)  ,f_{3}^{(1)}=\left(
+,+,+,-\right)  $ and $\pi^{(1)}=1234$.

\begingroup

\scalefont{0.7}

\[
\begin{tabular}
[c]{l|l||l|l}
$\left(  +,-,-,-\right)  ,\left(  +,+,-,-\right)  ,\left(  +,+,+,-\right)  $ &
$1234$ & $\left(  -,-,+,-\right)  ,\left(  -,+,+,-\right)  ,\left(
+,+,+,-\right)  $ & $3214$\\\hline
$\left(  -,+,-,-\right)  ,\left(  +,+,-,-\right)  ,\left(  +,+,+,-\right)  $ &
$2134$ & $\left(  -,-,+,-\right)  ,\left(  -,+,+,-\right)  ,\left(
-,+,+,+\right)  $ & $3241$\\\hline
$\left(  -,+,-,-\right)  ,\left(  -,+,+,-\right)  ,(+,+,+,-)$ & $2314$ &
$\left(  -,-,+,-\right)  ,\left(  -,-,+,+\right)  ,\left(  -,+,+,+\right)  $ &
$3421$\\\hline
$\left(  -,+,-,-\right)  ,\left(  -,+,+,-\right)  ,(-,+,+,+)$ & $2341$ &
$\left(  -,-,-,+\right)  ,\left(  -,-,+,+\right)  ,\left(  -,+,+,+\right)  $ &
$4321$
\end{tabular}
\ \ .
\]

\endgroup

It is simple to see that $F_{n}\varsubsetneq S_{n}$ if $n\geq3$, where $S_{n}$
denotes the set of all permutations of $[n]$. Let us consider a permutation
$\pi\notin F_{4}$. For instance, let $\pi=1324$. The intermediate steps taking
$(-,-,-,-)$ to $(+,+,+,+)$ induced by $\pi$ are $(+,-,-,-),(+,-,+,-)$ and
$(+,+,+,-)$. Notice that the second step is not in agreement with our
procedure. This is because $\pi(2)=3$ and $f_{2}(3)=+$, but $\pi(1)=1$, while,
in order to agree with the procedure, we should have $\pi(1)=2$ or $\pi(1)=4$.
The permutations in the set $S_{n}-F_{n}$ are then characterized by an extra
parameter, which we denote by $d$. This parameter specifies the number of
vertices from which the procedure can start independently. We denote by
$\pi^{(d,k)}$ the $k$-th permutation, with exactly $d$ \emph{non-adjacent
sequences} of $+$'s, inducing the functions $f_{1}^{(d,k)},f_{2}
^{(d,k)}...,f_{n-1}^{(d,k)}$. When $d=0$, we have the above setting. In this
case, we simply wrote $\pi^{(k)}$ instead of $\pi^{(0,k)}$. The set of the
permutations of $[n]$ of the form $\pi^{(d,k)}$ is denoted by $F_{n}^{d}$.
There is a clear relation between $n$ and $d$; when $n$ is even, $d\leq n/2$;
when $n$ is odd, $d\leq(n-1)/2$. In the next section, we will find an explicit
formula for $\#F_{n}^{d}$. It is a simple fact that $S_{n}=\bigcup
\nolimits_{d}F_{n}^{d}$, every $n$. In the table below, we include the
permutations in $F_{4}^{1}\equiv S_{4}-F_{4}$. Since $\#F_{4}=8$, then
$\#F_{4}^{1}=16$.

\begingroup

\scalefont{0.7}

\[
\begin{tabular}
[c]{l|l||l|l}
$\left(  +,-,-,-\right)  ,\left(  +,+,-,-\right)  \left(  +,+,-,+\right)  $ &
$1243$ & $\left(  -,-,+,-\right)  ,\left(  +,-,+,-\right)  ,\left(
+,+,+,-\right)  $ & $3124$\\\hline
$\left(  +,-,-,-\right)  ,\left(  +,-,+,-\right)  ,\left(  +,+,+,-\right)  $ &
$1324$ & $\left(  -,-,+,-\right)  ,\left(  +,-,+,-\right)  ,\left(
+,-,+,+\right)  $ & $3142$\\\hline
$\left(  +,-,-,-\right)  ,\left(  +,-,+,-\right)  ,\left(  +,-,+,+\right)  $ &
$1342$ & $\left(  -,-,+,-\right)  ,\left(  -,-,+,+\right)  ,\left(
+,-,+,+\right)  $ & $3412$\\\hline
$\left(  +,-,-,-\right)  ,\left(  +,-,-,+\right)  ,\left(  +,+,-,+\right)  $ &
$1423$ & $\left(  -,-,-,+\right)  ,\left(  +,-,-,+\right)  ,\left(
+,+,-,+\right)  $ & $4123$\\\hline
$\left(  +,-,-,-\right)  ,\left(  +,-,-,+\right)  ,\left(  +,-,+,+\right)  $ &
$1432$ & $\left(  -,-,-,+\right)  ,\left(  +,-,-,+\right)  ,\left(
+,-,+,+\right)  $ & $4132$\\\hline
$\left(  -,+,-,-\right)  ,\left(  +,+,-,-\right)  ,\left(  +,+,-,+\right)  $ &
$2143$ & $\left(  -,-,-,+\right)  ,\left(  -,+,-,+\right)  ,\left(
+,+,-,+\right)  $ & $4213$\\\hline
$\left(  -,+,-,-\right)  ,\left(  -,+,-,+\right)  ,\left(  +,+,-,+\right)  $ &
$2413$ & $\left(  -,-,-,+\right)  ,\left(  -,+,-,+\right)  ,\left(
-,+,+,+\right)  $ & $4231$\\\hline
$\left(  -,+,-,-\right)  ,\left(  -,+,-,+\right)  ,\left(  -,+,+,+\right)  $ &
$2431$ & $\left(  -,-,-,+\right)  ,\left(  -,-,+,+\right)  ,\left(
+,-,+,+\right)  $ & $4312$
\end{tabular}
\ \ .
\]

\endgroup

\section{Enumeration}
A generating tree consists of a \emph{root label} and a set of
\emph{succession rules}. Following \cite{W2}, a \emph{generating
tree} is a rooted labeled tree with the property that if $v_{1}$
and $v_{2}$ are any two vertices with the same label and $l$ is
any label, then $v_{1}$ and $v_{2}$ have exactly the same number
of children with the label $l$. To specify a generating tree it
therefore suffices to specify \emph{(i)} the label of the root,
and \emph{(ii) }a set of succession rules explaining how to derive
from the label of a parent the labels of all of its children. For
example, a portion of the generating tree $\mathcal{G}$ for the
set of all unrestricted permutations is illustrated in Figure~\ref{figS}.

\begin{figure}[htp]
\begin{center}
{\small
\leaf{$\vdots$}\leaf{$\vdots$}\leaf{$\vdots$}\leaf{$\vdots$}\branch{4}{$\begin{array}{c}(3)\\321\end{array}$}
\leaf{$\vdots$}\leaf{$\vdots$}\leaf{$\vdots$}\leaf{$\vdots$}\branch{4}{$\begin{array}{c}(3)\\231\end{array}$}
\leaf{$\vdots$}\leaf{$\vdots$}\leaf{$\vdots$}\leaf{$\vdots$}\branch{4}{$\begin{array}{c}(3)\\213\end{array}$}
\branch{3}{$\begin{array}{c}(2)\\21\end{array}$}

\leaf{$\vdots$}\leaf{$\vdots$}\leaf{$\vdots$}\leaf{$\vdots$}\branch{4}{$\begin{array}{c}(3)\\312\end{array}$}
\leaf{$\vdots$}\leaf{$\vdots$}\leaf{$\vdots$}\leaf{$\vdots$}\branch{4}{$\begin{array}{c}(3)\\132\end{array}$}
\leaf{$\vdots$}\leaf{$\vdots$}\leaf{$\vdots$}\leaf{$\vdots$}\branch{4}{$\begin{array}{c}(3)\\123\end{array}$}
\branch{3}{$\begin{array}{c}(2)\\12\end{array}$} \branch{2}{$\begin{array}{c}(1)\\1\end{array}$}

\qobitree} \caption{Generating the permutations according to their length}\label{figS}
\end{center}
\end{figure}

The root is indexed by the permutation of length $1$. A vertex indexed by a
permutation $\pi$ of length $n$ has $n+1$ children. These are respectively
indexed by the $n+1$ permutations that can be obtained by inserting the letter
$n+1$ in the word $\pi_{1}\pi_{2}\cdots\pi_{n}$. Clearly, this tree is
isomorphic to a simpler tree, in which the root is labeled by the number $1$,
and a node labeled by $(n)$ has exactly $n+1$ children, each one
labeled by $(n+1)$:

\begin{itemize}
\item \textbf{Root}: $(1)$;

\item \textbf{Rule}: $(s)\rightsquigarrow(s+1)^{s+1}$.
\end{itemize}

In order to enumerate the number of permutations in $F_{n}^{d}$, we define the
generating tree $\mathcal{G}$, in which we replace each permutation $\pi
=\pi_{1}\pi_{2}\cdots\pi_{n}$ with $\pi_1=1$ by the vector Vec$(\pi)=(j,k,r)$, where $\pi_{j}=n$, $\pi\in F_{n}^{k}$ and
\[
r=\left\{
\begin{array}
[c]{ll}
1, & \pi_{n}^{-1}<\pi_{n-1}^{-1};\\
0, & \pi_{n}^{-1}>\pi_{n-1}^{-1},
\end{array}
\right.
\]
as it is shown in Figure~\ref{fig1}.
\begin{figure}[h]
\begin{center}
{\small
\leaf{.}\leaf{.}\leaf{.}\leaf{.}\branch{4}{$\begin{array}{c}(2,0,1)\\\pi=1432\end{array}$}
\leaf{.}\leaf{.}\leaf{.}\leaf{.}\branch{4}{$\begin{array}{c}(3,1,0)\\\pi=1342\end{array}$}
\leaf{.}\leaf{.}\leaf{.}\leaf{.}\branch{4}{$\begin{array}{c}(4,1,0)\\\pi=1324\end{array}$}
\branch{3}{$\begin{array}{c}(2,0,1)\\\pi=132\end{array}$}

\leaf{.}\leaf{.}\leaf{.}\leaf{.}\branch{4}{$\begin{array}{c}(2,0,1)\\\pi=1423\end{array}$}
\leaf{.}\leaf{.}\leaf{.}\leaf{.}\branch{4}{$\begin{array}{c}(3,0,1)\\\pi=1243\end{array}$}
\leaf{.}\leaf{.}\leaf{.}\leaf{.}\branch{4}{$\begin{array}{c}(4,0,0)\\\pi=1234\end{array}$}
\branch{3}{$\begin{array}{c}(3,0,0)\\\pi=123\end{array}$}
\branch{2}{$\begin{array}{c}(2,0,0)\\\pi=12\end{array}$}

\qobitree} \caption{Generating the permutations $\pi=\pi_1\pi_2\cdots\pi_n$ with $\pi_1=1$ according to Vec$(\pi)$}\label{fig1}
\end{center}
\end{figure}

\begin{proposition}
\label{pro1} The generating tree $\mathcal{G}$ is given by

\begin{itemize}
\item \textbf{Roots: }$(2,0,0)$ and $(1,0,1)$;

\item \textbf{Rules: }

$(j,k,0)\rightsquigarrow(1,k+1,1)\cdots(j,k+1,1)(j+1,k,0)\cdots(n+1,k,0)$;

$(j,k,1)\rightsquigarrow(1,k,1)\cdots(j,k,1)(j+1,k,0)\cdots(n+1,k,0)$.
\end{itemize}
\end{proposition}

\begin{proof}
From the definitions, the permutations $12$ and $21$ are associated to the
vectors $(2,0,0)$ and $(1,0,1)$, respectively. Let $\pi=1\pi_{2}\cdots\pi_{n}$
be a permutation in $S_{n}$ associated to the vector $(j,k,0)$. By inserting
the letters $n+1$ between position $i-1$ and position $i$, we obtain a new
permutation $\pi=1\pi_{2}\cdots\pi_{i-1}(n+1)\pi_{i}\cdots\pi_{n}\in S_{n+1}$
associated to the vector $(i,k+1,1)$, for all $i=2,3,\ldots,j$, and the
vector $(i,k,0)$, for all $i=j+1,j+2,\ldots,n+1$. Let $\pi=1\pi_{2}\cdots
\pi_{n}$ be a permutation in $S_{n}$ associated to the vector $(j,k,1)$. By
inserting the letters $n+1$ between position $i-1$ and position $i$, we obtain
a new permutation $\pi=1\pi_{2}\cdots\pi_{i-1}(n+1)\pi_{i}\cdots\pi_{n}\in
S_{n+1}$ associated to the vector $(i,k,1)$, for all $i=1,2,\ldots,j$, and the
vector $\ (i,k,0)$, for all $i=j+1,j+2,\ldots,n+1$. This completes the proof.
\end{proof}

Let $G_{0}(t;u,v)$ and $G_{1}(t;u,v)$ be the associated generating functions:
\begin{align*}
G_{r}(t;u,v)  &  =\sum_{n\geq2}t^{n}\sum_{j\geq2}\sum_{k\geq0}\sum_{\pi\in
S_{n}\,:\text{Vec}(\pi)=(j,k,r)}u^{j}v^{k}\\
&  =\sum_{n\geq2}t^{n}\sum_{j\geq2}\sum_{k\geq0}g_{n,j,k,r}u^{j}v^{k},
\end{align*}
where $r=0,1$. Alternatively, this series counts the vertices of the tree
$\mathcal{G}$ by their height and their label (the root being at height $2$).

\begin{proposition}
\label{pro2}The generating function for the number of permutations
$\pi=\pi_{1}\cdots\pi_{n}$ in $S_{n}$, $n\geq2$, according to the statistics
$j,k$, where $\pi_{j}=n$ and $\pi\in F_{n}^{k}$, is given by
$G_{0}(t;u,v)+G_{1}(t;u,v)$ such that the generating functions $G_{0}(t;u,v)$ and
$G_{1}(t;u,v)$ satisfy
\[
G_{0}(t;u,v)=t^{2}u^{2}+\frac{tu}{1-u}(G_{0}(t;u,v)-uG_{0}(tu;1,v))+\frac
{tu}{1-u}(G_{1}(t;u,v)-uG_{1}(tu;1,v))
\]
and
\[
G_{1}(t;u,v)=t^{2}u+\frac{tuv}{1-u}(G_{0}(t;1,v)-G_{0}(t;u,v))+\frac{tu}
{1-u}(G_{1}(t;1,v)-G_{1}(t;u,v)).
\]
\end{proposition}
\begin{proof}
Since $g_{n,j,k,r}$ is the number of vertices in the generating tree $\mathcal{G}$, as it was shown in
Proposition~\ref{pro1}, with label $(j,k,r)$, we obtain that
\begin{align*}
g_{n+1,j,k,0}&=\sum_{i=1}^{j-1} (g_{n,i,k,0}+g_{n,i,k,1}),\\
g_{n+1,j,k,1}&=\sum_{i=j}^n (g_{n,i,k-1,0}+g_{n,i,k,1}).
\end{align*}
Let $g_{n+1,r}(u,v)=\sum_{j\geq1}\sum_{k\geq0}g_{n+1,j,k,r}u^jv^k$ for $r=0,1$. Rewriting the above recurrence relations in terms of $g_{n,r}(u,v)$, we obtain that
\begin{align*}
g_{n+1,0}(u,v)&=\sum_{j\geq1}\sum_{k\geq1}u^jv^k\left(\sum_{i=1}^{j-1}(g_{n,i,k,0}+g_{n,i,k,1})\right),\\
g_{n+1,1}(u,v)&=\sum_{j\geq1}\sum_{k\geq1}u^jv^k\left(\sum_{i=j}^n (g_{n,i,k-1,0}+g_{n,i,k,1})\right),
\end{align*}
which is equivalent to
\begin{align*}
g_{n+1,0}(u,v)&=\sum_{j\geq1}\sum_{k\geq0}g_{n,j,k,0}v^{k}(u^{j+1}+\cdots+u^{n+1})+\sum_{j\geq1}\sum_{k\geq0}g_{n,j,k,1}v^k(u^{j+1}+\cdots+u^{n+1}),\\
g_{n+1,1}(u,v)&=\sum_{j\geq1}\sum_{k\geq0}g_{n,j,k,0}v^{k+1}(u^1+\cdots+u^j)+\sum_{j\geq1}\sum_{k\geq0}g_{n,j,k,1}v^k(u^1+\cdots+u^j).
\end{align*}
Multiplying by $t^{n+1}$ and summing over $n\geq2$ together with using the initial conditions $g_{2,0}(u,v)=u^2$ and $g_{2,1}(u,v)=u$, we obtain that
\begin{align*}
G_{0}(t;u,v)  &  =t^{2}u^{2}+t\sum\limits_{n\geq2}\sum\limits_{j\geq1}
\sum\limits_{k\geq0}g_{n,j,k,0}t^{n}v^{k}(u^{j+1}+\cdots+u^{n+1}
)+t\sum\limits_{n\geq2}\sum\limits_{j\geq1}\sum\limits_{k\geq0}g_{n,j,k,1}
t^{n}v^{k}(u^{j+1}+\cdots+u^{n+1})\\
&  =t^{2}u^{2}+\frac{tu}{1-u}\sum\limits_{n\geq2}\sum\limits_{j\geq1}
\sum\limits_{k\geq0}g_{n,j,k,0}t^{n}v^{k}(u^{j}-u^{n+1})+\frac{tu}{1-u}
\sum\limits_{n\geq2}\sum\limits_{j\geq1}\sum\limits_{k\geq0}g_{n,j,k,1}
t^{n}v^{k}(u^{j}-u^{n+1}),
\end{align*}
and
\begin{align*}
G_{1}(t;u,v)  &  =t^{2}u+t\sum\limits_{n\geq2}\sum\limits_{j\geq1}
\sum\limits_{k\geq0}g_{n,j,k,0}t^{n}v^{k+1}(u^{1}+\cdots+u^{j})+t\sum
\limits_{n\geq2}\sum\limits_{j\geq1}\sum\limits_{k\geq0}g_{n,j,k,1}t^{n}
v^{k}(u^{1}+\cdots+u^{j})\\
&  =t^{2}u+\frac{tuv}{1-u}\sum\limits_{n\geq2}\sum\limits_{j\geq1}
\sum\limits_{k\geq0}g_{n,j,k,0}t^{n}v^{k}(1-u^{j})+\frac{tu}{1-u}
\sum\limits_{n\geq2}\sum\limits_{j\geq1}\sum\limits_{k\geq0}g_{n,j,k,1}
t^{n}v^{k}(1-u^{j}).
\end{align*}
From the definitions of the generating functions $G_0(t;u,v)$ and
$G_1(t;u,v)$, we get that these functions satisfy the
following functional equations:
\begin{align*}
G_{0}(t;u,v)  &  =t^{2}u^{2}+\frac{tu}{1-u}(G_{0}(t;u,v)-uG_{0}(tu;1,v))+\frac{tu}
{1-u}(G_{1}(t;u,v)-uG_{1}(tu;1,v)),
\end{align*}
and
\begin{align*}
G_{1}(t;u,v)  &  =t^{2}u+\frac{tuv}{1-u}(G_{0}(t;1,v)-G_{0}(t;u,v))+\frac{tu}{1-u}
(G_{1}(t;1,v)-G_{1}(t;u,v)),
\end{align*}
as claimed.
\end{proof}

\begin{theorem}
\label{th01}The generating function
\[
G(t,v)=\sum_{n\geq2}\sum_{d\geq0}\#F_{n}^{d}v^{d}t^{n}
\]
is given by
\[
G(t,v)=\sum_{j\geq0}\frac{4t^{2}\sqrt{1-v}(1-(1+2j)\sqrt{1-v}t-t(1-v))v^{j}
}{(1+\sqrt{1-v})^{1+2j}(1-2jt\sqrt{1-v})^{2}(1-2(j+1)t\sqrt{1-v})^{2}}.
\]
\end{theorem}
\begin{proof} Denote the generating functions
$G_{0}(t;u,v)+G_{1}(t;u,v)$ and $vG_{0}(t;u,v)+G_{1}(t;u,v)$ by
$G(t;u,v)$ and $H(t;u,v)$, respectively. Then,
Proposition~\ref{pro2} gives that
\[\begin{array}{l}
\left(  1-\frac{t^{2}u^{2}(1-v)}{(1-u)^{2}}\right)  G(t;u,v)\\
\qquad\qquad\qquad+\frac{u^{2}
t}{(1-u)^{2}}(1-u+ut(1-v))G(ut;1,v)-\frac{ut}{1-u}H(t;1,v)+\frac{ut^{2}
(u^{2}-1-u^{2}t(1-v))}{1-u}=0
\end{array}
\]
and
\[
\begin{array}{l}
\left(  1-\frac{t^{2}u^{2}(1-v)}{(1-u)^{2}}\right)  H(t;u,v)\\
\qquad\qquad\qquad+\frac{u^{2}
vt}{1-u}G(ut;1,v)-\frac{ut}{(1-u)^{2}}(1-u-ut(1-v))H(t;1,v)+\frac{ut^{2}}
{1-u}(u-1-vu+vu^{2}+ut(1-v))=0.\end{array}
\]
This type of functional equations can be solved systematically using
the kernel method (see \cite{HM} and references therein). In this
case, if we substitute $u=p=\frac{1}{1+t\sqrt{1-v}}$ and
$u=q=\frac{1}{1-t\sqrt{1-v}}$, we obtain that
\[
H(t;1,v)=\frac{1+\sqrt{1-v}}{1+\sqrt{1-v}t}G(\frac{t}{1+\sqrt{1-v}
t};1,v)+\frac{t^{2}\sqrt{1-v}(2+\sqrt{1-v}+t\sqrt{1-v})}{(1+\sqrt{1-v}t)^{2}}
\]
and
\[
H(t;1,v)=\frac{1-\sqrt{1-v}}{1-\sqrt{1-v}t}G(\frac{t}{1-\sqrt{1-v}
t};1,v)+\frac{t^{2}\sqrt{1-v}(2-\sqrt{1-v}-t\sqrt{1-v})}{(1-\sqrt{1-v}t)^{2}
}.
\]
Hence, the generating function $G(t,v)=G(t;1,v)$ satisfies
\begin{align*}
&  \frac{1+\sqrt{1-v}}{1+\sqrt{1-v}t}G(\frac{t}{1+\sqrt{1-v}t},v)+\frac
{t^{2}\sqrt{1-v}(2+\sqrt{1-v}+t\sqrt{1-v})}{(1+\sqrt{1-v}t)^{2}}\\
&  =\frac{1-\sqrt{1-v}}{1-\sqrt{1-v}t}G(\frac{t}{1-\sqrt{1-v}t},v)+\frac
{t^{2}\sqrt{1-v}(2-\sqrt{1-v}-t\sqrt{1-v})}{(1-\sqrt{1-v}t)^{2}}
\end{align*}
which is equivalent to
\[
G(t,v)=\frac{4t^{2}\sqrt{1-v}}{(1-2t\sqrt{1-v})^{2}(1+\sqrt{1-v})}
(1-t\sqrt{1-v}-t(1-v))+\frac{v}{(1+\sqrt{1-v})^{2}(1-2t\sqrt{1-v})}G\left(
\frac{t}{1-2t\sqrt{1-v}},v\right)  .
\]
Applying the above functional equation an infinite number of times,
we can find an explicit formula for the generating function
$G(t,v)$,as requested.
\end{proof}

Let $h_{n}(v)$ be the polynomial $\sum_{d=0}^{n}\#F_{n}^{d}v^{d}$.
For $n=2,3,\ldots,10$, Theorem \ref{th01} gives
\begin{align*}
h_{2}(v) &  =2,\\
h_{3}(v)&=4+2v,\\
h_{4}(v)&=8+16v,\\
h_{5}(v) &  =16+88v+16v^{2},\\
h_{6}(v)&=32+416v+272v^{2},\\
h_{7}(v) &  =64+1824v+2880v^{2}+272v^{3},\\
h_{8}(v)&=128+7680v+24576v^{2}+7936v^{3},\\
h_{9}(v) &  =256+31616v+185856v^{2}+137216v^{3}+7936v^{4},\\
h_{10}(v)&=512+128512v+1304832v^{2}+1841152v^{3}+353792v^{4}.
\end{align*}
On the other hand, Theorem \ref{th01} can be used to obtain explicit
formula for the generating functions
$h^{d}(t)=\sum_{n\geq2}\#F_{n}^{d}t^{n}$. For example, Theorem
\ref{th01}, with $v=0$, gives
$h^{0}(t)=\frac{2t^{2}}{1-2t}=\sum_{n\geq 2}2^{n-1}t^{n}$, which
implies that $\#F_{n}^{0}=2^{n-1}$, for all $n\geq2$. More
generally, in order to obtain an explicit formula for the generating
function $h^{d}(t)$, on the basis of the theorem, it is enough to
take the derivative of the sum
\[
\sum_{j=0}^{d}\frac{2t^{2}v^{j}\sqrt{1-v}}{(1-2jt\sqrt{1-v})(1-2(j+1)t\sqrt
{1-v})(1+\sqrt{1-v})^{2j+1}}
\]
exactly $d$ times and then substitute $v=0$. Applying Theorem~\ref{th01} for $d=0$, that is looking for the free coefficient of $v$ in the generating function $G(t,v)$ (in this case also $j=0$), we get that
\[h^0(t)=\frac{2t^2}{1-2t}.\]
By considering the coefficient of $v^j$, $j=1,2,3$, in the generating function $G(t,v)$ (see Theorem~\ref{th01}), we obtain an explicit formula for the generating function $h^j(t)$, and we can state the following result.

\begin{corollary}
We have
\begin{align*}
h^{0}(t)  &  =\frac{2t^{2}}{1-2t},\qquad h^{1}(t)=\frac{2t^{3}}{(1-2t)^{2}
(1-4t)},\\
h^{2}(t)  &  =\frac{16t^{5}(1-3t)}{(1-2t)^{3}(1-4t)^{2}(1-6t)},\qquad
h^{3}(t)=\frac{16t^{7}(17-184t+636t^{2}-720t^{3})}{(1-2t)^{4}(1-4t)^{3}
(1-6t)^{2}(1-8t)}.
\end{align*}
\end{corollary}

This gives an exact formula for $\#F_{n}^{d}$, when $d=0,1,2,3$ and
$n\geq1,3,5,7$, respectively
\begin{align*}
\#F_{n}^{0} &  =2^{n-1};\\
\#F_{n}^{1}&=2^{n-2}
(2^{n-1}-n);\\
\#F_{n}^{2} &  =\frac{1}{32}6^{n}-\frac{1}{16}4^{n}\left(  n-1\right)
+\frac{1}{32}2^{n}\left(  2n^{2}-4n-1\right)  \\
\#F_{n}^{3} &  =\frac{1}{128}8^{n}-\frac{1}{64}6^{n}\left(
n-2\right) +\frac{1}{64}4^{n}\left(  n^{2}-4n+2\right)
-\frac{1}{192}2^{n}\left( 12n^{2}-13n+2n^{3}+6\right).
\end{align*}

We now focus on the asymptotic behavior of $h_{d}$. Two sequences $a_{n}$ and
$b_{n}$ are said to be \emph{asymptotically equivalent} as $n\rightarrow
\infty$ if $\lim_{n\rightarrow\infty}\frac{a_{n}}{b_{n}}=1$. We denote this
fact by $a_{n}\sim b_{n}$.

\begin{theorem}
For any fixed $d\geq0$,
\[
\#F_{n}^{d}\sim2^{n-2d-1}(d+1)^{n}.
\]
\end{theorem}
\begin{proof}
Theorem \ref{th01} shows that the smallest positive pole of the generating
function $h^{d}(t)$ is $t^{\ast}=\frac{1}{2(d+1)}$ of order $1$. Thus, we have
$\#F_{n}^{d}\sim c_{d}2^{n}(d+1)^{n}$. Concerning the constant $c_{d}$, we can
write
\begin{align*}
c_{d}  &  =\lim\limits_{t\rightarrow t^{\ast}}(1-t/t^{\ast})\lim
\limits_{v\rightarrow0}\frac{1}{d!}\frac{\partial^{d}}{\partial v^{d}}\left(
\sum_{j\geq0}\frac{4t^{2}\sqrt{1-v}(1-(1+2j)\sqrt{1-v}t-t(1-v))v^{j}}
{(1+\sqrt{1-v})^{1+2j}(1-2jt\sqrt{1-v})^{2}(1-2(j+1)t\sqrt{1-v})^{2}}\right)
\\
&  =\lim\limits_{t\rightarrow t^{\ast}}(1-t/t^{\ast})\lim\limits_{v\rightarrow
0}\left(  \sum_{j=0}^{d}\frac{\partial^{d-j}}{\partial v^{d-j}}\frac
{4j!{\binom{{d}}{{j}}}t^{2}\sqrt{1-v}(1-(1+2j)\sqrt{1-v}t-t(1-v))}
{d!(1+\sqrt{1-v})^{1+2j}(1-2jt\sqrt{1-v})^{2}(1-2(j+1)t\sqrt{1-v})^{2}}\right)
\\
&  =\lim\limits_{t\rightarrow t^{\ast}}\lim\limits_{v\rightarrow0}\frac
{4t^{2}(1-t/t^{\ast})\sqrt{1-v}(1-(1+2d)\sqrt{1-v}t-t(1-v))}{(1+\sqrt
{1-v})^{1+2d}(1-2dt\sqrt{1-v})^{2}(1-2(d+1)t\sqrt{1-v})^{2}}\\
&  =\lim\limits_{t\rightarrow t^{\ast}}\frac{4t^{2}(1-t/t^{\ast})^{2}
}{2^{1+2d}(1-2dt)^{2}(1-t/t^{\ast})^{2}}\\
&  =\frac{4(t^{\ast})^{2}}{2^{1+2d}(1-2d/t^{\ast})^{2}}\\
&  =\frac{1}{2^{2d+1}},
\end{align*}
as claimed.
\end{proof}

\section{Conclusions}
In this paper, we have counted the number $\#F_{n}^{d}$ of
histories that allow to connect a ground state of an Ising chain
with $n$ variables to the other one, having specified the number
$d$ of domain walls (or kinks) created in every history. We have
given the generating functions and studied the asymptotic
behavior.

The solution of this problem is important in statistical
mechanics, to solve the random walk with kinks, and in quantum
computing, to investigate the robustness of topological quantum
memory at finite temperature. There is a number of open problems.
A first problem would be to count the number of histories to flip
the Ising variables along a non contractible loop in a torus. A
second open problem would be to introduce the possibility that at
a given click no variable is flipped or that a variables is
flipped back. Eventually, the goal would be is to assign
probabilities to the three different events: flipping an adjacent
variable, creating a kink, no flip, and computing the probability
of making a loop around the torus in a given number of steps.


TITLE: Product in the category of functors.
QUESTION [3 upvotes]: Let $A$ be a category and $C= Fun(A, Set)$ (i.e. the objects are functors and morphisms are natural transformations between them). I want to know if this category has a product. For given $X \in A$ and functors $F_i \in C$, is $\Pi_{i \in \Lambda}F_i(X)$ the correct product? If yes, what would be the projection maps onto the $F_i$'s? I'm having a hard time constructing the required unique natural transformation. Any help is appreciated.

REPLY [6 votes]: Oskar already gave a good answer (+1). I just wanted to add a different perspective.
Given a collection of objects $C_i$ in a category $C$, the product of the $C_i$, $\prod_i C_i$, is an object representing the (contravariant) functor $C\to \newcommand\Set{\mathbf{Set}}\Set$
$$A \mapsto \prod_i\newcommand\Hom{\operatorname{Hom}} \Hom(A,C_i).$$
Thus if $C$ and $A$ are categories, if $F_i$ are functors in $C^A$, the product of the $F_i$ is the functor $F$ representing
$$G \mapsto \prod_i\Hom_{C^A}(G,F_i).$$
I.e. it is a functor satisfying
$$\Hom_{C^A}(G,F)\simeq \prod_i \Hom_{C^A}(G,F_i).$$
However if we already know that $C$ has products, then let $F'(x)=\prod_i F_i(x)$ for any $x\in A$.
Then $$\Hom_C(y,F'(x)) \simeq \prod_i \Hom_C(y,F_i(x))$$ as functors from $C^{\mathrm{op}}\times A\to \Set$. Thus for any functor $G:A\to C$, given a natural transformation $\mu:G\to F'$, for any $x\in A$, we can use this natural isomorphism to break apart the component $\mu_x:G(x)\to F'(x)$ of the natural transformation into maps $\mu_{x,i} : G(x)\to F_i(x)$ giving natural transformations $\mu_i$, and conversely given natural transformations $\mu_i : G\to F_i$, we can put them together to get a natural transformation $\mu$. Thus $F'$ satisfies
$$\Hom_{C^A}(G,F')\simeq \prod_i\Hom_{C^A}(G,F_i),$$
so $F'=\prod_i F_i$ as desired.
It should hopefully be clear how to generalize this argument to arbitrary codomain categories and arbitrary limits/colimits as indicated by Derek's comment. (Well I already generalized to arbitrary codomain categories, I guess I mean to arbitrary shapes of limits/colimits).


TITLE: Is there a natural measures on the space of measurable functions?
QUESTION [37 upvotes]: Given a set Ω and a σ-algebra F of subsets, is there some natural way to assign something like a "uniform" measure on the space of all measurable functions on this space?  (I suppose first it would be useful to know if there's even a natural σ-algebra to use on this space.)
The reason I'm asking is because I'd like to do the following.  Let Ω be the (2-dimensional) surface of a sphere, with the uniform probability distribution.  Let F be the Borel σ-algebra, and let G be the sub-algebra consisting of all measurable sets composed of lines of longitude.  (That is, S is in G iff S is measurable and for all x in S, S contains all points with the same longitude as x.)  Let A be the set of all points with latitude 60 degrees north or higher (a disc around the north pole).
Let f be a G-measurable function defined on Ω such that the integral of f over any G-measurable set B equals the measure of (A\cap B).  (This is a standard tool in defining the conditional probability of A given G-measurable sets.)  It's not hard to show that for any such function f, for almost-all x, f(x) will equal the unconditional measure of A.
What I'd like to be able to say is that for any x, for almost-all such functions f, f(x) will equal the unconditional measure of A.  However, I can't say "almost-all" on the functions unless I have some measure on the space of functions.
Clearly I can do this by concentrating all the measure on the single constant function in this set.  But I'd like to be able to pick out this most "generic" such function even in cases where A isn't so nice and symmetric.
Maybe there's some other, simpler question I should be asking first?

REPLY [3 votes]: Kirk Sturtz proves that the category $Meas$ is monoidal closed in the paper Categorical probability theory.


TITLE: Prove/Disprove if $\sup \left\{\sqrt[n]{a_n}:n\ \in \mathbb{N}\right\}<1$ than $\sum_{n=1}^\infty a_n < \infty$
QUESTION [1 upvotes]: Let $a_n \ge 0$ for every $n \in \mathbb{N}$.
Prove or disprove: if $\sup \left\{\sqrt[n]{a_n}:n\ \in \mathbb{N}\right\}<1$, than $\sum_{n=1}^\infty a_n < \infty$.
I think that this one is false.
We know that if $\lim_{n \to \infty} \sqrt[n]{a_n}<1$ than the series converges, but if the limit doesn't exists than it can diverge or converge.
So I want to take a split series, between even and odd, such that $\sup \left\{\sqrt[n]{a_n}:n\ \in \mathbb{N}\right\}<1$, but the limit of $a_n \ne 0$, or something like that, so the series converges.
Am I on the right way?
Thanks!

REPLY [2 votes]: Denote $\overline{s}=\sup\left\{ \sqrt[n]{a_{n}}:n\in\mathbb{N}\right\}$ and let $q=\frac{\overline{s}+1}{2}$. $\;\forall  n\in\mathbb{N}$ we have:
$$\sqrt[n]{a_{n}}\le\overline{s}<q<1\Longrightarrow$$
$$0\le a_{n}<q^{n}<1$$
Hence $\;\displaystyle{\sum_{n=1}^{\infty}a_{n}}$ converges by the direct comparison test.


text:
\begin{document}
\title{Part of the D - dimensional Spiked harmonic oscillator spectra}
\author{ Omar Mustafa and Maen Odeh\\
 Department of Physics, Eastern Mediterranean University\\
 G. Magusa, North Cyprus, Mersin 10 - Turkey\\
 email: omustafa.as@mozart.emu.edu.tr\\
\date{}\\}
\maketitle
\begin{abstract}
{\small The pseudoperturbative shifted - $l$ expansion technique PSLET
[5,20] is generalized for states with arbitrary number of nodal zeros.
Interdimensional degeneracies, emerging from the isomorphism between
angular momentum and dimensionality of the central force Schr\"odinger
equation, are used to construct part of the $D$ - dimensional spiked
harmonic oscillator bound - state spectra. PSLET results are found to
compare excellently
with those from direct numerical integration and generalized variational
methods [1,2].}
\end{abstract}
\newpage

\section{Introduction}

The simplest model of realistic interaction potentials in atomic, molecular,
and nuclear physics is provided by the spiked harmonic oscillator
\begin{equation}
V(q)=c_1 q^2+c_2 q^{-b}~~,~~~~ c_1, c_2, b>0~~,~~~~q\in(0, \infty).
\end{equation}\\
The construction of its bound - states has attracted attention over the
last few years [1-9]. It is an interesting model not only because of being
a singular potential representing a repulsive core in realistic interactions,
but also because of its intrinsic properties in view of mathematical physics
[10-16]. However, most of the studies on this model potential (1) were
devoted to one spatial dimension ( $1D$, the hyperquantum limit in view
of Herschbach [17,18]). It was just very recently, to the best of our
knowledge, that Hall and Saad have generalized their variational
analysis [1a] and smooth transformation [2] methods, VAM and STM, respectively, to the
D - dimensional case and studied its bound - states. They have also used
direct numerical integration (DNI) for comparison purposes. It is therefore
interesting to carry out systematic studies of the bound - state spectra
generated by this interesting class of singular potentials (1).

On the other hand, results from exactly solvable potentials ( an interesting
field of mathematical physics in itself) are essential ingredients for
the description of realistic physical problems [1-5,19].
The solutions of these can be used in
perturbation and pseudoperturbation theories, or they can be combined with
numerical calculations. Nevertheless, in the simplest case, analytical
calculations can aid numerical studies in areas where numerical techniques
might not be safely controlled. For example, when bound - state wave
functions with arbitrary nodal zeros are required for certain singular
potentials (a next level of complexity), analytical solutions can supply
a basis for numerical calculations. Moreover, in many problems the
Hamiltonian does not contain any physical parameter suitable for a
perturbation expansion treatment. More often, the Hamiltonian contains
physical parameters, but, typically, zeroth - order solutions for special
values of these are not tractable or good starting approximations. One
would therefore resort to variational calculations [1], pseudoperturbation
expansions ( artificial in nature) [5,18-26], etc.

Recently, we have introduced a pseudoperturbative shifted - $l$ ( $l$ is the
angular momentum quantum number) expansion technique ( PSLET) to solve for
nodeless states of Schr\"odinger equation. It simply consists of using
$1/\bar{l}$ as a pseudoperturbation parameter, where $\bar{l}=l-\beta$
and $\beta$ is a suitable shift. The shift $\beta$ is vital for it removes
the poles  that would emerge, at lowest orbital states with
$l$=0, in our proposed expansions below. Our analytical, or often
semianalytical, methodical proposal PSLET has been successfully applied
to quasi - relativistic harmonic oscillator [20], spiked harmonic oscillator
[5], anharmonic oscillators [21], and to the two - dimensional ({\em
flatland}, in view of Godson and L\'opez - Cabrera in [17]) hydrogenic atom
in an arbitrary magnetic field [22].

Encouraged by its satisfactory performance in handling nodeless states,
we generalize PSLET recipe ( in section 2) for states with arbitrary number
of nodal zeros, $k \geq 0$. Moreover, in the underlying "radical" time -
independent radial Schr\"odinger equation, in $\hbar=m=1$ units,\\
\begin{equation}
\left[-\frac{1}{2}\frac{d^{2}}{dq^{2}}+\frac{l(l+1)}{2q^{2}}+V(q)\right]
\Psi_{k,l}(q)=E_{k,l}\Psi_{k,l}(q),
\end{equation}\\
the isomorphism between orbital angular momentum $l$ and  dimensionality
$D$ invites interdimensional degeneracies to obtain [17].  Which, in effect,
allows us to generate the ladder of excited states for any given $k$ and
nonzero $l$ from the $l$=0 result, with that $k$, by the transcription
$D \longrightarrow D+2l$. That is, if $E_{k,l}(D)$ is the eigenvalue in $D$
- dimensions, then\\
\begin{equation}
E_{k,l}(2) \equiv E_{k,l-1}(4) \equiv  \cdots
\equiv E_{k,1}(2l) \equiv E_{k,0}(2l+2)
\end{equation}\\
for even $D$, and\\
\begin{equation}
E_{k,l}(3) \equiv E_{k,l-1}(5)  \equiv \cdots \equiv
E_{k,1}(2l+1) \equiv E_{k,0}(2l+3)
\end{equation}\\
for odd $D$. For more details the reader may refer to ref.s [17,18,27].
We therefore calculate, in section 3, the energies for $D=2$ and $D=3$
spiked harmonic oscillators, for a given number of nodes $k$ and different
values of $l$, and construct part of its $D$ - dimensional bound - state
spectra. We compare our results with those reported by Hall and Saad via
generalized variational analysis VAM, and direct
numerical integration DNI methods [1,2]. Section 4 is devoted for concluding
remarks.

\section{The generalization of PSLET}

With the shifted angular momentum, equation (2) reads\\
\begin{equation}
\left\{-\frac{1}{2}\frac{d^{2}}{dq^{2}}+\frac{\bar{l}^{2}+(2\beta+1)\bar{l}
+\beta(\beta+1)}{2q^{2}}+\frac{\bar{l}^2}{Q}V(q) \right\}
\Psi_{k,l} (q)=E_{k,l}\Psi_{k,l}(q),
\end{equation}\\
where Q is a constant that scales the potential $V(q)$ at large - $l_D$ limit
( the pseudoclassical limit [17]) and is set, for any specific choice of
$l_D$ and $k$, equal to $\bar{l}^2$ at the end of the calculations. Here
$l_D=l+(D-3)/2$, to incorporate the interdimensional degeneracies associated
with the isomorphism between angular momentum and dimensionality $D$. Hence,
$\bar{l} \longrightarrow \bar{l}=l_D - \beta$ through out this paper. Next,
we shift the origin of the coordinate system through
$x=\bar{l}^{1/2}(q-q_{o})/q_{o}$, where $q_o$ is currently an arbitrary
point to be determined below. Expansions about this point
(see Appendix for more details), $x=0$ (i.e. $q=q_o$),
obviously localize the problem at an
arbitrary point $q_o$ and the derivatives, in effect, contain
information not only at $q_o$ but also at any point on $q$-axis, in
accordance with Taylor's theorem. It is then convenient to expand $E_{k,l}$
 as\\
\begin{equation}
E_{k,l}=\sum^{\infty}_{n=-2}E_{k,l}^{(n)}~\bar{l}^{-n}.
\end{equation}\\
Equation (5) thus becomes\\
\begin{equation}
\left[-\frac{1}{2}\frac{d^2}{dx^2} + \sum^{\infty}_{n=0} v^{(n)}
\bar{l}^{-n/2}\right]\Psi_{k,l} (x)=
\left[\sum^{\infty}_{n=1} q_o^2 E_{k,l}^{(n-1)}
\bar{l}^{-n} \right] \Psi_{k,l}(x).
\end{equation}\\

Up to this point, one would conclude that the above procedure is nothing
but an imitation of the eminent shifted large-N expansion (SLNT)
[25,26,28-30]. However, because of the limited capability of SLNT
in handling large-order corrections via the standard Rayleigh-Schr\"odinger
perturbation theory, only low-order corrections have been reported,
sacrificing in effect its preciseness. Therefore, one should seek
for an alternative and proceed by setting the wave functions with any number
of nodes as \\
\begin{equation}
\Psi_{k,l}(x(q)) = F_{k,l}(x)~ exp(U_{k,l}(x)).
\end{equation}\\
In turn, equation (7) readily transforms into the
following Riccati equation:\\
\begin{eqnarray}
&&F_{k,l}(x)\left[-\frac{1}{2}\left( U_{k,l}^{''}(x)+U_{k,l}^{'}(x)
U_{k,l}^{'}(x)\right)
+\sum^{\infty}_{n=0} v^{(n)}(x) \bar{l}^{-n/2} \right. \nonumber\\
&&\left. -\sum^{\infty}_{n=1} q_o^2 E_{k,l}^{(n-1)} \bar{l}^{-n} \right]
-F_{k,l}^{'}(x)U_{k,l}^{'}(x)-\frac{1}{2}F_{k,l}^{''}(x)=0,
\end{eqnarray}\\
where the primes denote derivatives with respect to $x$. It is
evident that this equation admits solution of the form \\
\begin{equation}
U_{k,l}^{'}(x)=\sum^{\infty}_{n=0} U_{k}^{(n)}(x)~~\bar{l}^{-n/2}
+\sum^{\infty}_{n=0} G_{k}^{(n)}(x)~~\bar{l}^{-(n+1)/2},
\end{equation}\\
\begin{equation}
F_{k,l}(x)=x^k +\sum^{\infty}_{n=0}\sum^{k-1}_{p=0}
a_{p,k}^{(n)}~~x^p~~\bar{l}^{-n/2},
\end{equation}\\
where\\
\begin{equation}
U_{k}^{(n)}(x)=\sum^{n+1}_{m=0} D_{m,n,k}~~x^{2m-1} ~~~~;~~~D_{0,n,k}=0,
\end{equation}\\
\begin{equation}
G_{k}^{(n)}(x)=\sum^{n+1}_{m=0} C_{m,n,k}~~x^{2m}.
\end{equation}\\
Substituting equations (10) - (13) into equation (9) implies\\
\begin{eqnarray}
&&F_{k,l}(x)\left[-\frac{1}{2}\sum^{\infty}_{n=0}\left(U_{k}^{(n)^{'}}
\bar{l}^{-n/2}
+ G_{k}^{(n)^{'}} \bar{l}^{-(n+1)/2}\right) \right. \nonumber\\
&-&\left.\frac{1}{2} \sum^{\infty}_{n=0} \sum^{n}_{m=0}
\left( U_{k}^{(m)}U_{k}^{(n-m)} \bar{l}^{-n/2}
+G_{k}^{(m)}G_{k}^{(n-m)} \bar{l}^{-(n+2)/2}
\right. \right.\nonumber\\
&+&\left.\left.2 U_{k}^{(m)}G_{k}^{(n-m)} \bar{l}^{-(n+1)/2}\right)
+\sum^{\infty}_{n=0}v^{(n)} \bar{l}^{-n/2}
-\sum^{\infty}_{n=1} q_o^2 E_{k,l}^{(n-1)} \bar{l}^{-n}\right] \nonumber\\
&-&F_{k,l}^{'}(x)\left[\sum^{\infty}_{n=0}\left(U_{k}^{(n)}\bar{l}^{-n/2}
+ G_{k}^{(n)} \bar{l}^{-(n+1)/2}\right)\right]-\frac{1}{2}F_{k,l}^{''}(x)
=0
\end{eqnarray}\\
The above procedure
obviously reduces to the one described by Mustafa and Odeh [5,20-22], for
$k=0$. Moreover, the solution of equation (14) follows from the uniqueness
of power series representation. Therefore, for a given $k$ we equate the
coefficients of the same powers of $\bar{l}$ and $x$, respectively.
For example, when $k=1$ one obtains\\
\begin{equation}
D_{1,0,1}=-w,~~~ U_{1}^{(0)}(x) =-~w~x,
\end{equation}\\
\begin{equation}
C_{1,0,1}=-\frac{B_{3}}{w},~~~~a_{0,1}^{(1)}=-\frac{C_{0,0,1}}{w},
\end{equation}\\
\begin{equation}
C_{0,0,1}=\frac{1}{w}\left(2C_{1,0,1}+2\beta+1\right),
\end{equation}\\
\begin{equation}
D_{2,2,1}=\frac{1}{w}\left(\frac{C_{1,0,1}^2}{2}-B_{4}\right),
\end{equation}\\
\begin{equation}
D_{1,2,1}=\frac{1}{w}\left(\frac{5}{2}~D_{2,2,1}+C_{0,0,1}~C_{1,0,1}
-\frac{3}{2}(2\beta+1)\right),
\end{equation}\\
\begin{equation}
E_{1,l}^{(0)} = \frac{1}{q_o^2}\left(\frac{\beta(\beta+1)}{2}+
a_{0,1}^{(1)}~C_{1,0,1}-\frac{3~D_{1,2,1}}{2}-\frac{C_{0,0,1}^2}{2}\right),
\end{equation}\\
etc. Here, we reported the nonzero coefficients only and give the
definitions of the related parameters in the Appendix. One can then calculate
the energy eigenvalues and eigenfunctions from the knowledge of
$C_{m,n,k}$, $D_{m,n,k}$, and $a_{p,k}^{(n)}$ in a hierarchical manner.
Nevertheless, the procedure just described is suitable for a
software package such as  MAPLE to determine
the energy eigenvalue and eigenfunction corrections up to any order of the
pseudoperturbation series (6).

Although the energy series, equation (6), could appear
divergent, or, at best, asymptotic for small $\bar{l}$, one can still
calculate the eigenenergies to a very good accuracy by forming the
sophisticated [N,M] Pad\'e approximation [24]\\
\begin{center}
$P_{N}^{M}(1/\bar{l})=(P_0+P_1/\bar{l}+\cdots+P_M/\bar{l}^M)/
(1+q_1/\bar{l}+\cdots+q_N/\bar{l}^N)$
\end{center}
to the energy series (6). The energy series (6) is calculated up to
$E_{k,l}^{(8)}/\bar{l}^8$ by
\begin{equation}
E_{k,l}=\bar{l}^{2}E_{k,l}^{(-2)}+E_{k,l}^{(0)}+\cdots
+E_{k,l}^{(8)}/\bar{l}^8+O(1/\bar{l}^{9}),
\end{equation}\\
and with the $P_{4}^{4}(1/\bar{l})$ Pad\'e approximant it becomes\\
\begin{equation}
E_{k,l}[4,4]=\bar{l}^{2}E_{k,l}^{(-2)}+P_{4}^{4}(1/\bar{l}).
\end{equation}\\
Our recipe is therefore well prescribed.

\section{D - spiked harmonic oscillator spectra}

In this section we consider the spiked harmonic oscillator potential (1)
and illustrate the above mentioned procedure. The substitution of equation
(1) in (45), for $k \geq 0$, implies\\
\begin{equation}
w=\sqrt{\frac{8c_1q_o+bc_2(b-2)q_o^{-(b+1)}}
{2c_1q_o-bc_2q_o^{-(b+1)}}}~~,~~ \beta=-\frac{1}{2}(1+[2k+1]w).
\end{equation}\\
Equation (44), in turn, reads\\
\begin{equation}
l_D+\frac{1}{2}\left(1+[2k+1]\sqrt{\frac{8c_1q_o+bc_2(b-2)q_o^{-(b+1)}}
{2c_1q_o-bc_2q_o^{-(b+1)}}}\right)
=q_o^2 \sqrt{c_1-\frac{bc_2}{2}q_o^{-(b+2)}},
\end{equation}\\
which is explicit in $q_o$. However, in the absence of a closed - form
solution for $q_o$, which is often the case ( hence the notion that PSLET
is often semianalytical), numerical solutions of (24) could resolve this
issue. Once $q_o$ is determined the coefficients $C_{m,n,k}$, $D_{m,n,k}$,
and $a_{p,k}^{(n)}$ are determined in a sequential manner. Hence, the
eigenvalues, equation (21), and eigenfunctions, equations (10)-(13), are
calculated in the same batch for each value of $k$, $D$, $l$, $c_1$, $c_2$,
and $b$.

Table 1 shows PSLET results for the ground - state energies, covering a wide
range of the coupling $c_2$ when $b=2.5$, along with those reported by Hall
and Saad [1a], via a generalized variational analysis and
direct numerical integration  methods. Using the interdimensional
degeneracies, equations (3) and (4), or directly the dimensionality $D$
in $l_D$, we display the energies for $V(q)=(q^2+10/q^{1.9})/2$ in table 2.
Clearly, our results compare excellently with those from direct numerical
integrations. However, it should be noted that in [5] we have calculated
the energy series up to $E_{0,l}^{(4)}/\bar{l}^4$ correction. Therefore,
slight discrepancies obtain between the present results in table 1 and those
reported in table 2 of [5].

Adhering to the implicated wisdom in equations (3) and (4), that the  two - and three - dimensional ( 2D and 3D, respectively) cases are the basic
ingredients of the energy ladder at larger dimensions, we report (in
table 3) the 2D -  and 3D - nodal bound - state energies when the coupling
$c_2=1000$ and $b=0.5, 1,\cdots, 2.5, 3$. The stability of the last three
approximants of the Pad\'e sequence indicate that the results are exact.
For more details on this issue the reader may refer to ref.s [20,24].
Nevertheless, our results $E_{0,0}$ for the 3D - spiked harmonic oscillator
are in exact accord with those from direct numerical integrations [2].
Following the same strategy, we display in table 4 the $k=1$ and 2 nodal
bound - state energies for $V(q)=(q^2+1000/q^{3/2})/2$.
Eventually, the leading term of PSLET, $\bar{l}^2E_{k,l}^{(-2)}$,
turns out to be a good starting approximation. Tables 1,2 and 4 bear
this out.

Moreover, for the spiked harmonic oscillator, with $b=2$, one would
rewrite the effective potential term $(l(l+1)+c_2)/2q^2+q^2/2$ as
$l^{'}(l^{'}+1)/2q^2+q^2/2$ with $l^{'}=-1/2+\sqrt{(l+1/2)^2+c_2}$. For this
particular case, PSLET procedure yields, respectively, $w=2$,
$\beta=-(2k+3/2)$, $\bar{l}=2k+l^{'}+3/2$, $q_o^2=\bar{l}$,
$\bar{l}^2 E_{k,l^{'}}^{(-2)}=2k+l^{'}+3/2$ ( the exact well
known energies),\\
\begin{equation}
E_{k,l^{'}}^{(0)}=E_{k,l^{'}}^{(1)}= \cdots=E_{k,l^{'}}^{(8)}=\cdots
=E_{k,l^{'}}^{(n)}=0,
\end{equation}\\
and when $k=0$, for example,\\
\begin{eqnarray}
U_{0,l^{'}}(x)&=&-\frac{1}{2}\left(y-\frac{y^2}{2}+\frac{y^3}{3}-\frac{y^4}{4} +\frac{
y^5}{5}-\frac{y^6}{6}+\frac{y^7}{7}-\frac{y^8}{8}+\cdots\right)  \nonumber \\
&&+\bar{l}\left(y-\frac{y^2}{2}+\frac{y^3}{3}-\frac{y^4}{4}+\frac{y^5}{5} -
\frac{y^6}{6}+\frac{y^7}{7}-\frac{y^8}{8}+\cdots\right)  \nonumber \\
&&-\bar{l}\frac{y^2}{2}-\bar{l}y,
\end{eqnarray}\\
where $y=x\bar{l}^{-1/2}$. Obviously, the terms in brackets in equation (26)
are the infinite geometric series expansions for $ln(1+y)$. Equation (26)
thus becomes\\
\begin{equation}
U_{0,l^{'}}(x) = ln(1+y)^{-1/2} + ln(1+y)^{\bar{l}} - \bar{l}y - \bar{l}\frac{y^2
}{2}.
\end{equation}\\
Hence Eq.(8) ( with $F_{0,l^{'}}(x)=1$ from (11)) reads\\
\begin{equation}
\Psi_{0,l^{'}} (q) = N_{0,l^{'}}~~q^{l^{'}+1}~~e^{-q^2 /2},
\end{equation}\\
the exact well known solutions [31], where $N_{0,l^{'}}$ are the normalization
constants. Proceeding exactly as above, one could obtain the well known
solutions with $k \geq 1$. However, this already lies far beyond the scope
of our present methodical proposal.

Hall and Saad [1a] have therefore used, indirectly, the transformation of
the angular momentum quantum number and cast the Hamiltonian of the
spiked harmonic oscillator (1) as\\
\begin{equation}
H=-\frac{1}{2}\frac{d^{2}}{dq^{2}}+\frac{l_H(l_H+1)}{2q^{2}}
+\frac{q^2}{2}+\frac{c_2}{2q^b}-\frac{A}{2q^2}.
\end{equation}\\
Where $l_H=-1/2 + \sqrt{(l+1/2)^2+A}$, and A is used as a {\em further
variational refinement} in their generalized variational analysis method.
They found that $A=c_2$ is a {\em good} general estimate for the value of $A$.
Indeed this optimum value of $A$, which reduced substantially the number
of the basis function needed for a given accuracy in [1a], enhances the
convergence and accuracy of approximation methodical recipes. Practically,
it minimizes the effect of the perturbation term $c_2q^{-b}$ over the
harmonic oscillator one (with the irrational quantum number $l^{'}$),
especially for values of $b \longrightarrow  2$. In table 5, the results of
PSLET are obtained using such prescription. They compare excellently with
direct numerical integrations and do not contradict with the upper bounds
from the generalized variational estimates.

\section{Concluding remarks}

We have generalized our pseudoperturbative shifted - $l$ expansion
technique PSLET [5,20-22] for states with arbitrary number of nodal
zeros, $k \geq 0$. Starting with the central force problem,
represented by the radial Schr\"odinger equation, and augmenting the
orbital angular momentum by $l \longrightarrow l_D=l+(D-3)/2$, we have
incorporated interdimensional degeneracies. To test PSLET performance,
we have treated the spiked harmonic oscillator problem in $D$ - dimensions.
and used results from direct numerical integrations and generalized
variational analysis methods [1,2] to compare with. The comparison is readily
satisfactory.

The salient features of the attendant proposal PSLET are in order.

It avoids troublesome questions as those pertaining to the nature
of small parameter expansions, the trend of convergence to the exact
numerical values ( marked in tables 1-3 and 5), the utility in calculating
the eigenvalues and eigenfunctions in one batch to sufficiently higher -
orders ( documented through the solution (28) of (1), with $b=2$), and the
applicability to a wide range of potentials. Provided that the potential
$V(q)$ gives rise to one minimum of $E_{k,l}^{(-2)}$ and an infinite
number of bound - states. Moreover, beyond its promise as being quite
handy ( on the computational and practical methodical sides), it offers
a useful perturbation prescription where the zeroth - order approximation
$\bar{l}^2E_{k,l}^{(-2)}$ inherits a substantial amount of the total energy.

The above has been a very limited review and a number of other useful
approaches such as those presented by Papp [9,32], Bender and Wu [33],etc,
have been left unattended. However, their accomplishments are indeed of
actual novelties.

Finally, the scope of PSLET applicability extends beyond the present
$D$ - dimensional spiked harmonic oscillator model. It could be applied
to angular momentum states of multi - electron atoms [34-36], relativistic
and non - relativistic quark - antiquark models [37], etc.
\newpage

\begin{center}
Appendix
\end{center}

Although some of the following expressions have appeared in previous
articles [5,20-22], we would like to repeat them to make this article self
contained.

Expansions about $x=0$ (i.e.$q=q_o$), yield\\
\begin{equation}
\frac{1}{q^{2}}=\sum^{\infty}_{n=0} (-1)^{n}~ \frac{(n+1)}{q_{o}^{2}}
~ x^{n}~\bar{l}^{-n/2},
\end{equation}\\
\begin{equation}
V(x(q))=\sum^{\infty}_{n=0}\left(\frac{d^{n}V(q_{o})}{dq_{o}^{n}}\right)
\frac{(q_{o}x)^{n}}{n!}~\bar{l}^{-n/2}.
\end{equation}\\
Equation (5) thus becomes\\
\begin{equation}
\left[-\frac{1}{2}\frac{d^{2}}{dx^{2}}+\frac{q_{o}^{2}}{\bar{l}}
\tilde{V}(x(q))\right]
\Psi_{k,l}(x)=\frac{q_{o}^2}{\bar{l}}E_{k,l}\Psi_{k,l}(x),
\end{equation}\\
with\\
\begin{eqnarray}
\frac{q_o^2}{\bar{l}}\tilde{V}(x(q))&=&q_o^2\bar{l}
\left[\frac{1}{2q_o^2}+\frac{V(q_o)}{Q}\right]
+\bar{l}^{1/2}B_1 x+ B_2 x^2+\frac{(2\beta+1)}{2} \nonumber\\
&+&(2\beta+1)\sum^{\infty}_{n=1}(-1)^n \frac{(n+1)}{2}x^n \bar{l}^{-n/2}
+\sum^{\infty}_{n=3}B_n x^n\bar{l}^{-(n-2)/2} \nonumber\\ &+&
\beta(\beta+1)\sum^{\infty}_{n=0}(-1)^n\frac{(n+1)}{2}x^n\bar{l}^{-(n+2)/2},
\end{eqnarray}\\
\begin{equation}
B_n=(-1)^n \frac{(n+1)}{2}
+\left(\frac{d^n V(q_o)}{dq_o^n}\right)\frac{q_o^{n+2}}{n! Q}.
\end{equation}\\
Equation (32), along with (33) and (34), is evidently the one - dimensional
Schr\"odinger equation for a perturbed harmonic oscillator\\
\begin{equation}
\left[-\frac{1}{2}\frac{d^2}{dx^2}+\frac{1}{2}w^2 x^2 +\varepsilon_o
+P(x)\right]X_{k}(x)=\lambda_{k}X_{k}(x),
\end{equation}\\
where $w^2=2B_2$,\\
\begin{equation}
\varepsilon_o =\bar{l}\left[\frac{1}{2}+\frac{q_o^2 V(q_o)}{Q}\right]
+\frac{2\beta+1}{2}+\frac{\beta(\beta+1)}{2\bar{l}},
\end{equation}\\
and $P(x)$ represents the remaining terms in eq.(33) as infinite power
series perturbations to the harmonic oscillator. One would then imply that\\
\begin{eqnarray}
\lambda_{k}&=&\bar{l}\left[\frac{1}{2}+\frac{q_o^2 V(q_o)}{Q}\right]
+\left[\frac{2\beta+1}{2}+(k+\frac{1}{2})w\right]\nonumber\\
&+&\frac{1}{\bar{l}}\left[\frac{\beta(\beta+1)}{2}+\lambda_{k}^{(0)}\right]
+\sum^{\infty}_{n=2}\lambda_{k}^{(n-1)}\bar{l}^{-n},
\end{eqnarray}\\
and\\
\begin{equation}
\lambda_{k} = q_o^2 \sum^{\infty}_{n=-2} E_{k,l}^{(n)}
\bar{l}^{-(n+1)}.
\end{equation}\\
Hence, equations (37) and (38) yield\\
\begin{equation}
E_{k,l}^{(-2)}=\frac{1}{2q_o^2}+\frac{V(q_o)}{Q}
\end{equation}\\
\begin{equation}
E_{k,l}^{(-1)}=\frac{1}{q_o^2}\left[\frac{2\beta+1}{2}
+(k +\frac{1}{2})w\right]
\end{equation}\\
\begin{equation}
E_{k,l}^{(0)}=\frac{1}{q_o^2}\left[ \frac{\beta(\beta+1)}{2}
+\lambda_{k}^{(0)}\right]
\end{equation}\\
\begin{equation}
E_{k,l}^{(n)}=\lambda_{k}^{(n)}/q_o^2  ~~;~~~~n \geq 1.
\end{equation}\\
Where $q_o$ is chosen to minimize $E_{k,l}^{(-2)}$, i. e.\\
\begin{equation}
\frac{dE_{k,l}^{(-2)}}{dq_o}=0~~~~
and~~~~\frac{d^2 E_{k,l}^{(-2)}}{dq_o^2}>0.
\end{equation}\\
Hereby, $V(q)$ is assumed to be well behaved so that $E_{k,l}^{(-2)}$ has
a minimum $q_o$ and there are well - defined bound - states.
Equation (43) in turn gives, with $\bar{l}=\sqrt{Q}$,\\
\begin{equation}
l_D-\beta=\sqrt{q_{o}^{3}V^{'}(q_{o})}.
\end{equation}\\
Consequently, the second term in Eq.(33) vanishes and the first term adds
a constant to the energy eigenvalues. It should be noted that the energy term
$\bar{l}^2E_{k,l}^{(-2)}$  corresponds roughly to the energy of a classical
particle with angular momentum $L_z$=$\bar{l}$  executing circular motion of
radius $q_o$ in the potential $V(q_o)$. It thus identifies the
zeroth - order approximation, to all eigenvalues, as a classical
approximation and the higher - order corrections as quantum fluctuations
around the minimum $q_o$, organized in inverse powers of $\bar{l}$.
The next correction to the energy series, $\bar{l}E_{k,l}^{(-1)}$,
consists of a constant term and the exact eigenvalues of the harmonic
oscillator $w^2x^2/2$.The shifting parameter
$\beta$ is determined by choosing
$\bar{l}E_{k,l}^{(-1)}$=0. This choice is physically motivated. In addition
to its vital role in removing the singularity at $l=0$, it also requires
the agreements between PSLET eigenvalues and eigenfunctions with
the exact well known ones
for the harmonic oscillator and Coulomb potentials.  Hence\\
\begin{equation}
\beta=-\left[\frac{1}{2}+(k+\frac{1}{2})w\right],
\end{equation}\\
where $w=\sqrt{3+q_o V^{''}(q_o)/V^{'}(q_o)}$, and primes of $V(q_o)$ denote
derivatives with respect to $q_o$. Then equation (33) reduces to\\
\begin{equation}
\frac{q_o^2}{\bar{l}}\tilde{V}(x(q))=
q_o^2\bar{l}\left[\frac{1}{2q_o^2}+\frac{V(q_o)}{Q}\right]+
\sum^{\infty}_{n=0} v^{(n)}(x) \bar{l}^{-n/2},
\end{equation}\\
where\\
\begin{equation}
v^{(0)}(x)=B_2 x^2 + \frac{2\beta+1}{2},
\end{equation}\\
\begin{equation}
v^{(1)}(x)=-(2\beta+1) x + B_3 x^3,
\end{equation}\\
and for $n \geq 2$\\
\begin{eqnarray}
v^{(n)}(x)&=&B_{n+2}~ x^{n+2}+(-1)^n~ (2\beta+1)~ \frac{(n+1)}{2}~ x^n
\nonumber\\
&+&(-1)^{n}~ \frac{\beta(\beta+1)}{2}~ (n-1)~ x^{(n-2)}.
\end{eqnarray}\\

\newpage