TITLE: Number of bit strings of length four do not have two consecutive 1s
QUESTION [3 upvotes]: I came across following problem:

How many bit strings of length four do not have two consecutive 1s?

I solved it as follows:

Total number of bit strings of length: $2^4$
  Total number of length 4 bit strings with 4 consecutive 1s: 1
  Total positions for three consecutive 1s in length 4 bit string: 2 (111X, X111)
  Number of bit strings for each of above positions: 2 (X can be 0 or 1)
  Total positions for two consecutive 1s in length 4 bit string: 3 (11XX, X11X, XX11)
  Number of bit strings for each of above positions: 4
  By inclusion exlcusion principle, the desired count $=2^4-3\times 4+2\times 2-1=16-12+4-1=7$

However the correct solution turns out to be 8. It seems that I incorrectly applied inclusion exclusion principle. Where did I go wrong?

REPLY [5 votes]: Inclusion-Exclusion to Count Bad Strings
To count the number of bit strings with $2$ consecutive one bits (bad strings), I would let
$$
\begin{align}
S_1&=11xx&4\\
S_2&=x11x&4\\
S_3&=xx11&4\\
N_1&=&12
\end{align}
$$
Then
$$
\begin{align}
S_1\cap S_2&=111x&2\\
S_1\cap S_3&=1111&1\\
S_2\cap S_3&=x111&2\\
N_2&=&5
\end{align}
$$
and
$$
\begin{aligned}
S_1\cap S_2\cap S_3&=1111&1\\
N_3&=&1
\end{aligned}
$$
The count of bad strings is $N_1-N_2+N_3=8$.
The count of good strings is $16-8=8$.

Generating Functions
Let $x$ represent the atom '$0$' and $x^2$ represent the atom '$10$' and build all possible strings by concatenating one or more atoms and removing the rightmost '$0$'.
$$
\begin{align}
\overbrace{\vphantom{\frac1x}\ \ \ \left[x^4\right]\ \ \ }^{\substack{\text{strings of}\\\text{length $4$}}}\overbrace{\ \quad\frac1x\ \quad}^{\substack{\text{remove the}\\\text{rightmost '$0$'}}}\sum_{k=1}^\infty\overbrace{\vphantom{\frac1x}\left(x+x^2\right)^k}^\text{$k$ atoms}
&=\left[x^4\right]\frac{1+x}{1-x-x^2}\\
&=\left[x^4\right]\left(1+2x+3x^2+5x^3+8x^4+13x^5+\dots\right)\\[9pt]
&=8
\end{align}
$$
Note that the denominator of $1-x-x^2$ induces the recurrence $a_n=a_{n-1}+a_{n-2}$ on the coefficients.

Recurrence
Good strings of length $n$ can be of two kinds: a good string of length $n-1$ followed by '$0$' or a good string of length $n-2$ followed by '$01$'. That is,
$$
a_n=a_{n-1}+a_{n-2}
$$
Starting with
$a_0=$ the number of good strings of length $0=1$.
$a_1=$ the number of good strings of length $1=2$.
we get $a_4=8$.


text:
\begin{document}
\title
{The generalized Yamada polynomials of virtual spatial graphs}

\author{Qingying Deng}
\address{School of Mathematical Sciences,Xiamen University, Xiamen, Fujian 361005,
P. R. China. E-mail: qydeng.xmu@gmail.com (Q. Y. Deng)}

\author{Xian'an Jin}
\address{School of Mathematical Sciences,Xiamen University, Xiamen, Fujian 361005,
P. R. China. E-mail: xajin@xmu.edu.cn (X. Jin)}

\author{Louis H. Kauffman}
\address{Department of Mathematics, Statistics and Computer Science \\ 851 South Morgan Street   \\ University of Illinois at Chicago\\
Chicago, Illinois 60607-7045\\ and\\ Department of Mechanics and Mathematics\\ Novosibirsk State University\\Novosibirsk, Russia\\E-mail: kauffman@uic.edu (L. Kauffman)}

\begin{abstract}
Classical knot theory can be generalized to virtual knot theory and spatial graph theory. In 2007, Fleming and Mellor combined virtual knot theory and spatial graph theory to form, combinatorially, virtual spatial graph theory. In this paper, we introduce a topological definition of virtual spatial graphs that is similar to the topological definition of a virtual link. Our main goal is to generalize the classical Yamada polynomial that is defined for a spatial graph. We define a generalized Yamada polynomial for a virtual spatial graph and prove that it can be normalized to a rigid vertex isotopic invariant and to a pliable vertex isotopic invariant for graphs with maximum degree at most 3. We consider the connection and difference between the generalized Yamada polynomial and the Dubrovnik polynomial of a classical link. The generalized Yamada polynomial specializes to a version of the Dubrovnik polynomial for virtual links such that it can be used to detect the non-classicality of some virtual links. We obtain a specialization for the generalized Yamada polynomial (via the Jones-Wenzl projector $P_2$ acting on a virtual spatial graph diagram), that can be used to write a program for calculating it based on Mathematica Code.
\end{abstract}

\keywords{Virtual spatial graph; generalized Yamada polynomial; Dubrovnik polynomial; Jones-Wenzl projector}

\subjclass[2000]{57M27 }

\maketitle

\section{Introduction}

\noindent

A knot is a closed 1-manifold embedded in $\mathbb{R}^3$.
A link is a disjoint union of finitely many closed 1-manifolds embedded in $\mathbb{R}^3$.
Knot theory is the study of isotopy classes of circles embedded in $\mathbb{R}^3$.
Any link can be described by its \textit{diagram}, the result of projecting the embedding in $\mathbb{R}^3$ to a plane, retaining information about over-strand and under-strand on each crossing.
The notion of studying topological embeddings of spatial graphs has been in the literature for a long time. For example, see Section 5 in \cite{RHFox}.

In 1989, Kauffman \cite{Kau89} and Yamada \cite{Yam} independently introduced the notion of a diagrammatic \textit{spatial graph} (that is, a graph in $\mathbb{R}^3$), which extended  diagrammatic knot theory.
The theory of spatial graphs studies two types of isotopy classes of graphs embedded in $\mathbb{R}^3$: graphs with rigid vertices and graphs with nonrigid (topological) vertices.
Later, Kauffman \cite{VKT} introduced the notion of a \textit{virtual knot}, which is an extension of classical knot theory.
Moreover, Kamada \cite{Kam} introduced the notion of an abstract link diagram, and it is proved that there is a bijection from the equivalence classes of virtual link diagrams to an appropriate equivalence relation on abstract link diagrams.
Fleming and Mellor introduced the notion of a \textit{virtual spatial graph} (see Section \ref{S:virtualsg}) by using a combinatorial method in \cite{Fleming07}, which combined a spatial graph and a virtual knot.
They also defined the Yamada polynomial of virtual spatial graphs based on the idea of the original Yamada polynomial for spatial graphs.
But it is very weak in the sense that Miyazawa \cite{Miyazawa} defined a new type Yamada polynomial for virtual spatial graphs via adding a new parameter $\varepsilon$ with value $\pm1$. Miyazawa's polynomial will correspond to our generalized Yamada polynomial $R(D;\alpha,x)$ with $\alpha=A$ and $x=\pm1$.

Furthermore, the theory of virtual spatial graphs studies two kinds of isotopy classes of graphs embedded in orientable thickened surface $S_g\times I$, where $S_g$ is a compact orientable surface with genus $g$ and $I$ is a unit interval of $[0,1]$.
In \cite{KauMishra}, Kauffman and Mishra proposed the concept of \textit{a virtual graph} which is equivalent to a 4-regular virtual spatial graph as virtual rigid vertex graph (see Section \ref{S:virtualsg}).
In \cite{KauMishra}, degree 4 vertices are considered as special crossings, i.e., in a virtual graph, there are three types of transverse double points.
However, Kauffman and Manturov in \cite{KauMan} use the term ``virtual graph'' to mean a 4-regular graph with virtual crossings only.
We therefore note that from our point of view an acceptable usage is ``virtual graph'' for arbitrary cyclic graph (See Definition \ref{D:cyclic}) with virtual crossings immersed in the plane. The term ``spatial'' is reserved for diagrams that have classical crossings.

Very recently, Snyder and Miller \cite{SnyderMiller} defined the notion of a virtual graph (equivalently, cyclic graph) in a topological way.
And they define the $S$-polynomial for virtual graphs which is a little different from  (but similar with) our generalized Yamada polynomial for cyclic graphs.
They also defined the Yamada polynomial for virtual spatial graphs which is based on the $S$-polynomial.

For related studies of spatial graphs, please refer to \cite{Hanaki,Harvey,KKKP,LLLV,Murakami,Yam}.
For related studies of virtual spatial graphs, please refer to
\cite{Fleming07,fm3,KauMishra,Miyazawa,SnyderMiller}.

Understanding the equivalence classes of the virtual spatial graphs is an important issue.
Therefore, people try to generalize the related research in knot theory, virtual knot theory, and spatial graph theory to virtual spatial graphs.
Fleming and Mellor's article \cite{Fleming07} generalized some concepts in classical and virtual knot theory such as fundamental groups and quandles.
And they proved that the fundamental group and quandle are both pliable vertex (topological) isotopy invariants.

The paper is organized as follows:
In Section \ref{S:virtualsg}, we introduce a topological definition of the virtual spatial graph which is similar to the topological definition of a virtual link.
We define the generalized Yamada polynomial of virtual spatial graphs (as virtual rigid vertex graph and virtual pliable vertex graph) via their diagrams in Section \ref{S:GYP}.
We shall consider the connection and difference between it and the Dubrovnik polynomial of classical links in Section \ref{S:Dubrovnik}.
As an application of the generalized Yamada polynomial, by the Jones-Wenzl projector $P_2$ acting on a virtual spatial graph diagram,
we get a special parameter for the generalized Yamada polynomial, which can be used to write a program for calculating the generalized Yamada polynomial based on \textit{Mathematica} Code in Section \ref{S:Application}.

\section{Virtual spatial graphs}\label{S:virtualsg}

\noindent

Let us start with the definitions and introduce the notation.

\begin{defn}
Let $G=(V,E)$ be a graph embedded in $\mathbb{R}^3$. We say $G$ is a \textit{spatial graph}.
\end{defn}

\begin{defn}\cite{Yam,Kau89,KV}\label{kvd}
A \textit{spatial graph diagram} is a planar representation of a spatial graph and it is analogous to the link diagram of a link.
In the spatial graph diagram, vertices of the graph are represented by planar nodes as in Figure \ref{F:classicalmoves}, and all crossings are in generic form as in a classical link diagram.
\end{defn}

A $\textit{virtual link diagram}$ consists in a finitely many closed 1-manifolds generically immersed in $\mathbb{R}^2$ such that each double point is labeled to be (1) a classical crossing which is indicated as usual in classical knot theory or (2) a virtual crossing which is indicated by a small circle around the double point.
The moves (I)-(III) and (I*)-(IV*) for virtual link diagrams illustrated in Figures \ref{F:classicalmoves} and \ref{F:virtualmoves} are called $\textit{generalized Reidemeister moves}$.
The $\textit{Detour move}$ illustrated in Figure \ref{dm} is equivalent to a combination of moves (I*)-(IV*) in Figure \ref{F:virtualmoves}.
Two virtual link diagrams are said to be \textit{equivalent} if they are related by a finite sequence of generalized Reidemeister moves.
We call the equivalence class of a virtual link diagram a $\textit{virtual link}$.
We refer the reader to \cite{VKT,Kau3} for further details about virtual links.

\begin{defn}
A \textit{virtual spatial graph diagram} is a graph generically immersed in $\mathbb{R}^2$, that is, there are two kinds of double points: virtual crossings and classical crossings.
A virtual spatial graph diagram is analogous to the spatial graph diagram of a spatial graph, with the addition of virtual crossings.
\end{defn}

\begin{figure}[!htbp]
\centering
\includegraphics[width=10cm]{classicalmoves.eps}
\caption{Reidemeister\,moves for spatial graph diagrams.}
\label{F:classicalmoves}
\end{figure}

\begin{figure}
  \centering
  \includegraphics[width=8cm]{virtualmoves.eps}
 \caption{Reidemeister\,moves for virtual spatial graph diagrams.}
 \label{F:virtualmoves}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=3.5in]{f2.eps}
