TITLE: An example of conditional expectation
QUESTION [0 upvotes]: Let $(\Omega, F, P)$ be a probability space.
$P=1/6 \ (\omega \in \{1,2,3, 4, 5, 6\})$
$X=0 \ (\omega \in \{1,2,3\}), \ 1 \ (\omega \in \{4\}), \ 2 \ (\omega \in \{5, 6\})$
$Y=1 \ (\omega \in \{1,2,3\}), \ 0 \ (\omega \in \{4, 5, 6\})$
What is $E(X|\sigma(X+Y))$ ?
I think $X+Y=1 \ (\omega \in \{1,2,3,4\}), \ 2 \ (\omega \in \{5,6\})$
so,
$E(X|\sigma(X+Y))= 1/4 \ (X+Y=1), \ 2 \ (X+Y=2)$
Is this true?

REPLY [0 votes]: You calculation of X+ Y is wrong.  If $\omega$ is 1, 2, or 3, X is 0 and Y is 1 so X+ Y= 1. That you have right.  If $\omega$ is 4 or 5, X= 1 and Y= 0 so X+ Y= 1.  X+ Y is NOT 2 for $\omega$= 5.  It is only for $\omega$= 6 that X= 2 and Y is 0 so X+ Y= 2.
You should have X+ Y= 1 for $\omega\in \{1, 2, 3, 4, 5\}$, X+ Y= 2 for $\omega$= 6.


text:
\begin{document}
\author{
   J\'er\^ome Bolte\thanks{Authors in alphabetical order.}\\
   Toulouse School of Economics \\
   Univ. Toulouse\\
   Toulouse, France
   \And
   Edouard Pauwels\\
    IRIT, CNRS\\
   Univ. Toulouse\\
   Toulouse, France
}
\date{\today}

\maketitle

\begin{abstract}
Automatic differentiation, as implemented today, does not have a simple mathematical model adapted to the needs of modern machine learning. In this work we articulate the relationships between differentiation of programs as implemented in practice and differentiation of nonsmooth functions. To this end we provide a simple class of functions, a nonsmooth calculus, and show how they apply to stochastic approximation methods. We also evidence the issue of artificial critical points created by algorithmic differentiation and show how usual methods avoid these points with
probability one.
\end{abstract}

\section{Introduction}

Optimization algorithms based on backpropagation oracles, and more generally on automatic or algorithmic differentiation (AD) \cite{speelpenning1980compiling,rumelhart1986learning}, are one of the most widely used training tools for modern learning architectures \cite{bottou2008tradeoffs,lecun2015deep,bottou2018optimization,chizat,davis2018stochastic,baydin2018automatic,castera2019inertial}. They often rely on popular  numerical implementations as TensorFlow or PyTorch \cite{abadi2016tensorflow,paszke2017workshop}. However, for nonsmooth, nonconvex losses, AD does not have  a stable theory  \cite{griewank2008evaluating,griewank2013stable,griewank2016lipschitz,barton2018computationally,kakade2018provably,griewank2019treating,griewank2020beyond,bolte2020conservative}, matching the actual practice. We wish to present a simple mathematical framework addressing this issue. Let us progressively explain our approach.

\subsection{What is backpropagation?}
\paragraph{Algorithmic differentiation acts on programs not on functions:}
\label{sec:autodiffOnPrograms}
To convey this fact we carry out a small experiment in TensorFlow \cite{abadi2016tensorflow} with the function $\relu \colon t \mapsto \max\{0,t\}$, see Appendix \ref{sec:suppRelu} for implementation details. Algorithmic differentiation is displayed in Figure \ref{fig:illustrAutodiff}, in particular, we have $\relu'(0) = 0$. Consider the two functions
\begin{align*}
    \relu_2 \colon t \mapsto \relu(-t) + t,\qquad \qquad \relu_3 \colon t \mapsto \frac{1}{2}(\relu(t) + \relu_2(t)).
\end{align*}
As mathematical functions on $\RR$ these are {\em equal to} $\relu$. However TensorFlow returns $\relu_2'(0) = 1$ and $\relu_3'(0)=1/2$ (Figure \ref{fig:illustrAutodiff}). Indeed, AD does not act on functions, but on their representations, i.e., on  programs. Different programs implementing the same function may provide different results, beyond numerical precision; we refer to this as the spurious behaviour of AD for nonsmooth functions\footnote{
The validity domain of AD is restricted in theory to smooth functions \cite{griewank2008evaluating}, yet it is  common practice  to use it for nonsmooth functions.}.
Let us explore this phenomenon further. The function $\zero \colon t \mapsto \relu_2(t) - \relu(t)$, outputs constantly $0$ but AD gives $\zero'(0) = 1$. More generally, one can modify the value of the derivative of a given function at prescribed arguments (Figure \ref{fig:illustrAutodiff}). This may generate artificial critical points; for instance  $x\to x-\zero$ is the identity but its derivative at $0$ according to AD is $0$.

This discussion was limited to univariate functions, but these pathologies grow in size and in complexity when occurring in higher dimensions. Besides, as the ``compositional depth" of functions increases the phenomenon gets more complex, making the geometry of artificial point difficult to grasp.
\begin{figure}[t]
    \centering
    \includegraphics[width=.9\textwidth]{3reluActivations.pdf}\\
    \includegraphics[width=.9\textwidth]{zero2SinDerivative.pdf}
    \caption{Top: AD applied to $\relu$ and two different implementations of the same function. Bottom: Algorithmic differentiation of a constant function, creation of artificial critical point or arbitrary derivatives at prescribed arguments for the sine function.}
    \label{fig:illustrAutodiff}
\end{figure}

\paragraph{Canonical surjection between programs functions:}
Numerical programs combine basic mathematical functions within an algorithm and return an output. This can be understood in two ways:
\begin{itemize}\itemsep-.1em
    \item Computer science: it is a sequence of instructions with numerical inputs-outputs,
    \item Mathematics: the program is a function\footnote{In the usual mathematical sense.} of its arguments.
