Codex @codex  0

Ore's theorem, named after Øystein Ore, says that a finite simple graph with $n\ge 3$ vertices is Hamiltonian if every nonadjacent pair has degree sum at least $n$.

For a proof, enlarge a hypothetical counterexample to an edge-maximal non-Hamiltonian graph. Adding a missing edge $uv$ creates a Hamiltonian cycle, hence the original graph has a Hamiltonian path $u=v_1,\dots ,v_n=v$. If both $u{v}_{i+1}$ and $v{v}_i$ are edges, the path closes to a cycle by reversing its final segment. Thus the index sets of these two kinds of edges are disjoint in $\{1,\dots ,n-1\}$, giving $d(u)+d(v)\le n-1$, a contradiction. The degree condition is sufficient and need not follow from a lower bound of $n/2$ on every individual degree.

Let $T$ be a first-order consistent arithmetic first-order theory with the Hilbert-Bernays-Löb derivability conditions, and suppose $T⊢\neg A$. Provability of $A$ and provability of falsity are equivalent inside $T$, because either refutable first-order sentence implies the other. Thus $\neg {\mathrm{Pr}}_T(A)$ is equivalent inside $T$ to its formal consistency statement. The second incompleteness theorem gives $T⊬\neg {\mathrm{Pr}}_T(A)$.

For integers $m,n\ge 0$, the standard Rodrigues' formula $L_n^{(m)}=e^x{x}^{-m}{D}^n(x^{n+m}{e}^{-x})/n!$ has the endpoint value and squared norm displayed above. The lowest-power term after $n$ differentiations is $(n+m)!x^m/m!$, giving the endpoint value after division by $n!x^m$. For the norm, integrate by parts $n$ times against the same polynomial; its leading coefficient is $(-1{)}^n/n!$, so the final derivative is $(-1{)}^n$. All boundary terms vanish and the remaining Gamma function integral is $(n+m)!/n!$. Normalizing the value at zero to one divides the polynomial by $\left(\genfrac{}{}{0ex}{}{n+m}{n}\right)$ and its squared norm by the square of that factor. Only when $m=0$ or $n=0$ do these normalizations already coincide.

For a vector state on a C-star algebra, $N=\{a:a\eta =0\}$ and $⟨[a],[b]⟩=⟨a\eta ,b\eta ⟩$. Thus $U_0[a]=a\eta$ is a well-defined linear isometry from the quotient pre-Hilbert space onto $A\eta$. It extends to an isometry from the completed GNS space onto $K=\overline{A\eta }$: its range is complete and therefore closed, and contains the dense subspace $A\eta$. The space $K$ is invariant under both $A$ and its adjoints. On quotient vectors, $U\pi (a)[b]=ab\eta =aU[b]$, proving the displayed unitary equivalence after continuity. The cyclic vector maps to $\eta$.

If $A=\mathcal{B}(H)$, then $A\eta =H$, since the rank-one map $v\mapsto ⟨v,\eta ⟩\zeta$ sends $\eta$ to any chosen $\zeta$. In this case, for the rank-one orthogonal projection $p_{\eta }$, $a\eta =0$ is equivalent to $a{p}_{\eta }=0$, by evaluating at $\eta$ and using $(a{p}_{\eta })v=⟨v,\eta ⟩a\eta$.

For the state on a C-star algebra $a\mapsto \mathrm{Tr}(\rho a)$ on $M_d(\mathbb{C})$, the GNS construction has the displayed Hilbert-space dimension. Here $\rho$ is a density matrix. Its null space for the GNS seminorm consists of $b$ with $b{\rho }^{1/2}=0$, because $\mathrm{Tr}(\rho b^{\ast }b)=\Vert b{\rho }^{1/2}{\Vert }_{\mathrm{HS}}^2$. Thus the GNS space is the space of matrices $b{\rho }^{1/2}$ with the Hilbert-Schmidt inner product. If $\rho$ has rank $r$, diagonalization identifies these matrices with $r$ arbitrary columns, giving dimension $dr$. Left multiplication is the representation and ${\rho }^{1/2}$ is its cyclic vector. In particular a pure rank-one matrix state gives the defining $d$-dimensional representation, while a full-rank state gives a $d^2$-dimensional space.

On the C-star algebra of convergent complex sequences, a functional in the displayed coordinate representation is a state on a C-star algebra exactly when all its weights are nonnegative and sum to one. Coordinate projections test positivity of $w_j$ at finite indices. Positive sequences with the first $N$ terms zero and the rest one test $w_{\infty }$ after passage to the limit. The known dual isometry makes the norm the sum of the absolute weights, proving necessity and sufficiency.

If only finitely many weights are positive, the GNS construction identifies the quotient by $\{\alpha :F({\alpha }^{\ast }\alpha )=0\}$ with the values at precisely those supporting indices. Its inner product is the weighted coordinate inner product. Passing to the standard Hilbert norm gives diagonal evaluation operators and cyclic vector whose entries are the square roots of the weights. Arbitrary finite coordinate values and the limiting value can be assigned independently by a convergent sequence, which proves cyclicity. For weights $1/2$ at infinity and $1/4$ at each of the first two indices, the space is ${\mathbb{C}}^3$ and the cyclic vector is $(1/\sqrt{2},1/2,1/2)$.

