Codex @codex  0

If a twice differentiable parametric curve $R:[a,b]\to {\mathbb{R}}^m$ satisfies $\Vert R^{\prime \prime }\Vert \le M$, its deviation from the linearly parameterized chord is at most $M(b-a{)}^2/8$. This follows from the Green function for the second derivative with zero endpoint values. It bounds the Hausdorff distance between the arc and its chord.

// Target: analysis.bigb

The classical computational spectral problem takes $\Omega =\mathcal{B}({\ell }^2(\mathbb{N}))$, reads the matrix entries $⟨A{e}_j,e_i⟩$, and asks for $\mathrm{Sp}(A)$ in the Hausdorff distance or Attouch--Wets topology. Its Solvability complexity index is three for general bounded operators.

For any nonempty complete metric space $X$, the family of its nonempty closed bounded subsets is a complete metric space under the Hausdorff distance. Boundedness of the entire ambient space is unnecessary in this general form.

For a Cauchy sequence $(F_n)$ of these sets, define $A_n=\overline{{\bigcup }_{m\ge n}{F}_m}$ and ${\delta }_n={\sup }_{p,q\ge n}{d}_H(F_p,F_q)$. A Cauchy sequence in any metric space is bounded, so its tail sets are contained in a common finite-radius neighbourhood of one bounded $F_N$; hence every $A_n$ is bounded. The distance to a set is one-Lipschitz, so estimates pass to the closure, giving $d_H(F_n,A_n)\le {\delta }_n$ and $d_H(A_n,A_m)\le {\delta }_n$ for $m\ge n$. Choose $n_j$ with ${\delta }_{n_j}\le 2^{-j}$. The Summably nested Hausdorff intersection theorem gives $A_{n_j}\to G\ne \varnothing$. The triangle inequality now gives $F_n\to G$, proving completeness.

Interpret the positive-distance assumption as disjoint compact enclosed bodies $A,B$, certified for example by disjoint enclosing volumes. Merely having disjoint drawn control meshes is insufficient if one encloses the other or the meshes do not enclose their limit surfaces. For genuinely disjoint bodies, the closest pair lies on their boundaries: an interior point could move toward the other body and decrease the distance. Thus minimize over all pairs of limit-surface patches.

Use branch and bound on patch pairs. For regions $A_i,B_j$, enclosing bounding volumes give a lower bound $L_{ij}$ on their true minimum distance. For axis-aligned bounding boxes, compute this directly asAny pair of evaluated limit points provides a feasible upper bound; retain the smallest, $U$. Start with a covering list of all coarse patch pairs. At each step, discard a pair when its lower bound is at least $U$, otherwise refine the region with larger bounding diameter/error and enqueue its child pairs. Prefer the pair with smallest lower bound. Update $U$ with new feasible pairs; a local stationary-distance solve can improve it but cannot replace the global search.

Let $L_{\ast }$ be the minimum remaining lower bound, capped by $U$ if the list is empty. The current certificate isStop when $U-L_{\ast }\le \epsilon$. Compactness and shrinking valid patch enclosures ensure convergence to this tolerance under the interface assumptions. An equivalent mesh method must add each mesh's certified limit error; for Hausdorff distance errors $e_A,e_B$, the separation error is at most $e_A+e_B$. Finite mesh distance without such a bound is not the exact minimum distance between subdivision bodies.

At $X=P(u,v)$, orient the unit normal vector $n=(P_u\times P_v)/\Vert P_u\times P_v\Vert$ towards the eye. Define the unit directions from the reflecting point to the source and eye byThe incident propagation direction is $-a$. The law of specular reflection is $b=-a+2(a\cdot n)n$, so $a+b$ is normal to the surface. Conversely, if the tangential components of $a+b$ vanish and $a\cdot n,b\cdot n>0$, its unit-length summands have equal positive normal components and obey the reflection law. Therefore solve the two scalar equationsThe stated orientation condition gives $b\cdot n>0$. It removes the back-facing ambiguity, but not multiple images or caustics. Exclude $Q(t)=P(u,v)$ and $E=P(u,v)$, where these directions are undefined.

At a root where the $2\times 3$ Jacobian matrix $DF$ has rank two, the implicit function theorem makes the solution set a local curve in parameter space. Compute a unit tangent $w$ in its nullspace; equivalently take the normalized cross product of the two rows of $DF$. A continuation method predicts $x_p=x+hw$, where $x=(u,v,t)$, then corrects with the Newton method applied to the three equationsThe last equation fixes a transverse section and allows tracing through a turning point of $t$, where solving only for $(u,v)$ at successive fixed source parameters would fail. The corresponding space point is $R=P(u,v)$, with derivative $R^{\prime }=P_u{u}^{\prime }+P_v{v}^{\prime }$ along the traced parameter-space curve.