\end{itemize}
It is tempting to identify both, but functions can be represented by different programs. This defines a surjection $\mathcal{F}$ mapping a program to a function (in the class of functions ``accessible through coding").

\paragraph{Algorithmic differentiation:} As presented above, AD is an operation on programs, $\mathcal{A}$ which takes as argument a program and returns a program with the same input variables. This operation can be ``pushed'' to the space of functions using the canonical surjection $\mathcal{F}$. Remar\-ka\-bly, if we restrict ourselves to programs $\mathcal{P}$ which only smoothly combine smooth functions, then we have the following fundamental relation, depicted in Figure \ref{fig:diagrams}:
\begin{align}
    \mathcal{F} (\mathcal{A}(\mathcal{P})) = \nabla \mathcal{F}(\mathcal{P}).
    \label{eq:fundamentalRelation}
\end{align}
In other words, algorithmic differentiation of a program which smoothly combines smooth functions, is equivalent, through the canonical surjection, to derivation.

\begin{figure}[H]
    \center
    \includegraphics[width=\textwidth]{diagrams.pdf}
    \caption{Left: Algorithmic differentiation applied to programs combining smooth functions in a smooth way, the diagram commutes. Right: Algorithmic differentiation in nonsmooth settings, connection with known notion of generalized derivative is much less clear.}
    \label{fig:diagrams}
\end{figure}

However practitioners use AD and backpropagation  beyond smooth programs with nonsmooth elementary functions or program branching for instance. Can we find a proper operational  interpretation of this widespread practice?

\paragraph{Algorithmic differentiation cannot be represented through a variational operator}
At first, it is tempting to simply use AD to induce a differential operator on functions generalizing classical differentiation. This operator, say $\partial^{A}$, should:
\begin{itemize}
    \item[(a)] encompass the outputs of algorithmic differentation for all functions
    \item[(b)] be such that $0$ is an element of $\partial^{A}(\relu)$ at $0$.
\end{itemize}
Unfortunately such an operator does not exist:
\begin{theorem}[Algorithmic differentiation does not induce an operator on functions]\label{th:noOperator}
There is no nontrivial operator on functions satisfying $(a)$ and $(b)$.
\end{theorem}

\subsection{Contribution and related work}
We address  this impossibility result and provide a class of functions together with an operational nonsmooth differential calculus which is able to cope with spurious behaviours.

\paragraph{Elementary selections and selection derivatives:} We introduce a new  class of  nonsmooth nonconvex functions, encompassing most objective functions met in machine learning, having appealing stability properties. This allows us to define simple  differential objects called selection derivatives. Selection derivatives turn out to have an operational calculus adapted to the analysis of many learning methods, as backpropagation or stochastic first order methods. They thus provide an operational model to  capture nonsmooth AD as implemented in current numerical software.

\paragraph{Algorithmic differentiation, algorithms} This framework allows to formalize properly the relationships between, functions, algorithmic differentiation and capture the corresponding notion of critical points as met in practice. These  characterize the set of attractors (limit points) for  stochastic approximation algorithms based on nonsmooth backpropagation  \cite{robbins1951stochastic,benaim1999dynamics,kushner20003stochastic,benaim2005stochastic,borkar2009stochastic}.
It is important to stress that these attractors, which  models sharply the whole scope of AD-induced  stationnarity,  are different from the traditional notions as Clarke criticality   \cite{clarke1983optimization,rockafellar1998Variational,davis2018stochastic}.
This is described in Theorems~\ref{th:tensorflowConservativeField} and \ref{th:convergenceGrad}.

\paragraph{Avoidance of traps:} As sketched above and in the introduction AD produces artificial critical points, i.e. stationary points which are not Clarke critical. These points have a parasitic nature which could be detrimental to training purposes, were they met in practice. We show that randomly initialized mini-batch stochastic gradient method do not lead to  artificial critical points (Theorem~\ref{th:trapAvoidance}). This result applies to modern machine learning software libraries based on AD \cite{abadi2016tensorflow,paszke2017workshop}, seen as performing operation over the reals, without any modification. Although AD may have unpredictable behavior in nonsmooth contexts, both theoretically and numerically, this result justifies theoretically that the practical impact is somewhat negligible in the context of common machine learning usage.

\paragraph{Related work:} Spurious behaviour of AD in nonsmooth context has been investigated in \cite{griewank2008evaluating,griewank2013stable,griewank2016lipschitz,griewank2016first,barton2018computationally,kakade2018provably,bolte2020conservative}. In particular, \cite{griewank2016first,kakade2018provably} considers qualification conditions allowing to construct AD algorithms which compute proper Clarke subgradients  \cite{clarke1983optimization,rockafellar1998Variational,davis2018stochastic}.  However qualification is extremely hard to check and almost impossible to enforce in practice.
Let us also mention \cite{barton2018computationally} which uses the notion of lexicographic derivatives, but, at this day, algorithmic computations are limited to forward mode for the moment which is of little use in machine learning.

\cite{griewank2008evaluating,griewank2013stable,griewank2016first,griewank2016lipschitz,griewank2019treating,griewank2020beyond} use settings closer to ours. Piecewise
smooth functions, selection derivatives and their variational properties are extensively described in \cite{scholtes2012introduction}. Our approach differs because we adopt more stringent definitions and rigidity assumptions, which allows in turn for much stronger properties.  For instance, we fully treat backward algorithmic differentiation which is the most useful tool in machine learning.

Altogether, our contribution is an accessible and elementary framework for the conservative fields recently introduced in \cite{bolte2020conservative}, without explicitly requiring the introduction of semialgebraic geometry and o-minimal structures \cite{dries1996geometric,Cos99}.

Stochastic approximation algorithms \cite{robbins1951stochastic,benaim1999dynamics,kushner20003stochastic,benaim2005stochastic,borkar2009stochastic} are widely used in machine learning contexts \cite{rumelhart1986learning,bottou2008tradeoffs,moulines2011nonasymptotic,lecun2015deep,bottou2018optimization,chizat,castera2019inertial}. For example \cite{davis2018stochastic} describes asymptotics of stochastic subgradient algorithms in nonsmooth, nonconvex settings. In contrast, we do not assume access to subgradients and instead explicitly model the behaviour of AD in optimization contexts. Our convergence results are based on \cite{bolte2020conservative}, complemented by a new result on
``the avoidance of critical traps'' in the line of \cite{bianchi2020convergence} in the context of long run convergence.

\noindent
{\bf Notations} The ambient space is Euclidean $\RR^p$. For each $k$, $e_k$ is the $k$-th vector of the canonical basis. We use $D \colon \RR^m \rightrightarrows\RR^q$ for set valued functions, \textit{i.e} functions from $\RR^m$ to the subsets of $\RR^q$. The convex hull of $A \subset \RR^p$ is denoted by $\mathrm{conv}(A)$. All proofs are postponed to the Appendix.
\section{Basic piecewise differentiable functions and selection gradient}
\label{sec:basicPDfunction}
We introduce a simple but vast class of functions that model rigorously the  machine learning models and losses for applications such as deep learning.
\begin{definition}[Elementary (log-exp) functions]{\rm
				{\em Elementary (log-exp) functions}  are functions on $\RR^p$ described by a finite compositional expression involving basic operations, $+,-,\times, /$ as well as affine mappings, exponential and logarithms, inside their domain of definition.  We denote by $\mathcal{E}$ the set of elementary functions in any dimension~$p$.
				\label{def:elemFunction}}
\end{definition}
Examples include polynomials, logistic loss, boosting loss, Gaussian likelihood.
Observe that  the corresponding functions are  $C^\infty$ smooth on their open domains. Note also that if log and exp are not present we obtain the field of rational functions. See Remark~\ref{r:elementary} in Appendix \ref{sec:auxiliaryResults}.

\begin{definition}[Elementary  index]
				$s \colon \RR^p \mapsto \left\{ 1,\ldots, m \right\}$ is an elementary (log-exp) index if the set $\left\{ x \in \RR^p,\, s(x) = i  \right\}$ is the solution set of a finite number of inequalities and equalities involving elementary functions on $\RR^p$.
				The set of such functions is denoted by  $\mathcal I$  (for any input dimensions $p$).
				\label{def:elemIndex}
\end{definition}
\textbf{Examples:} The Heaviside function, the index of the largest or $k$-th largest element in a vector, the sign pattern of a vector in $\RR^p$ which is indexed by integers from $1$ to $2^p$.

\begin{definition}[Elementary  selection]{\rm
    Let $f \colon \RR^p \mapsto \RR$ be continuous. We say that $f$ has an {\em elementary (log-exp)  selection} $(s, f_1, \ldots, f_m)$ if $s \colon \RR^p \mapsto \left(1,\ldots, m\right)$ is an elementary index in $\mathcal{I}$ and for $i = 1 \ldots, m$, $f_i\colon \RR^p \mapsto \RR$ are elementary functions in $\mathcal{E}$, such that for all $x \in \RR^p$,
    \begin{align}
        f(x) = f_{s(x)}(x).
        \label{eq:C1Selection}
    \end{align}
    The $m+1$-uplet $(s, f_1, \ldots, f_m)$ is a {\em representation} of $f$, and $f$ admits an {\em elementary (log-exp) selection}.
		The class of such functions is denoted by $\SSS_{\log\exp}$ or simply here $\SSS$. This extends to functions from $\RR^p$ to $\RR^m$ by applying a coordinatewise definition with a common elementary index.
    \label{def:C1selection}}
\end{definition}
Observe that the representation is {\em never} unique, both in $s$ and in the sequence $f_1,\ldots,f_m$.  The ReLU, hinge loss, maximal entry,  $k$-th largest entry functions are elementary selections. Note also that continuity is part of the definition.

\begin{proposition}[Stability of $\SSS$ by $\circ,+,\times$]\label{p:stability}
             The class $\SSS$ of elementary selections is stable by composition, sum and product.
\end{proposition}
The class $\SSS$ is close to the one of piecewise $C^k$ functions, see e.g \cite{scholtes2012introduction}, but it is also much more disciplined since indices and functions are required to satisfy strong ``log-exp" rigidity assumptions.

\subsection{Selection derivative}
Functions in $\mathcal{S}$ can be associated with a flexible notion of generalized derivative based on the selection structure of the underlying function.
\begin{definition}[Selection gradient]{\rm
				(i) Let $f \colon \RR^p \mapsto \RR$,  in $\mathcal{S}$ with selection $(s, f_1, \ldots, f_m)$. We set the {\em selection derivative of $f$ with respect to $s$} to be
				\begin{align}\label{e:deriv}
								\selgrad^s f \colon x \mapsto \nabla f_{s(x)}(x).
				\end{align}
				This extends to multivariate outputs by applying the definition coordinatewise, which leads to a notion of a {\em selection Jacobian} denoted by $\seljac^s$.\\
				(ii) Given a function $f\in \SSS$, a {\em selection derivative} is a derivative of the form \eqref{e:deriv} for a given representation. In that case a selection derivative of $f$ is merely denoted by $\selgrad f$.
				\label{def:derivative}}
			\end{definition}

\textbf{Example:} Set for all $x \in \RR$, $f_1(x) = 0$, $f_2(x) = x$ and $s(x) = 1$ for $x \leq 0$ and $s(x) = 2$ for $x>0$. This this defines the $\relu$ function and its selection derivative at $0$ is $0$. See more in Appendix \ref{sec:suppRelu}.

\textbf{Remark:} (a) $\selgrad f$ is different from any known notion of subgradient. Set for all $x \in \RR$, $f_1(x) = 0$, $f_2(x) = x$ and $s(x) = 1$ for $x \neq 0$ and $s(0) = 2$. This defines a  elementary selection  for the null function however, $\selgrad^s f(0) = 1$. This is the $\zero$ function of the introduction.\\

(b) This formalizes what one would obtained by differentiating a code with all decision branches frozen and hence represents the numerical output of AD (see \ref{sec:autodiff}). Note that one  only needs one branch and do not need to explore all possible outcomes, avoiding combinatorial explosion.

The properties of selection derivatives might seem too liberal at first sight and too disconnected from the original function, but this is not the case as shown below.
\begin{proposition}[Integration along segments]
				Let $f \colon  \RR^p \mapsto \RR$ be in $\SSS$, with elementary selection $(s, f_1, \ldots, f_m)$. Then $f$ is locally Lipschitz and for all $y,x$ in $\RR^p$.:
				\begin{align*}
										f(y)-f(x)=	\int_{0}^1 \left\langle y - x, \selgrad^s f(x + t(y-x)) \right\rangle dt
				\end{align*}

				\label{prop:SCintegration}
\end{proposition}

\begin{proposition}[Gradient almost everywhere]\label{gevery}
				Let $f \colon  \RR^p \mapsto \RR$ be in $\SSS$, with elementary selection $(s, f_1, \ldots, f_m)$. There exists sets $U_1,\ldots,U_N$ with nonempty interior such that $\bigcup_{i=1}^N \mathrm{cl}(U_i) = \RR^p$ and for each $i=1$, and for all $x$ in the interior of $U_i$, $\selgrad^s f(x) = \nabla f(x)$.
				Furthermore, the $U_i$ are solution sets of equations and inequalities involving functions in $\mathcal{E}$.
				\label{prop:SGradientAE}
\end{proposition}

\textbf{Remark:} Although less transparent, Proposition \ref{prop:SCintegration} is not a consequence of Proposition \ref{prop:SGradientAE}.
Both results crucially rely on the rigidity of elementary functions in $\mathcal{E}$ (Definition~\ref{def:C1selection}), not only on their piecewise smoothness. This a central novelty of our approach.

\subsection{A calculus for selection derivatives}

One has an unusual differential calculus: although it does not involve the linearity of some (sub)differential operator, the selection derivative of a sum gives a sum of selection derivatives provided that the selection is refined.

\begin{proposition}[Chain rule]
				Let $F \colon \RR^{p_1} \mapsto \RR^{p_2}$ such that each of its coordinate $f_i$, $i = 1 \ldots p_2$, is in $\mathcal{S}$ and $g \colon \RR^{p_2} \mapsto \RR$, $g \in \mathcal{S}$. Consider a  selection Jacobian for $F$,   $\seljac_F \colon \RR^{p_1} \mapsto \RR^{p_2 \times p_1}$
				\begin{align}
								x &\mapsto \begin{pmatrix}\selgrad {f_1}(x)^T \\
										\vdots\\
										\selgrad {f_q}(x)^T
								\end{pmatrix}
							\label{eq:chainRule}\end{align}
				Then $g \circ F \in \mathcal{S}$ and the function $x \mapsto \seljac_F(x)^T \selgrad g(F(x))$ is a selection derivative for $g \circ F$.
				\label{prop:compositionGeneralizedDerivatives}
\end{proposition}

Proposition \ref{prop:compositionGeneralizedDerivatives} extends readily to the case when the outer function $g$ is multivariate. For example, we  have a sum rule $\selgrad (f+g)=\selgrad f+\selgrad g$ for full-domain functions $f,g$ in~$\SSS$. Indeed, if $F_1$ and $F_2$ are elementary selections then $F_1 \circ F_2\in \SSS$  and
\begin{align}
    \seljac_{F_1 \circ F_2} = (\seljac_{F_1} \circ F_2) \times \seljac_{F_2}.
    \label{eq:chainRule}
\end{align}

\section{Programs and elementary selections}
\label{sec:programs}
Numerical programs encode numerical functions by combining elementary functions using a predecessor relation which models program  execution.
In what follows, $m$ can be seen as an estimate of the memory footprint of a program\footnote{We consider programs which do not overwrite values in memory}, while $p$ and $q$ the number of inputs and outputs respectively.

Given positive integers $m \geq p+q$, a {\em predecessor relation} is a set valued map $\pr \colon \left\{ 1,\ldots,m \right\} \rightrightarrows \left\{ 1, \ldots, m \right\}$ such that
\begin{itemize}
				\item For $i \in \left\{ 1,\ldots,m \right\}$ and $j \in \pr(i)$, $j < i$. \qquad $\bullet$ For $i \in \left\{ p+1,\ldots,m \right\}$, $\pr(i)$ is nonempty.
\end{itemize}

\begin{minipage}{.55\textwidth}
A predecessor relation induces a partial order on the set of integers from $1$ to $m$ and hence can be represented by a directed acyclic graph \cite[Theorem 9.4.9]{lehman2010mathematics}.
Given $(p,q,m)$ and a predecessor relation $\pr$, a elementary function sequence $\mathcal{G} = (g_i)_{i=p+1}^m$ is a set of functions such that $g_i \colon \RR^{|\pr(i)|} \mapsto \RR$, and $g_i \in \mathcal{S}$, for all $i = p+1, \ldots, m$.  A program $P$ is then given by the data
$		P = \left(p,q,m, \pr, \mathcal{G} \right),	\label{eq:program}
$ while its {\em evaluation} is described in Algorithm \ref{alg:algof}. We denote by
$\mathcal{P}$ the set of programs, and $\mathcal{P}_{p,q}$ when input-output dimensions have to be made  explicit.

By definition a program encodes a function, but the representation is not unique. We express this fact below through the canonical surjection $\mathcal F$ of the introduction.
\end{minipage}\qquad
\begin{minipage}{.4\textwidth}
\begin{algorithm}[H]
  \caption{Program evaluation}
	\label{alg:algof}
	\textbf{Program data:} $p,q \geq 1$, $m \geq p+q$, $\pr$ a predecessor relation, $\mathcal{G} = (g_i)_{i=p+1}^m$ an adapted function sequence.
  \begin{algorithmic}[1]
  \item[\textbf{Input:}] $x=(x_1, \ldots x_p)$
    \FOR{$k=p+1,p+2,\ldots m$}
    \STATE $x_k = g_{k} (x_{\pr (k)})$ where $x_{\pr (k)} = \left( x_i \right)_{i \in \pr (k)}$.
    \ENDFOR
		\item[\textbf{Return:}] $y := (x_j)_{j = m-q + 1}^m$.
\end{algorithmic}
\end{algorithm}
\end{minipage}
The following proposition illustrates the fact that practitioners {\em implicitly} implement selection functions when writing programs.
\begin{proposition}[Programs represents elementary selections]
   Through its input-output correspondence each program $P$ of the form \eqref{eq:program} induces  a function which is an elementary selection.
   In other words $\mathcal{F}(P) \in \mathcal{S}.$
\end{proposition}

\section{Algorithmic differentiation and a variational model}
\label{sec:autodiff}

Algorithmic differentiation is based on the idea of propagating infinitesimal variations in a program $P$ through the chain rule,  either forward or backward.

\begin{algorithm}[H]
  \caption{Algorithmic differentiation computes selection gradients}
	\label{alg:autodiff0}
	\textbf{Program data:} $p \geq 1$, $m \geq p+1$, $\pr$ a predecessor relation, $\mathcal{G} = (g_i)_{i=p+1}^m$ an adapted function sequence. \\
	\textbf{Input:} variables $(x_1, \ldots x_m)$ computed by Algorithm \ref{alg:algof}, $d_i = (d_{i}[j])_{j=1}^{|\pr (i)|} =  \selgrad {g_i}(x_{\pr (i)})$, $i = p+1 \ldots m$
	\vspace{.1in}

   \begin{minipage}[h]{0.45\linewidth}
   \begin{algorithmic}[1]
    \STATE \textbf{Forward mode:}
    \STATE Initialize: $
    \frac{\partial x_k}{\partial x} = e_k $,\\ $k = 1,\ldots, p$.
    \FOR{$k= p+1, \ldots m$}
    \STATE
    \[
    \frac{\partial x_k}{\partial x} = \sum_{j \in \pr (k)} \frac{\partial x_j }{\partial x} d_{k}[j]
    \]
    \mbox{where $x=(x_1,\ldots,x_p).$}
    \ENDFOR
    \item[\textbf{Return:}]
$\frac{\partial x_m}{\partial x}$.
  \end{algorithmic}
  \end{minipage}
  \begin{minipage}[h]{0.45\linewidth}
     \begin{algorithmic}[1]
     \STATE \textbf{Backward mode:}
    \STATE Initialize: $ v = e_m$
    \FOR{$t= m, \ldots p+1$}
    \FOR{$j \in \pr (t)$}
        \STATE Update coordinate $j$ of $v$:
    \[
    v[j] \mathrel{:=}  v[j] + v[t] d_{t}[j]
    \]
    \ENDFOR
    \ENDFOR
    \item[\textbf{Return:}]
$\left(v[1], v[2], \ldots, v[p]\right) $.
  \end{algorithmic}
  \end{minipage}
\end{algorithm}

Consider Algorithm \ref{alg:algof}, and assume for simplicity that $q=1$. The program can be seen as the implementation of $m-p$ successive transformations on $\RR^m$, of the form
\begin{align*}
        G_k \colon \RR^m &\mapsto\RR^m \\
        x &\mapsto x + e_k(g_k(x_{\pr (k)}) - x_k),
\end{align*}
for $k = p+1, \ldots, m$ which belong to $\mathcal{S}$. Algorithm \ref{alg:autodiff0} combines gradients dynamically along two modes: forward or backward.
Let us describes these two forms.

Fix $x \in \RR^m$. After applying Algorithm \ref{alg:algof}, for each $k$, let $d_k \in \RR^m$ be the selection gradient $\selgrad g_k(x_{\pr (k)})$, appending $0$ to non dependant coordinates. A selection Jacobian of $G_k$ (at $x$) is given by
\begin{align*}
    \seljac_{G_k}  = I - e_k e_k^T + e_k d_k^T
\end{align*}
Denote by $J_p \in \RR^{m \times p}$, the matrix whose entries are $0$, except for diagonal entries which are $1$. In Algorithm \ref{alg:autodiff0}, the forward mode computes
\begin{align*}
    e_m^T  \seljac_{G_m}  \ldots  \seljac_{G_{p+1}} J_p = e_m^T  \left(I - e_m e_m^T + e_m d_m^T \right)  \ldots   \left(I - e_{p+1} e_{p+1}^T + e_{p+1} d_{p+1}^T \right) J_p
\end{align*}
which is a selection Jacobian thanks to the chain rule in \eqref{eq:chainRule}.
On the other hand the backward mode computes
\begin{align*}
J_p^T  \left(I + d_{p+1}e_{p+1}^T \right) \ldots \left(I + d_{m}e_{m}^T \right) e_m.
\end{align*}
This quantity turns out to be the same as the one computed by the forward mode thanks to:
\begin{lemma}
		Let $p,m \in \NN$, $0<p<m$. Assume that for $i = p+1,\ldots, m$ we have $d_i \in \RR^m$. Then we have
		\begin{align}
					P_p \left(I - e_{p+1} e_{p+1}^T + d_{p+1}e_{p+1}^T \right) \ldots \left(I - e_{m} e_{m}^T + d_{m}e_{m}^T \right) = P_p \left(I + d_{p+1}e_{p+1}^T \right) \ldots \left(I + d_{m}e_{m}^T \right)
					\label{eq:backpropAlgebra}
		\end{align}
		where $I \in \RR^{m \times m}$ is the identity matrix and $P_p \in \RR^{m \times m}$ denotes the projection on the first $p$ coordinates.
		\label{lem:algebraBackprop}
\end{lemma}

Denote by  $\mathcal{A}:\PP_{p,1}\to \PP_{p,p}$ the algorithmic-differentiation operator. This establishes the following fundamental fact which is at the root of this work. This result asserts that practitioners {\em implicitly} implement selection derivatives when writing numerical programs and calling forward or backward AD on these programs.
\begin{theorem}[Algorithmic differentiation outputs a selection gradient]\label{t:autodiffgrad}
Algorithmic differentiation of a given program, i.e.,  $\mathcal{A}(P)$, outputs a selection derivative of the underlying numerical function. In other words there exists a representation of the numerical function $\FF(P)$ with elementary index $s$ such that:
$$\FF(\mathcal{A}(P))=\selgrad^s \FF(P).$$
\end{theorem}

\section{Algorithmic differentiation at work}

\subsection{Selection derivatives, conservative fields and Clarke subgradient}

The asymptotic study of first-order optimization methods implies limiting processes and necessitates thus the introduction of graph closed operators. Given a representation for $f$, we may construct such a convex-valued mapping pointwise as follows\footnote{Minimality relates to the {\em representation of the function}, not the function itself. This is the minimal convex-valued operator, constructed pointwise and guaranteed to be graph-closed.}.
\begin{definition}[Representation minimal operator]\label{def:tensorflowConservativeField}
			{\em	Let $f \in \mathcal{S}$ with elementary selection $(s, f_1, \ldots, f_m)$. For any $x \in \RR^p$, set $I(x) = \left\{ i\in\left\{ 1,\ldots,m \right\}, \, f(x) = f_i(x) \right\}$. The index closure of $\selgrad^s f$ is given by the set valued map
				\begin{align*}
				D^s_f \colon \RR^p &\rightrightarrows \RR^p \\
								x &\rightrightarrows \mathrm{conv}\left( \left\{ \nabla f_i(x),\, i \in I(x) \right\} \right).
				\end{align*}
				where the double arrows express that the map has values in subsets of $\RR^p$, much like subgradients, and $\conv$ denotes the convex hull.
}
\end{definition}

The role of $D^s_f$ is to capture all possible outputs of AD including all possible program branches. Of course, due to combinatorial explosion, this quantity is intractable in practice. Its introduction here is only instrumental, we do not use it in algorithms, we just need to access one of its element, for example using a selection derivatives, obtained from AD.
A point $x$ satisfying $0 \in D^s_f(x)$ is called a {\em selection critical point}. We will often drop the index $s$ and write $D_f=D^s_f$.

The two following results highlight crucial properties of $D_f$ in terms of optimization, they again rely on the rigidity constraint of elementary functions.

\begin{theorem}\label{th:tensorflowConservativeField}
				Let $f \in \mathcal{S}$ with  elementary selection  $(s, f_1, \ldots, f_m)$ and $D_f$ be as in Definition \ref{def:tensorflowConservativeField}. Then $D_f$ is conservative for $f$, that is for all absolutely continuous curves $\gamma \colon [0,1] \mapsto \RR^p$, for almost all $t \in [0,1]$, $f\circ \gamma$ is differentiable and
				\begin{align*}
								\frac{d}{dt} f(\gamma(t)) = \left\langle v, \dot{\gamma}(t) \right\rangle,\qquad \forall v \in D_f(\gamma(t)).
				\end{align*}
\end{theorem}

The previous result generalizes Proposition \ref{prop:SCintegration} by allowing to integrate arbitrary selections along absolutely continuous curves.
This connects our work to the general setting of \cite{bolte2020conservative}, note that $D_f$ has a closed graph thanks to Proposition \ref{prop:Dcontinuity} in Appendix \ref{sec:auxiliaryResults}.

In \cite{scholtes2012introduction}, the author considers the {\em essential index set}, for each $x \in \RR^p$,
\begin{align*}
    S_E(x) = \left\{ i\in\left\{ 1,\ldots,m \right\}, \, x\in \mathrm{cl}(\mathrm{int}(\{y,\,f(y) = f_i(y)\})) \right\} \subset S(x).
\end{align*}
Considering Definition \ref{def:tensorflowConservativeField} with $S_E(x)$ instead of $I(x)$ leads to the Clarke subgradient, which can also be defined as
$$\partial^cf(x)=\mathrm{conv}\{d\in \R^p:\exists x_k \in \Delta_f, x_k\to x, \nabla f(x_k)\to d\}$$
where $\Delta_f$ is the dense set of differentiability points of $f$.  While $I(x)$ can be computed pointwise (check finitely many equalities), it might be very hard to check membership in $S_E(x)$ without restrictive qualification conditions on programs \cite{kakade2018provably}.

\paragraph{Illustration with ReLU and sorting:}
(a) Set for all $x \in \RR$, $f_1(x) = 0$, $f_2(x) = x$, $s(x) = 1$ for $x \leq 0$ and $s(x) = 2$ for $x>0$. This  is $\relu$. In this case $D_f = \partial \relu$, the convex subgradient.\\
(b)
Let  $F \colon \RR^p \mapsto \RR^p$ to be the sorting function which associates to $x$ a vector $Px$ where $P$ is any permutation such that $Px$ belongs to the set of vectors which values are sorted in descending order coordinatewise. $F$ obviously has an elementary selection  and the construction which we have proposed leads to
\begin{align*}
    D_F \colon x &\mapsto \conv \left\{ P \in \Delta, \quad Px = F(x) \right\},
\end{align*}
where $\Delta$ denotes the set of permutation matrices of size $p \times p$. Then $D$ is a conservative mapping for $F$ and it actually corresponds to the Clarke Jacobian.

\subsection{Convergence of gradient type algorithm and criticality of limit points}

Optimization processes in learning are supposed to provide at least a critical point $x$ of the loss, i.e. a point satisfying   $0 \in \partial^cf(x)$. When using AD  one enlarges the definition of criticality into
$0 \in D_f(x)$  and {\em artificial critical points} appear, they satisfy $0 \not \in \partial^c f(x)$ and $0 \in D_f(x)$. Artificial critical points could possibly trap the optimization process in strongly non-optimal situations, we thus have to determine if they have an impact on learning phases.

We consider the problem
\begin{align}
    \min_{x \in \RR^p} J(x) = \frac{1}{n} \sum_{i=1}^n f_i(x)
    \label{eq:mainProblem}
\end{align}
where $f_i \colon \RR^p \mapsto \RR$, $f_i \in \mathcal{S}$, $i=1,\ldots, n$. We consider the following algorithm, given $x_0 \in \RR^p$, a sequence of positive step sizes $(\gamma_k)_{k \in \NN}$ and a sequence of \textit{iid} indices $(I_k)_{k\in \NN}$ taken uniformly in the nonempty subsets of $\left\{0,\ldots, n\right\}$,
\begin{align}
    x_{k+1} = x_k - \gamma_k \selgrad f_{I_k}(x_k) \mbox{ where }f_I=\frac{1}{|I|}\sum_{i\in I}f_i, \:I\subset \{1,\ldots,n\}.
    \label{eq:gradientDescent}
\end{align}
Note that as discussed in Section \ref{sec:autodiff} selection derivatives can be computed by AD if $f_i$ are given by the data of numerical programs as in \eqref{eq:program}, and could be far from usual notions of subgradients. Hence this algorithm models explicitly the training of a nonsmooth deep network using existing backpropagation implementations. Note that $J \in \mathcal{S}$ and that $1/n \sum_{i=1}^n \selgrad f_i$ is a selection gradient for $J$ as stated in Proposition \ref{prop:compositionGeneralizedDerivatives}, denote by $\selgrad J$ this quantity and $D_J$ the corresponding set valued field (Definition \ref{def:tensorflowConservativeField}). The following result illustrates that selection critical points are the only attractors for the recursion and that generically such attractors are actually Clarke critical. The first result stands on the theory developed in \cite{benaim2005stochastic}. The second parallels developments in \cite{bianchi2020convergence} in the context of long run convergence. The spurious behaviour illustrated in Figure \ref{fig:illustrAutodiff} does not affect asymptotics, for typical initialization.
\begin{theorem}[Convergence and insignificance of artefacts]
    \label{th:convergenceGrad}
    Let for all $k$, $\gamma_k = c \alpha_k$ where $c \in (0,1]$ and $\alpha_k=o(1/\log k)$ and $K \subset \RR^p$ be open.
Assume that for all $c \in (0,1]$ and all $x_0 \in K$ the sequence in \eqref{eq:gradientDescent} is bounded almost surely.
\begin{itemize}
    \item For all $x_0 \in K$, almost surely, $J(x_k)$ converges as $k$ tends to infinity and all accumulation points, $\bar{x}$, of $(x_k)_{k \in \NN}$ are selection critical points: $0 \in D_J(\bar{x})$.
    \item For almost all $c \in (0,1]$, almost all $x_0 \in K$, and almost surely, any accumulation point, $\bar{x}$, of $(x_k)_{k \in \NN}$ is Clarke critical: $0 \in \partial^cJ(\bar{x})$.
\end{itemize}

    \label{th:trapAvoidance}
\end{theorem}

\section{Conclusion}
The current work departs from existing approaches to  nonsmooth algorithmic differentiation  in a fundamental way. We propose to study the backward mode of AD, as implemented in machine learning, without any modification. Our theoretical results model thus AD  ``as is", and our focus is precisely on its unpredictable behavior  in a nonsmooth context, addressing an issue which is ubiquitous in machine learning. Our main contribution was to prove  that, in a stochastic optimization context, this spurious behavior is essentially harmless from a theoretical point of view, providing justifications for the use of AD outside of its original domain of validity in machine learning.

We achieve our goal by modeling sharply common machine learning functions and their differentiation using selection derivatives, a known concept, which models the way AD differentiates nonsmooth programs. We restrict it to certain classes of elementary functions, opening the possibility to use powerful geometric techniques.

Further questions include convergence rates and complexity issues, hardly tackled at this day, let us mention the attempt of \cite{zhang2020complexity}. Our theory is limited to continuous functions and an interesting venue is to extend it to discontinuous functions, in view of treating ranking operations \cite{blondel2020fast} ubiquitous in recommendation systems, or more generally differentiating through an argmax \cite{berthet2020learning}.

\section*{Broader impact}
One of the goals of the paper is to raise awareness about an important issue of in the training of ML methods: the spuriousness of AD. To address adequately this issue, we think it is necessary  to include algorithmic differentiation explicitly in the study of optimization algorithms, a point of view which is largely ignored by today's machine learning community.

\begin{ack}
The authors acknowledge the support of ANR-3IA Artificial and Natural Intelligence Toulouse Institute, Air Force Office of Scientific Research, Air Force Material Command, USAF, under grant numbers FA9550-19-1-7026, FA9550-18-1-0226, and ANR MasDol. J. Bolte acknowledges the support of ANR Chess, grant ANR-17-EURE-0010 and ANR OMS. The authors would like to thank anonymous referees for careful reading of this work and useful suggestions.
The authors would like to thank N. Asher and S. Gerchinovitz for useful discussions. We also warmly thank J. Malick who triggered this research.
\end{ack}

config: arxiv


TITLE: How many vectors are there in a two dimensional linear subspace of $(\mathbb{Z}_3)^6$?
QUESTION [0 upvotes]: Let $W$ be a two dimensional linear subspace of $(\mathbb{Z}_3)^6$. How many vectors does $W$ contain?
My shot is that we have $3$ possible values for each of $6$ positions in a vector and we have $2$ of them. $W$ is a set: $$W=\{(x_1,...,x_6),(y_1,...,y_6)\}.$$ First vector can have $3^6$ possible permutations of coordinates. Same for the second one. Since the question didn't ask for all possible pairs, I conclude that $3^6$ is the answer. Is that right?

REPLY [0 votes]: A 2-dimensional subspace of $\mathbb F_3^6$ is isomorphic to $\mathbb F_3^2$ and thus should have $3^2=9$ distinct vectors.


TITLE: Closure and inclusion with countable union of closed sets
QUESTION [1 upvotes]: Let $X$ be a topological space and fix a sequence of closed sets $(C_n)$ such that $C_n\subseteq C_{n+1}$ for all $n$. Then $C:=\bigcup C_n$ is an $F_{\sigma}$-set. Fix also a set $S\subseteq C$. Is it true that
$$
\mathrm{Closure}(S) \subseteq C\,\,\,?
$$
My attempt: For each $n$ we have $C_n \supseteq C_n \cap S$. Hence $C_n \supseteq \mathrm{Closure}(C_n \cap S)$ hence
$$
C = \bigcup C_n \supseteq \bigcup \mathrm{Closure}(C_n \cap S).
$$
At this point, is it true that $\bigcup \mathrm{Closure}(C_n \cap S)=\mathrm{Closure}(S)$?

REPLY [1 votes]: Let $X= \mathbb{R}$ in the usual topology. Enumerate the rationals as $r_n, n=1,2,\ldots$, and define $C_n = \{r_1, \ldots, r_n\}$ which are all finite thus closed. Then $C= \mathbb{Q}$ and $S= \mathbb{Q}$ has closure $\mathbb{R}$..


TITLE: If $G$ be the centroid of...
QUESTION [1 upvotes]: If $G$ be the centroid of $\triangle ABC$, prove that $AB^{2} + BC^{2} + CA^{2} = 3(GA^{2}+GB^{2}+GC^{2}).$
Please help me. I couldn't get even to the first step. However,  i guess centroid is the point of intersection of medians of triangle and median is the the line that joins the vertex to the mid point of opposition side, not the perpendicular. Am I right?
Please help me to solve this.

REPLY [3 votes]: Hint
$1)$ If $M$ is the midpoint of $BC$ then $GA=(2/3)AM$.
$2)$ Use Stewart's theorem to find $AM$:

