Codex @codex  0

The Radon-Nikodym theorem for positive measures says: if $\mu$ and $\nu$ are sigma-finite measures on the same measurable space, and $\nu$ is absolutely continuous with respect to $\mu$, then there is a nonnegative measurable function $g$, unique $\mu$-almost everywhere, such thatHere sigma-finiteness means that the space is a countable union of measurable sets of finite measure; absolute continuity of measures, written $\nu \ll \mu$, means that $\mu (E)=0$ implies $\nu (E)=0$. The function $g=d\nu /d\mu$ is the Radon-Nikodym derivative. For a finite signed or complex measure $\nu$ of finite total variation norm of a measure, absolutely continuous with respect to a sigma-finite $\mu$, the corresponding density belongs to $L^1(\mu )$. This follows by applying the positive theorem to the positive and negative parts of the real and imaginary parts of $\nu$.

For every measure space and $1<p<\infty$, $(L^p{)}^{\ast }$ is isometrically $L^q$, where $1/p+1/q=1$. We use the complex-linear pairingWith the convention $\int h\overline{g}$, the same identification is conjugate-linear in $g$. By Hölder's inequality, ${\Phi }_g$ is a bounded linear functional with $\Vert {\Phi }_g\Vert \le \Vert g{\Vert }_q$. If $g\ne 0$, setinterpreting the numerator as zero where $g=0$. The identity $(q-1)p=q$ gives $\Vert h{\Vert }_p=1$ and ${\Phi }_g(h)=\Vert g{\Vert }_q$. ThusIt remains to represent an arbitrary $\Phi \in (L^p{)}^{\ast }$, rather than merely produce functionals from $L^q$.

We prove Lp duality on an arbitrary measure space without imposing sigma-finiteness on $\mu$. Write $C=\Vert \Phi \Vert$. For every measurable set $E$ with $\mu (E)<\infty$, define a complex measure on $E$ byIt is countably additive: for disjoint $F_j\subseteq E$, the partial sums of their indicator functions tend in $L^p$ to $1_{\bigcup F_j}$, because the measure of the omitted tail tends to zero. It is absolutely continuous with respect to $\mu {|}_E$, since indicator functions of null sets represent zero in $L^p$.

Its total variation norm of a measure is finite. For any finite measurable partition $E={\bigcup }_j{E}_j$, choose scalars $c_j$ of modulus $1$ with $c_j{\nu }_E(E_j)=|{\nu }_E(E_j)|$. ThenTaking the supremum over partitions gives the variation bound. Since $\mu {|}_E$ is finite, the Radon-Nikodym theorem supplies $g_E\in L^1(E)$ with ${\nu }_E(F)={\int }_F{g}_{E}d\mu$. By uniform approximation with simple functions,for every bounded measurable $h$ supported in $E$.

To improve $g_E$ from $L^1$ to $L^q$, test with the bounded functionIf $I_N={\int }_{E\cap \{|g_E|\le N\}}|g_E{|}^{q}d\mu$, thenThus $I_N^{1/q}\le C$ when $I_N>0$, and the same bound is trivial when it is zero. The monotone convergence theorem givesIf $E,F$ both have finite measure, the densities $g_E,g_F$ agree almost everywhere on $E\cap F$: their integrals over every measurable subset of the intersection equal the same functional value. This is uniqueness in the Radon-Nikodym theorem.

We now perform support localization of an Lp functional. SetChoose finite-measure sets $E_n$ whose displayed integrals tend to $M$, and let $D_n=E_1\cup \cdots \cup E_n$, $S={\bigcup }_n{D}_n$. If $M=0$, take $E_n=\varnothing$. Compatibility allows us to define a measurable function $g$ on $S$ by taking $g_{D_n}$ on the disjoint measurable sets $D_n\setminus D_{n-1}$, and put $g=0$ off $S$. It agrees almost everywhere with $g_{D_n}$ on every $D_n$. Moreover,Indeed each integral is at most $M$, and it is at least the integral over $E_n$, which tends to $M$.

For any finite-measure set $F\subseteq \Omega \setminus S$, compatibility on the disjoint union $D_n\cup F$ givesLetting $n\to \infty$ forces $g_F=0$ almost everywhere. For an arbitrary finite-measure set $E$, compatibility on $E\cap D_n$ and the preceding conclusion on $E\setminus S$ show that $g_E=g$ almost everywhere on $E$. Consequently $\Phi (h)=\int hgd\mu$ for every simple function supported on a finite-measure set.

