TITLE: Relative motion and magnetic field production
QUESTION [2 upvotes]: We have Ampere's circuital law
$$\oint \vec B\cdot dl=\mu_0I+d\phi/dt \tag{1}$$
stating that every current-carrying wire produces a magnetic field. And so should a charge moving with constant velocity. But, for an observer moving with the velocity of charge, there should be no magnetic field lines, right?
Is my line of thought correct? How can it be explained intuitively?
I am a high school student, under a calculus-based physics course.

REPLY [1 votes]: It is correct that moving with the charge, there will no longer be an observed magnetic field. In fact, it hints on something much deeper.
Instead of a point charge, consider an infinite line of current. From Ampere's law, we can calculate the magnetic field
$$
\vec{B} = \frac{\mu_0 I}{2 \pi r}\hat{\phi}
$$
If we then stop the line current, we have an infinite line of charge, which has an electric field given by Gauss' law:
$$
\vec{E} = \frac{\lambda}{2 \pi \epsilon_0 r} \hat{r}
$$
From this, we can see that (at least in this case), moving with respect to electric and magnetic fields will transform them into each other!
A reasonable question to ask after making this observation is we should describe the electromagnetic field in a way that can cope with such changes in observers. We can do this by introducing the electromagnetic field strength tensor, defined by
$$
F_{\mu \nu} =
\begin{bmatrix}
0 & \frac{E_x}{c} & \frac{E_y}{c} & \frac{E_z}{c} \\
- \frac{E_x}{c} & 0 & -B_z & B_y \\
- \frac{E_y}{c} & B_z & 0 & -B_x \\
- \frac{E_z}{c} & -B_y & B_x & 0
\end{bmatrix}
$$
Each index of this tensor can then be transformed with Lorentz transformations, which will allow you to calculate the fields for an arbitrary boost:
$$
F_{\mu' \nu'} = \Lambda^{\ \ \ \mu}_{\mu'} \Lambda_{\nu'}^{\ \ \nu} F_{\mu \nu}
$$


TITLE: Joint density of $X = \min(U_{1}, U_{2})$ and $Y = \max(U_{2}, U_{3})$
QUESTION [1 upvotes]: Let $U_{1}, U_{2}, U_{3}$ be i.i.d. random variables which are uniformly dis tributed on (0,1). Let $X = \min(U_{1}, U_{2})$ and $Y = \max(U_{2}, U_{3})$
(a) Find $P(X< x, Y < y)$ for all x,y in $\mathbb R$
(b) Find $P(X = Y)$
(c) Find $E[XI_{\{X=Y\}}]$ where $I_{A}$ is the indicator function of A.
(a) I found the PDFs of X and Y, i.e. $f_X(x)=2(1-x), f_Y(y)=2y$ using order statistics. I wanted to find the joint density and then integrate it to get the joint CDF, but I'm not sure how to find the joint density given that X and Y are dependent (?). Can someone please help?
b) $P(X=Y)=P( min(U_1,U_2)=max(U_2,U_3))=P(min(U_1,U_2)=U_2,max(U_2,U_3)=U_2)=P(U_1>U_2>U_3)=\frac{1}{6}$ (Since there are 6 (3!) ways to order 3 of these variables, I'm neglecting the possibility of $U_1=U_2=U_3$). Is this correct?
c) Isn't it the same as part (b)? I'm confused, please help.

REPLY [0 votes]: (a). The joint distribution $F(x, y) := P(X < x, Y < y)$ clearly depends on the value of $(x, y)$:

If $x > 1$ and $y > 1$, then clearly $F(x, y) = 1$.
If $x \leq 0$ or $y \leq 0$, then clearly $F(x, y) = 0$.
If $0 < x \leq 1$ and $y > 1$ then
$$F(x, y) = P(X < x) = 1 - P(\min(U_1, U_2) \geq x) = 1 - (1 - x)^2 = 2x - x^2.$$
If $x > 1$ and $0 < y \leq 1$, then
$$F(x, y) = P(Y < y) = P(U_2 < y)P(U_3 < y) = y^2. $$

The only non-trivial case is when $0 < x \leq 1$ and $0 < y \leq 1$, for which by the independence assumption:
\begin{align}
 & P(X < x, Y < y) = P(\min(U_1, U_2) < x, \max(U_2, U_3) < y) \\
=& \int_0^1 P(\min(U_1, z) < x, \max(z, U_3) < y)dz \tag{1} \\
=& \int_0^1 [P(\max(z, U_3) < y) - P(\min(U_1, z) \geq x, \max(z, U_3) < y)]dz \\
=& \int_0^1 P(\max(z, U_3) < y)dz - \int_0^1P(\min(U_1, z) \geq x, \max(z, U_3) < y)dz \\
=& \int_0^y P(U_3 < y) dz - \int_0^1P(\min(U_1, z) \geq x, \max(z, U_3) < y)dz \\
=:& y^2  - I
\end{align}
For the integral $I$, if $x \geq y$, then the integrand is $0$ whence $I = 0, F(x, y) = y^2$. If $x < y$, then
\begin{align*}
I = \int_0^1P(\min(U_1, z) \geq x, \max(z, U_3) < y)]dz
= \int_x^y P(U_1 \geq x, U_3 < y) dz = (1 - x)y(y - x).
\end{align*}
It then follows that $F(x, y) = y^2 - y(1 - x)(y - x) = xy + xy^2 - x^2y$.  For the veracity of equation $(1)$, refer to Theorem $20.3$ of Probability and Measure by P. Billingsley.
The above calculations can then be summarized as
\begin{align}
F(x, y) = \begin{cases}
0 & (x, y) \in \{(u, v): u \leq 0\} \cup \{(u, v): v \leq 0\}, \\
xy + xy^2 - x^2y & (x, y) \in \{(u, v): 0 < u < v < 1\}, \\
y^2 & (x, y) \in \{(u, v): 0 < v \leq u < 1\} \cup \{(u, v): u > 1, 0 < v \leq 1\},  \\
2x - x^2 & (x, y) \in \{(u, v): 0 < u \leq 1, v > 1\}, \\
1 & (x, y) \in \{(u, v): u > 1, v > 1\}.
\end{cases}
\end{align}

(c). (c) is clearly different from (b), which is identical to $E[I_{\{X = Y\}}]$ (i.e., without multiplying $X$).   To evaluate $E[XI_{\{X = Y\}}]$, note that it's the expectation of a non-negative random variable, therefore,
\begin{align}
E[XI_{\{X = Y\}}] = \int_0^\infty P[XI_{\{X = Y\}} > t] dt = \int_0^1 P[XI_{\{X = Y\}} > t] dt = \int_0^1 P[X > t, X = Y] dt. \tag{2}
\end{align}
The probability in the integrand can be evaluated in the same manner as determining $F(x, y)$, for which we apply the Theorem leading to $(1)$ again:
\begin{align*}
 & P[X > t, X = Y] = P[\min(U_1, U_2) > t, \min(U_1, U_2) = \max(U_2, U_3)] \\
=& \int_0^1 P[\min(U_1, s) > t, U_1 \geq s, U_3 \leq s] ds \\
=& \int_t^1 P[U_1 > t, U_1 \geq s, U_3 \leq s] ds \\
=& \int_t^1 P[U_1 \geq s, U_3 \leq s]ds \\
=& \int_t^1 s(1 - s)ds = \frac{1}{6} - \frac{1}{2}t^2 + \frac{1}{3}t^3.
\end{align*}
Substituting it into $(2)$, it then follows that
\begin{align*}
E[XI_{\{X = Y\}}] = \int_0^1 \left(\frac{1}{6} - \frac{1}{2}t^2 + \frac{1}{3}t^3
\right) dt = \frac{1}{12}.
\end{align*}


TITLE: prove that if $a = bmod(p)$ then the value of the legendre symbol $(\frac{a}p) = (\frac{b}p)$
QUESTION [2 upvotes]: I started by using the fact that $a = b + \lambda p$ and i then substituted this into eulers lemma: $a^{(p-1)/2} = (\frac{b + \lambda p}p)mod(p)$. But i was unsure if you could split up the the symbol $(\frac{b + \lambda p}p)$ into $(\frac{b}p) + (\frac{\lambda p}p)$. because if so then the proof follows quite quickly. but if not i dont know how to proceede.