$$AB^2\cdot CM+AC^2\cdot BM=BC(AM^2+BM\cdot CM)\quad (1)$$
Use that $$BM=CM=BC/2$$
and then $(1)$ becomes:
$$ AM^2=\frac{1}{4}\left(2AB^2+2AC^2-BC^2\right)$$
So,
$$GA^2=\frac{1}{9}\left(2AB^2+2AC^2-BC^2\right)$$
Use the same idea to find $GB^2$ and $GC^2$.
Can you finish?


TITLE: Primes in the form $n^{k}+n-1$
QUESTION [9 upvotes]: Lately I've been (very casually) toying with primes in the form $n^k+n-1$, as a very far-reaching generalization of Fermat primes. (you get a Fermat prime when you set $k=2^m$ and $n=2$). I have little training in number theory, so mainly I've been just typing stuff into Wolfram and searching for patterns.
One thing I started doing was looking for the smallest $k$ such that $n^k+n-1$ is prime for any particular $n$. I've been able to find solutions for $n \leq 106$. Obviously $k=1$ and $k=2$ do a lot of heavy lifting, but there are some remarkable numbers here. The one that stunned me the most upon finding it was $32^{108}+31 \approx 3.6 \times 10^{162}$, but there's an even bigger smallest solution: $80^{194}+79 \approx 1.58 \times 10^{369}$.
For $n=107$, there are no solutions for $k \leq 495$, which is about as far as I can reliably check.  Obviously any $k$ that works must be divisible by $4$.
So, three things I wonder about are:

