text:
\iffalse
\section{Missing Proofs for Section \ref{sec:structure}}\label{appstructure}

Even though the results in this section hold for any direction $\mathbf{w}\in \mathbb{R}^n$, we will prove the statements for $\mathbf{w} = \nabla f(\x_0)$ for readability in the context of the paper.

\noindent
\textcolor{blue}{\textbf{Properties of normal cones}}

\noindent
\textbf{there exists a small neighborhood in which normal cone is same.}
\begin{lemma} Consider any $x\in P$. There exists $\delta>0$ such that $N_P(x) = N_P(y)$ for all $y \in B_F(x, \delta)$, where $F$ is the minimal face of $x \in P$.
\end{lemma}

\noindent
\textbf{moving in a linear segment until feasibility of P can only add a constraint.}
\begin{lemma} Consider any $x\in P$. Let $y = x+ \lambda d$ for some $d \in \mathbb{R}^n$ and maximum feasible movement $\delta$. Then, $N_P(x+\lambda d - \epsilon) \subset N_P(x + \lambda d)$.
\end{lemma}

\noindent
\textbf{moving away from a point can only drop a constraint in its neighborhood}
\begin{lemma}
Let $P \subseteq \mathbb{R}^n$ be a polytope defined using $m$ facet inequalities (e.g., as in \eqref{polytope}). Let $\x_0\in P$ and we are given $d \in \mathbb{R}^n$. There exists a scalar $\delta > 0$ such that $N_P(x+\lambda d) = N_P(x+\lambda^\prime d) \subseteq N_P(\x_0)$, for all $0<\lambda<\lambda^\prime < \delta$.
\end{lemma}

\noindent
\textcolor{blue}{\textbf{Properties about the projections curve}}\\

\noindent
\textbf{if in normal cone, stop}
\basecase*

\noindent
\textbf{if normal cone same, then linear}
\begin{theorem}
Let $P \subseteq \mathbb{R}^n$ be a polytope defined using $m$ facet inequalities (e.g., as in \eqref{polytope}). Let $\x_0\in P$ and we are given $\nabla f(\x_0) \in \mathbb{R}^n$. Let $g(\lambda) = \Pi_P(x_0 - \lambda \nabla f(\x_0))$ be the parametric projections curve. Then, if $N_P(g(\lambda)) = N_P(g(\lambda^\prime))$ for some $\lambda < \lambda^\prime$, then the curve between $g(\lambda)$ and $g(\lambda^\prime)$ is linear, i.e., $g(\delta\lambda + (1-\delta)\lambda^\prime) = \delta g(\lambda) + (1-\delta)g(\lambda^\prime)$, where $\delta\in[0,1]$.
\end{theorem}

\noindent
\textbf{projections curve is piecewise linear}

\begin{lemma}
Let $P \subseteq \mathbb{R}^n$ be a polytope. Let $\x_{0} \in P$ and $d \in \mathbb{R}^n$ be given. Further, let $g(\lambda) = \Pi_{P}(\x_0 -\lambda \nabla f(\x_0))$ denote the projections curve. Fix an arbitrary $\lambda$. Then, $\lim_{\epsilon \rightarrow 0} g(\lambda - \epsilon) = \lim_{\epsilon \rightarrow 0} g(\lambda + \epsilon)$. Moreover, there exists $\delta>0$: $g(\gamma \lambda + (1-\gamma) (\lambda - \delta)) = \gamma g(\lambda) + (1-\gamma)g(\lambda-\delta)$. And similarly for $g(\gamma \lambda + (1-\gamma) (\lambda + \delta)) = \gamma g(\lambda) + (1-\gamma)g(\lambda + \delta)$ for all $\gamma \in [0,1]$.
\end{lemma}

\noindent
\textbf{\color{blue} define breakpoints.}
where the left and right directions are different.

WE'VE SHOWN SO FAR: curve is piecewise linear, breakpoints, walk from a point you could drop constraints, when you reach a tight constraints then grow the normal cone.\\

\noindent
\textbf{projections curve does not intersect itself.}
corollary from normal cones.

\noindent
\textcolor{blue}{\textbf{What are the directions?}}

\textbf{from the starting point, walk in shadow}
\begin{theorem}
Let $P \subseteq \mathbb{R}^n$ be a polytope defined using $m$ facet inequalities (e.g., as in \eqref{polytope}). Let $\x_0\in P$ and we are given $\nabla f(\x_0) \in \mathbb{R}^n$. Let $g(\lambda) = \Pi_P(\x_0 - \lambda \nabla f(\x_0))$ be the parametric projections curve. Then, the projections curve is given by $g(\lambda) = \x_0 +  \lambda \bd_{\x_0}^\Pi, \text{ for all } \lambda \in [0,\lambda_1^-]$, where $\lambda_1^{-} = \max\{\lambda \mid \x_0 + \lambda \bd_{\x_0}^\Pi \in P\}$.
\end{theorem}
\fi

\section{Missing Proofs for Section \ref{sec:structure}}\label{appstructure}

\subsection{Missing Proofs for Section \ref{sec:piecewise}} \label{app:piecewise proofs}

\subsubsection{Proof of Lemma \ref{equivalence}}
\equivalence*

\begin{proof}
Fix $\lambda,\lambda^\prime \geq 0$ arbitrarily such that $\lambda^\prime > \lambda$. we will show that $\delta g(\lambda) + (1 - \delta) g(\lambda^\prime)$ satisfies the first-order optimality condition for $g(\delta \lambda + (1 - \delta) \lambda^\prime)$. For brevity, let $I$ and $J$ (resp. $\tilde{I}$ and $\tilde{J}$) denote the index set of active and inactive constraints at $g(\lambda)$ (resp. $g(\lambda^\prime)$). Note that since $N_P(g(\lambda^\prime)) = N_P(g(\lambda))$ we have $I = \tilde{I}$ and $J =\tilde{J}$. The first-order optimality of $g(\lambda)$ and $g(\lambda^\prime)$ yields
\begin{align}
    \x_0 - \lambda \nabla f(\x_0) - g(\lambda) &= \mb{\mu}^\top \mathbf{A}_I \in N_P(g(\lambda))  \label{eq1 - lemma2} &\text{for some $\mb{\mu} \in \mathbb{R}^{|I|}_+$}\\
    \x_0 - \lambda^\prime \nabla f(\x_0) - g(\lambda^\prime) &=  \tilde{\mb{\mu}}^\top \mathbf{A}_{\tilde{I}} = \tilde{\mb{\mu}}^\top \mathbf{A}_I \in  N_P(g(\lambda)) &\text{for some $\tilde{\mb{\mu}} \in \mathbb{R}^{|{I}|}_+$} \label{eq2 - lemma2}.
\end{align}
Thus, by aggregating equations \eqref{eq1 - lemma2} and \eqref{eq2 - lemma2} with weights $\delta$ and $(1 - \delta)$ respectively, we can conclude:
\begin{equation}\label{eq3 - lemma2}
    \x_0 - (\delta \lambda + (1 - \delta)\lambda^\prime)\nabla f(\x_0) - (\delta g(\lambda) + (1 - \delta)g(\lambda^\prime)) = (\delta \mb{\mu} + (1- \delta) \tilde{\mb{\mu}})^\top \mathbf{A}_{{I}} \in N_P(g(\lambda)).
\end{equation}
We now claim that
\begin{equation}\label{eq4 - lemma2}
    N_P(g(\lambda)) = N_P(\delta g(\lambda) + (1 - \delta) g(\lambda^\prime)).
\end{equation}
Assuming \eqref{eq4 - lemma2} holds, we can equivalently write  \eqref{eq3 - lemma2} as
\begin{equation*}
    \x_0 - (\delta \lambda + (1 - \delta)\lambda^\prime)\nabla f(\x_0) - (\delta g(\lambda) + (1 - \delta)g(\lambda^\prime)) \in N_P(\delta g(\lambda) + (1 - \delta) g(\lambda^\prime)),
\end{equation*}
so that $\delta g(\lambda) + (1 - \delta) g(\lambda^\prime)$ satisfies the optimality condition for $g(\delta \lambda + (1 - \delta) \lambda^\prime)$, as claimed.

We now prove the claim in \eqref{eq4 - lemma2}. Since $I = \tilde{I}$ and $J =\tilde{J}$, we have
\begin{align*}
    \mathbf{A}_{I} (\delta g(\lambda) + (1 - \delta)g(\lambda^\prime)) &= \delta \mathbf{A}_{I}g(\lambda) +  (1 - \delta) \mathbf{A}_{I}g(\lambda^\prime) = \mathbf{b}_{I}\\
    \mathbf{A}_{J} (\delta g(\lambda) + (1 - \delta)g(\lambda^\prime)) &= \delta \mathbf{A}_{J}g(\lambda) +  (1 - \delta) \mathbf{A}_{J}g(\lambda^\prime) < \mathbf{b}_{J}
\end{align*}
This implies that $I = I(\delta g(\lambda) + (1 - \delta)g(\lambda^\prime))$ and $J = J(\delta g(\lambda) + (1 - \delta)g(\lambda^\prime))$, which proves \eqref{eq4 - lemma2} and concludes the proof.
 \qed \end{proof}

\subsubsection{Proof of Lemma \ref{continuous and piecewise}}

\continuousandpiecewise*

\begin{proof} Assume that $\nabla f(\x_0) \neq \mathbf{0}$, since otherwise the result follows trivially. We now prove the result in the next two claims:
\begin{itemize}
    \item[$(a)$] \textit{Continuity of the projections curve.} Fix an arbitrary $\lambda > 0$. We first show that $\lim_{\lambda^\prime \to \lambda^+}g(\lambda^\prime) = \lim_{\lambda^\prime \to \lambda^-} g(\lambda^\prime) = g(\lambda)$. Let $\epsilon > 0$ be arbitrary. Then, by non-expansiveness of the Euclidean projection operator over convex sets (see Section \ref{sec: prelims}) \eqref{nonexpansive}, we know that
\begin{equation*}\label{nonexpansive}
\begin{aligned}
     \|g(\lambda) - g(\lambda + \epsilon)\| &\leq \|(\x_0 - \lambda \nabla f(\x_0)) - (\x_0 - (\lambda + \epsilon) \nabla f(\x_0)) \|
     = |\epsilon| \|\nabla f(\x_0)\|.
\end{aligned}
\end{equation*}
Thus, whenever $ |\lambda^\prime - \lambda| < \delta$, we have $\|g(\lambda^\prime) - g(\lambda)\| \leq |\lambda^\prime - \lambda| \| \nabla f(\x_0)\| < \delta \| \nabla f(\x_0)\|$. Thus, by choosing $\delta = \frac{\epsilon}{\|\nabla f(\x_0)\|}$, we have $\|g(\lambda^\prime) - g(\lambda)\| < \epsilon$. This implies that:
\begin{itemize}
    \item For every $\epsilon > 0$, there exists  $\delta > 0$ such that if $0 < \lambda -\lambda^\prime < \delta $, then $\| g(\lambda^\prime) - g(\lambda)\| <\epsilon$. Thus, we have $\lim_{\lambda^\prime \to \lambda^-} g(\lambda^\prime) = g(\lambda)$
    \item For every  $\epsilon > 0$ there exists  $\delta > 0$ such that if $0 < \lambda^\prime - \lambda < \delta$, then $\| g(\lambda^\prime) - g(\lambda)\| <\epsilon$. Thus, we have  $\lim_{\lambda^\prime \to \lambda^+}g(\lambda^\prime) = g(\lambda)$.
\end{itemize}
This establishes the continuity of the projections curve.
\item[$(b)$] \textit{Piecewise linearity of the projections curve.} Fix an arbitrary $\lambda_0 > 0$ and define $\y_0 := g(\lambda_0)$. We now show that there exists a $\delta_1^\prime >0$ and direction $\bar{\bd} \in \mathbb{R}^n$ such that $g(\lambda_0 + \epsilon) = \y_0 + \epsilon \bar{\bd}$, for all $\epsilon \in (0, \delta_1^\prime]$. Suppose for a contradiction that the projections curve in the neighborhood of $\y_0$ is not linear, and let $\lambda_1 \in (\lambda_0, \infty)$ be any lambda such that the curve between $\y_0$ and $\y_1:= g(\lambda_1)$ is non-linear (there is no segment that is linear between $\y_0$ and $\y_1$). Now, consider the following points: $\lambda_{i+1} = \lambda_0 + (\lambda_1 - \lambda_0)/2^i$ for $i = 1, \hdots, 2^{m}$ and define $\y_i := g(\lambda_i)$. Thus, $N_P(\y_i) \neq N_P(\y_j)$ for any $i,j = 0,\dots 2^{m}+1$ such that $i \neq j$, otherwise the curve would be linear between $\y_i$ and $\y_j$ contradicting our assumption (using Lemma \ref{equivalence}). In other words, the normal cones at each of these points $\y_i$ must be distinct, but this is more than the distinct normal cones in any polytope with $m$ facet inequalities, which is a contradiction.

Using the exact similar argument, we know that there exists $\delta_2^\prime >0$ and direction $\uline{\bd} \in \mathbb{R}^n$ such that $g(\lambda - \epsilon^\prime) = g(\lambda) - \epsilon^\prime \uline{\bd}$ for all $\epsilon \in (0,\delta_2^\prime]$. The result now follows by setting $\delta^\prime := \min \{\delta_1^\prime, \delta_2^\prime\}$.
\end{itemize}
 \qed \end{proof}

\iffalse
\subsubsection{Proof of Lemma \ref{existence-new}}

To prove this lemma, we need the following structural result about Euclidean projections, which states that if for some $\lambda^\prime > \lambda >0$ the point $\mathbf{z} := \left(1 - \frac{\lambda^\prime}{\lambda}\right)\x_0 +  \frac{\lambda^\prime}{\lambda}g(\lambda)$
in the affine hull of $g(\lambda)$ and $\x_0$ is feasible in $P$, then it indeed coincides with the  $g(\lambda^\prime)$.

