TITLE: Output of $e^{jw_0n}$ using transfer function $H(e^{jw})$
QUESTION [0 upvotes]: As you can see in the picture, they simply multiplied the input in the $n$ domain with the Transfer function in the $w$ domain, to get the output in the $n$ domain. That's what they did, right?
This doesn't make sense to me. The proper way of doing this is to compute discrete time fourier transform of the input, multiply it with the transform of the transfer function and then do inverse transform.
The reason given is that 'complex exponential are eigensignals'. I have a rough idea about eigenvectors (that they only get scaled on transformations). So I guess something like that is happening here. But the problem is that integral transforms involve change of variable instead of just scaling.

REPLY [1 votes]: This comes from the definition of a transfer function. An LTI system $H$ is usually characterized by its impulse response, $h[n]$, but the question is, why?
As you know the impulse response is simply $H(\delta[n])$. In discrete time, we use the Kronecker deltas as our basis. For an LTI system, we can use the resolution of identity to find
$$H(x[n]) = H\left(\sum_{k\in\mathbb{Z}}x[k]\delta[n-k]\right) = \sum_{k\in\mathbb{Z}} x[k]H(\delta[n-k]) = \sum_{k\in\mathbb{Z}} x[k]h[n-k] \equiv (x\star h)[n]$$
But let's consider another basis, namely the complex exponential basis, $\{e^{j\omega n}\}$. These guys are the Fourier transform of the Kronecker delta basis, $\{\delta[n-k]\}$. Applying the system to each of these basis vectors individually:
$$H\left(e^{j\omega n}\right) = \sum_{k\in\mathbb{Z}} e^{j\omega k}h[n-k] = \sum_{k\in\mathbb{Z}} e^{j\omega (n-k)}h[k] = e^{j\omega n}\sum_{k\in\mathbb{Z}} e^{j\omega -k}h[k] \equiv H\left(e^{j\omega}\right)e^{j\omega n}$$
by recognizing that last equality as the definition of the Fourier transform. Now, for a fixed $\omega$, the transfer function $H\left(e^{j\omega}\right)$ is a constant. In other words the complex exponentials are eigenvectors of the LTI signal with eigenvalue $H\left(e^{j\omega}\right)$, so they have merit as an alternative basis.
Suppose we represented our signals in this basis:
$$x[n] = \sum_{k\in\mathbb{Z}}x_ke^{jk\omega_0n}$$
Then the system applied to the signal would be
$$H(x[n]) = H\left(\sum_{k\in\mathbb{Z}}x_ke^{jk\omega_0 n}\right) = \sum_{k\in\mathbb{Z}} x_kH(e^{jk\omega_0 n}) = \sum_{k\in\mathbb{Z}} x_kH(e^{jk\omega_0 })e^{jk\omega_0 n}$$
So if you can write your input signal in this basis very nicely, then it becomes easier to compute the output, rather than trying to find the impulse response and computing the convolution by hand.


TITLE: Given a curve $C$, does there exist a rational function on $C$ totally ramified at two given points?
QUESTION [2 upvotes]: Let $C$ be a smooth projective irreducible curve over $\mathbb C$. Let $x$ and $y$ be distinct points of $C$.
We say that $f$ is totally ramified at a point $p$ if the ramification index of $p$ equals $\deg(f)$.
Does $C$ admit a finite map $f \colon C \to \mathbb P^1$ which is totally ramified at $x$ and $y$?

REPLY [11 votes]: The answer is in general no. More precisely, the following holds.

A finite map $f \colon C \to \mathbb P^1$ as in the question exists if and only if $\mathcal{O}_C(x-y)$ is a point of finite order in $\textrm{Pic}^0\, C$.

In fact, if $f$ exists, calling $n$ its degree we have $\mathcal{O}_C(nx) = \mathcal{O}_C(ny)$, that is $\mathcal{O}_C(n(x-y))=\mathcal{O}_C$, in other words the degree zero divisor $x-y$ defines a point of finite order in $\textrm{Pic}^0 \,C$.
Conversely, if $\mathcal{O}_C(x-y)$ is a point of finite order $n$ in $\textrm{Pic}^0 \, C$, then the two divisors $nx$ and $ny$ are linearly equivalent on $C$ and the linear pencil generated by them is a $g^1_n$ without base points. Thus such a $g_n^1$ defines a morphism $f \colon C \to \mathbb{P}^1$ of degree $n$, totally ramified at both $x$ and $y$.


TITLE: Proving that $\lim_{n \to \infty} \int_0^1 f(x) \sin(nx) \, dx = 0$ if $f : \mathbb R \to \mathbb R$ is continuous
QUESTION [1 upvotes]: Specifically I would like to know how one can justify the following equality
$$\begin{align}
&2 \int_0^1 f(x) \sin(nx) \, dx \\
= &\int_0^\frac{\pi}{n}f(x)\sin(nx) \, dx - \int_1^{1+\frac{\pi}n} f(x)\sin(nx) \, dx + \int_0^1 \left(f(x)-f\left(x-\frac {\pi}n \right) \right) \sin(nx) \, dx
\end{align}
$$
knowing that (as $\sin(nx)$ has a period of $\frac{2\pi}n$)
$$
\int_0^1 f(x) \sin(nx) \, dx = -\int_{\frac{\pi}n}^{1+\frac{\pi}n} f\left(x-\frac {\pi}n \right)  \sin(nx) \, dx
$$
for all continuous functions $f: \mathbb R \to \mathbb R$?
The equality in question is taken from page 1 of this PDF file and is used to prove that
$$
\lim_{n \to \infty} \int_0^1 f(x) \sin(nx) \, dx = 0
$$
if $f : \mathbb R \to \mathbb R$ is continuous.
I am already aware of the Riemann Lebesgue Lemma, but I wanted to understand precisely the justification of the equality in question. The remainder of the proof follows easily for me.

REPLY [2 votes]: The equality is incorrect.
Let $f(x) = x$.  Then we get
$$\begin{align}2 \int_0^1 x \sin nx \, dx &= \frac{2 \sin n}{n^2}-\frac{\cos n}{n} \\ &\neq \frac{2 \sin n}{n^2} +\frac{2\pi}{n^2} - \frac{2 \cos n}{n} - \frac{2 \pi \cos n}{n^2}\\ &=  \int_0^{\pi/n} x \sin nx \, dx - \int_{1}^{1 + \pi/n} x \sin nx \, dx + \int_0^1 [x - (x -\pi/n)] \sin nx \, dx\end{align}$$
The correct result is
$$\begin{align} 2 \int_0^1 f(x) \sin nx \, dx  &= \int_0^\frac{\pi}{n}f\left(x-\frac {\pi}n \right)\sin(nx) \, dx - \int_1^{1+\frac{\pi}n} f\left(x-\frac {\pi}n \right)\sin(nx) \, dx \\ &+ \int_0^1 \left(f(x)-f\left(x-\frac {\pi}n \right) \right) \sin(nx) \, dx \end{align}
$$
This follows easily by splitting the integral over $[\pi/n, 1+\pi/n]$ on the RHS of the first line of the solution in the attached PDF into integrals  over $[\pi/n,1]$ and $[1,1 + \pi/n]$ and then adding and subtracting the integral over $[0,\pi/n]$.


TITLE: limit of summation
QUESTION [4 upvotes]: Using Riemann integrals of suitably functions, find the following limit
$$\lim_{n\to \infty}\sum_{k=1}^n \frac{k}{n^2+k^2}$$
Please help me check my method:
Let $$f(x)=\frac{x}{1+x^2}$$
For each n$\in$ $\Bbb N$, let partition $$P_n=({\frac{k}{n}:0\le k\le n})$$ and $$\xi^{(n)}=(\frac{1}{n},\frac{2}{n},...,\frac{n-1}{2n},1)$$ and $||P_n||=\frac{1}{n} \rightarrow 0$
$$\lim_{n\to \infty}\sum_{k=1}^n \frac{k}{n^2+k^2}=\int_0^1 \frac{x}{1+x^2}dx=\frac{1}{2} \ln(1+x^2)|^1_0=\frac{\ln 2}{2}$$
Is there any other methods for this question?

REPLY [1 votes]: Your approach is fine and Riemann sums are definitely the way to go.
Anyway, I will show you an interesting overkill. Since:
$$ \frac{2k}{k^2+n^2}=\frac{1}{k+in}+\frac{1}{k-in}=\int_{0}^{+\infty}e^{-kx}\left(e^{-inx}+e^{inx}\right)\,dx $$
we may write the original sum as:
$$\begin{eqnarray*} S_n=\sum_{k=1}^{n}\int_{0}^{+\infty}\cos(nx) e^{-kx}\,dx &=& \int_{0}^{+\infty}\frac{1-e^{-nx}}{e^x-1}\cos(nx)\,dx\\&=&\int_{0}^{+\infty}\frac{(1-e^{-x})\cos x}{n(e^{x/n}-1)}\,dx\\&=&\int_{0}^{+\infty}\frac{\cos x-e^{-x}}{n(e^{x/n}-1)}\,dx+\int_{0}^{+\infty}\frac{1-\cos x}{e^x n (e^{x/n}-1)}\,dx.\end{eqnarray*}$$
Now you may notice that $n(e^{x/n}-1)$ is pointwise convergent to $x$ as $n\to +\infty$ and check that:
$$ \int_{0}^{+\infty}\frac{\cos x-e^{-x}}{x}\,dx = 0. $$
So, by the dominated convergence theorem we have
$$ \lim_{n\to +\infty} S_n = \int_{0}^{+\infty}\frac{1-\cos x}{xe^{x}}\,dx = \text{Re}\log(1+i) = \log\|1+i\| = \log\sqrt{2} = \color{red}{\frac{\log 2}{2}}$$
through the Cantarini-Frullani's theorem.