Is any solution for $n=107$ known? Does it exist for sure?
In general, has it been shown that there is a solution for any $n$?
For any $k$ not in the form $6m+5$, is there $n$ such that $k$ is the smallest solution?

EDIT:
Let $f(n)$ be any polynomial $\mathbb N \rightarrow \mathbb N$. Let $\text{GCD}[f]$ denote the greatest common divisor of $\{f(n): n \in \mathbb N\}$. There is this long-standing conjecture by Bouniakowsky that $f$ is irreducible iff there are infinitely many numbers $n$ such that $\frac{f(n)}{\text{GCD}[f]}$ is prime.
If we suppose this is true, then the following statement implies a positive answer to question 3:
For any $k: k \not \equiv 5 \pmod 6$ there are natural numbers $\alpha,\beta$ such that $\text{GCD}[(\alpha n+\beta)^k+(\alpha n+\beta)-1]=1$, but $\text{GCD}[(\alpha n + \beta)^m+(\alpha n + \beta)-1] \neq 1$ for any $m<k: m \not \equiv 5 \pmod 6$.
Example: for $k=3$, one can let $\alpha = 15, \beta = 2$.
To my untrained eye, this seems approachable.

REPLY [4 votes]: Not a 'real' answer, but it was too big for a comment. I think that you're looking for a solution without using a calculator or PC but maybe this gives some insight. I did only a quick search with the following bounds: $1\le\text{n}\le10^3$ and $1\le\text{k}\le10$.

I wrote and ran some Mathematica-code:
In[1]:=Clear["Global`*"];
\[Alpha] = 10^3;
\[Beta] = 10^1;
ParallelTable[
  If[PrimeQ[n^k + n - 1], {n, k}, Nothing], {n, 1, \[Alpha]}, {k,
   1, \[Beta]}] //. {} -> Nothing

