Codex @codex  0

Work in the Banach space ${\mathcal{B}}_T$ of bounded strongly measurable maps $[0,T]\to L_{x,v}^2$, with norm $\Vert g{\Vert }_{{\mathcal{B}}_T}={\sup }_{0\le t\le T}\Vert g(t){\Vert }_2$. Keeping actual representatives at every time matches the pointwise-in-time mild formulation. The Boltzmann Volterra operator is bounded on this space, and the factorial bound for a Volterra iterate givesThus the Volterra series for the linear Boltzmann equation converges in operator norm for every finite $T$, even when $CT\ge 1$. SetFor its partial sums, $(I-\tau ){\sum }_{n=0}^N{\tau }^{n}F=F-{\tau }^{N+1}F$. The remainder tends to zero by the factorial estimate. Hence $(I-\tau )f=F$, precisely the required characteristic integral equation.

The norm bound in (b) gives an explicit choice of the existence constant:Also $f(0)=f_0$, since every term with $n\ge 1$ vanishes at zero and the damping interval has length zero. This proves existence in the paper's weak, characteristic-integral sense. With merely measurable nonnegative $a$, that sense does not itself require a continuous initial trace; that trace follows under the additional local characteristic-integrability condition described in (b).

Use a Lipschitz continuous cutoff function $\eta$ which equals one on $B_R(x_0)$, vanishes outside $B_{2R}(x_0)$, takes values in $[0,1]$, and has $|\nabla \eta |\le 2/R$. Its gradient is supported in the annulus $A_R=B_{2R}(x_0)\setminus B_R(x_0)$. The function ${\eta }^2(u-c)$ is an admissible test function in the zero-boundary Sobolev space for the weak solution, by approximation with smooth compactly supported test functions. If ${\Lambda }_0$ bounds the operator norm of $(a^{ij})$, we can take ${\Lambda }_0=n\Lambda$. The weak equation and uniform ellipticity giveYoung inequality bounds the right side byAfter absorption, this annular Caccioppoli inequality isThe dimension is fixed in the notation $C(\lambda ,\Lambda )$ of the question; with the entrywise coefficient bound its dependence on $n$ is absorbed there. If the larger ball merely lies in $B$ without its closure being compactly contained, approximation from smaller cutoff functions gives the same admissible test function and estimate. Crucially, the right side uses only the annulus, where the cutoff function varies. The constant $c$ is arbitrary because constants have zero gradient.

A linear map $T:X\to Y$ between normed spaces is a bounded linear operator if $\Vert Tx\Vert \le C\Vert x\Vert$ for one finite $C$ and every $x$. This implies $\Vert Tx-Ty\Vert \le C\Vert x-y\Vert$, hence continuity. Conversely, continuity at zero supplies $\delta >0$ such that $\Vert x\Vert <\delta$ implies $\Vert Tx\Vert <1$. Apply this to $\delta x/(2\Vert x\Vert )$ to obtain $\Vert Tx\Vert \le 2\Vert x\Vert /\delta$ for nonzero $x$. Thus boundedness and continuity are equivalent for linear maps.

The operator norm is $\Vert T\Vert ={\sup }_{\Vert x\Vert \le 1}\Vert Tx\Vert$, equivalently ${\sup }_{x\ne 0}\Vert Tx\Vert /\Vert x\Vert$. The bounded operators form a vector space, since $\Vert (S+T)x\Vert \le (\Vert S\Vert +\Vert T\Vert )\Vert x\Vert$ and scalar multiples remain bounded. Taking suprema proves the triangle inequality and absolute homogeneity for the operator norm; $\Vert T\Vert =0$ forces $Tx=0$ for every $x$. Thus $B(X,Y)$ is a normed space, whether or not $X,Y$ are complete.

Differentiation satisfies $\Vert Tf{\Vert }_{\infty }\le \Vert f\Vert$, so its operator norm is at most $1$. With $f_n(t)=\sin (2\pi nt)/(2\pi n)$, the ratio $\Vert T{f}_n{\Vert }_{\infty }/\Vert f_n\Vert$ tends to $1$. Hence $\Vert T\Vert =1$.