\caption{Detour move.}
\label{dm}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=9cm]{forbiddenmoves.eps}
\caption{Forbidden moves on virtual spatial graph diagrams.}
\label{F:forbiddenmoves}
\end{figure}

Figure \ref{F:classicalmoves} illustrates the Reidemeister moves for spatial graph diagrams. In \cite{Fleming07},
Fleming and Mellor added five moves with virtual crossings for virtual spatial graph diagrams as shown in Figure \ref{F:virtualmoves}.
\begin{defn}
In virtual spatial graph diagrams, there are the following four kinds of isotopy deformations.
\begin{itemize}
  \item Moves (II)-(III) and moves (I*)-(V*) generate \textit{{\bf regular deformation}}.
  \item Moves (I)-(III) and moves (I*)-(V*) generate \textit{{\bf ambient isotopic deformation}}.
  \item Moves (I)-(V) and moves (I*)-(V*) generate \textit{{\bf rigid vertex deformation}}, where the cyclic order of the half-edges around each vertex is fixed.
  \item Moves (I)-(VI) and moves (I*)-(V*) generate \textit{{\bf pliable vertex deformation}}, where the order of the half-edges around each vertex can be changed using move (VI).
\end{itemize}
\end{defn}

\begin{rem}
The four moves shown in Figure \ref{F:forbiddenmoves} are forbidden. They are not in the list of Reidemeister moves for virtual spatial graph diagrams although they are not a combination of Reidemeister moves for virtual spatial graph diagrams.
\end{rem}

Two virtual spatial graph diagrams are said to be \textit{regular, ambient, rigid vertex and pliable vertex isotopic} if they are related by a finite sequence of regular, ambient isotopic, rigid vertex and pliable vertex deformations, respectively.
We call the rigid vertex and pliable vertex isotopic equivalence class of a virtual spatial graph diagram as a \textit{virtual rigid vertex graph and virtual pliable vertex graph}, respectively.
That is, for this study, two types of virtual spatial graphs are considered: graphs with rigid vertices and graphs with nonrigid (topological) vertices.
Note that, virtual rigid vertex graph means that a vertex of the graph is regarded as a disk, but virtual pliable vertex graph means that the vertex of graph is a topological vertex such that the cyclic order of the half-edges around each vertex can be changed at will.

Let $S_g$ be a compact orientable surface with genus $g$ and $I$ be the unit interval $[0,1]$. It is also well known that a link diagram drawn on $S_g$, considered up to Reidemeister moves, is equivalent to a virtual link in the thickened surface $S_g\times I$, considered up to isotopy,
Similarly, we will give a topological definition of the virtual spatial graph.

\begin{defn}
Let $G=(V,E)$ be a graph embedded in the thickened surface $S_g\times I$.  We say $G$ is a \textit{virtual spatial graph}.
\end{defn}

We say that two such surface embeddings are \textit{stably equivalent} if one can be obtained from the other by  rigid vertex isotopy (or pliable vertex isotopy) in the thickened surface, homeomorphisms of surfaces,
and the addition or subtraction of handles not incident to images of curves in the graph.
That is, one can perform surgery on the surface along curves that do not intersect the virtual spatial graph diagram on
the surface.

Similar to virtual knot theory, we obtain the following result for the virtual spatial graph diagrams.
\begin{thm}
\label{T:stableequivalent}
Two virtual spatial graph diagrams are rigid vertex isotopic or pliable vertex isotopic if and only if their corresponding surface embeddings are stably equivalent. In each case, we take the corresponding diagrammatic relations on the surfaces, plus surface homeomorphism and stabilization.
\end{thm}
\begin{proof}
The proof is similar to the proof for the case of virtual link diagrams as in
\cite{Car2000}.
\end{proof}
\begin{defn}
\label{D:cyclic}
A \textit{cyclic graph} consists of an abstract graph $G$ and a cyclic ordering of the half-edges at each vertex.
\end{defn}
\begin{defn}\cite{Mo}
A $\textit{ribbon graph}$ $\textbf{G}=(V(\textbf{G}),E(\textbf{G}))$ is a surface with boundary, represented as the union of two sets of discs: a set $V(\textbf{G})$ of vertices and a set $E(\textbf{G})$ of edges such that:
\begin{itemize}
  \item [(1)] the vertices and edges intersect in disjoint line segments;
  \item [(2)] each such line segment lies on the boundary of precisely one vertex and precisely one edge; and
  \item [(3)] every edge contains exactly two such line segments.
\end{itemize}
\end{defn}

It is well-known that ribbon graphs are equivalent to cellularly embedded graphs in surfaces, orientable or non-orientable.
Ribbon graphs arise naturally from small neighborhoods of cellularly embedded graphs.
On the other hand, topologically, a ribbon graph is a surface with boundary.
Capping-off the holes results in a band decomposition in the surface, which gives rise to a cellularly embedded graph in the obvious way.
A ribbon graph is $\textit{orientable}$ if it is orientable when viewed as a punctured surface.
Two ribbon graphs are $\textit{equivalent}$ if there is a homeomorphism taking one to the other that preserves the vertex-edge structure.
The homeomorphism should be orientation preserving when the ribbon graphs are orientable.
Here we will not go into ribbon graph deeply, we refer to interested reader to \cite{Mo} and references in it.

\begin{figure}[!htbp]
\centering
\includegraphics[width=3.5in]{orientableribbon.eps}
\caption{The cyclic graph $G$ and its associated orientable ribbon graph $\textbf{G}_r$.}
\label{F:orientableribbon}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=12cm]{fivegraphs.eps}
\caption{Five types of objects.}
\label{F:fivegraphs}
\end{figure}

The theory of cyclic graphs is equivalent to the theory of graphs on orientable surfaces.
For an example of a cyclic graph and its associated orientable ribbon graph, see Figure \ref{F:orientableribbon}.
Note that there is a virtual crossing where two edges are traversing.
Figure \ref{F:fivegraphs} gives an example for the five kinds of virtual spatial graph diagrams. We define \textit{the number of boundary components of a cyclic graph $G$} to be the number of boundary components of the ribbon graph $\textbf{G}_r$ associated with $G$.

From a virtual spatial graph diagram $D$, an orientable ribbon graph $\textbf{D}_r$ (possibly non-connected) can be constructed naturally, i.e., a classical crossing in $D$ is considered as a disk of a degree 4 vertex.
Thus the vertex discs of $\textbf{D}_r$ correspond to classical crossings and vertices.
The edge discs correspond to arcs, where the arcs of a diagram start and end at classical crossings and vertices.
$D$ can be embedded into the closed surface $\textbf{F}_D$ formed by capping off the holes of $\textbf{D}_r$.
The genus of $\textbf{F}_D$ is called the genus of diagram $D$,
i.e., $g(D)=g(\textbf{F}_D)$. The reader can check that a formula of the genus of closed orientable surface $\textbf{F}_D$ is
\begin{eqnarray}
  g(\textbf{F}_D)&=&k(\textbf{D}_r)+\frac{|E(\textbf{D}_r)|-|V(\textbf{D}_r)|-bc(\textbf{D}_r)}{2},
  \label{E:genus}
\end{eqnarray}
where $|V(\textbf{D}_r)|$, $|E(\textbf{D}_r)|$, $k(\textbf{D}_r)$ and $bc(\textbf{D}_r)$ are the number of vertices, edges, connected components and boundary components of $\textbf{D}_r$, respectively. In $\textbf{D}_r$, classical crossings of $D$ are here seen as distinct from graphical vertices of $D$, virtual crossings of $D$ do not count as graphical vertices. Then the number of vertices of  $\textbf{D}_r$ includes both the number of graphical vertices and the number of classical crossings.
Let $|V(D)|$ and $c(D)$ be the number of vertices and classical crossings of $D$, respectively. Let $d(v)$ be the degree of vertex $v$ of $D$.
Then by Eq. (\ref{E:genus}), we get the genus of surface $\textbf{F}_D$ as follows:
\begin{eqnarray}
  g(\textbf{F}_D)&=&k(\textbf{D}_r)+c(D)+\frac{\sum_{v\in V(D)} d(v)}{4}-\frac{|V(D)|+c(D)+bc(\textbf{D}_r)}{2}.
\end{eqnarray}

Note that the formula is designed to not use edge counts.
Let $G$ be a virtual spatial graph.
The \textbf{genus} of $G$ is defined as $g(G)=min\{g(\textbf{F}_D)|D$ is any diagram of $G \}$.

\begin{rem}\label{R:generalresults}
It is well known that another motivation for the introduction of virtual knots is that all Gauss codes can be implemented.
Another motivation for the introduction of virtual spatial graphs is that all Gauss codes of graphs can be implemented.
For the definition of the Gauss code for spatial graphs and related results, see \cite{FlemingMellor,KKKP}.
\end{rem}

\section{The generalized Yamada polynomial of a virtual spatial graph}\label{S:GYP}

\noindent

In \cite{Fleming07}, Fleming and Meller followed Yamada's method in \cite{Yam} to define the Yamada polynomial of a virtual spatial graph diagram $D$.
After the deletion and contraction of edges, $D$ becomes a bouquet graph (cyclic graph with one vertex).
They defined that the Yamada polynomial of a bouquet graph is equal to the Yamada polynomial of the underlying bouquet graph,
i.e., the cyclic order of the edges incident to the vertex of bouquet is ignored. Such a calculation method cannot distinguish the non-equivalence between the two virtual spatial graphs in Figure \ref{twotheta}.

\begin{figure}
\centering
\includegraphics[width=8cm]{twotheta.eps}
\caption{Two theta graphs with the same Yamada polynomial.}
\label{twotheta}
\end{figure}

In this section, we want to use an idea commonly used in ribbon graph theory, that is, to count the number of boundary components of a cyclic graph to define a polynomial of a virtual spatial graph diagram.
In addition, we shall add several new variables to define a multivariate polynomial.
We call this the \textbf{generalized Yamada polynomial}.
We mainly are interested in the generalized Yamada polynomial of a virtual rigid vertex graph,
although the generalized Yamada polynomial can become a polynomial of a special type of a virtual pliable vertex graph, where the maximum degree of a virtual pliable vertex graph is at most 3.

We first define a polynomial with 7 variables associated with the virtual spatial graph diagram by recursion.
This polynomial must be specialized so that it can be a rigid vertex isotopy invariant.

Let $e$ be an edge of the underlying abstract graph of a virtual spatial graph diagram $D$.
We use $D-e$, $D/e$, and $D(\overline{e})$ to denote deletion, contraction, and marking of the edge $e$ in a virtual spatial graph diagram $D$, respectively.
$D(\overline{e})$ indicates that the edge $e$ is preserved in $D$ and the edge $e$ is marked with a short slash.

It is convenient to introduce a short-hand for the evaluation of the generalized Yamada
polynomial: the virtual spatial graph diagram $D$ itself will stand for the evaluation of $R(D)$.

