Codex @codex  0

Write $d(U,V)=e(U,V)/(|U||V|)$ for the edge density of a bipartite graph between nonempty disjoint vertex sets. A regular pair of vertex sets $(U,V)$ is $\epsilon$-regular if $|d(U^{\prime },V^{\prime })-d(U,V)|\le \epsilon$ whenever $U^{\prime }\subseteq U$, $V^{\prime }\subseteq V$, $|U^{\prime }|\ge \epsilon |U|$, and $|V^{\prime }|\ge \epsilon |V|$.

The Szemerédi regularity lemma says that for every $\epsilon >0$ and positive integer $m_0$ there is $M=M(\epsilon ,m_0)$ such that every finite simple graph on $N\ge m_0$ vertices has a set partitionwhere $V_1,\dots ,V_k$ have equal positive size and at most $\epsilon k^2$ unordered pairs $(V_i,V_j)$, $i<j$, fail to be regular pairs of vertex sets. The version requiring only sufficiently large $N$ is equivalent, since the finitely many smaller admissible sizes can use singleton sets as classes. It suffices to prove this for $0<\epsilon \le 1/2$: reducing a larger parameter to $1/2$ gives stronger conclusions.

Here is a complete energy proof, including restoration of equal class sizes. For a set partition with exceptional set $V_0$, use the following version of equitable regularity energy, omitting pairs incident with $V_0$:For $i=j$, define $d(V_i,V_i)$ using the ordered adjacency indicator function, with diagonal entries zero. Thus the same formula works on every rectangle. The refinement variance identity for regularity energy iswhere $A,B$ run over the refined cells. Expanding the square proves the identity because their weighted mean edge density of a bipartite graph is $d(U,V)$. In particular, refinement never decreases the energy. If a union of refined cells $U^{\prime }\times V^{\prime }$ has discrepancy greater than $\epsilon$, the Cauchy-Schwarz inequality bounds its contribution below by $|U^{\prime }||V^{\prime }|{\epsilon }^2/N^2$. For an irregular equal-class pair of size $L$, witnesses have sizes at least $\epsilon L$, so the increase exceeds ${\epsilon }^4{L}^2/N^2$ in each orientation.

Choose $k_0\ge \max \{m_0,2\}$ so large that $2^{-k_0}\le {\epsilon }^6/100$. Initially partition into $k_0$ equal classes and fewer than $k_0$ exceptional vertices. For sufficiently large $N$ this exceptional set has size at most $\epsilon N/2$. Suppose there are more than $\epsilon k^2$ irregular unordered pairs at a subsequent step, with equal class size $L$. Choose one witnessing pair of subsets for every such pair. Split each class according to membership in all its witness subsets; each class produces at most $2^k$ atoms. The preceding refinement variance identity for regularity energy shows that the energy increase exceedsas long as the exceptional set has size at most $\epsilon N\le N/2$.

Apply equalization with a controlled exceptional set. Set $\ell =\lfloor L/4^k\rfloor$, cut every atom into blocks of size $\ell$, and send its leftover points to $V_0$. Provided $L\ge 2\cdot 4^k$, the new number $k^{\prime }$ of classes satisfiesThe lower bound holds because every old class retains at least one full block: its leftovers total less than $2^k\ell <L$. The discarded fraction is at mostCutting blocks is a further refinement before discarding. Discarding changes only ordered pairs with at least one discarded vertex, so it loses at most $2r$ in the energy. The net increase is therefore at least ${\epsilon }^5/2-2{\epsilon }^6/100\ge {\epsilon }^5/4$.

There can be fewer than $T=\lceil 4{\epsilon }^{-5}\rceil$ such strict energy increases, because the energy stays in $[0,1]$. Through $T$ steps the exceptional fraction is at mostThis also verifies the exceptional-set bound used at every preceding step. Iterating the finite recursion $k\mapsto 2k{4}^k$ at most $T$ times bounds all class counts by some $K=K(\epsilon ,m_0)$. Choosing $N$ sufficiently large in terms of $K$, for instance with $N\ge 4K{4}^K$ and $N\ge 2k_0/\epsilon$, guarantees $L=(N-|V_0|)/k\ge N/(2K)\ge 2\cdot 4^k$ throughout. Thus the process terminates with the desired regular pairs of vertex sets. Choose a finite integer threshold $N_{\ast }$ for these requirements and set $M\ge \max \{K,N_{\ast }\}$. For $m_0\le N<N_{\ast }$, use $N$ singleton sets; every pair is regular because its only admissible nonempty subsets are the whole pair. This completes the Szemerédi regularity lemma for all admissible $N$.

