text:
\begin{document}

\maketitle
\noindent\footnotetext[1]{Department of Mathematics, Miami University {\tt debiasld@miamioh.edu}.}
\noindent\footnotetext[2]{Department of Mathematics, University of Illinois, Urbana-Champaign {\tt rak5@illinois.edu}.}

\begin{abstract}
For all positive integers $r\geq 3$ and $n$ such that $r^2-r$ divides $n$ and an affine plane of order $r$ exists, we construct an $r$-edge colored graph with minimum degree $(1-\frac{r-2}{r^2-r})n-2$ such that the largest monochromatic component has order less than $\frac{n}{r-1}$.  This generalizes an example of Guggiari and Scott and, independently, Rahimi for $r=3$ and thus disproves a conjecture of Gy\'arf\'as and S\'ark\"ozy for all integers $r\geq 3$ such that an affine plane of order $r$ exists.
\end{abstract}

\section{Introduction}

An \emph{affine plane of order $q$} is a $q$-uniform hypergraph on $q^2$ vertices (called points), with $q(q+1)$ edges (called lines) such that each pair of vertices is contained in exactly one edge.  It is well known that an affine plane of order $q$ exists whenever $q$ is a prime power (and it is unknown whether there exists an affine plane of non-prime power order).  Given an affine plane $\mathcal{G}$ of order $q$, there exists a $q+1$-coloring of the edges of $\mathcal{G}$ such that every color class (called a parallel class) consists of a collection of $q$ vertex disjoint edges of order $q$, every vertex is contained in exactly one edge of each color, and the union of the $q+1$ edges incident to a given vertex is all of $V(\mathcal{G})$.

Let $H=(\{x_1, \dots, x_t\},E)$ be a hypergraph which has a proper edge coloring with $r$ colors (that is, every color class induces a matching).  Let $\alpha = (\alpha_1, \dots, \alpha_t)\in \mathbb{R}^t$ be such that $\sum_{i=1}^t\alpha_i=1$ and $\alpha_i>0$ for all $i\in [t]$.  For a positive integer $n$, let $G$ be a graph on $n$ vertices obtained by replacing each $x_i\in V(H)$ with a set $X_i$ of order $\ceiling{\alpha_i n}$ or $\floor{\alpha_i n}$; for all $u\in X_i$, $v\in X_j$, let $uv$ be an edge of $G$ if and only if there exists $e\in E$ such that $\{x_i, x_j\}\subseteq e$, and color $uv$ using the color which appears on $e$ (if there are multiple such edges, choose a color arbitrarily from one such edge).  We call $G$ an $\alpha$-\emph{weighted blow-up} of $H$, and if $\alpha_i=\frac{1}{t}$ for all $i\in [t]$, we call $G$ a \emph{uniform blow-up} of $H$.

Given a graph $G$ and a positive integer $r$, let $\mc_r(G)$ be the largest integer $m$ such that in every $r$-edge-coloring of $G$, there exists a monochromatic component (i.e.\ a maximal connected subgraph) of order at least $m$.  For the rest of the paper, when we speak of an $r$-coloring of $G$, we mean an $r$-coloring of the edges of $G$.

Gy\'arf\'as \cite{Gy} proved $$\mc_r(K_n)\geq \frac{n}{r-1}$$ and this is best possible when $(r-1)^2$ divides $n$ and an affine plane of order $r-1$ exists.  To see this, let $K_n$ be a uniform blow-up of the affine plane of order $r-1$.  Since every pair of distinct points from the affine plane is contained in exactly one edge the $r$-coloring of $K_n$ is well defined, and since each line of the affine plane has order $r-1$ and there are $(r-1)^2$ points, the size of the largest monochromatic component in $K_n$ is $(r-1)\frac{n}{(r-1)^2}=\frac{n}{r-1}$.

Gy\'arf\'as and S\'ark\"ozy \cite{GyS} raised the following interesting question: for a graph $G$ on $n$ vertices, how large does the minimum degree of $G$ need to be so that $\mc_r(G)\geq\frac{n}{r-1}$?  As noted in \cite{GyS0}, the answer is $n-1$ for $r=2$ because there is a 2-coloring of any non-complete graph on $n$ vertices such that the largest monochromatic component has order at most $n-1$.  So it was perhaps surprising that for all $r\geq 3$, they showed there exists $\ep_r>0$ such that if $G$ is a graph on $n$ vertices with $n$ sufficiently large and $\delta(G)\geq(1-\ep_r)n$, then $\mc_r(G)\geq \frac{n}{r-1}$.  The bounds on $\ep_r$ given in \cite{GyS} were later improved in \cite{DKS} as follows: for $r=3$, $\delta(G)\geq 7n/8$ suffices and for $r\geq 4$, $\delta(G)\geq (1-\frac{1}{3072(r-1)^5})n$ suffices.

Gy\'arf\'as and S\'ark\"ozy \cite{GyS} also gave the following natural construction whenever an affine plane of order $r$ exists and $r^2$ divides $n$.  Repeat the construction given above, but instead of an affine plane of order $r-1$, take a uniform blow-up of an affine plane of order $r$ with one parallel class removed.  This gives an $r$-colored graph on $n$ vertices with minimum degree $(1-\frac{r-1}{r^2})n-1$ where the largest monochromatic component has order $\frac{n}{r}<\frac{n}{r-1}$.  They conjectured that the bound arising from this construction is tight.