\begin{restatable}[Affine hull expansion of projections]{lemma}{affinehull}
\label{affine-hull}
Let $P \subseteq \mathbb{R}^n$ be a polytope. Let $\x_0\in P$ and we are given $\nabla f(\x_0) \in \mathbb{R}^n$. Further, let $g(\lambda) = \Pi_{P}(\x_0 - \lambda \nabla f(\x_0))$ be the parametric projections curve. If $\mathbf{z} := \left(1 - \frac{\lambda^\prime}{\lambda}\right)\x_0 +  \frac{\lambda^\prime}{\lambda}g(\lambda) \in P$ for some $\lambda < \lambda^\prime$, then $g(\lambda^\prime) = \mathbf{z}$.
\end{restatable}
\begin{proof}
We will show that $\mathbf{z} := \left(1 - \frac{\lambda^\prime}{\lambda}\right)\x_0 +  \frac{\lambda^\prime}{\lambda}g(\lambda) = \x_0 + \frac{\lambda^\prime}{\lambda} (g(\lambda) - \x_0) \in P$ satisfies first-order optimality for the projection at $\lambda^\prime$. Suppose for a contradiction, there exists some $\y \in P$ with
\begin{align*}
    &\innerprod{\x_0 - \lambda^\prime \nabla f(\x_0) - \mathbf{z}}{\y - \mathbf{z}} > 0\\
    \Leftrightarrow &\innerprod{\x_0 - \lambda^\prime \nabla f(\x_0) - \left(\x_0 + \frac{\lambda^\prime}{\lambda} (g(\lambda) - \x_0)\right)}{\y - \left(\x_0 + \frac{\lambda^\prime}{\lambda} (g(\lambda) - \x_0)\right)} > 0\\
     \Leftrightarrow & \frac{\lambda^\prime}{\lambda} \innerprod{\x_0 - \lambda \nabla f(\x_0) - g(\lambda)}{\y + \left(\frac{\lambda^\prime}{\lambda} -1\right) \x_0 - \frac{\lambda^\prime}{\lambda} g(\lambda)} > 0\\
     \Leftrightarrow &\left(\frac{\lambda^\prime}{\lambda}\right)^2 \innerprod{\x_0 - \lambda \nabla f(\x_0) - g(\lambda)}{\frac{\lambda}{\lambda^\prime} \y + \left(1 - \frac{\lambda}{\lambda^\prime} \right) \x_0 -  g(\lambda)} > 0.
\end{align*}
Observe that $\frac{\lambda}{\lambda^\prime} \y + \left(1 - \frac{\lambda}{\lambda^\prime} \right) \x_0 \in P$ since $\frac{\lambda}{\lambda^\prime} \in (0,1)$ and $P$ is a convex set. This contradicts the first-order optimality condition of $g(\lambda)$ given by:
$\innerprod{\x_0 - \lambda \nabla f(\x_0) - g(\lambda)}{\mathbf{x} -  g(\lambda)} \leq 0$ for all $ \mathbf{x} \in P$.
\qed\end{proof}

We are now ready to prove Lemma \ref{existence-new}:

\existencenew*
\begin{proof}
Using Theorem \ref{elephant} we know that $g(\lambda)$ is piecewise linear. Let $\x_1$ be the first breakpoint of $g(\lambda)$ and recall from \eqref{newdirectional1} that $g(\lambda) = \x_0 +  \lambda \bd_{\x_0}^\Pi$ for all $\lambda \in [0,\lambda_1^-]$. Let $\delta := \max\{\lambda \mid \x_0 + \lambda \bd_{\x_0}^\Pi \in P\}$ and note that $\lambda_1^- \leq \delta$. Suppose for a contradiction that $\lambda_1^- < \delta$ and fix $\lambda \in (\lambda_1^-, \delta]$. Then, $g(\lambda) \neq \x_0 + \lambda \bd_{\x_0}^\Pi$ by assumption. However, since
$$\mathbf{z}:=\x_0 + \lambda \bd_{\x_0}^\Pi = \x_0 + \frac{\lambda}{\lambda^\prime}(g(\lambda^\prime) - \x_0) \quad \text{for any arbitrary $\lambda^\prime \in [0,\lambda_1^{-}]$}$$
is feasible in $P$ by definition of $\delta$, we have $g(\lambda) = \mathbf{z}$ using the affine hull expansion property (Lemma \ref{affine-hull}), which is a contradiction.
\qed\end{proof}
\fi

\subsection{Missing Proofs for Section \ref{sec:normal cone props} \label{app:normal proofs}}

\subsubsection{Proof of Lemma \ref{movement along linear segments}}
\movementlinear*

\begin{proof}
First note that $\delta > 0$ since $\bd$ is feasible at $\x$, and $\delta < \infty$ since $P$ is a polytope and movements along any direction are bounded. For brevity, we let $I$ and $J$ denote the index-set of active and inactive constraints at $\x$ respectively. Fix $\lambda,\lambda^\prime \in (0,\delta)$ arbitrarily such that $\lambda < \lambda^\prime$. We prove the Lemma in the next two claims.
\begin{enumerate}
    \item[(a)] {\it We first show that $N_P(\x+\lambda \bd) = N_P(\x+\lambda^\prime \bd) \subseteq N_P(\x)$}. We prove Claim $(a)$ in the next two sub-claims:
\begin{itemize}
    \item[(a.i)] {\it Inactive constraints remain inactive: $N_P(\x + \lambda \bd) \subseteq N_P(\x)$}. Since $\x + \delta \bd \in P$, we have $\A_J (\x + \delta\bd) \leq \mathbf{b}_{J}$, which implies that $\A_J \bd \leq \frac{\mathbf{b}_{J} - \A_J \x}{\delta}$. Moreover, for any $\lambda < \delta$, we have
    \vspace{-8 pt}
\begin{equation*}
    \A_J (\x + \lambda\bd) \leq \A_J\x + \lambda\frac{\mathbf{b}_{J} - \A_J \x}{\delta} = \left( 1 -\frac{\lambda}{\delta} \right)\A_J\x + \mathbf{b}_{J} \frac{\lambda}{\delta} < \mathbf{b}_{J},
    \vspace{-5 pt}
\end{equation*}
where the last (strict) inequality follows from the fact that we are taking a convex combination. This shows $\A_J(\x + \lambda \bd) < \mathbf{b}_J$ (component-wise) for all $\lambda \in (0,\delta)$, i.e. $N_P(\x + \lambda \bd) \subseteq N_P(\x)$.
    \item[(a.ii)] {\it Active constraints are maintained: $N_P(\x+\lambda \bd) = N_P(\x+\lambda^\prime \bd)$}. Fix $\lambda,\lambda^\prime \in (0,\delta)$ arbitrarily such that $\lambda^\prime > \lambda$. Since the inactive constraints remain inactive, we just need to check the constraints in the index set $I$. Consider any $i \in I$. Since $\innerprod{\mathbf{a}_i}{\x_0} = b_i$ and $\x_0 + \delta \bd \in P$ $(\delta>0)$, we know that $\innerprod{\mathbf{a}_i}{\bd} \leq 0$. If $\innerprod{\mathbf{a}_i}{\bd} = 0$, then  $\innerprod{\mathbf{a}_i}{\x+\lambda \bd} = b_i$ for all $\lambda \in [0,\delta)$. So the constraint corresponding to $\mathbf{a}_i$ is active at both $\x+\lambda \bd$ and $\x+\lambda^\prime \bd$. On the other hand, if $\innerprod{\mathbf{a}_i}{\bd} < 0$, then $\innerprod{\mathbf{a}_i}{\x+\lambda \bd} < b_i$ for all $\lambda \in [0,\delta)$. Thus, the constraint corresponding to $\mathbf{a}_i$ is inactive at both $\x+\lambda \bd$ and $\x+\lambda^\prime \bd$.
\end{itemize}

\item[(b)] {\it We next show that $N_P(\x+\lambda \bd) \subset N_P(\x+ \delta \bd)$}. Let $\tilde{I}$ denote the index set of active constraints at $\x+\lambda \bd$. Using Claim (a.i), we know that $\tilde{I} \subseteq I$. Therefore, for any $i \in \tilde{I}$, we have
\begin{equation*}
 \innerprod{\mathbf{a}_i}{\x+\lambda \bd} = b_i \implies \innerprod{\mathbf{a}_i}{\bd} = 0 \implies \innerprod{\mathbf{a}_i}{\x + \delta \bd} = b_i,
\end{equation*}
and so the constraint corresponding to $\mathbf{a}_i$ (which is active at $\x+\lambda \bd$) is also active at $\x + \delta \bd$. We have thus shown that $N_P(\x+\lambda \bd) \subseteq N_P(\x+\delta \bd)$. It remains to show that this containment is strict. Since $\bd$ is a feasible direction at $\x$, we have $\innerprod{\mathbf{a}_i}{\bd} \leq 0$ for all $i \in I$. Thus
\begin{equation} \label{max lambda}
    \delta = \min_{\substack{j \in J:\\ \innerprod{\mathbf{a}_j}{\bd} > 0}} \frac{b_j - \innerprod{\mathbf{a}_j}{\x}}{\innerprod{\mathbf{a}_j}{\bd}},
\end{equation}
where the feasible set of the above problem is non-empty, since otherwise this would imply that $\bd$ is a recessive direction (i.e. direction of unboundedness), contradicting the fact that $P$ is a polytope. Let $j^*$ be any optimal index to the optimization problem in \eqref{max lambda}, where by definition $\innerprod{\mathbf{a}_{j^*}}{\x+\delta \bd} = b_{j^*}$. Now, since $\innerprod{\mathbf{a}_{j^*}}{\bd }>0$ and $\lambda < \delta$, we have
$\innerprod{\mathbf{a}_{j^*}}{\x+\lambda \bd} < \innerprod{\mathbf{a}_{j^*}}{\x + \delta \bd}$,
implying that the constraint $\mathbf{a}_{j^*}$ is not active at $\x+\lambda \bd$. Thus, $N_P(\x+\lambda \bd) \subset N_P(\x+\delta \bd)$.
\end{enumerate}
 This completes the proof since $\lambda,\lambda^\prime$ were chosen arbitrarily.\qed
 \end{proof}

\iffalse
\subsubsection{Proof of Lemma \ref{maxmimum movement along linear segments}}

\maximumlinearmovement*
\begin{proof}
First note that $\delta > 0$ since $\bd$ is feasible at $\x$. Fix $\epsilon \in (0,\delta)$ arbitrarily. Let $I$ denote the index set of active constraints at $\x+(\delta - \epsilon)\bd$. Using Lemma \ref{movement along linear segments}, we know that $I \subseteq I(\x_0)$. Therefore, for any $i \in I$, we have
 \vspace{-8 pt}
\begin{equation*}
 \innerprod{\mathbf{a}_i}{\x+(\delta - \epsilon)\bd} = b_i \implies \innerprod{\mathbf{a}_i}{\bd} = 0 \implies \innerprod{\mathbf{a}_i}{\x + \delta \bd} = b_i,
 \vspace{-8 pt}
\end{equation*}
and so the constraint corresponding to $\mathbf{a}_i$ (which is active at $\x+(\delta - \epsilon)\bd$) is also active at $\x + \delta \bd$. We have thus shown that $N_P(\x+(\delta - \epsilon) \bd) \subseteq N_P(\x+\delta \bd)$. It remains to show that this containment is strict. Since $\bd$ is a feasible direction at $\x$, we have $\innerprod{\mathbf{a}_i}{\bd} \leq 0$ for all $i \in I$. Thus
\begin{equation} \label{max lambda}
    \delta = \min_{\substack{j \in J:\\ \innerprod{\mathbf{a}_j}{\bd} > 0}} \frac{b_j - \innerprod{\mathbf{a}_j}{\x}}{\innerprod{\mathbf{a}_j}{\bd}},
\end{equation}
where the feasible set of the above problem is non-empty, since otherwise this would imply that $\bd$ is a recessive direction (i.e. direction of unboundedness), contradicting the fact that $P$ is a polytope. Let $j^*$ be any optimal index to the optimization problem in \eqref{max lambda}, where by definition $\innerprod{\mathbf{a}_{j^*}}{\x+\delta \bd} = b_{j^*}$. Now, since $\innerprod{\mathbf{a}_{j^*}}{\bd }>0$ we have
$\innerprod{\mathbf{a}_{j^*}}{\x+(\delta - \epsilon)\bd} < \innerprod{\mathbf{a}_{j^*}}{\x + \delta \bd}$,
implying that the constraint $\mathbf{a}_{j^*}$ is not active at $\x+(\delta - \epsilon)\bd$. Thus, we have $N_P(\x+(\delta - \epsilon) \bd) \subset N_P(\x+\delta \bd)$. The result now follows since $\epsilon$ was arbitrary.
 \qed \end{proof}
\fi

\subsection{Missing Proofs in Section \ref{sec:trace}} \label{app:missing proofs for trace}
\iffalse
We prove Theorem \ref{invariance} in this section. To do that, we first need the following result about minimizing strongly convex functions over polyhedrons.

\subsubsection{Properties of strongly convex minimization over polytopes}
We now give a structural result about minimizing strongly functions over \emph{polyhedrons}, which states that if we know the optimal (minimal) face then we can restrict the optimization to that optimal face and ignore the remaining faces of the polyhedron. We will crucially use this result to  prove case $(b)$ for Theorem \ref{invariance}.
\begin{lemma}[Reduction of optimization problem to optimal face]\label{optimal face}
Let $\mathcal{P} = \{\x \in \mathbb{R}^n: \innerprod{\mathbf{a}_i}{\mathbf{x}} \leq b_i \; \forall \; i \in [m]\}$ be a polyhedron and suppose that $f:\mathbb{R}^n \to \mathbb{R}$ be $\mu$-strongly convex over $\mathcal{P}$. Let $\x^* = \argmin_{\x \in \mathcal{P}} f(\x)$, where uniqueness and existence of the optimal solution follow from the strong convexity of $f$. Further, let
\begin{equation}\label{optimal face equation}
    \tilde{\x} = \argmin_{\x \in \mathbb{R}^n} \{f(\x) \mid \mathbf{A}_{I(\x^*)} \x = \mathbf{b}_{I(\x^*)}\}.
\end{equation}
Then, we claim that $\x^* =  \tilde{\x}$.
\end{lemma}

\begin{proof} Let $J(\x^*)$ denote the index set of inactive constraints at $\x^*$. We assume that $J(\x^*) \neq \emptyset$, since otherwise the result follows trivially. Now, suppose for a contradiction that $\x^* \neq \tilde{\x}$. Due to uniqueness of the minimizer of the strongly convex function over $\mathcal{P}$, we have that $\tilde{\x}\notin \mathcal{P}$ (otherwise it contradicts optimality of $\x^*$ over $\mathcal{P}$). We now construct a point $\y \in \mathcal{P}$ that is a strict convex combination of $\tilde{\x}$ and $\x^*$ and satisfies $f(\y) < f(\x^*)$, which contradicts the optimality of $\x^*$. To that end, define
\begin{equation} \label{gamma def}
    \gamma := \min_{\substack{j \in J(\x^*):\\ \innerprod{\mathbf{a}_j}{\tilde{\x} - \x^*} > 0}} \frac{b_j - \innerprod{\mathbf{a}_j}{\x^*}}{\innerprod{\mathbf{a}_j}{\tilde{\x} - \x^*}} > 0,