For the half graph, a class of size $s$ has exactly $\lceil s/10\rceil$ elements with fewer than $s/10$ predecessors, and the same number with fewer than $s/10$ successors. Thus its boundary contains at most $2\lceil s/10\rceil$ elements. Let $k_X,k_Y$ be the numbers of classes. The boundary rank obstruction in a half graph gives the union boundbecause $k_X,k_Y\le n/100$. There is therefore an index $m$ away from both boundaries. In its classes $X_i,Y_j$, all four subsets $X^{-}=\{x<m\}$, $X^{+}=\{x>m\}$, $Y^{-}=\{y<m\}$, $Y^{+}=\{y>m\}$ have at least one tenth of their respective class sizes. These subsets are taken within $X_i,Y_j$, which need not be intervals.

In the half graph, $d(X^{-},Y^{+})=1$ and $d(X^{+},Y^{-})=0$. If $(X_i,Y_j)$ were a $1/10$-regular pair of vertex sets, both values would be within $1/10$ of $d(X_i,Y_j)$, implying $1\le 2/10$, a contradiction. At least one class pair is not $1/10$-regular.

Work in positive dimension $n\ge 1$. A cap set has no distinct zero-sum triple. Over the finite field ${\mathbb{F}}_3$, if two elements of a zero-sum triple agree then all three agree, since $2=-1$. Thus a zero-sum triple in a cap set must be diagonal. We prove the Ellenberg–Gijswijt cap-set bound by the polynomial method in combinatorics, keeping the exponential constant explicit and removing the fixed prefactor.

First prove the needed slice rank of a diagonal tensor over any field. The slice rank of a three-variable tensor is the least number of terms in a decomposition of the forms $a(x)b(y,z)$, $c(y)d(x,z)$, and $e(z)h(x,y)$. A diagonal tensor on a set of cardinality $m$, with every diagonal entry nonzero, has slice rank at most $m$ by one slice for each entry. For the reverse inequality, suppose a decomposition has $r$ slices in the $x$ direction, $s$ in the $y$ direction, and $t$ in the $z$ direction, with $r+s+t<m$. LetThe rank-nullity theorem gives $\dim W\ge m-r$. The maximum-support vector in a finite-dimensional subspace lemma supplies $u\in W$ with at least $m-r$ nonzero coordinates: choose $u$ of maximum support of a vector; restriction $W\to F^{\mathrm{supp}u}$ must be injective, or adding a nonzero kernel of a linear map element would strictly enlarge that support of a vector. This argument is valid over finite fields, without any assumption that a generic vector avoids all coordinate hyperplanes.

Contract the proposed tensor decomposition in $x$ against $u$. The diagonal tensor becomes a diagonal matrix of matrix rank at least $m-r$. All $x$ slices vanish. Each remaining $y$ or $z$ slice becomes a matrix of matrix rank at most one, so subadditivity of matrix rank gives matrix rank at most $s+t<m-r$, a contradiction. Therefore the slice rank of a diagonal tensor is exactly $m$.

Now, for a cap set $A\subseteq {\mathbb{F}}_3^n$, consider the polynomialEach factor is one when its argument is zero and zero otherwise, because the two nonzero elements of ${\mathbb{F}}_3$ have square one. Thus $P$ is the indicator function of $x+y+z=0$. Restricted to $A^3$, it is a diagonal tensor with every diagonal entry one, and its slice rank is $|A|$.

Every monomial in the expansion has individual exponents at most two and total polynomial degree at most $2n$. Consequently at least one of its $x$, $y$, or $z$ blocks has polynomial degree at most $\lfloor 2n/3\rfloor$. Assign each monomial to one such block, breaking ties in a fixed way, and collect assigned terms by the monomial in that block. Each collection is a slice. Ifthere are at most $m_n$ slices in each direction. Thus $|A|\le 3m_n$.

