text:
\begin{document}

\title{Divisors and specializations of Lucas polynomials}
\author[1]{Tewodros Amdeberhan}
\author[2]{Mahir Bilen Can}
\author[3]{Melanie Jensen}
\affil[1]{{\small Tulane University, New Orleans; tamdeber@tulane.edu}}
\affil[2]{{\small Tulane University, New Orleans; mcan@tulane.edu}}
\affil[3]{{\small Tulane University, New Orleans; mjensen1@tulane.edu}}
\normalsize

\maketitle

\begin{abstract}
Three-term recurrences have infused stupendous amount of research
in a broad spectrum of the sciences, such as orthogonal polynomials (in special functions)
and lattice paths (in enumerative combinatorics).
Among these are the Lucas polynomials,
which have seen a recent true revival. In this paper one of the themes of investigation
is the specialization to the Pell and Delannoy numbers.
The underpinning motivation comprises primarily of divisibility and symmetry.
One of the most remarkable findings is a structural decomposition
of the Lucas polynomials into what we term as flat and sharp analogs.
\end{abstract}

\section{Introduction}

\begin{comment}

In this paper, we focus on two themes on Lucas polynomials, the first of which has a rather ancient flavor.
In mathematics, often, the simplest ideas carry most importance, and hence they live longest.
Among all combinatorial sequences, the Pell sequence seem to be particularly
resilient to the traumas of human memory, including the great fire of the library in Alexanderia.
Defined by the simple recurrence
\begin{align}\label{Pell recurrence}
P_n = 2P_{n-1} + P_{n-2}\ \text{ for } n\geq 2,
\end{align}
with respect to initial conditions $P_0=0$, $P_1=1$, Pell numbers appear in
ancient texts (for example, in Shulba Sutra, approximately 800 BC).
We speculate that, some simple facts about Pell numbers, such as their first few values
$(0, 1, 2, 5, 12, 29, 70, 169)$, as well as their remainders modulo 3
\begin{align}\label{A:periods}
(P_0,P_1,P_2,P_3,P_4,P_5,P_6,P_7) \equiv_3 (0,1,2,2,0,2,1,1)
\end{align}
were known to Sumerians.
It is hard not to appreciate (\ref{A:periods}), since the sequence $( P_n \mod 3 : n\geq 0 )$
is periodic, of period 8.
This fact is easily proven by inducting on $n$, and by using the recurrence from (\ref{Pell recurrence}).

\end{comment}

In this paper, we focus on two themes on Lucas polynomials, the first of which has a rather ancient flavor.
In mathematics, often, the simplest ideas carry most importance, and hence they live longest.
Among all combinatorial sequences, the (misattributed) Pell sequence seem to be particularly
resilient. Defined by the simple recurrence
\begin{align}\label{Pell recurrence}
P_n = 2P_{n-1} + P_{n-2}\ \text{ for } n\geq 2,
\end{align}
with respect to initial conditions $P_0=0$, $P_1=1$, Pell numbers appear in
ancient texts (for example, in Shulba Sutra, approximately 800 BC).
The first eight values of $P_n$ are given by $(0, 1, 2, 5, 12, 29, 70, 169)$, and the remainders modulo 3 are
\begin{align}\label{A:periods}
(P_0,P_1,P_2,P_3,P_4,P_5,P_6,P_7) \equiv_3 (0,1,2,2,0,2,1,1).
\end{align}
It is hard not to appreciate (\ref{A:periods}), since the sequence $( P_n \mod 3 : n\geq 0 )$
is periodic, of period 8.
This fact is easily proven by inducting on $n$, and by using the recurrence from (\ref{Pell recurrence}).

Let $m,n$ be two positive integers, and let $p$ be a prime number.
By the Fundamental Theorem of Arithmetic, there exists a unique expression of the form
$m/n= p_1^{f_1}\cdots p_r^{f_r}$ for some integers $f_i \in \Z$, and prime numbers $p_i$.
The $p$-adic valuation of $m/n$ is then defined by
$$
\nu_p \left(\frac{m}{n} \right) =
\begin{cases}
f_i & \text{ if } p= p_i, \\
0 & \text{ otherwise.}
\end{cases}
$$
Although the ancients did not document their $p$-adic arithmetic,
it is fair to assume that the tools for proving the following interesting consequence of the 8-periodicity
was at their disposal: the 3-adic valuation of the Pell sequence is of the form
\begin{align}\label{A:3-adic}
\nu_3 (P_n ) =
\begin{cases}
\nu_3(3k)& \text{ if } n=4k, \\
0  & \text{ otherwise. }
\end{cases}
\end{align}
Indeed, the case $4\nmid n$ is evident from the periodicity and (\ref{A:periods}).
For the other cases, we use the following well-known consequence
\begin{equation}\label{E:Pell relation}
P_{m+n}=P_mP_{n+1}+P_{m-1}P_n
\end{equation}
of the recurrence (\ref{Pell recurrence}).

Suppose $n=4(3k+1)$. From (\ref{E:Pell relation}), $P_{12k+4}=P_{12k}P_5+P_{12k-1}P_4$.
By induction, $\nu_3(P_{4(3k)})=2+\nu_3(k), \nu_3(P_{12k-1})=0$.
By direct calculation $\nu_3(P_5)=0, \nu_3(P_4)=1$. So,
$$
\nu_3(P_n)=1=\nu_3(4(3k+1)).
$$
Suppose $n=4(3k+2)$. From (\ref{E:Pell relation}), $P_{12k+8}=P_{12k}P_9+P_{12k-1}P_8$.
By induction, $\nu_3(P_{4(3k)})=2+\nu_3(k), \nu_3(P_{12k-1})=0$.
By direct calculation $\nu_3(P_9)=0, \nu_3(P_8)=1$. So,
$$
\nu_3(P_n)=1=\nu_3(4(3k+2)).
$$

\noindent
Suppose $n=4(3k+3)$. Once more, apply (\ref{E:Pell relation}) repeatedly to obtain
$$
\begin{aligned}
P_{12k+12}
&=P_{8k+8}P_{4k+5}+P_{8k+7}P_{4k+4} \\
&=(P_{4k+4}P_{4k+5}+P_{4k+3}P_{4k+4})P_{4k+5}+P_{8k+7}P_{4k+4} \\
&=P_{4k+4}[(P_{4k+5}+P_{4k+3})P_{4k+5}+P_{8k+7}] \\
&=P_{4k+4}[(P_{4k+5}+P_{4k+3})P_{4k+5}+P_{4k+3}P_{4k+5}+P_{4k+2}P_{4k+4}] \\
&=P_{4k+4}[2(P_{4k+4}+P_{4k+3})P_{4k+5}+P_{4k+3}P_{4k+5}+P_{4k+2}P_{4k+4}] \\
&=P_{4k+4}[(2P_{4k+5}+P_{4k+2})P_{4k+4}+3P_{4k+3}P_{4k+5}].
\end{aligned}
$$
Since $\nu_3(3P_{4k+3}P_{4k+5})=1, \nu_3(P_{4k+4})=1+\nu_3(k+1)$ and $3\mid (2P_{4k+5}+P_{4k+2})$,
it follows that the terms in $[(2P_{4k+5}+P_{4k+2})P_{4k+4}+3P_{4k+3}P_{4k+5}]$ are divisible by {\em exactly} $3$.
Combining these facts,
$$
\nu_3(P_n)=\nu_3(P_{4k+4})+1=\nu_3(3(k+1))+1=\nu_3(4(3k+3)).
$$
The proof of (\ref{A:3-adic}) is complete.

We denote by $\N$ the set of all non-negative integers, and by $\PP$
the set of positive integers.
\begin{Corollary}\label{C:Motivating}
Given $k\in \PP$, let $n=4k$. Then $P_n^2$ does not divide $P_{n^2}$.
\end{Corollary}
\begin{proof}
A simple use of~(\ref{A:3-adic}) leads to $\nu_3(P_{n^2}) = 1+ 2 \nu_3 (k)
< \nu (P_n^2)= 2+ 2\nu_3(k)$.
\end{proof}
The hypothesis of Corollary~\ref{C:Motivating} is restrictive in the sense that $n$ is assumed to be
a multiple of 4. Our effort to remove the restriction has led us to consider the same question in
a more general context, for a family of polynomials $L_n=L_n(s,t)\in \N[s,t]$, known as
{\em Lucas polynomials},\footnote{In \cite{SS1}, $L_n$ is denoted by $\{ n \}$.}
defined by
$$
L_n = s L_{n-1} + t L_{n-2},\ \text{ subject to the initial conditions }\ L_1=1,L_0=0.
$$
Obviously, when $s=2$, $t=1$ we recover Pell numbers. At the same time,
Lucas polynomials have many other interesting specializations:
\begin{enumerate}
\item $L_n (1,1)= f_n$, $n$-th Fibonacci number;
\item $L_n(2,-1) = n$, for all $n\geq 0$;
\item $L_n(s,0) = s^{n-1}$, for all $n\geq 1$;
\item $L_{2n}(0,t) =0$, and $L_{2n+1}(0,t)=t^n$, for all $n\geq 0$;
\item $L_n(q+1,-q) = 1+ q+\cdots +q^{n-1}$, the standard $q$-analog of $n$.
\end{enumerate}
The main result that motivated our paper is the following truly remarkable multiplicity-free property
of Lucas polynomials:
\begin{Theorem}
Let $d\neq 1$ be a divisor of $n\in \PP$. Then $L_d^2$ does not divide $L_n$.
\end{Theorem}
\noindent
Note that, by evaluating $L_n$ at $s=2,t=1$, we obtain Corollary~\ref{C:Motivating} without any
restriction on $n$.

From an algebraic point of view, ``binomial coefficients'' are the special values of the
$\Q$-valued function
\begin{align}\label{A:in rational}
{x_n \choose x_k} =
\frac{x_n x_{n-1}\cdots x_{n-k+1}}{x_{k} x_{k-1}\cdots x_2 x_1},\ (\text{when } 1 \leq k \leq n)
\end{align}
defined on a sequence $(x_i)_{i\in \PP}$ of non-negative integers $x_i$.
For an arbitrary integer sequence, the binomials in~(\ref{A:in rational})
need not be integral. However, it follows from well-known combinatorial reasons
that for the sequence $x_i = i$, for all $i\in \N$, the binomial coefficients are integers.
When $x_n$ is the $n$-th Fibonacci number, the associated binomial-like
coefficients, customarily called {\em fibonomials}, are integers as well.

In general, to understand the nature of integer sequences, it is often helpful to study them
by introducing extra parameters. For Fibonacci numbers there are many polynomial generalizations,
and the family of Lucas polynomials is one of them.
In analogy, the Lucas polynomial analog of the fibonomials
are defined by
$$
{L_n \choose L_k} := \frac{ L_n L_{n-1} \cdots L_{n-k+1}}{ L_k L_{k-1} \cdots L_1}.
$$
The tapestry
\begin{align}\label{SS1 recurrence}
{ L_{m + n} \choose L_m } = L_{ n +1} { L_{m +n -1} \choose L_{m-1} } + t L_{ m-1} { L_{m+n-1} \choose L_{n-1} },
\end{align}
which is a consequence of the definitions, shows that ${ L_{m+n} \choose L_m }$
are indeed polynomials in $\N[s,t]$.
Sagan and Savage in~\cite{SS1} call these expressions
{\em lucanomial coefficients},\footnote{In \cite{SS1}, ${L_n \choose L_k}$ is denoted by ${ n \brace k}$.}
and they furnish a combinatorial interpretation for them.

One of our goals in this paper is to better understand
these polynomials by analyzing their factorizations. To this end, suppose $n= p_1^{e_1} \cdots p_r^{e_r}$
is the prime factorization of $n$.
We define the {\em $n$-th flat Lucas polynomial} to be the product
\begin{align}\label{A:flat Lucas}
L_n^\flat = L_{p_1} L_{p_2} \cdots L_{p_r},
\end{align}
and the {\em $n$-th sharp Lucas polynomial} to be
\begin{align}\label{A:sharp Lucas}
L_n^\sharp = \frac{L_n}{L_n^\flat}.
\end{align}
Obviously, a flat Lucas polynomial is a polynomial. Less obvious is to show that
a sharp Lucas polynomial is indeed a polynomial (in $s$ and $t$).
We prove this fact in Corollary~\ref{C:divisible}.

We define {\em flat} and {\em sharp} factorials in a conventional manner, as follows:
$$
L_n^\flat ! = L_n^\flat L_{n-1}^\flat \cdots L_1^\flat\  \text{ and }\ L_n^\sharp !
= L_n^\sharp L_{n-1}^\sharp \cdots L_1^\sharp.
$$
Accordingly, let us introduce
$$
{ L_n \choose L_k }^\flat = \frac{ L_n^\flat !} {L_{n-k}^\flat ! \, L_k^\flat ! }
\ \text{ and } \ { L_n \choose L_k }^\sharp = \frac{ L_n^\sharp !} {L_{n-k}^\sharp ! \, L_k^\sharp ! },
$$
and call ${ L_n \choose L_k }^\flat $ and ${ L_n \choose L_k }^\sharp$, respectively,
{\em flat} and {\em sharp} lucanomial coefficients.
For all $0 \leq k \leq n $, we observe the following ``flat and sharp'' decomposition of lucanomials:
$$
{ L_n \choose L_ k } = { L_n \choose L_k }^\flat { L_n \choose L_k }^\sharp.
$$
What is really intriguing is that
\begin{Theorem}
Both the flat and sharp lucanomials are polynomials in $\N[s,t]$.
\end{Theorem}
While the proof of polynomiality of ${ L_n \choose L_k }^\flat $ follows from a much more general
fact about polynomials, when specialized to integral values of $s$ and $t$, it provided us with the following
challenge.

Let $s$ and $t$ be two fixed integers. In this case, we denote the numerical sequence
$(L_n^\flat(s,t))_{n\in \PP}$ by $(\text{ev}(L_n^\flat))_{n\in \PP}$ in order to distinguish
from the polynomials $L_n^\flat$.
Empirical evidence suggests, for a prime number $p$, that there exists a constant
$\theta=\theta_{s,t}(p) \in \N$ such that
$$
\nu_p( \text{ev}(L_n^\flat) !)=\left\lfloor \frac{n}{\theta} \right\rfloor.
$$
We do not pursue this question here, however the interested reader might do so.
Note that when $s=2$, $t=-1$, the number $\text{ev}(L_n^\flat)$ is nothing but $n^\flat$,
the product of all prime numbers dividing $n$.
In this case, $\theta_{2,-1}(p)=p$, and hence
$\nu_p( n^\flat ! ) = \left\lfloor \frac{n}{p} \right\rfloor$.

\vspace{.5cm}
\noindent
\textbf{Question:} Does there exist an explicit expression for $\theta_{s,t}(p)$ ?
\vspace{.5cm}