TITLE: How many permutations of 160 outputs from binomial B(1, p) if p varies?
QUESTION [1 upvotes]: I apologise for the question title if it's not accurate.  I've spent a long time trying to formulate this.  Let me try to explain by example...
Assume a binomial distribution like B(1, p) where there is a binary choice of 1 or 0 as output, and p is the probability of the output being 1.  Now assume we generate 160 outputs. This is my question: I'm interested in how many permutations (order matters) of the 160 output numbers there are in a general case where p can vary.
So for B(1, 0.5) on average, we can have 160!/(80! * 80!) permutations of ones and zeros which is ~ 10^47. I get this formula from https://math.stackexchange.com/a/452/394771.
What would the mean number of permutations be for 160 outputs from the general case of B(1, p) if p is a variable and not equal to 0.5?
Another example:
Take p = 0.1, and get 160 outcomes from distribution B(1, 0.1).  On the average, you'll get 16 ones, and therefore the mean number of unique permutations is 160! / (16! x 144!) or 4.1^21.  What's the general formula for any p?  My formula collapses for long decimal values of p where the binomial mean isn't an integer such as p = 0.557, giving a mean of 89.12.  The factorial of 89.12 is tricky for me.
I feel exactly what I want but can't express it clearly, so please bear with me.  I'm only an engineer :-(

REPLY [0 votes]: Take p = 0.1, and get 160 outcomes from distribution B(1, 0.1). On the average, you'll get 16 ones, and therefore the mean number of unique permutations is 160! / (16! x 144!) or 4.1^21. What's the general formula for any p?

Let $(X_1,...,X_n)$ be the sequence of $n$ independent random variables, each distributed as $\text{Binomial}(1,p),$ and let $S_n=X_1+...+X_n$ (which equals the number of $1$s in the sequence).
Let $A_n$ be the number of different ways in which to arrange the random binary sequence $(X_1,...,X_n)$. (In combinatorics these are called arrangements, whereas the term permutations refers to sequences all of whose elements are distinct.) This is given by the following binomial coefficient:
$$A_n = \binom{n}{S_n}.$$
We may now consider the expected value of $A_n$:
$$\begin{align}E[A_n]&=E\,\binom{n}{S_n}\\[2ex]
&=\sum_\limits{k=0}^{n}\,\binom{n}{k}\,P(S_n=k)\\[2ex]
&=\sum_\limits{k=0}^{n}\,\binom{n}{k}\binom{n}{k}p^k(1-p)^{n-k}\\[2ex]
&=\sum_\limits{k=0}^{n}\,\binom{n}{k}^2\,p^k(1-p)^{n-k}\\[2ex]
&= \ _2F_1\left(-n;-n;1;{p\over 1-p}\right)\,(1-p)^n
\end{align}$$
where $_2F_1$ is the ordinary hypergeometric function, which in this case is a polynomial in $p$. (To get this and results below, I used Wolfram Alpha.)
Note that $E[A_n]$, as a function of $p$, is maximized by $p={1\over 2}$:
$$\left\{E[A_n]\right\}_{p={1\over 2}}=2^n{\left(n-{1\over 2}\right)!\over n!\,\sqrt{\pi}}\sim 2^n\sqrt{{1\over n\,\pi}}.$$
NB: Instead of computing the mean number of arrangements, $E[A_n]=E\,\binom{n}{S_n}$, you computed the number of arrangements of a sequence having the mean number of $1$s, i.e., $\binom{n}{E[S_n]}=\binom{n}{np}$, when $np$ is an integer; then you were confused by what to do in case $np$ is not an integer. Although I think $E[A_n]$ is probably the quantity you want to look at, nevertheless the quantity you were using can be naturally extended to non-integers, using the Gamma function:
$$\binom{n}{E[S_n]}=\binom{n}{np}={n!\over (np)!\,(n(1-p))!}$$
where $x!$ is extended to all real $x$ except negative integers, by the definition
$$x!::=\Gamma(x+1).$$
This too is maximized by $p={1\over 2}$, for which its asymptotic behavior differs from before by a factor of $\sqrt{2}$:
$$\left\{\binom{n}{E[S_n]}\right\}_{p={1\over 2}}=\binom{n}{n\over 2}\sim 2^n\sqrt{{2\over n\,\pi}}.
$$


TITLE: Inequalities: A Mathematical Olympiad Approach (Exercise 1.17)
QUESTION [0 upvotes]: My attempt:
Since $a>0\Rightarrow-a<0\Rightarrow1-a<1\Rightarrow c(1-a)<c$. Thus, ${1\over 4}<c(1-a)<c$. Similarily ${1\over 4}<a(1-b)<a$ and ${1\over 4}<b(1-c)<b$. On adding these inequalities, we get: ${3\over 4}<-(ab+bc+ca)<0$, which is a contradiction. Hence all the three inequalities cannot hold at the same time.
Is this proof correct? I am asking this because my method is quite different from that given by the author in the solutions.Also I am new to Inequalities.

REPLY [2 votes]: if the inequalities are true. then $$a,b,c$$ are less than $1$ and $$a(1-b)b(1-c)c(1-a)>\frac{1}{64}$$ But since $$x(1-x)\le \frac{1}{4}$$ for $$0\le x\le 1$$ then $$a(1-b)b(1-c)c(1-a)\le \frac{1}{64}$$


TITLE: Distributing n balls into k boxes so that every box has an even number of balls
QUESTION [1 upvotes]: How many ways can you distribute n balls into k boxes so that every box has an even number of balls?
Well, so far I think than n must be an even number. And I know that it basically starts with a simple equation:
$$x_1 + x_2 + x_3 + \cdots + x_k = n$$
where
$$x_i\equiv 0\pmod 2$$
Normally I would use a combination with repetition but since there has to be an even number of balls in every box I don't know what to do.

REPLY [2 votes]: Of course $n$ must be even. Then distribute $\frac{n}{2}$ balls over $k$ boxes (no conditions) and double the amounts in all boxes. This gives all such even distibutions and so the problem is equivalent to the $\frac{n}{2}$ over $k$ boxes problem for even $n$. For $n$ odd there are no solutions.

REPLY [1 votes]: Hint:  Let $n = 2m$.  Let $x_i = 2y_i$, $1 \leq i \leq k$.  Then
\begin{align*}
x_1 + x_2 + x_3 + \cdots + x_k & = n\\
2y_1 + 2y_2 + 2y_3 + \cdots + 2y_k & = 2m\\
y_1 + y_2 + y_3 + \cdots + y_k & = m
\end{align*}
which is an equation in the nonnegative integers.


TITLE: Exponential equation that's been bothering me: $(2^x)^{x-1}=1024$
QUESTION [1 upvotes]: Equation: $(2^x)^{x-1}=1024$
What I did was:
$(2^x)^{(x-1)}=2^{10}$
$x(x-1)=10$
$x^2-x=10$
$x^2-x-10=0$
And proceeded to use Bhaskara, with the final result of
$\frac{1\pm \sqrt{41}}{2}$
I've tried to resolve but the output for $+$ and $-$ results from here onwards don't give me what I need; I have tried to check changing the $x$ in the equation to those results, and it doesn't match to $1024$ as final result. What should I do?

REPLY [1 votes]: Write $$2^{x(x-1)}=2^{10}$$ so you will get $$x(x-1)=10$$
By the quadratic formula we get $$x_{1,2}=\frac{1}{2}\pm\sqrt{\frac{1}{4}+10}$$
$$\frac{1}{4}+10=\frac{1+4\cdot 10}{4}=\frac{41}{4}$$

REPLY [1 votes]: We have
$$(2^x)^{x-1}=2^{10} \implies 2^{x^2-x}=2^{10} \implies x^2-x=10$$
$$\implies x_{1,2}=\dfrac{1\pm\sqrt{1+4\cdot 10}}{2}=\dfrac{1\pm\sqrt{41}}{2}.$$
So your answer is correct. You can verify it with wolfram alpha.


text:
\chapter{Proofs related to the discrete homogenization theorem}
\label{chap:proofs-related-to-penalization-theorems}
\section{Fattening the unit-cell}
In this section, all the estimates will hold almost surely, and hence we'll not explicitly refer to $\w \OR \W$. It will be useful for the reader to visualize the lattice as being embedded in $\R^d$. Discrete paths on the lattice will now be allowed to wander away from the edges of the graph on $\Z^d$ and into $\R^d$. This will let us define continuum variational problems ---what we've called \deltaapprox s in~\Secref{sec:outline-of-paper}--- that will approximate discrete \FPP~and its associated cell-problem.

Consider a unit-cell of the lattice embedded in $\R^d$. We will ``fatten'' the edges and vertices of the lattice into tubes and corners. The remaining space in the unit-cell contains its center point, and so we will call this region a center (see~\Figref{fig:sketch-of-fattened-unit-cell}). Let $0 < \delta < 1/2$ be a parameter describing the size of the tubes and corners. Define \begin{enumerate}
  \item The \emph{tube} at $x \in \Z^d$ in the $\alpha \in A$ direction as:
    \[
      TU^{\delta}_{x,\alpha} := \big\{ x + \lambda \alpha + y:\delta < \lambda < 1 - \delta,~y \in \{\alpha\}^{\perp},~|y|_{\infty} \leq \delta\big\}.
    \]
    The tubes have width $2\delta$ and length $1-2\delta$.
  \item The \emph{corner} around a vertex $x$ as:
\[
  CO^{\delta}_{x} := \{ y:|y-x|_{\infty} \leq \delta \}.
\]
  \item The \emph{center} of the cell as:
\[
  CE^{\delta}_x := \bigg\{ x + \sum_{i=1}^d \lambda_i e_i : \delta < \lambda_i < 1 - \delta, ~\forevery~ i \bigg\}.
\]
\end{enumerate}
The three regions are disjoint. That is, for any $x,y,z \in \R^d$ and $\alpha \in A$,
\[
  TU_{x,\alpha}^{\delta} \cap CO_y^{\delta} \cap CE^{\delta}_z = \emptyset .
\]

\begin{figure}[t]
  \begin{center}
    \includegraphics[width=0.65\textwidth]{penalization_for_paper.pdf}
  \end{center}
    \caption{Sketch of fattened unit-cell. The dotted lines represent the edges of the lattice. The solid lines show the boundaries of the corners, tubes and centers. When $\delta$ is expanded to $\eta$, the center becomes a bad region.}
    \label{fig:sketch-of-fattened-unit-cell}
\end{figure}

Next, we need to define the edge-weight function $t^{\delta}(x,\alpha)$ and the cell-problem running cost $l^{\delta}(x,\alpha)$ in the \deltaapprox . We'd like the value functions in the \deltaapprox~to be close to the discrete problem, and so we would like paths to avoid the centers of cells and stick close to the edges. By penalizing paths that cross into centers of cells with additional cost, we'll ensure that they stay inside the tubes and corners. For each $\alpha \in A$, let
\begin{equation}
  t^{\delta}_c(x,\alpha) := \left\{
  \begin{array}{cl}
    \tau(x,\alpha) & \text{if } x \in TU^{\delta}_{z,\alpha} \text{ for some } z \in \Z^d \\
    a   & \text{if } x \in CO_z \text{ for some } z \in \Z^d \\
    \delta^{-1}   & \text{otherwise}
  \end{array} \right. .
  \label{eq:time-edge-weights-tau}
\end{equation}

Fix $p \in \R^d$, and let $\lambda(x,\alpha) = p\cdot\alpha$ be the discrete cell-problem weight  defined in~\Eqref{eq:running-costs-for-discrete-cell-problem}. We define the running costs as
\begin{equation}
  l^{\delta}_c(x,\alpha) = \left\{
  \begin{array}{cl}
    \lambda(x,\alpha) & \text{if } x \in TU_{z,\alpha} \text{ for some } z \in \Z^d\\
    -C & \text{if } x \in CO_z \text{ for some } z \in \Z^d \\
    \delta^{-1} & \text{otherwise}
  \end{array} \right. ,
  \label{eq:running-cost-per-unit-time-l-extension}
\end{equation}
  where $C = -|p|_{\infty} $ is the lower bound on $\lambda(x,\alpha)$. The functions $t^{\delta}_c$ and $l^{\delta}_c$ represent piecewise extensions of the discrete edge-weights and  running costs. Define the mollified functions
\[
  l^{\delta}(x,\alpha) = \eta_{\delta/2} * l^{\delta}_c(x,\alpha) \quad \AND \quad t^{\delta}(x,\alpha) = \eta_{\delta/2} * t^{\delta}_c(x,\alpha),
\]
where $\eta_{\delta}$ is the standard mollifier with support $\delta$. The Hamiltonian $H^{\delta}$ obtained from $l^{\delta}$ and $t^{\delta}$ using~\Eqref{eq:continuous-hamiltonian-definition} satisfies the hypotheses of the Lions-Souganidis continuum homogenization theorem (\Thmref{thm:lions-homogenization-theorem}).

For the finite time-horizon cell-problem, there is a final cost given by $\mu_0\colon\Z^d \to \R$. We can extend the final cost smoothly to $\R^d$ by defining
\[
  u_0^{\delta}(x) = \eta_{\delta/2} * \mu_0([x]).
\]
The continuous variational problems in~\Secref{sec:optimal-control-theory} can now be defined using the smooth functions $l^{\delta}$, $t^{\delta}$ and $u_0^{\delta}$.

The main focus of this section is~\Thmref{thm:commutation-theorem-for-u-and-T}. We will first prove it for when $\beta = \mu(x,s) \AND b^{\delta} = u^{\delta}(x,s)$, the finite time-horizon cell-problems.
\begin{remark}
  Although trivial, we remark that
  \[ u^{\delta}(x,s) \leq \mu(x,s),\]
    since we can always take paths going along edges in the \deltaapprox.
    \label{rem:L-delta-smaller-than-L}
\end{remark}
Then, the proof of~\Thmref{thm:commutation-theorem-for-u-and-T} is easy given that
\begin{lemma}
  for $\delta$ small enough, we have the estimate
  \[
    \frac{\mu([nx],ns)}{n} - \frac{u^{\delta}([nx],ns)}{n} \leq C\left( \sqrt{\delta}s + \frac{1}{n}\right) .
  \]
  \label{lem:uniform-in-n-delta-estimate}
\end{lemma}
We will complete the proof of the main theorem before proving~\Lemref{lem:uniform-in-n-delta-estimate}.
\begin{proof}[Proof of~\Thmref{thm:commutation-theorem-for-u-and-T}]
  While the homogenization theorem applies directly to $u^{\delta}(x,s)$, our scaling in~\Eqref{eq:scaling-for-finite-time-horizon-problem} is slightly different. We scaled it differently so that it is enough to compare the discrete problem $\mu(z,s)$ to the continuum problem $u^{\delta}(z,s)$ on lattice points $z \in \Z^d$. So we account for this first. Since $l^{\delta}$ is bounded above by $\delta^{-1}$, we have
  \[
    \left| \frac{u^{\delta}([nx],ns)}{n} - \frac{u^{\delta}(nx,ns)}{n} \right| \leq \frac{Cs}{\delta n}.
  \]
    It follows from~\Propref{prop:convergence-of-u-to-H-p} (or the continuum homogenization theorem) that $u^{\delta}(nx,ns)/n$ has a limit, and hence
  \[
    \lim_{n \to \infty} \frac{u^{\delta}([nx],ns)}{n} = \lim_{n \to \infty} \frac{u^{\delta}(nx,ns)}{n} =: \overline{u}^{\delta}(x,s).
  \]

  From~\Lemref{lem:uniform-in-n-delta-estimate} and~\Remref{rem:simple-observation-that-will-help-us-work-with-piecewise-functions}, we have the following inequality for the scaled functions~\Eqref{eq:scaling-for-finite-time-horizon-problem}
  \begin{equation}
    u^{\delta}_n(x,s) \leq \mu_n(x,s) \leq u^{\delta}_n(x,s) + C\left( \sqrt{\delta}s  + \frac{1}{n} \right) \quad \forall x \in \R^d.
    \label{eq:squeeze-mu-between-u-and-c-times-delta}
  \end{equation}

  Taking a limit in $n$ first, and then in $\delta$ (limsups and liminfs as appropriate), we get
  \[
  \begin{split}
    \overline{u}^{\delta}(x,s) \leq & \varliminf_{n \to \infty} \mu_n(x,s),\\
    & \varlimsup_{n \to \infty} \mu_n(x,s) \leq \overline{u}^{\delta}(x,s) + C\sqrt{\delta} s.
  \end{split}
  \]
  Since $\delta$ is arbitrary, it follows that $\mu_n(x,s) \to \overline{u}(x,s)$ as $n \to \infty$. Taking limits in the reverse order and using the fact that $\mu_n(x,s)$ has a limit completes the proof.

\end{proof}

\section{Integral formulation of variational problem}
It's easier to work with an integral formulation of \FPP~and its cell-problem that will allow us to drop reference to the control $a(s)$ in~\Eqref{eq:cost-functional}. This is easily done by extending $l^{\delta}(x,\alpha)$ and $t^{\delta}(x,\alpha)$ one-homogeneously from $\R^d \times A$ to $\R^d \times \R^d$. For $x,r \in \R^d$ we redefine
\begin{equation}
  \begin{split}
    l^{\delta}(x,r) & = l^{\delta}\left( x, \frac{r}{|r|} \right)|r|, \\
    t^{\delta}(x,r) & = t^{\delta}\left( x, \frac{r}{|r|} \right)|r|.
  \end{split}
  \label{eq:running-cost-and-time-one-homo-extension}
\end{equation}

Hence, we may write the total cost of a path parametrized by $g\colon[0,s]\to\R^d$ (see~\Eqref{eq:cost-functional}) as
\begin{equation}
  I^{\delta}(g) = \int_0^s l^{\delta}(g(r),g'(r))dr.
  \label{eq:cost-functional-definition}
\end{equation}
We have to prove that dropping reference to the control in~\Eqref{eq:cost-functional-definition} will not affect our problem. That is we've to show that if we take a path $g$ realized by a control and reparametrize it, its total cost will be unaffected. Let $r = h(q)$ be a smooth change of time parametrization, where $h$ is an increasing function. Let $y(r) = g(h^{-1}(r))$ be the path. Then, a simple change of variable gives
\begin{prop}[Cost is independent of path parametrization]
  \[ I^{\delta}(g) = \int_0^s l^{\delta}(g(q),g'(q))dq = \int_0^{h(s)} l^{\delta}(y(r),y'(r))dr.\]
  \label{prop:cost-is-independent-of-time-parametrization}
\end{prop}

Since we can dispense with the controls and talk directly about paths, define
\[
  U := \left\{ g(s) \in C^{0,1}([0,1],\R^d): \frac{g'(s)}{|g'(s)|} \in A ~\text{a.e. } \Leb[0,1] \right\}.
\]
This restricts us to paths that can be ``realized'' with controls. Let $U_x$ be the subset of paths that start at $x$, and let $U_{x,y}$ be the subset of paths that go from $x$ to $y$. Let $\mathcal{U}$, $\mathcal{U}_x$ and $\mathcal{U}_{x,y}$ be the corresponding subsets of $U$ where paths are only allowed to go on the edges of the lattice $\Z^d$.

The total-time or weight of a path $g \in U$ is
\begin{equation}
  W^{\delta}(g) = \int_0^1 t^{\delta}\left( g(r),\frac{g'(r)}{|g'(r)|} \right)|g'(r)|~dr.
  \label{eq:time-functional-definition}
\end{equation}
The cost of $g$ is given by~\Eqref{eq:cost-functional-definition} with $s=1$. Let the $L^1$ length of $g$ be
\begin{equation}
  d(g) = \int_0^1 |g'(r)|~dr.
  \label{eq:L1-length-of-a-continuous-path}
\end{equation}

This allows us the following reformulation of the discrete and continuous cell-problems:
\begin{prop}
  For $x \in \R^d,~z \in \Z^d$  and $s \in \R^+$, we have
  \[
    \begin{split}
      u^{\delta}(x,s) & = \inf_{g \in U_x} \left\{ I^{\delta}(g) : W^{\delta}(g) \leq s \right\}, \\
      \mu(z,s) & = \inf_{\gamma \in \mathcal{U}_z} \left\{ I^{\delta}(\gamma) : W^{\delta}(\gamma) \leq s \right\}.
    \end{split}
  \]
  \label{prop:reformulation-of-control-problem-as-integral-variational-problem}
\end{prop}

\begin{proof}
  The proof follows from~\Propref{prop:cost-is-independent-of-time-parametrization} and the definitions of $u$ and $\mu$ in~\Eqref{eq:finite-time-horizon-variational-problem} and~\Eqref{eq:discrete-finite-time-horizon-problem}.
\end{proof}

\begin{remark}
  There are two things to notice about~\Propref{prop:reformulation-of-control-problem-as-integral-variational-problem}. First, notice that $\mu(x,s)$ is ``embedded'' in the continuum problem for every $\delta$, and further, $u^{\delta}(x,s) \leq \mu(x,s) ~\forall~ x \in \Z^d$. Second, we no longer need $t^{\delta}(x,\alpha)$ and $l^{\delta}(x,\alpha)$ to be smooth in $x$ for the variational problem to be well-defined. This allows us to work with the piecewise versions $l^{\delta}_c(x,\alpha)$ and $t^{\delta}_c(x,\alpha)$, since these are easier to compare to the discrete problems.
\end{remark}

\begin{remark}
  One could argue that we needn't have introduced the optimal-control framework since our costs depend only on the graph of the path and not its parametrization. However, DPPs and Hamiltonians are conventionally represented using the control interpretation.  Several other models can be naturally formulated using the optimal-control language, and our approach ought to work for these (see~\Secref{sec:generalization}).
\end{remark}

\section{Proof of~\Lemref{lem:uniform-in-n-delta-estimate}}
We state a simple comparison result first. Suppose $t_1(x,\alpha) \leq t_2(x,\alpha)$ and $l_1(x,\alpha) \leq l_2(x,\alpha)$. Let $u_1(x,s)$ and $u_2(x,s)$ be the corresponding variational problems defined by~\Propref{prop:reformulation-of-control-problem-as-integral-variational-problem}. Then, it follows quite easily that
\begin{prop}[Comparison of variational problems]
  for all $x \in \R^d$ and $s > 0$,
  \[
    u_1(x,s) \leq u_2(x,s).
  \]
  \label{prop:comparison-of-variational-problems}
\end{prop}

\begin{remark}
  Let $w^{\delta}(x,s) \leq u^{\delta}(x,s)$ for all $x \in \R^d$ and $s > 0$. To prove~\Lemref{lem:uniform-in-n-delta-estimate}, it's enough to show that for any $s > 0$,
\[
  \mu(x,s) - w^{\delta}(x,s)  \leq  C (\sqrt{\delta} s + 1) \quad \forall x \in \Z^d.
\]

  \label{rem:simple-observation-that-will-help-us-work-with-piecewise-functions}
\end{remark}

\begin{proof}[Proof of~\Lemref{lem:uniform-in-n-delta-estimate}]

We will use the observation made in~\Remref{rem:simple-observation-that-will-help-us-work-with-piecewise-functions} repeatedly in the proof. We will also refer to the bounds on $\tau(x,\alpha)$ assumed in~\Eqref{eq:basic-assumption-on-edge-weights}. The proof takes several steps.

\newcounter{proofsteps} \setcounter{proofsteps}{0}
\stepcounter{proofsteps}\noindent\theproofsteps .  Let us first reduce to the case where the cost and time functions are piecewise constant. For this, we will show that
    \begin{equation}
      \begin{split}
        l^{2\delta}_c(x,\alpha) & \leq l^{\delta}(x,\alpha), \\
        t^{2\delta}_c(x,\alpha) & \leq t^{\delta}(x,\alpha).
      \end{split}
      \label{eq:reducing-to-piecewise-case}
    \end{equation}
    Then, for a fixed path $g$, it would follow from~\Propref{prop:comparison-of-variational-problems} that
    \[
      I^{2\delta}_c(g) \leq I^{\delta}(g) \AND W^{2\delta}_c(g) \leq W^{\delta}(g),
    \]
    where the subscript $c$ in $I$ and $W$ represent the cost and time corresponding to the piecewise versions of $l$ and $\tau$. Then,~\Propref{prop:comparison-of-variational-problems} and~\Remref{rem:simple-observation-that-will-help-us-work-with-piecewise-functions} imply that we can just work with $t_c^{2\delta}$ and $l_c^{2\delta}$.

    To show the two inequalities in~\Eqref{eq:reducing-to-piecewise-case}, it's enough to show that $t^{2\delta}_c(x,\alpha) \leq t^{\delta}_c(y)$ and $l^{2\delta}_c(x) \leq l^{\delta}_c(y)$ for all $y$ in the ball $B_{\delta}(x)$. This is clear by drawing a picture. Then, multiply with the standard mollifier $\eta_{\delta/2}(y-x)$ and integrate over $y$.

  \stepcounter{proofsteps}\noindent\theproofsteps .
  Create boxes of side-length $1-2(\delta+\sqrt{\delta})$ called \emph{bad regions} (BRs) contained inside centers (see~\Figref{fig:sketch-of-fattened-unit-cell}). We show that if a path goes through a BR, it will do so badly that it will make more sense to stick to the tubes and corners. If $g$ visits a BR, it will take at least time
    \[ \sqrt{\delta}t^{2\delta}_c(x,\alpha) = \frac{1}{\sqrt{\delta}}.  \]
    Hence it accumulates cost
    \[ \sqrt{\delta}t^{\delta}_c(x,\alpha) \cdot \frac{\delta^{-1}}{t^{\delta}_c(x,\alpha)} = \frac{1}{\sqrt{\delta}} .\]
    A path $g$ that visits a BR must leave a tube at some point $A$ to enter the BR. Once it's done being bad, it must re-enter another tube or corner in the same cell at a point $B$. We will form a new path $g^*$ that connects $A$ and $B$ by a path that only goes through tubes and corners. Making crude estimates, we see that the new path $g^*$ has distance at most $3$ to travel. Since the edge-weight function is bounded, it takes time at most $3b$, and costs at most $3C$. Since $g^*$ does not take more time than $g$ and costs less, we might as well assume that paths do not enter BRs. Henceforth, we will assume that $U$ contains only such good paths.

\stepcounter{proofsteps}\noindent\theproofsteps .
 Expand the tubes $TU^{2\delta}$ and corners $CO^{2\delta}$ to have thickness $\eta$, where
  \begin{equation}
    \eta = 2 \delta + \sqrt{\delta}.
    \label{eq:eta-tube-size-definition}
  \end{equation}
That is, we've expanded the tubes $TU^{2\delta}$ and corners $CO^{2\delta}$ so that the centers shrink to the BRs. Consider the problem $t^{\eta}_c$, $l^{\eta}_c$ defined by~\Eqref{eq:running-cost-per-unit-time-l-extension} and~\Eqref{eq:time-edge-weights-tau}. Then for $\delta$ small enough,
\[ u^{\eta}(x,s) \leq u^{2\delta}(x,s). \]

\stepcounter{proofsteps}\noindent\theproofsteps .
 For a path $g \in U$, we need to construct an edge-path $\gamma \in \mathcal{U}$ that has a similar cost and time. We will consider each tube and corner that $g$ passes through (since it avoids BRs), and construct $\gamma$ in each region so that it follows $g$ around. Fix such a tube $TU$ or corner $CO$, and continue to write $g$ for just the section of the path going through it. Then,
\begin{claim}
  We can find $\gamma \in \mathcal{U}$ such that
  \[
    I^{\eta}_c(\gamma) \leq I^{\eta}_c(g) + C\eta,
  \]
  \[
    W^{\eta}_c(\gamma) \leq W^{\eta}_c(g) + C\eta,
  \]
  inside each tube or a corner that $g$ goes through.
  \label{claim:comparing-paths-deltapprox-to-edge-paths}
\end{claim}
We will prove Claim~\ref{claim:comparing-paths-deltapprox-to-edge-paths} after completing the proof of this lemma.

\stepcounter{proofsteps}\noindent\theproofsteps .
 A path $g \in U$ can travel a distance at most $s/a$ in time $s$. So the number of tubes and corners the path can visit is at most $2s/a$. Using Claim~\ref{claim:comparing-paths-deltapprox-to-edge-paths}, we will approximate $g$ by an edge-path $\gamma$ in each corner and tube that it goes through, except for possibly $C\eta s$ tubes and corners (since $\gamma$ is typically slower through the corners). Hence, the most cost that $\gamma$ could have missed out on is $C\eta s$, since $l^{\eta}_c(x,\alpha)$ is bounded below.

 We must also take the final cost due to $u_0$ into account. Recall that we've assumed that $\Norm{u_0}{Lip} < \infty$. The final locations of $g$ and $\gamma$ cannot differ by more than $C\eta s$ and hence, neither can the final cost. Finally, $\gamma$ ought to end on a lattice point, whereas $g$ need not. Accounting for all this, we get that
\[
  I^{\eta}_c(\gamma) \leq I^{\eta}_c(g) + C \eta s + C.
\]

Since $I^{\eta}_c(\gamma)$ is exactly the cost accumulated by a path in the discrete problem, scaling by $n$ completes the proof.
\end{proof}

\begin{proof}[Proof of claim~\ref{claim:comparing-paths-deltapprox-to-edge-paths}]
  Corners are of size $\eta$, and the inequalities in Claim~\ref{claim:comparing-paths-deltapprox-to-edge-paths} are immediate. Hence, we only need to prove it for a tube, which wlog, we can assume to be $TU^{\eta}_{0,e_1}$. The end-caps of the tube of size $\eta$ at the origin in the $e_1$ direction are $\{ \eta e_1 + y : y \in \{e_1\}^{\perp}, |y|_{\infty} \leq \eta\}$, and $\{ (1-\eta) e_1 + y : y \in \{e_i\}^{\perp}, |y|_{\infty} \leq \eta\}$. Let $A = (A_i)_{i=1}^{d}$ be the last point on the end-cap before $g$ enters the tube, and let $B=(B_i)_{i=1}^{d} $ be the first point on the end-cap when $g$ exits the tube. Assume a parametrization such that $g(0) = A$ and $g(1) = B$.
   The total cost of $g$ is
    \begin{equation*}

        I^{\eta}_c(g) = \int_0^1 p \cdot g'(s) ~ds = p \cdot (B - A).

    \end{equation*}
  If $A$ and $B$ are on the same end-cap, the edge-path $\gamma$ does not move at all, and if they're on different end-caps, it travels from end-cap to end-cap along the edge.

  The tube is aligned with $e_1$ by construction, and hence $|A_1 - B_1| = 1-2\eta$ and $|A_j - B_j| \leq 2\eta ~\forall j \neq 1$. Hence,
  \[
    I^{\eta}_c(g) - I^{\eta}_c(\gamma) \leq C \eta.
  \]
  It's also clear that the $L^1$ length of the path is
  \[ 1 - 2\eta = d(\gamma) \leq d(g). \]
  It follows that
  \begin{equation}
    W^{\eta}_c(\gamma) \leq W^{\eta}_c(g).
    \label{eq:time-of-edge-path-compare-smooth-path}
  \end{equation}
\end{proof}

To obtain a version of~\Lemref{lem:uniform-in-n-delta-estimate} for $T^{\delta}_n(x)$ and $\mathcal{T}_n(x)$, first replace $U$ by $U_{0,x}$. The essential estimate is already present in Claim~\ref{claim:comparing-paths-deltapprox-to-edge-paths}, and the rest of the argument is identical.

\section{Lipschitz estimates on Hamiltonians and time-constants}
We next prove the Lipschitz estimates on the time-constants $m^{\delta}$ and limiting Hamiltonians $\overline{H}^{\delta}$.
\begin{proof}[Proof of~\Propref{prop:lipschitz-continuity-of-limit-hamiltonian}]
  Fix $p_1 \AND p_2 \in \R^d$. Let $l^{\delta}_{i,c}(x,\alpha)$ be the piecewise function defined in~\Eqref{eq:running-cost-per-unit-time-l-extension} for each $p_i$. Let $l^{\delta}_{i}$ be the mollified versions, and let $u^{\delta}_i$ be the corresponding finite time cell-problems with the same $t^{\delta}(x,\alpha)$ (for $i=1,2$). Then,~\Propref{prop:convergence-of-u-to-H-p} states that
  \[
  \lim_{t \to \infty} \frac{u^{\delta}_i(x,s)}{t} = -\overline{H}^{\delta}(p_i) \quad \text{ for } i=1,2.
  \]
  Now, $l^{\delta}_{1,c}$ and $l^{\delta}_{2,c}$ differ only in the tubes, and hence satisfy
  \[
    |l^{\delta}_{1,c}(x,r) - l^{\delta}_{2,c}(x,r)| \leq |p_1 - p_2||r| \quad \forall x,r \in \R^d.
  \]
  It follows that the same inequality applies for the mollified versions $l_{i}^{\delta}$. So for any path $g(s)$,
  \[
  \begin{split}
    I^{\delta}_{p_1}(g) - I^{\delta}_{p_2}(g) & = \int_0^s l_1^{\delta}(g(r),g'(r)) - l_2^{\delta}(g(r),g'(r))dr \\
    & \leq |p_1 - p_2|d(g)  .
  \end{split}
  \]
  Since the total length of the path is at most $d(g) \leq s/a$, the Lipschitz estimate follows.
\end{proof}

\begin{proof}[Proof of~\Propref{prop:lipschitz-continuity-of-time-constant}]
  Let $T^{\delta}(x,y)$ be the first-passage time from $x$ to $y$ in the \deltaapprox. Since
  \[ |T^{\delta}(0,[x]) - T^{\delta}(0,x)| \leq \frac{1}{\delta}, \]
  we have that
  \[ \lim_{n \to \infty} \frac{T^{\delta}(0,[nx])}{n} = m^{\delta}(x). \]
  For any $x,y \in \R^d$, using subadditivity, we get the estimate
  \[

    T^{\delta}(0,[nx]) \leq T^{\delta}(0,[ny]) + T^{\delta}([ny],[nx]). \\

  \]
  Then, using the fact that we can take an edge path from $[ny]$ to $[nx]$, and that the time to cross each edge is at most $b$, we get
  \begin{equation*}
    T^{\delta}(0,[nx]) \leq T^{\delta}(0,[ny]) +  b |[ny] - [nx]|.\\
  \end{equation*}
Dividing by $n$ and taking a limit as $n \to \infty$ gives us the Lipschitz estimate.
\end{proof}

config: arxiv


TITLE: What are "unranked trees"?
QUESTION [4 upvotes]: Recently I have some dispute with my colleagues and would like to clarify the following question.
It is clear what are "ranked" trees. They are those, which produced by tree grammars, where each symbol in their finite alphabets (terminals and non-terminals resp.) has an arity or "rank", which specifies number of possible children. So for terminals it is always "0", while for non-terminals it is always $\geq 1$.
But what should we consider by "unranked" trees?
In my understanding, as some papers state (I don't have references right now), an unranked tree is produced by a tree grammar where there are no restrictions on the rank for non-terminals. I.e. alphabets are not ranked anymore. And that's all (I don't want to go deeper into the formal details and definitions).
Basically in my understanding, each XML document is generally an unranked tree.
So what my colleague states, is that the "unrankness" necessary implies a kind of "unboundness" of children inside each node. In other words, if a tree grammar specifies a certain finite set of "ranks" for each non-terminal, then trees produced by such a grammar are not unranked.
The difference between my understanding and my opponent's one, is that my definition seems to be more soft and general. So I can say that any XML document is an example of an unranked tree. My colleague's definition restricts it, so not each XML document will be unranked, but only that satisfying an XSD schema which contains some unbounded lists.
So, who is right?

REPLY [2 votes]: You are Right if the Computing Power for XSD schema is free or freely available (Soft). Otherwise, it will be Hard.


TITLE: Do identical, equally spaced lenses possess the same magnification, or does it depend on the sample's distance?
QUESTION [1 upvotes]: Do identical, equally spaced lenses always have the same magnification, or does it depend on the sample's distance to the first lens?
This question comes from trying to solve:
"There are 4 identical and equally spaced lenses between the sample and the camera. The distance from the first to the last lens is 70cm. Find their individual magnifications to achieve a magnification of $10^6$."
I know that when there's more than a lense, the total magnification is the product of the magnification values for each lense, meaning $M_{total}= M_1 M_2 ...M_n$ .
This makes me think that, because they are identical, the magnification of each of these lenses must be $(10^6)^{1/4} =10 \sqrt{10} \approx 31.62$
This does not use the distance between each lens which makes me think it is not correct. But if I think of using this distance then I must require the initial distance from the sample to the first lens, is this not so? Is there a lack of information in this exercise?
Does the magnification solely depend on its shape/material (in which case they would all be the same)?

REPLY [1 votes]: "Does the magnification solely depend on its shape/material (in which case they would all be the same)?"
In the realm of simple geometrical optics, the magnification of a lens is given by q/p, where q is the image distance and p is the object distance. So it's not really a property of the lens but rather of the image conjugates in any particular case. (A magnifier might be characterized by a magnification but that type of lens is always used in a particular way).
The only way the magnification of each identical lens can be the same is if q/p is the same for each one. Let's say the image and object distances for the first lens are q$_1$ and p$_1$. One way for the second lens to have the same magnification is if the object distance to the second lens, p$_2$, equals p$_1$. Etc. for the remaining two lenses. Under this special case, in which each lens has the same object and image distances, I think your result would be correct.
But I'm not totally clear on what the assumptions of the problem are.


TITLE: Proving continuity using the topological definition?
QUESTION [1 upvotes]: Let $f$ be a function from $\mathbb{R}$ to $\mathbb{R}$, and suppose that $f(x) = 0$, $\forall x \in  \mathbb{R}$, except when $x=c$, for a fixed $c \in \mathbb{R}$. Now, $f$ is clearly discontinuous at $c$, and I can easily show this using the $\delta$-$\epsilon$ definition, but how do I show discontinuity using the definition of continuity that the preimage of every open set is open? I just don't see any nontrivial open sets in the image of the function, as $f(\mathbb{R}) = \{0,f(c)\}$.
Any ideas?
EDIT: Note that $f(c) \neq 0$.

REPLY [3 votes]: You know that $f(c)\neq 0$. So take some open neighborhood $U$ such that $f(c)\in U$ but $0\notin U$. So $f^{-1}(U)=\{c\}$. However, singletons are not open in the usual topology.
To see this, note that $c\in\{c\}$. But $\{c\}$ does not contain any open interval about $c$, hence it cannot possibly be open, since any open set contains an open neighborhood of any of its points.


text:
\section{Introduction}

Graph clustering is a fundamental task in network analysis, where the goal is to find a tightly connected vertex set in a graph.
It has been used in many applications such as community detection~\cite{Fortunato:2010iw} and image segmentation~\cite{Felzenszwalb:2004bx}.

Because of its importance, graph clustering has been intensively studied, and a plethora of clustering methods have been proposed.
See, e.g.,~\cite{Fortunato:2010iw} for a survey.

There is no single best criterion to measure the quality of a vertex set as a cluster; however, one of the most widely used is the notion of \emph{conductance}.
Roughly speaking, the conductance of a vertex set is small if many edges reside within the vertex set, whereas only a few edges leave it (see Section~\ref{sec:pre} for details).
Many clustering methods have been shown to have theoretical guarantees on the conductance of the output vertex set~\cite{Alon:1986gz,Alon:1985jg,Andersen:2007tsa,Kloster:2014wq,Chung:2007ep,Spielman:2013cc,Gharan:2012fy,Andersen:2009fj,Kwok:2017ga}.

Although a graph is suitable to represent binary relations over entities, many relations, such as coauthorship, goods that are

purchased together, and chemicals involved in metabolic reactions inherently comprise three or more entities.
A hypergraph is a more natural
object to model such relations.
Indeed, if we represent coauthorship network by a graph,
an edge only indicates the existence of co-authored paper, and information about co-authors in one paper is lost.
However, hypergraphs do not lose that information.

As with graphs, hypergraph clustering is also an important task,

and it is natural to use an extension of conductance for hypergraphs~\cite{Chan:2018eu,Yoshida:2019zz} to measure the quality of a vertex set as a cluster.
Although several methods have been shown to have theoretical guarantees on the conductance of the output vertex set~\cite{Chan:2018eu,Yoshida:2019zz,ikeda2018finding}, none of them are efficient in practice.

To obtain efficient hypergraph clustering algorithms with a theoretical guarantee, we utilize the graph clustering algorithm developed by Andersen~\emph{et~al.}~\cite{Andersen:2007tsa}.
Their algorithm is based on \emph{personalized PageRank} (PPR), which is the stationary distribution of a random walk that jumps back to a specified vertex with a certain probability in each step of the walk.
Roughly speaking, their algorithm first computes the PPR from a specified vertex, and then returns a set of vertices with high PPR values.
They showed a theoretical guarantee on the conductance of the returned vertex set.

In this work, we propose two hypergraph clustering algorithms by extending Andersen~\emph{et~al.}'s algorithm~\cite{Andersen:2007tsa}.
The first one is \emph{local} in the sense that its goal is to find a vertex set of a small conductance and a bounded volume including a specified vertex.
The second one is \emph{global} in the sense that its goal is to find a vertex set of the smallest conductance.

Although there could be various definitions of random walk on hypergraphs and corresponding PPRs, we adopt the PPR recently introduced by Li and Milenkovic~\cite{Li:2018we} using a hypergraph Laplacian~\cite{Chan:2018eu,Yoshida:2019zz}.
Because the hypergraph Laplacian well captures the cut information of hypergraphs, the corresponding PPR can be used to find vertex sets with small conductance.

Because we can efficiently compute (a good approximation to) the PPR, our algorithms are efficient.
Moreover, as with Andersen~\emph{et~al.}'s algorithm~\cite{Andersen:2007tsa}, our algorithms have theoretical guarantees on the conductance of the output vertex set.
To the best of our knowledge, no local clustering algorithm with a theoretical guarantee on the conductance of the output set is known for hypergraphs.
Although, as mentioned previously, several algorithms have been proposed for global clustering for hypergraphs~\cite{Chan:2018eu,Yoshida:2019zz,ikeda2018finding}, we stress here that our global clustering algorithm is the first practical algorithm with a theoretical guarantee.

We experimentally demonstrate that our clustering algorithms outperform other baseline methods in terms of both the solution quality and running time.

Our contribution can be summarized as follows.
\begin{itemize}
\leftskip=-15pt
\itemsep=0pt
\item We propose local and global hypergraph clustering algorithms based on PPR for hypergraphs given by Li and Milenkovic~\cite{Li:2018we}.

\item We give theoretical guarantees on the conductance of the vertex set output by our algorithms.

\item Our algorithms are more efficient than existing algorithms with theoretical guarantees~\cite{Chan:2018eu,Yoshida:2019zz,ikeda2018finding}
(see Section~\ref{sec:related} for the details).

\item We experimentally demonstrate that our clustering algorithms outperform other baseline methods in terms of both the solution quality and running time.
\end{itemize}

This paper is organized as follows.
We discuss related work in Section~\ref{sec:related} and then introduce notions used throughout the paper in Section~\ref{sec:pre}.
After discussing basic properties of PPR for hypergraphs in Section~\ref{sec:ppr}, we introduce a key lemma

(Lemma~\ref{lem:upperbound-of-sweep-conductance-local-2}) that connects conductance and PPR in Section~\ref{sec:conductance}.
On the basis of the key lemma, we show our local and global clustering algorithms in Sections~\ref{sec:local-clustering} and~\ref{sec:global-clustering}, respectively.
We discuss our experimental results in Section~\ref{sec:experiments}, and conclude in Section~\ref{sec:conclusion}. In appendix, we
give the proofs which could not be included in the main body
because of the page restrictions.


TITLE: How to reverse the bend in a 2 DOF arm using inverse kinematics
QUESTION [0 upvotes]: I have the inverse kinematics working, but the arm bends the wrong way. I'm really new to this type of math, so please have patience. Here's the equations:
math equations
image for clarification
l1 and l2 are the lengths of each segment(2 segments) and the thetas are the angles that they are at. There should be two different positions that will reach the same point, and I want to be able to pick which one I want to use.

REPLY [0 votes]: You can put $\pm$ sign in
$$
\theta_2=\pm \arctan(\ldots,\ldots)
$$
to get two solutions.


text:
(*
    Author:      René Thiemann
                 Akihisa Yamada
    License:     BSD
*)
section \<open>Newton Interpolation\<close>

text \<open>We proved the soundness of the Newton interpolation, i.e., a method to interpolate a polynomial $p$
  from a list of points $(x_1,p(x_1)), (x_2, p(x_2)), \ldots$. In experiments it performs
  much faster than the Lagrange interpolation.\<close>
theory Newton_Interpolation
imports
  "HOL-Library.Monad_Syntax"
  Ring_Hom_Poly
  Divmod_Int
  Is_Rat_To_Rat
begin

text \<open>For the Newton interpolation, we start with an efficient implementation (which in prior examples
  we used as an uncertified oracle). Later on, a more abstract definition of the algorithm
  is described for which soundness is proven, and which is provably equivalent to the efficient
  implementation.

  The implementation is based on divided differences and the Horner schema.\<close>

fun horner_composition :: "'a :: comm_ring_1 list \<Rightarrow> 'a list \<Rightarrow> 'a poly" where
  "horner_composition [cn] xis = [:cn:]"
| "horner_composition (ci # cs) (xi # xis) = horner_composition cs xis * [:- xi, 1:] + [:ci:]"
| "horner_composition _ _ = 0"

lemma (in map_poly_comm_ring_hom) horner_composition_hom:
  "horner_composition (map hom cs) (map hom xs) = map_poly hom (horner_composition cs xs)"
  by (induct cs xs rule: horner_composition.induct, auto simp: hom_distribs)

lemma horner_coeffs_ints: assumes len: "length cs \<le> Suc (length ys)"
  shows "(set (coeffs (horner_composition cs (map rat_of_int ys))) \<subseteq> \<int>) = (set cs \<subseteq> \<int>)"
proof -
  let ?ir = "int_of_rat"
  let ?ri = "rat_of_int"
  let ?mir = "map ?ir"
  let ?mri = "map ?ri"
  show ?thesis
  proof
    define ics where "ics = map ?ir cs"
    assume "set cs \<subseteq> \<int>"
    hence ics: "cs = ?mri ics" unfolding ics_def map_map o_def
      by (simp add: map_idI subset_code(1))
    show "set (coeffs (horner_composition cs (?mri ys))) \<subseteq> \<int>"
      unfolding ics of_int_poly_hom.horner_composition_hom by auto
  next
    assume "set (coeffs (horner_composition cs (?mri ys))) \<subseteq> \<int>"
    thus "set cs \<subseteq> \<int>" using len
    proof (induct cs arbitrary: ys)
      case (Cons c cs xs)
      show ?case
      proof (cases "cs = [] \<or> xs = []")
        case True
        with Cons show ?thesis by (cases "c = 0"; cases cs, auto)
      next
        case False
        then obtain d ds and y ys where cs: "cs = d # ds" and xs: "xs = y # ys"
          by (cases cs, auto, cases xs, auto)
        let ?q = "horner_composition cs (?mri ys)"
        define q where "q = ?q"
        define p where "p = q * [:- ?ri y, 1:] + [:c:]"
        have id: "horner_composition (c # cs) (?mri xs) = p"
          unfolding cs xs q_def p_def by simp
        have coeff: "coeff p i \<in> \<int>" for i
        proof (cases "coeff p i \<in> set (coeffs p)")
          case True
          with Cons(2)[unfolded id] show ?thesis by blast
        next
          case False
          hence "coeff p i = 0" using range_coeff[of p] by blast
          thus ?thesis by simp
        qed
        {
          fix i
          let ?f = "\<lambda> j. coeff [:- ?ri y, 1:] j * coeff q (Suc i - j)"
          have "coeff p (Suc i) = coeff ([: -?ri y, 1 :] * q) (Suc i)" unfolding p_def by simp
          also have "\<dots> = (\<Sum>j\<le>Suc i. ?f j)" unfolding coeff_mult by simp
          also have "\<dots> = ?f 0 + ?f 1 + (\<Sum>j\<in>{..Suc i} - {0} - {Suc 0}. ?f j)"
            by (subst sum.remove[of _ 0], force+, subst sum.remove[of _ 1], force+)
          also have "(\<Sum>j\<in>{..Suc i} - {0} - {Suc 0}. ?f j) = 0"
          proof (rule sum.neutral, auto, goal_cases)
            case (1 x)
            thus ?case by (cases x, auto, cases "x - 1", auto)
          qed
          also have "?f 0 = - ?ri y * coeff q (Suc i)" by simp
          also have "?f 1 = coeff q i" by simp
          finally have int: "coeff q i - ?ri y * coeff q (Suc i) \<in> \<int>" using coeff[of "Suc i"] by auto
          assume "coeff q (Suc i) \<in> \<int>"
          hence "?ri y * coeff q (Suc i) \<in> \<int>" by simp
          hence "coeff q i \<in> \<int>" using int Ints_diff Ints_minus by force
        } note coeff_q = this
        {
          fix i
          assume "i \<le> degree q"
          hence "coeff q (degree q - i) \<in> \<int>"
          proof (induct i)
            case 0
            from coeff_q[of "degree q"] show ?case
              by (metis Ints_0 Suc_n_not_le_n diff_zero le_degree)
          next
            case (Suc i)
            with coeff_q[of i] show ?case
              by (metis Suc_diff_Suc Suc_leD Suc_n_not_le_n coeff_q le_less)
          qed
        } note coeff_q = this
        {
          fix i
          have "coeff q i \<in> \<int>"
          proof (cases "i \<le> degree q")
            case True
            with coeff_q[of "degree q - i"] show ?thesis by auto
          next
            case False
            hence "coeff q i = 0" using le_degree by blast
            thus ?thesis by simp
          qed
        } note coeff_q = this
        hence "set (coeffs q) \<subseteq> \<int>" by (auto simp: coeffs_def)

        from Cons(1)[OF this[unfolded q_def]] Cons(3) xs have IH: "set cs \<subseteq> \<int>" by auto
        define r where "r = coeff q 0 * (- ?ri y)"
        have r: "r \<in> \<int>" using coeff_q[of 0] unfolding r_def by auto
        have "coeff p 0 \<in> \<int>" by fact
        also have "coeff p 0 = r + c" unfolding p_def r_def by simp
        finally have c: "c \<in> \<int>" using r using Ints_diff by force
        with IH show ?thesis by auto
      qed
    qed simp
  qed
qed

context
fixes
  ty :: "'a :: field itself"
  and xs :: "'a list"
  and fs :: "'a list"
begin

fun divided_differences_impl :: "'a list \<Rightarrow> 'a \<Rightarrow> 'a \<Rightarrow> 'a list \<Rightarrow> 'a list" where
  "divided_differences_impl (xi_j1 # x_j1s) fj xj (xi # xis) = (let
    x_js = divided_differences_impl x_j1s fj xj xis;
    new = (hd x_js - xi_j1) / (xj - xi)
    in new # x_js)"
| "divided_differences_impl [] fj xj xis = [fj]"

fun newton_coefficients_main :: "'a list \<Rightarrow> 'a list \<Rightarrow> 'a list list" where
  "newton_coefficients_main [fj] xjs = [[fj]]"
| "newton_coefficients_main (fj # fjs) (xj # xjs) = (
    let rec = newton_coefficients_main fjs xjs; row = hd rec;
      new_row = divided_differences_impl row fj xj xs
    in new_row # rec)"
| "newton_coefficients_main _ _ = []"

definition newton_coefficients :: "'a list" where
  "newton_coefficients = map hd (newton_coefficients_main (rev fs) (rev xs))"

definition newton_poly_impl :: "'a poly" where
  "newton_poly_impl = horner_composition (rev newton_coefficients) xs"

qualified definition "x i = xs ! i"
qualified definition "f i = fs ! i"

private definition "xd i j = x i - x j"

lemma [simp]: "xd i i = 0" "xd i j + xd j k = xd i k" "xd i j + xd k i = xd k j"
  unfolding xd_def by simp_all

(* divided differences [xi,..,xj]f *)
private function xij_f :: "nat \<Rightarrow> nat \<Rightarrow> 'a" where
  "xij_f i j = (if i < j then (xij_f (i + 1) j - xij_f i (j - 1)) / xd j i else f i)"
  by pat_completeness auto

termination by (relation "measure (\<lambda> (i,j). j - i)", auto)

private definition c :: "nat \<Rightarrow> 'a" where
  "c i = xij_f 0 i"

private definition "X j = [: - x j, 1:]"

private function b :: "nat \<Rightarrow> nat \<Rightarrow> 'a poly" where
  "b i n = (if i \<ge> n then [:c n:] else b (Suc i) n * X i + [:c i:])"
  by pat_completeness auto

termination by (relation "measure (\<lambda> (i,n). Suc n - i)", auto)

declare b.simps[simp del]

definition newton_poly :: "nat \<Rightarrow> 'a poly" where
  "newton_poly n = b 0 n"

private definition "Xij i j = prod_list (map X [i ..< j])"

private definition "N i = Xij 0 i"

lemma Xii_1[simp]: "Xij i i = 1" unfolding Xij_def by simp
lemma smult_1[simp]: "smult d 1 = [:d:]"
  by (fact smult_one)

private lemma newton_poly_sum:
  "newton_poly n = sum_list (map (\<lambda> i. smult (c i) (N i)) [0 ..< Suc n])"
  unfolding newton_poly_def N_def
proof -
  {
    fix j
    assume "j \<le> n"
    hence "b j n = (\<Sum>i\<leftarrow>[j..<Suc n]. smult (c i) (Xij j i))"
    proof (induct j n rule: b.induct)
      case (1 j n)
      show ?case
      proof (cases "j \<ge> n")
        case True
        with 1(2) have j: "j = n" by auto
        hence "b j n = [:c n:]" unfolding b.simps[of j n] by simp
        thus ?thesis unfolding j by simp
      next
        case False
        hence b: "b j n = b (Suc j) n * X j + [: c j:]" unfolding b.simps[of j n] by simp
        define nn where "nn = Suc n"
        from 1(2) have id: "[j..< nn] = j # [Suc j ..< nn]" unfolding nn_def by (simp add: upt_rec)
        from False have "Suc j \<le> n" by auto
        note IH = 1(1)[OF False this]
        have id2: "(\<Sum>x\<leftarrow>[Suc j..< nn]. smult (c x) (Xij (Suc j) x * X j)) =
          (\<Sum>i\<leftarrow>[Suc j..< nn]. smult (c i) (Xij j i))"
        proof (rule arg_cong[of _ _ sum_list], rule map_ext, intro impI, goal_cases)
          case (1 i)
          hence "Xij (Suc j) i * X j = Xij j i" by (simp add: Xij_def upt_conv_Cons)
          thus ?case by simp
        qed
        show ?thesis unfolding b IH sum_list_mult_const[symmetric]
          unfolding nn_def[symmetric] id
          by (simp add: id2)
      qed
    qed
  }
  from this[of 0] show "b 0 n = (\<Sum>i\<leftarrow>[0..<Suc n]. smult (c i) (Xij 0 i))" by simp
qed

private lemma poly_newton_poly: "poly (newton_poly n) y = sum_list (map (\<lambda> i. c i * poly (N i) y) [0 ..< Suc n])"
  unfolding newton_poly_sum poly_sum_list map_map o_def by simp

private definition "pprod k i j = (\<Prod>l\<leftarrow>[i..<j]. xd k l)"

private lemma poly_N_xi: "poly (N i) (x j) = pprod j 0 i"
proof -
  have "poly (N i) (x j) = (\<Prod>l\<leftarrow>[0..<i]. xd j l)"
    unfolding N_def Xij_def poly_prod_list X_def[abs_def] map_map o_def xd_def by simp
  also have "\<dots> = pprod j 0 i" unfolding pprod_def ..
  finally show ?thesis .
qed

private lemma poly_N_xi_cond: "poly (N i) (x j) = (if j < i then 0 else pprod j 0 i)"
proof -
  show ?thesis
  proof (cases "j < i")
    case False
    thus ?thesis using poly_N_xi by simp
  next
    case True
    hence "j \<in> set [0 ..< i]" by auto
    from split_list[OF this] obtain bef aft where id2: "[0 ..< i] = bef @ j # aft" by auto
    have "(\<Prod>k\<leftarrow>[0..<i]. xd j k) = 0" unfolding id2 by auto
    with True show ?thesis unfolding poly_N_xi pprod_def by auto
  qed
qed

private lemma poly_newton_poly_xj: assumes "j \<le> n"
  shows "poly (newton_poly n) (x j) = sum_list (map (\<lambda> i. c i * poly (N i) (x j)) [0 ..< Suc j])"
proof -
  from assms have id: "[0 ..< Suc n] = [0 ..< Suc j] @ [Suc j ..< Suc n]"
    by (metis Suc_le_mono le_Suc_ex less_eq_nat.simps(1) upt_add_eq_append)
  have id2: "(\<Sum>i\<leftarrow>[Suc j..< Suc n]. c i * poly (N i) (x j)) = 0"
    by (rule sum_list_neutral, unfold poly_N_xi_cond, auto)
  show ?thesis unfolding poly_newton_poly id map_append sum_list_append id2 by simp
qed

declare xij_f.simps[simp del]

context
  fixes n
  assumes dist: "\<And> i j. i < j \<Longrightarrow> j \<le> n \<Longrightarrow> x i \<noteq> x j"
begin
private lemma xd_diff: "i < j \<Longrightarrow> j \<le> n \<Longrightarrow> xd i j \<noteq> 0"
   "i < j \<Longrightarrow> j \<le> n \<Longrightarrow> xd j i \<noteq> 0" using dist[of i j] dist[of j i] unfolding xd_def by auto

text \<open>This is the key technical lemma for soundness of Newton interpolation.\<close>

private lemma divided_differences_main: assumes "k \<le> n" "i < k"
  shows "sum_list (map (\<lambda> j. xij_f i (i + j) * pprod k i (i + j)) [0..<Suc k - i]) =
  sum_list (map (\<lambda> j. xij_f (Suc i) (Suc i + j) * pprod k (Suc i) (Suc i + j)) [0..<Suc k - Suc i])"
proof -
  let ?exp = "\<lambda> i j. xij_f i (i + j) * pprod k i (i + j)"
  define ei where "ei = ?exp i"
  define esi where "esi = ?exp (Suc i)"
  let ?ki = "k - i"
  let ?sumi = "\<lambda> xs. sum_list (map ei xs)"
  let ?sumsi = "\<lambda> xs. sum_list (map esi xs)"
  let ?mid = "\<lambda> j. xij_f i (k - j) * pprod k (Suc i) (k - j) * xd (k - j) i"
  let ?sum = "\<lambda> j. ?sumi [0 ..< ?ki - j] + ?sumsi [?ki - j ..< ?ki] + ?mid j"
  define fin where "fin = ?ki - 1"
  have fin: "fin < ?ki" unfolding fin_def using assms by auto
  have id: "[ 0 ..< Suc k - i] = [0 ..< ?ki] @ [?ki]" and
    id2: "[i..<k] = i # [Suc i ..< k]" and
    id3: "k - (i + (k - Suc i)) = 1" "k - (?ki - 1) = Suc i" using assms
    by (auto simp: Suc_diff_le upt_conv_Cons)
  have neq: "xd (Suc i) i \<noteq> 0" using xd_diff[of i "Suc i"] assms by auto
  have "sum_list (map (\<lambda> j. xij_f i (i + j) * pprod k i (i + j)) [0..<Suc k - i])
    = ?sumi [0 ..< Suc k - i]" unfolding ei_def by simp
  also have "\<dots> = ?sumi [0 ..< ?ki] + ?sumsi [?ki ..< ?ki] + ei ?ki"
    unfolding id by simp
  also have "\<dots> = ?sum 0"
    unfolding ei_def using assms by (simp add: pprod_def id2)
  also have "?sum 0 = ?sum fin" using fin
  proof (induct fin)
    case (Suc fin)
    from Suc(2) assms
    have fki: "fin < ?ki" and ikf: "i < k - Suc fin" "i < k - fin" and kfn: "k - fin \<le> n" by auto
    from xd_diff[OF ikf(2) kfn] have nz: "xd (k - fin) i \<noteq> 0" by auto
    note IH = Suc(1)[OF fki]
    have id4: "[0 ..< ?ki - fin] = [0 ..< ?ki - Suc fin] @ [?ki - Suc fin]"
      "i + (k - i - Suc fin) = k - Suc fin"
      "Suc (k - Suc fin) = k - fin" using Suc(2) assms  \<open>fin < ?ki\<close>
      by (metis Suc_diff_Suc le0 upt_Suc) (insert Suc(2), auto)
    from Suc(2) assms have id5: "[i..<k - Suc fin] = i # [Suc i ..< k - Suc fin]"
      "[Suc i..<k - fin] = [Suc i..<k - Suc fin] @ [k - Suc fin]"
      by (force simp: upt_rec) (metis Suc_leI id4(3) ikf(1) upt_Suc)
    have "?sum 0 = ?sum fin" by (rule IH)
    also have "\<dots> = ?sumi [0 ..< ?ki - Suc fin] + ?sumsi [?ki - fin ..< ?ki] +
      (ei (?ki - Suc fin) + ?mid fin)"
      unfolding id4 by simp
    also have "?mid fin = (xij_f (Suc i) (k - fin) - xij_f i (k - Suc fin))
      * pprod k (Suc i) (k - fin)" unfolding xij_f.simps[of i "k - fin"]
      using ikf nz by simp
    also have "\<dots> = xij_f (Suc i) (k - fin) * pprod k (Suc i) (k - fin) -
      xij_f i (k - Suc fin) * pprod k (Suc i) (k - fin)" by algebra
    also have "xij_f (Suc i) (k - fin) * pprod k (Suc i) (k - fin) = esi (?ki - Suc fin)"
      unfolding esi_def using ikf by (simp add: id4)
    also have "ei (?ki - Suc fin) = xij_f i (k - Suc fin) * pprod k i (k - Suc fin)"
      unfolding ei_def id4 using ikf by (simp add: ac_simps)
    finally have "?sum 0 = ?sumi [0 ..< ?ki - Suc fin]
      + (esi (?ki - Suc fin) + ?sumsi [?ki - fin ..< ?ki])
      + (xij_f i (k - Suc fin) * (pprod k i (k - Suc fin) - pprod k (Suc i) (k - fin)))"
      by algebra
    also have "esi (?ki - Suc fin) + ?sumsi [?ki - fin ..< ?ki]
      = ?sumsi ((?ki - Suc fin) # [?ki - fin ..< ?ki])" by simp
    also have "(?ki - Suc fin) # [?ki - fin ..< ?ki] = [?ki - Suc fin ..< ?ki]"
      using Suc(2) by (simp add: Suc_diff_Suc upt_rec)
    also have "pprod k i (k - Suc fin) - pprod k (Suc i) (k - fin)
      = (xd k i) * pprod k (Suc i) (k - Suc fin) - (xd k (k - Suc fin)) * pprod k (Suc i) (k - Suc fin)"
      unfolding pprod_def id5 by simp
    also have "\<dots> = (xd k i - xd k (k - Suc fin)) * pprod k (Suc i) (k - Suc fin)"
      by algebra
    also have "\<dots> = (xd (k - Suc fin) i) * pprod k (Suc i) (k - Suc fin)" unfolding xd_def by simp
    also have "xij_f i (k - Suc fin) * \<dots> = ?mid (Suc fin)" by simp
    finally show ?case by simp
  qed simp
  also have "\<dots> = (ei 0 + ?mid (k - i - 1)) + ?sumsi [1 ..< k - i]"
    unfolding fin_def by (simp add: id3)
  also have "ei 0 + ?mid (k - i - 1) = esi 0" unfolding id3
    unfolding ei_def esi_def xij_f.simps[of i i]  using neq assms
    by (simp add: field_simps xij_f.simps pprod_def)
  also have "esi 0 + ?sumsi [1 ..< k - i] = ?sumsi (0 # [1 ..< k - i])" by simp
  also have "0 # [1 ..< k - i] = [0 ..< Suc k - Suc i]"
    using assms by (simp add: upt_rec)
  also have "?sumsi \<dots> = sum_list (map (\<lambda> j. xij_f (Suc i) (Suc i + j) *
    pprod k (Suc i) (Suc i + j)) [0..<Suc k - Suc i])"
    unfolding esi_def using assms by simp
  finally show ?thesis .
qed

private lemma divided_differences: assumes kn: "k \<le> n" and ik: "i \<le> k"
  shows "sum_list (map (\<lambda> j. xij_f i (i + j) * pprod k i (i + j)) [0..<Suc k - i]) = f k"
proof -
  {
    fix ii
    assume "i + ii \<le> k"
    hence "sum_list (map (\<lambda> j. xij_f i (i + j) * pprod k i (i + j)) [0..<Suc k - i])
      = sum_list (map (\<lambda> j. xij_f (i + ii) (i + ii + j) * pprod k (i + ii) (i + ii + j)) [0..<Suc k - (i + ii)])"
    proof (induct ii)
      case (Suc ii)
      hence le1: "i + ii \<le> k" and le2: "i + ii < k" by simp_all
      show ?case unfolding Suc(1)[OF le1] unfolding divided_differences_main[OF kn le2]
        using Suc(2) by simp
    qed simp
  } note main = this
  have ik: "i + (k - i) \<le> k" and id: "i + (k - i) = k" using ik by simp_all
  show ?thesis unfolding main[OF ik] unfolding id
    by (simp add: xij_f.simps pprod_def)
qed

lemma newton_poly_sound: assumes "k \<le> n"
  shows "poly (newton_poly n) (x k) = f k"
proof -
  have "poly (newton_poly n) (x k) =
    sum_list (map (\<lambda> j. xij_f 0 (0 + j) * pprod k 0 (0 + j)) [0..<Suc k - 0])"
    unfolding poly_newton_poly_xj[OF assms] c_def poly_N_xi by simp
  also have "\<dots> = f k"
    by (rule divided_differences[OF assms], simp)
  finally show ?thesis by simp
qed
end

lemma newton_poly_degree: "degree (newton_poly n) \<le> n"
proof -
  {
    fix i
    have "i \<le> n \<Longrightarrow> degree (b i n) \<le> n - i"
    proof (induct i n rule: b.induct)
      case (1 i n)
      note b = b.simps[of i n]
      show ?case
      proof (cases "n \<le> i")
        case True
        thus ?thesis unfolding b by auto
      next
        case False
        have "degree (b i n) = degree (b (Suc i) n * X i + [:c i:])" using False unfolding b by simp
        also have "\<dots> \<le> max (degree (b (Suc i) n * X i)) (degree [:c i:])"
          by (rule degree_add_le_max)
        also have "\<dots> = degree (b (Suc i) n * X i)" by simp
        also have "\<dots> \<le> degree (b (Suc i) n) + degree (X i)"
          by (rule degree_mult_le)
        also have "\<dots> \<le> n - Suc i + degree (X i)"
          using 1(1)[OF False] 1(2) False add_le_mono1 not_less_eq_eq by blast
        also have "\<dots> = n - Suc i + 1" unfolding X_def by simp
        also have "\<dots> = n - i" using 1(2) False by auto
        finally show ?thesis .
      qed
    qed
  }
  from this[of 0] show ?thesis unfolding newton_poly_def by simp
qed

context
  fixes n
  assumes xs: "length xs = n"
    and fs: "length fs = n"
begin
lemma newton_coefficients_main:
  "k < n \<Longrightarrow> newton_coefficients_main (rev (map f [0..<Suc k])) (rev (map x [0..<Suc k]))
    = rev (map (\<lambda> i. map (\<lambda> j. xij_f j i) [0..<Suc i]) [0..<Suc k])"
proof (induct k)
  case 0
  show ?case
    by (simp add: xij_f.simps)
next
  case (Suc k)
  hence "k < n" by auto
  note IH = Suc(1)[OF this]
  have id: "\<And> f. rev (map f [0..<Suc (Suc k)]) = f (Suc k) # f k # rev (map f [0..< k])"
    and id2: "\<And> f. f k # rev (map f [0..<k]) = rev (map f [0..< Suc k])" by simp_all
  show ?case unfolding id newton_coefficients_main.simps Let_def
    unfolding id2 IH
    unfolding list.simps id2[symmetric]
  proof (rule conjI, goal_cases)
    case 1
    have xs: "xs = map x [0 ..< n]" using xs unfolding x_def[abs_def]
      by (intro nth_equalityI, auto)
    define nn where "nn = (0 :: nat)"
    define m where "m = Suc k - nn"
    have prems: "m = Suc k - nn" "nn < Suc (Suc k)" unfolding m_def nn_def by auto
    have "?case = (divided_differences_impl (map ((\<lambda>j. xij_f j k)) [nn..< Suc k]) (f (Suc k)) (x (Suc k)) (map x [nn ..< n]) =
      map ((\<lambda>j. xij_f j (Suc k))) [nn..<Suc (Suc k)])"
      unfolding nn_def xs[symmetric] by simp
    also have "\<dots>" using prems
    proof (induct m arbitrary: nn)
      case 0
      hence nn: "nn = Suc k" by auto
      show ?case unfolding nn by (simp add: xij_f.simps)
    next
      case (Suc m)
      with \<open>Suc k < n\<close> have "nn < n" and le: "nn < Suc k" by auto
      with Suc(2-) have id:
        "[nn..<Suc k] = nn # [Suc nn..< Suc k]"
        "[nn..<n] = nn # [Suc nn..< n]"
      and id2: "[nn..<Suc (Suc k)] = nn # [Suc nn..<Suc (Suc k)]"
        "[Suc nn..<Suc (Suc k)] = Suc nn # [Suc (Suc nn)..<Suc (Suc k)]"
        by (auto simp: upt_rec)
      from Suc(2-) have "m = Suc k - Suc nn" "Suc nn < Suc (Suc k)" by auto
      note IH = Suc(1)[OF this]
      show ?case unfolding id list.simps divided_differences_impl.simps IH Let_def
        unfolding id2 list.simps
        using le
        by (simp add: xij_f.simps[of nn "Suc k"] xd_def)
    qed
    finally show ?case by simp
  qed simp
qed

lemma newton_coefficients: "newton_coefficients = rev (map c [0 ..< n])"
proof (cases n)
  case 0
  hence xs: "xs = []" "fs = []" using xs fs by auto
  show ?thesis unfolding newton_coefficients_def 0
    using newton_coefficients_main.simps
    unfolding xs by simp
next
  case (Suc nn)
  hence sn: "Suc nn = n" and nn: "nn < n" by auto
  from fs have fs: "map f [0..<Suc nn] = fs" unfolding sn
    by (intro nth_equalityI, auto simp: f_def)
  from xs have xs: "map x [0..<Suc nn] = xs" unfolding sn
    by (intro nth_equalityI, auto simp: x_def)
  show ?thesis
    unfolding newton_coefficients_def
      newton_coefficients_main[OF nn, unfolded fs xs]
    unfolding sn rev_map[symmetric] map_map o_def
    by (rule arg_cong[of _ _ rev], subst upt_rec, intro nth_equalityI, auto simp: c_def)
qed

lemma newton_poly_impl: assumes "n = Suc nn"
  shows "newton_poly_impl = newton_poly nn"
proof -
  define i where "i = (0 :: nat)"
  have xs: "map x [0..<n] = xs" using xs
    by (intro nth_equalityI, auto simp: x_def)
  have "i \<le> nn" unfolding i_def by simp
  hence "horner_composition (map c [i..<Suc nn]) (map x [i..<Suc nn]) = b i nn"
  proof (induct i nn rule: b.induct)
    case (1 i n)
    show ?case
    proof (cases "n \<le> i")
      case True
      with 1(2) have i: "i = n" by simp
      show ?thesis unfolding i b.simps[of n n] by simp
    next
      case False
      hence "Suc i \<le> n" by simp
      note IH = 1(1)[OF False this]
      have bi: "b i n = b (Suc i) n * X i + [:c i:]" using False by (simp add: b.simps)
      from False have id: "[i ..< Suc n] = i # [Suc i ..< Suc n]" by (simp add: upt_rec)
      from False have id2: "[Suc i ..< Suc n] = Suc i # [Suc (Suc i) ..< Suc n]" by (simp add: upt_rec)
      show ?thesis unfolding id bi list.simps horner_composition.simps id2
        unfolding IH[unfolded id2 list.simps] by (simp add: X_def)
    qed
  qed
  thus ?thesis
    unfolding newton_poly_impl_def newton_coefficients rev_rev_ident newton_poly_def i_def
      assms[symmetric] xs .
qed
end
end

context
  fixes xs fs :: "int list"
begin

fun divided_differences_impl_int :: "int list \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int list \<Rightarrow> int list option" where
  "divided_differences_impl_int (xi_j1 # x_j1s) fj xj (xi # xis) = (
     case divided_differences_impl_int x_j1s fj xj xis of None \<Rightarrow> None
   | Some x_js \<Rightarrow> let (new,m) = divmod_int (hd x_js - xi_j1) (xj - xi)
     in if m = 0 then Some (new # x_js) else None)"
| "divided_differences_impl_int [] fj xj xis = Some [fj]"

fun newton_coefficients_main_int :: "int list \<Rightarrow> int list \<Rightarrow> int list list option" where
  "newton_coefficients_main_int [fj] xjs = Some [[fj]]"
| "newton_coefficients_main_int (fj # fjs) (xj # xjs) = (do {
    rec \<leftarrow> newton_coefficients_main_int fjs xjs;
    let row = hd rec;
    new_row \<leftarrow> divided_differences_impl_int row fj xj xs;
    Some (new_row # rec)})"
| "newton_coefficients_main_int _ _ = Some []"

definition newton_coefficients_int :: "int list option" where
  "newton_coefficients_int = map_option (map hd) (newton_coefficients_main_int (rev fs) (rev xs))"

lemma divided_differences_impl_int_Some:
  "length gs \<le> length ys
  \<Longrightarrow> divided_differences_impl_int gs g x ys = Some res
  \<Longrightarrow> divided_differences_impl (map rat_of_int gs) (rat_of_int g) (rat_of_int x) (map rat_of_int ys) = map rat_of_int res
    \<and> length res = Suc (length gs)"
proof (induct gs g x ys arbitrary: res rule: divided_differences_impl_int.induct)
  case (1 xi_j1 x_j1s fj xj xi xis)
  note some = 1(3)
  from 1(2) have len: "length x_j1s \<le> length xis" by auto
  from some obtain x_js where rec: "divided_differences_impl_int x_j1s fj xj xis = Some x_js"
    by (auto split: option.splits)
  note IH = 1(1)[OF len rec]
  have id: "hd (map rat_of_int x_js) = rat_of_int (hd x_js)" using IH by (cases x_js, auto)
  from some[simplified, unfolded rec divmod_int_def] have mod: "(hd x_js - xi_j1) mod (xj - xi) = 0"
    and res: "res = (hd x_js - xi_j1) div (xj - xi) # x_js" by (auto split: if_splits)
  have "rat_of_int ((hd x_js - xi_j1) div (xj - xi)) = rat_of_int (hd x_js - xi_j1) / rat_of_int (xj - xi)"
    using mod by force
  hence "(rat_of_int (hd x_js) - rat_of_int xi_j1) / (rat_of_int xj - rat_of_int xi) =
    rat_of_int ((hd x_js - xi_j1) div (xj - xi))"
    by simp
  thus ?case by (simp add: IH Let_def res id)
next
  case (2 fj xj xis res)
  hence res: "res = [fj]" by simp
  thus ?case by simp
qed simp

lemma div_Ints_mod_0: assumes "rat_of_int a / rat_of_int b \<in> \<int>" "b \<noteq> 0"
  shows "a mod b = 0"
proof -
  define c where "c = int_of_rat (rat_of_int a / rat_of_int b)"
  have "rat_of_int a / rat_of_int b = rat_of_int c" unfolding c_def using assms(1) by simp
  hence "rat_of_int a = rat_of_int b * rat_of_int c" using assms(2)
    by (metis divide_cancel_right nonzero_mult_div_cancel_left of_int_eq_0_iff)
  hence a: "a = b * c" by (simp add: of_int_hom.injectivity)
  show "a mod b = 0" unfolding a by simp
qed

lemma divided_differences_impl_int_None:
  "length gs \<le> length ys
  \<Longrightarrow> divided_differences_impl_int gs g x ys = None
  \<Longrightarrow> x \<notin> set (take (length gs) ys)
  \<Longrightarrow> hd (divided_differences_impl (map rat_of_int gs) (rat_of_int g) (rat_of_int x) (map rat_of_int ys)) \<notin> \<int>"
proof (induct gs g x ys rule: divided_differences_impl_int.induct)
  case (1 xi_j1 x_j1s fj xj xi xis)
  note none = 1(3)
  from 1(2,4) have len: "length x_j1s \<le> length xis" and xj: "xj \<notin> set (take (length x_j1s) xis)" and xji: "xj \<noteq> xi" by auto
  define d where "d = divided_differences_impl (map rat_of_int x_j1s) (rat_of_int fj) (rat_of_int xj) (map rat_of_int xis)"
  note IH = 1(1)[OF len _ xj]
  show ?case
  proof (cases "divided_differences_impl_int x_j1s fj xj xis")
    case None
    from IH[OF None] have d: "hd d \<notin> \<int>" unfolding d_def by auto
    {
      let ?x = "(hd d - rat_of_int xi_j1) / (rat_of_int xj - rat_of_int xi)"
      assume "?x \<in> \<int>"
      hence "?x * (of_int (xj - xi)) + rat_of_int xi_j1 \<in> \<int>"
        using Ints_mult Ints_add Ints_of_int by blast
      also have "?x * (of_int (xj - xi)) = hd d - rat_of_int xi_j1" using xji by auto
      also have "\<dots> + rat_of_int xi_j1 = hd d" by simp
      finally have False using d by simp
    }
    thus ?thesis
      by (auto simp: Let_def d_def[symmetric])
  next
    case (Some res)
    from divided_differences_impl_int_Some[OF len Some]
    have id: "divided_differences_impl (map rat_of_int x_j1s) (rat_of_int fj) (rat_of_int xj) (map rat_of_int xis) =
      map rat_of_int res" and res: "res \<noteq> []" by auto
    have hd: "hd (map rat_of_int res) = of_int (hd res)" using res by (cases res, auto)
    define a where "a = (hd res - xi_j1)"
    define b where "b = xj - xi"
    from none[simplified, unfolded Some divmod_int_def]
    have mod: "a mod b \<noteq> 0"
      by (auto split: if_splits simp: a_def b_def)
    {
      assume "(rat_of_int (hd res) - rat_of_int xi_j1) / (rat_of_int xj - rat_of_int xi) \<in> \<int>"
      hence "rat_of_int a / rat_of_int b \<in> \<int>" unfolding a_def b_def by simp
      moreover have "b \<noteq> 0" using xji unfolding b_def by simp
      ultimately have False using mod div_Ints_mod_0 by auto
    }
    thus ?thesis
      by (auto simp: id Let_def hd)
  qed
qed auto

lemma newton_coefficients_main_int_Some:
  "length gs = length ys \<Longrightarrow> length ys \<le> length xs
  \<Longrightarrow> newton_coefficients_main_int gs ys = Some res
  \<Longrightarrow> newton_coefficients_main (map rat_of_int xs) (map rat_of_int gs) (map rat_of_int ys) = map (map rat_of_int) res
    \<and> (\<forall> x \<in> set res. x \<noteq> [] \<and> length x \<le> length ys) \<and> length res = length gs"
proof (induct gs ys arbitrary: res rule: newton_coefficients_main_int.induct)
  case (2 fv v va xj xjs res)
  from 2(2,3) have len: "length (v # va) = length xjs" "length xjs \<le> length xs" by auto
  note some = 2(4)
  let ?n = "newton_coefficients_main_int (v # va) xjs"
  let ?ri = rat_of_int
  let ?mri = "map ?ri"
  from some obtain rec where n: "?n = Some rec"
    by (cases ?n, auto)
  note some = some[simplified, unfolded n]
  let ?d = "divided_differences_impl_int (hd rec) fv xj xs"
  from some obtain dd where d: "?d = Some dd" and res: "res = dd # rec"
    by (cases ?d, auto)
  note IH = 2(1)[OF len n]
  from IH have lenn: "length (hd rec) \<le> length xjs" by (cases rec, auto)
  with len have "length (hd rec) \<le> length xs" by auto
  note dd = divided_differences_impl_int_Some[OF this d]
  have hd: "hd (map ?mri rec) = ?mri (hd rec)" using IH by (cases rec, auto)
  show ?case unfolding newton_coefficients_main.simps list.simps
    IH[THEN conjunct1, unfolded list.simps] Let_def hd
    dd[THEN conjunct1] res
  proof (intro conjI)
    show "length (dd # rec) = length (fv # v # va)" using len
      IH[THEN conjunct2] dd[THEN conjunct2] by auto
    show "\<forall>x\<in>insert dd (set rec). x \<noteq> [] \<and> length x \<le> length (xj # xjs)"
      using len IH[THEN conjunct2] dd[THEN conjunct2] lenn by auto
  qed auto
qed auto

lemma newton_coefficients_main_int_None: assumes dist: "distinct xs"
  shows "length gs = length ys \<Longrightarrow> length ys \<le> length xs
  \<Longrightarrow> newton_coefficients_main_int gs ys = None
  \<Longrightarrow> ys = drop (length xs - length ys) (rev xs)
  \<Longrightarrow> \<exists> row \<in> set (newton_coefficients_main (map rat_of_int xs) (map rat_of_int gs) (map rat_of_int ys)). hd row \<notin> \<int>"
proof (induct gs ys rule: newton_coefficients_main_int.induct)
  case (2 fv v va xj xjs)
  from 2(2,3) have len: "length (v # va) = length xjs" "length xjs \<le> length xs" by auto
  from arg_cong[OF 2(5), of tl] 2(3)
  have xjs: "xjs = drop (length xs - length xjs) (rev xs)"
    by (metis 2(5) butlast_snoc butlast_take length_drop rev.simps(2) rev_drop rev_rev_ident rev_take)
  note none = 2(4)
  let ?n = "newton_coefficients_main_int (v # va) xjs"
  let ?n' = "newton_coefficients_main (map rat_of_int xs) (map rat_of_int (v # va)) (map rat_of_int xjs)"
  let ?ri = rat_of_int
  let ?mri = "map ?ri"
  show ?case
  proof (cases ?n)
    case None
    from 2(1)[OF len None xjs] obtain row where
      row: "row\<in>set ?n'" and "hd row \<notin> \<int>" by auto
    thus ?thesis by (intro bexI[of _ row], auto simp: Let_def)
  next
    case (Some rec)
    note some = newton_coefficients_main_int_Some[OF len this]
    hence len': "length (hd rec) \<le> length xjs" by (cases rec, auto)
    hence lenn: "length (hd rec) \<le> length xs" using len by auto
    have hd: "hd (map ?mri rec) = ?mri (hd rec)" using some by (cases rec, auto)
    let ?d = "divided_differences_impl_int (hd rec) fv xj xs"
    from none[simplified, unfolded Some]
    have none: "?d = None" by (cases ?d, auto)
    have "xj \<notin> set (take (length (hd rec)) xs)"
    proof
      assume "xj \<in> set (take (length (hd rec)) xs)"
      then obtain i where "i < length (hd rec)" and xj: "xj = xs ! i"
        unfolding in_set_conv_nth by auto
      with len' have i: "i < length xjs" by simp
      have "Suc (length xjs) \<le> length xs" using 2(3) by auto
      with i have i0: "i \<noteq> 0"
        by (metis 2(5) Suc_diff_Suc Suc_le_lessD diff_less dist distinct_conv_nth
          hd_drop_conv_nth length_Cons length_drop length_greater_0_conv length_rev less_le_trans
          list.sel(1) list.simps(3) nat_neq_iff rev_nth xj xjs)
      have "xj \<in> set xjs"
        by (subst xjs, unfold xj in_set_conv_nth, rule exI[of _ "length xjs - Suc i"], insert i 2(3) i0,
           auto simp: rev_nth)
      hence ndist: "\<not> distinct (xj # xjs)" by auto
      from dist have "distinct (rev xs)" by simp
      from distinct_drop[OF this] have "distinct (xj # xjs)" using 2(5) by metis
      with ndist
      show False ..
    qed
    note dd = divided_differences_impl_int_None[OF lenn none this]
    show ?thesis
      by (rule bexI, rule dd, insert some hd, auto)
  qed
qed auto

lemma newton_coefficients_int: assumes dist: "distinct xs"
  and len: "length xs = length fs"
  shows "newton_coefficients_int = (let cs = newton_coefficients (map rat_of_int xs) (map of_int fs)
    in if set cs \<subseteq> \<int> then Some (map int_of_rat cs) else None)"
proof -
  from len have len: "length (rev fs) = length (rev xs)" "length (rev xs) \<le> length xs" by auto
  show ?thesis
  proof (cases "newton_coefficients_main_int (rev fs) (rev xs)")
    case (Some res)
    have rev: "\<And> xs. map rat_of_int (rev xs) = rev (map of_int xs)" unfolding rev_map ..
    note n = newton_coefficients_main_int_Some[OF len Some, unfolded rev]
    {
      fix row
      assume "row \<in> set res"
      with n have "row \<noteq> []" by auto
      hence id: "hd (map rat_of_int row) = rat_of_int (hd row)" by (cases row, auto)
      also have "\<dots> \<in> \<int>" by auto
      finally have int: "hd (map rat_of_int row) \<in> \<int>" by auto
      have "hd row = int_of_rat (hd (map rat_of_int row))" unfolding id by simp
      note this int
    }
    thus ?thesis unfolding newton_coefficients_int_def Some newton_coefficients_def n[THEN conjunct1] Let_def option.simps
      by (auto simp: o_def)
  next
    case None
    have "rev xs = drop (length xs - length (rev xs)) (rev xs)" by simp
    from newton_coefficients_main_int_None[OF dist len None this]
    show ?thesis unfolding newton_coefficients_int_def newton_coefficients_def None by (auto simp: Let_def rev_map)
  qed
qed

definition newton_poly_impl_int :: "int poly option" where
  "newton_poly_impl_int \<equiv> case newton_coefficients_int of None \<Rightarrow> None
     | Some nc \<Rightarrow> Some (horner_composition (rev nc) xs)"

lemma newton_poly_impl_int: assumes len: "length xs = length fs"
  and dist: "distinct xs"
  shows "newton_poly_impl_int = (let p = newton_poly_impl (map rat_of_int xs) (map of_int fs)
    in if set (coeffs p) \<subseteq> \<int> then Some (map_poly int_of_rat p) else None)"
proof -
  let ?ir = "int_of_rat"
  let ?ri = "rat_of_int"
  let ?mir = "map ?ir"
  let ?mri = "map ?ri"
  let ?nc = "newton_coefficients (?mri xs) (?mri fs)"
  have id: "newton_poly_impl_int = (if set ?nc \<subseteq> \<int>
    then Some (horner_composition (rev (?mir ?nc)) xs) else None)"
    unfolding newton_poly_impl_int_def newton_coefficients_int[OF dist len] Let_def by simp
  have len: "length (rev ?nc) \<le> Suc (length xs)"
    unfolding length_rev
    by (subst newton_coefficients[OF refl], insert len, auto)
  show ?thesis unfolding id
    unfolding newton_poly_impl_def
    unfolding Let_def set_rev rev_map horner_coeffs_ints[OF len]
  proof (rule if_cong[OF refl _ refl], rule arg_cong[of _ _ Some])
    define cs where "cs = rev ?nc"
    define ics where "ics = map ?ir cs"
    assume "set ?nc \<subseteq> \<int>"
    hence "set cs \<subseteq> \<int>" unfolding cs_def by auto
    hence ics: "cs = ?mri ics" unfolding ics_def map_map o_def
      by (simp add: map_idI subset_code(1))
    have id: "horner_composition (rev ?nc) (?mri xs) = map_poly ?ri (horner_composition ics xs)"
      unfolding cs_def[symmetric] ics
      by (rule of_int_poly_hom.horner_composition_hom)
    show "horner_composition (?mir (rev ?nc)) xs
      = map_poly ?ir (horner_composition (rev ?nc) (?mri xs))"
      unfolding id unfolding cs_def[symmetric] ics_def[symmetric]
      by (subst map_poly_map_poly, auto simp: o_def map_poly_idI)
  qed
qed
end

definition newton_interpolation_poly :: "('a :: field \<times> 'a)list \<Rightarrow> 'a poly" where
  "newton_interpolation_poly x_fs = (let
    xs = map fst x_fs; fs = map snd x_fs in
    newton_poly_impl xs fs)"

definition newton_interpolation_poly_int :: "(int \<times> int)list \<Rightarrow> int poly option" where
  "newton_interpolation_poly_int x_fs = (let
    xs = map fst x_fs; fs = map snd x_fs in
    newton_poly_impl_int xs fs)"

lemma newton_interpolation_poly: assumes dist: "distinct (map fst xs_ys)"
  and p: "p = newton_interpolation_poly xs_ys"
  and xy: "(x,y) \<in> set xs_ys"
  shows "poly p x = y"
proof (cases "length xs_ys")
  case 0
  thus ?thesis using xy by (cases xs_ys, auto)
next
  case (Suc nn)
  let ?xs = "map fst xs_ys" let ?fs = "map snd xs_ys" let ?n = "Suc nn"
  from xy[unfolded set_conv_nth] obtain i where xy: "i \<le> nn" "x = ?xs ! i" "y = ?fs ! i"
    using Suc
    by (metis (no_types, lifting) fst_conv in_set_conv_nth less_Suc_eq_le nth_map snd_conv xy)
  have id: "newton_interpolation_poly xs_ys = newton_poly ?xs ?fs nn"
    unfolding newton_interpolation_poly_def Let_def
    by (rule newton_poly_impl[OF _ _ Suc], auto)
  show ?thesis
    unfolding p id
  proof (rule newton_poly_sound[of nn ?xs _ ?fs, unfolded
      Newton_Interpolation.x_def Newton_Interpolation.f_def, OF _ xy(1), folded xy(2-)])
    fix i j
    show "i < j \<Longrightarrow> j \<le> nn \<Longrightarrow> ?xs ! i \<noteq> ?xs ! j" using dist Suc nth_eq_iff_index_eq by fastforce
  qed
qed

lemma degree_newton_interpolation_poly:
  shows "degree (newton_interpolation_poly xs_ys) \<le> length xs_ys - 1"
proof (cases "length xs_ys")
  case 0
  hence id: "xs_ys = []" by (cases xs_ys, auto)
  show ?thesis unfolding
    id newton_interpolation_poly_def Let_def list.simps newton_poly_impl_def
    Newton_Interpolation.newton_coefficients_def
    by simp
next
  case (Suc nn)
  let ?xs = "map fst xs_ys" let ?fs = "map snd xs_ys" let ?n = "Suc nn"
  have id: "newton_interpolation_poly xs_ys = newton_poly ?xs ?fs nn"
    unfolding newton_interpolation_poly_def Let_def
    by (rule newton_poly_impl[OF _ _ Suc], auto)
  show ?thesis unfolding id using newton_poly_degree[of ?xs ?fs nn] Suc by simp
qed

text \<open>For @{const newton_interpolation_poly_int} at this point we just prove that it
  is equivalent to perfom an interpolation on the rational numbers, and then check
  whether all resulting coefficients are integers. That this corresponds to a
  sound and complete interpolation algorithm on the integers is proven in the theory
  Polynomial-Interpolation, cf.\ lemmas newton-interpolation-poly-int-Some/None.\<close>

lemma newton_interpolation_poly_int: assumes dist: "distinct (map fst xs_ys)"
  shows "newton_interpolation_poly_int xs_ys = (let
     rxs_ys = map (\<lambda> (x,y). (rat_of_int x, rat_of_int y)) xs_ys;
     rp = newton_interpolation_poly rxs_ys
     in if (\<forall> x \<in> set (coeffs rp). is_int_rat x) then
       Some (map_poly int_of_rat rp) else None)"
