text:
\begin{document}
\maketitle
  \vspace{-1cm}
  \begin{center}
  	$a$
  	{\small \it Algorithms and Complexity Group}\\
  	{\small \it Vienna University of Technology}\\
  	{\small  \it Favoritenstrasse 9-11,}
  	\vspace*{5mm}
  	{\small \it 1040 Vienna, Austria }\footnote{Research supported in part by FWF Project P27615-N25.} \\

  \end{center}

\begin{abstract}
It is a well-known fact that hamiltonicity in planar cubic graphs is an
NP-complete problem. This implies that the existence of an $A-$trail in
plane eulerian graphs is also an NP-complete problem even if restricted
to planar $3-$connected eulerian graphs.
In this paper we deal with hamiltonicity in planar cubic graphs $G$
having a facial $2-$factor $\mathcal{Q}$ via (quasi) spanning trees of
faces in $G/\mathcal{Q}$ and study the algorithmic complexity of finding
such (quasi) spanning trees of faces. We show, in particular, that
if Barnette's Conjecture is false, then hamiltonicity in $3-$connected
planar cubic bipartite graphs is an NP-complete problem.\\
\\

{\bf Keywords:}
Barnette's Conjecture; Eulerian plane graph; Hamiltonian cycle; Spanning tree of faces;  $A-$trail.

\end{abstract}

\section{Introduction and Preliminary Discussion}

Our joint paper~\cite{Bagheri} can be considered as the
point of departure for the subsequent discussion and results of this
paper. Next, we make a few historical remarks.
In $1884$, Tait  conjectured that every cubic
$3-$connected planar graph is
hamiltonian~\cite{Tait}.
And Tait knew that the validity of his conjecture would yield a simple
proof of the Four Color Conjecture. On the other hand, the Petersen graph
is the smallest non-planar $3-$connected cubic graph which is not hamiltonian,~\cite{Petersen}.
Tait's Conjecture
 was disproved by Tutte in $1946$. However, none of the known counterexamples of Tait's Conjecture is
bipartite. Tutte himself conjectured that every cubic $3-$connected
bipartite graph is hamiltonian~\cite{Tutte1971}, but this was shown to be
false by the construction of a counterexample,
the Horton graph~\cite{Horton}.  Barnette  proposed a
combination of Tait's and Tutte's Conjectures implying that every counterexample
to Tait's conjecture is non-bipartite.\\