The second theme of our paper is on certain symmetry,
which is lacking from Lucas polynomials.
The specialization of $L_n$ at $s=x+1$, $t=x$ (denoted here by $D_n$) has a
happy ending in the sense that
\begin{Theorem}
For all $0\leq k \leq n$, the delannomial coefficient
$$
{ D_n \choose D_k } = \frac{ D_n D_{n-1}\cdots D_{n-k+1}}{ D_k \cdots D_1}.
$$
is symmetric and unimodal in the variable $x$.
\end{Theorem}
\begin{Remark}
When $x=1$, the numbers $D_n$ evaluate to Pell numbers, which were our original motivation
for the present work.
\end{Remark}
Wishing for more, we apply divided-difference calculus to Lucas polynomials
and obtain various interesting corollaries, one of which we mention here.
Let $\partial_{s,t}: \N [s,t] \rightarrow \N[s,t]$ denote the operator
$\partial_{s,t} (F(s,t))= (F(s,t)-F(t,s))/(s-t)$.
Let $\alpha\in\mathbb{N}$ and define {\em modified Lucas polynomials}
by
$L_0(s,t:\alpha)=L_1(s,t:\alpha)=\alpha$. For $n\geq2$, define
$$
L_n(s,t:\alpha)=sL_{n-1}(s,t:\alpha)+tL_{n-2}(s,t:\alpha).
$$
Let $S_n(s,t:\alpha)$  denote the divided-difference polynomial $\partial_{s,t}L_n(s,t:\alpha)$.
\begin{Theorem} The following hold true:
\begin{enumerate}
\item[(i)] $S_n(s,t:\alpha)=\alpha S_n(s,t:1)$ for all $\alpha\in\mathbb{N}$;

\item[(ii)] $(s+t-1)$ divides $S_n(s,t:\alpha)$ for all $n\in\mathbb{N}$;

\item[(iii)] $\frac{S_n(s,t:\alpha)}{s+t-1}$ has non-negative integral coefficients, only.
\end{enumerate}
\end{Theorem}

An important connection between multiplicative arithmetic functions and
symmetric polynomials, which we were not aware of at the time of writing this paper
is pointed out to us by an anonymous referee.
In the articles \cite{MacHenry00,MacHenry05,MacHenry12,MacHenry13}, MacHenry and et al
develop the idea that the convolution algebra of multiplicative arithmetic functions is representable by the evaluations of
certain Schur polynomials. It would be interesting to investigate our flat and sharp Lucanomials in the
context of arithmetic functions in relation with symmetric functions.

We conclude our introduction with an observation on further
potential interpretation of the Lucas polynomials in the context of representation theory.
We plan to pursue this in the future, so we keep it brief in here.

\noindent

Let $q$ be a variable and $\mb{K}$ denote a field of characteristic zero.
Consider the polynomial ring $\mc{P}=\mb{K}[q][x_1,\dots,x_n]$ in $n$ variables
over the ring $\mb{K}[q]$.
If  $\sigma_i : \mc{P} \rightarrow \mc{P}$, $1\leq i<n$, denotes the $\mb{K}[q]$-linear operator
interchanging $x_i$ with $x_{i+1}$, define the operators on the ring $\mc{P}$ by
$$
T_i=(q-1)\left[\frac{x_i-x_{i+1}\sigma_i}{x_i-x_{i+1}}\right]+\sigma_i \qquad (1\leq i<n).
$$
Then the $T_i$'s generate a faithful representation of a particular deformation $\mc{H}_n$ of
the group ring $\mb{K}[\mf{S}_n]$ of the symmetric group $\mf{S}_n$. In fact, it is isomorphic
to a specialization of the Iwahori-Hecke algebra of $\mf{S}_n$.

Let $\rho_{(n-1,1)}$ denote the irreducible  representation of $\mc{H}_n$ on
the space $V$ of linear polynomials without constant terms modulo $x_1+\cdots +x_n = 0$,
having the polynomials $\{x_{n-1}+\cdots+x_1,\dots,x_2+x_1,x_1\}$ as a basis.
Consider the following element of $\mc{H}_n$:
$$
H=\sum_{i=1}^{n-1}(T_i-q).
$$