\end{equation}
with the convention that $\gamma = \infty$ if the feasible set of \eqref{gamma def} is empty, i.e. $\innerprod{\mathbf{a}_j}{\tilde{\x} - \x^*} \leq 0$ for all $j \in J(\x^*)$. Select $\tilde{\theta} \in (0, \min\{\gamma,1\})$. Further, define $\y :=  \x^* + \tilde{\theta} (\tilde{\x} - \x^*) \neq \x^*$ to be a strict convex combination of $\x^*$ and $\tilde{\x}$. We claim that that $(i)$ $\y \in \mathcal{P}$ and $(ii)$ $f(\y) < f(\x^*)$, which completes our contradiction argument:
\begin{itemize} [leftmargin= 40pt]
    \item [$(i)$: $\y \in \mathcal{P}.$] Any inequality satisfied by $\tilde{\x}$ is also satisfied by $\x^*$ and therefore by $\y$. Consider $j \in J(\x^*)$ such that $\innerprod{\mathbf{a}_j}{\tilde{\x}} > b_j \geq \innerprod{\mathbf{a_j}}{\x^*}$. Then, we have
\begin{align*}
   \innerprod{\mathbf{a}_j}{\y} &= \innerprod{\mathbf{a}_j}{\x^*} + \tilde{\theta} \innerprod{\mathbf{a}_j}{\tilde{\x} - \x^*}
   \leq \innerprod{\mathbf{a}_j}{\x^*} + \gamma \innerprod{\mathbf{a}_j}{\tilde{\x} - \x^*}\\
    &\leq \innerprod{\mathbf{a}_j}{\x^*} + b_j - \innerprod{\mathbf{a}_j}{\x^*}
   = b_j,
\end{align*}
where we used the fact that $\tilde{\theta} \leq \gamma$ in the first inequality, and the definition of $\gamma$ \eqref{gamma def} in the second inequality. This establishes the feasibility of $\y \in \mathcal{P}$.
\item [$(ii)$: $f(\y) < f(\x^*).$] Observe that $f(\tilde{\x}) \leq f(\x^*)$ since $\x^*$ is feasible for \eqref{optimal face equation}. Since, $\x^* \neq \tilde{\x}$, We can now complete the proof of this claim as follows:
\begin{align*}
    f(\y) &= f((1 -\tilde{\theta})\x^* + \tilde{\theta}\tilde{\x})
    < (1 -\tilde{\theta})f(\x^*) + \tilde{\theta}f(\tilde{\x})
    \leq f(\x^*)\label{opt face eq 4},
\end{align*}
where we used the fact $\tilde{\theta} \in (0,1)$ and the fact that $f$ is strictly convex (since it is strongly convex) in the first inequality, and the fact that $f(\tilde{\x}) \leq f(\x^*)$ in second.
\end{itemize}
This completes the proof.
 \qed \end{proof}
\fi

\subsubsection{Proof of Theorem \ref{invariance}}

\invariance*

We first show that if at breakpoint $\x_{i-1}$ the shadow $\mathbf{d}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0)) = 0$, then $\x_{i-1}$ is the endpoint of the curve:
\begin{lemma} If $\bd_{\x_{i-1}}^\Pi(\nabla f(\x_0)) = \mathbf{0}$, then $\lim_{\lambda \to \infty}g(\lambda) = \x_{i-1}$ is the end point of the projections curve $g(\lambda)$.
\end{lemma}
\begin{proof}
Since $\bd_{\x_{i-1}}^\Pi(\nabla f(\x_0)) =\mathbf{0}$, using Lemma \ref{basecase} we have $-\nabla f(\x_{0}) \in N_P(\x_{i-1})$. The first-order optimality condition of $ g(\lambda_{i-1}^{+}) = \x_{i-1}$, we have $\innerprod{\mb{p}}{\mathbf{z} - \x_{i-1}} \leq 0 $ for all $\mathbf{z} \in P$. Since $-\nabla f(\x_{0}) \in N_P(\x_{i-1})$ (i.e. $\innerprod{\textcolor{blue}{-}\nabla f(\x_0)}{\mathbf{z} - \x_{i-1}} \leq 0 \forall \mathbf{z} \in P$) and $\lambda \geq \lambda_{i-1}^{+}$, we get $\innerprod{\x_0-\lambda \nabla f(\x_0) - \x_{i-1}}{\mathbf{z} - \x_{i-1}}  \leq 0 \quad \forall \mathbf{z} \in P$. Thus,
$\x_{i-1}$ satisfies the first-order optimality condition for $g(\lambda)$ when $\lambda \geq \lambda_{i-1}^{+}$.
 \qed \end{proof}

\paragraph{Proof of Theorem \ref{invariance} Case \textit{(a)}.}
We prove this case in the following lemma:
\begin{lemma}
If $\innerprod{\mb{p}}{\bd_{\x_{i-1}}^\Pi (\nabla f(\x_0))} = 0$,
then,  $\x_{i} := g(\lambda_{i}^-)=\mathbf{x}_{i-1} + (\lambda_{i}^- - \lambda_{i-1}^+)\mathbf{d}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0))$, where $\lambda_{i}^- := \lambda_{i-1}^+ + \max \{\delta : \mathbf{x}_{i-1} + \delta \mathbf{d}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0)) \in P\}$.
\end{lemma}
\begin{proof} We first claim that if $\innerprod{\mb{p}}{\bd_{\x_{i-1}}^\Pi (\nabla f(\x_0))} = 0$, then \begin{equation} \label{invaraint equation}
  \tilde{g}(\lambda) := \Pi_P(\x_{i-1} - (\lambda - \lambda_{i-1}^{+}) \nabla f(\x_0)) = g(\lambda) \quad \text{for $\lambda \in [\lambda_{i-1}^{+}, \lambda_{i}^{-}]$}.
\end{equation}
Assuming that \eqref{invaraint equation} holds, the lemma follows by invoking Lemma \ref{existence-new} about the structure of the first linear segment of $g(\lambda)$ with $\x_{i-1}$ in place $\x_0$ and parameter $(\lambda - \lambda_{i-1}^+)$ in place of $\lambda$.

We now prove claim \eqref{invaraint equation}. Fix ${\lambda} \in (\lambda_{i-1}^{+}, \lambda_{i}^{-}]$. Suppose for a contradiction that
$\mathbf{z} := \tilde{g}({\lambda})$ does not equal the projection $g({\lambda})$. Then, since $\mathbf{z} \neq g(\lambda)$, we know there exists $\tilde{\mathbf{z}}\in P$:
\begin{align}
    &\innerprod{\x_0- \lambda \nabla f(\x_0) - \mathbf{z}}{\tilde{\mathbf{z}} - \mathbf{z}} > 0
    \Rightarrow \innerprod{\mb{p}}{\tilde{\mathbf{z}} - \mathbf{z}} + \innerprod{\x_{i-1}  - (\lambda - \lambda_{i-1}^{+}) \nabla f(\x_0) - \mathbf{z}}{\tilde{\mathbf{z}} - \mathbf{z}} > 0\nonumber\\
    &\Rightarrow \innerprod{\mb{p}}{\tilde{\mathbf{z}} - \mathbf{z}} > 0
    \Rightarrow  \innerprod{\mb{p}}{\tilde{\mathbf{z}} - \x_{i-1}} + \innerprod{\mb{p}}{\x_{i-1} - \mathbf{z}} > 0, \label{eq-31}\\
    &\Rightarrow  \innerprod{\mb{p}}{\x_{i-1} - \mathbf{z}} > 0,\label{eq-32}
\end{align}
where \eqref{eq-31} follows by first-order optimality at $\mathbf{z}$, and \eqref{eq-32} follows by first-order optimality at ${\x_{i-1}}$.

Using Lemma \ref{existence-new} with $\x_{i-1}$ in place of $\x_0$ and parameter $(\lambda - \lambda_{i-1}^{+})$ in place of $\lambda$, we have $\mathbf{z} = \x_{i-1} + (\lambda - \lambda_{i-1}^{+}) \bd_{\x_{i-1}}^\Pi(\nabla f(\x_0))$. Thus, using this fact in \eqref{eq-32}, we have $\innerprod{\mb{p}}{\x_{i-1} - \mathbf{z}} = \innerprod{\mb{p}}{{-}(\lambda - \lambda_{i-1}^{+}) \bd_{\x_{i-1}}^\Pi (\nabla f(\x_0))} > 0$,
which implies that $\innerprod{\mb{p}}{\bd_{\x_{i-1}}^\Pi (\nabla f(\x_0))} < 0$. This is a contradiction to our assumption $\innerprod{\mb{p}}{\bd_{\x_{i-1}}^\Pi (\nabla f(\x_0))} = 0$.
 \qed \end{proof}

\paragraph{ Proof of Theorem \ref{invariance} Case \textit{(b)}.}
We now prove case $(b)$. Consider a breakpoint $\x_{i-1}$ and recall that $\hat{\lambda}_{i-1}:=\sup\{\lambda \mid N_P(g(\lambda^\prime)) = N_P(\x_{i-1}) \; \forall \lambda^\prime \in [\lambda_{i-1}^-,\lambda)\}$. For brevity we let $I := I(\x_{i-1})$ and $\mb{p}:= \x_0- \lambda_{i-1}^{+} \nabla f(\x_0) - \x_{i-1}$ Here we assume that $\innerprod{\mb{p}}{\bd_{\x_{i-1}}^\Pi (\nabla f(\x_0))} \neq 0$. To prove case $(b)$ we have to show the following claims:
\begin{enumerate}
    \item If $\innerprod{\mb{p}}{\bd_{\x_{i-1}}^\Pi (\nabla f(\x_0))} \neq 0$, then $\hat{\bd}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0)) \neq {\bd}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0))$ and $\hat{\lambda}_{i-1} > \lambda_{i-1}^+$ (i.e. the projections curve moves in-face at $\x_{i-1}$). \textbf{(Lemma \ref{in-face movement})}
    \item The next breakpoint in the curve occurs by walking in-face up to $\hat{\lambda}_{i-1}$, i.e., $\x_{i} := g(\hat{\lambda}_{i-1}) =\mathbf{x}_{i-1} + (\hat{\lambda}_{i-1} - \lambda_{i-1}^+)\hat{\bd}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0))$ and $\lambda_{i}^- := \hat{\lambda}_{i-1}$. \textbf{(Lemma \ref{in-face shadow movement})}
\end{enumerate}

\begin{lemma} \label{in-face movement} Let $\mb{p}:= \x_0- \lambda_{i-1}^{+} \nabla f(\x_0) - \x_{i-1}$. If $\innerprod{\mb{p}}{\bd_{\x_{i-1}}^\Pi (\nabla f(\x_0))} \neq 0$, then $\hat{\lambda}_{i-1} > \lambda_{i-1}^+$ and $\hat{\bd}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0)) \neq {\bd}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0))$.
\end{lemma}

\begin{proof}
We first show that $\hat{\bd}_{\x_{i-1}}^\Pi (\nabla f(\x_0)) \neq {\bd}_{\x_{i-1}}^\Pi (\nabla f(\x_0))$. Note that since $\hat{\bd}_{\x_{i-1}}^\Pi (\nabla f(\x_0))$ is the projection of $-\nabla f(\x_0)$ onto the nullspace of $\mathbf{A}_{I}$ and $\mb{p}$ is in the rowspace of  $\mathbf{A}_{I}$, it follows that $\innerprod{\mb{p}}{\hat{\bd}_{\x_{i-1}}^\Pi (\nabla f(\x_0))} = 0$. However, $\innerprod{\mb{p}}{{\bd}_{\x_{i-1}}^\Pi (\nabla f(\x_0))} \neq 0$, and thus $\hat{\bd}_{\x_{i-1}}^\Pi (\nabla f(\x_0)) \neq {\bd}_{\x_{i-1}}^\Pi (\nabla f(\x_0))$. We now prove that $\hat{\lambda}_{i-1} > \lambda_{i-1}^+$. Observe that by definition of $\hat{\lambda}_{i-1}$ have $\hat{\lambda}_{i-1} \geq \lambda_{i-1}^+$. However, we now claim that if $\innerprod{\mb{p}}{\bd_{\x_{i-1}}^\Pi (\nabla f(\x_0))} \neq 0$, then $\hat{\lambda}_{i-1} \neq \lambda_{i-1}^+$, and thus $\hat{\lambda}_{i-1} > \lambda_{i-1}^+$. To show our claim, we prove the contrapositive:
 \begin{itemize}
     \item[] \textit{Claim: If $\hat{\lambda}_{i-1} = \lambda_{i-1}^+$, then $\innerprod{\mb{p}}{\bd_{\x_{i-1}}^\Pi (\nabla f(\x_0))} = 0$.}
     \item[] \textit{Pf.}  Assume that $\mathbf{d}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0)), \mb{p} \neq \mathbf{0}$, otherwise the statement follows trivially.
Recall that $\bd_{\x_{i-1}}^\Pi (\nabla f(\x_0)) = \argmin_{\bd} \{\| -\nabla f(\x_0) - \bd\|^2 \mid \mathbf{A}_I \bd \leq \mb{0}\}$ (see Section \ref{sec: prelims}).
Let $\hat{I} \subseteq I$ be such that $\mathbf{A}_{\hat{I}} \bd_{\x_{i-1}}^\Pi (\nabla f(\x_0)) = \mathbf{0}$. By reducing the previous optimization problem to the optimal face (Lemma \ref{optimal face}), we can write $\bd_{\x_{i-1}}^\Pi (\nabla f(\x_0)) = \argmin_{\bd} \{\| -\nabla f(\x_0) - \bd\|^2 \mid \mathbf{A}_{\hat{I}} \bd = \mb{0}\}.$

Since $\bd_{\x_{i-1}}^\Pi (\nabla f(\x_0)) \neq \mathbf{0}$ is the projection of $-\nabla f(\x_0)$ onto the nullspace of $\mathbf{A}_{\hat{I}}$ and $\mb{p} \neq \mathbf{0}$, it follows that $\innerprod{\mb{p}}{\bd_{\x_{i-1}}^\Pi (\nabla f(\x_0))} = 0$ if and only if $\mb{p}$ is in the rowspace of $\mathbf{A}_{\hat{I}}$, that is
$\innerprod{\mb{p}}{\bd_{\x_{i-1}}^\Pi (\nabla f(\x_0))} = 0 \Leftrightarrow \mb{p} = \mathbf{A}_{\hat{I}} ^\top \mb{v}$ for some $\mb{v} \in \mathbb{R}^{|\hat{I}|}$.