\begin{conjecture}[Gy\'arf\'as, S\'ark\"ozy \cite{GyS}]\label{exGS}
Let $n$ and $r\geq 3$ be positive integers.  If $G$ is a graph on $n$ vertices such that $\delta(G) \geq (1-\frac{r-1}{r^2})n$, then $\mc_r(G)\geq \frac{n}{r-1}$.
\end{conjecture}

Recently, Guggiari and Scott, and independently Rahimi, disproved this conjecture for $r=3$. The combination of their results gives the best possible minimum degree condition.

\begin{theorem}[Guggiari, Scott \cite{GS}, Rahimi \cite{R}]\label{GuggiariScott}
Let $G$ be a graph on $n$ vertices.  If $\delta(G) \geq \frac{5}{6} n-1$, then $\mc_3(G)\geq \frac{n}{2}$. Moreover, for every $n$, there exists a graph $G$ on $n$ vertices with $\delta(G) = \ceiling{\frac{5}{6} n} - 2$ such that $\mc_3(G)<\frac{n}{2}$.
\end{theorem}

Note that the $3$-colorings of graphs with $\delta(G) = \ceiling{\frac{5}{6}n} -2$ given by Guggiari and Scott and Rahimi have largest monochromatic components of order just under $\frac{n}{2}$. This is in contrast to the example of Gy\'arf\'as and S\'ark\"ozy above, where the largest monochromatic components have order $\frac{n}{3}$.

The purpose of this note is to generalize the lower bound construction of Guggiari and Scott and Rahimi which disproves Conjecture \ref{exGS} whenever an affine plane of order $r$ exists.

\begin{theorem}\label{main_example}
Let $n$ and $r$ be integers such that $r\geq 3$ and $n\geq r(r-1)((r-1)(r-2)+1)$.  If $(r^2-r) \mid n$ and an affine plane of order $r$ exists, then there exists a graph $G$ on $n$ vertices with $$\delta(G) = \left(1-\frac{r-2}{r^2-r}\right)n-2=\left(1-\frac{r-1}{r^2}+\frac{1}{r^2(r-1)}\right)n-2$$ such that $\mc_r(G)< \frac{n}{r-1}$.
\end{theorem}

The construction is based on a blow-up of the following hypergraph $\mathcal{H}_r$ which is derived from an affine plane of order $r$.

\begin{definition}[$\mathcal{H}_r$]\label{H_r}
Let $r\geq 3$ such that an affine plane of order $r$ exists.  Let $\mathcal{G}_r=(V, \mathcal{L})$ be an affine plane of order $r$.  Let $\{L_1, \dots, L_{r+1}\}$ be the partition of $\mathcal{L}$ into parallel classes.  Label the vertices of $\mathcal{G}_r$ as $v_{i,j}$ with $i,j \in [r]$ so that $L_1=\{\{v_{i,1}, \dots, v_{i,r}\}: i\in [r]\}$ and $L_{r+1}=\{\{v_{1,i}, \dots, v_{r,i}\}: i\in [r]\}$
(in Figure \ref{H_rfigure}, $L_1$ is represented by the rows and $L_{r+1}$ by the columns).
Let $S=\{v_{r,i} : i\in [r-1]\} \cup \{v_{r-1,r}\}$.

Let $\mathcal{H}_r$ be the hypergraph obtained from $\mathcal{G}_r$ by deleting the lines from $L_{r+1}$ and the vertices of $S$ from each of the remaining edges; i.e.\ let $\mathcal{H}_r=(V\setminus S, E)$ where $E=\{e\setminus S: e\in \mathcal{L}\}$.
\end{definition}

\begin{figure}[ht]
\centering
\begin{tikzpicture}
\def\x{2.4};
\def\y{1};
\def\round{6pt}

\draw[rounded corners=\round,fill=gray] (-0.5*\x,-0.4*\y) -- ++(0,0.8*\y) -- ++(4.0*\x,0) -- ++(0.2*\x,1*\y) -- ++(0.6*\x,0) -- ++(0,-0.8*\y) -- ++(-0.6*\x,-0.0*\y) -- ++(-0.2*\x,-1.0\y) -- cycle;
\draw (4.5*\x,1*\y) node{$S$};

\draw (0*\x,0*\y) node{$v_{r,1}$};
\draw (1*\x,0*\y) node{$v_{r,2}$};
\draw (2*\x,0*\y) node{$\cdots$};
\draw (3*\x,0*\y) node{$v_{r,r-1}$};
\draw (4*\x,0*\y) node{$v_{r,r}$};

\draw (0*\x,1*\y) node{$v_{r-1,1}$};
\draw (1*\x,1*\y) node{$v_{r-1,2}$};
\draw (2*\x,1*\y) node{$\cdots$};
\draw (3*\x,1*\y) node{$v_{r-1,r-1}$};
\draw (4*\x,1*\y) node{$v_{r-1,r}$};

\draw (0*\x,2*\y) node{$v_{r-2,1}$};
\draw (1*\x,2*\y) node{$v_{r-2,2}$};
\draw (2*\x,2*\y) node{$\cdots$};
\draw (3*\x,2*\y) node{$v_{r-2,r-1}$};
\draw (4*\x,2*\y) node{$v_{r-2,r}$};

\draw (0*\x,3*\y) node{$v_{r-3,1}$};
\draw (1*\x,3*\y) node{$v_{r-3,2}$};
\draw (2*\x,3*\y) node{$\cdots$};
\draw (3*\x,3*\y) node{$v_{r-3,r-1}$};
\draw (4*\x,3*\y) node{$v_{r-3,r}$};

\draw (0*\x,4*\y) node{$\vdots$};
\draw (1*\x,4*\y) node{$\vdots$};
\draw (2*\x,4*\y) node{$\ddots$};
\draw (3*\x,4*\y) node{$\vdots$};
\draw (4*\x,4*\y) node{$\vdots$};

\draw (0*\x,5*\y) node{$v_{1,1}$};
\draw (1*\x,5*\y) node{$v_{1,2}$};
\draw (2*\x,5*\y) node{$\cdots$};
\draw (3*\x,5*\y) node{$v_{1,{r-1}}$};
\draw (4*\x,5*\y) node{$v_{1,r}$};

\end{tikzpicture}
\caption{The hypergraph $\mathcal{H}_r$.}\label{H_rfigure}
\end{figure}

Given a hypergraph $H=(V,E)$, the \emph{rank} of $H$, denoted $r(H)$, is $\max\{|e|: e\in E\}$ and the \emph{proportional rank} of $H$ is $\frac{r(H)}{|V|}$.  The \emph{edge chromatic number} of $H$ is the minimum number of colors needed to color the edges of $H$ so that each color class forms a matching. Given a vertex $v\in V$, let $N[v]=\{u: \exists e\in E, \{u,v\}\subseteq e\}$; in other words, $N[v]$ is the set of all vertices (including $v$) which are contained in an edge with $v$. Let $\delta^*(H)=\min\{|N[v]|: v\in V\}$.

Note the following properties of $\mathcal{H}_r=(V,E)$:
\begin{enumerate}[label={(P\arabic*)}]
\item \label{itm:P1} the edge chromatic number of $\mathcal{H}_r$ is $r$,
\item \label{itm:P2} the proportional rank of $\mathcal{H}_r$ is $\frac{r}{r^2-r}=\frac{1}{r-1}$,
\item \label{itm:P3} $\delta^*(\mathcal{H}_r)=|V|-(r-2)=(1-\frac{r-2}{r^2-r})|V|$.
\end{enumerate}

Roughly speaking, we prove Theorem \ref{main_example} by taking a uniform blow-up of $\mathcal{H}_r$ (which has monochromatic components of order $\frac{n}{r-1}$) and then slightly  ``perturbing" the sizes of the blown-up sets so that all the monochromatic components have order less than $\frac{n}{r-1}$.  This raises the more general question of when such a perturbation is possible, which we address in Section \ref{sec:perturb}.

As is elaborated in Section \ref{sec:rough}, the choice of vertices $S$ to delete in the definition of $\mathcal{H}_r$ is to ensure that a uniform blow-up of $\mathcal{H}_r$ is ``perturbable.'' As an example of a hypergraph which is not ``perturbable,'' let $\mathcal{H}_3'=(V,E)$ be obtained from an affine plane of order 3, by deleting one parallel class and deleting the vertices from one of the remaining edges (say $v_{3,1}, v_{3,2}, v_{3,3}$ as in Figure \ref{H_rfigure}).  The edge chromatic number of $\mathcal{H}_3'$ is 3, the proportional rank is $1/2$, and $\delta^*(\mathcal{H}_3')=5=(1-\frac{1}{6})|V|$.  By taking a uniform blow-up of $\mathcal{H}_3'$ we obtain a 3-colored graph $G$ with $\delta(G)= \frac{5n}{6}-1$, and every monochromatic component has order at most $n/2$.  However, no matter how we change the sizes of the blown-up sets, one of the monochromatic components will have order at least $n/2$.

\section{Perturbable hypergraphs}\label{sec:perturb}

It is possible to skip directly to Section \ref{skipto} to see the proof of Theorem \ref{main_example}; however, to understand where the construction comes from we need to take a slight detour.

The \emph{standard simplex} of $\mathbb{R}^n$ is the set of vectors $(w_1, \dots, w_n)$ such that $w_i\geq 0$ for all $i\in [n]$ and $\sum_{i=1}^nw_i=1$.  A \emph{weight assignment} on a hypergraph $H=(V,E)$ where $V=\{v_1, \dots, v_n\}$ is a function $w:V\to \mathbb{R}$ such that $(w(v_1), \dots, w(v_n))$ is in the standard simplex of $\mathbb{R}^n$. For all $S\subseteq V$ let the weight of $S$, denoted $w(S)$, be $\sum_{v\in S}w(v)$.   We say that $w:V\to \mathbb{R}$ given by $w(v)=\frac{1}{|V|}$ for all $v\in V$ is the \emph{uniform} weight assignment.

\begin{definition}[Perturbation, perturbable]
A \emph{perturbation} on a hypergraph $H = (V,E)$ is a function $p:V\to\mathbb{R}$ such that $\sum_{i=1}^n p(v_i) = 0$ and for all $e \in E$, $p(e) = \sum_{v\in e} p(v) < 0$. We say $H$ is \emph{perturbable} if a perturbation on $H$ exists.
\end{definition}

Observe that if $w$ is a positive weight assignment on $H$ (meaning $w(v) > 0$ for all $v \in V$) and $p$ is a perturbation on $H$, then $w+\ep p$ is also a weight assignment on $H$ for sufficiently small $\ep>0$ (say $\ep < \min \left\{\left|\frac{w(v)}{p(v)}\right|: v\in V, p(v)\neq 0\right\}$). Since $p(e) < 0$ for every $e \in E$, the weight assignment $w+\ep p$ is strictly smaller than $w$ on every edge of $H$. Thus, if a perturbation on $H$ exists, then we can alter any weight assignment by at most $\ep$ at each vertex (for $\ep$ sufficiently small) and \emph{strictly} decrease the weights on the edges.

Theorem \ref{perturbable} gives an equivalent condition for the existence of a perturbation, but first we must recall the following definitions. Given a hypergraph $H=(V,E)$, a \emph{fractional matching} is a function $m:E\to [0,1]$ such that for all $v\in V$, $\sum_{e\ni v}m(e)\leq 1$, and a \emph{fractional vertex cover} is a function $t:V\to [0,1]$ such that for all $e\in E$, $\sum_{v\in e}t(v)\geq 1$. A fractional matching is called \emph{perfect} if we have equality for all $v\in V$. We let
\[
\nu^*(H)=\max\left\{\sum_{e\in E}m(e): m \text{ is a fractional matching on } H\right\}
\]
and
\[
\tau^*(H)=\min\left\{\sum_{v\in V}t(v): t \text{ is a fractional vertex cover on } H\right\}.
\]
It is well known consequence of the duality theorem in linear programming that $\tau^*(H)=\nu^*(H)$ for all hypergraphs.  When it is clear from context we just write $\tau^*$ and $\nu^*$ for $\tau^*(H)$ and $\nu^*(H)$ respectively. Note that if $H$ is $k$-uniform and has a perfect fractional matching, then $\nu^*(H) = \frac{n}{k}$.

\begin{theorem}\label{perturbable}
Let $H=(V,E)$ be a hypergraph.  $H$ is perturbable if and only if $H$ does not have a perfect fractional matching.
\end{theorem}

\begin{proof}
Let $n:=|V|$ and $e:=|E|$ and let $A$ be the $n$-by-$e$ incidence matrix of $H$ (with rows indexed by vertices and columns by edges).  Let $\mathbf{1}$ be the $n$-dimensional vector of all 1's.  Note that in this language, a perfect fractional matching $m$ is a solution to the system $Am = \mathbf{1}$, $m \geq 0$, and a perturbation $p$ is a solution to the system $A^T p < 0$, $\mathbf{1}^T p = 0$.

Recall Farkas' Lemma (see \cite{LP}), which states for a $n$-by-$e$ matrix $A$ and $n$-dimensional vector $b$, there is no $m\geq 0$ such that $Am = b$ if and only if there exists $w$ such that $A^T w \leq 0$ and $b^T w > 0$.

We claim that for the given $A$, the solvability of $A^T w \leq 0$, $\mathbf{1}^T w > 0$ is equivalent to the solvability of $A^T p < 0$, $\mathbf{1}^T p = 0$. So by Farkas' lemma, the result will follow by establishing this claim.

First suppose there exists $w$ such that $A^T w \leq 0$ and $\mathbf{1}^T w > 0$. Letting $p = w - \frac{\mathbf{1}^Tw}{n}\mathbf{1}$, we have $\mathbf{1}^T p = 0$ and $p < w$.  Since $A$ has only nonnegative entries, and it has at least one positive entry in each column, we have $A^T p < A^T w \leq 0$, so $p$ is a perturbation for $H$.

For the other direction, suppose there exists $p$ such that $A^T p < 0$ and $\mathbf{1}^T p = 0$. Let $\alpha>0$ be the absolute value of the largest entry of $A^T p$ (smallest in absolute value), and let $w = p + \frac{\alpha}{n}\mathbf{1}$. Then $\mathbf{1}^T w=\alpha > 0$ and the largest entry of $A^T w=A^Tp+\frac{\alpha}{n} A^T \mathbf{1}$ is $-\alpha + \frac{\alpha}{n} n \leq 0$, since the largest entry of $A^T \mathbf{1}$ is the rank of $H$ which is at most $n$.
\end{proof}

\section{When an affine plane of order $r$ exists}\label{sec:main}

Given a hypergraph $H=(V,E)$ and a weight assignment $w$, the \emph{top-level} of $H$, denoted $\overline{H}$, is the hypergraph $(V,E')$ where $E'\subseteq E$ is the set of edges of maximum weight.

\subsection{Rough construction}\label{sec:rough}

Let $\mathcal{H}_r=(V,E)$ be the hypergraph from Definition \ref{H_r}.  We first show that under the uniform weight assignment, the top-level of $\mathcal{H}_r=(V,E)$ is perturbable. This together with properties \ref{itm:P1}, \ref{itm:P2}, and \ref{itm:P3}, imply that for all sufficiently large $n$ we can use $\mathcal{H}_r$ to define a graph $G$ on $n$ vertices with $\delta(G)\geq (1-\frac{r-2}{r^2-r})n-O(1)$ and $\mc_r(G)<\frac{n}{r-1}$.

\begin{observation}\label{rough}
Let $r\geq 3$ be an integer such that an affine plane of order $r$ exists.  Under the uniform weight assignment, the top-level of $\mathcal{H}_r=(V,E)$ is perturbable.
\end{observation}

\begin{proof}

Given the uniform weight assignment on $\mathcal{H}_r$, let $\overline{\mathcal{H}_r}=(V,E')$ be the top-level of $\mathcal{H}_r$ (which is just the edges of order $r$ in this case).

Let $t:V\to \mathbb{R}$ given by $t(v)=\frac{1}{r-1}$ if $v\in \{v_{r,r}\}\cup \{v_{i,j}: i\in [r-2], j\in [r-1]\}$ and $t(v)=0$ otherwise (see Figure \ref{roughfigure}).  We first claim that $t$ is a fractional vertex cover of $\overline{\mathcal{H}_r}$.  Indeed, every edge of $E'$ either comes from $L_1$ or contains $v_{r,r}$, and consequently intersects $\{v_{r-1,i}: i\in [r-1]\}\cup \{v_{i,r}: i\in [r-2]\}$ in at most one vertex.  So we have
\[
\nu^*=\tau^*\leq \sum_{v\in V}t(v)=(r-1)(r-2)\frac{1}{r-1}+\frac{1}{r-1}=r-2+\frac{1}{r-1}<r-1=\frac{|V|}{r},
\]
and thus $\overline{\mathcal{H}_r}$ does not have a perfect fractional matching. By Theorem \ref{perturbable}, $\overline{\mathcal{H}_r}$ is perturbable.
\end{proof}

\begin{figure}[ht]
\centering
\begin{tikzpicture}
\def\x{2.4};
\def\y{1};
\def\round{6pt}

\draw[rounded corners=\round,fill=gray] (-0.5*\x,-0.4*\y) -- ++(0,0.8*\y) -- ++(4.0*\x,0) -- ++(0.2*\x,1*\y) -- ++(0.6*\x,0) -- ++(0,-0.8*\y) -- ++(-0.6*\x,-0.0*\y) -- ++(-0.2*\x,-1.0\y) -- cycle;
\draw (4.5*\x,1*\y) node{$S$};

\draw (0*\x,0*\y) node{\textbullet};
\draw (1*\x,0*\y) node{\textbullet};
\draw (2*\x,0*\y) node{$\cdots$};
\draw (3*\x,0*\y) node{\textbullet};
\draw (4*\x,0*\y) node{$\frac{1}{r-1}$};

\draw (0*\x,1*\y) node{0};
\draw (1*\x,1*\y) node{0};
\draw (2*\x,1*\y) node{$\cdots$};
\draw (3*\x,1*\y) node{0};
\draw (4*\x,1*\y) node{\textbullet};

\draw (0*\x,2*\y) node{$\frac{1}{r-1}$};
\draw (1*\x,2*\y) node{$\frac{1}{r-1}$};
\draw (2*\x,2*\y) node{$\cdots$};
\draw (3*\x,2*\y) node{$\frac{1}{r-1}$};
\draw (4*\x,2*\y) node{0};

\draw (0*\x,3*\y) node{$\frac{1}{r-1}$};
\draw (1*\x,3*\y) node{$\frac{1}{r-1}$};
\draw (2*\x,3*\y) node{$\cdots$};
\draw (3*\x,3*\y) node{$\frac{1}{r-1}$};
\draw (4*\x,3*\y) node{0};

\draw (0*\x,4*\y) node{$\vdots$};
\draw (1*\x,4*\y) node{$\vdots$};
\draw (2*\x,4*\y) node{$\ddots$};
\draw (3*\x,4*\y) node{$\vdots$};
\draw (4*\x,4*\y) node{$\vdots$};

\draw (0*\x,5*\y) node{$\frac{1}{r-1}$};
\draw (1*\x,5*\y) node{$\frac{1}{r-1}$};
\draw (2*\x,5*\y) node{$\cdots$};
\draw (3*\x,5*\y) node{$\frac{1}{r-1}$};
\draw (4*\x,5*\y) node{0};

\end{tikzpicture}
\caption{The fractional vertex cover of $\overline{\mathcal{H}_r}$.}\label{roughfigure}
\end{figure}

One may wonder if other choices of $S$ in the definition of $\mathcal{H}_r$ would yield a perturbable hypergraph satisfying properties \ref{itm:P1}, \ref{itm:P2}, and \ref{itm:P3}. An exhaustive search shows that there are no other choices of $S$ (up to isomorphism) for $r = 3$ and $r = 4$, but there are other choices for say $r=5$.  While it would be interesting to characterize the possible choices of $S$, doing so would not improve the given construction.

\subsection{Fine tuning}\label{skipto}

\begin{theorem}\label{planeminus}
Let $n,r,c$ be integers such that $r\geq 3$, $c\geq 1$, and $n\geq r(r-1)((r-1)(r-2)+1)c$.  If $(r^2-r) \mid n$ and an affine plane of order $r$ exists, then there exists a graph $G$ on $n$ vertices with $\delta(G) = (1-\frac{r-2}{r^2-r})n-c-1$ such that $\mc_r(G)\leq \frac{n}{r-1}-c$.
\end{theorem}

Note that the main case of interest is when $c=1$, but phrasing the result in general as we do shows that by lowering the minimum degree further, one can further decrease the size of the largest monochromatic component.  Also note that our construction only addresses the case $(r^2-r) \mid n$ for simplicity.
It is possible that in the case when $r^2-r$ does not divide $n$, by slightly modifying this construction (as was done in \cite{GS} for the case $r=3$), one can construct a graph $G$ with $\delta(G) =\ceiling{(1-\frac{r-2}{r^2-r})n}-2$ such that $\mc_r(G)\leq \ceiling{\frac{n}{r-1}}-1$.

\begin{proof}
Let $\mathcal{H}_r=(V,E)$ be the hypergraph from Definition \ref{H_r} and let $G$ be a uniform blow-up of $\mathcal{H}_r$ where $v\in V$ becomes $X_v$ in $G$ (with $|X_v|=\frac{n}{r^2-r}$).

Let $A=\{v_{r-1, i} : i\in [r-1]\}\cup \{v_{r-2, r}\}$.  We now adjust the size of each $X_v$ as follows:
\[ |X_v| := \begin{cases}
\frac{n}{r^2-r}-c      ,& \text{ if } v \in V(\mathcal{H}_r)\setminus A ,\\
\frac{n}{r^2-r}+(r-2)c ,& \text{ if } v \in A .
\end{cases} \]

\begin{figure}[ht]
\centering
\begin{tikzpicture}
\def\x{2.4};
\def\y{1};
\def\round{6pt}

\draw[rounded corners=\round,fill=gray] (-0.5*\x,-0.4*\y) -- ++(0,0.8*\y) -- ++(4.0*\x,0) -- ++(0.2*\x,1*\y) -- ++(0.6*\x,0) -- ++(0,-0.8*\y) -- ++(-0.6*\x,-0.0*\y) -- ++(-0.2*\x,-1.0\y) -- cycle;
\draw (4.5*\x,1*\y) node{$S$};
\draw[rounded corners=\round] (-0.5*\x,0.6*\y) -- ++(0,0.8*\y) -- ++(3.9*\x,0) -- ++(0.2*\x,1*\y) -- ++(0.9*\x,0) -- ++(0,-0.8*\y) -- ++(-0.9*\x,-0.0*\y) -- ++(-0.2*\x,-1.0\y) -- cycle;
\draw (4.7*\x,2*\y) node{$A$};

\draw (0*\x,0*\y) node{\textbullet};
\draw (1*\x,0*\y) node{\textbullet};
\draw (2*\x,0*\y) node{$\cdots$};
\draw (3*\x,0*\y) node{\textbullet};
\draw (4*\x,0*\y) node{$-c$};

\draw (0*\x,1*\y) node{$+(r-2)c$};
\draw (1*\x,1*\y) node{$+(r-2)c$};
\draw (2*\x,1*\y) node{$\cdots$};
\draw (3*\x,1*\y) node{$+(r-2)c$};
\draw (4*\x,1*\y) node{\textbullet};

\draw (0*\x,2*\y) node{$-c$};
\draw (1*\x,2*\y) node{$-c$};
\draw (2*\x,2*\y) node{$\cdots$};
\draw (3*\x,2*\y) node{$-c$};
\draw (4*\x,2*\y) node{$+(r-2)c$};

\draw (0*\x,3*\y) node{$-c$};
\draw (1*\x,3*\y) node{$-c$};
\draw (2*\x,3*\y) node{$\cdots$};
\draw (3*\x,3*\y) node{$-c$};
\draw (4*\x,3*\y) node{$-c$};

\draw (0*\x,4*\y) node{$\vdots$};
\draw (1*\x,4*\y) node{$\vdots$};
\draw (2*\x,4*\y) node{$\ddots$};
\draw (3*\x,4*\y) node{$\vdots$};
\draw (4*\x,4*\y) node{$\vdots$};

\draw (0*\x,5*\y) node{$-c$};
\draw (1*\x,5*\y) node{$-c$};
\draw (2*\x,5*\y) node{$\cdots$};
\draw (3*\x,5*\y) node{$-c$};
\draw (4*\x,5*\y) node{$-c$};

\end{tikzpicture}
\caption{The adjustment of the sizes of the sets in a uniform blow-up of $\mathcal{H}_r$. Each number corresponds to a vertex of $\mathcal{H}_r$, with the rows corresponding to $L_1$ and the columns corresponding to $L_{r+1}$. The number at a vertex $v$ is the amount in which we adjusted the size of $X_v$, i.e.\ $|X_v| - \frac{n}{r^2-r}$.}
\label{planefigure}
\end{figure}

First note that $\sum_{v\in V}|X_v|=n$ (since each column sums to 0 in Figure \ref{planefigure}).

Now we check the minimum degree condition.  Let $v\in V(\mathcal{H}_r)$, let $\ell_v\in L_{r+1}$ such that $v\in \ell_v$, and let $u\in X_v$.  We have (see Figure \ref{planefigure} in which each vertex is adjacent to everything except the distinct members of its own column)
\begin{align*}
d(u)&=(n-1)-\sum_{w\in \ell_v\setminus \{v\}}|X_w|\\
&= \begin{cases}
(n-1)-(r-3)(\frac{n}{r^2-r}-c)-(\frac{n}{r^2-r}+(r-2)c)    ,& \text{ if } v \in V(\mathcal{H}_r)\setminus A ,\\
(n-1)-(r-2)(\frac{n}{r^2-r}-c) ,& \text{ if } v \in A,
\end{cases}
\end{align*}
and thus $\delta(G) = (n-1)-(r-2)\frac{n}{r^2-r}-c= (1-\frac{r-2}{r^2-r})n - c-1$.

Finally we check that every monochromatic component of $G$, which corresponds to an edge $\ell$ from $\mathcal{H}_r$, has order at most $\frac{n}{r-1}-c$. Since $c \leq \frac{n}{r(r-1)((r-1)(r-2)+1)}$, we have $(r-1)\left(\frac{n}{r^2-r}+(r-2)c\right)\leq \frac{n}{r-1}-c$ and thus we need only consider the edges $\ell$ of $\mathcal{H}_r$ of order $r$; that is, when $\ell \cap S = \emptyset$. Since every edge from $\mathcal{H}_r$ of order $r$ intersects $A$ in at most one vertex, the order of the largest monochromatic component in $G$ will be at most
\[
(r-1)\left(\frac{n}{r^2-r}-c\right)+\frac{n}{r^2-r}+(r-2)c=\frac{n}{r-1}-c.
\]
\end{proof}

\section{When an affine plane of order $r$ does not exist}

It is known that there is no affine plane of order 6, so $r=6$ is the first case for which the construction of the previous section does not apply.  An example of a graph $G$ with $\delta(G)=\frac{5n}{7}-1$ such that $\mc_6(G)<\frac{n}{5}$ (in fact, $\mc_6(G)\leq \frac{n}{7}<\frac{n}{5}$) is a uniform blow-up of an affine plane of order 7 with two parallel classes removed.

\begin{problem}
Construct an example of a graph $G$ with large minimum degree such that $\mc_6(G)<\frac{n}{5}$.  In particular, for some $\alpha>0$ and all $n$, construct a graph $G$ on $n$ vertices with $\delta(G)\geq (\frac{5}{7}+\alpha)n$ such that $\mc_6(G)<\frac{n}{5}$.
\end{problem}

In light of Section \ref{sec:perturb}, it would suffice to construct a hypergraph $H=(V,E)$ with edge chromatic number 6, proportional rank at most $\frac{1}{5}$, $\delta^*(H)>\frac{5}{7}|V|$ such that if the proportional rank of $H$ is equal to $\frac{1}{5}$, then the top-level of $H$ with respect to the uniform weight assignment (the edges of maximum rank) has no perfect fractional matching.

In general, when an affine plane of order $r$ does not exist, trying to produce an example of an $r$-colored graph $G$ with large minimum degree for which $\mc_r(G)<\frac{n}{r-1}$ leads us back to the original problem for complete graphs.  The purpose of this section is mostly to collect what is known in one place and make a few observations.  These observations have consequences for the original problem for complete graphs and may be useful for extending our construction in the case when an affine plane of order $r$ does not exist.

Recall that Gy\'arf\'as \cite{Gy} proved $\mc_r(K_n)\geq \frac{n}{r-1}$ and this is best possible when $(r-1)^2$ divides $n$ and an affine plane of order $r-1$ exists.  For all $r$ such that affine plane of order $r-1$ does not exist, the problem of determining $\mc_r(K_n)$ (even asymptotically) is still open.  The following result of F\"uredi shows that one can improve the lower bound on $\mc_r(K_n)$ when there is no affine plane of order $r-1$ (note that the upper bound comes from the construction mentioned in the introduction).

\begin{theorem}[F\"uredi \cite{F1}]\label{furedi}
Let $r\geq 3$ be an integer, let $q$ be the largest integer at most $r-1$ such that there exists an affine plane of order $q$, and let $n\geq q^2$ be an integer.  If an affine plane of order $r-1$ does not exist, then $\frac{n}{r-1-\frac{1}{r-1}}\leq \mc_r(K_n)\leq \ceiling{\frac{n}{q}}$.
\end{theorem}

Since an affine plane is a hypergraph in which every pair of distinct vertices is contained in exactly one edge and the edges of the hypergraph can be decomposed into perfect matchings (and thus has the smallest possible edge chromatic number), a natural place to look for examples which improve the upper bound (when an affine plane of order $r-1$ does not exist) are resolvable balanced incomplete block designs.

A \emph{$(v,k,1)$-resolvable balanced incomplete block design}, a \emph{$(v,k,1)$-RBIBD} for short, is a $k$-uniform hypergraph $H$ on $v$ vertices such that each pair of vertices is contained in exactly one edge and the edges of $H$ can be decomposed into $\frac{\binom{v}{2}/\binom{k}{2}}{v/k}=\frac{v-1}{k-1}$ perfect matchings.  A necessary condition for the existence of a $(v,k,1)$-RBIBD is that $v\equiv k\bmod k(k-1)$.  Ray-Chaudhuri and Wilson \cite{RW} proved that for all $k\geq 3$ there exists a constant $C(k)$ such that if $v\geq  C(k)$ and $v\equiv k\bmod k(k-1)$, then a $(v,k,1)$-RBIBD exists.  Later Chang \cite{yC} proved that $C(k) = \exp(\exp(k^{12k^2}))$ suffices.

There are some other sporadic results for small $k$ (see \cite{AGY}), but in general, the existence of $(v,k,1)$-RBIBDs is open.

Note that an affine plane of order $k$ is a $(k^2,k,1)$-RBIBD and by the necessary condition above, $k^2$ is the smallest $v$ for which a non-trivial $(v,k,1)$-RBIBD exists.  Because of this, we parameterize $v$ in terms of $k$ and a non-negative integer $t$, and speak of $(k^2+tk(k-1),k,1)$-RBIBDs.

Given a hypergraph $H$, let $v(H)$ be the number of vertices in $H$ and recall that $r(H)$ is the rank of $H$.

\begin{fact}\label{RBIBD}
Let $k\geq 2$, $t\geq 0$, and $n\geq k^2+tk(k-1)$ be integers such that $k^2+tk(k-1)$ divides $n$.  If there exists a $(k^2+tk(k-1),k,1)$-RBIBD, then there is a $((t+1)k+1)$-coloring of $K_n$ such that every monochromatic component has order at most $\frac{n}{(t+1)k-t}$.

In particular, when $t=0$ this means that if there exists an affine plane of order $k$, then there exists $(k+1)$-coloring of $K_n$ such that every monochromatic component has order at most $\frac{n}{k}$.
\end{fact}

\begin{proof}
This follows from the fact that the proportional rank of a $(k^2+tk(k-1),k,1)$-RBIBD is $$\frac{k}{k^2+tk(k-1)}=\frac{1}{(t+1)k-t}$$ and a $(k^2+tk(k-1),k,1)$-RBIBD has $$\frac{\binom{k^2+tk(k-1)}{2}/\binom{k}{2}}{(k^2+tk(k-1))/k}=\frac{k^2+tk(k-1)-1}{k-1}=(t+1)k+1$$ parallel classes. Taking a uniform blow-up gives the desired conclusion.
\end{proof}

The point of Fact \ref{RBIBD} is that, for instance when $r=23$, Theorem \ref{furedi} implies that $\frac{n}{22-1/22}\leq \mc_{23}(K_n)\leq \frac{n}{19}$ (if no affine plane of order 20, 21, or 22 exists).  But by Fact \ref{RBIBD}, if a $(231,11,1)$-RBIBD exists ($k=11$, $t=1$), then $\frac{n}{22-1/22}\leq \mc_{23}(K_n)\leq \frac{n}{21}$.

Also note that for $r=7$, Theorem \ref{furedi} implies that $\frac{6n}{35}\leq \mc_7(K_n)\leq \frac{7n}{35}=\frac{n}{5}$.  It is well known that a $(15, 3, 1)$-RBIBD exists; this is the original Kirkman schoolgirls problem (in fact, four out of the 80 Steiner triple systems on 15 vertices are resolvable -- see \cite{MPR}).  So Fact \ref{RBIBD} implies that there are at least four other examples which show that $\mc_7(K_n)\leq \frac{n}{5}$.

\section{Conclusion}

The main open problem is to prove an analogue of Theorem \ref{GuggiariScott} for $r\geq 4$ colors (the lack of additional evidence prevents us from calling it a conjecture).  Note that the following is true for $r=2,3$.

\begin{problem}
Let $n$ and $r\geq 2$ be positive integers. Prove that if $G$ is a graph on $n$ vertices with $\delta(G)\geq (1-\frac{r-2}{r^2-r})n-1$ and an affine plane of order $r$ exists, then $\mc_r(G)\geq \frac{n}{r-1}$.
\end{problem}

When $r=7$, Theorem \ref{main_example} says that when $42|n$, there exists a graph $G$ on $n$ vertices with $\delta(G)= (1-\frac{5}{42})n-2$, such that $\mc_7(G)<\frac{n}{6}$.  However, Theorem \ref{furedi} says $\mc_7(K_n)\geq \frac{6n}{35}>\frac{n}{6}$ (and it is even conceivable that $\mc_7(K_n)=\frac{n}{5}$).

So we can ask a modified version of the original question of Gy\'arf\'as and S\'ark\"ozy which is different whenever an affine plane of order $r-1$ does not exist.

\begin{problem}
If $G$ is a graph on $n$ vertices, how large does the minimum degree of $G$ need to be so that $\mc_r(G)=\mc_r(K_n)$?
\end{problem}


TITLE: Show that $AP=AQ$
QUESTION [0 upvotes]: Let $\triangle ABC$ and $E, D$ on $[AB]$ and $[AC]$ s.t. $BEDC$ is inscribable. Let $P\in [BD], Q\in [CE]$ s.t. $AEPC$ and $ADQB$ are also inscribable. Show that $AP=AQ$.
I draw the points and I considered $R$, the point of intersections of the two circles, as shown in the following figure.

REPLY [1 votes]: $\angle ABD = \angle EBD = \angle ECD = \angle ACE \Rightarrow$ $\triangle ABD \sim \triangle ACE \Rightarrow$ $\frac{AD}{AB}=\frac{AE}{AC} \Rightarrow$ $AD\cdot AC=AB\cdot AE$
$\angle EPA = \angle ECA = \angle ECD = \angle EBD = \angle PBA \Rightarrow$ $\triangle EPA \sim \triangle PBA \Rightarrow$ $\frac{AE}{AP}=\frac{AP}{AB}\Rightarrow$ $AP^2=AB\cdot AE$
In the same way: $AQ^2 = AC\cdot AD$
Then $AP^2 = AB\cdot AE = AC\cdot AD = AQ^2$, $AP =AQ$


TITLE: An error in a proof due to variable creep?
QUESTION [2 upvotes]: I'm working through some exam practice questions and I came across this one:

Identify the error in the following “proof.”
Let u, m, n be three integers. If u|mn and gcd(u, m) = 1, then m = ±1.
If gcd(u, m) = 1, then 1 = us + mt for some integers s, t. If u|mn, then
us = mn for some integer s. Hence, 1 = mn + mt = m(n + t), which
implies that m|1, and therefore m = ±1.

Now I think the problem here is that we cannot go from the linear transformation statement 1 = us + mt and then state that u|mn => mn = us for some integer s, because we already have a value of s in the previous statement. so we would need to define u|mn => mn = uj for some integer j.
And now the substitution doesn't work and we cannot proceed.
Does this make sense to you guys? It makes sense to me that we cannot use s in two different places here. But I'm having a hard time trying to explain why in a clear manner.

REPLY [1 votes]: You're right: the "proof" has defined $s$ in incompatible ways in two different places. You could explain it by analogy as follows:

We prove that $2=4$. Indeed, the number $2$ is even, so it can be expressed as $2 = 2n$ for some $n$. The number $4$ is even, so it can be expressed as $4 = 2n$ for some $n$. Hence $2 = 2n = 4$, so $2 = 4$.


TITLE: Question about vector subspace
QUESTION [1 upvotes]: Let $V,W$ be real vector spaces and let $L: V \to W$ be a linear function.
 Prove that if $U \subset V$ is a vector subspace then $L(U) \subset W$ is a vector subspace.
What condition is required to have a vector as a subspace to another vector?

REPLY [1 votes]: Let $\def\v#1{{\bf#1}}\v w_1,\v w_2$ be in $L(U)$.  By definition this means
$$\v w_1=L(\v u_1)\ ,\quad \v w_2=L(\v u_2)$$
for some $\v u_1,\v u_2$ in $U$.  Because $L$ is linear we have
$$\v w_1+\v w_2=L(\v u_1+\v u_2)\ ;$$
because $U$ is a subspace of $V$ we have $\v u_1+\v u_2\in U$.  So $\v w_1+\v w_2$ is in $L(U)$.  This proves that $L(U)$ is closed under addition.
There are two more things to prove: one very similar to what I have shown you, the other is extremely easy.
Good luck!


TITLE: Obtaining differential equation from recursive function
QUESTION [1 upvotes]: I have a function $f(x)$ for $x = \{0, 1, \ldots, m\}$ which is defined as
$$
f(x) = \begin{cases}0 & \mbox{if }x = 0 \\ f(x-1)(1- \dfrac{x}{m}) + \dfrac{x}{m} & \mbox{if } x \ge 1   \end{cases}
$$
Now it would like to obtain a continuously differentiable function $g(y)$ for $y \in [0,m]$ such that $g(x) = f(x)$ for $x = \{0, 1, \ldots, m\}$.
One obvious option would be fitting a $(m-1)$-th degree polynomial through $f$. I think that there should also be a possibility to transform the problem into a differential equation, but can't see how exactly I would do that. Any suggestions?

REPLY [1 votes]: There are infinite functions that interpolate $f$. If you only need the values at integer $x$, any one will do. If you are interested in intermediate values, a polynomial could be a terrible idea (it can very well oscillate wildly between the integer points, even if they do grow tamely).
What values of $m$ are of interest?
Write the recurrence so there is no subtraction in $x$:
$\begin{align*}
   m f(x + 1)
     &= f(x) (m - 1 - x) + x + 1 \\
\end{align*}$
This is a linear recurrence of the first order. Divide by the summing factor
$\begin{align*}
   \prod_{0 \le r < x} \frac{m - 1 - x}{m}
      &= \frac{(m - 1)^{\underline{x}}}{m^x}
\end{align*}$
and get, after changing variable to $r$:
$\begin{align*}
   \frac{m^{r + 1} f(r + 1)}
        {(m - 1)^{\underline{r}}}
    - \frac{m^r f(r)}
           {(m - 1)^{\underline{r - 1}}}
    &= \frac{r m^r}
            {(m - 1)^{\underline{r}}}
\end{align*}$
Summing over $0 \le r < x$ has the left hand side telescope nicely:
$\begin{align*}
  \frac{m^{x - 1} f(x)}{(m - 1)^{\underline{x - 1}}}
    - \frac{m^0 f(0)}{(m - 1)^\underline{0}}
    &= \sum_{0 \le r < x} \frac{r m^r}{(m - 1)^{\underline{r}}}
\end{align*}$
Sadly, the last sum seems to have no simple form. If it had, you could tahe it as your natutal interpolant.


text:
\begin{document}

\voffset=-.5 truecm
\textheight=8.25 truein

\title{A new integrable system on the sphere}
\date{}

\author{
Holger R. Dullin
\thanks{Department of Mathematical Sciences, Loughborough University, LE11 3TU  UK;
h.r.dullin@lboro.ac.uk},
Vladimir S. Matveev
\thanks{Mathematisches Institut, Universit\"at Freiburg, 79104 Germany
 matveev@email.mathematik.uni-freiburg.de}}
\maketitle

\begin{abstract}
We present a new Liouville-integrable natural  Hamiltonian system
on the (cotangent bundle of the) sphere $S^2$.
The second integral is cubic in the momenta.
\end{abstract}

{MSC2000: 37J35, 58F07, 58F17, 70H06, 70E40}

\section{Introduction}

A Hamiltonian system is called natural if
its Hamiltonian is a sum of a positive-definite
kinetic energy and a potential.
Natural Hamiltonian systems on (cotangent bundles of) closed  surfaces
admitting  integrals polynomial in momenta are
interesting for a number of reasons:

\begin{enumerate}
\item They are classical:  The formulation
of the problem is due at least to Darboux \cite{Darboux}.

\item If a natural Hamiltonian system admits a real-analytic integral,
then it admits an integral polynomial in momenta \cite{Whittaker}.

\item In particular, all known natural integrable Hamiltonian
systems on surfaces have integrals polynomial in momenta.

\item The existence of the integral polynomial in momenta of degree
one or  two  has   a very clear geometric background: the
existence of an integral of degree one implies the existence of a
one-parametric family of symmetries of the system.  The existence
of an integral of degree two implies the existence of so-called
separating variables.
\end{enumerate}

Natural Hamiltonian systems on closed surfaces that admit a
nontrivial integral which is polynomial in momenta of degree one
or two are completely understood: there exists  a complete
description and classification, see, for example, \cite{BF}.
Up to now, only one family of natural
Hamiltonian systems on a closed surface admitting an integral of
degree three and admitting no (nontrivial) integral of degree one
or two is explicitly known, namely the family of  system obtained
from the  Goryachev-Chaplygin top.
We now present a second, distinct, family of natural Hamiltonian
systems with a cubic integral.

\subsection{The result}
Consider the sphere $S^2 \subset \R^3$ of radius 1 with
the spherical coordinates $(x,y,z) = (-\sin\theta\cos\phi,-\sin\theta\sin\phi,
 \cos\theta)$ and the following two functions
$H$ (the Hamiltonian) and $F$ (the second integral)
on the cotangent bundle of the sphere without poles $z={\pm}1$.
Let $A, c, s \in \R$ be parameters with $s > 1$ and define
\[
     W(z)  =  z + s, \quad
      P(z) = 3z^2 + 4 s z + 1, \quad
      Q(z) = 3z^2 + 2 s z - 1
\]
and
\[
    G(z)  =  \frac{P(z)}{(2 W(z))^2}.
\]
Then, the function $H$ is given by  $H :=  K+ V$, where
\begin{align*}
K & :=\frac12 \left( \frac{1}{\sin^2\theta} +{G(\cos\theta)}\right) p_\phi^2 + \frac12 p_\theta^2 \\
V & := A\frac{ \sin\theta}{ \sqrt{W(\cos\theta)} } \cos \phi+ \frac{c}{W(\cos\theta)},
\end{align*}
and $F$ is defined as
 \[
 F := 2Hp_\phi - p_\phi^3 +
A  \cos(\phi)\frac{Q(\cos\theta)}{\sqrt{W(\cos\theta)}\sin\theta}
p_\phi + 2A\sin \phi \sqrt{W(\cos\theta)}  p_\theta   \,.
\]

\vspace{2ex}
 \noindent {\bf Proposition: }
 {\em  The functions $H$ and $F$ can be analytically continued to
the cotangent bundle of the whole sphere.  The continuation is also
polynomial in momenta (of degree 2 for H and of degree 3 for $F$).}

\vspace{2ex}  We will denote the continuations of $H$, $K$, $F$
  by the same letters $H$, $K$, $F$; in particular in the
theorem  below we mean the continued functions
defined on the cotangent bundle of the whole sphere.

\vspace{2ex}

\noindent {\bf Theorem:}
{\it The following statements hold:
\begin{enumerate}

\item   The functions $H$ and  $F$ commute with respect  to the standard Poisson bracket on $T^*S^2$
and  are functionally  independent

\item  The  kinetic energy $K$ is positive definite

\item  If $A\ne 0$, the Hamiltonian $H$ does not admit a (smooth) nontrivial   integral which is  polynomial in velocities of degree less than three and which is linearly independent of
$H$.

\end{enumerate}
}

\vspace{2ex}

In other words,  we found a new 1) Liouville integrable,
2) natural Hamiltonian system on the sphere with 3) an integral cubic in momenta.

\subsection{Why the system is new} \label{sec:new}

The previously known family comes  from  the Goryachev-Chaplygin top
using symplectic reduction, see \cite{BKF} for the details.
It is a natural Hamiltonian system on the sphere. In the standard
spherical  coordinates its Hamiltonian $H_1$ is $K_1+V_1$, where
the kinetic energy $K_1$ and the potential $V_1$ are
\begin{align*}
K_1 & :=\frac{1}{2}\left(\frac{\cos^2\theta}{\sin^2\theta}+4
\right)p_\phi^2+ \frac{1}{2}p_\theta^2  \\
V_1 & := A_1\sin \theta \sin \phi\, ,
\end{align*}
see, for example, \cite{DMT}.
The integral $F_1$ for the Hamiltonian $H_1$ is given by
$$
F_1:= H_1p_\phi-2p_\phi^3-\frac{A_1}{2}
p_\theta\cos(\phi)\cos(\theta) +\frac{A_1}{2}{\frac {{}\,\sin \phi
\left( 3\, \left( \cos  \theta  \right) ^{2}-2 \right) }{\sin
\theta }}p_\phi. $$

It is easy to see  that the system we found is essentially
different from the Goryachev-Chaplygin system, i.e.\ that there
exists  no diffemorphism $D:S^2\to S^2$ such that $D_*\, K= \alpha
\, K_1$ and $D_*\,  V =\beta V_1$ for certain constants $\alpha$,
$\beta$.

Consider the metrics $g,$ $g_1$ corresponding to the kinetic
energies $K$, $K_1$, respectively. They  are given by the
formulae:
\begin{eqnarray} \label{eqn:metric}
ds^2 &=&  d\theta^2 + \frac{d\phi^2}{1/\sin^2\theta + G(\cos
\theta)} \label{metric1}
\\ \label{eqn:metric1}
ds_1^2&=&{d\theta^2}+ \frac{d\phi^2}{4+\cot^2\theta}
   = {d\theta^2}+ \frac{d\phi^2}{1/\sin^2\theta + 3}
\label{metric2}.
\end{eqnarray}

By direct calculation,  it is easy to see that level lines of the
curvature of both metric are the lines $\{\theta=\textrm{const}\}$.
More precisely, since the formulae above do not depend on $\phi$,
the curvature is constant along every such line. It is easy to see
that the curvature is not constant.

Then, the diffeomorphism $D$, if it exists, must take the lines
$\{\theta=\textrm{const}\}$ of the first system to the lines
$\{\theta=\textrm{const}_1\}$ of the second system. Since the
lines $\{\theta=\textrm{const}\}$ are orthogonal to the lines
$\{\phi=\textrm{const}\}$ in the first and in the second metric,
the diffeomorphism $D$  must also take the lines
$\{\phi=\textrm{const}\}$ of the first system to the lines
$\{\phi=\textrm{const}_1\}$ of the second system. Using that  the
coordinate $\phi$ is periodic with the period $2\pi$, we obtain
that  the diffeomorphism $D$ must be given by formulae $$
\theta_{new}=\theta_{new}(\theta), \ \ \ \phi_{new}=\pm \phi+
\phi_0 \, .$$
 Then, the pull-back of the metric $g_1$ has the
form $$ \left(\frac{\partial \theta_{new}}{\partial
\theta}\right)^2 d\theta^2  + \frac{d\phi^2}{4 + \cot^2
\theta_{new}}.$$ Then, $\frac{\partial \theta_{new}}{\partial
\theta}=\pm 1$, and the  diffeomorphism $D$ must be given by the
formula
 $$
\theta_{new}=\theta \ \ \ \ \ \mathrm{or} \ \  \theta_{new}=\pi -
\theta, \ \ \ \ \ \phi_{new}=\pm \phi+ \phi_0 \,  . $$ Clearly,
the pull-back of the metric $g_1$  with the help of such
diffeomorphism  is not proportional to $g$. Otherwise $G$ would
need to become a constant. But then $P$ would have a double root at $z = -s$,
which is impossible.
Thus, our system is essentially different from the reduced Goryachev-Chaplygin top.

Selivanova \cite{Selivanova} proved the existence of an additional
family of natural Hamiltonian systems admitting  integrals of degree 3 in
momenta.  This family is not explicit. Instead, a nonlinear
differential equation is derived and it is proved that certain
solutions of this equation allow to construct a geodesic flow
admitting an integral of degree three and admitting no integral of
smaller degree.

At present we do not know whether our system overlaps
with the systems considered by Selivanova.  Our guess is that this
is not the case.
Here are some reasons supporting this claim:
\begin{enumerate}
\item It is not clear whether the
system of  Selivanova is real-analytic; she claims the smoothness only.

\item Selivanova's family  contains (the reduction of) Goryachev-Chaplygin system;
our family does not.

\item The ansatz of Selivanova is more restrictive than the form of our system.

\end{enumerate}

\section{Proof of the proposition}

\subsection{Analytic proof}
\label{proposition}
Clearly, the functions $V,K,F$  depend real-analytically
on $(\phi,\theta)$ and on the corresponding momenta $p_\phi, p_\theta$,
so the only possible problem could appear near the points $z=\pm
1$. We consider $(x,y)$  as a local coordinate system near these
points  of the sphere. The coordinates $(x,y)$ are related to
coordinates $(\phi,\theta)$ by the following real-analytic change of variables:
\begin{align*}
   \sin\theta &= \sqrt{x^2+y^2}, &  p_\theta &= (x p_x + y p_y) \sqrt{(x^2+y^2)^{-1}-1} \\
   \tan\phi &= y/x, \quad             & p_\phi &= x p_y - y p_x  \,.
\end{align*}
In the new local coordinates the kinetic energy and potential are
\[
   K = \frac12\left( p_x^2 + p_y^2 - (xp_x + yp_y)^2 + (xp_y-yp_x)^2 G(z) \right) ,
\]
\[
    V(x,y) = -A \frac{x}{\sqrt{W(z)}} + \frac{c}{W(z)}, \ \ \ \textrm{where} \quad z = \pm \sqrt{1-x^2-y^2}
    \,.
\]
The sign of $z$ depends on whether a neighbourhood of the north or
south pole is considered. Clearly, $K$ and $V$ are real-analytic.
Thus, the Hamiltonian   $H$ is a real-analytic  function on the
whole $T^*S^2$.
Since we will need it for the proof of  the second statement of  the Theorem,
we remark that the kinetic energy is positive definite near the poles,
where $x$ and $y$ are small.

Now let us show that the second integral also is a real-analytic function
on the whole  $T^*S^2$. The first two terms of $F$  are
real-analytic,  since the momentum $p_\phi$ is $x p_y - y p_x$ in
the new coordinate system, and therefore is real-analytic, and we
already have proven that $H$ is real-analytic. The sum of the
third  and the fourth terms in the new coordinate system is
$$
A\left(\frac{-xy}{\sqrt{\sqrt{1-x^2-y^2}+s}}p_x +
\frac{2-3x^2-2y^2+2s\sqrt{1-x^2-y^2}}{\sqrt{\sqrt{1-x^2-y^2}+s}}p_y
\right), $$
and this is clearly real-analytic.

\subsection{Geometric proof}

The second integral $F$ is cubic in the momenta, like the
Goryachev-Chaplygin top. This top does not appear as a limiting
case in our family, but is serves as a motivation for the
following coordinate transformation, which uses global coordinates
$(x,y,z)$ on a sphere embedded in $\R^3$. The angular momentum
$(L_x,L_y,L_z)$ where $L_z = x p_y - y p_x = p_\phi$ etc.\ with
cyclic permutations, satisfies the usual Poisson structure on the
sphere with non-vanishing brackets
\[
  \{ L_x, L_y \} = L_z, \quad
   \{x, L_y \} = z, \, \{ z, L_y \} = -x

\]
and cyclic permutations thereof. This bracket has
Casimirs $x^2+y^2+z^2=1$ and $xL_x + yL_y + zL_z=0$.
The global Hamiltonian is $H = K+V$, where
\[
   K  = \frac12 \left( L_x^2 + L_y^2 + (1+G(z))L_z^2 \right)
\]
\[
      V(x,y,z) = -A \frac{ x}{\sqrt{W(z)}} + \frac{c}{W(z)},
\]
and is clearly real-analytic. The integral reads
\[
\begin{aligned}
  F & =
2  H L_z -  L_z^3 -

A \frac{Q}{\sqrt{W}}\frac{xL_z}{1-z^2}

   - 2A\sqrt{W} \frac{y (xL_y-yL_x)}{1-z^2}  \\
   & = 2  H L_z -  L_z^3
+ \frac{A}{\sqrt{W}}( x L_z + 2W L_x )
   \,.
\end{aligned}
\]
In the second line the apparent singularity in $F$ is removed by using
both Casimirs $x^2+y^2+z^2 = 1$ and $x L_x + y L_y + z L_z = 0$ and
in addition the identity $Q = 2zW + z^2 - 1$.
The integral is cubic in the momenta, and clearly is real-analytic.

Like the Goryachev-Chaplygin
top the system is only integrable on the level set of the Casimir
$x L_x + y L_y + z L_z = 0$. Writing the Hamiltonian in this form
suggests an interpretation of a spinning top with zero
angular momentum (the vanishing Casimir), an orientation
dependent moment of inertia, and a non-standard potential.
Note, however,
that $1+G$ is not positive for all $z \in [-1,1]$ for certain
values of $s$, which means that a moment of inertia may
pass through infinity for such value of $s$.
Nevertheless, the kinetic energy in $H$ is positive
definite for all $s$, see Section~\ref{3.1}.
This is
possible because even when $1+G < 0$ because $x L_x + y L_y + z
L_z = 0$.

Introducing $\xi = x + i y$ and $\eta = L_x + i L_y$ and writing $V(x,y,z) = x U(z)$
the equations of motion are
\begin{align}
  -i \dot \xi    & = - L_z  ( 1 + G) \xi + z \eta  \\
  -i \dot \eta & =  - \frac12 G' L_z^2 \xi - L_z G \eta + z U - \frac12 U' \,(\xi^2 + \xi \bar \xi) \,.
\end{align}
Here $z^2 = 1 - \xi \bar \xi $ and $-2 z L_z = \xi \bar \eta + \eta \bar \xi$,
or the equations are completed with
$ \dot z  = x L_y - y L_x$ and $ \dot L_z  =  -y U$.

\section{Proof of the Theorem}

\subsection{Liouville integrable}

It is tedious but easy to check that the functions $H$ and $F$ commute,
since they are given by explicit formulae.
The calculation goes as follows.
The canonical bracket is a quadratic polynomial in the momenta. The term independent
of the momenta vanishes because $Q = 2z W - 1 + z^2$.

The coefficient of $p_\theta p_\phi$ vanishes because $P = 4 z W + 1 - z^2$.
The nontrivial fact is that the coefficients of $p_\phi^2$ which contains $P$, $Q$
and derivatives thereof vanishes.

$H$ and $F$ are independent because $H$ has terms quadratic in momenta
(and not a square of a linear function of momenta)
and $F$ has terms that are cubic in momenta
(and not a square of a linear function of momenta).
So $H$ and $F$ have vanishing Poisson bracket and are functionally
independent,
hence the system is Liouville integrable.

\subsection{Natural} \label{3.1}

As we already have remarked in Section~\ref{proposition}, the
kinetic energy $K$ is positive near the poles of the sphere. Thus,
it is sufficient to show that the metric (\ref{metric1}) is
positive definite at regular points of the spherical coordinate
systems, i.e. we have to show that $C:=1/\sin^2\theta + G(\cos
\theta)$ is positive for $0<\theta<\pi$. Substituting $z$ instead
of $\cos \theta$, we obtain
\[
 C(z)=\frac{1}{4} \frac{6z^{2}+12s z+4 {s}^{2}-3{z}^{4}-4s{z}^{3}-1}{(1-{z}^{2})  (z+s)^{2}} \, .
\]
 Since the denominator
$\left( 1-{z}^{2} \right)  \left( z+s \right) ^{2}$ is always
positive for $-1<z=\cos(\theta)<1$, we need to prove that the numerator
$$
R(z):={\frac{3}{2}{z}^{2}+3s z+{s}^{2}-\frac{3}{4}{z}^{4}-s{z}^{3}-\frac{1}{4}}
$$
is positive.
Its value at $z=-1$ is $(s-1)^2$ and hence positive; its derivative is
$$
\frac{\partial R(z)}{\partial z} = 3(1-z^2)(z+s) \,.
$$
Since the derivative is also positive for $-1<z=\cos(\theta)<1$, $R(z)$ is positive
for $-1<z=\cos(\theta)<1$.
Hence the metric (\ref{metric1}) is positive definite.

\subsection{Cubic}

 Let us prove that,  for $A\ne 0$, our system does not admit
 an integral linear in momenta, and that every integral quadratic in momenta is
 proportional to the Hamiltonian.

 Suppose the function $P_2+P_1+P_0$, where every $P_i$ is a
 homogeneous polynomial in momenta of degree $i$,  is an integral for $H=K+V$.
 Then, the Poisson bracket $\{K+V, P_2+P_1+P_0\}$ must vanish. We  have
 \begin{align} \label{bracket}
 0 & =  \{K+V, P_2+P_1+P_0\}   \nonumber \\
 & =  \{K,P_2\}+ \{K,P_1\}+   \{K,P_0\} + \{V,P_2\}  +  \{V,P_1\}+  \{V,P_0\} \, .
 \end{align}

Since the Poisson bracket  of two functions $F_1,F_2:T^*M^2\to
\mathbb{R}$ is given by $$ \{F_1,F_2\}=\frac{\partial
F_1}{\partial x}\frac{\partial F_2}{\partial p_x}+ \frac{\partial
F_1}{\partial y}\frac{\partial F_2}{\partial p_y} -\frac{\partial
F_1}{\partial p_x}\frac{\partial F_2}{\partial x}-\frac{\partial
F_1}{\partial p_y}\frac{\partial F_2}{\partial y}, $$ where $x,y$
are local coordinates on $M^2$ and $p_x,p_y$ are the corresponding
momenta, every term on the right-hand side of (\ref{bracket}) is
polynomial and homogeneous in momenta: $\{K,P_2\}$ of degree $3$;
$\{K,P_1\}$ of degree $2$;
$\{K,P_0\} +  \{V,P_2\}$ of degree $1$ and $\{V,P_1\}$ of degree $0$.
The Poisson bracket $\{V,P_0\}$ evidently vanishes.
 For (\ref{bracket}) to vanish all the other degree 0, 1, 2, and 3 polynomials
 must also vanish identically.

  Let us  prove that the linear term $P_1$ must be zero.
 Vanishing of $\{K,P_1\}$  implies that $P_1$ is a linear integral
 of the geodesic flow of the metric given by $K$. In the  spherical
 coordinates $\phi, \theta$ on the sphere the metric is given by (\ref{eqn:metric}).
We have already remarked in Section \ref{sec:new} that the
level curves of the curvature are the curves $\{\theta=\mathrm{const}\}$.

Suppose the integral $P_1$ has the form
$v_1(\theta,\phi)p_\theta+v_2(\theta,\phi)p_\phi$. Then, by
Noether's Theorem, the vector field $v:=(v_1,v_2)$ is a Killing
vector field, i.e. its flow preserves the metric. Then, the flow
of $v$ preserves the  curvature, which implies that the component
$v_1$ must be zero.

Now, using that $\{V,P_1\}$ vanishes, we have that $\{V,
v_2p_\phi\}$ is zero, which in the case $v_2\not\equiv 0$ implies
$\frac{\partial V}{\partial \phi}=0$, which is definitely not the
case. Thus, $v_2\equiv 0$,  and $P_1\equiv 0$.

Now let us show  that $P_2+P_0$ is proportional to the Hamiltonian $H$.
Since $\{K,P_2\}=0$, $P_2$ is an  integral  of the geodesic flow
for the metric (\ref{eqn:metric}). As we already mentioned, for
geodesic flows on closed surfaces the
integrals quadratic in velocities are completely understood.
In particular, if the
curvature of the surface is not constant, then  the space of
quadratic integrals is at most two-dimensional
\cite{dissertation,Kio}.

The curvature of the metric (\ref{eqn:metric}) is not  constant, and
the following two linearly independent functions are integrals of
its geodesic flow: the first is $K$ itself, and the second is
$p_\phi^2$. Then, for certain constants $\beta,\alpha$, we
have $P_2=\alpha p_\phi^2 + \beta K$. Our goal is to show that
$P_2+P_0$ is proportional to  $H$.

>From $\{K,P_0\} + \{V,P_2\}=0$ we find
$\{K,P_0 - \beta V \} + \alpha  \{V,p_\phi^2\}=0$.
Hence,
$$
 p_\theta \frac{\partial (P_0- \beta V)}{\partial
\theta}+ p_\phi\frac{1}{\sin^2\theta+G(\cos \theta)}\frac{\partial
(P_0 - \beta V)}{\partial \phi} -2\alpha p_\phi \frac{\partial V}{\partial
\phi}=0 \,.
 $$
Therefore $\frac{\partial (P_0-\beta V)}{\partial \theta}=0$, and then
$\frac{\partial (P_0-\beta V)}{\partial \phi}=2\alpha (\sin^2\theta+G(\cos
\theta))\frac{\partial V}{\partial \phi}$.
By cross differentiation we find
$$
2\alpha \frac{\partial \left( (\sin^2\theta+G(\cos
\theta))\frac{\partial V}{\partial \phi}\right)}{\partial
\theta}=0,
$$
which is possible only if $\alpha=0$ or $A=0$.
If $\alpha = 0$ then $P_0 - \beta V = {\rm const}$,
and so after absorbing the constant in the Hamiltonian
we have $\beta = 1$ and the integral $P_2+P_1+P_0$ is proportional to $H$.
This proves the Theorem.

\section{Geodesic flows with cubic integrals}

A geodesic flow is  a  natural Hamiltonian system whose potential
energy is identically zero.

According to Maupertuis's principle, an integrable natural
Hamiltonian system  immediately gives a family of  integrable
geodesic flow, see \cite{BKF} for details. If the integral of the
system is polynomial in momenta, the integrals of the geodesic
flows are  also polynomial of the same degree.

In our case, the Hamiltonian of the geodesic flow is
 given by $$H_{geod} =  \frac{p_\theta^2 +
{p_\phi^2}{\left(1/\sin^2\theta + G(\cos
\theta)\right)}}{2(h-V)}.$$ Here $h$ is a constant such that

$h$ is larger than the maximum of the potential $V(x)$ on the sphere $S^2$.
The integral of the third degree is
\begin{equation}\label{integral12}
\begin{aligned}
   F_{geod} = & 2Hp_\phi - 2Vp_\phi+ p_\phi^3
    +H_{geod} \Big( 2Vp_\phi \\
  &  +
 A  \cos(\phi)\frac{Q(\cos\theta)}{\sqrt{W(\cos\theta)}\sin\theta}
p_\phi + 2A\sin \phi \sqrt{W(\cos\theta)}  p_\theta \Big)  \,.
\end{aligned}
\end{equation}

The metric corresponding to $H_{geod} $ is
 \begin{equation}
\label{metric11} ds^2_{geod} =\left(h-V\right) \left(d\theta^2 +
\frac{d\phi^2}{1/\sin^2\theta + G(\cos
\theta)}\right).
\end{equation}

The investigation of geodesic flows that admit an integral polynomial in momenta
is a very classical subject. If the degree of integrals is one or two, they
were  well-understood already in 19th century, see for example
\cite{Darboux}. There are a lot of local examples of geodesic
flows admitting integral polynomial in velocities of degree 3, see
the survey \cite{Hijetarinta} for details, and only very few global,
i.e.\ on closed or complete surfaces.

Let us recall the known results about geodesic flows on closed
surfaces admitting an integral polynomial in momenta.  For a more
detailed review see \cite{BF}.

First of all, in view of results of Kolokoltsov \cite{Kol},
a geodesic flow of a surfaces of genus greater than two cannot
admit a nontrivial integral polynomial in momenta. Then, an
orientable surfaces admitting such geodesic flows must be the
sphere or the torus.

We  collect  the main results about existence
 and classification of  metrics on the torus and  on
 the sphere  whose geodesic flow
 admits a nontrivial integral polynomial in momenta in the following table:

\vspace{3ex}

\begin{tabular} {|c|c|c|}
\hline
         & Sphere $S^2$  &Torus $T^2$ \\
         \hline
Degree 1 & All is known & All is known \\ \hline
 Degree 2 & All is
known & All is known\\ \hline
 Degree 3 & Series of examples & Partial negative results \\
\hline Degree 4 & Series of examples & Partial negative results \\
\hline Degree $\ge$ 5 & Nothing is known  & Nothing is known \\
\hline
\end{tabular}

\vspace{3ex}

The following notation is used in the table.
``Degree" means the smallest degree of an integral polynomial in velocities.
``All is known" means that there exists an effective description and classification
(can be found in \cite{BMF}).

There exists only one explicit ``Series of examples" for degree
three. It  comes from the Goryachev-Chaplygin case of rigid body
motion (by applying symplectic reduction and Maupertuis's
principle), see \cite{BKF}. The most valuable "partial negative
results" are due to Byaly\u i \cite{Byalyi} and Denisova and
Kozlov \cite{Denisova}.  They proved that if a natural Hamiltonian
system on the torus  whose kinetic energy is given by a flat
metric admits an integral polynomial in momenta of degree three,
it admits an integral  linear in momenta.

Thus, our system gives one more series of examples of integrable
geodesic flows on the sphere whose integral is polynomial in
momenta of degree 3. Below, in Sections~\ref{4.1}, \ref{4.2}, we
show that these geodesic flows do not admit an  integral which is
polynomial in momenta of degree less than 3, and that these
examples are different from examples coming from
Goryachev-Chaplygin.   Note, that this does not follow directly from
the Theorem.

Kiyohara \cite{Kyoh} proved the existence of one more series of
examples of integrable geodesic flows on the sphere whose integral
is polynomial in momenta of degree 3. Although his examples are
not explicit (similar to Selivanova \cite{Selivanova} he writes a
nonlinear differential equation and claims that its solutions give
integrable geodesic flows), it is easy to see that his examples
are different from ours, since they have regions of constant
curvature and therefore can not be real-analytic.

\subsection{Cubic}

\label{4.1}

We need to prove that the Hamiltonian $H_{geod}$ has no integral which is
polynomial in velocities of degree 1,2.
We will prove it assuming that the energy level $h$  is sufficiently large.
Our proof for arbitrary $h$ is based on the technique
developed in \cite{BF} and is very long. It will be published
elsewhere.

It is easy to see that the integral $F_{geod}$ is  not the third
power of a function linear in momenta and is not the product of a
function linear in momenta and the Hamiltonian. Then, if
$F_{additional}\not\equiv 0$  is linear or quadratic  in momenta
integral for $H_{geod}$, it must be functionally independent of
$F_{geod}$. Then, the system is resonant. Then, all geodesics are
closed. The theory of metrics all whose geodesics are closed is
well-developed, see \cite{besse}. It is known \cite{gromoll} that, on the
two-sphere, geodesics of such metrics have no self-intersections.
But if $h$ is very big, certain  geodesics of our metric must have
self-intersections: indeed, for huge $h$, the geodesics of  our
metric are very close to the geodesic of the metric
(\ref{metric1}), and by direct analysis it is easy to check that
certain  geodesics of (\ref{metric1}) do have self-intersections.

Thus, for very big $h$,  the Hamiltonian $H_{geod}$ admits no
integral of  degree one or two.

\subsection{Why  $ds^2_{geod}$  is new}
\label{4.2}

The examples coming   from Goryachev-Chaplygin are the metrics
\begin{equation}
\label{metric12} ds^2_{2} =\left(h_1-V_1\right)\left({d\theta^2}+
\frac{d\phi^2}{4+\cot^2(\theta)}\right)\, .\end{equation} Their
Hamiltonians are $$ H_2:=\frac{{p_\theta^2}+
\left({4+\cot^2(\theta)}\right){p_\phi^2}}{2(h_1-V_1)} \, ,
$$
and the integral for the system with the Hamiltonian $H_2$ is
$$
\begin{aligned}
 F_2:=&H_1p_\phi- 2p_\phi^3- V_1p_\phi \\
  &+ \left(V_1p_\phi-\frac{A_1}{2} p_\theta\cos(\phi)\cos(\theta)
+\frac{A_1}{2}{\frac {{}\,\sin \phi \left( 3\, \left( \cos  \theta
\right) ^{2}-2 \right) }{\sin \theta }}p_\phi\right) H_{2} \, .
\end{aligned}
$$

Our goal is to show that there is no diffeomorphism $D:S^2\to S^2$
that takes the metric (\ref{metric11}) to the metric (\ref{metric12})
or a constant multiple thereof.
Since the potential energy $V_1$  depends linearly  on the parameter $A_1$,
it is sufficient to show that  there exists no diffeomorphism $D:S^2\to S^2$
that takes the metric (\ref{metric11}) to the metric (\ref{metric12}).

First let us show that such diffeomorphism $D$ must be given by
the formulae $\theta_{new}=\theta_{new}(\theta)$,
$\phi_{new}=\pm\phi+\phi_0$, where $\phi_0$ is a constant.
 It is known, that the Goryachev-Chaplygin system is nonresonant on every energy level,
 see for example \cite{Orel} where the rotation function is calculated explicitely.
 Then, the geodesic flow of  (\ref{metric12}) is nonresonant as well. Then,
 the diffeomorphism $D$ must take the integral (\ref{integral12})
 to the integral (\ref{metric12}) or a constant multiple thereof.

It is known that a Riemannian metric on a (oriented) surface
defines a complex structure on it. That is, in a neighbourhood of
every point we can find a  coordinate $z=x+iy$ such that the
metric looks like $\lambda(x,y)(dx^2+dy^2)$. In such  complex
coordinates,
an  integral of degree three
has the form
\begin{equation}\label{integral}
a(z)p^3+b(z)p^2\bar p+ \bar b(z)p\bar p^2+\bar a(z) \bar p^3.
\end{equation}
Here $a,b$ are functions;
``bar" means  the complex  conjugation, $p$ is the complex momentum
 corresponding to  $z$. The
functions $a,b$ are  a-priory not assumed to be holomorphic.
Note that this form is not restrictive:  If  (\ref{integral})
is a real-valued
function, the coefficients at $\bar p^3$ and $p^2\bar p$ must be
complex-conjugate to the  coefficients at $p^3$ and $\bar p^2 p$,
respectively.

We will use the following result of Kolokoltsov from \cite{Kol};
in a weaker form, this result has been already known to Birkhoff
\cite{Birkhoff}.

\vspace{2ex}

  \noindent {\bf Lemma: }{\it  Suppose (\ref{integral}) is an integral for
the geodesic flow of $g$ and that it is not the product of the Hamiltonian
and an integral linear in velocities. Then, \begin{equation}
\label{Bir} \frac{1}{a(z)}dz^3
\end{equation}
is a meromorphic $(3,0)$-form. }

\vspace{2ex}

Evidently, the form (\ref{Bir}) has no zeros. It could have poles.
In fact, because of Abel's Lemma, it always has poles on the
sphere.

The metrics (\ref{metric11},\ref{metric12}) and the integrals
$F_{geod},F_2$ are given explicitly.  Direct calculation of the
form (\ref{Bir}) shows that the form (\ref{Bir}) for the metric
(\ref{metric11}) and for the integral  $F_{geod}$ is very similar
to the form (\ref{Bir}) for the metric (\ref{metric12}) and for the
integral  $F_{2}$: they have precisely two poles. The poles are
located at $\theta=0,\pi$.
Then, the diffeomorpism $D$ takes the points $\theta=0,\pi$ to the points $\theta=0,\pi$.

It is known  that a holomorphic diffeomorphism of the Riemann
sphere $\bar {\C}$  that preserves the points $z=0$ and $z=\infty$
is a linear transformation $z\mapsto \alpha z$. A holomorphic
diffeomorphism that interchange the points is a transformation
$z\mapsto \frac{\alpha}{ z}$. In both cases, the diffeomorphism
$D$ has the form
 $\theta_{new}=\theta_{new}(\theta)$,
$\phi_{new}=\pm\phi+\phi_0$.

Then, the pull-back of the metric (\ref{metric12}) has the form
$$(h_1-A_1 \sin\theta_{new}\sin(\pm
\phi+\phi_0))\left(\left(\frac{\partial \theta_{new}}{\partial
\theta}\right)^2d\theta^2+\frac{d\phi^2}{4+\cot
^2(\theta_{new})}\right).
$$
If this metric coincides with the
metric (\ref{metric11}),
 the coefficients of $d\theta^2$ must
coincide. Then,
 $$ \left(\frac{\partial \theta_{new}}{\partial
\theta}\right)^2(h_1-A_1\sin(\theta_{new})\sin(\pm
\phi+\phi_0))=h-\frac{A\sin\theta \cos\phi
}{\sqrt{\cos(\theta)+s}}-\frac{c}{\cos(\theta)+s},
$$
which implies  (for simplicity, we assume $\textrm{sign}(A)=\textrm{sign}(A_1)$, the case $\textrm{sign}(A)=-\textrm{sign}(A_1)$ can be triated similarly)
\begin{equation}\label{-1}
A_1\sin(\theta_{new})\left(\frac{\partial \theta_{new}}{\partial
\theta}\right)^2=\frac{A\sin\theta }{\sqrt{\cos(\theta)+s}}\, ,
\end{equation}
\begin{equation}\label{-2} h_1\left(\frac{\partial \theta_{new}}{\partial
\theta}\right)^2=\left(h-\frac{c}{\cos(\theta)+s}\right). $$
\end{equation}

Similarly, comparing coefficients of $d\phi^2$, we obtain
\begin{equation}\label{-3}
\frac{A_1\sin(\theta_{new})}{4+\cot^2\theta_{new}}=\frac{A\sin(\theta)}{\sqrt{\cos(\theta)+s}}\, ,
\end{equation}
\begin{equation}\label{-4}\frac{h_1}{4+\cot^2\theta_{new}}=
\frac{h-c/(\cos\theta+s)}{1/\sin^2\theta+G(\cos\theta)} \, .
\end{equation}

Comparing Equations (\ref{-1},\ref{-3}) and Equations
(\ref{-2},\ref{-4}), we obtain $$\left(\frac{\partial
\theta_{new}}{\partial \theta}\right)^2= {4+\cot^2\theta_{new}} \
\ \textrm{and}  \ \ \  \left(\frac{\partial \theta_{new}}{\partial
\theta}\right)^2=
\frac{4+\cot^2\theta_{new}}{1/\sin^2\theta+G(\cos\theta)}. $$
Thus, we obtain a contradiction, since clearly
${1/\sin^2\theta+G(\cos\theta)}$ is not constant.

Finally, there exists no diffeomorphism $D$ that takes the metric
(\ref{metric11}) to metric (\ref{metric12}).

\section{What to do next}

We constructed a new natural integrable Hamiltonian system on the
sphere.  It suggests the following ways of further investigation:

\begin{enumerate}

\item Construction of bifurcation diagram and description of the
topological structure of the system.

\item Finding   action-angle variables and explicit formulae for orbits.

\item Quantization of the system.

\item Painlev\'{e} analysis.

\end{enumerate}

We constructed this new system  using methods based on an
observation  from  \cite{DMT}. We will describe the methods and
how we applied them elsewhere.
It seems that it is the only new integrable system with cubic integral
on a closed manifold  containing elementary functions only
that can be found using these methods.
But still one can construct  many new local examples of metrics
with integrable geodesic flows, which we will do in a joint paper
with Tabov and Topalov.

config: arxiv


TITLE: Differentiate $\mathrm{e}^{x\arctan\left(x\right)}$
QUESTION [2 upvotes]: I was trying to differentiate the question and I did it in the following 2 ways:
METHOD $1:$
Using the cain rule, we get, $$\frac{\,d}{\,dx}\mathrm{e}^{x\arctan\left(x\right)}=\mathrm{e}^{x\arctan\left(x\right)}\frac{\,d}{\,dx}x\arctan\left(x\right)=\mathrm{e}^{x\arctan\left(x\right)}\left\{\arctan\left(x\right)+\frac{x}{x^2+1}\right\}\tag1$$
METHOD $2:$
But, when we try to do implicit differentiation, we get
$$y=\mathrm{e}^{x\arctan\left(x\right)}$$
$$\ln y=x\arctan\left(x\right)$$
$$\frac{\,d}{\,dx}\tan\left(\frac{\ln\left(y\right)}{x}\right)=\frac{\,d}{\,dx}x$$
$$\frac{1}{\cos^2\left(\frac{\ln\left(y\right)}{x}\right)}\frac{1}{xy}y’=1$$
$$y’=\cos^2\left(\tan^{-1}\left(x\right)\right)x\mathrm{e}^{x\arctan\left(x\right)}$$
$$y’=\frac{x}{x^2+1}\mathrm{e}^{x\arctan\left(x\right)}$$
But these give different answers, please help me where have I gone wrong.

REPLY [2 votes]: For the implicit differentiation:
$$\frac {y'}{y} = \arctan(x) + \frac{x}{x^2+1} \\
y' = e^{x\arctan(x)} \left( \arctan(x) + \frac{x}{x^2+1} \right)$$


TITLE: A quotient map from $[0,1]$ to $S^1$
QUESTION [6 upvotes]: I would like to show that the function $f(x) = (\textrm{cos}2 \pi x, \textrm{sin}2 \pi x)$ is a quotient map; I have already shown that it is surjective and continuous (the latter by invoking the universal property for functions into a product topology (I am considering $S^1$ as a subspace of $\mathbb{R} \times \mathbb{R}$)). However, I'm stuck trying to prove the final condition for $f$ to be a quotient map. Here's my work so far:
Let $U \subset S^1$. Suppose $f^{-1}[U]$ is open in $[0,1]$. Then we need to show that $U$ is open in $S^1$. Let $\bar{y} \in U$; either $\bar{y} = (1,0)$ or $\bar{y} \neq (1,0)$. If $\bar{y} = (1,0)$, then by using the openness of $f^{-1}[U]$, we can deduce that there exists $\epsilon, \epsilon' \in \mathbb{R}_{> 0}$ such that $[0,\epsilon) \cup (\epsilon',1] \subset f^{-1}[U]$ (since $f^{-1}[\{ (1,0) \}] = \{0, 1 \}$). Similarly, if $\bar{y} \neq (1,0)$, there exist $\delta, \delta'\in \mathbb{R}_{> 0}$ such that $(\delta,\delta') \subset f^{-1}[U]$. Of course these sets, $[0,\epsilon) \cup (\epsilon',1]$ and $(\delta,\delta')$ are open in $[0,1]$.
How do I (or can I) proceed from here to show that $U$ is open in $S^1$? On the other hand, I'd also love to hear of some more general methods for showing that the function is a quotient map (maybe certain theorems or something). Thanks in advance for the help!

REPLY [1 votes]: Fix a set $U\subset S^1$ such that $f^{-1}(U)$ is open, and a point $z \in U$. Suppose $z$ has positive second coordinate for the moment. Then there is a unique point in $f^{-1}(z)$ which we'll call $x$, and by the openness of $f^{-1}(U)$ an interval $I=(x-\epsilon, x+\epsilon)\subseteq f^{-1}(U)\cap (0,1/2)$. Consider $f$ restricted to $[x-{\epsilon}/2, x+{\epsilon}/2]$. The function $\cos(2\pi x)$ has a minimum and maximum on this interval, as it is closed and bounded. In fact, by the properties of $I$ above, there are no critical points in the interval so the min and max must occur on the boundary. We will call the min and max $x_0$ and $x_1$. Write $z=(z_0, z_1)$. We claim that, $V=S^1 \cap [(x_0, x_1)\times (0, z_1+1)]$ is an open set containing $z$ and contained in $U$. Clearly it is open by the definition of the subspace topology.  By the discussion above, $z_0$ is not the min or max so $x_0<z_0<x_1$, and this gives $z\in V$. Now take $(a, \sqrt{1-a^2})\in V\subseteq S^1$. Since $x_0<a<x_1$, the intermediate value theorem gives that $\cos(2\pi c)=a$ for some $c\in I$. But then $\sin(2\pi c)=\pm \sqrt{1-a^2}$ and it must be the plus sign since $c\in I$. This gives $(a, \sqrt{1-a^2})=f(c)$, and since $c\in I\subseteq f^{-1}(U)$, we have shown that $V\subseteq U$. What we have shown is that $z$ has an open neighborhood around it which is contained in $U$. We want to extend this to all possible $z$, not just ones with positive second coordinate. $Mutatis$ $mutandis$, the same proof goes through for $z$ with second coordinate negative. (E.g., use $(z_1-1, 0)$ in the definition of $V$ instead.) I will leave it to you to modify the details for the remaining two points. You will want to use sine instead of cosine if you do the above min/max argument in these cases. This will show $U$ is open and complete the proof.


TITLE: Eventually increasing or decreasing sequence of ratios
QUESTION [0 upvotes]: Let $(a_n)_{n\geq 0}$ be a positive sequence of real numbers. I have two questions about sequences that are related to log-convex and log-concave. I'll just copy the necessary part in an article (Lemma 4.1) I'm reading
Question 1:

Suppose that $(a_{n+1}/a_n)_{n\geq 0}$ is eventually increasing to $\lambda\in (1,\infty]$. Then the proof says: for any $\lambda_0\in (1,\lambda)$, we have $a_{n+1}\geq \lambda_0 a_n$ for $n$ sufficiently large. Why?

Question 2:

Suppose that $(a_{n+1}/a_n)_{n\geq 0}$ is eventually decreasing to $\lambda\in [0,\infty)$. Then, the proof says: if $\lambda\in[0,1)$, then $\sum a_n<\infty$. Why?

REPLY [1 votes]: The first statement says that $a_{n+1}/a_n \le \lambda$ but
$$
\lim_{n \to \infty} \frac{a_{n+1}}{a_n} = \lambda \in (1,\infty).
$$
So if $1 < \lambda_0 < \lambda$, eventually (for $n$ large enough), we will have
$$
\frac{a_{n+1}}{a_n} > \lambda_0 \iff a_{n+1} > \lambda_0 a_n.
$$

Here,
$$
\lim_{n \to \infty} \frac{a_{n+1}}{a_n} = \lambda \in [0,1)
$$
so analogously letting $0 \le \lambda \le \mu < 1$, for $n$ large enough you will get $a_{n+1} < \mu a_n$, and from that $n$ onwards, we can bound $\sum a_n$ by a geometric series.

UPDATE

Let $(b_n)_{n = 0}^\infty$ be a sequence with $b_n \le L \in (1,\infty)$ and assume $\lim_n b_n \to L$. Let $\ell \in (1,L)$. Prove that for $n$ large enough we have $b_n > \ell$.

Proof
Since $\lim_n b_n \to L$, there must exist $N \in \mathbb{N}$ such that $\forall \epsilon >0$ we have $|b_n - L| < \epsilon$ whenever $n > N$. In particular, pick $\epsilon = (L- \ell)/2$. Hence, there must exists $N \in \mathbb{N}$ such that for all $n > N$ we have $|b_n - L| < \epsilon$. Since $b_n < L$, we have $|b_n - L| = L-b_n$ and our inequality becomes
$$L -b_n < \frac{L - \ell}{2}.$$
Eliminating $L/2$ and solving for $b_n$ on the LHS we get
$$
b_n > L - \frac{L - \ell}{2} = \frac{L + \ell}{2} > \frac{\ell + \ell}{2} = \ell.
$$


TITLE: Differential on tensor product of $A_\infty$ modules
QUESTION [2 upvotes]: Let $A$ be an $A_\infty$-algebra over a commutative ring $k$, and $M$ is a left $A$-module and $N$ is a right $A$ module. By modules I mean $A_\infty$-modules. Then we can define $A_\infty$ tensor product $M \otimes_A^{\infty} N$. The construction is briefly described in Keller's "Introduction to $A_\infty$ algebras and modules", where it is claimed that it is $M \otimes_k T(A) \otimes_k N$ with some differential. What is the formula for the differential? I'm also interested in special case: $A$ is an associative algebra or a DG algebra. Are there any papers where I can find detailed description of the $A_\infty$ tensor product?

REPLY [1 votes]: See Section 2.7 in this paper of Rinna Anno and Timothy Logvinenko. The construction is given explicitly.
Recall that an $A_\infty$-algebra $A$ is the same as the quasi-free dg coalgebra $B_\infty A$, and if $M$ is a complex, then an $A_\infty$-module structure on $M$ is the same as a differential on the free comodule $B_\infty A \otimes M$.
Now you can take cotensor products of comodules, just like tensor products. The end result is that one $B_\infty A$ cancels leaving you with $N \otimes B_\infty A \otimes M$, and if you follow the isomorphism, you should get an explicit form of the differential making $M\otimes N$ an $A_\infty$-comodule.


text:
\section{Open Subset of Locally Connected Space is Locally Connected}
Tags: Topology, Locally Connected Spaces

\begin{theorem}
Let $T - \left({S, \tau}\right)$ be a [[Definition:Locally Connected Space|locally connected]] [[Definition:Topological Space|topological space]].
Let $U \subset S$ be [[Definition:Open Set (Topology)|open]] in $T$.
Then $U$ is [[Definition:Locally Connected Space|locally connected]].
\end{theorem}

config: wiki


text:
\begin{document}

\title{The Look-and-Say The Biggest Sequence Eventually Cycles}

\author{
    \'Eric Brier\inst{2} \and Rémi Géraud-Stewart\inst{1} \and David Naccache\inst{1}\and Alessandro Pacco\inst{1} \and Emanuele Troiani\inst{1}
}

\institute{
    ÉNS (DI), Information Security Group,
CNRS, PSL Research University, 75005, Paris, France.\\
45 rue d'Ulm, 75230, Paris \textsc{cedex} 05, France\\
\email{\url{remi.geraud@ens.fr}},~~~~
\email{\url{given\_name.family\_name@ens.fr}}
	\and
	Ingenico Laboratories, 75015, Paris, France.\\
	\email{\url{eric.brier@ingenico.com}}\\
}
\maketitle

\begin{abstract}
In this paper we consider a variant of Conway's sequence (\textsf{OEIS A005150, A006715}) defined as follows: the next term in the sequence is obtained by considering contiguous runs of digits, and rewriting them as $ab$ where $b$ is the digit and $a$ is the \emph{maximum} of $b$ and the run's length. We dub this the \enquote{look-and-say the biggest} ($\lsb$) sequence.

Conway's sequence is very similar ($b$ is just the run's length). For any starting value except \dig{22}, Conway's sequence grows exponentially: the ration of lengths converges to a known constant $\lambda$. We show that $\lsb$ does not: for every starting value, $\lsb$ eventually reaches a cycle. Furthermore, all cycles have a period of at most 9.
\end{abstract}