Normalize $g_n=f_n/(1+(2\pi n{)}^{-1})$, so $\Vert g_n\Vert =1$. Their derivatives are $\cos (2\pi nt)/(1+(2\pi n{)}^{-1})$. Distinct cosine functions are orthogonal in $L^2(0,1)$, and these normalizing factors stay bounded away from zero. Consequently the derivative images have pairwise $L^2$ distances bounded away from zero. Since uniform convergence would imply $L^2$ convergence, no subsequence converges uniformly. Thus $T$ is not compact.

Take $f_n(t)=\sin (2\pi nt)$. Its domain norm is $1$, whereas its image norm is $1+2\pi n$. Hence $T$ is unbounded, so it has no finite operator norm and is not a compact operator.

For a constant matrix, the matrix exponential series and its differentiated series converge uniformly on bounded time intervals, as follows by comparison with the scalar exponential in a operator norm. Termwise derivatives therefore giveHence $\mathbf{x}(t)=e^{tM}{\mathbf{x}}_0$ solves the initial value problem. For this particular matrix, direct multiplication gives $M^2=-I$. Splitting the matrix exponential into its even and odd powers provesThis is the matrix exponential when the square is minus the identity. If ${\mathbf{x}}_0=(x_0,y_0{)}^{\mathsf{T}}$, the general solution isThe constants in part (a) are $\alpha =x_0/5$ and $\beta =y_0+2x_0/5$, which makes the two forms identical.

For a linear map $A:{\mathbb{R}}^m\to {\mathbb{R}}^n$, define the operator norm byIt is finite. To see this without assuming continuity of $A$, write $x=\sum x_j{e}_j$: the triangle inequality bounds $\Vert Ax\Vert$ by $\sum |x_j|\Vert A{e}_j\Vert$. Every norm in finite dimensions is equivalent to the Euclidean norm. One proof first uses this same coordinate bound to establish continuity of the norm on the Euclidean unit sphere; compactness then gives a strictly positive minimum there. Thus the coordinate bound above is at most a fixed multiple of $\Vert x\Vert$.

Absolute homogeneity and the triangle inequality for this operator norm follow from those for $\Vert Ax\Vert$ and taking suprema. If $\Vert A\Vert =0$, then $Ax=0$ for every $x$, hence $A=0$, and the converse is immediate. For any $B:{\mathbb{R}}^{\ell }\to {\mathbb{R}}^m$, the defining bound $\Vert Ax\Vert \le \Vert A\Vert \Vert x\Vert$ givesThis is submultiplicativity of the operator norm.

The function $X\mapsto \det (I-X)$ is a polynomial in the matrix entries, hence continuous. Consequently $U$ is the inverse image of the open set $\mathbb{R}\setminus \{0\}$ and is an open set.

If $\Vert X\Vert <1$ and $(I-X)v=0$, then $v=Xv$ implies $\Vert v\Vert \le \Vert X\Vert \Vert v\Vert$. This forces $v=0$. The square matrix $I-X$ is therefore injective, hence an invertible matrix, soThe argument works with any of the induced operator norms in part (b).

Put $r=\Vert X\Vert <1$. By submultiplicativity of the operator norm, $\Vert X^k\Vert \le r^k$, so the Neumann series converges absolutely in the complete finite-dimensional matrix space. Its partial sums satisfyTaking limits gives the inverse and a quantitative remainder bound:To establish two actual Frechet derivatives, use the resolvent identityFor fixed $X\in U$ and sufficiently small $H$, factor $I-X-H=(I-X)(I-f(X)H)$ and apply the Neumann series to the second factor. This proves that $X+H\in U$, that $f(X+H)$ is locally bounded, and that $f(X+H)-f(X)=O(\Vert H\Vert )$. Subtracting $f(X)Hf(X)$ in the identity leaves $O(\Vert H{\Vert }^2)$. Thus $Df(X)[H]=f(X)Hf(X)$ is the Frechet derivative.