Running the code gives:
Out[1]={{{2, 1}, {2, 2}, {2, 4}, {2, 8}}, {{3, 1}, {3, 2}, {3, 3}, {3,
   4}, {3, 8}, {3, 10}}, {{4, 1}, {4, 2}, {4, 3}, {4, 6}, {4, 8}, {4,
   9}}, {{5, 2}, {5, 6}, {5, 10}}, {{6, 1}, {6, 2}, {6, 4}, {6,
   7}, {6, 10}}, {{7, 1}, {7, 3}}, {{8, 2}, {8, 6}, {8, 10}}, {{9,
   1}, {9, 2}, {9, 4}, {9, 7}, {9, 10}}, {{10, 1}, {10, 2}, {10,
   3}, {10, 4}, {10, 9}}, {{11, 2}, {11, 8}}, {{12, 1}, {12,
   4}}, {{13, 2}, {13, 4}, {13, 10}}, {{15, 1}, {15, 2}, {15, 3}, {15,
    9}}, {{16, 1}, {16, 2}, {16, 3}, {16, 4}, {16, 8}, {16,
   10}}, {{17, 4}, {17, 8}}, {{18, 3}, {18, 6}}, {{19, 1}, {19,
   2}}, {{20, 2}, {20, 4}}, {{21, 1}, {21, 2}, {21, 3}}, {{22,
   1}, {22, 7}}, {{23, 4}, {23, 6}}, {{24, 1}, {24, 2}, {24,
   10}}, {{25, 3}, {25, 8}}, {{26, 2}, {26, 4}, {26, 10}}, {{27,
   1}, {27, 3}, {27, 8}}, {{28, 2}, {28, 4}}, {{29, 10}}, {{30,
   1}, {30, 2}, {30, 7}}, {{31, 1}, {31, 2}, {31, 4}, {31, 6}, {31,
   10}}, {{33, 3}, {33, 4}}, {{34, 1}, {34, 6}}, {{35, 2}}, {{36,
   1}, {36, 3}, {36, 6}}, {{37, 1}, {37, 7}}, {{38, 2}}, {{39,
   2}, {39, 3}}, {{40, 1}, {40, 4}, {40, 10}}, {{41, 2}}, {{42,
   1}}, {{43, 3}, {43, 4}}, {{44, 2}, {44, 4}}, {{45, 1}, {45,
   2}}, {{46, 2}, {46, 3}, {46, 8}}, {{48, 2}}, {{49, 1}, {49,
   7}, {49, 9}}, {{50, 2}, {50, 6}, {50, 8}}, {{51, 1}, {51, 3}, {51,
   6}, {51, 10}}, {{52, 1}, {52, 3}}, {{53, 2}, {53, 6}}, {{54,
   1}, {54, 2}, {54, 4}}, {{55, 1}, {55, 2}, {55, 3}}, {{56, 2}, {56,
   6}}, {{57, 1}, {57, 9}}, {{58, 4}}, {{59, 2}, {59, 10}}, {{60,
   2}, {60, 6}}, {{61, 7}, {61, 9}}, {{62, 8}}, {{63, 3}, {63,
   6}}, {{64, 1}, {64, 2}}, {{65, 2}}, {{66, 1}, {66, 2}, {66,
   8}, {66, 9}}, {{68, 2}, {68, 8}}, {{69, 1}, {69, 6}}, {{70,
   1}, {70, 2}, {70, 7}, {70, 9}}, {{72, 4}}, {{73, 3}, {73,
   6}}, {{74, 8}}, {{75, 1}, {75, 6}}, {{76, 1}, {76, 2}, {76,
   6}, {76, 10}}, {{77, 4}, {77, 8}}, {{78, 3}}, {{79, 1}, {79,
   9}}, {{81, 3}}, {{82, 1}}, {{83, 2}, {83, 6}}, {{84, 1}, {84,
   8}}, {{85, 2}}, {{86, 2}}, {{87, 1}, {87, 3}, {87, 8}}, {{88,
   8}}, {{89, 2}, {89, 10}}, {{90, 1}, {90, 10}}, {{91, 1}, {91,
   6}}, {{92, 4}}, {{93, 2}, {93, 3}, {93, 4}, {93, 7}}, {{94,
   2}, {94, 3}}, {{96, 1}, {96, 2}, {96, 3}, {96, 6}, {96, 10}}, {{97,
    1}}, {{98, 4}}, {{99, 1}, {99, 10}}, {{100, 1}, {100, 2}, {100,
   3}, {100, 7}, {100, 8}}, {{101, 2}}, {{103, 2}, {103, 3}, {103,
   10}}, {{105, 3}, {105, 4}, {105, 7}, {105, 9}}, {{106, 1}}, {{108,
   6}}, {{109, 3}}, {{110, 4}}, {{111, 6}, {111, 8}}, {{112, 1}, {112,
    3}, {112, 9}}, {{114, 1}, {114, 2}, {114, 9}}, {{115, 1}, {115,
   2}, {115, 3}, {115, 7}}, {{116, 6}}, {{117, 1}, {117, 3}, {117,
   4}, {117, 8}}, {{118, 6}, {118, 7}, {118, 8}}, {{119, 4}}, {{120,
   1}, {120, 2}, {120, 3}, {120, 4}, {120, 10}}, {{121, 1}, {121,
   9}}, {{122, 4}, {122, 8}}, {{124, 3}, {124, 10}}, {{125, 2}, {125,
   4}, {125, 8}}, {{126, 1}, {126, 2}, {126, 8}}, {{127, 3}}, {{129,
   1}, {129, 3}}, {{130, 2}}, {{131, 2}}, {{132, 1}, {132, 4}, {132,
   7}, {132, 8}}, {{133, 8}}, {{134, 2}, {134, 10}}, {{135, 1}, {135,
   3}, {135, 6}}, {{136, 1}}, {{138, 2}}, {{139, 1}, {139, 3}}, {{140,
    2}, {140, 8}}, {{141, 1}, {141, 2}}, {{142, 1}, {142, 7}, {142,
   9}}, {{143, 4}, {143, 6}}, {{144, 2}, {144, 9}}, {{145, 2}, {145,
   3}}, {{146, 8}}, {{147, 1}, {147, 9}}, {{148, 2}, {148, 6}}, {{149,
    2}, {149, 8}}, {{150, 3}}, {{151, 3}}, {{153, 2}, {153,
   8}}, {{154, 1}, {154, 2}}, {{155, 2}, {155, 10}}, {{156,
   1}}, {{157, 1}, {157, 4}}, {{158, 2}}, {{159, 1}, {159, 2}, {159,
   6}, {159, 7}}, {{160, 2}, {160, 8}}, {{162, 8}}, {{163, 2}, {163,
   7}}, {{164, 2}, {164, 4}, {164, 8}, {164, 10}}, {{165, 3}, {165,
   8}, {165, 9}}, {{166, 1}, {166, 3}, {166, 9}}, {{168, 8}, {168,
   10}}, {{169, 1}, {169, 2}, {169, 7}}, {{171, 2}, {171, 3}, {171,
   8}}, {{172, 9}}, {{174, 1}, {174, 2}, {174, 9}}, {{175, 1}}, {{176,
    2}}, {{177, 1}}, {{178, 3}, {178, 10}}, {{180, 1}, {180, 2}, {180,
    7}, {180, 8}}, {{181, 2}, {181, 8}}, {{182, 4}}, {{183, 6}, {183,
   8}}, {{184, 1}, {184, 2}, {184, 7}}, {{185, 10}}, {{186,
   2}}, {{187, 1}}, {{188, 2}, {188, 6}, {188, 8}}, {{189, 3}, {189,
   6}}, {{190, 1}}, {{191, 2}, {191, 6}}, {{192, 1}, {192, 3}}, {{193,
    2}}, {{195, 1}, {195, 2}}, {{196, 2}, {196, 7}}, {{198,
   3}}, {{199, 1}, {199, 2}, {199, 3}, {199, 9}}, {{201, 1}, {201,
   4}, {201, 6}}, {{202, 3}}, {{203, 2}}, {{204, 3}, {204, 4}}, {{205,
    1}, {205, 4}}, {{206, 2}, {206, 6}}, {{208, 7}}, {{209, 2}, {209,
   8}}, {{210, 1}}, {{211, 1}, {211, 7}}, {{215, 2}}, {{216, 1}, {216,
    3}, {216, 8}, {216, 9}}, {{217, 1}}, {{218, 2}}, {{219,
   2}}, {{220, 1}, {220, 2}}, {{221, 8}}, {{222, 1}}, {{223,
   3}}, {{225, 1}, {225, 2}}, {{228, 3}}, {{229, 1}, {229, 4}, {229,
   9}}, {{230, 2}, {230, 6}, {230, 8}, {230, 10}}, {{231, 1}, {231,
   2}, {231, 4}, {231, 6}}, {{232, 1}}, {{233, 2}}, {{234, 1}, {234,
   6}}, {{235, 8}}, {{236, 2}}, {{240, 1}, {240, 2}}, {{241, 2}, {241,
    3}}, {{243, 3}}, {{244, 1}, {244, 2}, {244, 9}}, {{246, 1}, {246,
   2}, {246, 3}}, {{247, 7}}, {{248, 2}, {248, 6}, {248, 8}}, {{250,
   1}}, {{252, 1}}, {{253, 8}}, {{254, 6}, {254, 8}}, {{255, 1}, {255,
    6}, {255, 7}}, {{256, 9}}, {{258, 2}, {258, 3}}, {{259, 2}, {259,
   3}, {259, 7}}, {{260, 6}, {260, 8}}, {{261, 1}}, {{262, 1}}, {{263,
    2}}, {{264, 2}}, {{265, 2}, {265, 8}}, {{266, 4}}, {{268,
   2}}, {{271, 1}, {271, 6}}, {{274, 1}}, {{275, 4}}, {{276,
   7}}, {{279, 1}, {279, 4}}, {{280, 8}}, {{281, 2}}, {{282,
   1}}, {{283, 3}}, {{285, 1}, {285, 2}, {285, 3}}, {{286, 1}, {286,
   3}, {286, 4}}, {{288, 2}, {288, 4}}, {{289, 1}, {289, 6}}, {{290,
   2}, {290, 4}, {290, 8}}, {{291, 9}}, {{292, 4}, {292, 8}}, {{293,
   4}}, {{294, 1}, {294, 2}}, {{296, 2}}, {{297, 1}}, {{298,
   2}}, {{300, 1}, {300, 3}}, {{301, 1}, {301, 2}}, {{303, 2}}, {{304,
    1}, {304, 4}}, {{305, 2}, {305, 6}}, {{306, 2}}, {{307, 1}, {307,
   7}}, {{308, 10}}, {{309, 1}, {309, 2}, {309, 4}}, {{310, 1}, {310,
   3}, {310, 8}}, {{312, 8}}, {{313, 3}}, {{314, 2}}, {{316, 1}, {316,
    3}}, {{318, 4}}, {{319, 2}, {319, 3}}, {{321, 1}, {321,
   4}}, {{322, 1}, {322, 4}}, {{323, 2}, {323, 6}}, {{324, 1}, {324,
   10}}, {{326, 8}}, {{327, 1}, {327, 7}, {327, 8}}, {{328,
   6}}, {{329, 4}}, {{330, 1}, {330, 2}, {330, 4}, {330, 9}}, {{331,
   1}, {331, 2}, {331, 6}}, {{334, 3}, {334, 4}}, {{335, 2}}, {{336,
   10}}, {{337, 1}}, {{339, 1}, {339, 2}, {339, 10}}, {{342,
   1}}, {{343, 2}, {343, 3}}, {{344, 4}}, {{346, 1}, {346, 9}}, {{348,
    3}, {348, 6}}, {{349, 2}, {349, 6}}, {{350, 2}, {350, 4}}, {{351,
   1}, {351, 2}, {351, 4}, {351, 10}}, {{352, 3}, {352, 7}}, {{353,
   4}}, {{354, 2}}, {{355, 1}}, {{356, 8}}, {{358, 2}}, {{360,
   1}, {360, 2}, {360, 3}, {360, 8}}, {{361, 2}}, {{363, 4}}, {{364,
   1}, {364, 2}}, {{366, 3}, {366, 4}, {366, 10}}, {{367, 1}, {367,
   3}, {367, 8}}, {{370, 1}, {370, 9}}, {{371, 6}}, {{372, 1}}, {{373,
    2}, {373, 4}, {373, 6}}, {{374, 2}}, {{375, 6}}, {{376, 1}, {376,
   3}}, {{378, 2}}, {{379, 1}, {379, 3}}, {{380, 2}, {380, 6}}, {{381,
    1}, {381, 3}, {381, 7}}, {{385, 1}, {385, 2}, {385, 6}, {385,
   7}, {385, 8}}, {{386, 2}, {386, 6}}, {{387, 1}, {387, 7}, {387,
   9}}, {{390, 4}}, {{391, 2}, {391, 3}}, {{393, 2}, {393, 6}, {393,
   8}}, {{394, 1}}, {{395, 2}, {395, 10}}, {{396, 2}}, {{397,
   4}}, {{398, 4}, {398, 8}}, {{399, 1}, {399, 4}}, {{401, 2}, {401,
   6}}, {{405, 1}, {405, 2}}, {{406, 1}, {406, 4}, {406, 7}}, {{407,
   4}}, {{408, 2}, {408, 4}, {408, 7}}, {{409, 4}, {409, 8}}, {{411,
   1}}, {{412, 1}, {412, 3}}, {{414, 1}, {414, 6}}, {{415, 1}}, {{417,
    3}}, {{418, 2}, {418, 3}}, {{419, 2}}, {{420, 1}, {420, 2}, {420,
   6}}, {{421, 3}}, {{423, 2}, {423, 8}}, {{424, 3}, {424, 8}}, {{426,
    3}, {426, 8}}, {{427, 1}}, {{428, 2}}, {{429, 1}, {429, 3}, {429,
   8}}, {{430, 1}, {430, 3}}, {{431, 2}}, {{432, 1}, {432, 3}}, {{433,
    2}}, {{434, 8}}, {{435, 9}}, {{437, 8}}, {{438, 6}}, {{439,
   1}, {439, 10}}, {{440, 8}}, {{441, 1}}, {{442, 1}}, {{443,
   6}}, {{444, 1}, {444, 3}}, {{445, 2}}, {{446, 8}}, {{447,
   8}}, {{448, 2}}, {{449, 2}}, {{450, 2}, {450, 3}}, {{451,
   8}}, {{453, 2}}, {{454, 1}, {454, 3}}, {{455, 2}, {455, 4}}, {{456,
    1}, {456, 2}, {456, 7}}, {{459, 3}}, {{460, 1}, {460, 4}, {460,
   6}}, {{461, 2}}, {{462, 7}}, {{463, 2}, {463, 4}}, {{465,
   1}}, {{466, 3}, {466, 6}}, {{468, 2}, {468, 3}}, {{469, 1}, {469,
   3}, {469, 4}, {469, 6}}, {{471, 1}, {471, 2}, {471, 6}}, {{472,
   3}, {472, 4}, {472, 9}}, {{473, 2}, {473, 8}}, {{474, 1}, {474,
   2}}, {{475, 2}}, {{477, 1}}, {{478, 2}}, {{481, 2}, {481,
   3}}, {{482, 4}}, {{483, 4}, {483, 7}}, {{484, 1}, {484, 3}}, {{486,
    1}, {486, 2}, {486, 3}, {486, 9}}, {{489, 1}, {489, 3}, {489,
   9}, {489, 10}}, {{490, 2}}, {{492, 1}}, {{493, 6}}, {{494,
   2}, {494, 6}}, {{495, 2}, {495, 9}}, {{496, 1}, {496, 2}}, {{499,
   1}, {499, 2}, {499, 7}}, {{500, 2}}, {{501, 2}}, {{502, 4}}, {{504,
    2}}, {{505, 1}, {505, 3}}, {{506, 2}, {506, 4}}, {{507, 1}, {507,
   4}}, {{508, 6}}, {{510, 1}, {510, 2}, {510, 3}}, {{511, 1}, {511,
   2}}, {{513, 4}}, {{514, 3}, {514, 10}}, {{515, 2}, {515,
   6}}, {{516, 1}, {516, 4}}, {{517, 1}}, {{518, 2}}, {{519, 2}, {519,
    8}}, {{520, 1}, {520, 4}, {520, 6}}, {{521, 4}, {521, 10}}, {{522,
    3}}, {{524, 4}}, {{525, 1}, {525, 6}}, {{526, 1}}, {{528,
   2}, {528, 3}, {528, 7}, {528, 10}}, {{529, 9}}, {{530, 2}}, {{531,
   1}}, {{532, 1}, {532, 3}, {532, 7}}, {{534, 4}}, {{535, 1}, {535,
   3}, {535, 4}}, {{537, 9}}, {{538, 3}, {538, 4}, {538, 7}}, {{539,
   4}}, {{540, 6}, {540, 7}}, {{541, 2}, {541, 3}}, {{542, 4}}, {{543,
    8}}, {{544, 1}, {544, 2}, {544, 6}, {544, 8}, {544, 9}, {544,
   10}}, {{546, 1}, {546, 7}}, {{547, 1}}, {{548, 2}}, {{549,
   1}, {549, 2}}, {{550, 2}}, {{551, 2}, {551, 6}}, {{552, 1}}, {{553,
    3}, {553, 4}}, {{554, 4}, {554, 8}}, {{555, 1}, {555, 4}, {555,
   6}, {555, 8}}, {{556, 4}}, {{558, 3}, {558, 10}}, {{559, 1}, {559,
   6}, {559, 9}}, {{560, 2}}, {{561, 2}, {561, 4}}, {{562, 1}, {562,
   3}, {562, 4}}, {{564, 9}}, {{565, 1}, {565, 8}}, {{566,
   10}}, {{567, 4}, {567, 8}}, {{568, 3}}, {{569, 2}}, {{571,
   2}}, {{572, 4}}, {{573, 2}, {573, 4}}, {{574, 3}, {574, 4}}, {{576,
    1}}, {{577, 1}, {577, 4}}, {{578, 2}}, {{579, 3}}, {{580,
   8}, {580, 10}}, {{581, 2}, {581, 4}}, {{582, 1}, {582, 3}}, {{585,
   6}}, {{586, 1}, {586, 9}, {586, 10}}, {{588, 2}}, {{589,
   2}}, {{590, 4}}, {{591, 1}, {591, 2}}, {{593, 10}}, {{594,
   1}, {594, 2}, {594, 7}, {594, 10}}, {{595, 2}, {595, 8}}, {{596,
   2}}, {{597, 1}}, {{598, 2}, {598, 4}}, {{599, 8}}, {{601, 1}, {601,
    10}}, {{604, 2}}, {{605, 4}}, {{606, 2}}, {{607, 1}}, {{608,
   4}, {608, 10}}, {{609, 1}, {609, 10}}, {{610, 2}, {610, 3}}, {{612,
    1}, {612, 4}, {612, 9}}, {{613, 8}}, {{615, 1}, {615, 3}, {615,
   8}}, {{616, 1}, {616, 2}, {616, 10}}, {{618, 2}}, {{619, 1}, {619,
   4}}, {{623, 4}, {623, 6}}, {{624, 2}, {624, 9}}, {{625, 1}, {625,
   2}, {625, 4}, {625, 9}, {625, 10}}, {{628, 6}}, {{629, 2}, {629,
   4}, {629, 10}}, {{630, 1}, {630, 8}, {630, 9}}, {{631, 3}, {631,
   10}}, {{633, 2}}, {{634, 6}}, {{635, 10}}, {{637, 8}}, {{639,
   1}, {639, 2}, {639, 4}}, {{640, 1}, {640, 2}}, {{641, 8}}, {{642,
   1}, {642, 3}}, {{643, 8}}, {{644, 2}, {644, 4}}, {{645, 1}, {645,
   7}}, {{646, 1}, {646, 2}}, {{648, 2}}, {{649, 1}, {649, 7}, {649,
   10}}, {{651, 1}, {651, 2}, {651, 8}}, {{652, 1}, {652, 4}}, {{654,
   1}, {654, 2}}, {{655, 2}}, {{656, 6}}, {{658, 7}}, {{659, 2}, {659,
    6}, {659, 8}}, {{660, 1}, {660, 3}, {660, 6}}, {{661, 1}, {661,
   3}}, {{663, 6}}, {{664, 1}, {664, 4}}, {{665, 10}}, {{666,
   3}, {666, 4}, {666, 7}}, {{667, 3}}, {{668, 2}, {668, 6}}, {{670,
   2}, {670, 6}, {670, 9}}, {{673, 2}}, {{674, 10}}, {{675,
   8}}, {{676, 2}, {676, 8}, {676, 9}}, {{681, 1}, {681, 10}}, {{683,
   2}}, {{684, 1}, {684, 3}, {684, 4}, {684, 7}}, {{685, 3}}, {{686,
   2}, {686, 10}}, {{687, 1}, {687, 3}}, {{688, 3}, {688, 4}, {688,
   6}, {688, 10}}, {{690, 3}, {690, 8}}, {{691, 1}, {691, 2}}, {{693,
   2}, {693, 10}}, {{694, 3}}, {{695, 2}}, {{697, 3}}, {{699,
   2}}, {{700, 1}}, {{703, 6}}, {{705, 1}, {705, 2}}, {{706, 2}, {706,
    8}}, {{708, 2}}, {{709, 2}}, {{710, 10}}, {{711, 9}}, {{712,
   1}}, {{714, 1}, {714, 4}, {714, 8}}, {{715, 1}, {715, 2}, {715,
   7}}, {{716, 2}}, {{717, 1}, {717, 4}}, {{720, 1}, {720, 2}}, {{721,
    4}, {721, 8}}, {{722, 4}}, {{723, 3}}, {{724, 1}, {724,
   2}}, {{726, 1}, {726, 3}}, {{727, 1}, {727, 4}}, {{728, 2}, {728,
   10}}, {{730, 1}, {730, 10}}, {{731, 4}, {731, 10}}, {{733,
   3}}, {{736, 1}}, {{738, 10}}, {{739, 2}, {739, 3}, {739,
   9}}, {{741, 1}, {741, 4}, {741, 7}}, {{742, 1}, {742, 3}}, {{743,
   2}, {743, 4}}, {{744, 1}}, {{745, 1}}, {{746, 2}}, {{747,
   1}}, {{748, 4}}, {{750, 1}, {750, 2}, {750, 3}}, {{751, 3}, {751,
   8}}, {{753, 2}, {753, 3}}, {{754, 2}}, {{755, 10}}, {{756,
   1}}, {{757, 7}}, {{759, 7}}, {{761, 2}}, {{762, 1}, {762,
   4}}, {{763, 2}, {763, 3}, {763, 4}, {763, 8}}, {{765, 2}}, {{766,
   1}, {766, 6}}, {{768, 10}}, {{769, 2}, {769, 3}, {769, 9}}, {{770,
   6}}, {{771, 6}}, {{772, 1}}, {{774, 6}, {774, 8}}, {{775, 1}, {775,
    6}, {775, 10}}, {{776, 2}, {776, 4}}, {{777, 1}, {777, 3}}, {{778,
    8}}, {{779, 2}, {779, 6}}, {{780, 1}, {780, 2}, {780, 4}}, {{781,
   2}, {781, 8}}, {{783, 3}}, {{784, 1}, {784, 3}}, {{786, 1}, {786,
   2}, {786, 4}}, {{787, 7}}, {{789, 9}}, {{790, 1}, {790, 6}, {790,
   9}}, {{792, 1}, {792, 8}}, {{794, 2}}, {{795, 8}}, {{796, 6}, {796,
    8}}, {{797, 8}}, {{798, 2}, {798, 6}, {798, 7}}, {{799,
   1}}, {{800, 6}, {800, 8}}, {{801, 1}}, {{803, 2}, {803, 4}, {803,
   10}}, {{804, 1}, {804, 2}, {804, 7}}, {{805, 1}}, {{807, 1}, {807,
   4}, {807, 8}}, {{808, 8}}, {{809, 2}}, {{810, 1}, {810, 9}}, {{811,
    1}}, {{813, 6}}, {{814, 1}, {814, 2}, {814, 3}, {814, 4}, {814,
   9}}, {{815, 2}, {815, 8}, {815, 10}}, {{816, 2}, {816, 3}, {816,
   9}}, {{819, 1}, {819, 3}}, {{825, 2}, {825, 10}}, {{828,
   3}}, {{829, 1}, {829, 3}}, {{831, 6}}, {{832, 1}, {832, 3}, {832,
   4}}, {{833, 2}, {833, 8}}, {{834, 1}, {834, 4}, {834, 9}}, {{835,
   1}, {835, 3}}, {{836, 10}}, {{837, 3}}, {{838, 2}}, {{839,
   8}}, {{841, 3}}, {{843, 3}}, {{845, 2}, {845, 4}}, {{846,
   10}}, {{847, 1}}, {{848, 2}, {848, 6}}, {{849, 1}}, {{850,
   1}, {850, 4}, {850, 9}}, {{852, 8}}, {{853, 10}}, {{855,
   1}}, {{856, 2}, {856, 10}}, {{857, 4}}, {{860, 4}}, {{861,
   1}, {861, 3}, {861, 4}}, {{862, 1}}, {{863, 2}}, {{866, 6}}, {{867,
    1}}, {{868, 6}}, {{869, 6}}, {{870, 7}}, {{871, 1}, {871,
   3}, {871, 8}}, {{873, 2}, {873, 4}}, {{874, 1}}, {{875, 6}, {875,
   8}}, {{876, 4}}, {{877, 1}, {877, 7}}, {{879, 3}}, {{880, 1}, {880,
    6}, {880, 10}}, {{881, 2}}, {{882, 3}}, {{883, 4}}, {{884,
   2}}, {{885, 2}}, {{888, 3}}, {{889, 1}, {889, 2}}, {{890, 2}, {890,
    4}, {890, 6}}, {{891, 4}}, {{892, 1}}, {{894, 1}, {894, 6}, {894,
   10}}, {{895, 1}}, {{897, 3}}, {{898, 10}}, {{901, 1}, {901,
   2}, {901, 8}}, {{906, 1}, {906, 2}, {906, 8}}, {{909, 3}, {909,
   8}, {909, 9}}, {{910, 3}}, {{912, 1}}, {{913, 4}, {913, 7}}, {{915,
    2}}, {{916, 1}, {916, 8}}, {{917, 8}}, {{918, 6}}, {{919,
   8}, {919, 9}}, {{921, 2}, {921, 8}}, {{922, 4}}, {{923, 2}}, {{924,
    1}, {924, 4}, {924, 7}}, {{925, 2}, {925, 4}}, {{926, 6}}, {{928,
   6}}, {{930, 2}, {930, 9}}, {{931, 1}, {931, 6}}, {{934, 1}}, {{936,
    1}}, {{937, 1}, {937, 7}}, {{938, 4}, {938, 10}}, {{939, 1}, {939,
    2}, {939, 8}}, {{940, 1}, {940, 3}, {940, 9}, {940, 10}}, {{941,
   2}}, {{943, 3}}, {{944, 2}}, {{945, 1}, {945, 9}}, {{946, 2}, {946,
    4}}, {{948, 3}, {948, 4}}, {{950, 2}, {950, 6}, {950, 8}}, {{951,
   1}, {951, 4}, {951, 8}}, {{952, 4}}, {{953, 4}}, {{954, 1}}, {{955,
    2}, {955, 4}, {955, 7}}, {{956, 2}}, {{957, 1}}, {{960,
   6}}, {{961, 8}}, {{963, 2}}, {{965, 2}}, {{966, 1}, {966,
   2}}, {{967, 1}}, {{968, 2}}, {{969, 3}, {969, 8}}, {{970, 3}, {970,
    6}, {970, 9}}, {{972, 3}}, {{974, 2}}, {{975, 1}}, {{976,
   1}, {976, 2}, {976, 6}}, {{979, 4}, {979, 8}, {979, 9}}, {{980,
   4}}, {{981, 2}, {981, 4}}, {{982, 3}, {982, 8}}, {{984, 2}, {984,
   3}, {984, 6}}, {{987, 1}, {987, 3}}, {{988, 6}}, {{989, 2}, {989,
   10}}, {{990, 1}, {990, 3}}, {{991, 3}}, {{992, 4}}, {{994,
   1}, {994, 2}, {994, 6}}, {{996, 2}, {996, 3}, {996, 4}, {996,
   6}}, {{997, 1}}, {{998, 2}}, {{999, 1}, {999, 9}}, {{1000,
   1}, {1000, 2}}}

