text:
\begin{document}
\title{On the location of spectral edges in $\Z$-periodic media}
\author{Pavel Exner$^1$, Peter Kuchment$^2$ and Brian Winn$^3$}
\address{$^1$ Department of Theoretical Physics,
Nuclear Physics Institute, Academy of Sciences, 250 68 \v{R}e\v{z}
near Prague, Czech Republic}
\address{$^2$ Mathematics Department, Texas A\&M University,
College Station, Texas 77843-3368, USA}
\address{$^3$   School of Mathematics,
Loughborough University, Loughborough,
Leicestershire LE11 3TU, UK}
\begin{center}
This paper is dedicated to the memory of P. Duclos.
\end{center}
\begin{abstract}
Periodic $2$nd order ordinary differential operators on $\R$ are
known to have the edges of their spectra to occur only at the
spectra of periodic and antiperiodic boundary value problems. The
multi-dimensional analog of this property is false, as was shown
in a 2007 paper by some of the authors of this article. However,
one sometimes encounters the claims that in the case of a single
periodicity (i.e., with respect to the lattice $\Z$), the $1D$
property still holds, and spectral edges occur at the periodic and
anti-periodic spectra only. In this work we show that even in the
simplest case of quantum graphs this is not true. It is shown that
this is true if the graph consists of a $1D$ chain of finite
graphs connected by single edges, while if the connections are
formed by at least two edges, the spectral edges can already occur
away from the periodic and anti-periodic spectra.
\end{abstract}
\ams{35P99, 35Q99,47F05, 58J50, 81Q10, 05C99}
\submitto{\JPA}

\maketitle

\section{Introduction}
The following frequently used feature of spectra of periodic second order ordinary differential operators in $L^2(\R)$ is well known and follows from the standard Floquet theory \cite{MagnusWinkl,Eastham}: all edges of the spectral bands of such an operator on the whole axis can be found by considering the spectra of periodic and antiperiodic boundary value problems. In the multi-dimensional case, the role of the periodic and anti-periodic problems is played by symmetry points of the Brillouin zone. Thus, until recently, there had been a rather wide spread belief that these were the only possible locations of the spectral edges. This belief was in most cases confirmed by numerics done for crystalline or photonic crystal media. It was, however, the experience of numerical analysts that in general this claim should be incorrect. This was shown analytically to be indeed the case in \cite{HKSW}. However, after that, claims have been encountered that in the case of a single periodicity (i.e., with respect to the lattice $\Z$), the spectral edges do occur at the periodic and anti-periodic spectra only. In this work we show that even in the simplest case of quantum graphs this is not true. Namely, it is shown in Theorem \ref{T:main} that this is indeed true if the graph consists of a $1D$ chain of finite graphs connected by single edges, while if the connections are formed by two or more edges, the spectral edges can already occur away from the periodic and anti-periodic spectra. Thus, one has to be careful drawing conclusions about $1D$-like spectral behavior when the medium is $1D$-periodic.

We will be considering a graph $G$ that is an infinite ``chain'' of identical copies $\G_j$ of a graph $\G$, consecutive copies being connected by $m$ edges. E.g., Fig. \ref{F:chain} shows such a chain graph with $m=3$ connecting edges. Here the internal structure of the repeated copies $\G_j$ is not important and thus is not revealed.
\begin{figure}[ht!]
\begin{center}
\setlength{\unitlength}{2cm}
\begin{picture}(5,1)
\put(0.0,0.0){\includegraphics[width=10cm]{chain.eps}}
\put(0.8,0.35){$\Gamma_{j-1}$}
\put(2.4,0.35){$\Gamma_j$}
\put(4.0,0.35){$\Gamma_{j+1}$}
\end{picture}
\end{center}
\caption{A $\Z$-periodic ``chain'' graph $G$ with three connecting edges.}\label{F:chain}
\end{figure}
The graph $G$ is equipped with the natural action by the shifts of the group of integers $\Z$. We will denote this action as $(n,x)\in \Z\times G \mapsto \tau_n x \in G$.

We will assume $G$ to be a quantum graph (see, e.g., the survey \cite{KuAGA} and references therein). In other words, each edge $e$ is assigned a finite length $0<l_e<\infty$ in such a way that it is invariant with respect to the $\Z$-action. Correspondingly, each edge $e$ is provided with a ($\Z$-periodic on the whole $\G$) coordinate function $x_e$ (or just $x$), which identifies $e$ with the segment $[0,l_e]$. Moreover, an operator (Hamiltonian) $\H$ is defined, which acts as the (negative) second derivative $-\rmd^2/\rmd x^2$ on each edge, accompanied with the conditions at the vertices, which require the functions from its domain to be continuous, and their outgoing derivatives along edges to sum to zero at each vertex (the so called Neumann or Kirchhoff vertex conditions \cite{KuAGA}). We define the domain of $\H$ as consisting of all functions $f$ on $G$ such that
\begin{enumerate}
  \item $f\in H^2(e)$ for each edge $e$, where $H^2(e)$ is the standard Sobolev space of order $2$ on the segment $e$ (e.g., \cite{KuAGA}),
  \item
  \begin{equation}\label{E:h2cond}
  \sum\limits_e \|f\|^2_{H^2(e)}<\infty,
  \end{equation}
  \item $f$ satisfies at each vertex $v$ the vertex conditions specified above:
      \begin{equation}\label{E:Kirchhoff}
        f \mbox{ is continuous at }v \mbox{ and }
        \sum\limits_e \frac{\rmd f}{\rmd x_e}(v)=0,
      \end{equation}
      where the sum is taken over all edges adjacent to the vertex $v$ and derivatives are taken in the directions away from $v$.
\end{enumerate}
It is known that this unbounded operator $\H$ in $L^2(G)$ is self-adjoint \cite{KuAGA}.

Due to the $\Z$-periodicity of $\H$, the graph version of the standard Floquet theory applies (see, e.g., \cite{Eastham,MagnusWinkl,RS,Ku93,Ku01} for the Floquet theory for differential equations, and references in \cite{KuAGA} for its graph version). It implies the following features that we will need to use. Let $k\in [-\pi,\pi]$ be a {\bf quasi-momentum} (the name comes from the solid state physics, e.g. \cite{AM}). We consider the Floquet Hamiltonian operator $\H (k)$ that is defined similarly to $\H$, with the exception that the second condition (\ref{E:h2cond}) is replaced by the automorphicity (Floquet, cyclic) condition
\begin{equation}\label{E:h2cond_k}
  f(\tau_nx)=\rme^{\rmi kn}f(x) \mbox{ for any }(n,x)\in \Z\times G.
  \end{equation}

Notice that when $k=0$, condition (\ref{E:h2cond_k}) reduces to the $\Z$-periodicity of $f$, while $k=\pm \pi$ produces the anti-periodic condition. These two cases play an important role in our considerations.

The spectrum of $\H (k)$ is discrete and, numbered in non-decreasing order (counting multiplicity), consists of the eigenvalues $\lambda_j(k), \quad j=1,2,\dots$. The functions $\lambda_j(k)$ are called the {\bf band functions}. The closed interval $I_j$, which is the image of the $j$-th band function, $I_j:=\lambda_j([-\pi,\pi])$, is called the $j$-th {\bf band}. The multiple-valued function
$$
\lambda(k):=\{\lambda_j(k)\}
$$
is said to be the {\bf dispersion relation} and its graph $B$ is called the {\bf Bloch variety}. The level sets of the dispersion relation are often called {\bf Fermi surfaces} (although in physics this term is used for one specific level \cite{AM}).

The following result is well known both in ODE and graph situations:

\begin{theorem}\label{T:Floquet}(see \cite{RS,Eastham,KuAGA,Ku01,Ku93,Titchmarsh} and references therein) \indent
 \begin{enumerate}
 \item The band functions $\lambda_j(k)$ are continuous and piece-wise analytic.
 \item The Bloch variety is an analytic set, i.e. it can be described as the set of all zeros of an analytic function $\phi(k,\lambda)$.
 \item The spectrum of the operator $\H$ in $L^2(G)$ consists of the union of the bands:
\begin{equation}\label{spectr}
    \sigma(\H)=\bigcup\limits_{j}I_j=\bigcup\limits_{k\in[-\pi,\pi]} \sigma(\H(k)).
\end{equation}
\end{enumerate}
\end{theorem}

Our goal is to consider in the $\Z$-periodic quantum graph case the validity of the analog of the following classical theorem:

\begin{theorem}\label{T:ODE}(see \cite{RS,Eastham,Ku01,Ku93,MagnusWinkl,Titchmarsh} and references therein) In the ODE case (i.e., when the graph $G$ is just the straight line), the endpoints of the bands $I_j=\lambda_j([-\pi,\pi])$ (i.e., the extrema of the band functions) are attained at the points $k=0,k=\pm \pi$. In other words, the spectra of the periodic and anti-periodic problems provide the ends of the bands of the spectrum.
\end{theorem}

\section{The main result}
We will now discuss the validity of an analog of Theorem \ref{T:ODE} in the quantum graph case.
\begin{theorem}\label{T:main} Let $G$ be a $\Z$-periodic ``chain'' graph $G$ with $m$ connecting edges (Fig. \ref{F:chain}) and $\H$ be the corresponding Hamiltonian operator in $L^2(G)$. Then
\begin{enumerate}
  \item If $m=1$, the endpoints of the bands $I_j=\lambda_j([-\pi,\pi])$ (i.e., the extrema of the band functions) are attained at the points $k=0,k=\pm \pi$ (although, they might be attained at some other points as well). In other words, the spectra of the periodic and anti-periodic problems provide the ends of the bands of the spectrum.
  \item If $m>1$, this is not always true.
\end{enumerate}
\end{theorem}

The first statement of the theorem essentially claims that in terms of the spectral band edges, the chain quantum graphs with single connecting edges behave similarly to ODEs.

We start with the following crucial auxiliary statement:
\begin{lemma}\label{L:dimension}\indent
\begin{enumerate}
\item If some value $\lambda$ is attained by the band functions $\lambda_j(k)$ at more than two points $k$ in the segment $(-\pi,\pi]$, then there is a constant branch $\lambda(k)\equiv \lambda$ for all $k$, and thus this value is attained at all points of the segment.