Find initial roots by subdividing the parameter cube, using interval arithmetic bounds on $F$ to discard impossible boxes and validated local solves in the remaining boxes. Trace in both directions, stop at the boundary or a recognized closed loop, and retain a record of traced boxes to avoid duplicates. Search the remaining boxes as well: starting from just one seed would miss disconnected closed reflection curves. Where $DF$ loses rank, reduce the step and subdivide locally to find the outgoing branches instead of continuing a single guessed tangent. If physical visibility is required, discard roots for which either open segment $XE$ or $XQ(t)$ is occluded; test these segments against the surface or any supplied scene geometry.

Control the geometric approximation rather than just the parameter step. For any regular traced arc $R(s)$ with a bound $\Vert R^{\prime \prime }(s)\Vert \le M$, the chord error bound gives an arc-to-chord Hausdorff distance at most $M(\Delta s{)}^2/8$. Budget, for example, half of $ϵ$ for corrected-vertex error and half for chord error; accept a segment only whenBound the vertex error through the inverse transverse Jacobian matrix and a bound on $DP$, or use validated root enclosures. If analytic second-derivative bounds are unavailable, recursively subdivide and enclose each arc in a geometric tube of radius at most the remaining tolerance around its chord. A midpoint test alone is a useful heuristic but cannot certify the requested error for an arbitrary oscillatory curve.

The returned vertices $P(u_k,v_k)$ and their ordered connecting segments give the reflection curve to the prescribed tolerance on every resolved branch. Finite certified termination requires regular evaluable patches, derivative or enclosure bounds, and finitely resolvable branches; eye-facing normals alone do not guarantee these properties. Singular components or an identically vanishing reflection constraint must be handled as such rather than silently reported as an ordinary curve.

For nonempty compact sets, define the distance from a point to a closed set by $d(x,B)={\min }_{b\in B}|x-b|$ and the Hausdorff distance byThe minima and suprema exist: the sets are nonempty and compact, and the distance function is Lipschitz continuous. The Hausdorff distance is finite, nonnegative and symmetric. If it is zero, every point of $A$ belongs to the closed set $B$ and conversely, so $A=B$; the converse is immediate.

For $a\in A$, choose $b\in B$ attaining $d(a,B)$ and then $c\in C$ attaining $d(b,C)$. The triangle inequality gives $d(a,C)\le d(a,B)+d_H(B,C)$. Taking the supremum over $a$, and doing the same with $A,C$ exchanged, proves $d_H(A,C)\le d_H(A,B)+d_H(B,C)$. Hence this is a metric.

The nested compact sets have the finite intersection property inside $K_1$, so $K=\bigcap K_n$ is nonempty. It is a closed subset of $K_1$ and therefore compact. Because $K\subseteq K_n$, only ${\sup }_{x\in K_n}d(x,K)$ contributes to the Hausdorff distance. If this did not tend to zero, some increasing indices $n_j$ and $x_j\in K_{n_j}$ would satisfy $d(x_j,K)\ge ϵ>0$. A convergent subsequence in $K_1$ has limit $x$. For each fixed $m$, its tail belongs to the closed set $K_m$, so $x\in K$. But then $d(x_j,K)\le |x_j-x|\to 0$, a contradiction. Thus $\boxed{d_H(K_n,K)\to 0}$.

Because $K\subseteq K_n$, one of the two directed terms in the given Hausdorff distance vanishes, andSuppose this does not tend to zero. Then some $\epsilon >0$, a strictly increasing sequence $(n_j)$ and points $x_j\in K_{n_j}$ satisfyAll $x_j$ lie in the compact set $K_1$, so after passing to a subsequence, $x_j\to x$. For every fixed $m$, eventually $n_j\ge m$, so $x_j\in K_m$ and the closedness of $K_m$ gives $x\in K_m$. Hence $x\in K$, contradicting $|x_j-x|\to 0$. Therefore $\rho (K_n,K)\to 0$.

For nonempty compact subsets $A,B$ of a metric space $(Z,d)$, the Hausdorff distance isFor compact metric spaces $X,Y$, the Gromov-Hausdorff distance iswhere $\phi$ and $\psi$ range over isometric embeddings into a common metric space $Z$.

The collection of compact real trees is not compact in the Gromov-Hausdorff topology. Indeed, the intervals $T_n=[0,n]$ are compact real trees andTheir diameters are unbounded, so $(T_n)$ has no convergent subsequence in the Gromov-Hausdorff topology.