Using properties Theorem \ref{elephant}$(i)$-$(ii)$ and the fact that $\hat{\lambda}_{i-1} = \lambda_{i-1}^+$, we have $N_P(g(\lambda_{i-1}^+ + \epsilon)) = N_P(g(\lambda_{i-1}^+ + \epsilon^\prime)) \subset N_P(\x_{i-1})$ for all $0<\epsilon < \epsilon^\prime < \lambda_{i}^- - \lambda_{i-1}^+$. Furthermore, using the definition of $\bd_{\x_{i-1}}^\Pi (\nabla f(\x_0))$, it follows that for any $\epsilon$ sufficiently small, the set of active constraints at $g(\lambda_{i-1}^+ + \epsilon)$ will also be $\hat{I}$. Denoting $\mb{p}_\epsilon := \x_0  - (\lambda_{i-1}^+ + \epsilon)\nabla f(\x_0) - g(\lambda_{i-1}^+ + \epsilon) \in N_P(g(\lambda_{i-1}^+ + \epsilon))$, it follows that we can write $\mb{p}_\epsilon = \mathbf{A}_{\hat{I}} ^\top \mb{\mu}$ for some $\mb{\mu} \in \mathbb{R}^{|\hat{I}|}_+$. Since this is true for any $\epsilon > 0$ arbitrarily small and the projections curve is continuous by Lemma \ref{continuous and piecewise}, the result follows by letting $\epsilon \downarrow 0$. \qed
\end{itemize}
\end{proof}

\begin{lemma} \label{in-face shadow movement}
 Let $\mb{p}:= \x_0- \lambda_{i-1}^{+} \nabla f(\x_0) - \x_{i-1}$. If $\innerprod{\mb{p}}{\bd_{\x_{i-1}}^\Pi (\nabla f(\x_0))} \neq 0$, then $\x_{i} := g(\hat{\lambda}_{i-1}) =\mathbf{x}_{i-1} + (\hat{\lambda}_{i-1} - \lambda_{i-1}^+)\hat{\bd}_{\mathbf{x}_{i-1}}^\Pi(\nabla f(\x_0))$ and $\lambda_{i}^- := \hat{\lambda}_{i-1}$.
\end{lemma}
 \begin{proof} First, note that $\lambda_{i-1}^{+} < \hat{\lambda}_{i-1}$ using Lemma \ref{in-face movement}, which further implies that $\lambda_{i-1}^{-} = \lambda_{i-1}^{+}$. Also, by definition $\hat{\lambda}_{i-1}$, we know that $g(\lambda)$ lies on the face defined by $\mathbf{A}_{I} g(\lambda) = \mb{b}_{I}$ for $\lambda \in [\lambda_{i-1}^{-}, \hat{\lambda}_{i-1})$. The fact that $\x_i := g(\hat{\lambda}_{i-1})$ is the next breakpoint follows from the fact that the projections curve leaves the minimal face after this point, and thus direction change in the projections curve must happen by Lemma \ref{equivalence}.

 It remains to show that the projections curve is directed by $\hat{\bd}_{\x_{i-1}}^\Pi (\nabla f(\x_0))$ up to $\hat{\lambda}_{i-1}$. By reducing the projection to the optimal face (Lemma \ref{optimal face}) and using the fact that $g(\lambda)$ is continuous, we can write the projection problem as a least-squares optimization problem:
    \begin{equation} \label{proj in face}
        g(\lambda) = \argmin_{\y} \{\|\x_0 - \lambda \nabla f(\x_0) - \mathbf{y}\|^2 \mid \mathbf{A}_{I} \mathbf{y} = \mb{b}_{I}\} \quad
        \forall \lambda \in [\lambda_{i-1}^{+}, \hat{\lambda}_{i-1}].
    \end{equation}
   Using standard linear algebra arguments (see e.g. Section 5.13 in \cite{meyer2000matrix}), the solution to \eqref{proj in face} is given by $g(\lambda)= \x_{i-1} + (\lambda -\lambda_{i-1}^{+}) \hat{\bd}_{\x_{i-1}}^\Pi (\nabla f(\x_0))$ for any $\lambda \in [\lambda_{i-1}^{+}, \hat{\lambda}_{i-1}]$.
 \qed \end{proof}
 \noindent
This concludes the proof of Theorem \ref{invariance}.

\subsubsection{Proof of Theorem \ref{breakpoints}}

\breakpoints*

\begin{proof}
Fix $\mathbf{x} \in P$ and consider the procedure $\textsc{Trace}(\x, \nabla f(\x))$. The fact that $\textsc{Trace}(\x, \nabla f(\x))$ correctly traces the curve $g(\lambda) = \Pi_P(\mathbf{x} - \lambda \nabla f(\mathbf{x}))$ follows from the constructive proof given for Theorem \ref{invariance}. Moreover, upon termination there are two things that can happen: (i) the line-search evaluates to a step-size that is not maximal in one of the segments of $g(\lambda)$, (ii) we reach the end point of the curve $\mathbf{v}^* = \lim_{\lambda \to \infty} g(\lambda)$ (as defined in Theorem \ref{FW limit}). At this point, we know that $-\nabla f(\x) \in N_P(\mathbf{v}^*)$. Recall that for any $\x \in P$, we can compute the directional derivative using a single projection:
\begin{equation*}
   \bd_{\x}^\Pi = \frac{\Pi_P(\x - \epsilon \nabla f(\x)) - \x}{\epsilon},
\end{equation*}
where $\epsilon$ is sufficiently small. Thus, when recomputing the directional derivative in the subsequent iteration:
\begin{equation*}
   \frac{\Pi_P(\mathbf{v}^* - \epsilon \nabla f(\x)) - \mathbf{v}^*}{\epsilon} = \frac{\mathbf{v}^* - \mathbf{v}^*}{\epsilon} = \mathbf{0},
\end{equation*}
where $\epsilon$ is sufficiently small. The second equality above follows from the definition of $\mathbf{v}^*$ and Lemma \ref{basecase}. This proves the correctness of the termination criterion given in Algorithm \ref{alg: tracing PW proj}.

Once the curve leaves the interior of a face, it can no longer visit the face again. This is because equivalence of normal cones at two projections implies the projections curve is linear between the two points (Lemma \ref{equivalence}). Therefore, the number of breakpoints can be at most the number of faces, i.e.,  $O(2^m)$.

 \qed \end{proof}


