text:
\begin{document}

\title{Integrality of Subgradients and Biconjugates of \\
Integrally Convex Functions

}

\author{
Kazuo Murota
\thanks{Department of Economics and Business Administration,
Tokyo Metropolitan University,

murota@tmu.ac.jp}
\ and
Akihisa Tamura
\thanks{Department of Mathematics, Keio University,

aki-tamura@math.keio.ac.jp}
}

\date{June 2018; September 2018}

\maketitle

\begin{abstract}
Integrally convex functions constitute a fundamental function class
in discrete convex analysis.
This paper shows that an integer-valued integrally convex function
admits an integral subgradient and that the integral biconjugate
of an integer-valued integrally convex function coincides with itself.
The proof is based on the Fourier--Motzkin elimination.
The latter result provides a unified proof of integral biconjugacy
for various classes of integer-valued discrete convex functions,
including L-convex, M-convex, L$_{2}$-convex, M$_{2}$-convex,
BS-convex, and UJ-convex functions as well as multimodular functions.
Our results of integral subdifferentiability and integral biconjugacy
make it possible to extend the theory of discrete DC (difference of convex) functions
developed for L- and M-convex functions to that for integrally convex functions,
including an analogue of the Toland--Singer duality for integrally convex functions.

\end{abstract}

{\bf Keywords}:
Discrete convex analysis,  Integrally convex function,
Subgradient, Biconjugate function, Integrality,
Fourier-Motzkin elimination

\section{Introduction}
\label{SCintro}

In discrete convex analysis \cite{Fuj05book,Mdca98,Mdcasiam},
a variety of discrete convex functions are considered.
Among others, integrally convex functions,
due to Favati--Tardella \cite{FT90},
constitute a common framework for discrete convex functions,
and almost all kinds of discrete convex functions
are known to be integrally convex.
Indeed, separable convex,
{\rm L}-convex, ${\rm L}^{\natural}$-convex, {\rm M}-convex,
${\rm M}^{\natural}$-convex,  ${\rm L}^{\natural}_{2}$-convex, and
${\rm M}^{\natural}_{2}$-convex functions are known to be integrally convex \cite{Mdcasiam}.
Multimodular functions \cite{Haj85}
are also integrally convex,
as pointed out in \cite{Mdcaprimer07}.
Moreover, BS-convex and UJ-convex functions \cite{Fuj14bisubmdc}
are integrally convex.

The concept of integral convexity
is used in formulating discrete fixed point theorems
and found applications in economics and game theory
\cite{IMT05,Mdcaeco16,Yan09fixpt}.
A proximity theorem for integrally convex functions
has recently been established in \cite{MMTT17proxIC}
together with a proximity-scaling algorithm for minimization.
Fundamental operations for integrally convex functions
such as projection and convolution are investigated in \cite{MM17projcnvl}.

In this paper we are concerned with subgradients and biconjugates
of integer-valued integrally convex functions.
For a function $f: \ZZ\sp{n} \to \RR \cup \{ +\infty \}$
we denote its effective domain as
$\domZ f = \{ x \in \ZZ\sp{n} \mid f(x) < +\infty \}$;
we always assume that $\domZ f$ is nonempty.
For an integer-valued function
$f: \ZZ\sp{n} \to \ZZ \cup \{ +\infty \}$,
we define
$f\sp{\bullet}: \ZZ\sp{n} \to \ZZ \cup \{ +\infty \}$
by
\begin{align}
f\sp{\bullet}(p)  &= \sup\{  \langle p, x \rangle - f(x)   \mid x \in \ZZ\sp{n} \}
\qquad ( p \in \ZZ\sp{n}),
 \label{conjvexZpZ}
\end{align}
where
$\langle p, x \rangle = \sum_{i=1}\sp{n} p_{i} x_{i}$
is the inner product of
$p=(p_{1}, p_{2}, \ldots, p_{n})$ and
$x=(x_{1}, x_{2}, \allowbreak \ldots, \allowbreak  x_{n})$.
This function $f\sp{\bullet}$ is referred to as the
\kwd{integral conjugate} of $f$.
We can apply (\ref{conjvexZpZ}) twice to obtain
$f\sp{\bullet\bullet} = (f\sp{\bullet})\sp{\bullet}$,
which is called the \kwd{integral biconjugate} of $f$.

Concerning conjugacy and biconjugacy
it is natural to ask the following questions
for a given class of discrete convex functions.

\begin{itemize}
\item
For an integer-valued function $f$ in the class,
does the integral conjugate $f\sp{\bullet}$
belong to the same class?
If not, how is it characterized?

\item
For an integer-valued function $f$ in the class,
does integral biconjugacy $f\sp{\bullet\bullet} =f$ hold?
\end{itemize}
These questions are completely settled for
separable convex,
{\rm L}-convex,
${\rm L}^{\natural}$-convex,
{\rm M}-convex,
${\rm M}^{\natural}$-convex,
${\rm L}^{\natural}_{2}$-convex, and
${\rm M}^{\natural}_{2}$-convex functions;
see \cite[Chapter 8]{Mdcasiam}.
We may say that they are also settled for multimodular functions
via equivalence between ${\rm L}^{\natural}$-convexity and multimodularity
pointed out in \cite{Mmult05}.
The conjugacy question for BS-convex and UJ-convex functions
is addressed in \cite{Fuj14bisubmdc}.

For integrally convex functions,
the first question about conjugacy is already settled in the negative \cite{MS01rel}.
Indeed, there is an example of an integrally convex function
whose integral conjugate is not integrally convex;
see Remark \ref{RMconjIC} in Section \ref{SCintcnvfn}.
The main result of this paper is an affirmative answer to the second question
about biconjugacy, which is stated as Theorem~\ref{THbiconjIC} in Section \ref{SCbiconj}.

Integral biconjugacy is closely related to
integral subgradients.
For a point $x \in \domZ f$,
the \kwd{integral subdifferential} of $f$ at $x$
is defined as
\begin{equation} \label{subgZZdef}
 \subgZ f(x)
= \{ p \in  \ZZ\sp{n} \mid
  f(y) - f(x)  \geq  \langle p, y - x \rangle     \ \mbox{for all }  y \in \ZZ\sp{n} \} ,
\end{equation}
and an element of $\subgZ f(x)$ is called an
\kwd{integral subgradient}
of $f$ at $x$.
It is known that
$f\sp{\bullet\bullet}(x) = f(x)$ if and only if $\subgZ f(x) \not= \emptyset$;
see Lemma \ref{LMbiconjsubg} in Section \ref{SCbiconj}.
The condition $\subgZ f(x) \not= \emptyset$ is sometimes referred to as
the \kwd{integral subdifferentiability}  of $f$ at $x$.
Our proof of the integral biconjugacy
actually consists in showing the integral subdifferentiability,
which is stated as Theorem~\ref{THsubgrIC} in Section \ref{SCsubr}.

We can name the following significances of the present result:

\begin{enumerate}
\item
Our result of integral biconjugacy for integrally convex functions serves as a
unified proof of integral biconjugacy
for various classes of discrete convex functions,
such as
{\rm L}-convex, ${\rm L}^{\natural}$-convex, {\rm M}-convex,  ${\rm M}^{\natural}$-convex,
${\rm L}^{\natural}_{2}$-convex, and ${\rm M}^{\natural}_{2}$-convex functions.
The existing proofs for these functions
are based on conjugacy statements valid for respective function classes,
and as such, vary with function classes.
Our proof considers integral biconjugacy directly,
without involving conjugacy properties
that depend on function classes.

\item
In addition to being a unified proof for known results,
our result reveals new facts that
integer-valued BS-convex and UJ-convex functions
admit integral subgradients and  enjoy integral biconjugacy
(Corollaries \ref{COsubgrBSUJ} and \ref{CObiconjBSUJ}).

\item
Our results imply that a theory of discrete DC functions can be developed for
integrally convex functions.
In particular, an analogue of the Toland--Singer duality
for integrally convex functions can be established.
See Section \ref{SCdcprog} for details.
\end{enumerate}

This paper is organized as follows.
Section~\ref{SCintcnvfn} is a review of relevant results on
integrally convex functions.
Section~\ref{SCres} presents the main results of this paper,
followed by Section~\ref{SCproof} for the proofs.
Section~\ref{SCconclrem} concludes the paper with some remarks.

\section{Integrally Convex Functions}
\label{SCintcnvfn}

In this section we summarize fundamental facts about integrally convex functions.
The reader is referred to \cite{FT90} and \cite[Section 3.4]{Mdcasiam} for backgrounds.

For integer vectors
$a \in (\ZZ \cup \{ -\infty \})\sp{n}$ and
$b \in (\ZZ \cup \{ +\infty \})\sp{n}$ with $a \leq b$,
$[a,b]_{\ZZ}$ denotes the integer interval
(box, discrete rectangle)
between $a$ and $b$, i.e.,
$[a,b]_{\ZZ} = \{ x \in \ZZ\sp{n} \mid a \leq x \leq b \}$.
For $x \in \RR^{n}$ the integral neighborhood of $x$ is defined as
\[
N(x) = \{ z \in \mathbb{Z}^{n} \mid | x_{i} - z_{i} | < 1 \ (i=1,\ldots,n)  \}.
\]
For a function
$f: \mathbb{Z}^{n} \to \mathbb{R} \cup \{ +\infty  \}$
the local convex extension
$\tilde{f}: \RR^{n} \to \RR \cup \{ +\infty \}$
of $f$ is defined
as the union of all convex envelopes of $f$ on $N(x)$.  That is,
\begin{equation} \label{fnconvclosureloc2}
 \tilde f(x) =
  \min\{ \sum_{y \in N(x)} \lambda_{y} f(y) \mid
      \sum_{y \in N(x)} \lambda_{y} y = x,  \
  (\lambda_{y})  \in \Lambda(x) \}
\quad (x \in \RR^{n}) ,
\end{equation}
where $\Lambda(x)$ denotes the set of coefficients for convex combinations indexed by $N(x)$:
\[
  \Lambda(x) = \{ (\lambda_{y} \mid y \in N(x) ) \mid
      \sum_{y \in N(x)} \lambda_{y} = 1,
      \lambda_{y} \geq 0 \ (\forall y \in N(x))  \} .
\]
If $\tilde f$ is convex on $\RR^{n}$,
then $f$ is said to be {\em integrally convex} \cite{FT90,Mdcasiam}.