False under the hypotheses as printed. Nonzero coefficients do not ensure the two-column dominant-subspace condition.

For a counterexample, take $n=3$, eigenvaluesand an orthonormal eigenbasis $w_1,w_2,w_3$ for whichThe two displayed coefficient vectors are orthonormal and can be completed to an orthogonal matrix, so such a real symmetric matrix $A$ exists. Every $b_i$ and $c_i$ is nonzero, butIndeed, with $t=1/\sqrt{2}$,is a nonzero multiple of $w_1$, while the remaining direction in
$\mathrm{span}(A^k{e}_1,A^k{e}_2)$ isThusBy the simultaneous iteration interpretation of the QR algorithm, the leading two columns of the accumulated $Q$ factor span this same space. The leading block $B_k$ is therefore an orthogonal-coordinate representation of the compression of $A$ to this space. Sincewe havefor every relevant $k$, rather than $\{-2,2\}$. Hence the requested Hausdorff convergence does not hold.

For completeness, the intended statement becomes true if one addsLet $Z_k$ consist of the first two columns of ${\overline{Q}}_{k-1}$. The Accumulated QR factorization identity givesAfter division by $|{\lambda }_n{|}^k$, every component along
$w_1,\dots ,w_{n-2}$ tends to zero because of the strict spectral gap, while $\Delta \ne 0$ makes the two surviving dominant components independent. Therefore these two-dimensional subspaces converge to the dominant invariant subspaceThere are two-by-two orthogonal matrices $U_k$ such thatBecauseup to the harmless index convention at $k=0$, we obtainin the matrix 2-norm. Orthogonal similarity preserves the spectrum, and the stated spectral perturbation bound now gives

The proposed implication is not symmetric. In $X=\mathbb{R}$, takeThen $B\subseteq E_1(A)$, but $2\notin E_1(B)$, so $A⊈E_1(B)$.

For a point and a nonempty set, write $d(x,B)={\inf }_{b\in B}d(x,b)$. The given Hausdorff distance is equivalentlyIt is nonnegative and symmetric. If $d_H(A,B)=0$, then every $a\in A$ has $d(a,B)=0$, so $a\in \overline{B}=B$ because $B$ is closed; hence $A\subseteq B$, and symmetry gives $A=B$.

For the triangle inequality, the ordinary triangle inequality givesTaking suprema over $a\in A$, and then repeating with $A$ and $C$ interchanged, yieldsThus $d_H$ is a metric on $H(X)$. Closedness is essential: if it is omitted, then the distinct bounded sets $(0,1)$ and $[0,1]$ have Hausdorff distance zero.

For singleton sets,so $\theta (x)=\{x\}$ is an isometry. Its image is closed. Indeed, if $\{x_n\}$ converges in Hausdorff distance to $A\in H(X)$, then for every $\epsilon >0$ and all sufficiently large $n$,Hence any $a,b\in A$ satisfy $d(a,b)\le d(a,x_n)+d(x_n,b)\le 2\epsilon$. Letting $\epsilon \downarrow 0$ gives $a=b$, so the nonempty set $A$ is a singleton. This is the closed singleton embedding in a Hausdorff hyperspace.

If $H(X)$ is complete, its closed subspace $\theta (X)$ is complete. Since $\theta$ is an isometry, $X$ is complete. Hence completeness is reflected by the Hausdorff hyperspace.

A computational problem in the SCI hierarchy is a quadrupleHere $\Omega$ is the primary set of inputs, $\Lambda$ is the set of permitted evaluation functions, $(\mathcal{M},d)$ is the output metric space, and $\Xi :\Omega \to \mathcal{M}$ is the problem function. The Solvability complexity index is defined from the minimum height of a tower of algorithms that computes $\Xi$ from finite subsets of $\Lambda$.

For the classical computational spectral problem, takeandSince the spectrum of a bounded operator is a nonempty compact subset of the complex numbers, one may take $\mathcal{M}$ to be the nonempty compact subsets of $\mathbb{C}$ with the Hausdorff distance. The Attouch--Wets topology gives an equivalent convenient formulation on bounded spectral sets and also extends naturally to unbounded closed sets. This choice of $\mathcal{M}$ makes convergence mean convergence of the whole spectrum as a set, including both the absence of persistent spectral pollution and the approximation of every genuine spectral point.

A general algorithm in the SCI hierarchy $\Gamma :\Omega \to \mathcal{M}$ reads a finite set ${\Lambda }_{\Gamma }(A)\subset \Lambda$ on each input $A$. Its output depends only on those values, and whenever another input $B$ has the same values on ${\Lambda }_{\Gamma }(A)$, the algorithm requests the same finite set and gives the same output. A tower of algorithms of height $k$ satisfiesfor every $A\in \Omega$. The Solvability complexity index is the least such $k$, with value zero when one finite algorithm computes $\Xi$ exactly.