Those simple functions are dense in $L^p$ even for this arbitrary measure space. To see the needed finite-support property, for $h\in L^p$ the sets $\{|h|>1/n\}$ have finite measure, bounded by $n^p\Vert h{\Vert }_p^p$. First truncate $h$ to such sets and to bounded values, then approximate by simple functions; the discarded $L^p$ integral tends to zero. Continuity of $\Phi$ and Hölder's inequality therefore extend the representation to every $h\in L^p$.

We have constructed $g\in L^q$ with $\Phi ={\Phi }_g$, and the previously proved norm identity gives $\Vert g{\Vert }_q=\Vert \Phi \Vert$. It also proves uniqueness: if ${\Phi }_g={\Phi }_{\tilde{g}}$, then $\Vert g-\tilde{g}{\Vert }_q=0$. This completes the isometric duality of Lp spaces.

The dominated sequence actually converges to zero in norm, and hence weakly. The assumptions give $|f_n{|}^p\le |f{|}^p\in L^1$ and $|f_n{|}^p\to 0$ almost everywhere. The dominated convergence theorem yieldsFor every $\Phi \in (L^p{)}^{\ast }$, $|\Phi (f_n)|\le \Vert \Phi \Vert \Vert f_n{\Vert }_p\to 0$. Therefore

The definitions in a unital C-star algebra areThus a Hermitian element of a C-star algebra is self-adjoint, a Unitary element of a C-star algebra has inverse $x^{\ast }$, and a Normal element of a C-star algebra commutes with its adjoint. We derive the needed C-star algebra facts directly from $\Vert a^{\ast }a\Vert =\Vert a{\Vert }^2$, as required.

First $\Vert 1\Vert =\Vert 1{\Vert }^2$ gives $\Vert 1\Vert =1$, andgives $\Vert a\Vert \le \Vert a^{\ast }\Vert$; applying the same argument to $a^{\ast }$ gives equality. Thus the involution is an isometry. For a Unitary element of a C-star algebra $u$,The general Banach algebra spectrum bound gives $|\lambda |\le 1$ for $\lambda \in \sigma (u)$. Such a $\lambda$ is nonzero, and the inverse spectral mapping theorem gives ${\lambda }^{-1}\in \sigma (u^{-1})$, so also $|\lambda {|}^{-1}\le 1$. Hence

If $h=h^{\ast }$, the convergent exponential series and the isometric involution give $(e^{ith}{)}^{\ast }=e^{-ith}$. These commuting exponentials multiply to $1$, so $e^{ith}$ is unitary for real $t$. By the exponential spectral mapping theorem, if $\lambda \in \sigma (h)$ then $e^{it\lambda }\in \sigma (e^{ith})\subseteq \mathbb{T}$. Taking $t=1$ gives $e^{-\mathrm{Im}\lambda }=1$, soOnly general Banach algebra spectral mapping theorem and the defining C-star identity were used.

Now prove spectral permanence for C-star algebras. Let $B\subseteq A$ be the norm-closed C-star subalgebra with the same identity. The algebraic inclusion always gives ${\sigma }_A(b)\subseteq {\sigma }_B(b)$. For $h=h^{\ast }\in B$, both spectra lie in $\mathbb{R}$. If $\lambda \notin {\sigma }_A(h)$, choose nonreal ${\lambda }_n\to \lambda$. Since ${\sigma }_B(h)\subseteq \mathbb{R}$, each $({\lambda }_{n}1-h{)}^{-1}$ belongs to $B$. By continuity of inversion in a Banach algebra, these inverses converge in $A$ to $(\lambda 1-h{)}^{-1}$, which belongs to $B$ because $B$ is closed. Thus $\lambda \notin {\sigma }_B(h)$, proving equality for hermitian elements.

For the requested normal $x\in B$, suppose $b=x-\lambda 1$ is invertible in $A$. The element $b^{\ast }b$ is hermitian and invertible in $A$, so the equality just proved places $(b^{\ast }b{)}^{-1}$ in $B$. ConsequentlySince $b$ already has a two-sided inverse in $A$, multiplying $yb=1$ by that inverse gives $y=b^{-1}$. Hence its inverse belongs to $B$, and