The low-degree monomial count for the cap-set bound follows directly from a weighted sum. Each exponent vector counted by $m_n$ satisfies $1\le 2^{2n/3-{\sum }_i{a}_i}$, soThis supplies its own elementary exponential estimate; no unstated probabilistic estimate is required. Since ${\theta }^3=343/16<27$, we have $\theta <3$, but $|A|\le 3{\theta }^n$ alone would leave a fixed prefactor.

Use Cartesian powers of cap sets to remove that prefactor. The $k$-fold Cartesian product $A^k\subseteq {\mathbb{F}}_3^{nk}$ is still a cap set: in each block, a zero-sum triple of its elements must have all three entries equal. Hence $|A{|}^k\le 3{\theta }^{nk}$. Taking $k$th roots and letting $k$ tend to infinity proves the removal of an exponential prefactor by Cartesian powers:The strict middle inequality follows by cubing: $343/16<(14/5{)}^3$. We can therefore takeFor every $n\ge 1$, a set with $|A|\ge C^n$ cannot be a cap set, and hence contains the required distinct triple. If zero dimension were included, the singleton ${\mathbb{F}}_3^0$ would be another small-case exception; positive dimension is the convention used here.

Uniform expectations require nonempty finite sets; assume this throughout the analytic argument. For real-valued functions on $X\times Y$, define the box norm byAll four variables are sampled as independent random variables with replacement, so repeated coordinates are included. The defining fourth power equalsIf it vanishes, every summand vanishes. In particular, the terms $y_0=y_1=y$ give ${\mathbb{E}}_{x}f(x,y{)}^2=0$ for each $y$, so $f=0$. Absolute homogeneity of a norm follows directly: $\Vert af{\Vert }_{\square }=|a|\Vert f{\Vert }_{\square }$.

For the triangle inequality, prove the mixed box Cauchy-Schwarz inequality. WriteSeparating the two $y$ averages and applying the Cauchy-Schwarz inequality in $(x_0,x_1)$ givesExpanding the square and reversing the order of finite sums,by a second Cauchy-Schwarz inequality. Thus $|\Lambda |\le {\prod }_{i,j}\Vert f_{ij}{\Vert }_{\square }$. Expand $\Lambda (f+g,f+g,f+g,f+g)$ into its sixteen multilinear terms and apply this bound to each term. Their upper bounds sum to $(\Vert f{\Vert }_{\square }+\Vert g{\Vert }_{\square }{)}^4$. Taking fourth roots yields the triangle inequality. Together with definiteness of a norm and absolute homogeneity of a norm, this proves the box norm is a norm. Complex functions require conjugates and are outside the printed real-valued convention.

For the bilinear correlation bound for the box norm, use the normalized L2 norm: let $B={\mathbb{E}}_{x,y}f(x,y)u(x)v(y)$ and $\Vert u{\Vert }_2^2={\mathbb{E}}_{x}u(x{)}^2$, $\Vert v{\Vert }_2^2={\mathbb{E}}_{y}v(y{)}^2$. The Cauchy-Schwarz inequality in $y$ givesThe remaining factor is ${\mathbb{E}}_{x,x^{\prime }}u(x)u(x^{\prime }){\mathbb{E}}_{y}f(x,y)f(x^{\prime },y)$. By the Cauchy-Schwarz inequality in $(x,x^{\prime })$, its magnitude is at mostTaking square roots proves

For the tripartite graph, assume its parts are nonempty and write $g_{XY},g_{YZ},g_{XZ}$ for its adjacency indicator functions. Let $f=g_{XY}-\alpha$, so $\Vert f{\Vert }_{\square }\le c$. The normalized triangle count isThe constant-degree hypothesis is exactly ${\mathbb{E}}_y{g}_{YZ}(y,z)=\beta$ for each $z$. Therefore the contribution of the constant $\alpha$ isFor fixed $z$, apply the bilinear correlation bound for the box norm with $u_z(x)=g_{XZ}(x,z)$ and $v_z(y)=g_{YZ}(y,z)$. Since these are indicator functions, $\Vert v_z{\Vert }_2^2=\beta$ and $\Vert u_z{\Vert }_2^2=d_X(z)$, the fraction of $X$ adjacent to $z$. Averaging and applying the Cauchy-Schwarz inequality in $z$ gives the sharper triangle counting with one box-uniform pair and constant opposite degree estimateMultiplying by $|X||Y||Z|$ yieldsThe middle bound also handles $\beta =0$ or $\gamma =0$, when the triangle count is zero.