\begin{defn}\label{defn}
Let $D$ be a virtual spatial graph diagram.
Let $\alpha,\beta,\gamma,x,y,z,\mu$ be the variables, and assume that the product $\alpha\beta\gamma xyz\mu \neq 0$.
The generalized Yamada polynomial of $D$, $R(D)=R(D;\alpha,\beta,\gamma,x,y,z,\mu)$, can be recursively defined as follows:
\begin{enumerate}
\item [(1)] If $D$ contains degree 2 vertices, and $D'$ is the graph diagram obtained after absorbing all degree 2 vertices (i.e., reserve half edges incident with the degree 2 vertex and erase the degree 2 vertex), then $R(D')=R(D)$.
\item [(2)] \Across = $\alpha$ \Bsmooth+ $\beta$ \Asmooth+ $\gamma$ \onevertex.
\item [(3)] \Bcross = $\alpha$ \Asmooth+ $\beta$ \Bsmooth+ $\gamma$ \onevertex.
\item [(4)] \onee\ =\ $x$ \deleteedge+ $y$ \markingedge\ .
\item [(5)] If each edge of a cyclic graph $D$ is a marked edge, then $R(D)=z^{k(D)}\mu^{bc(D)-k(D)}$, where $k(D)$ and $bc(D)$ are the number of connected components and boundary components of $D$, respectively.
In particular, if $D$ is an $n$-th order empty graph ($n$ disjoint vertices), then $R(D)=z^n$ and $R(\emptyset)=1$.
\end{enumerate}
\end{defn}

When a virtual spatial graph is a 2-regular graph, it becomes a virtual knot or link.
To define the polynomial invariants of a virtual spatial graph diagram, in the edges of the graph, absorbing or adding degree 2 vertices does not change the value of the polynomial.
Each diagram in the equations means that only the drawn part is different and the other parts are the same. Note that the marker is on y-coefficient graph in Definition \ref{defn} (4). There can also be some virtual crossings on the edge $e$, but for simplicity and convenience, we do not draw them in Definition \ref{defn} (4).
For Definition \ref{defn} (5), for example, suppose $D$ is an all-marked connected cyclic graph with 5 boundaries components, then $R(D)=z\mu^4$.

There are two natural ways of combining two virtual spatial graph diagrams $D_1$ and $D_2$.
The first, the \textit{disjoint union} $D_1\cup D_2$, is exactly the same as for graphs.
The second, the \textit{one-point join} $D_1\vee D_2$, is formed by taking disjoint virtual spatial graph diagrams $D_1$ and $D_2$, choosing any vertices $v_1\in V(D_1)$ and $v_2\in V(D_2)$, and uniting the vertices $v_1$ and $v_2$, combining their cyclic orders so that all the edges of $v_1$ and $v_2$ are consecutive in the new order.
The following proposition is obvious.

\begin{proposition}\label{P:cupvee}
Let $D_1$ and $D_2$ be two virtual spatial graph diagrams. Then
\begin{enumerate}
\item [(1)] $R(D_1\cup D_2)=R(D_1) R(D_2),$
\item [(2)] $R(D_1\vee D_2)=z^{-1} R(D_1) R(D_2).$

\end{enumerate}
\end{proposition}
\begin{proof}
(1) is trivial. (2) follows from the fact that the one-point join of two cyclic graphs ensures that two boundary components will be merged into one component via Definition \ref{defn} (5).
\end{proof}

In a virtual spatial graph diagram, a non-loop edge that does not intersect other edges at classical or virtual crossings will be called a \textit{normal edge}.
Otherwise, it is called an \textit{abnormal edge}. It is easy to perform the edge contraction operation for the normal edge, but the contraction of an abnormal edge is a less intuitive task because of the need to take into account the vertex cyclic order. This is also the reason why we introduce the marking edge operation.

\begin{lem}\label{markcontract}
Let $D$ be a virtual spatial graph diagram and $e$ be a normal edge of $D$.
Then $R(D(\overline{e}))=R(D/e).$
\end{lem}
\begin{proof}
According to the Definition \ref{defn} (5) of the generalized Yamada polynomial of a virtual spatial graph diagram, the contribution of marking a normal edge \makrboundary ~to the boundary component is equivalent to the contraction of the edge.
\end{proof}

\begin{rem}
For the normal edge, marking operations and contraction operations are consistent.
Using $R(D/e)$ to represent $R(D(\overline{e}))$ will simplify the process of diagrammatic calculation of the generalized Yamada polynomial of a virtual spatial graph diagram $D$.
\end{rem}

Next, in order to ensure that this polynomial $R(D;\alpha,\beta,\gamma,x,y,z,\mu)$ is invariant under regular isotopy, the value of some variables and relationship between the variables are determined.

\begin{proposition}\label{P:calculate}
\begin{itemize}
\item[(1)] $\selfloop=(x+y\mu)z$
\item[(2)] $\loopvertex=(x+y\mu) \downarc$
\item[(3)] $\twovertex =  x^2 \Bsmooth + (2xy +y^2\mu) \onevertex$
\end{itemize}
\end{proposition}
\begin{proof}
\begin{itemize}
\item[(1)]
\begin{eqnarray*}
&\selfloop&=x~ \vertex  +  y~\loopmaker\\
& &=(x+y\mu)z
\end{eqnarray*}
\item[(2)] According to Proposition \ref{P:cupvee} (1) and above identity, we have
\begin{eqnarray*}
&\loopvertex&= z^{-1}\times \selfloop\times \downarc \\
& &=(x+y\mu)\downarc
\end{eqnarray*}
\item[(3)] \begin{eqnarray*}
&\twovertex &= x \oneedge  +  y\markedge \\
& &= x^2 \Bsmoothvertex +xy \onerightmark +xy \oneleftmark +y^2 \twomark\\
& &=  x^2 \Bsmooth + (2xy +y^2\mu) \onevertex
\end{eqnarray*}
\end{itemize}
\end{proof}

Proposition \ref{P:calculate} implies that the generalized Yamada polynomial of the standard diagram $\bigcirc$
 of the trivial knot is $(x+y\mu)z$.

\begin{lem}\label{RM2}
To ensure that $R(D)$ is invariant under Reidemeister moves (II) and (III),
then $\beta=\alpha^{-1},$ $\gamma=x^{-1}$, $y=1$, $z=-x^{-1}$ and $\mu=-(\alpha+\alpha^{-1}+2)x.$
\end{lem}
\begin{proof}
On the one hand,
\begin{eqnarray*}\label{r2invariant}
\ReidMove
&=& \alpha\beta \Asmooth  + [\alpha^2+\beta^2+\alpha\beta(xz+y\mu z)]\Bsmooth
     +(\alpha+\beta)\gamma \onevertex\\
& &+ \alpha\gamma\downvertexloop + \beta\gamma\upvertexloop+ \gamma^2 \twovertex \\
&=&\alpha\beta \Asmooth  + [\alpha^2+\beta^2+\alpha\beta(xz+y\mu z)+
   \gamma(\alpha+\beta)(x+y\mu)+\gamma^2x^2]\Bsmooth\\