A set $S \subseteq \ZZ^{n}$ is said to be
integrally convex if
the convex hull $\overline{S}$ of $S$ coincides with the union of the
convex hulls of $S \cap N(x)$ over $x \in \RR^{n}$,
i.e., if, for any $x \in \RR^{n}$,
$x \in \overline{S} $ implies $x \in  \overline{S \cap N(x)}$.
A set $S$ is integrally convex if and only if its indicator function
$\delta_{S}: \ZZ\sp{n} \to \{ 0, +\infty \}$
is an integrally convex function,
where the indicator function $\delta_{S}$ is defined by
$\delta_{S}(x)  =
   \left\{  \begin{array}{ll}
    0            &   (x \in S) ,      \\
   + \infty      &   (x \not\in S) . \\
                      \end{array}  \right.$
An integrally convex set $S$ is ``hole-free'' in the sense that
\begin{equation}  \label{holefree}
S =  \overline{S} \cap \mathbb{Z}^{n}.
\end{equation}

In this paper we need the following property of integrally convex sets.

\begin{proposition}    \label{PRpolyhedICset}
The convex hull $\overline{S}$
of an integrally convex set $S \subseteq \ZZ\sp{n}$ is
an integer polyhedron.
Moreover, for any face $F$ of $\overline{S}$,
the smallest affine subspace containing $F$
is given as
$\{ x + \sum_{k=1}\sp{h} c_{k} d^{(k)} \mid c_{1}, c_{2}, \ldots, c_{h} \in \RR \}$
for a point $x$ in $F$ and some direction vectors
$d^{(k)} \in \{ -1,0,+1 \}\sp{n}$ $(k=1,2,\ldots, h)$.
\end{proposition}
\begin{proof}
The proof is given in Section \ref{SCproofpolyh}.
\end{proof}

\begin{remark} \rm \label{RMedgedir}
The properties mentioned in Proposition \ref{PRpolyhedICset} do not characterize
integral convexity of a set.
For example, let
$S = \{  (0,0,0), \allowbreak  (1,0,1),  \allowbreak (1,1,-1), (2,1,0) \}$.
The convex hull $\overline{S}$ is a parallelogram with edge directions
$(1,0,1)$ and $(1,1,-1)$,
and hence is an integer polyhedron such that
the smallest affine subspace containing each face is spanned by $\{ -1,0,1 \}$-vectors.
However, $S$ is not integrally convex, since
$x = [(1,0,1) + (1,1,-1) ]/2 = (1,1/2,0) \in \overline{S}$,
$N(x) = \{ (1,0,0), (1,1,0) \}$, and
$S \cap N(x) = \emptyset$.
\finbox
\end{remark}

The effective domain of an integrally convex function is an integrally convex set.
Integral convexity of a function can be characterized by a local condition
under the assumption that the effective domain is an integrally convex set.

\begin{theorem}[\cite{FT90,MMTT17proxIC}]
\label{THfavtarProp33}
Let $f: \mathbb{Z}^{n} \to \mathbb{R} \cup \{ +\infty  \}$
be a function with an integrally convex effective domain.
Then the following properties are equivalent:

{\rm (a)}
$f$ is integrally convex.

{\rm (b)}
For every $x, y \in \ZZ\sp{n}$ with $\| x - y \|_{\infty} =2$  we have \
\begin{equation}  \label{intcnvconddist2}
\tilde{f}\, \bigg(\frac{x + y}{2} \bigg)
\leq \frac{1}{2} (f(x) + f(y)).
\end{equation}
\vspace{-1.7\baselineskip} \\
\finbox
\end{theorem}

A minimizer of an integrally convex function
can be characterized by a local minimality condition as follows.

\begin{theorem}[\protect{\cite[Proposition 3.1]{FT90}};
  see also \protect{\cite[Theorem 3.21]{Mdcasiam}}]
  \label{THintcnvlocopt}
Let $f: \mathbb{Z}^{n} \to \mathbb{R} \cup \{ +\infty  \}$
be an integrally convex function and $x^{*} \in \domZ f$.
Then $x^{*}$ is a minimizer of $f$
if and only if
$f(x^{*}) \leq f(x^{*} +  d)$ for all $d \in  \{ -1, 0, +1 \}^{n}$.
\finbox
\end{theorem}

\begin{remark} \rm \label{RMintcnvconcept}
The concept of integrally convex functions is introduced in \cite{FT90}
for functions defined on integer intervals (discrete rectangles).
The extension to functions with general integrally convex effective domains
is straightforward, which is found in \cite{Mdcasiam}.
Theorem~\ref{THfavtarProp33} is proved in \cite[Proposition 3.3]{FT90}
when the effective domain is an integer interval
and in \cite{MMTT17proxIC} for the general case.
\finbox
\end{remark}

\begin{remark} \rm \label{RMconjIC}
The integral conjugate of an integrally convex function $f$ is not necessarily integrally convex.
This is shown by the following example
(\cite[Example 4.15]{MS01rel} with a minor correction).
Let $S = \{(1, 1, 0, 0), (0, 1, 1, 0), (1, 0, 1, 0), (0, 0, 0, 1)\}$.
This is obviously an integrally convex set, as it is contained in $\{ 0,1 \}\sp{4}$.
Accordingly, its indicator function $\delta_{S}: \ZZ^{4} \to \{0, + \infty\}$
is integrally convex.
 The integral conjugate $g = \delta_{S}^\bullet$ is given by
\[
 g(p_{1}, p_{2}, p_{3}, p_{4})
 = \max\{p_{1} + p_{2}, p_{2} + p_{3}, p_{1} + p_{3}, p_{4}\} \qquad (p \in \ZZ^{4}).
\]
Let $\tilde g$ be the local convex extension of $g$.
For $p =(0,0,0,0)$ and $q=(1,1,1,2)$
we have
$(p+q)/2 =(1/2,1/2,1/2,1) = [(1,0,0,1) + (0,1,0,1) + (0,0,1,1) + (1,1,1,1)]/4$ and
$\tilde g ((p+q)/2)  = [g(1,0,0,1) + g(0,1,0,1) + g(0,0,1,1) + g(1,1,1,1)]/4
= (1+1+1+2)/4 = 5/4$,
whereas $(g(p)+ g(q)) /2 = (0+2)/2 = 1$.
Thus we have
$\tilde g ((p+q)/2) > (g(p)+ g(q)) /2$,
violating (\ref{intcnvconddist2}) in Theorem~\ref{THfavtarProp33}.
Hence $g$ is not integrally convex.
\finbox
\end{remark}

\section{Results}
\label{SCres}

\subsection{Integral subgradients}
\label{SCsubr}

\begin{theorem}[Integral subdifferentiability]  \label{THsubgrIC}
For an integer-valued integrally convex function
$f: \ZZ^{n} \to \ZZ \cup \{ +\infty \}$,
we have $\subgZ f(x) \neq \emptyset$ for all $x \in\domZ f$.
\end{theorem}
\begin{proof}
The proof is given in Section \ref{SCproofsubgr}.
\end{proof}

The following example shows that integral subdifferentiability is not guaranteed
without the assumption of integral convexity.

\begin{example}[{\cite[Example 1.1]{Mdca98}}]  \rm \label{EXla1}
Let $D = \{ (0,0,0), \pm (1,1,0), \pm (0,1,1), \pm (1,0,1) \}$
and $f: \mathbb{Z}^3 \to \mathbb{Z} \cup \{+\infty\}$ be defined by
\begin{align*}
f(x_{1},x_{2},x_{3}) =
 \begin{cases} (x_{1}+x_{2}+x_{3})/2 & (x \in D), \\
                +\infty & (\textrm{otherwise}).
  \end{cases}
\end{align*}
This function can be naturally extended to a convex function on
the convex hull $\overline{D}$ of $D$
and $D$ is hole-free in the sense of (\ref{holefree}).
However, $D$ is not integrally convex since
for $x=(1,1,0)$ and $y=(-1,0,-1)$ we have
$(x+y)/2 = (0, 1/2, -1/2)$,
$N((0, 1/2, -1/2)) = \{ (0,0,0), (0,1,0), (0,0,-1), (0,1,-1)  \}$,
and hence
$N((0, 1/2, -1/2)) \cap D    \allowbreak   = \{ (0,0,0) \}$.
Therefore, $f$ is not integrally convex.

To investigate the integral subgradient of $f$ at the origin,
suppose that $p \in \subgZ f(\veczero) \subseteq \mathbb{Z}^3$.
Since $f(y) - f(\veczero) \ge \langle p, y \rangle$ for all $y \in D$, we must have
\begin{center}
\begin{tabular}{ccc}
$ 1 \ge  p_{1} + p_{2}$, & $ 1 \ge  p_{2} + p_{3}$, & $ 1 \ge  p_{3} + p_{1}$, \\
$-1 \ge -p_{1} - p_{2}$, & $-1 \ge -p_{2} - p_{3}$, & $-1 \ge -p_{3} - p_{1}$.
\end{tabular}
\end{center}
However, this system admits no integer solution,
though it is satisfied by $(p_{1}, p_{2}, p_{3}) = (1/2, 1/2, 1/2)$.
Hence $\subgZ f(\veczero) = \emptyset$.
\finbox
\end{example}

\begin{remark} \rm \label{RMsubgNotIntPolyh}
Here is a subtle point about the statement of Theorem~\ref{THsubgrIC}.
In parallel to the integral subdifferential $\subgZ f(x)$ in (\ref{subgZZdef}),
the (real) subdifferential $\subgR f(x)$ is defined by
\begin{equation} \label{subgZRdef2}
 \subgR f(x)
= \{ p \in  \RR\sp{n} \mid
  f(y) - f(x)  \geq  \langle p, y - x \rangle     \ \mbox{for all }  y \in \ZZ\sp{n} \}.
\end{equation}
Theorem~\ref{THsubgrIC} states that
$\subgR f(x) \cap \ZZ\sp{n} \not= \emptyset$,
but it does not claim a stronger statement that $\subgR f(x)$ is an integer polyhedron.
Indeed, $\subgR f(x)$ is not necessarily an integer polyhedron, as the following example shows.
Let
$f: \mathbb{Z}^3 \to \mathbb{Z} \cup \{+\infty\}$ be defined by
$f(0,0,0)=0$ and $f(1,1,0)=f(0,1,1)=f(1,0,1)=1$,
with $\domZ f = \{ (0,0,0), (1,1,0), (0,1,1), (1,0,1) \}$.
This function is integrally convex
 and the subdifferential of $f$ at the origin is given as
\[
\subgR f(\veczero) = \{ p= (p_{1}, p_{2}, p_{3}) \in \RR\sp{3} \mid
 p_{1} + p_{2} \leq 1,
 p_{2} + p_{3} \leq 1,
 p_{1} + p_{3} \leq 1   \},
\]
which is not an integer polyhedron, having a non-integral vertex at $p=(1/2, 1/2, 1/2)$.
In contrast, it is known \cite{Mdcasiam} that,
$\subgR f(x)$ is an integer polyhedron if $f$ is
${\rm L}^{\natural}$-convex, ${\rm M}^{\natural}$-convex,
${\rm L}^{\natural}_{2}$-convex, or ${\rm M}^{\natural}_{2}$-convex.
\finbox
\end{remark}

\begin{remark} \rm \label{RMsubgBS}
BS-convex and UJ-convex functions are investigated by Fujishige \cite{Fuj14bisubmdc}.

For an integer-valued BS-convex function $f$,
the subdifferential $\subgR f(x)$ in (\ref{subgZRdef2})
contains a half-integral vector
\cite[Theorem 2]{Fuj14bisubmdc}, and it contains an integral vector
if the function $f$ arises as the conjugate of a $D$-convex function,
which, by definition, is associated with a disconcordant Freudenthal simplicial division $D$
\cite[Theorem 5]{Fuj14bisubmdc}.
The function used as an example in Remark \ref{RMsubgNotIntPolyh}
is actually a BS-convex function (\cite[Example~3]{Fuj14bisubmdc}),
and therefore, $\subgR f(x)$ is not necessarily an integer polyhedron
for a BS-convex function $f$.
Nevertheless, BS-convex and UJ-convex functions admit integral subgradients,
as they are integrally convex.  This fact is stated below as a corollary
of Theorem~\ref{THsubgrIC}.
\finbox
\end{remark}

\begin{corollary}  \label{COsubgrBSUJ}
\quad

\noindent
{\rm (1)}
For an integer-valued BS-convex function $f$,
we have $\subgZ f(x) \neq \emptyset$ for all $x \in\domZ f$.

\noindent
{\rm (2)}
For an integer-valued UJ-convex function $f$,
we have $\subgZ f(x) \neq \emptyset$ for all $x \in\domZ f$.
\finbox
\end{corollary}

\subsection{Integral biconjugacy}
\label{SCbiconj}

In this section we establish the integral biconjugacy
$f\sp{\bullet\bullet} = f$
for integer-valued integrally convex functions.

\begin{lemma}[{\cite[Lemma 4.1]{Mdca98}}]  \label{LMbiconjsubg}
 For each $x \in \domZ f$ we have: \ \
$f\sp{\bullet\bullet}(x) = f(x)  \iff  \subgZ f(x) \not= \emptyset$.
\end{lemma}
\begin{proof}
By the definitions (\ref{conjvexZpZ}) and (\ref{subgZZdef})
it holds, for $x \in \domZ f$ and $p \in \ZZ\sp{n}$, that
\begin{equation} \label{subgconj}
p \in  \subgZ f(x)  \iff f(x) + f\sp{\bullet}(p) = \langle p, x \rangle  .
\end{equation}
If there exists $p \in \subgZ f(x)$, (\ref{subgconj}) implies that
$f(x) + f\sp{\bullet}(p) = \langle p, x \rangle$.   From this
and the definition of $f\sp{\bullet\bullet}(x)$ we obtain
$f\sp{\bullet\bullet}(x) \geq \langle p, x \rangle - f\sp{\bullet}(p) = f(x)$,
while $ f\sp{\bullet\bullet}(x) \leq f(x)$ is obvious.
Conversely, if
$f\sp{\bullet\bullet}(x) = f(x)$,
there exists
$p \in \ZZ\sp{n}$ such that
$\langle p, x \rangle - f\sp{\bullet}(p) = f\sp{\bullet\bullet}(x) = f(x)$.
This implies  $p \in \subgZ f(x)$ by (\ref{subgconj}).
\end{proof}

\begin{remark}  \rm  \label{RMfbbf}
The desired integral biconjugacy $f\sp{\bullet\bullet} = f$
does not follow immediately from the combination of
Theorem~\ref{THsubgrIC} and Lemma \ref{LMbiconjsubg}.
Let
$f: \ZZ\sp{2} \to \ZZ \cup \{+\infty \}$ be the indicator function of
$S = \{ (x_{1},x_{2}) \in \ZZ\sp{2}   \mid x_{2} \geq \sqrt{2} x_{1} - 1/2 \}$, which is not an integrally convex set.
Then  $\subgZ f(x) = \subgR f(x) = \{ (0,0) \} \not= \emptyset$
for all $x \in S = \domZ f$.
On the other hand,
we have $f\sp{\bullet}(0,0) = 0$ and $f\sp{\bullet}(p) =+\infty$
for $p \in \ZZ\sp{2}\setminus \{(0,0)\}$,
from which follows that
$f\sp{\bullet\bullet}(x)= 0$ for all $x \in \ZZ\sp{2}$.
Thus we have $\domZ f\sp{\bullet\bullet} =  \ZZ\sp{2} \not= \domZ f$,
and, a fortiori,  $f\sp{\bullet\bullet} \not= f$.
This example,
taken from \cite[Remark 4.1]{Mdca98}, motivates the technical condition (\ref{Fcond2}) below.
\finbox
\end{remark}

For $f: \mathbb{Z}^{n} \to \mathbb{Z} \cup \{+\infty\}$
we consider the following conditions:
\begin{align}
 &  \domZ f = {\rm cl}(\overline{\domZ f}) \cap \mathbb{Z}^{n}  \neq \emptyset,
\label{Fcond1} \\
    & {\rm cl}(\overline{\domZ f}) \textrm{ is rationally-polyhedral},
\label{Fcond2} \\
    & \subgZ f(x) \neq \emptyset
 \ \mbox{for all} \  x \in \domZ f ,
\label{Fcond3}
\end{align}
where ${\rm cl}(\overline{\domZ f})$ denotes
the closure of the convex hull
\footnote{
${\rm cl}(\overline{\domZ f})$ coincides with the closed convex hull of $\domZ f$;
\cite[Section 1.4]{HL01}.
}
of $\domZ f$,
and a closed convex set in $\mathbb{R}^{n}$ is said to be
rationally-polyhedral if it is described by a system of finitely many
inequalities with coefficients of rational numbers.
The first condition (\ref{Fcond1}) is natural,
the second condition (\ref{Fcond2}) is rather technical,
and the third condition (\ref{Fcond3}) is essential.

\begin{lemma}[{\cite[Lemma 4.2]{Mdca98}}]    \label{LMsubgext}
Suppose that
$f: \mathbb{Z}^{n} \to \mathbb{Z} \cup \{+\infty\}$
satisfies the conditions {\rm (\ref{Fcond1})}, {\rm (\ref{Fcond2})}, and {\rm (\ref{Fcond3})}.
\footnote{
In Lemma 4.1 of \cite{Mdca98} an additional condition
``$\partial_\mathbb{R} f(x) = {\rm cl}(\overline{\domZ f})$''
is involved in the definition of $\mathcal{F}_G$ in (4.18).
However, we can verify that this condition is not needed.
} \
Then the  following hold.
\smallskip
\par
\noindent
{\rm (1)} \
${\displaystyle
 \domZ f\sp{\bullet} =  \bigcup \{ \subgZ f(x) \mid x \in \domZ f \}
 \not= \emptyset.
}$

\smallskip

\noindent
{\rm (2)} \
$ \domZ f\sp{\bullet\bullet} = \domZ f$.

\smallskip

\noindent
{\rm (3)} \
$f\sp{\bullet\bullet}(x) = f(x) \qquad (x \in \ZZ\sp{n})$.

\smallskip

\noindent
{\rm (4)} \
For $x \in \domZ f$, $p \in \domZ f\sp{\bullet}:$  \quad
$p \in  \subgZ f(x) \iff x \in  \subgZ f\sp{\bullet}(p)$.

\smallskip

\noindent
{\rm (5)} \
$\subgZ f\sp{\bullet}(p) \not= \emptyset
\qquad (p \in \domZ f\sp{\bullet})$.
\finbox
\end{lemma}

\begin{lemma}    \label{LMcond123IC}
An integer-valued integrally convex function satisfies
the conditions {\rm (\ref{Fcond1})}, {\rm (\ref{Fcond2})}, and {\rm (\ref{Fcond3})}.
\end{lemma}
\begin{proof}
Since  $S = \domZ f$ is integrally convex,
$\overline{S}$ is an integer polyhedron by Proposition \ref{PRpolyhedICset}.
In particular, we have
${\rm cl}(\overline{S}) = \overline{S}$.
The condition (\ref{Fcond1}) is satisfied by (\ref{holefree}).
The property (\ref{Fcond2}) can be shown as follows.
By Proposition \ref{PRpolyhedICset},
the smallest affine subspace containing a facet $F$ of $\overline{S}$
is described by a system of equations, say,  $A_{F} x = b_{F}$
with the entries of $A_{F}$ belonging to $\{ -1,0,+1 \}$
and $b_{F}$ being an integer vector.
This implies the rationality  (\ref{Fcond2}).
The property (\ref{Fcond3}) is shown in Theorem~\ref{THsubgrIC}.
\end{proof}

By combining Lemmas \ref{LMsubgext} and \ref{LMcond123IC},
we obtain the following statements about
the integral subdifferential, integral conjugate, and integral biconjugate
of an integer-valued integrally convex function.

\begin{proposition}    \label{PRsubgextIC}
For an integer-valued integrally convex function
$f: \mathbb{Z}^{n} \to \mathbb{Z} \cup \{+\infty\}$,
we have the properties {\rm (1)} to {\rm (5)} in Lemma {\rm \ref{LMsubgext}}.
\finbox
\end{proposition}

The integral biconjugacy claimed in Proposition \ref{PRsubgextIC}
deserves a separate statement as a theorem.

\begin{theorem}[Integral biconjugacy]  \label{THbiconjIC}
For an integer-valued integrally convex function
$f: \ZZ^{n} \to \ZZ \cup \{ +\infty \}$
we have
$f\sp{\bullet\bullet}(x) =f(x)$ for all $x \in \ZZ\sp{n}$.
\finbox
\end{theorem}

The following example shows that
integral biconjugacy is not guaranteed
without the assumption of integral convexity.

\begin{example}[{\cite[Example 1.1]{Mdca98}}]  \rm \label{EXla1cont}
In Example \ref{EXla1}, $D = \domZ f$ is not an integrally convex set,
and therefore $f$ is not integrally convex.
The integral conjugate of $f$ is given as
\[
f^{\bullet}(p) = \max \{ 0, |p_{1}+p_{2}-1|, |p_{2}+p_{3}-1|, |p_{3}+p_{1}-1| \}
\]
and the integral biconjugate is
$f^{\bullet\bullet}(x) = \sup_{p \in \mathbb{Z}^3} \{ \langle p, x \rangle - f^{\bullet}(p) \}$.
Hence
\[
f^{\bullet\bullet}(\veczero) = - \inf_{p \in \mathbb{Z}^3} \max \{ 0, |p_{1}+p_{2}-1|, |p_{2}+p_{3}-1|, |p_{3}+p_{1}-1| \}.
\]
Therefore we have $f^{\bullet\bullet}(\veczero) = -1 \neq 0 = f(\veczero)$.
This shows $f^{\bullet\bullet} \neq f$.
\finbox
\end{example}

As special cases of Theorem~\ref{THbiconjIC}
we obtain integral biconjugacy
for {\rm L}-convex,
${\rm L}^{\natural}$-convex,
{\rm M}-convex,
${\rm M}^{\natural}$-convex,
${\rm L}^{\natural}_{2}$-convex, and
${\rm M}^{\natural}_{2}$-convex functions
given in \cite[Theorems 8.12, 8.36, 8.46]{Mdcasiam}.
Integral biconjugacy for BS-convex and UJ-convex functions
are also obtained as a corollary of Theorem~\ref{THbiconjIC}.

\begin{corollary}  \label{CObiconjBSUJ}
\quad

\noindent
{\rm (1)}
For an integer-valued BS-convex function $f$,
we have
$f\sp{\bullet\bullet}(x) =f(x)$ for all $x \in \ZZ\sp{n}$.

\noindent
{\rm (2)}
For an integer-valued UJ-convex function $f$,
we have
$f\sp{\bullet\bullet}(x) =f(x)$ for all $x \in \ZZ\sp{n}$.
\end{corollary}

\subsection{Discrete DC programming}
\label{SCdcprog}

A discrete analogue of
the theory of DC functions (difference of two convex functions)
and DC programming has recently been proposed in \cite{MM15dcprog}
using \Lnat-convex and \Mnat-convex functions.
As already noted in \cite[Remark 4.7]{MM15dcprog},
such  theory of discrete DC functions can in fact be developed for functions
that satisfy integral biconjugacy and integral subdifferentiability.
Our present results, Theorems \ref{THsubgrIC} and \ref{THbiconjIC},
enable us to extend the theory of discrete DC functions
to integrally convex functions.
In particular,
an analogue of
the Toland--Singer duality~\cite{Sin79,Tol79}
can be established for integrally convex functions as a corollary of our results.

\begin{theorem}[Toland--Singer duality] \label{THtolandsinger}
Let $g$ and $h$ be integer-valued integrally convex functions.
\footnote{
As the proof shows, the integral convexity of $g$ is not needed.
That is, (\ref{tolandsingerduality}) holds for
any  $g: \mathbb{Z}^{n} \to \mathbb{Z} \cup \{+\infty\}$,
as long as $h: \mathbb{Z}^{n} \to \mathbb{Z} \cup \{+\infty\}$ is integrally convex.
}
Then
\begin{align} \label{tolandsingerduality}
\inf_{x \in \mathbb{Z}^{n}} \{ g(x) - h(x) \}
= \inf_{p \in \mathbb{Z}^{n}} \{ h^{\bullet}(p) - g^{\bullet}(p) \} .
\end{align}
\end{theorem}
\begin{proof}
By integral biconjugacy (Theorem~\ref{THbiconjIC}) of $h$,
we can prove (\ref{tolandsingerduality}) as follows:
\begin{align*}
& \inf_x \{ g(x) - h(x) \} = \inf_x \{ g(x) - h^{\bullet\bullet}(x) \}
        = \inf_x \{ g(x) - \sup_p \{ \left<p,x\right> - h^{\bullet}(p) \} \}
\\
  &= \inf_x \inf_p \{ g(x) - \left<p, x\right> + h^{\bullet}(p) \}
= \inf_p \{ h^{\bullet}(p) - \sup_x \{ \left<p, x\right> - g(x) \} \}
\\
& = \inf_p \{ h^{\bullet}(p) - g^{\bullet}(p) \} .
\end{align*}
\vspace{-2\baselineskip} \\
\end{proof}

\section{Proofs}
\label{SCproof}

\subsection{Proof of Proposition \ref{PRpolyhedICset} about the convex hull}
\label{SCproofpolyh}

We start with a basic fact, which will be intuitively obvious.
\begin{lemma}  \label{LMhullICclosed}
The convex hull $\overline{S}$ of an integrally convex set $S$ is a closed set.
\end{lemma}
\begin{proof}
Take any point $x$ in the (topological) closure of $\overline{S}$.
There exists a sequence
$\{ x_{k} \} \subseteq \overline{S}$ that converges to $x$.
We may assume that $N(x) \subseteq N(x_{k})$ holds for all $k$,
by considering a subsequence consisting of $\{ x_{k} \}$ with
$\| x_{k} - x \|_{\infty} < \varepsilon$ for a sufficiently small $\varepsilon >0$.
We may further assume that $N(x_{k})$  is identical for all $k$,
since there are finitely many possibilities of the set $N(x_{k})$
and we can choose an appropriate subsequence of $\{ x_{k} \}$.
Let $N_{*}$ denote this $N(x_{k})$.
Since $S$ is integrally convex and
$x_{k} \in \overline{S}$,
we have
$x_{k} \in
\overline{S \cap N(x_{k})} = \overline{S \cap N_{*}}$.
Here $\overline{S \cap N_{*}}$ is a closed set, since $S \cap N_{*}$ is a finite set.
Therefore, $x = \lim_{k} x_{k} \in \overline{S \cap N_{*}} \subseteq \overline{S}$.
\end{proof}

Let $S \subseteq \ZZ\sp{n}$ be an integrally convex set,
and $F$ be a face of its convex hull $\overline{S}$.
Let $L_{F}$ denote the linear subspace of $\RR\sp{n}$
such that the smallest affine subspace containing $F$
is represented as $ x + L_{F}$ for a point $x$ in $F$.
In the following we prove Proposition \ref{PRpolyhedICset} by showing that
(1) $F$ contains an integer point,
(2) $L_{F}$ is spanned by vectors in $\{-1,0,+1\}\sp{n}$, and
(3) $\overline{S}$ is a polyhedron.

\medskip

Proof of (1):
Take any $x \in \RR\sp{n}$ in $F$.
By the integral convexity of $S$, we have
$x \in \overline{S \cap N(x)}$.  That is,
there exist integer points $y\sp{(1)}, y\sp{(2)}, \ldots, y\sp{(m)} \in S \cap N(x)$
and  $\lambda_{1}, \lambda_{2}, \ldots, \lambda_{m} > 0$ such that
$ x = \sum_{k=1}\sp{m} \lambda_{k}y\sp{(k)}$
and $\sum_{k=1}\sp{m} \lambda_{k} = 1$.
Here we have
$y\sp{(1)}, y\sp{(2)},  \allowbreak \ldots,   \allowbreak y\sp{(m)} \in F$,
since $F$ is a face of $\overline{S}$, $x \in F$, and
$y\sp{(1)}, y\sp{(2)},  \ldots,  y\sp{(m)} \in \overline{S}$.

Proof of (2):
Fix $x \in F \cap \ZZ\sp{n}$.
We shall show that there exist $d^{(1)}, d^{(2)}, \ldots, d^{(h)} \in \{-1,0,+1\}\sp{n}$
such that
\begin{equation}  \label{prfFAC1}
 F = (x + \mbox{span}\{ d^{(1)}, d^{(2)},\ldots, d^{(h)} \}) \cap \overline{S},
\end{equation}
where
$\mbox{span}\{ \cdots \}$
means the subspace spanned by the vectors in the braces.
We assume that $F$ is not a singleton,
since otherwise (\ref{prfFAC1}) is trivially true.
Take any $y \in F \setminus \{ x \}$ and
define
$z = (1-\varepsilon)x + \varepsilon y$
with a sufficiently small $\varepsilon > 0$
so that $x \in N(z)$.
Since $z \in \overline{S}$
and $S$ is integrally convex,
there exist $z\sp{(1)}, z\sp{(2)}, \ldots, z\sp{(m)} \in S \cap N(z)$
and  $\lambda_{1}, \lambda_{2}, \ldots, \lambda_{m} > 0$ such that
$ z = \sum_{k=1}\sp{m} \lambda_{k}z\sp{(k)}$ and
$\sum_{k=1}\sp{m} \lambda_{k} = 1$.
Here we have
$z\sp{(1)}, z\sp{(2)}, \ldots, z\sp{(m)} \in F$, since $F$ is a face of $\overline{S}$,
$z \in F$,
and $z\sp{(1)}, z\sp{(2)}, \ldots, z\sp{(m)} \in \overline{S}$.
It follows from
 $(1-\varepsilon)x + \varepsilon y = z = \sum_{k=1}\sp{m} \lambda_{k}z\sp{(k)}$
that
\[
 y = x + \frac{1}{\varepsilon} \sum_{k=1}\sp{m} \lambda_{k}(z\sp{(k)} - x),
\]
where each direction vector
$z\sp{(k)} - x$ belongs to $\{-1,0,+1\}\sp{n}$,
since both $z\sp{(k)}$ and $x$ are members of $N(z)$.
By collecting all the direction vectors
$z\sp{(k)} - x$ arising from all choices of $y \in F \setminus \{ x \}$
we obtain a set of vectors $\{ d^{(1)}, d^{(2)}, \ldots, d^{(h)} \}  \subseteq \{-1,0,+1\}\sp{n}$
for which (\ref{prfFAC1}) holds.

Proof of (3):
First suppose that $\overline{S}$ is full dimensional.
For a facet $F$ of $\overline{S}$,
the linear subspace $L_{F}$ is a hyperplane of dimension $n-1$,
and is described by an (outward) normal vector.
The normal vector is perpendicular to
$(n-1)$ linearly independent direction vectors generating $L_{F}$
and is uniquely determined under some appropriate normalization of the length.
Since the direction vectors are contained in $\{-1,0,+1\}\sp{n}$
by (\ref{prfFAC1}),  there exist only a finite number of possible normal vectors, and hence
$\overline{S}$ has a finite number of facets.
If $\overline{S}$ is not full dimensional,
we consider normal vectors of its facets contained in
the subspace $L_{\overline{S}}$.
There are only a finite number of such normal vectors, up to scaling.
Therefore, $\overline{S}$ is a polyhedron.

\subsection{Proof of Theorem~\ref{THsubgrIC} for integral subdifferentiability}
\label{SCproofsubgr}

Let
$f: \mathbb{Z}^{n} \to \mathbb{Z} \cup \{ +\infty  \}$
be an integer-valued integrally convex function.
For a point $x \in \domZ f$,
the subdifferential of $f$ at $x$
is defined as
\begin{equation} \label{subgZRdef}
 \subgR f(x)
= \{ p \in  \RR\sp{n} \mid
  f(y) - f(x)  \geq  \langle p, y - x \rangle     \ \mbox{for all }  y \in \ZZ\sp{n} \}.
\end{equation}
The subdifferential $\subgR f(x)$ is nonempty for every $x \in \domZ f$,
since an integrally convex function is extensible to a convex function.
In the following we prove that $\subgR f(x)$ contains an integer vector,
which is the claim of Theorem~\ref{THsubgrIC}.

We may assume that $x = \veczero$ and $f(\veczero) = 0$.
In the definition of  $\subgR f(\veczero)$ by (\ref{subgZRdef}),
it suffices, by Theorem~\ref{THintcnvlocopt},
to consider  $y$ in $\{-1,0,+1\}^n$.
Therefore, we have
\begin{equation} \label{subgZR0def}
 \subgR f(\veczero)
= \{ p \in  \RR\sp{n} \mid
  \sum_{j=1}\sp{n} y_{j} p_{j} \leq f(y)   \ \mbox{for all }  y \in \{ -1,0,+1 \}\sp{n} \} .
\end{equation}
We represent the system of inequalities
$\sum_{j=1}\sp{n} y_{j} p_{j} \leq f(y)$
for $y$ with $f(y) < +\infty$
in a matrix form as
\begin{equation}\label{ineqApb}
 A p \leq b.
\end{equation}
Let $I$ denote the row set of $A$ and $A = ( a_{ij} \mid i \in I, j \in \{ 1,2,\ldots, n \})$.
We denote the $i$th row vector of $A$ by $a_{i}$ for $i \in I$.
The row set $I$ is
indexed by $y \in \{ -1,0,+1 \}\sp{n}$ with $f(y) < +\infty$,
and
$a_{i}$ is equal to the corresponding $y$ for $i \in I$;
we have $a_{ij} = y_{j}$ for $j=1,2,\ldots, n$ and $b_{i}= f(a_{i})$.
Note that $a_{ij} \in \{ -1,0,+1 \}$
and $a_{i} \in \{ -1,0,+1 \}\sp{n}$ for all $i$ and $j$.

We apply the Fourier--Motzkin elimination procedure \cite{Sch86} to
the system of inequalities (\ref{ineqApb})
to show the existence of an integer vector satisfying
(\ref{ineqApb}).

The Fourier--Motzkin elimination for (\ref{ineqApb}) goes as follows.
According to the value of the coefficient $a_{i1}$ of the first variable $p_{1}$,
we partition $I$ into three disjoint parts $(I_{1}^{+},I_{1}^{0},I_{1}^{-})$ as
\begin{align*}
 I_{1}^{+} &= \{ i \in I \mid a_{i1} = +1 \},
\\
 I_{1}^{0} &= \{ i \in I \mid a_{i1} = 0 \},
\\
 I_{1}^{-} &= \{ i \in I \mid a_{i1} = -1 \},
\end{align*}
and decompose (\ref{ineqApb}) into three parts as
\begin{align}
 a_{i}  p \leq b_{i} &
\qquad (i \in I_{1}^{+}),
\label{ineqApbi+}
\\
 a_{i}  p \leq b_{i} &
\qquad (i \in I_{1}^{0}) ,
\label{ineqApbi0}
\\
 a_{i}  p \leq b_{i} &
\qquad (i \in I_{1}^{-}) .
\label{ineqApbi-}
\end{align}
For all possible combinations of $i \in I_{1}^{+}$ and $k \in I_{1}^{-}$,
we add the inequality for $i$ in (\ref{ineqApbi+}) and the inequality for $k$ in (\ref{ineqApbi-})
to obtain
\begin{equation}\label{FMp2pn}
 (a_{i} + a_{k}) p \leq b_{i} + b_{k}
\qquad (i \in I_{1}^{+},\; k \in I_{1}^{-}) .
\end{equation}
The inequalities in  (\ref{FMp2pn}) are free from the variable $p_{1}$,
since $a_{i1} + a_{k1}= 0$ for all
$i \in I_{1}^{+}$ and $k \in I_{1}^{-}$.
For the variable $p_{1}$ we obtain
\begin{equation}\label{FMp1}
 \max_{k \in I_{1}^{-}} \left\{ \sum_{j=2}^n a_{kj}p_{j} - b_{k} \right\}
 \leq p_{1} \leq
 \min_{i \in I_{1}^{+}} \left\{ b_{i} - \sum_{j=2}^n a_{ij}p_{j}  \right\}
\end{equation}
from (\ref{ineqApbi+}) and (\ref{ineqApbi-}).
It is understood that
the maximum over the empty set is equal to $-\infty$
and the minimum over the empty set is equal to $+\infty$.

We have thus eliminated $p_{1}$ and obtained
a system of inequalities
in $(p_{2},\ldots,p_{n})$ consisting of (\ref{ineqApbi0}) and (\ref{FMp2pn}).
Once $(p_{2},\ldots,p_{n})$ is found,
$p_{1}$ can easily be found from (\ref{FMp1}),
if the interval described by (\ref{FMp1}) is nonempty.
It is important that the derived system of inequalities
in $(p_{1}, p_{2},\ldots,p_{n})$
consisting of  (\ref{ineqApbi0}), (\ref{FMp2pn}), and (\ref{FMp1})
is in fact equivalent to the original system consisting of
(\ref{ineqApbi+}), (\ref{ineqApbi0}), and (\ref{ineqApbi-}).
In particular, $(p_{1}, p_{2},\ldots,p_{n})$ satisfies
(\ref{ineqApbi+}), (\ref{ineqApbi0}), and (\ref{ineqApbi-})
if and only if $(p_{2},\ldots,p_{n})$ satisfies
(\ref{ineqApbi0}) and  (\ref{FMp2pn}),
and $p_{1}$ satisfies (\ref{FMp1}).

The Fourier--Motzkin elimination applies the above procedure
recursively to eliminate variables $p_{1},p_{2}, \ldots,p_{n-1}$.
This process
results in a single inequality in $p_{n}$ of the form (\ref{FMp1}).
Then we can determine $(p_{1}, p_{2},\ldots,p_{n})$
in the reverse order $p_{n}, p_{n-1},\ldots,p_{1}$.

By virtue of the integral convexity of $f$, a drastic simplification occurs
in the elimination process.
The inequalities (\ref{FMp2pn}) that are to be added in general
are actually redundant and need not be added,
which is shown in the following lemma.
The lemma implies in particular that
$I_{1}^{0}$ is nonempty if
$I_{1}^{+}$ and $I_{1}^{-}$ are nonempty.

\begin{lemma}  \label{LMelimIC}
The inequalities in {\rm (\ref{FMp2pn})} are implied by those in  {\rm (\ref{ineqApbi0})}.
\end{lemma}
\begin{proof}
In (\ref{FMp2pn})
we have
$b_{i} = f(a_{i})$ and $b_{k} = f(a_{k})$,
and hence the inequality in (\ref{FMp2pn}) can be rewritten as
\begin{equation}\label{FMp2pnvar}
 \frac{1}{2} (   a_{i}+ a_{k} ) p
 \leq
 \frac{1}{2} (   f(a_{i}) +f(a_{k}) ) .
\end{equation}

By the integral convexity of $f$
there exist
$y\sp{(1)}, y\sp{(2)}, \ldots, y\sp{(m)} \in N((a_{i}+a_{k})/2)$
such that
\begin{equation}\label{prfFMredun1}
 \sum_{l=1}\sp{m} \lambda_{l} y\sp{(l)}
  =
 \frac{1}{2} (   a_{i} + a_{k} ),
\qquad
 \sum_{l=1}\sp{m} \lambda_{l} f(y\sp{(l)})
\leq
 \frac{1}{2} (   f(a_{i}) +f(a_{k}) ) ,
\end{equation}
where $\lambda_l \geq 0$ for  $l =1,2,\ldots,m$ and $\sum_{l=1}\sp{m} \lambda_l = 1$
 (cf., Theorem~\ref{THfavtarProp33}).
Since
the first component of
$(a_{i}+a_{k})/2$
is zero,
the first component of each $y\sp{(l)}$ must also be zero,
which means that each
$y\sp{(l)}$ coincides with $a_{j}$ for some $j=j(l) \in I_{1}^{0}$.
Hence we have
$y\sp{(l)}  p \leq f(y\sp{(l)})$
for $l =1,2,\ldots,m$
by (\ref{ineqApbi0}).
Using this and (\ref{prfFMredun1}) we obtain
\begin{equation*}
 \frac{1}{2}(a_{i} + a_{k}) p
=
\sum_{l=1}\sp{m} \lambda_l y\sp{(l)}  p
\leq
\sum_{l=1}\sp{m} \lambda_l f(y\sp{(l)})
\leq  \frac{1}{2} (   f(a_{i}) +f(a_{k}) ) .
\end{equation*}
The above argument shows that (\ref{FMp2pnvar}) can be derived from
the inequalities in (\ref{ineqApbi0}).
\end{proof}

For $j=2,3,\ldots,n$, define
\begin{align*}
 I_{j}^{+} &= \{ i \in I_{j-1}^{0} \mid a_{ij} = +1 \},
\\
 I_{j}^{0} &= \{ i \in I_{j-1}^{0} \mid a_{ij} = 0 \},
\\
 I_{j}^{-} &= \{ i \in I_{j-1}^{0} \mid a_{ij} = -1 \}.
\end{align*}
Then the original system (\ref{ineqApb}) is equivalent to
\begin{align}
 \max_{k \in I_{1}^{-}} \left\{ \sum_{j=2}^n a_{kj}p_{j} - b_{k} \right\}
  \leq & \ p_{1} \leq
 \min_{i \in I_{1}^{+}} \left\{ b_{i} - \sum_{j=2}^n a_{ij}p_{j}  \right\} ,
\nonumber \\
 \max_{k \in I_{2}^{-}} \left\{ \sum_{j=3}^n a_{kj}p_{j} - b_{k} \right\}
  \leq & \  p_{2} \leq
 \min_{i \in I_{2}^{+}} \left\{ b_{i} - \sum_{j=3}^n a_{ij}p_{j}  \right\} ,
\nonumber \\
  & \ \vdots
\label{FMp12n}
\\
 \max_{k \in I_{n-1}^{-}} \left\{ a_{kn}p_{n} - b_{k} \right\}
  \leq & \  p_{n-1} \leq
 \min_{i \in I_{n-1}^{+}} \left\{ b_{i} - a_{in}p_{n}  \right\} ,
\nonumber \\
 \max_{k \in I_{n}^{-}} \left\{ - b_{k} \right\}
  \leq & \ p_{n} \leq
 \min_{i \in I_{n}^{+}} \left\{ b_{i} \right\} .
\nonumber
\end{align}
Note that the expressions above are valid even when some of
the index sets $I_{j}^{+}$ and/or $I_{j}^{-}$ are empty.

Since $\subgR f(x)$ is nonempty,
there exists a real vector $p$ satisfying the inequalities (\ref{FMp12n}).
As for integrality, the last inequality in (\ref{FMp12n}) shows
that we can choose an integral $p_{n} \in \ZZ$,
since $b_{i} = f(a_{i})$
for $i \in I_{n}^{-} \cup I_{n}^{+}$
 and $f$ is integer-valued.
Then the next-to-last inequality shows that
we can choose an integral $p_{n-1} \in \ZZ$,
since
$a_{kn}p_{n} - b_{k} \in \ZZ$ for $k \in I_{n-1}^{-}$
and
$b_{i} - a_{in}p_{n} \in \ZZ$ for $i \in I_{n-1}^{+}$.
Continuing in this way we can see the existence of an integer vector $p \in \ZZ\sp{n}$
satisfying (\ref{FMp12n}).
This shows  $\subgZ f(x) \not= \emptyset$,
completing the proof of Theorem~\ref{THsubgrIC}.

\begin{remark} \rm \label{BoundedSG}
Suppose that $\subgR f(x)$ is a bounded polyhedron for an integrally convex function
$f: \mathbb{Z}^{n} \to \mathbb{Z} \cup \{ +\infty  \}$ and $x \in \dom f$.
The expression (\ref{FMp12n}) shows that there exists an integral vertex of  $\subgR f(x)$.
Indeed we can choose the (finite) upper bound in (\ref{FMp12n}) for each $p_i$.
It is emphasized, however, that not every vertex is an integral vector.
\finbox
\end{remark}

\section{Concluding Remarks}
\label{SCconclrem}

The established biconjugacy implies that
there is a one-to-one correspondence
between the class $\calF_{\rm IC}$
of integer-valued integrally convex functions
and the class of their integral conjugates
$\calF\sp{\bullet}_{\rm IC} = \{ f\sp{\bullet}  \mid  f \in \calF_{\rm IC} \}$.
By the conjugacy theorems related to L- and M-convex functions

(see \cite[Fig.~8.1]{Mdcasiam}),
the class $\calF\sp{\bullet}_{\rm IC}$ also contains
separable convex,
{\rm L}-convex,
${\rm L}^{\natural}$-convex,
{\rm M}-convex,
${\rm M}^{\natural}$-convex,
${\rm L}^{\natural}_{2}$-convex, and
${\rm M}^{\natural}_{2}$-convex functions.
A direct characterization of $\calF\sp{\bullet}_{\rm IC}$ is an interesting question
and is left for the future.
It will be also interesting to characterize its subclasses
$\calF\sp{\bullet}_{\rm BS} = \{  f\sp{\bullet} \mid \mbox{$f$: integer-valued BS-convex} \}$
and
$\calF\sp{\bullet}_{\rm UJ} = \{  f\sp{\bullet} \mid \mbox{$f$: integer-valued UJ-convex} \}$.

\

\noindent {\bf Acknowledgement}
The authors thank  Satoru Fujishige and Hiroshi Hirai for helpful comments.
This work was supported by CREST, JST,
Grant Number JPMJCR14D2, Japan, and
JSPS KAKENHI Grant Numbers 26280004, 16K00023.

config: arxiv


TITLE: Viewing a closed point as a scheme
QUESTION [1 upvotes]: If $P$ is a closed point of a scheme $X$, then pullback of the structure sheaf $\mathscr{O}_X$ is $k(P)$. This really baffles me - by definition, this pullback is just $P \mapsto \lim_{U \supset P}\mathscr{O}_X(U)$, which is the stalk of $\mathscr{O}_X$ at $P$. So why isn't the pullback the local ring $\mathscr{O}_{X,P}$ instead of the residue field?

REPLY [0 votes]: Just see that $\{P\}$ is, as closed subscheme, $\textrm{Spec }k(P)$. Take $U=\textrm{Spec }A$ an affine open containing $P$. Hence $P$ corresponds to a maximal ideal $\mathfrak{m}$ in $A$ and $$A/\mathfrak{m}\cong A_{\mathfrak{m}}/\mathfrak{m}A_{\mathfrak{m}}=k(P).$$


TITLE: gcd's in non-UFD rings
QUESTION [5 upvotes]: In a UFD ring we have that for coprime $a,b \in R$, i.e. $(a,b)=1$:

$$ a|cb \Rightarrow a|c $$

Does this property hold for non-UFD rings? I think not but do not recall a standard counter-example.
NOTE: In a non-UFD ring the elements $a,b$ may not even have a gcd, but I am assuming here they do have one.

REPLY [3 votes]: As mentioned, this version of Euclid's Lemma is true in any ring if $\,(a,b) = 1\,$ is interpreted as an ideal equality, i.e. that $\,(a),(b)\,$ are comaximal. But I think you probably intend $\,(a,b)=1\,$ to mean $\,\gcd(a,b)=1,\,$ i.e. $\,d\mid a,b\,\Rightarrow\,d\mid 1.\,$ Then $\,a\mid bc\,\Rightarrow a\mid c\,$ yields, when $\,a\,$ is an atom (irreducible), that atoms are prime, so the domain is a UFD, assuming every nonunit $\ne 0$ has a factorization in atoms. Conversely any UFD satisfies Euclid's Lemma because it is an immediate consequence of the uniqueness of prime factorizations.
As for counterexamples, any domain with a nonunique factorization will have a non-prime atom $\,a\mid bc,\,\ a\nmid b,c,\,$ which yields a failure of Euclid's Lemma,$ $  e.g. $\ 2\mid \alpha \alpha',\ \alpha = 2+\sqrt 5\,\in\,\Bbb Z[\sqrt{-5}].\,$ As I elaborate here this immediately yields a nonexistent gcd, and a nonprincipal ideal. See also this answer for over $15$ closely related properties which all imply uniqueness of atomic factorizations.


TITLE: $f(x)=x^2-3x-2$ for $x\ge3$. how to find point of intersection of $f^{-1}(x)$ and $g(x)=x-3$?
QUESTION [2 upvotes]: We have $f(x)=x^2-3x-2$  where $x\ge3$. graph of two functions
$y=f^{-1}(x)$ and $g(x)=x-3$ intersect each other at the point $A$.
What is the distance from the point $A$ to the origin?
$1)\sqrt{74}\qquad\qquad\qquad2)\sqrt{69}\qquad\qquad\qquad3)\sqrt{89}\qquad\qquad\qquad4)\sqrt{97}$