\item The set $D$ of all such values $\lambda$ is discrete (possibly empty).
\item If $\lambda\notin D$, then in a neighborhood of this value all band functions are strictly monotonic on $[0,\pi]$.
\end{enumerate}
\end{lemma}
{\bf Proof of the Lemma.}\phantom{M}
Figure \ref{F:chain1} shows a link of a chain graph with $m=1$.
\begin{figure}[ht!]
\begin{center}
\setlength{\unitlength}{2cm}
\begin{picture}(3,1)
\put(0.0,0.0){\includegraphics[width=6cm]{chain1.eps}}
\put(0.4,0.6){$x_1$}
\put(2.5,0.6){$x_2$}
\put(1.4,0.4){$\Gamma$}
\end{picture}
\end{center}
\caption{One link of a chain graph with $m=1$, where the two marked points are related by the unit shift: $x_2=\tau_1 x_1$. The internal structure of the link $\G$ is irrelevant and not shown.}\label{F:chain1}
\end{figure}

Suppose that a value $\lambda$ is taken by band functions $\lambda_j(k)$ at more than two points $k\in [-\pi,\pi]$. This means that the space of (bounded) solutions of the equation $(\H-\lambda \I)u=0$ on $G$ is more than two-dimensional. Hence, there exists a non-trivial solution $u$ that vanishes with its first derivative at a point $x_1$ on the connecting edge (see Fig. \ref{F:chain1}). Since the equation is of the second order on each edge, we conclude that $u$ vanishes on the whole edge containing $x_1$. Suppose that $u$ is not identically equal to zero on the part of the graph to the right of $x_1$ (the case when this happens to the left can be treated in a similar manner). Re-defining $u$ as being equal to zero everywhere to the left of $x_1$, one has a legitimate bounded solution, which we will denote by $u$ again. Then the linear hull of the right shifts of $u$ is infinitely dimensional. However, the Floquet theory (e.g., \cite{Ku_graphs2}) implies that then the ``Fermi surface'' of all points  $k\in [0,\pi]$ where $\lambda_j(k)=\lambda$ for some $j$ must also be infinite. Then the analytic structure (see Theorem \ref{T:Floquet}) of the Bloch variety
$$
B=\{(k,\lambda)\mid \lambda_j(k)=\lambda \mbox{ for some }j\}
$$
implies that it contains the flat branch $\lambda_j(k)\equiv\lambda$ and that this can occur only at a discrete set $D$ of values of $\lambda$. This proves the first two statements of the Lemma.

Consider now a value $\lambda\notin D$. Due to the invariance of the operator $\H$ with respect to the complex conjugation (which corresponds to the time reversal symmetry of the system), the band functions $\lambda_j(k)$ are even: $\lambda_j(-k)=\lambda_j(k)$. This, together with the first statement of the Lemma and the assumption that $\lambda\notin D$ implies that all values near $\lambda$ are attained by the (continuous) function $\lambda_j(k)$ only once on $[0,\pi]$. Thus, this function is monotonic there, which proves the last claim of the Lemma.
\qed

\noindent
{\bf Proof of Theorem \ref{T:main}.}\phantom{M} Suppose that $\lambda$ is a band edge, i.e. an extremum of a band function $\lambda_j(k)$. If $\lambda\in D$, where $D$ is the set defined in the Lemma, then the statement (i) of the Lemma claims that this value $\lambda$ is attained at all values of quasi-momentum $k$, in particular for $k=\pi$ and $k=0$ that correspond to the anti-periodic and periodic problems.

Let now $\lambda\notin D$. Then the statement (iii) of the Lemma implies that the corresponding value of $k$ cannot be in the interior $(0,\pi)$ of the segment $[0,\pi]$. Thus, either $k=0$ and $\lambda$ belongs to the spectrum of the periodic problem, or  $k=\pi$ and $\lambda$ belongs to the spectrum of the anti-periodic problem. This proves the first statement of the theorem.

Let us now construct an example with $m=2$, where some of the band edges are attained not on the spectra of the periodic and anti-periodic problems. We start with the $\Z^2$-periodic graph considered in \cite[Fig. 1]{HKSW}. Its fundamental domain $W$ (with the dotted line boundary) is shown in Figure \ref{fig:quantumfd} below.
\begin{figure}[ht!]
\begin{center}
\setlength{\unitlength}{4cm}
\begin{picture}(1,1)
\put(0.0,0.0){\includegraphics[width=4cm]{quantumfd.eps}}
\put(0.26,0.41){$4$} \put(0.53,0.41){$5$} \put(0.74,0.41){$2$}
\put(0.55,0.257){$3$} \put(0.55,0.71){$1$} \put(0.7,0.74){$W$}
\put(0.05,0.41){$9$} \put(0.55,0.02){$8$} \put(0.98,0.41){$7$}
\put(0.55,0.98){$6$}
\end{picture}
\caption{The graph $\Gamma$ with fundamental region $W$.}
\label{fig:quantumfd}
\end{center}
\end{figure}
One imagines the whole graph as obtained by tiling the plane with the $\Z^2$-shifted copies of $W$. The lengths of all edges are assumed to be equal to $1$. The two basic period vectors are $v_1$ connecting vertices $4$ to $7$ and $v_2$ connecting $3$ to $6$.

It was shown in \cite{HKSW} that some of the band functions of the discrete Laplace operator on this graph attain their extremal values strictly inside the reduced Brillouin zone $[0,\pi]^2$. It was then shown that this implies the same feature for the quantum graph operator $\H$.

We obtain our example by folding this graph along the period vector $v:=v_1+v_2$. In other words, the points $x$ and $y$ such that $y=v+x$ are identified. This leads to the $\Z$-periodic graph $G$ shown in Fig. \ref{F:Zgraph}.
\begin{figure}[ht!]
\begin{center}
\setlength{\unitlength}{5cm}
\begin{picture}(1,1)
\put(0.0,0.0){\includegraphics[width=5cm]{Zgraph.eps}}
\put(0.55,0.55){$W$}

\end{picture}
\end{center}
\caption{The $\Z$-periodic graph obtained by folding the graph of Fig. \ref{fig:quantumfd}.}\label{F:Zgraph}
\end{figure}
This graph is clearly $\Z$-periodic and has $m=2$ (the two skew edges connecting the adjacent copies of the fundamental domain $W$).

Let us consider the version of the discrete Laplace-Beltrami operator $\Delta$ on functions defined on the vertices of $G$, which adds the values at all neighboring vertices,
weighted by the reciprocals of the square roots of the degrees
(valences):
$$
(\Delta f)(v):=\frac{1}{\sqrt{d_v}}\sum\limits_{u\sim v}\frac{1}{\sqrt{d_u}}f(u),
$$
where $u$ and $v$ are vertices, $d_u$ is the degree of $v$, and the sum is taken over all vertices $u$ adjacent to $v$ (in the paper \cite{HKSW} this operator was denoted $L$).
For instance, for a function $f$ defined on the vertices of the graph in Fig. \ref{fig:quantumfd} one has
$$
(\Delta f)(5)=\frac1{\sqrt{3}}\left(\frac1{\sqrt{3}}f(1)+\frac12f(3)+
\frac1{\sqrt{3}}f(4)\right),$$
and
$$ (\Delta f)(3)=\frac12\left(\frac1{\sqrt{3}}f(2)+\frac1{\sqrt{3}}f(4)+
\frac1{\sqrt{3}}f(5)+\frac1{\sqrt{3}}f(8)\right), \mbox{{\it etc}.}
$$
Then direct calculation shows that for any quasi-momentum $k$, the Floquet operator $\Delta(k)$ is given by the following $5\times 5$ matrix:
\begin{equation}\label{E:matrix}
  \Delta(k)=  \frac1{\sqrt{3}}\left(
      \begin{array}{ccccc}
        0 & 3^{-1/2} & \rme^{\rmi k}/2 & 0 & 3^{-1/2} \\
        3^{-1/2} & 0 & 1/2 & \rme^{\rmi k}/3^{1/2} & 0 \\
        \rme^{-\rmi k}/2 & 1/2 & 0 & 1/2 & 1/2 \\
        0 & \rme^{-\rmi k}/3^{1/2} & 1/2 & 0 & 3^{-1/2} \\
        3^{-1/2} & 0 & 1/2 & 3^{-1/2} & 0 \\
      \end{array}
    \right)
\end{equation}
The plot of the five eigenvalues of $\Delta(k)$ for $k=(l-1)\pi/20,l=1\ldots21$ is shown in Fig. \ref{F:plot}.

\begin{figure}[ht!]
\begin{center}
\scalebox{.6}{\includegraphics{plot.eps}}
\end{center}
\caption{The graphs over $[0,\pi]$ of the five band functions of $\Delta$.}\label{F:plot}
\end{figure}
One sees that the minimum of the third branch, as well as the maximum of the second one are attained inside the segment, and thus not at the points $k=0$ or $k=\pi$. This numerical observation can be confirmed, as in \cite{HKSW}, by a somewhat tedious explicit calculation of the dispersion relation and elementary analysis of its behavior. Again, as in \cite{HKSW}, one shows that this fact about the band functions of the discrete operator $\Delta$, in the case of all edges having equal length implies the same conclusion for the quantum graph Hamiltonian $\H$ on $G$.
This provides the required counter-example for $m=2$. It is easy to figure out that now one can create examples of this kind for any $m>1$, just by adding an unrelated structure to the example above.

Thus, the Theorem is proven.
\qed

\section{Remarks}

\begin{enumerate}
  \item The set $D$ of the exceptional values in Theorem \ref{T:main} constitutes the pure point part of the spectrum of the operator $\H$. In the case of periodic ODEs and 2nd order PDEs it is known that this part of the spectrum is empty (see, e.g., the surveys \cite{Ku01,BirSu}) and the whole spectrum is absolutely continuous (the singular continuous part is always absent in the periodic situation \cite{Ku93}).

      The reason for appearance of the pure point spectrum in the graph case is that it corresponds to compactly supported eigenfunctions \cite{Ku_graphs2}. Such compactly supported solutions are known not to exist for the second order elliptic operators.
  \item Various spectral investigations and applications of periodic quantum graphs can be found, for instance, in \cite{AEL,Exner_KrPen,Exner_rectang,volume,kuchment:91,Ku_graphs2,KuchPost,KuchVain3,Oleinik} (see also references in these works).
  \item The first statement of Theorem \ref{T:main} should be understood correctly: when $m=1$, the extrema are attained at $k=0$ and $k=\pi$. However, as the proof shows, in contrast with the ODE case, it can be also attained elsewhere, if a flat branch of dispersion relation is present.
\end{enumerate}

\section*{Acknowledgments}

The authors express their gratitude to G. Berkolaiko for his suggestion to discuss the $\Z$-periodic case and for useful comments about the proofs. The work of the first author was supported in part by the Czech
Ministry of Education, Youth and Sports within the project LC06002. The work of the second author was partially supported by the KAUST grant KUS-CI-016-04 through the Inst. Appl. Math. Comp. Sci. (IAMCS) at Texas A\&M University.
The third author has been financially supported by the National Sciences
Foundation under research grant DMS-0604859.
The authors are grateful to these agencies for the support.