So, we can see that using the bounds $1\le\text{n}\le10^3$ and $1\le\text{k}\le10$ we found $1419$ solutions. That number is found by using the following Mathematica-code:
In[2]:=Clear["Global`*"];
\[Alpha] = 10^3;
\[Beta] = 10^1;
f = Total@*Map[Length];
f[ParallelTable[
   If[PrimeQ[n^k + n - 1], {n, k}, Nothing], {n, 1, \[Alpha]}, {k,
    1, \[Beta]}] //. {} -> Nothing]

Out[2]=1419

Extending the bounds to $1\le\text{n}\le10^4$ and $1\le\text{k}\le10^2$ gives $19235$ solutions.

I did a search to find solutions for $\text{n}=107$. I did find a solution for $1\le\text{k}\le5\cdot10^3$ because when $\text{k}=1400$ the number $\text{n}^\text{k}+\text{n}-1$ is prime.
I also searched for solutions of $\text{n}$ and $\text{k}$ such that $\text{k}\ne6\text{m}+5$ (where $\text{m}\in\mathbb{N}$). I did find solutions for $1\le\text{n}\le10^2$ and $1\le\text{k}\le10$:
In[3]:=Clear["Global`*"];
\[Alpha] = 10^2;
\[Beta] = 10^1;
ParallelTable[
  If[TrueQ[PrimeQ[n^k + n - 1] && IntegerQ[(k - 5)/6] == False], {n,
    k}, Nothing], {n, 1, \[Alpha]}, {k, 1, \[Beta]}] //. {} -> Nothing

Out[3]={{{2, 1}, {2, 2}, {2, 4}, {2, 8}}, {{3, 1}, {3, 2}, {3, 3}, {3,
   4}, {3, 8}, {3, 10}}, {{4, 1}, {4, 2}, {4, 3}, {4, 6}, {4, 8}, {4,
   9}}, {{5, 2}, {5, 6}, {5, 10}}, {{6, 1}, {6, 2}, {6, 4}, {6,
   7}, {6, 10}}, {{7, 1}, {7, 3}}, {{8, 2}, {8, 6}, {8, 10}}, {{9,
   1}, {9, 2}, {9, 4}, {9, 7}, {9, 10}}, {{10, 1}, {10, 2}, {10,
   3}, {10, 4}, {10, 9}}, {{11, 2}, {11, 8}}, {{12, 1}, {12,
   4}}, {{13, 2}, {13, 4}, {13, 10}}, {{15, 1}, {15, 2}, {15, 3}, {15,
    9}}, {{16, 1}, {16, 2}, {16, 3}, {16, 4}, {16, 8}, {16,
   10}}, {{17, 4}, {17, 8}}, {{18, 3}, {18, 6}}, {{19, 1}, {19,
   2}}, {{20, 2}, {20, 4}}, {{21, 1}, {21, 2}, {21, 3}}, {{22,
   1}, {22, 7}}, {{23, 4}, {23, 6}}, {{24, 1}, {24, 2}, {24,
   10}}, {{25, 3}, {25, 8}}, {{26, 2}, {26, 4}, {26, 10}}, {{27,
   1}, {27, 3}, {27, 8}}, {{28, 2}, {28, 4}}, {{29, 10}}, {{30,
   1}, {30, 2}, {30, 7}}, {{31, 1}, {31, 2}, {31, 4}, {31, 6}, {31,
   10}}, {{33, 3}, {33, 4}}, {{34, 1}, {34, 6}}, {{35, 2}}, {{36,
   1}, {36, 3}, {36, 6}}, {{37, 1}, {37, 7}}, {{38, 2}}, {{39,
   2}, {39, 3}}, {{40, 1}, {40, 4}, {40, 10}}, {{41, 2}}, {{42,
   1}}, {{43, 3}, {43, 4}}, {{44, 2}, {44, 4}}, {{45, 1}, {45,
   2}}, {{46, 2}, {46, 3}, {46, 8}}, {{48, 2}}, {{49, 1}, {49,
   7}, {49, 9}}, {{50, 2}, {50, 6}, {50, 8}}, {{51, 1}, {51, 3}, {51,
   6}, {51, 10}}, {{52, 1}, {52, 3}}, {{53, 2}, {53, 6}}, {{54,
   1}, {54, 2}, {54, 4}}, {{55, 1}, {55, 2}, {55, 3}}, {{56, 2}, {56,
   6}}, {{57, 1}, {57, 9}}, {{58, 4}}, {{59, 2}, {59, 10}}, {{60,
   2}, {60, 6}}, {{61, 7}, {61, 9}}, {{62, 8}}, {{63, 3}, {63,
   6}}, {{64, 1}, {64, 2}}, {{65, 2}}, {{66, 1}, {66, 2}, {66,
   8}, {66, 9}}, {{68, 2}, {68, 8}}, {{69, 1}, {69, 6}}, {{70,
   1}, {70, 2}, {70, 7}, {70, 9}}, {{72, 4}}, {{73, 3}, {73,
   6}}, {{74, 8}}, {{75, 1}, {75, 6}}, {{76, 1}, {76, 2}, {76,
   6}, {76, 10}}, {{77, 4}, {77, 8}}, {{78, 3}}, {{79, 1}, {79,
   9}}, {{81, 3}}, {{82, 1}}, {{83, 2}, {83, 6}}, {{84, 1}, {84,
   8}}, {{85, 2}}, {{86, 2}}, {{87, 1}, {87, 3}, {87, 8}}, {{88,
   8}}, {{89, 2}, {89, 10}}, {{90, 1}, {90, 10}}, {{91, 1}, {91,
   6}}, {{92, 4}}, {{93, 2}, {93, 3}, {93, 4}, {93, 7}}, {{94,
   2}, {94, 3}}, {{96, 1}, {96, 2}, {96, 3}, {96, 6}, {96, 10}}, {{97,
    1}}, {{98, 4}}, {{99, 1}, {99, 10}}, {{100, 1}, {100, 2}, {100,
   3}, {100, 7}, {100, 8}}}


TITLE: When is a quotient map open?
QUESTION [52 upvotes]: Quotient map from $X$ to $Y$ is continuous and surjective with a property : $f^{-1}(U)$ is open in $X$ iff $U$ is open in $Y$.
But when it is open map? What condition need?

REPLY [3 votes]: Let us agree that $f : X \to Y$ denotes a continuous surjection.
$f : X \to Y$ is called a quotient map if it satisfies the following condition:
$$U \subset Y \text{ is open } \Longleftrightarrow f^{-1}(U) \subset X \text{ is open.}  \tag{Q}$$
The $\Longrightarrow$ part means nothing else than that $f$ is continuous which is redundant because $f$ was assumed to be continuous. We can therefore replace (Q) by
$$f^{-1}(U) \subset X \text{ is open } \Longrightarrow U \subset Y \text{ is open.}   \tag{Q'}$$
We have the following well-known
Lemma. $f$ is a quotient map if and only it satisfies
$$f^{-1}(C) \subset X \text{ is closed } \Longrightarrow C \subset Y \text{ is closed.}   \tag{Q''}$$
This gives the well-known
Lemma. If $f$ is an open or a closed map, then $f$ is a quotient map.
Proof. Let  $f$ be an open map. If $f^{-1}(U)$ is open, then $f(f^{-1}(U))) = U$ is open. Thus $f$ is a quotient map. Note that the equation $f(f^{-1}(U))) = U$ requires surjectivity.
The case that $f$ is a closed map is treated similarly.
We have seen that being a quotient map is weaker than  being an open map. Of course we get
Lemma. A quotient map $f$ is an open map if and only if
$$U \subset X \text{ is open } \Longrightarrow f^{-1}(f(U)) \subset X \text{ is open.} \tag{O}$$
Proof. If $f$ is an open map, then $f(U)$ is open and thus $f^{-1}(f(U))$ is open. For the converse observe that $f^{-1}(f(U))$ open implies $f(U)$ open because $f$ is a quotient map.
There are certainly cases where the above lemma is very useful, but it depends on the concrete situation whether it is easier to verify condition (O) then to verify directly that $f$ is open.
The benefit of (O) is that we do not need to know the topology on $Y$ explicitly. This is particularly useful if we are given a surjection $f : X \to Y$ from a space $X$ to a set $Y$ and endow $Y$ with the quotient topology. If we are given a continuous surjection $f :X \to Y$ from a space $X$ to a space $Y$, it is probably easier to show directly that $f$ is an open map than proving first that $f$ is a quotient map and then verifying (O).