It is a problem from a timed exam, so I am looking for the fastest answers.
One approach is completing the square of $x^2-3x-2$ then find $f^{-1}(x)$ and equate it with $g(x)=x-3$, but since completing the square containing some fractions it seems not a good idea to solve the problem quickly.
Another approach: I noticed that $f(x)$ and $y=x$ intersect each other at the same point(s) as $f^{-1}(x)$ intersects $y=x$ (because $f$ and $f^{-1}$ are symmetrical along $y=x$) so we can find the points of intersections of $f^{-1}(x)$ and $y=x$ by solving the equation $x^2-3x-2=x$, but I can't make a connection between those points and points of intersections of $f^{-1}(x)$ and $y=x\color{red}{-3}$.

REPLY [5 votes]: The inverse function is given by $y$ where $x=y^2-3y-2$ (just swap the x and the y).
Line is $y=x-3$
Write that as $x=y+3$ and equate the two;
$y^2-3y-2=y+3$
Rearrange and solve easy quadratic.


TITLE: Random Variable absolute value distribution (PDF and CDF)
QUESTION [2 upvotes]: X has a Uniform distribution $U(0,1)$.
I have to find the distribution of the variable $U =|X-1/3|$.
This is what i can get so far :
$F(U) \;{= P\{U < u\} \\ = P\{| X-1/3 | < u\} \\ \ddots}$
I know that i shall get something like $P\{-(U-1/3) < X < U -1/3\}$.
Could anyone explain how to get the PDF and the CDF for this problem and explain how can i easily change this absolute values for other problems ( other examples $Z=1-|X|,~~G=|X|-1$ etc..).