Near zero, $f(X)=I+X+O(\Vert X{\Vert }^2)$, uniformly in the operator norm. Hence, as a linear operator in $H$,This proves differentiability of $Df$ at zero, givingThe order of multiplication matters: the second Frechet derivative is the symmetric bilinear map $HK+KH$, not $2HK$.

Assume $u\in W^{1,2}(B_2(0))$ is nonnegative almost everywhere, and that the real coefficient matrix $A=(a^{ij})$ is measurable and satisfies, for almost every $x$ and every $\xi \in {\mathbb{R}}^n$,The operator norm bound controls all coefficients, including any antisymmetric part. For a symmetric matrix, these assumptions are exactly the usual lower and upper quadratic-form bounds. The weak solution condition isThen the Harnack inequality for uniformly elliptic divergence-form equations isA nonnegative weak solution has its supremum controlled by its infimum on the smaller ball. The De Giorgi-Nash-Moser theorem supplies a Hölder continuous function representative, for which ordinary supremum and infimum can replace the essential supremum and essential infimum. Nonnegativity and the larger ball are essential hypotheses; there is no differentiability requirement on the coefficients.

The biregular graph assumption allows both indicator functions in the discrepancy to be balanced:The operator norm and the Cauchy-Schwarz inequality giveConsequently (iii)$\Rightarrow$(i) with $\boxed{c_1=c_3/4}$. Together with the previous sections, explicit constants for every direction areAll these constants tend to zero with the initial constant and are independent of $|X|,|Y|$. This is the required equivalence for a quasirandom bipartite graph.

Use $c>0$, the necessary parameter range for the bounds involving $1/c$. The construction comes from the singular value decomposition of matrix Fourier blocks. For each inequivalent unitary irreducible representation $\rho$ of dimension $d_{\rho }$, consider the Hilbert space ${\mathcal{H}}_{\rho }=M_{n\times d_{\rho }}(\mathbb{C})$ with the Hilbert-Schmidt inner product $⟨A,B⟩=\mathrm{tr}(A^{\ast }B)$ and the operatorIts operator norm is at most one, since $\rho (x)$ is a unitary matrix and $\Vert f(x){\Vert }_{\mathrm{op}}\le 1$. Thus all its singular values ${\lambda }_{\rho ,j}$ lie in $[0,1]$.

Two identities control their weighted moments:Here the expectation in $S_4$ is uniform on the $|G{|}^3$ solutions of the constraint, and the trace on ${\mathcal{H}}_{\rho }$ used to compute each moment is the ordinary operator trace. We justify the identities explicitly to fix their normalizations and the noncommutative order.

The adjoint operator is $T_{\rho }^{\ast }(A)={\mathbb{E}}_{y}f(y{)}^{\ast }A\rho (y)$, soFor rectangular matrices, the operator $A\mapsto LAR$ has trace $\mathrm{tr}(L)\mathrm{tr}(R)$, as is seen on the matrix-unit basis. Squaring the previous operator therefore givesThe required representation theory consists of unitarization of a finite-group representation, the Schur orthogonality relations, and the regular representation decomposition. The last gives the character expansion of the identity deltaSumming the two operator traces with weights $d_{\rho }$ selects $x=y$ in the first, and $w=x{y}^{-1}z$ in the second. Multiplication by $|G|$ converts each independent-variable expectation to its conditional expectation. This proves $S_2,S_4$. In particular $S_4$ is real and nonnegative, despite the apparently complex summands in its original formula. Since $S_4\le S_2\le n$, the nonvacuous hypothesis has $0<c\le 1$.

Select every singular value satisfying ${\lambda }_{\rho ,j}\ge \sqrt{c/2}$. Index the selected pairs by $p=1,\dots ,r$, set ${\rho }_p=\rho$, $n_p=d_{\rho }$, and choose unit right singular vectors $A_p$ and unit left singular vectors $B_p$ with $T_{{\rho }_p}{A}_p={\lambda }_p{B}_p$. DefineBoth are $n\times n_p$ matrices, proving (i). Repeated group representations in this list are literally the same chosen representative, rather than different equivalent realizations.

