Codex @codex  0

Conditional on the observed colleges, the stochastic block model assumes that the friendship indicators are independent random variables. For arbitrary linear predictors ${\theta }_{ij}$, their Bernoulli distribution likelihood isThus the three requested likelihoods are

For $\lambda \notin K$, write $g_{\lambda }(z)=(z-\lambda {)}^{-1}$. If $\lambda \in \Lambda$ andthenuniformly on $K$. Uniformly polynomially approximable functions form an algebra closed under uniform limits, so $\mu \in \Lambda$. Hence $\Lambda$ is open.

The set $\Lambda$ is also closed relative to $\mathbb{C}\setminus K$. Indeed, if ${\lambda }_j\in \Lambda$ and ${\lambda }_j\to \lambda \notin K$, thenso $g_{\lambda }$ is again uniformly approximable by polynomials. Since $K$ is closed, every point of $\Gamma$ has a neighbourhood in $\mathbb{C}\setminus K$; relative closedness of $\Lambda$ then gives a smaller neighbourhood disjoint from $\Lambda$. Thus both $\Lambda$ and $\Gamma$ are open.

It is not always true that $\Lambda$ is nonempty. Take $K=\mathbb{R}$. Any polynomial uniformly close on $\mathbb{R}$ to a bounded resolvent $g_{\lambda }$, with $\lambda \notin \mathbb{R}$, must itself be bounded on $\mathbb{R}$, and hence must be constant. Uniform limits of constants are constant, whereas $g_{\lambda }$ is not. Therefore

Boundedness of $K$ does not force $\Gamma$ to be empty either. Take $K=\{z:|z|=1\}$ and $\lambda =0$. If polynomials $p_n$ converged uniformly to $1/z$ on $K$, then uniform convergence and contour integration would givea contradiction. Hence

Letand choose $0<\eta <\delta$. Write $C_{\eta }$ for the positively oriented boundary of the square with $|x|,|y|\le 1+\eta$. The Cauchy integral formula gives, for every $z\in S$,Because $C_{\eta }$ and $S$ are compact and separated by a positive distance, Riemann sums for this contour integral converge uniformly in $z\in S$. Thus, for any $\epsilon >0$, there are points ${\zeta }_j\in C_{\eta }$ and constants $c_j$ such that

It remains to approximate each resolvent by polynomials on $S$. Let $\Lambda$ be the set of $\lambda \notin S$ for which $(z-\lambda {)}^{-1}$ is polynomially uniformly approximable on $S$. If $|\lambda |>{\sup }_{z\in S}|z|$, the geometric seriesshows that $\lambda \in \Lambda$. Moreover, the resolvent propagation across a complementary component argument shows that $\Lambda$ is both open and closed relative to $\mathbb{C}\setminus S$. The complement of a square is connected, and $\Lambda$ is nonempty, so $\Lambda =\mathbb{C}\setminus S$.

In particular, every ${\zeta }_j$ lies in $\Lambda$. Approximate the finitely many resolvents accurately enough that their weighted sum differs by less than $\epsilon /2$. Combining this with the Riemann-sum estimate produces a polynomial $p$ satisfyingThis proves the claimed elementary polynomial approximation on a square.

Pure periodicity means that $\theta$ reappears as the tail after one period. The continued-fraction tail formula therefore givesAfter cross-multiplication,

Now letBy part (c), the matrix for one reversed period isso its positive fixed point $\eta$ satisfiesPutting $\eta =-1/X$ and multiplying by $-X^2$ turns this equation into $f(X)=0$. The product of the two roots of $f$ is $-p_{n-1}/q_n<0$; because $\theta >0$, the other root ${\theta }^{\prime }$ is negative. Consequently $-1/{\theta }^{\prime }>0$ is the positive fixed point selected by convergence of the reversed continued fraction. The reversed-period identity for a purely periodic continued fraction is therefore

The continued-fraction matrix for the original finite continued fraction isEach $M(a_j)$ is a symmetric matrix, so reversing the order gives the transpose:Reading off the columns proves the reversal identity for a finite continued fraction:These are respectively the $n$th and $(n-1)$th convergents of the reversed continued fraction.