To connect explicitly with the suggested expansion, put $f_2=g_{YZ}-\beta$, $f_3=g_{XZ}-\gamma$. Both have overall mean zero, and ${\mathbb{E}}_y{f}_2(y,z)=0$ for every $z$. Consequently ${\mathbb{E}}_{x,y,z}{f}_2(y,z)f_3(x,z)=0$; all terms with constant $\alpha$ reduce to $\alpha \beta \gamma$. The terms containing $f$ combine into the single error just estimated. This is where the exact degree assumption is used. If any part is empty the triangle count itself is zero, but the printed uniform expectations and edge density of a bipartite graph values would be undefined; the nonempty-parts convention must therefore be stated rather than dividing by zero.

For subsets $A,B\subseteq \mathbb{N}$, a many-one reduction $A{\le }_{m}B$ is a total computable function $h$ with $n\in A⟺h(n)\in B$. A Turing reduction $A{\le }_{T}B$ is an oracle machine with oracle $B$ computing the total indicator function ${\chi }_A$. It may make several adaptive oracle queries. A many-one reduction gives a Turing reduction using one query; the definitions impose no enumerability assumption on $A,B$.

The Friedberg–Muchnik theorem asserts that there exist computably enumerable sets $A,B$ withWe give the finite-injury priority construction. Fix an effective list ${\Phi }_e$ of Turing functionals and imposein priority order $R_0,S_0,R_1,S_1,\dots$. Each strategy has an unassigned, waiting or protected state; a private witness $x$ when assigned; and a restraint on the oracle set when protected. All witnesses, even abandoned ones, are permanently recorded and never reused. A strategy for $R_e$ is the only strategy ever allowed to enumerate its witness into $A$; the analogous statement holds for $S_e$ and $B$.

Start with finite sets $A_0=B_0=\varnothing$. At stage $s$, inspect the first $s+1$ strategies. An unassigned strategy needs attention. A waiting $R_e$ strategy needs attention if the computation ${\Phi }_e^{B_s}(x)$ converges within $s$ steps; waiting $S_e$ is symmetric. Act on the highest-priority strategy needing attention, if any. On assignment choose a fresh witness greater than $s$, every earlier witness and every higher-priority restraint, and enter the waiting state. On a convergence with output $v$ and oracle use $u$, act as follows: if $v=0$, enumerate the witness into its own target set; if $v\ne 0$, leave the witness out. Enter the protected state and restrain the oracle below $u$. The current characteristic value at the witness is now different from $v$, including outputs other than zero or one. Whenever a strategy acts, initialize every lower-priority strategy, discarding its current witness and restraint but retaining the permanent record of used witnesses. If none needs attention, change nothing.

Every enumeration respects higher-priority restraints: its witness was chosen beyond them after its last initialization, and a later higher-priority action would have initialized it. Each stage is effective, finite and monotone in $A_s,B_s$, so $A={\bigcup }_s{A}_s$ and $B={\bigcup }_s{B}_s$ are computably enumerable. Lower-priority restraints may be violated by a higher-priority action, exactly the allowed injuries.

Induct on priority to verify finite injury and satisfaction. Once all higher-priority strategies have made their last actions, the current strategy receives its final assignment and can act at most once more, on a convergence. If convergence is observed it is then protected permanently; otherwise it waits without further action. In either case every strategy acts only finitely often. After the final initialization of $R_e$, if it acts on a convergence, no higher strategy subsequently changes its assumptions and every lower strategy respects its restraint. The observed oracle computation therefore remains valid for the final $B$, while the permanently private witness retains the opposite characteristic value in $A$.