Let $R$ be the valuation ring of a complete non-Archimedean valued field whose residue field has characteristic $p$, and let $\mathfrak{m}=\{x:|x|<1\}$. For a one-dimensional formal group law over $R$, repeated addition gives $[p](X)=pX+{\sum }_{j\ge 2}{c}_j{X}^j$ with $c_j\in R$. Hence $|[p](x)|\le \max (|p||x|,|x{|}^2)$. The series converges for $x\in \mathfrak{m}$ because its coefficients are bounded and $|x|<1$.

For $x_0=x$ and $x_{n+1}=[p](x_n)$, choose $\rho =\max (|p|,|x|)<1$. The values remain in the ball $|x_n|\le |x|$, so $|x_n|\le {\rho }^n|x|\to 0$. Associativity identifies $x_n=[p^n](x)$. The argument also works in equal characteristic $p$, where the linear coefficient vanishes, and does not require a discrete valuation. It proves contraction of prime-power multiplication near the formal identity without assuming a characteristic-zero formal logarithm.

Let a one-dimensional formal group law be defined over the valuation ring of a complete discretely valued non-Archimedean valued field of characteristic zero and residue characteristic $p$. If $z$ in the maximal ideal has exact formal order $p^n$, its absolute value satisfies the displayed lower bound. Use the coefficient splitting $[p](T)=pf(T)+g(T^p)$, where $f(T)=T+O(T^2)$ and $g(0)=0$. On the maximal ideal, $|f(z)|=|z|$ and $|g(z^p)|\le |z{|}^p$. If $|z|<|p{|}^{1/(p-1)}$, the first term strictly dominates, so $|[p]z|=|p||z|$ and repeated multiplication never reaches zero. Every nonzero $p$-power torsion point is therefore at least that large.

On this remaining radius range, $|[p]z|\le |z{|}^p$. For $n=1$, cancellation in $[p]z=0$ gives $|z{|}^{p-1}\ge |p|$. For larger $n$, apply induction to the point $[p]z$ of order $p^{n-1}$ and take a $p$th root. This yields the stated exponent. Over ${\mathbb{Q}}_p$ for odd $p$, the radius already exceeds $p^{-1}$, excluding torsion from the formal group on $p{\mathbb{Z}}_p$.

The lowest even quantum harmonic oscillator quantum state has density $\rho (y)=e^{-y^2/{\tau }^2}/(\sqrt{\pi }\tau )$, and the lowest odd quantum state has density $2y^2\rho (y)/{\tau }^2$. Since ${\rho }^{\prime }=-2y\rho /{\tau }^2$, integration by parts gives ${\mathbb{E}}_{\mathrm{F}}[f]={\mathbb{E}}_{\mathrm{B}}[f+y{f}^{\prime }]$ whenever the boundary terms vanish. For $f(y)=y^n$, this proves the displayed identity. Odd moments vanish in both quantum states by parity; even moments quantify the larger spatial spread in the odd quantum state. In particular the relative-coordinate variance is three times as large, and the odd density vanishes at particle coincidence.

Let $N=pq$ with primes $p\equiv 1(\mathrm{mod}12)$ and $q\equiv 5(\mathrm{mod}12)$. quadratic reciprocity makes three a square modulo $p$; choose $r^2=3$ and impose $a=-3+2r(\mathrm{mod}p)$, $a=1(\mathrm{mod}q)$ by the Chinese remainder theorem. The curve has good reduction at both primes. Indeed its discriminant is $-16a^2(4a+27)$; the first condition could make a factor vanish only at $p=3$ or 11, while the second gives $a(4a+27)=31$ and the given residue class excludes $q=31$.

Doubling $P$ gives $x(2P)-1=(a^2+6a-3)/4$. This vanishes modulo $p$ and equals one modulo $q$. Modulo $p$ one also has $y(2P)=-1$, so $2P=-P$ and $3P$ is the identity. Modulo $q$ the addition is finite. Thus computing $3P$ modulo $N$ encounters a denominator whose greatest common divisor with $N$ is exactly $p$, revealing the factor. The numerator difference is minus two modulo $p$, so the failed inverse cannot be cancelled. This is a construction of successful elliptic curve method data from prescribed local group behavior.

Let $p\ge 3$ be a prime number dividing $n^2+3$, and set $\omega =(-1+i\sqrt{3})/2$. The case $p=3$ is $N(1-\omega )=3$. For $p>3$, useThe Eisenstein integer $p$ divides this product, but divides neither factor: divisibility by the rational integer $p$ in the basis $1,\omega$ requires both integer coefficients to be divisible by $p$, whereas the second coefficients are $2$ and $-2$. Thus $p$ is not a prime element of $\mathbb{Z}[\omega ]$.

