Let $b_{\ast }$ be the smallest threshold for which the edges of length at most $b_{\ast }$ connect $x$ to $y$. This is exactly the optimum value of the bottleneck shortest path problem. While any edge longer than $b_{\ast }$ is being processed, every edge of some threshold-$b_{\ast }$ route is still present, because shorter edges have not yet been processed. Thus all edges longer than $b_{\ast }$ are deleted. The final path from part (i) consequently has maximum edge length at most $b_{\ast }$. It cannot have a smaller maximum by the definition of $b_{\ast }$, proving optimality. Ties in edge ordering do not affect this argument.

There is an index slip in the source: starting with $G_1$ and performing steps $1,\dots ,n$ produces the final graph $G_{n+1}$. Write $H$ for that final graph. The literal assertion for $G_n$ can fail: take a triangle with $\ell (xz)=3$, $\ell (xy)=2$, $\ell (yz)=1$. Before the final step the extra edge $yz$ remains; only the final deletion removes it.

The invariant is that $x$ and $y$ remain connected. Choose a simple $xy$ graph path $P$ in $H$. If an edge of $H$ did not lie in $P$, then at its processing time $P$ was still present and avoided that edge. The algorithm would therefore have deleted it, a contradiction. Thus every edge of $H$ lies in $P$. The final graph is precisely an $xy$ path and possibly isolated vertices.

Starting from $3$, the initial tentative distances to $0,1,2,4$ are $5,7,9,13$. Finalize $0$ next. Its edges improve these to $d(1)=5+1=6$, $d(2)=5+3=8$, and $d(4)=5+7=12$. No subsequent relaxation improves them. Hence one shortest-path tree isThese values follow either by completing Dijkstra's algorithm in the order $3,0,1,2,4$, or by observing that any internal vertex $w$ on a simple route adds $4w-1$ to the direct-edge cost: only the internal vertex $0$ can reduce it.

For Dijkstra's algorithm, initialize $d(x)=0$ and $d(v)=\infty$ for other vertices, with no predecessor initially. Repeatedly select an unfinalized vertex $u$ of least tentative distance, finalize it, and relax each edge $uv$: if $d(u)+\ell (uv)<d(v)$, replace $d(v)$ by that value and set the predecessor of $v$ to $u$. Continue until all vertices are finalized. The predecessor edges form the shortest-path tree.

To justify finalization, consider a supposedly shorter route to the next selected vertex. Its first unfinalized vertex is preceded by a finalized one, whose relaxation would already have offered a tentative distance no greater than the length of that route's prefix. Nonnegative remaining lengths would contradict the selected vertex's minimal tentative label. Thus final labels are the true shortest distances. Strictly positive lengths also make predecessors have smaller distances, ruling out predecessor cycles in a graph.

A shortest-path tree rooted at $x$ is a spanning tree $T$ such that, for every vertex $v$, the unique $xv$ graph path in $T$ has minimum total edge length among all $xv$ graph paths in $G$. The objective is the sum of the lengths along each route, not the sum of all the tree's edge lengths.

A spanning tree of the connected graph $G$ is a subgraph containing every vertex, connected and without cycles in a graph. Equivalently, between every pair of vertices it has exactly one graph path. For a finite graph with $v$ vertices, it has $v-1$ edges.

In the space of tempered distributions, this Fourier transform convention gives $\hat{1}=2\pi \delta$ and $\hat{\delta }=1$. ThereforeThe constant distribution and the Dirac delta distribution are linearly independent: testing away from zero first determines the constant coefficient, and then testing at zero determines the delta coefficient. Hence $c=\lambda$ and $\lambda c=2\pi$, giving

At zero, the Fourier transform is $\hat{f}(0)=\int f=1$, so $\lambda f(0)=1$. In particular $\lambda \ne 0$ and $f(0)=1/\lambda$. The Fourier inversion theorem at zero also givesEquating the two values yields $\boxed{{\lambda }^2=2\pi }$. Since the explicit normalized Gaussian function in part (i) has $f(0)>0$, here $\lambda =\sqrt{2\pi }$.