TITLE: Construct a triangle with $m_b = a$ and one of angles
QUESTION [0 upvotes]: I have a question for construct a triangle with know $m_b = a$ and one of angles. In this question, There may be a possibility of drawing mode or under certain circumstances be able to draw it. (E.g angle). This question wants us to find those conditions.
1) If we know $m_b = a$ and $\angle C$
I solved this question. It's my pictures.

We can see only condition for this question is $\angle C$. If It's more than 90, Then we can't draw it.
2) If we know $m_b = a$ and $\angle B$
Thanks Mos Black for answer these question. It's just shape of that.

3) If we know $m_b = a$ and $\angle A$
for two above questions, I work but I couldn't find anything. because of question, I don't know I can't do it or it is not possible to do!
Is it possible to help me?
I'm sorry for bad English too.

REPLY [1 votes]: For 1) For the constrution of the triangle ABC given $m_b=a$ and $\angle C$ the necessary and sufficient condition of the constrution to be possible is that $\angle C <90$.
2) is always possible. This can be verified from the following:
$m_b=a$ gives using appollinius theorem $c^2-\frac{b^2}{2}=a^2$........(1)
And from cosince rule we have $\frac{c^2+a^2-b^2}{2ac}=t=\cos B$......(2)
Now eliminating $b^2$ from (1) and (2) we get
$c^2-2act-3a^2=0$ which always has  a positive root in $c$.
So, its always possible.
for 2) a geometric construction is as follows:
Construct a line segment of length $a$ and constuct $\angle CBK$.
Now, from $C$ draw a line $l_1$ parallel to $BK$.
Extend $BC$ to $D$ such that $CD=BC$.
With $B$ as the center draw a circle of radius $BD$ and let it cut $l_1$ at $E$.
Draw line parallel to $BC$ passing through $E$ and let it cut $BK$ at $A$.
You have your triangle $ABC$

REPLY [0 votes]: I'm not sure if I fully understand your problem, but I'll offer some information which will hopefully help you.
Two triangles can be proven congruent if you can show that one of the four following conditions is met:

All three sides are the same.
Two sides and their included angle are the same.
Two angles and their included side are the same.
Two angles and their non-included side are the same.

