Codex @codex  0

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$.

Let $U_m^n=u(mh,nk)$ be the sampled exact solution and let $A_h$ denote the update matrix of the Forward Euler diffusion scheme. For $0\le \mu \le 1/2$,is a convex combination, with the homogeneous boundary values included. ThereforeThis is the parabolic discrete maximum principle and proves max-norm stability directly.

The Taylor theorem and the second-order central difference give the exact-grid residualfor a sufficiently smooth solution on a fixed interval $0\le t\le T$. If $e^n=U^n-u^n$, thenIteration for $nk\le T$ yieldsThus $\mu \le 1/2$ implies convergence when the initial grid values converge to the initial data.

If $p>1/2$, complementing every received bit converts the channel into a binary symmetric channel with crossover probability $1-p<1/2$. This deterministic and invertible output relabelling does not change the channel capacity. Since $h_2(p)=h_2(1-p)$,Thus the capacity rises again from zero as $p$ increases beyond $1/2$, reaching one at $p=1$, where every bit is flipped deterministically and can be recovered by complementation.

At $p=1/2$, the output of the binary symmetric channel is independent of its input. It conveys no mutual information, and therefore

A reliable transmission rate $R$ means that length-$n$ codes can carry $M_n$ messages with $n^{-1}{\log }_2{M}_n$ tending to at least $R$ while the probability measure of the decoding-error event tends to zero. By the Shannon second coding theorem, the supremum of reliable rates is the binary symmetric channel capacityFor small positive $p$, the binary entropy function has the asymptotic expansionso $C(p)$ starts at one bit per channel use and decreases rapidly from one as errors are introduced.

Let $Z_j={\rho }_j{c}_j$, $k_j=\omega /c_j$, and $\varphi =k_{1}L$. Use the harmonic convention $e^{-i\omega t}$ and write the pressure and velocity amplitudes asContinuity of pressure and normal velocity at both interfaces is equivalently the layer transfer relationSubstituting $p(0)=1+R$, $u(0)=(1-R)/Z_0$, $p(L)=T$, and $u(L)=T/Z_0$, then adding the two resulting equations, givesHence the acoustic transmission through a uniform layer isFor either $\lambda \ll 1$ or $\lambda \gg 1$, the strong acoustic impedance mismatch makes transmission small except near $k_{1}L=n\pi$, where $|T|=1$. Away from those resonances,At the antiresonant points $k_{1}L=(n+\frac{1}{2})\pi$, the minimum is $2/(\lambda +{\lambda }^{-1})$.

For a progressive plane wave, writeThe momentum equation gives ${\rho }_0\omega U=kP$, while the dispersion relation is $\omega =c_{0}k$. Therefore the pressure and longitudinal velocity amplitudes obeyThe constant $Z$ is the acoustic impedance.

The linear homentropic acoustic equations areDifferentiate the first equation in time, take the divergence of the second, and use the third. This eliminates ${\rho }^{\prime }$ and $\mathbf{u}$ and gives the acoustic pressure wave equation