text:
\begin{document}
\title{A genus zero Lefschetz fibration on the Akbulut cork}
\author{Takuya Ukida}
\address{Department of Mathematics, Tokyo Institute of Technology,
2-12-1 Oh-okayama, Meguro-ku, Tokyo 152-8551, Japan}
\email{ukida.t.aa@m.titech.ac.jp}
\date{}
\thanks{The author was partially supported by Research Fellow of Japan
Society for the Promotion of Science}
\begin{abstract}
    We first construct a genus zero positive allowable Lefschetz fibration
    over the disk (a genus zero PALF for short) on the Akbulut cork
    and describe the monodromy as a positive factorization
    in the mapping class group of a surface of genus zero with five boundary components.
    We then construct genus zero PALFs on infinitely many exotic pairs of
    compact Stein surfaces such that one is a cork twist of the other along an Akbulut cork.
    The difference of smooth structures on each of exotic pairs of compact Stein surface
    is interpreted as the difference of the corresponding
    positive factorizations in the mapping class group
    of a common surface of genus zero.
\end{abstract}
\maketitle

    \section{Introduction}
    Gompf \cite{Go} proved that compact Stein surfaces can be characterized in terms of
    handle decompositions, or more precisely, Kirby diagrams.
    Akbulut and Yasui \cite{AY1} introduced corks and plugs,
    which are compact Stein surfaces themselves, and constructed
    various exotic smooth structures on Stein surfaces by using cork twists and plug twists
    together with Gompf's characterization and Seiberg-Witten invariants. On the other hand,
    Loi and Piergallini \cite{LP} proved that every compact Stein surface admits a positive allowable
    Lefschetz fibration over $D^2$ (a PALF for short), which enables us to investigate compact
    Stein surfaces in terms of positive factorizations in mapping class groups
    (see also Akbulut and Ozbagci \cite{AO}, Akbulut and Arikan \cite{AA}).

    In this paper we first construct a genus zero PALF on the Akbulut cork
    and describe the monodromy as a positive factorization
    in the mapping class group of a fiber.
    The Akbulut cork is the pair $(W_1,f_1)$ of the manifold $W_1$ shown
    in Figure \ref{AkbulutCork}
    and an involution $f_1$ on $W_1$ (see Definition \ref{def:AkbulutCork}).
    The manifold $W_1$ is often called the Mazur manifold.

    \begin{Thm}\label{main1}
        The manifold $W_{1}$
        admits a genus zero PALF.
        The monodromy of the PALF is described by the
        factorization
        $t_{\alpha_4} t_{\alpha_3} t_{\alpha_2} t_{\alpha_1}$,
        where $t_\alpha$ is a right-handed Dehn twist along a
        simple closed curve $\alpha$ on a fiber and
        $\alpha_4, \ldots, \alpha_1$ are simple closed curves
        shown in Figure \ref{PALF_of_the_Akbulut_cork}.
    \end{Thm}

    \begin{figure}[htbp]
        \centering
        \includegraphics[width=20mm]{01_Akbulut_cork_KirbyDiagram.eps}
        \caption{Kirby diagram for $W_1$.}
        \label{AkbulutCork}
    \end{figure}

    \begin{figure}[htbp]
        \centering
        \includegraphics[width=70mm]{02_genus0_PALF_of_the_AkbulutCork.eps}
        \caption{Vanishing cycles of a genus zero PALF on $W_1$.}
        \label{PALF_of_the_Akbulut_cork}
    \end{figure}

    Note that the genus of a PALF on the manifold $W_1$
    which is obtained by applying any known method
    (cf. \cite{AO} and \cite{AA} ) is much larger than zero.

    Akbulut and Yasui \cite{AY2} proved that the compact Stein surfaces
    $C_1(m,1,3,0)$ and $C_2(m,1,3,0)$ $(m\leq -5)$
    shown in Figure \ref{Kirby_diag_of_C1} and Figure \ref{Kirby_diag_of_C2}
    are homeomorphic but not diffeomorphic to each other.
    It is easily seen that $C_2(m,1,3,0)$ is a cork twist of $C_1(m,1,3,0)$ along an obvious Akbulut cork.

    We next construct PALFs with the same fiber on
    $C_1(m,1,3,0)$ and $C_2(m,1,3,0)$ for each integer $m$ less than $-4$.
    The common fiber is a surface of genus zero with $-m+5$ boundary components.

    \begin{figure}[htbp]
        \centering
        \includegraphics[width=30mm]{03_KirbyDaigram_of_C1.eps}
        \caption{Kirby diagram for $C_1(m, 1, 3, 0)$.}
        \label{Kirby_diag_of_C1}
    \end{figure}

    \begin{figure}[htbp]
        \centering
        \includegraphics[width=30mm]{04_KirbyDaigram_of_C2.eps}
        \caption{Kirby diagram for $C_2(m, 1, 3, 0)$.}
        \label{Kirby_diag_of_C2}
    \end{figure}

    \begin{Thm}\label{main2}
        The manifolds $C_1(m, 1, 3, 0)$ and $C_2(m, 1, 3, 0)$ $(m \leq -5)$
        shown in Figure \ref{Kirby_diag_of_C1} and  Figure \ref{Kirby_diag_of_C2}
        admit genus zero PALFs.
        The monodromy of the PALF on $C_1(m, 1, 3, 0)$ is
        described by the positive factorization
        \begin{align*}
            t_{\delta_{-m+5}} \ldots t_{\delta_{11}} t_{\delta_{10}}
                t_{\delta_9} t_{\delta_8} t_{\delta_7}
                t_{\beta_6} t_{\beta_5} t_{\beta_4} t_{\beta_3}
                t_{\beta_2} t_{\beta_1}
        \end{align*}
        while that for $C_2(m, 3, 1, 0)$ is described by the
        positive factorization
        \begin{align*}
            t_{\delta_{-m+5}} \ldots t_{\delta_{11}} t_{\delta_{10}}
                t_{\delta_9} t_{\delta_8} t_{\delta_7}
                t_{\gamma_6} t_{\gamma_5} t_{\gamma_4} t_{\gamma_3}
                t_{\gamma_2} t_{\gamma_1}
        \end{align*}
        , where $\beta_i, \gamma_j$ are simple closed curves shown in
        Figure \ref{PALF_of_C1} and Figure \ref{PALF_of_C2}.
    \end{Thm}

    \begin{figure}[htbp]
        \centering
        \includegraphics[width=110mm]{05_genus0_PALF_of_C1.eps}
        \caption{Vanishing cycles of a genus zero PALF on $C_1(m, 1, 3, 0)$.}
        \label{PALF_of_C1}
    \end{figure}

    \begin{figure}[htbp]
        \centering
        \includegraphics[width=110mm]{06_genus0_PALF_of_C2.eps}
        \caption{Vanishing cycles of a genus two PALF on $C_2(m, 1, 3, 0)$.}
        \label{PALF_of_C2}
    \end{figure}

The difference of smooth structures on $C_1(m,1,3,0)$ and $C_2(m,1,3,0)$
(or the effect of cork twisting the former to obtain the latter)
is reflected in the corresponding
positive factorizations as the difference between partial factorizations
$t_{\beta_6}t_{\beta_5}t_{\beta_4}t_{\beta_3}t_{\beta_2}t_{\beta_1}$ and
$t_{\gamma_6}t_{\gamma_5}t_{\gamma_4}t_{\gamma_3}t_{\gamma_2}t_{\gamma_1}$.

    In Section 2 we briefly review definitions of Mapping class groups,
    PALF, Stein surfaces, and corks, and recall several known results.
    We prove our main theorems in Section 3.

    \section{Preliminaries}

        \subsection{Mapping class groups}

        In this subsection we review a precise definition of
        mapping class groups of surfaces with boundary and that of
        Dehn twists along simple closed curves on surfaces.

        \begin{Def}
            Let $F$ be a compact oriented  connected surface with boundary.
            Let Diff${}^+(F, \partial F)$ be
            the group of all orientation-preserving self-diffeomorphisms
            of $F$ fixing the boundary $\partial F$ point-wise.
            Let Diff${}^+_0(F, \partial F)$ be
            the subgroup of Diff${}^+(F, \partial F)$ consisting of
            self-diffeomorphisms isotopic to the identity.
            The quotient group
            Diff${}^+(F, \partial F)/$ Diff${}^+_0(F, \partial F)$
            is called the mapping class group of $F$ and it is
            denoted by Map$(F, \partial F)$.
        \end{Def}

        \begin{Def}
            A {\em positive $($or right-handed$)$ Dehn twist}
            along a simple closed curve $\alpha$, $t_\alpha:F \rightarrow F$
            is a diffeomorphism  obtained by
            cutting $F$ along $\alpha$, twisting $360^\circ$
            to the right and regluing.
        \end{Def}

        \subsection{PALF}

        \begin{Def}\label{aLFdef}
            Let $M^4$ and $B^2$ be compact oriented smooth manifolds
            of dimensions $4$ and $2$.
            Let $f: M \rightarrow B$ be a smooth map.
            $f$ is called a {\em positive Lefschetz fibration} over $B$
            if it satisfies the following conditions (1) and (2):

            \begin{enumerate}
                \renewcommand{\labelenumi}{(\arabic{enumi})}
                \setlength{\itemsep}{0cm}
                                \setlength{\parskip}{1mm}
                \item There are finitely many critical values
                      $b_1, \ldots, b_m $ of $f$ in the interior of $B$
                      and there is a unique critical point $p_i$
                      on each fiber $f^{-1}(b_i)$, and
                \item The map $f$ is locally written as
                      $f(z_1, z_2) = z_1^2 + z_2^2$ with respect to
                      some local complex coordinates around
                      $p_i$ and $b_i$ compatible with the orientations of
                      $M$ and $B$.
            \end{enumerate}
        \end{Def}

        \begin{figure}[htbp]
            \centering
            \includegraphics[width=80mm]{07_PALF_diag.eps}
            \caption{PALF.}
            \label{PALFdiag}
        \end{figure}

        \begin{Def}
            A positive Lefschetz fibration is called {\em allowable} if
            its all vanishing cycles are homologically non-trivial on the
            fiber.
            A positive allowable Lefschetz fibration over $D^2$ with
            bounded fibers is called a {\em PALF} for short.
        \end{Def}

        The following Lemma is useful to prove Theorem \ref{main1}.

        \begin{Lem}[{cf. Akbulut-Ozbagci \cite[Remark 1]{AO}}]
            \label{Lefschetz_2_h_PALF}
            Suppose that a $4$-manifold $X$ admits a PALF.
            If a $4$-manifold $Y$ is obtained from $X$ by attaching a
            Lefschetz $2$-handle, then $Y$ also admits a PALF.
        \end{Lem}

        The Lefschetz $2$-handle is defined as follows.

        \begin{Def}
            Suppose that $X$ admits a PALF.
            A {\em Lefschetz $2$-handle} is a $2$-handle attached
            along a homologically non-trivial simple closed curve
            in the boundary of $X$ with framing $-1$ relative to
            the product framing induced by the fiber structure.
        \end{Def}

        \subsection{Stein surfaces}

        In this section, we recall a definition of Stein surfaces.
        The question of which smooth $4$-manifolds admit
        Stein structures can be completely reduced to a
        problem in handlebody theory.

        \begin{Def}
            A complex manifold is called a {\em Stein manifold} if
            it admits a proper biholomorphic embedding to $\mathbb{C}^n$.
        \end{Def}

        \begin{Def}
            Let $W$ be a compact manifold with boundary.
            The manifold $W$ is called a {\em Stein domain} if it
            satisfies following condition:
            There is a Stein manifold $X$ and
            a plurisubharmonic function
            $\varphi : X \rightarrow [0, \infty)$
            such that
            $W = \varphi^{-1}([0, a])$
            for a regular value $a$ of $\varphi$.
        \end{Def}

        \begin{Def}
            A Stein manifold or a Stein domain is called
            a {\em Stein surface} if its complex dimension is $2$.
        \end{Def}

        \subsection{Corks}

        Corks are Stein surfaces and
        they are useful for constructing exotic manifolds.

        \begin{Def}
            Let $C$ be a  Stein domain.
            Let $\tau : \partial C \rightarrow \partial C$ be an
            involution on the boundary $\partial C$ of $C$.
            \begin{enumerate}
                \renewcommand{\labelenumi}{(\arabic{enumi})}
                \setlength{\itemsep}{0cm}
                                \setlength{\parskip}{1mm}
                \item $(C, \tau)$ is called a {\em cork} if $\tau$
                      extends to a self-homeomorphism of $C$,
                      but does not extend to any self-diffeomorphism of $C$.
                \item Suppose that $C$ is embedded in a smooth
                      $4$-manifold $X$.
                      The manifold obtained from $X$ by removing $C$
                      and regluing it via $\tau$
                      is called a {\em cork twist} of
                      $X$ along $(C, \tau)$.
                \item The pair $(C, \tau)$ is called a {\em cork of $X$}
                      if the cork twist of $X$ along $(C, \tau)$ is
                      homeomorphic but not diffeomorphic to $X$.
            \end{enumerate}
        \end{Def}

        In this paper, we investigate Akbulut cork $(W_1, f_1)$ ([Ak]).

        \begin{Def}\label{def:AkbulutCork}
            Let $W_1$ be a smooth 4-manifold
            given by Figure \ref{AkbulutCork}.
            Let $f_1: \partial W_1 \rightarrow \partial W_1$
            be the obvious involution obtained from first surgering
            $S^1 \times D^3$ to $D^2 \times S^2$ in the
            interiors of $W_1$, then surgering the
            other imbedded $D^2 \times S^2$ back to
            $S^1 \times D^2$.
        \end{Def}

        \begin{Thm}[Akbulut \cite{Ak}]
            The pair $(W_1, f_1)$ is
            a cork.
        \end{Thm}

        Akbulut and Yasui constructed infinitely many exotic pairs.

        \begin{Thm}[{Akbulut-Yasui \cite[Theorem 3.3(2)]{AY2}}]
            $C_1(m, n, p, 0)$ and $C_2(m, n, p, 0)$ are
            homeomorphic but not diffeomorphic to each other,
            for $1 \leq n \leq 3, p \geq 3$ and
            $m \leq p^2 - 3p + 1$.
        \end{Thm}

        \begin{figure}[htbp]
            \centering
            \includegraphics[width=80mm]{08_C1_mnpq.eps}
            \caption{Kirby diagram for $C_1(m, n, p, q)$.}
            \label{C1(mnpq)}
        \end{figure}

        \begin{figure}[htbp]
            \centering
            \includegraphics[width=80mm]{09_C2_mnpq.eps}
            \caption{Kirby diagram for $C_2(m, n, p, q)$.}
            \label{C2(mnpq)}
        \end{figure}

    \section{Proofs of Theorems \ref{main1} and \ref{main2}.}

    {\it Proof of Theorem  \ref{main1}.}
    Let $F$ be the compact oriented surface of genus zero
    with $5$ boundary components
    and $\alpha_1,\ldots , \alpha_4$ be the curves on $F$ shown in
    Figure \ref{PALF_of_the_Akbulut_cork}.
    We denote the right-handed Dehn twists along $\alpha_1,\ldots , \alpha_4$
    by $t_{\alpha_1}, \ldots ,t_{\alpha_4}$, respectively.
    Let $f:X \rightarrow D^2$ be a Lefschetz fibration over $D^2$
    with monodromy representation $(t_{\alpha_4},\ldots ,t_{\alpha_1})$.
    Since each curve $\alpha_i$ is homologically non-trivial on $F$,
    we see that $f$ is a PALF with fiber $F$.

    We now show that $X$ is diffeomorphic to $W_1$.
    The obvious Kirby diagram for $W_1$ is given by
    Figure \ref{AkbulutCork}.
    We draw it as in Figure \ref{Proof_Akbulut_cork_PALF}$(a)$,
    and create the cancelling pair to get Figure
    \ref{Proof_Akbulut_cork_PALF}$(b)$.
    We slide the $0$-framed $2$-handle over a $1$-framed $2$-handle
    to get Figure \ref{Proof_Akbulut_cork_PALF}$(c)$.
    We get Figure \ref{Proof_Akbulut_cork_PALF}$(d)$
    by sliding the $-3$-framed $2$-handle over a $1$-framed $2$-handle.
    By $1$-handle slide,
    we get Figure \ref{Proof_Akbulut_cork_PALF}$(e)$.
    We slide the $-4$-framed $2$-handle over a $1$-framed $2$-handle,
    and erase a cancelling $1$-handle/$2$-handle pairs
    to get Figure \ref{Proof_Akbulut_cork_PALF}$(f)$.
    We create the cancelling pairs
    to get Figure \ref{Proof_Akbulut_cork_PALF}$(g)$.
    We get Figure \ref{Proof_Akbulut_cork_PALF}$(h)$ by
    by creating the cancelling pairs.

    The Kirby diagram for $X$ corresponding to the monodromy
    representation $t_{\alpha_4}, \ldots, t_{\alpha_1}$ is
    given by Figure \ref{Proof_Akbulut_cork_PALF}$(h)$.

    Therefore we conclude that $X$ is diffeomorphic to $W_1$,
    which implies the theorem.

    \hfill $\Box$

    \begin{figure}[htbp]
        \centering
        \includegraphics[width=120mm]{10_proof_of_cork_admits_genus0_PALF.eps}
        \caption{}
        \label{Proof_Akbulut_cork_PALF}
    \end{figure}

    \vspace*{5mm}

    {\itshape Proof of Theorem \ref{main2}.}
    Let $F_{C_i(m, 1, 3, 0)}$ $(i = 1, 2)$ be the compact oriented surface of
    genus zero with $-m+5$ boundary components and
    $\beta_1, \ldots, \beta_{-m+5}$ and $\gamma_1, \ldots, \gamma_{-m+5}$
    be the curves on $F_{C_i(m, 1, 3, 0)}$ shown in
    Figure \ref{PALF_of_C1} and Figure \ref{PALF_of_C2}, respectively.
    Let $g_1:X_{C_1(m, 1, 3, 0)} \rightarrow D^2$
    (resp. $g_2:X_{C_2(m, 1, 3, 0)} \rightarrow D^2$) be
    a Lefschetz fibration over $D^2$
    with monodromy representation $(t_{\beta_{-m+5}},\ldots ,t_{\beta_1})$
    (resp. $(t_{\gamma_{-m+5}}, \ldots, t_{\gamma_1})$).
    Since each curve $\beta_i$ (resp. $\gamma_i$) is
    homologically non-trivial on $F_{C_1(m, 1, 3, 0)}$ (resp. $F_{C_2(m, 1, 3, 0)}$),
    we see that $g_1$ (resp. $g_2$) is a PALF with fiber
    $F_{C_1(m, 1, 3, 0)}$ (resp. $F_{C_2(m, 1, 3, 0)}$).

    The Kirby diagram for $C_1(m, 1, 3, 0)$ is given by
    Figure \ref{Kirby_diag_of_C1}.
    We get Figure \ref{Proof_C1_PALF_1}$(a)$ by isotopy.
    We create a cancelling pair to get Figure \ref{Proof_C1_PALF_1}$(b)$.
    We slide the $0$-framed $2$-handle over a $1$-framed $2$-handle to get
    Figure \ref{Proof_C1_PALF_1}$(c)$.
    By sliding the $-3$-framed $2$-handle over a $1$-framed $2$-handle,
    we get Figure \ref{Proof_C1_PALF_1}$(d)$.
    We get Figure \ref{Proof_C1_PALF_1}$(e)$ by $1$-handle slide.
    We obtain Figure \ref{Proof_C1_PALF_1}$(f)$ by handle slides and
    cancellation.
    By handle slide and creating cancelling pair,
    we get Figure \ref{Proof_C1_PALF_2}$(g)$.
    We get Figure \ref{Proof_C1_PALF_2}$(h)$ by handle slide and
    creating cancelling pair.
    We slide the $m$-framed $2$-handle over $-1$-framed $2$-handle
    to get Figure \ref{Proof_C1_PALF_2}$(i)$.
    In Figure \ref{Proof_C1_PALF_2}$(i)$, creating cancelling pair
    gives Figure \ref{Proof_C1_PALF_2}$(j)$.
    We create cancelling pairs to get Figure \ref{Proof_C1_PALF_3}$(k)$.

    The Kirby diagram for $X_{C_1(m, 1, 3, 0)}$ corresponding to the
    monodromy representation $t_{\beta_{-m+5}}, \ldots, t_{\beta_1}$ is
    given by \ref{Proof_C1_PALF_3}$(k)$.

    The Kirby diagram for $C_2(m, 1, 3, 0)$ is given by
    Figure \ref{Kirby_diag_of_C2}.
    We get Figure \ref{Proof_C2_PALF_1}$(a)$ by isotopy.
    We obtain Figure \ref{Proof_C2_PALF_1}$(b)$ by handle slides and
    cancellation (see the proof of Theorem \ref{main1}).
    By creating cancelling pairs, we get Figure \ref{Proof_C2_PALF_1}$(c)$.
    We slide the $m$-framed $2$-handle under a $1$-handle to get
    Figure \ref{Proof_C2_PALF_1}$(d)$.
    In Figure \ref{Proof_C2_PALF_1}$(d)$, handle slides gives
    Figure \ref{Proof_C2_PALF_1}$(e)$.
    We create cancelling pairs to get Figure \ref{Proof_C2_PALF_2}$(f)$.

    The Kirby diagram for $X_{C_2(m, 1, 3, 0)}$ corresponding to
    the monodromy representation $t_{\gamma_{-m+5}}, \ldots, t_{\gamma_1}$
    is given by Figure \ref{Proof_C2_PALF_2}$(f)$.

    Therefore we conclude that
    the manifolds $C_1(m, 1, 3, 0)$ and $C_2(m, 1, 3, 0)$ admit
    genus zero PALFs.
    \hfill $\Box$

    \begin{figure}[htbp]
        \centering
        \includegraphics[width=120mm]{11_proof_of_C1_PALF.eps}
        \caption{}
        \label{Proof_C1_PALF_1}
    \end{figure}

    \begin{figure}[htbp]
        \centering
        \includegraphics[width=140mm]{12_proof_of_C1_PAFL_2.eps}
        \caption{}
        \label{Proof_C1_PALF_2}
    \end{figure}

    \begin{figure}[htbp]
        \centering
        \includegraphics[width=120mm]{13_proof_of_C1_PAFL_3.eps}
        \caption{}
        \label{Proof_C1_PALF_3}
    \end{figure}

    \begin{figure}[htbp]
        \centering
        \includegraphics[width=100mm]{14_proof_of_C2_PAFL_1.eps}
        \caption{}
        \label{Proof_C2_PALF_1}
    \end{figure}

    \begin{figure}[htbp]
        \centering
        \includegraphics[width=120mm]{15_proof_of_C2_PAFL_2.eps}
        \caption{}
        \label{Proof_C2_PALF_2}
    \end{figure}

    \clearpage

    \renewcommand{\abstractname}{Acknowledgements}
    \begin{abstract}
        The author would like to thank his adviser
        Hisaaki Endo for his helpful comments and
        his encouragement.
        The author wishes to thank Kouichi Yasui for
        his useful comments.
    \end{abstract}