\section{Introduction}

The look-and-say (\textsf{LS}) sequence \cite{conway2012book}, also known as the \emph{Morris} or the \emph{Conway sequence} \cite{conway1987weird,hilgemeier1996one,ekhad1997proof} is a recreational integer sequence having very intriguing properties. A \textsf{LS} sequence is obtained iteratively by reading off the digits of the current value, and counting the number of digits in groups of the identical digit.\smallskip

Following Conway's work, numerous variants of \textsf{LS} sequences were proposed and studied, e.g., Pea Pattern sequences \cite{kowacs2017studies,pea}, Sloane's sequences\cite{slo} or Oldenburger--Kolakoski sequences \cite{kola,kola2,lagarias1992number} (\textsf{OEIS A000002}).\smallskip

In this paper we consider a variant of $\textsf{LS}$ sequence: the next term in the sequence is obtained by considering contiguous runs of digits, and rewriting them as $ab$ where $b$ is the digit and $a$ is the \emph{maximum} of $b$ and the run's length (this is formally defined further below). We dub this the \enquote{look-and-say the biggest} ($\lsb$) sequence. An $\lsb$ sequence is therefore very similar to a \textsf{LS} sequence; however it behaves very differently.

Indeed, Conway showed \cite{conway1987weird} that for all starting values (except \dig{22}), \textsf{LS} sequences produce ever-growing numbers, with a growth ratio converging to some constant $\lambda$ (which is the root of an explicit degree-$71$ polynomial). As we will show, however, for \emph{every} starting value, $\lsb$ sequences eventually reach a cycle. When they do, this cycle repeats itself in at most 9 iterations (\Cref{thm:sam}).