proof -
  have id1: "map fst (map (\<lambda>(x, y). (rat_of_int x, rat_of_int y)) xs_ys) = map rat_of_int (map fst xs_ys)"
    by (induct xs_ys, auto)
  have id2: "map snd (map (\<lambda>(x, y). (rat_of_int x, rat_of_int y)) xs_ys) = map rat_of_int (map snd xs_ys)"
    by (induct xs_ys, auto)
  have id3: "length (map fst xs_ys) = length (map snd xs_ys)" by auto
  show ?thesis
    unfolding newton_interpolation_poly_def  newton_interpolation_poly_int_def Let_def newton_poly_impl_int[OF id3 dist]
    unfolding id1 id2
    by (rule sym, rule if_cong, auto simp: is_int_rat[abs_def])
qed

hide_const
  Newton_Interpolation.x
  Newton_Interpolation.f
end

subset_name: curated


TITLE: Probability question help me please?
QUESTION [1 upvotes]: A company produces monitors.30 % of the monitors do not work.What is the probability that in a box with 15 monitors.
a) 3 monitors dont work
b) at least 6 monitors dont work
c) less than 10 monitors dont work.
I am thinking about solving this with Bayes' theorem,but I have no Idea how to apply it here? Any help or hint?

REPLY [2 votes]: I do not see a role for Bayes' Theorem.
We are intended to assume that with probability $0.30$, a randomly chosen monitor is defective, and that defectiveness of the various monitors in the box are independent events.
For (a), we are I think asked for the probability that exactly $3$ monitors are defective. The number of defective monitors in the box has binomial distribution, $n=15$, $p=0.30$. The probability that there are exactly $k$ defective is
$$\binom{15}{k}p^k(1-p)^{15-k}.\tag{1}$$
From this you can quickly find the probability of $3$ defectives.
For (b), we want the probability that the number of bads is $6$ or $7$ or $8$ or  $9$ or $\dots$. From (1) you can find the probability of $6$ bad, the probability of $7$ bad, and so on, and add  up.
It is easier to find the probability that the number of bads is $\lt 6$, by using (1) to find the probability of $0$ bad, $1$ bad, and so on up to $5$ bad. Add these up, and you get the probability of $5$ or fewer bad. From this you should be able to write down the probability of $6$ or more bad.
The last problem does not involve any new idea.