TITLE: A new generalisation of Fermat's little theorem?
QUESTION [11 upvotes]: I would like to share a personal result, which I interpret as a "generalisation of Fermat's little theorem". I know that there exist already several generalisations (e.g. Euler's) but I would like to know whether the result I found is something original or not. Let me explain...
Some years ago, my researches on binary representation of numbers lead me to this sequence of naturals: 1, 2, 1, 2, 3, 6, 9, 18, 56, ... . After some researches, I found that this was already indexed as A001037 sequence in OEIS; this is known as number of "binary Lyndon words of length $n$" or "$n$-bead necklaces with beads of 2 colors". Such sequence can easily be generalised to other bases than 2. After naming $\lambda_a(n)$ the number of $n$-bead necklaces with beads of $a$ colors with $a \ge 2$, I found that
$$ a^n = \sum_{d|n}  d \lambda_a(d) $$
For example,
$$ 2^6 = 1\lambda_2(1) + 2\lambda_2(2) + 3\lambda_2(3) + 6\lambda_2(6) = 2 + 2 + 6 + 54 = 64 $$
This is NOT an original result since you can find this relationship on the afore-mentioned OEIS page, at least.
QUESTION 1: Can someone provides references for a proof of this equation (papers, books, ...)?
Now, after defining
$$ \sigma_a(n) \triangleq \sum_{\substack{ d|n \\ 1<d<n}} d \lambda_a(d) $$
the previous equation can be rewritten
$$ a^n = a + n\lambda_a(n) + \sigma_a(n) $$
Then, using modular arithmetic, we obtain a generalisation of Fermat's little theorem:
$$ a^n \equiv a + \sigma_a(n) \pmod {n} $$
Note that this is indeed a generalisation since it applies on any natural $n$ and it boils down to
$$ a^p \equiv a \pmod {p} $$
for any prime $p$, that is the Fermat's little theorem.
This relationship looks appealing to me, at least for studying Fermat pseudoprimes: these are the composites $n$ having the "rare" property that $\sigma_a(n) \equiv 0 \pmod {n}$.
QUESTION 2: Is this generalisation of Fermat's little theorem a known result? If yes, could you please provide references?
Thanks,
PS: Please, be indulgent: this is my very first post on MO!

REPLY [8 votes]: Here's a massive generalization, with references.
Consider a sequence $\{a_n \}_{n\ge 1}$ of integers. We'll say it satisfies the necklace congruences if $a_{n} \equiv a_{n/p} \mod n$ whenever $p \mid n$ ($p$ prime).
Here are some equivalent formulations:

$a_{p^{k+1} m} \equiv a_{p^k m} \mod {p^{k+1}}$ for all $p,m,k$
$\sum_{d \mid n} a_d \mu(n/d) \equiv 0 \mod n$ for all $n$
The Mobius function can be replaced by any arithmetic function $f$ satisfying $\sum_{d \mid n} f(d) =0 \mod n, f(1) = \pm 1$.

So any such sequence gives rise to an integer sequence $\lambda_{\tilde{a}}(n) := \frac{1}{n}\sum_{d \mid n} a_d \mu(n/d)$ which satisfies $a_n = \sum_{d \mid n} d \lambda_{\tilde{a}}(n)$ by Mobius inversion. One can then define $\sigma_{\tilde{a}}(n):=\sum_{d \mid n, 1<d<n} d\lambda_{\tilde{a}}(d)$ and obtain the following generalization of Fermat's little theorem:
$a_n \equiv a_1 + \sigma_{\tilde{a}}(n) \mod n$
Now, let's go back to necklace congruences. A less obvious equivalence is the following:
Theorem: $\{a_n\}_{n \ge 1}$ satisfies the necklace congruences iff $\zeta_{a}(x):=\exp(\sum_{n\ge1} \frac{a_n}{n}x^n)$ has integer coefficients.
Proof: Write, $\zeta_a$ formally as $\prod_{n\ge 1} (1-x^n)^{-\frac{b_n}{n}}$. The $b_n$'s are uniquely determined, and in fact (by taking logarithmic derivative) it can be seen that they are $b_n = \sum_{d \mid n} a_d \mu(n/d)$. Now one direction is immediate and the other requires an inductive argument. $\blacksquare$
(Reference: Exercise 5.2 (and its solution) in Richard Stanley's book "Enumerative Combinatorics, vol. 2")
As Sergei remarked, for any integer square matrix $A$, the sequence $a_n := \text{Tr}(A^n)$ satisfies the necklace congruences. This is immediate from the last theorem, as the corresponding "zeta" function $\zeta_a$ is just:
$\exp( \sum_{n \ge 1} \frac{\text{Tr}((Ax)^n)}{n}) = \exp (\text{Tr} (- \ln (I -Ax)))=\det(I-Ax)^{-1} \in \mathbb{Z}[x]$
In particular, by taking a 1 on 1 matrix, we recover your observation.
Another generalization is $a_n = [x^n]f^n(x)$, where $f \in \mathbb{Z}[[x]]$. By taking the linear polynomial $f(x)=1+ax$ we recover your example, by taking $f(x)=(1+x)^m$ we get $a_n = \binom{nm}{n}$.
The really interesting feature is that this notion has a local version. Specifically, theorems of Dieudonne-Dwork and Hazewinkel give the following result:
Theorem: Given $\{ a_n \}_{n\ge 1} \subseteq \mathbb{Q}_{p}$ ($p$-adic numbers), the following are equivalent:

$\zeta_{a}(x) := \exp(\sum_{n\ge 1} \frac{a_n }{n}x^n)\in\mathbb{Z}_{p}[x]$
$\exp( \sum_{n \ge 1} p \frac{a_n - a_{n/p}}{n} x^n) \in 1+px\mathbb{Z}_{p}[x]$ (I defnite $a_{n/p}=0$ if $p\nmid n$)
$\sum_{n \ge 1}  \frac{a_n - a_{n/p}}{n} x^n) \in \mathbb{Z}_{p}[x]$
$p \mid n \implies a_n \equiv a_{n/p} \mod {n\mathbb{Z}_{p}}$

Applying this simultaneously for all $p$, we recover the previous theorem.
A reference for this theorem is "A Course in p-adic Analysis" by Alain M. Robert (the theorems are stated there in a much more general context).


TITLE: Group theory, character, representations, delta function, unit element
QUESTION [9 upvotes]: I am reading a physics paper (hep-th/9204083 v1 above eq (4.15)) where there is a nice formula that reads
$$
\delta(U-\mathbb{1}) = \sum\limits_{r} \dim(r)\, \mathrm{tr}_r(U)
$$
Here $\:U\:$ is a group element, $\:1\:$ is the unit group element, $\:r\:$ are the representations.
I would like to know if this formula has a name (for example something like Weyl's formula), if I can get any intuitive argument why it should be true.
I am not sure the formula applies to $\:U(1)\:$ group. The simplest case maybe would be $\:SU(2)\:$ and already there this formula seems quite complicated. I would like to verify the formula for the simplest possible case.
Is this formula a generalized Fourier transform?

REPLY [0 votes]: Combining Zachos formula
$$\int dU \delta(U-1) \chi_r(U) = \chi_r(1) = dim(r)$$
with
$$\delta(U-1) = \sum_s dim(s) \chi_s(U)$$
leads me to
$$\sum_s dim(s) \int dU \chi_s(U)\chi_r(U) = dim(r)$$
In other words, we should have
$$\int dU \chi_s(U) \chi_r(U) = \delta_{r,s}$$
This might be easier to prove than the original formula.


TITLE: Linear Algebra: Minimum Polynomial
QUESTION [1 upvotes]: Problem
Let $V$ be a finite-dimensional vector space over a field $K$ and let $T$ be a linear transformation
of $V$ to itself. We define the minimum polynomial $m(x)$ of $T$. Suppose that $q(x)$ is any polynomial in $K[x]$ and that $r(x)$ is the highest common factor of $q(x)$ and $m(x)$. Show that Ker($q(T)$) = Ker($r(T)$).

Progress
$r(x)$ hcf of $q(x)$ amd $m(x)$ $\Rightarrow$ $q=f_1r$ and $m=f_2r$ for some $f_1, f_2 \in K[x]$.
Take $v \in$ Ker ($r(T)$), then $q(T)v=(f_1r)(T)v=f_1(T)(r(T)v)=f_1(T)(0)=0$.
That is, Ker$r(T) \subseteq$ Ker $q(T)$. Not sure how to show the opposite relation; any help would be greatly appreciated. Regards.

REPLY [0 votes]: It is a matter of taste, but one can do without explicit mention of polynomial division (Euclid, Bezout). Since $q(t)$ is a multiple of $r(t)$ one certainly has $\ker(q(T)) \supseteq \ker(r(T))$ (as you remarked). For the opposite inclusion write $q(t)=p(t)r(t)$ and suppose $v\in\ker(q(T))$ so $p(T)(r(T)(v))=\vec0$; we wish to show that already $w=r(T)(v)=\vec0$. By definition of $r(t)$, there is no non-unit common factor of $p(t)$ and $(m/r)(t)$ but $w$ is annihilated by both $p(T)$ and by $(m/r)(T)$, so the minimal polynomial in $T$ that annihilates $w$ can only be $1$, which means that $w=\vec0$, as we wished to show.


TITLE: Negative frequency contributions for very short pulses?
QUESTION [3 upvotes]: I am wondering if very short optical light pulses can have a Gaussian envelope?
When I describe the pulse shape with a Gaussian than the frequency distribution has also a Gaussian shape. But if the envelope of the short pulse will have a pulse width of $1\,\text{as}=10^{-18}\,\text s$, then the frequency bandwidth will roughly be the inverse of the pulse width (since its a Gaussian), which leads to a frequency bandwidth of $10^{18}\,\text{Hz}$. But when the mean frequency of the pulse is in the optical regime, say $10^{15}\,\text{Hz}$, the frequency distribution will have enormous negative frequency contributions. Almost half of the frequency distribution will be in the negative range.
How can one avoid this problem?

REPLY [0 votes]: We sometimes forget about negative frequencies but they are always there. All real signals are composed equally of negative frequency and positive frequency components.
If you take an oscillating pulse with Gaussian envelope,
$$E(t) = A \exp(-\tfrac 12 t^2/\tau^2)\cos(\omega_0 t)$$
and convert it into its spectral representation, then you get two Gaussians:
$$E(\omega) =
\tfrac{A\tau}{\sqrt{8\pi}} \exp(-\tfrac 12(\omega - \omega_0)^2\tau^2)
+
\tfrac{A\tau}{\sqrt{8\pi}} \exp(-\tfrac 12(\omega + \omega_0)^2\tau^2)
$$
Note that I have defined that $E(t) = \int E(\omega) e^{-i\omega t} d\omega$. [Though I am possibly off by a prefactor here]
This is exact, but let's not get confused about the meaning of $\tau$ and $\omega_0$. $\tau$ and $\omega_0$ only roughly correspond to pulse duration and peak frequency. You can see this if you closely examine plots of $|E(t)|^2$ and $|E(\omega)|^2$ for various cases.
In general the two Gaussians mix together in frequency space---the tail of the negative frequency one extends to positive frequencies, and vice versa.
As a result, $\omega_0$ is only the peak energy frequency in the case of long pulses ($\omega_0\tau \gg 1$) where the mixing is negligible.
In this case can we approximate $|E(\omega)|^2$ as the sum of two Gaussians centered at $\pm \omega_0$.
If I choose short pulses ($\omega_0 \tau \lesssim 1$) then the peak energy frequency is less than $\omega_0$ for this example. Though that frequency shift does on the phase that I have chosen -- if I replaced $\cos$ by $\sin$ in the first formula then the peak energy would be at higher frequencies than  $\omega_0$ and the pulse would last slightly longer and contain less overall energy.
So do not expect $\omega_0$ and $\tau$ to have precise intuitive meanings in these sorts of cases --- they are just pulse shaping parameters.
One final exception to keep in mind --- if $\omega_0 = 0$ then $\tau$ again exactly corresponds to pulse duration and the peak energy is again at $\omega_0$.
Short answer: Gaussian pulses do not necessarily have single-Gaussian spectra, and negative frequencies are real.


TITLE: Taking a natural number different from zero as a base case in an inductive proof
QUESTION [5 upvotes]: Principle of mathematical induction states that if a subset $S$ of a successor set $\omega$ is also a successor set, then $S=\omega$. In primitive terms, it is formulated as:
if $S \subset \omega$, if $0 \in S$, and if $n^+ \in S$ whenever $n \in S$, then $S=\omega$.
Now, I wonder what if a statement that I want to prove holds for numbers starting from $b \in \omega$ for example. Would it be correct to introduce

a set $L$ that contains all natural numbers that satisfy the
    statement
a function $s: \omega \to \omega, s(n) = n^+$
a function $r: \omega \to \omega,
\begin{cases}
r(0) = b\\
r(n^+) = s(r(n))\\
\end{cases}$
a set $S$ that
    contains all natural numbers for which $r(n)\in L$

and show that $0$, $n$ and $n^+$ are in $S$? Because I can't just start proving inductively from $b$ and say that it holds for all numbers starting from $b$, as the principle of induction clearly states that $0$ has to be in $S$ too. So, I introduce a trick, i.e. mapping to perform induction.
Is it correct to do so? If not, then how to formally show that I can start from any number?

REPLY [5 votes]: You can either generalize the principle of induction to:
"For all $b \in \omega$: if $S \subset \omega$, if $b \in S$, and if $n^+ \in S$ whenever $n \in S$, then $S=\{ n \in \omega | n \geq b \}$."
Or, you can use the principle as stated and prove the base and step for the property $P(n)$ defined as $n \geq b \to P'(n)$, where $P'(n)$ is the 'real' property you are interested in, i.e. the property you want to prove all numbers $n \geq b$ to have. This works, since $P(n)$ will be trivially true for all $n < b$.


TITLE: Solving algebraic equations with modulus
QUESTION [0 upvotes]: How do I solve for 'b' given:
$1 \equiv a\pmod{2} \\ a=\frac{b-1}{3}$

REPLY [1 votes]: Seems pretty straight forward.
The first line states that a is odd.
The second line states that $ \frac{b-1}{3}$ must equal a and that way must also be odd.
$ \frac{b-1}{3}$ is odd if b-1 is a multiple of 3 with an odd number.
Set  $ b-1 = 3 \cdot (2n+1) = 6n+3, n>=0 $
So $ b = 6n+4 $ and of course $ a = \frac{b-1}{3} = 2n+1 $ for $ n>= 0 $


TITLE: Functional Equation for $f(x-y)+f(y-z)+f(z-x)=2f(x+y+z)$
QUESTION [8 upvotes]: The following functional equation proved quite difficult.
$1.$ $f(x)$ is a polynominal with real coeffecients.
$2.$ $f(1)=2,f(2)=20$.
$3.$ When for real $x,y,z$ satisfies the condition  $xy+yz+zx=0$, $$f(x-y)+f(y-z)+f(z-x)=2f(x+y+z)$$
Find $f(x)$ that satisfies all conditions given above.
While it is easy enough to guess that $f(x)=x^4+x^2$, proving it proved difficult.
First, putting in $(x,0,0)$ gives us that $f(-x)=f(x)$.
Second, putting in $(0,0,0)$ gives us $f(0)=0$
I also substituted $f(x)=g(x^2)$.
However, I was able to progress no further from here. Any help would be appreciated.

REPLY [1 votes]: Here There is no need to assume $f(x)=g(x^2)$, just assume $f(x)$ to be a real polynomial of degree 'n'. Eliminate z by taking $x-y = r,y-z = s$. Then invoke the polynomial equation and apply it to each term in both sides of given equation and by comparing you can arrive that $$f(x) = ax^2 +bx^4$$


TITLE: Eigenvalues of a Rank-One Update of a Matrix
QUESTION [15 upvotes]: Let $\lambda_1,\dots,\lambda_n$ be the eigenvalues of the square and symmetric $n\times n$ real matrix $A$. Consider a rank-one perturbation $B=A+\rho\,uu^T$, where $u$ is a real $n$-vector.
Is there an analytical expression for the eigenvalues of $B$, exploiting the known eigenvalues of $A$? I'm thinking something similar to the Sherman-Woodbury formula for the update of the inverse could work, but I have not succeeded.
I found some related results:

https://en.wikipedia.org/wiki/Bunch%E2%80%93Nielsen%E2%80%93Sorensen_formula, and also
https://doi.org/10.1137%2FS089547989223924X.

But both seem to require that $u$ is an eigenvector of $A$. Here, I am considering a more general statement, where $u$ need not be an eigenvector of $A$.

REPLY [12 votes]: I doubt there is an analytic expression for all but the smallest matrix dimensions. However, there is an inexpensive way to compute the eigenvalues of rank-one update.  The following comes from Demmel's Applied Numerical Linear Algebra subsection 5.3.3.
For any symmetric matrix $\mathbf{A}$, we can use the eigendecomposition $\mathbf{A} = \mathbf{V}^\top \text{diag}(\mathbf{d})\mathbf{V}$
to determine the eigenvalues of $\mathbf{B} = \mathbf{A} + \rho \mathbf{u}\mathbf{u}^\top$ as equivalently the eigenvalues of a diagonal plus rank-one matrix $\mathbf{V}\mathbf{B}\mathbf{V}^\top = \text{diag}(\mathbf{d}) + \rho (\mathbf{V}\mathbf{u})(\mathbf{V}\mathbf{u})^\top$.
We can then compute the eigenvalues through the roots of the determinant $\det(\mathbf{B}- \lambda \mathbf{I})$; in particular, if $\lambda$ is not an eigenvalue of $\mathbf{A}$ we have
$$ \det(\mathbf{B} - \lambda \mathbf{I}) = \det(\mathbf{A} + \rho \mathbf{u}\mathbf{u}^\top -\lambda \mathbf{I})
= \det(\mathbf{A} - \lambda \mathbf{I})\left[1+ \rho \sum_i \frac{(\mathbf{e}_i^\top \mathbf{V}\mathbf{u})^2 }{d_{i} -\lambda}
\right]
$$
where $d_{i}$ are the original eigenvalues of $\mathbf{A}$ and $\mathbf{e}_i$ is the $i$th column of the identity matrix (cf. eq. (5.14)). This bracketed term is called the secular equation and its roots are the eigenvalues of $\mathbf{B}$. Finding these roots can be challenging numerically, but a robust algorithm is implemented in LAPACK in xLAED4.


TITLE: Definition formal group law in the book complex cobordism.... of Doug Ravenel
QUESTION [1 upvotes]: I have read the chapter from the Complex Cobordism.... book of Doug Ravenel.
It is here https://web.math.rochester.edu/people/faculty/doug/mybooks/ravenelA2.pdf.
In the definitions $(A2.1.19)$, page $341$,  it is mentioned that-

If $x$ and $y$ are elements in an $R$-algebra $A$ which also "contains the
  power series $F(x,y)$", let $$x +_F y = F(x,y).$$

This definition seems to be in different language what I know from other sources and $x+_F y=F(x,y)$ is simply giving the group structure.
What does the phrase "contains the power series $F(x,y)$ " mean?
Here $x$ and $y$ are variables from $A$.
I have specifically problem with word $\text{contains}$.
So how does and in what sense  $x$ and $y$ $\text{contains}$ the power series $F(x,y)$  ?

REPLY [2 votes]: It is $A$ which is supposed to contain the power series $F(x,y)$, not $x$ and $y$.  That doesn't really clarify much though--what does it mean for $A$ to contain $F(x,y)$?  Ravenel seems to be using this phrase in an imprecise informal sense, just saying that $A$ is such that it makes sense to evaluate the infinite sum $F(x,y)$ in $A$.  To make this more precise, in practice what he means is that $A$ is complete with respect to some ideal $I$ which contains both $x$ and $y$, so that the power series $F(x,y)$ converges in the $I$-adic topology.  For instance, typically $A$ will be something like a power series ring $B[[t]]$ for some $R$-algebra $B$, and $x$ and $y$ will be elements with no constant term so that any power series in $x$ and $y$ converges in the $t$-adic topology.


TITLE: Proving statement about convergent sequence $(a_n)$ and the sequence $(\max\{a_n,a_n^2\})$
QUESTION [4 upvotes]: Suppose $(a_n)$ is a sequence and $\lim_{n\to\infty} a_n = a$ and let $(b_n)=(\max\{a_n,a_n^2\})$. I have to prove/disprove that:

If $a>1$ then $\lim_{n\to\infty} b_n = a^2$
If $a=1$ then  $\lim_{n\to\infty} b_n = 1$

I believe both are true, but I fail to prove it, although it looks intuitive and easy. Any hints?

REPLY [0 votes]: For $a > 1$:
By the limit definition of $\lim_{n\to\infty}a_n=a$, there is an $N \in \mathbb N$ with
$$n > N \Rightarrow |a_n-a| < \epsilon.$$
for all $\epsilon > 0$. Let $\epsilon = \frac{a-1}{2}$, then $1 < a-\epsilon$,
and therefore, for all $n > N: a_n > 1$.
From this we know, again for all $n > N$, that $a_n^2 > a_n$. Thus, we can conclude that $\lim_{n\to\infty} \max\{a_n, a_n^2\} = \lim_{n\to\infty} a_n^2 = a^2$.
The other case can be solved similarly.


TITLE: Polygon and angles
QUESTION [0 upvotes]: A cyclic polygon is a polygon with vertices upon which a circle $C_0$ can be circumscribed. (All vertices lie on circle $C_0$).
We are given the lengths of the cyclic polygon $\{L_1, L_2,..., L_n\}$. We need to find the coordinates of the vertices $\{(x_1, y_1), (x_2, y_2),...(x_n, y_n)\}$ such that the center of the circle $C_0$ is $(0, 0)$.
Example:
If lengths are $\{2,2,2,2\}$ then one of the possible locations of vertices is
$$ \sqrt2 \, (( -1,1), (-1,1),(1,1),(1,-1)) $$
EDIT1:
Is there Ruler & Compass method to determine its radius and locate the center  ?

REPLY [1 votes]: Find the radius $R$ numerically from
$$ t_1=\sin^{-1} \frac{L_1}{2 R  } \,,\quad  t_2= \sin^{-1 } \frac{L_2}{2 R  }\,,\,\,\dots\,\,, t_n=\sin^{-1 } \frac{L_n}{2 R  }    $$
$$ \pi = t_1+t_2+\dots +t_n$$
Find angle subtended by each sector at center $(t_1,t_2,..).$ Upto rigid rotations/translations of the entire polygon in x-y plane
$$ x_0 = R;\, y_0= 0\,,$$
$$ x_1= R \cos 2 t_1;y_1= R \sin 2 t_1,$$
$$ x_2= R \cos (2 t_1+ 2 t_2) ,\,y2= R \cos (2 t_1+ 2 t_2) \dots$$


TITLE: Information loss in a black hole
QUESTION [5 upvotes]: How does the Holographic Principle help to establish the fact that all the information is not lost in a black hole?

REPLY [0 votes]: I would expect the resolution of this dilemma to hold no relation whatsoever to AdS/CFT, being it specific to anti de Sitter spaces, which makes it irrelevant to our universe (unless someone proves an analog version for de Sitter spaces, which seems unlikely)
see this answer for details about an alternative resolution.


text:
\begin{document}

\title{Approximation with Conditionally Positive Definite Kernels on Deficient Sets}
\author{Oleg Davydov\thanks{University of Giessen, Germany,
\texttt{oleg.davydov@math.uni-giessen.de}}}

\maketitle

\begin{abstract}
Interpolation and approximation of functionals with conditionally positive definite kernels
is considered on sets of centers that are not determining for polynomials. It is shown that polynomial consistency is
sufficient in order to define kernel-based numerical approximation of the functional with usual properties of optimal
recovery. Application examples include generation of sparse kernel-based numerical differentiation formulas for the
Laplacian on a grid and accurate approximation of a function on an ellipse.

\end{abstract}

\section{Introduction}
Let $\Omega$ be a set and $P$ a finite dimensional space of functions on $\Omega$. A function $K:\Omega\times\Omega\to\RR$ is
said to be a \emph{conditionally positive definite kernel with respect to $P$} if for any finite set
$X=\{x_1,\ldots,x_n\}\subset\Omega$ the quadratic form $\sum_{i,j=1}^n c_ic_jK(x_i,x_j)$ is positive
for all $c\in\RR^n\setminus\{0\}$ such that $\sum_{i=1}^n c_ip(x_i)=0$ for all $p\in P$ \cite{Wendland}.

Given data $(x_j,f_j)$, $j=1,\ldots,n$, with $x_j\in \Omega$, $f_j\in\RR$, a sum of the form
\begin{equation}\label{sigma}
\sigma(x)=\sum_{j=1}^n c_j K(x,x_j)+\tilde p,\qquad c_j\in\RR,\quad \tilde p\in P
\end{equation}
can be used to solve the interpolation problem
\begin{equation}\label{intc}
\sigma(x_i)=f_i,\qquad i=1,\ldots,n.
\end{equation}
Moreover, a solution of (\ref{intc}) satisfying the condition
\begin{equation}\label{polyc}
\sum_{j=1}^n c_jp(x_j)=0\quad\hbox{for all } p\in P,
\end{equation}
can always be found \cite[p.~117]{Wendland}. This solution is unique if $X$ is a \emph{determining set} for $P$, that is
$p\in P$ and $p|_X=0$  implies $p=0$.

In meshless finite difference methods, conditionally positive definite kernels with respect to
spaces of polynomials are often used to produce numerical approximations of linear functionals
\begin{equation}\label{numdif}
\lambda f\approx \sum_{i=1}^n w_i f(x_i),\quad w_i\in\RR,
\end{equation}
such as the value $\lambda f=Df(x)$ of a differential operator $D$ applied to a function $f$ at a point
$x\in\Omega$.
If the interpolant $\sigma=\sigma_f$ satisfying (\ref{sigma})--(\ref{polyc}) with $f_i=f(x_i)$ is uniquely defined, then the weights $w_i$
of (\ref{numdif}) can be obtained by the approximation $\lambda f\approx\lambda\sigma_f$, which leads to the conditions
\begin{eqnarray}\label{kere}
\sum_{j=1}^n w_j K(x_i,x_j)+\tilde p(x_i)&=&\lambda'K(x_i),\quad i=1,\ldots,n,\quad\hbox{for some }\tilde p\in P,\\
\label{polye}
\sum_{i=1}^n w_i p(x_i)&=&\lambda p\quad\hbox{for all } p\in P,
\end{eqnarray}
where $\lambda'K:\Omega\time\Omega\to\RR$ is the function obtained by applying $\lambda$ to the first argument of $K$.
The weights $w_i$ are in this case uniquely determined by the conditions (\ref{kere})--(\ref{polye}). In particular, by introducing a basis for the space $P$,
we can write  both (\ref{sigma})--(\ref{polyc}) and (\ref{kere})--(\ref{polye}) as systems of linear equations with the same matrix which is non-singular as soon as
$X$ is a determining set for $P$. Solving this system is the standard way to obtain the weights $w_i$,
see e.g.\ \cite{FFprimer15}. It is demonstrated in \cite{BFFB17} that  the weights satisfying (\ref{kere})--(\ref{polye})
for a polyharmonic kernel $K$ significantly improve the
performance of meshless finite difference methods in comparison to the weights obtained by
unconditionally positive definite kernels such as the Gaussian. In addition, these weights provide optimal recovery of
$\lambda f$ from the data $f(x_i)$, $i=1,\ldots,n$, on spaces of functions of finite smoothness,
see e.g.~\cite[Chapter 13]{Wendland}.

An alternative interpretation of (\ref{kere})--(\ref{polye}) is that the approximation (\ref{numdif}) of $\lambda f$
is required to be exact for all $f=\sigma$ in the form (\ref{sigma})
with coefficients $c_j$ satisfying (\ref{polyc}). Indeed, this can be easily shown
 with the help of the Fredholm alternative for matrices, see Theorem~\ref{exact} below.
In particular, (\ref{polye}) already expresses exactness of (\ref{numdif}) for all elements of $P$.
In the case when $\Omega$ is a domain in $\RR^d$ and $P$ is
a space of $d$-variate polynomials, (\ref{polye}) can be used to obtain error bounds for the numerical differentiation
with weights $w_i$, see e.g.\ \cite{DavySchaback18,DavySchaback19}.

However, exactness (\ref{polye}) for $p\in P$ is sometimes achievable without $X$ being a
determining set for $P$. We then say that $X$ is \emph{$P$-consistent} for $\lambda$. The best known examples are the Gauss quadrature when $\lambda f=\int_a^bf(x)\,dx$ and the five point
stencil for the two-dimensional Laplacian. Moreover, $P$-consistent sets with $n$ significantly smaller than the
dimension of $P$ often can be used for the numerical discretization of the Laplace operator on gridded nodes in irregular
domains, leading to sparser differentiation matrices \cite{D19arxiv}.

In this paper we study numerical approximation formulas (\ref{numdif}) obtained by requiring exactness conditions
(\ref{kere})--(\ref{polye}) on ``deficient'' sets $X$ that are not determining for $P$.

Our main result
(Theorem 2 and Corollary 1) shows
that a unique formula satisfying these conditions exists as soon as $X$ is $P$-consistent. Another consequence is that
the coefficients $c_j$ of the interpolant (\ref{sigma}) are uniquely defined for any $X$ (Corollary 2). Numerical differentiation
formulas obtained in this way  provide optimal recovery on native spaces of the kernels.  We also discuss computational methods for
the weights of the formula (\ref{numdif}) and coefficients of the interpolant (\ref{sigma}). In particular, a null space
method can be used for the saddle point problems  (\ref{kere})--(\ref{polye}) or (\ref{sigma})--(\ref{polyc}) even if in the
case of deficient sets they do not satisfy restrictions usually required in the literature \cite{BGL05}.

In the last section we describe two types of deficient sets that arise naturally in applications. First, deficient
subsets of a grid may be used for numerical differentiation of the Laplacian (Section 3.1). Second, function values and
differential operators on algebraic surfaces, in this case an ellipse, may  be approximated using data  located on the
manifold, which are necessarily deficient sets for polynomials in the ambient space of degree at least the order of the
surface (Section 3.2). In both cases, numerical results demonstrate a robust performance of the suggested numerical methods,
and a reasonable approximation quality of the polyharmonic kernels we employ in the experiments.

\section{Approximation on deficient sets}
We assume that $K:\Omega\times\Omega\to\RR$ is a conditionally positive definite kernel with respect to a linear space $P$ of functions on $\Omega$,
with $\dim P=m$. Let $\{p_1,\ldots,p_m\}$ be a basis for $P$. By writing $\tilde p=\sum_{j=1}^m v_j p_j$, $v_j\in\RR$,
 conditions (\ref{kere})--(\ref{polye}) give rise to a linear system with respect to $w_j$ and $v_j$, in block matrix form,
\begin{equation}\label{kpem}
\left[ \begin{array}{cc}
K_X & P_X  \\
P_X^T & 0 \end{array} \right] \cdot
\left[ \begin{array}{c}
w \\
v\end{array} \right]=
\left[ \begin{array}{c}
a \\
b\end{array} \right],
\end{equation}
where
$$
K_X=[K(x_i,x_j)]_{i,j=1}^n,\quad P_X=[p_j(x_i)]_{i,j=1}^{n,m},$$
$$
w=[w_j]_{j=1}^n,\quad v=[v_j]_{j=1}^m,\quad
a=[\lambda'K(x_i)]_{i=1}^n,\quad b=[\lambda p_j]_{j=1}^{m}.$$
Condition (\ref{polyc}) in matrix form is
$$
P_X^Tc=0,\quad c=[c_j]_{j=1}^{n},$$
that is $c$ belongs to the null space $N(P_X^T)$ of $P_X^T$. Since
$$
P_Xv=[\tilde p(x_i)]_{i=1}^{n},\quad \tilde p=\sum_{j=1}^m v_j p_j,$$
we see that the condition that $X$ is a determining set for $P$ is equivalent to
$N(P_X)=0$.

We  show that  the conditions (\ref{kere})--(\ref{polye})
express the exactness of (\ref{numdif}) for the sums $\sigma$ conditional on (\ref{polyc}), even when $X$ is
a \emph{deficient set} for $P$, that is $N(P_X)\ne0$. Recall that this condition is equivalent to $R(P^T_X)\ne\RR^m$,
where $R(A)$ denotes the range of a matrix $A$.

\begin{theorem}\label{exact}   Let $X=\{x_1,\ldots,x_n\}\subset\Omega$. An approximation formula (\ref{numdif})  satisfies the exactness condition
$\lambda \sigma= \sum_{i=1}^n w_i \sigma(x_i)$ for all
sums $\sigma$ in the form (\ref{sigma}) with coefficients $c_j$ satisfying (\ref{polyc}) if and only if (\ref{kere})--(\ref{polye}) holds
for the weights  $w_i$, $i=1,\ldots,n$.
\end{theorem}

\begin{proof} The exactness condition is
$$
\sum_{j=1}^n c_j \lambda'K(x_j)+\lambda p= \sum_{j=1}^n c_j\sum_{i=1}^n w_i K(x_i,x_j)+\sum_{i=1}^n w_i p(x_i)$$
for all $c=[c_j]_{j=1}^{n}$ satisfying (\ref{polyc}) and all $p\in P$. In particular, for $c=0$ we obtain (\ref{polye}), and
rewrite the condition as
$$
\sum_{j=1}^n c_j \Big(\lambda'K(x_j)-\sum_{i=1}^n w_i K(x_i,x_j)\Big)=0\quad\hbox{for all } c\in N(P_X^T).$$
By the Fredholm alternative for matrices this is equivalent to
$$
\Big[\lambda'K(x_j)-\sum_{i=1}^n w_i K(x_i,x_j)\Big]_{j=1}^n\in R(P_X),$$
which is in turn equivalent to (\ref{kere}) in view of the symmetry of the
kernel $K$. \qed
\end{proof}

Linear systems of the type (\ref{kpem}) have been extensively studied under the name of equilibrium equations
\cite[Section 4.4.6]{GoVanL96} or saddle point problems \cite{BGL05} because they arise in many application areas.
Our approach below is a variation of the null space techniques described in \cite[Section 6]{BGL05}. However,
usual assumptions that $n\ge m$, $K_X$ is positive semidefinite and $P_X$ has full column rank are not satisfied
in our case of interest.

As long as $X$ is a deficient set,  $R(P^T_X)\ne\RR^m$ and hence the solvability of $P^T_Xw=b$  cannot be
guaranteed for all $b$. Nevertheless, should this last equation
have a solution for $w$, there is a unique weight vector $w$ satisfying (\ref{kpem}).

\begin{theorem}\label{weights} There is a unique vector $w$ satisfying (\ref{kpem}) if and only if $b\in R(P^T_X)$.
\end{theorem}

\begin{proof} The necessity of the condition $b\in R(P^T_X)$ is obvious. To show the sufficiency, assume that $P^T_Xw_0=b$ for some $w_0\in\RR^n$. Then the solution $w$
must satisfy $P^T_X(w-w_0)=0$ if it exists, so we look for $w$ in the form
$$
w=w_0+\tilde u,\quad \tilde u\in N(P^T_X).$$
Let $M$ be a matrix whose columns form a basis for $N(P^T_X)$. Then $\tilde u=Mu$ for some vector $u$,
and we may write (\ref{kpem}) equivalently as a linear system with respect to $u$ and $v$,
\begin{equation}\label{veq}
K_XMu+P_Xv=a-K_Xw_0.
\end{equation}
Since $M^TP_X=0$, it follows that
\begin{equation}\label{ueq}
M^TK_XMu=M^T(a-K_Xw_0).
\end{equation}
Since $K$ is conditionally positive definite, the matrix $M^TK_XM$ is positive definite, and hence there is a unique
$u$ determined by the last equation. The existence of some $v\in\RR^m$ such that
(\ref{veq}) holds is equivalent to the claim that $K_XMu-a+K_Xw_0\in R(P_X)$. This claim
follows from  the Fredholm alternative since (\ref{ueq}) implies that $K_XMu-a+K_Xw_0\perp N(P^T_X)$.
Thus, $u$ and $v$ satisfying (\ref{veq}) exist, and $u$ is uniquely determined. Then $w=w_0+Mu$ is a unique
vector satisfying (\ref{kpem}). \qed
\end{proof}

\begin{remark}\label{weightsg}
Theorem~\ref{weights} is valid for any linear system (\ref{kpem}) with arbitrary matrices $A$ and $B$ replacing $K_X$
and $P_X$, respectively, and arbitrary $a,b$, as soon as $A$ is definite on $N(B^T)$, that is $x^TAx\ne0$ for all
$x\in N(B^T)\setminus\{0\}$. Indeed, this condition implies that $M^TAM$ is non-singular and hence the argument in the
proof goes through.
\end{remark}

As long as the condition $b\in R(P^T_X)$ is satisfied, the weight vector $w$ may be found by any solution method applicable to the system
(\ref{kpem}), for example via the pseudoinverse of its matrix when it is singular. Alternatively, we may use the null space matrix $M$
of the above proof and find $w$ from the linear system
\begin{equation}\label{kpem1}
\left[ \begin{array}{c}
M^TK_X  \\
P_X^T  \end{array} \right]
w=
\left[ \begin{array}{c}
M^Ta \\
b\end{array} \right],
\end{equation}
which is in general overdetermined but
has full rank because its solution $w$ is unique. Indeed, any solution $w$ of (\ref{kpem1}) satisfied (\ref{kpem}) for some
$v$ since $M^TK_Xw=M^Ta$ implies $K_Xw-a\perp N(P^T_X)$ and thus $K_Xw-a\in R(P_X)$. We refer to
 \cite[Section 6]{BGL05} for the computational methods for the null space matrix $M$.
 One obvious possibility is to employ the right singular vectors of $P_X$, see
 \cite[Eq.\ (2.5.4)]{GoVanL96}. Should $v$ be needed, it can be computed
as a solution of the consistent linear system
\begin{equation}\label{vo}
P_Xv=a-K_Xw.
\end{equation}
For example we can use
\begin{equation}\label{v}
v=P_X^+(a-K_Xw),
\end{equation}
where $P_X^+$ denotes the Moore-Penrose pseudoinverse
of $P_X$, is the unique $v$ with the smallest 2-norm.

We formulate two immediate consequences of Theorem~\ref{weights} for the numerical approximation of functionals and for the interpolation. Note that
(\ref{sigma})--(\ref{polyc}) can be written in the form (\ref{kpem}) with $w$ replaced by $c$, $a=[f_i]_{i=1}^n$, and $b=0$. In particular, the condition
$0\in R(P^T_X)$ of Theorem~\ref{weights} is trivially satisfied.

\begin{corollary}\label{ndw}
For any $X$ and $\lambda$ there is a unique numerical approximation formula (\ref{numdif}) satisfying
(\ref{kere})--(\ref{polye}) as soon as (\ref{polye}) is solvable.
\end{corollary}

\begin{corollary}\label{intw}
For any data $(x_j,f_j)$, $j=1,\ldots,n$, one or more interpolants $\sigma$ satisfying (\ref{sigma})--(\ref{polyc}) exist and their coefficients $c_j$,
$j=1,\ldots,n$, are uniquely determined.
\end{corollary}

Thanks to Theorem~\ref{exact} we also obtain the property known for the case of a determining set $X$ that the approximation
$\lambda f\approx\sum_{i=1}^n w_i f(x_i)$ can be found by requiring $\lambda f\approx\lambda\sigma$ for any interpolant
$\sigma$ of Corollary~\ref{intw} with $f_i=f(x_i)$.

Looking specifically at numerical differentiation, consider the case when $\Omega=\RR^d$, $\lambda f=Df(x)$ for a linear
differential operator $D$ of order $k$ and $x\in\RR^d$, and $P=\PP^d_q$, the space of $d$-variate polynomials of total order at most $q$
(that is, total degree at most $q-1$) for some $q\in\NN$. Any kernel $K$ that is conditionally positive definite with respect to $P$
generates a native semi-Hilbert space $F(K,P)$ of functions on $\Omega$ with null space $P$, see e.g.~\cite{Wendland}. By inspecting the
arguments in Section~2 and Lemma~6 of \cite{DavySchaback16}, we see that thanks to Corollary~\ref{ndw}, the optimal recovery property of the weights $w_i$ defined by
(\ref{kere})--(\ref{polye}) remains valid for deficient sets $X=\{x_1,\ldots,x_n\}$.
More precisely,
the worst case error of numerical differentiation formulas on the unit ball of $F_q(K):=F(K,\PP^d_q)$,
$$
E(u):=\sup_{f\in F_q(K)\atop \|f\|_{F_q(K)}\le 1}\big|Df(x)-\sum_{i=1}^n u_i f(x_i)\big|,$$
can be computed as
\begin{equation}\label{wcerror}
\begin{array}{rcl}
  E^2(u)&=& \displaystyle D'D''K(x,x)-\sum_{i=1}^n u_i\big(D'K(x,x_i)+D''K(x_i,x)\big)\\[4pt]
  &&\displaystyle +\sum_{i,j=1}^n u_iu_jK(x_i,x_j).
\end{array}
\end{equation}
The weight vector $w$ has the \emph{optimal recovery} property in the sense that it  satisfies
\begin{equation}\label{optrec}
E(w) =\min\big\{E(u):u\in\RR^n,\; Dp(x)=\sum_{i=1}^n u_i p(x_i)\;\hbox{ for all }p\in \PP^d_q\big\}
\end{equation}
as soon as the mixed partial derivatives of $K$ exist at $(x,x)\in\RR^d\times\RR^d$ up to the order $k$ in each of both
$d$-dimensional variables, and
$X$ is such that there exists a vector $u\in\RR^n$ with polynomial exactness
$$
Dp(x)=\sum_{i=1}^n u_i p(x_i)\;\hbox{ for all }p\in \PP^d_q.$$
We use here $D'$ and $D''$ to indicate when $\lambda f=Df(x)$ acts on the first, respectively, the second argument of $K$.

Note that the equality-constraned quadratic minimization problem (\ref{optrec}) provides an alternative way of computing
the optimal weight vector on a deficient set.
By Theorem~\ref{weights} we know that its solution $w$
is unique as soon as the feasible region is non-empty.

\section{Examples}
In this section we illustrate Corollaries \ref{ndw} and \ref{intw} on particular examples where deficient sets $X$ seem
useful.

We consider the \emph{polyharmonic kernels} $K_{s,d}:\RR^d\times \RR^d\to\RR$, defined for all real
$s>0$ by $K_{s,d}(x,y)=\varphi_{s}(\|x-y\|_2)$, where
\begin{equation}\label{polyh}
\varphi_{s}(r):=(-1)^{\lfloor s/2 \rfloor +1}
\left\{
\begin{array}{ll}
r^s\log r, &\hbox{ if $s$ is an even integer, }\\
r^s,& \hbox{ otherwise. }
\end{array}
\right.
\end{equation}
The kernel $K_{s,d}$ is conditionally positive definite with respect to $\PP^d_q$ for all
$q\ge\lfloor s/2 \rfloor +1$. We cite \cite{Wendland,DavySchaback19} and references therein
for further information on these kernels.
If $m=(s+d)/2$ is an integer and  $q$ is chosen equal to $m$, then
the native space $F_m(K_{s,d})$ coincides with the Beppo-Levi space $BL_{m}(\RR^d)$, see
\cite[Theorem 10.43]{Wendland}. For any $q\ge \lfloor s/2 \rfloor +1$, the space $F_q(K_{s,d})$ can be described
with the help of the generalized Fourier transforms as in \cite[Theorem 10.21]{Wendland}.
By the arguments in Section~2, formulas (\ref{wcerror}) and (\ref{optrec}) apply to  $K_{s,d}$ as soon as $s>2k$, where $k$ is
the order of the differential operator $D$.

\subsection{Numerical differentiation of Laplacian on a grid}\label{Lgrid}
We are looking for numerical differentiation formulas of the type
\begin{equation}\label{ndL}
\Delta f(0)\approx \sum_{\alpha\in Z_{d,r}}w_\alpha f(\alpha),
\quad Z_{d,r}:=\{\alpha\in\ZZ^d:\|\alpha\|_2\le r\},\quad r>0,
\end{equation}
where $\Delta$ is the Laplacian
$\Delta f=\sum_{i=1}^d{\partial^2 f}/{\partial x_i^2}$.
The set $Z_{d,r}$ for $0\le r<1$ consists of the origin only and hence is not useful for the approximation of the Laplacian.
For $r=1$ we have
$Z_{d,1}=\{0,\pm e_1,\ldots \pm e_d\}$,
where $e_i$ is the $i$-th unit vector in $\RR^d$,
and
\begin{equation}\label{star}
\Delta f(0)\approx -2df(0)+\sum_{i=1}^df(e_i)+\sum_{i=1}^df(-e_i)
\end{equation}
is the classical numerical differentiation formula exact for all cubic polynomials $f=p\in\PP^d_4$. Hence
(\ref{polye}) is solvable for all $X=Z_{d,r}$, $r\ge1$, if $P=\PP^d_4$.

According to Corollary \ref{ndw}, we have computed the unique weights of the formula (\ref{ndL})
satisfying (\ref{kere})--(\ref{polye})
for the kernel $K_{7,d}$, $P=\PP^d_4$ and $X=Z_{d,r}$
for all $d=2,\ldots,5$ and $r=1,\sqrt{2},\sqrt{3},2$. As a basis for $\PP^d_4$ we choose ordinary monomials. However,
the computation is performed using the rescaling of $X$ as $X/r$ according to the suggestion in \cite[Section 6.1]{DavySchaback18}

\begin{table}[h!]
\label{Lgridt}
\caption{Numerical differentiation of Laplacian on a grid: $|X|$ is the cardinality of $X$, $dN=\dim N(P_X)$, $dNt=\dim N(P_X^T)$, $E(w)$
is given by (\ref{wcerror}), and $cond$ is the condition number of the matrix of
(\ref{kpem1}).}
\begin{center}
\begin{tabular}{|c@{\enskip}|@{\enskip}r@{\enskip}|@{\enskip}r@{\enskip}|
                @{\enskip}r@{\enskip}|@{\enskip}r@{\enskip}|@{\enskip}r@{\enskip}|@{\enskip}c@{\enskip}|}
\hline
\multicolumn{7}{|c|}{\rule{0pt}{12pt}$d=2$, $X=Z_{2,r}$, $\dim \PP^2_4=10$}\\[2pt]
\hline\rule{0pt}{12pt}
$r$ & $|X|$ & $dN$ & $dNt$ & $E(w)$ & $\|w\|_1$ & $cond$ \\[2pt]
\hline\rule{0pt}{12pt}
1          &  5 &  5 & 0 & 13.4 & 8.0   & - \\
$\sqrt{2}$ &  9 &  2 & 1 & 10.6 & 13.5  & 2.0e\spl02 \\
$\sqrt{3}$ &  9 &  2 & 1 & 10.6 & 13.5  & 2.0e\spl02  \\
2          & 13 &  0 & 3 & 7.4  & 11.8  & 3.9e\spl02 \\[2pt]
\hline
\hline
\multicolumn{7}{|c|}{\rule{0pt}{12pt}$d=3$, $X=Z_{3,r}$, $\dim \PP^3_4=20$}\\[2pt]
\hline\rule{0pt}{12pt}
$r$ & $|X|$ & $dN$ & $dNt$ & $E(w)$ & $\|w\|_1$ & $cond$ \\[2pt]
\hline\rule{0pt}{12pt}
1  & 7  &  13   &  0  &   17.2    &    12.0 & - \\
$\sqrt{2}$ & 19   &   4    &  3    &  12.3   &  22.7   &   3.8e\spl02   \\
$\sqrt{3}$ & 27   &  3  &  10  &   12.4  &  24.8  &  2.5e\spl03   \\
2          & 33    &  0   &  13   &   9.0   &   30.1   &  5.1e\spl03 \\[2pt]
\hline
\hline
\multicolumn{7}{|c|}{\rule{0pt}{12pt}$d=4$, $X=Z_{4,r}$, $\dim \PP^4_4=35$}\\[2pt]
\hline\rule{0pt}{12pt}
$r$ & $|X|$ & $dN$ & $dNt$ & $E(w)$ & $\|w\|_1$ & $cond$ \\[2pt]
\hline\rule{0pt}{12pt}
1  & 9   &   26   &    0   &    20.8     &     16.0  & - \\
$\sqrt{2}$ & 33   &  8  &   6  &    14.0  &  31.8  &  5.7e\spl02  \\
$\sqrt{3}$ &  65  &   4  &  34  &   13.9 &  39.7  &  6.9e\spl03  \\
2          & 89  &   0  &  54   &  10.4  &  40.5  &   3.1e\spl04  \\[2pt]
\hline
\hline
\multicolumn{7}{|c|}{\rule{0pt}{12pt}$d=5$, $X=Z_{5,r}$, $\dim \PP^5_4=56$}\\[2pt]
\hline\rule{0pt}{12pt}
$r$ & $|X|$ & $dN$ & $dNt$ & $E(w)$ & $\|w\|_1$ & $cond$ \\[2pt]
\hline\rule{0pt}{12pt}
1  & 11  &   45  &     0 &    24.2   &      20.0 & - \\
$\sqrt{2}$ & 51  &  15   &  10  &  15.6  &   40.9  &   7.7e\spl02  \\
$\sqrt{3}$ & 131  &    5  &    80  &   15.4  &   56.4  &    1.3e\spl04   \\
2          & 221  &   0  &  165  &  11.7  &  55.0  &   9.0e\spl04  \\[2pt]
\hline
\end{tabular}
\end{center}
\end{table}

Table~1 presents information about the
size $|X|$ of $X$, dimensions of the null spaces of $P_X$ and $P_X^T$,  the optimal recovery error (\ref{optrec})
on $F_4(K_{7,d})$, the stability constant of the weight vector $\|w\|_1=\sum_{i=1}^n|w_i|$, and the condition number $cond$
of the system (\ref{kpem1}) we solved in order to compute the weights for $r\ne1$. A smaller optimal recovery error indicates
better approximation quality, whereas $\|w\|_1$ and $cond$ measure the numerical stability of the formulas.
Note that $\dim N(P_X^T)=0$ for $r=1$, which means that (\ref{star}) is the only
solution of (\ref{polye}) in this case, and hence it provides the optimal recovery on $F_4(K_{7,d})$.
For $r=2$ we have $\dim N(P_X)=0$ and it follows that $Z_{d,2}$ is a determining set for $\PP^d_4$. For $r=\sqrt{2},\sqrt{3}$ we obtain
examples of optimal recovery weights on deficient sets, with $\dim N(P_X)$ being the dimension
of the affine space of weight vectors satisfying the polynomial exactness condition (\ref{polye}).
These new weights seem to provide a meaningful choice for the two intermediate sets
between the classical polynomial stencil on  $Z_{d,1}$, and the standard polyharmonic weights on the determining set
$Z_{d,2}$. Indeed, as expected, the optimal recovery error $E(w)$ reduces when $|X|$ increases, whereas the stability
constant and condition numbers tend to increase.

\subsection{Interpolation of data on ellipse}\label{ellipse}

In this example we compute the kernel interpolant (\ref{sigma}) satisfying (\ref{polyc}) and $\sigma(x_i)=f(x_i)$, $i=1,\ldots,n$,
for the test function $f:\RR^2\to\RR$ given by
$$
f(x,y)=\sin(\pi x)\sin(\pi y).$$
We use the polyharmonic kernels $K_{s,2}$ and $P=\PP^2_q$ for the pairs
$$
(s,q)=(5,3),(7,4),(9,5),$$
and choose sets $X$ with $n=|X|=5\cdot 2^i$, $i=0,1,\ldots 6$, on the ellipse $\cal E$ with half-axes $a=1$ and $b=0.75$ centered at the origin.
The sets are obtained by first choosing parameter values $t_i=ih$, $i=0,\ldots,n-1$, where $h=2\pi/n$, then adding to each
$t_i$ a random number $\epsilon_i$ with uniform distribution in the interval $[-0.3h,0.3h]$, and selecting
$x_i=\big(a\cos(t_i+\epsilon_i),b\sin(t_i+\epsilon_i)\big)$. The first two sets used in our experiments are shown in Fig.~1.

\begin{figure}[htbp!]
\begin{center}
\hspace*{-10pt}\includegraphics[width=120pt]{5points.eps}\qquad\qquad\includegraphics[width=120pt]{10points.eps}
\end{center}
\caption{Interpolation of data on ellipse: The sets $X$ with $|X|=5$ (left) and 10 (right).}
\end{figure}

Since $X\subset\cal E$ and there exists a nontrivial quadratic polynomial $p\in \PP^2_3$
that vanishes on $\cal E$,
$$
p(x,y)=x^2/a^2+y^2/b^2-1,$$
all sets $X$ are deficient for $\PP^2_q$, $q\ge3$. Nevertheless,
according to Corollary~\ref{intw}, the coefficients $c_j$ of the interpolant $\sigma$ in (\ref{sigma})
are uniquely determined and can be computed by solving the system (\ref{kpem1}). A polynomial
$\tilde p$ of (\ref{sigma}), $\tilde p=v_1p_1+\cdots +v_m p_m$, can be computed by solving (\ref{vo}). We will use the
pseudoinverse as in (\ref{v}), but in fact the polynomial $\tilde p$ is uniquely determined on the ellipse $\cal E$ as soon as
$n\ge 2q-1$. Indeed, if both $\tilde p_1,\tilde p_2\in\PP^2_q$ satisfy (\ref{vo}), and
$\tilde p_1-\tilde p_2=u_1p_1+\cdots +u_m p_m$, then $P_Xu=0$, which implies $(\tilde p_1-\tilde p_2)|_X=0$. Hence
$x_1,\ldots,x_n$ are intersection points of the ellipse and the zero curve of $\tilde p_1-\tilde p_2$, an algebraic curve of order
$q-1$. By Bezout theorem, this curve must contain $\cal E$ as soon as $n>2(q-1)$, which implies
$\tilde p_1|_{\cal E}=\tilde p_2|_{\cal E}$.

Thus, $\sigma|_{\cal E}$ is well defined as soon as $|X|\ge5$ for $q=3$,
$|X|\ge7$ for $q=4$ and $|X|\ge9$ for $q=5$. We are using $\sigma(x)$ as an approximation of $f(x)$ for $x\in\cal E$.
Moreover, we also approximate the surface gradient
$$
\nabla_{\cal E}f(x):=\nabla f(x)-\nabla f(x)^T\nu(x)\cdot\nu(x),\quad x\in \cal E,$$
where $\nu(x)$ is the unit outer normal to $\cal E$ at $x$. The surface gradient $\nabla_{\cal E}f(x)$ can either be
approximated by $\nabla_{\cal E}\sigma(x)$, or by using a numerical differentiation formula (\ref{numdif}),
with the same result. For each $X$, except of $|X|=5$ for $q=4,5$, we evaluated the maximum error of the function
and surface gradient,
\begin{eqnarray*}
max&=&\max_{x\in\cal E}|f(x)-\sigma(x)|,\\
maxg&=&\max_{x\in\cal E}\|\nabla_{\cal E}f(x)-\nabla_{\cal E}\sigma(x)\|_2,
\end{eqnarray*}
by sampling the parameter $t$ of the ellipse $\big(a\cos t,b\sin t\big)$, $t\in[0,2\pi)$, equidistantly
with the step $h/20$. The results are presented in Table 2, where we also included
the condition number $cond$ of the system (\ref{kpem1}). Note that we translate and scale $X$ using its center of gravity
$z$, and perform the computations with $K_{s,2}$ and ordinary monomials on the set
$Y=(X-z)/\max\{\|x_i-z\|_2:i=1,\ldots,n\}$, in order to improve the condition numbers.
The results in the table demonstrate a fast convergence of the interpolant $\sigma$ and its surface gradient to $f$ and
$\nabla_{\cal E}f$. Note that although the condition numbers become high when the set $X$ fills the ellipse more densely,
they are moderate in comparison to significantly worse conditioned matrices arising if
infinitely smooth kernels such as the Gaussian $K_{G,\varepsilon}(x-y)=\exp(-\varepsilon\|x-y\|_2^2)$, $\varepsilon>0$,
are employed, see also discussions in \cite[Section 5.1.5]{FFprimer15}.

\begin{table}[htbp!]
\label{ellipset}
\caption{Interpolation of a test function on an ellipse using the kernel $K_{s,2}$ and $P=\PP^2_q$: $|X|$ is the cardinality of $X$,
$max$ and $maxg$ are the maximum errors of the function or  the surface gradient, respectively, and $cond$ is the condition number of the matrix of
(\ref{kpem1}).}
\begin{center}
\begin{tabular}{|r@{\enskip}|@{\hspace{3pt}}c@{\hspace{3pt}}|@{\hspace{3pt}}c@{\hspace{3pt}}|@{\hspace{3pt}}c@{\hspace{3pt}}|
                @{\hspace{3pt}}c@{\hspace{3pt}}|@{\hspace{3pt}}c@{\hspace{3pt}}|@{\hspace{3pt}}c@{\hspace{3pt}}|
                @{\hspace{3pt}}c@{\hspace{3pt}}|@{\hspace{3pt}}c@{\hspace{3pt}}|@{\hspace{3pt}}c@{\hspace{3pt}}|}
\hline
&\multicolumn{3}{c|}{\rule{0pt}{12pt}$s=5$, $q=3$}&\multicolumn{3}{c|}{\rule{0pt}{12pt}$s=7$, $q=4$}
&\multicolumn{3}{c|}{\rule{0pt}{12pt}$s=9$, $q=5$}\\[2pt]
\hline\rule{0pt}{12pt}
$|X|$ & $max$ & $maxg$  & $cond$ & $max$ & $maxg$  & $cond$ & $max$ & $maxg$  & $cond$\\[2pt]
\hline\rule{0pt}{12pt}
5  &  8.3e\sml01   &   2.5e\spl00  &    4.7e\spl00 & -    &        -   &  - & -    &   -  &   -\\
10 & 2.5e\sml01  &  9.9e\sml01  &  3.0e\spl02 & 1.8e\sml01  &   7.9e\sml01  &   1.9e\spl02 & 1.6e\sml01  &   6.9e\sml01 &    2.3e\spl02\\
20 & 2.9e\sml03  &  2.0e\sml02  &  2.3e\spl04 & 1.6e\sml03  &   1.1e\sml02  &   9.8e\spl04 & 1.6e\sml03  &   1.5e\sml02  &   2.0e\spl05\\
40 & 4.6e\sml05  &  6.9e\sml04  &  2.5e\spl06 & 2.2e\sml06  &   3.6e\sml05  &   5.3e\spl07 & 6.1e\sml07  &   1.4e\sml05  &   6.3e\spl08\\
80 &  1.0e\sml06 &   3.1e\sml05 &   2.4e\spl08 & 1.4e\sml08  &   3.5e\sml07  &   2.3e\spl10 & 4.2e\sml10  &   1.5e\sml08  &   1.2e\spl12\\
160 &  2.2e\sml08  &  1.2e\sml06  &  1.2e\spl10 & 7.5e\sml11  &   4.2e\sml09  &   4.8e\spl12 & 8.1e\sml12 &    1.8e\sml09  &   4.6e\spl15\\
320 &   2.7e\sml10 &   3.1e\sml08  &  9.2e\spl11 &  1.0e\sml12 &    2.2e\sml10 &   2.9e\spl15 & 9.1e\sml12 &   4.9e\sml10 &   5.8e\spl17\\[2pt]
\hline
\end{tabular}
\end{center}
\end{table}

\bibliographystyle{abbrv}

\bibliography{bibl}

\end{document}

config: arxiv


TITLE: The cartesian form of a complex number with high power index
QUESTION [0 upvotes]: In the example I have : write $z^{2018}$ in its cartesian form .
$z= \frac{\sqrt 2}{2}(1-i)$
What are the steps that I should follow to solve such thing?
(HINT in the bottom of the page : remember that 2018 = 2016 + 2 = 8 ⋅ 252 + 2)

REPLY [0 votes]: If you're asked to compute $z^n$, always work in polar form. If you are asked to give the answer in Cartesian form, that's no problem; just convert at the end. We have $z=e^{-\pi i/4}$ (the modulus is $1$, but we'd still succeed even if it weren't). Thus $z^8=1$. That's the point of the hint: $z^{2018}=z^2=e^{-\pi i/2}=-i$.


TITLE: Rotation of rotating axis
QUESTION [0 upvotes]: I was recently solving a problem which had rotation of rotating axis. The answer was pretty simple: just vector addition of their angular velocities. After searching up a bit about rotation of axis of rotation, I came across Euler rotational theorem. But I was a bit confused with the statement that the resultant axis of rotation is not necessarily fixed and can change with time. What does that even mean? The theorem clearly states that there can be only one axis of rotation, but if that axis is itself changing, won't it result in some new axis of rotation and so on? I know I am missing something but have no idea what. (Please try to keep the language simple as I am a high school student.)

REPLY [1 votes]: It is a consequence of the hypothesis of a rigid body. A simple example is a dumbell, with two masses $M$ linked by a rod with negligible mass compared to $M$.
For an observer in the center of mass, or both masses are at rest, or if they move, its instantaneous velocity must be perpendicular to the rod and one opposite to the other (otherwise its relative distance changes and the body is not rigid). But the path followed by the masses can be any curve, since that kinematical constraint is fulfilled, what means any path in a sphere centered in the COM.
In this example, it can only be achieved by applying an external torque. Without it, the movement is a constant rotation in the same plane. But for a general geometry, an external torque is not required for a non planar path.


TITLE: Conditional card drawing probability programming question
QUESTION [0 upvotes]: Mary has a deck of $x$ cards of only two types. There are $y$ cards of the first type and $z$ cards of the second type.
If Mary draws $n$ cards before Sarah draws $m$ cards from the same deck (without replacement of cards), what are the chances of Mary having at least a quantity $q$ of the first type of cards if she draws another $t$ cards from the deck?
I am thinking that this question could be solved with the following function:
$$ \sum_{k=q_2}^t \sum_{j=0}^m \sum_{i=q_1}^n \left ( \frac{\binom{y}{i} \cdot \binom{z}{n-i}}{\binom{x}{n}} \right ) \left ( \frac{\binom{y-i}{j} \cdot \binom{x-y+i-n}{m-j}}{\binom{x-n}{m}} \right ) \left ( \frac{\binom{y-i-j}{k} \cdot \binom{x-y+i-n+j-m}{t-k}}{\binom{x-n-m}{t}} \right ) $$
in all cases in which $q_1 + q_2\geq q$.
As you can see, the problem is that multiple summation functions cannot calculate conditional probability because they do not multiply each new case by the previous cases from which it is conditional upon.
Any way you can define a new function for the benefit of all humanity?

REPLY [1 votes]: You're severely overthinking this. Mary draws $n+t$ cards from a deck of $x$ cards that contains $y$ cards of the first type. Then the probability that she has at least $q$ cards of the first type is
$$
\sum_{r=q}^{n+t}\frac{\binom yr\binom{x-y}{n+t-r}}{\binom x{n+t}}\;.
$$


TITLE: open problems regarding functions
QUESTION [2 upvotes]: I am looking for some open problems regarding functions. Problems like,
Whether a function satisfying some properties say, X,Y,Z, exists or not, is unknown.
Like there is no function $f(x)$ such that $f'(x)=h(x)$ where  $h(x)=0$ if $x<0$ and $h(x)=1$ if $x\geq 0$.
Or if $J=\mathbb{R} \setminus \mathbb{Q}$ denote the set of irrational numbers. There is no continuous map $f: \mathbb{R} \rightarrow \mathbb{R}$ such that $f(\mathbb{Q}) \subseteq J$ and $f(J) \subseteq \mathbb{Q}$.
What are some interesting properties for which researchers are looking to find mappings that satisfies them.

REPLY [1 votes]: At the Open Problem Garden, Andreas Rudinger has posted this question: Give a necessary and sufficient condition on the sequence $a_n$ such that the power series $\sum_{n=0}^{\infty}a_nx^n$ is bounded for all real $x$.


TITLE: Find how many real positive numbers, a, b, c, exist, such that they form an ordered pair (a,b,c), satisfying the following equations.
QUESTION [0 upvotes]: The equations are:
$ [a]bc =3 $,
$ a[b]c = 4 $,
$ ab[c] = 5 $,
I tried to assume limits of values of a,b, and c, but it is not working...
Neither is working the division or multiplication of things...
Please help

REPLY [0 votes]: Notice that $[a][b][c] \leq [a]bc = 3$, and none of $[a],[b],[c]$ can be zero. Thus $[a][b][c] \in \{1,2,3\}$. So the only possibilities are

All of $[a],[b],[c]$ are $1$
Two of them are $1$ and one of them is $2$
Two of them are $1$ and one of them is $3$.

Consider cases based on the value of $[a]$. If $[a]=3$, then the first equation implies $bc=1$. But since $b,c \geq 1$, in fact $b=c=1$. But then the second equation implies $a=4$, a contradiction.
If $[a]=2$, then the first equation implies $bc= \frac{3}{2}$. Since $b,c \geq 1$, we have $b \leq bc = \frac{3}{2}$ and $c \leq bc = \frac{3}{2}$. Thus $[b]=[c]=1$. Then the third equation implies $ab=5$, yet we know $a <3$ (since $[a]=2$) and $b \leq \frac{3}{2}$, so this is impossible.
The the only possibility is $[a]=1$. From the bullet points above, we know at least one of $[b]$ or $[c]$ must also be $1$. We also know $bc=3$ from the first equation.
Say we have $[a]=[b]=1$. The second equation implies $ac=4$, and since $a<2$ we have $c>2$. The first equation implies $bc=3$. Dividing $ac$ by $bc$, we have $a/b=ac/bc=4/3$. So equation $3$ becomes
$$ \frac{4}{3}b^2[c]=5.$$
If $[c]=2$, then this implies $b^2=15/8$, so $b=\sqrt{15/8}$, $a= \frac{4}{3}\sqrt{15/8}$, and $c=\sqrt{24/5}$. If $[c]=3$, then this implies $b^2=\frac{5}{4}$, so $b=\sqrt{5/4}$, $a = \frac{4}{3}\sqrt{5/4}$, and $c=3/\sqrt{5/4}<3$, a contradiction.
If instead we have $[a]=[c]=1$, then the third equation implies $ab=5$, and since $a<2$ we have $b>5/2$. The first equation also implies $bc=3$. Dividing $ab$ by $bc$, we have $a/c=ab/bc = 5/3$. So the second equation becomes
$$\frac{5}{3}c^2[b]=4.$$
If $[b]=2$, this implies $c^2 = \frac{6}{5}$, so $c=\sqrt{6/5}$, $a = \frac{5}{3}\sqrt{6/5}$, and $b = \sqrt{15/2}$. If instead $[b]=3$, then this implies $c^2 = \frac{4}{5}$, but then $c<1$, a contradiction.
So there are two solutions:

$a=\frac{4}{3}\sqrt{\frac{15}{8}} = \sqrt{\frac{10}{3}}$
$b =\sqrt{15}{8}=\frac{1}{2}\sqrt{\frac{15}{2}}$
$c= \sqrt{\frac{24}{5}}=2\sqrt{\frac{6}{5}}$

and

$a = \frac{5}{3}\sqrt{\frac{6}{5}}=\sqrt{\frac{10}{3}}$
$b= \sqrt{\frac{15}{2}}$
$c = \sqrt{\frac{6}{5}}$