\section{Notations and definitions}
In this paper we assume that numbers are written in base 10. Any integer $T$ can thus be written $T = t_1t_2 \cdots t_k$ with $t_1, \dotsc, t_k \in \{{\dig{0}}, {\dig{1}}, \dotsc, {\dig{9}}\}$. To avoid any ambiguity, $ab$ will denote the \emph{concatenation} of the numbers $a$ and $b$; accordingly $a^b$ indicates that a digit $a$ is repeated $b$ times. If we want to emphasise concatenation we use $a\|b$ instead of $ab$.

\begin{definition}[Run-length representation]
Let $T\in \mathbb{N}^*$, we can write
\begin{equation*}
    T = \underbrace{a_1\ldots a_1}_{n_1}\underbrace{a_2\ldots a_2}_{n_2}\ldots\underbrace{a_k\ldots a_k}_{n_k}
\end{equation*}
with $a_1\neq a_2, a_2\neq a_3, \dotsc, a_{k-1}\neq a_{k}$. The \emph{run-length representation} of $T$ is the sequence $\rl(T)= a_1^{n_1}a_2^{n_2} \cdots a_k^{n_k}$. Conversely, any finite sequence of couples $(a_i, b_i)_i$ where $a \in \mathbb N^*$ and ${\dig{0}}\leq b_i\leq {\dig{9}}$ is such that $b_{i-1}\neq b_i\neq b_{i+1}$, corresponds to an integer with run-length representation $(a_i^{b_i})_i$.
\end{definition}