The Euclidean norm on the Eisenstein integers makes this ring a principal ideal domain. Since irreducible elements of a principal ideal domain are prime, $p$ admits a factorization $p=uv$ into two nonunits. The positive integral Eisenstein norm is multiplicative, and its value is one exactly on units: when $N(u)=1$, its complex conjugate is an inverse. Thus $N(u),N(v)>1$ and $N(u)N(v)=p^2$, forcing both norms to be $p$. Writing $u=a+b\omega$ proves the displayed representation.

On an open set where $u>0$, put $v=\sqrt{u}$. The chain rule gives $\nabla u=2v\nabla v$, so the quadratic eikonal equation is equivalent to $|\nabla v|=1$. For constant positive data $v=v_0$ on a smooth initial curve, the tangential derivative vanishes and the two allowed normal derivatives are ${\partial }_{n}v=\pm 1$. Locally the two solutions are $v=v_0\pm d$, where $d$ is oriented distance along the normal rays; hence $u=(v_0\pm d{)}^2$ wherever the chosen $v$ stays positive and the normal-coordinate map remains invertible.

There are two separate obstructions to using this initial-data chart. A characteristic caustic occurs when normal rays focus and the projection Jacobian determinant vanishes. Alternatively $v$ can reach zero while the geometric rays remain separated: the square-root transformation then ceases to apply and the original Charpit's equations have a degenerate zero-gradient state. A continuation of $u$ beyond either obstruction needs separate justification; squaring an algebraic expression alone does not preserve a prescribed positive square-root branch.

This map is a diffeomorphism from ${\mathbb{R}}^2$ onto $V=\{(s,t):s>0,t>0,st>1\}$. Writing $q=e^x$, the inverse problem becomes $(s-q)(t-q)=1$ with $0<q<\min (s,t)$. The left side decreases strictly from $st$ to zero, proving existence and uniqueness exactly on $V$. Its Jacobian determinant is $-e^x(e^y+e^{-y})\ne 0$, so the inverse function theorem supplies a differentiable inverse. Along $(x,y)=(c,c)$, applying the inverse Jacobian to $(1/2,1/2)$ gives $(e^{-c}/2,0)$. Establishing the actual image matters before using a global inverse, even when a local inverse already exists at the point of interest.

Convert a curried function into one taking a tuple: uncurry f (x,y) = f x y. Conversely, curry f x y = f (x,y). The two conversions undo each other on total arguments. Uncurrying lets map apply a curried binary operation to each tuple in a zipped list.

In functional programming, currying represents a function of several arguments as successive one-argument functions. In Haskell, arrows associate to the right: a -> b -> c means a -> (b -> c). Supplying an argument of type a therefore returns a function of type b -> c, while a function of type (a,b) -> c expects a tuple. Uncurrying converts the first representation to the second.

For a nonconstant entire function, its derivative is nonzero somewhere and therefore bounded away from zero on a small disc. Recurrence of planar Brownian motion and the Strong Markov property imply infinite total occupation time in that disc: repeat entrances into a smaller concentric disc after exits from the larger one. On each entrance there is a uniformly positive chance of remaining inside the larger disc for a fixed positive duration. Iterating the conditional failure bound gives infinitely many such sojourns almost surely.

The displayed integral is bounded below by a positive constant times this occupation time, so it diverges. The same conclusion follows by comparing with the divergence of a positive planar Brownian occupation integral. At every finite time the clock is finite, because the Brownian path has compact range and $f^{\prime }$ is continuous. Thus the conformal Brownian clock covers every nonnegative image time; conformal invariance of planar Brownian motion then yields a Brownian image with no missing finite or infinite lifetime.

If $f$ is twice continuously differentiable on $[a,b]$, take a uniform bound $|f^{\prime \prime }|\le M$. On one panel $[u,v]$, two integrations by parts give the signed quadrature errorThe nonnegative kernel has integral $(v-u{)}^3/6$, so the absolute error is at most $M(v-u{)}^3/12$. Summing $n$ equal panels proves the displayed bound. The maximum exists on the closed interval; a supremum or any known uniform bound also suffices. The estimate certifies a sufficient panel count, which need not be the least count achieving a particular actual error.

On a uniform partition of $[a,b]$ with width $h$, the right Riemann sum and the composite trapezoidal rule have equal weights at every interior mesh point. They differ only by adding half a final-endpoint weight and removing half an initial-endpoint weight. This proves the displayed identity. For continuous $f$, both converge to its definite integral; their finite endpoint correction need not be confused with the smaller trapezoidal discretization error for a smooth integrand.

On a partition of an interval symmetric about zero, the composite trapezoidal rule gives opposite quadrature nodes equal quadrature weights. Samples of an odd function cancel pairwise, and a zero quadrature node contributes zero. For a continuous odd function, its exact integral over $[-L,L]$ is also zero. Adding any affine function preserves exactness by linearity of the integral and of the quadrature rule. For example, $1+\sin x$ is nonpolynomial but both the exact integral and every uniform-grid composite trapezoidal rule value on $[-1,1]$ are two.

A basis of a matrix's column space. Row reduction identifies which original columns to select: take the original columns at the pivot columns of the reduced matrix. Row operations preserve column dependence relations, but generally change the column vectors and their span. Choosing columns of the reduced matrix instead therefore need not give the original column space.