TITLE: What does 'coherent isomorphism' mean in the sense of pseudofunctors?
QUESTION [5 upvotes]: From what I've been able to find, psuedofunctors are not-quite-functors, in the sense that they preserve the identity morphism and composition of morphisms only up to coherent isomorphism, and not 'on the nose'.
But I'm struggling to find an explicit definition of what this means anywhere. The nLab has a large section on coherence theorems, but most of it is far above my head.
I'm assuming that it simply means 'isomorphic in a nice way', but I can't quite pin down what 'nice' means here.
Could anybody please explain what it does mean here?
Or even give a different definition of a pseudofunctor.

REPLY [7 votes]: The definition of pseudofunctors on nLab is actually quite explicit, but it's for pseudofunctors between bicategories. Borceux (Handbook of Categorical Algebra,  volume 1, 7.5) gives the definition for strict categories.
As for what a coherent (iso)morphism is, it's a morphism that satisfies coherence laws. These laws ensure that things that ought to be equal (and trivially would be, if the morphisms were identities) really are.
For example in this case you are given isomorphisms $φ : Ff ∘ Fg ≅ F(f ∘ g)$, but to do anything, you'll obviously need isomorphisms $Ff ∘ Fg ∘ Fh ≅ F(f ∘ g ∘ h)$ too, and similarly for any number morphisms.
Of course you can get from $Ff ∘ Fg ∘ Fh$ to $F(f ∘ g ∘ h)$ using $φ$, but you can do so in two ways: via $Ff ∘ F(g ∘ h)$ or via $F(f ∘ g) ∘ Fh$.
One of the coherence laws for pseudofunctors says that these two ways are the same. That given this, all paths (constructed from $φ$) from $F(f_1) ∘ ... ∘ F(f_n)$ to $F(f_1 ... f_n)$ are the same is then a part of the coherence theorem for pseudofunctors (but these can also be stated in more sophisticated ways).
As a side-note, monoidal categories are a good way to get familiar with coherence and coherence theorems. In a way, anybody who uses product of sets or tensor products already is.