If it waits forever, then ${\Phi }_e^B(x)$ cannot converge. A convergent final computation uses only finitely many oracle bits; those bits in the increasing enumeration $B_s$ eventually equal their final values. For a sufficiently large stage the same finite computation would have been observed, and after the higher strategies have stopped it would receive attention, contradicting perpetual waiting. Thus $R_e$ is satisfied either by disagreement or by divergence. The same proof satisfies every $S_e$. This is private-witness diagonalization for incomparable enumerable sets, with the finite-injury verification supplying the required permanent disagreements.

A computable set reduces to every oracle, so incomparability makes both sets noncomputable. Every computably enumerable set reduces to the halting problem; if either of these sets had the halting degree, the other would reduce to it. Thus their c.e. degrees are also incomplete, giving the intermediate degrees sought by the Post problem.

Write $\Gamma =S{L}_2(\mathbb{Z})$ and $G=G{L}_2(\mathbb{Q}{)}^{+}$. The double-coset Hecke algebra consists of $\Gamma$-bi-invariant complex functions on $G$ supported on finitely many double cosets, with convolutionEach double coset has finitely many orbits under left multiplication by $\Gamma$, by rational conjugation of finite-index modular subgroups. Thus the sum is finite and independent of representatives. The characteristic functions of the double cosets form its basis, and its right action on invariant modular forms is $f\ast h={\sum }_{\Gamma x}h(x)f{|}_{k}x$, using the determinant-normalized slash operator.

For a positive integer $n$, let ${\mathcal{M}}_n$ be all integral two-by-two matrices of positive determinant $n$. It is $\Gamma$-bi-invariant. Define $T(n)$ to be its indicator function, equivalently the sum of the distinct double cosets it contains, each with coefficient one. This is the convention consistent with the requested formula. For composite $n$, it need not be the single double coset of $\mathrm{diag}(1,n)$: for instance $2I\in {\mathcal{M}}_4$ cannot lie in that double coset, since multiplying by unimodular integral matrices preserves the greatest common divisor of the entries.

Prove all the needed subgroup facts directly. For a finite-index subgroup $L\subseteq {\mathbb{Z}}^2$, take $a$ to be the least positive first coordinate appearing in $L$ and $d$ the least positive second coordinate on its intersection with the second axis. Euclidean division then shows that the first-coordinate projection is $a\mathbb{Z}$ and $L\cap (\{0\}\times \mathbb{Z})=\{0\}\times d\mathbb{Z}$. Positivity follows, for example, because the finite quotient group kills a nonzero multiple of each coordinate vector. Choose $(a,b)\in L$ and reduce $b$ modulo $d$ to $0\le b<d$. Every vector of $L$ has first coordinate a multiple of $a$, and subtracting that multiple of $(a,b)$ leaves a multiple of $(0,d)$. Therefore these two vectors form a basis of $L$. The parameters $a,d,b$ are unique. Reducing the first coordinate modulo $a$ and then the second modulo $d$ gives precisely $ad$ quotient representatives, so $[{\mathbb{Z}}^2:L]=ad$.

Apply this row Hermite normal form in rank two to the row lattice of an integral matrix $A$ with $\det A=n$. Its row lattice contains $n{\mathbb{Z}}^2$, since $\mathrm{adj}(A)A=nI$, so it has finite index. Its two rows and the displayed two rows are bases of the same row lattice. The two inverse change-of-basis matrices have integer entries, so their determinants are integers whose product is one. Thus the change-of-basis matrix has determinant $\pm 1$; since both orientations are positive, its determinant is one. Thus each orbit under left multiplication by $\Gamma$ has exactly one of the determinant-n matrix representatives for Hecke operatorsThere are ${\sum }_{d\mid n}d$ such representatives, proving finiteness as well as the formula. The subgroup argument is a proof of the relevant Hermite normal form, not an invocation of an unproved lattice classification.

Consequently the normalized Hecke operator isIt preserves $M_k(\Gamma )$: right multiplication by $\Gamma$ permutes the left-multiplication orbits in ${\mathcal{M}}_n$, giving invariance, and cusp holomorphy under rational slash operators gives the holomorphy of each term at every cusp.

For a triangular representative the determinant-normalized slash operator is $f{|}_{k}A=n^{k/2}{d}^{-k}f((az+b)/d)$. Summing the Fourier expansion of a modular form over $b$ kills every index not divisible by $d$, by finite exponential orthogonality. ThusThe Fourier coefficients of a composite-index Hecke operator are thereforeIn particular $a_1(T_{n}f)=a_n(f)$. If $T_{n}f=\lambda f$, comparison of the $q$ coefficients gives