& &+[(\alpha+\beta)\gamma+\gamma^2(2xy+y^2\mu)]\onevertex  \\
\end{eqnarray*}
In order to have $R(\ReidMove)=R(\Asmooth)$, we take the following relations:
\begin{equation}
\left\{ \begin{array}{ll}
  \alpha\beta = 1 \\
  \alpha^2+\beta^2+\alpha\beta(xz+y\mu z)+\gamma(\alpha+\beta)(x+y\mu)+\gamma^2x^2=0 \\
  (\alpha+\beta)\gamma+\gamma^2(2xy+y^2\mu) =0
\end{array}
\right.  \label{eq:rm2}
\end{equation}
Thus $\beta=\alpha^{-1}.$

On the other hand,
\begin{eqnarray*}
\threevertex
&=& \alpha^2 \aav  + \alpha^{-2} \bbv + \abv + \bav + \alpha\gamma\av+\alpha^{-1}\gamma \bv
   +\alpha^{-1}\gamma \vb \\
& & +\alpha\gamma\va+\gamma^2\vv  \\
&=& \alpha^2 \aav  + \alpha^{-2} \bbv + \abv + (x+y\mu)\onearc + \alpha\gamma(x \twothree+y\five)\\
& &+ \alpha^{-1}\gamma [x^2\onearc +(2xy+y^2\mu)\bbv] +\alpha^{-1}\gamma (x \threetwo+y\five)\\
& &+\alpha\gamma[x^2\onearc +(2xy+y^2\mu)\aav]+\gamma^2[x^3\onearc +(y^3\mu+3xy^2) \five\\
& &+ x^2y(\bbv+\aav+\crossarc)]  \\
&=&[\alpha^2+\alpha\gamma(2xy+y^2\mu) +\gamma^2x^2y] \aav
  + [\alpha^{-2}+\alpha^{-1}\gamma(2xy+y^2\mu) +\gamma^2x^2y] \bbv \\
& &+ \abv + \alpha\gamma x \twothree+\alpha^{-1}\gamma x \threetwo+[ \alpha\gamma y +\alpha^{-1}\gamma y+\gamma^2(y^3\mu+3xy^2)] \five \\
& &+\gamma^2x^2y\crossarc+ [(x+y\mu)+\alpha^{-1}\gamma x^2+\alpha\gamma x^2+\gamma^2x^3] \onearc
\end{eqnarray*}
\begin{eqnarray*}
\upthree
&=& \alpha \twothree  + \alpha^{-1} \threetwo +\gamma x\abv + \gamma y \five\\
\end{eqnarray*}
In order to have $R(\threevertex)=R(\upthree)$, we take
\begin{equation}
\left\{ \begin{array}{ll}
  \gamma x=1\\
  x+y\mu+\alpha^{-1}\gamma x^2+\alpha\gamma x^2+\gamma^2x^3 =0 \\
  \alpha^2+\alpha\gamma(2xy+y^2\mu) +\gamma^2x^2y=0 \\
   \alpha^{-2}+\alpha^{-1}\gamma(2xy+y^2\mu) +\gamma^2x^2y=0\\
    \alpha\gamma y +\alpha^{-1}\gamma y +\gamma^2(y^3\mu+3xy^2)=\gamma y
\end{array}
\right.  \label{eq:rm3}
\end{equation}
Solving the system of Eq. (\ref{eq:rm3}), we firstly obtain that $\gamma=x^{-1}$.
Based on  $\gamma=x^{-1}$, we can simplify Eq. (\ref{r2invariant}) and Eq. (\ref{eq:rm3}) to be the following equations:

\begin{equation}
\left\{ \begin{array}{ll}
  \alpha^2+\alpha^{-2}+(xz+y\mu z)+x^{-1}(\alpha+\alpha^{-1})(x+y\mu)+1=0 \\
  (\alpha+\alpha^{-1})+2y+x^{-1}y^2\mu =0\\
  (\alpha+\alpha^{-1})x+2x+y\mu=0 \\
  \alpha^2+2\alpha y+\alpha x^{-1}y^2\mu +y=0 \\
   \alpha^{-2}+2\alpha^{-1} y+\alpha^{-1} x^{-1}y^2\mu +y=0 \\
    (\alpha+\alpha^{-1})y +x^{-1}(y^3\mu+3xy^2)=y
\end{array}
\right.  \label{eq:simplify1}
\end{equation}
Solving the second and third identities of the system of Eq. (\ref{eq:simplify1}), we get that $\mu=-\frac{(\alpha+\alpha^{-1})+2y}{x^{-1}y^2}=-\frac{(\alpha+\alpha^{-1})x+2x}{y}.$
Meanwhile it can be solved that
\begin{equation}
\left\{ \begin{array}{ll}
  y=1\\
 \mu =(-\alpha-\alpha^{-1}-2)x
\end{array}
\right.  \label{eq:rm4}
\end{equation}
Hence we can figure out that $z=-x^{-1}$ according to the first identity of Eq. (\ref{eq:simplify1}), and all other identities of Eq. (\ref{eq:simplify1}) are correct when $y=1$ and $\mu =(-\alpha-\alpha^{-1}-2)x.$ This ensures that $R(D)$ is invariant under move (II).

\noindent If the vertex degree is at least 3, then by the definition and induction hypothesis of the generalized Yamada polynomial, we have
\begin{align*}
  R(\ndv) & =R(\ndvae)-xR(\ndvde) \\
   & = R(\ndvaes)-xR(\ndvdes) \\
   &=R(\ndvs)\\
\end{align*}
This ensures that $R(D)$ is invariant under move (IV).
From the definition of $R(D)$ and its invariance under the moves (II) and (IV), we can obtain that
\begin{eqnarray*}
\Gte&=&\alpha\graphone +\alpha^{-1}\graphtwo+ \gamma\graphthree \\
&=&\alpha\graphfour +\alpha^{-1}\graphfive+ \gamma\graphsix \\
&=&\Gts
\end{eqnarray*}
Hence, $R(D)$ is invariant under move (III).
\end{proof}

\begin{thm}\label{regiso}
When variables satisfy that
$$(\alpha,\beta,\gamma,x,y,z,\mu)=(\alpha,\alpha^{-1},x^{-1},x,1,-x^{-1},
-(\alpha+\alpha^{-1}+2)x),$$
then $R(D)$ is a regular isotopy invariant. That is, the generalized Yamada polynomial $R(D;\alpha,x)$ of a virtual spatial graph diagram is a two-variable polynomial and a regular isotopy ((II)(III) and Figure \ref{F:virtualmoves}) invariant.
\end{thm}
\begin{proof}
It is obvious that $R(D)$ is invariant under moves except (IV*) in Figure \ref{F:virtualmoves}.
Furthermore, $R(D)$ is invariant under moves (IV*) which is similar to the case of move (III).
Thus $R(D)$ is a regular isotopy invariant.
\end{proof}

We reformulate the Definition \ref{defn} as follows:
\begin{defn}\label{definition1}
Let $D$ be a virtual spatial graph diagram. Then the generalized Yamada polynomial $R(D;\alpha,x)$ satisfies the following relations:
\begin{enumerate}
\item [(1)] If $D$ contains degree 2 vertices, and $D'$ is the graph diagram obtained after absorbing all degree 2 vertices, then $R(D')=R(D).$
\item [(2)] \Across = $\alpha$ \Bsmooth+ $\alpha^{-1}$ \Asmooth+ $x^{-1}$ \onevertex.
\item [(3)] \Bcross = $\alpha$ \Asmooth+$\alpha^{-1}$ \Bsmooth+ $x^{-1}$ \onevertex.
\item [(4)] \onee\ =\ $x$ \deleteedge+ \markingedge\ .
\item [(5)] If each edge of a cyclic graph $D$ is a marked edge, then $R(D)=(-x)^{bc(D)-2k(D)}(\alpha+\alpha^{-1}+2)^{bc(D)-k(D)}$, where $k(D)$ and $bc(D)$ are the number of connected components and boundary components of $D$, respectively. In particular, if $D$ is an $n$-th order empty graph ($n$ disjoint vertices), then $R(D)=(-x)^{-n}$ and $R(\emptyset)=1$.
\end{enumerate}
\end{defn}

In the following, for a virtual spatial graph diagram $D$, the generalized Yamada polynomial of $D$ will always mean $R(D;\alpha,x)$. Let $e$ be an edge of a virtual spatial graph  $G$. We say that $e$ is an \textit{isthmus} of $G$ or its diagram $D$ if $G-e$ as abstract graph has more connected components than $G$ as abstract graph.

\begin{proposition}\label{pro1}
If a virtual spatial graph diagram $D$ contains a normal isthmus, then $R(D)=0.$
\end{proposition}
\begin{proof}
Let $e$ be a normal isthmus of $D$. Then there exists $D_1$, $D_2$ such that $D-e=D_1 \cup D_2$ and $D/e=D_1 \vee D_2$.
By the definition of generalized Yamada polynomial, when $xz=-1$, $R(D)=x R(D-e)+R(D/e)=(xz+1)R(D_1 \vee D_2)=0$.
\end{proof}

Just as \cite{Yam}, the behaviors of $R(D;\alpha,x)$ under moves (I), (V) and (VI) are illustrated in Figure \ref{F:yamada}.
The generalized Yamada polynomial $R(D;\alpha,x)$ is changed under moves (I), (V) and (VI).

\begin{figure}
\centering
\includegraphics{yamada.eps}
\caption{The behaviors of $R(D)$ under moves (I), (V) and (VI). In move (V), the degree of vertex is $n$.}
\label{F:yamada}
\end{figure}

Let $G$ be a virtual spatial graph and $D$ be a diagram of $G$.
Based on the formulas of Figure \ref{F:yamada},
the generalized Yamada polynomial can be normalized as $\overline{R}(G;\alpha,x)=(-\alpha)^{-m}R(D;\alpha,x)$, where $m$ is the minimum degree of $\alpha$ in $R(D)$.
Then we can obtain the following result.
\begin{thm}
Let $G$ be a virtual spatial graph. Then $\overline{R}(G;\alpha,x)$ is a rigid vertex isotopy invariant.
When the maximum degree of $G$ is at most 3, $\overline{R}(G;\alpha,x)$ is a pliable vertex isotopy invariant.
\end{thm}
\begin{proof}
The moves (I) and (V) do not change the value of $\overline{R}(G;\alpha,x)$.
But under the move (VI) it will change the value of $\overline{R}(G;\alpha,x)$, so it is not a pliable vertex isotopy invariant in a general case.
However, there are exceptions.
When the maximum degree of the graph is less than or equal to 3, the result of the move (VI) at a degree 3 vertex is equivalent to the result of the moves (V) and (IV).
Thus, when the maximum degree of the graph is at most 3, $\overline{R}(G;\alpha,x)$ is a pliable vertex isotopy invariant.
\end{proof}

Let $L$ be an oriented virtual link and $D$ be a diagram of $L$.
The writhe of $D$, which is denoted by $w(D)$, is defined to the sum of the signs of classical crossings of $D$.
If $D$ has no classical crossings, then $w(D)=0$.
We defined a polynomial for $L$ as follows.

\begin{eqnarray}
\widetilde{R}(L;\alpha,x)&=&\alpha^{-2w(D)}R(D;\alpha,x).
\end{eqnarray}

Then, we have the following result.
\begin{thm}
Let $L$ be an oriented virtual link.
Then $\widetilde{R}(L;\alpha,x)$ is an ambient isotopy invariant.
\end{thm}

According to the Definition \ref{definition1}, the following result is obvious.
\begin{proposition}
Let $D^*$ be the mirror image of a virtual spatial graph diagram $D$. Then $R(D^*;\alpha,x)=R(D;\alpha^{-1},x)$.
\end{proposition}
This proposition implies the following two theorems.
\begin{thm}
Let $G$ be a virtual rigid vertex graph.
If $G$ is amphicheiral (i.e., rigid vertex isotopic to the mirror image of itself), then $\overline{R}(G;\alpha,x)=(-\alpha)^{d}\overline{R}(G;\alpha^{-1},x)$,
where $d$ is the degree of $\alpha$ in $\overline{R}(G;\alpha,x)$.
\end{thm}

\begin{thm}
Let $G$ be a virtual pliable vertex graph whose maximum degree is at most 3.
If $G$ is amphicheiral (i.e., pliable vertex isotopic to the mirror image of itself), then $\overline{R}(G;\alpha,x)=(-\alpha)^{d}\overline{R}(G;\alpha^{-1},x)$,
where $d$ is the degree of $\alpha$ in $\overline{R}(G;\alpha,x)$.
\end{thm}
Next we give the state-space expansion of the generalized Yamada polynomial of a virtual spatial graph diagram.
\begin{figure}
\centering
\includegraphics[width=2.5in]{spin.eps}
\caption{The spin set.}
\label{F:spin}
\end{figure}
Let $D$ be a virtual spatial graph diagram and the number of classical crossings of $D$ is $c$.
For a classical crossing of $D$, we define $s_+$, $s_-$ and $s_0$, called the \textit{spin} of $D$, as shown in Figure \ref{F:spin}.
Let $S$ be the cyclic graph obtained from $D$ by replacing each classical crossing with a spin of $\{s_+, s_-, s_0\}$.
$S$ is called a state of $D$, and $\mathscr{S}(D)$ denotes the set of all states of $D$.
If the number of spins $s_+$ and $s_-$ in the state $S$ is $a$ and $b$, respectively, then the number of spins $s_0$ is $c-a-b$.
For a cyclic graph $S=(V(S),E(S))$, we use $|V(S)|$ and $|E(S)|$ to denote the number of vertices and edges in the graph $S$, respectively.
When the context is clear, $|V(S)|$ and $|E(S)|$ are abbreviated as $|V|$ and $|E|$, respectively.
For each $F\subseteq E(S)$, let $\langle F\rangle$ be the spanning subgraph whose vertex set is $V(S)$ and the edge set is $F$.
Let $|F|$ be the number of edges in $F$.
Let $k(F)$ be the number of connected components of $\langle F\rangle$ (that is, the zero-th Betti number of the graph).
Let $bc(F)$ be the number of boundary components of $\langle F\rangle$.
Let $E(S)\backslash F$ be the complement of $F$ in $E(S)$, i.e., $E(S)\backslash F=E(S)-F$.

By Definition \ref{definition1} (4) and (5), we have the \textit{spanning subgraph expansion} of the generalized Yamada polynomial of a cyclic graph $S$ as follows:
$$R(S;\alpha,x)=\sum_{F\subseteq E(S)}
x^{|E(S)\backslash F|}z^{k(F)}\mu^{bc(F)-k(F)}.$$
That is,

\begin{equation}\label{E:spanningsubgraph}
\begin{split}
R(S;\alpha,x)
&=\sum_{F\subseteq E(S)}(-1)^{bc(F)}x^{|E|-|F|+bc(F)-2k(F)}(\alpha+\alpha^{-1}+2)^{bc(F)-k(F)}\\
&=\sum_{F\subseteq E(S)}(-1)^{bc(F)}x^{|E|-|V|+|V|-|F|+bc(F)-2k(F)}(\alpha+\alpha^{-1}+2)^{bc(F)-k(F)}\\
&=\sum_{F\subseteq E(S)}(-1)^{bc(F)}x^{|E|-|V|-2g(F)}(\alpha+\alpha^{-1}+2)^{bc(F)-k(F)}\\
&=x^{|E|-|V|}\sum_{F\subseteq E(S)}(-1)^{bc(F)}x^{-2g(F)}(\alpha+\alpha^{-1}+2)^{bc(F)-k(F)},
\end{split}
\end{equation}
where $|V|-|F|+bc(F)=2k(F)-2g(F)$ is the formula for the genus in an orientable ribbon graph (cyclic graph).

Then we can get the \textit{state-space expansion} of the generalized Yamada polynomial of a virtual spatial graph diagram $D$ as follows:
\begin{eqnarray}\label{E:Dspanningsubgraph}
R(D;\alpha,x)=\sum_{S\in \mathscr{S}(D)}\alpha^{a-b}x^{a+b-c}R(S;\alpha,x).
\end{eqnarray}

When $D$ is a virtual link diagram, we note that each cyclic graph $S$ is a 4-regular graph with $|V|=c-a-b$, $|E|=2(c-a-b)$.
By Eq. (\ref{E:spanningsubgraph}), we can simplify Eq. (\ref{E:Dspanningsubgraph}) as follows:
\begin{eqnarray}\label{E:Dspanningsubgraph1}
R(D;\alpha,x)=\sum_{S\in \mathscr{S}(D)}\alpha^{a-b}\sum_{F\subseteq E(S)}(-1)^{bc(F)}x^{-2g(F)}(\alpha+\alpha^{-1}+2)^{bc(F)-k(F)}.
\end{eqnarray}
Obviously we have the following result.
\begin{corollary}\label{C:powerofx}
Let $D$ be a virtual link diagram. Then the powers of $x$ in $R(D;\alpha,x)$ are even.
\end{corollary}

In \cite{Yam}, the Yamada polynomial $R(D)(A)$ of a spatial graph diagram $D$ has the following state-space expansion:
\begin{eqnarray}\label{E:cyp}
R(D)(A)=\sum_{S\in \mathscr{S}(D)}A^{a-b}\sum_{F\subseteq E(S)}(-1)^{k(F)+n(F)}(A+A^{-1}+2)^{n(F)}.
\end{eqnarray}

Note that each state of a spatial graph diagram is a plane graph.
If $S$ is a plane graph, then $g(F)=0$ and $k(F)+n(F)=bc(F)$ for any spanning subgraph $\langle F\rangle$ of $S$.
Hence we have the following corollary by Eq. (\ref{E:Dspanningsubgraph}) and  Eq. (\ref{E:cyp}).

\begin{corollary}\label{C:classicalYP}
Let $D$ be a spatial graph diagram. Then $R(D;A,1)$ coincides with the Yamada polynomial for $D$.
\end{corollary}

For the two theta spatial graph diagrams in the Figure \ref{twotheta}, their generalized Yamada polynomials $R(G;A,1)$ are: $-A^2-A-2-A^{-1}-A^{-2}$ and $2(A+A^{-1}+1)$.
Thus their normalized generalized Yamada polynomials $\overline{R}(G;A,1)$ are: $-A^4-A^3-2A^2-A-1$ and $2(A^2+1+A)$.
Hence they are neither rigid vertex isotopic nor pliable vertex isotopic virtual spatial graphs.

\begin{rem}
If $D$ is a virtual spatial graph diagram, the generalized Yamada polynomial $R(D;A,1)$ usually does not coincide with the Yamada polynomial for $D$.
\end{rem}

\section{The relationship between generalized Yamada polynomial and a link polynomial}\label{S:Dubrovnik}
\noindent

Kauffman \cite{Kau2-variable} had defined a regular isotopy invariant for a classic link diagram $l$ (2-regular spatial graph).
$D(l;a,z)$ is a special case of the Kauffman polynomial.
$D(l;a,z)$ is called Dubrovnik polynomial.
$D(l;a,z)$ can be obtained from the following skein relation.
\begin{enumerate}
\item [(1)] $D(\Across)-D(\Bcross)= z [D(\Bsmooth)-D(\Asmooth)]$
\item [(2)] $D(\positivecurl)=aD(\downarc)$
\item [(3)] $D(\negativecurl)=a^{-1}D(\downarc)$
\item [(4)] $D(\bigcirc K)=[1+\frac{(a-a^{-1})}{z}]D(K)$,~~~$D(\bigcirc)=1+\frac{(a-a^{-1})}{z}.$
\end{enumerate}
The above definition is different from the original definition, with $D(\bigcirc)=1$ in the original definition.
According to the Definition \ref{definition1} of the generalized Yamada polynomial $R(l;\alpha,x)$ of the virtual spatial graph diagram, the following skein relations can be obtained.
\begin{enumerate}
\item [(1)] $R(\Across)-R(\Bcross)= (\alpha-\alpha^{-1}) [R(\Bsmooth)-R(\Asmooth)]$
\item [(2)] $R(\positivecurl)=\alpha^2 R(\downarc)$
\item [(3)] $R(\negativecurl)=\alpha^{-2}R(\downarc)$
\item [(4)] $R(\bigcirc K)=(1+\alpha+\alpha^{-1})R(K)$,~~~$R(\bigcirc)=1+\alpha+\alpha^{-1}$
\end{enumerate}
Thus $R(l;\alpha,x)$ satisfies the recursive definition of the Dubrovnik polynomial.

\begin{lem}\label{l:detectclassical}
Let $l$ be a classical link diagram, then $R(l;\alpha,x)=D(l;\alpha^2,\alpha-\alpha^{-1}),$ where $a=\alpha^2$ and $z=\alpha-\alpha^{-1}$ in the Dubrovnik polynomial.
That is, for a classical link diagram $l$, there is no $x$ term in $R(l;\alpha,x)$.
\end{lem}

\begin{proof}
Note that for classical links, variable $x$ does not appear because we can just calculate $R(l;\alpha,x)$ from skein relations above.
\end{proof}

\begin{rem}\label{R:detectclassical}
The above Lemma \ref{l:detectclassical} can often be used to determine if a virtual link is non-classical.
\end{rem}

It is well known that the Dubrovnik polynomial cannot be generalized directly to virtual links because its skein relations are not sufficient to calculate the polynomials of virtual link diagrams.
Note that some virtual diagrams can not be unknotted or unlinked by switching classical crossings.
Nevertheless, the generalized Yamada polynomial $R(l;\alpha,x)$ specializes to a version of the Dubrovnik polynomial for virtual link diagrams.
That is, we can first resolve classical crossings via skein relations until we can not continue to use the skein relations.
Then we turn to formulas (2)(3) in Definition \ref{definition1} to resolve the remaining classical crossings.
In this way the graphical expansion of the generalized Yamada polynomial provides a method to decide evaluations that are ambiguous to just the Dubrovnik skein relation.
These structures may act as a guide to finding a full formulation of the Dubrovnik polynomial for virtual knots and links.

By calculating, we have
$R(0_1;\alpha,x)=R(\bigcirc)=\alpha+\alpha^{-1}+1.$
Let \virtualtrefoil ~be a diagram of virtual trefoil knot (the mirror of virtual knot $2_1$ in \cite{Gr}), then
$R(\virtualtrefoil;\alpha,x)=\alpha^3+3\alpha^2+5\alpha-4\alpha^{-1}-3\alpha^{-2}+\alpha^{-4}-x^{-2}(\alpha-\alpha^{-1})$, which contains $x$.
Thus virtual trefoil knot is non-trivial and non-classical.
Let \virtualizedtrefoil ~be a diagram of virtualized trefoil knot (virtual knot $3_7$ in \cite{Gr}), then
\begin{eqnarray*}
R(\virtualizedtrefoil;\alpha,x)&=&-\alpha^{-4}-2\alpha^{-3}+3\alpha^{-2}+2\alpha^{-1}+\alpha-2\alpha^{2}+2\alpha^{3}+\alpha^{4}-\alpha^{5}\\
& &+x^{-2}(\alpha^{-2}-3\alpha^{-1}+3\alpha-\alpha^{2}),
\end{eqnarray*}
which contains $x$.
Thus virtualized trefoil knot is non-trivial and non-classical.
We are sure that the generalized Yamada polynomial detects non-classicality for many link diagrams with a single virtualization that have unit Jones polynomial (it was generally proved by Dye \emph{et al.} in \cite{DKK}), but it is a project to compute more of them. We would like to find a general theorem about this situation.
Note that $D(\virtualhopflink)$ cannot be calculated with the above definition of Dubrovnik polynomial.
However, we can obtain the polynomial of a virtual Hopf link by the recursive definition of the generalized Yamada polynomial $R(l;\alpha,x)$.
Let \virtualhopflink ~be a diagram of virtual Hopf link, then $R(\virtualhopflink;\alpha,x)=
(\alpha+\alpha^{-1}+1)^2+(\alpha+\alpha^{-1}+2)-x^{-2}$, which contains $x$.
Thus the virtual Hopf link is non-trivial and non-classical.

\section{Applications and calculations}\label{S:Application}
\noindent

In this Section, we consider a special case of $R(D;\alpha,x)$ which corresponds to an evaluation of the 2-cabled bracket polynomial with Jones-Wenzl projector $P_2$.

Kauffman defined the bracket polynomial of the classical link diagrams using the skein relations, giving a new model of the Jones polynomial.
In \cite{VKT}, Kauffman extended the bracket polynomial of classical links to a bracket polynomial for virtual links.
Thus, the classical Jones polynomial is extended to the Jones polynomial of virtual links.

For a virtual link diagram $D$, the $\textit{bracket polynomial}$ $\langle D\rangle=\langle D\rangle(A,B,d)$ \cite{VKT} can be defined recursively by using the following three relations:
\begin{equation*}
\centering
\includegraphics[width=2.0in]{skein.eps}
\end{equation*}
Here it is understood that the three small diagrams are parts of otherwise identical larger diagrams and $\bigcirc$ denotes a connected diagram with no classical crossings.
There is also a state expansion for the bracket polynomial as follows.

\begin{thm}(\cite{VKT})
The bracket polynomial of a virtual link diagram $D$ is a polynomial in three variables $A,B,d$ defined by the formula
$$\langle D\rangle(A,B,d)=\sum_{\sigma\in \mathscr{S}(D)}A^{\alpha(\sigma)}B^{\beta(\sigma)}d^{|\sigma|-1},$$
\noindent where $\alpha(\sigma)$ and $\beta(\sigma)$ are the numbers of $A$-smoothings ($s_{+}$) and $B$-smoothings ($s_{-}$) (see the spin $s_{+}$ and $s_{-}$ in Figure \ref{F:spin}, respectively) in a state $\sigma$, respectively, $\mathscr{S}(D)$ denotes the set of states of $D$, and $|\sigma|$ is the number of closed curves in $\sigma$.
\end{thm}
In particular, it is well known that if $B=A^{-1}$, $d=-(A^2+A^{-2})$ then $\langle D\rangle$ is invariant under moves (II), (III) and moves (I*)-(IV*).
\vskip0.5cm

The $n$-strand Temperley-Lieb algebra $TL_n$ is an algebra in $\mathbb{C}[d]$;
the elements of the algebra are generated by 1-dimensional sub-manifolds of a rectangle.
Each sub-manifold intersects the top and bottom of the rectangle in $n$ vertices.
If the two sub-manifolds are isotopic keeping the boundary fixed, then we call them equivalent.
Deleting a simple closed curve is equivalent to generating a multiple of $d$.
The product between two sub-manifold\textcolor[rgb]{0.00,0.07,1.00}{s} is represented by a vertical stack of rectangles.
Let $\{1_n,e_1,e_2,...,e_{n-1}\}$ be the generator set of algebra $TL_n$ as illustrated in Figure \ref{F:TLAgenerators}.
Each element in $TL_n$ can be represented as a linear combination of the product of these generators.
For any $i,j=1,2,...,n-1$, the generators satisfy the following relations:
\begin{equation}\label{E:TLArelation}
\begin{split}
&1_ne_i=e_i=e_i1_n \\
&e_i^2=d~ e_i\\
&e_ie_j=e_je_i \ \ {if~} |i-j|\geq 2\\
&e_ie_{i\pm1}e_i=e_{i}\\
\end{split}
\end{equation}

\begin{figure}[!htbp]
\centering
\includegraphics[width=8cm]{TLAgenerators.eps}
\caption{The generator set of $TL_n$.}
\label{F:TLAgenerators}
\end{figure}

In $TL_2$, we have the Jones-Wenzl projector $P_2=1_2-\frac{1}{d}e_1$, and $P_2^{2}=P_2$, $P_2e_1=0$
as shown in Figure \ref{F:projector2}. Next we apply $P_2$ to the virtual spatial graph diagram to get a special parameter for the generalized Yamada polynomial.

\begin{figure}
\centering
\includegraphics[width=11cm]{projector2.eps}
\caption{The diagrammatic definition and properties of $P_2$.}
\label{F:projector2}
\end{figure}

With Jones-Wenzl projector $P_2$, we shall construct a new diagram from a virtual spatial graph diagram as follows.
First, for a virtual spatial graph diagram $D$, we shall resolve each vertex and crossing with $P_2$ and replace each arc of the graph as shown in Figure \ref{F:edgetranslate}.
After converting all vertices and crossing of $D$, we denote $D^{p}$ \textit{the virtual link diagram associated with $D$ with projector $P_2$}, see Figure \ref{F:G50} for an example.
Note that there are two $P_2$s on each arc of $D$ in $D^p$ and recall that the arcs of $D$ start and end at classical crossings and vertices.
In particular, when $D$ is $K_1$, i.e. $1-$th order empty graph, $D^{p}$ is a unknot (free loop).

\begin{figure}[ht]
\centering
\includegraphics[height=1.8cm]{edgetranslate.eps}
\caption{Resolve each arc, each vertex and each classical crossing of a virtual spatial graph diagram.}
\label{F:edgetranslate}
\end{figure}

\begin{figure}[!htbp]
\centering
\includegraphics[width=8cm]{G50.eps}
\caption{With $P_2$, the virtual spatial graph $D$ is converted to $D^p$.}
\label{F:G50}
\end{figure}

We call $\langle D^p\rangle(A,A^{-1},d)$ the \textit{2-cabled bracket polynomial of $D$ with projector $P_2$}, where $d=-A^{2}-A^{-2}$.

In \cite{KauLins}, Kauffman and Lins discussed about applying $P_2$ to classical link diagrams and obtained a formula which is extended to virtual spatial graph diagrams here.

\begin{proposition}\label{P:PhiYamada}
\begin{eqnarray}\label{F:2strandformula}
\langle\cablecrossing\rangle &=& A^4 \langle\cableA\rangle +A^{-4}\langle\cableB\rangle+(A^{2}+A^{-2})\langle\cablev\rangle,
\end{eqnarray}
where the four small diagrams are parts of otherwise identical larger virtual link diagrams with projectors, and every term is the bracket polynomial of the diagram which is understood to fully expand each $P_{2}$ and represents a linear combination of some virtual link diagrams.
\end{proposition}
\begin{proof}
When there are virtual crossings in the diagram, Eq. (\ref{F:2strandformula}) is still true since Detour moves do not affect the action of projector $P_2$. So the proof is similar to  the original one in \cite{KauLins}.
\end{proof}

According to the definition of $P_2$ and the above Proposition \ref{P:PhiYamada}, the following theorem can be obtained.

\begin{thm}\label{T:PhiYamada1}
Let $D$ be a virtual spatial graph diagram and $D^p$ be the virtual link diagram associated with $D$ with projector $P_2$.
Then $$R(D;A^4,-d^{-1})=d\langle D^p\rangle(A,A^{-1},d),$$
where $d=-A^{2}-A^{-2}.$
\end{thm}

\begin{proof}
Note that during the process of the calculation of $d\langle D^p\rangle(A,A^{-1},d)$,  we shall first use the formula in Proposition \ref{P:PhiYamada} to deal with the classical crossings of $D$, then expand all projectors and record the number of closed curves.

It is sufficient to prove that the Definition \ref{definition1} of $R(D;A^4,-d^{-1})$ satisfies the calculation process of $d\langle D^p\rangle(A,A^{-1},d)$ .

(1) The degree 2 vertex has no effect on $R(D;A^4,-d^{-1})$ and the degree 2 vertex can also be removed in calculating $d\langle D^p\rangle(A,A^{-1},d)$ by using $P_2^2=P_2$.

(2) Reducing a classical crossing in $R(D;A^4,-d^{-1})$ is equivalent to reducing the corresponding four classical crossings in $D^p$ as the formula given in Proposition \ref{P:PhiYamada}.

(3) Reducing an edge in $R(D;A^4,-d^{-1})$ is equivalent to expanding the corresponding $P_2$ in $D^p$, that is, the deletion of an edge corresponds to choose $e_1$ of $P_2$ and the marking of an edge corresponds to choose $1_2$ of $P_2$.

(4) The relation $z=\mu=d$ also satisfies the value of a trivial knot and each circle in the calculation of $d\langle D^p\rangle$.
\end{proof}

\begin{rem}\label{R:Gp0}
According to Lemma \ref{l:detectclassical}, for a classical link diagram $l$, $R(l;A^4,-d^{-1})=D(l;A^8,A^4-A^{-4})=D(l;\alpha^2,\alpha-\alpha^{-1})_{|\alpha=A^4}$, which means that the power of each $A$ is a multiple of four.
Furthermore, for any virtual link diagram, we can obtain that the power of each $A$ of $R(l;A^4,-d^{-1})$ is a multiple of four by Corollary \ref{C:powerofx}.
\end{rem}

According to the relation $R(D;A^4,-d^{-1})=d\langle D^p\rangle(A,A^{-1},d)$, we write a program for calculating generalized Yamada polynomials based on \textit{Mathematica} code.

\noindent\textbf{Program 1:}\\
1. \text{rule1} $=\{Y[a\_, b\_, c\_, d\_, e\_, f\_, g\_, h\_,bc\_,de\_,fg\_,ha\_]$
$:>A^{-4}*X[a, b, c, d]*X[g, h, e, f] +A^{4}*X[a, b, g, h]*X[c, d, e, f] -dd*X[a, b, bc, ha]*X[c, d, bc, de]*X[e, f, fg, de]*X[g, h, ha, fg]\};$\\

2.  \text{rule2} $=\{X[a\_, b\_, c\_, d\_] :> del[a~ d]*del[b~ c]-1/dd*del[a~ b]*del[c~ d]\};$\\
3.  \text{rule3} $=\{del[a\_ b\_] del[b\_ c\_] :> del[a~c]\};$\\
4.  \text{rule4} $=\{(del[\_])^2 :> dd, del[\_^2] :> dd\};$\\
5.  \text{rule5} $=\{dd :> -A^2 - A^{-2}\};$\\
6.  \text{YamadaPoly}$[t\_]:=\\
\text{Simplify}[\text{Expand}[(t /. \text{rule1} /. \text{rule2} // \text{Expand}) //. \text{rule3} /.\text{rule4} /. \text{rule5}]$\\

\noindent where $X[a\_, b\_, c\_, d\_]$ denotes the 4 endpoints of a projector $P_2$ counterclockwise as shown in Figure \ref{F:codeingforD}(4)(usually $X[a\_, b\_, c\_, d\_]$ can be used to denote a classical crossing of a link diagram),
$Y[a\_, b\_, c\_, d\_, e\_, f\_, g\_, h\_,bc\_,de\_,fg\_,ha\_]$ denotes a classical crossing of a virtual spatial graph diagram as shown in Figure \ref{F:codeingforD}(4).
That is, there contains three steps for coding process in calculating generalized Yamada polynomial $R(D;A^4,-d^{-1})$ as shown in Figure \ref{F:codeingforD}(1)(2)(3).
(1) Put two projectors on each arc between two classical crossings and one projector on each arc between a classical crossing and a vertex in the diagram. (2) Use the letters $a,b,c,d$, etc. to mark the two sides of the arc between one classical crossing and another classical crossing and mark mark the region between every two half edges of each vertex in the diagram. (3) For each classical crossing in the diagram, by listing the information of the four semi-arcs forming the classical crossings,
we record the projector labels counter-clockwise which start from over-crossing half arc and firstly meets the A-region as follows:
$Y[d,c,b,a,e,$
$g,h,j,cb,ae,gh,jd]$,
where the newly last 4 labels will be used to
calculate the state graphs obtained after choosing spin $s_0$ for the classical crossing as shown in last term of identity of Proposition 5.2.
For the projector on the arc between two vertices in the graph,
we consecutively record the labels near a vertex counter-clockwise, and list the 4 endpoints of the projector as follows: $X[g,f,k,h]$.
\begin{figure}[!htbp]
\centering
\includegraphics[width=12cm]{codeingforD.eps}
\caption{The coding process in calculating generalized Yamada polynomial $R(D;$ $A^4,$ $-d^{-1}).$}
\label{F:codeingforD}
\end{figure}

An example is illustrated as in Figure \ref{F:codeingforD},
the virtual spatial graph diagram $D$ can be entered as:
\begin{equation*}
\begin{aligned}
&GraphG = \\
&Y[d,c,b,a,e,g,h,j,cb,ae,gh,jd]
Y[j,k,f,e,a,b,c,d,kf,ea,bc,dj]
X[g,f,k,h];
\end{aligned}
\end{equation*}
Once the graph $D$ is encoded, the command $YamadaPoly[t]$ will produce a value of generalized Yamada polynomial.
For example, the command $YamadaPoly[GraphG]$ will generate the value of generalized Yamada polynomial for the graph in Figure \ref{F:codeingforD}.
\vskip0.5cm
\textbf{Example 1:} Using $R(D; A^4, -d^{-1})$ to detect the virtual spatial graph diagram in Figure \ref{F:G50} and its mirror are not equivalent since $R(D; A^4, -d^{-1})$ is not equal to $R(D^*; A^4, -d^{-1})$ up to multiplication by some $(-A^4)^m$. Its coding is illustrated as in Figure \ref{F:exampleDp}.

\begin{figure}[!htbp]
\centering
\includegraphics[width=12cm]{exampleDp.eps}
\caption{The coding of the virtual spatial graph diagram in Figure \ref{F:G50}.}
\label{F:exampleDp}
\end{figure}

Input: \text{VirtualgraphD} =Y[b,a,c,b,a,d,d,c,ac,ba,dd,cb];\\
 \text{YamadaPoly}[\text{VirtualgraphD}]\\
Output: $-\frac{A^{-6}(1+3A^{4}+3A^{8}+2A^{12})}{1+A^4}$.
\vskip0.5cm

Input:  \text{VirtualgraphD1} = Y[c,b,a,d,d,c,b,a,ba,dd,cb,ac];\\
 \text{YamadaPoly}[\text{VirtualgraphD}]\\
Output: $-\frac{A^{2}(2+3A^{4}+3A^{8}+A^{12})}{1+A^4}$.

\begin{rem}
When the parameter $x\neq -d^{-1},\alpha\neq A^{4}$, the program is no longer valid.
In calculating a generalized Yamada polynomial, the difficulty is that the contribution of some circles in the boundary component is $z$ and the other is $\mu$.
But currently we cannot resolve this kind of difficulty in the Mathematica program.
It may be possible to use other methods to write programs which can be used to compute the full generalized Yamada polynomial.
\end{rem}

\section{Acknowledgements}

Xian'an Jin is supported by NSFC (No. 11671336), President's Funds
of Xiamen University (No. 20720160011).
Qingying Deng is supported by the China Scholarships Council (Grant Nos. 201706310009).
Louis H. Kauffman is supported by the Laboratory of Topology and Dynamics, Novosibirsk State University (contract no. 14.Y26.31.0025 with the Ministry of Education and Science of the Russian Federation).

config: arxiv


TITLE: Why is there a unique ordinal $\alpha$ for every infinite cardinal $\kappa$ such that $\kappa = \aleph_\alpha$?
QUESTION [1 upvotes]: For finding the $\alpha$ I literally can't get any further than writing out the definitions.
For the second part:
Suppose $\aleph_\alpha = \aleph_\beta$ and $\beta \neq \alpha$. Then either $\alpha \in \beta$ or $\beta \in \alpha$. Assume w.l.o.g. that $\alpha \in \beta$. If $\beta$ is a limit ordinal, then $\aleph_\beta = \bigcup \{\aleph_\gamma \ | \ \gamma < \beta\}$, so maybe that is strictly greater than $\aleph_\alpha$, but I can't prove that, and I don't know what to do if $\beta$ is not a limit ordinal.

REPLY [1 votes]: First, use transfinite induction to prove that $\alpha\le \aleph_{\alpha}$ for all ordinal alpha.
From that we get $\kappa\le\aleph_{\kappa}$, so the following is well defined: $$\alpha=\min\{\beta\in On\mid \kappa\le \aleph_{\beta}\}$$
Now try proving that this $\alpha$ is indeed the alpha you are searching for.
For the other part, define
$$\alpha=\min\{\beta\in On\mid \exists\gamma\in On(\gamma\ne \beta\land \aleph_\beta=\aleph_\gamma)\}$$
And
$$\beta=\min\{\gamma\in On\mid \gamma\ne\alpha\land \aleph_\alpha=\aleph_\gamma\}$$
Now we get $\aleph_\alpha<\aleph_{\alpha+1}\le\aleph_\beta$


TITLE: What software do you use to write limits,integrals,sequences,etc?
QUESTION [1 upvotes]: I tried using office word and I couldn't copy paste my limits,sequences and I want help.Does anyone know what program can write the functions in bold as you do?I am new in this and I have no idea what to use.I'm asking for guidance.I am so sorry that I had to write my functions as normal texts but I don't know how to write them in bold as you do.

REPLY [0 votes]: We don't write in bold. We typeset in $\LaTeX$, which is (and has been for many years) the best way to typeset mathematics (and a lot of things, when you know the right packages for the task).


TITLE: Eigenvalues and eigenfunctions of fourth order ODE
QUESTION [0 upvotes]: Find the eigenvalues and eigenfunctions of the problem
$$y^{(4)} − λy = 0$$
with the boundary conditions
(i)  $\quad y(0) = y'' (0) = y(β) = y'' (β) = 0$
(ii)  $\quad y(0) = y' (0) = y'' (β) = y''' (β) = 0$
(iii)  $\quad y(0) = y' (0) = y(β) = y' (β) = 0$

REPLY [1 votes]: $$\begin{align}
\bigg(\frac{d^{4}}{dt^{4}} - \lambda \bigg) y &= \bigg( \frac{d^{2}}{dt^{2}} + \sqrt{\lambda} \bigg) \bigg(\frac{d^{2}}{dt^{2}} - \sqrt{\lambda} \bigg) y\\
&= \bigg(\frac{d}{dt} + i \lambda^{\frac{1}{4}} \bigg) \bigg(\frac{d}{dt} - i\lambda^{\frac{1}{4}} \bigg) \bigg(\frac{d}{dt} + \lambda^{\frac{1}{4}} \bigg) \bigg(\frac{d}{dt} - \lambda^{\frac{1}{4}} \bigg) y \\
&= 0
\end{align}$$
One of the solutions is given by
$$\begin{align}
\bigg(\frac{d}{dt} + i \lambda^{\frac{1}{4}} \bigg) y &= \frac{dy}{dt} + i \lambda^{\frac{1}{4}} y \\
&= 0 \\
\implies y_1(t) &= A\exp(-i\lambda^{\frac{1}{4}}t)
\end{align}$$
where $A$ is a constant. Now it remains to solve each of the other three ODEs (the bracketed terms above), $y_2, y_3, y_4$ to get your solution. Remember to add the solutions together for the total solution $y(t) = y_1 + y_2 + y_3 + y_4$, then use your BCs to solve for the constants $A, B, C, D$.


TITLE: Find 3D distance between two parallel lines in simple way
QUESTION [7 upvotes]: Is there a simple way to get 3D distance between two parallel lines given end points of each line?

REPLY [10 votes]: Simplest way in my opinion:
You can easily calculate the unit direction vector $v$ in each line (subtract the two end points and then divide by the distance between them). $v$ is the same for both lines since they are parallel.
Now we say that $line1$ is represented by a point $p1$ and a unit vector $v$.
and $line2$ is represented by a point $p2$ and the same unit vector $v$.
Then in this case the distance between $line1$ and $line2$ is $||v \times (p_2-p_1)||$.
You can see why in the drawing below:


TITLE: Does irreducibility in $\mathbb{F}_p[x]$ imply irreducibility in $\mathbb{Q}[x]$?
QUESTION [1 upvotes]: As per the title. I'm wondering if $f(x) \in \mathbb{Z}[x]$ is monic and has degree $\geq 2$ and $p$ is prime. I want to prove that if $f \mod n$ in $\mathbb{F}_p$ is irreducible, then $f$ is irreducible in $\mathbb{Q}[x]$. One approach I considered is that since irreducibility over rationals implies irreducibility over ring of integers. So, if I can show that if it's reducible in the integers, it is in $\mathbb{F}_p$ would be an equivalent statement. Could someone show me how I could prove this?

REPLY [3 votes]: Suppose $\;f(x)\in\Bbb Z[x]\;$ reducible in $\;\Bbb Q[x]\;$ . Then by Gauss Lemma it is reducible over $\;\Bbb Z[x]\;$, say $\;f(x)=g(x)h(x)\;,\;\;g,h\in\Bbb Z[x]\;$ , but then
$$\;f(x)\pmod p=\left(g(x)\pmod p\right)\left( h(x)\pmod p\right)\implies f(x)\pmod p\in\Bbb F_p[x]\,$$
is reducible.


TITLE: How will the Starshot swarm accelerate perfectly?
QUESTION [0 upvotes]: I was reading about the Breakthrough Initiative Starshot and I a question came to mind.
From my understanding, the "mothership" will focus powerful lasers on each of the tiny ships, accelerating them out of the solar system.
My thinking is that other photon radiation-emitting objects will interfere with the microships' flight (like the sun). Even with a much more focused force coming from the lasers, won't the sun apply a force in a different direction, causing the ships to veer slightly off course? Even if it's negligible over solar system distances, over the course of ~4.5 light years this would create a huge difference. If the sun and other radiation-emitting bodies won't affect the flight path, why won't they?
Thank you

REPLY [3 votes]: The bulk of the acceleration will be done in the short period where the lasers are trained on the sails. The intensity of the lasers (100 GW or so) is going to be many orders of magnitude larger than sunlight (about 1000 W/m$^2$) and starlight (about 32 million times weaker than sunlight). So the main velocity vector will be set by the lasers, although I can imagine a careful design taking a bit of solar influence into account (not just the light, but also the solar gravity of 0.0059 N/kg that actually will be slightly higher than the light pressure of the sail if is not lighter than about 0.5 g/m$^2$).
In space the starlight is essentially isotropic, so it will not have a major effect.
Once the probe is launched there is really no reason to retain the solar sail and it could be discarded from the probe chip, removing most of the light pressure issues.


TITLE: References to programming languages based on conditional logics
QUESTION [11 upvotes]: Conditional logics are logics which augment traditional logical implication with modal operators corresponding to other notions of condition (for example, the causal conditional $A\; \square\!\!\!\!\to B$ reads "$A$ causes "B", or probabilistic conditioning "$A|B$", which reads "$A$ given $B$").
Typically these logics are studied model-theoretically, but I've wondered about their applications to programming language design (for example, to type imperative actions).
I'd appreciate references to their proof theory (ie, sequent calculus/natural deduction), or to programming languages with types based on these kinds of modal operators.
Thanks!
EDIT: The Stanford Encyclopedia of Philosophy has a nice introduction to the subject.

REPLY [3 votes]: Church might be the kind of thing you are looking for -- it is functional (scheme derivative), but is designed with a probabilistic semantics, and implements conditional probabilities using "query" for doing Bayesian inference.  Discussion of conditioning in Church.  This is (as I understand it) more or less the main operation in most Church programs.
To Matteo Mio: you might also be interested in Graham Priest's book, "An introduction to non-classical logic", which is centered around defining different types of conditionals.


TITLE: Concentration inequalities specialized for log-likelihood / log-density functions
QUESTION [3 upvotes]: Let $P$ be a probability measure and $f$ be some probability density function (not necessarily related to $P$). Consider the function
$$
L(X_1,\ldots,X_n)
=\frac1n\sum_{i=1}^n\log f(X_i),
\quad
X_i\overset{iid}{\sim}P.
$$
This is just the empirical log-likelihood from statistics. Are there any concentration inequalities that are specialized for $L(X_1,\ldots,X_n)$?
Surprisingly, I could not find any in the literature besides the generic ones. That is, we can naively apply generic inequalities such as Bernstein, etc. or assume that $\log f(X_i)$ is a subgaussian random variable, but this is a bit unsatisfying. For example, in the simplest case where $f$ is a Gaussian density, $\log f(x)$ is a quadratic function, and hence not subgaussian if $X_i$ is also Gaussian.
It seems like it should be possible to exploit the fact that $f$ is a density to come up with something more useful.

REPLY [2 votes]: Assume $X$ has density $f$ and put $Y=\log f(X)$.
Then, to compute the moment-generating function of $Y$, we write
$$ E e^{\lambda Y}
=E e^{\lambda\log f(X)}
=E[f(X)^{\lambda}]
=\int_{-\infty}^\infty f^{\lambda+1}(x)dx.
$$
For $\lambda\ge0$,
the latter integral is finite for all densities, because the region where $f\ge1$ must have (Lebesgue) measure $\le 1$, and elsewhere $f<1$ so raising it to a power $>1$ only decreases the value. So the answer depends on your ability to analytically control $F(\lambda):=\int_{-\infty}^\infty f^{\lambda+1}(x)dx$. In the normal Gaussian case, we have $F(\lambda)=1/\sqrt{\lambda+1}$. You can then apply the standard exponential bounding technique (plus Markov's inequality) to the sum of $Y$'s.


TITLE: Independence of functions of order statistics when the random variables are uniformly distributed
QUESTION [3 upvotes]: Let $X_1$,$X_2$,…,$X_n$ be $n$ i.i.d. random variables with $f(x)$ as the pdf and $F(x)$ as the cdf in interval $[0,1]$. Let $F$ be uniformly distributed. Let $X_{i:n}$ be the $i^{th}$ order statistic such that $X_{1:n} \leq X_{2:n} \leq ... \leq X_{n:n}$. I wish to compute the expected value $\mathbb{E} [\frac{X_{(k-1):n} X_{i:n}}{X_{k:n}} ]$ for any $ k < i \leq n$. So the question is are $\frac{X_{(k-1):n}}{X_{k:n}}$ and $X_{i:n}$ independent? Because if they are not, then the problem is non-trivial. Due to a standard result in theory of order statistics, we already know that for any $i \leq n$, $\frac{X_{(i-1):n}}{X_{i:n}}$ and $X_{i:n}$ are independent.

REPLY [2 votes]: It is easy to show that given $X_{i:n} = x$, the order statistics $X_{1:n}, \dots, X_{(i-1):n}$ have the same joint distribution as the order statistics $X_{1:(i-1)}, \dots, X_{(i-1):(i-1)}$ of a sample from the uniform distribution on $[0,x]$, which, in turn, have the same distribution as $x$ times the order statistics of a sample from $[0,1]$. It follows, in particular, that for $k<i$, $\frac{X_{(k-1):n}}{X_{k:n}}$ is indeed independent of $X_{i:n}$ and
$$
\mathrm{E}\Big[\frac{X_{(k-1):n} X_{i:n}}{X_{k:n}} \Big] = \mathrm{E}\Big[\frac{X_{(k-1):n} }{X_{k:n}} \Big]\mathrm{E}[X_{i:n}] = \frac{k-1}k \cdot \frac{i}{n+1}.
$$


TITLE: Integral along parametric curve
QUESTION [0 upvotes]: Studying complex analysis I came across the following example. Consider the function $f(z)=x^2+i\,y^2$ integrated along the smoof curve parametrized by $z(t)=t+i\,t$ for $0\leq t\leq1$.  How do I construct this parametric curve?
I know that such a curve $z(t)$, must be in the complex plane, and that, I can start that the start and end points are, respectively, $z(0)=0$ and $z(1)=1+i$. But I really can not build the curve itself. I just need to understand this to continue with the calculation of the integral of $f(z)$ on the aforementioned curve, which by the way is quite simple in this case. In advance I am grateful for the clarifications.

REPLY [0 votes]: Also you can think the following idea. Writing the curve one has $$z(t) = t+it=t(1+i), $$i. e., it's a segment that starts at the origin with direction vector $$1+i. $$


TITLE: Find all properties of this set $S$ in the metric space $(\mathbb{R},\rho)$
QUESTION [0 upvotes]: Set $S=(0,1]\cup([-\sqrt{2},\sqrt{3})\cap\mathbb{Q})$ in metric space $(\mathbb{R},\rho)$ with standard metric $\rho(x,y)=|x-y|$.
Find the following sets:
$S'$, $\text{Closure}(S)$, $\text{Closure}(S')$, $\text{int}(S)$, $\text{ext}(S)$, $\text{bd}(S)$, $\text{bd}(\text{int}(S))$, $\text{bd}(\text{ext}(S))$, $\text{int}(\text{bd}(S))$, $\text{ext}(\text{bd}(S))$.
Also, which of these sets are open and which are closed

Im not sure what am I doing
$S'=\mathbb{R} \setminus (\mathbb{Q}\cup(0,1])$
$\text{Closure}(S)=\text{int}(S)\cup \text{bd}(S)=\emptyset \cup \text{bd}(S) = S $
$\text{Closure}(S)=\text{?}$
$\text{int}(S)=\emptyset$
$\text{ext}(S)=\mathbb{R} \setminus S$
$\text{bd}(S) = S$
....

Or can I look at each cases individually and combine their results?

$(0,1]$
$[-\sqrt{2}. \sqrt{3})$
$\mathbb{Q}$

REPLY [2 votes]: $\newcommand{\cl}{\operatorname{cl}}\newcommand{\int}{\operatorname{int}}\newcommand{\bdry}{\operatorname{bdry}}$ You have the set $S=(0,1]\cup\left([-\sqrt2,\sqrt3)\cap\Bbb Q\right)$. $S'$ is the set of limit points of $S$. In this setting there are at least two ways to think about limit points that might help. First, $x\in S'$ if every open interval containing $x$ contains some point of $S\setminus\{x\}$. Equivalently, $x\in S'$ if there is a sequence of distinct points of $S$ converging to $x$. For instance, take $0$. If an open interval $(a,b)$ contains $0$, then $a<0<b$, and clearly we can find a point of $(0,1]$ and hence of $S$ in $(a,b)$; thus, $0\in S'$. (In fact $0\in S$ as well, since $0\in[-\sqrt2,\sqrt3)\cap\Bbb Q$.) Alternatively, $\langle\frac1n:n\in\Bbb Z^+\rangle$ is a sequence of distinct point of $S$ converging to $0$, so $0\in S'$. It’s not hard to see that in similar fashion we can demonstrate that every $x\in(0,1]$ is in $S'$, so $[0,1]\subseteq S'$. What else is in $S'$?
We can write off anything that’s less than $-\sqrt2$ or more than $\sqrt3$: if $x<-\sqrt2$, then $(x-1,-sqrt2)$ is an open interval around $x$ that contains no point of $S$, and similarly, if $x>\sqrt3$, $(\sqrt3,x+1)$ is an open interval around $x$ that completely misses $S$. Suppose, though, that $-\sqrt2\le x\le\sqrt3$, and that $(a,b)$ is an open interval containing $x$. Then there is a sequence of distinct rationals in $[-\sqrt2,\sqrt3)$ converging to $x$, so $x\in S'$. Thus, $[-\sqrt2,\sqrt3]\subseteq S'$.
Putting the pieces together, and noting that $[0,1]\subseteq[-\sqrt2,\sqrt3]$, we see that $S'=[-\sqrt2,\sqrt3]$. Note that in this case it happens to be true that $S\subseteq S'$: every point of $S$ is also a limit point of $S$. This isn’t always the case: if $A=\{0\}\cup[1,2]$, then $0\in A$, but $0\notin A'$: $(-1,1)$ is an open interval about $0$ that contains no other point of $A$.
Now $\cl S=S\cup S'$, and $S\subseteq S'$, so $\cl S=S'=[-\sqrt2,\sqrt3]$. This means that $S'$ is a closed set, so $\cl S'=S'$: it already contains all of its limit points.
A point $x$ is in the interior of $S$ if there is an open interval $(a,b)$ containing $x$ such that $x\in(a,b)\subseteq S$. Clearly $(0,1)\subseteq S$, so for every $x\in(0,1)$ we can take $(a,b)$ to be $(0,1)$ and see that $x\in\int S$; this shows that $(0,1)\subseteq\int S$. The only other part of $\Bbb R$ where we even find points of $S$ is in the interval $[-\sqrt2,\sqrt3)$. Some of those are in $(0,1)$ and are already known to belong to $\int S$. The others are the points of $[-\sqrt2,0]\cap\Bbb Q$ and $[1,\sqrt3)\cap\Bbb Q$. Neither of these sets contains any non-empty open interval at all: both are full of ‘holes’ at the irrational numbers. Thus, no point in either of these sets has an open interval around it lying entirely within $S$, and therefore no point of either of these sets is in the interior of $S$. Consequently, $\int S=(0,1)$.
I’m going to stop here to give you a chance to have another go at the exterior and boundary of $S$ on your own. I do want to comment on the last bit of your question, however, where you ask whether you can look at three cases individually and combine their results. You really have only two cases: $S$ is the union of two sets, $(0,1]$ and $[-\sqrt2,\sqrt3)\cap\Bbb Q$, not three. And you can’t treat even them completely in isolation from each other, because they have a non-empty intersection, $(0,1]\cap\Bbb Q$: every rational number in $(0,1]$ is in both pieces. If you really wanted to deal with $S$ in separate chunks and then combine the results, a much better choice of chunks would be $[-\sqrt2,0]\cap\Bbb Q$, $[0,1)$, and $[1,\sqrt3)\cap\Bbb Q$, since these are disjoint.


TITLE: Prove by mathematical induction that $n! < n^n$ where $n > 1$
QUESTION [1 upvotes]: Basic step
Show that $P(2)$ is true:
$$2! < (2)^2$$
$$1*2 < 2*2$$
$$2 < 4 \quad \text{(which is true)}$$
Inductive Step
Assume $P(k) \implies (k)! < (k)^k $ is true
then, I'm not sure how to continue

REPLY [1 votes]: When $n=2$,
$n!=2<n^n=4$
Assume when $n=k$,$k!<k^k$ is true,i.e.$\frac{k^k}{k!}>1$
When$\  n=k+1$
We consider
$$\frac{k+1^{k+1}}{(k+1)!}$$
$$=\frac{k+1^{k}}{k!}$$
$$\frac{k+1^{k}}{k!}>\frac{k^k}{k!}>1$$
So, when $n=k+1$,$n!<n^n$ is right.


TITLE: Let $F(x)=cot\int_{\int_{0}^{x}tan(a)da}^{1}cosh(\int_{0}^{t}udu)dt$ Find $F'(x)$
QUESTION [1 upvotes]: "Let $F(x)=\cot\int_{\int_{0}^{x}\tan(a)da}^{1}\cosh(\int_{0}^{t}udu)dt$. Find $F'(x).$"
We know:
$F'(x)=-\csc^{2}(\int_{\int_{0}^{x}\tan(a)da}^{1}\cosh(\int_{0}^{t}udu)dt)\times(\int_{\int_{0}^{x}\tan(a)da}^{1}\cosh(\int_{0}^{t}udu)dt)'$
Let $A(x)=\int_{\int_{0}^{x}\tan(a)da}^{1}\cosh(\int_{0}^{t}udu)dt$
Then: $A'(x)=-\cosh(\int_{0}^{\int_{0}^{x}\tan(a)da}udu)\tan(x)$
Then,
$F'(x)=\csc^{2}(\int_{\int_{0}^{x}\tan(a)da}^{1}\cosh(\int_{0}^{t}udu)dt)\cosh(\int_{0}^{\int_{0}^{x}\tan(a)da}udu)\tan(x)$
But I'm not sure my result is correct. Can someone help me?

REPLY [0 votes]: Your function has the form
$$F (x)=\cot (f (x))=$$
$$\cot (-\int_1^{g (x)}h (t)dt )$$
with $$g (x)=\int_0^x\tan (a)da $$
and
$$h (t)=\cosh (\int_0^t udu) .$$
thus
$$F'(x)=-\frac {1}{\sin^2 (f (x))}\Bigl (-h (g (x))g'(x)\Bigr) $$
with $$g'(x)=\tan (x) $$
hence

$$F'(x)=(1+F^2 (x))\cosh (\int_0^{\int_0^x\tan (a)da})\tan (x) $$


TITLE: Characteristic roots of symmetrical transformation in euclidean space
QUESTION [1 upvotes]: Need help in understanding a key point in the proof:
In euclidean space, a symmetrical transformation's characteristic roots are reals.
Let $f$ be a symmetrical transformation in a euclidean space $E$, $\dim (E)=n$, let $e:= \{e_1,\ldots ,e_n\}$ be an orthonormed basis in $E$ and let $A:= A_f^e$ be matrix of $f$ with respect to basis $e$. Transformation $f$ has the same characteristic roots as $A$, which are the roots of $\det (A-\lambda I)$. We have an $n-$degree polynomial with real coefficients, which has $n$ roots in $\mathbb{C}$. Objective is to show all roots are real.
Matrix $A$ is symmetrical. ##Now comes the problematic part for me##:
Let $\lambda _0\in\mathbb{C}$ be a root of $\det (A-\lambda I)$ then we have a system of equations with complex coefficients:
$$\begin{cases} (a_{11}-\lambda_0)x_1 +\ldots +a_{1n}x_n = 0\\
a_{21}x_1+(a_{22}-\lambda_0)x_2 +\ldots +a_{2n}x_n= 0\\\ldots\\
a_{n1}x_1 + a_{n2}x_2 +\ldots + (a_{nn}-\lambda_0)x_n=0 \end{cases}$$
The former system has a non-zero solution $(k_1,\ldots ,k_n)\in\mathbb{C}^n$, therefore for every $i\in\{1,\ldots ,n\}$
$$\sum_{j=1}^n a_{ij}k_j = \lambda_0k_i $$
and so on..
Are we not supposed to calculate the determinant, I don't understand where the system of equations came from or how/why it is relevant. Secondly, why does the system of equations have a non-zero solution and thirdly why is the last equality satisfied for all $i$?

REPLY [1 votes]: Let $A$ be an $n\times n$ real matrix.  We say $A$ is symmetric iff $A=A^T$ is equal to its own transpose.
The compact expression $\det(A-\lambda I) = 0$ is the characteristic polynomial equation in $\lambda$, whose roots are the "characteristic roots" or eigenvalues of $A$.  In other words, those $\lambda$ which give $A-\lambda I$ as singular matrices will result in nontrivial solutions to the homogeneous linear equations:
$$ (A - \lambda I) \vec x = \vec 0 $$
Writing out the separate linear equations results in the system shown in the Question.
The vector $x$, if it is such a nonzero solution, then satisfies $A\vec x = \lambda \vec x$.  Then we say $x$ is an eigenvector of $A$ corresponding to eigenvalue $\lambda$.
Now the related facts about a symmetric real $A$ are remarkable.  Not only will the characteristic roots of $A$ be real, there will be a "full set" of these in the sense that there will be a basis of the eigenvectors of $A$ for all of its eigenvalues.  Representing $A$ with respect to such a basis results in a diagonal matrix.  Hence we know $A$ is (real) diagonalizable, i.e. similar to a (real) diagonal matrix, when $A$ is real and symmetric.


TITLE: Classification of closed 3-manifolds with finite first homology group?
QUESTION [6 upvotes]: I am interested in a topological classification of connected closed 3-manifold $M$ that have finite homology group $H_1(M)$.
Since $H_1(M)$ is the abelization of the fundamental group $\pi_1(M)$, each closed 3-manifold with finite homotopy group has finite homology group.
It is known that each closed 3-manifold with finite homotopy group $\Gamma$ is a spherical 3-manifold (i.e., is the orbit space $S^3/_\sim$ of the 3-sphere, endowed with a free action of the group $\Gamma$).

Question. Is each closed 3-manifold with trivial homology group a spherical 3-manifold? Equivlalently, is the fundamental group $\pi_1(M)$ of a closed 3-manifold finite if its first homology group $H_1(M)$ is finite?

REPLY [6 votes]: Pick any knot in the three-sphere, and perform any Dehn surgery on it with some coefficient $p/q \neq 0$. This means that you remove the tubular neighborhood of the knot and you glue it back in a different way, parametrized by $p/q$. The manifold you get has $H_1(M,\mathbb Z) = \mathbb Z/_{p\mathbb Z}$. You get plenty of distinct 3-manifolds in this way. For instance, if the knot is hyperbolic, you get plenty of closed hyperbolic manifolds if $p$ or $q$ is sufficiently large. You can also require that $p=1$ and find plenty of homology spheres.