text:
\section{Introduction}
\label{sec:Intro}
A fundamental fact of Fourier analysis is that no non-zero signal can be simultaneously bandlimited and timelimited. Thus, a compactly supported non-zero function cannot have a compactly supported Fourier transform, and a non-zero function whose Fourier transform is compactly supported cannot itself be compactly supported. Between 1960 and 1978, Landau, Pollak, and Slepian published a series of seminal papers \cite{SlepianPollakI, LandauPollakII, LandauPollakIII, SlepianIV, SlepianV} exploring to what extent a bandlimited signal can be timelimited and to what extent a timelimited signal can be bandlimited. They formulate both of these questions as eigenproblems involving bandlimiting and timelimiting operators. In the continuous-time case, the eigenfunctions which are bandlimited to the frequency band $[-\Omega,\Omega]$ and are maximally concentrated in the time interval $[-\tfrac{T}{2},\tfrac{T}{2}]$ are known as the prolate spheroidal wave functions (PSWFs). In the discrete-time case, the eigensequences which are bandlimited to frequencies $[-W,W]$ and are maximally concentrated in the time indices $\{0,1,\ldots,N-1\}$ are known as the discrete prolate spheroidal sequences (DPSSs).

By truncating the DPSSs, one can form the Slepian basis vectors, which are an efficient basis for representing a window of samples from bandlimited signals \cite{DavenportWakin12,ZhuWakin17,KarnikFST}. As such, Slepian basis vectors can be used in a variety of applications. Some classic applications include prediction of bandlimited signals based on past samples \cite{SlepianV} and Thomson's multitaper method for spectral analysis \cite{Thomson82}. More recent applications include time-variant channel estimation \cite{Zemen05,Zemen07}, wideband
compressive radio receivers \cite{Davenport10}, compressed sensing of analog signals \cite{DavenportWakin12}, target detection \cite{Yin12,ZhuWakin15}, and a fast method \cite{Matthysen16} for computing Fourier extension series coefficients \cite{Huybrechs10, Adcock14}.