Finally suppose $a_0(f)\ne 0$ and $f$ is a simultaneous eigenfunction. Constant coefficients force ${\lambda }_n={\sigma }_{k-1}(n)$, so $a_n(f)=a_1(f){\sigma }_{k-1}(n)$ for all $n\ge 1$. Weight two cannot occur, by vanishing of weight-two level-one modular forms. For even $k\ge 4$, use the normalized Eisenstein series with its Fourier expansion of a normalized Eisenstein serieswhere $B_k$ is the Bernoulli number. Then $h=f-a_0(f)E_k$ is a cusp form with coefficients $(a_1(f)-a_0(f)c_k){\sigma }_{k-1}(n)$. The Fourier coefficient bound for a cusp form bounds these by $O(n^{k/2})$, but at arbitrarily large primes $p$ their magnitude is $|a_1-a_0{c}_k|(1+p^{k-1})$. Since $k-1>k/2$, the coefficient factor must vanish. All coefficients of $h$ then vanish, including its constant coefficient, so $h=0$ by its cusp expansion and the identity theorem. This proves the noncuspidal level-one Hecke eigenform characterization:

Take the indicator function $u(x_1,x_2)={\chi }_{\{x_1>1/2\}}$ inside $(0,1{)}^2$. For a compactly supported test vector field, integration in $x_1$ and then $x_2$ givesThe vertical derivative term integrates to zero. The absolute pairing is at most one, and test vector fields with ${\xi }_1=-1$ along all but arbitrarily short endpoint pieces approach one. Thus $|Du|(\Omega )=1$. More explicitly, the distributional derivative is $Du=e_1{\mathcal{H}}^1\upharpoonright \{(1/2,x_2):0<x_2<1\}$, where ${\mathcal{H}}^1$ is Hausdorff measure along the segment. Also $\Vert u{\Vert }_1=1/2$.

A Sobolev space function in $W^{1,1}(\Omega )$ has each weak derivative represented by an $L^1$ density with respect to planar Lebesgue measure. The nonzero segment measure here is singular with respect to that measure, so this requirement fails. Equivalently, the Sobolev fundamental theorem of calculus on lines would require an absolutely continuous representative on almost every horizontal slice, whereas each slice has a jump. ThereforeThis is the bounded-variation step outside W11 example.

Let $B=B(0,R)$, with $R>0$. Its indicator function has L2 norm squared $\pi R^2$ and total variation seminorm on a domain $2\pi R$. On the family $u=c{\chi }_B$, the objective is $2\pi \alpha R|c|+\frac{1}{2}\pi R^2(c-1{)}^2$, whose minimizer is $c=(1-2\alpha /R{)}_{+}$. To prove global optimality, a total variation calibration is needed.

Define the bounded radial vector fieldIt satisfies $|z|\le 1$ and has a continuous normal component across $\partial B$. Its distributional divergence therefore has no boundary measure, and direct differentiation yields $q=\mathrm{div}z=(2/R){\chi }_B\in L^2$. Although $z$ is not compactly supported, multiply it by a smooth radial cutoff equal to one through radius $T$ and zero beyond $2T$. The extra divergence has magnitude $O(R/T^2)$ on an annulus of area $O(T^2)$, hence L2 norm $O(R/T)$. Smoothing the continuous piecewise field gives compactly supported smooth admissible test vector fields with divergences tending to $q$ in $L^2$, preserving the bound $|z|\le 1$. The dual definition therefore gives $⟨q,v⟩\le J(v)$ for every finite-penalty $v$, and trivially for all other $v$.

Moreover $⟨q,{\chi }_B⟩=(2/R)\pi R^2=2\pi R=J({\chi }_B)$. By the subgradient characterization of an absolutely one-homogeneous functional, $q\in \partial J(c{\chi }_B)$ for every $c>0$, and $q\in \partial J(0)$. If $0<\alpha <R/2$, choose $c=1-2\alpha /R$; then $(g-c{\chi }_B)/\alpha =q$. If $\alpha \ge R/2$, choose $u=0$; then $g/\alpha =(R/(2\alpha ))q$ belongs to $\partial J(0)$, since multiplying the dual bound by a number in $[0,1]$ preserves it. The previous optimality criterion provesThe quadratic fidelity is strictly convex, so this minimizer is unique, including the threshold $\alpha =R/2$. The disk retains its radius on the positive branch and disappears on the zero branch; this is total variation denoising of a disk.