Use the Fourier transform convention $\hat{f}(s)={\int }_{\mathbb{R}}{e}^{-isx}f(x)dx$. First observe that $f(x)=(2\pi {)}^{-1/2}{e}^{-x^2/2}$ satisfies the differential equation, decay, and normalization, using the Gaussian integral. The uniqueness allowed in the question identifies it with $f$. In particular it is a Schwartz function, so the derivative and multiplication rules below are justified.

Taking the Fourier transform of the differential equation givesThe Riemann-Lebesgue lemma gives decay of $\hat{f}$. Every decaying solution $h$ of this equation is proportional to $e^{-s^2/2}$: setting $w=h^{\prime }+sh$ gives $w^{\prime }=sw$, and integration yieldsThe term with $C\ne 0$ grows like $C{e}^{s^2/2}/(2s)$ as $s\to +\infty$, so decay forces $C=0$. Thus $\hat{f}=\lambda f$ for a scalar $\lambda$. This establishes proportionality before using Fourier inversion to calculate the scalar.

The integral $I$ is the convolution of the positive-half-line kernels $x^{a-1}$ and $x^{b-1}$. The convolution theorem for Laplace transforms therefore gives, for $p>0$,On the other hand, the substitution $t=xu$ gives $I(x)=x^{a+b-1}B(a,b)$, where $B(a,b)={\int }_0^1{u}^{a-1}(1-u{)}^{b-1}du$ is the beta function. Applying part (i) again yields $\mathcal{L}I(p)=B(a,b)\Gamma (a+b)p^{-(a+b)}$. Comparing the two expressions provesAll integrands used in the real-$p$ convolution argument are nonnegative, so Tonelli's theorem justifies the interchange; the endpoint singularities are integrable because $a,b>0$.

For real $p>0$, substitute $t=px$ in the Laplace transform:The Gamma function integral is finite because $a>0$. For complex $p$, absolute convergence holds exactly when $\mathrm{Re}p>0$: the modulus of the integrand is $x^{a-1}{e}^{-(\mathrm{Re}p)x}$. On this half-plane the same answer holds with the branch $p^{-a}=\exp (-a\mathrm{Log}p)$ whose logarithm is real on the positive axis, by holomorphic continuation of the two sides.

If “exists” permits conditionally convergent ordinary improper integrals, there are additional boundary points when $0<a<1$: for $p=i\omega \ne 0$, the Dirichlet test gives convergence, with value $\Gamma (a)|\omega {|}^{-a}{e}^{-i\mathrm{sgn}(\omega )\pi a/2}$. For $a\ge 1$ these boundary integrals do not converge in that sense. At $p=0$, and for $\mathrm{Re}p<0$, the integral diverges. Thus $\mathrm{Re}p>0$ is the region of absolute convergence of a Laplace transform, with the stated conditional boundary qualification.

The linear map $\pi (A)=(A+A^T)/2$ is the projection onto the space $\mathcal{S}$ of symmetric matrices, with kernel $\mathcal{A}$. Define $F=\pi \circ L$ on $V$. Since $DL$ is invertible everywhere on $V$ and $\pi$ is onto, $DF$ is onto everywhere. By part (ii),The regular level set theorem makes this a submanifold of codimension $\dim \mathcal{S}=n(n+1)/2$, and henceThis neighborhood is $V$ around $I$; the source's final occurrence of $U$ in this step is a neighborhood-label slip. For any $Q\in O(n)$, left multiplication by $Q$ is an invertible linear map of the ambient matrix space and carries $V\cap O(n)$ onto $QV\cap O(n)$. These translated charts establish the submanifold property at every group element.