REPLY [3 votes]: Your approach indeed works (though it's an overkill ) . Use Euler's lemma :
$$\left (\frac{a}{p} \right )\equiv a^{\frac{p-1}{2}} \pmod{p}$$
$$ \left (\frac{b}{p} \right )\equiv b^{\frac{p-1}{2}} \pmod{p}$$
Now because $a \equiv b \pmod{p}$ it follows that $$a^{\frac{p-1}{2}} \equiv b^{\frac{p-1}{2}} \pmod{p}$$
Now use all these congruences together so :
$$\left (\frac{a}{p} \right )\equiv \left (\frac{b}{p} \right ) \pmod{p}$$
But remember that these numbers are $-1,0$ or $1$ so because $p>2$ they must be equal else the congruence doesn't hold .


text:
\begin{document}
\allowdisplaybreaks[4]

\title{A basic model of mutations}

\author{ Maxime Berger
\footnote{
\noindent
D\'epartement de math\'ematiques et applications, Ecole Normale Sup\'erieure,
CNRS, PSL Research University, 75005 Paris}
\hskip 70pt
Rapha\"el Cerf
\footnotemark[1]
\footnote{
Laboratoire de Math\'ematiques d'Orsay, Universit\'e Paris-Sud, CNRS, Universit\'e
Paris--Saclay, 91405 Orsay.}
}

\maketitle

\begin{abstract}
\noindent
We study a basic model for mutations. We derive exact formulae for the mean time needed to discover
	the master sequence, the mean returning
time to the initial state, or to any Hamming class. These last two formulae are
	the same than the formulae
	obtained by Mark Kac for the Ehrenfest model.
\end{abstract}

\section{\bf Introduction}
According to the Darwinian paradigm,

the evolution of living creatures is driven by two main forces: mutations
and selection. Mutations create
new forms of behaviour or new characters,
some less fit to their environment,
some more,
whereas  selection favors the reproduction of fitter individuals.

On the one hand, mutations may discover very fit characters but without selection,
they would be quickly erased by further mutations.

On the other hand, selection alone would result in uniform populations, lacking in genetic diversity.

The success of an evolutionary process rests on a subtle interaction between mutations
and selection.

Let us consider for instance
a population of HIV viruses or {\itshape Drosophila melanogaster}.
The genetic material of one individual, also called its genotype, is encoded into its DNA, which is
a long chain of nucleobases A,T,G or C.
To simplify the analysis, we suppose here that there are only two types of nucleobases
instead of four, and we denote them by $0$ or $1$.

Selection enters the game through fitness.
The fitness describes the adaptation of the individuals to the environnement.
The fitness of an individual can be thought as a function of its genotype.
For instance, a possible choice for the fitness function is the expected number of offspring
of the individual.
We consider the situation where all the genotypes are equally fitted, except one,
say $0\cdots 0$, which has a superior fitness.

There exist several
mathematical models of evolution combining mutations and selection.
The simplest one

is perhaps the Moran model, whose dynamics is the following.
At each time step, one individual dies, while one individual gives birth to a child
(in particular, the population size stays constant).
All individuals are equally likely to die, but the fitter individuals having
genotype $0\cdots 0$ reproduce more often.
Mutations occur during reproduction: the genotype of the child is not an exact
copy of the one of its parent.

A central question is then to determine the proportion of individuals
with genotype $0\cdots 0$
in the population after a long time.

To answer this question, one should understand how long it takes for
a population to escape from
the set of the selectively neutral genotypes. We perform this crucial step here.
We consider one single individual, we follow his lineage and we
compute the time needed for the genotype $0\cdots 0$ to be discovered.

\noindent

{\bf A model for mutations}.

We follow the genotypes of the individuals along a lineage.

We fix the probability of mutation $p\in (0,1)$.
We start from a string $X_0$ in $\{0,1\}^N$, which represents the genotype of the
first individual.
We denote by $X_n$ the genotype of the $n$--th individual in the lineage.
At time $n$, for each bit of $X_n$, we toss a coin of parameter~$p$ to decide whether a
mutation occurs on the bit, in which case it is transformed into the complementary digit.
All the coins are taken independent, so the probability of having no mutations at all at time $n$ is $(1-p)^n$.
The assumption of independance simplifies considerably the mathematical analysis, and it is also
biologically plausible. Indeed the mutations arise because of transcription errors during the replication
process, and for long genomes, they are not correlated. It seems however that the mutation probability $p$
varies along the genome,
so the next modelling step would be to incorporate this spatial dependance into the model.

We end up with a random walk $(X_n)_{n\in\N}$
on the hypercube $\{\,0,1\,\}^N$, for which the transition probabilities only depend on the number of differences between two states.

Let
$\tau_0$ be
the hitting time of the master sequence $0\cdots 0$, i.e.,
$$\tau_0\,=\,\inf\,\big\{\,n\geq 1:X_n=0\cdots 0\,\big\}\,.$$
The goal is then to compute the expected value of $\tau_0$.

\noindent
{\bf Lumping.}
The smart way to analyze this random walk is to lump together the states of the hypercube into
Hamming classes.
The Hamming class number $i$ consists of the points which have $i$
digits equal to $1$ and $N-i$ equal to $0$.
So we define a new process $(Y_n)_{n\in\N}$ by setting
\begin{equation*}
Y_n\,=\,\text{number of digits of $X_n$ equal to $1$}
	\,.
\end{equation*}
We obtain a Markov chain with state space $\{\,0,\dots,N\,\}$,
and we shall provide explicit formulas for its mean passage times.

\noindent
{\bf Discovering and recovering time.}
For $0\leq j\leq N$, we define
the hitting time of the Hamming class $j$ by

$$\tau_j\,=\,\inf\,\big\{\,n\geq 1:Y_n=j\,\big\}\,.$$
The three theorems
below give exact formulas for the expected value of $\tau_j$, when starting
from $0$, $N$, or $j$. These formulas are surprisingly simple and come out from tricky computations.
The discovering time of the master sequence is bounded from above by
the traversal time, which is the time
needed to reach the class $0$ starting from the class $N$.
This corresponds to the situation where we start with a string containing only ones, and
we wait until we see a string containing only zeroes.
\begin{theorem}
\label{trav}
The mean traversal time is given by
$$E\big(\tau_0\,\big|\,Y_0=N\big)\,=\,
\sum_{k=1}^N
\displaystyle{N \choose {k}}
	\frac{1-(-1)^k}{1-(1-2p)^k}\,.$$
\end{theorem}
The recovering time of the master sequence corresponds to the
returning time to the class $0$ when starting away from a genotype different from $0\cdots 0$.
This time is bounded from below by the mean return time to $0$ starting from $0$, which we compute next.
\begin{theorem}
\label{return}
The mean returning time to the class $0$ is given by
$$E\big(\tau_0\,\big|\,Y_0=0\big)\,=\,2^N
\,.$$
\end{theorem}
Of course, the formula of theorem~\ref{return} is also a straightforward consequence of the classical
result expressing the invariant probability measure of a Markov chain in terms of mean recurrence times.
However, it does not seem that the other formulas presented in theorems~\ref{trav} or~\ref{greturn}
are easy consequences of more general results.
We compute next a beautiful formula for the returning time to the class~$j$ when starting away from a genotype of the same class.
\begin{theorem}
\label{greturn}
For $1\leq j\leq N$,
the mean returning time to the class $j$ is

$$E\big(\tau_j\,\big|\,Y_0=j\big)\,=\,
\frac{
\displaystyle
2^N}{\displaystyle{N \choose {j}}
}\,.$$
\end{theorem}

	From
	theorems~\ref{trav} and~\ref{return}, it is easy to infer an estimate on the mean returning time
	of $0$ which is uniform with respect to the starting point. Indeed, a standard coupling
	argument yields that, for any starting string $x_0$,
$$E\big(\tau_0\,\big|\,Y_0=0\big)\,\leq\,
E\big(\tau_0\,\big|\,X_0=x_0\big)\,\leq\,
E\big(\tau_0\,\big|\,Y_0=N\big)\,.$$
Taking into account theorems~\ref{trav} and~\ref{return}, we conclude that
$$2^N\,\leq\,
E\big(\tau_0\,\big|\,X_0=x_0\big)\,\leq\,
\sum_{k=1}^N
\displaystyle{N \choose {k}}
	\frac{1-(-1)^k}{1-(1-2p)^k}\,\leq\,

	\frac{2^N}{p}\,.$$
	These inequalities show that the discovering and the recovering times of the master
	sequence are of order $2^N$.
	It turns out that these results are akin to those related to an old classical model,
	the Ehrenfest model, that we describe briefly.

\noindent
{\bf The Ehrenfest model.}
Let us consider $N$ balls and two boxes.
Initially, all the balls are in the first box. At each time step, one ball is selected
at random and is moved from its current box to the other box. The central question is then the following:
\smallskip

\centerline{On average, how long will it take
to return to the initial state?}
\smallskip

\noindent
In 1947,
Mark Kac gave a simple answer to this question in a celebrated paper \cite{KAC}.
He considered the evolution of the number of balls in the first box. This process is a Markov chain on
$\{\,0,\cdots,N\,\}$, which is quite different from our process $(Y_n)_{n\in\N}$. For instance,
its increments are either $-1,0$ or $+1$.
Mark Kac showed that,
starting from $0$,
the average time for the Ehrenfest process to return to its initial state is equal to
$2^N$, which is the analog of theorem~\ref{return}.
He showed also that,
when starting from the state $j$,
the average time until return to $j$ is equal to

	${ 2^N}/{N \choose {j}}$. Theorem~\ref{greturn} gives the analogous result for our model of mutations.

	\smallskip

	\noindent
{\bf A glimpse of potential theory}.
We attack here the general case, i.e., we look for a formula for
the mean returning time to the class $j$,
when the process starts from the class $i$.
We start from the formula obtained in theorem~\ref{trav}, for the specific case where $i=N$ and $j=0$.
We expand in a geometric series the denominator and we get
$$E\big(\tau_0\,\big|\,Y_0=N\big)\,=\,
\sum_{k=1}^N
\sum_{n\geq 0}
\displaystyle{N \choose {k}}
 \Big( (1-2p)^{nk}
- (-1)^k (1-2p)^{nk}\Big)
 \,.$$
We exchange the order of the summations and, using the formulas~\eqref{gutq}
and~\eqref{gutr}, we obtain
$$
E\big(\tau_0\,\big|\,Y_0=N\big)\,=\, 2^N \sum_{n \geq 0}\Big(P_0\big(Y_n=0\big)-P_N\big(Y_n=0\big)\Big)\,.
$$
From theorem~\ref{return}, we have also that
$E\big(\tau_0\,\big|\,Y_0=0\big)=2^N$.

The above display formula is actually a particular case of a more general
identity valid for a large class of Markov chains, that we state in the next theorem.
\begin{theorem}
\label{general}
For any $i,j$ in $\{\,0,\dots,N\,\}$, we have
$$E\big(\tau_j\,\big|\,Y_0=i\big)\,=\,E\big(\tau_j\,\big|\,Y_0=j\big)
	\bigg(\sum_{n \geq 0}\Big(P_j\big(Y_n=j\big)-P_i\big(Y_n=j\big)\Big)\bigg)\,.
$$
\end{theorem}
In the case of our specific model, we have further a formula for each term in the sum
(see formula~\eqref{genfor}). This way, we get an exact formula for
$E\big(\tau_j\,\big|\,Y_0=i\big)$, which we present in the next theorem.

\begin{theorem}
\label{greturngen}
For $1\leq j\leq N$,
the mean returning time to the class $j$ starting from class $i$ is given by
\begin{multline}
E\big(\tau_j\,\big|\,Y_0=i\big)\,=\\
\frac{1}
{\displaystyle{N \choose {j}}
}
\sum_{n\geq 0} \sum_{k=0}^N
\Bigg(
{j \choose k} {N-j \choose k} - {i \choose j-k}{N-i \choose k} \Big(\frac{1-(1-2p)^n}{1+(1-2p)^n}\Big)^{i-j}
\Bigg) \\
\Big(1-(1-2p)^n\Big)^{2k} \Big(1+(1-2p)^n\Big)^{N-2k}
\,.
\end{multline}
\end{theorem}
{\bf Strategy of the proof}.
We will employ the same method that Mark Kac used for the Ehrenfest model.
We shall try to compute
$E\big(\tau_j\,\big|\,Y_0=i\big)$ for $0\leq i,j\leq N$.
These computations are tricky.
We will in fact compute the generating functions
of the event $\{\,Y_n=j\,\}$ and of the random variable $\tau_j$, and we will
relate them through a functional equation that we derive in the next section.
The mean passage times are equal to the left derivative at $1$ of the generating
function of $\tau_j$. We compute these derivatives by performing a local expansion of the
functions around~$1$.
Finally, in the last section, we prove a general formula for
$E\big(\tau_j\,\big|\,Y_0=i\big)$ for $0\leq i,j\leq N$, which is based on the potential
theory for Markov chains.
\section{A classical probabilistic identity}
\label{clid}

Throughout the computations, we shall denote by $P_i$ the
probability conditioned on the event that $Y_0=i$.
Let us fix $0\leq i,j\leq N$.
For $n\geq 1$,
we compute $P_i(Y_n=j)$ by decomposing the
event $\{\,Y_n=j\,\}$ according to the hitting time $\tau_j$, as follows:
\begin{align*}
P_i(Y_n=j)\,&=\,
\sum_{k=1}^n
P_i(Y_n=j,\,\tau_j=k)\cr
\,&=\,
\sum_{k=1}^n
P_i\big(Y_1\neq j,\dots,Y_{k-1}\neq j, Y_k=j,Y_n=j\big)\,.
\end{align*}
We perform a conditioning in the probability in the sum and we get
\begin{multline*}
P_i(Y_n=j)\,=\,

\smash{\sum_{k=1}^n}
P_i\big(Y_1\neq j,\dots,Y_{k-1}\neq j, Y_k=j\big)\cr
\qquad\qquad\times
 P_i\big(Y_{n}=j\,\big|\,
Y_1\neq j,\dots,Y_{k-1}\neq j, Y_k=j
\big)\,.
\end{multline*}
The constitutive property of a Markov chain is that the past influences the future only
through the present state. This is rigorously formalized in the Markov property, which
yields that
$$ P_i\big(Y_{n}=j\,\big|\,
Y_1\neq j,\dots,Y_{k-1}\neq j, Y_k=j
\big)
\,=\,
P_i\big(Y_{n}=j\,\big|\, Y_k=j\big)\,.$$
Since in addition the Markov chain is time homogeneous, we have that
$$P_i\big(Y_{n}=j\,\big|\, Y_k=j\big)
\,=\,
P_j\big(Y_{n-k}=j\big)
\,.$$

Plugging the last two equalities in the sum, we conclude that
\begin{equation}
\label{iden}
P_i(Y_n=j)\,=\,
\sum_{k=1}^n
P_i\big(\tau_j=k\big)P_j\big(Y_{n-k}=j\big)\,.
\end{equation}
To take advantage of this identity, we introduce the generating functions
of the event $\{\,Y_n=j\,\}$ and of the random variable $\tau_j$, i.e.,
we consider the series
\begin{align*}
F_{ij}(z)\,&=\,
\sum_{n\geq 1}
P_i(Y_n=j)\,z^n\,,\cr
G_{ij}(z)\,&=\,
\sum_{n\geq 1}
P_i(\tau_j=n)\,z^n\,.
\end{align*}
Their radius of convergence is at least one.
In equation~\eqref{iden}, we isolate the term corresponding to $k=n$, and we multiply
by $z^n$ to get
\begin{equation*}

P_i(Y_n=j)z^n\,=\,
P_i\big(\tau_j=n\big)z^n\,+\,
\sum_{k=1}^{n-1}
P_i\big(\tau_j=k\big)z^k\,P_j\big(Y_{n-k}=j\big)z^{n-k}\,.
\end{equation*}
Looking at the sum, we recognize the Cauchy product of the two series. Summing this
identity, we conclude that
\begin{equation}
\label{idgen}
F_{ij}(z)\,=\,
G_{ij}(z)\,+\,
F_{jj}(z)\,
G_{ij}(z)\,.
\end{equation}
The strategy is now the following. We try to compute the functions $F_{ij}$.
We use then the above identity to obtain the functions $G_{ij}$.
Finally, the mean passage times can be computed from $G_{ij}$
by taking its left derivative at~$1$:
$$
E\big(\tau_j\,\big|\,Y_0=i\big)\,=\,
\sum_{n\geq 1} nP_i(\tau_j=n)\,=\,
G'_{ij}(1)\,.$$

\section{Single nucleotide dynamics}
We suppose here that $N=1$, i.e., we focus on the dynamics of a single nucleotide.
In this case, the process
$(X_n)_{n\geq 0}$ is
the Markov chain
with state space $\{0,1\}$ and transition
matrix
$$M\,=\,\begin{pmatrix}
\displaystyle 1-p & p \cr

	p & 1-p\cr
\end{pmatrix}\,.
$$
The eigenvalues of $M$ are $1$ and
$1-2p$.

We compute, for $n\geq 1$,
$$M^n\,=\,
\frac{1}{2}
\begin{pmatrix}
	\displaystyle 1+ (1-2p)^n & 1-(1-2p)^n  \cr
	\displaystyle 1- (1-2p)^n & 1+(1-2p)^n  \cr
\end{pmatrix}\,.
$$
Here is a simple illuminating way to realize the dynamics and to
understand the expression of the $n$--th power $M^n$.
Let
$(\varepsilon_n)_{n\geq 1}$ be an i.i.d. sequence of Bernoulli random variables with
parameter $p$. At each time step, we use the variable $\varepsilon_n$ to decide
whether $X_n$ mutates or not. More precisely, we set
$$X_n\,=\,
\begin{cases}
X_{n-1}\quad&\quad\text{if}\quad \varepsilon_n=0\,,\cr
1-X_{n-1}\quad&\quad\text{if}\quad \varepsilon_n=1\,.\cr
\end{cases}
$$
Now, the event $X_n=X_0$ occurs if and only if the total number of
mutations which happened until time $n$ is even, i.e.,
$$
P(X_n=X_0)\,=\,P\big(\varepsilon_1+\cdots+\varepsilon_n\text{ is even}\big)\,.
$$
Let us set
$$S_n\,=\,\varepsilon_1+\cdots+\varepsilon_n\,.
$$
Here is a little trick to compute the probability that $S_n$ is even.
We compute in two different ways the expected value of $(-1)^{S_n}$. Indeed, we have
\begin{align*}
E\big((-1)^{S_n}\big)&\,=\,
\Big(
E\big((-1)^{\varepsilon_1}\big)\Big)^n
\,=\, \big(-p+1-p\big)^n
\,=\, \big(1-2p\big)^n
\cr

&\,=\,
P\big(S_n\text{ is even}\big)\,-\,
P\big(S_n\text{ is odd}\big)\,.
\end{align*}
Obviously, we have
$$
P\big(S_n\text{ is even}\big)\,+\,
P\big(S_n\text{ is odd}\big)\,=\,1\,,$$
therefore we obtain that
$$
	P(X_n=X_0)\,=\,
P\big(S_n\text{ is even}\big)\,=\,
	\frac{1}{2} \Big(1+(1-2p)^n\Big)\,.$$
This way we recover the expression of the diagonal coefficients of $M^n$.
Let us define
\begin{equation}
\label{albe}
p_n\,=\,

	\frac{1}{2} \Big(1+(1-2p)^n\Big)\,.

\end{equation}
From the above computations,

we conclude the following.
Conditionally on $X_0=1$, $X_n$ is a
Bernoulli random variable with parameter $p_n$, i.e.,
$$P\big(X_n=1\,\big|\,X_0=1\big)\,=\,p_n\,,\qquad
P\big(X_n=0\,\big|\,X_0=1\big)\,=\,1-p_n\,.
$$
Similarly, conditionally on $X_0=0$, $X_n$ is a
Bernoulli random variable with parameter $1-p_n$.
\section{Multiple nucleotides dynamic}
We consider now the case where the number $N$ of nucleotides is larger than one.
In our model, the mutations occur independently at each site. An important consequence
of this structural assumption is that the components of $X_n$,
$(X_n(i),1\leq i\leq N)$, are themselves Markov chains like the one studied in the previous
section, and these Markov chains are moreover independent.
This remark, combined with the results of the previous section, allows to derive
explicitly the distribution of $Y_n$.
Indeed, suppose that we start from $Y_0=i$.
This means that $i$ digits in $X_0$ are equal to $1$ and $N-i$ to $0$.
At time $n$, in $X_n$, the $i$ digits which were initially equal to $1$ are distributed according
to a Bernoulli law of parameter $p_n$, the others
are distributed according
to a Bernoulli law of parameter $1-p_n$.
The evolution of the nucleotides being independent, these Bernoulli variables are independent, so their sum
is distributed as the sum of two independent Binomial random variables:
$$Y_n\,\sim\,\bino(i,p_n)+
\,\bino(N-i,1-p_n)\,.$$
This yields for instance the following formula:
\begin{multline}
	\label{genfor}
	P_i(Y_n=j)\,=\,
\kern-7pt

\sum_{\tatop{0\leq k\leq i}{ 0\leq j-k\leq N-i}}
\kern-10pt
P\big( \bino(i,p_n)=k\big)
P\big(
\bino(N-i,1-p_n)
=j-k\big)\cr
	\hfill
	=\kern-7pt

\sum_{\tatop{0\leq k\leq i}{ 0\leq j-k\leq N-i}}
\kern-7pt
{i \choose k}

	{N-i \choose j-k}
	(1-p_n)^{i+j-2k}(p_n)^{N-i-j+2k}
\,.
\end{multline}
This formula is quite complicated. Yet it becomes particularly simple in the cases
where $i$ or $j$ is equal to $0$ or $N$. Indeed, we have, for $0\leq i\leq N$,
\begin{align*}
	P_i(Y_n=0)\,&=\,
(1-p_n)^i (p_n)^{N-i}\,,\cr
\qquad
	P_i(Y_n=N)\,&=\,
(p_n)^i (1-p_n)^{N-i}\,,
\end{align*}
and
for $0\leq j\leq N$,
\begin{align}
	P_0(Y_n=j)\,&=\,
{N \choose j}
	(1-p_n)^{j}(p_n)^{N-j}
	\label{trag}
	\,,\\
	\label{trai}
\qquad
	P_N(Y_n=j)\,&=\,
{N \choose j}(p_n)^j(1-p_n)^{N-j}
	\,.
\end{align}
For once, surprisingly enough, these two cases are also the most relevant for genetic applications,
so we treat them first. We will indeed compare these extreme cases to the general chain and deduce an estimation on the discovering and returning time.

\section{Proofs of theorems~\ref{trav} and~\ref{return}.}
	This section is devoted to the completion of the proof of theorems~\ref{trav} and~\ref{return}.
	We shall implement the strategy explained at the end of section~\ref{clid}.
Our first goal is to compute the generating function
$$F_{N0}(z)\,=\,
\sum_{n\geq 1}
P_N(Y_n=0)\,z^n\,.$$
From formulas~\eqref{trai} and~\eqref{albe}, we have
\begin{equation*}
P_N(Y_n=0)\,=\,
	(1-p_n)^{N}
	\,=\,
	\Big(
	\frac{1-
	(1-2p)^n
	}{2}
	\Big)^N
	\,.
\end{equation*}
	We use the binomial expansion to develop the $N$--th power in order to compute
	the generating function $F_{N0}$ as a sum of geometric series:
\begin{equation}
	\label{gutq}
P_N(Y_n=0)\,=\,
 \frac{1}{2^N}\sum_{k=0}^N \binom{N}{k}(-1)^k (1-2p)^{nk}.
\end{equation}
Notice that $P_N\big(Y_0=0\big)=0$. For convenience, we start the sum defining $F_{N0}$ at $n=0$
and we obtain a finite number of geometric series:
\begin{align*}
	F_{N0}(z)&\,=\,
\sum_{n\geq 0}
P_N(Y_n=0)\,z^n\\
&\,=\,\sum_{n \geq 0}
 \frac{1}{2^N}\sum_{k=0}^N \binom{N}{k}(-1)^k (1-2p)^{nk}
	z^n\\
&\,=\, \frac{1}{2^N}\sum_{k=0}^N \binom{N}{k}
	\frac{ (-1)^k }{1-(1-2p)^k z}\,.
\end{align*}
Our next goal is to compute the generating function
$$F_{00}(z)\,=\,
\sum_{n\geq 1}
P_0(Y_n=0)\,z^n\,.$$
From formulas~\eqref{trag} and~\eqref{albe}, we have, after binomial expansion:
\begin{align}
	P_0(Y_n=0)&\,=\,
	(p_n)^{N}
	\,=\,
	\Big(
	\frac{1+
	(1-2p)^n
	}{2}
	\Big)^N\cr
	&\,=\,
 \frac{1}{2^N}\sum_{k=0}^N \binom{N}{k} (1-2p)^{nk}
	\,.
	\label{gutr}
\end{align}
This time, we have
	$P_0\big(Y_0=0\big)=1$. Adding this term to $F_{00}$, we get again nice geometric series:
\begin{align*}
	1+F_{00}(z)&\,=\,
\sum_{n\geq 0}
P_0(Y_n=0)\,z^n\\
&\,=\,\sum_{n \geq 0}
 \frac{1}{2^N}\sum_{k=0}^N \binom{N}{k} (1-2p)^{nk}
	z^n\\
&\,=\, \frac{1}{2^N}\sum_{k=0}^N \binom{N}{k}
	\frac{ 1 }{1-(1-2p)^k z}\,.
\end{align*}
For $0\leq k\leq N$,
we introduce the auxiliary functions
$$
\phi_k(z) = \binom{N}{k} \frac{1}{1-(1-2p)^k z}\,,
$$
and we rewrite the expressions of
$F_{N0}$ and $1+F_{00}$ as
\begin{align}
	\label{foo}
		F_{N0}(z)\,=\,
 \frac{1}{2^N}\sum_{k=0}^N  (-1)^k\phi_k(z)
 \,,\cr
	1+F_{00}(z)\,=\,
 \frac{1}{2^N}\sum_{k=0}^N  \phi_k(z)
 \,.
\end{align}
We have computed $F_{N0}$ and $1+F_{00}$. From the probabilistic identity~\eqref{idgen},
we obtain
$$
G_{N0}(z)\,=\,
\frac{F_{N0}(z)}{1+F_{00}(z)}\,.$$
Remember that our ultimate goal is to compute the left derivative of $G_{N0}$ at $1$.
The functions $\phi_k$ are regular around $1$, except the first one, $\phi_0$, indeed,
$$\phi_0(z)\,=\,\frac{1}{1-z}\,.$$
To get $G'_{N0}(1)$, we perform a local expansion of $G_{N0}$ around $1$, as follows:
\begin{align*}
G_{N0}(z)
	&\,=\,
\frac{\displaystyle \frac{1}{1-z}+ \sum_{k=1}^N  (-1)^k\phi_k(z)}
{\displaystyle \frac{1}{1-z}+ \sum_{k=1}^N  \phi_k(z)}\\
	&\,=\,

	\displaystyle {1}+({1-z}) \sum_{k=1}^N  \big((-1)^k-1\big)\phi_k(z)+o(z-1)\,.
\end{align*}
This expansion readily yields the value of the left derivative of $G_{N0}$ at $1$:
$$G'_{N0}(1) \,=\,
	 \sum_{k=1}^N  \big(1-(-1)^k\big)\phi_k(1)\,.
$$
Replacing $\phi_k(1)$ by its value, we obtain the formula stated in theorem~\ref{trav}.
We proceed similarly to prove
theorem~\ref{return}. In fact, we have to compute $G'_{00}(1)$, and the
probabilistic identity~\eqref{idgen} yields
$$
G_{00}(z)
\,=\,
\frac{F_{00}(z)}{1+F_{00}(z)}
\,=\,1-
\frac{1}{1+F_{00}(z)}\,.$$
We have already computed $1+F_{00}(z)$ in formula~\eqref{foo}. We use this expression
and we expand around $z=1$:
\begin{equation*}
G_{00}(z) \,=\,1- \frac{\displaystyle 2^N}{
	\displaystyle\sum_{k=0}^N  \phi_k(z)}
\,=\,1- 2^N (1-z)+o(1-z)\,.

\end{equation*}
This expansion shows that
$G'_{00}(1)=2^N$.

\section{Proof of theorem~\ref{greturn}}
We shall finally prove the analog of Kac theorem on the mean returning time to the class $j$,
when the process starts from the class $j$.

We write the formula~\eqref{genfor} with $i=j$, we reindex the sum by setting
$\ell=j-k$
and we perform the two binomial expansions:
\begin{multline*}
	P_j(Y_n=j)\,=\,
\cr
	\hfill
	\kern-7pt

\sum_{\tatop{0\leq k\leq j}{ 0\leq j-k\leq N-j}}
\kern-7pt
{j \choose k}

	{N-j \choose j-k}

	\Big(
	\frac{ 1-(1-2p)^n }{2}
	\Big)^{2j-2k}
	\Big(
	\frac{ 1+(1-2p)^n }{2}
	\Big)^{N-2j+2k}
\cr
	\hfill
	\kern-7pt
\,=\,

	\sum_{\ell=0}^{ j\land{(N-j)}}

{j \choose \ell}

	{N-j \choose \ell}

	\Big(
	\frac{ 1-(1-2p)^n }{2}
	\Big)^{2\ell}
	\Big(
	\frac{ 1+(1-2p)^n }{2}
	\Big)^{N-2\ell}
	\hfill
	\cr
\,=\,

	\kern-7pt
	\sum_{\ell=0}^{ j\land{(N-j)}}
	\kern-5pt
	\frac{ 1 }{2^N}

{j \choose \ell}

	{N-j \choose \ell}

	\sum_{\alpha=0}^{2\ell}
\sum_{\beta=0}^{N-2\ell}
	\binom{2\ell}{\alpha}
\binom{N-2\ell}{\beta}
	(-1)^{\alpha}(1-2p)^{(\alpha+\beta) n}
\,.
\end{multline*}
	For $n=0$, we have
	$P_j(Y_0=j)=1$, therefore, after a geometric summation, we get
	$$\displaylines{
	1+F_{jj}(z)\,=\,
\sum_{n\geq 0}
P_j(Y_n=j)\,z^n\hfill\cr
	\,=\,
	\kern-7pt
	\sum_{\ell=0}^{ j\land{(N-j)}}
	\kern-5pt
	\frac{ 1 }{2^N}
{j \choose \ell}
	{N-j \choose \ell}
	\sum_{\alpha=0}^{2\ell}
\sum_{\beta=0}^{N-2\ell}
	\binom{2\ell}{\alpha}
\binom{N-2\ell}{\beta}
	\frac{(-1)^\alpha}{1-(1-2p)^{\alpha +\beta } z}
	\,.}$$
We expand this function around $z=1$ and we get
\begin{align*}
	1+F_{jj}(z)&\,=\,
	\kern-7pt
	\sum_{\ell=0}^{ j\land{(N-j)}}
	\kern-5pt
	\frac{ 1 }{2^N}
{j \choose \ell}
	{N-j \choose \ell}
	\frac{1}{1-z}+O(1)\cr
	&\,=\,
	\frac{ 1 }{2^N}
	{N \choose j}
	\frac{1}{1-z}+O(1)\,,
\end{align*}
thanks to the combinatorial identity stated in the next lemma.
\begin{lemma}\label{binom}
For~$0\leq j\leq N$, we have
$$

	\sum_{\ell=0}^{ j\land{(N-j)}}
	\kern-5pt
{j \choose \ell}
	{N-j \choose \ell}\,=\,
	{N \choose j}\,.
$$
\end{lemma}
\begin{proof}
	Let us fix $j$ in $\{\,0,\dots,N\,\}$, and let us consider a set $E$
	having cardinality $N$.
	We fix also a subset $A$ of $E$ having $j$ elements.
	We classify the subsets of $E$ having cardinality $j$ according
	to the cardinality of their intersection with $A$ and we readily obtain
	the formula of the lemma.
\end{proof}

\noindent
From the probabilistic identity~\eqref{idgen},
we have
$$
G_{jj}(z)

\,=\,1-
\frac{1}{1+F_{jj}(z)}\,,$$
thus
$G_{jj}(z)$ admits the following expansion around $z=1$:
$$
G_{jj}(z)\,=\,
	1+
	\frac{2^N}{\displaystyle {N \choose j}}
	({z-1})+o(z-1)\,.
$$
From this expansion, we infer that
$$E\big(\tau_j\,\big|\,Y_0=j\big)\,=\,
G'_{jj}(1)\,=\,
	\frac{2^N}{\displaystyle {N \choose j}}
	$$
	and this concludes the proof of theorem~\ref{greturn}.

\section{ Proof of theorem~\ref{general}}
It has been observed a long time ago that the equations defining the invariant measure, or the
returning time to a set for a random walk, or more generally a Markov chain, are formally
equivalent to the equations arising in potential theory, if one interprets the transition probabilities
as conductances (see the very nice book \cite{doyle}).
In fact, the formula presented in theorem~\ref{general} takes its roots in potential theory \cite{neveu}.
Let us denote by $P$ the transition matrix of the process
$(Y_n)_{n\geq 0}$, defined by
$$\forall i,j\in\{\,0,\dots,N\,\}\quad\forall n\geq 0
\qquad
P(i,j)\,=\,P(Y_{n+1}=j\,|\,Y_n=i)\,.$$
The arguments presented below are in fact valid for a general class of Markov chains with finite
state space.
For instance, it suffices that $P$, or one of its powers, has all its entries positive. In this
situation, the classical ergodic theorem for Markov chains ensures the existence and uniqueness
of an invariant probability measure and the following convergence holds:
\begin{equation}
	\label{ergodic}
\forall i,j\in\{\,0,\dots,N\,\}

\qquad
\lim_{n\to\infty}
P^n(i,j)\,=\,\frac{1}{ E\big(\tau_j\,\big|\,Y_0=j\big) }\,.
\end{equation}
From now on, we fix $j$ in
$\{\,0,\dots,N\,\}$ and we try to compute
$E\big(\tau_j\,\big|\,Y_0=i\big) $. The idea is to study
the behavior of the Markov chain until the time~$\tau_j$. To do so, we introduce
the companion matrix $G$ defined by
$$\forall i,k\in\{\,0,\dots,N\,\}\qquad
G(i,k)\, =\, E_i\Big(\sum_{n=0}^{\tau_j-1}1_{\{Y_n=k\}}\Big)\, .  $$
The matrix $G$ is called the potential matrix associated with the restriction
of $P$ to
$\{\,0,\dots,N\,\}\setminus \{j\}$.
The quantity $G(i,k)$ represents the average number of visits of the state $k$ before reaching the state $j$
when starting from $i$. We introduce also the matrix $H$ given by
$$\forall i,k\in\{\,0,\dots,N\,\}\qquad
H(i,k)\, =\,
\begin{cases}
1&\quad\text{if}\quad k=j\,\cr
0&\quad\text{if}\quad k\neq j\,\cr
\end{cases}
\, .  $$
The matrix $H$ describes the distribution of the exit point from the set
$\{\,0,\dots,N\,\}\setminus \{\,j\,\}$. In our case, it is necessarily the Dirac mass on $j$, yet
in the general case, the matrix $H$ is more involved!

The three matrices $P,G,H$ are linked through a simple identity.
\begin{lemma}
	\label{lempot}
	Denoting by $I$ the identity matrix,
we have
$$GP=H+G-I\, .
$$
\end{lemma}
\begin{proof}
The matrix $G$ encodes the behaviour of the process until it hits $j$. Multiplying on the right $G$
by the transition matrix $P$ amounts to perform one further step of the process.
This step might either stay inside
$\{\,0,\dots,N\,\}\setminus \{\,j\,\}$, in which case we recover the matrix $G-I$, or it might land in
$j$, and this is where the matrix $H$ enters the game.
Let us make this argument rigorous.
We have to check that
$$\forall i,k
\in\{\,0,\dots,N\,\}\qquad
	GP(i,k)\,=\,H(i,k)+G(i,k)-I(i,k)\, .
	$$

For $i,k
\in\{\,0,\dots,N\,\}$, we compute
\begin{align*}
GP(i,k) \, =\,
 & \sum_{0\leq\ell\leq N}\, G(i,\ell)\,P(\ell,k)
	\\
\,=\, &
  \sum_{0\leq\ell\leq N}
	E_i\Big(\sum_{n\geq 0 }1_{\{\tau_j>n\}}1_{\{Y_n=\ell\}}\Big)
	\,P(\ell,k) \\
\,=\, &
  \sum_{0\leq\ell\leq N}
	\sum_{n\geq 0 }
	P_i\Big(
	\tau_j>n,\,Y_n=\ell\Big)
	\,P\big(Y_{n+1}=k\,\big|\,Y_n=\ell\big) \\
\,=\, & \sum_{n\geq 0 }
  \sum_{0\leq\ell\leq N}

	P_i\Big(
	\tau_j>n,\,Y_n=\ell,\,
	Y_{n+1}=k \Big)
	\\
\,=\, &
	P(i,j)+
	\sum_{n\geq 1 }

	P_i\Big(
	\tau_j>n,\,
	Y_{n+1}=k \Big)\,.
\end{align*}
We consider now two cases.
If $k=j$, the formula becomes
$$GP(i,j) \,=\,
	\sum_{n\geq 0 }
	P_i\big(
	\tau_j=n+1
	\big)
\,=\,  1\,=\,
	H(i,j)+G(i,j)-I(i,j)\, .
	$$
If $k\neq j$, the formula becomes
\begin{align*}
	GP(i,k) &\,=\,
	P(i,k)+
	\sum_{n\geq 1 }
	P_i\Big(
	\tau_j>n+1,\,
	Y_{n+1}=k \Big)\\
	 &\,=\,
	G(i,k)-I(i,k)
	\,.
\end{align*}
This ends the proof, since $H(i,k)=0$ in this case.
\end{proof}

\noindent
We complete finally the proof of theorem \ref{general}.
We multiply the formula of lemma~\ref{lempot} by $P^n$ and we sum from $0$ to $m$ to obtain
$$

G -G P^{m+1}\,=\,\sum_{n=0}^m \big( P^n -H P^n\big) \,.
$$
We focus on the coefficients $(i,j)$ of the matrices and we send $m$ to $\infty$:

$$
\lim_{m\rightarrow \infty}
\big(G(i,j)
-GP^m(i,j)
\big)\,=\,\sum_{n\geq0} \big( P^n(i,j) - P^n(j,j)\big).
$$
Now $G(i,j)=0$ and
from the convergence~\eqref{ergodic}, we have
\begin{equation*}
\lim_{m\rightarrow \infty}GP^m(i,j)\,=\,
	\Big(\sum_{k=0}^N G(i,k)\Big)\times

	\frac{1}{E\big(\tau_j\,\big|\,Y_0=j\big)}\, .
\end{equation*}
Noticing that
	$$\sum_{k=0}^N G(i,k)\,=\,
	{E\big(\tau_j\,\big|\,Y_0=i\big)}\,,$$
	and putting together the previous identities, we obtain the formula stated in
	theorem~\ref{general}. It then suffices to replace the probabilities with their expression to get theorem \ref{greturngen}.

\bibliographystyle{plain}

config: arxiv


TITLE: finding the max of a function
QUESTION [1 upvotes]: This question popped up during a nights drinking and it has been bugging me ever since.
the conditions are:
$$\left\{\begin{matrix}
x+14y\leq 1820\\
x+25y\leq 2162.5\\
x\geq 0\\
y\geq 0
\end{matrix}\right.$$
The question is what is the maximum possible value of :
\begin{matrix}
\\
4x+3y
\end{matrix}.
It took us 3 lads around an hour and plenty of drawing to solve this.
My question is are there ways to solve this without plotting a graph and purely through equations.
I tried looking up the Lagrange multipliers method but that method falls flat for me as all the derivative are reduced to 1.

REPLY [0 votes]: That region is a polyhedron whose sides are:

the line segment that goes from $(0,0)$ to $(0,86.5)$;
the line segment that goes from $(0,86.5)$ to $(1384.09,31.1364)$;
the line segment that goes from $(1384.09,31.1364)$ to $(130,0)$;
the line segment that goes from $(130,0)$ to $(0,0)$.

Since the gradient of $4x+3y$ is never $0$, the maximum has to be attained at one of the sides. Now, $(x,y)$ belongs to the first side if and only if $x=0$ and $y\in[0,86.5]$. So, $4x+3y$ attains the maximum ($259.5$) at $(0,86.5)$. Do the same thing for the other three sides, and you will get the answer.


TITLE: Values of cyclotomic polynomial and properties of groups
QUESTION [4 upvotes]: There are restrictions on the values of a cyclotomic polynomial evaluated at an integer that are reminiscent of the restrictions on the number of Sylow groups of a group. So I'd like to know if there is a connection.

Does the value of a cyclotomic polynomial evaluated at an integer count something related to the properties of a certain group (for example, something related to its Sylow groups)?

For example, if $n_p$ is the number of $p$-Sylow groups of the group $G$ with $|G|=n=p^\alpha r$, then $n_p\equiv 1 \pmod p$. On the other hand, if $p | \Phi_n(x)$ and $p \not| n$, then $p\equiv 1 \pmod n$. Since the cyclotomic polynomial are closely related to the cyclic groups, their values might count something about the group.

REPLY [3 votes]: I believe
$$ \Phi_n(r) = \frac{LCM(r^k-1, k=1\ldots n)}{LCM(r^k-1,k=1\ldots n-1)} $$
for integers $n \ge 1$ and $r \ge 2$.


TITLE: How do you calculate a partial derivative of a matrix with respect to a scalar in a vector?
QUESTION [1 upvotes]: Let's say I have a matrix, $A$:
\begin{pmatrix} a_{11} & a_{12} \\\ a_{21} & a_{22} \end{pmatrix}
vector $p$:
\begin{pmatrix} p_{1} \\\ p_{2} \end{pmatrix}
and vector $q$:
\begin{pmatrix} q_{1} \\\ q_{2} \end{pmatrix}
If I have some function, $f(....) = \sum_{1\leq i, j \leq n}a_{ij}p_{i}q_{j} $, how can I go about determining what $\frac{\partial{f}}{p_1}$ for instance?
If I do this by hand I get $a_{11}q_{1} + a_{12}q_{2} + 0 + 0$ but how do I do this without evaluating it manually?

REPLY [1 votes]: Write the function using explicit dot products
$$f=(A\cdot q)\cdot p$$
and consider how $f$ changes when $p$ is perturbed
$$\eqalign{
df &= (A\cdot q)\cdot dp
\quad\implies\quad
\frac{df}{dp} &= (A\cdot q) \\
}$$
The same result as obtained by manual component-wise computation.
However the new equation works not only for $2\times 2$ matrices, but for $n\times n$ matrices.


TITLE: What comes after length, area and volume?
QUESTION [28 upvotes]: The length of the unit is 1.
  The area of the unit square is 1.
  The volume of the unit cube is 1.
  The $\color{red}{???}$ of the unit tesseract is 1.
  The $\color{blue}{???}$ of the unit 5-cube is 1.

So this is a fill in the blanks-question, but I've been wondering if there's a common term for this? I'd imagine it'd be "n-volume", but I cannot seem to find any uses of that term, so I'm guessing there is another term?

REPLY [32 votes]: The term "hypervolume" is in use, but that doesn't tell you the dimension. I don't see any trouble using "$4$-volume" to describe the amount of space the unit tesseract occupies.


TITLE: Prove the formula for direction cosines.
QUESTION [1 upvotes]: Pf.

END pf.
I have no idea where they came up with the fact that $a=\hat{i}* \hat{v}$ $/$ $|i|$ or $b=\hat{j}* \hat{v}$ $/$ $|j|$ etc. Can I can get proof explanation?
I don't see this equality:

REPLY [4 votes]: Note that $\hat{i}$, $\hat{j}$ and $\hat{k}$ are orthonormal. Consequently, $\hat{i}\cdot\hat{j}=\hat{i}\cdot\hat{k}=\hat{j}\cdot\hat{k}=0$, and $\hat{i}\cdot\hat{i}=\hat{j}\cdot\hat{j}=\hat{k}\cdot\hat{k}=1$. Therefore, if $\mathbf{v} = a\hat{i}+b\hat{j}+c\hat{k}$ then $\hat{i}\cdot\mathbf{v} = a \hat{i}\cdot\hat{i}+ b \hat{i}\cdot\hat{j} + c \hat{i}\cdot\hat{k}=a$. Similarly, $\hat{j}\cdot\mathbf{v}=b$, and $\hat{k}\cdot\mathbf{v}=c$.


text:
\begin{document}

\title[Polynomials of Annular Surfaces and their Boundary Links]
{On Knot Polynomials of Annular Surfaces and their Boundary Links}
\makeatletter
\author[Hermann Gruber]{Hermann Gruber\thanks{Most of the work was done while the author was at Institut f\"ur Informatik,
Ludwig-Maximilians-Universit\"at M\"unchen,
Oettingenstra\ss{}e~67, D-80538 M\"unchen, Germany.}\\
Institut f\"ur Informatik,
Justus-Liebig-Universit\"at Giessen\addressbreak
Arndtstr. 2, 35392 Giessen, Germany\addressbreak
e-mail: \textup{\texttt{hermann.k.gruber@informatik.uni-giessen.de}}
}
\receivedline{Received \textup{7} March \textup{2008;}
              revised \textup{10} October \textup{2008}}
\makeatother
\maketitle
\begin{abstract}
Stoimenow and Kidwell asked the following question:
Let $K$ be a non-trivial knot, and let $W(K)$ be a
Whitehead double of $K$. Let $F(a,z)$ be the
Kauffman polynomial and $P(v,z)$ the skein polynomial.
Is then always $\max\deg_z P_{W(K)} - 1 = 2 \max\deg_z F_K$?
Here this question is rephrased in more general terms
as a conjectured relation between the maximum $z$-degrees
of the Kauffman polynomial of an annular
surface $A$ on the one hand, and the Rudolph polynomial on
the other hand, the latter being defined as a certain
M\"obius transform of the skein
polynomial of the boundary link $\partial A$.
That relation is shown to hold for
algebraic alternating links, thus simultaneously solving
the conjecture by Kidwell and Stoimenow and a related
conjecture by Tripp for this class of links.
Also, in spite of the heavyweight definition of the
Rudolph polynomial $\{K\}$ of a link $K$,
the remarkably simple formula
$\{\bigcirc\}\{L\#M\}=\{L\}\{M\}$
for link composition is established.
This last result can be used to reduce the conjecture
in question to the case of prime links.
\end{abstract}

\section{Preliminaries.}

We assume the reader is familiar with basic notions in knot theory
as contained, e.g., in~\cite{BZ85}. To fix the notation, we recall
some notions on framed links and framed link polynomials
that are, in part, not yet contained in~\cite{BZ85}.

\subsection{Framed Links.}\label{framed-links}

Let $A$ be an orientable
annulus $S^1 \times I$
contained in an unknotted solid torus $V$ in $S^3$
such that $A$ is parallel to the core of $V$,
and let $N(K)$ denote the tubular neighborhood
of a knot $K$ in $S^3$. Let $h: V \to N (K)$ be an orientation
preserving homeomorphism taking the meridian disk of $V$ to the
meridian disk of $N(K)$ and the core of $V$ to $K$.
The image $h(A)$, a knotted annulus, is called
the {\em framed knot} $A(K,f)$ whose framing $f\in \mathbb{Z}$ is the
linking number of $h(\ell)$ and $K$, with $\ell$ being the preferred
longitude of $V$. The mapping $h$ naturally induces an orientation
on $h(A)$ and its boundary $\partial h(A)$. The notation $A(K,f)$
is justified by the fact that, up to ambient isotopy, $A(K,f)$
depends only on $K$ and $f$. A change of orientation
yields $A(K,f)=A(-K,f)=-A(K,f)$.
The boundary $\partial A(K,f)$ is an oriented $2$-component link,
sometimes referred to as the {\em $f$-twisted double} of $K$.

The above notions readily generalize to links $L$ in $S^3$ with $\mu$
components $C_1,\ldots C_\mu$, by specifying corresponding homeomorphisms
$h_i: V_i \to N(C_i)$, with unknotted solid tori $V_i$ as preimages.
A {\em framed link} is an annular surface $A(L,f)$ specified by a
pair $(L,f)$ as above, but now the framing $f$ maps $L$ to a vector
in $\mathbb{Z}^\mu$ specifying the framing for each component $C_i$.
A {\em sublink} $L'$ of $L$ is obtained from $L$ by erasing zero or more
components from $L$; A framing $f$ of $L$ naturally induces a framing
on the sublinks. As long as there is no risk of confusion, this framing will be also
denoted by $f$.

For a link $L$, let $D = D(L)$ be a diagram of $L$ in $\mathbb{R}^2$.
We call a crossing in $D$ {\em homogeneous} if it involves only
one component, and {\em heterogeneous} in the other case.
We say that the crossing
$\vcenter{\hbox{\includegraphics{fig/positive}}}$  has positive sign,
and the crossing $\vcenter{\hbox{\includegraphics{fig/negative}}}$ has negative sign.
For a link diagram $D(L)$, the {\em writhe} $w(D)$ is the overall sum of the crossings in $D$,
the {\em total linking number} $t(L)$ is half the sum of signs of the heterogeneous crossings
in $D$, and the {\em self-writhe} $sw(D)$ is the sum of signs of the homogeneous crossings in $D$.
The total linking number is invariant under ambient isotopy, and writhe and self-writhe
are regular isotopy invariants. Each link diagram $D = D(L)$ naturally induces
a framing~$f$ onto the surface $A(L,f)$. For a component $C$ of $L$, we have
$f(C) = sw(D|_{C})$, where $D|_C$ is the diagram of~$C$ obtained by erasing
all other components from~$D$.
The self-writhe is sometimes also called {\em total framing}~\cite{Rud90}.

\subsection{Link polynomials.}

The {\em skein polynomial} $P(v,z)$, defined first in~\cite{HOMFLY,PT}
is a Laurent polynomial in two variables $v$ and $z$. It is an ambient isotopy
invariant of oriented knots and links and is defined {\em via} link diagrams
by  the (skein) relation
 $$v^{-1}\vcenter{\hbox{\includegraphics{fig/positive}}}
-v\vcenter{\hbox{\includegraphics{fig/negative}}}=z\vcenter{\hbox{\includegraphics{fig/smooth}}},$$
and agreeing that the polynomial is equal to $\frac{v^{-1}-v}{z}$
for the unknot, the latter being denoted by $\delta_P$ as a shorthand.
In addition, we let the polynomial be equal to $1$ on the empty diagram.
It is not hard to see that then taking the split union of link
diagrams amounts to multiplying their skein polynomials, also if
one of the diagrams is empty.

Similarly, the {\em framed Kauffman polynomial} $L_{K,f}(a,x)$, defined
in~\cite{Kau90}, is an ambient isotopy invariant for framed
links $A(L,f)$ defined via the following relations, and
the convention that the polynomial equals $\frac{a^{-1}+a}{x}-1$
for the unknotted annulus with framing $0$ and $1$ for the empty diagram:

$$\vcenter{\hbox{\includegraphics{fig/positive_uo}}}+\vcenter{\hbox{\includegraphics{fig/negative_uo}}}=
x\left(\vcenter{\hbox{\includegraphics{fig/smooth_uo}}}+\vcenter{\hbox{\includegraphics{fig/smooth2_uo}}}\right);$$
$$\vcenter{\hbox{\includegraphics{fig/kink_uo}}}=a~\vcenter{\hbox{\includegraphics{fig/straight}}};$$
the mirror image of this kink can be resolved by multiplying with $a^{-1}$.

The above diagrams are to be interpreted as parts of band diagrams
of an annular surface that appears untwisted,
and are denoted by  $K_+$, $K_-$, $K_\infty$ and $K_0$ respectively.
Similar to above, write $\delta_L=\frac{a^{-1}+a}{x}-1$
for the polynomial of an unknotted annulus with framing $0$.
The framed Kauffman polynomial can be normalized to an
unoriented link invariant, by letting $U_K =a^{-sw(K)}L_K$, or
to a semi-oriented link invariant, by letting $F_K =a^{-w(K)}L_K$ \cite{Kau90}.

\begin{rem*}
Note that the normalization used here differs from the convention in
some standard works on link polynomials, where these polynomials
equal $1$ on a simple closed circle, resp. an unknotted annulus
with framing $0$, rather than on the empty diagram.
The author deliberately sticks to this convention because many of the formulas
appearing in this paper would become otherwise much more cumbersome.
\end{rem*}

Yamada defined the following linear operator on polynomial
invariants for framed links~\cite{Yam89}:
Let $R_K$ be a polynomial invariant for framed links $K$ under ambient isotopy,
and let~$\lambda$ be a scalar. Let $|K|$ denote the number of components of~$K$.
Then the invariant~$(R_K\oplus\lambda)$ is defined
as $\sum_{K'}\lambda^{|K|-|K'|}R_{K'}$,
where the summation index $K'$ runs over all framed sublinks of $K$,
including the empty link.

Now the {\em framed Rudolph polynomial} $\{K,f\}$ is defined as
$\{K,f\} = (P_{\partial A(K,f)}\oplus(-1))$.
Using~$[K,f]$ as a shorthand for the skein polynomial~$P_{\partial A(K,f)}$,
this is the M\"obius transform $\{K,f\}=\sum_{K'}(-1)^{|K|-|K'|}[K',f]$,
as originally defined in~\cite{Rud90}. Note that for the special case of
knots, we have $\{L,f\}=[L,f]-1$.
Write $A(L,0)$ if the framing for each annulus
has the value~$0$, let $[L]:=[L,0]$ and $\{L\}=\{L,0\}$.
In~\cite[prop. 2(5)]{Rud90}, it is noted
that $\{L,f\}=v^{2sw(L)}\{L\}$, and $\{L\}$ is an ambient isotopy
invariant for the link $L$, that is, independent of the framing~$f$.

\subsection{Inequalities for Link Polynomials}

We briefly recall two known inequalities for the skein polynomial and
the Kauffman polynomial. Morton proved the following inequality:
\begin{thm}[Morton's Inequality]
Let $K$ be a link. For any link diagram $D$ of $K$, let $c(D)$ denote the number
of crossings and $s(D)$ denote the number of Seifert circles obtained from
smoothing out all crossings, i.e. replacing each
$\vcenter{\hbox{\includegraphics{fig/positive}}}$ and
$\vcenter{\hbox{\includegraphics{fig/negative}}}$ with
$\vcenter{\hbox{\includegraphics{fig/smooth}}}$.
Then $\max\deg_z P_K \le c(D) - s(D).$
\end{thm}
Kidwell proved an inequality relating properties of link diagrams
to the maximum $z$-degree of a specialization of the (at that time yet
undiscovered) Kauffman polynomial~\cite{Kid87};
Thistlethwaite later showed that essentially the same proof
applies to the more general Kauffman polynomial~\cite{Thi88}:
\begin{thm}[Kidwell's Inequality]\label{thm:Kidwell}
Let $K$ be a link. For any link diagram $D$ of $K$, let $c(D)$ denote the number
of crossings and $b(D)$ denote the maximal bridge length, i.e. the longest
sequence of consecutive crossing overpasses in $D$. Then
$\max\deg_x F_K \le c(D) - b(D)$. Moreover, equality holds if $D$ is a reduced
alternating and prime diagram.
\end{thm}

\section{Reformulations of Rudolph's Congruence Theorem.}

Rudolph stated a curious theorem \cite{Rud90},
which in part motivates the present study,
relating the Kauffman and Rudolph polynomials with coefficients reduced modulo~$2$.
We start this investigation by taking a closer look at his
Congruence Theorem:

\begin{thm}[Congruence Theorem]
Let $K$ be any link. Then
$$F_K(v^{-2},z^2)\equiv_2 v^{4t(K)}\{K\}.$$
\end{thm}

We can reformulate the theorem in terms of the unoriented
and the framed Kauffman polynomial, rendering the
congruence more natural. In particular, the congruence can also
be used to relate the framed versions of these invariants.
We also present versions involving a M\"obius transform of the
Kauffman polynomial, and the polynomial $[L,f]$, which unveil
a certain symmetry in Rudolph's congruence.

\begin{prop}[Unoriented, framed, M\"obius transformed and Dubrovnik version]\label{prop:congruence-transform}
The following are equivalent reformulations of the congruence theorem:
\begin{eqnarray*}
U_K(v^{-2},z^2)& \equiv_2& \{K\} \\
L_{(K,f)}(v^{-2},z^2)& \equiv_2& \{K,f\} \\
~[K,f] & \equiv_2 & ({L}_{(K,f)}\oplus \pm 1)(v^{-2},z^2)  \\
~[K,f] & \equiv_2 & (D_{(K,f)}\oplus \pm 1)(v^{-2},-z^2)
\end{eqnarray*}
where the sum in the second and the third congruence runs over all
non-empty sublinks $K'$ of $K$.
\end{prop}
\begin{proof}
First, the signs in the $\pm 1$ terms in the congruences
are immaterial since we work with coefficients reduced modulo~$2$.
For every framed link $(K,f)$, we have $w(K)=sw(K)+2t(K)$. Since
$F_K(a,x)=a^{-(sw(K)-2t(K))}L_K =a^{-2t(K)}U_K$,
we see that $F_K(v^{-2},z^2)=v^{4t(K)}U_K(v^{-2},z^2)$,
so that we can rewrite the congruence theorem as in the
first congruence. For the second, we have
$F_K(v^{-2},z^2)=v^{4t(K)}v^{2sw(K)}L_{(K,f)}(v^{-2},z^2)$.
From~\cite[Prop.~2(5)]{Rud90},
we deduce $\{K,f\}=v^{-2sw(K)}\{K\}$. Thus, the second
congruence is also equivalent to the original one.
For the third congruence, we use the fact that
$([K,f]\oplus0) = ([K,f]\oplus(-1)\oplus1) = \sum_{K'}\{K',f\}$,
where the sum runs over all sublinks
of~$K$~\cite[Prop.~1]{Yam89}; finally the
fourth congruence is obtained by
the Interchange Formula (see \cite{Lic88})
$$L_{(K',f)}(v^{-2},z^2)= (-1)^{w(K',f)+|K'|}D_{(K',f)}(v^{-2},-z^2)$$
for switching between the Kauffman and the Dubrovnik polynomial.
\end{proof}

It can be readily seen that the congruence theorem would equally hold
when using the variant $([K,f]\oplus1)$ instead
of $\{K,f\} = ([K,f]\oplus(-1))$.
As we will see later, however, the
current choice is rewarded by an eminently simple formula for the Rudolph
polynomial of composite links.
We note on the fourth version of the congruence that
Yamada  proved in~\cite{Yam89} the remarkable one-variable {\em equality}
$$[L,f](t,t^{\frac{1}{2}}-t^{-\frac{1}{2}}) = (D_{(K,f)}\oplus 1)(t^{-2},t^{-1}-t),$$
The left-hand side of the above equation is the
Jones polynomial of $\partial A(K,f)$ from \cite{Jon85},
normalized to value~$1$ at the empty diagram.

\section{Problem Statement and Preliminary Results}\label{sec:statement}

Kidwell and Stoimenow posed the following question
relating the $x$-degree of the Kauffman polynomial
of a knot and the $z$-degree of its Whitehead
double~(\cite{KidSto03}, see also~\cite{Oht04}):

\begin{conj}[Kidwell, Stoimenow]\label{conj:Kidwell}
Let $K$ be a non-trivial knot, and let $W(K)$ be a
Whitehead double of $K$.
Is then always $\max\deg_z P_{W(K)} - 1 = 2 \max\deg_x F_K $?
\end{conj}

They note that their conjecture holds for all prime knots with up to $11$
crossings, by exhaustive calculation. A related conjecture
by Tripp states that the canonical genus of a Whitehead double
of every knot $K$ coincides with the minimal crossing number
of $K$~\cite{Tri02}. As pointed out by Nakamura~\cite{Nak04},
a possible approach to proving this for prime alternating links would
be to establish $\max\deg_z P_{W(K)} = 2n-2$.
In this special case, this statement is equivalent
to Conjecture~\ref{conj:Kidwell}. We will study here a
variant of this conjecture that also applies to links:
\begin{conj}\label{conj:extended}
Let $A(K,f)$ be a framed link. Then
$$\max\deg_z \{K,f\} = 2 \max\deg_x F_K$$
\end{conj}

We show that under an apparently weak additional condition
on the knots under consideration,
the statement of Conjecture~\ref{conj:extended} implies
the statement of Conjecture~\ref{conj:Kidwell}:

\begin{lem}\label{lem:bridge}
Let $A(K,f)$ be a framed knot for which
$\max\deg_x F_K > 0$, and \\
$\max\deg_z \{K,f\} = 2 \max\deg_x F_K.$
Let $W_K$ be a Whitehead double of $K$.
Then Conjecture~\ref{conj:Kidwell} holds for $K$.
\end{lem}
\begin{proof}
Let $K$ be a knot with $\max\deg_x F_K > 0$ for which
Conjecture~\ref{conj:extended} holds. Then for every framing $f$,
we have $\max\deg_z [K,f] > 0$ since $\{K,f\} = [K,f]-1$.
Let $W(K)$ be the $n$-twisted Whitehead double of $K$.
Applying a skein relation in the region of the clasp of the Whitehead double,
we get
$P_W(K) = v^2 \delta_P +vz [K,n]$, hence
$\max\deg_z P_{W(K)}  = 1 + \max\deg_z [K,n]$.
\end{proof}

The above additional condition $\max\deg_x F_K > 0$ appears to be
very weak, since to the author's knowledge no example of a nontrivial knot
with~$\max\deg_x F_K = 0$ is known.
As a warm-up, it is easy to see that Conjecture~\ref{conj:extended}
in particular holds for all unlinks:
\begin{lem}\label{lem:unlink}
Conjecture~\ref{conj:extended} holds for all trivial links.
\end{lem}
\begin{proof}
Assume $f$ is the framing induced by a diagram $D$ for the $n$-component
trivial link $\bigcirc^n$. Then
$$\{\bigcirc^n,f\} =v^{2sw(D)}\{\bigcirc\}^n =v^{2sw(D)}(1-\delta_P)^n$$
by elementary properties of the Rudolph polynomial stated in \cite{Rud90}.
Thus $\max\deg_z \{\bigcirc^n,f\}=0$. For the Kauffman polynomial,
we similarly have $F_{\bigcirc^n} = \delta_F^n$, and so the maximal
$x$-degree of $F$ equals~$0$ as well.
\end{proof}

We briefly review some previous results related to the above conjectures.
The following generalizes an observation made by Tripp in~\cite{Tri02}:
\begin{prop}\label{prop:extended-ineq}
Let $K$ be a nontrivial $n$-crossing prime alternating link.
Then for every framing $f$, the inequality
$\max\deg_z \{K,f\} \le 2 \max\deg_x F_K$ holds.
\end{prop}
\begin{proof}
Let $D$ be a reduced alternating diagram of $K$ with $n$ crossings,
and let $\widetilde D$ be the diagram obtained by
replacing each arc in $D$ by a corresponding pair of antiparallel arcs.

We apply Morton's inequality to $\widetilde D$:
The number of crossings $c(\widetilde D)$ equals $4n$.
For counting the number of Seifert circles, we follow an idea given
in~\cite{Tri02}: Regard $D$ as a $4$-regular planar graph with~$n$
vertices at the crossings, and, by Euler's polyhedral formula,
with $n+2$ faces.
Then the number of Seifert circles $s(\widetilde D)$ arising from smoothing
out the crossings equals $2n+2$: One for each face of the graph, and one for
each four-crossing region in $\widetilde D$ that corresponds
to a single crossing in $D$.
Since the maximum $z$-degree is not altered by changing the
framing, Morton's inequality gives $\max\deg_z [K,f] \le 2n-2$ for every
framing $f$. Applying the same procedure after deleting some link
components from the diagram~$D$ and corresponding components from the diagram
$D'$, we also get $\max\deg_z [K',f] < 2n-2$ for every proper sublink $K'$ of $K$.
Thus, $\max\deg_z \{K\} \le 2n-2$. On the other hand, Theorem~\ref{thm:Kidwell}
implies that $\max\deg_x F_K = n-1$, since $D$ is a reduced prime alternating
diagram.
\end{proof}
\begin{rem*}
A similar fact was claimed, but with an erroneous proof that
is fixed here, in a draft of an earlier paper
of the present author, see~\cite{Ich03}.
\end{rem*}

Recently, Nakamura proved that $\max\deg_z [K,f] = 2n-2$ for every
$n$-crossing rational link with framing $f$,
generalizing a previous result by Tripp~\cite{Nak04,Tri02}.
Since each of the proper sublinks of a $2$-component
rational link $K$ is by itself a trivial knot or empty, we have in this case
$\{K\} = 1- 2\delta_P^2 + [K]$ and $\max\deg_z [K,f] =\max\deg_z \{K\} =
2n-2$. Together with Lemma~\ref{lem:bridge} and
Proposition~\ref{prop:extended-ineq}, we obtain the following preliminary result:
\begin{prop}
Conjectures~\ref{conj:Kidwell} and~\ref{conj:extended} hold for all rational links.\quad\proofbox
\end{prop}
In the following, we will generalize this result to a much larger class
of links.

\section{Split Union and Composition of Links.}

In this section, we prove that the relation from
Conjecture~\ref{conj:extended} is preserved under split union
and composition, hence reducing the task to proving it
for the case of prime links. The case of disjoint union is
not hard to prove:

\begin{prop}\label{prop:split-links}
If Conjecture~\ref{conj:extended} holds for two framed links
$L_1$, $L_2$, it also holds for the disjoint union $L_1\sqcup L_2$.
\end{prop}
\begin{proof}
For the Kauffman polynomial, we have
$F_{L_1\sqcup L_2}= F_{L_1}F_{L_2}$, see~\cite{Kau90};
and similar for the framed Rudolph polynomial
$\{L_1\sqcup L_2,f\}=\{L_1,f\}\{L_2,f\}$, see~\cite{Rud90}.
\end{proof}

Next, we examine the case of composite links.
Conjecture~\ref{conj:Kidwell} suggests that the
$z$-degree of $[L_1\#L_2,f]$ is additive for nontrivial knots
$L_1$,$L_2$ --- since for the Kauffman polynomial of composite links,
the relation $F_{L_1\#L_2}=\delta_F F_{L_1}F_{L_2}$ holds~\cite{Kau90}.
But if one of the factor links $L_1$,$L_2$ is the unknot $\bigcirc$,
the additive behavior of $\max\deg_z$
holds {\em if and only if} we choose the framing
in a way such that $[\bigcirc,f]$ has nonnegative degree.
Despite these seeming complications, we can indeed derive a formula for
$[L_1\#L_2,f]$ using linear skein theory.
We need the following definition.
\begin{defn}
For an appropriately oriented tangle~$P$,
its {\em numerator closure}, denoted by~$P^N$,
and its {\em denominator closure}, denoted by~$P^D$,
are the links obtained by  closing up the pending ends
as shown in the left and middle diagram of
Figure~\ref{fig:numdensum}. The right part of Figure~\ref{fig:numdensum}
shows the link obtained as the {\em total sum} of two tangles $P$ and $Q$,
denoted by~$(P+Q)^N$.
\end{defn}

\begin{figure}\label{fig:numdensum}
\includegraphics[scale=.8]{fig/tangles}
\caption{Numerator closure, denominator closure and total sum}
\end{figure}

\begin{prop}\label{composite}
Let $A(L,0)=K_A\#_{B}J$ be a composite framed link
obtained by joining the component $A$ of $K$
with the component $B$ of $J$. Then
\begin{equation*}

(\delta_P^2-1)[L]= \delta_P^2 [K\setminus A]\cdot
[J\setminus B] +  [K]\cdot[J]- [K\setminus A]\cdot[J] - [K]\cdot[J\setminus B]

\end{equation*}
\end{prop}
\begin{proof}
Lickorish and Millet  showed that the following formula holds
for the skein polynomial of the total sum of two tangles
$Q$ and $R$, referred
to as the numerator-denominator formula \cite{LicMil87}.
$$(\delta_P^3-\delta_P)P_{(Q+R)^N} = \delta_P\left(P_{Q^N} P_{R^N} + P_{Q^D}P_{R^D}\right)-
\left(P_{Q^N}P_{R^D}+P_{Q^D}P_{R^N}\right),$$
 We can interpret $\partial A(L,0)$ as the total sum of tangles $Q$ and $R$,
with $\partial A(K,0)=Q^D$, and $\partial A(J,0)=R^D$.
Then we get $$Q^N=\partial A(K\setminus A,0)\,\sqcup\,\bigcirc,~R^N = \partial A(J\setminus B,0)\,\sqcup\, \bigcirc.$$
Applying the numerator-denominator formula to this total sum
yields the result.
\end{proof}

We have obtained a somewhat complex formula describing the polynomial $[L]$
under link composition. Astonishingly, the Rudolph polynomial
admits a rather simple and natural formula for link composition.

\begin{thm}[The Composition Formula]\label{thm:composition}
Let $L=K\#J$ be a composite link with factors $K$ and $J$.
Then $$\{\bigcirc\}\{K\#J\}=\{K\}\{J\}.$$
\end{thm}

\begin{proof}
Assume the components $A$ and $B$ are joined to form the composite link
$L=K_A\#_{B}J$. Then we use $C$ to denote the resulting joint component.
We order the $r = 2^{|L|-1}$ sublinks of $L$ containing the
joint component $C$, and denote them by $M_1,M_2\ldots M_{r}$.
Then, by definition of the Rudolph polynomial,
\begin{equation}\label{drigg1}
\{\bigcirc\}\{L\}= (\delta_P^2-1)\left(\sum_{k=1}^{r}\left((-1)^{|L|-|M_k|}[M_k]\right)-\{L\setminus C\}\right).
\end{equation}
Note that the term $-\{L\setminus C\}$ on the right hand side of
Equation~\eqref{drigg1} has negative sign
since $(-1)^{|L|} = -(-1)^{|L\setminus C|}$.

Each of the sublinks $M_k$ is of the form $K'_A\#_B J'$
for some sublinks $K' \subseteq K$ and $J'\subseteq J$.
Proposition~\ref{composite} allows to compute the skein polynomial
of these links in terms of sublinks of $K \sqcup J$. In order to do so,
we associate with each $M_k$ the following four sublinks of $K \sqcup J$:
\begin{itemize}
\item the sublink $L_{1,k}=(K'\setminus A)\sqcup(J'\setminus B)$, containing
  neither $A$ nor $B$,

\item the sublink $L_{2,k}= K' \sqcup J'$, containing both $A$ and $B$,

\item the sublink $L_{3,k}=(K'\setminus A)\sqcup J'$, containing $B$ but not $A$,

and
\item the sublink $L_{4,k}=K'\sqcup(J'\setminus B)$, containing $A$ but not $B$.
\end{itemize}

Note that the above association partitions the set of sublinks
of $K \sqcup J$ into four sets
the sense that $\bigcup_{j=1}^4\left(\bigcup_{k=1}^r L_{j,k}\right)$
equals the set of all sublinks of $K \sqcup J$. Thus,
\begin{equation}\label{drigg2}
\{K\sqcup J\} =  \sum_{j=1}^{4}\sum_{k=1}^{r}
 (-1)^{|K|+|J|-|L_{j,k}|}[L_{j,k}].
\end{equation}
Fix a sublink $M_k$ for the moment. By Proposition~\ref{composite} and
the fact that the skein polynomial is multiplicative under split union,
we obtain:
\begin{equation}
(\delta_P^2-1)[M_k] =
 \delta_P^2 [L_{1,k}]+[L_{2,k}]  -[L_{3,k}] -[L_{4,k}].
\end{equation}
Observe that $|L_{1,k}|$ and $|L_{2,k}|$ both have parity different
from $|M_k|$, while $|L_{3,k}|$ and $|L_{4,k}|$ have the same parity
as $|M_k|$. Thus, for instance $(-1)^{|L|-|M_k|} = (-1)^{|L|+1-|L_{1,k}|}$.
Hence, when multiplying both sides of the above equation with
$(-1)^{|L|-|M_k|}$, using analogous considerations,
we obtain the following equation:
\begin{equation}
\begin{split}
(\delta_P^2-1)(-1)^{|L|-|M_k|}[M_k] =\delta_P^2& (-1)^{|L|+1-|L_{1,k}|} [L_{1,k}]\\
+&(-1)^{|L|+1-|L_{2,k}|} [L_{2,k}] \\
+&(-1)^{|L|+1-|L_{3,k}|}[L_{3,k}] \\
+&(-1)^{|L|+1-|L_{4,k}|}[L_{4,k}] \\
\end{split}
\end{equation}
By adding the term $(\delta_P^2-1) (-1)^{|L|-|L_{1,k}|}[L_{1,k}]$
to both sides of the equation, we get:
\begin{equation}\label{drigg3}
(\delta_P^2-1)\left((-1)^{|L|-|M_k|}[M_k] +(-1)^{|L|-|L_{1,k}|} [L_{1,k}]\right)
= \sum_{j=1}^4 (-1)^{|L|+1-|L_{j,k}|}[L_{j,k}]
\end{equation}
Now we treat $k$ again as variable, and
sum up left hand sides and right hand sides of
Equation~\eqref{drigg3} for $k=1$ up to $r$. By virtue of
the equality $|L|+1 = |K|+|J|$, we can use
Equation~\eqref{drigg2} to simplify the resulting right-hand side, and
get:
\begin{equation}\label{drigg4}
(\delta_P^2-1)\left(\sum_{k=1}^r
\left((-1)^{|L|-|M_k|}[M_k]\right) +\sum_{k=1}^r\left((-1)^{|L|-|L_{1,k}|} [L_{1,k}]\right)\right)
= \{K\sqcup J\}
\end{equation}
A basic property of the Rudolph polynomial is
$\{K\sqcup J\} = \{K\}\{J\}$ (see~\cite{Rud90}), so the right-hand side of
Equation~\eqref{drigg4} equals the right-hand side of the equation
in the statement of the theorem.

To simplify the left-hand-side of Equation~\eqref{drigg4},
observe that the set $\{\,L_{1,k} \mid 1 \le k \le r\,\}$
equals the set of sublinks of the link $L \setminus C$.
Obviously, $|L|=|L\setminus C|+1$, hence
\begin{equation}
\sum_{k=1}^r(-1)^{|L|-|L_{1,k}|} [L_{1,k}]= -\{L \setminus C\}.
\end{equation}
Therefore, the left hand side of Equation~\eqref{drigg4}
equals the right hand side of Equation~\eqref{drigg1}.
This completes the proof of the theorem.
\end{proof}

The composition formula reduces the problem of proving
Conjecture~\ref{conj:extended} to the case of prime
links. In particular, it allows us to drop the primality
condition from Proposition~\ref{prop:extended-ineq}:
\begin{cor}
If $K$ is an alternating knot, then
$$\max\deg_z \{K \} \leq 2\max\deg_x F_K.\mathproofbox$$
\end{cor}

With the aid of the composition formula, it is now
also easy to verify that Conjecture~\ref{conj:Kidwell}
holds for infinitely many non-alternating knots, since that
conjecture has been verified in particular
for all prime (also non-alternating)
knots of crossing number at most $11$~\cite{KidSto03}.
We can of course construct infinitely many different
composite knots whose prime
factors are non-alternating and have at most $11$ crossings each.
In these cases, Lemma~\ref{lem:bridge} is applicable, so this
fact extends to Conjecture~\ref{conj:extended}.

We conclude this section with a further
property of the Rudolph polynomial which can be derived
from the composition formula:
Note that the expression $K\#J$ is ambiguous in the case
where at least one of $K,J$ is a link---the ambiguity disappears
only if we write $K_A\#_{B}J$ instead. Thus, similar to the case of
the skein polynomial~\cite{LicMil87}, we have
\begin{cor}
There exist infinitely many pairs of nonequivalent links with the same
Rudolph polynomial.\quad\proofbox
\end{cor}

\section{Algebraic Alternating Links}

In this section, we apply the congruence theorem to
identify a large class of alternating links for which
Conjecture~\ref{conj:extended} holds true.
This class in particular contains all algebraic alternating links.

We need some additional notions first.
The framed Kauffman polynomial $L_{K}(a,x)$ can be equivalently
seen as a single-variable Laurent polynomial in $x$ over $\mathbb Z[a^{\pm 1}]$.
Then the coefficient of the maximal power in $x$ is a polynomial in $a$,
denoted by $X_{K}(a)$. (Here we use the framed version because
below we make use of some results on that polynomial from~\cite{Thi88}.)
Let $c(K)$ denote the minimal crossing number of~$K$.
Now the congruence theorem can be used to show that
Conjecture~\ref{conj:extended} holds in the case
where $X_K(a)$ does not vanish when reduced modulo $2$:

\begin{thm}
Assume $K$ is an alternating link with $X_K(a)\not\equiv_2 0$.
Then Conjecture~\ref{conj:extended} holds for $K$.
\end{thm}

\begin{proof}
By virtue of Proposition~\ref{prop:extended-ineq}, it suffices
to show the inequality $\max\deg_z \{K\} \ge 2\max\deg_x F_K(x,z)$.
Also, by virtue of Lemma~\ref{lem:unlink} and the composition formula
(Theorem~\ref{thm:composition}),
we may assume $K$ is nontrivial and prime.
Write $F_K(a,x)\mod 2$ for the Kauffman polynomial
with coefficients reduced modulo $2$.
Since $X_K(a)$ does not vanish when reduced modulo $2$,
$\max\deg_x L_K(a,x) \mod 2 =\max\deg_x F_K(a,x)$. Moreover,
Theorem~\ref{thm:Kidwell} yields $\max\deg_x L_K(a,x)=n-1$
for a nontrivial prime alternating framed link $K$ with minimal
crossing number~$n$.
By the congruence theorem, we can deduce $\max\deg_z \{K,f\} \ge 2(n-1)$,
and since the maximum $x$-degree of the framed Kauffman polynomial
is independent of the framing provided it is greater than $0$,
which is the case since $n \ge 2$, we have
$\max\deg_z \{K\} \ge 2(n-1) = 2\max\deg_x F_K(x,z)$.
\end{proof}

The first alternating knots violating the condition $X_K(a)\not\equiv_2 0$
are the knots $8_{16}$ and $8_{17}$. These are also among the first
alternating knots which are not algebraic. Indeed,
Thistlethwaite investigated the polynomial~$X_K(a)$
for prime alternating links, and found the equality
\[ X_K(a) = \kappa  (a^{-1}+a)z^{n-1},\]
where $n$ denotes the number of crossings in a reduced alternating diagram,
and $\kappa$ denotes the {\em chromatic invariant} of a basic Conway polyhedron
into which~$K$ can be inscribed, see~\cite{Biggs74,Con69,Thi88} for precise
definitions and more background information.
There are probably infinitely many basic Conway polyhedra with odd chromatic
invariant, and each of them gives rise to an infinite family of alternating
links for which the above theorem is applicable.
In particular, algebraic alternating links can be inscribed into the
basic Conway polyhedron $1^*$, for which $\kappa=1$ holds~\cite{Thi88}.
We thus obtain our second main result:
\begin{thm}
Conjecture~\ref{conj:extended} holds for all algebraic alternating links.
\quad\proofbox
\end{thm}
Furthermore, the same fact holds for alternating links that can be
inscribed into the basic Conway polyhedra $8^*$, $10^{**}$, and a
few other small basic polyhedra which are known to have odd
chromatic invariant, as computed in~\cite{Thi88}.

\section{Conclusion}

To the author's knowledge, the relation between the skein polynomial
and the $2$-variable Kauffman polynomial is not yet understood very well.
A notable exception is Rudolph's Congruence Theorem. The present paper
contains a framed variant of this theorem, which relates the
framed Kauffman polynomial of a knotted annulus $A(K,f)$ and the
skein polynomial of its boundary link $\partial A(K,f)$.

Next, a new conjectured relation between the skein polynomial
and the $2$-variable Kauffman polynomial was presented,
which generalizes, at least under a weak additional assumption,
a recent conjecture by Kidwell and Stoimenow, and, in the case of
prime alternating knots, a recent conjecture by Tripp.
The present research report studied the the behavior of
the Rudolph polynomial under basic operations on links. In particular,
an unexpectedly natural formula for the Rudolph polynomial of composite links
was found. We proved that the conjectured relation is preserved under split
union and link composition, and established its truth for a large class of
alternating links. This class properly contains the algebraic
alternating links, and for this class
the mentioned additional assumption is true, namely that the $x$-degree of the
Kauffman polynomial is greater than zero.
Hence, the conjectures by Kidwell and Stoimenow and Tripp turn out to hold
for algebraic alternating knots. A weaker result heading into the same direction
is found in a recent preprint by Brittenham and Jensen, establishing
the conjecture for alternating pretzel knots~\cite{BriJen06}.
That work, although appearing later than a preprint of the present paper,
is apparently independent of the present work,
since their proof is in part geometric, based on canonical Seifert surfaces.
It would be interesting to see whether these approaches admit a joint
generalization, in particular for proving the conjecture for a larger family
of non-alternating links.
Another interesting line of research concerns the relation of
the framing variable~$v$ of the Kauffman polynomial and the
Rudolph polynomial.
Some results in this direction are found already in~\cite{Nutt97,Nutt99,Rud90}.

\begin{acknowledgment}
Many thanks to Lee Rudolph for pointing the author to
reference~\cite{Rud90}; this enabled the author to establish
substantially more general results than in a first draft of
the present paper.
Thanks also to Alexander Stoimenow for some interesting discussion
during the early stage of this work, and to an anonymous referee for some
valuable corrections and suggestions.
\end{acknowledgment}

\bibliographystyle{numeric}


TITLE: a basic question in crossed product for compact group action
QUESTION [2 upvotes]: I am quite new into crosssed product of Fréchet algebras or C$^*$-algebras. So if the question is too basic please excuse me.
Suppose we have two Fréchet algebras or C$^*$-algebras $A$ and $B$ and they are isomorphic by a map $\phi$. Moreover $G$ be a compact Lie group acting on $A$ and $B$ by $\alpha$ and $\beta$ respectively. When can we say that $\phi$ extends to a isomorphism of the crossed products $A\rtimes_{\alpha} G$ and $B\rtimes_{\beta} G$?

REPLY [1 votes]: A sufficient condition is that $\phi$ intertwines the actions. Also, note that saying that $\phi$ "extends" to an isomorphism on the crossed products is slightly incorrect, since in general there is no inclusion $A\to A\rtimes G$.


TITLE: Provability and computability
QUESTION [1 upvotes]: Is there an algorithm whose correctness is not provable? That is, it works but we are sure that we will never know that it’s correct. I’m basically exploring the difference between computability and provability: does the former imply the latter? What’s the relationship between the two concepts?
On the one hand I think provability is stronger, because there are facts that can be proved but never verified. And if it’s provable, then you can search for the proof in finite time. On the other hand, the existence of unprovable statements is equivalent to the existence of undecidable problems, since both concepts are regarding finiteness.

REPLY [4 votes]: Yes, it is easy to write programs whose correctness is not provable or disprovable in, say, ZFC (or whatever other computably axiomatized theory you prefer). For instance, let's say that $P$ is a program that solves some problem. Consider the program $P'$ which does the following: on an input of size $n$ it searches for a proof of size at most $n$ that ZFC is not consistent. If it finds such a proof then it gives some garbage as its output. If it doesn't find such a proof then it just does whatever $P$ would do.
Assuming ZFC is consistent, this program will solve the problem correctly. But ZFC can't prove that because then ZFC would prove that ZFC is consistent.
For what it's worth, Adam Yedidia and Scott Aaronson have worked on finding the smallest Turing machine whose behavior is not provable in ZFC. See here for the paper.


TITLE: Rotated matrix and rotated eigenvectors.
QUESTION [0 upvotes]: Let $R_\theta$ be a rotational matrix,
my intuition (from experiences with quadratic forms)
tells me that if $A$ has an eigenvector $v$,
then $R_\theta^T A R_\theta$ has an eigenvectors $R_\theta v$.

Is this true?
If so, how can I prove this?

REPLY [0 votes]: Close.
If $v$ is an eigenvector of $A$, then $v' = R_\theta^T v$ is an eigenvector of $R' =R_\theta^T A R_\theta$, with the same eigenvalue.
Proof:
$$
A v = \lambda v
$$
$$
R'v' = (R_\theta^T A R_\theta) (R_\theta^T v) = R_\theta^T A (R_\theta R_\theta^T) v
$$
$$
 = R_\theta^T A v = R_\theta^T \lambda v = \lambda (R_\theta^T v) = \lambda v'
$$
This proof relies on the equation: $R_\theta R_\theta^T = I$, which is true for rotations.