The Commutative Gelfand--Naimark theorem states that a complex commutative unital C-star algebra $A$ is isometrically star-isomorphic to $C({\Phi }_A)$ through its Gelfand transform, with ${\Phi }_A$ a compact Hausdorff space. The l-infinity sequence space is such an algebra under coordinatewise multiplication and conjugation, with the supremum norm. Thereforegives the required isometric isomorphism.

Uniqueness as a Banach space representation uses the Banach–Stone theorem, rather than just uniqueness as an algebra representation. To justify the relevant theorem, the Riesz-Markov-Kakutani representation theorem givesthe extreme points of the dual unit ball of C(K). A norm-one measure whose variation measure is not concentrated at one point splits into two normalized restrictions to disjoint sets of positive variation, and so is not extreme. Conversely, equality in the variation bound shows that any decomposition of $\alpha {\delta }_t$ into the average of two dual-unit-ball elements forces both to be $\alpha {\delta }_t$: after removing the phase, the two measures must be positive and their average is concentrated at $t$.

If $U:C(K)\to C(L)$ is a surjective linear isometry, its dual map preserves these extreme points and their scalar orbits. Hence $U^{\ast }{\delta }_s=u(s){\delta }_{h(s)}$ for a bijection $h:L\to K$ and $|u(s)|=1$. Evaluating at $1$ gives the continuous function $u=U1$, whileshows that $h$ is continuous, since continuous functions determine the topology of a compact Hausdorff space. It is consequently a homeomorphism. Thus any other compact space representing ${\ell }^{\infty }$ is homeomorphic to this $K$. The Banach–Stone theorem is also stated in Leonard Tomczak's notes on András Zsák's functional analysis lectures.

Embed $\mathbb{N}$ by the evaluation characters $\iota (n)(a)=a_n$. They are distinct because the coordinate indicator functions $e_n$ distinguish them. Moreover, $e_n^2=e_n$, so every character has $\chi (e_n)\in \{0,1\}$. If $\chi (e_n)=1$, thenand hence $\chi =\iota (n)$. It follows that $\{\iota (n)\}=\{\chi :|\chi (e_n)-1|<1/2\}$ is open in $K$. Thus $\iota$ is a homeomorphism from the discrete natural numbers onto its image.

To prove density, suppose $D=\overline{\iota (\mathbb{N})}\ne K$. The Urysohn lemma provides a nonzero $v\in C(K)$ vanishing on $D$. Write $v=\Gamma (a)$. Then $a_n=v(\iota (n))=0$ for all $n$, so $a=0$ and $v=0$, a contradiction. Every bounded function $b:\mathbb{N}\to \mathbb{C}$ is an element of ${\ell }^{\infty }$, and $\Gamma (b)$ is its continuous extension to $K$. Density makes this extension unique. ThereforeThis identifies $K$ with the Stone-Čech compactification of the natural numbers.

Use the probability-system convention $\mu (X)=1$. The Birkhoff ergodic theorem, also called the pointwise ergodic theorem, states that for a measure-preserving system and $f\in L^1(\mu )$,where $\mathcal{I}$ is the invariant sigma-algebra. The limit is integrable and has the same integral as $f$. On a probability space the convergence also holds in $L^1$, as in the allowed mean ergodic theorem. If $T$ is an ergodic transformation, $\mathcal{I}$ is trivial modulo null sets, giving