We need one more elementary consequence of the C-star identity: the spectral radius norm equality for normal elements. If $h=h^{\ast }$, then $\Vert h^2\Vert =\Vert h{\Vert }^2$. If $a$ is normal, commutativity of $a,a^{\ast }$ givesEvery power of $a$ is a Normal element of a C-star algebra. Induction gives $\Vert a^{2^n}\Vert =\Vert a{\Vert }^{2^n}$. The general spectral radius formula therefore implies

The continuous functional calculus is the unique unital $\ast$-homomorphism $C(K)\to \mathcal{B}(H)$ taking the coordinate function to $T$. For bounded linear operators on a Hilbert space, the adjoint identity gives $\Vert S\Vert ={\sup }_{\Vert v\Vert =\Vert w\Vert =1}|⟨Sv,w⟩|=\Vert S^{\ast }\Vert$. ThereforeThis proves the C-star identity for $\mathcal{B}(H)$ directly; completeness and submultiplicativity come from the operator norm. LetBecause $T$ is a normal operator, this is a commutative unital C-star algebra. Every element of $C$ is a Normal element of a C-star algebra, so the preceding norm identity says its Gelfand transform is isometric:Here $\Delta (C)$ is the compact character space from the general Gelfand representation theorem for commutative Banach algebras.

Each algebra character preserves the involution. Indeed, write $a=h+ik$ with $h,k$ hermitian; $\chi (h)\in {\sigma }_C(h)\subseteq \mathbb{R}$ and similarly for $k$, so $\chi (a^{\ast })=\overline{\chi (a)}$. Therefore the continuous mapis injective: its value determines $\chi (T^{\ast })$ and hence its value on all the dense polynomials. It is surjective because the general character description of the spectrum gives $\{\chi (T):\chi \in \Delta (C)\}={\sigma }_C(T)$, and spectral permanence for C-star algebras identifies this with ${\sigma }_{\mathcal{B}(H)}(T)=K$. A continuous function that is a bijection from a compact space to a Hausdorff space is a homeomorphism, so we identify $\Delta (C)$ with $K$.

Under this identification, the Gelfand transform sends $T$ to $u(z)=z$ and $T^{\ast }$ to $\overline{u}$. Its image is an isometric, and therefore closed, unital self-adjoint subalgebra of $C(K)$. It separates points because it contains $u$. The complex Stone-Weierstrass theorem makes the image dense, hence equal to all of $C(K)$. Inverting the Gelfand transform and including $C$ into $\mathcal{B}(H)$ givesan isometric unital C-star homomorphism with $u(T)=T$.

To prove uniqueness without assuming automatic continuity of C-star homomorphisms, let $\Psi$ be any other such map. Since every $f\in C(K)$ is normal, $\Psi (f)$ is normal. A unital algebra homomorphism preserves inverses, soUsing the normal-element norm identity yields $\Vert \Psi (f)\Vert =r(\Psi (f))\le \Vert f{\Vert }_{\infty }$. Thus $\Psi$ is contractive. It agrees with $\Phi$ on polynomials in $u,\overline{u}$, since both send them to the same polynomials in $T,T^{\ast }$. These polynomials are dense by the Stone-Weierstrass theorem, so continuity proves $\Psi =\Phi$. This establishes the continuous functional calculus with no unproved theorem specific to C-star algebras.

A disconnected spectrum gives a nontrivial closed invariant subspace. Write $K=K_1\bigsqcup K_2$ with $K_1,K_2$ nonempty and both open and closed in $K$. The indicator function $f=1_{K_1}$ is continuous on $K$, even though no such continuity is needed across the gap outside $K$. Let $P=f(T)$. The continuous functional calculus givesIts isometry gives $\Vert P\Vert =1$ and $\Vert I-P\Vert =1$, so $P\ne 0,I$. The linear projection has closed range $Y=PH=\ker (I-P)$. Its range is nonzero and proper, and $T(Px)=P(Tx)\in Y$ proves invariance. Since it also commutes with $T^{\ast }$, the same subspace is reducing. This proves disconnected spectrum gives a reducing subspace.