\medskip \noindent
{\bf Barnette's Conjecture}~\cite{Barenette}
{\it Every $3-$connected cubic planar bipartite graph is hamiltonian.}\\

Holton, Manvel and McKay showed in~\cite{Holton}  that Barnette's Conjecture holds true for graphs with up to
$64$ vertices. The conjecture
also holds for the infinite family of graphs where all faces are either quadrilaterals or  hexagons, as shown by
Goodey~\cite{Goodey}. However, it is NP-complete to decide whether
a $2-$connected cubic planar bipartite graph  is hamiltonian~\cite{Takanori}.

For a more detailed account of the early development of hamiltonian graph theory we refer the interested reader
to~\cite{Biggs}.

As for the terminology used in this paper we follow~\cite{Bondy} unless stated explicitly otherwise.
In particular, the subset $E(v)\subseteq E(G)$ denotes the set of edges incident to $v\in V(G)$.

\medskip \noindent
We repeat some definitions stated already in~\cite{Bagheri} in order to make life easier for the reader.

\begin{definition}
A cubic graph $G$ is {\sf cyclically $k-$edge-connected} if at least $k$ edges must be removed to disconnect $G$ either into two components
 each of which contains a cycle provided $G$ contains two disjoint cycles, or else into two non-trivial components. The {\sf cyclic edge-connectivity} of $G$ is the maximum $k$ such that $G$ is cyclically $k-$edge-connected, denoted $\kappa{'}_c(G)$.
\end{definition}
\begin{definition}
Let $C$ be a cycle in a plane graph $H$. The cycle $C$ divides
the plane into two disjoint open domains. The  {\sf interior} $(${\sf exterior}$)$ of $C$
is the bounded $($unbounded$)$ domain and is denoted by
$int(C)\ (ext(C))$.
By treating parallel edges as a single edge,
we say a cycle $C^{'}$ is {\sf inside} of
$C$ if $int(C^{'})\subseteq int(C)$.
Moreover,
a cycle $C$ is said
{\sf to contain a vertex $v$ inside (outside)}   if $v\in int(C)\ (v \in ext(C))$. Finally,  $C$ is said to be a  {\sf separating} cycle in $H$ if
$int(C)\cap V(H)\neq \emptyset \neq ext(C)\cap V(H)$.
\end{definition}

\begin{remark}
\begin{description}
\item[1.]
Two edges $e=xy$ and $e^{'}=xy$ are called {\sf parallel edge}s
if the digon $D$ defined by $e$ and $e^{'}$ has no vertices inside.
If two different triangles $T_1$ and $T_2$ have an edge  in common, then
they have no other edge in common (because of our understanding that
parallel edges are treated as a single edge), unless there is
$e_i=xy\in E(T_i),\ i=1,2$, such that $\langle e_1,e_2\rangle$ defines a digon with
some vertex  inside.
\item[2.]
Given a $2-$connected plane  graph, we do not distinguish between faces and their face boundaries.
Observe that in planar $3-$connected graphs $H$,
the face boundaries are independent from any actual
embedding of $H$ in the plane or sphere.
\end{description}
\end{remark}
\begin{definition}
Given a graph $H$ and a vertex $v$, a fixed sequence
$\langle e_1,\ldots,e_{\deg(v)}\rangle$ of the edges in $E(v)$
is called a {\sf positive ordering} of $E(v)$ and is denoted by
$O^{+}(v)$. If  $H$ is imbedded in some surface, one such $O^{+}(v)$
is given by the counterclockwise cyclic ordering of the edges incident
to $v$.
\end{definition}

\begin{definition}\label{DEF:A-trail}
Let $H$ be an eulerian graph with a given positive ordering $O^{+}(v)$
for each vertex $v\in V(G)$. An eulerian trail $L$ is an {\sf $A-$trail}
if  $\{e_i,e_j\}$ being a pair of consecutive edges  in $L$
incident to $v$ implies
$j=i\pm1$ $({\rm mod}\ \deg(v))$.
-- As a consequence, in an $A-$trail in a $2-$connected plane graph any two consecutive edges belong to a face boundary.

An $A-$trail $L$ in an eulerian triangulation of the plane is called {\sf non-separating} if for every face boundary $T$  at least two edges of $E(T)$ are consecutive in
$L$.
\end{definition}

An $A-$trail $L=e_1e_2\ldots e_m$ induces a vertex partition $V_L(H)=\{V_1,V_2\}$ on $V(H)$ as follows.  Consider  a
$2-$face-coloring of $H$ with colors $1$ and $2$. For every vertex $v$ of $H$, $v\in V_i$ if and only if  there is $j\in \{1,\ldots,m-1\}$ such that $v\in V(e_j)\cap V(e_{j+1})$ and the face containing $e_j$ and $e_{j+1}$ in its boundary is colored $3-i$,  $i=1,2$.

\begin{oldtheorem}~$(${\rm\cite[Theorem~2]{Andersen95}}$)$\label{TH:A-Tr.NP-C}
The problem of deciding whether a planar eulerian graph admits an
$A-$trail is NP-complete, even for $3-$connected graphs having only $3-$cycles
and $4-$cycles as face boundaries.
\end{oldtheorem}

In contrast,  Andersen et al. in~\cite{Andersen98} gave a polynomial algorithm for
finding $A-$trails in simple $2-$connected outerplane eulerian graphs.

\begin{definition}\label{DEF:Radial}
Suppose $H$ is a $2-$connected plane  graph. Let  $\mathcal{F}(H)$ be
the set of faces of $H$. The {\sf radial graph} of $H$ denoted by
$\mathcal{R}(H)$ is a bipartite graph
with the vertex bipartition $\{V(H),\mathcal{F}(H)\}$
such that $xf\in E(\mathcal{R}(H))$ if and only if $x$ is a vertex in the boundary of
$F\in \mathcal{F}(H)$ corresponding to $f\in V(\mathcal{R}(H))$.

Let $U\subseteq V(H)$ and let $\mathcal{T}\subset \mathcal{F}(H)$ be a
set of bounded faces of $H$.
The {\sf restricted radial graph}
$\mathcal{R}(U,\mathcal{T})\subset \mathcal{R}(H)$ is defined  by $\mathcal{R}(U,\mathcal{T})=\langle U\cup \mathcal{T}\rangle_{\mathcal{R}(H)}$.
\end{definition}

\begin{definition}\label{DEF:Leapfrog}
Let $G$ be a $2-$connected plane graph and  $v$ be a vertex of $G$ with $\deg(v)\ge 3$. Also assume that a sequence
$\langle e_1,\ldots,e_{\deg(v)}\rangle$, $e_i=u_iv,\ i=1,\ldots,\deg(v)$
is given by the counterclockwise cyclic ordering of the edges incident to $v$.
\begin{description}

\item[$(i)$]
  A {\sf truncation} of $v$ is the process of replacing $v$ with a
cycle $C_v=v_1\ldots v_{\deg(v)}v_1$ and replacing $e_i=u_iv$ with
$e_i^{'}=u_iv_i$, for $i=1,\ldots,\deg(v)$ in such a way
that the result is a plane graph again. A plane graph obtained from
$G$ by truncating  all vertices of $G$ is called {\sf  the truncation of $G$}
and denoted by $Tr(G)$.
\item[$(ii)$]
For a  plane graph $G$ let
$G^{*}$ denote   the dual of $G$.
The {\sf leapfrog extension} $Lf(G)$ of a plane
graph $G$ is $(G\cup \mathcal{R}(G))^{*}$. In the case of cubic $G$,
it can be viewed as obtained from $G$  by replacing every $v\in V(G)$ by
a hexagon $C_6(v)$, with $C_6(v)$ and $C_6(w)$ sharing an edge if and
only if $vw\in E(G)$; and these hexagons are faces of $Lf(G)$.
\end{description}
\end{definition}

\begin{oldtheorem}~$(${\rm\cite[Theorem~23]{FleischnerEnvelope}}$)$\label{TH:Lf.NP-C}
The question of whether the leapfrog extension of a plane cubic graph
with multiple edges is hamiltonian is NP-complete.
\end{oldtheorem}

We note in passing that we call leapfrog extension,
what is called in other papers  vertex envelope, or leapfrog construction, or leapfrog operation, or  leapfrog transformation (see e.g.~\cite{FleischnerEnvelope,Fowler,Kardos,Yoshida}).

\begin{definition}
Let $H$ be a  $2-$connected plane graph, let $U\subset V(H)$, and let $\mathcal{T}\subset \mathcal{F}(H)$ be a set of bounded faces. We define a subgraph $H_{\mathcal{T}}$ of $H$  by
$H_{\mathcal{T}}=\big\langle \cup_{F\in \mathcal{T}}E(F)\big\rangle$.
If for every $x\in V(H)\setminus U$, $\big|\big\{F\in \mathcal{T}\ :\ x\in V(F)\big\}\big|=\frac{1}{2} \deg_H(x)$
and if $\mathcal{R}(U,\mathcal{T})$ is a tree, then we call $\mathcal{T}$
a {\sf quasi spanning tree of faces} of $H$, and the vertices in
$U\ (V(H)\setminus U)$ are called {\sf proper} $(${\sf quasi}$)$ vertices.
If $U=V(H)$, then $\mathcal{T}$ is called a {\sf spanning tree of faces}.
\end{definition}

If a plane graph has a face-coloring with color set $X$, the faces of color $x\in X$ will then be called $x-$faces.

\begin{observation}\label{obs:A-trail}
We observe that if $H$ is a  plane eulerian graph with $\delta(H)\ge 4$
having an $A-$trail $L$, then  $L$ defines
uniquely a quasi spanning tree of faces as follows.
Starting with a
$2-$face-coloring of $H$ with colors $1$ and $2$, suppose the outer face
of $H$ is colored $1$.    Let $V_L(H)=\{V_1, V_2\}$ be the
partition of $V(H)$ induced by $L$.
Now, the set of all $2-$faces  defines a quasi spanning tree of
faces $\mathcal{T}$ with $V_1$ being the set of all quasi vertices of
$\mathcal{T}$.
Conversely, a $($quasi$)$ spanning tree of faces $\mathcal{T}$ defines
uniquely an $A-$trail in $H_\mathcal{T}$.
\end{observation}

The aforementioned relation between the concepts of $A-$trail  and
(quasi) spanning tree of faces is not a coincidence. In fact, it had been shown
(\cite[pp.~$VI.112-VI.113$]{Fleischner})
that

$\bullet$ {\it Barnette's Conjecture is true if and only if every simple $3-$connected eulerian
triangulation of the plane admits an $A-$trail.}\\

We point out, however, that the concept of (quasi) spanning tree of faces
is a somewhat more general tool to deal with hamiltonian cycles in
plane graphs, than the concept of $A-$trails.

We are thus focusing our considerations below on the
complexity of the existence of $A-$trails and (quasi) spanning trees
of faces in plane (eulerian) graphs.

Parts of this paper are the result of extracting
some results and their proofs of~\cite{Feder} which appear correct to
all four of us; they have not been published yet.
Moreover, we relate some of the results of this paper to the theory of
$A-$trails, as developed in~\cite{Fleischner}.

\medskip \noindent
In the sequel

\medskip \noindent
{\it $G$ always denotes a $3-$connected cubic plane graph
having a facial $2-$factor $\mathcal{Q}$ $($i.e., a $2-$factor whose cycles are face
boundaries of $G)$; we denote the set of face boundaries of $G$ not in
$\mathcal{Q}$ by $\mathcal{Q}^{c}$.
 In general, when we say that $F$ is an $\mathcal{X}-$face, we mean that
  $F\in \mathcal{X}$.
 Let $H$ always denote the reduced graph obtained from $G$ by contracting  the $\mathcal{Q}-$faces
  to single vertices; i.e., $H=G/\mathcal{Q}$.
  \hfill $(\bf H)$}\\

Next, we list several results of a preceding joint paper
which will be essential for the current paper.

\begin{oldtheorem}~$(${\rm\cite[Proposition~1]{Bagheri,Feder}}$)$
\label{PR:1}
Let $G,\mathcal{Q},$ and $H$  be as stated in $(\bf H)$.
  The reduced
graph $H$ has a quasi spanning tree of faces, $\mathcal{T}$, with
 the external face not
in $\mathcal{T}$ if and only if $G$
has a hamiltonian cycle $C$ with  the external $\mathcal{Q}^{c}-$face outside of $C$,
with all $\mathcal{Q}-$faces corresponding to proper vertices
of $\mathcal{T}$
inside of $C$, with
all $\mathcal{Q}-$faces corresponding to quasi vertices
of $\mathcal{T}$
outside of $C$, and such that no two $\mathcal{Q}^{c}-$faces sharing an edge are both
inside of $C$.
\end{oldtheorem}

\begin{oldtheorem}~$(${\rm\cite[Corollary~7]{Bagheri}}$)$\label{cor:4con-eulerian-triangulation}
Every simple $4-$connected eulerian triangulation of the plane has a
quasi  spanning tree of faces.
\end{oldtheorem}

\section{Polynomial and NP-Complete Problems}\label{Sec:Complexity}

In proving   Propositions $3$ and $6$, and Theorem $11$
in~\cite{Bagheri}, we used implicitly some
algorithms to construct a (quasi) spanning tree of faces. In all of them,
we find some triangular face such that the  graph
resulting from the
contraction of this face, still satisfies the
hypothesis of the respective result.
 By repeating this
process, finally the contracted faces together  with a
special face form a (quasi) spanning tree of faces.
 Note that it is possible to identify the contractible faces in linear time, since every simple plane graph has $O(n)$ faces, where $n$ is the order of graph.
 Therefore, our
algorithms for finding a quasi spanning tree of faces   in~\cite{Bagheri}
are  polynomial.

We show next that one can decide in polynomial time whether the reduced graph $H$ has a spanning tree of
faces which are either digons or triangles. The result easily extends to the
case of a spanning tree of faces where all but a constant number of faces are either digons
or triangles.

{\bf The Spanning Tree Parity Problem:} {\it
Given a graph $G$ and a collection of pairs of edges,
$\{\{e_i,f_i\}\ |\ i=1,\ldots, k\}$. {\sf The Spanning Tree Parity Problem}
asks whether $G$ has a spanning tree $T$ satisfying $|\{e_i,f_i\}\cap E(T)|\in \{0,2\}$, for each $i=1,\ldots,k$.}

Note that the Spanning Tree Parity Problem is
solvable in polynomial time (see~{\rm\cite{Gabow,Lovasz}}).

\begin{theorem}\label{TH:3}
Let $G,\mathcal{Q},$ and $H$  be as stated in $(\bf H)$.
 Let $D$ be the set
 of faces in $H$ such that
all faces in $\mathcal{D}$ are either digons or triangles. Then we can decide in polynomial time whether $H$ has a spanning
tree of faces in $D$, giving a hamiltonian cycle for $G$, by a spanning tree
parity algorithm.
\end{theorem}
\begin{proof}{ Construct a graph $H^{'}$ related to $H$ as follows. $V(H^{'})=V(H)$. If $xyx$ is a digon in $\mathcal{D}$, then let  $xy$ be an edge in $H^{'}$ . If $xyzx$ is a triangle
in $\mathcal{D}$, then put edges $xy$ and $yz$ in $H^{'}$
(the naming of the  vertices of the triangle with the symbols $x,y,z$ is arbitrary but fixed). A spanning tree of faces in $\mathcal{D}$ for H then corresponds
to a  spanning tree in $H^{'}$ which must contain either both or none of
 the edges $xy$ and
$yz$ corresponding to  the triangle $xyzx$ in $\mathcal{D}$. Thus, these conditions on pairs of edges in $H^{'}$
transform the problem of finding a spanning tree of faces
 in $\mathcal{D}$ for $H$ equivalently in polynomial time into a Spanning Tree Parity Problem in $H^{'}$.
}\end{proof}

If $\mathcal{D}$ contains faces with four or more sides, say a face $xyztx$, then we could include three
edges linking these four vertices, say $xy,\ yz,$ and $zt$, and require that a spanning tree  must contain
either all three or none of these three edges. Such a spanning tree triarity problem, as we
shall  see later, turns out to be NP-complete.

The following is immediate from Theorem~\ref{PR:1}.

\begin{theorem}~$(${\rm\cite[Proposition~3]{Feder}}$)$\label{PR:3} Let $G$ be a $3-$connected cubic plane bipartite graph whose faces are $3-$colored with color set $\{1,2,3\}$ and the outer face of $G$ is a $3-$face. Then the following statements are equivalent.

\begin{description}

\item[$(i)$]  $G$ has a hamiltonian cycle $C$ with the $2-$faces  lying inside of $C$, the $3-$faces lying outside of $C$, and $1-$faces on either side;
\item[$(ii)$] the reduced graph $H$ obtained by contracting  the
$1-$faces has an $A-$trail;
\item[$(iii)$] the reduced graph $H^{'}$ obtained by
contracting  the $2-$faces has a spanning tree of $1-$faces;
\item[$(iv)$] the reduced graph $H^{''}$
obtained by contracting  the $3-$faces has a spanning tree of $1-$faces.
\end{description}
\end{theorem}

\begin{proof} $(i)\Rightarrow(ii):$ Let $T_C$ be a
closed trail in $H$ induced by
hamiltonian cycle $C$ of $G$. The
closed trail $T_C$ is an eulerian trail, otherwise there are two  faces of $G$ with two different colors $2$ and $3$ lying on one side of $C$. Since all $2-$faces ($3-$faces) of $G$ are lying inside (outside) of $C$, for every $1-$face $F_1$ of $G$ we conclude that $E(F_1)\cap E(C)$ is a matching. Thus, $T_C$ is an $A-$trail.\\

$(ii)\Rightarrow(i):$ It is easy to see that any $A-$trail of $H$ can be transformed into a hamiltonian cycle $C$ of $G$ with the $2-$faces  lying inside of $C$, the $3-$faces lying outside of $C$, and $1-$faces lying on either side.\\

$(i)\Rightarrow(iii):$  Let $U= V(H^{'})$ be the vertex set corresponding to the $2-$faces. Also, let $\mathcal{T}$ be the set of  $1-$faces
of $H^{'}$ corresponding to the $1-$faces in $int(C)$.

Observe that $G_{int}:=C\cup int(C)$
is a spanning outerplane subgraph of $G$, and that the weak dual
(the subgraph of the dual graph whose vertices correspond to the bounded faces) of
$G_{int}$ is a tree (see~\cite{Fleischner}). Therefore,
$H^{'}_{int}\subset H^{'}$ being the reduced graph of $G_{int}$
after contracting the $2-$faces, is a spanning tree of faces in $H^{'}$.
\\
$(iii)\Rightarrow(i):$   Suppose $H^{'}$ has a spanning tree of
 $1-$faces $\mathcal{T}$.
 Then $H^{'}_{\mathcal{T}}$ has a unique $A-$trail which can be transformed    into a hamiltonian cycle $C$ of $G$ such that
 the $2-$faces
 (corresponding to $V(H^{'})$) lie in $int(C)$ and
the  corresponding $3-$faces   lie in $ext(C)$.

The equivalence of $(i)$ and $(iv)$ is established analogously by looking at $G_{ext}:=C\cup ext(C)$ which is also an outerplanar graph.
\end{proof}

An application of Theorems~\ref{TH:3} and~\ref{PR:3}
yields the following.

\begin{corollary}\label{CR:2} Let $G$ be a cubic plane bipartite graph
with a $3-$face-coloring with color set $\{1,2,
3\}$, and let $H$ be the reduced graph obtained by contracting
 the $1-$faces. Suppose all vertices of $H$ have degree $4$ or $6$.

Then one can decide in polynomial time whether $H$ has an $A-$trail
 which in turn yields a hamiltonian cycle in $G$.
\end{corollary}

\begin{proof}{ Let $H^{'}$ be the reduced graph of $G$ obtained by contracting the $2-$faces instead
of the $1-$faces. Then  each $1-$face of $G$ yields a
digon or triangle in $H^{'}$. By Theorem~\ref{PR:3}, an
$A-$trail  in $H$ corresponds to a spanning tree of $1-$faces in $H^{'}$. Since all
$1-$faces  of $H^{'}$ are either digons or triangles, one can decide
in polynomial time by Theorem~\ref{TH:3}, whether such a spanning tree
of $1-$faces exists in $H^{'}$.
}\end{proof}

By Observation~\ref{obs:A-trail}, we have the following theorem
in which we make use of the fact that an
(eulerian) triangulation of the plane admits two interpretations, namely: as the dual of a plane cubic   (bipartite) graph, and as the contraction of a facial (even) $2-$factor $Q$ in $G$ whose faces in $Q^c$ are hexagons. Also note that a plane bipartite cubic graph  $G$ has a hamiltonian cycle if and only if the dual graph $G^*$ has a non-separating $A-$trail~\cite{Fleischner}.

\begin{theorem}\label{TH:Herbert}
	 Let $G$ be a  $3-$connected cubic planar bipartite graph and let $\mathcal{F}$ be the set of its faces. Let
$\mathcal{Q}_{\mathcal{F}}$ be the facial $2-$factor of $Lf(G)$
corresponding to $\mathcal{F}$ and let the color classes of the $3-$face-coloring of $Lf(G)$ be denoted by $F_1$, $F_2$, and $F_3$ such that $F_3 = \mathcal{Q}_{\mathcal{F}}$, and thus $F_1$, $F_2$ translates into a $2-$face-coloring of $Lf(G)/\mathcal{Q}_{\mathcal{F}}$  denoting the corresponding sets of faces by $F1$, $F2$ and whose vertex set $($corresponding to $F_3)$ be denoted by $V_3$. Then the following is true.

\begin{description}

\item[$(1)$]
 $G^{*} = Lf(G)/\mathcal{Q}_{\mathcal{F}}.$

\item[$(2)$] $G$ is hamiltonian if and only if $Lf(G)$ has a hamiltonian cycle $C$ such that $int(C) = F_1\cup F_3^{'}$ and $ext(C) = F_2\cup F_3^{''}$ where $F_3 = F_3^{'}\dot{\cup} F_3^{''}$.\\
\\

Statement $(2)$ is equivalent to

\item[$(3)$] $G^{*}$ has a non-separating  $A-$trail if and only if

\begin{itemize}

\item[$(i)$]
  $Lf(G)/\mathcal{Q}_{\mathcal{F}}$ has a quasi spanning tree of faces containing all of F1 and where $V_3^{'}$ is its set of proper vertices and $V_3^{''}$ is its set of quasi vertices; and

\item[$(ii)$]
 $Lf(G)/\mathcal{Q}_{\mathcal{F}}$ has a quasi spanning tree of faces containing all of $F2$ and where $V_3^{''}$ is its set of proper vertices and $V_3^{'}$ is its set of quasi vertices.

$(V_3^{'}$ and $V_3^{''}$ are the vertex sets in  $Lf(G)/\mathcal{Q}_{\mathcal{F}}$ corresponding to $F_3^{'}$ and $F_3^{''}$, respectively.$)$
\end{itemize}
\end{description}
\end{theorem}

\begin{proof}
By Definition~\ref{DEF:Leapfrog} and definition of the dual graph of a plane graph,  statement $(1)$ is true.

Assume $G$ has a hamiltonian cycle $C_0=e_1e_2\ldots e_n$ such that $e_i=v_iv_{i+1}$ for $i=1,\ldots,n-1$.
Let $e=v_iv_j\in E(G)$ be the edge  corresponding to $e^{'}\in E(C_6(v_i))\cap E(C_6(v_j))\subset E(Lf(G))$, for $1\le i\neq j\le n$ (see Definition~\ref{DEF:Leapfrog} $(ii)$
concerning $C_6(v_i)$).

Now we construct a hamiltonian cycle $C$ in $Lf(G)$ corresponding to $C_0$ as follows.
Begin with $C=e_1^{'}$. Consider the shortest path in $Lf(G)$ between  the endvertex of $e_1^{'}$ lying inside of $C_0$ and the endvertex of $e_2^{'}$ lying inside  of $C_0$, and add this path to $C$. Then add $e_2$ and add
the shortest path in $Lf(G)$ between  the endvertex of $e_2^{'}$  lying outside of $C_0$ and the endvertex of $e_3^{'}$ lying outside  of $C_0$, to the already constructed $C$. Add $e_3^{'}$ to $C$ and continue this algorithm such that at the $n-$th step you must add the  shortest path in $Lf(G)$ between  the endvertex of $e_n^{'}$  lying outside of $C_0$ and the endvertex of $e_1^{'}$ lying outside  of $C_0$ to the $C$.
It is easy to check that $C$ is a hamiltonian cycle in $Lf(G)$
such that $int(C) = F_1\cup F_3^{'}$ and $ext(C) = F_2\cup F_3^{''}$ where $F_3 = F_3^{'}\dot{\cup} F_3^{''}$ (cf.~\cite[pp.~$VI.109-VI.110$]{Fleischner}).

Conversely, it is straightforward to see that a hamiltonian cycle in $Lf(G)$ as described yields a hamiltonian cycle in $G$.

The remainder of the proof follows from the paragraph preceding the statement of the theorem.
\end{proof}

Theorem~\ref{TH:Herbert} puts hamiltonicity in $G$ in a qualitative perspective of the algorithmic complexity regarding quasi spanning trees of faces of a special type in
the reduced graph  of the leapfrog extension of $G$.
In fact, if $\mathcal{G}$ is a class of $3-$connected cubic planar bipartite graphs where hamiltonicity can be decided in polynomial time, then the same can be said regarding
special types of
quasi spanning trees of faces in the reduced graphs of the leapfrog extensions of  $\mathcal{G}$ (as stated in the theorem). For, given a hamiltonian cycle $C_0$ in $G\in \mathcal{G}$, a
non-separating  $A-$trail $L_{C_0}$ in $G^{*}$ can be found in polynomial time which in turn yields a quasi spanning tree of faces in $Lf(G)/\mathcal{Q}_{\mathcal{F}}$ as described in $(3)\ (i)$ and  $(3)\ (ii)$, respectively,
also in polynomial time. Compare this with Theorem~\ref{TH:Lf.NP-C} and Theorem~\ref{cor:4con-eulerian-triangulation}.

We now establish several NP-completeness results.

The question of whether a $3-$connected planar cubic graph $G_0$ has a hamiltonian
cycle is NP-complete, as shown by Garey et al.~\cite{Garey}.
Let $e =uv\in E(G_0)$. Then the question of whether $G_0$ has a hamiltonian
cycle traversing this specified edge $e$, is also
NP-complete. Let $G_0^{'}=G_0\setminus \{e\}$. Thus, the question
of whether $G_0^{'}$ has a hamiltonian path from $u$ to $v$ is also NP-complete.

\begin{theorem}~$(${\rm\cite[Theorem~4]{Feder}}$)$\label{TH:4}
Let $G$ be a $3-$connected cubic planar bipartite graph.
Let a $3-$face-coloring with color set $\{1,2,
3\}$ be given, and let $H$ be the reduced graph obtained by contracting the $1-$faces. Suppose that the $2-$faces
correspond in $H$ to quadrilaterals
and the $3-$faces correspond in $H$
to digons. Then the question of whether $H$ has a spanning tree of $2-$faces
is NP-complete.
\end{theorem}

\begin{proof}{ We want to construct $G$ and $H$ as stated  in the theorem. To this end,
let  $G_0^{'}$ be given as above and
assume $G_0^{'}$ is the plane graph resulting from a fixed imbedding of $G_0$  by edge deletion.
Let $H$ be the plane graph resulting by replacing every  edge of the radial graph $\mathcal{R}(G_0^{'})$ with a digon.
First color
the digons corresponding to edges in $\mathcal{R}(G_0^{'})$ with color $3$. The remaining faces of $H$  are quadrilaterals
$Q=xfx^{'}f^{'}x$  corresponding to edges $xx^{'}\in E(G_0^{'})$ that separate two faces $F$ and $F^{'}$ in $G_0^{'}$ corresponding to $f,f^{'}\in V(\mathcal{R}(G_0^{'}))$. Color these quadrilaterals with color $2$.
Let $G$  be the truncation of $H$; i.e., $G=Tr(H)$. Thus, $G$ is a $3-$connected cubic planar bipartite graph
whose $3-$face-coloring has color set $\{1,2,3\}$; the $1-$faces of $G$ correspond to the vertices of $H$.

\begin{claim}\label{clm:3}
A set $L$ of edges in $G_0^{'}$ forms a hamiltonian path from $u$ to $v$ in $G_0^{'}$ if and
only if the set $\mathcal{T}$ of $2-$faces $($quadrilaterals$)$ in $H$ corresponding to the edges in $E(G_0^{'})\setminus L$  is a spanning tree of $2-$faces in $H$.
\end{claim}

Suppose $L$ is a hamiltonian path from $u$ to $v$ in $G_0^{'}$. Let $L^{'}= E(G_0^{'})\setminus L$, and let $\mathcal{T}$ be the corresponding quadrilaterals in $H$. Note that for any two edges $g,h\in L^{'}$, there is a sequence of edges $g = e_1,e_2, \ldots,e_k = h$ in $L^{'}$ such that each pair of
edges $e_i, e_{i+1}$ belongs to a face boundary, $1\le i\le k-1$. Therefore the $2-$faces in $\mathcal{T}$ induce a connected subgraph of $H$.
Notice also that every vertex in $H$ belongs to some face in $\mathcal{T}$, since every vertex $x\in V(G_0^{'})$ is
incident to an edge in $L^{'}$, and every face $F$ in $G_0^{'}$ has at least one edge in $L^{'}$.

  Finally,
the $2-$faces in $\mathcal{T}$ do not contain a cycle. Suppose to the contrary,  we had a cycle $Q_1Q_2\ldots Q_kQ_1$ of
$2-$faces in $\mathcal{T}$.
 Since the number of $2-$faces
in $\mathcal{T}$ containing $x$ is equal to $\deg_{G^{'}}(x)-\deg_L(x)=1$, for every vertex $x\in V(G_0^{'})$, so $Q_i$ and $Q_{i+1}$ share a vertex $f\in V(H)$  corresponding to  a face $F\in \mathcal{F}(G_0^{'})$. Thus
$\{e_1, e_2, \ldots, e_k\}\subset L^{'}$, with $e_i$ corresponding to the face $Q_i$ in the cycle of $2-$faces in $\mathcal{T}$, separates
the graph $G_0^{'}$ into two components; so the hamiltonian path $L$ would have to contain at least
one of these edges $e_i\in L^{'}$, a contradiction. Therefore
$\mathcal{T}$ is a spanning
tree of $2-$faces for $H$.

Conversely, suppose $\mathcal{T}$ is a spanning tree of  $2-$faces for $H$. Let $L^{'}$ be the corresponding edges in $G_0^{'}$, and let $L=E(G_0^{'})\setminus L^{'}$.
Each vertex $x\in V(G_0^{'})$  belongs to exactly one $2-$face $Q=xfx^{'}f^{'}x$ in $\mathcal{T}$, since every other
$2-$face in $\mathcal{T}$ containing $x$ also contains either $f$ or $f^{'}$, and therefore these two $2-$faces share an edge
 and thus cannot both be in the spanning tree of faces $\mathcal{T}$. Therefore every vertex in $G_0^{'}$ is incident to exactly one edge in $L^{'}$, and so the two vertices $u$ and $v$ of degree $2$ in $G_0^{'}$
are incident to exactly one edge in $L$, while the remaining vertices  of degree $3$ in $G_0^{'}$ are
incident to exactly two edges in $L$. That is, $L$ induces a path joining $u$ and $v$ in $G_0^{'}$ plus a possibly empty set
 of cycles in $G_0^{'}$, such that the path and the cycles are disjoint and cover all of $V(G_0^{'})$. We show that $L$ cannot contain a cycle in $G_0^{'}$, and so $L$ is just a hamiltonian path joining $u$
to $v$.

Suppose
$L$ contains a cycle $C=e_1e_2\ldots e_ke_1$ in $G_0^{'}$. Let $F$ and $F^{'}$ be faces of $G_0^{'}$ inside and outside the
cycle of $C$, respectively, and let $f$ and $f^{'}$ be the vertices in $H$ corresponding to  $F$ and $F^{'}$, respectively.  Since $f$ and $f^{'}$ are vertices in the $\mathcal{T}$, there
is a unique sequence of $2-$faces $Q_1, Q_2,\ldots, Q_l$ in $\mathcal{T}$ such that $Q_1$ contains $f$, $Q_l$ contains $f^{'}$ and each
pair $Q_{i-1}$ , $Q_i$ share a vertex $f_i$ corresponding to
a face in $G_0^{'}$, for $2\le i<l$. In particular, if we denote $f_1 = f$ and $f_l = f^{'}$, then for
some pair $f_i$, $f_{i+1}$ we must have for the
corresponding  face $F_i$ in $G_0^{'}$ we must have $F_i\subseteq G_0^{'} \cap int(C)$ and for the corresponding  face $F_{i+1}$ in $G_0^{'}$ we must have $F_{i+1}\subseteq G_0^{'}\cap ext(C)$. This implies that the  $2-$face $Q_i$ in $\mathcal{T}$ corresponds to one of the edges $e_i$ in $L$ and not in $L^{'}$, a contradiction. This completes the proof of Claim~\ref{clm:3}.

 Therefore by Claim~\ref{clm:3}, $H$ has a
spanning tree of $2-$faces if and only if $G_0^{'}$ has a hamiltonian path from $u$ to $v$, and so the
question of whether $H$ has a spanning tree of $2-$faces is NP-complete.
}\end{proof}

We obtain two Corollaries from this result.

\begin{corollary}~$(${\rm\cite[Corollary~3]{Feder}}$)$\label{CR:3}
Let $G$ be a $3-$connected cubic planar bipartite graph
with a $3-$face-coloring with color set $\{1,2,
3\}$, and let $H$ be the reduced graph obtained by contracting the $1-$faces. Suppose all vertices of $H$ have degree $8$. Then the question
of whether $H$ has an $A-$trail is NP-complete.
\end{corollary}

\begin{proof}{ Consider the reduced graph $H$
in the statement of Theorem~\ref{TH:4} where  all $2-$faces in $H$ are quadrilaterals,
corresponding to octagons in $G$. If we contract these $2-$faces, we obtain an $8-$regular reduced graph
$H^{'}$. By Theorem~\ref{PR:3}, $H^{'}$ has an $A-$trail  if and only
if $H$ has a spanning tree of $2-$faces, and this problem is NP-complete by Theorem~\ref{TH:4}.
}\end{proof}

\begin{corollary}~$(${\rm\cite[Corollary~4]{Feder}}$)$\label{CR:4}
Let $G$ be a $3-$connected cubic planar bipartite graph
with a $3-$face-coloring with color set $\{1,2,
3\}$, and let $H_0$ be the reduced graph obtained by contracting the $1-$faces. Suppose that the $2-$faces in $H_0$ are octagons and digons and
the $3-$faces in $H_0$ are triangles. Then the question of whether $H_0$ has a spanning tree of faces is NP-complete.
\end{corollary}

\begin{proof}{  Let $H$ be the reduced graph of Theorem~\ref{TH:4}, with $2-$colored quadrilaterals and $3-$colored
digons. If $e$ and $f$ are the two parallel edges of a $3-$colored digon,
subdivide $e$ with  vertex $w$  and
subdivide $f$ with vertex $x$, with $w$ and $x$ joined by two parallel edges. The $3-$colored
digon splits thus into two $3-$color triangles and a $2-$colored digon, while the $2-$colored quadrilaterals become
$2-$colored octagons, in the new reduced graph $H_0$.

Suppose $H$ has a spanning tree of $2-$colored quadrilaterals $\mathcal{T}$. Select the corresponding $2-$colored
octagons in $H_0$. For a $3-$colored digon consisting of two edges $e$ and $f$ in $H$, if one of the two $2-$colored
quadrilaterals containing $e$ or $f$ is in $\mathcal{T}$, then select the
$2-$colored digon joining the middle vertices
$w$ and $x$; if neither of the two $2-$colored quadrilaterals containing $e$ or $f$ is in $\mathcal{T}$, then select one
of the two $3-$colored triangles containing $w$ and $x$. The $2-$colored and
$3-$colored faces in $H_0$ thus selected,
involving $2-$colored octagons, $2-$colored digons, and $3-$colored triangles, form a spanning tree of faces in $H_0$.

Conversely, suppose $H_0$ has a spanning tree of faces $\mathcal{T}_0$. Let $\mathcal{T}$ be the set of $2-$colored
quadrilaterals in $H$ such that the corresponding $2-$colored octagon is in $\mathcal{T}_0$. Note that for each
digon in $H$, only one of the corresponding two $3-$colored triangles and $2-$colored digon in $H_0$ can be in $\mathcal{T}_0$. Thus $\mathcal{T}$ is a spanning tree of $2-$colored faces.
Thus $H_0$ has a spanning tree of arbitrary faces if and only if $H$ has a spanning tree of
$2-$colored faces, and NP-completeness follows from Theorem~\ref{TH:4}.
}\end{proof}

\begin{lemma}\label{LE:G1}
If there exists a non-hamiltonian $3-$connected cubic planar bipartite graph, then there exists a hamiltonian $3-$connected cubic planar bipartite graph $G_1$
with a particular edge $e=uv$  such that $e\in E(C)$ for every hamiltonian cycle $C$ of $G_1$. Furthermore, if $e_1$ and $e_2$ are the two edges other than $e$ incident to $u$ in
$G_1$, then $G_1$ has a hamiltonian cycle $C_i$ traversing $e$ and $e_i$, for $i=1,2$.
\end{lemma}

\begin{proof}{
Suppose $G_0$ is a smallest counterexample to Barnette's Conjecture.

First we construct a hamiltonian $3-$connected cubic planar bipartite graph $G_1^{'}$
with a particular edge $e_0=u_0v$  such that $e_0\in E(C)$ for every hamiltonian cycle $C$ of $G_1^{'}$.

 Let $Q=wxyzw$ be a facial quadrilateral
 in $G_0$ and let $a_1$ be the third neighbour of $a$ in $G_0$, for $a\in \{w,x,y,z\}$.

Set $G_0^{'}=(G_0\setminus \{w,x,y,z\})\cup \{w_1x_1,y_1z_1\}$ and
$G_0^{''}=(G_0\setminus \{w,x,y,z\})\cup \{w_1z_1,x_1y_1\}$.
Both $G_0^{'}$ and $G_0^{''}$ are planar, cubic and bipartite.

Suppose that $G_0^{'}$ is   $3-$connected. By minimality of $G_0$, the graph $G_0^{'}$ has a hamiltonian
cycle. Furthermore, no hamiltonian cycle of $G_0^{'}$ goes through either the edge $w_1x_1$ or the edge $y_1z_1$, otherwise,
 we can extend this cycle to a hamiltonian cycle  in $G_0$, a contradiction.

  We have thus guaranteed that no
hamiltonian cycle in $G_1^{'}=G_0^{'}$ traverses a particular edge $w_1x_1$, and thus every hamiltonian cycle traverses an edge $e_0$
adjacent to $w_1x_1$, as desired.

Suppose instead that $G_0^{'}$ and $G_0^{''}$ are both  $2-$connected only. Then there are two edge cuts of size four $T_1$ and $T_2$ in $G_0$ such that $\{w_1x_1,y_1z_1\}\subset T_1$ and  $\{w_1z_1,x_1y_1\}\subset T_2$.

 Removing the vertices $w,x,y,z$ and the two edge cuts $T_1$ and $T_2$
separates $G_0$ into four components $R_1, R_2, R_3, R_4$, with the removed edges of $G_0$ including
an edge from $R_i$ to $R_{i+1}$, for $i=1,2,3$, and an edge from
$R_4$ to $R_1$, plus the four edges from the four $R_i$'s  adjacent to $Q$.

That is, each $R_i$ has three   edges whose
endvertices not in $R_i$ can be identified to a single vertex $r_i$ to construct $R_i^{'}$, since their
three endvertices in $R_i$ are at even distance from each other (in the $2-$vertex-coloring of $G_0$, the three
$2-$colored vertices of $R_i,\ 1\le i\le 4$, must have the same color;
otherwise, two copies of such $R_i$ could be used to construct a cubic bipartite graph having a bridge). Clearly, $R_i^{'}$
is $3-$connected, cubic, planar, and bipartite, for each $i=1,\ldots,4$.

By minimality of $G_0$ each such   $R_i^{'}$
 has a hamiltonian cycle, yet it is not the case that each of the
three choices of two edges going into each $R_i$ yields a hamiltonian cycle, since otherwise we
would obtain a hamiltonian cycle for $G_0$. Thus one of the three edges
incident to $r_i$ in $R_i^{'}$ must belong to every hamiltonian cycle, thus yielding a $3-$connected cubic
planar bipartite graph $G_1^{'}$ with an edge $e_0=u_0v$ that belongs to every hamiltonian cycle of $G_1^{'}$.

It remains to ensure that a hamiltonian cycle in $G_1$, which is forced to take $e =uv$,
can take either $e_1$ or $e_2$ out of $u$. Suppose instead that every hamiltonian cycle in $G_1^{'}$ is forced to
take $e_1^{'}=u_0v^{'}\in E(G_1^{'})$ as well.

Consider the $3-$connected cubic planar bipartite graph $Q_3$ of a cube with
$8$ vertices and $t\in V(Q_3)$ and $N_{Q_3}(t)=\{u,u^{'},u^{''}\}$.
Let $G_1=(G_1^{'}\setminus \{u_0\})\cup (Q_3\setminus \{t\})\cup\{uv,u^{'}v^{'},u^{''}v^{''}\}$, where
$e_2^{'}=u_0v^{''}\in E(G_1^{'})$.

It is easy to check that $G_1$ is hamiltonian and every hamiltonian cycle
going through $e=uv$; and furthermore, $G_1$ has a hamiltonian cycle $C_i$ going through $e$ and $e_i$, for $i=2,3$, where $e_1$ and $e_2$ are the two edges other than $e$ incident to $u$ in
$G_1$.
 }\end{proof}

\begin{theorem}~$(${\rm\cite[Theorem~5]{Feder}}$)$\label{TH:5}
Assume that  Barnette's Conjecture is false. Then the question of whether a $3-$connected cubic planar bipartite graph  has
a hamiltonian cycle, is NP-complete.
\end{theorem}

\begin{proof}{ Takanori et al.~\cite{Takanori} showed that the question of whether a $2-$connected cubic
planar bipartite graph $R$ has a hamiltonian cycle is NP-complete.

 If such an $R$ has a $2-$edge-cut
$\{e_1,e_2\}$ that separates $R$ into two components $R^{'}$ and $R^{''}$, then their endpoints in either side
are at odd distance (see the above argument),
 so we may instead join the two endpoints of $e_1$ and $e_2$ in $R^{'}$ and $R^{''}$, separately, and
ask whether $R^{'}$ and $R^{''}$ both contain a hamiltonian cycle containing the added edge joining
the endpoints of $e_1$ and $e_2$.

Repeating this decomposition process, we eventually reduce the
question of whether $R$ has a hamiltonian cycle to the question of whether various $R_i$'s each
contain a hamiltonian cycle going through certain prespecified edges, with each $R_i$ being
$3-$connected. Thus the question of whether a $3-$connected cubic planar bipartite graph $G^{'}$
has a hamiltonian cycle going through certain prespecified edges is NP-complete.

 Let a $3-$connected cubic planar bipartite graph $G^{'}$
 with certain prespecified edges $e^{'}_1,\ldots,e^{'}_k$ that a hamiltonian cycle must traverse, be given.
Assume that  $e_i^{'}=x_iy_{i,1}$ and $N_{G^{'}}(x_i)=\{y_{i,1},y_{i,2},y_{i,3}\}$, for $i=1,\ldots,k$.

Suppose that  Barnette's Conjecture is false. Then by
Lemma~\ref{LE:G1}, there exists a hamiltonian $3-$connected cubic planar bipartite graph $G_{i}$ with a vertex $u_i\in V(G_{i})$ and $N_{G_{i}}(u_i)=\{v_{i,1},v_{i,2},v_{i,3}\}$
 such that  every hamiltonian cycle
in $G_{i}$ traverses $e_i= u_iv_{i,1}\in E(G_i)$, $i=1\ldots,k$. Furthermore,   $G_i$ has a hamiltonian cycle traversing $e$ and $u_iv_{i,j}$, for $i=1,\ldots,k$ and $j=2,3$.

Construct a new $3-$connected cubic planar bipartite graph
$$G=\bigg(G^{'}\setminus \{x_1,\ldots,x_k\}\bigg)\cup
\bigg(\bigcup_{i=1}^k(G_i\setminus \{u_i\})\bigg) \cup \bigg(\bigcup_{i=1}^k\{v_{i,1}y_{i,1},v_{i,2}y_{i,2},v_{i,3}y_{i,3}\}\bigg).$$

Since every hamiltonian cycle in  $G_i$ traversing the edge $e_i$ and   $G_i$ has also a hamiltonian cycle traversing $e_i$ and $u_iv_{i,j}$, for $i=1,\ldots,k$ and $j=2,3$, the resulting graph $G$ has a hamiltonian cycle if and only if $G^{'}$
has a hamiltonian cycle traversing the edges $e_1^{'},\ldots,e_k^{'}$.
 Therefore, whether the resulting $3-$connected cubic
planar bipartite graph $G$ has a hamiltonian cycle, is NP-complete.
}\end{proof}


text:
{\bf Problem.} Carla rotated point $A$ 420 degrees clockwise about point $B$ and it landed at point $C$. Devon rotated the original point $A$ $x$ degrees counterclockwise about point $B$ and it also landed at point $C$. If $x<360$, what is the value of $x$?
{\bf Level.} Level 3
{\bf Type.} Geometry
{\bf Solution.} Carla's rotation was equivalent to one of $60^{\circ}$ clockwise. To get to the same point by going counter-clockwise, we have to go $360^{\circ}$ minus Carla's rotation, or $\boxed{300^{\circ}}$.

set_name: MATH


TITLE: Different ways of constructing the free group over a set.
QUESTION [18 upvotes]: This could be too broad if we're not careful. I'm sorry if it ends up that way.

Let's put together a list of different constructions of the free group $F_X$ over a given set $X$.

It seems to be one of those things a lot of people know about (and use implicitly) but whose constructions can be so tedious, it's hard to get hold of at first. The main problem, as Lee Mosher reminds us, seems to be associativity.
The Wikipedia page (linked to above) goes some way into listing some useful perspectives. I'm impressed by this intuitive summary from Wolfram:

A group is called a free group if no relation exists between its group generators other than the relationship between an element and its inverse required as one of the defining properties of a group.

But this is not exactly a construction nor is it strictly the free group over a set.
Here's a brief list of what I have so far:

An alternative approach to constructing the free group.

This starts with the "standard" construction  using finite strings over $\mathcal{X}=X\cup X'$ then asks for an opinion on quotienting by some equivalence relation.

Can a free group over a set be constructed this way (without equivalence classes of words)?

The free group is constructed as the left adjoint of the composition of certain forgetful functors. This one is interesting in that it goes via the category InvMon of monoids with involutions as objects and involution-preserving homomorphims as morphisms.
Martin Brandenburg also gives quite a concise one in the comments there, so I invite him to elaborate on that here :)

Magnus et al. in "Combinatorial Group Theory: Presentation of Groups in Terms of Generatorators and Relations" manage to define group presentations first of all in their opening chapter.
W. Ledermann in "Introduction to Group Theory" in $\S V$ gives a very standard construction by first defining finite words over $X$, then what it means to be a reduced word, then taking $F_X$ as the reduced words over $X$ under (reduced) concatenation.

The above list is not at all exhaustive (of what I know) and there's bound to be some overlap. Personally I would be interested to see explicit use of Universal Algebra, Semigroup Theory, and Category Theory. The reason for the latter should be clear from the above; as for the first two, see

Page 68 onwards of "A Course in
Universal Algebra" by Burris et al. and
Chapter 2 of "Nine Chapters on the Semigroup Art" by A.J. Cain.

Feel free to give more details on those already listed here.

REPLY [1 votes]: While reading about category theory in the book "Category Theory for Scientists," I started wondering about the free group construction after the part about adjunctions, in particular showing that the free monoid construction is left-adjoint to the forgetful functor.  I'm pretty sure that the free monoid construction can be pushed through to a free group constructor, here is what I came up with.
One imagination of the free monoid over a set $A$ the the List functor.  This maps $A$ to the monoid $([], ++, A+)$, where $[]$ is the empty list and identity, $++$ is concatenation, given on atoms by $[a] {++} [b] = [a,b]$, and $A+$ is the set of all lists of elements of $A$.  This is a standard construction, and will be denoted $L$.
To lift this to a group, the first hint for me is that, in a group, $(a*b)^{-1} = b^{-1} * a^{-1}$.  So in some sense our inverse elements for lists should be the reversed list.  But I'm hesitant to say that (for instance) $[a,b,b,c] = [a,b] {++} [b,a] = []$, this seems like an extreme condition for a free construction.  Let's first consider $L(A) \sqcup L(A)$, the disjoint union of $L(A)$ with itself.
For ease and abuse of notation we'll let $a_1$ represent an element of the left copy of $L(A)$ in $L(A) \sqcup L(A)$, and it will also represent $a_1$ as the injected value (in $A$).  If your mental "type-checker" is sufficiently tuned, this won't be ambiguous or confusing.  We'll assume similarly for $a_2, l_1, l_2$, favoring $a_i$ to represent atoms and $l$ to represent lists.  $\mathcal{G} = (G,*,\mathrm{id})$ will denote a group, and we'll probably not make a fuss about whether an element $e \in G$ or $e \in \mathcal{G}$.  We'll let $i$ be the injection $L(A) \rightarrow L(A) \sqcup L(A)$ when we need it.  Since we're lifting our monoid to a group, we will call the group operation $\overline{++}$.  Now it would be nice if
$i(l_i \overline{++} l_i') = l_i {++} l_i'$
(Remember, the elements in the LHS are members of $L(A) \sqcup L(A)$, while the ones in the RHS are elements of $L(A)$).  This would immediately imply that
$i([]_1 \overline{++} []_1) = []_1 {++} []_1 = [] = []_2 {++} []_2 = i([]_2 \overline{++} []_2)$
We don't yet know that $i([]_i \overline{++} []_j) = []$ when $i \neq j$. But, it seems reasonable that our desired $\overline{++}$ won't (shouldn't?) be able to tell apart an empty list from the left or right copy of $L(A)$, which is good because we only want one identity element anyways.  So we have the relation:
$[]_1 = []_2 = \mathrm{id}$
Here comes the "good idea."  Denote the "reverse" of a list $l$ as $l^r$  We now choose our inverse elements to finish our construction.  We'll pick:
$l_1^{-1} = l_2^r$
That is, the inverse of our lists on the left are the reversed lists on the right.  This, along with our desire for the injection to behave naturally on the group operation, subsumes our relation for the identity.  It also makes our "inverse formula" hold:
$([a]_1 \overline{++} [b]_1)^{-1} = [a,b]_1^{-1} = [b,a]_2 = [b]_2 \overline{++} [a]_2 = [b]_1^{-1} \overline{++} [a]_1^{-1}$
Now the part of showing that this $\bar{L}$ construction from $\mathbf{Set} \rightarrow \mathbf{Grp}$  Is left-adjoint to the forgetful functor.  This boils down to finding a unique homomorphism $\psi(f): \bar{L}(A) \rightarrow \mathcal{G}$ for every function $f: A \rightarrow G$.  The apparent way is:
$\psi(f)([]) = \mathrm{id}$
$\psi(f)([a_1]) = f(a_1)$
$\psi(f)([a_2]) = f(a_1)^{-1}$
$\psi(f)([a_i,...,z_i]) = f(a_i) * ... * f(z_i)$
We can end the discussion immediately by demonstrating a total $\phi: \mathrm{Homo}(\bar{L}(A), \mathcal{G}) \rightarrow \mathrm{Func}(A,G)$ such that
$\phi(\psi(f)) = f$
$\psi(\phi(h)) = h$
So say we have a homomorphism $h: \bar{L}(A) \rightarrow \mathcal{G}$, and we want a function $\phi(h): A \rightarrow G$.  One obvious choice is:
$\phi(h)(a) = h([a_1])$
(Remembering that we're not really distinguishing elements of $\mathcal{G}$ and $G$).  Now lets see what happens when we compose them...
$\phi(\psi(f))(a) = \psi(f)([a_1]) = f(a_1)$.
And the other way around:
$\psi(\phi(h))([a_1]) = \phi(h)(a_1) = h([a_1])$
$\psi(\phi(h))([a_2]) = \phi(h)(a_1)^{-1} = h([a_1])^{-1} = h([a_1]^{-1}) = h([a_2]) \quad \blacksquare$
I'm not sure if this gives a free-group as required by other definitions, but it seems like a straightforward construction using adjunctions.
Comments

This is my first time using category theory to try and do something interesting or useful, so if I f***ed something up please DO NOT be gentle.
If someone already did it better, I'd appreciate a reference.
There seems to be an ironic asymmetry to the argument (ironic because we're discussing groups).  I guess that the conclusion is that while an isomorphism demonstrating $\mathrm{Homo}(\bar{L}(A), \mathcal{G}) \cong \mathrm{Func}(A,G)$ is required, that isomorphism itself does not need to be unique...
A cute "intuitive" interpretation of this construction is to first generate the free monoid, then put it up to a mirror, squashing the identity element with the mirror.


TITLE: Vector field of functions equalling real numbers
QUESTION [1 upvotes]: We consider the set $\mathbb{N}^{\mathbb{R}}$ (i.e. all functions $f\colon\mathbb{N}\to\mathbb{R}$). I've been asked to prove that this forms a real vector space (that is, a vector space over $\mathbb{R}$). The most straightforward way of doing this seemed to me to just show that it satisfies the axioms.
I've done this (it wasn't particularly difficult or tricky, so I'm assuming I've done it correctly...), but had a moment of confusion when I looked back at what I'd written.
So, for example, to show that it satisfies one of the distributive laws, I wrote the following:
Let $\lambda\in\mathbb{R}$ and $f,g\in V$. Then
$$\lambda(f+g)
= \lambda(f(n)+g(n))
= \lambda f(n) + \lambda g(n)
= \lambda f + \lambda g$$
as required.
First of all, is this correct? It seems so trivial really.
But mainly, when I write the first equals sign, the $f$ on the left is a member of $V$, but the $f(n)$ is $f$ evaluated at $n$, so is a member of $\mathbb{R}$. That's how I justify the next step, as we know about how addition and multiplication distribute in $\mathbb{R}$.
Am I really justified in using an equals sign there though? How can something in a vector space that is not a real number equal something that is a real number? That is, $f\not=f(n)$, surely?
Sorry if this question seems like it isn't a question at all; I'm not sure if I'm just reading too much into it and getting confused.

REPLY [2 votes]: First: Yes, checking the axioms is not very enlightning and very trivial. But it is the only way to go.
Second: Equating $f$ with $f(n)$ is not justified, since, as you write $f$ is a function $\def\N{\mathbb N}\def\R{\mathbb R}\N\to \R$ and $f(n) \in \R$. But you can correct your line with small changes. First note, that you want to prove $\lambda(f+g) = \lambda f + \lambda g$ for $f,g \in \R^\N$. This is an equation for functions. Two functions $\N\to \R$ are equal if they are equal evaluated at every $n \in \N$, for $n \in \N$ we have
$$ \bigl(\lambda(f+g)\bigr)(n)= \lambda(f+g)(n) = \lambda \bigl(f(n) + g(n)\bigr) = \lambda f(n) + \lambda g(n) = (\lambda f + \lambda g)(n) $$
As $n\in \N$ was arbitrary, this implies, $\lambda (f+g) = \lambda f+ \lambda g$.


TITLE: How to find the time a pendulum reaches max angle given that its position is $3\cos(2t)+\sin(2t)$?
QUESTION [0 upvotes]: Kept the equation simple in the title, it's a bit more complicated
The position of the pendulum over time, $ y(t)$, is described by the equation $y=0.3cos(2.214t) + 0.135sin(2.214t) $
3 questions:

When does the pendulum first reach its maximum angle from vertical (hint: you might want to use an inverse trig in your answer)
what is the max angle?
how long after reaching its max angle until the pendulum reaches max deflection in the other direction (hint: where is the next critical point)?

So...I can guess that finding the time when velocity hits 0 would give me the maximum angle of the pendulum, but the equation has two trig functions so I don't know how to solve for $t$...
Since $ y=0.3\cos(2.214t) + 0.135(\sin(2.214t)$, we have
$y'(t) = 2.21 * 0.3 * -sin(2.214t) + 0.135 * 2.214 * cos(2.214t) = -0.663sin(2.214t) + 0.3cos(2.214)$
That's as far as I can get. I cant see any trig identities that could help me isolate t here. Even if I did have such an identity, I don't know how I'd answer part 3 which asks you to find the second time that the velocity = 0 (that makes no sense since solving the velocity equation for 0 should just give you a single t value)

REPLY [3 votes]: There are some formulas that can help combine sin and cos functions, I'm not going to prove this formula because there are plenty of proofs you can find online. Also I do not think the second question is doable without some more context, I'm assuming that y describes elevation, relative to an arbitrary standard, so it is impossible to find the length of the pendulum, and therefore the angle, but we can still find its maximum elevation.
$$asinx+bcosx = \sqrt{a^2+b^2}cos(x-\alpha);tan(\alpha)=\frac{a}{b}$$
Using this formula gives:
$$y=0.135sin(2.214t)+0.3cos(2.214t) = \sqrt{0.3^2+0.135^2}cos(2.214t-arctan(\frac{0.135}{0.3}))$$
$$y\approx0.3289cos(2.214t−0.4228)$$
Taking the derivative to get the velocity formula of:
$$y'=-0.3289\times2.214sin(2.214t−0.4228)$$
Now it should be apparent why there are multiple points where velocity (in the y direction) equates to zero (a sin wave has infinite zeros). Solving for t gives:
$$0=-0.3289\times2.214sin(2.214t−0.4228)$$
$$0=sin(2.214t−0.4228)$$
$$k\pi=2.214t−0.4228$$
$$t=\frac{k\pi+0.4228}{2.214}$$
This gives us when the y component of velocity equals zero, which includes both when the pendulum peaks and when it is at the bottom of its cycle. So to identify which is which, evaluate $y(t)$ for some integer values of $k$. Evaluating at $k=0$ gives you the first maximum, and $k=1$ gives the first minimum. Because increasing integer values of $k$ should give alternating maximums and minimums, one can conclude that even numbers of $k$ give maximums and odd values of $k$ give minimums. So to answer question one, we just need to evaluate $t$ at $k=0$, which gives:
$$t_0=\frac{0\times\pi+0.4228}{2.214}$$
$$t_0=\frac{0.4228}{2.214}=0.1910$$
The time it takes to get to the next peak should be $t_2-t_0$, so:
$$t_2-t_0=\frac{2\times\pi+0.4228}{2.214}-\frac{0\times\pi+0.4228}{2.214}$$
$$t_2-t_0=\frac{2\times\pi}{2.214}=2.838$$
*sorry in advance if anything is rounded incorrectly


TITLE: Find Z = max(X,Y) value of the distribution function at x = a.
QUESTION [0 upvotes]: I really strugger with this question.

Two archers with probabilities p = 0.52 and q = 0.58 independantly of
  each other shooting at the target. Both shot n=5 times. Let's say that first archer hitted X times while second archer hitter Y times. Find Z =
  max(X,Y) value of the distribution function at x = a(a=2.51).

I don't understand how to calculate Z = max(X,Y) part.
Any help appreciate, thanks.

REPLY [3 votes]: We can compute the distribution function of $Z$ using the fact that
$$
Z\leq z\iff X\leq z \; \text{and}\; Y\leq z
$$
In particular
$$
P(Z\leq z)=P(X\leq z) P(Y\leq z)
$$
by independence. We want
$$
P(Z\leq 2.51)=P(Z\leq 2)=P(X\leq 2) P(Y\leq 2)
$$
since $Z$ is integer valued. Since $X$ and $Y$ are binomially distributed the probabilities on the right hand side are easy to compute.


text:
\begin{document}

\title{Comply/Constrain Subtraction}

\author{Archishman Sravankumar}
\address{Euler Circle, Palo Alto, CA, 94306}
\email{archishman.sravankumar@gmail.com}

\date{\today}

\begin{abstract}
A comply/constrain game or a game with a Muller twist is a game where the next player is allowed to place constraints on
opponent's next move. We develop a closed form formula for
the Grundy value of the single-pile \noun{subtraction} game where the next
player may determine whether the previous player has to select a move
from the set of some first $k$ natural numbers or its complement. We
also investigate the periodicity of Grundy values when the set of legal
moves is from a set of finite arithmetic sequences.
\end{abstract}

\maketitle

\section{Introduction}

In this paper, we consider a variant of the classic game of \textsc{subtraction}. In an instance of \textsc{subtraction}, we choose some subset $S\subseteq\ZZ^+$ (where $\ZZ^+$ for us does not include 0) for once and for all. A move in the game \textsc{subtraction}$_S(n)$ consists of removing some $s\in S$ stones from a pile of size $n$, leaving $n-s\ge 0$ stones. The loser is the first player who cannot make a move.
If $s\in S$ is such that $s>n$, then we ignore $s$ because we cannot take more than $n$ stones from a pile of $n$ stones. Therefore, the set of legal moves can be simplified to $S\cap[n]$ where $[n]=\{1,2,3,4,\ldots, n\}$. We can represent a \noun{subtraction} position by its options. The position $\textsc{subtraction}_S(n)$ can be defined in terms of its options as
\begin{equation}
\textsc{subtraction}_S(n)=\{(n-s,S):s\in S\cap[n]\}.
\end{equation}
The values of impartial games like \noun{subtraction} can be calculated
using the minimal excludant (mex) rule.

In this paper, we consider a modification of the \noun{subtraction} game, known as a \emph{Muller twist}, which we call \noun{comply/constrain subtraction}. A comply/constrain game (or a game with a Muller twist) is one where
the next player (the player whose turn it is to move) may add a condition
about the moves the opponent may make along with the physical
move itself. In the game of \noun{subtraction}, we introduce a Muller twist by allowing the next player to decide whether the opponent should make a move from $S$ or its complement $\overline{S}=\mathbb{Z}^+\setminus S$. We denote a game of \noun{comply/constrain subtraction} with $n$ stones and subtraction set $S$ as $(n,S)$.

Comply/constrain games were first studied in a paper by St\u{a}nic\u{a} and Smith \cite{SS02}. A comply/constrain game, or a game with a Muller twist, is a variant of a traditional game where a player's physical move of game pieces is followed by a constraint chosen from a well-defined set of constraints. Their paper considered \noun{odd-or-even nim}, \noun{tall-or-short Wyt queens}, and \noun{Fibonacci-or-not nim}, all of which are traditional combinatorial games with a Muller twist. Other variants of nim with a Muller twist include \noun{blocking nim} which was studied in \cite{FHR03}. A paper by Horrocks and Trenton \cite{key-2} considers the game of \noun{subtraction} with a Muller twist. They analyze the periodicity of Grundy values when the subtraction set is of the form $S = \{a : a \equiv b \mod c\}$ for some $b$ and $c$.

Another related family of games that has recently attracted interest is the family of \emph{push-the-button} games; see~\cite{DHLP18}. In push-the-button games, there are two rulesets, say $A$ and $B$, played on the same heap set. The game initially starts with players moving according to the $A$-ruleset, but at any point, a player may ``push the button,'' and all subsequent moves are played according to the $B$-ruleset. Games with Muller twists are similar, except that the button can be pressed many times, thus switching back and forth between the rulesets.

This paper also fits in with recent interest in finding Grundy values of heap games. See for instance~\cite{LR16} for recent work on Grundy values of the game of \textsc{Fibonacci nim}, first studied in~\cite{Whinihan63}.

The options of the \noun{comply/constrain subtraction} $(n,S)$ are
\begin{equation}
(n,S)=\{(n-s,S):s\in S\cap[n]\}\cup\{(n-s,\overline{S}):s\in S\cap[n]\}.
\end{equation}
We will use $\mathcal{G}(n,S)$
for the Grundy value of the game $(n,S)$. That is, if $(n,S)=*x$,
then $\mathcal{G}(n,S)=x$.

In \S \ref{sec:consec}, we develop a closed form expression for the Grundy values of
games where $S=[k]$ or $S=\overline{[k]}$.
In \S \ref{sec:arith} we analyze the periodicity of Grundy values when $S=\{b+ic:\ 0\leq i\leq i_{\max},\frac{c+2}{2}\leq b<c\}$. These are similar to the games studied in \cite{key-2} except that we now cut off the arithmetic progression at some point.

\section*{Acknowledgments}

I would like to thank Simon Rubinstein-Salzedo for helpful discussions.

\section{Consecutive integers} \label{sec:consec}
Here we investigate the Grundy values of games $(n,S)$ where $S = [k]:=\{1,2,\ldots,k\}$. While these sets are also arithmetic progressions, they fail other parts of the hypothesis required for the analysis in \S \ref{sec:arith}. Therefore, we investigate them separately.

\begin{lem}\label{thm:1}
For $n>k$, we have $\mathcal{G}(n+1,\overline{[k]})\geq \mathcal{G}(n,\overline{[k]})$.
\end{lem}

\begin{proof}
From any $(n,\overline{[k]})$ a player can move to any or $(m,[k])$ or $(m,\overline{[k]})$ where $m<n-k$ since $\overline{[k]}$ contains all integers greater than or equal to $k + 1$. From $(n+1,\overline{[k]})$ a player can move to any $(m,[k])$ or $(m,\overline{[k]})$ where $m<n+1-k$. Therefore, all the options of $(n,\overline{[k]})$
are also options of $(n+1,\overline{[k]})$. Therefore, by the mex rule,
$\mathcal{G}(n+1,\overline{[k]})\geq\mathcal{G}(n,\overline{[k]})$.
\end{proof}
\begin{thm}
With notation as in the introduction, we have
\begin{equation}\label{eq:1a}
\mathcal{G}(n,[k])=\begin{cases}
n & 0\leq n\leq2k\\
n+1\mod(k+1) & 2k<n \footnotemark
\end{cases}
\end{equation}
and
\begin{equation}\label{eq:1b}
\mathcal{G}(n,\overline{[k]})=\begin{cases}
0 & 0\leq n<k\\
n-k & k\leq n\leq3k\\
2k+\lceil\frac{n-3k}{k+1}\rceil & 3k<n.
\end{cases}
\end{equation}
\end{thm}
\footnotetext{$a\mod b$ denotes the smallest non-negative integer that is congruent to $a \mod b$ rather than the entire residue class. }
\begin{proof}
We will approach this proof by alternating between proving base cases
for \eqref{eq:1a} and \eqref{eq:1b} and then finally using induction to prove the general
case.
\begin{casenv}
\item $\mathcal{G}(n,\overline{[k]})=0$ for $0\leq n<k$.

The set of legal moves is $\overline{[k]}\cap[n]=\varnothing$. Since there are
no legal moves, we have no options. Thus $\mathcal{G}(n,\overline{[k]})=0$
for $0\leq n<k$.
\item $\mathcal{G}(n,[k])=n$ for $0\leq n<k$.

The set of legal moves is $[k]\cap[n]=[n]$. Therefore
\begin{equation}\label{eq:3}
(n,[k])=\{(0,[k]),(0,\overline{[k]}),\ldots,(n-1,[k]),(n-1,\overline{[k]})\}.
\end{equation}
From Case (1) we know that $\mathcal{G}(i,\overline{[k]})=0$ for $0\leq i<k$.
Substituting this result into \eqref{eq:3} we get
\begin{equation}
(n,[k])=\{(0,[k]),*0,\ldots,(n-1,[k]),*0\}.
\end{equation}
We proceed with using induction.

\textbf{Base Case:} Since $(0,[k])$ has no options, $\mathcal{G}(0,[k])=0$.

\textbf{Inductive Step: }Assume that for some $n'<k$ that $\mathcal{G}(n,[k])=n$
for all $n<n'$.
Consider $\mathcal{G}(n'+1,[k])$:
\begin{align}
(n'+1,[k]) &= \{(0,[k]),(0,\overline{[k]}),\ldots,(n',[k]),(n',\overline{[k]})\}
\\
&= \{*0,*0,*1,*0,\ldots,*n',*0\}.
\end{align}
Thus $\mathcal{G}(n'+1,[k])=n'+1$ by the mex rule.
By induction, $\mathcal{G}(n,[k])=n$.
\item $\mathcal{G}(n,\overline{[k]})=n-k$ for $k\leq n<2k$.

The set of legal moves is $\overline{[k]}\cap[n]=\{k+1,k+2,\ldots, n\}$.
Therefore,
\begin{equation}\label{eq:6}
(n,[k])=\{(0,[k]),(0,\overline{[k]}),\ldots,(n-k-1,[k]),(n-k-1,\overline{[k]})\}.
\end{equation}
Since $n<2k$, we conclude that $n-k-1<k-1$. Therefore, we know how
to evaluate all the options of $(n,\overline{[k]})$. Substituting those
values into \eqref{eq:6} we get
\begin{equation}
(n,[k])=\{*0,*0,*1,*0,\ldots,*(n-k-1),*0\}.
\end{equation}
Using the mex rule we can evaluate this as $\mathcal{G}(n,[k])=n-k$.
\item $\mathcal{G}(n,[k])=n$ for $k\leq n<2k$.

The set of legal moves is $[k]\cap[n]=[k]$. Therefore
\begin{equation}
(n,[k])=\{(n-k,[k]),(n-k,\overline{[k]}),\ldots,(n-1,[k]),(n-1,\overline{[k]})\}.
\end{equation}
We will prove that $\mathcal{G}(n,[k])=n$ using induction.

\textbf{Base Case: }We know from Case (2) that $\mathcal{G}(n,[k])=n$
for $0\leq n<k$. This serves as our base case.

\textbf{Inductive Step: }Now assume for some for some $n'<2k$
that it is true that all $\mathcal{G}(n,[k])=n$ for all $n\leq n'$. Consider
$(n'+1,[k])$. We have
\begin{equation}
(n'+1,[k])=\{(n'+1-k,[k]),(n'+1-k,\overline{[k]}),\ldots,(n',[k]),(n',\overline{[k]})\}.
\end{equation}
To evaluate options of the form $(n,[k])$ we use our inductive assumption. The options are
\begin{equation}\label{eq:10}
(n'+1,[k])=\{*(n'+1-k),(n'+1-k,\overline{[k]}),\ldots,*n',(n',\overline{[k]})\}.
\end{equation}
To evaluate options of the form $\mathcal{G}(i,\overline{[k]})$ we use
our result from Cases (1) and (3). Since $n'+1<2k$, $n'+1-k<k$.
We apply the result from Case (1) to find that $(i,\overline{[k]})=*0$
where $0\leq i<k$. For $k<n<n'+1$, $\mathcal{G}(n,\overline{[k]})=n-k$, which
implies that the options are $*0,*1,\ldots,*(n'+1-k)$. Substituting these results
into \eqref{eq:10} we get
\begin{equation}
(n'+1,[k])=\{*(n'+1-k),*0,\ldots,*n',*(n'-k)\}.
\end{equation}
Using the mex rule here, we determine that $\mathcal{G}(n'+1,[k])=n'+1$. By
 induction $\mathcal{G}(n,[k])=n$ for $k\leq n\leq2k$.
\item $\mathcal{G}(n,\overline{[k]})=n-k$ for $2k\leq n \leq 3k$.

The set of legal moves is $\overline{[k]}\cap[n]=\{k+1,k+2,\ldots, n\}$.
Therefore the set of options are given by
\begin{equation}\label{eq:16}
(n,\overline{[k]})=\{(0,[k]),(0,\overline{[k]}),\ldots,(n-k-1,[k]),(n-k-1,\overline{[k]})\}.
\end{equation}
Since $n\leq3k$, we know that $n-k-1\leq2k-1$. Therefore, we know
how to evaluate the options of $(n,\overline{[k]})$. Substituting those
values into \eqref{eq:16} we get:
\begin{equation}
(n,\overline{[k]})=\{*0,*0,*1,*0,\ldots,*(n-k-1),*(n-2k-1)\}
\end{equation}
We use the mex rule to find that $\mathcal{G}(n,\overline{[k]})=n-k$.
\item $\mathcal{G}(n,[k])=n+1\mod(k+1)$ for $2k<n$.

The set of legal moves is $[k]\cap[n]=[k]$. Therefore the set of options is
\begin{equation}
(n,[k])=\{(n-k,[k]),(n-k,\overline{[k]}),\ldots,(n-1,[k]),(n-1,\overline{[k]})\}.
\end{equation}
Now we use induction.

\textbf{Base Cases:} Our base cases will be $(2k+1,[k]),\ldots,(3k+1,[k])$.
The game $(2k+1,[k])$ can be written in terms of its options as
\begin{equation}
(2k+1,[k])=\{(k+1,[k]),(k+1,\overline{[k]}),\ldots,(2k,[k]),(2k,\overline{[k]})\}.
\end{equation}
Substituting values from our previous casework, we may rewrite the above as
\begin{equation}
(2k+1,[k])=\{*(k+1),*(1),\ldots,*(2k),*(k)\}
\end{equation}
We use the mex rule to get $\mathcal{G}(2k+1,[k])=0=(2k+2)\mod(k+1)$.
The game $(2k+2,[k])$ can be written in terms of its options as
\begin{equation}
(2k+2,[k])=\{*(k+2),*(2),\ldots,*0,*(k+1)\}.
\end{equation}
We use the mex rule to get $\mathcal{G}(2k+2,[k])=1=(2k+3)\mod(k+1)$.
We use the same process to evaluate our other base cases. \\
\textbf{Inductive Step: } For some $n'>3k+1$
assume that $\mathcal{G}(n,[k])=(n+1)\mod(k+1)$ for all $2k<n\leq n'$.
We evaluate $\mathcal{G}(n'+1,[k])$ as
\begin{equation}\label{eq:21}
(n'+1,[k])=\{(n'-k+1,[k]),(n'-k+1,\overline{[k]}),\ldots,(n',[k]),(n',\overline{[k]})\}.
\end{equation}

Because of the mex rule and Lemma \ref{thm:1}, we may disregard all the
$(n,\overline{[k]})$ because $\mathcal{G}(n,\overline{[k]})\geq2k-1$, while
$*(k+1)$ is missing from the options list (i.e. $\mathcal{G}(n'+1,[k])\leq k+1$).
After removing such options, we can rewrite \eqref{eq:21} as
\begin{equation}
(n'+1,[k])=\{(n'-k+1,[k]),\ldots,(n',[k])\}.
\end{equation}
We use the the mex rule here to see that $\mathcal{G}(n'+1,[k])=\mathcal{G}(n'-k,[k])=n'-k+1\mod(k+1)=n'+2\mod(k+1)$.
By induction, $\mathcal{G}(n,[k])=n+1\mod(k+1)$
for $2k<n$.
\item $\mathcal{G}(n,\overline{[k]})=2k+\lceil\frac{n-3k}{k+1}\rceil$.

The set of legal moves is $\overline{[k]}\cap[n]=\{k+1,k+2,\ldots, n\}$.
Therefore the options are
\begin{equation}
(n,[k])=\{(0,[k]),(0,\overline{[k]}),\ldots,(n-k-1,[k]),(n-k-1,\overline{[k]})\}.
\end{equation}

\textbf{Base Cases:} The base cases are $(3k+1,\overline{[k]}),\ldots,(4k+1,\overline{[k]})$.We rewrite $(3k+1,\overline{[k]})$ in terms of its options as
\begin{equation}
(3k+1,\overline{[k]})=\{(0,[k]),(0,\overline{[k]}),\ldots,(2k,[k]),(2k,\overline{[k]})\}.
\end{equation}

From our previous casework and the mex rule, we conclude that
$\mathcal{G}(3k+1,\overline{[k]})=2k+1=2k+\lceil\frac{3k+1-3k}{k+1}\rceil$.
The other base cases have very similar options and also evaluate to
$2k+1$.

\textbf{Inductive Step: }Assume for some $n'>4k+1$ that \eqref{eq:1b} holds
true for $n'-k$ to $n'$ (inclusive).

From our previous casework, we notice that the options of the form
$(n,[k])$ take on every values in $\{*0,*1,\ldots,*2k\}$and no other
values. Consider $(m,\overline{[k]})$, an option of $(n,\overline{[k]})$. Because
stones need to be taken from $n$ to reach $m$, $m<n$. We know that $\mathcal{G}(n,[k])$
is monotonic from Lemma \ref{thm:1}. However, if $(m,\overline{[k]})$ is an option
of $(n,\overline{[k]})$, then $\mathcal{G}(n,\overline{[k]})\neq \mathcal{G}(m,\overline{[k]})$
by the mex rule. Since $\mathcal{G}(n,\overline{[k]})\geq \mathcal{G}(m,\overline{[k]})$
and $\mathcal{G}(n,\overline{[k]})\neq\mathcal{G}(m,\overline{[k]})$
(by the mex rule), we know that $\mathcal{G}(n,\overline{[k]})>\mathcal{G}(m,\overline{[k]})$.
Therefore, the value of $(n,\overline{[k]})$ is greater than the value
of any of its options. However, by the mex rule, it can only
be 1 greater than any of its options. Using this we will prove the
last part of the formula. We notice that $(n'-k,\overline{[k]})$ is the largest option
of $(n'+1,\overline{[k]})$. Therefore, $\mathcal{G}(n'+1,\overline{[k]})=\mathcal{G}(n'-k,\overline{[k]})+1=2k+\lceil\frac{n'-k-3k}{k+1}\rceil+1=2k+\lceil\frac{n'+1-3k}{k+1}\rceil$.
By induction \eqref{eq:1b} is true.
\end{casenv}
\end{proof}

\section{Arithmetic Progressions} \label{sec:arith}

Now we will proceed with investigating Grundy values for games where
$S=\{b+ic:\ 0\leq i\leq i_{\max},\ b,c,i,i_{\max}\in\mathbb{N},\frac{c+2}{2}\leq b<c\}$.
Here we extend the results in \cite{key-2} where subtraction sets
of the form $\{b+ic:\ 0\leq i,\ b,c,i\in\mathbb{N},\frac{c+2}{2}\leq b<c\}$
were considered by considering the behavior of Grundy values when the infinite arithmetic progression is chopped off to form a finite arithmetic progression. For any given subtraction set $S = \{b+ic:\ 0\leq i\leq i_{\max},\ b,c,i,i_{\max}\in\mathbb{N},\frac{c+2}{2}\leq b<c\}$
we call set $S'=\{b+ic:\ 0\leq i,\ b,c,i\in\mathbb{N}\}$. This helps
us use the results of \cite{key-2} in proving our results.

We observe that the sequence of values for $\mathcal{G}(n,S)$
is eventually periodic with period $p=2b+i_{\max}c$.
A list of Grundy values of $(n,S)$ and $(n,\overline{S})$ where $S = \{8, 21, 34, 47\}$ is given as an example in Figure~\ref{fig:grundytable}.

\begin{figure}
\includegraphics[clip,height=8in]{GrundyValueTableDrawing}

\caption{Labeled Grundy value table for $S=\{8,21,34,47\}$}
\label{fig:grundytable}
\end{figure}

\begin{lem} \label{thm:3.1}
If $n<p$, $\mathcal{G}(n,S)=\mathcal{G}(n,S')$ and $\mathcal{G}(n,\overline{S})=\mathcal{G}(n,\overline{S'})$.
\end{lem}

\begin{proof}
Since $p=2b+i_{\max}c<b+(i_{\max}+1)c$, the extra moves
in $S'$ do not affect the game, since the next player may not remove more than
$n$ stones from $(n,S)$ anyway. So the options of $(n,S)$ and
$(n,S')$ are identical when $n<p$. Therefore, $\mathcal{G}(n,S)=\mathcal{G}(n,S')$
and $\mathcal{G}(n,\overline{S})=\mathcal{G}(n,\overline{S'})$.
\end{proof}
\begin{lem}\label{thm:3.2}
If $n\geq2$, then $\mathcal{G}(n,S)\geq2$.
\end{lem}

\begin{proof}
This proof is virtually identical to the proof provided for a similar
result in \cite{key-2}. If $n-1\in\overline{S}$, then $(n,\overline{S})$
has the options $(1,S)$ and $(1,\overline{S})$. $\mathcal{G}(1,S)=0$
and $\mathcal{G}(1,S)=1$, therefore $\mathcal{G}(n,S)\geq2$. If
$n-1\in S$, $n\in\overline{S}$ and $n-b\in\overline{S}$. Since $(0,S)=*0$
and $(b,S)=*1$ are options of $(n,\overline{S})$, $\mathcal{G}(n,S)\geq2$.
\end{proof}
\begin{lem}\label{thm:3.3}
If $0\leq j\leq b-1$, $\mathcal{G}(p+j,S)=0$.
\end{lem}

\begin{proof}
The options of $(p+j,S)$ are of the form $(b+kc+j,S)$ and $(b+kc+j,\overline{S})$
where $0<k<i_{\max}$. Since in these options the number of stones
is less than $p$ we may evaluate them by using Lemma \ref{thm:3.1}. By using Lemma \ref{thm:3.1}, we see that they are all greater than $0$. Therefore,
$\mathcal{G}(p+j,S)=0$ by the mex rule.
\end{proof}

\begin{lem}\label{thm:3.4}
If $b\leq j\leq2b-1$, $\mathcal{G}(p+j,S)=1$.
\end{lem}

\begin{proof}
First, we consider games where $b\leq j\leq c$. $(2b+i_{\max}c+j,S)$
has options of the form $(b+kc+j,S)$ and $(b+kc+j,\overline{S})$. Since
$b\leq j\leq c$, these can be rewritten as $(2b+kc+x,S)$ and $(2b+kc+x,\overline{S})$
for some $0\leq x\leq c-b$. From the results in \cite{key-2} and
our result in Lemma \ref{thm:3.3}, these options all evaluate to 0. If $c\leq j\leq2b-1$,
we may rewrite $(b+kc+j,S)$ and $(b+kc+j,\overline{S})$ as $(b+(k+1)c+x,S)$
and $(b+(k+1)c+x,\overline{S})$ for $0\leq x\leq2b-c-1$. From Lemma \ref{thm:3.2}
we know $\mathcal{G}(b+(k+1)c+x,\overline{S})>2$. $\mathcal{G}(b+(k+1)c+x,S)>1$
from the results in \cite{key-2}. Therefore, $\mathcal{G}(p+j,S)=1$.
\end{proof}
\begin{lem}\label{thm:3.5}
If $0\leq i'\leq i_{\max}$ and $0\leq j\leq c-b$, then $\mathcal{G}(p+2b+i'c+j,S)=0$.
\end{lem}

\begin{proof}
Consider the games of form $(p+2b+i'c+j,S)$ where $0\leq j\leq c-b$.
These games have options of the form $(3b+(i_{\max}+i'-k)c+j,S)$ and
$(3b+(i_{\max}+i'-k)c+j,\overline{S})$ where $0\leq k\leq i_{\max}$. As we will see, the
options of the latter kind can be ignored since they are all greater
than or equal to 2. We consider the options described before. If $3b+(i_{\max}+i'-k)c+j\leq p$
then that option evaluates to $1$ from the results in \cite{key-2}.
If $3b+(i_{\max}+i'-k)c+j>p$, then we consider the option's options.
The option has an option of the form $(2b+i'c+j,S)=*0$ by results
described in \cite{key-2}. Therefore, the option itself cannot b.
$*0$. Additionally, we note that none of the options with $\overline{S}$ as the subtraction set have values equal to $0$ or $1$ by Lemma \ref{thm:3.2}.
Therefore, we use the mex rule to evaluate the game as $\mathcal{G}(p+2b+i'c+j,S)=0$.
\end{proof}
\begin{lem}\label{thm:3.6}
If $0\leq i'\leq i_{\max}$ and $0\leq j\leq c-b$, then $\mathcal{G}(p+i'c+3b+j,S)=1$.
\end{lem}

\begin{proof}
The options of $(p+i'c+3b+j,S)$ are of the form $(4b+kc+j,S)$. If
$4b+kc+j>p$ then we know from Lemma \ref{thm:3.5} that $(4b+kc+j,S)=*0$. Else,
we can rewrite $(4b+kc+j,S)$ as $(2b+(k+1)c+(2b-c)+j,S)$. From the
results in \cite{key-2}, we know that these options are either 0
or greater than 1 (they all have options that are $*1$). Therefore,
$\mathcal{G}(p+i'c+3b+j,S)=1$.
\end{proof}
\begin{lem}\label{thm:3.7}
If $0\leq i'\leq i_{\max}$ and $0\leq j\leq2b-c$, then $\mathcal{G}(p+i'c+3b+j,S)>1$.
\end{lem}

\begin{proof}
The options of $(p+i'c+3b+j,S)$ has options of the form $(p+2b-c+j,S)$.
This option evaluates to 0 by Lemma \ref{thm:3.3}. Other options of the form
$(p+2b+jc+j,S)$ evaluate to 1. Therefore, using the mex rule, all
of these games have Grundy values greater than 1.
\end{proof}
\begin{lem}\label{thm:3.8}
If $n\geq p$ then $\mathcal{G}(n,\overline{S}) > 2i_{\max}$.
\end{lem}

\begin{proof}
Since $n\geq p$, $(n,\overline{S})$ has all of $(0,\overline{S}),(0,\overline{S}),\ldots,(p-1,\overline{S})$
as options. From \cite{key-2} we know that the Grundy values of these
options contain every value from
$0$ to $\max(\{\mathcal{G}(0,\overline{S}),\allowbreak \mathcal{G}(0, \overline{S}), \ldots, G(p-1,\overline{S})\})$.
For $n<p$ we know that if $n=b+3+2br+i$ then $\mathcal{G}(n,\overline{S})=3+rb+i$.
From this we know: $2\times\mathcal{G}(n,\overline{S})=2br+6+2i$. Subtracting
$n$ from both sides, we have $2\times\mathcal{G}(n,\overline{S})-n=-b+3+i$.
By definition $0\leq i<2b$, so $-b+3\leq2\mathcal{G}(n,\overline{S)}-n\leq b+3$.
That is, $2\mathcal{G}(n,\overline{S})\geq n-b+3$ or $\mathcal{G}(n,\overline{S})\geq\frac{{n-b+3}}{2}$.
Since the max $n$ possible is $b+i_{\max}c$, we substitute that in
here and see that $\mathcal{G}(n,\overline{S})>\frac{i_{\max}c+3}{2}$. Since we assumed
$b\geq5\text{ and }c>b$, $c>5$. This implies $\frac{i_{\max}c+3}{2}>2i_{\max}$.
Therefore, $\mathcal{G}(n,\overline{S}) > 2i_{\max}$.
\end{proof}
\begin{thm}\label{thm:3.9}
$\mathcal{G}(n,S)$ is eventually periodic with period $p$.
\end{thm}

\begin{proof}
First, we notice that for $n>2p$, there are at most $2i_{\max}$ options
for the game $(n,S)$, therefore the maximum value of $(n,S)\leq2i_{\max}$.
All of these options have more than $p$ stones, therefore, the options
with set $\overline{S}$ are all greater than $2i_{\max}$ and therefore
do not affect the value of $(n,S)$. We will prove that given the
following statements for some $l$, they will also hold for $l+1$:
\begin{itemize}
\item if $0\leq j\leq b-1$, $\mathcal{G}(lp+j,S)=0$;
\item if $b\leq j\leq2b-1$, $\mathcal{G}(lp+j,S)=1$;
\item if $0\leq i'\leq i_{\max}$ and $0\leq j\leq c-b$, $\mathcal{G}(lp+2b+i'c+j,S)=0$;
\item if $0\leq i'\leq i_{\max}$ and $0\leq j\leq c-b$, then $\mathcal{G}(lp+i'c+3b+j,S)=1$;
\item i $0\leq i'\leq i_{\max}$ and $0\leq j\leq2b-c$, then $\mathcal{G}(lp+i'c+3b+j,S)>1$.
\end{itemize}
We first note that all of these conditions are met when $l=1$ because of Lemmas \ref{thm:3.1}--\ref{thm:3.8} which serve as the base case. Proving all of the above conditions is sufficient prove that
$\mathcal{G}(n,S)$ is periodic with period $p$ since the only group
of numbers which is not given a constant value ($0\leq i'\leq i_{\max}$
and $0\leq j\leq2b-c$, $\mathcal{G}(lp+i'c+3b+j,S)$) does not have
options of the form $\mathcal{G}((l-1)p+i'c+3b+j,S)$). All its options
from the previous block are given constant values by the conditions listed above, therefore they must be the same in each block. Now we proceed to prove that if the above conditions hold for some $l$, they hold for $l+1$.

First we consider games of the form $((l+1)p+j,S)$ where $0\leq j\leq b-1$. The options of $((l+1)p+j,S)$ are of the form $(lp+b+kc+j,S)$ and $(lp+b+kc+j,\overline{S})$
where $0<k<i_{\max}$. These options are all greater than 0 by our inductive hypothesis. Therefore, $\mathcal{G}((l+1)p+j,S)=0$
by the mex rule.

Next we consider games of the form $\mathcal{G}((l+1)p+j,S)=1$ where $b\leq j\leq2b-1$.
First, we consider games where $b\leq j\leq c$. The game $((l+1)p+2b+i_{\max}c+j,S)$
has options of the form $(lp+b+kc+j,S)$ and $(lp+b+kc+j,\overline{S})$.
Since $b\leq j\leq c$, these can be rewritten as $(lp+2b+kc+x,S)$
and $(lp+2b+kc+x,\overline{S})$ for some $0\leq x\leq c-b$. From
the conditions from the inductive hypothesis listed before, and our previous observation, these
options all evaluate to 0. If $c\leq j\leq2b-1$, we may rewrite $(lp+b+kc+j,S)$
and $(lp+b+kc+j,\overline{S})$ as $(lp+b+(k+1)c+x,S)$ and $(lp+b+(k+1)c+x,\overline{S})$
for $0\leq x\leq2b-c-1$. Therefore, $\mathcal{G}((l-1)p+b+(k+1)c+x,S)>1$ because of the conditions from the inductive hypothesis. Therefore, $((l+1)p+j,S)=1$.

Next we consider the games of form $((l+1)p+2b+i'c+j,S)$ where $0\leq j\leq c-b$.
These games have options of the form $lp+3b+(i_{\max}+i'-k)c+j,S)$
and $lp+3b+(i_{\max}+i'-k)c+j,\overline{S})$ where $0\leq k\leq i_{\max}$.
The options of the latter kind can be ignored since they are all greater
than or equal to $2 i_{\max}$. We consider the options described before. If
$lp+3b+(i_{\max}+i'-k)c+j\leq(l+1)p$ then that option evaluates to
$1$ from the results in \cite{key-2}. If $lp+3b+(i_{\max}+i'-k)c+j>(l+1)p$,
then we consider the option's options. The option has an option of
the form $(lp+2b+i'c+j,S)=*0$ by our assumptions. Therefore, the
option itself cannot be $*0$. Using the mex rule, we can see now
that $\mathcal{G}((l+1)p+2b+i'c+j,S)=0$.

The options of $((l+1)p+i'c+3b+j,S)$ are of the form $(lp+4b+kc+j,S)$.
If $lp+4b+kc+j>(l+1)p$ then we know from Lemma \ref{thm:3.5} that $(4b+kc+j+lp,S)=*0$.
Else, we can rewrite $(4b+kc+j+lp,S)$ as $(2b+(k+1)c+(2b-c)+j+lp,S)$.
From the assumptions, we know that these options are either 0 or greater
than 1 (they all have options that are $*1$). Therefore, n $\mathcal{G}((l+1)p+i'c+3b+j,S)=1$.

The options of $((l+1)p+i'c+3b+j,S)$ has options of the form $((l+1)p+2b-c+j,S)$.
This option evaluates to 0 by our assumptions. Other options of the
form $((l+1)p+2b+jc+j,S)$ evaluate to 1. Therefore, using the mex
rule, all of these games have Grundy values greater than 1.

All of the conditions specified in the inductive assumption are met. Therefore, by induction, the $\mathcal{G}(n,S)$ is periodic with period $p$.
\end{proof}

\bibliographystyle{alpha}
\bibliography{muller}

\end{document}

config: arxiv


TITLE: Is it true that for any integer $c_1, c_2$, we have $\gcd(n_1, n_2, n_3) = \gcd(n_1, n_2, c_1 n_1 + c_2 n_2 + n_3)$ for $n_1, n_2, n_3 \in \mathbb N$?
QUESTION [1 upvotes]: I got this task to check that if $n_1, n_2, n_3 \in \mathbb{N}$ the $\text{gcd}(n_1, n_2, n_3) =\text{gcd}(n_1, n_2, c_1n_1 + c_2n_2 + n_3)$ is valid for any $c_1, c_2 \in \mathbb{Z}$.
I started the idea saying that if:
$\text{gcd}(n_1, n_2, n_3) = k$, only if:
$k|n_1 \land k|n_2 \land k|n_3$ which means that:
$$
\left\{
\begin{array}{c}
n_1=ke \\
n_2=kf \\
n_3=kg
\end{array}
\right. \quad e, f, g\in \mathbb{N}
$$
Now $gcd(n_1, n_2, c_1n_1 + c_2n_2 + n_3) = k$ only if:
$$ c_1n_1 + c_2n_2 + n_3 = kr, \quad r \in \mathbb{Z}
$$
Substituting the values of $n_1, n_2, n_3$:
$$ k(c_1e + c_2f + g) = kr
$$
Which means that it is valid only if:$$c_1e + c_2f + g = r$$
But now I got stucked, I cannot say if this is valid for any $c_1, c_2$, could anyone help?

REPLY [1 votes]: $${\rm RHS} =\:\! \overbrace{((n_1,n_2),\,c_1n_1\!+\!c_2n_2\!+\!n_3) = ((n_1,n_2), \color{#c00}{n_3})}^{\textstyle\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \bmod d\!=\!\color{#0a0}{(n_1,n_2)}\!:\, c_1\color{#0a0}{n_1}\!+\!c_2\color{#0a0}{n_2}\!+\!\color{#c00}{n_3}\equiv \color{#c00}{n_3} } =\:\! \rm LHS\qquad$$
via gcd mod reduction: $\,(d,n,\ldots) = (d,\color{#c00}{\bar n},\ldots)\, $ if $\, n\equiv \color{#c00}{\bar n}\pmod{\!d},\,$ and  gcd associative law.
Similarly a gcd stays the same if we replace any argument by any integer congruent to it mod the gcd of (some of) the other arguments. That's essentially  the Euclidean algorithm reduction step.


text:
/-
Copyright (c) 2022 Bhavik Mehta All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Bhavik Mehta, Yaël Dillies
-/
import analysis.convex.cone
import analysis.convex.gauge

/-!
# Separation Hahn-Banach theorem

In this file we prove the geometric Hahn-Banach theorem. For any two disjoint convex sets, there
exists a continuous linear functional separating them, geometrically meaning that we can intercalate
a plane between them.

We provide many variations to stricten the result under more assumptions on the convex sets:
* `geometric_hahn_banach_open`: One set is open. Weak separation.
* `geometric_hahn_banach_open_point`, `geometric_hahn_banach_point_open`: One set is open, the
  other is a singleton. Weak separation.
* `geometric_hahn_banach_open_open`: Both sets are open. Semistrict separation.
* `geometric_hahn_banach_compact_closed`, `geometric_hahn_banach_closed_compact`: One set is closed,
  the other one is compact. Strict separation.
* `geometric_hahn_banach_point_closed`, `geometric_hahn_banach_closed_point`: One set is closed, the
  other one is a singleton. Strict separation.
* `geometric_hahn_banach_point_point`: Both sets are singletons. Strict separation.

## TODO

* Eidelheit's theorem
* `convex ℝ s → interior (closure s) ⊆ s`
-/

open set
open_locale pointwise

variables {𝕜 E : Type*}

/-- Given a set `s` which is a convex neighbourhood of `0` and a point `x₀` outside of it, there is
a continuous linear functional `f` separating `x₀` and `s`, in the sense that it sends `x₀` to 1 and
all of `s` to values strictly below `1`. -/
lemma separate_convex_open_set [seminormed_add_comm_group E] [normed_space ℝ E] {s : set E}
  (hs₀ : (0 : E) ∈ s) (hs₁ : convex ℝ s) (hs₂ : is_open s) {x₀ : E} (hx₀ : x₀ ∉ s) :
  ∃ f : E →L[ℝ] ℝ, f x₀ = 1 ∧ ∀ x ∈ s, f x < 1 :=
begin
  let f : linear_pmap ℝ E ℝ :=
    linear_pmap.mk_span_singleton x₀ 1 (ne_of_mem_of_not_mem hs₀ hx₀).symm,
  obtain ⟨r, hr, hrs⟩ := metric.mem_nhds_iff.1
    (filter.inter_mem (hs₂.mem_nhds hs₀) $ hs₂.neg.mem_nhds $ by rwa [mem_neg, neg_zero]),
  obtain ⟨φ, hφ₁, hφ₂⟩ := exists_extension_of_le_sublinear f (gauge s)
    (λ c hc, gauge_smul_of_nonneg hc.le)
    (gauge_add_le hs₁ $ absorbent_nhds_zero $ hs₂.mem_nhds hs₀) _,
  { refine ⟨φ.mk_continuous (r⁻¹) $ λ x, _, _, _⟩,
    { rw [real.norm_eq_abs, abs_le, neg_le, ←linear_map.map_neg],
      nth_rewrite 0 ←norm_neg x,
      suffices : ∀ x, φ x ≤ r⁻¹ * ∥x∥,
      { exact ⟨this _, this _⟩ },
      refine λ x, (hφ₂ _).trans _,
      rw [←div_eq_inv_mul, ←gauge_ball hr],
      exact gauge_mono (absorbent_ball_zero hr) (hrs.trans $ inter_subset_left _ _) x },
    { dsimp,
      rw [←submodule.coe_mk x₀ (submodule.mem_span_singleton_self _), hφ₁,
        linear_pmap.mk_span_singleton'_apply_self] },
    { exact λ x hx, (hφ₂ x).trans_lt (gauge_lt_one_of_mem_of_open hs₁ hs₀ hs₂ hx) } },
  rintro ⟨x, hx⟩,
  obtain ⟨y, rfl⟩ := submodule.mem_span_singleton.1 hx,
  rw linear_pmap.mk_span_singleton'_apply,
  simp only [mul_one, algebra.id.smul_eq_mul, submodule.coe_mk],
  obtain h | h := le_or_lt y 0,
  { exact h.trans (gauge_nonneg _) },
  { rw [gauge_smul_of_nonneg h.le, smul_eq_mul, le_mul_iff_one_le_right h],
    exact one_le_gauge_of_not_mem (hs₁.star_convex hs₀)
      ((absorbent_ball_zero hr).subset $ hrs.trans $ inter_subset_left _ _).absorbs hx₀,
    apply_instance }
end

variables [normed_add_comm_group E] [normed_space ℝ E] {s t : set E} {x y : E}

/-- A version of the **Hahn-Banach theorem**: given disjoint convex sets `s`, `t` where `s` is open,
there is a continuous linear functional which separates them. -/
theorem geometric_hahn_banach_open (hs₁ : convex ℝ s) (hs₂ : is_open s) (ht : convex ℝ t)
  (disj : disjoint s t) :
  ∃ (f : E →L[ℝ] ℝ) (u : ℝ), (∀ a ∈ s, f a < u) ∧ ∀ b ∈ t, u ≤ f b :=
begin
  obtain rfl | ⟨a₀, ha₀⟩ := s.eq_empty_or_nonempty,
  { exact ⟨0, 0, by simp, λ b hb, le_rfl⟩ },
  obtain rfl | ⟨b₀, hb₀⟩ := t.eq_empty_or_nonempty,
  { exact ⟨0, 1, λ a ha, zero_lt_one, by simp⟩ },
  let x₀ := b₀ - a₀,
  let C := x₀ +ᵥ (s - t),
  have : (0:E) ∈ C := ⟨a₀ - b₀, sub_mem_sub ha₀ hb₀,
    by rw [vadd_eq_add, sub_add_sub_cancel', sub_self]⟩,
  have : convex ℝ C := (hs₁.sub ht).vadd _,
  have : x₀ ∉ C,
  { intro hx₀,
    rw ←add_zero x₀ at hx₀,
    exact disj.zero_not_mem_sub_set (vadd_mem_vadd_set_iff.1 hx₀) },
  obtain ⟨f, hf₁, hf₂⟩ := separate_convex_open_set ‹0 ∈ C› ‹_› (hs₂.sub_right.vadd _) ‹x₀ ∉ C›,
  have : f b₀ = f a₀ + 1 := by simp [←hf₁],
  have forall_le : ∀ (a ∈ s) (b ∈ t), f a ≤ f b,
  { intros a ha b hb,
    have := hf₂ (x₀ + (a - b)) (vadd_mem_vadd_set $ sub_mem_sub ha hb),
    simp only [f.map_add, f.map_sub, hf₁] at this,
    linarith },
  refine ⟨f, Inf (f '' t), image_subset_iff.1 (_ : f '' s ⊆ Iio (Inf (f '' t))), λ b hb, _⟩,
  { rw ←interior_Iic,
    refine interior_maximal (image_subset_iff.2 $ λ a ha, _) (f.is_open_map_of_ne_zero _ _ hs₂),
    { exact le_cInf (nonempty.image _ ⟨_, hb₀⟩) (ball_image_of_ball $ forall_le _ ha) },
    { rintro rfl,
      simpa using hf₁ } },
  { exact cInf_le ⟨f a₀, ball_image_of_ball $ forall_le _ ha₀⟩ (mem_image_of_mem _ hb) }
end

theorem geometric_hahn_banach_open_point (hs₁ : convex ℝ s) (hs₂ : is_open s) (disj : x ∉ s) :
  ∃ f : E →L[ℝ] ℝ, ∀ a ∈ s, f a < f x :=
let ⟨f, s, hs, hx⟩ := geometric_hahn_banach_open hs₁ hs₂ (convex_singleton x)
  (disjoint_singleton_right.2 disj)
  in ⟨f, λ a ha, lt_of_lt_of_le (hs a ha) (hx x (mem_singleton _))⟩

theorem geometric_hahn_banach_point_open (ht₁ : convex ℝ t) (ht₂ : is_open t) (disj : x ∉ t) :
  ∃ f : E →L[ℝ] ℝ, ∀ b ∈ t, f x < f b :=
let ⟨f, hf⟩ := geometric_hahn_banach_open_point ht₁ ht₂ disj in ⟨-f, by simpa⟩

theorem geometric_hahn_banach_open_open (hs₁ : convex ℝ s) (hs₂ : is_open s) (ht₁ : convex ℝ t)
  (ht₃ : is_open t) (disj : disjoint s t) :
  ∃ (f : E →L[ℝ] ℝ) (u : ℝ), (∀ a ∈ s, f a < u) ∧ ∀ b ∈ t, u < f b :=
begin
  obtain (rfl | ⟨a₀, ha₀⟩) := s.eq_empty_or_nonempty,
  { exact ⟨0, -1, by simp, λ b hb, by norm_num⟩ },
  obtain (rfl | ⟨b₀, hb₀⟩) := t.eq_empty_or_nonempty,
  { exact ⟨0, 1, λ a ha, by norm_num, by simp⟩ },
  obtain ⟨f, s, hf₁, hf₂⟩ := geometric_hahn_banach_open hs₁ hs₂ ht₁ disj,
  have hf : is_open_map f,
  { refine f.is_open_map_of_ne_zero _,
    rintro rfl,
    exact (hf₁ _ ha₀).not_le (hf₂ _ hb₀) },
  refine ⟨f, s, hf₁, image_subset_iff.1 (_ : f '' t ⊆ Ioi s)⟩,
  rw ←interior_Ici,
  refine interior_maximal (image_subset_iff.2 hf₂) (f.is_open_map_of_ne_zero _ _ ht₃),
  rintro rfl,
  exact (hf₁ _ ha₀).not_le (hf₂ _ hb₀),
end

/-- A version of the **Hahn-Banach theorem**: given disjoint convex sets `s`, `t` where `s` is
compact and `t` is closed, there is a continuous linear functional which strongly separates them. -/
theorem geometric_hahn_banach_compact_closed (hs₁ : convex ℝ s) (hs₂ : is_compact s)
  (ht₁ : convex ℝ t) (ht₂ : is_closed t) (disj : disjoint s t) :
  ∃ (f : E →L[ℝ] ℝ) (u v : ℝ), (∀ a ∈ s, f a < u) ∧ u < v ∧ ∀ b ∈ t, v < f b :=
begin
  obtain rfl | hs := s.eq_empty_or_nonempty,
  { exact ⟨0, -2, -1, by simp, by norm_num, λ b hb, by norm_num⟩ },
  unfreezingI { obtain rfl | ht := t.eq_empty_or_nonempty },
  { exact ⟨0, 1, 2, λ a ha, by norm_num, by norm_num, by simp⟩ },
  obtain ⟨U, V, hU, hV, hU₁, hV₁, sU, tV, disj'⟩ := disj.exists_open_convexes hs₁ hs₂ ht₁ ht₂,
  obtain ⟨f, u, hf₁, hf₂⟩ := geometric_hahn_banach_open_open hU₁ hU hV₁ hV disj',
  obtain ⟨x, hx₁, hx₂⟩ := hs₂.exists_forall_ge hs f.continuous.continuous_on,
  have : f x < u := hf₁ x (sU hx₁),
  exact ⟨f, (f x + u)/2, u, λ a ha, by linarith [hx₂ a ha], by linarith, λ b hb, hf₂ b (tV hb)⟩,
end

/-- A version of the **Hahn-Banach theorem**: given disjoint convex sets `s`, `t` where `s` is
closed, and `t` is compact, there is a continuous linear functional which strongly separates them.
-/
theorem geometric_hahn_banach_closed_compact (hs₁ : convex ℝ s) (hs₂ : is_closed s)
  (ht₁ : convex ℝ t) (ht₂ : is_compact t) (disj : disjoint s t) :
  ∃ (f : E →L[ℝ] ℝ) (u v : ℝ), (∀ a ∈ s, f a < u) ∧ u < v ∧ ∀ b ∈ t, v < f b :=
let ⟨f, s, t, hs, st, ht⟩ := geometric_hahn_banach_compact_closed ht₁ ht₂ hs₁ hs₂ disj.symm in
⟨-f, -t, -s, by simpa using ht, by simpa using st, by simpa using hs⟩

theorem geometric_hahn_banach_point_closed (ht₁ : convex ℝ t) (ht₂ : is_closed t) (disj : x ∉ t) :
  ∃ (f : E →L[ℝ] ℝ) (u : ℝ), f x < u ∧ ∀ b ∈ t, u < f b :=
let ⟨f, u, v, ha, hst, hb⟩ := geometric_hahn_banach_compact_closed (convex_singleton x)
  is_compact_singleton ht₁ ht₂ (disjoint_singleton_left.2 disj)
  in ⟨f, v, hst.trans' $ ha x $ mem_singleton _, hb⟩

theorem geometric_hahn_banach_closed_point (hs₁ : convex ℝ s) (hs₂ : is_closed s) (disj : x ∉ s) :
  ∃ (f : E →L[ℝ] ℝ) (u : ℝ), (∀ a ∈ s, f a < u) ∧ u < f x :=
let ⟨f, s, t, ha, hst, hb⟩ := geometric_hahn_banach_closed_compact hs₁ hs₂ (convex_singleton x)
  is_compact_singleton (disjoint_singleton_right.2 disj)
  in ⟨f, s, ha, hst.trans $ hb x $ mem_singleton _⟩

/-- Special case of `normed_space.eq_iff_forall_dual_eq`. -/
theorem geometric_hahn_banach_point_point (hxy : x ≠ y) : ∃ (f : E →L[ℝ] ℝ), f x < f y :=
begin
  obtain ⟨f, s, t, hs, st, ht⟩ :=
    geometric_hahn_banach_compact_closed (convex_singleton x) is_compact_singleton
      (convex_singleton y) is_closed_singleton (disjoint_singleton.2 hxy),
  exact ⟨f, by linarith [hs x rfl, ht y rfl]⟩,
end

/-- A closed convex set is the intersection of the halfspaces containing it. -/
lemma Inter_halfspaces_eq (hs₁ : convex ℝ s) (hs₂ : is_closed s) :
  (⋂ (l : E →L[ℝ] ℝ), {x | ∃ y ∈ s, l x ≤ l y}) = s :=
begin
  rw set.Inter_set_of,
  refine set.subset.antisymm (λ x hx, _) (λ x hx l, ⟨x, hx, le_rfl⟩),
  by_contra,
  obtain ⟨l, s, hlA, hl⟩ := geometric_hahn_banach_closed_point hs₁ hs₂ h,
  obtain ⟨y, hy, hxy⟩ := hx l,
  exact ((hxy.trans_lt (hlA y hy)).trans hl).not_le le_rfl,
end

subset_name: curated


TITLE: $AB \neq 0$ but $BA=0$
QUESTION [10 upvotes]: Do there exists to matrices or objects such that $AB \neq 0$ but $BA=0$?
Another way to ask this question is if there exists objects or matrices $A$ and $B$ such that...
$[A,B]=AB$
where $[ \, , \, ]$ is the commutator $[A,B]=AB-BA.$
If such matrices do not exist, what does that imply about the algebra that the elements are in?

REPLY [4 votes]: As the other answer show: there are uncountably many pairs of matrices $(A,B)$ such that $AB = 0$ while $BA \neq 0$. If you think of square matrices as linear transformations then it is obvious why this should be so: in $AB$, we can think of the product as recording the image of each of the columns of $B$ under the linear transformation $A$, likewise with $BA$.
A nice question to ask is the following: Given a fixed matrix $A \in \text{Mat}_n\mathbb{R},$ what is the following:
$$\widetilde{A} := \{ X \in \text{Mat}_n\mathbb{R} : AX = 0 \ \wedge \ XA \neq 0\} \, ?$$
Clearly, if $X \in \widetilde{A}$ then $\lambda X \in \widetilde{A}$ for all $\lambda \neq 0.$ Interestingly, this space is not a vector space because the zero matrix $0 \notin \widetilde{A}$ and $X,Y \in \widetilde{A}$ does not imply that $X+Y \in \widetilde{A}.$


TITLE: Finding a formula $\phi_{n}$ such that every model satisfying $\phi_{n}$ has $n$ elements
QUESTION [0 upvotes]: I was trying to solve the following exercise.

Let $n$ be a natural number. Write down a formula $\phi_{n}$ such that every model that satisfies $\phi_{n}$ has exactly $n$-many elements.

Here was my solution. For all elements $v$, I wanted to express that it should be equal to one of $n$ variables, $v_1, \dots, v_n$. And those variables should be distinct. Thus, we get:
$$
\bigwedge_{1 \leq i, j \leq n, i \neq j} \neg\left(v_{i} \doteq v_{j}\right) \wedge \forall v \bigvee_{1 \leq i \leq n}\left(v \doteq v_{i}\right).
$$
This way, under an identification with a model, the $v_i$ would get sent to different elements of the domain. Thus for all elements in the domain, it is one of the $n$ elements that the $v_i$ get sent to. But, the solution is given:
$$
\exists v_{1}, v_{2}, \cdots, v_{n}\left(\bigwedge_{1 \leq i, j \leq n, i \neq j} \neg\left(v_{i} \doteq v_{j}\right) \wedge \forall v \bigvee_{1 \leq i \leq n}\left(v \doteq v_{i}\right)\right).
$$
I don't understand where I went wrong with my solution. Also, why is the $\exists v_{1}, v_{2}, \cdots, v_{n}$ needed?

REPLY [2 votes]: This depends on what it would mean for a formula with free variables to be satisfied in a model. The two options are already mentioned in the comments. If we have a formula $\phi(\bar{x})$, where $\bar{x}$ is the tuple of free variables appearing in $\phi$, then what does $M \models \phi(\bar{x})$ mean? I agree with Mees that this usually means $M \models \forall \bar{x} \phi(\bar{x})$. Mauro points out another piece of terminology, namely that "$\phi(\bar{x})$ is satisfiable in $M$" means that there is some $\bar{a} \in M$ such that $M \models \phi(\bar{a})$, or equivalently $M \models \exists \bar{x} \phi(\bar{x})$. It is best to be clear about what you mean precisely, and for that it is probably best to just talk about closed formulas (sentences).
The imprecision in your answer is in the bit "under an identification with a model". Does this mean that your formula holds if there are some values for $v_1, \ldots, v_n$ which make the formula true? Or if the formula is true for all values of $v_1, \ldots, v_n$? The former is hiding an existential quantification, the latter is hiding a universal quantification.
As for the formula you are asking about. The intuition is that the formula should express "there are at least $n$ elements, and every element $v$ should be one of those elements". The first half of that sentence is done by existential quantification ("there are") and saying that these elements are distinct ("at least $n$"). Then the second half you already got right.
Note that this sentence (for $n \geq 2$) would be false in any (nonempty) model if we would replace the existential quantifier by a universal quantifier.


TITLE: Hodge diamond of a Calabi-Yau fourfold
QUESTION [6 upvotes]: I am trying to compute the Hodge diamond of a Calabi-Yau fourfold which is a complete intersection inside of a projective bundle over a threefold base. I have computed the arithmetic genera $\chi_1$ and $\chi_2$ which give me two linear relations between the four independent Hodge numbers $h^{(1,1)}$, $h^{(1,2)}$, $h^{(1,3)}$ and $h^{(2,2)}$. So if I can compute two of them the arithmetic genera will give me the other two. Since my variety is a Calabi-Yau fourfold, $h^{(1,1)}$ is the second Betti number and $h^{(1,2)}$ is twice the third Betti number, so really all I need are the second and third Betti numbers to finish the calculation. As such, I wanted to use the Lefschetz hyperplane theorem to relate the cohomology of my fourfold to the cohomology of the ambient projective bundle, but it turns out that the divisors for which my fourfold is a complete intersection of are not ample (they are only relatively ample). So does anyone have any ideas on how to relate the cohomology of my variety to the cohomology of the projective bundle if the divisors for which my variety is a complete intersection of are only relatively ample?

REPLY [10 votes]: I encountered a similar problem a few years ago, but then in dimension 3. In that case a master student wanted to calculate the hodge diamond of a threefold which was a hypersurface  $W$ in a $P^2$-bundle over a del Pezzo surface. This threefold was birational to a singular hypersurface $Y$ in some weighted projective 4-space.
Now you can apply Lefschetz' hyperplane theorem for $Y$, but it only works for the lower cohomology groups, since Poincar\'e duality might fail. There are methods to calculate the higher cohomology groups if the singularities of $Y$ are nice enough.
Then you consider a factorization of the birational map $W\dashrightarrow Y$, calculate exceptional divisors etc, in order to figure out the difference between the Hodge numbers of $W$ and of $Y$.
In the end this turned out to be too hard for the student in question, so I worked out some of the details. This particular example is worked out at the end of the first version (on arXiv) of my paper with Klaus Hulek on MW-groups of elliptic threefolds. The referee considered this example superfluous, therefore we omitted this example in the later versions and the published version of this paper.


TITLE: Prove that Markov's inequality is not tight
QUESTION [0 upvotes]: For any fixed random variable $X\geq0$ with $EX\leq\infty$, $$\lim_{\lambda\rightarrow\infty}\frac{\lambda\mathbb{P}(X\geq\lambda)}{EX}=0$$

REPLY [2 votes]: Let $\lambda_n$ be any sequence diverging to $\infty$. Check the two assumptions of the Dominated Convergence Theorem :

$\lambda_n 1_{X \geq \lambda_n} \le X$, and this r.v. is integrable (independent of \lambda) given your assumption.
$\lambda_n 1_{X \geq \lambda_n}\to 0$ a.s. since $P(X<\infty)=1$.

to conclude that
$$\lambda_n P(X \geq \lambda_n)\to 0$$ (while being bounded by $E[X]$, which you already knew)