If $\rho_{(n-1,1)}(H)$ is the image of $H$ under the representation $\rho_{(n-1,1)}$
with respect to the above basis, then the matrix form of the image is
$\rho_{(n-1,1)}(H)=M_{n-1}(q)-(1+q)I_{n-1}$, where $I_{n-1}$ is the identity matrix,
and $M_n(q)$ is the tri-diagonal matrix (with super-diagonal all $q$'s, diagonal all $0$'s,
sub-diagonal all $1$'s, and everything else $0$).
For example,

\[
   \rho_{(4,1)}(H)=\left[
   {\begin{array}{cccc}
   -(1+q) & q & 0 & 0  \\ 1 & -(1+q) & q & 0 \\ 0 & 1 & -(1+q) & q \\ 0 & 0 & 1 & -(1+q)
  \end{array} }
  \right].
\]

Furthermore, the characteristic polynomial of $\rho_{(n-1,1)}(H)$ takes the form
$Ch_{n-1}(x,q)=\det[(x+1+q)I_{n-1}-M_{n-1}(q)]$. If we replace $q=t$ and $s=x+1+q$,
then $Ch_{n-1}(s,t)=\det[sI_{n-1}-M_{n-1}(t)]$. These determinants are easy to compute recursively by
$$
Ch_n=sCh_{n-1}+tCh_{n-2}.
$$
Comparing initial conditions reveals a surprising connection: $Ch_{n-1}(s,t)=L_n(s,t)$, the Lucas polynomials!

\newpage

\section{Preliminaries}

A closely related family of polynomials, defined by the same recurrence
$K_n = s K_{n-1} + t K_{n-2}$ with respect to the initial conditions $K_0=2,K_1=s$
is called the family of {\em circular Lucas polynomials}.\footnote{In \cite{SS1}, $K_n$ is denoted by $\langle n \rangle$.}
The ordinary and circular Lucas polynomials are interwoven by the identity:
\begin{equation} \label{mn}
2L_{m + n} = K_n L_m + K_mL_n \ \text{ for all } m,n\in \N.
\end{equation}
Table~\ref{List} gives a short list of $K_n$'s and $L_n$'s for small $n$.
\begin{table}[htdp]
\begin{center}
\begin{tabular}{l|l}
Lucas polynomials& Circular Lucas Polynomials\\
\hline
$L_0 =0$ & $K_0 =2$ \\
$L_1 =1$ & $K_1 =s$ \\
$L_2 =s$ & $K_2 =s^2+2t$ \\
$L_3 =s^2+t$ & $K_3 =s^3+3st$ \\
$L_4 =s^3+2st$ & $K_4 =s^4+4s^2t+2t^2$ \\
$L_5 =s^4+3s^2t+t^2$ & $K_5 =s^5+5s^3t+5st^2$ \\
$L_6 =s^5+4s^3t+3st^2$ & $K_6 =s^6+6s^4t+9s^2t^2+2t^3$ \\
\end{tabular}
\end{center}
\caption{A list of Lucas and circular Lucas polynomials}
\label{List}
\end{table}
Due to their recursive nature, the polynomials $K_n$ and $L_n$, as well as
$L_n \choose L_k$ have nice combinatorial interpretations:
\begin{enumerate}
\item For all $n\geq 1$,
\begin{equation*}
K_n = \sum_{T \in \mathcal{C}_{n}}w(T),
\end{equation*}
where $w(T) = s^{m}t^{d}$ such that $m$ is the number of monominos
and $d$ is the number of dominos and
$\mathcal{C}_{n}$ is the set of all circular tilings of a
$1\times n$ rectangle with disjoint dominos and monominos.

\item For all $n\geq 1$,
\begin{equation}
L_n= \sum_{T \in \mathcal{L}_{n-1}}w(T)
\end{equation}
where $w(T) = s^{m}t^{d}$ such that $m$ is the number of monominos
and $d$ is the number of dominos and
$\mathcal{L}_{n-1}$ is the set of all linear tilings of a $1\times (n-1)$
rectangle with disjoint dominos and monominos.
\item
For a partition $\lambda$, let $\mc{L}_\lambda$ denote the set of all possible linear
tilings of the rows of the Young diagram of $\lambda$, and for $\lambda\subseteq m\times n$,
let $\lambda^*$ denote the the complimentary Young diagram of $\lambda$ in $m \times n$.
Also, the let $\mc{L}'_{\lambda}$ denote the set of all linear tilings of the rows of $\lambda$
that do not start with a monomino.
Finally, the weight $w(T)$ of an element $T=(T_1,T_2) \in \mc{L}_\lambda \times \mc{L}_\mu$
is defined as the product of the weights of the rows of $T_1$ and $T_2$.
It is shown in [Theorem 3,~\cite{SS1}] that
if $m$ and $n$ are two positive integers, then
\begin{align}\label{L:SS1 Theorem 3}
{L_{m+n} \choose L_n } = \sum_{\lambda \subseteq m\times n } \sum_{T\in \mc{L}_\lambda \times \mc{L}'_{\lambda^*}} w(T).
\end{align}
\end{enumerate}

\section{Prime Divisors of Lucas Polynomials}

\begin{Proposition}\label{neven}
Let $N$ be a positive integer. Then $N$ is even if and only if
$L_2$ divides $L_N$. Moreover,
\begin{equation} \label{ctol}
\frac{L_{2N}}{L_N} = K_N \text{ for any } N \geq 1.
\end{equation}
\end{Proposition}

\begin{proof}
Equation~(\ref{ctol}) is immediate from~(\ref{mn}).
When $N$ is even, the linear tiling corresponding to $L_N$
has length $N-1$, which is odd. Thus, each linear tiling must
contain at least one monomino.
The converse statement is easy to show by induction
and the recurrence for $L_N$.

\end{proof}

\begin{Corollary}\label{C:even or odd}

Let $N = 2^r n$ for some positive integers $r,n$. Then
\begin{equation*}
L_N = L_n \prod_{i = 1}^r K_{\frac{N}{2^i}}.
\end{equation*}
In particular, when
$ N = 2^r$ with $r \geq 2$, we have $L_N=  \prod_{i = 1}^r K_{ \frac{N}{2^i}}$.

\end{Corollary}

\begin{proof}
This follows from a repeated use of Proposition~ \ref{neven}.
\end{proof}

\vspace{.1cm}

\begin{Example}
When $n = 6$:
\begin{align*}
\frac{L_6}{L_3} & = \frac{s^{5} + 4s^{3}t + 3st^{2}} {s^2+t}\\
& = \frac{(s^3+3st)(s^2+t)}{s^2+t}\\
& = K_3
\end{align*}
\end{Example}

\begin{Theorem}\label{T:divisible}
Let $N$ be a positive integer. Then
\begin{enumerate}
\item[(i)] If $a \mid N$, then $L_a \mid L_N$. More precisely,
\begin{equation}\label{E:division}
\frac{L_N}{L_a} =  \sum_{i=1}^b \frac{ K_{N-ia }  K_a^{i-1}}{2^i}.
\end{equation}
\item[(ii)] If $L_a \mid L_N$, then $a \mid N$.

\end{enumerate}
\end{Theorem}

\begin{proof}

To prove $(i)$, it suffices to prove the identity~(\ref{E:division}).
If $a \cdot b = N$, we write
\begin{align}
L_N &= L_{a + (N-a)} \notag \\
& =   \frac{ K_{ N-a} }{2} L_a + \frac{ K_a}{2} L_{N-a}. \label{SS2}
\end{align}
Since $N-ia = N-(i+1)a + a$ for any $i=1,\dots, b$,
we repeatedly use~(\ref{mn}) in (\ref{SS2}) to get:
\begin{align}
L_N &=  \sum_{i=1}^b \frac{ K_{N-ia} }{2^i} L_a K_a^{i-1}.
\end{align}

For part $(ii)$, we already know from Proposition~\ref{neven} that
our claim is true when $a=2$, so we assume that $a>2$.

Observe that $L_N$ at ${s=t=1}$ is the $N$-th Fibonacci number $f_N$.
Thus, if $L_a$ divides $L_N$, then $a$-th Fibonacci number $f_a$ divides $f_N$.
On the other hand, it is well known that, for $n >2 $, $f_n \mid f_N$ if and only if
$n \mid N$ (see~\cite{BH}). Hence, the proof is complete.

\end{proof}

\begin{Example}
$$
L_6= s^{5} + 4s^{3}t + 3st^{2} = L_2 L_3 (s^2+3t).
$$
\end{Example}

\begin{Corollary}\label{C:divisible}
Let $N$ be a positive integer with prime factorization
$N= p_1^{e_1} \cdots p_r^{e_r}$, where $e_1,\dots, e_r$ are some positive integers. Then
$L_N$ is divisible by $\prod_{i=1}^rL_{ p_i }$.
\end{Corollary}

\begin{proof}
By Theorem~\ref{T:divisible} and induction, we re-write $L_N$
in the form $L_N = L_{p_1} \cdots L_{p_{r-1}} p(s,t)$
for some polynomial $p(s,t)$.

Now, if a prime factor of the polynomial $L_{ p_r}$ divides any
of $L_{p_1},L_{p_2},\dots. L_{ p_{r-1}}$, then a prime factor of the $p_r$-th
Fibonacci number divides one of $f_{p_1},\dots, f_{p_{r-1}}$.
However, it is well known that Fibonacci numbers that have a prime index
do not share any common divisor greater than 1, since ~\cite{R}
\begin{align}\label{fibonacci common divisors}
\text{gcd} (f_n, f_m) = f_{\text{gcd}}(n,m).
\end{align}
Therefore, $L_{p_{r}}$ divides $p(s,t)$, and hence, the proof is complete.
\end{proof}

Although $L_2$ divides $L_8$, it is not true that higher powers of $L_2$
divide $L_8$:
$$
\frac{ L_8 } { L_2^2 }  = \frac{ (s^2 + 2t) (s^4 + 4s^2 t + 2t^2)}{ s}.
$$
More generally, in our next result we are going to show that $L_N$
is not divisible by the square of any of its divisors.

\newpage

\begin{Theorem}\label{T:p^2 does not divide}
Let $p\neq 1$ be a (not necessarily prime) divisor of $N\in \PP$.
Then $L_{p}^2$ does not divide $L_N$.
\end{Theorem}

\begin{proof}
Let $n$ be such that $N=np$. We claim that
\begin{align}\label{CLAIM}
L_N \equiv n t^{n-1} L_{ p-1}^{n-1} \mod L_p^2.
\end{align}
We show this by proving that $L_N/L_p \equiv n t^{n-1} L_{ p-1}^{n-1} \mod L_p$.
Obviously, if $n=1$, then there is nothing to prove. To use induction, assume that
our claim is true for $n$.
After some cancellations, equation (\ref{SS1 recurrence}) implies that
\begin{align}\label{basic basic}
L_{ a+b } = L_a L_{ b+1} + t L_{a-1} L_{ b} \text{ for all } a,b\geq 0.
\end{align}
Replacing $a$ by $np$ and $b$ by $p$ in (\ref{basic basic}), we have
$L_{ np+p } = L_{ np } L_{ p+1 } + t L_{np-1} L_{ p}$.
Combining this with the defining recurrence $L_p= s L_{ p-1} + t L_{p-2}$,
induction assumption and one more application of (\ref{basic basic}), we get:
\begin{align*}
\frac{ L_{ (n+1)p } }{ L_p} &\equiv \frac{ L_{ np } }{L_p} L_{ p+1 } + t L_{np-1} \mod L_p\\
&\equiv n t^{n-1} L_{ p-1}^{n-1} \left( s L_p+ t L_{p-1} \right) + t L_{np-1} \mod L_p \\
&\equiv n t^{n} L_{ p-1}^{n}  + t L_{np-1} \mod L_p.
\end{align*}
Thus, it remains to show that $L_{np-1} \equiv t^{n-1} L_{p-1}^n \mod L_p$.
We use induction on $n$ once more. If $n=1$, there is nothing to prove.
Assuming validity for $n$ and using (\ref{basic basic}) once again, we see that
$$
L_{ np + p -1 } = L_{np}L_{p}+tL_{np-1}L_{p-1} \equiv t^{n} L_{ p-1 }^n \mod L_p.
$$
Hence, we have our claim proven.

Since $L_{p-1}$ is not divisible by $L_p$ as $p$ and $p-1$ are relatively prime,
we see that the right hand side of (\ref{CLAIM}) is not zero, hence $L_N$ is not
divisible by $L_{ p }^2$.

\end{proof}

\section{Flat and Sharp Decomposition}

\subsection{Flat and Sharp Lucas polynomials}

We know from Corollary~\ref{C:divisible} that the sharp Lucas polynomials are
indeed polynomials. Due to prime involvement, finding a combinatorial interpretation
for sharp polynomials is a challenging problem. Equivalently difficult is the problem of describing
all monomials of a sharp (or of a flat) polynomial.
Note that, if $n$ itself is a prime number, then $L_n^\sharp$ is trivial ($=1$).
More generally, suppose $n=p_1^{e_1}\cdots p_r^{e_r}$ is the prime decomposition of $n$.
It is easy to see from the recursive definition of $L_n$ that $L_n$ is monic in $s$
with degree $n-1$ (for $n\geq 1$).
Therefore, the $s$-degree of $L_n^\sharp$ is equal to
$$
\deg_s L_n^\sharp= n-1 - \sum_{i=1}^r (p_i-1) = n- \sum_{i=1}^r p_i + r - 1.
$$
For the $t$-degree, we have
$$
\deg_t L_n^\sharp = \left\lfloor \frac{n-1}{2} \right\rfloor  - \sum_{i=1}^r \left\lfloor \frac{p_i-1}{2} \right\rfloor.
$$

When $N\in \PP$ is a power of 2, $L_N^\sharp$ reveals itself rather explicitly.
Indeed, we have a precise analogue of Corollary~\ref{C:even or odd}:
suppose $N = 2^r n$ for some positive integers $r,n$. Then
\begin{equation*}
L_N^\sharp= \frac{ L_n^\sharp }{L_2} \prod_{i = 1}^r K_{ \frac{N}{2^i} }.
\end{equation*}
In the special case when
$ N = 2^r$ for $r \geq 2$, then
\begin{equation*}
L_N^\sharp =  \frac{\prod_{i = 1}^r K_{2^i} }{L_2}.
\end{equation*}

\begin{Lemma}\label{L:orthogonal}
For any prime number $p$, and an arbitrary positive integer $N$, we have
$$
\text{gcd}(L_p,L_N^\sharp)=1.
$$
\end{Lemma}
\begin{proof}
If $p$ does not divide $N$, then there is nothing to prove. So, we proceed
with the assumption that $p$ divides $N$. Suppose $N=np$ for some $n\in \N$,
and let $g=g(s,t)\in \N[s,t]$ denote $\text{gcd}(L_p,L_N^\sharp)$.
Obviously, we may assume that $g$ is a non-constant polynomial.
It is also evident that $g$ is a divisor of $L_N/L_p$.
We know from the proof of Theorem~\ref{T:p^2 does not divide} that
$L_N/L_p \equiv n t^{n-1} L_{ p-1}^{n-1} \mod L_p$, hence,
\begin{align}\label{A:tL}
\frac{L_N}{L_p} \equiv n t^{n-1} L_{ p-1}^{n-1} \mod g.
\end{align}
Therefore, $g$ divides the right hand side of (\ref{A:tL}).
In particular, specializing at $s=t=1$, we see that $g(1,1)$ divides $f_{p-1}^{n-1}$, hence,
a prime factor of $g(1,1)$ divides $f_{p-1}$. But this means $f_p=L_p(1,1)$ and
$f_{p-1}$ have a common prime divisor, which is absurd. Therefore $g=1$.
\end{proof}

Recall that $\text{gcd}(L_m,L_n) = L_{\text{gcd}(m,n)}$.
Divisibility properties of Lucas polynomials carry over to the flattened and sharpened versions:
\begin{Theorem}
Let $m$ and $n$ be two positive integers such that $m \mid n$. Then
\begin{enumerate}
\item[(i)] $L_m^\flat \mid L_n^\flat  \text{ in } \N[s,t]$,
\item[(ii)] $L_m^\sharp \mid L_n^\sharp \text{ in } \N[s,t]$.
\end{enumerate}
\end{Theorem}
\begin{proof}
Part $(i)$ follows from Theorem~\ref{T:divisible}. Part $(ii)$ follows from part $(i)$ combined with
Lemma~\ref{L:orthogonal}.
\end{proof}

\subsection{Flat and Sharp Lucanomials}

\begin{Theorem}\label{T:orthogonal}
For all $0 \leq k \leq n $, we have
$$
{ L_n \choose L_ k } = { L_n \choose L_k }^\flat { L_n \choose L_k }^\sharp.
$$
\end{Theorem}
\begin{proof}
This is immediate from
$$
L_n^\sharp!=\frac{L_n!}{L_n^\flat!},
$$
which itself is a consequence of equation (\ref{A:sharp Lucas}).
\end{proof}

Clearly, the remarkable combinatorial interpretation (\ref{L:SS1 Theorem 3})
of ${ L_n \choose L_k }$ exists because of polynomiality.
A natural question to ask at this point is whether or not the flat/sharp lucanomials
are polynomials. The answer is affirmative.

We proceed with a rather general result on ``binomial coefficients'' for the flattened
polynomial sequences. Although we state this for polynomials only,
it stays valid for sequences in an integral domain.
\begin{Theorem}\label{T:flat is polynomial}
Let $R$ be a polynomial algebra over a field of characteristic zero.
Let $\{ P_n \}_{n\in \N}$ be a sequence of polynomials from $R$ with $P_0=0$
and $P_1=1$.
For each $n\in \PP$, let $P_n^\flat$ denote the flattening of $P_n$, that is $P_n^\flat=P_{p_1}\cdots P_{p_r}$,
whenever $n= p_1^{e_1}\cdots p_r^{e_r}$ is the prime factorization of $n$.
Then the associated flat binomial
${ P_n \choose p_k }^\flat:= \frac{P_n^\flat \cdots P_{n-k+1}^\flat }{ P_k^\flat \cdots P_1^\flat}$
is a polynomial.
\end{Theorem}

\begin{proof}
If $p\in \PP$ is a prime number, then with an abuse of terminology call $P_p$ ``prime.''
We define the $P_p$-valuation of $P_n$ to be the highest exponent of $P_p$ in
the factorization of $P_n$ in $R$. Since $P_n^\flat$ is a product of primes,
the $P_p$-valuation of $P_n^\flat ! := P_n^\flat P_{n-1}^\flat\cdots P_1^\flat$ is equivalent to the
$p$-adic valuation of $n^\flat !$, which is
$$
\nu_{P_p} (P_n^\flat!)= \nu_p( n^\flat !)= \left \lfloor \frac{n}{p} \right\rfloor,
$$
hence
\begin{align}\label{A:buyuk}
\nu_{P_p} \left( { P_n \choose P_k }^\flat \right) = \left \lfloor \frac{n}{p} \right\rfloor
-\left \lfloor \frac{k}{p} \right\rfloor - \left \lfloor \frac{n-k}{p} \right\rfloor \geq 0.
\end{align}
To prove the inequality in (\ref{A:buyuk}) write $n= mp+r$, $k=lp+t$ where $0\leq t,s \leq p$.
So,
$$
 \left \lfloor \frac{n}{p} \right\rfloor
-\left \lfloor \frac{k}{p} \right\rfloor - \left \lfloor \frac{n-k}{p} \right\rfloor
= m-l - (m-l)- \left \lfloor \frac{r-t}{p} \right\rfloor = -  \left \lfloor \frac{r-t}{p} \right\rfloor \geq 0
$$
since $r-t< p$ (possibly negative). In fact, this argument shows that
$\nu_{P_p} \left( { P_n \choose P_k }^\flat \right) $ is 0 or 1.
Therefore, the {\it a priori }rational function ${P_n \choose P_k}^\flat$ is a polynomial.
\end{proof}

\begin{Theorem}\label{T:sharp is polynomial}
Both the flat and sharp lucanomials are polynomials in $\N[s,t]$.
\end{Theorem}

\begin{proof}
Polynomiality of the flat lucanomials follows from Theorem~\ref{T:flat is polynomial},
so, we proceed with the sharp lucanomials.
Since ${L_n \choose L_k}$ is a polynomial, by Theorem~\ref{T:orthogonal} it is enough
to show that the denominator of ${L_n \choose L_k}^\sharp$ has no divisor
shared with the polynomial ${L_n \choose L_k}^\flat$. In light of Lemma~\ref{L:orthogonal}
this is now obvious.
\end{proof}

\subsection{Catalanomials}

In this section we extend the discussion to an $s,t$-version of the
classical  Catalan numbers.

\begin{Definition} A general binomial version of Catalan, the $(s,t)$-Catalan, is defined to be
$$
C_{L_n}:=\frac{1}{L_{n+1}} {L_{2n}\choose L_n}.
$$
The {\em flat} and {\em sharp} $(s,t)$-Catalan polynomials, $C_n^\flat$, $C_n^\sharp$
are defined similarly, by replacing $L_i$'s with $L_i^\flat$'s, and with $L_i^\sharp$'s, respectively.
\end{Definition}

\begin{Theorem}
The $(s,t)$-Catalans $C_{L_n},C_n^\flat,C_n^\sharp$ are all polynomials in $\mathbb{N}[s,t]$.
\end{Theorem}
\begin{proof}
The first assertion is immediate from
$$
C_{L_n}={ L_{2n-1}\choose L_{n-1}} +t {L_{2n-1} \choose L_{n-2}},
$$
which is one of the properties found in~\cite{SS1}.
The proof is completed by double induction on $n$ and $k$.
For the second, it is enough to observe that $L_{n+1}^\flat$ divides ${L_{2n}\choose L_n}$
and $\text{gcd}(L_{n+1}^\flat, {L_{2n}\choose L_n}^\sharp) =1$ (by Lemma~\ref{L:orthogonal}).
The proof of the third assertion follows from that of the second.
\end{proof}

\section{Delannomials}

Let $a,b\in \PP$ be two positive integers.
The {\em Delannoy number} $D(a,b)$ is the number of lattice paths
starting at $(0,0)$ and ending at $(b,a)$ moving with unit steps $(1,0),(0,1)$, or $(1,1)$.
These numbers are given by the recurrence relation
\begin{align}\label{D:basic recurrence}
D(a,b)=D(a-1,b)+D(a,b-1)+D(a-1,b-1)
\end{align}
and the initial conditions $D(a,0)=D(0,b)=D(0,0)=1$.
The beautiful symmetry of the generating series
$$
\mc{D}(x,y)= \sum_{
\begin{subarray}{l}
      a+b \geq 1 \\ a,\, b\, \in \N
      \end{subarray}}
D(a,b)x^{a}y^{b} = \frac{1}{1-x-y-xy}
$$
is indicative of a rich combinatorics associated with these numbers.
Of particular interest is the paper \cite{Bump}, where Delannoy numbers
find a prominent place in number theory (especially, in the discussion on the
notion of the so-called {\it local Riemann Hypothesis}).

Let $x$ be a new variable,
and define the polynomial $D_n(x)$, $n\in \N$ by
\begin{align*}
D_n(x) = L_n\vert_{s=x+1,t=x}.
\end{align*}
It is immediate from the defining recurrence of Lucas polynomials that $D_{0}=0$, $D_{1}=1$ and
\begin{align}\label{D:recurrence}
D_n(x)= (x+1) D_{n-1} + x D_{n-2},
\end{align}
for $n\geq 2$.
If there is no danger of confusion we remove the argument $x$ and write simply $D_n$
in place of $D_n(x)$.

\vspace{.5cm}

The next result shows that the coefficients of $D_n(x)$ are the classical Delannoy numbers.
\begin{Lemma}\label{L:dn}
For each $n\geq 1$, we have
\begin{align}\label{A:explicit form}
D_n(x) =  \sum_{i=1}^{n} D(n-i,i-1) x^{i-1}.
\end{align}
\end{Lemma}

\begin{proof}
Write $D_n = \sum_{i=0}^{n-1} d^n_i x^i$. Then by the recurrence~(\ref{D:recurrence})
we see that
$$
\sum_{i=0}^{n-1} d^n_i x^i = (x+1) \sum_{i=0}^{n-2} d^{n-1}_i x^i + x \sum_{i=0}^{n-3} d^{n-2}_i x^i,
$$
or equivalently, for $1\leq i \leq n-3$,
\begin{align}\label{A:d}
d^n_{i} = d^{n-1}_{i-1} + d^{n-1}_{i} + d^{n-2}_{i-1}.
\end{align}
Assume by induction that $d^n_i = D(n-i,i-1)$. Then the recurrence (\ref{D:recurrence}) together
with the induction hypothesis implies that
$$
D(n-i,i-1)= D((n-1)-(i-1),i-2)+ D((n-1)-i,i-1)+D((n-2)-(i-1),i-2),
$$
which is equivalent to (\ref{A:d}).

\end{proof}

\begin{Lemma}
Preserve the notation from the proof of Lemma~\ref{L:dn}, and
write $D_n = \sum_{i=0}^{n-1} d^n_i x^i$. Then $d^n_i = d^n_{n-i-1}$.
\end{Lemma}
\begin{proof}
By Lemma~\ref{L:dn}, we know that $d^n_{n-i-1} = D(n-1-(n-i-1), n-i-1)$
and that $d^n_i = D(n-1-i,i)$. Obviously these are equal quantities.
\end{proof}

\begin{Definition}
The $(n,k)$-th {\em delannomial}
is defined to be
$$
 { D_n \choose D_k } = \frac{ D_n D_{n-1}\cdots D_{n-k+1}}{ D_k \cdots D_2 D_1}.
$$
\end{Definition}

Let $p(x) = \sum_{i=0}^r a_i x^i$ be a polynomoial. If
$r$ is odd, then the {\em central monomial} of $p(x)$ is defined to be
$a_j x^j$, where $j= (r+1)/2$. If $r$ is even, it is defined to be $a_j x^j$ with
$j= \lfloor r/2 \rfloor$.

\begin{Theorem}
For all $m$ and $n$, the delannomial ${D_{m+n} \choose  D_m}$ is symmetric and unimodal.
\end{Theorem}
\begin{proof}
The recurrence~(\ref{SS1 recurrence}) induces the same recurrence on ${D_{m+n} \choose D_m}$.
Since product of symmetric and unimodal polynomials is symmetric and unimodal,
we only need to show that the degree of the central monomial of
$D_{m+1} {D_{m+n} \choose D_{m-1}}$ matches with the central monomial of
$xD_{m-1} {D_{m+n} \choose D_{n-1}}$. This follows from induction.

\end{proof}

\begin{Remark}
For ${D_{m+n} \choose  D_m}$, there exists a combinatorial interpretation, along the lines of~\cite{SS1},
by using dominos (weighted by $x$) and two kinds of monominos
(weighted by $x$ and $x^2$).
\end{Remark}

\section{Divided-Differences}

The Lucas polynomials bring in many interesting features,
but they fail to be symmetric in the variables $s$ and $t$. For example,
$L_2=s$.
To remedy this deficit, we consider their behavior under the
\emph{divided-difference operator}. To be precise, we associate the sequence of polynomials defined by
$$
S_n(s,t)=\frac{L_n(s,t)-L_n(t,s)}{s-t}.
$$
Of course, $S_n(s,t)=S_n(t,s)$ for all $n\geq0$.
Let's record some basic properties of $S_n(s,t)$.
The next result shows a simple algebraic relation between the two sequence of polynomials via generating functions.

\begin{Lemma}\label{L:generating function for S}
Suppose $S(x;s,t)=\sum_nS_n(s,t)x^n$ and $L(x;s,t)=\sum_nL_n(s,t)x^n$. Then
$$
S(x;s,t)=(1-x)L(x;s,t)L(x;t,s).
$$
\end{Lemma}
\begin{proof} It is well-known that $L(x;s,t)=\frac{x}{1-sx-tx^2}$. Now, proceed as follows:
\begin{align*} \frac{L(x;s,t)-L(x;t,s)}{s-t}&=\frac1{s-t}\left[\frac{x}{1-sx-tx^2}-\frac{x}{1-tx-sx^2}\right] \\
&=\frac1{s-t}\left[\frac{(s-t)(1-x)x^2}{(1-sx-tx^2)(1-tx-sx^2)}\right]. \end{align*}
The proof is complete.
\end{proof}

\begin{Corollary} There is a recurrence relation linking $L_n(s,t)$ with $S_n(s,t)$:
$$
S_n(s,t)=sS_{n-1}(s,t)+tS_{n-2}(s,t)+L_{n-1}(s,t)-L_{n-2}(s,t).
$$
\end{Corollary}

\begin{proof}
Rewrite Lemma~\ref{L:generating function for S} in the form: $(1-sx-tx^2)S(x;s,t)=(x-x^2)L(x,s,t)$.
Taking the coefficients of $x^n$ on both sides of this equation reveals that
$$
S_n(s,t)-sS_{n-1}(s,t)-tS_{n-2}(s,t)=L_{n-1}(s,t)-L_{n-2}(s,t),
$$
which is equivalent to desired conclusion.
\end{proof}
\noindent
The generating function for \emph{second order Fibonacci numbers}, as defined in

\begin{center}{\tt http://oeis.org.A010049},\end{center}

\noindent
is $x(1-x)/(1-x-x^2)^2$. The next statement connects these numbers with the divided-differences $S_n(1,1)$.

\begin{Corollary} Let $a_n$ denote the specialization of $S_n(s,t)$ at $s=t=1$. Then
\begin{enumerate}
\item[(i)] $a_n$ is the $(n-1)$-th second order Fibonacci number;

\item[(ii)] $a_n=f_{n-1}+\sum_{k=0}^{n-2}f_{n-2-k}f_k$.
\end{enumerate}
\end{Corollary}
\begin{proof}
$(ii)$ Recall that $L(x;1,1)=\sum_nf_nx^n$, where $f_n$ are the Fibonacci numbers.
Observe also that given any $F(x)=\sum_nc_nx^n$, the partial sums $\sum_{k=0}^nc_n$
have generating function $\frac{F(x)}{1-x}$.
From Lemma~\ref{L:generating function for S}, we have $\frac{S(x;1,1)}{1-x}=L(x;1,1)^2$.
Extract the coefficients of $x^n$ to obtain $\sum_{k=0}^na_k=\sum_{k=0}^nf_{n-k}f_k$
(where Cauchy's product formula has been utilized). Since $f_{n-k}-f_{n-1-k}=f_{n-2-k}$, it is easy to see that
\begin{align*} a_n=\sum_{k=0}^na_k-\sum_{k=0}^{n-1}a_k
&=\sum_{k=0}^nf_{n-k}f_k-\sum_{k=0}^{n-1}f_{n-1-k}f_k \\
&=f_{n-1}+\sum_{k=0}^{n-1}(f_{n-k}-f_{n-1-k})f_k \\
&=f_{n-1}+\sum_{k=0}^{n-2}f_{n-2-k}f_k.
\end{align*}
To get $(i)$, use $S(x;1,1)=(1-x)L(x;1,1)^2=x\left[\frac{x(1-x)}{(1-x-x^2)^2}\right]$. The proof follows.
\end{proof}

In the next result we obtain a recurrence for the divide-difference $S_n(s,t)$.
\begin{Corollary}
Preserve the notations from Lemma~\ref{L:generating function for S}.
Write $S_n$ for $S_n(s,t)$. For $n\geq4$, we have
$$
S_n=(s+t)S_{n-1}+(s+t-st)S_{n-2}-(s^2+t^2)S_{n-3}-stS_{n-4}.
$$
\end{Corollary}
\begin{proof}
Once more, Lemma~\ref{L:generating function for S} implies $(1-sx-tx^2)(1-tx-st^2)S(x;s,t)=x^2-x^3$.
Equivalently,
$$
[1-(s+t)x-(s+t-st)x^2+(s^2+t^2)x^3+stx^4]\,S(x;s;t)=x^2-x^3.
$$
Now, simply compare the coefficients of $x^n$ on both sides of the last equation.
\end{proof}

Here is an amusing corollary with beautiful symmetry.
\begin{Corollary}
For $s,\, t\in \PP$, we have the numerical series evaluation
$$
\sum_{n\geq0}\frac{S_n(s,t)}{(s+t)^{n+1}}=\frac1{st(s+t-1)}.$$
\end{Corollary}
\begin{proof} Corollary 2.6 of~\cite{ACMS} states that
$$
\sum_n\frac{L_n(s,t)}{(s+t)^{n+1}}=\frac1{t(s+t-1)}.
$$
Thus,
\begin{align*}
\sum\frac{S_n(s,t)}{(s+t)^{n+1}} &=\sum\frac{L_n(s,t)-L_n(t,s)}{(s-t)(s+t)^{n+1}}\\
&=\frac1{s-t}\left[\frac1{t(s+t-1)}-\frac1{s(s+t-1)}\right]=\frac1{st(s+t-1)}.
\end{align*}
\end{proof}

\begin{Remark}
Despite the above plethora of facts, one aspect of the symmetric
functions $S_n(s,t)$ remains undesirable from a combinatorial view point:
the coefficients are not all non-negative.
Fortunately, all is not lost because there is a quick fix as will be seen below.
\end{Remark}

Let $\alpha\in\mathbb{N}$. While maintaining the recursive relation for Lucas polynomials,
we make a slight alteration to the initial conditions: assume
$L_0(s,t:\alpha)=L_1(s,t:\alpha)=\alpha$. For $n\geq2$, define
$$
L_n(s,t:\alpha)=sL_{n-1}(s,t:\alpha)+tL_{n-2}(s,t:\alpha).
$$
Let $S_n(s,t:\alpha)$  denote the divided-difference polynomial that is
associated with $L_n(s,t:\alpha)$.

\begin{Theorem} The following hold true:
\begin{enumerate}
\item[(i)] $S_n(s,t:\alpha)=\alpha S_n(s,t:1)$ for all $\alpha\in\mathbb{N}$;

\item[(ii)] $(s+t-1)$ divides $S_n(s,t:\alpha)$ for all $n\in\mathbb{N}$;

\item[(iii)] $\frac{S_n(s,t:\alpha)}{s+t-1}$ has non-negative integral coefficients, only.
\end{enumerate}
\end{Theorem}

\begin{proof} $(i)$ The defining recurrence and initial conditions imply the homogeneity
$L_n(s,t:\alpha)=\alpha L_n(s,t:1)$.
From here, it is evident that $S_n(s,t:\alpha)$ inherits the same property.
Routine standard methods give
$$
L(s,t:1):=\sum_nL_n(s,t:1)x^n=\frac{1-(s-1)x}{1-sx-tx^2}.
$$
One can easily verify that $\sum_nS_n(s,t:1)x^n=\frac{(s+t-1)x^3}{(1-sx-tx^2)(1-tx-sx^2)}$.
In particular,
$$
\sum_n\frac{S_n(s,t:1)}{s+t-1}x^n=\frac{x^3}{(1-sx-tx^2)(1-tx-sx^2)}=xL(s,t)L(t,s)
$$
simultaneously demonstrates the divisibility in $(ii)$ as well as the claim in $(iii)$.
\end{proof}

\begin{Remark}
It is worthwhile to note that $L_n(s,t:1)=L_n(s,t)+tL_{n-1}(s,t)$.
As a result, the modified Lucas polynomials also retain a combinatorial interpretation
much as the ordinary ones.
Such as simultaneous tiling of a pair of rectangles, one $1\times (n-1)$ and the other
$1\times n$, where the latter always begins with a domino.
\end{Remark}

\smallskip
\noindent
\textbf{Acknowledgements.} The second and the third authors are partially supported by
a Louisiana Board of Regents Research and Development Grant 549941C1.


TITLE: To be ordered or not to be ordered
QUESTION [0 upvotes]: This is the general format of many probability questions:

From the given $N$ distinct numbers, $n$ distinct numbers are randomly selected such that...

OR

$a_1 ,a_2 ,a_3,...,a_n$ are $n$ distinct numbers randomly selected from $N$ distinct numbers, such that...

OR any other that I'm yet to see.
My question:

When do I treat these $n$ numbers as an ordered set of numbers, and when do I not?

i.e. to say, for $n=4$, $(5,6,7,8)$ is not the same as $(6,7,8,5)$ if these are ordered pairs.
I ask this question because when sets become ordered, their count, hence probability
($=\frac{\text{count favored}}{\text{total count}}$) changes. I need to know if there exist "signals" (word usage patterns) in probability questions from which I can infer that the answer has to be derived using ordered pair or un ordered pair.

REPLY [1 votes]: Actually, when probability is asked for, it doesn't matter !
Q: Pr that we get $5,6,7,8$ when $4$ distinct digits are randomly selected from the $10$ decimal digits.
(a) When the order in which you select the digits doesn't matter: $\dfrac{1}{\binom{10}4}$
(b) When the order in which you select the digits matters: $\dfrac{4!}{10\cdot9\cdot8\cdot7}$


TITLE: Expected time of visits to a transient state in a Markov chain
QUESTION [2 upvotes]: Suppose that $\left\{X_{n}\right\}$ is a Markov chain and $y$ is a transient state. So we know the following:
1) $V(y)=\sum_{k=0}^{\infty}\mathbb{1}_{\left\{y\right\}}(X_{k})$, the # of times that we arrive to $y$.
2) $\mathbb{P}(V(y)<\infty)=1$, because the state is transient.
3) $\mathbb{P}_{y}\big[T_{y}< \infty \big]<1$,the probability to start from y and visit again $y$ is less than $1$. Where $T_{y}=\inf\left\{k>0:X_{k}=y\right\}$ is a stopping time.
and we have to show that $\mathbb{E}_{x}\big[V(y)\big]=\mathbb{P}_{x}\big[T_{y}<\infty\big]\mathbb{E}_{y}\big[V(y)\big]$.
I tried to start with the calculation of $\mathbb{E}_{x}\big[V(y)\big]$ but I couldn't take the result.
$$
\mathbb{E}_{x}\left[V(y)\right]=\mathbb{E}_{x}\left[\sum_{k=0}^{\infty}\mathbb{1}_{\left\{y\right\}}(X_{k})\right]=\sum_{k=0}^{\infty}\mathbb{E}_{x}\left[\mathbb{1}_{\left\{y\right\}}(X_{k})\right]=\sum_{k=0}^{\infty}\mathbb{P}(X_{k}=y|X_{0}=x)=\sum_{k=0}^{\infty}\rho^{k}(x,y)
$$
But I can't see how this helps to take the $\mathbb{P}_{x}\big[T_{y}<\infty\big]\mathbb{E}_{y}\big[V(y)\big]$.
Any help or idea would be really helpful.

REPLY [2 votes]: Setup: Suppose $x \neq y$.
Define $\rho_{xy} := \mathbb{P}_x(T_y < \infty)$, and let $T_y^k$ be the $k$-th return time to $y$.

Lemma: $\mathbb{P}_x(T_y^k<\infty) = \rho_{xy} \cdot \rho_{yy}^{k-1}$ for all $k \ge 1$ and $x,y \in S$. Prove this with induction, use Strong Markov Property.

Your Problem: Note that $\mathbb{E}_y[V(y)] = \frac{1}{1-\rho_{yy}}$, since $V(y)$ is geometric with success probability $\rho_{yy}$ conditional upon $X_0 = y$.
Now we need an expression for $\mathbb{E}_x[V(y)]$.
$$
\mathbb{E}_x(V(y)) = \sum_{k=1}^\infty \mathbb{P}_x(V(y) \ge k) = \sum_{k=1}^\infty \mathbb{P}_x(T_y^k < \infty)
= \sum_{k=1}^\infty \rho_{xy} \rho_{yy}^{k-1} = \frac{ \rho_{xy}}{1-\rho_{yy}}
$$

My initial comment was to show that the result is obviously  not true for $y=x$.


TITLE: Adjust Saturation in CIE L*a*b* space.
QUESTION [0 upvotes]: Given a color in CIE L*a*b* space, how does one change the saturation? This is what I know...
$$\mathrm{chroma} = \sqrt {(a^*)^2 + (b^*)^2}$$
$$\mathrm{hue} = \arctan \left( a^* \over b^* \right)$$
$$\mathrm{sat} = {\frac{\mathrm{chroma}}{\sqrt{(L^*)^2 + \mathrm{chroma}^2}}}$$
I want to add $\mathrm{satdiff}$ to $\mathrm{sat}$, keeping $\mathrm{hue}$ and $L^*$ constant. I need to determine how to recalculate $a^*$ and $b^*$.

REPLY [0 votes]: Here is what I get: suppose your new total value of $sat$ is shown by $x$. Then you want to multiply the original $(a,b)$ by
$t={{xL}\over{\sqrt{(a^2+b^2)(1-x^2)}}}$. I dropped all the stars!


text:
\begin{document}
\title[Controlling alliances through executing pressure]{Controlling
alliances through executing pressure}
\thanks{$^{\ast }$Corresponding author}
\author{L. A. Khodarinova$^{1}$}
\thanks{$^{1}$SPMMRC, School of Physics and Astronomy, University of
Nottingham, Nottingham NG7 2RD UK}
\author{J. M. Binner$^{2\ast }$}
\thanks{$^{2}$Dept. of Strategic Management, Aston Business School, Aston
University, Birmingham B4 7ET UK}
\author{L. R. Fletcher$^{3}$}
\thanks{$^{3}$School of Computing and Mathematical Sciences, Liverpool John
Moores University, Liverpool L2 3AA UK}
\author{V. N. Kolokoltsov$^{4}$}
\thanks{$^{4}$School of Computing and Mathematics, Nottingham Trent
University, Nottingham NG1 4BU UK}
\author{P. Whysall$^{5}$}
\thanks{$^{5}$Nottingham Business School, Nottingham Trent University,
Nottingham NG1 4BU UK}
\keywords{Prisoners' dilemma, cooperation, alliances}

\begin{abstract}
In this paper the standard prisoners' dilemma is embedded in environmental
conditions in which the interaction takes place. This provides a theoretical
background to the analysis of the empirical studies which indicate that
including additional factors when considering an alliance is very important.
We show that such an approach, though theoretically simple, provides a
powerful tool for suggesting successful strategies for forming, maintaining
and withstanding a rival attack on an alliance, projecting an alliance
possible success and determining which measures must be taken to maintain an
alliance in a changing environment. It also provides insight into the
possibility of preventing alliances in rivals. The relative simplicity of
this framework means that the approach can be easily applied when the real
life decisions are taken.
\end{abstract}

\maketitle

\section{Introduction}

Recently there has been an increasing interest in understanding the
instruments responsible for success in business alliances. In a highly
competitive and globalized market alliances and joint ventures are becoming
increasingly popular by allowing companies to share risks, develop new
markets, acquire technological advances and so on. There has also been a
significant increase in alliances between competitors$^{1,2}$ as such
ventures not only improve their market performance but also reduce costs due
to eliminating rivalry hazards. Unfortunately, empirical research$^{2-8}$
shows that business alliances have high failure rates (at or higher than
50\%). The reason for such failure has a dual nature$^{2,9}.$ On one side
non opportunistic reasons such as managerial complexity and coordinating
costs play a significant role. The other important reason is interfirm
rivalry as each partner is acting to maximize its own benefits. This paper
is aimed at addressing the second reason.

In order to explain the cooperative behaviour when the risk of opportunistic
behavior is high game-theoretic descriptions of social interactions are
often\ used$^{10,11,12}.$ The single-interaction prisoners' dilemma has been
widely used$^{11,12}$ as a generic model of such\ interactions. Analysis of
the single interaction prisoners' dilemma leads to the conclusion that
cooperative behaviour cannot be rational; nevertheless it is observed by
many empirical studies. The main approach to resolving this paradox has been
based on considering the iterated prisoners' dilemma, i.e. considering the
game in the long term context$^{9,10,11}.$ This changes the structure of the
game and cooperation becomes rational$^{13,14}.$ The basic idea is that by
including future interactions \textquotedblleft punishing
strategies\textquotedblright\ may be used, i.e., \textquotedblleft if you do
not cooperate now, you will be punished in the future\textquotedblright .
Unfortunately, the empirical studies indicate$^{10}$ that companies using
such strategies are not very successful in maintaining alliances. Nor are
such strategies evolutionary stable and if a player operates in a
noncooperative society no alliance can evolve in the long run$^{15}.$

From a game-theoretic point of view there exist many different approaches to
overcoming these difficulties$^{16-24}.$ Such approaches, most of which are
based on computer simulations$^{17-23},$ in particular include considering
complex strategies in an evolutionary model$^{17,18}.$ For example players
may be allowed to learn from experience$^{19}.$ It is shown$^{19}$ that
mutual cooperation can be maintained when players have a primitive learning
ability. It was shown that under proposed learning evolution some
cooperative strategies can invade not only unconditional cooperation, Tit
for Tat and Pavlov strategies but also noncooperative strategies. Another
approach is to embed the prisoners' dilemma into a spatial context$^{20,21}.$
For example$^{20},$ the version of the iterated prisoners' dilemma with only
unconditionally cooperating and unconditionally defecting players
interacting with the immediate neighbours was considered. It was shown$^{20}$
that such a model can generate chaotically changing spatial patterns, in
which cooperators and defectors both persist indefinitely. The pattern
generated by groups of cooperators exhibits$^{21}$ the scale-invariance
which is typical of self-organized criticality$^{22}$. Multi players games
are also considered$^{23}$ with solutions found by computer simulations.
There is also a direction of research based on the idea of private
information available to the players. That is, each player may have some
information about themselves or state of the game which is not available to
other players. The recent developments$^{24}$ in this area have revealed the
possibility of cooperation under condition of private information. Providing
an important framework for understanding evolution of cooperation in Nature,
such approaches however are not easily applicable to the situations when the
real life business alliances must be managed. Let us notice nevertheless
that all of these studies indicate that cooperative behaviour becomes
understandable when the interaction is considered in a wider context (such
as length of interaction, for example).

Surprisingly, there are few theoretical studies that suggest modeling
cooperation by the games other than prisoners' dilemma. Empirical research
on the other side shows that including additional factors when considering
an alliance is very important and may suggest successful strategies for
forming and maintaining an alliance. For example$^{1},$ it is shown that
engaging in unilateral commitments significantly increases an alliance
success rate. It is argued$^{1}$ that unilateral commitments change the
payoff structure of the game in such a way that mutual defection is no
longer the Nash Equilibrium in the single interaction game. Unfortunately
the lack of general game theoretic description of such and similar
situations leaves it unexplained why some unilateral commitments lead to an
alliance in one situation but not in others.

In this paper we try to overcome this deficiency by embedding the standard
Prisoners Dilemma in environmental conditions in which the interaction takes
place. We show that such an approach, thought theoretically simple, provides
a powerful tool for suggesting successful strategies for forming,
maintaining and withstanding a rival attack on an alliance, projecting an
alliance's possible success and determining which measures must be taken to
maintain an alliance in a changing environment. It also provides insights
into the possibility of preventing alliances in rivals. The relative
simplicity of this framework means that the approach can be easily applied
when the real life decisions are taken.

The main idea of our approach is to evaluate the external conditions under
which the alliance is forming. We suggest that the majority of such
conditions can be evaluated as either unchangeable or changeable pressure
(benefits) to the players. As far as the unchangeable factors are concerned
they can be considered as the base payoffs of the single interaction game
(for example prisoners' dilemma in our case). We model changeable conditions
by introducing a \textquotedblleft third player\textquotedblright . The
\textquotedblleft third player\textquotedblright\ can be irrational$^{25}$
and, for example, can represent \textquotedblleft Nature\textquotedblright ,
that is environmental or other conditions that have an impact on the game
but do not depend on the behaviour of the first two players (for example, a
highly competitive market or a tax regime imposed by a government). This
could also include pressure that a company decides to impose on itself by
engaging in unilateral commitments. The \textquotedblleft third
player\textquotedblright\ can also be rational. In this context there might
be a real third player who interacts with the first and the second players
(engaged in a prisoners' dilemma type game for example), possibly to a
degree he can choose.

This model correlates well with the empirical studies showing that by
considering the two players not in isolation but in the context of their
interaction with the \textquotedblleft third player\textquotedblright\ a
cooperative Nash Equilibrium between the first two players may emerge. We
investigate the effect which the existence of the \textquotedblleft third
player\textquotedblright\ has on the possibility of cooperation. This
provides mechanisms for controlling and managing the alliances via changing
the external conditions. Considering the \textquotedblleft third
player\textquotedblright\ as another company attacking the alliance we show
how to find an optimal strategy for the attack and also how such an attack
could be resisted and the alliance could be saved by good management.

\section{Modeling interaction under external pressure}

In this section we give an example of modelling an interaction in the
context of external conditions. As our example we consider two rival
companies engaged in the prisoners' dilemma game who, at the same time, are
withstanding an attack from a third player. In the model below we choose
certain unchangeable factors such as the value of the market or corporate
benefits. Clearly, it is done solely for the purpose of illustrating the
approach and the parameters appropriate to the situation under consideration
must be taken by the practitioners using this framework. For simplicity we
also consider a symmetric base interaction which also can be modified
without much difficulty. It is however important to note that the changeable
pressure is modelled continuously. Although in the current situation the
specific values of such pressure might apply, it is necessary to estimate
the impact of the pressure over the whole range of possible outcomes.

We begin by modelling an interaction with the prisoners' dilemma game in
which the players simultaneously choose an action from a set of two actions:
\textquotedblleft Ally\textquotedblright\ and \textquotedblleft
Fight\textquotedblright . Both players choosing \textquotedblleft
Ally\textquotedblright\ results in forming an alliance in which the players
share a market (resource) equally and obtain payoff of $l.$ Here $2l$
represents the value of the market (resource) share available. One player
choosing \textquotedblleft Fight\textquotedblright\ and the other
\textquotedblleft Ally\textquotedblright\ will be taken as the former player
is attacking the latter who does not fight back. Here $v$ represents the
value of the market (resource) share transferred as a result of the attack
from the \textquotedblleft allying\textquotedblright\ player to the
\textquotedblleft fighting\textquotedblright\ player. The parameter $x$
represents extra costs of running the business outside the alliance compared
with the cost of running the business in alliance (for example, corporate
benefits) If both players chose \textquotedblleft Fight\textquotedblright\
then each player is supposed to have an equal probability of obtaining the
whole market (resource). Here $f$ represents the cost of fighting. In order
for this game to be identified as a prisoners' dilemma we must have $v>x$
and $v>f$ and we also assume that $x\geq 0$ and $f\geq 0.$ The payoffs for
this game are summarized in the table below.
\begin{equation}
\begin{tabular}{ccc}
$^{P_{1}\,}\backslash _{\,P_{2}}$ & Ally & Fight \\
Ally & $^{l\,}\backslash _{\,l}$ & $^{l-v-x\,}\backslash _{\,l+v-x}$ \\
Fight & $^{l+v-x\,}\backslash _{\,l-v-x}$ & $^{l-x-f\,}\backslash _{\,l-x-f}$
\end{tabular}
\label{3Players_PD}
\end{equation}
Building on the model let us now assume that there is a third player who
attacks the $i^{th}$ player with level $q_{i},$ $i=1,2.$ For the convenience
of the analysis we normalize the levels of the attack to be between zero and
one: $0\leq q_{i}\leq 1.$ If the third player attacks with level $q_{i}$ a
market share proportional to the appropriate level of attack is lost by the $
i^{th}$ player. We assume that there may be a cost of being attacked which
is proportional to the level of the attack and will be expressed as $q_{i}c,$
where $c\geq 0.$ We also assume that withstanding an attack in an alliance
may be easier for a company than on its own, so that there maybe an extra
cost $q_{i}y,$ $y\geq 0,$\ of an attack if companies are not in an alliance.
Finally, we suppose that if players are in an alliance they share the cost
of the attack equally. These assumptions result in payoffs summarized in the
bi-matrix below.
\begin{equation}
\begin{tabular}{ccc}
$^{P_{1}\,}\backslash _{\,P_{2}}$ & Ally & Fight \\
Ally & $^{l-lq_{1}-\frac{c}{2}\left( q_{1}+q_{2}\right) \,}\backslash
_{\,l-lq_{2}-\frac{c}{2}\left( q_{1}+q_{2}\right) }$ & $^{l+v-x-q_{1}\left(
l-v+c+y\right) \,}\backslash _{\,l-v-x-q_{2}\left( l+v+c+y\right) }$ \\
Fight & $^{l+v-x-q_{1}\left( l+v+c+y\right) \,}\backslash
_{\,l-v-x-q_{2}\left( l-v+c+y\right) }$ & $^{l-x-f-q_{1}\left( l+c+y\right)
\,}\backslash _{\,l-x-f-q_{2}\left( l+c+y\right) }$
\end{tabular}
\label{3Players_new_payoffs}
\end{equation}
It is fairly simple to obtain the pure strategy Nash Equilibrium conditions,
which are summarized in the Table I below.
\begin{equation}
\begin{array}{c}
\text{Table I : Nash Equilibrium conditions for two players.} \\
\begin{tabular}{ccccc}
\hline
NE $^{P_{1}}\backslash _{P_{2}}$ & $^{Ally}\backslash _{Ally}$ & $
^{Fight}\backslash _{Fight}$ & $^{Ally}\backslash _{Fight}$ & $
^{Fight}\backslash _{Ally}$ \\ \hline
$_{Condition}$ & $
\begin{array}{c}
q_{1}\geq \frac{2v-2x+cq_{2}}{2v+2y+c} \\
q_{2}\geq \frac{2v-2x+q_{1}c}{2v+2y+c}
\end{array}
$ & $
\begin{array}{c}
q_{1}\leq 1-\frac{f}{v} \\
q_{2}\leq 1-\frac{f}{v}
\end{array}
$ & $
\begin{array}{c}
q_{1}\geq 1-\frac{f}{v} \\
q_{2}\leq \frac{2v-2x+q_{1}c}{2v+2y+c}
\end{array}
$ & $
\begin{array}{c}
q_{1}\leq \frac{2v-2x+cq_{2}}{2v+2y+c} \\
q_{2}\geq 1-\frac{f}{v}
\end{array}
$ \\ \hline
\end{tabular}
\end{array}
\label{NE}
\end{equation}
This indicates that the cooperative Nash Equilibrium can be obtained if the
levels of attack $q_{i}$ on both players is quite high. If $q_{i}$ are not
high enough the standard non cooperative Nash Equilibrium is observed. If $
q_{i}$ vary significantly the weakly attacked player fights while the
strongly attacked player does not fight back. There could also\ be a mixed
strategy Nash Equilibrium as we will show in the example below.

As a next step we consider the rational third player and determine the
optimal levels of the attack $q_{i}.$ In this model we assume that before
the game~(\ref{3Players_new_payoffs}) is played the third player chooses $
q_{i}$ or, equivalently, that the first two players are certain about the
strength with which they are attacked. This approach simplifies the analysis
of the game.\ The first and the second player make their choices at the
game~(\ref{3Players_new_payoffs}) which determine their own payoffs and also
the payoff obtained by the third player. The payoffs to the third player
will be given in Table II.
\begin{equation}
\begin{array}{c}
\text{Table II: Payoffs to the third player.} \\
\begin{tabular}{ccccc}
\hline
NE $^{P_{1}}\backslash _{P_{2}}$ & $^{Ally}\backslash _{Ally}$ & $
^{Fight}\backslash _{Fight}$ & $^{Ally}\backslash _{Fight}$ & $
^{Fight}\backslash _{Ally}$ \\ \hline
$^{Payoff}$ & $^{\left( l-\sigma -\varepsilon \right) \left(
q_{1}+q_{2}\right) }$ & $^{\left( l-\sigma -\epsilon \right) \left(
q_{1}+q_{2}\right) }$ & $^{\left( l-\sigma \right) \left( q_{1}+q_{2}\right)
+v\left( q_{2}-q_{1}\right) }$ & $^{\left( l-\sigma \right) \left(
q_{1}+q_{2}\right) +v\left( q_{1}-q_{2}\right) }$ \\ \hline
\end{tabular}
\end{array}
\label{3Players_payoffs_to_the_third}
\end{equation}
Here $\sigma $ represents the cost of the attack, $\varepsilon $ represents
the additional cost due to attacking an alliance and $\epsilon $ represents
the decrement in the cost of the attack if it is made on the companies which
are fighting with each other.

We now consider examples showing how the optimal level of attack can be
chosen.

\section{Example}

Consider the game with the following parameters $v=5,$ $x=2,$ $y=2,$ $f=2$
and $c=3.$ Using formulae~(\ref{NE}) we obtain the following conditions for
the various Nash Equilibria.
\begin{equation}
\begin{array}{c}
\text{Table III : Nash Equilibrium conditions for two players when} \\
v=5,x=2,y=2,f=2\text{ and }c=3. \\
\begin{tabular}{ccccc}
\hline
NE $^{P_{1}}\backslash _{P_{2}}$ & $^{Ally}\backslash _{Ally}$ & $
^{Fight}\backslash _{Fight}$ & $^{Ally}\backslash _{Fight}$ & $
^{Fight}\backslash _{Ally}$ \\ \hline
$_{Condition}$ & $
\begin{array}{c}
q_{1}\geq \frac{3q_{2}+6}{17} \\
q_{2}\geq \frac{3q_{1}+6}{17}
\end{array}
$ & $
\begin{array}{c}
q_{1}\leq \frac{3}{5} \\
q_{2}\leq \frac{3}{5}
\end{array}
$ & $
\begin{array}{c}
q_{1}\geq \frac{3}{5} \\
q_{2}\leq \frac{3q_{1}+6}{17}
\end{array}
$ & $
\begin{array}{c}
q_{1}\leq \frac{3q_{2}+6}{17} \\
q_{2}\geq \frac{3}{5}
\end{array}
$ \\ \hline
\end{tabular}
\end{array}
\label{Ex_NE}
\end{equation}
We can also find that if $\frac{3q+6}{17}\leq q_{1}\leq \frac{3}{5}$ and $
\frac{3p+6}{17}\leq q_{2}\leq \frac{3}{5}$\ then there is a mixed strategy
Nash Equilibrium in which the first player and the second player choose
\textquotedblleft Ally\textquotedblright\ with probabilities $\frac{6-10q_{2}
}{7q_{2}-3q_{1}}$ and $\frac{6-10q_{1}}{7q_{1}-3q_{2}},$ correspondingly.
For each combination of the parameters we have a unique Nash Equilibrium
solution except for the region where $\frac{3q+6}{17}\leq q_{1}\leq \frac{3}{
5}$ and $\frac{3p+6}{17}\leq q_{2}\leq \frac{3}{5}$ for which there are
three Nash Equilibria: \textquotedblleft Ally\textquotedblright
-\textquotedblleft Ally\textquotedblright , \textquotedblleft
Fight\textquotedblright -\textquotedblleft Ally\textquotedblright\ and the
mixed Nash Equilibrium. It can be shown that in this region
\textquotedblleft Ally\textquotedblright -\textquotedblleft
Ally\textquotedblright\ is Pareto efficient meaning that both players obtain
their highest payoffs if the \textquotedblleft Ally\textquotedblright
-\textquotedblleft Ally\textquotedblright\ is played. The Nash Equilibrium
regions are shown in Figure 1.

Let us now fix parameters determining the payoff of the third player at $
\varepsilon =1,\epsilon =1,\sigma =3$ and consider two scenarios: of high $
(l=8)$ and low $(l=5)$ value of the market (resource). The payoff to the
third player depends on the strategies of the first two players~(\ref
{3Players_payoffs_to_the_third}). If the Nash Equilibrium is not unique for
some range of the parameters $q_{i}$ we assume that the Pareto efficient
Nash Equilibrium is played. The payoffs to the third player and the points
at which its maxima are reached are summarized in Table IV below.
\begin{equation*}
\begin{array}{c}
\text{Table IV: Payoffs to the third player and points of maxima.} \\
\begin{tabular}{cccccccc}
\hline
\multicolumn{2}{c}{} & \multicolumn{3}{c}{$l=8$} & \multicolumn{3}{c}{$l=5$}
\\ \hline
range of $q_{1}\&q_{2}$ & NE & $\text{payoff}$ & max & a$\text{t }\left(
q_{1},q_{2}\right) $ & payoff & max & a$\text{t }\left( q_{1},q_{2}\right) $
\\ \hline
$
\begin{array}{c}
\frac{3q_{2}+6}{17}\leq q_{1} \\
\frac{3q_{1}+6}{17}\leq q_{2}
\end{array}
$ & AA & $4q_{1}+4q_{2}$ & $8$ & $\left( 1,1\right) $ & $q_{1}+q_{2}$ & $2$
& $\left( 1,1\right) $ \\ \hline
$
\begin{array}{c}
q_{1}\leq \frac{3}{5} \\
q_{2}\leq \frac{3}{5}
\end{array}
$ & FF & $6q_{1}+6q_{2}$ & $\frac{108}{17}$ & $
\begin{array}{c}
\left( \frac{3}{5},\frac{39}{85}\right)  \\
\left( \frac{39}{85},\frac{3}{5}\right)
\end{array}
$ & $3q_{1}+3q_{2}$ & $\frac{54}{17}$ & $
\begin{array}{c}
\left( \frac{3}{5},\frac{39}{85}\right)  \\
\left( \frac{39}{85},\frac{3}{5}\right)
\end{array}
$ \\ \hline
$
\begin{array}{c}
\frac{3}{5}\leq q_{1} \\
q_{2}\leq \frac{3q_{1}+6}{17}
\end{array}
$ & AF & $10q_{2}$ & $\frac{90}{17}$ & $\left( 1,\frac{9}{17}\right) $ & $
7q_{2}-3q_{1}$ & $\frac{24}{17}$ & $\left( \frac{3}{5},\frac{39}{85}\right) $
\\ \hline
$
\begin{array}{c}
q_{1}\leq \frac{3q_{2}+6}{17} \\
\frac{3}{5}\leq q_{2}
\end{array}
$ & FA & $10q_{1}$ & $\frac{90}{17}$ & $\left( \frac{9}{17},1\right) $ & $
7q_{1}-3q_{2}$ & $\frac{24}{17}$ & $\left( \frac{39}{85},\frac{3}{5}\right) $
\\ \hline
\end{tabular}
\end{array}
\end{equation*}
We can draw plots (see figure 2 and 3) that represent the payoff obtained by
the third player when he chooses different levels of attack. Comparing the
values at the points where the maxima are reached, the optimal choice of
attack levels is $q_{1}=1$ and $q_{2}=1$ if $l=8.$ Such a strategy of the
third player forces the first two players to form (or maintain) an alliance.
If $l=5,$ we see that the third player obtains maximum payoff at the points $
\left( \frac{3}{5},\frac{39}{85}\right) $ or $\left( \frac{39}{85},\frac{3}{5
}\right) $ but if the levels of attack are set to be exactly at these values
the payoff bi-matrix~(\ref{3Players_new_payoffs}) for the two firms is
non-generic and there exist an infinite number of Nash Equilibria for this
game. It includes the \textquotedblleft Ally\textquotedblright
-\textquotedblleft Ally\textquotedblright\ Nash Equilibrium which, if it is
played by the first two players, gives them the highest payoffs. The third
player obtains the payoff of $\frac{54}{17}$ only if the first two players
choose to fight. Therefore to prevent the first and the second players from
swapping between Nash Equilibria the third player must not choose $\left(
\frac{3}{5},\frac{39}{85}\right) $ or $\left( \frac{39}{85},\frac{3}{5}
\right) $ but choose $\left( \frac{3}{5}-\delta _{1},\frac{39}{85}-\delta
_{2}\right) $ or $\left( \frac{39}{85}-\delta _{1},\frac{3}{5}-\delta
_{2}\right) $ such that these points are still in (\textquotedblleft
Fight\textquotedblright -\textquotedblleft Fight\textquotedblright ) Nash
Equilibrium region and $\delta _{1}$ and $\delta _{2}$ are very small. We
can see that for this example the optimal choice of parameters $q_{1}$ and $
q_{2}$ does not exist. The best strategy for the third player would be to
break the alliance by using appropriate levels of attack. In this case a
moderate, asymmetric attack will achieve higher payoff than a strong
(symmetric or asymmetric) attack.
\begin{equation*}
\begin{array}{ccc}
\begin{tabular}{c}
{\unitlength=0.5400pt \begin{picture}(265.00,290.00)(0.00,0.00)
\put(140.00,260.00){\framebox(110.00,20.00){$AA$, $M$, $FF$}}
\put(140.00,260.00){\vector(0,-1){130.00}}
\put(200.00,80.00){\makebox(0.00,0.00){$AF$}}
\put(70.00,80.00){\makebox(0.00,0.00){$FF$}}
\put(190.00,190.00){\makebox(0.00,0.00){$AA$}}
\put(70.00,190.00){\makebox(0.00,0.00){$FA$}}
\put(260.00,30.00){\makebox(0.00,0.00){$q_1$}}
\put(30.00,260.00){\makebox(0.00,0.00){$q_2$}}
\put(230.00,10.00){\makebox(0.00,0.00){$1.0$}}
\put(10.00,230.00){\makebox(0.00,0.00){$1.0$}}
\put(10.00,190.00){\makebox(0.00,0.00){$0.8$}}
\put(10.00,150.00){\makebox(0.00,0.00){$0.6$}}
\put(10.00,110.00){\makebox(0.00,0.00){$0.4$}}
\put(10.00,70.00){\makebox(0.00,0.00){$0.2$}}
\put(190.00,10.00){\makebox(0.00,0.00){$0.8$}}
\put(150.00,10.00){\makebox(0.00,0.00){$0.6$}}
\put(110.00,10.00){\makebox(0.00,0.00){$0.4$}}
\put(70.00,10.00){\makebox(0.00,0.00){$0.2$}}
\put(110.00,110.00){\line(1,6){20.00}}
\put(110.00,110.00){\line(4,1){120.00}}
\put(230.00,230.00){\line(0,-1){200.00}}
\put(30.00,230.00){\line(1,0){200.00}}
\put(150.00,150.00){\line(0,-1){120.00}}
\put(30.00,150.00){\line(1,0){120.00}} \put(30.00,230.00){\line(-1,0){5.00}}
\put(30.00,190.00){\line(-1,0){5.00}} \put(30.00,150.00){\line(-1,0){5.00}}
\put(30.00,110.00){\line(-1,0){5.00}} \put(30.00,70.00){\line(-1,0){5.00}}
\put(230.00,30.00){\line(0,-1){5.00}} \put(190.00,30.00){\line(0,-1){5.00}}
\put(150.00,30.00){\line(0,-1){5.00}} \put(110.00,30.00){\line(0,-1){5.00}}
\put(70.00,30.00){\line(0,-1){5.00}} \put(30.00,30.00){\vector(1,0){220.00}}
\put(30.00,30.00){\vector(0,1){220.00}} \end{picture}} \\
$
\begin{array}{c}
\text{Figure 1:} \\
\text{NE regions for player 1 and 2.}
\end{array}
$
\end{tabular}
&
\begin{tabular}{c}
{\unitlength=0.5400pt \begin{picture}(265.00,285.00)(0.00,0.00)
\put(140.00,260.00){\framebox(110.00,20.00){$4q_1+4q_2$}}
\put(140.00,260.00){\vector(0,-1){130.00}}
\put(200.00,80.00){\makebox(0.00,0.00){$10q_2$}}
\put(80.00,80.00){\makebox(0.00,0.00){$6q_1+6q_2$}}
\put(185.00,190.00){\makebox(0.00,0.00){$4q_1+4q_2$}}
\put(70.00,190.00){\makebox(0.00,0.00){$10q_1$}}
\put(260.00,30.00){\makebox(0.00,0.00){$q_2$}}
\put(30.00,260.00){\makebox(0.00,0.00){$q_2$}}
\put(230.00,10.00){\makebox(0.00,0.00){$1.0$}}
\put(10.00,230.00){\makebox(0.00,0.00){$1.0$}}
\put(10.00,190.00){\makebox(0.00,0.00){$0.8$}}
\put(10.00,150.00){\makebox(0.00,0.00){$0.6$}}
\put(10.00,110.00){\makebox(0.00,0.00){$0.4$}}
\put(10.00,70.00){\makebox(0.00,0.00){$0.2$}}
\put(190.00,10.00){\makebox(0.00,0.00){$0.8$}}
\put(150.00,10.00){\makebox(0.00,0.00){$0.6$}}
\put(110.00,10.00){\makebox(0.00,0.00){$0.4$}}
\put(70.00,10.00){\makebox(0.00,0.00){$0.2$}}
\put(110.00,110.00){\line(1,6){20.00}}
\put(110.00,110.00){\line(4,1){120.00}}
\put(230.00,230.00){\line(0,-1){200.00}}
\put(30.00,230.00){\line(1,0){200.00}}
\put(150.00,150.00){\line(0,-1){120.00}}
\put(30.00,150.00){\line(1,0){120.00}} \put(30.00,230.00){\line(-1,0){5.00}}
\put(30.00,190.00){\line(-1,0){5.00}} \put(30.00,150.00){\line(-1,0){5.00}}
\put(30.00,110.00){\line(-1,0){5.00}} \put(30.00,70.00){\line(-1,0){5.00}}
\put(230.00,30.00){\line(0,-1){5.00}} \put(190.00,30.00){\line(0,-1){5.00}}
\put(150.00,30.00){\line(0,-1){5.00}} \put(110.00,30.00){\line(0,-1){5.00}}
\put(70.00,30.00){\line(0,-1){5.00}} \put(30.00,30.00){\vector(1,0){220.00}}
\put(30.00,30.00){\vector(0,1){220.00}} \end{picture}} \\
$
\begin{array}{c}
\text{Figure 2:} \\
\text{3 player's payoffs }l\text{=8.}
\end{array}
$
\end{tabular}
&
\begin{tabular}{c}
{\unitlength=0.5400pt \begin{picture}(265.00,285.00)(0.00,0.00)
\put(140.00,260.00){\framebox(110.00,20.00){$q_1+q_2$}}
\put(140.00,260.00){\vector(0,-1){130.00}}
\put(190.00,80.00){\makebox(0.00,0.00){$7q_2-3q_1$}}
\put(80.00,80.00){\makebox(0.00,0.00){$3q_1+3q_2$}}
\put(185.00,190.00){\makebox(0.00,0.00){$q_1+q_2$}}
\put(80.00,190.00){\makebox(0.00,0.00){$7q_1-3q_2$}}
\put(260.00,30.00){\makebox(0.00,0.00){$q_1$}}
\put(30.00,260.00){\makebox(0.00,0.00){$q_2$}}
\put(230.00,10.00){\makebox(0.00,0.00){$1.0$}}
\put(10.00,230.00){\makebox(0.00,0.00){$1.0$}}
\put(10.00,190.00){\makebox(0.00,0.00){$0.8$}}
\put(10.00,150.00){\makebox(0.00,0.00){$0.6$}}
\put(10.00,110.00){\makebox(0.00,0.00){$0.4$}}
\put(10.00,70.00){\makebox(0.00,0.00){$0.2$}}
\put(190.00,10.00){\makebox(0.00,0.00){$0.8$}}
\put(150.00,10.00){\makebox(0.00,0.00){$0.6$}}
\put(110.00,10.00){\makebox(0.00,0.00){$0.4$}}
\put(70.00,10.00){\makebox(0.00,0.00){$0.2$}}
\put(110.00,110.00){\line(1,6){20.00}}
\put(110.00,110.00){\line(4,1){120.00}}
\put(230.00,230.00){\line(0,-1){200.00}}
\put(30.00,230.00){\line(1,0){200.00}}
\put(150.00,150.00){\line(0,-1){120.00}}
\put(30.00,150.00){\line(1,0){120.00}} \put(30.00,230.00){\line(-1,0){5.00}}
\put(30.00,190.00){\line(-1,0){5.00}} \put(30.00,150.00){\line(-1,0){5.00}}
\put(30.00,110.00){\line(-1,0){5.00}} \put(30.00,70.00){\line(-1,0){5.00}}
\put(230.00,30.00){\line(0,-1){5.00}} \put(190.00,30.00){\line(0,-1){5.00}}
\put(150.00,30.00){\line(0,-1){5.00}} \put(110.00,30.00){\line(0,-1){5.00}}
\put(70.00,30.00){\line(0,-1){5.00}} \put(30.00,30.00){\vector(1,0){220.00}}
\put(30.00,30.00){\vector(0,1){220.00}} \end{picture}} \\
$
\begin{array}{c}
\text{Figure 3:} \\
\text{3 player's payoffs }l\text{=5.}
\end{array}
$
\end{tabular}
\end{array}
\end{equation*}

It is possible to show that (for $v=5,$ $x=2,$ $y=2,$ $f=2,$ $c=3,$ $
\varepsilon =1,$ $\epsilon =1$) if the difference between value of the
market $l$ and the price of the attack $\delta $\ is

\begin{itemize}
\item less than $-1$ (note that in this case the actual cost of the attack
is $\sigma -\epsilon $ so the difference between value of the market $l$ and
the cost of the attack is less than $0)$ then it is optimal not to attack,
that is $q_{1}=0$ and $q_{2}=0;$

\item between $-1$ and $\frac{13}{4}$ then the optimal choice of parameters $
q_{1}$ and $q_{2}$ does not exist and the third player should follow the
approach described above;

\item greater than $\frac{13}{4}$ then the optimal choice of attack levels
is $q_{1}=1$ and $q_{2}=1$; this choice of the third player forces the first
and the second players to form (or maintain) an alliance.
\end{itemize}

\noindent The proof can be obtained using item-by-item examination of all
possible cases. Similar conditions can be obtained for any generic set of
parameters.

\section{Summary and discussions.}

This simple example leads to a few important conclusions.

Firstly, as it can be seen from the results summarized in figure 1, the
successful formation of an alliance greatly depends on the position of the
players on the Nash Equilibrium diagram (figure 1). As in a single
interaction prisoners' dilemma in the absence of pressure cooperative
behaviour is not a Nash Equilibrium and alliances which are formed under
such conditions are not stable. However under the threat of an attack by
another player (or under unfavorable conditions) the players may be induced
to cooperate. It is clear that cooperative behaviour becomes a Nash
Equilibrium of the game~(\ref{3Players_new_payoffs}) because an attack on
the players changes their payoffs. But on the other hand, if, in modelling,
such changes are not taken into account we would obtain the result that
cooperation is not rational when, in fact, it is. In the considered model
strong pressure, where its level does not vary significantly between the
players will stabilize the possibility of forming an alliance. On the other
hand, an asymmetric, weak or moderate pressure does not provide an incentive
for cooperation.

In this instance the possibility for stabilizing an alliance arises by
applying a careful managing strategy. For example, assume the first player
position and suppose that $q_{1}=1/5$ (other values of $q_{1}$ can be
treated in a similar way).\ Assume also that the first player is interested
in forming an alliance. The idea is that the first player may be able to
change its own value of $q_{1}$ (for example by engaging in unilateral
commitments up to some extent)\ in such a way that the alliance becomes a
Nash Equilibrium. Three different approaches must be taken in such a
situation depending on the value on $q_{2}.$ If $0\leq q_{2}\leq 3/7$\ ($3/7$
appears as the point of intersection of $q_{1}=\left( 3q_{2}+6\right) /17$
and $q_{2}=\left( 3q_{1}+6\right) /17$) both players are in the
\textquotedblleft Fight\textquotedblright -\textquotedblleft
Fight\textquotedblright\ region and the pressure on the second player is not
high enough to promote a stable alliance. In this case the first player's
best strategy would be \textquotedblleft Fight\textquotedblright . The
unilateral commitments would only shift the players position into
\textquotedblleft Ally\textquotedblright -\textquotedblleft
Fight\textquotedblright\ region and the first company would suffer losses.
If $3/7<q_{2}\leq 3/5$ both players are still in the \textquotedblleft
Fight\textquotedblright -\textquotedblleft Fight\textquotedblright\ region
but the pressure on the second player is high enough to allow for the
possibility of an alliance. As can be seen from the figure~1, the first
company may change its own value of $q_{1}$ in such a way that
\textquotedblleft Ally\textquotedblright -\textquotedblleft
Ally\textquotedblright\ becomes a Nash Equilibrium. The unilateral
commitments in this case can lead to ensuring an alliance, though it should
be noted that the level of such commitments must be carefully assessed in
order to avoid shifting the players even further to the right on the Nash
Equilibrium diagram which would result in \textquotedblleft
Ally\textquotedblright -\textquotedblleft Fight\textquotedblright\
equilibrium and alliance failure. If $3/5\leq q_{2}$ the second player is
under high pressure and is likely to cooperate. The main threat to the
alliance is that the first player might prefer to use such an opportunity to
maximize its immediate payoff jeopardizing the future of the alliance. To
avoid such a contempt (for example the first company might be interested in
a strategic alliance which is expected to be highly beneficial in the
future) the first player might engage in unilateral commitments to stabilize
the alliance. As we can see engaging in unilateral commitments might be
highly beneficial for formation and maintaining of an alliance if used
appropriately. Note that it is assumed that the parameters of the model can
be estimated accurately enough. Although it is always possible to allow for
a margin of error, such an error must not be neglected when a strategy is
chosen as it might significantly change the strategy. The analysis of the
risks arising from this situation must be done, however we do not address
this issue in this paper.

The alliances must be frequently reassessed and managed$^{1}.$ In this
instance the results of the model can also be used for projections of
possible outcomes of an alliance. The estimates of future threats and
pressures must be made. If a company anticipates the position of an alliance
to leave the \textquotedblleft Ally\textquotedblright -\textquotedblleft
Ally\textquotedblright\ region it should be assessed if it is possible to
save the alliance by changing the values of $q_{1}$ or (and) $q_{2}.$ If it
is possible, careful management might save the alliance. If it is not the
case the company might save itself from heavy losses in the future by
withdrawing from an alliance prior to its failure.

Another result of the above analysis concerns the third player's strategy.
As we have seen from the examples, depending on the relationship between the
value of the market and the costs of the attack, the third player may either
wish to split the alliance or it may be better for the third player to
engage in the strongest symmetric attack. A strong attack, where the level
of attack does not vary significantly between the target firms, will
stabilize an alliance. An asymmetric, weak or moderate attack will result in
an alliance failure if the alliance is not managed well. It must be noticed
though that\ in this situation there exist mechanisms implying that good
management can always ensure that the alliance withstands an attack. The
strategy here is the same as when $3/5\leq q_{2}:$ the weakly attacked
player (let us say player one) must increase the value of $q_{1}$ to shift
the players position to the right on the Nash Equilibrium diagram. This
opportunity might be important then the third player represents hostile
conditions for one of the partners which are of a temporary nature. In this
situation the temporary sacrifice of another player might save the alliance
from failure bringing strategic benefits in the future.

As it can be seen from the example we have considered, a simple idea of
including environmental conditions into consideration provides several
important implications which would be overseen otherwise. In the considered
example, in addition to explaining the mechanisms which might be responsible
for formation of alliances, one of the important benefits is to allow us to
distinguish between two \textquotedblleft Fight\textquotedblright
-\textquotedblleft Fight\textquotedblright\ situations. In one unilateral
commitments are beneficial and in another would imply losses. These allow us
to use the proposed approach for determining successful strategies for
forming and maintaining alliances.

1. R. Gulati, T. Khanna and N. Nohria (1994) Unilateral commitments and the
importance of process in alliances, \textit{Sloan Management Rev.,} \textbf{
35,} 61--69.

2. S.H. Park and G.R. Ungson (2001) Interfirm Rivalry and Managerial
Complexity: A Conceptual Framework of Alliance Failure, \textit{Organisation
Science,} \textbf{12} (1), 37-53.

3. E. Anderson (1990) Two Firms, One Frontier: On Assessing Joint Venture
Performance, \textit{Sloan Management Rev.,} \textbf{31} (2), 19-30.

4. J.M. Geringer and L. Hebert (1989) Control and Performance of
International Joint Ventures, \textit{J. of International Business Studies,}
\textbf{20} (2), 235-254.

5. J.M. Geringer and L. Hebert (1989) Measuring Performance of International
Joint Ventures, \textit{J. of International Business Studies,} \textbf{22}
(2), 249-263.

6. K.R. Harrigan (1986) Managing for Joint Venture Success, Lexington, MA:
Lexington Books.

7. J.F. Hennart (1988) A Transition Cost Theory of Equity Joint Ventures,
\textit{Strategic Management J.,} \textbf{9} (4), 361-374

8. A. Parkhe (1993) "Messy" Research, Methodological Predispositions, and
Theory Development in International Joint Ventures, \textit{Academy of
Management Rev.,} \textbf{18} (2), 227-268.

9. Y. Zhang and N. Rajagopalan (2002)\ Inter-partner Credible Threat in
International Joint Ventures: An Infinitely Repeated Prisoner's Dilemma
Model, \textit{J. of International Business Studies,} \textbf{33 }(3),
457-478.

10. J. Nash (1950) Equilibrium points in n-person games, \textit{Proc. Nat.
Acad. Sci.,} \textbf{36,} 48--49.

11. D. Fudenberg and J. Tirole (1991) Game theory, The MIT Press, Cambridge
Massachusetts USA.

12. J. von Neumann and O. Morgenstern (1944) Theory of games and economic
behaviour, Princeton Univ. Press, Princeton, NJ.

13. R. Axelrod and W. D. Hamilton (1981) The evolution of co-operation,
\textit{Science,} \textbf{211,} 1390--1396.

14. M. Nowak and K. Sigmund (1993) A strategy of win-stay, lose-shift that
outperforms tit-for-tat in the prisoner's dilemma game, \textit{Nature,}
\textbf{364,} 56--58.

15. J. Lorberaum (1994) No strategy is evolutionary stable, \textit{J. of
Theor. Biol.,} \textbf{168,} 117--130.

16. H. Gintis (2000) Game theory evolving: a problem-centered introduction
to modeling strategic interaction, Princeton Univ. Press, Princeton, New
Jersey.

17. R. Hoffmann (2001) The ecology of cooperation, \textit{Theory and
Decisions,} \textbf{50 }(2), 101-118.

18. D. P. Kraines and V. Y. Kraines (2000) Natural selection on memory-one
strategies for the iterated prisoner's dilemma, \textit{J. theor. Biol.,}
\textbf{203,} 335-355.

19. J.Y. Wakano and N. Yamamura (2001) A simple learning strategy that
realizes robust cooperation better than Pavlov in iterated prisoners'
dilemma, \textit{J. of Ethology,} \textbf{19 }(1) 1-8.

20. M.A. Nowak and R.M. May (1992) Evolutionary games and spatial chaos,
\textit{Nature,} \textbf{359} 826-829.

21. Y.F. Lim, K. Chen and C. Jayaprakash (2002) Scale invariant behaviour in
a spatial game of prisoners' dilemma, \textit{Physical Review E,} \textbf{65
}(2), art. no. 026134,.

22. H.J. Jensen (1998) Self-organized criticality: emergent complex
behaviour in physical and biological systems, \textit{Cambridge lecture
notes in physics,} \textbf{10}, Cambridge Univ. Press.

23. M.N. Szilagyi and Z.C. Szilagyi (2002) Non-trivial solutions to the
N-person prisoners' dilemma, \textit{System Res\textit{earch }and
Behavioural Science,} \textbf{19 }(3), 281-290.

24. M. Kandori (2001) Introduction to repeated games with private
monitoring, \textit{J. of Economic Theory,} \textbf{102,} 1-15.

25. V. N. Kolokoltsov (1998) Nonexpansive maps and option pricing theory,
\textit{Kybernetika,} \textbf{34} (6), 713--724.

\end{document}

config: arxiv


TITLE: If $f \colon \mathbb{R}^n \rightarrow \mathbb{R}$ is differentiable and vanishing, it has $0$ gradient somewhere.
QUESTION [3 upvotes]: I'm interested in ideas for improving and fixing the proof I wrote for the following theorem:

Let $f \colon \mathbb{R}^n \to \mathbb{R} $ be differentiable, and $ \lim_{\| x \| \to \infty} f(x) = 0 $. Then $\nabla f(x) = 0 $ for some $x \in \mathbb{R}^n$.

Here's the idea of the proof. First, since $f$ is differentiable, it is continuous.
As  $ \lim_{\| x \| \to \infty} f(x) = 0 $, $\forall \varepsilon > 0, \exists r \in \mathbb{R} : |f(x) - 0| < \varepsilon$ whenever $\| x \| > r$.
If we choose $D = \{x \in \mathbb{R}^n : \| x \| \leq r \}$, we can use the theorem that states that all continuous functions are bounded inside closed sets. In other words, there's a supremum of $|f(x)|$ in $D$.
Then we just look at the cases: if $f(x) = 0$, so its gradient is always 0 and we're done.
If $f$ varies in the set $D$, there exist $a,b \in D$ such that $f(a) \neq f(b)$, ie. $\exists \varepsilon_2 > 0$ so $| f(a) - f(b) | > \varepsilon_2 $.
If we choose $\varepsilon_2 > \varepsilon$, $|f(x)|$ attains greater values in $D$ than outside it, and if we choose $c$ to be a point such that $$f(c) = \sup{\{f(x) : x \in D\}}$$ Then $|f(x)| \leq |f(c)|\quad \forall x \in D$ and as $f$ is differentiable, $\nabla f(c) = 0$.
There are more than a few issues I have with the formulation of the proof. First, "$f$ attains greater values in $D$ than outside it" seems a little ambiguous. Then the choosing of $c$ in a convenient way after having talked about it at such length... Additionally, I'd like to use the definition of differentiability that states that if $f$ is differentiable, it can be represented as
$$f(x_0+h) = f(x_0) + Df(x_0)h + \varepsilon(h)\| h \|,\quad h \in \mathbb{R}^n $$
where $\varepsilon(h)\| h \| \to 0$ as $\| h \| \to 0$, and where $Df(x)$ is the gradient in this case, or the Jacobian in a more general case. I'm almost certain you could bound the gradient $Df(c)$ to $0$ somehow using that definition, because it gives you a semi-explicit expression, instead of the verbal hand-waving I'm facing.
There might've also been a method much simpler than this, but I couldn't exactly employ the mean value theorem easily here with the whole open domain. Maybe using the $D$ I defined there would've worked.

REPLY [1 votes]: I'll assume $f$ is bounded since you seem to get that part.
Let $\alpha = \inf_{x \in \mathbb{R}^n} f(x)$ and $\beta = \sup_{x \in \mathbb{R}^n} f(x)$.
Then there are sequences $\{x_k\}$ and $\{y_k\}$ in $\mathbb{R}^n$ such that $\alpha = \lim_{k \rightarrow \infty} f(x_k)$ and $\beta = \lim_{k \rightarrow \infty} f(y_k)$.
If both $x_k$ and $y_k$ are unbounded, then $\alpha = \beta = 0$, so that $f=0$.
Suppose $x_k$ bounded. Then it has a convergent subsequence $x_{k_p} \rightarrow x_{\alpha}$. Hence, by continuity, $\alpha = f(x_{\alpha})$.
If $y_k$ is bounded we conclude, analogously, that $\beta = f(x_{\beta})$.
Therefore, $f$ always has a global minimum/maximum and at this point, $\nabla f$ is zero.


TITLE: Prove that the least upper bound of $\mathcal F$ is $\bigcup\mathcal F$ and the greatest lower bound of $\mathcal F$ is $\bigcap\mathcal F$.
QUESTION [4 upvotes]: Not a duplicate of this or this.
This is exercise $4.4.23$ from the book How to Prove it by Velleman $($$2^{nd}$ edition$)$:
Prove theorem $4.4.11.$
Theorem $4.4.11.$ Suppose $A$ is a set, $\mathcal F\subseteq \mathscr P(A)$, and $\mathcal F\neq \emptyset$. Then the least upper bound of $\mathcal F$ $($in the subset partial order$)$ is $\bigcup\mathcal F$ and the greatest lower bound of $\mathcal F$ is $\bigcap\mathcal F$.
Here is my proof:
Let $F$ be an arbitrary element of $\mathcal F$. Let $x$ be an arbitrary element of $F$. Ergo clearly $x\in\bigcup\mathcal F$. Since $x$ is arbitrary, $F\subseteq\bigcup\mathcal F$. Therefore if $F\in\mathcal F$ then $F\subseteq\bigcup\mathcal F$. Since $F$ is arbitrary, $\bigcup\mathcal F$ is an upper bound for $\mathcal F$. Let $U$ be the set of all upper bounds for $\mathcal F$ and let $X$ be an arbitrary element of $U$. Let $y$ be an arbitrary element of $\bigcup\mathcal F$. So we can choose some $G_0\in\mathcal F$ such that $y\in G_0$. Since $X$ is an upper bound for $\mathcal F$ then $G_0\subseteq X$. Since $y\in G_0$, $y\in X$. Since $y$ is arbitrary, $\bigcup\mathcal F\subseteq X$. Thus if $X\in U$ then $\bigcup\mathcal F\subseteq X$. Since $X$ is arbitrary, $\bigcup\mathcal F$ is the smallest element of $U$ and hence the least upper bound for $\mathcal F$.
Let $F$ be an arbitrary element of $\mathcal F$. Let $x$ be an arbitrary element of $\bigcap\mathcal F$. Ergo clearly $x\in F$. Therefore if $F\in\mathcal F$ then $\bigcap\mathcal F\subseteq F$. Since $F$ is arbitrary, $\bigcap\mathcal F$ is a lower bound for $\mathcal F$. Let $L$ be the set of all lower bounds for $\mathcal F$ and let $Y$ be an arbitrary element of $L$. Let $y$ be an arbitrary element of $Y$. Since $Y$ is a lower bound for $\mathcal F$, $Y\subseteq F$. Since $y\in Y$, $y\in F$. Since $F$ is arbitrary, $y\in\bigcap\mathcal F$. Since $y$ is arbitrary, $Y\subseteq \bigcap\mathcal F$. Thus if $Y\in L$ then $Y\subseteq \bigcap\mathcal F$. Since $Y$ is arbitrary, $\bigcap\mathcal F$ is the biggest element of $L$ and hence the greatest lower bound for $\mathcal F$.
$Q.E.D.$
Is my proof valid$?$
Thanks for your attention.

REPLY [3 votes]: Your proves look good. You could gain in clarity by explaining upfront what you're doing.
For example for least upper bond.
Let's first prove that $\bigcup \mathcal F$ is an upper bound.
Proof...
And now let's prove that $\bigcup \mathcal F$ is less than any upper bound $U$.
Proof...
This allows to conclude that $\bigcup \mathcal F$ is the least upper bound.


TITLE: How to prove fourier spectrum symmetrical at k=0
QUESTION [0 upvotes]: There is this question,
Let f(x) be a real function whose Fourier transform is F(k).
Prove that the Fourier spectrum (i.e., the graph of |F(k)|^2 versus k) is symmetric around k = 0.
How do I prove it???

REPLY [0 votes]: I don't think the statement is true. Take any $v\in \mathcal{S}$ (Schwartz space) with support contained in $\mathbb{R}_+$. Since $\mathcal{F}:\mathcal{S}\to\mathcal{S}$, there is $u\in\mathcal{S}$ such that $v=\mathcal{F}u$. Still, $|v|^2$ is not an even function...


TITLE: On Lyapunov stability of a solution
QUESTION [2 upvotes]: I have recently encountered the following exercise: prove or disprove that the solution of the ODE $\dot x = -\frac{2x}{t} + t^2$ that satisfies $x(1)=1$ is Lyapunov stable. I have proved that the solution is stable, however, the correct answer (as per my teacher) is the opposite.
My proof is as follows:
$$\begin{aligned}
\dot x &= -\frac{2x}{t} + t^2 \\
t^2\dot x + 2xt &= t^4 \\
t^2\dot x + x(t^2)' &= t^4 \\
(t^2 x)' &= t^4 \\
t^2 x &= \frac{t^5}{5} + C \\
x &= \frac{t^3}{5} + \frac{C}{t^2} \\
\end{aligned}$$
The solution that satisfies $x(1)=1$ is $x=\varphi(t)=\cfrac{t^3}{5} + \cfrac{4}{5t^2}$.
The definition of Lyapunov stability:
$$\forall \varepsilon > 0 \ \ \exists \delta > 0 \ \ |x(t_0) - \varphi(t_0)|< \delta \implies \forall t > t_0 \ \ |x(t) - \varphi(t)| < \varepsilon$$
$$|x(t_0) - \varphi(t_0)|< \delta \implies \left|\frac{1}{5} + \frac{C}{t^2} - \frac{1}{5} - \frac{4}{5}\right| < \delta \implies \left|C - \frac{4}{5}\right| < \delta$$
$$|x(t) - \varphi(t)| < \varepsilon \implies \left|\frac{t^3}{5} + \frac{C}{t^2} - \frac{t^3}{5} - \frac{4}{5t^2}\right| < \varepsilon \implies \left|\frac{1}{t^2}\left(C-\frac{4}{5}\right)\right| < \varepsilon$$
Let $\delta=\varepsilon$. Then
$$\left|\frac{1}{t^2}\left(C-\frac{4}{5}\right)\right| < \varepsilon \implies \varepsilon\left|\frac{1}{t^2}\right| < \varepsilon$$
, which holds.

REPLY [1 votes]: You obtained the following equation
$$\frac{d}{dt}(t^2 x)  = t^4 \quad (1) $$
then you found the following general solution:
$$t^2 x(t) = \frac{t^5}{5} + C $$
which is also true, but you can not treat $C$ as an initial condition of the original differential equation. To use the defintion of stability, you sould integrate both sides of Equaiton (1) form $t_0$ to $t\geq t_0$. Integrating (1) gives:
$$t^2x(t)-t_0^2x(t_0)=\frac{1}{5}t^5-\frac{1}{5}t_0^5$$
or equivilanetly:
$$x(t)=\frac{t_0^2}{t^2}x(t_0)+\frac{1}{5}t^3-\frac{1}{5t^2}t_0^5$$
To prove the stability, the following should hold for any   $\epsilon$ .....
$$\|x(t)-x(t_0)||=\bigg\|(\frac{t_0^2}{t^2}-1)x(t_0)+\frac{1}{5}t^3-\frac{1}{5t^2}t_0^5\bigg\|\leq\epsilon \qquad (2)$$
But if there exists at least one $\epsilon$ such that Equaiton (2) is not satisfied for all initial conditions then the system is not stable. Slecet $\epsilon =1$, then one can see that $\bigg\|(\frac{t_0^2}{t^2}-1)x(t_0)+\frac{1}{5}t^3-\frac{1}{5t^2}t_0^5\bigg\|$ is not bounded because of $t^3$.


TITLE: Eigenvalue distribution of real anti-symmetric Gaussian random matrices
QUESTION [1 upvotes]: Let $A_{ij} = - A_{ji}$ be a $n \times n$ matrix with real entries distributed according to a Gaussian distribution with zero mean and standard deviation $\sigma$. What is the eigenvalue distribution of such matrices? I am mostly interested in the case where $n\rightarrow\infty$. If the matrices were symmetric, rather than anti-symmetric, then the answer to this question in the $n \rightarrow \infty$ limit would be the Wigner semi-circle law.

REPLY [1 votes]: I can't find a reference but based on a few simulations the imaginary part of the eigenvalues (the real part is of-course zero) seem to follow the semi-circle law as well if the entries are picked independently from the standard normal distrbution. Here is a quick python script:
%matplotlib inline   # For use in a Jupyter notebook
import numpy as np
import matplotlib.pyplot as plt

N=100
mu = 0
sigma = 1

matlist = list()
eval_list = list()

for i in range(1,1000):
    mat = sigma*np.random.randn(N,N) + mu
    matlist.append((mat - mat.T)/2)

for matrix in matlist:
    eigs, vecs = np.linalg.eig(matrix)
    eval_list.extend(map(lambda k: np.imag(k), eigs))

plt.figure()
plt.hist(eval_list)
plt.show()


TITLE: How to maximize the profit for the given equation
QUESTION [2 upvotes]: It is a maximize profit question. Basically:

There is a play which costs $180$
Each attendee costs $0.4$
Ticket price affects the overall attendance. When the ticket price is $5$, then there are $120$ attendees. If the ticket price is lowered by $0.1$, then there are $15$ more attendees.

How can I model this problem?
How can I maximize the profit? I believe it has something to do with derivatives, but I don't know how to approach it.

REPLY [1 votes]: Fixed cost of the play is $180$, variable cost is $0.4$ by attendee.
Total cost is the fixed cost plus the variable cost multiplied by the number of attendees:
$$c=180+0.4n$$
You can express the number of attendees as a function of ticket price:
$$n=120+15\times\frac{5-p}{0.1}$$
Total revenue is the ticket price multiplied by number of attendees:
$$r=pn$$
Profit is the total revenue minus the total cost:
$$
\begin{align}
 \pi&=r-c\\
 \pi&=pn-(180+0.4n)\\
 \pi&=pn-180-0.4n\\
 \pi&=(p-0.4)n-180\\
 \pi&=(p-0.4)\left(120+15\times\frac{5-p}{0.1}\right)-180\\
 \pi&=-150p^2+930p-528
\end{align}
$$
You get a quadratic function of profit depending on the ticket price, whose maximum you can easily get by calculating the coordinates of the vertex of the quadratic parabola described by the function:
$$
V\left(-\frac{b}{2a},\frac{b^2-4ac}{4a}\right)
$$
In this case, the profit reaches its maximum of:
$$\pi=\frac{b^2-4ac}{4a}=\frac{930^2-4(-150)(-528)}{4(-150)}=913.5$$
at the ticket price of:
$$p=-\frac{b}{2a}=-\frac{930}{2(-150)}=3.1$$


TITLE: Setting up this volume integral
QUESTION [0 upvotes]: I just have a quick question on setting up a volume integral of a region bounded by $y = \sin(x)$ and $y = -\sin(x)$ for $0\leq x\leq\pi$ about the x-axis. I keep getting zero when I set it up as $x = \sin^{-1}(y)$ and similar for the outer radius, but I don't know why. Any help is appreciated, thanks, should just be a small problem.

REPLY [2 votes]: Remember that $\arcsin(x)$ have image $y\in\left[-\frac{\pi}{2},\frac{\pi}{2}\right]$, but you are searching for $0\leq x\leq \pi$.
If you take $0\leq x\leq \frac{\pi}{2}$, then, we have the radius of the bigger disk (in respect to the line $x=5$) is:
$$5-\arcsin(y)$$
The smaller disk, instead has radius:
$$5-\pi-\arcsin(y)$$
Note that here, I have used $y$ because the disk will have heigth $dy$. So:
$$V=\int_{0}^{1}\pi\left((5-\arcsin(y))^2-(5-\pi+\arcsin(y))^2\right)dy=20\pi-4\pi^2$$


TITLE: Prove that the Markov chain is irreducible and recurrent
QUESTION [1 upvotes]: Show that if a Markov chain $(X_{n})_{n}$ with transition matrix $P$ admits a $P-$invariant probability $\lambda$ (i.e. $\lambda=\lambda \cdot P$), then the Markov chain is irreducible and recurrent.
I am trying to show that: $U(x,x)=+\infty,$ $\forall x \in E$ s.t. $\lambda(x)>0$, where $U(x,x)=\sum_{n \geq 1}P_{n}(x,x)=\sum_{n \geq 1}\mathbb{P}(X_{n}=x|X_{0}=x)$. For this, I think I need to use that $U(y,x) \leq U(x,x)$, $\forall y \in E$, but I don't know how to proceed.
I wonder if maybe the statement is only true if the state space $E$ is finite...

REPLY [1 votes]: Not true even when the state space is finite. Let $\{X_n\}$ have state space $\{0,1\}$ and suppose both $0$ and $1$ are absorbing states. The transition matrix is the identity matrix. Then $(\frac  1 2,\frac  1 2)$ is an invariant distribution but the chain is not irreducible.