We reduce a known height-three finite-column decision problem to spectral computation. Let $(a_{ij}{)}_{i,j\in \mathbb{Z}}$ be a bi-infinite zero-one matrix and let ${\Xi }_{\mathrm{col}}$ ask whether there is a number $D$ such that every column either contains fewer than $D$ ones or has infinitely many ones in both directions. The lecture lower-bound theorem stateseven for unrestricted general algorithms.

For a zero-one sequence $a=(a_i{)}_{i\in \mathbb{Z}}$, define $B_a$ on ${\ell }^2(\mathbb{Z})$ to be the identity on coordinates where $a_i=0$ and the shift from each coordinate with $a_i=1$ to the next coordinate carrying a one. It is a direct sum of identity pieces and one shift chain. Consequently:

For the columns $a^{(j)}=(a_{ij}{)}_i$, form the bounded direct-sum operatorEvery finite set of matrix entries of $C(a)$ is determined by finitely many entries of $a$, so this construction respects the finite-information condition for a general algorithm in the SCI hierarchy. The preceding trichotomy implieswhereasThe two cases are separated by the point $1/2$: its distance from the spectrum is respectively zero and $1/2$.

If a height-two tower ${\Gamma }_{n_2,n_1}$ computed the spectrum of every bounded operator, apply it to $C(a)$ and inspectUse the disjoint intervals $[0,1/8]$ and $[3/8,\infty )$ to turn each finite output into Yes or No, retaining the latest inner-stage value that lies in either interval. Convergence in the Hausdorff distance ensures that the inner limit stabilizes; the outer limit answers ${\Xi }_{\mathrm{col}}$ correctly. This would give a height-two tower for a problem whose Solvability complexity index is three, a contradiction. Therefore

Let $L_n=\mathrm{span}\{e_1,\dots ,e_n\}$ and let $P_n$ be its orthogonal projection. For $z\in \mathbb{C}$, defineBecause $A$ is unitary,The displayed finite Hermitian matrix uses only finitely many matrix entries of $A$, and its least eigenvalue can be approximated by an arithmetic algorithm in the SCI hierarchy.

As $L_n$ increases densely,A unitary operator is normal, so the spectral theorem for normal operators on a separable Hilbert space identifies the limit asThe functions ${\gamma }_n$ are continuous and decrease to a continuous function on the compact unit circle. The Dini theorem therefore gives uniform convergence there.

Take successively finer rational meshes $G_n$ around $\mathbb{T}$. From the finitely computed values of ${\gamma }_n$, retain the mesh minima in the comparison neighborhoods whose radii are ${\gamma }_n(z)$; equivalently, use the standard local-minimum construction for a decreasing approximation to a distance function. Call the resulting finite set ${\Gamma }_n(A)$. Uniform convergence and the shrinking mesh implyin Hausdorff distance. Every operation at stage $n$ is finite and arithmetic, so $({\Gamma }_n)$ is the required one-limit sequence.

There is no finite-stage certificate that the whole output has the correct Hausdorff error: the convergence of ${\gamma }_n$ has no uniform computable rate over all unitary operators, and unseen matrix entries can still reveal a missing spectral component. A small computed residual can certify that an individual output point lies near the spectrum, but it cannot verify that ${\Gamma }_n(A)$ covers all of $\mathrm{Sp}(A)$. Thus the full finite-stage output is not verifiable without additional information.

Let $(F_n)$ be a Cauchy sequence for the Hausdorff distance, and putThe bounded set hypothesis makes ${\delta }_n$ finite, and the Cauchy sequence property gives ${\delta }_n\to 0$. Each $A_n$ is nonempty and a closed set, with $A_{n+1}\subseteq A_n$.

We need estimates that survive taking the closure. For every nonempty $F$, the distance to a set is Lipschitz continuous with constant one: the triangle inequality gives $\mathrm{dist}(x,F)\le d(x,y)+\mathrm{dist}(y,F)$, and interchanging $x,y$ provesFor every $m\ge n$, points of $F_m$ have distance at most ${\delta }_n$ from $F_n$. The same holds throughout their union and its closure, by this continuity. Since $F_n\subseteq A_n$,More generally, if $m\ge n$, every point in ${\bigcup }_{k\ge n}{F}_k$ is within ${\delta }_n$ of $F_m\subseteq A_m$. Passing to its closure again, and using $A_m\subseteq A_n$, givesChoose strictly increasing indices $n_j$ with ${\delta }_{n_j}\le 2^{-j}$. Then $(A_{n_j})$ satisfies part (ii), so it converges in Hausdorff distance to the nonempty closed set $G={\bigcap }_j{A}_{n_j}={\bigcap }_n{A}_n$, with $\rho (A_{n_j},G)\le 2^{1-j}$.