The figure can be realized without any eigenvalues: take $H=L^2(K,dA)$, where $dA$ is planar area on the two closed disks, and let $T$ multiply by $z$. Its adjoint multiplies by $\overline{z}$, so it is a normal operator. An eigenvector for $\lambda$ would be supported on the area-zero singleton $\{\lambda \}$, hence would be zero in $L^2$. Outside $K$, multiplication by $1/(z-\lambda )$ is a bounded inverse to $T-\lambda I$. For $\lambda \in K$, normalized indicator functions of $K\cap \{|z-\lambda |<\epsilon \}$ have $\Vert (T-\lambda I)h\Vert \le \epsilon$, excluding a bounded inverse. Thus its spectrum is exactly $K$. The linear projection in the figure multiplies by $1_{K_1}$, and its range consists of functions supported on the left disk.

The Szemerédi theorem says that for every integer $k\ge 2$ and every $\delta >0$, there is $N_0(k,\delta )$ such that, for $N\ge N_0$, every $A\subseteq \{1,\dots ,N\}$ with $|A|\ge \delta N$ contains a nonconstant arithmetic progressionEquivalently, every subset of the positive integers with positive upper asymptotic density contains arithmetic progressions of every finite length. Length one is immediate.

The Furstenberg multiple recurrence theorem states that for every probability measure-preserving system, every measurable $B$ with $\mu (B)>0$, and every integer $k\ge 2$, there is $n\ge 1$ withHere $T^{-jn}B$ means a preimage, so invertibility is unnecessary. The Furstenberg multiple recurrence theorem also does not assume an ergodic transformation.

We prove the implication to the finite Szemerédi theorem by constructing the Furstenberg correspondence principle explicitly. Suppose, to the contrary, that for fixed $k$ and $\delta >0$ there are $N_{\ell }\to \infty$ and $A_{\ell }\subseteq \{1,\dots ,N_{\ell }\}$ with $|A_{\ell }|\ge \delta N_{\ell }$, but with no length-$k$ arithmetic progression of positive common difference. In the binary full shift $\Omega =\{0,1{\}}^{\mathbb{Z}}$, encode $A_{\ell }$ as $x_j^{(\ell )}=1_{A_{\ell }}(j)$, taking all coordinates outside $A_{\ell }$ to be zero. Let $S$ be the left shift, $(S\omega {)}_j={\omega }_{j+1}$, and setThe cylinder set $C$ is a clopen set, and ${\nu }_{\ell }(C)=|A_{\ell }|/N_{\ell }\ge \delta$. The binary full shift is a compact metric space, so compactness of probability measures on a compact metric space gives a subsequence of these empirical measures with weak convergence of probability measures to a Borel probability measure $\nu$.

For every continuous $h$ on the full shift,Passing to the weak limit shows that $\nu$ is an invariant measure for the continuous left shift. Thus $(\Omega ,\mathcal{B},\nu ,S)$ is a probability measure-preserving system. Since the indicator function of $C$ is continuous, $\nu (C)\ge \delta$.

Apply the Furstenberg multiple recurrence theorem to $C$. For some $n\ge 1$, the clopen sethas $\nu (D)>0$. Its continuous indicator function gives ${\nu }_{\ell }(D)\to \nu (D)>0$. For large $\ell$, at least one $S^a{x}^{(\ell )}$ in the defining empirical measure therefore belongs to $D$. The choice of left shift impliesso $a,a+n,\dots ,a+(k-1)n$ lies in $A_{\ell }$. This contradicts the assumed absence of arithmetic progressions and proves the finite Szemerédi theorem. Applying the finite Szemerédi theorem on intervals where an infinite set has density bounded below proves the stated upper asymptotic density formulation.

For multiple recurrence for circle rotations, write $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ and $R_{\alpha }x=x+\alpha$, with normalized Lebesgue measure $m$, which is the Haar measure of the circle group. Fix a measurable $B\subseteq \mathbb{T}$ with $m(B)>0$ and $k\ge 2$. If $\alpha$ is rational, there is $q\ge 1$ with $R_{\alpha }^q$ the identity, and $n=q$ gives an intersection of measure $m(B)$.

For irrational $\alpha$, the pigeonhole principle applied to $0,\alpha ,\dots ,Q\alpha$ in $Q$ equal arcs gives $1\le n\le Q$ with $\Vert n\alpha {\Vert }_{\mathbb{T}}\le 1/Q$. In particular there are arbitrarily small nonzero returns to zero for the irrational rotation of the circle.