REPLY [2 votes]: when $0\leq u\leq 1/3 $
$$F_U(u)=\int_{1/3~-u}^{1/3~+u}dx=2u,$$
when $1/3 \leq u\leq 2/3$
$$F_U(u)=\int_0^{1/3~+u}dx=1/3~+u$$
Now  just calculate the pdf. differentiate the cdf


TITLE: some questions related to virtual displacement
QUESTION [2 upvotes]: Could anyone tell me if the virtual displacement between two trajectories is $\delta x$ then
(1) how the squared distance between them is $\delta x^{\top}\delta x$?
(2)And why, $\frac{d}{d t}\left(\delta \mathbf{x}^{T} \delta \mathbf{x}\right)=2 \delta \mathbf{x}^{T} \delta \dot{\mathbf{x}}=2 \delta \mathbf{x}^{T} \frac{\partial \mathbf{f}}{\partial \mathbf{x}} \delta \mathbf{x}$?
(3) Could anyone explain to me how equation (3) comes from?
Reference, page 3: http://web.mit.edu/nsl/www/preprints/contraction.pdf
Thanks!

REPLY [2 votes]: (1) For any vector $v$: $v^{\top} v = \langle v, v \rangle = \Vert v \Vert^2$.
(2) For any continuous symmetric bilinear form $B$: $\frac{d}{dt} B(v(t),v(t)) = 2 B(v(t),v^\prime(t))$. The result is applied to the inner product here.
(3) This is Grönwall's inequality.