Note that the run-length representation of an integer is unique.

\begin{definition}[Pieces]
If $N = (a_i^{b_i})$ is a run-length encoded integer, we call each $a_i^{b_i}$ a \emph{piece} of $N$.
\end{definition}

\begin{definition}[Look-and-say-again sequence]
Let $T_0$ be a decimal digit, and for each $T_n$ define
\begin{equation*}
    T_{n+1} = n_1n_1a_1a_1n_2n_2a_2a_2\cdots n_kn_ka_ka_k.
\end{equation*}
where $(a_i^{n_i})_i = \rl(T_n)$. We call the sequence $(T_k)_{k \in \mathbb N}$ the \emph{look-and-say-again sequence} of seed $T_0$, and denote it by $\lsa(T_0)$.
\end{definition}

\begin{definition}[Look-and-say-the-biggest sequence]
Let $S_0\in\mathbb{N}^*$, and for every integer $S_n\in\mathbb{N}^*$, $(a_i^{n_i})_i = \rl(S_n)$, let
\begin{equation*}
    S_{n+1} = \max(n_1,a_1)a_1\max(n_2,a_2)a_2 \cdots \max(n_k,a_k)a_k.
\end{equation*}
We call $(S_n)_{n \in \mathbb N}$ the \emph{look-and-say-the-biggest} sequence of seed $S_0$, and denote it by $\lsb(S_0)$.
\end{definition}