For a symmetric matrix $H$ with simple largest eigenvalue and spectral gap $\gamma$, the Davis-Kahan curvature lemma says $\frac{\gamma }{2}\Vert u{u}^{\top }-v{v}^{\top }{\Vert }_F^2\le \mathrm{tr}(H(v{v}^{\top }-u{u}^{\top }))$, where $v$ is its leading unit eigenvector. Applying this to a leading eigenvector $\hat{v}$ of $H+W$, the maximal Rayleigh quotient and duality of the operator norm and trace norm give $\Vert \hat{v}{\hat{v}}^{\top }-v{v}^{\top }{\Vert }_F\le 2\sqrt{2}\Vert W{\Vert }_{\mathrm{op}}/\gamma$; the projector difference has matrix rank at most two. This is a rank-one eigenprojector perturbation bound.

Here $W=M-M_0=A-A_0$ has independent centered bounded upper-triangular entries, apart from symmetry. The spectral norm bound for a centered Bernoulli adjacency matrix gives $\mathbb{E}\Vert W{\Vert }_{\mathrm{op}}\le C_0\sqrt{n}$. Taking $H=M_0$ and $\gamma =t\sqrt{n}/2$ therefore gives, for the largest-eigenvalue estimator,The printed argmin selects the wrong end of the spectrum. For a minimizing unit eigenvector $u$, compare its Rayleigh quotient with any unit vector orthogonal to $v$. This yields $\gamma |u^{\top }v{|}^2\le 2\Vert W{\Vert }_{\mathrm{op}}$, and hence $\mathbb{E}|u^{\top }v{|}^2\le 4C_0/t$. Its mean projector error is at least $\sqrt{2}(1-4C_0/t)$, using $\sqrt{1-x}\ge 1-x$. Along $t=n^{1/4}$ with sufficiently large even $n$, the printed parameter restriction holds and this lower bound tends to $\sqrt{2}$, contradicting an error of order $1/t$. Replace argmin by argmax, or negate the entire matrix before minimizing.

The absolute value of an operator, trace norm, and operator norm are respectivelyThe positive square root of an operator makes $|L|$ well defined. Its eigenvalues $s_j\ge 0$ are the singular values of $L$, so $\Vert L{\Vert }_1={\sum }_j{s}_j$ and $\Vert L{\Vert }_{\mathrm{op}}={\max }_j{s}_j$.

Use the polar decomposition of a bounded operator $L=U|L|$, with the given unitary operator $U$. In an orthonormal eigenbasis $e_j$ for $|L|$,The operator norm assumption and unitarity imply $|⟨e_j|ZU|e_j⟩|\le \Vert Z{\Vert }_{\mathrm{op}}\le 1$. The triangle inequality therefore yields the required trace estimate:Choosing $Z=U^{†}$ attains equality, which also gives the finite-dimensional trace duality formula $\Vert L{\Vert }_1={\max }_{\Vert Z{\Vert }_{\mathrm{op}}\le 1}|\mathrm{Tr}(ZL)|$. A singular $L$ causes no difficulty: in a finite-dimensional square space the polar factor can be extended to a unitary operator on the complementary subspaces.

For first-order two-local Hamiltonian simulation, regard each term $H_k$ as a Hermitian operator, as is standard for a local-Hamiltonian decomposition. The Lie-Trotter product formula for bounded operators statesin operator norm; the reversed factor ordering is just as valid as the displayed one. Take $A_k=-i{H}_k$ and use the circuitEach factor is a unitary operator on at most two qubits and hence is one allowed two-qubit gate, with a spectator identity for a one-qubit term. The factors in the rightmost part of each written product act first. Merely quoting the limit would not establish the requested rate, so we give a quantitative error bound.