We also need translation continuity in L1 on the circle. Given a measurable $B$, approximate its indicator function in the L1 norm by a continuous $g$ on the circle group. Such approximation follows from regularity of Lebesgue measure, or approximation by finite unions of intervals. Translation invariance and uniform continuity givewhere the approximation error is first made arbitrarily small. Equivalently, $m(B△(B-t))\to 0$.

Choose a return time $n\ge 1$ so small modulo one that for each $1\le j<k$,This is possible because multiplication by each fixed $j$ is continuous on the circle group and translation continuity in L1 on the circle applies to the finitely many translates. The union bound now givesThis proves the Furstenberg multiple recurrence theorem for every circle rotation with its normalized Lebesgue measure, including both rational and irrational angles.

A sufficient absolute constant is $\boxed{C=16}$. The proof is a density increment argument for a cap set over the finite field ${\mathbb{F}}_3$.

First work in $V={\mathbb{F}}_3^d$, write $N=3^d$, and let $f=1_A$ be the indicator function of a cap set of subset density $\alpha >0$. All expectations below are uniform. In characteristic three, a solution of $x+y+z=0$ having two equal entries has all three equal. Consequently the normalized linear configuration count isSet $\omega =e^{2\pi i/3}$ and use Fourier analysis on a finite abelian group withThe orthogonality of roots of unity and the Parseval identity on a finite group giveIf $N{\alpha }^2\ge 2$, then $\alpha <1$ for a cap set andThus some nonzero finite abelian Fourier coefficient has magnitude at least ${\alpha }^2/2$.

For this $\xi$, let ${\alpha }_j$ be the subset density of $A$ on the affine subspace $\{x:\xi \cdot x=j\}$, for $j=0,1,2$. These three affine subspaces have equal cardinality, andAmong three directions separated by $2\pi /3$, one makes an angle at most $\pi /3$ with any given complex number. Hence ${\max }_j({\alpha }_j-\alpha )\ge |\hat{f}(\xi )|$. Restricting to that hyperplane gives the hyperplane density increment for cap setsTranslate the affine subspace to its underlying vector space. This preserves the cap set property: translating a triple by $t$ changes its sum by $3t=0$. The same argument can therefore be iterated.

For completeness, the density increment iteration gives an explicit uniform bound. If $n<16$, the hypothesis $\alpha \ge 16/n$ is impossible. Suppose $n\ge 16$ and a cap set has ${\alpha }_0\ge 16/n$. For every integer $0\le t\le \lfloor n/2\rfloor$, its remaining dimension is at least $n/2$, and its current subset density is at least $16/n$. ThusThe last inequality holds at $n=16$ and remains true as $n$ increases: the successive ratio of $3^{n/2}/n^2$ is $\sqrt{3}(n/(n+1){)}^2>1$ for $n\ge 16$. At each step, as long as the subset density remains at most one,After $L=\lfloor n/2\rfloor$ steps this would implya contradiction. The endpoint $\alpha =1$ already contradicts the cap set property in positive dimension. This proves the claimed existence of three distinct points and the Meshulam bound for cap sets.

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.

Let ${\sigma }_1=\gamma ,{\sigma }_2,\dots$ be the singular values of the normalized adjacency operator of a bipartite graph, with the uniform inner products used above. Its ordinary matrix in an orthonormal basis on each side is $G/\sqrt{|X||Y|}$. Expanding the trace of $({\theta }_G{\theta }_G^{\ast }{)}^2$ proves the box norm singular-value identityTherefore (ii) immediately implieswhich is (iii).

Conversely, the square of the Hilbert-Schmidt norm of this operator issince a graph indicator function takes values zero and one. Under (iii), every ${\sigma }_j$ with $j\ge 2$ is at most $c_3$, soThus (iii)$\Rightarrow$(ii) with $\boxed{c_2=c_3^2/4}$. This bound also covers the empty and complete bipartite graphs.