\begin{example}
$\lsb(1) =
\small{
    \dig{1}\to\dig{11}\to\dig{21}\to\dig{2211}\to\dig{2221}\to\dig{3211}\to\dig{332211}\to\dig{332221}\leftrightarrows\dig{333211}}$
\end{example}

\section{The look-and-say-the-biggest sequence}

\begin{theorem}[Eventual periodicity]\label{thm:sam}
Let $s$ be an integer, then the sequence $\lsb(s)$ is eventually periodic, of period $\tau \leq 9$.
\end{theorem}
To prove this result we introduce several useful definitions and lemmas.

\begin{definition}[Maxmaps]
Let $a_i^{n_i}$ be a piece, we define the \emph{partial maxmap}:
\begin{equation*}
    z: a_i^{n_i} \mapsto \max(a_i, n_i) a_i
\end{equation*}

which sends a piece to an integer. We extend this definition to work on integers: if $(a_i^{n_i})_i = \rl(N)$, we define the \emph{maxmap}:
\begin{equation*}
    Z: N \mapsto z(a_1^{n_1})z(a_2^{n_2}) \cdots z(a_k^{n_k})
\end{equation*}
which maps integers to integers. Finally, for every integer $m > 0$, we write $Z^m = Z \circ Z \circ \cdots \circ Z$,
where $Z$ appears $m$ times in the composition.