The eigenvalues associated with the PSWFs as well as the DPSSs (which we will refer to in this paper as the PSWF eigenvalues and the DPSS eigenvalues respectively) exhibit a particular clustering behavior. All of these eigenvalues are strictly between $0$ and $1$. Furthermore, most of these eigenvalues are either very close to $1$ or very close to $0$, and very few of these eigenvalues are not near $1$ or $0$. This clustering behavior plays a critical role in many applications. In \cite{Abreu17}, it is shown that the bias of Thomson's multitaper spectral estimator depends on the sum of the leading DPSS eigenvalues. In \cite{DavenportWakin12}, it is shown that the number of DPSS eigenvalues not near $0$ determines the effective dimension of a vector of samples from a bandlimited signal. Also, the sum of the trailing DPSS eigenvalues bounds the error in approximating a vector of samples from a bandlimited signal by a linear combination of the leading DPSSs. In \cite{Matthysen16,KarnikFST,KarnikSampTA19}, the fact that only a small number of DPSS eigenvalues are not near $1$ or $0$ is exploited to perform fast computations. As such, the behavior of the DPSS eigenvalues is of considerable interest. There are many results (both asymptotic and non-asymptotic) regarding the eigenvalues associated with the PSWFs \cite{SlepianPollakI,LandauPollakIII,LandauWidom80,Hogan11,Osipov13,Israel15,Bonami17,Bonami18}. However, there are far fewer results regarding the DPSS eigenvalues. Furthermore, the existing non-asymptotic results don't fully capture the behavior of the DPSS eigenvalues or the PSWF eigenvalues.