First take nonempty bounded open sets $A,B\subset {\mathbb{R}}^n$. Their Minkowski sum is open and hence a Lebesgue measurable set. Apply the Prékopa–Leindler inequality to their indicator functions and the indicator function of $(1-\theta )A+\theta B$. This gives the multiplicative formTo obtain the usual additive Brunn–Minkowski inequality, put $a={\lambda }_n(A{)}^{1/n}$, $b={\lambda }_n(B{)}^{1/n}$, $A_0=A/a$ and $B_0=B/b$. Both normalized open sets have Lebesgue measure one. For $\theta =b/(a+b)$,The multiplicative bound and the scaling rule for Lebesgue measure implyReplacing $A,B$ by $A\cap B(0,R),B\cap B(0,R)$ and using continuity from below extends this form of the Brunn–Minkowski inequality to all nonempty open sets, including those of infinite Lebesgue measure. This open-set form is sufficient here and avoids any measurability qualification for sums of arbitrary measurable sets.

A many-one reduction $A{\le }_{m}B$ is a total computable function $f:\mathbb{N}\to \mathbb{N}$ such thatA Turing reduction $A{\le }_{T}B$ is an oracle machine which, with membership oracle $B$, halts on every input and computes the indicator function ${\chi }_A$. It may make finitely many adaptive queries on each input. A many-one reduction gives a Turing reduction by a single query, but Turing reducibility allows more general procedures.

The Friedberg–Muchnik theorem states that there are computably enumerable sets $A,B$ with incomparable Turing degrees:Here is a finite-injury priority construction proving it. Effectively enumerate all Turing functionals $({\Phi }_e)$. Arrange the requirements in the priority orderEquality would require the Turing functional to be total and give the correct bit at every input; one disagreement or one undefined input defeats it.

Start with $A_0=B_0=\varnothing$ and enumerate elements without ever removing them. A strategy has a private witness, a flag recording whether it has acted, and a restraint on its oracle. Every new witness is larger than every previously assigned witness and every current higher-priority restraint. Retired witnesses are never reused. The only possible enumeration of a witness is by its owner, so an unacted witness remains outside its target set.

The strategy for $R_e$ chooses a witness $x$ and waits for a stage at which the bounded simulation givesOn seeing this, put $x$ into $B$, declare the strategy acted, and impose restraint $u$ on $A$, where $u$ is the oracle use: one more than the largest queried number, or zero if there were no queries. Initialize every lower-priority strategy, discarding its current witness, acted flag and restraint. An acted strategy does nothing further until initialized. The strategy for $S_e$ is identical with $A,B$ interchanged. Waiting specifically for zero is enough: if the eventual output is nonzero while the witness stays out, it already disagrees with the target indicator function.

For a completely effective schedule, at stage $s$ visit the first $s+1$ strategies in priority order. Assign an unassigned witness when visited. Simulate each unacted strategy's computation for at most $s$ steps with the current finite oracle. If some strategy can act, perform the first such action and end the stage; otherwise end after all visits. All steps are finite and algorithmic, so the limiting $A,B$ are computably enumerable sets.

Every lower-priority enumeration respects higher-priority restraints. When its witness was chosen it lay above these restraints. Any subsequent action of a higher-priority strategy would have initialized it, so its current witness remains safe to enumerate. The initialization of all lower strategies also removes their obsolete restraints before they can obstruct a legitimate higher-priority action.

We verify finite injury by mathematical induction on priority. The first strategy is never injured and acts at most once. If all predecessors of a strategy act finitely often, there is a last stage when a higher-priority action initializes it. It is subsequently visited, chooses its permanent witness, and acts at most once. Thus it too acts finitely often and all its lower-priority strategies suffer only finitely many injuries. The scheduling cannot starve a fixed strategy: after the finitely many higher-priority actions, all sufficiently large stages visit it.

Consider the final uninjured $R_e$ with witness $x$. If it acts, then $x\in B$ permanently, and every later lower-priority enumeration into $A$ respects its restraint. No later higher-priority action occurs. The preserved computation is thereforeIf it never acts, $x\notin B$. Were ${\Phi }_e^A={\chi }_B$, the final computation on $x$ would halt with zero and have finite oracle use. The finitely many oracle bits it queries eventually stabilize, and a sufficiently late bounded stage simulation would see exactly this zero computation. The strategy would then act, a contradiction. Hence $R_e$ holds in this case too. The same reasoning proves every $S_e$.

All possible Turing reductions in both directions are excluded. This proves the Friedberg–Muchnik theorem; in particular both constructed Turing degrees are noncomputable, since a computable set is Turing reducible to every oracle.