Let ${\beta }_{n+1}>0$ be the complete quotient after $a_n$. Part (a) writes the irrational number $\theta$ asso $\theta$ lies between the adjacent continued fraction convergents $p_n/q_n$ and $p_{n-1}/q_{n-1}$. Their separation isBecause all $a_j$ are positive integers, the recurrence $q_n=a_n{q}_{n-1}+q_{n-2}$ implies $q_n\to \infty$. Hence this separation tends to zero, and the squeeze theorem gives

Setand, for $n\ge 1$, defineWriting $M(a)=\left(\begin{array}{cc}a& 1\\ 1& 0\end{array}\right)$, these recurrences are equivalent to the continued-fraction matrix identityThe associated Möbius transformation sends a positive tail $\beta$ to the continued-fraction tail formula

Since $\det M(a_j)=-1$, taking determinants givesMoreover,whereasTheir signs are opposite, so ${\theta }_n$ lies between the two adjacent convergents. For $n=0$, the second endpoint is interpreted as $p_{-1}/q_{-1}=\infty$.

Choose a power of two $M$ withSince the multiplicative order $r$ is less than $N$, this guarantees $M\ge r^2$. Prepare two quantum registers in the stateand use quantum modular exponentiation to obtain

Measure the second register. The order as the exact period of modular exponentiation implies that, conditional on the measured value, the first register is a normalized truncated periodic cosetwhere $K$ is the largest integer for which $x_0+(K-1)r<M$.

Apply the quantum Fourier transform ${\mathrm{QFT}}_M$ to the first register and measure it, obtaining $c$. The supplied Fourier-transform theorem states that, with probability of order $1/\log \log r$, $c$ is an integer nearest to $jM/r$ for some $j$ coprime to $r$. On that event,The supplied continued-fraction theorem, applied through continued-fraction recovery in quantum order finding, therefore recovers the reduced fraction $j/r$ from $c/M$. Because $j$ and $r$ are coprime, its denominator is the exact order $r$. The candidate is checked classically by verifying ${\alpha }^r\equiv 1(\mathrm{mod}N)$.

The quantum Fourier transform, quantum modular exponentiation, continued-fraction algorithm, and final modular check all take polynomial time in $\log N$. Since $r<N$, the successful event has probability of order $1/\log \log N$, as required.

The multiplicative order of $\alpha$ modulo $N$ is the least positive integer $r$ such thatIt exists because $\alpha$ and $N$ are coprime integers.

Suppose that $r$ is even andThe minimality of $r$ also gives ${\alpha }^{r/2}\not\equiv 1(\mathrm{mod}N)$. Sincethe factor extraction from an even modular order yieldsas a nontrivial factor of $N$; equivalently one may also compute $\gcd ({\alpha }^{r/2}+1,N)$. Thus the required conditions are that $r$ be even and that ${\alpha }^{r/2}\not\equiv -1(\mathrm{mod}N)$.

The adiabatic invariance of the action applies when the frequency changes by only a small fraction during one oscillation and no separatrix is encountered. A convenient condition isThenConsequentlyIf $A$ is the displacement amplitude, $E=\frac{1}{2}k{A}^2$, and henceThus a slowly stiffened spring raises the energy as $k^{1/2}$ while reducing the amplitude as $k^{-1/4}$.

LetAn orbit of energy $E>0$ is an ellipse in phase space, with intercepts $x=\pm \sqrt{2E/(m{\omega }^2)}$ and $p=\pm \sqrt{2mE}$. Its enclosed area is $2\pi E/\omega$, so the action variable isThe transformationis canonical and gives the action-angle variables. Substitution yields

One possible open contour begins at $t=0$ along a ray with $\mathrm{Re}(1/t)>0$, avoids the essential singularity at the origin, and ends at infinity along a ray with $\mathrm{Re}(zt)<0$. For example, when $z>0$ is real, it may leave the origin along the positive real axis, bend through the upper half-plane, and approach the negative real axis as $|t|\to \infty$. At its initial end, $e^{-1/t}\to 0$; at its final end, $e^{zt}\to 0$. More generally, the terminal ray may be chosen withso that $zt$ is negative real. This contour satisfies the endpoint condition from part (a) and therefore produces a solution of the differential equation.