For $n\ge n_j$, the triangle inequality gives the explicit full-sequence boundIt tends to zero as $j\to \infty$. ThereforeThis proves Completeness of the Hausdorff hyperspace using the proposed tail closures, rather than assuming their diameters shrink.

The intersection $G$ is a closed set because arbitrary intersections of closed sets are closed. Its nonemptiness needs a construction: bounded closed sets need not be compact sets in this setting.

Fix $n$, $x_n\in F_n$, and $\eta >0$. Recursively choose $x_{k+1}\in F_{k+1}$, for $k\ge n$, using the approximation property of an infimum so thatThis is possible because $x_k\in F_k$ and $\mathrm{dist}(x_k,F_{k+1})\le \rho (F_k,F_{k+1})\le 2^{-k}$. The two bounds form convergent geometric series, so the triangle inequality shows $(x_k{)}_{k\ge n}$ is a Cauchy sequence. By completeness it converges to some $x\in X$.

For each fixed $j$, all sufficiently late $x_k$ lie in $F_j$, by nesting. Closedness of $F_j$ gives $x\in F_j$, and hence $x\in G$. In particular, starting with any $x_1\in F_1$ proves $G\ne \varnothing$. Moreover,For each starting point $x_n$, let $\eta \downarrow 0$ in this bound on its distance to a set $G$. This does not assert that a nearest point exists. It proves $\mathrm{dist}(x_n,G)\le 2^{1-n}$. Since $G\subseteq F_n$, the other directed Hausdorff distance is zero, andThis is the Summably nested Hausdorff intersection theorem; the summable movement replaces any need for compactness.

Write $h(A,B)={\sup }_{a\in A}\mathrm{dist}(a,B)$, so that $\rho (A,B)=\max \{h(A,B),h(B,A)\}$ is the Hausdorff distance. Since $X$ is a bounded set, there is a finite $M$ with $d(x,y)\le M$. Nonemptiness of $A,B$ therefore gives $0\le h(A,B)\le M$, so $\rho$ is finite. Its symmetry and nonnegativity are immediate, as is $\rho (A,A)=0$.

If $\rho (A,B)=0$, then every $a\in A$ has zero distance to a set $B$. Since $B$ is a closed set, part (a)(iii) gives $A\subseteq B$. Interchanging the sets gives $B\subseteq A$. Thus $\rho (A,B)=0$ implies $A=B$. Closedness is essential here: without it a set and its closure have Hausdorff distance zero.

For the triangle inequality, fix $a\in A$ and $ϵ>0$. The approximation property of an infimum supplies $b\in B$ with $d(a,b)<\mathrm{dist}(a,B)+ϵ$, and then $c\in C$ with $d(b,c)<\mathrm{dist}(b,C)+ϵ$. Consequently,Let $ϵ\downarrow 0$ and take the supremum over $a$ to obtain $h(A,C)\le h(A,B)+h(B,C)$. Applying this inequality in the reverse direction as well yieldsAll metric axioms follow. Boundedness was used to ensure finiteness, and closedness to distinguish different sets; neither was needed for the triangle inequality.

Let $X$ be a complete metric space and let $F_n$ be nonempty closed bounded subsets with $F_{n+1}\subseteq F_n$ and Hausdorff distance $d_H(F_n,F_{n+1})\le a_n$, where $a_n\ge 0$ and ${\sum }_n{a}_n<\infty$. Then $G={\bigcap }_n{F}_n$ is nonempty and closed, and $d_H(F_n,G)\le {\sum }_{k=n}^{\infty }{a}_k\to 0$.

To prove this, start with any $x_n\in F_n$ and choose $x_{k+1}\in F_{k+1}$ with $d(x_k,x_{k+1})<a_k+\eta 2^{n-k-1}$. The triangle inequality makes the resulting sequence a Cauchy sequence. Its limit exists by completeness and belongs to every $F_j$ by nesting and closedness. Its distance from the starting point is at most ${\sum }_{k=n}^{\infty }{a}_k+\eta$. Let $\eta \downarrow 0$ and take the supremum over starting points. The reverse directed distance is zero since $G\subseteq F_n$. Unlike the usual shrinking-diameter form of Cantor's intersection theorem, the sets need not have diameters tending to zero.