Part (b) already shows $\exp (U\cap \mathcal{A})\subset V\cap O(n)$. Conversely, if $Q\in V\cap O(n)$ and $A=L(Q)\in U$, thenBoth $A^T$ and $-A$ lie in $U$, where the matrix exponential is injective. Therefore $A^T=-A$, proving the reverse inclusion. The restricted map is a bijection, indeed a diffeomorphism between these local sets.

The matrix exponential is smooth, and part (a) identifies its derivative at zero as the identity. The inverse function theorem therefore gives a local diffeomorphism from an open neighborhood $U_0$ of zero onto a neighborhood of $I$. Choose a sufficiently small operator norm ball $U\subset U_0$ and let $V=\exp U$. This is again a diffeomorphism onto an open set, since it is a restriction of the original one.

The ball $U$ is preserved by $A\mapsto A^T$ and $A\mapsto -A$. Since $(\exp A{)}^T=\exp (A^T)$ and $(\exp A{)}^{-1}=\exp (-A)$, $V$ is preserved by adjoint and inversion. For its local inverse $L$, injectivity also gives

If $Q(t)$ is a smooth curve of orthogonal matrices with $Q(0)=I$, differentiating $Q(t{)}^{T}Q(t)=I$ gives $Q^{\prime }(0{)}^T+Q^{\prime }(0)=0$. Thus each tangent velocity is a skew-symmetric matrix.

Conversely, if $A^T=-A$, the curve $Q(t)=\exp (tA)$ satisfiesusing commutation of $-tA$ and $tA$. By part (a), $Q^{\prime }(0)=A$. Both inclusions prove

The curve-based tangent space at $x$ consists of velocities ${\gamma }^{\prime }(0)$ of smooth curves $\gamma :(-\epsilon ,\epsilon )\to M$ satisfying $\gamma (0)=x$. For an arbitrary subset these velocities need not form a vector space; for a smooth submanifold they do, and this is its usual tangent space. This definition suffices for the direct computation at the identity.

The identity $T=S^{-1}(ST)$ shows that $S,ST$ generate the same group. Direct multiplication givesConsequently their images $\bar{S},\overline{ST}$ in the quotient group $PSL(2,\mathbb{Z})$ satisfy ${\bar{S}}^2=1$ and ${\overline{ST}}^3=1$. The universal property of a group presentation gives a group homomorphism taking $u\mapsto \bar{S}$, $v\mapsto \overline{ST}$ from the stated presentation. It is surjective because these images generate the target. Injectivity is not needed here.

After the reduction in part (b), multiply by $S$. The new bottom-left entry is $r$, whose absolute value is strictly smaller than the previous $|c|$:Repeated Euclidean division must terminate because the nonnegative integers $|c|$ decrease strictly until zero. Thus a word $W$ in $S,T$ and their inverses gives a matrix with bottom-left entry zero. Its determinant is one, so the diagonal entries are equal and are either both $1$ or both $-1$:Since $S^2=-I$, this final matrix belongs to $⟨S,T⟩$. So does $W^{-1}$, proving

For $f(x)=x^2-n$, a root modulo the odd prime $p$ is nonzero because $p\nmid n$. Its derivative $2x$ is therefore nonzero modulo $p$. Part (i) gives exactly one lift of each root. A nonzero quadratic residue modulo an odd prime has two distinct roots, $x$ and $-x$; a nonresidue has none. Hence

Let $a$ be a root modulo $p^j$. Every lift to a residue modulo $p^{j+1}$ is uniquely $a+t{p}^j$ with $t(\mathrm{mod}p)$. The polynomial expansion givesBecause $a(\mathrm{mod}p)$ is a root and there are no common roots of $f$ and $f^{\prime }$, $f^{\prime }(a)$ is nonzero modulo $p$. Thus precisely one $t$ solvesEvery root at one level therefore has exactly one lift, and every root at the next level reduces to a root at the previous level. Induction proves equality of the counts from $p$ to $p^l$. This is simple-root Hensel lifting by successive residues at finite precision; completeness is unnecessary for this finite-level assertion.