The main contribution of this work is establishing a novel non-asymptotic bound on the number of DPSS eigenvalues which are not close to $1$ or $0$, as well as non-asymptotic bounds on the DPSS eigenvalues themselves. We show that for any threshold $\eps \in (0,\tfrac{1}{2})$, the number of DPSS eigenvalues which lie in the interval $(\eps,1-\eps)$ is bounded above by a quantity that scales like $O(\log(NW)\log\tfrac{1}{\eps})$. This improved bound is similar to the known asymptotic result and is a significant improvement over existing non-asymptotic bounds which scale like $O(\log(NW)/\eps)$ or $O(\log N \log \tfrac{1}{\eps})$. Furthermore, the fact that our bound depends on the time-bandwidth product $NW$ as opposed to the time duration $N$ allows us to obtain non-asymptotic bounds on the PSWF eigenvalues, which are also similar to the known asymptotic result and a substantial improvement over existing non-asymptotic results.

The rest of this work is organized as follows. In Section~\ref{sec:Preliminaries}, we define DPSSs, Slepian basis vectors, and PSWFs, as well as review their basic properties. In Sections~\ref{sec:PrevDPSSBounds} and \ref{sec:PrevPSWFBounds}, we will outline existing results on the DPSS eigenvalues and the PSWF eigenvalues respectively. In Section~\ref{sec:NewResults}, we state our new results. In Section~\ref{sec:MainProof}, we prove two novel non-asymptotic bounds on the number of DPSS eigenvalues that are not within $\eps$ of $1$ or $0$. In Section~\ref{sec:DPSSEigenvalueBounds}, we use the two new bounds to derive non-asymptotic bounds on the DPSS eigenvalues themselves, as well as the sum of the leading and trailing DPSS eigenvalues. In Section~\ref{sec:PSWFProofs}, we apply the results on DPSS eigenvalues to prove our results on PSWF eigenvalues. Finally, we conclude the paper in Section~\ref{sec:NumericalResults} with some numerical results to demonstrate the quality of our non-asymptotic bounds on the number of DPSS eigenvalues in $(\eps,1-\eps)$.