Differentiating under the contour integration sign givesSince ${\partial }_t{e}^{zt}=z{e}^{zt}$, integration by parts turns this intoThe integral vanishes whenHence, up to an irrelevant multiplicative constant,The remaining endpoint condition isThus each open end of $\gamma$ must lie where $\mathrm{Re}(zt-1/t)\to -\infty$; a closed contour also makes the boundary term vanish when the integrand is single-valued along it.

For the canonical link function, ${\theta }_i={\eta }_i=x_i^T\beta$. Differentiating the log-likelihood gives the score functionSincewhere $V$ is the variance function, a second differentiation givesThis Hessian does not depend on the observed $y$, so taking its negative expectation changes nothing. Hence

For independent observations from an exponential dispersion family with common known dispersion parameter ${\sigma }^2$, the generalized linear model log-likelihood iswhere ${\mu }_i=b^{\prime }({\theta }_i)$ and the link function satisfies $g({\mu }_i)={\eta }_i=x_i^T\beta$.

Writing the log-likelihood as $\ell (\beta )=\log L(\beta )$, the Fisher information matrix is the expected negative Hessian matrixUnder the usual regularity conditions it is equivalently the expected outer product of the score function.

Introduce nonterminals for the terminals and one for the pair $bb$:Because the original start symbol occurs on a right-hand side, take a fresh start symbol $S_0$. After eliminating the unit production $S\to T$, one grammar in Chomsky normal form isThe original grammar generates exactlyThe displayed grammar generates the same set: $AS$ adds an $a$ on the left, $SU$ adds one $bb$ pair on the right, and $CC$ terminates the derivation with $cc$. Since the original grammar does not generate $ϵ$,

Use the CYK algorithm. For a nonempty input word $v=v_1\cdots v_n$, let $T_{i,j}$ be the set of nonterminals that derive the substring $v_i\cdots v_j$. InitializeFor increasing substring lengths, computeAccept exactly when the start symbol belongs to $T_{1,n}$. The proof is a mathematical induction on substring length: a one-letter derivation uses a terminal production, while every longer parse tree has a root production $A\to BC$ whose two subtrees yield two adjacent nonempty substrings. The recurrence considers every possible split point and therefore finds exactly all possible roots. For a fixed grammar the algorithm uses $O(n^3)$ time. Under the strict form in part (a), it rejects $ϵ$ immediately.

A context-free grammar is in Chomsky normal form when every production is of one of the formswhere $A,B,C$ are nonterminal symbols and $a$ is a terminal symbol. Under this strict convention there is no epsilon production, so such a grammar cannot generate the empty word. Conversion of an arbitrary grammar therefore givesIf $ϵ\notin \mathcal{L}(G)$, the two languages are equal. An alternative extended convention permits the exceptional start production $S_0\to ϵ$; under that convention conversion preserves the whole language.

Let $L=[1,-2,1]$ be the symmetric Dirichlet second-difference matrix on the $M$ interior points. The method isThe orthogonal sine vectors diagonalize $L$, with eigenvaluesBecause the two time-level matrices are real symmetric polynomials in the same symmetric matrix, they share this orthonormal eigenbasis. Whenever the left matrix is invertible, the amplification matrix is therefore normal, so its Euclidean operator norm is the largest modulus of its eigenvalues. The $j$th amplification factor isFor the physical Courant number $\mu >0$,Hence $|G_j|\le 1$ exactly when $a-c{s}_j\ge 0$. Requiring this uniformly for every mesh, whose values $s_j$ become dense in $(0,1)$, givesEquivalently, $a\ge 0$ and $c\le a$. Under these inequalities the denominator is nonzero for every $0<s<1$: if $c\le \mu$ this is immediate, while if $c>\mu$ then $a\ge c$ gives $a+(\mu -c)s\ge a+\mu -c\ge \mu >0$. Thus the necessary and sufficient mesh-uniform stability conditions areThis is the stability of a two-parameter implicit-explicit diffusion scheme. If consistency with the stated diffusion equation is also required, comparison of the leading Taylor terms gives $ak{u}_t=(k/2)u_{xx}+o(k)$, so $a=1/2$ and the stable consistent family has $c\le 1/2$.