The reason I say this is because if you know the information that satisfies one of the above 4 situations, then you have a defined triangle (since each of the possibilities are congruent to each other). You are given only a side and an angle (correct me if I'm wrong), so none of the 4 conditions can be met, so there are multiple possible triangles (either 2 or infinity).


TITLE: The norm of a fundamental unit and the narrow Hilbert class field
QUESTION [4 upvotes]: Let $K$ be a real quadratic number field and $\epsilon$ be a fundamental unit. Then apparently the narrow Hilbert class field of $K$ equals the Hilbert class field if and only if $N_{K/\Bbb Q}(\epsilon)=-1$. Why is this the case?
Follow-up question: Does this also hold for complex cubic fields?

REPLY [4 votes]: In the totally real case, the narrow Hilbert class field equals the Hilbert class field exactly when every totally positive unit is a square.
For proof, use Dirichlet's Unit Theorem so see $U/U^2$ is isomorphic to $(\mathbb{Z}/2)^n$. Then apply Theorem V.1.7 in https://www.jmilne.org/math/CourseNotes/CFT.pdf with conductor the product of all infinite places.


TITLE: What is length of period of fibonacci number mod 1000033
QUESTION [1 upvotes]: Can some explain me how the period of Fibonacci mod $1000033$ is $4684$.
As we know if $n$ mod $5$ is $2$
 or $3$ then period is $2n + 2$ so the period should me $2\times1000033 + 2$
 but why it is $4684$.
Thanks.

REPLY [1 votes]: The period is actually $ \pi(n) = k\cdot\text{ord}_n(F_{k+1}) $ where k is the smallest positive integer such that $n\mid F_k$.
So first find the first Fibonacci number where 1000033 divides $F_k$, This happens at $F _{1171}$, so $F_{1171}/1000033$ does not give any remainder when dividing. Every fibonacci number before that does. Thus $k=1171$.
The second part: $\text{ord}_n(F_{k+1})$ is the multiplicative order. You can look that up yourself, but for fibonacci numbers its either 1, 2, or 4. In this case its 4.
(Wolfram Alpha proof: https://www.wolframalpha.com/input/?i=multiplicative+order%28fib%281172%29%2C1000033%29)
So: $1171*4=4684$
I think you are talking about $2*n+2$ with primes. That refers to the fact that all primes "land" on that, but there period can be shorter, meaning $F_{2*1000033+2}\equiv 0 \mod 1000033$. Thus for some primes $F_{2n+2}\equiv 0 \mod 1000033$.
"For p≡±1(mod5) and ±2(mod5) the periods for Fibonacci sequences modulo p divide p−1 and 2p+2 respectively."


TITLE: On the existence of a superquadratic map $\beta$ in a paper by DiPerna & Lions.
QUESTION [0 upvotes]: I am reading the paper by DiPerna & Lions on Global Weak Solutions of Vlasov-Maxwell Systems (1989).
On the 9th page of the article, the authors say that for a sequence of initial conditions $f^n(0)$ converging in $L^2(\mathbb R^3 \times \mathbb R^3)$, extracting sub-sequences if necessary there exists a superquadratic map $\beta$ such that $\beta(f^n(0))$ is uniformly bounded in $L^1(\mathbb R^3\times \mathbb R^3)$. This kind of argument is repeated later on in the article. I am also posting an image of the paragraph in discussion 1.
Can someone explain to me how the existence of this superquadratic $\beta$ is justified?

REPLY [0 votes]: I found a nice reference for a proof of this statement, but it is in German. If someone is interested in the proof, feel free to contact me.


TITLE: How do I generate regular expression from this deterministic finite state automaton?
QUESTION [1 upvotes]: I want to create a regular expression from the following deterministic finite automaton:
"abb" substring search

How do I generate regexp from above dfa and what are the steps for doing so?
Deterministic finite automaton generated from snippet:
{ w in {a,b}* | w contains the substring abb }

REPLY [0 votes]: There are several methods for finding a regular expressions for the language accepted by a finite automaton. In this case, though, you don't need them. If you have $\{w\in\{a,b\}^*\mid w\text{ contains }abb\}$, then any string in that language is just
$$
<something>abb<something>
$$
and the regular expression for these strings is obviously
$$
(a\cup b)^*abb(a\cup b)^*
$$
[or however you're used to writing regexps: $(a\mid b)^*abb(a\mid b)^*$, or $(a+ b)^*abb(a+ b)^*$].


TITLE: Proofs of the Weitzenbock inequality: $a^2+b^2+c^2\geq 4 \sqrt{3}\cdot(\text{area of }\triangle ABC)$
QUESTION [15 upvotes]: I'm collecting proofs for Weitzenbock's inequality, once featured as a question in IMO 1961. I made three proofs for this. See these proofs below. (Whoever has a more cool proof, please share.)

Weitzenbock's inequality. Let $a$, $b$, $c$ be the sides of the triangle, and let $A$ be its area. Then:
$$a^{2}+b^{2}+c^{2}\;\geq\;4\sqrt{3}\;A$$

Proof 1
Let $R$ the circunradius. Suppose, by contradiction, that:
\begin{equation}
\frac{1}{a}+\frac{1}{b}+\frac{1}{c}<\frac{3}{R\sqrt{3}} \tag{1}
\end{equation}
Using that:
\begin{equation}
a+b+c\leq 3R\sqrt{3} \tag{2}
\end{equation}
Multiplying (1) e (2):
$$(a+b+c)\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right)<9$$
What is absurd, this can be seen using the inequality that relates the arithmetic mean to the harmonic mean, or by the inequality of Cauchy-Schwarz. From where we conclude:
\begin{equation}
\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\geq\frac{3}{R\sqrt{3}}
\end{equation}
Using $\displaystyle A=\frac{abc}{4R}$, we get:
$$ab+ac+bc\geq \frac{\sqrt{3}abc}{R}$$
$$ab+ac+bc\geq 4A\sqrt{3}$$
This result follows using that $\displaystyle a^{2}+b^{2}+c^{2}\geq ab+bc+ac$

Proof 2
By Heron we get:
\begin{equation*}
    a^2+b^2+c^2 \geq 4\sqrt{3} \sqrt{S(S-a)(S-b)(S-c)}
\end{equation*}
Multiplying both sides of the inequality above by $\displaystyle \sqrt{\left(\frac{a+b+c}{2abc}\right)^2}=\sqrt{\left(\frac{S}{abc}\right)^2}$, :
\begin{equation*}
    \left(a^2+b^2+c^2\right)\left(\frac{a+b+c}{2abc}\right) \geq 4\sqrt{3} \sqrt{\frac{S(S-a)}{bc}\frac{S(S-b)}{ac}\frac{S(S-c)}{ab}}
\end{equation*}
By the law of cosine and law of sine we have:
\begin{equation*}
    \left(a^2+b^2+c^2\right)\left(\frac{a+b+c}{2abc}\right) \geq 4\sqrt{3} \cos\frac{\alpha}{2}\cos\frac{\beta}{2}\cos\frac{\gamma}{2}
\end{equation*}
\begin{equation*}
    \left(\frac{a^2}{bc}+\frac{a}{b}+\frac{a}{c}\right)+ \left(\frac{b^2}{ac}+\frac{b}{a}+\frac{b}{c}\right)+ \left(\frac{c^2}{ab}+\frac{c}{a}+\frac{c}{b}\right) \geq 8\sqrt{3} \cos\frac{\alpha}{2}\cos\frac{\beta}{2}\cos\frac{\gamma}{2}
\end{equation*}
\begin{equation*}
      \left(\frac{sen^2\alpha}{sen\beta sen\gamma}+\frac{sen\alpha}{sen\beta}+\frac{sen\alpha}{sen\gamma}\right)+\left(\frac{sen^2\beta}{sen\alpha sen\gamma}+\frac{sen\beta}{sen\alpha}+\frac{sen\beta}{sen\gamma}\right)+\left(\frac{sen^2\gamma}{sen\alpha sen\beta}+\frac{sen\gamma}{sen\alpha}+\frac{sen\gamma}{sen\beta}\right)  \geq 8\sqrt{3} \cos\frac{\alpha}{2}\cos\frac{\beta}{2}\cos\frac{\gamma}{2}
\end{equation*}
\begin{equation*}
      (sen\alpha+sen\beta+sen\gamma)\left(\frac{sen\alpha}{sen\beta sen\gamma}+\frac{sen\beta}{sen\alpha sen\gamma}+\frac{sen\gamma}{sen\alpha sen\beta}\right) \geq 8\sqrt{3} \cos\frac{\alpha}{2}\cos\frac{\beta}{2}\cos\frac{\gamma}{2}
\end{equation*}
\begin{equation*}
      \cot\alpha+\cot\beta+\cot\gamma\geq \sqrt{3}
 \end{equation*}
And this inequality follows from the Jensen inequality.

Proof 3
Let $\displaystyle R$ the circunradius, $\displaystyle \alpha, \beta, \gamma$ the opposite acute angles to the sides of $\displaystyle a, b, c$, so:
$\\ \\ \displaystyle a^2+b^2-c^2=\frac{4Rabc(a^2+b^2-c^2)}{4Rabc}=\frac{4AR(a^2+b^2-c^2)}{abc}=4A\times\frac{2R}{c}\times\frac{a^2+b^2-c^2}{2ab}=4Acot\gamma=4A\sqrt{cot^2\gamma}=4A\sqrt{csc^2\gamma-1}=4A\sqrt{\frac{4R^2}{c^2}-1}=4A\sqrt{\frac{4a^2b^2R^2}{a^2b^2c^2}-1}=4A\sqrt{\frac{a^2b^2}{4\left(\frac{abc}{4R}\right)^2}-1}=4A\sqrt{\frac{a^2b^2}{4A^2}-1}=2\sqrt{4A^2\left(\frac{a^2b^2}{4A^2}-1\right)}=2\sqrt{a^2b^2-4A^2}\Rightarrow a^2+b^2-c^2=2\sqrt{a^2b^2-4A^2}\\ \\$
By symmetry, we get:
\begin{equation*}
 2\sqrt{a^2b^2-4A^2}=a^2+b^2-c^2
\end{equation*}
\begin{equation*}
 2\sqrt{a^2c^2-4A^2}=a^2+c^2-b^2
\end{equation*}
\begin{equation*}
2\sqrt{b^2c^2-4A^2}=b^2+c^2-a^2
\end{equation*}
Multiplying these equalities two by two we will have:
\begin{equation*}
 4\sqrt{a^2b^2-4A^2}\sqrt{b^2c^2-4A^2}=(a^2+b^2-c^2)(b^2+c^2-a^2)
\end{equation*}
\begin{equation*}
 4\sqrt{a^2c^2-4A^2}\sqrt{b^2c^2-4A^2}=(a^2+c^2-b^2)(b^2+c^2-a^2)
\end{equation*}
\begin{equation*}
4\sqrt{a^2b^2-4A^2}\sqrt{a^2c^2-4A^2}=(a^2+c^2-b^2)(a^2+b^2-c^2)
\end{equation*}
We know that $\displaystyle m+n\geq 2\sqrt{mn}$, it folows that:
\begin{equation*}
 2(a^2b^2-4A^2+b^2c^2-4A^2)\geq (a^2+b^2-c^2)(b^2+c^2-a^2)
\end{equation*}
\begin{equation*}
 2(a^2c^2-4A^2+b^2c^2-4A^2)\geq(a^2+c^2-b^2)(b^2+c^2-a^2)
\end{equation*}
\begin{equation*}
2(a^2b^2-4A^2+a^2c^2-4A^2)\geq(a^2+c^2-b^2)(a^2+b^2-c^2)
\end{equation*}
Adding all the above inequalities we will have:
\begin{equation*}
4a^2b^2+4b^2c^2+4a^2c^2-16\times 3 A^2\geq (a^2+b^2-c^2)(b^2+c^2-a^2)+(a^2+c^2-b^2)(b^2+c^2-a^2)+(a^2+c^2-b^2)(b^2+c^2-a^2)
\end{equation*}
Let $ b^2+c^2-a^2=x,y=a^2+c^2-b^2,z=a^2+b^2-c^2$.Observe that
$$ 2a^2=(a^2+c^2-b^2)+(a^2+b^2-c^2)=y+z$$
$$ 2b^2=(a^2+b^2-c^2)+(b^2+c^2-a^2)=x+z$$
$$ 2c^2=(a^2+c^2-b^2)+(b^2+c^2-a^2)=x+y$$
We get:
$$ 4a^2b^2=(y+z)(x+z)$$
$$ 4a^2c^2=(y+z)(x+y)$$
$$ 4b^2c^2=(x+z)(x+y)$$
Replacing in the inequality above, we have:
\begin{equation*}
(x+z)(x+y)+(y+z)(x+y)+(y+z)(x+z)-16\times 3 A^2\geq xy+xz+yz
\end{equation*}
\begin{equation*}
x^2+y^2+z^2+2xy+2xz+2yz-16\times 3 A^2\geq 0
\end{equation*}
\begin{equation*}
(x+y+z)^2-16\times 3 A^2\geq 0
\end{equation*}
\begin{equation*}
x+y+z\geq 4\sqrt{3}A
\end{equation*}
Done

REPLY [4 votes]: I think that this answer hasn't been posted yet, so here it goes.
In virtue of the Law of Cosines and the fact that $2A=bc·\sin\alpha$

$$a^2+b^2+c^2\geq 4\sqrt3 A\iff b^2+c^2-2bc·\cos\alpha+b^2+c^2\geq 4·\sqrt3·\frac{bc·\sin\alpha}{2}$$ $$\iff b^2+c^2\geq bc(\sqrt3 \sin\alpha+\cos\alpha)$$

Now observe that for $f(\alpha)=\sqrt3 \sin\alpha+\cos\alpha$ for $\alpha\in(0, \pi)$ you have $$f'(\alpha)=\sqrt3 \cos\alpha -\sin\alpha$$
Thus $$f'(\alpha)=0\iff \sqrt3\cos\alpha=\sin\alpha\iff \sqrt3=\tan\alpha\iff \alpha=\frac{\pi}{3}$$ And since $f''(\alpha)=-\sqrt3\sin\alpha-\cos\alpha<0$ for $\alpha\in(0, \pi)$ $$f(\alpha)_{max}\text{ is achived for } \alpha\in(0, \pi)\text{ when } \alpha=\frac{\pi}{3}$$ Hence $$\sqrt3 \sin\alpha+\cos\alpha=f(\alpha)\leq\sqrt3 \sin\frac{\pi}{3}+\cos\frac{\pi}{3}=2$$
Therefore $$2bc\geq bc(\sqrt3 \sin\alpha+\cos\alpha)$$ And since the inequality $b^2+c^2\geq 2bc$ is almost trivial, we're done!
Remark
Observe that this proof uses the most basic trigonometry and calculus principles


TITLE: What is the unit of this "Rate of Change"?
QUESTION [1 upvotes]: This is the plot of the function $f(x) = 0.9x$.
So, the rate of change of $y$ with respect to $x$ is $0.9$.
My question is, what is the unit of this Rate of Change?
$0.9$ per $x$?

REPLY [1 votes]: Well, it really depends on context. In a very pure sense, the slope does not have units in this context. In a more vernacular sense, it's common to have things like
$$y=\text{# of meters travelled}$$
$$x=\text{# of seconds passed}$$
Then write $y=2x$ as a relationship. Then, the units of slope would be $\text{meters/second}$, meaning that two meters pass (on the $y$-axis) for every one second on the $x$-axis. So, the units here are the units of the $y$-axis divided by those of the $x$-axis.
However, it's worth noting that this relationship might be better written as
$$f(x\text{ seconds})=2x\text{ meters}$$
where you recognize that the function $f$ takes in a duration and spits out a length - and that the units are not an intrinsic quality of the function. In this sense, you could justifiably write for the same function that
$$f(x'\text{ minutes})=120x'\text{ meters}.$$
An equivalent way to write this function is as follows:
$$f(t)=(2\text{ meters/second})\cdot t$$
where you note that if you plug in $x\text{ seconds}$ for $t$, you get $2x\text{ meters}$. This last point of view shows that the slope is just the coefficient multiplied by the input - and it is very often desirable to treat these slopes as intrinsically having units which are part of the value, not an interpretation thereof.

In an abstract setting (or a setting where the input and output are both distances or both times or generally both the same), the slope does not have units. It is just $0.9$.


TITLE: Scheme of finite Krull dimension, with a closed point, whose closed subsets are all comparable
QUESTION [0 upvotes]: Let $X$ be a scheme which contains a closed point and also assume that for every two closed subsets $Y_1$ and $Y_2$ of $X$, we have either $Y_1 \subseteq Y_2$ or $Y_2 \subseteq Y_1$. Also assume that $X$ has finite Krull dimension. Then, is it true that $X$ is affine ?
My thoughts: Since the closed subsets of $X$ are comparable, so $X$ has exactly one closed point, say $x \in X$ and also every non-empty closed subset contains $x$ . Hence for any abelian sheaf $\mathcal F$ on $X$, we have $\mathcal F_x =\mathcal F(X)$. Since taking stalks of sheaves is exact, we get $H^j(X, \mathcal F)=0, \forall j>0$ for any abelian sheaf $\mathcal F$ on $X$. However , since I'm not assuming the scheme to be quasi-compact , I cannot quite apply Serre's criteria now.
Please help.

REPLY [2 votes]: The assumption of finite Krull dimension is unnecessary.  Let $x\in X$ be a closed point and note that for any $y\in X$, we must have $\{x\}\subseteq \overline{\{y\}}$.  This means that any open set containing $x$ must contain $y$, so the only open set containing $x$ is all of $X$.  Since there is some affine open set containing $x$, this means $X$ itself is affine.


TITLE: ON types of squarefree numbers and comparing their amounts < a given integer N.
QUESTION [2 upvotes]: Let an m-prime be a square-free number with m prime divisors. Also let the number of t-primes < N be represented as #(t-prime){N} (t and N being positive elements of integers). Is the following true? Given a fixed integer N ; #(2-prime){N} >= #(3-prime){N} >= #(4-primes){N} >=....etc.??

REPLY [1 votes]: The statement is false -- although it holds for quite some time.
If $c_t(n)$ denotes the number of $t$-primes smaller than or equal to $n$, we have $$c_2(1279789)<c_3(1279789)$$
and also
$$c_1(58)<c_2(58)$$
(the latter wasn't part of the conjectured series of inequalities, though).
Based on a quick non-rigorous reasoning (which could be wrong, of course), it seems that neither of the the inequalities can hold indefinitely: apparently, the count of $(t+1)$-primes starts as smaller than the count of $t$-primes, but it eventually catches up and overtakes the other (and this "eventually" happens at different point for each inequality). In order to see why, consider the estimate given in Wikipedia:
$$\pi_t(n)\sim \frac{n}{\log n} \frac{\left(\log \log n\right)^{t-1}}{(t-1)!}$$ Although the result in Wikipedia is stated for numbers with $t$ prime factors when counting multiplicity, it should also be true for numbers with $t$ distinct prime factors and also for square-free numbers with $t$ distinct prime factors; which is precisely our $c_t(n)$. Since the expression on right-hand side grows asymptotically faster when $t$ is greater (higher exponent at $\log \log n$), it eventually outgrows the one with smaller $t$. However, the speed of growth is proportional to double logarithm of $n$, so it might be a very slow process...