\end{definition}
\begin{example}
$Z(\dig{11193222}) = \dig{31993332}$.
\end{example}

\begin{remark}
With these notions in place, \Cref{thm:sam} can be reformulated as follows: for any integer $s$,
if $s$ does not contain more than 9 continuous identical digits, then $s \in \{Z^m(s) \mid 1 \leq m \leq 8\}$.
\end{remark}

\begin{remark}
Assume that $s$ contains more than $9$ consecutive identical digits $a$, but fewer than $100$; write this number $n$. Then the corresponding piece in the run-length representation is $a^n$, which will be mapped by $z$ to $na$ (as $n > a$ by assumption). But $n$ itself is made of two digits so that $na$ contains at most 3 consecutive identical digits. By iteratively applying $Z$ to a number having more than 9 consecutive digits, we eventually obtain a number with at most 9 consecutive digits.
\Cref{thm:sam} will therefore follow from this observation and the following result:
\end{remark}

\begin{lemma}\label{lem:periodweak}
Let $s \in \mathbb N$, $(a_i^{n_i})_i = \rl(s)$. If $n_i \leq 9$ for all $i$ then the sequence $Z^n(s)$ periodic, of period $\tau < 9$.
\end{lemma}

\begin{definition}[Kid and Adult Types]
We split digits into two sets: digits that are smaller or equal to $3$ are \emph{kid type}, the others are \emph{adult type}. Pieces $a^n$ where $a$ is a kid (resp. adult) are of type kid (resp. adult). Numbers made \emph{only} of type kid (resp. adult) digits are of type kid (resp. adult).
\end{definition}

\begin{lemma}\label{lem:ZtypeB}
$Z$ maps adult type numbers to adult type numbers.
 \end{lemma}
 \begin{proof}[of \Cref{lem:ZtypeB}]
 If $a^n$ is an adult piece, $z(a^n) = \max(n, a)a$ is an adult number, since $a$ is an adult digit by hypothesis and $\max(n, a)$ is adult if either numbers is. The result on $Z$ follows.
\qed
\end{proof}

\begin{lemma}[Fixed points of $Z$, sufficient condition]\label{lem:fixpt}
Let $s$ be an integer, $(a_i^{n_i})_i = \rl(s)$. If $n_i = 2, a_i \geq \dig{2}$ for all $i$ then $Z(s) = s$.
\end{lemma}
\begin{proof}[of \Cref{lem:fixpt}]
We have, for all $i$, $z(a_i^{n_i}) = \max(n_i, a_i)a_i = a_ia_i$. The result on $Z$ follows.
\qed
\end{proof}

\begin{theorem}[Adult seeds give constant sequences]\label{thm:typeB}
Let $s \in \mathbb N$ be adult, and assume that $s$ does not have more than 9 consecutive identical digits, then $Z^3(s) = Z^2(s)$. In particular, the sequence $\lsb(s)$ is constant from the third term on.
\end{theorem}
\begin{proof}[of \Cref{thm:typeB}]
Let $(a_i^{n_i})_i = \rl(s)$. By hypothesis, $a_i$ are adult and $n_i \leq 9$.
We have
\begin{equation*}
    z(a_i^{n_i}) =
    \begin{cases}
    a_ia_i & \text{if $n_i \leq a_i$} \\
    n_ia_i & \text{otherwise}
    \end{cases}
\end{equation*}
In the first case, $z(a_i^{n_i})$ is an adult number of length 2, and in the second case $n_i > a_i$ so that we again have an adult of length 2. Applying $Z$ to $s$, it is possible that two consecutive digits (coming from different pieces of $s$) are identical, but no more: as a result, if we write $(b_i^{m_i})_i =  \rl(Z(s))$, then $m_i \leq 3$ and $b_i$ is adult.