\section*{References}


TITLE: Nielsen extension of Riemann surface
QUESTION [0 upvotes]: Let $S$ be a riemann surface.
If S has idea boundary curves,then the intrinsic metric on $S$ can be defined by the restriction to $S$ of poincare metric of the double of $S$.
Also this metric can be derived from the restriction to $S$ of the poincare metric of $S^N$,where $S^N$ is the Nielsen extension of $S$.I don't know what the Nielsen extension of $S$ is

REPLY [1 votes]: The below is a cut and paste from a paper from Noemi Goldberg, PAMS, 1986. I blame Preview for the typesetting quality (= not knowing about mathjax). However, the original poster could also have googled "nielsen extension".
Let So be a Riemann surface of genus g with n punctures and m holes. Assume that 6<7- 6 + 2n + 3m > 0 and that m > 0. Then So can be represented as U/G where U is the upper half-plane and G is a torsion-free Fuchsian group of the second kind. There is an infinite set I of open intervals of R U {oo} on which G acts discontinuously.    Let fi = U U L U I, where L denotes the lower half-plane. The quotient S$ = U/G is the double of So- It is a compact surface, except for finitely many punctures. The surface Sq can be represented as U/G', where G' is a torsion-free Fuchsian group of the first kind. Let D be a component of the preimage of So under the natural projection U —>U/G' and let Gi be the stabilizer of D in G'. Then the surface Si = U/Gi is the Nielsen extension of So- Given a surface So, let Sfebe the Nielsen extension of Sk-i, for k G N. Define the infinite Nielsen extension of So to be Sqo= SoUSi US2U•••.


TITLE: Evaluation of $\int \ln(x^{n+1}-1) dx$
QUESTION [3 upvotes]: How do I approach $$\int \ln(x^{n+1}-1) dx, n \in \mathbb{Z}$$
My approach would be trial and error for various $n$ in order to find a general formula but it doesn't work.

REPLY [2 votes]: If I've done my partial fractions correctly, we should get
$$
\begin{align}
\int\log(x^{n+1}-1)\,\mathrm{d}x
&=x\log(x^{n+1}-1)-(n+1)\int\frac{x^{n+1}}{x^{n+1}-1}\mathrm{d}x\\
&=x\log(x^{n+1}-1)-(n+1)x-(n+1)\int\frac{\mathrm{d}x}{x^{n+1}-1}\\
&=x\log(x^{n+1}-1)-(n+1)x+\sum_{k=0}^{n}\int\frac{\mathrm{d}x}{1-e^{-2\pi ik/(n+1)}x}\\
\end{align}
$$
The last integral is a standard logarithmic integral.

REPLY [1 votes]: Factor $x^{n+1}-1$ into factors (each of the form $\left(x-\zeta_{n+1}^k\right)$ where $\zeta_{n+1}^k$ is a root of unity). Now, you have a sum of logarithms, each of which can be integrated individually.
Note that $\zeta_{n+1}^k=\cos\left(\frac{2\pi k}{n+1}\right)+i\sin\left(\frac{2\pi k}{n+1}\right)$.


TITLE: Simpler ways of finding solutions to $\int_0^x \lfloor{x\rfloor}^2 dx=2(x-1)$
QUESTION [3 upvotes]: So I was solving the following question:

Find the number of solutions to $$\int_0^x \lfloor{x\rfloor}^2 dx=2(x-1)$$
for $x<0$.$$$$
Options: $2,3,4,5$

And I managed to show that there's no solution whenever $x$ is an integer, and obtained the following equation for whenever $x$ is not an integer:

$$\lfloor{x\rfloor}^2(\lfloor{x\rfloor}+1-x)-\frac{\lfloor{x\rfloor}(\lfloor{x\rfloor}+1)(2\lfloor{x\rfloor}+1)}{6}=2(1-x)$$