An additive arithmetic function satisfies $f(mn)=f(m)+f(n)$ for coprime integers $m,n$; a completely additive arithmetic function satisfies this for all positive $m,n$. In either case $f(1)=0$. The Fundamental theorem of arithmetic gives $f(n)={\sum }_{p^k\parallel n}f(p^k)$, where $p^k\parallel n$ means that the prime valuation of $n$ at $p$ is exactly $k$.

Under the discrete uniform distribution on $[N]$, the expectation of the indicator function of $p^k\parallel n$ isThe formula remains valid when $p^{k+1}>N$. Applying linearity of expectation to the finite prime power decomposition proves the required mean formula:

For the last assertion, write the excess prime-factor multiplicity directly as a sum of nonnegative indicator functions:Here $\omega$ is the prime omega function and $\Omega$ is the total number of prime factors. The expectation is bounded independently of $N$, sinceThus Markov inequality gives vanishing probability on every diverging scale:

Write $y=N^{1/\phi (N)}$, $L={\sum }_{p\le y}|g(p)|$, and $A={\sum }_{p\le y}g(p)/p$. Put $I_p(n)=1_{p\mid n}$ and $Y_p=I_p-1/p$. The strongly additive arithmetic function identity is $g-A={\sum }_{p\le y}g(p)Y_p$.

For any tuple $p_1,\dots ,p_j$, expand ${\prod }_{r=1}^j(I_{p_r}-1/p_r)$ by choosing an indicator in some positions and the constant in the others. If the selected positions contain distinct primes whose product is $d$, thenFor the corresponding product of the independent Bernoulli random variables $X_p$, the expectation is exactly $1/d$. This includes repeated primes, since their indicator functions are idempotent, and the empty selection has zero error. Summing absolute values of all expansion coefficients bounds the difference bywhen $y\ge 2$. Expanding the $j$th power and summing the absolute coefficient weights gives

It remains to center at the actual expectation. Since ${\mathbb{E}}_N{I}_p=\lfloor N/p\rfloor /N$, we have $|{\mathbb{E}}_{N}g-A|\le L/N$. For each $n$, both $g(n)-A$ and $g(n)-{\mathbb{E}}_{N}g$ have absolute value at most $L$, because all their indicator coefficients have absolute value at most one. The identity $u^j-v^j=(u-v){\sum }_{r=0}^{j-1}{u}^{j-1-r}{v}^r$ therefore bounds the change in the central moment by $j{L}^j/N$.

Finally, independence factors each term of the independent central moment. If $q_1,\dots ,q_w$ are the distinct primes of the tuple and $a_i$ their multiplicities, the desired comparison becomesIf $y<2$, then $g=0$ and both sides vanish, so the formula remains valid. The argument also covers complex coefficients $g(p)$; a real-valued assumption is needed for the later normal distribution conclusion, not for this centered moment comparison for additive arithmetic functions.

Use the probability space $([0,1{]}^{{\mathbb{Z}}^d},\mathcal{F},\mathbb{P})$ with the product measure of the uniform distribution on $[0,1]$. Its coordinate random variables $U_v$ are independent and identically distributed random variables. Define simultaneously for every parameterFor $r\le s$, the indicator function inequality $X_r(v)\le X_s(v)$ holds pointwise at every graph vertex. For fixed $p$, each coordinate has the Bernoulli distribution with parameter $p$, and the coordinates are independent because they are functions of distinct independent $U_v$. Thus every marginal configuration is exactly the required site percolation model. This is a continuum-indexed family of processes, all on one probability space, and is the standard monotone coupling of Bernoulli percolation.

Write $h=h_n$ and $I=[t_0,t_0+h]$, restricting to meshes small enough that $t_0+h\le 1$. This discontinuous indicator function does not satisfy the hypothesis of part (b). Instead apply part (a) with $\Vert g_n{\Vert }_{\infty }=1/h$ and handle its two boundary cells directly.

Let $q_n(s)=g_n(t_{i-1})$ on each observation cell $[t_{i-1},t_i)$. Away from cells containing the two ends of $I$, $q_n=g_n$ almost everywhere. Even if an endpoint is itself an observation time, at most two cells contribute, and their total length is at most $2\Delta$. Thus the quadrature error obeysThe fluctuation has variance at most $2S\Delta /h^2$. Its zero expected value givesusing $\Delta \le 1$.