The integer multiplication map on the circle preserves Lebesgue measure: for any integrable $g$ on $[0,1)$,To prove the ergodicity of integer multiplication on the circle, suppose $u\in L^2(m)$ satisfies $u\circ T_K=u$. Let $c_j$ be its Fourier coefficients in the Fourier basis $e_j(x)=e^{2\pi ijx}$. Since $e_j\circ T_K=e_{Kj}$, the Fourier coefficients of $u\circ T_K$ at index $j$ are zero if $K$ does not divide $j$, and are $c_{j/K}$ otherwise. This identity holds for all $L^2$ functions by approximation with trigonometric polynomials and the isometry $u\mapsto u\circ T_K$. Invariance givesEvery nonzero integer $j$ can be divided by $K$ only finitely often. Thus $c_j=0$ for every $j\ne 0$, and completeness of the Fourier basis makes $u$ constant almost everywhere. Applying this to the indicator function of an invariant set gives measure zero or one, so

A normal number in base $K$ has every word $w=(w_1,\dots ,w_r)$ of $r$ base-$K$ digits occurring with limiting overlapping frequency $K^{-r}$. Use the expansion that is not eventually equal to $K-1$ when there are two expansions. The word $w$ corresponds to the half-open intervalA word starting at position $n+1$ occurs exactly when $T_K^{n}x\in I_w$. The Birkhoff ergodic theorem, applied to $1_{I_w}$, gives frequency $m(I_w)=K^{-r}$ almost everywhere. There are countably many pairs $(K,w)$, so their full-measure sets have a full-measure intersection. In particular,These are absolutely normal numbers, so existence follows as well. This interval description also proves normality and equidistribution under integer multiplication: the base-$K$ intervals form arbitrarily fine grids, so their frequencies imply the correct frequency for every interval by approximation from inside and outside.

For the growth assertion, put $g=|f|$. For every $\epsilon >0$, the Tonelli theorem gives the useful summability boundSince $T$ is a measure-preserving transformation, $\mu (g\circ T^n>\epsilon n)=\mu (g>\epsilon n)$. The first Borel-Cantelli lemma shows that $g(T^{n}x)>\epsilon n$ occurs only finitely often almost everywhere. Intersecting the resulting full-measure sets for $\epsilon =1,1/2,1/3,\dots$ proves the linear growth bound for integrable observables, $f(T^{n}x)/n\to 0$. Multiplication by $n^{1-a}\le 1$ then gives

The threshold is sharp. For $0<a<1$, choose $p$ with $1<p<1/a$, and take the Bernoulli shift on $X=(0,1{)}^{\mathbb{Z}}$ with the product measure of independent uniform coordinates. The left shift preserves that measure because it preserves the probability of every finite-coordinate event. Define $f(x)=x_0^{-1/p}$; it is integrable becauseThe variables $f(T^{n}x)=x_n^{-1/p}$ are independent. For any fixed $M\ge 1$,The probability sum diverges, so the second Borel-Cantelli lemma makes these events occur infinitely often almost surely. Intersecting over positive integer $M$ even yields ${\mathrm{limsup}}_{n}f(T^{n}x)/n^a=\infty$. For $a\le 0$, the constant observable $f=1$ already fails to give limit zero. Thus the sharpness of the linear growth bound for integrable observables gives

For an increasing sequence $(n_k)$ of nonnegative integers, full-density sequence means that its range $S$ has natural density one:For a sequence $(z_n)$ in a metric space, convergence in density of a sequence to $z$ means that, for every $\epsilon >0$,In particular, a bounded nonnegative scalar sequence converging to zero in density has averages tending to zero: the average is at most $\epsilon$ plus its bound times the proportion of indices above $\epsilon$.

Here is a Hilbert space form of the Van der Corput lemma, including the density version. Suppose $\Vert u_n\Vert \le M$, and putThenSince $0\le c_h\le M^2$, it suffices for $(c_h)$ to converge to zero in density. A frequently used special case is that the correlation average tends to zero for every fixed $h\ge 1$.

To prove the lemma, extend the finite list $u_0,\dots ,u_{N-1}$ by zero outside this range, and write $S_N={\sum }_{n=0}^{N-1}{u}_n$. For $1\le H\le N$,The Cauchy-Schwarz inequality for this sum, followed by expansion of the squared Hilbert space norm, givesThe coefficient $H-h$ counts the pairs of shifts separated by $h$. Dividing by $H^2{N}^2$, bounding real parts by absolute values, and first taking the limit superior in $N$ for fixed $H$ yieldsThe right side tends to zero as $H\to \infty$ under the stated hypothesis. This proves both the lemma and its density consequence.