TITLE: $a^2+b^2+c^2=nd^2$
QUESTION [2 upvotes]: This from the $2022$ Francophone Mathematics Olympiad:

Find the smallest natural number $n$ such that the only solution to: $a^2+b^2+c^2=nd^2$
$(a,b,c,d$ are intgers$)$ is $(0,0,0,0)$

Here is my solution:

For $n≤6$, we can see that the condition is not satisfied. Let's show that $n=7$ is the desired one. Suppose not: if $d$ is odd then working mod $8$ shows that there are no solutions. If $d$ is even, then we let $(a_0,b_0,c_0,d_0)$ be the smallest solution in which one of $a_0,b_0,c_0$ is not zero. Then working mod $4$ tells us that $a_0,b_0,c_0$ must all be even. And we have a smaller solution $(a_0/2,b_0/2,c_0/2,d_0/2)$.

Are there any other approaches different than mine?

REPLY [1 votes]: Leonard E. Dickson
Modern Elementary Theory of Numbers
1939
from pages 11, 112, 113


text:
\begin{document}

\title[Boshernitzan's condition]{Boshernitzan's condition, factor complexity, and an application}
\author{Van Cyr}
\address{Bucknell University, Lewisburg, PA 17837 USA}
\email{van.cyr@bucknell.edu}
\author{Bryna Kra}
\address{Northwestern University, Evanston, IL 60208 USA}
\email{kra@math.northwestern.edu}