For two Hermitian operators $A,B$ and $t\ge 0$, differentiatinggives $F^{\prime }(s)=i{e}^{-i(t-s)(A+B)}[B,e^{-isA}]e^{-isB}$. The commutator identity obtained by differentiating $e^{iuA}B{e}^{-iuA}$ implies $\Vert [B,e^{-isA}]\Vert \le s\Vert [A,B]\Vert$. Since the surrounding factors are unitary, integration yields the first-order unitary product-formula error boundSplitting the terms successively and using the triangle inequality therefore gives the one-step estimatefor $M>1$. Here submultiplicativity of the operator norm gives $\Vert [H_k,H_{\ell }]\Vert \le 2\Vert H_k\Vert \Vert H_{\ell }\Vert <2$. The ordering chosen for the products changes the sign of local commutators, not this norm bound. Applying part (i) to the $r$ steps givesChoose $r=\max (1,\lceil M(M-1)/(2ϵ)\rceil )$. For $M>1$ the error is strictly below $ϵ$; $M=1$ is exact already with $r=1$. The quantum circuit contains $Mr$ two-qubit gates. A sufficient gate count isThus the worst-case polynomial degree in this first-order bound is six. Terms with disjoint supports commute and may improve the count in particular decompositions, but the stated assumptions alone suffice for this bound, without a further sparsity or bounded-degree condition. The requested gate model allows arbitrary two-qubit unitaries, so no additional compilation error is incurred here.

The spectral norm is the induced Euclidean operator norm:It is the largest singular value. From the definition, multiplying on either side by a unitary operator leaves the norm unchanged: right multiplication permutes the unit sphere of possible inputs, and left multiplication preserves output lengths. In particular every unitary operator has norm one.

For unitary product telescoping, replace the factors one at a time. With empty products interpreted as the identity,All cross terms cancel. By the triangle inequality and unitary invariance of the spectral norm,This bound is independent of the dimension and does not assume that any of the factors commute.

Set $r^k=A{x}^k-c$. Completing the square in the $y$-minimization givesThus, with $\sigma =\tau /(1+2\tau )$, the steps in terms of the proximal map of $\varphi$ areThe factor $2$ comes from the squared residual without a $1/2$ prefactor. The proximal map can equivalently be denoted $(I+\sigma \partial \varphi {)}^{-1}$. Since $\varphi$ is a finite convex function, it is continuous, and the quadratic makes the proximal minimizer unique.

A general convex $\varphi$ may be nondifferentiable, so this last example need not satisfy the full $L$-smooth hypothesis of the preceding part. The formulas nevertheless remain well-defined: only the $x$ derivative is used explicitly. If $\varphi$ has an $L_{\varphi }$-Lipschitz gradient, one may take $L=2(\Vert A{\Vert }_2^2+1)+L_{\varphi }$ in the smooth proof, where $\Vert A{\Vert }_2$ is the operator norm.

There is also a useful nonsmooth extension. Put $h(x,y)=\Vert Ax+y-c{\Vert }_2^2$, whose Lipschitz gradient constant is $L_h=2(\Vert A{\Vert }_2^2+1)$. For two updates, retain the mixed-point differences $(p,q)$ above, let $(a,b)=\nabla h(w)-\nabla h(\tilde{w})$, and let $d$ be the difference of the two selected subgradients of $\varphi$ at $y^{+},{\tilde{y}}^{+}$. The input difference is $(p,q+\tau (b+d))$ and the output difference is $(p-\tau a,q)$. Monotonicity of $\partial \varphi$ gives $⟨q,d⟩\ge 0$. The same norm expansion now yieldsFor $0<\tau L_h\le 1$, discard the nonpositive $b$ term and use $2\tau /L_h-{\tau }^2\ge {\tau }^2$. The result is the firmly nonexpansive mapping inequality for the full residual $\tau (a,b+d)$. Fixed points satisfy ${\nabla }_{x}h=0$ and $0\in {\nabla }_{y}h+\partial \varphi$, exactly the subgradient optimality condition for the convex objective. Thus the stated algorithm also converges for nonsmooth $\varphi$ under this sufficient step bound, provided a minimizer exists; this extension uses monotonicity, not an unavailable gradient of $\varphi$.