TITLE: Convergent Series: $\sqrt{n+1}/(n^2 + 1)$
QUESTION [2 upvotes]: I have this homework problem that I'm having difficulty on.

$$
\sum_{n=1}^\infty \frac{\sqrt{n+1}}{n^2+2}
$$

I've found that the series is most likely convergent by the divergent test. As using lhospitals rule, the sequence approaches 0, thus it MIGHT be a convergent series. However, I do think it's convergent because it doesn't appear to be a harmonic sequence. So now I need to find the sum of the series, and that's where I am having trouble with.

REPLY [1 votes]: Note that for $n\ge1$, we have the estimate
$$0<\frac{\sqrt{n+1}}{n^2+2}\le \frac{\sqrt{n+n}}{n^2}=\frac{\sqrt2}{n^{3/2}} $$
Inasmuch as the series $\sum_{n\ge 1}\frac1{n^{3/2}}$ converges, the series of interest, $\sum_{n\ge1 }\frac{\sqrt{n+1}}{n^2+2}$ does likewise.


TITLE: For $[A,B]=0$, if an eigenfunction of $A$ not an eigenfunction of $B$, does that imply degeneracy of one operator?
QUESTION [5 upvotes]: When two operators $A$ and $B$ commute, there can be functions which are eigenfunctions of $A$ but not that of $B$.
For example, in case of the one-dimensional harmonic oscillator, any linear combination of the ground state and the second excited state is an eigenfunction of parity operator (with eigenvalue +1) but not that of the hamiltonian even though they commute. In this example, this happens because the parity operator has degenerate eigenfunctions with eigenvalue +1.
Is this true in general? I mean, for this to happen, do we always need one of the operators to have degenerate eigenfunctions? Can we prove this?

REPLY [0 votes]: yes the mathematics put above is correct, and in general way, you can say, whenever two operators commute, they must represent some degeneracy. You can put it in this way.