Therefore, $Z^2(s)$ satisfies the conditions of \Cref{lem:fixpt}, yielding $Z^3(s) = Z^2(s)$.
\qed
\end{proof}

\begin{remark}
\Cref{thm:typeB} proves \Cref{lem:periodweak}, and therefore \Cref{thm:sam}, for adult integers. We now turn our attention to the remaining case of kid integers.
\end{remark}

\begin{lemma}\label{lem:fixptA}
Let $s \in \mathbb N$ of kid type and assume that no digit appears more than 3 times consecutively in $s$. Then $Z(s)$ is kid and no digit appears more than 3 times consecutively in it.
\end{lemma}

\begin{proof}[of \Cref{lem:fixptA}]
Let $(n_i, a_i)_i = \rl(s)$, we can exhaust all possibilities:
\begin{align*}
      \dig{0}^1 & \xrightarrow{z} \dig{10} & \dig{0}^2 & \xrightarrow{z} \dig{20}
    & \dig{0}^3 & \xrightarrow{z} \dig{30}
    & \dig{1}^1 & \xrightarrow{z} \dig{11}
    & \dig{1}^2 & \xrightarrow{z} \dig{21}
    & \dig{1}^3 & \xrightarrow{z} \dig{31} \\
      \dig{2}^1 & \xrightarrow{z} \dig{22}
    & \dig{2}^2 & \xrightarrow{z} \dig{22}
    & \dig{2}^3 & \xrightarrow{z} \dig{32}
    & \dig{3}^1 & \xrightarrow{z} \dig{33}
    & \dig{3}^2 & \xrightarrow{z} \dig{33}
    & \dig{3}^3 & \xrightarrow{z} \dig{33}
\end{align*}
Clearly, $z(a_i^{n_i})$ is kid and of length 2. Furthermore, for $Z$ to contain more than 3 consecutive identical digits, $\rl(s)$ would need to contain a sub-sequence of the form $ \beta^{\alpha}\beta^{\alpha'}$ with $\alpha, \alpha'\in \{1,2,3\}$ and $ \beta \in \{\dig{1},\dig{2},\dig{3}\}$. This is impossible by definition of the run-length representation. \qed
\end{proof}

\begin{lemma}[Last digit]\label{lem:lastdigit}

Let $s$ be an integer, then the last digit of $Z(s)$ is the same as the last digit of $s$.
\end{lemma}
\begin{proof}
The proof is immediate from the definition of $Z$. \qed
\end{proof}

\begin{theorem}[Small kid seeds]\label{thm:smalltypeA}
Consider again a kid integer $s$, with no more than three consecutive identical digits, then the sequence $Z^n(s)$ loops after at most $7$ iterations, i.e. $s \in \{Z^m(s) \mid 1 \leq m \leq 8\}$.
\end{theorem}

\begin{proof}
\Cref{fig:smallnumbers} shows how $Z$ maps each piece of the integers satisfying the theorem's conditions. We notice that a fixed point is reached in one step for $\dig{2}$, $\dig{22}$, $\dig{3}$, $\dig{33}$, $\dig{333}$, and the only end nodes that are not fixed points are $\dig{10}$, $\dig{20}$, $\dig{30}$, $\dig{21}$, $\dig{32}$, $\dig{31}$ --- these are the ones we shall focus on.
We list the successive mappings of these three nodes up to the point before they enter a loop in \Cref{tab:fossils}, and refer to the list of integers in that table as \emph{fossil integers}.

\begin{figure}[!th]
    \centering
    \input{img/forest}
    \caption{Effect of $Z$ on small kid integers.} \label{fig:smallnumbers}
\end{figure}
\begin{table}[!th]
\centering
\caption{Cycles from small kid seeds. We call the numbers appearing here \emph{fossils}.}\label{tab:fossils}
\begin{tabular}{cc cc cc cc cc cc }
&&&&&&&&&& Steps & Period\\\toprule
$\dig{32}$&$\to$&$\dig{3322}$&\hspace{-0.3cm}$\bft$&&&&&&&1&1\\\midrule
$\dig{31}$&$\to$&\hspace{-0.3cm}$\dig{3311}$&\hspace{-0.7cm}$\to$&\hspace{-1.2cm}$\dig{3321}$&$\hspace{-1.7cm}\to$&\hspace{-2.2cm}$\dig{332211}$ &&&&&\\
&&&&&&\hspace{-2.2cm}$\downarrow$&&&&&\\
&&&&&&\hspace{-2.2cm}$\dig{332221}$&$\hspace{-2.6cm}\leftrightarrows$&$\hspace{-1.4cm}\dig{333211}$&&5&2\\
&&&&&&\hspace{-2.2cm}$\uparrow$&&&&&\\
$\dig{21}$&$\to$&\hspace{-0.3cm}$\dig{2211}$&$\hspace{-0.7cm}\to$&\hspace{-1.2cm}$\dig{2221}$&$\hspace{-1.7cm}\to$&\hspace{-2.2cm}$\dig{3211}$   &&&&& \\\midrule
$\dig{00}$&&$\dig{221110}$&$\to$&\hspace{-0.16cm}$\dig{223110}$&&$\dig{2233322110}$&&&&&\\
$\downarrow$&&$\uparrow$&&$\downarrow$&&$\downuparrows$&&&&7&2\\
$\dig{20}$&$\to$&$\dig{2210}$&&\hspace{-0.16cm}$\dig{22332110}$&$\to$&$\dig{2233222110}$&&&&&\\\midrule
$\dig{0}$    &       & $\dig{3110}$ & $\to$ & \hspace{-0.16cm}$\dig{332110}$ &&&&&&& \\
$\downarrow$&&$\uparrow$&&$\downarrow$&&&&&&6&2\\
$\dig{10}$   & $\to$ & $\dig{1110}$ &       & \hspace{-0.16cm}$\dig{33222110}$ & $\leftrightarrows$ & \hspace{-0.3cm}$\dig{33322110}$ &&&&& \\\midrule
$\dig{000}$&       & $\dig{331110}$ & $\to$& \hspace{-0.16cm}$\dig{333110}$ &       &\hspace{-0.3cm}$\dig{33222110}$\\
$\downarrow$&&$\uparrow$&&$\downarrow$&&$\downuparrows$&&&&7&2\\
$\dig{30}$ & $\to$ & $\dig{3310}$   &      &  \hspace{-0.16cm}$\dig{332110}$ & $\to$&\hspace{-0.3cm}$\dig{33222110}$
\\
\bottomrule
\end{tabular}
\end{table}

Assume that $s = s_0 \| p \| s_1$, with $s_0, p, s_1$ integers such that $Z(s_i) = s_i$, and such that $s_0$ does not end with $p$'s first digit and $s_1$ does not start with $p$'s last digit. If $p$ is not fossil then $Z(p) = p$ and therefore $Z(s) = s$. Otherwise,
\begin{itemize}
    \item For $Z(p)$ to start with $\dig{3}$, we must have $p$ beginning with $\dig{3}b$, $\dig{33}b$, with $b \neq\dig{3}$, or three consecutive digits $aaa$. Then $Z(p)$ starts with $\dig{3}a$ and $Z^2(p)$ starts with $\dig{33}$ which is not fossil. By \Cref{lem:lastdigit}, the first digit of $Z(s_1)$ and the last digit of $Z(p)$ differ. As a result after two iterations of $Z$ we are in a situation $s' = s_0'\|p'\|s_1$ where
    $s_0' = s_0\|\dig{33}$ and $p'$ does not begin with $\dig{3}$ nor three consecutive digits.
    \item For $Z(p)$ to start with $\dig{2}$, we must have $p$ beginning with $\dig{2}b$ with $b < \dig{2}$, or two consecutive digits $aa$ with $a \leq \dig{2}$. Then $Z(p)$ starts with $\dig{22}$ or $\dig{2}a$ respectively, and $Z^2(p)$ starts with $\dig{22}$. As above, after two iterations of $Z$ we are in a situation $s' = s_0'\|p'\|s_1$ where
    $s_0' = s_0\|\dig{22}$ and $p'$ does not begin with $\dig{2}$ nor two consecutive digits.
    \item For $Z(p)$ to start with $\dig{1}$, we must have $p$ beginning with $ab$ with $a \leq \dig{1}$ and $b > \dig{1}$. Then $Z(p)$ starts with $\dig{10}$ or $\dig{11}$, and $Z^2(p)$ starts with $\dig{11}$ or $\dig{21}$ respectively. Then $Z^4(p)$ or $Z^3(p)$ respectively starts with $\dig{22}$. Thus after three or four iterations of $Z$ we are in a situation $s' = s_0'\|p'\|s_1$ where
    $s_0' = s_0\|\dig{22}$ and $p'$ does not begin with an isolated digit.
\end{itemize}
Since $Z(p)$ cannot start with $\dig{0}$, these are the only cases. Therefore, after at most $4 + 2 + 2 = 8$ iterations there remain no possibility for $p$. In other terms $Z^m(s) = s$ for $m \leq 8$.

\iffalse

Let's take a section of the sentence that contains only the sentences listed above, cut in a way not to separate letters. If we show that no matter what there is before or after the section the evolution is the same we have proven the result.
If the characters before and after the section are different than the starting or ending one then the mapping of the section doesn't change.

We only start the discussion after one mapping.
After one iteration every sentence starts with either a \dig{1}, \dig{2} or a \dig{3} and ends with either a \dig{0} or a \dig{1}.

Using the lemma we get that the only way to have a starting 3 after one iteration is because there was a \([3^a]\) letter before. That means that after one iteration the letter becomes \([3^2]\) as the starting part of the section didn't have a 3 (otherwise the letter would have been included), so now it has only \([3^1]\). As \([3^1]\to[3^2]\) and \([3^3]\to[3^2]\) having 3s is indifferent.

The same reasoning applies to a starting \dig{2} as it comes from \([2^a]\). In this case we have two cases: either we come from \([2^3]\) or from \([2^1]\) and \([2^2]\). In the first case we have a single starting 2 and as before a single 2 in the section. As \([2^1]\to[2^2]\) and \([2^2]\to[2^2]\) it is indifferent. In the second case we have two starting \dig{2} and a single \dig{2}. It occurs only in two situations: in the evolution of \([1,1]\) and  \([0^2]\).
Cases:
\([2^3],[1,1]\to[3,2],[2,1]\to[3,3,2,2,1,1]\)
\([2^3],[0^2]\to[3,2],[2,0]\to[3,3,2,2,1,0]\) so in both cases we end up in the same node after two iterations.

The ending \dig{0}s are trivial as there is no sentence whose evolved start with\dig{0}.

All the previous cases don't make the iteration longer

The ending 1s can only be complemented with sentences evolved from \([0]\to[1,0]\).
Consider the evolution:
\[[1,1,0]\to[2,1,1,0]\to [2,2,2,1,1,0]\to [3,2,2,1,1,0]\to [3,3,2,2,2,1,1,0]\]
We thus see that we end up in one of he previous cases in at most two iterations. Notice that this also proves the starting 1.

We can count how many iterations it takes to get to a cycle.

As a result of this, since we showed that all the sections end up in a cycle after at most 7 iterations, than the whole sentence end up in a cycle after 7 iterations.

\fi

\qed
\end{proof}

We are now ready to complete the proof:
\begin{proof}[of \cref{lem:periodweak,thm:sam}]
We have proven the result for adult seeds (\Cref{thm:typeB}) and for certain kid seeds (\Cref{thm:smalltypeA}).

Let $s$ be an integer, $(a_i^{n_i})_i = \rl(s)$. We partition the pieces $(a_i^{n_i})_i$ into kid type and adult types. The effect of $Z$ on kid pieces is the one that needs attention: either $n_i \leq 3$, or $n_i > 3$. In the second case, the effect of $Z$ is to introduce the adult digit $n_i$. Consider the type of pieces $(i-1)$ and $(i+1)$:
\begin{itemize}
    \item If piece $(i-1)$ is adult: then $n_i$ will fuse with the result of $z(a_{i-1}^{n_{i-1}})$ into a adult piece;
    \item Otherwise $n_i$ will be its own new adult piece, inserted between the result of $z$ on piece $(i-1)$ and the $a_i$.
\end{itemize}
As a result, after applying $Z$ to $s$, we can partition $Z(s)$ as a concatenation of kid integers having no more than 3 consecutive identical digits, and adult integers. These correspond in particular to disjoint run-length representations, so that $Z$ acts on them independently.

We have shown that the action of $Z$ on such integers preserves their properties, and that $Z$ reaches a cycle in at most 7 iterations. Accounting for the extra application of $Z$ at the beginning of this proof, we have the claimed result.
\qed
\end{proof}

\begin{remark}
\Cref{thm:sam} shows that we eventually reach a cycle; \Cref{lem:periodweak} shows that for certain integers (which do not repeat any digit more than 9 times in a row) this cycle is reached quickly. Nevertheless, some integers that \emph{do not} satisfy the conditions of \Cref{lem:periodweak} can still reach a cycle quickly: for instance, $\dig{2}^{22} \to \dig{222} \to \dig{3322}$ (two iterations).
This brings the following question: what is the smallest integer $y$ so that $\lsb(y)$ takes \emph{more} than $8$ iterations to reach a cycle?
\end{remark}

\begin{conjecture}\label{conj}
The smallest integer $y$ so that $\lsb(y)$ takes $9$ iterations to reach a cycle is $y = \dig{2}^x$ with $x = \dig{3}^{11}$. If we now (temporarily) use the standard multiplicative notation $a^b = \underbrace{a \times a \times \cdots \times a}_\text{$b$ times}$, then
\begin{equation*}
    y = \frac{2}{9}\left(10^{\left(10^{11}-1\right)/3}-1\right) \simeq 10^{10^{10.52}}.
\end{equation*}
\end{conjecture}

The convergence process in 9 steps is:

\begin{center}
{\small
\begin{tabular}{r}
$y=\dig{2}^x
    \to x\dig{2} \to \dig{11312} \to \dig{21331122} \to \dig{2211332122} \to \dig{222133221122}
    \to \dig{321133222122} \to \dig{33222133321122}$\\
    $\downuparrows$~~~~~~~~~~~~~\\
    $\dig{33321133222122}$
\end{tabular}}
\end{center}

\section{Open questions}
Although every $\lsb$ sequence cycles, it remains an open question to fully enumerate and classify the limit cycles. It also remains open to extend Conjecture~\ref{conj} and determine for every $n > 0$ the values $\sigma_n$ defined as the smallest positive integer such that $\lsb(\sigma_n)$ reaches a cycle in exactly $n$ iterations.

\bibliographystyle{alpha}
\bibliography{conway.bib}
\end{document}