\subjclass[2010]{37B10 (primary), 37B40, 35J10, 37A35}
\keywords{subshift, complexity, Schr\"odinger operator, uniquely ergodic}

\thanks{The first author thanks Northwestern for its hospitality while this work was completed and the second author was partially supported by NSF grant DMS-1800544.}

\begin{abstract}
Boshernitzan found a decay condition on the measure of cylinder sets that implies unique ergodicity for minimal subshifts.  Interest in the properties of subshifts satisfying this condition has grown recently, due to a connection with the study of discrete Schr\"odinger operators.  Of particular interest is the question of how restrictive Boshernitzan's condition is.  While it implies zero topological entropy, our main theorem shows how to construct minimal subshifts satisfying the condition  whose factor complexity grows faster than any pre-assigned subexponential rate.
As an application, via a theorem of Damanik and Lenz, we show that there is no subexponentially growing sequence
for which the spectra of all discrete Schr\"odinger operators associated with subshifts whose complexity grows faster than
the given sequence, have only finitely many gaps.
\end{abstract}

\maketitle

\section{Boshernitzan's complexity conditions}

For a symbolic dynamical system $(X,\sigma)$, many of the isomorphism invariants we have are statements about the growth rate of the {\em word complexity function $P_X(n)$},
which counts the number of distinct cylinder sets determined by words of length $n$
having nonempty intersection with $X$.  For example, the exponential growth of $P_X(n)$ is the topological entropy of $(X,\sigma)$, while the linear growth rate of $P_X(n)$ gives an invariant to begin distinguishing between zero entropy systems.  Of course there are different senses in which the growth of $P_X(n)$ could be said to be linear and different invariants arise from them.  For example, one can consider systems with {\em linear limit inferior growth}, meaning
 $\liminf_{n\to\infty}P_X(n)/n < \infty$,  or  the stronger condition of {\em linear limit superior growth}, meaning $\limsup_{n\to\infty}P_X(n)/n < \infty$. (There exist systems satisfying the first condition but not satisfying the second.)

Under the assumption of linear limit inferior growth,
 and with a further hypothesis that the system $(X,\sigma)$ is minimal,
 Boshernitzan~\cite{boshernitzan} showed that the system only supports finitely many $\sigma$-invariant ergodic probability measures.
 Boshernitzan also considered another version of linear complexity on a minimal shift, studying
 {\em linear measure growth}, also referred to in the literature (see for example~\cite{DL}) as {\em condition (B)}: if $\mu$ is a $\sigma$-invariant Borel probability measure on $X$, assume that there exists a sequence
 of integers $n_k \to \infty$ such that $$\inf_k \min_{|w|=n_k} n_k\mu([w]) > 0,$$
 where $\mu([w])$ denotes the measure of the cylinder set determined by the word $w$ and $|w|$ denotes the length of the word $w$.  Boshernitzan showed that linear measure growth implies that the minimal subshift $(X,\sigma)$ is uniquely ergodic.  Another consequence of linear measure growth, for word complexity, is that
 $\liminf_{n\to\infty}P_X(n)/n$ is finite.

 Each of these three linear complexity assumptions, linear limit inferior growth, linear limit superior growth, and linear measure growth, immediately implies that the associated system has zero topological entropy.  It is natural to ask which of these conditions imply any of the others.  One of our main results is that while linear measure growth implies linear limit inferior growth, it does not imply linear limit superior growth.  In fact, we show linear measure growth is flexible enough that examples satisfying it can be constructed with limit superior growth faster than any pre-assigned subexponential growth rate.

A second motivation for the construction we give comes from a question on the spectra of discrete Schr\"odinger operators that arise from a subshift.  If $(X,\sigma)$ is a shift, then each $x = (x_n)_{n\in\Z}\in X$ defines a discrete Schr\"odinger operator $H_x\colon\ell^2(\Z)\to\ell^2(\Z)$ by
$$
(H_xu)(n):=u(n+1)+u(n-1)+x_nu(n)
$$
(and $x$ is called the {\em potential function} for this operator).  Characterizing the spectra of discrete Schr\"odinger operators is an active field of study (e.g.,~\cite{DL,Avila-Krikorian,Bourgain-Jitomirskaya}) and we refer the reader to~\cite{Damanik2, Damanik} for excellent surveys on the theory of discrete Schr\"odinger operators associated
with symbolic systems.  For operators built in this way, the dynamical properties of $(X,\sigma)$ can influence the spectral properties of $H_x$ for any $x\in X$.  When $(X,\sigma)$ is minimal, Damanik (personal communication) asked whether the condition that $h_{top}(X)>0$ implies that the spectrum of $H_x$ can have only finitely many gaps.  Our example shows that the assumption of positive
entropy in this question cannot be relaxed to just ask that $P_X(n)$ grow ``nearly exponentially'' infinitely often: for any subexponential rate $\{a_n\}_{n=1}^{\infty}$ our example, via a theorem of Damanik and Lenz~\cite{DL}, gives a Schr\"odinger operator whose spectrum has infinitely many gaps and whose complexity is larger than $\{a_n\}_{n=1}^{\infty}$ infinitely often.

We turn to stating our main theorem.  For a word $w$ in the language of a subshift $(X, \sigma)$, we denote the cylinder set starting at zero it determines by $[w]_0^+$ and we denote the words of length $n$ in the language of the subshift by $\mathcal L_n(X)$ (for further discussion of the definitions, see Section~\ref{sec:background-symbolic}):
\begin{theorem}
\label{th:main}
Let $\{a_n\}_{n=1}^{\infty}$ be a sequence of positive integers
satisfying
\begin{equation}\label{eq:growth}
\limsup_{n\to\infty}\frac{1}{n}\log a_n=0.
\end{equation}
There exists a minimal and uniquely ergodic subshift $(Y, \sigma)$ such that
$$
\limsup_{n\to\infty}\frac{P_Y(n)}{a_n}=\infty
$$
and such that the unique invariant measure $\mu$ has the property that there is
a sequence $\{n_k\}_{k=1}^{\infty}$ satisfying
\begin{equation}
\label{eq:prop}
\liminf_{k\to\infty}\min\left\{\mu([w]_0^+)\cdot n_k\colon w\in\mathcal{L}_{n_k}(Y)\right\}>0.
\end{equation}
\end{theorem}
The hypothesis in this theorem is a type of subexponential growth on the sequence $\{a_n\}_{n=1}^{\infty}$ and the constructed system is a zero entropy system satisfying the Boshernitzan condition while the factor complexity grows faster than the given sequence.
To prove the theorem, it suffices to show that the system $(Y, \sigma)$ supports a measure $\mu$ satisfying the property~\eqref{eq:prop}, as it then follows from Boshernitzan~\cite[Theorem 1.2]{boshernitzan2} that the system is uniquely ergodic.

An immediate corollary of Theorem~\ref{th:main}, combined with a theorem of Damanik and Lenz~\cite[Theorem 2]{DL}, is the following:
\begin{corollary}
Let $\{a_n\}_{n=1}^{\infty}$ be a sequence of positive integers which grows subexponentially in the sense of~\eqref{eq:growth}.  There exists a Cantor set $\Sigma\subset\mathbb{R}$, of Lebesgue measure zero, and a minimal subshift $(Y,\sigma)$ such that
$$
\limsup_{n\to\infty}\frac{P_Y(n)}{a_n}=\infty
$$
and for every $y\in Y$ the discrete Schr\"odinger operator $H_y\colon\ell^2(\Z)\to\ell^2(\Z)$ given by
$$
(H_yu)(n):=u(n-1)+u(n+1)+y_nu(n)
$$
and the spectrum of $H_y$ is exactly $\Sigma$.
\end{corollary}

\subsection*{Acknowledgment}
We thank David Damanik for bringing this question to our attention and for his helpful remarks during the preparation of this paper.

\section{Background}

\subsection{Symbolic systems}
\label{sec:background-symbolic}
We work over the alphabet $\CA = \{0,1\}\subset\R$ and consider $\CA^\Z$.  We denote $x\in\CA^\Z$ as $x = (x_n)_{n\in\Z}$ and
we endow  $\CA^\Z$ with the topology induced by the metric $d(x, y) = 2^{-\inf\{|i|\colon x_i \neq y_i\}}$.
The {\em left shift} $\sigma \colon \CA^\Z\to\CA^\Z$ is defined by $(\sigma x)_n = x_{n+1}$ for all $n\in\Z$.
If $X\subset\CA^\Z$ is closed and $\sigma$-invariant, then $(X, \sigma)$ is a {\em subshift}.

If $w = (a_{-n}, \ldots, a_0, \ldots, a_n)\in\CA^{2n+1}$, then the {\em central cylinder set
$[w]_0$ determined by $w$ }is defined to be
$$\{x\in X\colon x_j = a_j \text{ for } j=-n, \ldots, n\}
$$
and the {\em one-sided cylinder set $[w]_0^+$ determined by $w$} is defined to be
$$\{x\in X\colon x_j = a_j \text{ for } j=0, \ldots, n\}.
$$
If $(X, \sigma)$ is a subshift and $n\in\N$, the {\em words $\CL_n(X)$  of length $n$}
are defined to be the collection of all $w\in\CA^n$ such that $[w]_0^+\neq\emptyset$,
and the {\em language $\CL(X)$} of the subshift is the union of all the words:
$$\CL(X) = \bigcup_{n=1}^\infty \CL_n(X). $$
If $w\in\CL(X)$ is a word, we say that {\em  $u\in\CL(X)$ is a subword of $w$} if $w = w_1uw_2$ for some (possibly empty) words $w_1, w_2\in\CL(X)$.

For a subshift $(X, \sigma)$, the {\em word complexity $P_X(n)\colon \N\to\N$} is defined to be the number of words of length $n$ in the language:
$$
P_X(n) = |\CL_n(X)|.
$$

\subsection{Well approximable irrationals}
\label{sec:approximations}
A key ingredient in our construction is the following theorem of V.~S\'os~\cite{sos} (formerly known as the Steinhaus Conjecture).
\begin{theorem}[The Three Gap Theorem]
 Assume $\alpha\in\R\setminus\Q$ and $n\in\N$, the partition of  the unit circle $\T = \R/\Z$
 determined by the points $\{0, \alpha, 2\alpha, \ldots, (n-1)\alpha\}$, with all points taken $\pmod 1$.
 Then the subintervals determined by this partition have at most three distinct lengths, and when there are three distinct length, the largest length is the sum of the other two.
\end{theorem}
Given an integer $n\geq 1$ and irrational $\alpha$, we refer to the partition determined by the points  $\{0, \alpha, 2\alpha, \ldots, (n-1)\alpha\}$ of the unit circle as the {\em $n$-step partition}, and make use of it for well chosen $\alpha$.
An irrational real number $\alpha$ is {\em well approximable} if there exists a sequence $\{n_k\}_{k=1}^{\infty}$ of integers
such that for each $n_k$, the associated $n_k$-step partition
in the Three Gap Theorem has three distinct lengths and the ratio of the smallest to the largest length in such a partition tends to zero as $k\to\infty$. (This  sequence is obtained as the denominators in the regular continued fraction expansion of $\alpha$, and this can be rephrased as unbounded partial quotients.) Furthermore,
we can choose the sequence $\{n_k\}_{k=1}^{\infty}$ such that
the smallest length present in the $n_k$-step partition is not present for in the $(n_k-1)$-step partition.

An irrational that is not well approximable is said to be {\em badly approximable},
and the set of badly approximable reals has Lebesgue measure zero.
Notice that if $\alpha$ is well approximable and $\{n_k\}_{k=1}^{\infty}$ is the associated sequence, then the $(n_k-1)$-step  partition in the Three Gap Theorem has only two distinct lengths and the ratio of their lengths tends to $1$ as $k\to\infty$.

\subsection{Sturmian systems}
\label{sec:sturmian}
To make use of the approximations determined by the Three Gap Theorem, we use Sturmian sequences.
To define this notion, let $\alpha$ be an irrational real number and consider the partition $\mathcal{P}=\{[0,\alpha),[\alpha,1)\}$ of $[0,1)$ and let $T_\alpha$ denote the rotation $T(x) = x+\alpha\pmod 1$.  For any $x\in[0,1)$ and each $n\in\Z$, define
$$
c_n(x)=\left\{\begin{tabular}{ll}
$0$ & if $x+n\alpha\pmod1 \in [0, \alpha)$; \\
$1$ & otherwise.
\end{tabular}\right.
$$
Let $X_{\alpha}\subseteq\{0,1\}^{\Z}$ be closure of the set of all sequences of the form
$$
(\dots,c_{-2}(x),c_{-1}(x),c_0(x),c_1(x),c_2(x),\dots).
$$
Then $X_{\alpha}$ is called the {\em Sturmian shift} with {\em rotation angle} $\alpha$.  A classical fact is that
the system $(X_{\alpha}, \sigma)$ is minimal, uniquely ergodic, and $P_{X_{\alpha}}(n)=n+1$ for all $n\in\N$.

Moreover, words $w\in\mathcal{L}_{X_{\alpha}}(X)$ correspond to the cells of
$\bigvee_{i=0}^{|w|-1}T_\alpha^{-i}\mathcal{P}$, and with respect to the unique invariant measure
$\nu_{\alpha}$, the measure of the cylinder set $[w]_0^+$ is the Lebesgue measure $\lambda$ of the cell of
$\bigvee_{i=0}^{|w|-1}T_\alpha^{-i}\mathcal{P}$ corresponding to $w$.
In other words, there is a bijection
\begin{equation}
\label{eq:biject}
\varphi_{n}\colon\mathcal{L}_n(X_{\alpha})\to\P_{n}
\end{equation}
such that
for any word $w\in\mathcal{L}_n(X)$, we have
$$\nu_i([w]_0^+)=\lambda(\varphi_{n}(w)).$$

 In view of the discussion in Section~\ref{sec:approximations}, if $\alpha$ is well approximable, there exists a sequence $\{n_k\}_{k=1}^{\infty}$ such that
\begin{equation}
\label{eq:well-approx-use}
\lim_{k\to\infty}\frac{\min\{\nu_{\alpha}([w]_0^+)\colon w\in\mathcal{L}_{n_k-1}(X_{\alpha})\}}{\max\{\nu_{\alpha}([w]_0^+)\colon w\in\mathcal{L}_{n_k-1}(X_{\alpha})\}}=1.
\end{equation}

Recall that $(X, \sigma)$ is {\em uniquely ergodic} if there exists a unique Borel probability $\sigma$-invariant measure on $X$.  Recasting this definition in terms of the language, the subshift $(X, \sigma)$ is uniquely ergodic if and only if for any $w\in\mathcal{L}(X)$, there exists $\delta\geq0$ such that for any $\varepsilon>0$ there
is an integer $N\geq 1$ with the property that for all $u\in\mathcal{L}(X)$ with $|u|\geq N$,  we have
$$
\left|\frac{\#\text{ of occurrences of $w$ as a subword of $u$}}{|u|}-\delta\right|<\varepsilon.
$$
In this case, $\delta$ is the measure of the cylinder set $[w]_0^+$ with respect to the unique invariant measure on $X$.

\section{The construction}

We construct a minimal subshift $X\subseteq\{0,1\}^{\Z}$ such that
\begin{equation}\label{eq1}
\limsup_{n\to\infty}\frac{P_X(n)}{n}=\infty
\end{equation}
and for which there exists an invariant measure $\mu$ supported on $X$ and a sequence $\{n_k\}_{k=1}^{\infty}$ satisfying
\begin{equation}\label{eq2}
\liminf_{k\to\infty}\min\left\{\mu([w]_0^+)\cdot n_k\colon w\in\mathcal{L}_{n_k}(X)\right\}>0.
\end{equation}

\subsection{Setup}
\label{previous}
We fix $\varepsilon = 1/8$ (any value $\leq 1/8$ suffices) and choose a well approximable real numbers $\alpha$ satisfying
\begin{equation}\label{eq:alpha}
\left|\frac{1}{2}-\alpha\right|<\varepsilon.
\end{equation}

Let $X_{\alpha}$ denote the Sturmian shift with rotation angle $\alpha$ and let $\nu$ denote the (unique) invariant measure supported on $X_{\alpha}$ (see Section~\ref{sec:sturmian}).  For each $n\in\N$,
let $\P_{n}$ denote the partition of $[0,1)$ into subintervals whose endpoints are given by the set
$$
\{0,\alpha,2\alpha, \dots,(n-1)\alpha\},
$$
where, as usual, all points are taken in $[0,1)$, meaning modulo $1$.

Using~\eqref{eq:well-approx-use}  derived from the well approximability of $\alpha$,
there exists $n\in\N$ satisfying
\begin{equation}
\label{eq:exist-n}
\frac{\lambda(\text{shortest subinterval in }\P_{n})}{\lambda(\text{longest subinterval in }\P_{n})}>1-\varepsilon
\end{equation}
(in fact there exist infinitely many such $n$).
The partition $\P_{n}$ is obtained from the partition
$\P_{n-1}$ by subdividing one of the subintervals in $\P_{n-1}$ into two pieces.
 Thus the length of the longest subinterval in $\P_{n-1}$ is at most twice the length of the longest subinterval in $\P_{n}$.  Similarly the length of the shortest subinterval in $\P_{n-1}$ is at least as long as the length of the shortest subinterval in $\P_{n}$.  Therefore we also have
$$
\frac{\lambda(\text{shortest subinterval in }\P_{n-1})}{\lambda(\text{longest subinterval in }\P_{n-1})}\geq\frac{\lambda(\text{shortest subinterval in }\P_{n})}{2\cdot\lambda(\text{longest subinterval in }\P_{n})}>\frac{1}{2}-\frac{\varepsilon}{2}.
$$

We are now ready to begin our construction.
\begin{equation}\label{eq:fixed}
\text{Fix some $n$ satisfying~\eqref{eq:exist-n}}
\end{equation}
and let
$\varphi_{n-1}\colon\mathcal{L}_{n-1}(X_{\alpha})\to\P_{n-1}$ and $\varphi_{n}\colon\mathcal{L}_{n}(X_{\alpha})\to\P_{n}$  denote the bijections defined in~\eqref{eq:biject}.  Then
\begin{equation}\label{eq:longer}
\frac{\min\{\nu([w]_0^+)\colon w\in\mathcal{L}_{n}(X_{\alpha})\}}{\max\{\nu([w]_0^+)\colon w\in\mathcal{L}_{n}(X_{\alpha})\}}>1-\varepsilon
\end{equation}
and
\begin{equation}\label{eq:shorter}
\frac{\min\{\nu([w]_0^+)\colon w\in\mathcal{L}_{n-1}(X_{\alpha})\}}{\max\{\nu([w]_0^+)\colon w\in\mathcal{L}_{n-1}(X_{\alpha})\}}>\frac{1}{2}-\frac{\varepsilon}{2}.
\end{equation}

Since $X_{\alpha}$ is uniquely ergodic, we can choose
$N\in\N$ such that for any $m\geq N$ and any word $w\in\mathcal{L}_{n-1}(X_{\alpha})\cup\mathcal{L}_{n}(X_{\alpha})$ and any word $u\in\mathcal{L}_m(X_{\alpha})$,  we have
\begin{equation}\label{eq:frequency}
\left|\frac{\#\text{ of occurrences of $w$ as a subword of $u$}}{|u|}-\nu([w]_0^+)\right|<\varepsilon.
\end{equation}

Since $X_{\alpha}$ is Sturmian, we have $P_{X_{\alpha}}(m)=m+1$ for all $m\in\N$.  Equivalently, this mean that  $P_{X_{\alpha}}(m+1)=P_{X_{\alpha}}(m)+1$ for all $n\in\N$.  In particular, for all $n$ there is a unique word $w\in\mathcal{L}_m(X_{\alpha})$ for which both $w0$ and $w1$ are elements of $\mathcal{L}_{m+1}(X_{\alpha})$.
Let $w\in\mathcal{L}_{N}(X_{\alpha})$ be the unique word with this property.  Note that for any $m\geq N$, the unique word in $\mathcal{L}_m(X_{\alpha})$ with this property has $w$ as its rightmost subword (of length $|w|$).

Since $X_{\alpha}$ is minimal,
all sufficiently long words in $\mathcal{L}(X_{\alpha})$ contain every word of length $|w|+1$
as a subword and there is a uniform gap $g$ (which depends only on $|w|$)
between consecutive occurrences of any word in $\mathcal{L}_{|w|+1}(X_{\alpha})$.
 Let $m\geq N+3g+3|w|$ be sufficiently large that the unique word $u\in\mathcal{L}_m(X_{\alpha})$ for which both $u0$ and $u1$ are in $\mathcal{L}_{m+1}(X_{\alpha})$, has this property.
 Then the rightmost subword of $u$ of length $|w|$ is $w$ and there is an occurrence of $w0$ within distance $g$ of the left edge of $u$.
 Define $a$ to be the subword of $u$ that begins with the leftmost occurrence of $w0$ and ends just before the rightmost occurrence of $w$
 (meaning we remove the rightmost $|w|$ letters of $u$ to obtain the end of the word $a$).
 Note that $|a|\geq\max\{2g+2|w|,N\}$ and so~\eqref{eq:frequency} holds for all words in $\mathcal{L}_{|w|}(X_{\alpha})$ and $u=a$ (because its length is at least $N$).  Since $|a|\geq2g+2|w|$, every word in $\mathcal{L}_{|w|}(X_{\alpha})$ occurs as a subword of $a$.  Moreover every subword of $aa$ of length $|w|$ is an element of $\mathcal{L}(X_{\alpha})$,
since $aw0\in\mathcal{L}_{|aw0|}(X_{\alpha})$ and the leftmost subword of length $|w0|$ in $a$ is $w0$.  Since $X_{\alpha}$ is aperiodic, there exists an integer $e$ such that
$$
A:=\underbrace{aa\cdots a}_{e\text{ times}}\notin\mathcal{L}(X_{\alpha}).
$$
Let $n\geq3|A|+3g+3|w|$ and let $v\in\mathcal{L}_n(X_{\alpha})$ be the unique word for which $v0$ and $v1$ are both elements of $\mathcal{L}_{n+1}(X_{\alpha})$.
Let $b$ be the subword of $v$ that begins at the leftmost occurrence of $w1$ and ends just before the rightmost occurrence of $w$.
Then $|b|\geq\max\{2g+2|w|,3|A|\}\geq\max\{2g+2|w|,N\}$ and so~\eqref{eq:frequency} holds for the words $w$ and $u=b$ and every word in $\mathcal{L}_{|w|}(X_{\alpha})$ occurs as a subword of $b$.
Moreover every subword of length $|w|$ that occurs in $ab$, $ba$, and $bb$ is in $\mathcal{L}_{|w|}(X_{\alpha})$, since $bw0, bw1\in\mathcal{L}(X_{\alpha})$, the leftmost subword of $a$ is $w0$ and the leftmost subword of $b$ is $w1$.  Finally we define two words:
	\begin{eqnarray*}
	x&:=&\underbrace{AA\cdots A}_{|b|\text{ times}} \\
	y&:=&\underbrace{bb\cdots b}_{|A|\text{ times}}.
	\end{eqnarray*}
By construction both of these words are periodic and we let $p$ denote the minimal period of $x$ and let $q$ denote the minimal period of $y$.  These words have the following properties:
	\begin{enumerate}
	\item $|x|=|y|$;
	\item $A$ does not occur as a subword of $y$ (since $y\in\mathcal{L}(X_{\alpha})$
	but $A\notin\mathcal{L}(X_{\alpha})$);
	\item $x$ does not occur as a subword of $yy$ (because $|y|\geq3|A|$ and
	if $x$ occurred in $yy$ it would force an occurrence of $A$ in $y$);
	\item $y$ does not occur as a subword of $xx$ (again because such an occurrence would force
	and occurrence of $A$ in $y$);
	\item $x$ occurs exactly once as a subword of $xy$.  Namely, $x$ cannot overlap $y$ by at least $|A|$ symbols without forcing an
	occurrence of $A$ in $y$, and
	so $x$ must overlap $x$ on more than $|A|\geq2p$
	symbols.
	This means that the occurrence of $x$ (the subword) has to be offset from the beginning of
	$xy$ by a multiple of $p$,
	and so if this occurrence of $x$ overlaps $y$ by at least $|w0|$ many
	symbols, then since $|x|$ is a multiple of $p$, this
	implies that $y$ has to begin with the word
	$w0$, but it begins with $w1$, a contradiction.  This means that $x$ (the subword) overlaps $y$ on at
	most $|w|$ symbols, and so a portion of the start of $w$ (the leftmost subword of $y$) whose length is a multiple of the minimal period of $x$ matches the subword of the same length at the end of $x$.
	\end{enumerate}

Next we define two more words, $s$ and $t$, as follows:
	\begin{eqnarray*}
	s&:=&xxyxx; \\
	t&:=&xxyyx.
	\end{eqnarray*}
Note that all of the words $ss$, $st$, $ts$, and $tt$ contain $xxxy$ at least once as a subword.  Consider where such a subword could occur:
	\begin{eqnarray*}
	ss&:=&xxyxxxxyxx; \\
	st&:=&xxyxxxxyyx; \\
	ts&:=&xxyyxxxyxx; \\
	tt&:=&xxyyxxxyyx.
	\end{eqnarray*}
We analyze where it can occur in $ss$,
and the analysis for the other three cases is similar.
Since $y$ does not occur as a subword of $xx$, the prefix $xxx$ (in $xxxy$) cannot completely overlap the leftmost $y$ in $ss$.
This means that the farthest to the left that this prefix can occur is if it begins one letter after the beginning of the leftmost $y$ in $ss$.  But since the word $y$ in $xxxy$ cannot be completely contained in the central $xxxx$ of $ss$, the farthest to the left $xxxy$ could occur in $ss$ is to have the $y$ at least partially overlap the rightmost $y$ in $ss$.  Also, since the only place in $xy$ that $x$ can occur is at the leftmost edge, the $y$ in $xxxy$ cannot occur anywhere farther to the right in $ss$ than the rightmost $y$ (otherwise it would force an occurrence of $x$ in $xy$ which would guarantee that one of the subwords $xx$ in $xxxy$ exactly overlaps the rightmost $xy$ in $ss$, which is impossible since $x\neq y$).  Therefore any occurrence of $xxxy$ in $ss$ must have the $y$ in $xxxy$ partially overlap the rightmost $y$ in $ss$, but not extend any farther to the right than this occurrence of $y$.
 This means the leftmost $x$ in $xxxy$ occurs as a subword of the central $xxxx$ in $ss$, and so it is a multiple of $p$ (the minimal period of the bi-infinite word $\cdots xxxx\cdots$) from the right edge of the central $xxxx$ in $ss$.
 This means that the $y$ in $xxxy$ overlaps the rightmost $y$ in $ss$ and is offset from the right edge of $y$ by a multiple of $p$.  If this multiple is zero, then we are done.  Otherwise, the $y$ in $xxxy$ partially overlaps the right edge of $xxxx$ by a multiple of $p$ and overlaps the rightmost $y$ in $ss$ by this same multiple of $p$.  Therefore this multiple of $p$ is a period of $y$ and since the leftmost edge of $y$ (of this length) agrees with the $p$-periodic word $xxxx$, then the entire word $y$ is also $p$-periodic and $y=x$, a contradiction.

\begin{lemma}
Any element $z\in\{0,1\}^{\Z}$ that can be written as a bi-infinite concatenation of the words $s$ and $t$ can be written in a unique way as such a concatenation.
\end{lemma}
A shift with this property is sometimes known as a {\em uniquely decipherable} coded shift.

\begin{proof}
Note that $s$ and $t$ have the same lengths and are not the same word.  We have already noted that the word $xxxy$ occurs in each of $ss$, $st$, $ts$, and $tt$ and, moreover, it occurs exactly once in each such word.  If $z$ can be written as a bi-infinite concatenation of the words $s$ and $t$, then there must be an occurrence of $xxxy$ within distance $|ss|$ of the origin.  Choose a way to write $z$ as a concatenation of $s$ and $t$ and mark the locations in $\Z$ where this choice places the beginnings of these words.  Let $0\leq d<|s|$ be the smallest non-negative integer that lies in this set.  Find an occurrence of $xxxy$ within distance $|ss|$ of the origin.  Since $|xxxy|<|s|=|t|$, this occurrence must be contained in one of the words $ss$, $st$, $ts$, or $tt$ that begins from our marked set of integers.  But $xxxy$ occurs exactly once in any such word and its location always places $y$ exactly $3|x|$ symbols from the right of whichever of $ss$, $st$, $ts$, or $tt$ it occurs in.  This allows us to determine where the marked integers in this occurrence of $ss$, $st$, $ts$, or $tt$ are located.  This allows us to read off the sequence of words $s$ and $t$ that were concatenated to produce $z$ by starting from one of the marked integers and looking at blocks of size $|s|$ moving to the right and left.

Thus, once we find an occurrence of $xxxy$ within distance $|ss|$ of the origin in $z$, the locations (in $\Z$) where the words $s$ and $t$ begin is determined, and once these locations are determined, the bi-infinite sequence of $s$ and $t$ is also determined.  In other words, there is a unique way to write $z$ as such a bi-infinite concatenation.
\end{proof}

\begin{lemma}\label{lem:meas-concat}
Let $Y\subseteq\{0,1\}^{\Z}$ be the subshift consisting of all elements of $\{0,1\}^{\Z}$ that can be written as bi-infinite concatenations of the words $s$ and $t$.  Let $Z\subseteq Y$ be any subshift of $Y$ and let $\mu$ be any $\sigma$-invariant probability measure on $Z$.
Recall that $n\in\N$ is defined in~\eqref{eq:fixed}.
Then $\mathcal{L}_{n}(Z)\cup\mathcal{L}_{n-1}(Z)=\mathcal{L}_{n}(X_{\alpha})\cup\mathcal{L}_{n-1}(X_{\alpha})$ and we have
$$
\frac{\min\{\mu([w]_0^+)\colon w\in\mathcal{L}_{n}(Z)\}}{\max\{\mu([w]_0^+)\colon w\in\mathcal{L}_{n}(Z)\}}>1-2\varepsilon
$$
and
$$
\frac{\min\{\mu([w]_0^+)\colon w\in\mathcal{L}_{n-1}(Z)\}}{\max\{\mu([w]_0^+)\colon w\in\mathcal{L}_{n-1}(Z)\}}>\frac{1}{2}-\varepsilon.
$$
\end{lemma}
\begin{proof}
By construction of the words $a$ and $b$ (from which $s$ and $t$ are built) our claim about equality of the languages holds.  The claim about measure follows from~\eqref{eq:longer},~\eqref{eq:shorter}, and~\eqref{eq:frequency} combined with the fact that $a,b\in\mathcal{L}(X_{\alpha})$ and $|a|,|b|\geq N$.
\end{proof}

\begin{lemma}
\label{lemma:top}
$h_{top}(Y)=\log(2)/|s|>0$.
\end{lemma}
\begin{proof}
The number of distinct words whose length $n$ is any particular multiple of $2|s|$ is at least $|s|\cdot 2^{n/|s|}$ and at most $4|s|\cdot 2^{n/|s|}$ since a word of this length must contain an occurrence of $xxxy$, which tells us how to parse it as a subword of a concatenation of the words $s$ and $t$ (other than perhaps the leftmost and rightmost words in the concatenation).
\end{proof}

We fix a subexponentially growing sequence $\{a_n\}_{n=1}^{\infty}$.  It follows from Lemma~\ref{lemma:top} that
\begin{equation}
\label{eq:grow}
P_{Y}(m)>a_m
\end{equation}
for all but finitely many $m\in\N$.  Thus,
\begin{equation}\label{eq:bound}
\text{given the subexponentially growing sequence $\{a_m\}_{m=1}^{\infty}$ and a bound $B\geq|s|$,}
\end{equation}
we can choose  some $m>B$ such that $P_Y(m)>a_m$, and then fix two (distinct) words $u,v\in\mathcal{L}(Y)$, of equal length, that each contain every element of $\mathcal{L}_{m}(Y)$ as a subword.  Finally define
	\begin{eqnarray}
	\label{eq:0*}
	0_*&:=&uuvuuvuuvvvvuuvuuvuuv \ ; \\
	\label{eq:1*}
		1_*&:=&uuvuuvuuvvvvvvvuuvuuv.
	\end{eqnarray}
Arguing as with words that can be written as bi-infinite concatenations of $s$ and $t$, observe that any element of $\{0,1\}^{\Z}$ that can be written as a bi-infinite concatenation of $0_*$ and $1_*$ can be written in a unique way as such a concatenation.  Let $Z$ be the subshift consisting of all elements of of $\{0,1\}^{\Z}$ that can be written as a bi-infinite concatenation of the word $0_*$ and $1_*$.  Then $Z\subseteq Y$, meaning Lemma~\ref{lem:meas-concat} applies to any $\sigma$-invariant probability measure on $Z$.  Furthermore, by~\eqref{eq:grow}, we have that
\begin{equation}
\label{eq:blank}
P_{Z}(|0_*|)>b_{|0_*|}.
\end{equation}

\subsection{Inflated subshifts}

\begin{lemma}\label{lem:induction}
Let $Z\subseteq\{0,1\}^{\Z}$ be a subshift.  Assume there exists an integer $m>1$ and positive constants $C_1 < C_2$
such that for any ergodic measure $\mu$ supported on $Z$, we have
$$
C_1<\frac{\min\{\mu([w]_0^+)\colon w\in\mathcal{L}_m(Z)\}}{\max\{\mu([w]_0^+)\colon w\in\mathcal{L}_m(Z)\}}<C_2.
$$
Assume that $\beta_0,\beta_1\in\{0,1\}^*$ are two words of equal length such that for any $x\in\{0,1\}^{\Z}$ that can be written as a bi-infinite concatenation of the words $\beta_0$ and $\beta_1$, there is a unique way to write it as such a concatenation.
Further assume that there is a word $v$ that appears exactly once in each of the concatenations
$\beta_0\beta_0$, $\beta_0\beta_1$, $\beta_1\beta_0$, and $\beta_1\beta_1$.
Let $X\subseteq\{0,1\}^{\Z}$ be the subshift consisting of all elements of $\{0,1\}^{\Z}$ that can be written as a (unique) bi-infinite concatenation
$$
\cdots\beta_{i_{-2}}\beta_{i_{-1}}\beta_{i_0}\beta_{i_1}\beta_{i_2}\cdots
$$
where $(\dots,i_{-2},i_{-1},i_0,i_1,i_2,\dots)\in Z$.
If $\mu$ is any ergodic measure supported on $X$, then
$$
\frac{C_1}{4}<\frac{\min\{\mu([w]_0^+)\colon w\in\mathcal{L}_{|\beta_0|\cdot(m+1)}(X)\}}{\max\{\mu([w]_0^+)\colon w\in\mathcal{L}_{|\beta_0|\cdot(m+1)}(X)\}}<4C_2
$$
\end{lemma}

We note that while this seems like a long list of assumptions on the shift $Z$, these hypotheses are satisfied by the shifts to which we apply our inductive construction.  Starting with the system defined in Section~\ref{previous}.  In our application,
the shift $Z$ is the shift $Z$ from the preceding section and the word $v$ is taken to be $xxxy$.

\begin{proof}
Let $\mu$ be an ergodic measure supported on $X$ and let $x\in X$
be a generic point for the measure $\mu$.
Choose $u_1,u_2\in\mathcal{L}_{(m+1)|\beta_0|}(X)$ such that
$$
\mu([u_1]_0^+)=\max\{\mu([w]_0^+)\colon w\in\mathcal{L}_{m|\beta_0|}(X)\}
$$
and
$$
\mu([u_2]_0^+)=\min\{\mu([w]_0^+)\colon w\in\mathcal{L}_{m|\beta_0|}(X)\}
$$
Since $\mu$ is ergodic,
$$
\mu([u_1]_0^+)=\lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}1_{[u_1]_0^+}(\sigma^kx)
$$
and
$$
\mu([u_2]_0^+)=\lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}1_{[u_2]_0^+}(\sigma^kx).
$$
We analyze occurrences of $u_1$ in $x$, noting that the same analysis applies for occurrences of $u_2$.
Any occurrence of $u_1$  in $x$ occurs in a concatenation of the words $\beta_0$ and $\beta_1$, and since $m\geq2$, the value of $d\in\{0,1,\dots,|\beta_0|-1\}$ where the beginnings of these concatenated words occur (starting from the left edge of $u_1$) are determined entirely by the word $u_1$ itself.  (In other words, if $u_1$ occurs in two different places within $x$, the value of $d$ can not change between occurrences of $u_1$,
 as by considering where the word $v$ is located within $u_1$, we can locate the beginnings.)
 Thus each occurrence of $u_1$ occurs as a subword of a concatenation of at most
 $m+1$ of the words $\beta_0$ and $\beta_1$ and that all but (perhaps) the first and last of the words $\beta_0$ and $\beta_1$ can be determined from the word $u_1$.
 Therefore there are at most four ways to concatenate the words $\beta_0$ and $\beta_1$ such that $u_1$
 occurs as a subword, corresponding to the ambiguity of the edge (first and last) concatenated words and that there are at
 most two choices for each of these edge words.
 This means that the asymptotic frequency with which $u_1$ occurs as a subword of $x$ is at least the frequency with which the sequence of $0$'s and $1$'s giving the indices of the $m-1$
 non-edge $\beta_i$ words occur in the element of $Z$ corresponding to $x$, it is at most four times as frequent.
 Since the ratio of the least to the most frequently occurring words of length $m-1$ in $\mathcal{L}(X)$ is
linear and bounded
$C_1$ and $C_2$ for all ergodic measures supported on $X$, this also holds for all elements of $X$.  Namely, if
there were a point in $X$ not satisfying these bounds, then via a standard argument of passing to a limit of the empirical  measures and taking an ergodic component, we would contradict the bounds imposed by $C_1$ and $C_2$.   Thus, we conclude that
\begin{equation*}
\frac{C_1}{4}<\frac{\mu([u_1]_0^+)}{\mu([u_2]_0^+)}<4C_2. \qedhere
\end{equation*}
\end{proof}

\subsection{Induction}
Let $\{a_m\}_{m=1}^{\infty}$ be a subexponentially growing sequence of positive integers, meaning
$$
\limsup_{m\to\infty}\frac{1}{m}\log a_m=0.
$$
We inductively construct a sequence of shifts $X_1,X_2,X_3,\dots$ and ultimately define our subshift $Y$ from Theorem~\ref{th:main}.  Let $n_1\in\N$ be the smallest integer that satisfies~\eqref{eq:exist-n} and let, by taking $n=n_1$ in~\eqref{eq:fixed}, let $X_1\subseteq\{0,1\}^{\Z}$ be the subshift constructed at the end of Section~\ref{previous} (where it was called $Z$).  Let $N$ be the parameter arising in Section~\ref{previous} and let $0_1$ and $1_1$ be the words defined in Equations~\eqref{eq:0*} and ~\eqref{eq:1*} constructed from the sequence $\{m\cdot a_m\}_{m=1}^{\infty}$ and $B\geq N$ in~\eqref{eq:bound} and let $N_1\geq B$ be the parameter $m$ in the sentence following~\eqref{eq:bound}.  Then we have $P_{X_1}(N_1)>N_1\cdot a_{N_1}$.

Now suppose we have constructed a nested sequence of subshifts
$$
X_1\supseteq X_2\supseteq X_3\supseteq\cdots\supseteq X_k,
$$
a sequence of positive integers $n_1<N_1<n_2<N_2<\cdots<n_k<N_k$, and a sequence of words $0_1,1_1,0_2,1_2,\dots,0_k,1_k$ where $0_i,1_i\in\mathcal{L}(X_i)$ are two words of equal length (and this common length is at least $N_k$).  We suppose that for each $i\leq k$, $X_i$ is the subshift obtained by taking all possible bi-infinite concatenations of the words $0_i$ and $1_i$.  Suppose further that for any $i\leq k$ and any $j\leq i$ we have $P_{X_i}(N_j)>N_j\cdot a_{N_j}$ and
$$
\frac{1}{16}<\frac{\min\{\mu([w]_0^+)\colon w\in\mathcal{L}_{n_j}(X_i)\}}{\max\{\mu([w]_0^+)\colon w\in\mathcal{L}_{n_j}(X_i)\}}<1.
$$
Take $n_{k+1}>|0_k|$ to be an integer satisfying~\eqref{eq:exist-n} and let $N_{k+1} =  |0_*|$ when $n$
is chosen to be $n_{k+1}$ in~\eqref{eq:fixed}.
We apply Lemma~\ref{lem:induction} with $Z=X_{\alpha}$, $m=n_{k+1}$, $C_1=1/4$, $C_2=3/4$, $\beta_0=0_k$, and $\beta_1=1_k$ to produce a new subshift $X_{k+1}$.
Note that every element of $X_{k+1}$ can be written as a bi-infinite concatenation of $0_k$ and $1_k$, and so $X_{k+1}\subseteq X_k$.  Let $0_{k+1}$ and $1_{k+1}$ be the words in $\mathcal{L}(X_{k+1})$ by ``inflating'' $0_*$ and $1_*$ from Section~\ref{previous}, with parameter $m=n_{k+1}$, using the words $\beta_0=0_k$ and $\beta_1=1_k$.

Note that since $N_{k+1} = |0_*|$, by
Equation~\eqref{eq:blank} and taking $b_n =na_n$, we have guaranteed that  $P_{X_{k+1}}(N_j)\geq N_ja_{N_j}$ for all $j\leq k+1$.  Finally, by Lemmas~\ref{lem:meas-concat} and~\ref{lem:induction}, we have
$$
\frac{1}{16}<\frac{\min\{\mu([w]_0^+)\colon w\in\mathcal{L}_{n_j}(X_{k+1})\}}{\max\{\mu([w]_0^+)\colon w\in\mathcal{L}_{n_j}(X_{k+1})\}}<1
$$
for all $j\leq k+1$.

Finally, define
$$
X:=\bigcap_{k=1}^{\infty} X_k.
$$
Then  since the subshifts are nested, $X$ is nonempty.  Since each pattern occurs syndetically, the system $X$
is minimal.  Finally, by construction, we obtain a
subshift satisfying $P_X(N_j)>N_ja_{N_j}$ for all $j\in\N$, in particular
$$
\limsup_{n\to\infty}\frac{P_X(n)}{a_n}=\infty,
$$
and such that
$$
\frac{1}{16}<\frac{\min\{\mu([w]_0^+)\colon w\in\mathcal{L}_{n_j}(X)\}}{\max\{\mu([w]_0^+)\colon w\in\mathcal{L}_{n_j}(X)\}}<1
$$
for all $j\in\N$.  This concludes the proof of Theorem~\ref{th:main}.


text:
\section{Suprema Preserving Mapping on Ideals is Increasing}
Tags: Order Theory, Increasing Mappings

\begin{theorem}
Let $\left({S, \preceq}\right)$, $\left({T, \precsim}\right)$ be [[Definition:Ordered Set|ordered sets]].
Let $f: S \to T$ be a [[Definition:Mapping|mapping]].
For every [[Definition:Ideal in Ordered Set|ideal]] $I$ in $\left({S, \preceq}\right)$, let $f$ [[Definition:Mapping Preserves Supremum/Subset|preserve the supremum]] on $I$.
Then $f$ is [[Definition:Increasing Mapping|increasing]].
\end{theorem}

\begin{proof}
Let $x, y \in S$ such that:
:$x \preceq y$
By [[Supremum of Singleton]]:
:$\left\{ {x}\right\}$ and $\left\{ {y}\right\}$ admit [[Definition:Supremum of Set|suprema]] in $\left({S, \preceq}\right)$
By [[Supremum of Lower Closure of Set]]:
:$\left\{ {x}\right\}^\preceq$ and $\left\{ {y}\right\}^\preceq$ admit [[Definition:Supremum of Set|suprema]] in $\left({S, \preceq}\right)$
where $\left\{ {x}\right\}^\preceq$ denotes the [[Definition:Lower Closure/Set|lower closure]] of $\left\{ {x}\right\}$
By [[Lower Closure of Singleton]]:
:$x^\preceq$ and $y^\preceq$ admit [[Definition:Supremum of Set|suprema]] in $\left({S, \preceq}\right)$
By [[Lower Closure of Element is Ideal]]:
:$x^\preceq$ and $y^\preceq$ are [[Definition:Ideal in Ordered Set|ideals]] in $\left({S, \preceq}\right)$
By assumption and definition of [[Definition:Mapping Preserves Supremum/Subset|mapping preserves the supremum on subset]]:
:$f^\to \left({x^\preceq}\right)$ and $f^\to \left({y^\preceq}\right)$ admit [[Definition:Supremum of Set|suprema]] in $\left({T, \precsim}\right)$
and
:$\sup \left({f^\to \left({x^\preceq}\right)}\right) = f \left({\sup \left({x^\preceq}\right)}\right)$ and $\sup \left({f^\to \left({y^\preceq}\right)}\right) = f \left({\sup \left({y^\preceq}\right)}\right)$
By [[Supremum of Lower Closure of Element]]:
:$\sup \left({x^\preceq}\right) = x$ and $\sup \left({y^\preceq}\right) = y$
By [[Lower Closure is Increasing]]:
:$x^\preceq \subseteq y^\preceq$
By [[Image of Subset under Relation is Subset of Image/Corollary 2]]:
:$f^\to \left({x^\preceq}\right) \subseteq f^\to \left({y^\preceq}\right)$
Thus by [[Supremum of Subset]]:
:$f\left({x}\right) \precsim f\left({y}\right)$
Thus by definition:
:$f$ is [[Definition:Increasing Mapping|increasing]].
{{qed}}
\end{proof}

config: wiki


TITLE: Obtain the probability distributions for $\frac{X-Y}{\sqrt2}$ and $\frac{(X+Y)^2}{(X-Y)^2}$
QUESTION [1 upvotes]: Let $X,Y$ be a random sample from $N(0,1)$. Obtain the probability distributions for the following:
$$(1)\frac{X-Y}{\sqrt{2}}\qquad\qquad(2)\frac{(X+Y)^2}{(X-Y)^2}$$
  also show that $(2)$ has an F-distribution with $(1,1)$ df.

$$X,Y\sim N(0,1)\implies f_{XY}(x,y)=\frac{1}{2\pi}e^{-\frac12(x^2+y^2)}\qquad\text{Joint density function}$$
Now I am confused how to proceed. Because using CDF to find PDF and recognize the distribution is lengthy process. However If I found $\mathbb E\left(\frac{X-Y}{2}\right)\text{ and }Var\left(\frac{X-Y}{2}\right)$ then I saw,
$$\mathbb E\left(\frac{X-Y}{\sqrt2}\right)=\frac{1}{\sqrt2}(\mathbb E[X]-\mathbb E[Y])=\frac{1}{\sqrt2}(0-0)=0$$
$$Var\left(\frac{X-Y}{\sqrt2}\right)\stackrel{1}{=}\frac12(Var[X]+Var[Y]+2.0)=\frac12(1+1)=1\quad {}^1Cov(X,Y)=0$$
That's mean $$\left(\frac{X-Y}{\sqrt2}\right)\sim N(0,1)$$
Similar way I can prove $(2)$ is ratio of two $\chi_{1}^2$ variate hence it is F-distribution with $(1,1)df$.

$(1)$ Now what make me confused$(\text{Or can't justify})$ is without any further investigate how could I conclude that $\left(\frac{X-Y}{\sqrt2}\right)\sim N(0,1)$ using just $\mathbb E\text{ and }Var?$
$(2)$ One addition question is I know the MGF of the sum of $n$ independent random variable is the product of their MGF. But is there any similar thing found for the product of $n$ independent random variable$?$ Or the ratio of two independent random variable$?$
Any help will be appreciated. Thanks in advance.

REPLY [1 votes]: Say we have $Y$ and $X$ to be independent.
Note that $X+Y$ and $X-Y$ are jointly normally distributed. Now as the covariance between these variables is zero, they are independent (since they are normally distributed random variables). Further, $X+Y\sim\mathcal{N}(0,2)$ and that $X-Y\sim\mathcal{N}(0,2)$. Therefore $\frac{(X+Y)^2}{2}\sim\chi_{(1)}^2$ and $\frac{(X-Y)^2}{2}\sim\chi_{(1)}^2$ implying that $$\frac{(X+Y)^2/2}{(X-Y)^2/2}=\frac{(X+Y)^2}{(X-Y)^2}$$ is the ratio of two independent $\chi^2_{(1)}$ which is distributed that $F$ with with $1$ and $1$ degrees of freedom.


TITLE: If $\lim\limits_{n \to \infty} \frac{a_n}{b_n}=1 \rightarrow \sum_{n=1}^\infty a_n = \sum_{n=1}^\infty b_n$
QUESTION [1 upvotes]: If $\lim\limits_{n \to \infty} \frac{a_n}{b_n}=1 \rightarrow \sum_{n=1}^\infty a_n = \sum_{n=1}^\infty b_n$
How may I prove this? Or give an example where it doesn't apply
Taking into account that $a_n > 0, b_n > 0, \forall n \in N$
Thanks in advance

REPLY [3 votes]: Take $a_n=\frac{1}{2^n}$ and $b_n=a_n$ for $n>1$ and $b_0=3$. Then $lim_{n\to \infty}\frac{a_n}{b_n}=1$ clearly and $\sum a_n=\sum b_n+2$.


TITLE: Why is the inclusion of the $ 0 $-vector part of the definition of a subspace?
QUESTION [0 upvotes]: I am not seeing why a subspace must include $ 0 $. From what I am told, this inclusion means that the subspace is not “empty”, but I cannot see how the inclusion of $ 0 $ does this. For instance, can you not have a subspace of $ \Bbb{R}^{2} $ that is a line represented by $ y = x + 1 $, which will not intersect $ (0,0) $ of $ \Bbb{R}^{2} $ at all? This subspace appears to exists and to be an element of $ \Bbb{R}^{2} $ by addition and scalar multiplication, but unless I am mistaken, it does not satisfy this $ 0 $-vector inclusion requirement (unless this means it is NOT a subspace, but then that is not making sense).

REPLY [1 votes]: Your confusion seems to stem from thinking incorrectly that all linear things in $\mathbb R^2$ are vector subspaces. This is not the case, as is discussed in the remarks. One of the requirements of a vector space is that it is not empty, that with each vector there is its additive inverse, and that it is closed under vector addition. From this it follows that there is an $x$ in the subspace, and thus also $x-x$ is there, but thus $0$ is in the subspace.


TITLE: The expected area of a triangle made up three points picked randomly inside a circle of radius, and contains the center
QUESTION [2 upvotes]: Consider the triangle formed by randomly distributing three points Inside a circle. What is the expected area of the triangle that contains the center of the circle.
And what is the expected area of the intersection of a set of dependent trinagles that contain the center?
Thank you in  advance for your help.

REPLY [2 votes]: This base part of the problem is not that hard because for suitable chosen coordinates, the condition that the center falls inside the triangle is relatively simple.
WOLOG, assume the circle is the unit circle.
Let $(r_i, \alpha_i), i = 1,2,3$ be the positions of the 3 random points in polar coordinates.
Because of the symmetry of the problem. It just suffices to look the case where $\alpha_1 = 0$ and $0 \le \alpha_2 \le \pi$.
Let $\theta = \alpha_2$ and $\phi = 2\pi - \alpha_3$. It is easy to check for the triangle to contain the origin, the condition is given by $0 \le \phi \le \pi$ and $\theta + \phi \ge \pi$. (see image at end for an illustration)
From this, we see the probability for the triangle to contain the origin is given by:
$$\int_0^\pi \frac{d\theta}{\pi}\int_{\pi-\theta}^\pi \frac{d\phi}{2\pi} \iiint_{0\le r_i\le1}  dr_1^2 dr_2^2 dr_3^2 = \frac{1}{2\pi^2}\int_0^\pi\theta d\theta = \frac14$$
When the triangle contains the origin, its area is given by:
$$\frac12 r_1 r_2 \sin\theta + \frac12 r_1 r_3 \sin\phi + \frac12 r_2 r_3 \sin(2\pi-(\theta+\phi))\tag{*}$$
Using symmetry of the problem again and notice $\int_0^1 r_i dr_i^2 = \frac23$,
the contribution to expected area when the triangle contains the origin is given by:
$$\int_0^\pi \frac{d\theta}{\pi}\int_{\pi-\theta}^\pi \frac{d\phi}{2\pi} \left[\frac32 \left(\frac23\right)^2 \sin\theta \right] = \frac{1}{3\pi^2}\int_0^\pi \theta\sin\theta d\theta = \frac{1}{3\pi}\tag{**}$$
As a result, the conditional expected area of the triangle when it contains the origin is $\frac{4}{3\pi}$.

UPDATE
There are higher dimension generalization on the probability of picking a triangle containing the origin. Quoting from an
article
by R.Howard and Paul Sisson, we have:

Let $\mathbb{R}^n$ be endowed with a probability measure $\mu$ which is symmetric with
  respect to the origin and such that when $n+1$ points are chosen
  independently with respect to $\mu$, with probability one their convex
  hull is a simplex. Then the probability that the origin is contained
  in the simplex generated by $n+1$ such random points is $\frac{1}{2^n}$.

UPDATE2 What does the contribution to expected area means.
In general, when you uniformly pick 3 points from a circle, it need not enclose the
center. Let $T$ be a variable running through all possible configuration of the 3 points.
Let $\mathscr{A}(T)$ be the area of corresponding triangle and $d\mu(T)$ be the probability density of occurrence of $T$. Let $\mathscr{C}$ be the set of configuration where the triangle contains the origin.
The expected area of the unconstrained triangle is given by
$$\int \mathscr{A}(T) d\mu(T)$$
The expected area of the triangle conditional to it contains the center is given by:
$$\frac{\int_{\mathscr{C}} \mathscr{A}(T) d\mu(T)}{\int_{\mathscr{C}} d\mu(T)}$$
The numerator here is what I mean "contribution to expected area"
and the denominator $\int_{\mathscr{C}} d\mu(T) = \frac14$ is
the probability for the triangle to contain the origin.
For $T \in \mathscr{C}$, one can setup coordinates so that $\mathscr{A}(T)$ has
the simple form in $(*)$. By symmetry, the contribution for those 3 pieces in $(*)$
equal to each other. This explains the factor $\frac32$ appear in the integrand
of L.H.S of $(**)$. The remaining part of the integrand in $(**)$ comes from the partial integral over $r_i$:
$$ \iiint_{0\le r_i \le 1} dr_1^2 dr_2^2 dr_3^2\;r_1 r_2 \sin \theta =
   \left(\frac23\right)\left(\frac23\right)\left(1\right) \sin\theta = \left(\frac23\right)^2 \sin\theta $$


TITLE: The value of an integral
QUESTION [1 upvotes]: Calculate
$$\int^{2\pi}_0 \arcsin|\sin(x)|dx$$
This is my solution.Is it correct?
$$\begin{align}\int_0^{2\pi}\arcsin|\sin x|dx&=\int_0^\pi\arcsin\sin xdx+\int_\pi^{2\pi}-\arcsin\sin xdx\\&=\int_0^\pi xdx-\int_\pi^{2\pi}xdx\\&=\frac{\pi^2}{2}2-2\pi^2=-\pi^2.\end{align}$$

REPLY [1 votes]: Most problems with an absolute value in them are made easier by getting rid of the absolute value by way of breaking the problem into cases.
$\sin x \geq 0$ on $0 \leq x \leq \pi$.  So for that part of the integral, you have $\arcsin(\sin(x))$--BUT there is another wrinkle, because of how $\arcsin x$ is defined.  In the first quadrant, the expression simplifies to $x$.  In the second quadrant, the expression simplifies to $\pi - x$.
In the third quadrant, the expression gives $\pi - x$, and in the fourth quadrant, it gives $x$.  So your integral is
$$\int_0^{\pi/2} x dx + \int_{\pi/2}^{\pi}(\pi-x) dx + \int_{\pi}^{3\pi/2} (\pi - x) dx + \int_{3\pi/2}^{2\pi} x dx$$


TITLE: Always prime? $6n+1$ and/or $6n-1$, if neither divisible by $5$ nor semiprime
QUESTION [3 upvotes]: It seems that the sequence of all integers $N$ that are either $6n+1$ or $6n-1$ are all primes if $N$ is neither divisible by $5$ nor semiprime.
It also seems that this sequence of primes includes all primes greater than $5$.
Finally, it seems that the semiprimes thus removed from the original sequence constitute the sequence of all semiprimes having neither a factor of $2$ nor $5$.
Is all this true?
Thank you for your help, Rev20

REPLY [4 votes]: It seems that the sequence of all integers $N$ that are either $6n+1$ or $6n-1$ are all primes if $N$ is neither divisible by $5$ nor semiprime.

Nor sphenic, nor the product of a prime times the square of another prime, nor the cube of a prime, nor the product of four distinct primes, nor the product of the square of a prime times the square of another prime, and so on and so forth for as long as you care to go.

It also seems that this sequence of primes includes all primes greater than $5$.

Yes, it does. Actually, if you allow $n = 0$, we get $6n - 1 = 5$. How do I insert a mind blown GIF on this thing?
There are infinitely many possibilities for $6n + k$, but to avoid duplicates, restrict $k$ to $0 \leq k < 6$. Also I get the feeling you're not too concerned with $n < 0$. Then if $k = 2$, $6n + k$ is always composite except when $n = 0$. Likewise $k = 4$ gives composites except for $n = -1$. And $k = 3$ gives composites except for $n = -1$ or $0$, because otherwise $6n + k$ is a nontrivial multiple of $3$.
That leaves us with $k = 1$ and $k = 5$. You might also find it useful to use $k = -1$ rather than $k = 5$.

Finally, it seems that the semiprimes thus removed from the original sequence constitute the sequence of all semiprimes having neither a factor of $2$ nor $5$.

You forgot about some multiples of $3$. I'm aware the others mentioned it already, but I'm going to lay it on really thick: a lot of multiples of $3$ are semiprimes. In fact, Neil Sloane has a listing that goes up to $674211$.

Is all this true?

Nope.

Thank you for your help, Rev20

And thank you for confirming charter schools are wonderfully terrible! Mwahahahahahahahahahahahaha!