TITLE: Application of Rolle's theorem in a problem
QUESTION [1 upvotes]: For $n\in\mathbb {N}$, we define the function $g_n$ by: for $x\in\mathbb {R} $
$$
g_0 (x)=1\\ g_n (x)=\frac {x (x-1)...(x-n+1)}{n!}
$$
Let $f:[0, + \infty [ \to\mathbb { R}$ be a map of class $C^\infty $. We suppose that there exists a unique sequence  $(a_n)_n $ such that: for all $n\in\mathbb {N}$
$$
\sum_{k=0}^{n}{a_kg_k (x)}=f (x)\qquad \forall x\in\{0,1,...,n\}\qquad(*)
$$
Problem
Let $x \in [0, + \infty[ $. Show that:
$$
\forall N\in \mathbb {N},\exists \theta\in \mathbb {R}\text { such that } f (x)=\sum_{k=0}^{N}{a_kg_k (x)}+g_{N+1}(x)f^{(N+1)}(\theta)
$$
for the case $x\in \{0,1,...,N\} $, from (*), it is evident. But for the case $x\notin \{0,1,...,N\} $ I have no idea I only have this indication:
Hint : use the auxiliary function $t \to f (t)= \sum_{k=0}^{N}{a_kg_k (t)}+Ag_{N+1}(t)$, where A is a suitably chosen constant and apply the rolle's theorem).
An idea please.

REPLY [1 votes]: Given $x\in\Bbb R\setminus\{0,1,\ldots,N\}$, consider $h(t)=\sum_{k=0}^{N}{a_kg_k (t)}+Ag_{N+1}(t)-f(t)$ with $A$ a constant such that $h(x)=0$. Then $A=\dfrac{f(x)-\sum_{k=0}^{N}{a_kg_k (t)}}{g_{N+1}(x)}$ (we can divide by $g_{N+1}(x)$ because $x\notin\{0,1,\ldots,N\}$). Moreover, $h(y)=0$ for all $y\in\{0,1,\ldots,N\}$. Besides, $h$ is $C^\infty$.
Thus $h$ has at least N+1 roots, so by Rolle's theorem $h'$ has at least N roots, each one between two roots of $h$. Applying Rolle's theorem again, $h''$ has at least N-1 roots; again, $h'''$ has at least N-2 roots. And so on, until we arrive at $h^{(N+1)}$, which will have at least one root. Let's call this root $\theta$.
We have that $h(t)=\sum_{k=0}^{N}{a_kg_k (t)}+Ag_{N+1}(t)-f(t)$ and each $g_k$ is a polynomial of degree $k$, so when we differentiate N+1 times the only polynomial that will "survive" (not disappear by differentiation so it becomes $0$) is $g_{N+1}$, since is the only one with degree greater or equal to N+1. The leading term of $Ag_{N+1}$ is $\dfrac{Ax^{N+1}}{(N+1)!}$, so when differentiating N+1 times we get $A$. Then $h^{(N+1)}(t)=A-f^{(N+1)}(t)$. We know it has a root we called $\theta$, so $h^{(N+1)}(\theta)=0=A-f^{(N+1)}(\theta)$, and then $A=f^{(N+1)}(\theta)$.
Now remember we know what $A$ is, since we demanded it to make true $h(x)=0$. We had that $A=\dfrac{f(x)-\sum_{k=0}^{N}{a_kg_k (x)}}{g_{N+1}(x)}$, and know we have $A=f^{(N+1)}(\theta)$, so finally
$f(x)=\sum_{k=0}^{N}{a_kg_k (x)}+g_{N+1}(x)f^{(N+1)}(\theta)$.
Note: Since we got $\theta$ by Rolle's theorem, we know something more about it: $\theta\in(0,N)$.


TITLE: Combinatorial problem on periodic dyck paths from homological algebra
QUESTION [2 upvotes]: edit: I added conjecture 2 that looks much more accessible.
Here is the elementary combinatorial translation of the problem (read below for the homological background):
Let $n \geq 2$.
A Nakayama algebra is a list $[c_0,c_1,...,c_{n-1}]$ of $n$ integers with $c_i \geq 2$, $c_{i+1} \geq c_i-1$ and $c_{n-1}=c_0+1$ (it can be interpreted as a periodic Dyck path). Read the indices $i$ in the $c_i$ mod $n$ so that they are defined for any $i \in \mathbb{Z}$.
A module is a tuple $(i,k)$ with $0 \leq i \leq n-1$ (the first entry $i$ is always viewed mod $n$) and $1 \leq k \leq c_i$. A proper module is a module with $k < c_i$.
A proper module $M=(i,k)$ is called weird in case with $k=s+tn$ with $0 \leq s <n$ we have $n \leq k$ and $max(0,2k-c_i) \leq s+(t-1)n$ (this should be equivalent to $Ext_A^1(M,M) \neq 0$ ).
Define the $i$-th syzygy of a proper module $(i,k)$ as follows:
$\Omega^0(i,k)=(i,k)$, $\Omega^1(i,k)=(i+k,c_i-k)$ and $\Omega^l(i,k)=\Omega^1(\Omega^{l-1}(i,k))$ for $l \geq 2$.
A proper module $M=(i,k)$ is called periodic with period $q$ in case $M = \Omega^q(M)$ and it is called quasi-periodic in case $\Omega^u(M)$ is periodic for some $u \geq 0$.
The below guess can now be stated completely elementary (I state it here as a conjecture, but it is hard to check since there are infinitely many Nakayama algebras for a given $n$):

Conjecture: Any weird module is quasi-periodic.
Conjecture 2: In case $M$ is weird, also $\Omega^1(M)$ is weird.

Conjecture 2 implies conjecture 1 and looks much easier but I cant find a good argument yet.
Example: The Nakayama algebra [3,4] has the unique weird module (1,2) , which is periodic of period 1.
Homological background:
The strong no loop conjecture states that for a simple module $S$ over a finite dimensional algebra $A$ we have that $S$ has infinite projective dimension in case $Ext_A^1(S,S) \neq 0$. In general this is not true for arbitrary indecomposable modules instead of simple modules, but it seems that it might be true for Nakayama algebras.

Guess: In case $A$ is a Nakayama algebra with an indecomposable module $M$ with $Ext_A^1(M,M) \neq 0$ then $M$ has infinite projective dimension.

I can prove this for algebras with finite global dimension (which includes all Nakayama algebras with a linear quiver and thus we can focus on cyclic quivers).
I should note that maybe there is an easy argument and Im too blind to see it at the moment.

REPLY [3 votes]: I think you have a typo in the definition of a Nakayama algebra list and it should read "$c_{i+1}\geq c_i-1$." If this is the case then conjecture 2 has a simple proof:
The condition for a module $M=(i,k)$ to be weird is that $n\le k\le c_i-n$. We have to show that this implies that $\Omega^1(M)=(i+k,c_i-k)$ is also weird. This means that we have to check that
$$n\le c_i-k\le c_{i+k}-n.$$
Now, the inequality $n\le c_i-k$ follows immediately from the weirdness of $M$. The second inequality follows from observing that
$$c_{i+k}-c_i=c_{i+k}-c_{i+n}=\sum_{j=n+1}^{k}(c_j-c_{j-1})\geq \sum_{j=n+1}^k (-1)=n-k.$$
After rearranging the terms we get $c_i-k\le c_{i+k}-n$ as desired.


TITLE: Determine if matrix is diagonizable
QUESTION [1 upvotes]: I am given matrix $A$:
\begin{pmatrix} 0 & 0 & -2\\1&2&1\\1&0&3\end{pmatrix}
I found the eigenvalues to be 1 and 2 by computing $\det(A-I\lambda)$.
Since the matrix is $3\times 3$ and there are only two distinct eigenvalues, I do not know what to do next. I know that there being n distinct eigenvalues proves that $A$ is diagonizable but the converse is not true so where do I go from here?

REPLY [0 votes]: The characteristic polynomial of
$$
A=\left[\begin{array}{rrr}
0 & 0 & -2 \\
1 & 2 & 1 \\
1 & 0 & 3
\end{array}\right]
$$
is $\chi_A(t)=t^{3} - 5\,t^{2} + 8\,t - 4=(t - 1) \cdot (t - 2)^{2}$. Thus the eigenvalues of $A$ are $\lambda=1$ and $\lambda=2$. The algebraic multiplicities of the eigenvalues of $A$ are $\DeclareMathOperator{am}{am}\am_A(1)=1$ and $\am_A(2)=2$.
Now, recall that the geometric multiplicity of an eigenvalue $\lambda$ of $A$ is defined as $\DeclareMathOperator{gm}{gm}\gm_A(\lambda)=\dim\DeclareMathOperator{Null}{Null}\Null(\lambda\cdot I-A)$. The inequality $1\leq \gm_A(\lambda)\leq\am_A(\lambda)$ is always respected. Thus the we have $\gm_A(1)=1$ and $\gm_A(2)=1$ or $\gm_A(2)=2$. Also recall that $A$ is diagonalizable if and only if each eigenvalue $\lambda$ of $A$ satisfies $\am_A(\lambda)=\gm_A(\lambda)$.
So, to check if $A$ is diagonalizable, we need only check if $\gm_A(2)=2$. To do so, note that
$$
2\cdot I-A=\left[\begin{array}{rrr}
2 & 0 & 2 \\
-1 & 0 & -1 \\
-1 & 0 & -1
\end{array}\right]
$$
One easily checks that $2\cdot I-A$ has rank one. The rank-nullity theorem then implies that $\gm_A(2)=2$. Hence $A$ is diagonalizable.


TITLE: Differentiating a vector valued function giving a row vector?
QUESTION [0 upvotes]: If $f:\mathbb R^n \to \mathbb R$, why is $f'(u)$ a $1 \times n$ row vector? (for any $u \in \mathbb R^n$). Many thanks!

REPLY [0 votes]: Notice that $f'$ by definition is a linear map $\mathbb{R}^n \to \mathbb{R}$. Therefore it has to be a $1 \times n$-Matrix which is the same as a row vector.

REPLY [0 votes]: The derivative of $f$ at point $x$ is a linear functional $L$ on $\Bbb R^n$ such that
$$f(x+\Delta x) = f(x) + L(\Delta x) + o(\|\Delta x\|).$$
The linear functionals in $\Bbb R^n$ are represented by a scalar multiplication by some fixed vector (Riesz representation theorem), i.e. $\exists v\in \Bbb R^n$ such that $L(x) = (v,x)$.
Finally, the scalar product of two column vectors $(v,x)$ is equivalent to the product $v^Tx$, that is why we can say that the gradient $\nabla_x f$ is a row vector.


TITLE: Orthocenter and coordinates of a vertex
QUESTION [1 upvotes]: In a triangle ABC,the vertex A is (1,1) and orthocenter is (2,4).If the sides AB and BC are members of the family of straight lines $ax+by+c=0$,where $a,b,c$ are in arithmatic progression.Then the coordinates of vertex C are (h,k).Find the value of 2h+12k.
My attempt:Since the coordinates of B are not given directly,I do not have any idea to solve this problem.Plus a,b,c in AP is confusing me.Can someone help me in this question?

REPLY [2 votes]: AB and BC are members of the family of straight lines ax+by+c=0,where a,b,c are in arithmatic progression. Therefore we can write
AB: $a_1x+b_1y+c_1=0$ and because A(1,1) lies on this line $\Rightarrow a_1+b_1+c_1=0$. Because $a_1,b_1,c_1$ are in AP follows $a_1+a_1+d+a_1+2d=0\Rightarrow a_1+d_1=0\Rightarrow b_1=0$. Consequently, the vector $(a_1,b_1)=(a_1,0)\perp$ AB $\Rightarrow$ the vector $(0,a_1)$ is colinear with AB. But $CH\perp AB\Rightarrow (2-h,4-k)\perp (0,a_1)\Rightarrow (4-k)a_1=0\Rightarrow k=4$  because $a_1\neq 0$.
For BC we proceed the same way:
BC: $a_2x+b_2y+c_2=0$ and because $C(h,k)$ lies on this line $\Rightarrow a_2h+b_2k+c_2=0\Leftrightarrow a_2h+4(a_2+d_2)+a_2+2d_2=0\Leftrightarrow a_2h+5a_2+6d_2=0 \,\,(*)$. Now we use that the vector $\vec {AH}\,(2-1,4-1)\perp BC$, i.e $(1,3)\perp (-b_2,a_2)=(-a_2-d_2,a_2)\Rightarrow -a_2-d_2+3a_2=0\Rightarrow d_2=2a_2$. Plug this in $(*)$ and get $a_2h+5a_2+12a_2=0\Rightarrow h=-17$, because $a_2\neq 0$.


TITLE: If an astronaut orbits earth, can both Time Dilation and Gravitational Time Dilation affect it?
QUESTION [1 upvotes]: I am very new at all of this stuff and this one thing bugs me very much...
If an astronaut is orbiting earth, it should be experiencing Time a bit faster than those on earth, correct?
Well then because of the speed he is traveling, he will also experience Time a little slower than those on earth.
Correct me if I’m wrong but those should pretty much cancel out, but that sounds completely wrong to me.
If you could answer this question and fix any of my poor logic/ reasoning, that would be awesome :)

REPLY [0 votes]: Yes on both counts.  There is time dilation due to the orbital velocity (special relativity), and there is also time dilation due to the Earth's gravity field (general relativity).  The signs of each of these are opposite, but the magnitudes can be different, leaving a net effect.  The example I am most familiar with is with GPS (or other GNSS) satellites... here's a good post on that (Why does GPS depend on relativity?).


text:
\begin{document}

\title[Genus of commuting conjugacy class graph of  groups]{Genus of commuting conjugacy class graph of finite groups}
\author[P. Bhowal and R. K. Nath]{Parthajit Bhowal  and Rajat Kanti Nath$^*$}
\address{Department of Mathematical Sciences, Tezpur
University,  Napaam-784028, Sonitpur, Assam, India.
}
\email{bhowal.parthajit8@gmail.com, rajatkantinath@yahoo.com (corresponding author).}

\subjclass[2010]{20D99, 05C25, 05C10,   05E15.}
\keywords{commuting conjugacy class graph, genus, finite group.}

\thanks{*Corresponding author}

\begin{abstract}
For a non-abelian group $G$, its commuting conjugacy class graph $\mathcal{CCC}(G)$  is a simple undirected graph whose vertex set is the set of conjugacy classes of the non-central elements of $G$ and two distinct vertices $x^G$ and $y^G$ are adjacent if there exists some elements $x' \in x^G$ and $y' \in y^G$ such that $x'y' = y'x'$.

In this paper we compute the genus of $\mathcal{CCC}(G)$ for six  well-known classes of non-abelian two-generated groups (viz. $D_{2n}, SD_{8n}, Q_{4m}, V_{8n}, U_{(n, m)}$ and $G(p, m, n)$) and determine whether $\mathcal{CCC}(G)$ for these groups are planar, toroidal, double-toroidal or triple-toroidal.
\end{abstract}

\maketitle

\section{Introduction} \label{S:intro}

The commuting conjugacy class graph of a non-abelian group $G$ is a simple undirected  graph, denoted by $\mathcal{CCC}(G)$, whose vertex set is the set of conjugacy classes of the non-central elements of $G$ and two distinct vertices $x^G$ and $y^G$ are adjacent if there exists some elements $x' \in x^G$ and $y' \in y^G$ such that $x'y' = y'x'$.  This graph extends the notion of commuting graph of a finite group introduced by Brauer and Fowler \cite{bF1955}, in 1955. Commuting graphs of finite algebraic structures, its extensions, generalizations and their complements remain active topic of research over the years. In 2009, Herzog, Longobardi and Maj \cite{hLM2009} initiated the study of  commuting conjugacy class graph of groups. In 2016, finite groups having triangle-free commuting conjugacy class graph were characterized by Mohammadian et al. \cite{mefw}.

Ashrafi and Salahshour  have also considered commuting conjugacy class graph of finite groups  in their recent work \cite{sA2020}, where they obtain  structures of $\mathcal{CCC}(G)$ for the following groups:

\begin{align*}
D_{2n} &= \langle \alpha, \beta : \alpha^n = \beta^2 = 1, \beta\alpha \beta = \alpha^{-1}\rangle \text{ for } n \geq 3,\\
SD_{8n} &= \langle \alpha, \beta : \alpha^{4n} = \beta^2 = 1, \beta\alpha \beta = \alpha^{2n -1}\rangle \text{ for } n \geq 2, \\
Q_{4m} &= \langle \alpha, \beta : \alpha^{2m} = 1, \alpha^m = \beta^2, \beta^{-1}\alpha \beta = \alpha^{-1}\rangle \text{ for } m \geq 2,\\
V_{8n} &= \langle \alpha, \beta : \alpha^{2n} = \beta^4 = 1, \beta\alpha = \alpha^{-1}\beta^{-1}, \beta^{-1}\alpha = \alpha^{-1}\beta \rangle \text{ for } n \geq 2,\\
U_{(n, m)} &= \langle \alpha, \beta :  \alpha^{2n} = \beta^m = 1, \alpha^{-1}\beta\alpha = \beta^{-1}\rangle \text{ for } m \geq 2 \text{ and } n \geq 2 \text{ and }\\
G(p, m, n) &= \langle \alpha, \beta : \alpha^{p^m} = \beta^{p^n} = [\alpha, \beta]^p = 1, [\alpha, [\alpha, \beta]] = [\beta, [\alpha, \beta]] = 1\rangle,
\end{align*}
where $p$ is any prime,  $m \geq 1$ and $n \geq 1$.

Continuing the works of Ashrafi and Salahshour \cite{sA2020}, in \cite{bN-CCG-1-20,bN-CCG-2-20} Bhowal and Nath have obtained various spectra and energies of commuting conjugacy class graphs of finite groups.
In this paper we compute genus of commuting conjugacy class graph of the above  mentioned groups and determine whether $\mathcal{CCC}(G)$ for those groups are planar, toroidal, double-toroidal or triple-toroidal.

The genus $\gamma(\mathcal{G})$ of a graph $\mathcal{G}$ is the smallest  integer $k \geq 0$ such that $\mathcal{G}$ can be embedded on the surface obtained by attaching $k$ handles to a sphere. A graph $\mathcal{G}$ is called planar, toroidal, double-toroidal or triple-toroidal if $\mathcal{G}$ has genus $0,1,2$ or $3$ respectively. Results on genus of commuting graphs of finite groups, including  its various extensions,  can be found in \cite{AF14,bnN20,das13,das2015}. However, genus of commuting conjugacy class graph of finite groups are not yet studied.

\section{Genus of $\mathcal{CCC}(G)$ and characterizations}

Let $K_n$ be the complete graph on $n$ vertices and $mK_n$ the disjoint union of $m$ copies of $K_n$. Then, by \cite[Theorem 6-38]{whit}, we have
\begin{equation} \label{kn}
\gamma(K_{n})=\left\lceil \frac{(n-3)(n-4)}{12}\right
\rceil, \text{ if } n \geq 3.
\end{equation}

By \cite[Corollary 2]{bhky}, we also have the following lemma.
\begin{lemma}\label{kmn}
If $\mathcal{G} = m_1K_{n_1} \sqcup m_2K_{n_2}$ then $\gamma(\mathcal{G}) = m_1\gamma(K_{n_1}) + m_2\gamma(K_{n_2})$.
\end{lemma}
Now we compute genus of commuting conjugacy class graph of the groups $D_{2n}, SD_{8n}, Q_{4m}, V_{8n}$, $U_{(n, m)}$ and $G(p, m, n)$ one by one and check their planarity, toroidality etc.
\begin{theorem}
Let $G = D_{2n}$. Then
\begin{enumerate}
\item $\mathcal{CCC}(G)$ is planar if and only if $3\leq n \leq 10$.
\item $\mathcal{CCC}(G)$ is toroidal if and only if $11\leq n \leq 16$.
\item $\mathcal{CCC}(G)$ is double-toroidal if and only if $n = 17,18$.
\item $\mathcal{CCC}(G)$ is triple-toroidal if and only if $n = 19,20$.
\item $\gamma(\mathcal{CCC}(G))=\begin{cases}
\left\lceil\frac{(n-7)(n-9)}{48}\right\rceil, & \text{ if $n$ is odd and $n\geq 21$ }
\vspace{.2cm}\\
\left\lceil\frac{(n - 8)(n - 10)}{48}\right\rceil, & \text{ if $n$ is even and $n\geq 22$. }
\end{cases}$
\end{enumerate}
\end{theorem}
\begin{proof}
Consider the following cases.

\noindent \textbf{Case 1.} $n$ is odd.

 By \cite[Proposition 2.1]{sA2020} we have $\mathcal{CCC}(G) = K_1 \sqcup K_{\frac{n - 1}{2}}$. Therefore, for $n = 3$ and $5$, it follows that $\mathcal{CCC}(G)= 2K_1$, $K_1\sqcup K_2$ respectively; and hence $\mathcal{CCC}(G)$ is planar. If $n \geq 7$ then, by Lemma \ref{kmn} and \eqref{kn}, we have
 \[
 \gamma(\mathcal{CCC}(G)) = \gamma(K_{\frac{n - 1}{2}}) =  \left\lceil\frac{(n-7)(n-9)}{48}\right\rceil.
 \]
Clearly $\gamma(\mathcal{CCC}(G)) = 0$ if and only if $n=7$ or $9$. Also, $\gamma(\mathcal{CCC}(G)) = 1$ if $n = 11$, $13$ or $15$; $\gamma(\mathcal{CCC}(G)) = 2$ if $n = 17$; $\gamma(\mathcal{CCC}(G)) = 3$ if $n = 19$. For $n\geq 21$ we have
\[
\frac{(n-7)(n-9)}{48} \geq \frac{7}{2} = 3.5,
\]
and so
 \[
 \gamma(\mathcal{CCC}(G)) =  \left\lceil\frac{(n-7)(n-9)}{48}\right\rceil \geq 4.
 \]
 Thus, $\mathcal{CCC}(G)$ is planar if and only if $n=3,5,7,9$; toroidal if and only if $n=11,13,15$; double-toroidal if and only if $n=17$ and triple-toroidal if and only if $n=19$.

 \noindent \textbf{Case 2.} $n$ is even.

 By \cite[Proposition 2.1]{sA2020} we have
 \[
 \mathcal{CCC}(G) =  \begin{cases}
 2K_1 \sqcup K_{\frac{n}{2} - 1}, & \text{ if $n$ and $\frac{n}{2}$ are even}\\
  K_2 \sqcup K_{\frac{n}{2} - 1}, & \text{ if $n$ is even and $\frac{n}{2}$ is odd.}
\end{cases}
 \]
 Therefore, for $n = 4$ and $6$, it follows that $\mathcal{CCC}(G) = 3K_1$, $2K_2$ respectively; and hence $\mathcal{CCC}(G)$ is planar. If $n\geq 8$ then, by Lemma \ref{kmn} and \eqref{kn}, we have
  \[
 \gamma(\mathcal{CCC}(G)) = \gamma(K_{\frac{n}{2} - 1}) =  \left\lceil\frac{(n - 8)(n - 10)}{48}\right\rceil.
 \]
 Clearly $\gamma(\mathcal{CCC}(G)) = 0$ if and only if $n=8$ or $10$. Also, $\gamma(\mathcal{CCC}(G)) = 1$ if $n = 12$, $14$ or $16$; $\gamma(\mathcal{CCC}(G)) = 2$ if $n = 18$; $\gamma(\mathcal{CCC}(G)) = 3$ if $n = 20$. For $n\geq 22$ we have
\[
\frac{(n-8)(n-10)}{48} \geq \frac{7}{2} = 3.5,
\]
and so
 \[
 \gamma(\mathcal{CCC}(G)) =  \left\lceil\frac{(n-8)(n-10)}{48}\right\rceil \geq 4.
 \]
 Thus, $\mathcal{CCC}(G)$ is planar if and only if $n=4,6,8,10$; toroidal if and only if $n=12,14,16$; double-toroidal if and only if $n=18$ and triple-toroidal if and only if $n=20$. Hence the result follows.
 \end{proof}
\begin{theorem}
Let $G=SD_{8n}$. Then
\begin{enumerate}
\item $\mathcal{CCC}(G)$ is planar if and only if $n= 2$ or $3$.
\item $\mathcal{CCC}(G)$ is toroidal if and only if $n=4$.
\item $\mathcal{CCC}(G)$ is double-toroidal if and only if $n=5$.
\item $\mathcal{CCC}(G)$ is not triple-toroidal.
\item $\gamma(\mathcal{CCC}(G))=\begin{cases}
\left\lceil\frac{(n - 3)(2n - 5)}{6}\right\rceil, & \text{ if $n$ is odd and $n\geq 7$ }
\vspace{.2cm}\\
\left\lceil\frac{(n - 2)(2n - 5)}{6}\right\rceil, & \text{ if $n$ is even and $n\geq 6$. }
\end{cases}$
\end{enumerate}
\end{theorem}
\begin{proof}
Consider the following cases.

\noindent \textbf{Case 1.} $n$ is odd.

By \cite[Proposition 2.1]{sA2020} we have $\mathcal{CCC}(G) = K_4 \sqcup K_{2n - 2}$. For $n \geq 3$, by Lemma \ref{kmn} and \eqref{kn}, we have
 \[
 \gamma(\mathcal{CCC}(G)) = \gamma(K_{4}) + \gamma(K_{2n - 2}) =  \left\lceil\frac{(n-3)(2n-5)}{6}\right\rceil.
 \]
Clearly $\gamma(\mathcal{CCC}(G)) = 0$ if $n = 3$; $\gamma(\mathcal{CCC}(G)) = 2$ if $n = 5$. For $n\geq 7$ we have
\[
\frac{(n-3)(2n-5)}{6} \geq 6,
\]
and so
 \[
 \gamma(\mathcal{CCC}(G)) =  \left\lceil\frac{(n-3)(2n-5)}{6}\right\rceil \geq 6.
 \]
Thus $\mathcal{CCC}(G)$ is planar if and only if $n=3$; double-toroidal if and only if $n=5$.

 \noindent \textbf{Case 2.} $n$ is even.

By \cite[Proposition 2.1]{sA2020} we have $\mathcal{CCC}(G) = 2K_1 \sqcup K_{2n - 1}$. For $n \geq 2$, by Lemma \ref{kmn} and \eqref{kn}, we have
 \[
 \gamma(\mathcal{CCC}(G)) = \gamma(K_{2n - 1}) =  \left\lceil\frac{(n-2)(2n-5)}{6}\right\rceil.
 \]
Clearly $\gamma(\mathcal{CCC}(G)) = 0$ if $n = 2$; $\gamma(\mathcal{CCC}(G)) = 1$ if $n = 4$. For $n\geq 6$ we have
\[
\frac{(n-2)(2n-5)}{6} \geq \frac{14}{3},
\]
and so
 \[
  \gamma(\mathcal{CCC}(G)) = \left\lceil\frac{(n-2)(2n-5)}{6}\right\rceil \geq 5.
 \]
Thus $\mathcal{CCC}(G)$ is planar if and only if $n=2$; toroidal if and only if $n=4$. Hence the result follows.
 \end{proof}

\begin{theorem}
Let $G= Q_{4m}$. Then
\begin{enumerate}
\item $\mathcal{CCC}(G)$ is planar if and only if $m= 2,3,4$ or $5$.
\item $\mathcal{CCC}(G)$ is toroidal if and only if $m= 6,7$ or $8$.
\item $\mathcal{CCC}(G)$ is double-toroidal if and only if $m=9$.
\item $\mathcal{CCC}(G)$ is triple-toroidal if and only if $m=10$.
\item $\gamma(\mathcal{CCC}(G)) =  \left\lceil\frac{(m - 4)(m - 5)}{12}\right\rceil$ for $m\geq 11$.
\end{enumerate}
\end{theorem}
\begin{proof}
 By \cite[Proposition 2.1]{sA2020} we have
 \[
 \mathcal{CCC}(G) =  \begin{cases}
 K_2 \sqcup K_{m - 1}, & \text{ if $m$ is odd}\\
  2K_1 \sqcup K_{m - 1}, & \text{ if $m$ is even.}
\end{cases}
 \]
 Therefore, for $m = 2, 3$, it follows that $\mathcal{CCC}(G) = 3K_1$, $2K_2$ respectively; and hence $\mathcal{CCC}(G)$ is planar. If $m\geq 4$ then, by Lemma \ref{kmn} and \eqref{kn}, we have
  \[
 \gamma(\mathcal{CCC}(G)) = \gamma(K_{m - 1}) =  \left\lceil\frac{(m - 4)(m - 5)}{12}\right\rceil.
 \]
 Clearly $\gamma(\mathcal{CCC}(G)) = 0$ if and only if $m=4$ or $5$. Also, $\gamma(\mathcal{CCC}(G)) = 1$ if $m = 6$, $7$ or $8$; $\gamma(\mathcal{CCC}(G)) = 2$ if $m = 9$; $\gamma(\mathcal{CCC}(G)) = 3$ if $m = 10$. For $m\geq 11$ we have
\[
\frac{(m - 4)(m - 5)}{12} \geq \frac{7}{2} = 3.5,
\]
and so
 \[
 \gamma(\mathcal{CCC}(G)) =  \left\lceil\frac{(m - 4)(m - 5)}{12}\right\rceil \geq 4.
 \]
 Thus, $\mathcal{CCC}(G)$ is planar if and only if $m = 2,3,4,5$; toroidal if and only if $m = 6,7,8$; double-toroidal if and only if $m=9$ and triple-toroidal if and only if $m=10$. Hence the result follows.
\end{proof}
\begin{theorem}
Let $G=V_{8n}$. Then
\begin{enumerate}
\item $\mathcal{CCC}(G)$ is planar if and only if $n= 2$.
\item $\mathcal{CCC}(G)$ is toroidal if and only if $n=3$ or $4$.
\item $\mathcal{CCC}(G)$ is not double-toroidal.
\item $\mathcal{CCC}(G)$ is triple-toroidal if and only if $n= 5$.
\item $\gamma(\mathcal{CCC}(G))=\begin{cases}
\left\lceil\frac{(n - 2)(2n - 5)}{6}\right\rceil, & \text{ if $n$ is odd and $n\geq 7$ }
\vspace{.2cm}\\
\left\lceil\frac{(n - 3)(2n - 5)}{6}\right\rceil, & \text{ if $n$ is even and $n\geq 6$. }
\end{cases}$
\end{enumerate}
\end{theorem}
\begin{proof}
Consider the following cases.

\noindent \textbf{Case 1.} $n$ is odd.

By \cite[Proposition 2.1]{sA2020} we have $\mathcal{CCC}(G) = 2K_1 \sqcup K_{2n - 1}$. For $n \geq 3$, by Lemma \ref{kmn} and \eqref{kn}, we have
 \[
 \gamma(\mathcal{CCC}(G)) = \gamma(K_{2n - 1}) =  \left\lceil\frac{(n-2)(2n-5)}{6}\right\rceil.
 \]
Clearly $\gamma(\mathcal{CCC}(G)) = 1$ if $n = 3$; $\gamma(\mathcal{CCC}(G)) = 3$ if $n = 5$. For $n\geq 7$ we have
\[
\frac{(n-2)(2n-5)}{6} \geq \frac{15}{2} = 7.5,
\]
and so
 \[
 \gamma(\mathcal{CCC}(G)) =  \left\lceil\frac{(n-2)(2n-5)}{6}\right\rceil \geq 8.
 \]

 \noindent \textbf{Case 2.} $n$ is even.

By \cite[Proposition 2.1]{sA2020} we have $\mathcal{CCC}(G) = 2K_2 \sqcup K_{2n - 2}$. Therefore, for $n = 2$ it follows that $\mathcal{CCC}(G) = 3K_2$; and hence $\mathcal{CCC}(G)$ is planar. If $n \geq 4$ then, by Lemma \ref{kmn} and \eqref{kn}, we have
 \[
 \gamma(\mathcal{CCC}(G)) = \gamma(K_{2n - 2}) =  \left\lceil\frac{(n-3)(2n-5)}{6}\right\rceil.
 \]
Clearly $\gamma(\mathcal{CCC}(G)) = 1$ if $n = 4$. For $n\geq 6$ we have
\[
\frac{(n-3)(2n-5)}{6} \geq \frac{7}{2} = 3.5,
\]
and so
 \[
  \gamma(\mathcal{CCC}(G)) = \left\lceil\frac{(n-3)(2n-5)}{6}\right\rceil \geq 4.
 \]
 Thus $\mathcal{CCC}(G)$ is planar if and only if $n=2$; toroidal if and only if $n=4$. Hence the result follows.
\end{proof}

\begin{theorem}
Let $G= U_{(n,m)}$. Then
\begin{enumerate}
\item $\mathcal{CCC}(G)$ is planar if and only if $n = 2$ and $m = 2, 3, 4, 5, 6$; $n = 3$ and $m = 2, 3, 4$; or $n = 4$ and $m = 2, 3, 4$.
\item $\mathcal{CCC}(G)$ is toroidal if and only if $n = 2$ and  $m = 7, 8$; or $n = 3$ and $m = 5, 6$.
\item $\mathcal{CCC}(G)$ is double-toroidal if and only if $n = 2$ and $m = 9, 10$; $n = 4$ and $m = 5, 6$; $n = 5$ and $m = 2, 3$; $n = 6$ and $m = 2, 3$; or $n = 7$ and $m = 2, 3$.
\item $\mathcal{CCC}(G)$ is triple-toroidal if and only if $n = 3$ and $m = 7, 8$; $n = 5$ and $m = 4$; $n = 6$ and $m = 4$; or $n = 7$ and $m = 4$.
\item $\gamma(\mathcal{CCC}(G)) = \begin{cases}
\left\lceil\frac{(mn - n - 6)(mn - n - 8)}{48}\right\rceil, & \text{if $n=2$, $m$ is odd and $m \geq 11$}
\vspace{.2cm}\\
\left\lceil\frac{(mn - 2n - 6)(mn - 2n - 8)}{48}\right\rceil, & \text{if $n=2$, $m$ is even and $m \geq 12$}
\vspace{.2cm}\\
\left\lceil\frac{(mn - n - 6)(mn - n - 8)}{48}\right\rceil + \left\lceil\frac{(n - 3)(n - 4)}{12}\right\rceil, & \text{if $n = 3$, $m$ is odd and $m\geq 9$};\\
& n = 4, m\geq 7; n = 5, m\geq 5;\\
& n = 6,m\geq 5;  n = 7, m\geq 5;\\
& \text{ or } n \geq 8, m\geq 3 \\
\left\lceil\frac{(mn - 2n - 6)(mn - 2n - 8)}{48}\right\rceil + 2  \left\lceil\frac{(n - 3)(n - 4)}{12}\right\rceil, &\text{if $n = 3$,  $m$ is even and $m\geq 10$};\\
& n = 4, m\geq 8; n = 5, m\geq 6;\\
& n = 6,m\geq 6;  n = 7, m\geq 6;\\
&\text{ or } n \geq 8, m\geq 2
\end{cases}$
\end{enumerate}
\end{theorem}
\begin{proof}
Consider the following cases.

\noindent \textbf{Case 1.} $m$ is odd.

By \cite[Proposition 2.3]{sA2020} we have $\mathcal{CCC}(G) =   K_{\frac{n(m - 1)}{2}} \sqcup K_n$.

\noindent \textbf{Sub case 1.1} $n=2.$

 If $n=2$ then we have $\mathcal{CCC}(G) =   K_{m - 1} \sqcup K_2$. Therefore, for $m = 3$ it follows that $\mathcal{CCC}(G) = 2K_2$; and hence $\mathcal{CCC}(G)$ is planar. For $m\geq 5$, by Lemma \ref{kmn}, we have
 \[
 \gamma(\mathcal{CCC}(G)) = \gamma(K_{m - 1}) = \left\lceil\frac{(m - 4)(m - 5)}{12}\right\rceil.
 \]
Clearly $\gamma(\mathcal{CCC}(G)) = 0$ if $m = 5$; $\gamma(\mathcal{CCC}(G)) = 1$ if $m = 7$; $\gamma(\mathcal{CCC}(G)) = 2$ if $m = 9$. For $m\geq 11$ we have
\[
\frac{(m - 4)(m - 5)}{12} \geq \frac{7}{2} = 3.5,
\]
and so
 \[
  \gamma(\mathcal{CCC}(G)) = \left\lceil\frac{(m - 4)(m - 5)}{12}\right\rceil \geq 4.
 \]
Thus $\mathcal{CCC}(G)$ is planar if and only if $m = 3,5$; toroidal if and only if $m=7$; double-toroidal if and only if $m=9$.

\noindent \textbf{Sub case 1.2} $n\geq 3.$

 If $n\geq 3$ then we have $\mathcal{CCC}(G) =   K_{\frac{n(m - 1)}{2}} \sqcup K_n$. By Lemma \ref{kmn}, we have
 \[
 \gamma(\mathcal{CCC}(G)) = \gamma(K_{\frac{n(m - 1)}{2}}) + \gamma(K_n) = \left\lceil\frac{(mn - n - 6)(mn - n - 8)}{48}\right\rceil + \left\lceil\frac{(n - 3)(n - 4)}{12}\right\rceil.
 \]
 Clearly $\gamma(\mathcal{CCC}(G)) = 0$ if $n=3, m=3$ or $n=4, m=3$. $\gamma(\mathcal{CCC}(G)) = 1$ if $n=3, m=5$; $\gamma(\mathcal{CCC}(G)) = 2$ if $n=4, m=5$ or $n=5, m=3$ or $n=6, m=3$ or $n=7, m=3$; $\gamma(\mathcal{CCC}(G)) = 3$ if $n=3,m= 7$. If $n = 3$ and $m\geq 9$ then
 \[
\frac{(mn - n - 6)(mn - n - 8)}{48} = \frac{(m - 3)(3m - 11)}{16} \geq 6.
\]
Therefore
\[
\gamma(\mathcal{CCC}(G)) = \left\lceil\frac{(mn - n - 6)(mn - n - 8)}{48}\right\rceil + \left\lceil\frac{(n - 3)(n - 4)}{12}\right\rceil \geq 6.
\]
If $n = 4$ and $m \geq 7$ then
\[
\frac{(mn - n - 6)(mn - n - 8)}{48} = \frac{(2m - 5)(m - 3)}{6} \geq 6.
\]
Therefore
 \[
\gamma(\mathcal{CCC}(G)) = \left\lceil\frac{(mn - n - 6)(mn - n - 8)}{48}\right\rceil + \left\lceil\frac{(n - 3)(n - 4)}{12}\right\rceil \geq 6.
\]
If $n = 5$ and $m \geq 5$ then
\[
\frac{(mn - n - 6)(mn - n - 8)}{48} = \frac{(5m - 11)(5m - 13)}{48} \geq \frac{7}{2} = 3.5 \text{ \, and \,} \frac{(n - 3)(n - 4)}{12} = \frac{1}{6}.
\]

Therefore
 \[
\gamma(\mathcal{CCC}(G)) = \left\lceil\frac{(mn - n - 6)(mn - n - 8)}{48}\right\rceil + \left\lceil\frac{(n - 3)(n - 4)}{12}\right\rceil \geq 5.
\]
If $n = 6$ and $m \geq 5$ then
\[
\frac{(mn - n - 6)(mn - n - 8)}{48} = \frac{(m - 2)(3m - 7)}{4} \geq 6 \text{ \, and \,} \frac{(n - 3)(n - 4)}{12} = \frac{1}{2}.
\]

Therefore
 \[
\gamma(\mathcal{CCC}(G)) = \left\lceil\frac{(mn - n - 6)(mn - n - 8)}{48}\right\rceil + \left\lceil\frac{(n - 3)(n - 4)}{12}\right\rceil \geq 7.
\]
If $n = 7$ and $m \geq 5$ then
\[
\frac{(mn - n - 6)(mn - n - 8)}{48} = \frac{(7m - 13)(7m - 15)}{48} \geq \frac{55}{6} \text{ \, and \,} \frac{(n - 3)(n - 4)}{12} = 1.
\]

Therefore
 \[
\gamma(\mathcal{CCC}(G)) = \left\lceil\frac{(mn - n - 6)(mn - n - 8)}{48}\right\rceil + \left\lceil\frac{(n - 3)(n - 4)}{12}\right\rceil \geq 11.
\]
If $n \geq 8$ and $m \geq 3$ then
\[
\frac{(mn - n - 6)(mn - n - 8)}{48} \geq \frac{(8(m - 1) - 6)(8(m - 1) - 7)}{48} \geq \frac{15}{8} \text{ \, and \,} \frac{(n - 3)(n - 4)}{12} = \frac{5}{3}.
\]

Therefore
 \[
\gamma(\mathcal{CCC}(G)) = \left\lceil\frac{(mn - n - 6)(mn - n - 8)}{48}\right\rceil + \left\lceil\frac{(n - 3)(n - 4)}{12}\right\rceil \geq 4.
\]
Thus $\mathcal{CCC}(G)$ is planar if and only if $n=3, m=3$ or $n=4, m=3$; toroidal if and only if $n=3, m=5$; double-toroidal if and only if $n=4, m=5$ or $n=5, m=3$ or $n=6, m=3$ or $n=7, m=3$; triple-toroidal if and only if $n=3,m= 7$.

\noindent \textbf{Case 2.} $m$ is even.

By \cite[Proposition 2.3]{sA2020} we have $\mathcal{CCC}(G) =   K_{\frac{n(m - 2)}{2}} \sqcup 2K_n$.

\noindent \textbf{Sub case 2.1} $n=2.$

 If $n=2$ then we have $\mathcal{CCC}(G) =   K_{m - 2} \sqcup 2K_2$. Therefore, for $m = 2, 4$ it follows that $\mathcal{CCC}(G) = 2K_2$ and $3K_2$; and hence $\mathcal{CCC}(G)$ is planar. For $m\geq 6$, by Lemma \ref{kmn}, we have
 \[
 \gamma(\mathcal{CCC}(G)) = \gamma(K_{m - 2}) = \left\lceil\frac{(m - 5)(m - 6)}{12}\right\rceil.
 \]
Clearly $\gamma(\mathcal{CCC}(G)) = 0$ if $m = 6$; $\gamma(\mathcal{CCC}(G)) = 1$ if $m = 8$; $\gamma(\mathcal{CCC}(G)) = 2$ if $m = 10$. For $m\geq 12$ we have
\[
\frac{(m - 5)(m - 6)}{12} \geq \frac{7}{2} = 3.5
\]
and so
 \[
  \gamma(\mathcal{CCC}(G)) = \left\lceil\frac{(m - 4)(m - 5)}{12}\right\rceil \geq 4.
 \]
Thus $\mathcal{CCC}(G)$ is planar if and only if $m = 2,4,6$; toroidal if and only if $m=8$; double-toroidal if and only if $m=10$.

\noindent \textbf{Sub case 2.2} $n\geq 3.$

 If $n\geq 3$ then we have $\mathcal{CCC}(G) = K_{\frac{n(m - 2)}{2}} \sqcup 2K_n$. By Lemma \ref{kmn}, we have
 \[
 \gamma(\mathcal{CCC}(G)) = \gamma(K_{\frac{n(m - 2)}{2}}) + \gamma(2K_n) = \left\lceil\frac{(mn - 2n - 6)(mn - 2n - 8)}{48}\right\rceil + 2 \left\lceil\frac{(n - 3)(n - 4)}{12}\right\rceil.
 \]
 Clearly $\gamma(\mathcal{CCC}(G)) = 0$ if $n=3, m=2,4$ or $n=4, m=2,4$. $\gamma(\mathcal{CCC}(G)) = 1$ if $n=3, m=6$; $\gamma(\mathcal{CCC}(G)) = 2$ if $n=4, m=6$ or $n=5, m=2$ or $n=6, m=2$ or $n=7, m=2$; $\gamma(\mathcal{CCC}(G)) = 3$ if $n=3,m = 8$ or $n = 5, m = 4$ or $n = 6, m = 4$ or $n = 7, m = 4$. If $n = 3$ and $m\geq 10$ then
 \[
\frac{(mn - 2n - 6)(mn - 2n - 8)}{48} = \frac{(m - 4)(3m - 14)}{16} \geq 6.
\]
Therefore
\[
\gamma(\mathcal{CCC}(G)) = \left\lceil\frac{(mn - 2n - 6)(mn - 2n - 8)}{48}\right\rceil + 2 \left\lceil\frac{(n - 3)(n - 4)}{12}\right\rceil \geq 6.
\]
If $n = 4$ and $m \geq 8$ then
 \[
\frac{(mn - 2n - 6)(mn - 2n - 8)}{48} = \frac{(m - 4)(2m - 7)}{6} \geq 6.
\]
Therefore
\[
\gamma(\mathcal{CCC}(G)) = \left\lceil\frac{(mn - 2n - 6)(mn - 2n - 8)}{48}\right\rceil + 2 \left\lceil\frac{(n - 3)(n - 4)}{12}\right\rceil \geq 6.
\]
If $n = 5$ and $m \geq 6$ then
 \[
\frac{(mn - 2n - 6)(mn - 2n - 8)}{48} = \frac{(5m - 16)(5m - 18)}{48} \geq \frac{7}{2} = 3.5 \text{ \, and \,} \frac{(n - 3)(n - 4)}{12} = \frac{1}{6}.
\]

Therefore
\[
\gamma(\mathcal{CCC}(G)) = \left\lceil\frac{(mn - 2n - 6)(mn - 2n - 8)}{48}\right\rceil + 2 \left\lceil\frac{(n - 3)(n - 4)}{12}\right\rceil \geq 6.
\]
If $n = 6$ and $m \geq 6$ then
 \[
\frac{(mn - 2n - 6)(mn - 2n - 8)}{48} = \frac{(m - 3)(3m - 10)}{4} \geq 6 \text{ \, and \,} \frac{(n - 3)(n - 4)}{12} = \frac{1}{6}.
\]

Therefore
\[
\gamma(\mathcal{CCC}(G)) = \left\lceil\frac{(mn - 2n - 6)(mn - 2n - 8)}{48}\right\rceil + 2 \left\lceil\frac{(n - 3)(n - 4)}{12}\right\rceil \geq 8.
\]
If $n = 7$ and $m \geq 6$ then
 \[
\frac{(mn - 2n - 6)(mn - 2n - 8)}{48} = \frac{(7m - 20)(7m - 22)}{48} \geq \frac{55}{6} \text{ \, and \,} \frac{(n - 3)(n - 4)}{12} = 1.
\]

Therefore
\[
\gamma(\mathcal{CCC}(G)) = \left\lceil\frac{(mn - 2n - 6)(mn - 2n - 8)}{48}\right\rceil + 2  \left\lceil\frac{(n - 3)(n - 4)}{12}\right\rceil \geq 12.
\]
If $n = 8$ and $m \geq 2$ then
\[
\frac{(n - 3)(n - 4)}{12} = \frac{5}{3} \text{ \, and \,} \left\lceil\frac{(mn - 2n - 6)(mn - 2n - 8)}{48}\right\rceil \geq 0.
\]

Therefore
\[
\gamma(\mathcal{CCC}(G)) = \left\lceil\frac{(mn - 2n - 6)(mn - 2n - 8)}{48}\right\rceil + 2  \left\lceil\frac{(n - 3)(n - 4)}{12}\right\rceil \geq 4.
\]
Thus $\mathcal{CCC}(G)$ is planar if and only if $n=3, m=2,4$ or $n=4, m=2,4$; toroidal if and only if $n=3, m=6$; double-toroidal if and only if $n=4, m=6$ or $n=5, m=2$ or $n=6, m=2$ or $n=7, m=2$; triple-toroidal if and only if $n=3,m = 8$ or $n = 5, m = 4$ or $n = 6, m = 4$ or $n = 7, m = 4$. Hence the result follows.
\end{proof}
\begin{theorem}
Let $G=G(p,m,n)$. Then
\begin{enumerate}
\item $\mathcal{CCC}(G)$ is planar if and only if $n=1, m=1, p= 2,3,5$; $n=1, m=2, p=2$; $n=1, m=3, p=2$; $n=2, m=1, p=2$; $n=2, m=2, p=2$; or $n=3, m=1, p=2$.
\item $\mathcal{CCC}(G)$ is not toroidal.
\item $\mathcal{CCC}(G)$ is double-toroidal if and only if $n=2, m=1, p=3$.
\item $\mathcal{CCC}(G)$ is not triple-toroidal.
\item $\gamma(\mathcal{CCC}(G))= \begin{cases}
(p + 1)  \left\lceil\frac{(p - 4)(p - 5)}{12}\right\rceil, & \text{if $n=1, m=1, p\geq 7$}\vspace{.2cm}\\

\vspace{.2cm}

(p + 1)  \left\lceil\frac{(p^2 - p - 3)(p^2 - p - 4)}{12}\right\rceil, & \text{if $n=1, m=2, p\geq 3$}\\

\vspace{.2cm}

(p + 1)  \left\lceil\frac{(p^3 - p^2 - 3)(p^3 - p^2 - 4)}{12}\right\rceil, & \text{if $n=1, m=3, p\geq 3$}\\
(p + 1)  \left\lceil\frac{(p^m - p^{m - 1} - 3)(p^m - p^{m - 1} - 4)}{12}\right\rceil, & \text{if $n=1, m \geq 3, p\geq 2$}\vspace{.2cm}\\
(p^2 - p)  \left\lceil\frac{(p - 4)(p - 5)}{12}\right\rceil + 2  \left\lceil\frac{(p^2 - p - 3)(p^2 - p - 4)}{12}\right\rceil, & \text{if $n=2, m=1, p\geq 5$} \vspace{.4cm}\\

(p^2 - 2)  \left\lceil\frac{(p^2 - p - 3)(p^2 - p - 4)}{12}\right\rceil \\
\quad \quad \quad + 2  \left\lceil\frac{(p^3 - p^2 - 3)(p^3 - p^2 - 4)}{12}\right\rceil, & \text{if $n=2, m=2, p\geq 3$}\vspace{.4cm}\\

(p^2 - 2)  \left\lceil\frac{(p^{m - 1}(p - 1) - 3)(p^{m - 1}(p - 1) - 4)}{12}\right\rceil\\
\quad \quad \quad + 2  \left\lceil\frac{(p^m(p - 1) - 3)(p^m(p - 1) - 4)}{12}\right\rceil, & \text{if $n=2, m\geq 3, p\geq 2$}\vspace{.4cm}\\

p^2(p - 1)  \left\lceil\frac{(p - 4)(p - 5)}{12}\right\rceil + 2  \left\lceil\frac{(p^3 - p^2 - 3)(p^3 - p^2 - 4)}{12}\right\rceil, & \text{if $n=3, m=1, p\geq 3$}\vspace{.2cm}\\

4, & \text{if $n=3, m=2, p=2$}\vspace{.4cm}\\

p^2(p - 1)  \left\lceil\frac{(p^2 - p - 3)(p^2 - p - 4)}{12}\right\rceil\\
\quad \quad \quad + 2  \left\lceil\frac{(p^4 - p^3 - 3)(p^4 - p^3 - 4)}{12}\right\rceil, & \text{if $n=3, m\geq 2, p\geq 3$} \vspace{.4cm}\\

2  \left\lceil\frac{(p^{n - 1}(p^m - p^{m - 1}) - 3)(p^{n - 1}(p^m - p^{m - 1}) - 4)}{12}\right\rceil, & \text{if $n\geq 4, m\geq 1, p\geq 2$}\\
&\text{ and $p^m - p^{m - 1} \leq 2$}\\
(p^n - p^{n - 1})   \left\lceil\frac{(p^m - p^{m - 1} - 3)(p^m - p^{m - 1} - 4)}{12}\right\rceil \\
\quad \quad \quad + 2  \left\lceil\frac{(p^{n - 1}(p^m - p^{m - 1}) - 3)(p^{n - 1}(p^m - p^{m - 1}) - 4)}{12}\right\rceil, & \text{if $n\geq 4, m\geq 1, p\geq 2$}\\
&\text{ and $p^m - p^{m - 1} \geq 3$}.\\
\end{cases}$
\end{enumerate}
\end{theorem}
\begin{proof}

By \cite[Proposition 2.6]{sA2020} we have
\[
\mathcal{CCC}(G) = (p^n - p^{n - 1})K_{p^{m - n}(p^n - p^{n - 1})} \sqcup K_{p^{n - 1}(p^m - p^{m - 1})} \sqcup K_{p^{m - 1}(p^n - p^{n - 1})}.
\]

Consider the following cases.

\noindent \textbf{Case 1.} $n = 1$.

We have $\mathcal{CCC}(G) = (p + 1)K_{p^{m - 1}(p - 1)}$. For $m = 1$ and $p = 2, 3$, it follows that $\mathcal{CCC}(G) = 2K_1$ or $3K_2$ which is planar. If $m = 1$ and $p\geq 5$, by Lemma \ref{kmn} and \eqref{kn}, we have
\[
 \gamma(\mathcal{CCC}(G)) = (p + 1)\gamma(K_{p - 1}) =  (p + 1)  \left\lceil\frac{(p - 4)(p - 5)}{12}\right\rceil.
\]
Clearly $\gamma(\mathcal{CCC}(G)) = 0$ for $p = 5$. If $p \geq 7$ then
\[
\frac{(p - 4)(p - 5)}{12} \geq \frac{1}{2}
\]
and so
\[
\gamma(\mathcal{CCC}(G)) = (p + 1)  \left\lceil\frac{(p - 4)(p - 5)}{12}\right\rceil \geq 8.
\]
If $m = 2$ and $p = 2$ then $\gamma(\mathcal{CCC}(G)) = 3\gamma(K_{2}) = 0$. For $m = 2$ and $p\geq 3$, by Lemma \ref{kmn} and \eqref{kn}, we have
\[
\gamma(\mathcal{CCC}(G)) = (p+1) \gamma(K_{p(p - 1)}) = (p+1)  \left\lceil\frac{(p^2 - p - 3)(p^2 - p - 4)}{12}\right\rceil.
\]
If $p \geq 3$ then
\[
\frac{(p^2 - p - 3)(p^2 - p - 4)}{12} \geq \frac{1}{2}
\]
and so
\[
\gamma(\mathcal{CCC}(G)) = (p + 1)  \left\lceil\frac{(p^2 - p - 3)(p^2 - p - 4)}{12}\right\rceil \geq 4.
\]
If $m = 3$ then $\gamma(\mathcal{CCC}(G)) = (p+1) \gamma(K_{p^2(p - 1)})$. Therefore, if $m = 3$ and $p\geq 2$ then by Lemma \ref{kmn} and \eqref{kn}, we have
\[
\gamma(\mathcal{CCC}(G)) = (p+1) \gamma(K_{p^2(p - 1)}) = (p+1)  \left\lceil\frac{(p^3 - p^2 - 3)(p^3 - p^2 - 4)}{12}\right\rceil.
\]
Clearly if $m = 3$ and $p = 2$ then $\gamma(\mathcal{CCC}(G)) = 0$. If $p \geq 3$ then
\[
\frac{(p^3 - p^2 - 3)(p^3 - p^2 - 4)}{12} \geq \frac{35}{2}
\]
and so
\[
\gamma(\mathcal{CCC}(G)) = (p + 1)  \left\lceil\frac{(p^3 - p^2 - 3)(p^3 - p^2 - 4)}{12}\right\rceil \geq 72.
\]
If $m \geq 4$ and $p \geq 2$ then $\gamma(\mathcal{CCC}(G)) = (p+1) \gamma(K_{p^{m - 1}(p - 1)})$. Therefore,  by Lemma \ref{kmn} and \eqref{kn}, we have
\[
\gamma(\mathcal{CCC}(G)) = (p+1) \gamma(K_{p^{m - 1}(p - 1)}) = (p+1)  \left\lceil\frac{(p^m - p^{m - 1} - 3)(p^m - p^{m - 1} - 4)}{12}\right\rceil.
\]
We have
\[
\frac{(p^m - p^{m - 1} - 3)(p^m - p^{m - 1} - 4)}{12} \geq \frac{20}{12}
\]
and so
\[
\gamma(\mathcal{CCC}(G)) = (p+1)  \left\lceil\frac{(p^m - p^{m - 1} - 3)(p^m - p^{m - 1} - 4)}{12}\right\rceil \geq 6.
\]
Therefore, $\mathcal{CCC}(G)$ is planar if and only if  $n=1, m=1, p= 2,3,5$; $n=1, m=2, p=2$; or $n=1, m=3, p=2$. Also, in this case, $\mathcal{CCC}(G)$ is neither toroidal, double-toridal nor triple-toroidal.

\newpage
\noindent \textbf{Case 2.} $n = 2$.

We have $\mathcal{CCC}(G) = (p^2 - p)K_{p^{m - 1}(p - 1)} \sqcup 2K_{p^m(p - 1)}$. For $m = 1$ and $p = 2$, it follows that $\mathcal{CCC}(G) = 2K_1 \sqcup 2K_2$ which is planar.  If $m = 1$ and $p = 3$ then, by Lemma \ref{kmn} and \eqref{kn}, we have
\[
 \gamma(\mathcal{CCC}(G)) = 2\gamma(K_6) = 2.
\]
If $m = 1$ and $p\geq 5$, by Lemma \ref{kmn} and \eqref{kn}, we have
\begin{align*}
 \gamma(\mathcal{CCC}(G)) &= (p^2 - p)\gamma(K_{p - 1}) + 2\gamma(K_{p(p - 1)}) \\
 & = (p^2 - p)  \left\lceil\frac{(p - 4)(p - 5)}{12}\right\rceil + 2  \left\lceil\frac{(p^2 - p - 3)(p^2 - p - 4)}{12}\right\rceil.
\end{align*}
If $p \geq 5$ then
\[
\frac{(p^2 - p - 3)(p^2 - p - 4)}{12} \geq \frac{68}{3}
\]
and so
\[
\gamma(\mathcal{CCC}(G)) \geq 2  \left\lceil\frac{(p^2 - p - 3)(p^2 - p - 4)}{12}\right\rceil \geq 46.
\]
If $m = 2$ and $p \geq 2$ then $\mathcal{CCC}(G) = (p^2 - p)K_{p(p - 1)} \sqcup 2K_{p^2(p - 1)}$. Therefore, if $p = 2$ then $\mathcal{CCC}(G) = 2K_2 \sqcup 2K_4$ hence by \eqref{kn} we have $\gamma(\mathcal{CCC}(G)) = 2\gamma(K_4) = 0$. If $p\geq 3$, by Lemma \ref{kmn} and \eqref{kn}, we have
\begin{align*}
\gamma(\mathcal{CCC}(G)) &= (p^2 - p) \gamma(K_{p(p - 1)}) + 2 \gamma(K_{p^2(p - 1)}) \\
&= (p^2 - 2)  \left\lceil\frac{(p^2 - p - 3)(p^2 - p - 4)}{12}\right\rceil + 2  \left\lceil\frac{(p^3 - p^2 - 3)(p^3 - p^2 - 4)}{12}\right\rceil.
\end{align*}

Also,
$
\frac{(p^3 - p^2 - 3)(p^3 - p^2 - 4)}{12} \geq \frac{35}{2}
$
and so
\[
\gamma(\mathcal{CCC}(G)) \geq

2  \left\lceil\frac{(p^3 - p^2 - 3)(p^3 - p^2 - 4)}{12}\right\rceil \geq 36.
\]
If $m \geq 3$ and $p\geq 2$ then
\begin{align*}
 \gamma(\mathcal{CCC}&(G)) = (p^2 - p)\gamma(K_{p^{m - 1}(p - 1)}) + 2\gamma(K_{p^m(p - 1)}) \\
 & = (p^2 - p)  \left\lceil\frac{(p^{m - 1}(p - 1) - 3)(p^{m - 1}(p - 1) - 4)}{12}\right\rceil + 2  \left\lceil\frac{(p^m(p - 1) - 3)(p^m(p - 1) - 4)}{12}\right\rceil.

\end{align*}
Therefore, $\mathcal{CCC}(G)$ is planar if and only if $n=2, m=1, p=2$; $n=2, m=2, p=2$; or $n=3; m=1; p=2$ and double-toroidal if and only if $n=2, m=1, p=3$. In this case, $\mathcal{CCC}(G)$ is neither toroidal nor triple-toroidal.

\noindent \textbf{Case 3.} $n = 3$.

We have $\mathcal{CCC}(G) = p^2(p-1)K_{p^{m - 1}(p- 1)} \sqcup 2K_{p^{m+1}(p-1)}$. If $m = 1$ and $p = 2$ then $\mathcal{CCC}(G) = 4K_1 \sqcup 2K_4$, and so by \eqref{kn} $\gamma(\mathcal{CCC}(G)) = 2\gamma(K_4) = 0$. For $p = 3$ we have $\mathcal{CCC}(G) = 18K_2 \sqcup 2K_{18}$. Therefore,  by \ref{kmn} and \eqref{kn} we have $\gamma(\mathcal{CCC}(G)) = 2\gamma(K_{18}) = 36$. For $m = 1$ and $p \geq 3$, by Lemma \ref{kmn} and \eqref{kn} we have
\begin{align*}
\gamma(\mathcal{CCC}(G)) &= p^2(p - 1) \gamma(K_{p - 1}) + 2 \gamma(K_{p^2(p - 1)}) \\
&= p^2(p - 1)  \left\lceil\frac{(p - 4)(p - 5)}{12}\right\rceil + 2  \left\lceil\frac{(p^3 - p^2 - 3)(p^3 - p^2 - 4)}{12}\right\rceil.
\end{align*}
If $p\geq 5$ then
\[
\frac{(p^3 - p^2 - 3)(p^3 - p^2 - 4)}{12} = 776,
\]
and so
\[
\gamma(\mathcal{CCC}(G)) \geq 2  \left\lceil\frac{(p^3 - p^2 - 3)(p^3 - p^2 - 4)}{12}\right\rceil \geq 1552.
\]
If $m = 2$ and $p = 2$ then we have $\mathcal{CCC}(G) = 4K_2 \sqcup 2K_8$. By Lemma \ref{kmn} and \eqref{kn} we have
\[
\gamma(\mathcal{CCC}(G)) = 2 \gamma(K_8) = 4.
\]
If $m = 2$ and $p\geq 3$ then we have $\mathcal{CCC}(G) = p^2(p-1)K_{p(p- 1)} \sqcup 2K_{p^3(p-1)}$. By Lemma \ref{kmn} and \eqref{kn} we have
\begin{align*}
\gamma(\mathcal{CCC}(G)) &= p^2(p - 1) \gamma(K_{p(p - 1)}) + 2 \gamma(K_{p^3(p-1)}) \\
&= p^2(p - 1)  \left\lceil\frac{(p^2 - p - 3)(p^2 - p - 4)}{12}\right\rceil + 2  \left\lceil\frac{(p^4 - p^3 - 3)(p^4 - p^3 - 4)}{12}\right\rceil.
\end{align*}
If $p \geq 3$ then
\[
\frac{(p^2 - p - 3)(p^2 - p - 4)}{12} \geq \frac{1}{2}
\]

and so
\[
\gamma(\mathcal{CCC}(G)) > p^2(p - 1)  \left\lceil\frac{(p^2 - p - 3)(p^2 - p - 4)}{12}\right\rceil \geq 18.
\]
If $m \geq 3$ and $p\geq 2$ then we have $\mathcal{CCC}(G) = p^2(p-1)K_{p^{m - 1}(p- 1)} \sqcup 2K_{p^{m+1}(p-1)}$. By Lemma \ref{kmn} and \eqref{kn} we have
\begin{align*}
\gamma(\mathcal{CCC}(G)) &= p^2(p - 1) \gamma(K_{p^{m - 1}(p- 1)}) + 2 \gamma(K_{p^{m+1}(p-1)}) \\
&= p^2(p - 1)  \left\lceil\frac{(p^{m - 1}(p- 1) - 3)(p^{m - 1}(p- 1) - 4)}{12}\right\rceil \\
& \quad \quad \quad \quad \quad \quad \quad + 2  \left\lceil\frac{(p^{m+1}(p-1) - 3)(p^{m+1}(p-1) - 4)}{12}\right\rceil.
\end{align*}

We have
\[
\frac{(p^{m+1}(p-1) - 3)(p^{m+1}(p-1) - 4)}{12} \geq 13
\]
and so
\[
\gamma(\mathcal{CCC}(G)) \geq 2  \left\lceil\frac{(p^{m+1}(p-1) - 3)(p^{m+1}(p-1) - 4)}{12}\right\rceil \geq 26.
\]

Therefore, $\mathcal{CCC}(G)$ is planar if and only if $n=3, m=1, p=2$. Also, in this case, $\mathcal{CCC}(G)$ is neither toroidal, double-toridal nor triple-toroidal.

\noindent \textbf{Case 4.} $n \geq 4$.

We have
\[
\mathcal{CCC}(G) = (p^n - p^{n - 1})K_{p^m - p^{m - 1}} \sqcup 2K_{p^{n - 1}(p^m - p^{m - 1})}.
\]
Therefore, by Lemma \ref{kmn}, we have
\begin{equation}\label{1}
\gamma(\mathcal{CCC}(G)) = (p^n - p^{n - 1})\gamma(K_{p^m - p^{m - 1}}) + 2\gamma(K_{p^{n - 1}(p^m - p^{m - 1})})
\end{equation}
For $m\geq 1$ and $p\geq 2$ we have

\[
\gamma(K_{p^{n - 1}(p^m - p^{m - 1})}) \geq \gamma(K_{p^{n - 1}}) \geq \gamma(K_8) = 2,
\]
noting that $K_8$ and $K_{p^{n - 1}}$ are subgraphs of $K_{p^{n - 1}}$ and $K_{p^{n - 1}(p^m - p^{m - 1})}$ respectively. Therefore
\begin{align*}
\gamma(\mathcal{CCC}(G)) \geq 2\gamma(K_{p^{n - 1}(p^m - p^{m - 1})}) \geq 4.
\end{align*}
Further, if $p^m - p^{m - 1} \leq 2$ then, by \eqref{1} and \eqref{kn}, we have
\begin{align*}
\gamma(\mathcal{CCC}(G)) &= 2\gamma(K_{p^{n - 1}(p^m - p^{m - 1})})\\
& = 2  \left\lceil\frac{(p^{n - 1}(p^m - p^{m - 1}) - 3)(p^{n - 1}(p^m - p^{m - 1}) - 4)}{12}\right\rceil.
\end{align*}
If $p^m - p^{m - 1} \geq 3$ then, by \eqref{1} and \eqref{kn}, we have
\begin{align*}
\gamma(\mathcal{CCC}(G))

& = (p^n - p^{n - 1})   \left\lceil\frac{(p^m - p^{m - 1} - 3)(p^m - p^{m - 1} - 4)}{12}\right\rceil +\\
& \quad \quad \quad \quad 2  \left\lceil\frac{(p^{n - 1}(p^m - p^{m - 1}) - 3)(p^{n - 1}(p^m - p^{m - 1}) - 4)}{12}\right\rceil.
\end{align*}
Hence the result follows.
\end{proof}

We conclude this paper with the following characterization of $\mathcal{CCC}(G)$.

\begin{corollary}
Let $G = D_{2n}, SD_{8n}, Q_{4m}, V_{8n}$, $U_{(n, m)}$ or $G(p, m, n)$. Then
\begin{enumerate}
\item $\mathcal{CCC}(G)$ is planar if and only if $G = D_{6}, D_{8}, D_{10}, D_{12}, D_{14}, D_{16}, D_{18}, D_{20}, SD_{16}, SD_{24}, Q_{8}$, $Q_{12}, Q_{16}, Q_{20}, V_{16}, U_{(2, 2)}, U_{(2, 3)}, U_{(2, 4)}, U_{(2, 5)}, U_{(2, 6)}, U_{(3, 2)}, U_{(3, 3)}, U_{(3, 4)}, U_{(4, 2)}, U_{(4, 3)}$, \, $U_{(4, 4)}$,  $G(2, 1, 1), G(3, 1, 1), G(5, 1, 1)$,
$G(2, 2, 1), G(2, 3, 1), G(2, 1, 2), G(2, 2, 2)$ or $G(2, 1, 3)$.

\item $\mathcal{CCC}(G)$ is toroidal if and only if $G = D_{22}, D_{24}, D_{26}, D_{28}, D_{30}, D_{32}, SD_{32}, Q_{24}, Q_{28}, Q_{32}, V_{24}$, $V_{32}, U_{(2, 7)}, U_{(2, 8)},  U_{(3, 5)}$ or $U_{(3, 6)}$.
\item $\mathcal{CCC}(G)$ is double-toroidal if and only if $G = D_{34}, D_{36}, SD_{40}, Q_{36}, U_{(2, 9)}, U_{(2, 10)}, U_{(4, 5)}, U_{(4, 6)}$, $U_{(5, 2)}, U_{(5, 3)},  U_{(6, 2)}, U_{(6, 3)}, U_{(7, 2)}, U_{(7, 3)}$ or $G(3, 1, 2)$.
\item $\mathcal{CCC}(G)$ is triple-toroidal if and only if $G = D_{38}, D_{40}, Q_{40}, V_{40}, U_{(3, 7)}, U_{(3, 8)}, U_{(5, 4)}, U_{(6, 4)}$ or $U_{(7, 4)}$.
\end{enumerate}
\end{corollary}

\noindent {\bf Acknowledgements}
    The first author is thankful to Council of Scientific and Industrial Research  for the fellowship (File No. 09/796(0094)/2019-EMR-I).

config: arxiv


TITLE: First uncountable ordinal number
QUESTION [0 upvotes]: Why is $\Omega$ the first uncountable ordinal number and not $\omega^\omega$? Isnt the latter a countably infinite product of countably infinite sets and hence uncountable?

REPLY [4 votes]: The ordinal exponentiation $\omega^\omega$ is a countable set. But is is not a countable product of countable sets. Instead it is the limit of $\omega^n$, all of which are countable.
As cardinal exponentiation $\omega^\omega=2^\omega$, and the question whether or not there is a smaller uncountable cardinal is known as the continuum hypothesis, and is unprovable from the usual axioms of set theory, that is from $\sf ZFC$.

Related:

Cardinal Arithmetic versus Ordinal Arithmetic
Do $\omega^\omega=2^{\aleph_0}=\aleph_1$?


text:
\begin{document}

\bibliographystyle{abbrv}

\title{Comments on ``A New Method to Compute the 2-Adic Complexity of Binary Sequences"}

\author{Honggang Hu
\smallskip\\
School of Information Science and Technology\\
University of Science and Technology of China\\
Hefei, China, 230027\\
Email. hghu2005@ustc.edu.cn}

\date{}
 \maketitle

\thispagestyle{plain}
\setcounter{page}{1}

\begin{abstract}
We show that there is a very simple approach to determine the 2-adic complexity of periodic binary sequences with ideal two-level autocorrelation. This is the first main result by H. Xiong, L. Qu, and C. Li, IEEE Transactions on Information Theory, vol. 60, no. 4, pp. 2399-2406, Apr. 2014,  and the main result by T. Tian and W. Qi, IEEE Transactions on Information Theory, vol. 56, no. 1, pp. 450-454, Jan. 2010.
\end{abstract}

\ls{1.5}

\section{A Very Simple Approach}

Let $S=\{s_i\}_{i=0}^{+\infty}$ be a periodic binary sequence with period $N$, and $S(x)=\sum_{i=0}^{N-1}s_ix^i\in \mathbb{Z}[x]$. Let us write
$$\frac{S(2)}{2^N-1}=\frac{\sum_{i=0}^{N-1}{{s_i}{2^i}}}{2^N-1}=\frac{p}{q}$$
with $0\leq p\leq q$, and $\gcd(p, q)=1$.

\begin{definition}[\cite{KG97}]
With the notations as above, the 2-adic complexity $\Phi(S)$
of $S$ is the real number $\log_2{q}$.
\end{definition}

\begin{remark}
If $\gcd(S(2), 2^N-1)=1$, then the 2-adic complexity $\Phi(S)$
of $S$ achieves the maximum value $\log_2 (2^N-1)$.
\end{remark}

For any $0\leq\tau<N$, the autocorrelation of $S$ at shift $\tau$ is defined by
$$C_S(\tau)=\sum_{i=0}^{N-1}(-1)^{s_{i+\tau}+s_i}.$$
If $C_S(\tau)=-1$ for any $0<\tau<N$, we call $S$ an ideal two-level autocorrelation sequence \cite{GG2005}. There are three cases of $N$ such that there exists an ideal two-level autocorrelation sequence of period $N$: 1) $N=2^n-1$; 2) $N=p$, where $p$ is a prime number with $p\equiv3\ (\mbox{mod }4)$; 3) $N=p(p+2)$, where both $p$ and $p+2$ are prime numbers \cite{GG2005}.

Let $P(x)=\sum_{i=0}^{N-1}(-1)^{s_i}x^i\in \mathbb{Z}[x]$. If $S$ is an ideal two-level autocorrelation sequence, then we have
\begin{eqnarray*}
P(x)P(x^{-1})&=&\left(\sum_{i=0}^{N-1}(-1)^{s_i}x^i\right)\left(\sum_{j=0}^{N-1}(-1)^{s_j}x^{-j}\right)\ (\mbox{mod }x^N-1)\\
&=&\sum_{i=0}^{N-1}\sum_{j=0}^{N-1}(-1)^{s_i+s_j}x^{i-j}\ (\mbox{mod }x^N-1)\\
&\equiv&N+\sum_{\tau=1}^{N-1}\sum_{j=0}^{N-1}(-1)^{s_{j+\tau}+s_j}x^{\tau}\ (\mbox{mod }x^N-1)\\
&\equiv& N-x-x^2-...-x^{N-1}\ (\mbox{mod }x^N-1).
\end{eqnarray*}

As a consequence, we have
\begin{eqnarray*}
P(2)P(2^{-1})&\equiv&N-2-2^2-...-2^{N-1}\ (\mbox{mod }2^N-1)\\
&\equiv&N+1\ (\mbox{mod }2^N-1).
\end{eqnarray*}
Note that $P(2)=\sum_{i=0}^{N-1}(-1)^{s_i}2^i=\sum_{i=0}^{N-1}(1-2s_i)2^i=2^N-1-2\cdot S(2)$. Hence, we obtain the following interesting theorem.

\begin{theorem}
With the notations as above, we have
$$S(2)P(2^{-1})\equiv-\frac{N+1}{2}\ (\mbox{mod }2^N-1).$$
\end{theorem}

By a simple argument, we can show that $\gcd(N+1, 2^N-1)=1$ as did in \cite{XQL14}. It follows that $\gcd(S(2), 2^N-1)=1$ which means that the 2-adic complexity of such sequences is maximum.

\section{Conclusion}

Using the property of ideal two-level autocorrelation carefully, we find a very simple way to show that the 2-adic complexity of ideal two-level autocorrelation sequences is maximum. This is the main result in \cite{TQ10}, and the first main result in \cite{XQL14}. For the case of symmetric 2-adic complexity \cite{HF08}, the same result also holds as pointed out in \cite{XQL14}.


TITLE: General solution for: $y^{5}u_{xx}-y.u_{yy}+2u_y=0$
QUESTION [2 upvotes]: After transforming the PDE: $$y^{5}u_{xx}-y.u_{yy}+2u_y=0$$
into canonical form, I get: $$-4y^{5}.v_{\xi\eta}+2y^{2}.(v_{\xi}+v_{\eta})=0$$ where $$
\begin{cases}
\xi=\frac{y^3}{3}-x\\
\eta=\frac{y^3}{3}+x
\end{cases}
$$I have no idea finding the general solution. Hope any help from u guys!

REPLY [0 votes]: After change variables
$$\xi=y^3+3x,\quad \eta=y^3-3x$$
we get
$$u_{\xi\eta}=0$$
Then
$$u=f(\xi)+g(\eta),$$
$$u=f(y^3+3x)+g(y^3-3x).$$
This is general solution.


TITLE: Bourbaki Algebraic Structures Question 4.11 [Groups of exponent 2 are commutative and have order of a power of two in the finite case]
QUESTION [0 upvotes]: Question: If all elements of a group $\mathrm G$ other than the identity element are of order $2$, $\mathrm G$ is commutative; if $\mathrm G$ is finite, its order $\mathrm n$ is a power of $2$ (argue by induction on $\mathrm n$).
(See the answer below for an attempt.)

REPLY [0 votes]: In such a group elements $\mathrm a$ are equal to their inverses $\mathrm a'$. If $\mathrm {a,b \in G}$ then $\mathrm {ab \in G}$ and hence $\mathrm {abab = e}$. By our first observation $\mathrm {aba'b' = e}$ and hence $\mathrm G$ is commutative;
In such a group observe that the quotient with respect to any monogenous subgroup $H = \{e, a\}$ is also of exponent two given that $gHgH = ggHH = H$ for all $g \in G$. Note that this shows as a corollary that $G$ must be of even order. Suppose that $f(n)$, $n$ a positive natural number, denotes the collection of natural numbers bounded strictly between $2^n$ and $2^{(n+1)}$. If no group of exponent two with order $m \in f(n)$ exists then neither can such a group exist with order $m' \in f(n+1)$ since we have shown that this would imply the existence of a group of exponent two with order $m'/2 \in f(n)$, absurd. The base case follows from the corollary.


TITLE: The integral solution of $x^{2}-y^{3}=1 (x>1,y>1) $?
QUESTION [1 upvotes]: I know it's a special case of catalan's conjecture.Wiki says its only solution is $(3,2)$.But I cannot work  it out.Any help will be appreciated.

REPLY [0 votes]: Not finished!
Write $$(x-1)(x+1)=y^3$$
Case 1. $x$ is even then $x+1$ and $x-1$ are relatively prime so $$ x-1 = a^3$$ $$x+1 = b^3$$ where $a<b$ are relatively prime and $ab=y$. Now we have $$2=(b-a)(b^2+ab+a^2)$$
and so:

$b-a=1$ and $b^2+ab+a^2 =2$ so $$ 3a^2+3a+1 =2$$ and this is impossibile.
$b-a=2$ and $b^2+ab+a^2 =1$ so $$ 3a^2+6a+4=1$$ so $a=-1$ and $b=1$ so $y=-2$ and $x=0$ whivh is not ok again.

Case 2. $x=2z+1$ then $y=2t$ so $$z(z+1)=2t^3$$
Since $z,z+1$ are relatively prime we have

$z=2a^3$ and $z+1=b^3$, so $2a^3=b^3-1= (b-1)(b^2+b+1)$. So $$b-1 = 2p^3$$ $$b^2+b+1=q^3$$ where $p,q$ are relatively prime...
$z=a^3$ and $z+1=2b^3$, so $2b^3= a^3+1=(a+1)(a^2-a+1)$. So $$a+1 = 2p^3$$ $$a^2-a+1=q^3$$ where $p,q$ are relatively prime...


TITLE: Differential equations notations confusion
QUESTION [1 upvotes]: Given these differential equations:
$\frac{d^2x}{dt^2} = 2\Omega\frac{dy}{dt}\sin(\lambda) - \frac{g}{L}x$
$\frac{d^2y}{dt^2} = -2\Omega\frac{dx}{dt}\sin(\lambda) - \frac{g}{L}y$
Now making the following substitutions:
$\frac{dx}{dt} = u$ and $\frac{dy}{dt} = v$ we have the following differential equations
$\frac{du}{dt} = 2\Omega v\sin(\lambda) - \frac{g}{L}x$
$\frac{dv}{dt} = -2\Omega u\sin(\lambda) - \frac{g}{L}y$
Now here is where I get confused, note that we can write $\frac{du}{dt} = f(t,u)$ and likewise for the other equation. But if that is so, then what would be my unknown variable for the first equation? Or is it wrong to write $\frac{du}{dt} = f(t,u)$?

REPLY [1 votes]: I think if you write the system as follows, it gets simpler, although it takes time.
$$D^2x=aDy-bx, ~~~\frac{dx}{dt}=Dx\\ D^2y=-aDx-by,~~~\frac{dy}{dt}=Dy$$ wherein $a=2\Omega\sin(\lambda), b=\frac{g}{L}$. So we get: $$(D^2+b)x-aDy=0\\\\ (D^2+b)y+aDx=0$$ By any method you know for solving abbove system, one gets: $$[(D^2+b)^2+a^2D^2]y=0$$ and $$[(D^2+b)^2+a^2D^2]x=0$$ Each of the above can converetd to standard form as, for example for $y(t)$, : $$[(D^2+b)^2+a^2D^2]y=0\to y^{(4)}+(2b+a^2)y''+b^2y=0$$ which  can be solved easily.


TITLE: solving second order non-homogeneous differential equation 2
QUESTION [1 upvotes]: I have a problem on solving this differential equation.
$
y=c_{1}+c_{2}e^{-2x}-cos2x-1/2(sin2x-cos2x)
$
I reached :
$
y''+2y'=4sin2x
$
as answer but I'm not sure.
my step by step solution is :
$
y_{h}=c_{1}+c_{2}e^{-2x}
$
$
w(1,e^{-2x})=-2e^{-2x}
$
$
u_{1}=\int([-e^{2x}*4sin2x]/-2e^{-2x})=> u_{1}=-cos2x
$
$
u_{2}=\int(4sin2x/-2e^{-2x})=> u_{2}=-1/2e^{2x}(sin2x-cos2x)
$
$
y_{p}=-cos2x-1/2e^{2x}(sin2x-cos2x)
$
$
y=c_{1}+c_{2}e^{-2x}-cos2x-1/2e^{2x}(sin2x-cos2x)
$

REPLY [0 votes]: i think it is easier to solve the equation for $y'.$ so let $u = y'.$ then $u$ satisfies $$u' + 2u = 4\sin 2x\tag 1$$ the homogeneous solution is $$u_h = -2ce^{-2x} $$ trying a particular solution of the form $$u = a\cos 2x + b \sin 2x, u' = -2a\sin 2x + 2b \cos 2x  \tag 2$$  subbing $(2)$ in $(1),$  we have $$(-2a+2b)\sin 2x + (2b +2a)\cos 2x=4 \sin 2x $$ so that we can set $$-2a + 2b = 4, 2a + 2b = 0\to b = 1, a = -1 $$ giving $$u_p = \sin 2x - \cos 2x $$
the general solution is $$ u = y' = -2ce^{-2x} + \sin 2x - \cos 2x \tag 3 $$
integrating $(3)$ gives $$y = ce^{-2x}-\frac12 \cos 2x -\frac12\sin 2x + d $$ where $c,d$  are arbitrary constants.


TITLE: Breaking a determinant into eight pieces
QUESTION [1 upvotes]: From Strang, Introduction to Linear Algebra, 4th ed. p. 250. This is an example whose answer is given in the text but I'm confused. I've paraphrased and corrected what I think is a typo in the first matrix (row 3 + row 3 changed to row 3 + row 2).
How is the determinant of M related to the determinant of A? Rows of M are combinations of the rows of A.
$$
M=
\begin{bmatrix}  \text{row 1 + row 3} \\ \text{row 2 + row 1} \\ \text{row 3 + row 2} \\  \end{bmatrix}
$$
M can be split into eight matrices:
$$
\det M=
\begin{vmatrix}  \text{row 1 + row 3} \\ \text{row 2 + row 1} \\ \text{row 3 + row 2} \\  \end{vmatrix}
=  \begin{vmatrix} \text{row 1} \\ \text{row 2} \\ \text{row 3} \end{vmatrix}
+ \begin{vmatrix} \text{row 3} \\ \text{row 2} \\ \text{row 3} \end{vmatrix}
+ \begin{vmatrix} \text{row 1} \\ \text{row 1} \\ \text{row 3} \end{vmatrix}
+ \cdots
+ \begin{vmatrix} \text{row 3} \\ \text{row 1} \\ \text{row 2} \end{vmatrix}
$$
All but the first and last have repeated rows and zero determinant.
My question: By the rule that $$\begin{vmatrix} a + a^\prime  & b + b^\prime \\ c & d \end{vmatrix} = \begin{vmatrix} a & b \\ c & d \end{vmatrix} + \begin{vmatrix} a^\prime  & b^\prime \\ c & d \end{vmatrix}$$ I'd have thought that the first three matrices (before the ellipsis) would suffice to produce the determinant of M. Why do we need the other bunch?

REPLY [2 votes]: Let's apply the rule you quoted once:
$$
\det M=\left|
\begin{matrix}
\text{row 1}+\text{row 3}\\
\text{row 2}+\text{row 1}\\
\text{row 3}+\text{row 2}\\
\end{matrix}
\right|
=
\left|
\begin{matrix}
\text{row 1}\\
\text{row 2}+\text{row 1}\\
\text{row 3}+\text{row 2}\\
\end{matrix}
\right|+
\left|
\begin{matrix}
\text{row 3}\\
\text{row 2}+\text{row 1}\\
\text{row 3}+\text{row 2}\\
\end{matrix}
\right|
$$
Now you apply the rule to the second row, and it gives $2\cdot 2=4$ terms. Lastly apply it to the third row to get all $2\cdot 2\cdot 2=8$ terms.
Each time you apply the rule to a row, the number of terms doubles.


TITLE: How to find the total derivative of a $\mathbb{R}^{n^2}$ function?
QUESTION [1 upvotes]: I'm studying Real Analysis and my homework is to find some total derivatives using curves. For instance:
let $f:\mathbb{R}^9 \to \mathbb{R}^9$ be such that $f(M) = M^2$, then $Df_{M_0}(v)= vM_0+ M_0v, \hspace{0.2cm} \forall v \in \mathbb{R^9}$.
Clearly $f$ is differentiable. Now, choose $\gamma$ of class $C^1$ such that $\gamma:I \to \mathbb{R}^9$ and $\gamma(0)=M_0$, $\gamma'(0) = v$. Define the curve $\sigma = f \circ \gamma$.
Now, note that ${D \sigma}_0(1) = \frac {d}{dt}\sigma(t) \bigg|_{t=0}= Df_{\gamma(0)}{D\gamma}_0(1)= Df_{\gamma(0)}(v) = Df_{M_0}(v)$.
Then $D\sigma_0 (1) = D \sigma_0  = \frac{d}{dt} f \circ \gamma \bigg|_{t=0} =  \frac{d}{dt}\gamma(t)^2 \bigg|_{t=0}= \gamma'(0) \gamma(0) + \gamma(0)\gamma'(0) = vM_0+M_0v.$
My questions is, how can I use that to find $Dh_0(v)$ and $Dg_0(v)$ where $h:U \subset\mathbb{R}^{n^2} \to \mathbb{R}^{n^2}$ is given by $h(M) = M^{-1}$ and $g:\mathbb{R}^9 \to \mathbb{R}^9$ is given by $G(M) = M^t$.
I know, $h$ and $g$ are differenciables and I would like to use $\gamma$ like the example given above, but for $Dh_0$ I will have $\frac {d}{dt} \gamma^{-1}(t) \bigg|_{t=0}$ but $\gamma(t) \subset \mathbb{R}^{n^2}$, how can I solve that?
And what is $\frac{d}{dt} \gamma^t(t)$?

REPLY [1 votes]: If $B$ is a continuous bilinear function, then $B$ is differentiable at any pair $(x, y)$ and its derivative is given by $B(x, y) \cdot (h, k) = B(x,k)+B(h,y).$ Apply this with $B(f,g)=fg$ at the point $(x, y) = (M, M)$ with $(h, k) = (v, v).$


TITLE: Are there any known barriers to some approach for solving P vs. NP?
QUESTION [8 upvotes]: Are there any known barriers to show the following invariant (perhaps by some sort of induction)?
Let $\Sigma$ be some finite alphabet with $|\Sigma| \geq 2$, let $M$ be some (deciding) deterministic Turing machine with input alphabet $\Sigma$, and let $L_0 \subseteq \Sigma^{\star}$ be some non-sparse, $\mbox{NP}$-complete language.
Then at least one of the following properties hold:

$M$ doesn't terminate always.
$M$ has superpolynomial time complexity.
$L(M) \triangle L_0$ is non-sparse.

Concise problem description: $\mbox{NP} \not\subseteq \mbox{P-close}$ (according to Tsuyoshi Ito, see his answer).
Caution: This problem is equivalent to $\mbox{P} \neq \mbox{NP}$.

REPLY [8 votes]: This is a slightly more detailed version of some of my comments on your cross-posting on cstheory.stackexchange.com.
The statement which you described can be concisely written as NP ⊈ P-close.  Here P-close is the class of decision problems for which there exists a polynomial-time algorithm A such that the set of instances on which A fails to answer correctly is sparse.
It is easy to see that P ⊆ P-close ⊆ P/poly, from which it is easy to see the implications hold that NP ⊈ P/poly ⇒ NP ⊈ P-close ⇒ P≠NP.  Since NP ⊈ P-close implies P≠NP, any proof of NP ⊈ P-close must also overcome the relativization barrier and the algebrization barrier.  I do not know if the natural-proof barrier (which every proof of NP ⊈ P/poly must overcome) necessarily applies to NP ⊈ P-close.
I do not think that it is known that NP ⊈ P-close is equivalent to P≠NP as you claim.

Edit: On the contrary to what I wrote in an earlier revision, I learned that NP ⊈ P-close is indeed equivalent to P≠NP.  Although I already answered your question about barriers above, I guess that writing down the proof of this equivalence may be useful.  The proof is based on what you described on cstheory.stackexchage.com with one modification (namely, I use the result by Ogihara and Watanabe instead of Mahaney’s theorem).
As stated above, we have the implication NP ⊈ P-close ⇒ P≠NP.  We will prove the converse: NP ⊆ P-close ⇒ P=NP.
A polynomial-time k-truth-table reduction from a language L1 to a language L2 is a Turing reduction from L1 to L2 which invokes the oracle at most k times nonadaptively.  Note that a many-one reduction is a special case of a 1-truth-table reduction.  Ogihara and Watanabe [OW91] proved the following result:
Theorem [OW91].  If some sparse language is NP-complete under polynomial-time k-truth-table reducibility for some constant k, then P=NP.
Note that this theorem generalizes Mahaney’s theorem, which is the special case of the theorem where the reduction is restricted to a polynomial-time many-one reduction.
Assume NP ⊆ P-close.  Then SAT ∈ P-close.  Equivalently, there exists a language L∈P such that the symmetric difference S=SAT△L is sparse.  Then the following is a polynomial-time 1-truth-table reduction from SAT to S: given an input x, decide (in polynomial time) whether x∈L and decide (by invoking the oracle for S) whether x∈S, and return the XOR of the two results.  Therefore, the sparse set S is NP-complete under polynomial-time 1-truth-table reducibility.  This implies P=NP by the aforementioned theorem by Ogihara and Watanabe.
[OW91] Mitsunori Ogihara and Osamu Watanabe.  On polynomial-time bounded truth-table reducibility of NP sets to sparse sets.  SIAM Journal on Computing, 20(3):471–483, June 1991.  http://dx.doi.org/10.1137/0220030


TITLE: defining a bicategory of real-valued matrices
QUESTION [4 upvotes]: Let $\mathbf{Rel}$ be the bicategory of sets, relations, and inclusions between relations.  The following fact is well-known:

Any ordinary function $f : X \to Y$ between sets induces a pair of relations $B(1,f) : X \to Y$ and $B(f,1) : Y \to X$ in $\mathbf{Rel}$, defined explicitly by
\begin{align*}
B(1,f) &= (x,y) \mapsto y = f(x)\\
B(f,1) &= (y,x) \mapsto f(x) = y
\end{align*}
forming an adjunction $B(1,f) \dashv B(f,1)$.  In particular, the unit and the counit of this adjunction correspond to the following logical implications:
$$
\eta : x' = x \longrightarrow \exists y. y = f(x) \wedge f(x') = y
$$
$$
\epsilon : \exists x. f(x) = y \wedge y' = f(x) \longrightarrow y' = y
$$