TITLE: Proving that an operator $K$ is bounded and $||K|| = \max_{0\leq x\leq 1}\bigg\{\int_0^1|k(x,y)|dy\bigg\}$
QUESTION [2 upvotes]: Define $K:C([0,1])\rightarrow C([0,1])$ by
$$Kf(x) = \int_0^1 k(x,y)f(y)dy,$$
where $k:[0,1]\times [0,1]\rightarrow \mathbb{R}$ is continuous. Prove that $K$ is bounded and
$$||K|| = \max_{0\leq x\leq 1}\bigg\{\int_0^1|k(x,y)|dy\bigg\}.$$
This is what I have so far:
Let $A = \max_{0\leq x\leq 1}\bigg\{\int_0^1|k(x,y)|dy\bigg\} = \max_{0\leq x\leq 1}\bigg\{\int_0^1|k(x_0,y)|dy\bigg\}$.
$|Kf(x)|\leq ||f||\int_0^1 |k(x,y)|dy \leq ||f||A$.
$\implies$ $||Kf|| = \sup_{0\leq x\leq 1}|Kf(x)| \leq A||f||$
$\implies$ $||K||\leq A$.
Now I know that I want to show that $||K||\geq A$ to have equality but I am not sure how to do so.
I should also note this is not a homework question. I am attempting to do all the problems in my book for better understanding.
Any help and comments would be appreciated. Thank you.

REPLY [0 votes]: So you need to approximate $f_{\infty}$ with a sequence of functions $f_{n}$ such that $f_{n}$ is continuous. $f_{\infty}$ can be written as $\frac{x}{|x|}$. Now, you just have to modify the formula for $f_{\infty}$ by adding something small and you'll get a continuous $f_{n}$ that'll converge to $f_{\infty}$. Then if you take the limit you get the >= case, and you'll have equality.