And I managed to solve it, but the method is faaaaar too lengthy(I'd made a silly error before).
Let $n$ denote $\lfloor{x\rfloor}$ and $f$ denote $x-\lfloor{x\rfloor}$.
So, the above equation transforms to:
$$f=\frac{-2n^3+3n^2+11n-12}{6(n^2-2)}$$
With some calculus, I was able to show $n=-3$ is the only possible (negative) value such that $0\leq f<1$, giving me the only answer $x=-3+\frac 67=-\frac{15}{7}$
Other methods to solve the original question are welcome.
Edit: The question was on a pen-paper test, so everything has to be done by hand.

As the answers show, it either the options or the question that's erroneous.

REPLY [3 votes]: The problem restricts $x < 0$.
The left side $f(x) = \int \dots$ is just a continuous set of line segments of increasing slope (as x goes more negative), and the right hand side $g(x) = 2(x-1)$ is just a straight line.  Since $f(0) < g(0)$, but eventually $f > g$, there is at least 1 intersection.  Because $g$ is a straight line and $f$ never curves up, there is at most 1 intersection.  So the answer is 1.
The graph here makes it more clear but isn't really necessary for the problem:
https://www.desmos.com/calculator/aprbenpnvd


TITLE: How to solve $xe^{x/250}-280e^{x/250}+280=0$
QUESTION [1 upvotes]: I need to solve the equation $$y=2500\ln{\left(\frac{70000}{70000-250x}\right)}-10x$$ for when $y=0$.
So far, I have simplified(?) the equation to give $$xe^{x/250}-280e^{x/250}+280=0$$ but at this point I am stuck. I know the two solutions are $x=0$ and $x\approx57.77$, although the latter I could only achieve by trial and error with a calculator, and I need to be able to show how I got these solutions.
Any pointers would be hugely appreciated!

REPLY [1 votes]: Calling $y = \frac{x}{250}$
$$
250 y e^y -280 e^y + 280 = 0 \Rightarrow (250y-280)e^y +280 = 0
$$
now making $z = 250y-280$
$$
ze^{\frac{z}{250}}e^{\frac{280}{250}}+280 = 0\Rightarrow 250\left(\frac{z}{250}e^{\frac{z}{250}}\right)+280 e^{-\frac{280}{250}} = 0
$$
now using the Lambert function
$\frac{z}{250} = W\left(-\frac{280}{250}e^{-\frac{280}{250}}\right)$
and finally
$$
\left\{
\begin{array}{rcl}
x & = & 0\\
x & = & 10\left(28-25 W\left(-\frac{28}{25e^{28/25}}\right)\right)\approx 57.7766
\end{array}
\right.
$$


TITLE: Minimal and characteristic polynomial of $\phi$
QUESTION [1 upvotes]: Let V be a vector space over a field F with a basis (e1, . . . , en), and the operator
$\phi : e_i = \left\{
    \begin{array}{ll}
        e_{i+1} & \mbox{if } i\ne j \\
        e_1 & \mbox{if } i=j
    \end{array}
\right.$
I want to show that the minimal polynomial of ϕ and its characteristic polynomial are both
equal to $t^n − 1$.
First at all I write the matrix of phi which is :
$\begin{pmatrix}
0 & 0 & ...&...& 0 &1\\
1 & 0&&&&.\\
 0 &1&0&&&. \\
... & ... &...&...&...&.\\
0 &0&0&...&1&0\\
\end{pmatrix}$
The I want to compute the characteristic polynomial which is :
det(t-$\phi$) = det$\begin{pmatrix}
t& 0 & ...&...& 0 &1\\
  1 & t&&&\\
 0 &1&t& \\
... & ... &...&...&...&...\\
 0 &0&0&...&t\\
 0 &0&0&...&1&t\\
\end{pmatrix}$
What can I do now?

REPLY [1 votes]: It's relatively easy to see that $\phi$ shifts the coordinates one place cyclically, and only after $n$ applications will they be in their original positions. Hence we immediately get the characteristic and minimal polynomials as $t^n-1$.
Indeed the given matrix is a companion matrix for $t^n-1$, so it is its own rational canonical form consisting of one invariant factor.


text:
\begin{document}
\title{On vosperian and superconnected vertex-transitive digraphs}

\author{ {Y. O. Hamidoune}\thanks{
Universit\'e Pierre et Marie Curie, E. Combinatoire, Case 189, 4
Place Jussieu, 75005 Paris, France. \texttt{yha@ccr.jussieu.fr}}
\and {A. Llad\'o}\thanks{
 Universitat
Polit\`ecnica de Catalunya, Dept. Matem\`atica Apl. IV;  Jordi
Girona, 1, E-08034 Barcelona, Spain. \texttt{allado@ma4.upc.edu}}
\and {S. C. L\'opez}\thanks{
 Universitat
Polit\`ecnica de Catalunya, Dept. Matem\`atica Apl. IV;  Jordi
Girona, 1, E-08034 Barcelona, Spain. \texttt{susana@ma4.upc.edu}} }

\date{}

\maketitle

\begin{abstract} We investigate the structure of a digraph  having a transitive automorphism group where every cutset of minimal cardinality consists of
 all successors or all predecessors of some vertex. We improve most of the existing results in this area.
\end{abstract}

\section{Introduction}

By a digraph, we shall mean a finite directed graph  having no loops. Let   $\Gamma =(V,E)$  be a digraph.
The set successors (resp. antecedents) of a vertex  $x\in V$ will be denoted by $\Gamma (x)$
( $\Gamma^- (x)$ ). The degree of $x$ is defined as $|\Gamma (x)|.$ If all the vertices have the same degree, the graph will be called regular
and this common value will be called the degree of $\Gamma.$
A subset $C$ of  $V$ is said to be {\em  strongly connected} if, for any two vertices $x,y$ of $C$ there is a directed
path of $\Gamma$ from $x$ to $y$ with all vertices contained in $C$.
The digraph $\Gamma$ is said to be {\em  strongly connected} if  $V$ is  strongly connected.
A subset $T$ of $V$ will be called a  {\em cutset} of $\Gamma$ if $V\setminus T$ is not  strongly connected. The minimal cardinality of a cutset   is called the {\em
 connectivity} of ${\Gamma}$.

Regular digraphs may have small connectivity. But vertex transitive digraphs have a large one. It was proved independently by
Mader \cite{mader} and Watkins \cite{watkins} that the connectivity of a  strongly connected vertex-transitive symmetric digraph with degree $d$
is greater than $2d/3.$ One of the authors proved in \cite{Ham77} that a  strongly connected vertex-transitive  digraph with degree $d$ has connectivity greater $ d/2.$
It was proved by Watkins  in \cite{watkins} that the connectivity of a  strongly connected edge-transitive graph is its minimal degree.
One of the authors proved in \cite{Ham77} that the connectivity of a  strongly connected arc-transitive digraphs is its  degree.

 A digraph $\Gamma$ with degree $d$ is said to be {\em
 superconnected} if every cutset with cardinality less than $d+1$   consists of
 all successors or all predecessors of some vertex. This notion,
 introduced in the undirected case, by Boesch and Tindell
 \cite{BoeTin84}, was  also investigated among others by Fiol
 \cite{Fio94} and Balbuena and Carmona \cite{BalCar01}. For an introduction to superconnectivity and related topics, we recommend  the
 chapter by F\`abrega and Fiol in \cite{FabFio04}.

 If any   cutset $T$  with  $|T|\le d$ and $|T|\neq  |V|-3,$ creates exactly two  strongly connected components one of them
 consists of a single vertex, the digraph $\Gamma$ will be called
 {\em vosperian}.
 Clearly  {
 vosperian} digraphs are superconnected.
  This notion was introduced by the authors of
 \cite{HamLlaSer91} as a step in their characterization of
 superconnected Abelian Cayley digraphs.  As observed by Meng in \cite{Men03},  vosperianity is basically equivalent to
 the notion of hyper-connectdness, introduced independently in the undirected case, by Boesch \cite{Boe86}.

A pair of vertices  $\{x,y\}$ will be called a {\em twin pair} (resp. {\em anti-twin pair}) if $x$ and $y$ have the same successors (resp. predecessors ). Following Meng \cite{Men03}, we shall say that a digraph having a twin pair or an  anti-twin pair is {\em reducible}. The presence
of twins or anti-twins is clearly an obstruction for vosperianity.

A recursive characterization of vosperian and superconnected Abelian
Cayley digraphs was obtained by the authors of \cite{HamLlaSer91}.
One of the authors \cite{Ham97} obtained a non-recursive characterization using
the $2$-atoms.

The description of vosperian and superconnected vertex-transitive
digraphs has  received considerable attention in recent years. Most
of the characterizations use a result due to one of the authors in
\cite{Ham97}. The case of edge-transitive undirected graphs was
considered by Meng \cite{Men03}. Liang, Meng and Zhang
\cite{LiaMenZha07} described the case of bipartite
 undirected graphs. Arc transitive digraphs are investigated by Zhang and
Meng in \cite{MenZha09}. In the last paper it is shown that a
strongly connected irreducible anti-symmetric  arc-transitive digraph is
either vosperian or bi-star superconnected. The last notion is
avoidable in our approach, but the reader may refer to
\cite{MenZha09} for its definition. It is also shown that strongly connected
irreducible anti-symmetric arc-transitive digraphs are
superconnected.

More recently, the authors of \cite{HamLlaLop} have given necessary
and sufficient conditions for an undirected vertex-transitive graph
to be vosperian. They have also proved that an irreducible
superconnected vertex transitive undirected graph is vosperian
\cite{HamLlaLop}.

We investigate in the present paper, the vosperianity and
superconnectdness of vertex-transitive digraphs. We give a complete
characterization of vosperian arc-transitive digraphs (Theorem 4)
which completes the result of \cite{MenZha09}. It states that an
arc-transitive   strongly connected digraph is vosperian if and only if it is
irreducible. In particular, this is the case if the degree is
coprime with the order of the digraph. We give also a complete
characterization of vosperian  Cayley digraphs (Theorem 6) and  a
complete characterization of irreducible superconnected Cayley
digraphs (Theorem 7). These two last characterizations extend the
corresponding ones in the directed case in \cite{HamLlaSer91,Ham97},
and the ones for the undirected case in \cite{HamLlaLop}.

The paper is organized as follows. After giving some terminology and
basic results in Section 2 we describe our main tools in Section 3.
Section 4 is devoted to the study of the arc--transitive case. We
then focus on Cayley digraphs and give the characterization of
vosperianity in Section 5 and of superconnectedness for Cayley
digraphs without twin pairs (i.e. defined by an aperiodic subset) in
Section 6.

\section{Terminology and preliminaries}

Let $\Gamma =(V,E)$ be a
digraph.
The elements of $V$ will be called {\em vertices}. The
elements of $E$ will be called {\em arcs}. Undirected graphs  can be safely identified with symmetric
digraphs. The {\em reverse} of
$\Gamma$ is the digraph  $\Gamma^{-}$ obtained by reversing the
orientation of the arcs of $E.$

More formally, $\Gamma^{-}=(V,E^-),$ where $E^-=\{(x,y) : (y,x)\in E\}.$

For a regular digraph $\Gamma,$ we denote the degree of any vertex by
$d(\Gamma).$
For a set $X\subset V$  we write $\Gamma (X)=\bigcup_{x\in X}\Gamma
(x)$  and
$\Gamma [X]$ will denote the subdigraph induced by $X$.
A {\em source} of $\Gamma$ is a  subset  $X\subset V$
such that $\Gamma^- (X)\subset X.$ A {\em sink} of $\Gamma$ is a
subset  $X\subset V$ such that $\Gamma (X)\subset X.$  It is
well known that a finite digraph is  strongly connected if and only
if it has no a proper subset which is a source (sink).
As a warning we mention that our $\Gamma (X)$ is written $\Gamma^+ (X)$
in some Graph Theory text books. Also our degree is sometimes called outdegree.

An {\em automorphism } of $\Gamma $  is a bijection $f
:V\rightarrow V$ such that $f (\Gamma (x))=\Gamma(f(x)),$  for every
$x\in V.$ A digraph is said to be {\em vertex-transitive} if, for
any pair $x,y$ of vertices, there is an automorphism that maps $x$
into $y$. A digraph is said to be {\em arc-transitive} if, for
any pair $(x,y),(x',y')$ of arcs, there is an automorphism that maps $x$
into $x'$ and maps $y$
into $y'$. It is an easy exercise to show that a  strongly connected arc-transitive digraph is also vertex-transitive,
and hence regular.

Let $G$ be a group and let $S\subset G\setminus\{1\}.$ The
digraph $\mbox{Cay} (G,S)=(G,E),$ where $E=\{(x,y): x^{-1}y\in S\}$
is called a {\it Cayley} digraph.
Recall that  $\Gamma$ is  strongly connected  if and only if  $S$ is a generating subset.
Note that the  left translation $
\gamma_a : x \mapsto ax$ is an automorphism of $\mbox{Cay} (G,S).$
A set $S$ of a group $G$ is said to be {\em left-aperiodic} if for some $x\in
G\setminus \{1\}$, $xS=S$. If both  $S$ and $S^{-1}$ are not left-periodic, we shall say that
$S$ is {\em aperiodic}.
The next lemma is just an exercise:

\begin{lemma} Let  $S$ be a subset of a group $G.$  Then
\begin{itemize}
  \item[(i)]  $\mbox{Cay} (G,S)=(G,E)$ has a pair of twins if and only if $S$ is left-periodic,
  \item[(ii)]  $\mbox{Cay} (G,S)=(G,E)$ is irreducible  if and only if $S$ is aperiodic.
\end{itemize}
\label{twincayley}
 \end{lemma}

Let $\Gamma =(V,E)$ be digraph.
 Given a subset $X\subset V,$ the {\em boundary}  of $X$ is defined as
  $$\partial_{\Gamma} (X)=\Gamma (X)\setminus X.$$

The {\em exterior} of $X$ is defined as
$
\nabla_{\Gamma} (X)=V\setminus (X\cup \Gamma (X)).
$
We write $\partial^-_{\Gamma}(X)=\partial_{\Gamma^-}(X)$ and  $
\nabla^-_{\Gamma}(X)=\nabla_{\Gamma^-}(X).
$
If the context is clear the reference to $\Gamma$ will be omitted.
Every set $X$ induces the partition (with possibly empty parts) $\{ X,\partial (X), \nabla (X)\}$ of
the vertex set with no arc from $X$ to $\nabla (X)$.

In particular,
\begin{equation}\label{boarduality}
\partial^- (\nabla (X))\subset \partial (X).
\end{equation}

The digraph $\Gamma$ is said to be $k$-{\em separable} if there is a subset $X\subset V$ such that
$\min\{|X|,|\nabla (X)|\}\ge k$.
We shall say that a subset $X$ of $V$ induces a $k$-separation  on $\Gamma$ if $k\le \min\{|X|,|\nabla (X)|\}< \infty$. In particular, $X$ induces a  $k$-separation on $\Gamma$ if and only if $\nabla (X)$ induces a  $k$-separation on $\Gamma^{-}$. Hence, $\Gamma$ is $k$-separable if and only if $\Gamma^{-}$ is  $k$-separable.

As an exercise, the reader may check that a subset $T\subset V$ is a { cutset} if and only if there is a nonempty subset $X\subset V,$ with  $\nabla (X)\neq \emptyset$
and $\partial (X)\subset T.$ One may see from (\ref{boarduality}) that  $T$ is a cutset of $\Gamma$ if and only if
$T$ is a cutset of $\Gamma ^-.$ A cutset of minimal cardinality, where $\min (\emptyset)=|V|-1,$ will be called a
{\em minimum} cutset.

For a $k$-separable digraph  $\Gamma,$ the
$kth$-{\em isoperimetric connectivity}  of $\Gamma$ is defined as
$$
\kappa_k (\Gamma)=\min \{|\partial (X)|: X\subset V \ \text{and} \ \min\{|X|,|\nabla (X)|\}\ge
k\}.
$$

A subset $F\subset V$ is called a $k$-{\em fragment} if $\min\{|F|,|\nabla (F)|\}\ge
k$ and $|\partial (F)|=\kappa_k (\Gamma )$. A $k$-{\em atom} is a $k$-fragment
of minimum cardinality.
A $k$-fragment (a $k$-atom) of $\Gamma^{-}$ is called a {\em  negative} $k$-{\em fragment} ({\em a negative $k$-atom}). We also write
$\kappa _{-k}(\Gamma)=\kappa _k(\Gamma^{-})$.

The notion of $kth$-{isoperimetric connectivity} was introduced in \cite{Ham96}.
We recall the following duality lemma:

\begin{theirlemma}[\cite{Ham08}]
Let $\Gamma =(V,E)$ be a  finite $k$-separable digraph. Then $\kappa_k(\Gamma )=\kappa_{-k}(\Gamma )$.\label{equal_kappa}
If $X$ is a $k$-fragment,  then
$$
   \partial^{-}(\nabla  (X))=\partial (X)
\ \text{and} \
   \nabla^-(\nabla (X))=X.$$

In particular, $\nabla(X)$ is a negative $k$-fragment.
\end{theirlemma}

It follows easily that $\kappa(\Gamma)=\kappa_1(\Gamma)$.
We need a special case $k=2$ of the easy next lemma:
\begin{theirlemma}[folklore]\label{katom}
Let $\Gamma =(V,E)$ be a  finite $k$-separable digraph and let $A$ be a $k$-atom with $|A|>k.$
 Then $\Gamma ^-(x)\cap A\neq \emptyset,$ for every $x\in A.$ In particular,  $A$ contains a circuit.
\end{theirlemma}

\section{Some tools}

Let $G$ be a group and let $S$ be a subset of $G$. The subgroup
generated by $S$ will be denoted by $\subgp{S}$. Let  $ A,B$ be
subsets of $ G $. The {\em Minkowski product} is defined as
$$AB=\{xy \ : \ x\in A\  \mbox{and}\ y\in
  B\}.$$

We use the following easy lemmas:

\begin{theirlemma}[\cite{manlivre}, Theorem 1]
Let $G$ be a finite group and let
 $A,B$  be  subsets of $G$
 such that $|A|+|B|>|G|$.
 Then $AB=G$.

\label{prehistorical}
 \end{theirlemma}

\begin{theirlemma}[folklore]
Let $G$ be a finite cyclic group generated by $r$ and let
 $B=\{1,r, , r^{|B|-1}\}b.$ For every subset $A\subset G,$
 such that $|AB|=|A|+|B|-1<|G|$, there is an $a\in G$ such that
$aA=\{1,r,\ldots  , r^{|A|-1}\}.$

\label{AP}
 \end{theirlemma}

Let $\Gamma =(V,E)$ be a finite digraph.
 A {\em block of imprimitivity} (or simply a block in what follows) of $\Gamma$ is
 a subset $B\subset V$ such that for every automorphism $f$ of $\Gamma$, either $f(B)=B$ or $f(B)\cap B=\emptyset$.

 Recall the following result:

\begin{theirlemma} [folklore]
Let $G$ be a finite group and let
 $S$  be  a subset of $G.$ Any block $B$ of  $\Gamma =Cay(G,S)$ with $1\in B$
 is a subgroup of $G.$
\label{bloccayley}
 \end{theirlemma}

As an easy exercise, the reader may show that a digraph $\Gamma$ is vosperian   if and only
if it is either non $2$-separable or if $\kappa _2(\Gamma )\ge d(\Gamma)+1$.
Thus, for finite digraphs Lemma \ref{equal_kappa}  implies that $\Gamma$  is non-vosperian if and only if $\Gamma^-$ is non-vosperian.

We shall use some results from \cite{Ham99}. These results were originally formulated
for directed graphs with loops.
 But they apply to our context, since the deletion (or addition) of loops does not modify the notions of $k$-fragments
and $k$-isoperimetric connectivity. We use the following result:

\begin{theirtheorem} [\cite{Ham99}] Let $\Gamma =(V,E)$ be a  finite non-vosperian vertex-transitive digraph.  Then one of the following holds:
\begin{itemize}
\item[(i)]  There is a $2$-atom of size $2$ or a negative $2$-atom of size $2.$
 \item[(ii)] There is a block which is a $2$-fragment or a negative $2$-fragment.
  \item[(iii)] Every vertex of $V$ is contained in at most two distinct $2$-atoms. Moreover the intersection of two distinct $2$-atoms has cardinality $<2.$
  \item[(iv)] Every vertex of $V$ is contained in at most two distinct negative $2$-atoms.
  Moreover the intersection of two distinct negative $2$-atoms has cardinality $<2.$
\end{itemize}
\label{asterix} \end{theirtheorem}

Note that the notion of superatoms, the smallest atoms with cardinality larger than one, is used in \cite{Ham99} instead of the close
notion of $2$-atoms used here.

\begin{corollary}[\cite{Ham99}]
Let $S$ be a  generating subset of a finite  group $G$ with $1\notin S$ such that
 $\Gamma =Cay(G,S)$ is non-vosperian.
Then there are  a subgroup $H$ and an  $a\in G$
such that  $H\cup Ha$ is a $2$-fragment or a negative $2$-fragment.
\label{vospercorog}
\end{corollary}

\proof
Let $M$ be a $2$-atom
and  let $N$ be a negative $2$-atom such that $1\in M\cap N.$ We may assume that $\min (|M|,|N|)\ge 3.$ Otherwise the result holds with $H=\{1\}.$ Moreover,  $\Gamma$ has no block which is a $2$-fragment or a negative $2$-fragment.
Otherwise the result holds by Lemma \ref{bloccayley}.

By Theorem \ref{asterix},  $1$ is contained in at most two $2$-atoms of $\Gamma$ or two $2$-atoms of $\Gamma^-.$
Up to replacing  $\Gamma$ by $\Gamma^-,$ we may assume that  $1$ is contained in at most two $2$-atoms of $\Gamma.$
Let
$H=\{x\in G: \hspace{0.2cm} xM=M\}$.
The result holds clearly if $M=H.$ Take an $a\in M\setminus H.$ We shall show that $M=H\cup Ha$.
Observe that $M$ and $a^{-1}M$ are two distinct $2$-atoms containing $1.$ Thus  for every $x\in M,$
we have $x^{-1}M=M$ or $x^{-1}M=a^{-1}M.$ Therefore either $x\in H$ or $xa^{-1}\in H$. In particular, $M\subset H\cup Ha.$ But $HM\subset M,$ by the definition of $H$.\qed

 Let $G$ be an Abelian group and let  $1\in A$ is a  $2$-atom of $Cay(G,S).$ It was proved in \cite{Ham97}, that  $A$ is a subgroup if $|A|\ge 3.$ An  example  given in \cite{HamLlaLop} shows that this conclusion may fail in the non-abelian case.

\section{Arc-transitive digraphs}

Let $a\in V.$ The {\em twin class} of $a$ is $W_a=\{x: \Gamma (a)=\Gamma (x)\}.$ We need the following lemma.

\begin{lemma}
Let  $\Gamma=(V,E)$ be   vertex-transitive digraph and let  $v$ be an element of $V$.
Then  $ \{W_a:\ a\in V\}$ is a partition of $V$. Moreover $\Gamma^-(v)=\bigcup _{a\in \Gamma^-(v)} W_a.$
 Also
$|W_v|$
 divides
both $|V|$ and
$d(\Gamma).$ In particular, $\Gamma$ is irreducible if $\gcd(|V|,d(\Gamma))=1.$
\label{twinn}
\end{lemma}

\proof
 Assume that there is a $x$ with $x\in W_a \cap W_b,$ for some $a,b\in V.$
 We have $\Gamma (x)=\Gamma (a)=\Gamma (b).$ In particular, $a\in W_b$ and hence
 $W_a=W_b.$ It follows that $\{W_a:\ a\in V\}$ is a partition of $V$.
 In particular, $|W_v| $ divides $|V|.$

Assume that   $x\in \Gamma ^- (v)$ and let $y$ be an element of $W_x.$
We have $v\in \Gamma (x)$ and $\Gamma (y)=\Gamma (x).$ Thus $y\in \Gamma ^- (v).$
It follows that $\{W_a; a\in \Gamma^-(v)\}$ is a  partition of $\Gamma^-(v)$.
Take an arbitrary $x\in V$ and an automorphism $f$ such that $f(v)=x.$
Clearly $f(W_v)=W_x$. It follows that $|W_v|=|W_x|,$ for every $x\in V.$
Therefore,  $|W_v|$ divides both $|V|$ and
$d(\Gamma).$ \qed

The next result gives a good description for vosperian arc-transitive digraphs.

\begin{theorem} A finite   strongly connected
  arc-transitive  digraph  $\Gamma =(V,E)$  of  degree $d\le |V|-4$ with $d\notin
\{1,2,4,6\}$
is vosperian if and only if it is irreducible.

\label{arctransitive} \end{theorem}

\proof
As we observed in the Introduction a reducible digraph is non-vosperian.
 Assume that $\Gamma$ is  an irreducible arc-transitive digraph which is non-vosperian. We prove the following points:

(i)  No  block  is a $2$-fragment.

Suppose to the contrary that some block $B$ is a $2$-fragment.
Take $a\in B$ and  an arc $(a,b)$ with $b\notin B.$ The set $B$ must
be an independent set,
otherwise there would exist an arc $(c,d)$ inside $B$. Since $\Gamma$ is arc-transitive, there is an automorphism $f$ with $f(c)=a,$
and $f(d)=b.$ Thus $B\cap f(B)\neq \emptyset$ but $B\neq f(B)$, contradicting the definition of  a block. Hence, $\Gamma (x)\subset
\partial (B),$ for every $x\in B.$ Since $|\Gamma (x)|\le |\partial (B)|\le\kappa _2(\Gamma)\le d,$ we have
$\Gamma (x)= \partial (B),$ for every $x\in B.$ In particular $\Gamma$
has a twin pair, a contradiction.

(ii)  No  block  is  a negative $2$-fragment.
The proof is similar to the proof of (i).

(iii) Every vertex of $V$ is contained in at least three
distinct $2$-atoms or there are distinct $2$-atoms $M,N$ with $|M\cap N|\ge 2.$

Suppose on the contrary, that two distinct $2$--atoms intersect in
at most one point, so that every pair of vertices is contained in at
most one $2$--atom, and  that every vertex is in at most two
distinct $2$--atoms.

Take a $2$-atom $A.$ Suppose that $|A|=2$. Since $|\partial
A|=\kappa_2(A)\le d$ (otherwise $\Gamma$ is vosperian) and the
digraph  has no twin pairs, $\Gamma [A]$ contains an arc $(x,y)$.
Since the degree $d\ge 3$, the automorphisms sending $(x,y)$ to
$(x,y')$ for each $y'\in \Gamma (x)$ provide at least three distinct
$2$--atoms containing $x$. Hence we may assume   that $|A|> 2$.

Let us show that $\Gamma [A]$ is a strongly connected vertex transitive
digraph. By Lemma \ref{katom},  $\Gamma [A]$ contains a circuit, say
$C=[a_1,a_2, \cdots, a_j].$ Take an arbitrary
 vertex $v\in A.$  By Lemma \ref{katom}, there is $w\in A\cap \Gamma^-(v).$
 Take an automorphism $f$ with $f(a_1,a_2)=(w,v)$. Since every pair
 of vertices is contained in a unique atom, we have $f(A)=A$.
 Therefore
$f(C)$ is a circuit in $\Gamma [A]$ containing $v.$ Thus every arc
of $\Gamma [A]$ is contained in a circuit of length at least two.
If $\Gamma [A]$ is not strongly connected, it contains a strongly connected component
$K$ which is a sink, which must have cardinality at least two. We
have $\partial (K)\subset \partial (A).$
 Hence, by the minimality of a $2$-atom  $K=A.$
 It follows that $\Gamma [A]$ is  strongly connected.
Moreover, the same argument shows that the arbitrary vertex
 $v$ can be sent to $a_2$ by an automorphism which leaves $\Gamma
 [A]$ invariant, so that this induced subgraph is vertex transitive and hence
  a regular digraph.
We shall denote the degree of $\Gamma
[A]$ by $r.$

There is an element $c\in A$ with an element $c'\in \Gamma (c)\cap \partial (A)$. By Lemma \ref{katom}, there is an arc
  $(b,c)$ contained in $A.$
  For every arc
$(x,y)\in E,$ there is an automorphism $f$
with $f (b)=x$ and $f (c)=y.$ In particular $f (A)$ is a $2$-atom containing
$\{x,y\}.$
By our hypothesis, such a $2$-atom  is  unique.
We shall denote this atom by $A_{xy}.$
Since $c$ is contained in at most two distinct $2$-atoms, $\Gamma (c)=(\Gamma(c)\cap A)\cup
  (\Gamma(c)\cap A_{cc'}).$
In particular,
$d=2r.$
Let $a$ be an element in $A\setminus\{b,c\}$ and let $a',b'$ be vertices in the boundary of $A$ such that $a'\in \Gamma (a)$ and $b'\in \Gamma (b)$.
  We have $\partial (A)\supset (\Gamma (a)\cap A_{aa'})\cup (\Gamma (b)\cap
A_{bb'})\cup (\Gamma (c)\cap A_{cc'}).$
  Thus we have using our hypothesis on atoms intersection,
   \begin{align*}
  |\partial (A)|&\ge |\Gamma
(a)\cap A_{aa'}|+|(\Gamma (b)\cap A_{bb'})\setminus A_{aa'}|+|(\Gamma (c)\cap
A_{cc'})\setminus (A_{aa'}\cup A_{bb'})|\\
&\ge |\Gamma
(a)\cap A_{aa'}|+|(\Gamma (b)\cap A_{bb'}|-1+|\Gamma (c)\cap
A_{cc'}|-2\\
&= r+r-1+r-2=
  3d/2-3>d,
   \end{align*}
   since $d>6,$ this implies a contradiction.

(iv) Every vertex of $V$ is contained in at least three
distinct negative $2$-atoms or there are distinct negative $2$-atoms $M,N$ with $|M\cap N|\ge 2.$
   The proof is exactly the same as for (iii).

By Theorem \ref{asterix}, $\Gamma$ has a $2$-atom with size $2$ or a negative
$2$-atom with size $2.$
The two cases are similar, we choose the first one. Since $\Gamma$ has
no twins, the $2$-atom
has the form $A=\{a,b\},$ with $(a,b)\in E.$

Let $v$ be the only element of
$\Gamma (b)\setminus \Gamma (a)$ and take $u\in \Gamma (b)\cap \Gamma
(a)$.
Now $\{b,v\}$ is a $2$-atom. It follows that $u\in \Gamma (v)$. Also
$\{b,u\}$ is a $2$-atom. It follows that $v\in \Gamma (u)$, a contradiction in the anti-symmetric case. Assume now that   $\Gamma$ is symmetric. A
similar reasoning proves that, $u\in\Gamma
(z)$ where $z$ is the only element of $\Gamma (a)\setminus
\Gamma (b)$. Since $\{a,u\}$ is a  $2$-atoms, it follows that
$|\Gamma(u)\cap(\Gamma (b)\cap \Gamma(a))|\ge d-4$. Thus, $|\Gamma(u)\cap
\Gamma (\{a,b\})|=d$ and hence, $\Gamma (u)\cap \nabla
(\{a,b\})=\emptyset$, a contradiction.\qed

\begin{corollary}
Let $\Gamma$ be   a  strongly connected arc-transitive  digraph  of degree $d\notin
\{2,4,6\}$  such that $\gcd(|V|,d)=1.$
Then  $\Gamma$ is vosperian.
\label{superung1}
\end{corollary}
\proof
By Lemma
\ref{twinn},
$\Gamma$ is irreducible.
 The result follows now by Theorem \ref{arctransitive}.\qed

\section{Vosperian  Cayley  digraphs}

In this section, we investigate  vosperian   Cayley digraphs.

 Let $X$ be a subset of a group $G.$ We shall  write $\tilde{X}=X\cup \{1\}.$
 We shall say that $X$ is  a {\em right $r$-coprogression},
if $G\setminus X=\{a, ra, \ldots , r^ja\},$ for some $a\in G$.
Similarly we define a {\em left $r$-coprogression}.
Notice that $S$ is  a {right} $r$-coprogression if and only if
$S$ is a left $a^{-1}ra$-coprogression.

In particular,  if $\tilde{S}$ is a right $r$-coprogression and $|S|\le |G|-4$ then \begin{equation}\label{coprogression}|\Gamma(\{1,r\})\cup \{1,r\}|=|\{1,r,\}\tilde{S}|=|S|+2,\end{equation} and
$\kappa_2(\Gamma )\le |S|.$

  \begin{theorem}
Let $S$ be a   generating subset of a finite group $G$, with $1\notin S.$
 Then $\Gamma =\mbox{Cay} (G,S)$ is  non-vosperian if and only if one of the following holds:

  \begin{enumerate}

    \item [(i)] There are a subgroup $H$  of $G$ with $|H|\ge 2,$ and  an element $a\in G$ such that
$|(H\cup Ha)\tilde{S}|\le \min (|G|-2,|H\cup Ha|+|{S}|).$
    \item  [(ii)] There are a subgroup $H$  of $G$ with $|H|\ge 2,$ and  an element $a\in G$ such that
$ |\tilde{S}(H\cup aH)|\le \min (|G|-2,|H\cup Ha|+|{S}|).$
    \item  [(iii)]  There is a $r\in G\setminus \{1\}$ such that $\tilde{S}$ is  a right $r$-coprogression and $|G|-4\ge |S|.$
  \end{enumerate}

\label{vosperg}
\end{theorem}

\proof
Let us first prove the sufficiency.

If there exist a subgroup $H$  with $|H\ge 2$ and an element $a\in G$ such that  (i) or (ii)  holds,  then $\Gamma $
 is $2$-separable and $\kappa_2(\Gamma )\le |S|$.
Similarly, if there exists a $r\in G\setminus \{1\}$, such that $\tilde{S}$ is a right $r$-coprogression, then
$|\Gamma(\{1,r\})\cup \{1,r\}|=|\{1,r,\}\tilde{S}|=|S|+2,$  and hence
 $\Gamma $ is $2$-separable and $\kappa_2(\Gamma )\le |S|$.   So each of these conditions is a necessary one.

Suppose now that $\Gamma$ is non-vosperian.

  By Corollary \ref{vospercorog}, there are a subgroup $H$ and an element $a\in G$
such that $H\cup Ha$ is a $2$-fragment or a negative $2$-fragment. The two cases are similar (and equivalent up to duality), so we shall consider
 only the case where $H\cup Ha$ is a $2$-fragment.
Assume first that  $|H|\ge 2.$
Since $H\cup Ha$ is a $2$-fragment, we have $|(H\cup Ha)\tilde{S}|=|\Gamma (H\cup Ha)|\le |G|-2.$ We have also
$|H\cup Ha|+|S|\ge |H\cup Ha|+\kappa_2(\Gamma)=|(H\cup Ha)\tilde{S}|.$  Therefore   (i) holds.

Assume now that $|H|=1.$
 Let $M=\{1,r\}$. By the definition of a $2$-atom we have $|\{1,r\}\tilde{S}|=\kappa_2(\Gamma)+2\le |{S}|+2.$
 We may assume that $\kappa_2(\Gamma)=|S|.$ Otherwise $r\tilde{S}=\tilde{S},$ and hence $\tilde{S}$ is a union of right $\subgp{r}$-cosets, and thus Condition (i) holds with $H=\subgp{r}$.
  Hence,

\begin{equation}\label{eq2g}
\kappa_2(\Gamma)=|S| \ \text{and thus } \ |\{1,r\}\tilde{S}|=|{S}|+2.
\end{equation}

 Let $K$ be the cyclic subgroup generated by $r$.
If $G=K,$ then by (\ref{eq2g}), $\tilde{S}$ is a progression and also a coprogression since $r$ generates $G.$
So we may assume that $K\neq G.$

Let
$\tilde{S}=S_1\cup \cdots\cup S_j$ be the partition of $\tilde{S}$ induced by the partition of $G$ into right $K$-cosets. We have $j\ge 2$ since $K\neq G$. We shall assume that $|S_1|\le
\cdots \le |S_j|$. We must have $|S_2|=|K|,$ since otherwise $|\{1,r\}{S_i}|\ge |S_i|+1,$ for all
$1\le i \le 2$. It would follows that $|\{1,r\}\tilde{S}|\ge |S_1|+1+ |S_2|+1 +\sum_{i\ge 3}|S_i|\ge |\tilde{S}|+2,$
contradicting (\ref{eq2g}). It follows also that $|\{1,r\}{S_1}|= |S_1|+1.$ Since $r$ generates $K$, Lemma \ref{AP} implies that
$S_1$ is a right progression with ratio $r$. Note that $KS_1\setminus S_1$ is also a right progression.

{\bf Subcase 2.1} $j|K|=|G|.$ In this case $G\setminus \tilde{S}=KS_1\setminus S_1$ is also a right progression.

{\bf Subcase 2.2} $j|K|\le |G|-|K|.$ We  have
$(j-1)|K|+|S_1|-1=|\tilde{S}|-1=\kappa _2(\Gamma)\le |K\tilde{S}|-|K|=(j-1)|K|.$ Thus $|S_1|=1.$
In particular, $K$ is clearly a $2$-fragment and (i) holds with $H=K$ and $a=1$. \qed

\section{Superconnected Cayley digraphs}

In this section we characterize irreducible  superconnected Cayley digraphs.
As we have seen, these Cayley digraphs are defined by an aperiodic subsets.

\begin{theorem}
An irreducible  strongly connected Cayley digraph $\Gamma=Cay(G,S)$  on a finite group $G$
is superconnected
if and only if one of the following conditions holds:
\begin{itemize}
 \item[(i)]  $\Gamma$ is vosperian,
  \item[(ii)] for some $r\in G,$  $\tilde{S}$ is a right $r$-coprogression with $ r^{-1}\notin S$ and $|G|-4\ge |S|$.
 \end{itemize}

\label{superg}
\end{theorem}

\proof
Take  a  subset $S$ of  $G$
such  that  $\Gamma=\mbox{Cay} (G,S).$
Since $\Gamma$ is  strongly connected, $S$ must be a generating subset of $G.$

 Condition (i) implies obviously that $\Gamma$ is superconnected.  Assume that (ii) holds
and let $P=\subgp{r}\cap \tilde{S}.$ By Lemma \ref{twincayley},  $S$ is
aperiodic, and thus $|P|\ge 2.$ Note that, since $\tilde{S}$ is a coprogression $\kappa (\Gamma)=|S|$. Take now any fragment $F$ of $\Gamma$. By a left-translation we can assume that
$1\in F.$ We must have $F \subset H,$ since otherwise $|FH|\ge
2|H|,$ and hence by Lemma \ref{prehistorical}, $$|F\tilde{S}|\ge
|F(\tilde{S}\setminus H)|=|(F)H(\tilde{S}\setminus
H)|=|(FH)(\tilde{S}\setminus H)|=|G|,$$ a contradiction. Now we have
$|F|+|\tilde{S}|-1=|F\tilde{S}|=|G\setminus
H|+|FP|=|\tilde{S}|-|P|+|FP|.$ In particular, $|H|-1\ge
|FP|=|F|+|P|-1.$ By Lemma \ref{AP}, $F$ is a $r$-progression. By a
left-translation, we may assume that $F=\{1,r, \ldots ,
r^{|F|-1}\}.$ Since $|H|-1\ge |FP|,$ we have $\Gamma  ( r^{|F|-1})=
\partial (F).$ Thus, $\mbox{Cay}(G,S)$ is  superconnected.

Let us now prove the necessity.

Suppose that  (i) and (ii) do not hold. Since $\Gamma$ is non-vosperian, by Theorem \ref{vosperg} we are in one of the following cases:

{\bf Case} 1. There are a subgroup $H$ and an element $a\in G$ with $|H|\ge 2$ such that
   $|G|-2\ge|(H\cup Ha) \tilde{S}|=|H\cup Ha|+| \tilde{S}|-1$.

   Put $T=(H\cup Ha) \tilde{S}\setminus (H\cup Ha).$ Clearly $T$ is a minimum cutset  with $HT=T.$
   We can not have $T=\Gamma (x),$ for some $x,$ otherwise $HxS=xS,$ and $S$ would be right-periodic, a contradiction.
   Also, we can not have $T=\Gamma^- (y),$ for some $y,$ otherwise $HyS^{-1}=yS^{-1},$
   and $S^{-1}$ would be right-periodic, a contradiction.
   Thus $\Gamma$  is non superconnected.

{\bf Case} 2.  There are a subgroup $H$ and an element $a\in G$ with $|H|\ge 2$ such that
    $|G|-2\ge|(H\cup Ha) \tilde{S}^{-1}|=|H\cup Ha|+| \tilde{S}|-1$. This case is similar to the previous one.

 {\bf Case} 3. For some $r\in G$,  $\tilde{S}$ is a right $r$-coprogression and $|S|\le |G|-4$.  Put $H=\subgp{r}$ and $G\setminus \tilde{S}\subset Ha$ for some $a\in G$.

{\bf Subcase} 3.1 $a\notin H$.
Since $\tilde{S},$ is a coprogression, we have $H\subset \tilde{S}.$
Since  $(a^{-1}Ha)\cap Ha=\emptyset,$ we have  $a^{-1}Ha\subset \tilde{S}.$
Take an arbitrary $h\in H\setminus \{1\}.$ We have $$\Gamma (ha)=haS\supset ha(a^{-1}Ha\setminus \{1\})=Ha\setminus \{ha\}.$$
It follows that $\Gamma[Ha]$ is a complete symmetric digraph.
Since $H \subset \tilde{S},$ we have $r, r^{-1} \in S$. Thus, $\Gamma[\{1,r\}]$ is a complete symmetric digraph.
Hence $V\setminus \partial (\{1,r\})$ has exactly two  strongly connected components each of them has size $\ge 2.$

Let $T=\partial (\{1,r\}).$ Since $|\{1,r\}\tilde{S}|=|S|+2,$ we have $|T|=|S|.$
By the observation made above $T\neq \Gamma (x),$ for every $x\in G.$ Therefore,  $\Gamma$ is non superconnected.

{\bf Subcase} 3.2 $a\in H$.  Since (ii) does not hold, we have $r, r^{-1} \in S$. Put
$P=\subgp{r}\cap \tilde{S}$.
 Let $F$ be any fragment with $1\in F.$ We must have $F \subset H,$ since otherwise by Lemma \ref{prehistorical}, $$|F\tilde{S}|\ge
|F(\tilde{S}\setminus H)|=|(F)H(\tilde{S}\setminus H)|=|(FH)(\tilde{S}\setminus H)|=|G|,$$  a contradiction.

Now we have $|F|+|\tilde{S}|-1=|F\tilde{S}|=|G\setminus H|+|FP|=|\tilde{S}|-|P|+|FP|.$
In particular, $|H|-1\ge |FP|=|F|+|P|-1.$ By Lemma \ref{AP}, $F$ is a $r$-progression.
Since $\{r,-r\}\subset S,$ the set $F$ is a  strongly connected subset. Similarly $G\setminus \Gamma (F)$
is a  strongly connected  subset. Therefore $\Gamma$ is non superconnected.\qed

\begin{corollary}
Let $S$ be   an aperiodic  generating subset of a finite group $G$,
with $1\notin S,$   and  $ |S|\le |G|/2$. Then  $\mbox{Cay} (G,S)$
is   superconnected if and only if  one of the following holds:

\begin{itemize}
  \item  $\mbox{Cay} (G,S)$ is vosperian,
  \item  There is a $r\in G$ such that $G$ is a cyclic group and $S=\{r,r^2,\ldots ,r^{|S|}\}.$
\end{itemize}
 \label{superung2}
\end{corollary}

\proof
Let us see that if $ |S|\le |G|/2$ holds then a coprogression is also a progression. If $G\setminus \tilde{S}\subset \subgp{r}$
then $G=\subgp{r}$. Since otherwise, $|\tilde{S}|\ge |G|-|\subgp{a}|+2\ge \frac{|G|}2+2,$
a contradiction. The result follows now by Theorem \ref{superg}.\qed

\noindent{\bf Acknowledgment}

Research supported by the Ministry of Science and Innovation, Spain under project MTM2008-06620-C03-01/MTM. Research done when the last author was \mbox{visiting} Universit\'e Pierre et Marie Curie, E. Combinatoire, Paris, supported by the Ministry of Science and Innovation, Spain  under the National Mobility Programme of Human Resources, Spanish National Programme I-D-I 2008--2011.

\bibliographystyle{model1a-num-names}

config: arxiv


TITLE: How to find the center of mass of the region bound by 2 intersecting parabolas efficiently?
QUESTION [0 upvotes]: I am aware you can find the center of mass of simple shapes such as those bound by parabolas using a single or double integral, but I have been trying to find a more computationally efficient method to compute this.
When you have 2 intersecting parabolas with the same magnitude of $x^2$ coefficients there seems to be a shortcut for finding the center of mass of the region they bound.
The center of mass seems to be the midpoint of the vertices of each parabola.

You can see a visual of this here: https://www.desmos.com/calculator/hr9wyik3z2
I was wondering if there was an elegant way to prove this finding, or even extend this finding for 2 intersecting parabolas with different magnitudes of $x^2$ coefficients.

REPLY [4 votes]: If one parabola has the form $y=\alpha x^2 + bx +c$ and another one $y=-\alpha x^2+dx+e$, then we can match one parabola with another with  $180^\circ$ rotation and translation. In 2D combination of rotation by some non-zero angle and translation is the same as rotation by the same angle around some other point. Thus 2 parabolas has rotational symmetry. Since after rotation the vertex of one parabola will go to the vertex of other, the center of rotation should be midpoint of the vertices. Finally, the body with rotational symmetry will always have its center of mass located in the center of rotation


TITLE: The number of different prime factors of a special class of positive integers
QUESTION [2 upvotes]: Let $m_i\geq 2 (1\leq i\leq n)$ be $n$ pairwisely coprime positive integers and let $q_i\geq 2 (1\leq i\leq n)$ be $n$ arbitrary prime powers, let$A=\prod_{i=1}^n(({q_i}^{m_i}-1)/(q_i-1))$. Let $\sigma(A)$ be the number of different prime factors of A, is it true that $\sigma(A)\geq n$? If this is not true, is there a counterexample? Is there a good way to estimate $\sigma(A)$?

REPLY [10 votes]: No it's not true you have the following counterexample:
$$ \frac{2^5-1}{2-1} \times \frac{5^3-1}{5-1} = 31^2 $$


text:
\section{Non-normal modal logics as axiom systems}
\label{section:classical logics axioms}

In this section we introduce, axiomatically, the class of non-normal
modal logics we consider in this work.

\begin{definition} {\em Non-normal modal logics} are defined over a
  propositional modal language $\lan$, based on a set
  $\atm = \{p_1, p_2, p_3, ...\}$ of countably many propositional
  variables.  The well-formed \emph{formulas} of $\lan$ are defined by
  the following grammar
  \begin{center}
    $A ::= p \mid \bot \mid \top \mid A\land A \mid A \lor A \mid A\to A \mid \Box A$.
  \end{center}
\end{definition}

\noindent
In the following, we use $A, B, C, D, E$ and $p, q, r$ as
metavariables for, respectively, arbitrary formulas and atoms of
$\lan$.  We consider the standard abbreviations
$\neg A := A \to \bot$, $A\leftrightarrow B := (A\to B)\land(B\to A)$,
and $\Diamond A := \neg\Box\neg A$.

\begin{definition}\label{def:axioms}
The family of non-normal modal logics  is generated by
\begin{enumerate}
\item  any axiomatization of  classical propositional logic (\CPL)
  formulated in the language $\lan$, comprising the rule
  of  \emph{modus ponens} (\MP)\label{item:axiomspc}
  \begin{center}
    \ax{$A \rightarrow B$}
    \ax{$A$}
    \llab{\MP}
    \binf{$B$}
    \disp
  \end{center}
\item The rule RE of Figure  \ref{figure:hilbert axioms}.\label{item:re}
\item Any or none of the other axioms or  rules of Figure \ref{figure:hilbert axioms}.
\end{enumerate}
The minimal non-normal modal logic is $\E$, defined by only
items~\ref{item:axiomspc} and~\ref{item:re} above. We denote
non-normal modal logics by $\EX$, where $\mathbf X$ stands for the
(possibly empty) additional set of axioms and rules from Figure
\ref{figure:hilbert axioms}.  We adopt the convention of replacing E
with M for systems containing axiom M, which are consequently denoted
by $\MX$. We also drop the ``R'' of rule \RDnplus. E.g., we write
$\mathbf{MD_3^+}$ for the logic given by extending $\E$ with the axiom
\axM{} and rule $RD_3^+$. In addition, given a non-normal modal logic
$\logic$, we will write $\Lstar$ to indicate an arbitrary extension of
$\logic$ with some other axioms.

As usual, we say that a formula $A$ is {\em provable} in $\logic$
(denoted by $ \vd_{\logic} A$) if it is an instance of an axiom of
$\logic$ or it is obtained from previous formulas by applying the
rules of $\logic$.
\end{definition}
\begin{figure}[t]
  \centering
  \fbox{\begin{minipage}{33em}
      \vspace{0.1cm}

      \begin{tabular}{lllllll}
        \vspace{0.2cm}
        &\ax{$A \leftrightarrow B$}
          \llab{\RE}
          \uinf{$\Box A \leftrightarrow \Box B$}
          \disp
        &&
           \multicolumn{4}{l}{
           \ax{$\neg(A_1 \land ... \land A_n)$}
           \llab{\RDnplus}
           \rlab{$(n \geq 1)$}
           \uinf{$\neg(\Box A_1 \land ... \land \Box A_n)$}
           \disp} \\

        \vspace{0.2cm}
        &\axM \quad $\Box (A \land B)\to \Box A$ &&
                                                    \axC \quad $\Box A \land \Box B \to \Box (A \land B)$ &&
                                                                                \axN \quad $\Box \top$ \\

        &\axT \quad $\Box A \to A$ &&
                                      \axD \quad $\neg(\Box A \land \Box \neg A)$ &&
                                                                                \axP \quad $\neg\Box \bot$ \\
      \end{tabular}
    \end{minipage}}
  \caption{Modal axioms and rules.}\label{figure:hilbert axioms}
\end{figure}

Logic $\E$ is the weakest system of the so-called \emph{classical
  cube} \cite{Chellas:1980,Lellmann:2019}, generated by any
combination of axioms \axM, \axC, and \axN, as shown in Figure
\ref{figure:classical cube}.

As it is well known, the axioms \axM{} and \axN{} are respectively equivalent to  the rules
of \emph{monotonicity} \RM\ and \emph{necessitation} \RN
$$RM \ \frac{A\to B}{\Box A \to \Box B} \quad\quad RN \ \frac{A}{\Box A}$$
Moreover, axiom \axK:
$\Box( A\rightarrow B)\rightarrow \Box A\rightarrow \Box B$ is
derivable in $\EMC$.  As a consequence, the top system $\EMCN$
coincides with the minimal normal modal logic $\K$.

In the following, we call \emph{monotonic}\index{monotonic logic} any
system containing axiom \axM\ (and \emph{non-monotonic} otherwise), we
call \emph{regular}\index{regular logic} any system containing both
axioms \axM{} and \axC, and we call \emph{normal}\index{normal logic}
any system containing \axM, \axC, and \axN{}.

\begin{figure}
\qquad \hfill
\resizebox{4cm}{3cm}{
\begin{tikzpicture}
	\node (a) at  (0,0)  {\E};
    \node (b) at (0, 2.1) {\EM};
    \node  (c) at (-1.5, 0.7) {\EC};
    \node (d) at (2.3, 0.7) {\EN};
    \node (e) at (-1.5, 2.8) {\EMC};
    \node (f) at (2.3, 2.8) {\EMN};
    \node (g) at (0.8, 1.4) {\ECN};
    \node (h) at (0.8, 3.5) {\EMCN{} (\K)};

\draw (a) -- (b);
\draw (a) -- (c);
\draw (a) -- (d);
\draw (b) -- (e);
\draw (b) -- (f);
\draw (c) -- (e);
\draw [dashed] (c) -- (g);
\draw (d) -- (f);
\draw [dashed] (d) -- (g);
\draw (e) -- (h);
\draw (f) -- (h);
\draw [dashed] (g) -- (h);
\end{tikzpicture}
}
\hfill \qquad
\caption{\label{figure:classical cube} The classical cube.}
\end{figure}
In the present work, we will in particular consider extensions of the
basic classical cube with any combination of the axioms \axT, \axD,
\axP, and for every $n \in \Nat$, $n \geq 1$, the rule \RDnplus\
(Figure~\ref{figure:classical cube}).

The logics given by the rules \RDnplus\ have a peculiar interest in
deontic logic since the latter exclude the possiblity of having $n$
obligations that cannot be realised all together.  Let us consider the
following example, essentially from Hansson~\cite[p. 41]{Hansson3}:
(1) I have to keep my mobile switched on (as I'm waiting for an urgent
call), (2) I have to attend my child schoolplay, (3) being in the
audience of a schoolplay I must keep my mobile switched
off. Representing these three claims by $mobile\_on$, $schoolplay$,
and $\neg (mobile\_on \land schoolplay)$, by using rule $RD_3^+$, it
can be concluded that the three obligations are incompatible:
$$\neg (\Box mobile\_on \land \Box schoolplay \land  \Box \neg (mobile\_on \land schoolplay))$$
This conclusion cannot be obtained in any non-normal modal logic
without $RD_3^+$ or \axC{}, even if it contains both deontic axioms
\axD\ and \axP.

While rules \RDnplus\ are entailed by axioms \axD\ and \axP\ in normal
modal logics, this is not the case in non-normal modal logics,
therefore they may be considered explicitly.  It is also worth noting
that the axioms \axD\ and \axP\ are equivalent in normal modal logics,
but not in non-normal ones.

The relations among the systems defined by adding \axD, \axP, and
\RDnplus\ to the systems of the classical cube are displayed in
Figure~\ref{figure:deontic systems}.  Finally, observe also that all
\axD, \axP, and \RDnplus\ are entailed by axiom \axT.

\begin{figure}[t]
\begin{center}
\resizebox{10cm}{9cm}{
\begin{small}
\begin{tikzpicture}
    \node (E) at  (0,0)  {\E};
    \node (EM) at (0, 4.7) {\EM};
    \node  (EC) at (-3, 1.5) {\EC};
    \node (EN) at (4.9, 1.5) {\EN};
    \node (EMC) at (-3, 6.1) {\EMC};
    \node (EMN) at (4.9, 6.1) {\EMN};
    \node (ECN) at (1.9, 3) {\ECN};
    \node (EMCN) at (1.9, 7.5) {\EMCN};
    \node  (EP) at (-1.1, 1.1) {$\EP \equiv \EDoneplus$};
    \node  (ED) at (2.5, 1.3) {\ED};
    \node  (EDtwo) at (1.1, 3.5) {$\EDtwoplus$};
    \node  (EDn) at (1.1, 4.6) {$\EDnplus$};
    \node  (MD) at (2.5, 6.5) {$\EMD \equiv \EMDtwoplus$};
    \node  (END) at (3.7, 4) {\END};
    \node  (ENP) at (6, 2.5) {\ENP};
    \node  (ECD) at (-4.1, 2.5) {\ECD};
    \node  (ECP) at (-4.1, 7.9) {$\ECP \equiv \ECDnplus$};
    \node  (ECND) at (-4.1, 8.9) {$\ECND \equiv \ECNP$};
    \node  (EPD) at (1.1, 2.1) {\EPD};
    \node  (MCD) at (-1.4, 9.4) {$\EMCD \equiv \EMCP \equiv \EMCDnplus$};
    \node (MP) at (-1.3, 5.7) {\EMP};
    \node  (MND) at (3.7, 8.6) {\EMND};
    \node  (MCND) at (0.7, 11.8) {$\KD \equiv \KP \equiv \KDnplus$};
    \node (MNP) at (6, 7.1) {\EMNP};
    \node (midECD-ECP) at (-2.88, 3.94) {};
    \node  (MDn) at (0.2, 8.1) {$\EMDnplus$};
    \node  (MNDn) at (3.7, 9.7) {$\EMNDnplus$};
\draw  (E) -- (EM);
\draw  (E) -- (EC);
\draw  (E) -- (EN);
\draw  (EM) -- (EMC);
\draw  (EM) -- (EMN);
\draw  (EC) -- (EMC);
\draw [dotted] (EC) -- (ECN);
\draw  (EN) -- (EMN);
\draw [dotted] (EN) -- (ECN);
\draw [dotted] (EMC) -- (EMCN);
\draw [dotted] (EMN) -- (EMCN);
\draw [dotted] (ECN) -- (EMCN);
   \draw [dashed] (E) -- (EP);
   \draw [dashed] (E) -- (ED);
   \draw [dashed] (EDtwo) -- (EPD);
   \draw [dashed] (EDtwo) -- (EDn);
   \draw [dashed] (ED) -- (MD);
   \draw [dashed] (ED) -- (END);
   \draw [dashed] (EN) -- (END);
   \draw [dashed] (EP) -- (ECP);
   \draw  (EC) -- (ECP);
   \draw [dashed] (ED) -- (EPD);
   \draw [dashed] (ED) -- (ECD);
   \draw [dashed] (EP) -- (EPD);
   \draw  (EC) -- (ECD);
   \draw  (EN) -- (ENP);
   \draw  (ENP) -- (MNP);
   \draw [dashed] (END) -- (ENP);
   \draw [dashed] (MD) -- (MDn);
   \draw [dashed] (MDn) -- (MCD);
   \draw  (MP) -- (MD);
   \draw  (EM) -- (MP);
   \draw [dashed] (EP) -- (MP);
   \draw [dashed] (MD) -- (EDtwo);
   \draw [dashed] (END) -- (MND);
   \draw  (EMN) -- (MND);
   \draw  (MD) -- (MND);
   \draw  (MND) -- (MNDn);
   \draw  (MNDn) -- (MCND);
   \draw [dashed] (EMCN) -- (MCND);
   \draw  (MCD) -- (MCND);
   \draw  (EMN) -- (MNP);
   \draw [dashed] (EDn) -- (ECP);
   \draw  (MP) -- (MCD);
   \draw  (EMC) -- (MCD);
   \draw  (ECP) -- (MCD);
   \draw  (MNP) -- (MND);
   \draw (ECP) -- (ECD);
   \draw (ECP) -- (ECND);
   \path[-]          (ECND)  edge   [bend left]   node {} (MCND);
   \draw [dashed] (EP) -- (ENP);
   \draw [dashed] (END) -- (ECND);
   \draw [dashed] (EDn) -- (MDn);
   \draw [dashed] (MDn) -- (MNDn);
\end{tikzpicture}
\end{small}
}
\end{center}
\caption{\label{figure:deontic systems} Diagram of deontic systems (
``Pantheon'').}
\end{figure}