One way of generalizing this example is by replacing sets with categories and relations by profunctors, considering the bicategory $\mathbf{Prof}$ as a proarrow equipment over $\mathbf{Cat}$.
I'm interested in a different sort of potential generalization. At least in the case of finite sets, a relation $X \to Y$ can be seen as an $X\times Y$ matrix with boolean-valued entries.  Suppose we generalize to finite matrices valued in an arbitrary field $k$.  Such matrices clearly form a 1-category (call it $\mathbf{FinMat}_k$), with composition defined by matrix multiplication. Moreover, every finite function $f : X \to Y$ induces a pair of matrices $B(1,f) : X \to Y$ and $B(f,1) : Y \to X$, corresponding to the indicator function
\begin{align*}
B(1,f) &= (x,y) \mapsto [y = f(x)]\\
B(f,1) &= (y,x) \mapsto [f(x) = y]
\end{align*}
where $[a = b]$ is 1 if $a = b$ and 0 otherwise.
Question: Is there a natural bicategorical structure on $\mathbf{FinMat}_k$ (at least for certain values of $k$), such that for every finite function $f : X \to Y$, we have an adjunction $B(1,f) \dashv B(f,1)$ in $\mathbf{FinMat}_k$? (Perhaps it is necessary to adjust the definition of $B(1,f)$ or $B(f,1)$?)
As a non-example which was my first attempt, in the case of $k = \mathbb{R}$, we could define 2-cells between real-valued matrices $\alpha : f \Rightarrow g : X \to Y$ as a family of inequalities
$$
\alpha_{x,y} : f(x,y) \le g(x,y)
$$
However, this would not verify the adjunction.  In particular, although we do have an $\eta$ inequality
\begin{align*}
[x' = x] &\le [f(x') = f(x)]
\\ &= \sum_y [y = f(x)] \cdot [f(x') = y]
\end{align*}
for every $x$ and $x'$, the $\epsilon$ inequality
$$
\sum_x [f(x) = y] \cdot [y' = f(x)] \le [y' = y]
$$
does not necessarily hold (in general, only if $f$ is injective).

REPLY [3 votes]: It's not strictly speaking true that working with a field $k$ generalizes the case of relations: composition of relations doesn't agree with composition of $\mathbb{F}_2$-valued matrices. Relations are instead matrices valued in the Boolean semiring $B = \{ 0, 1 \}$, where addition is logical OR instead of logical XOR. The Boolean semiring is fundamentally a poset, with addition coming from taking categorical coproducts and multiplication coming from taking categorical products, so it's natural to try to replace $B$ with a distributive lattice $L$ rather than a field.
I claim that this works; the crucial fact is that addition is idempotent so there's no issue with the failure of $f$ to be injective.
More generally, for a suitably nice monoidal category $V$ we can construct a bicategory out of $V$-enriched profunctors / bimodules. Composition of profunctors is defined in terms of enriched coends. In particular we can take $V$ to be a suitably nice monoidal poset, which should give generalizations of the above construction as well as Zhen Lin's suggestion of using a tropical semiring in the comments.


TITLE: Show that $SO_3(\mathbb{Z}) \simeq SO_3(\mathbb{Z}/3\mathbb{Z}) $
QUESTION [3 upvotes]: I have read the surprising fact that $SO_3(\mathbb{Z}) \simeq SO_3(\mathbb{Z}/3\mathbb{Z})  $.  At first I could only come up with diagonal elements of $SO_3$ such as:
$$\left[ \begin{array}{rrr} -1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 1 \end{array} \right] $$
However, then I was able to come up with rotations:
$$\left[ \begin{array}{rrr} 0 & 1 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & 1 \end{array} \right] $$
This rotation group needs to preserve the cube $\{ -1, 1\}^3$, and the are 24 symmetries of the cube, so $|SO_3(\mathbb{Z})| \leq 24$.
How can I show this is an isomorphism?

REPLY [6 votes]: For a simple explanation : a matrix in $O_n(\mathbb{Z})$ can only have $0$ and $\pm 1$ as coefficients, so reducing modulo $3$ is injective.


TITLE: Covariance between previous and next occurrence.
QUESTION [2 upvotes]: Consider a Poisson process where the time between occurrences is random from a distribution with density function $f(t)$. Assume that we are at a random point in time $T$, so likely between two occurrences, say $O_1$ and $O_2$. Then my question is

What is the covariance between the length of $[O_1,T]$ and the length of $[T,O_2]$?

Thanks for any help.

REPLY [3 votes]: Let $\tau$ be distribution of inter-arrival times and let $Z=O_2-O_1=O_2-T+(T-O_1)=Y+X$ where $X,Y|Z\sim Unif(0,Z)$. The probability of $T$ landing in an inter-arrival period of length $t$ is proportional to $tf_{\tau}(t)$, hence $$f_Z(t)=\frac {tf_{\tau}(t)}{\mu_\tau}$$
Then conditioning on $Z$ yields $$E(XY)-E(X)E(Y)=E(X(Z-X))-\frac 1 4 E(Z)^2=\frac 1 6E(Z^2)-\frac 1 4E(Z)^2=\frac 1 {\mu_\tau}(\frac {E(\tau^3)
}6-\frac {E(\tau^2)^2}{4\mu_\tau})$$
at the same time $$var(X)=var(Y)=E(\frac 1 {12}Z^2)+var(\frac 1 2 Z)=\frac {E(\tau^3)}{12\mu_\tau}+\frac {E(\tau^3)} {4\mu_\tau}-\frac {E(\tau^2)^2}{4\mu^2_{\tau}}=\frac 1 {\mu_\tau}(\frac {E(\tau^3)}{3}-\frac{E(\tau^2)^2}{4\mu_{\tau}})$$
Hence correlation coefficient is
$$\rho=\frac{2E(\tau^3)E(\tau)-3E(\tau^2)^2}{4E(\tau^3)E(\tau)-3E(\tau^2)^2}=\frac {2\kappa\sigma^3\mu-\mu^4-3\sigma^4}{4\kappa\sigma^3\mu+6\sigma^2\mu^2+\mu^4-3\sigma^4}=\frac{2\kappa c_v-c_v^4-3}{4\kappa c_v+6c_v^2+c_v^4-3}<\frac 1 2$$
To check correctness, plug in $\sigma=0$ to get $\rho=-1$ as expected. For $\tau$ exponential, $\kappa=2$, $c_v=1$ and $\rho=0$ as expected. We also see that by making $\kappa$ large we can approach $\rho = \frac 1 2$, but for $\kappa=0$, $\rho<0$ - as expected.

Since $\rho\ge -1$, we also get probabilistic proof that $$E(\tau^2)^2\le E(\tau^3)E(\tau)$$
for non-negative $\tau$.


TITLE: The ring of integers of a cubic number field generated by a root of $x^3-2x-2$
QUESTION [3 upvotes]: Let $\alpha$ be a root of the polynomial $f(x) = x^3-2x-2$, and let $K = \mathbb{Q}(\alpha)$. Show that $\mathcal{O}_{K} = \mathbb{Z}[\alpha]$.

I know the following
$$\text{disc}(1,\alpha,\alpha^2)=-76$$
$$\text{disc}(1,\alpha,\alpha^2)=[\mathcal{O}_K:\mathbb{Z}[\alpha]]^2\text{disc}(K)$$
It follows that $[\mathcal{O}_K:\mathbb{Z}[\alpha]]$ equals $1$ or $2$. I don't know how to complete from there, any one can help!
Thanks in advance.

REPLY [4 votes]: There is a tedious way and a slick way.
Tedious way:  Since the index is $1$ or $2$, the quotient $\mathcal O_K/\mathbf Z[\alpha]$ has size $1$ or $2$.  Therefore the group is killed by doubling, so $2\mathcal O_K \subset \mathbf Z[\alpha]$.  Thus $\mathbf Z[\alpha] \subset \mathcal O_K \subset (1/2)\mathbf Z[\alpha]$, which means you can just run through coset representatives $\beta_i$ for $((1/2)\mathbf Z[\alpha])/\mathbf Z[\alpha]$ to see which ones are algebraic integers: if $\beta_i$ is an algebraic integer, then the whole coset $\beta_i + \mathbf Z[\alpha]$ consists of algebraic integers, and if $\beta_i$ isn't an algebraic integer, then nothing in $\beta_i + \mathbf Z[\alpha]$ is an algebraic integer.
As representatives $\beta_i$ use
$(a/2) + (b/2)\alpha + (c/2)\alpha^2$ where $a, b, c \in \{0,1\}$. That is $8$ numbers to check. Well, really it's $7$ numbers to check since there the representative $0$, corresponding to the coset $\mathbf Z[\alpha]$, obviously is inside $\mathcal O_K$.  Not a single one of those $7$ nonzero numbers turns out to be an algebraic integer. For example, $\alpha/2 + \alpha^2/2$ is a root of $x^3 - 2x^2 - x - 1/4$. (This must be the minimal polynomial of $\alpha/2 + \alpha^2/2$ over $\mathbf Q$, granting that it really has that number as a root, since every number outside of $\mathbf Q$ in a cubic field has degree $3$ over $\mathbf Q$.) The only coset in $((1/2)\mathbf Z[\alpha])/\mathbf Z[\alpha]$ consisting of algebraic integers is the zero coset, and that means $\mathcal O_K = \mathbf Z[\alpha]$.
Slick way: the number $\alpha$ is a root of an Eisenstein polynomial at $2$, so $[\mathcal O_K:\mathbf Z[\alpha]]$ is not divisible by $2$ by Theorem 2.3 here. Therefore $[\mathcal O_K:\mathbf Z[\alpha]]$ must be $1$, which means $\mathcal O_K = \mathbf Z[\alpha]$.