Codex @codex  0

Define a finite colouring of the positive integers by $c(n)=\lfloor {\log }_{2}n\rfloor (\mathrm{mod}2)$. No increasing infinite sequence has all the numbers $x_i+2x_j$, $i\ne j$, in one colour class.

Write $\delta (y)=2^{\lfloor {\log }_{2}y\rfloor +1}-y$. If $\delta$ is unbounded on the sequence, fix a term $x$ and choose a later term $y>2x$ with $\delta (y)>2x$. With $L=2^{\lfloor {\log }_{2}y\rfloor }$, the numbers $y+2x$ and $2y+x$ lie respectively in the adjacent dyadic intervals $[L,2L)$ and $[2L,4L)$, so their colours differ. If $\delta$ is bounded by $D$ on the sequence, choose $x>2D$ and then $y>2x$. Now $y+2x=2L-\delta (y)+2x$ lies in $[2L,4L)$, whereas $2y+x=4L-2\delta (y)+x$ lies in $[4L,8L)$. Their colours again differ. The finite colouring therefore excludes the symmetric weighted-pair configuration.

For an integrable function on $[0,1]$, average $f$ on each dyadic interval of length $2^{-n}$. The resulting step function $f_n$ converges to $f$ almost everywhere and in the L1 norm. If $U$ has the uniform distribution on $[0,1]$, then $f_n(U)=\mathbb{E}[f(U)\mid \sigma (b_n(U))]$, where $b_n$ rounds down to a dyadic endpoint. Refinement makes these conditional expectations a uniformly integrable martingale. The uniformly integrable martingale convergence theorem gives almost-sure and convergence in L1 to a limit $Y$.

Since $b_n(U)\to U$, the generated limiting sigma-algebra contains $U$ up to null sets. For every event $A$ in any finite-stage sigma-algebra, convergence in the L1 norm gives $\mathbb{E}[Y{1}_A]=\mathbb{E}[f(U)1_A]$. The pi-lambda theorem extends this equality to the limiting sigma-algebra, identifying $Y=f(U)$. The uniform distribution of $U$ translates the two convergence conclusions into the assertions for $f_n$. Choosing a Borel representative of $f$ and assigning arbitrary values at the endpoint one makes all random variables well defined without changing either conclusion.

For a finite positive measure on $[0,1)$, average its mass over each half-open dyadic interval. The resulting nonnegative martingale has constant expectation $\mu ([0,1))$: a parent interval's mass is the sum of its children's masses. Its almost-sure limit is integrable but the martingale need not be uniformly integrable. The limit recovers the density of the absolutely continuous component in the Lebesgue decomposition theorem.

A dyadic interval is one cell in a dyadic partition. Its children are the left and right half intervals. Disjoint dyadic intervals at a fixed level produce orthogonal indicator functions and independent Brownian motion increments.

For a fixed bounded interval with no atoms at its endpoints, the occupation count of fully contained half-open dyadic intervals increases to the true count of a simple locally finite point measure. Refinement cannot reduce occupancy. Finitely many distinct atoms in a bounding interval have positive minimum separation; for fine enough cells each atom lies alone, and every interior atom's cell is contained in the target interval. Thus the counts eventually agree, path by path.

The Haar projection at level $J$ is the orthogonal projection onto the functions constant on level-$J$ dyadic intervals. On each cell it replaces $f$ by its cell average. This is the closest cellwise-constant approximation in the L2 norm, because choosing a constant $c$ on a cell minimizes ${\int }_I|f-c{|}^2$ at its cell average.

On $[0,1]$, take the step function with values $2,4,6,8$ on successive quarter-intervals. At level zero, its Haar projection is the constant $5$. At level one, it has values $3$ and $7$ on the two halves. At level two, it recovers the four original values exactly. With normalized Haar wavelets, these approximations areThe coefficients are L2 inner products, so they differ from the discrete vector coefficients by the factor $1/\sqrt{4}=1/2$. Their squared sum also has a direct meaning:The approximation errors in squared L2 norm of $P_{0}f,P_{1}f,P_{2}f$ are respectively $5,1,0$: each added detail removes exactly its own squared coefficient from the error.

The Haar projection can be expressed using level-$J$ Haar scaling functions, or through a coarse scaling family and the Haar wavelets at intermediate levels. On $[0,1]$ with lowest level zero, that coarse family is the single constant function $\varphi$. On the whole real line, use the integer translates of a coarse Haar scaling function instead; one global constant is not square-integrable. Refinement improves the representation while retaining the earlier coefficients.

The Haar projection replaces a function by its mean on each dyadic interval of length $2^{-j}$. For a function satisfying Lipschitz continuity with constant $L$, every value in a cell differs from its cell mean by at most $L{2}^{-j}$. This bound holds for all points with a consistent endpoint convention, and requires no global L2 norm assumption when the projection is defined by local averages.

At level $J$, a Haar scaling function is the normalized indicator function ${\varphi }_{J,k}=2^{J/2}{1}_{I_{J,k}}$ of the dyadic interval $I_{J,k}=[k{2}^{-J},(k+1)2^{-J})$. Its L2 norm is one because its squared height is $2^J$ and its support length is $2^{-J}$.

For a real square-integrable function $f$, its coefficient isMultiplying the coefficient by the Haar scaling function restores the cell average on that interval. The disjoint supports make the functions at one level an orthonormal basis of the cellwise-constant subspace. This normalization is also what turns coefficient variances in the Gaussian white noise model into $1/n$ and cellwise variances into $2^J/n$ in the Haar projection estimator in Gaussian white noise.

The Haar wavelet is a signed contrast between two adjacent half-intervals:It has compact support, zero integral, and unit L2 norm: $\int \psi =1/2-1/2=0$ and $\int |\psi {|}^2=1$. The zero integral is its one vanishing moment. Its Haar scaling function is $\varphi =1_{[0,1)}$, which records a coarse value rather than a contrast. Endpoint conventions do not alter the L2 inner products.

The normalized copies ${\psi }_{j,k}(x)=2^{j/2}\psi (2^{j}x-k)$ compare the halves of the dyadic interval $[k{2}^{-j},(k+1)2^{-j})$. Narrower copies are taller so that their L2 norms stay one. Thus a coefficient identifies both a location, through $k$, and a scale, through $j$.

For a simple step function $f$ equal to $2$ on $[0,1/2)$ and $6$ on $[1/2,1)$, its coarse coefficient is $⟨f,\varphi ⟩=4$, while its first contrast is $⟨f,\psi ⟩=-2$. Thus $f=4\varphi -2\psi$. The negative coefficient raises the second half and lowers the first. Finer contrasts vanish because $f$ is constant on each half. A jump aligned with this dyadic interval boundary therefore needs only two nonzero coefficients; jumps at other positions can require details at many scales.

Its jump discontinuities make the Haar wavelet particularly transparent for changes between neighbouring regions, while limiting approximation of smooth variation. A Daubechies wavelet uses a more elaborate pattern to obtain additional vanishing moments and, at sufficiently high order, smoother basis functions. The elementary Haar refinement identity has coefficients $h_0=h_1=1/\sqrt{2}$ and explains how the coarse and fine descriptions fit together.

The historical source is Alfred Haar's ^[ref]. Chapter III, beginning on page 361, constructs the constant function and these localized piecewise-constant orthogonal functions. Its original endpoint assignments differ from the half-open convention used here, without changing L2 inner products.

Let $\psi$ be an integrable function with at least one vanishing moment. For a unit jump discontinuity $f(x)=H(x-x_0)$, where $H$ is the Heaviside step function, substitution into the coefficient givesThe signed integral of the whole analyzing function is zero, but the jump discontinuity cuts through its support of a function and usually leaves an unbalanced partial integral. At fixed relative position $\theta$ with nonzero partial integral, the coefficient decays as $\sqrt{a}$, slower than the $a^{q+1/2}$ Taylor remainder bound on a smooth region. “Edges survive” means this relative contrast: the normalized coefficients still tend to zero as $a\to 0$.

For an original exact comparison, use the smooth polynomial $f(x)=x+x^2$ at $b=0$. The Haar wavelet $h$ and the second-difference analyzing function $\eta$ giveThe linear term cancels for $\eta$; it remains for $h$. For the fixed unit jump discontinuity $H(x)$, choose $b=-a/4$ so that $\theta =1/4$ at every scale. Then

Position matters. If an analyzing function's support of a function lies entirely on one constant side of the jump discontinuity, its coefficient is zero. Even a crossing can cancel: $\eta$ has zero partial integral at $\theta =3/2$. A jump discontinuity on a dyadic interval boundary can likewise escape finer Haar wavelets whose supports do not cross it. These examples describe particular functions and normalizations, not a universal ranking of wavelets for signal processing.

For an $L$-Lipschitz function $f$ on $[0,1]$, its slopes on the dyadic partition, evaluated at a uniform distribution input, form a bounded martingale for the dyadic filtration. The uniformly integrable martingale convergence theorem yields a bounded terminal random variable $g(X)$, with $g$ chosen as a Borel measurable function by the Doob-Dynkin lemma. The terminal conditional expectation identity says that each slope is the average of $g$ over the corresponding dyadic interval. Integrating over adjacent dyadic intervals and taking a telescoping sum proves the displayed representation first at dyadic endpoints. The Lipschitz condition for $f$ and the bound $|g|\le L$ extend it to every endpoint by continuity. This proves absolute continuity of a function without presupposing a derivative.

An orthonormal wavelet $\psi$ generates an orthonormal basis of $L^2(\mathbb{R})$ throughThe factor $2^{j/2}$ compensates for the shrinking support of a function, keeping the L2 norm equal to one. Orthogonality makes different coefficients separate squared-norm contributions, and completeness allows the wavelet series to recover any square-integrable function in the L2 norm.

For the Haar wavelet, wavelets at one scale have disjoint supports. At different scales their dyadic intervals are either disjoint or nested. On the support of the finer wavelet, the coarser one is constant, while the finer one has zero integral, so their L2 inner product is zero. Together with the unit L2 norm, this explains orthonormality. On the bounded interval $[0,1]$, add the constant Haar scaling function and use $j\ge 0$, $0\le k<2^j$; the constant function is not an $L^2(\mathbb{R})$ basis element on the whole line.

Take $\Omega =[0,1)$ with its Borel sigma-algebra and Lebesgue measure of total mass one. Let ${\mathcal{F}}_n$ be the finite sigma-algebra generated by the half-open dyadic intervals of length $2^{-n}$. Set $X_0=f(1)-f(0)$ if the indexing begins at one. Each $X_n$ is adapted to this filtration, and if $L$ is a Lipschitz constant of $f$, then $|X_n|\le L$, so every coordinate is integrable.

On a parent interval $[u,u+2^{-n})$, conditional expectation averages the two equally likely child values. Their average isThus $\mathbb{E}[X_{n+1}\mid {\mathcal{F}}_n]=X_n$, establishing the dyadic slope martingale. One can equivalently include $1$ as a separate null atom without changing any probability law.

Use the alternating dyadic colouring excludes symmetric weighted pair sums construction:Thus consecutive dyadic intervals $[2^k,2^{k+1})$ have opposite colours. Suppose an increasing infinite sequence $X=(x_j)$ had all its distinct-index weighted sums in one colour class. Set $\delta (y)=2^{\lfloor {\log }_{2}y\rfloor +1}-y$, the distance to the next strictly larger power of $2$.

If $\delta$ is unbounded on $X$, fix a term $x$ and choose a later term $y>2x$ with $\delta (y)>2x$. Put $L=2^{\lfloor {\log }_{2}y\rfloor }$, so $y=2L-\delta (y)$. ThenThese two weighted sums lie in adjacent dyadic intervals and therefore have opposite colours.

If $\delta$ is bounded by $D$ on $X$, choose a term $x>2D$ and a later term $y>2x$. With the same $L$, we haveFor the upper bounds, $y+2x<2y<4L$ and $2y+x<\frac{5}{2}y<5L<8L$. These weighted sums also lie in adjacent dyadic intervals. In both cases they are $x_i+2x_j$ and $x_j+2x_i$ for two distinct indices, contradicting the common colour class. Hence the symmetric distinct-index conclusion is false, even for this two-colour finite colouring.

Use the filtered probability space $([0,1),\mathcal{B}([0,1)),({\mathcal{F}}_n),\lambda )$, with its half-open dyadic intervals. Complete the initial definition by putting $X_0=\mu ([0,1))$. This is the same cell-average formula at level zero, where the only cell is $[0,1)$.

The function $X_n$ is ${\mathcal{F}}_n$-measurable and nonnegative. Its expectation isEvery parent cell is the disjoint union of its two half-open child cells. On $D_k^n$, the conditional expectation of $X_{n+1}$ is its cell average:Thus $\mathbb{E}[X_{n+1}\mid {\mathcal{F}}_n]=X_n$, including at $n=0$. This proves that $X$ is a nonnegative martingale, specifically the dyadic density martingale. The half-open endpoints are essential to the disjoint partition for an arbitrary measure, which may have atoms.

Write $\eta (A)={\int }_A{X}_{\infty }d\lambda$. This is a finite positive measure. For $A\in {\mathcal{F}}_n$, the conditional expectation inequality givesThe union $\mathcal{A}={\bigcup }_n{\mathcal{F}}_n$ is an algebra of sets generating $\mathcal{B}([0,1))$, since half-open dyadic intervals generate all open sets and hence all Borel sets. The class $\{A:\eta (A)\le \mu (A)\}$ is closed under increasing and decreasing limits, by continuity of these finite measures. The Monotone class theorem extends the inequality from $\mathcal{A}$ to every Borel set. Approximation by nonnegative simple functions and monotone convergence then giveThe difference $\nu =\mu -\eta$ is therefore a finite nonnegative measure, not merely a signed measure. For $A\in {\mathcal{F}}_n$,Consequently its restricted Radon-Nikodym derivative isChoose the cell-average versions of all the conditional expectations. Then $Y_n$ is constant on each level-$n$ cell and equals $2^n\nu (D_k^n)$ there, so these versions are nonnegative at every point.

Values at the endpoint one do not affect any of the conclusions, since $\mathbb{P}(U=1)=0$. Set $b_n(1)=1$ to define each random variable everywhere, and choose a Borel measurable function agreeing with $f$ almost everywhere if necessary. These choices leave all integrals and almost-sure assertions unchanged.

Every dyadic interval at level $n+1$ lies in a dyadic interval at level $n$. Equivalently, $b_n(U)$ is a measurable function of $b_{n+1}(U)$, so ${\mathcal{F}}_n\subseteq {\mathcal{F}}_{n+1}$: these sigma-algebras form a filtration. Since the uniform distribution of $U$ gives $\mathbb{E}|f(U)|={\int }_0^1|f(u)|du<\infty$, the conditional expectations $X_n=\mathbb{E}[f(U)\mid {\mathcal{F}}_n]$ are integrable and adapted. The tower property of conditional expectation givesThus $(X_n)$ is a martingale, and part (a) proves that it is uniformly integrable.

For $I_{n,k}=[k{2}^{-n},(k+1)2^{-n})$, the event $\{U\in I_{n,k}\}$ is an atom of a sigma-algebra ${\mathcal{F}}_n$, with probability $2^{-n}$. The value of the conditional expectation there is thereforeConsequently $\boxed{X_n=f_n(U)\text{ almost surely}.}$ This also shows directly that ${\int }_0^1|f_n|\le {\int }_0^1|f|$.

By the uniformly integrable martingale convergence theorem, there is an integrable $Y$ such that $X_n\to Y$ almost surely and in the L1 norm. To identify this limit, put ${\mathcal{F}}_{\infty }=\sigma ({\bigcup }_n{\mathcal{F}}_n)$. Since $0\le U-b_n(U)<2^{-n}$ away from the harmless endpoint, $U={\lim }_n{b}_n(U)$, and $U$ is ${\mathcal{F}}_{\infty }$-measurable. Conversely every $b_n(U)$ is a measurable function of $U$. Thus ${\mathcal{F}}_{\infty }=\sigma (U)$, and both $Y$ and $f(U)$ have ${\mathcal{F}}_{\infty }$-measurable versions.

For $A\in {\mathcal{F}}_m$, the defining property of conditional expectation gives $\mathbb{E}[X_n{1}_A]=\mathbb{E}[f(U)1_A]$ whenever $n\ge m$. Passing to the limit in the L1 norm yieldsThe increasing union ${\bigcup }_m{\mathcal{F}}_m$ is an algebra of sets generating ${\mathcal{F}}_{\infty }$. The class of events for which this integral identity holds is a Dynkin system, so the pi-lambda theorem extends the identity to every $A\in {\mathcal{F}}_{\infty }$. Since both random variables are measurable there, uniqueness of conditional expectation gives $Y=f(U)$ almost surely. We have proved that the dyadic conditional averages recover integrable functions:because a probability-one assertion for $U$ is a full-Lebesgue measure assertion for $x$. Likewise, the uniform distribution of $U$ turns convergence in L1 intoNo pointwise continuity of $f$ is required.

For $1\le j\le n$, repeated use of the floor function identity givesThus the filtration satisfies ${\mathcal{F}}_n=\sigma (X_n)$. Each positive-probability atom of a sigma-algebra here has the formwith probability $2^{-n}$; $\{X=1\}$ is a possible additional null set atom. Averaging over each dyadic interval gives a versionFor a globally defined version of the right side, assign any value, for example zero, on $\{X=1\}$.

Indeed, the displayed random variable is ${\mathcal{F}}_n$-measurable and bounded by $\sup |h|$. On each $A_{n,k}$ its integral isby the uniform distribution. Every member of ${\mathcal{F}}_n$ is a union of the displayed sets and the possible zero-probability atom. Summing these identities therefore verifies the defining conditional expectation property on all of ${\mathcal{F}}_n$.

Each $Z_n$ is a bounded Borel measurable function of $X_n$, including the specified value at $X_n=1$. Therefore $(Z_n)$ is an adapted process for $({\mathcal{F}}_n)$ and consists of integrable random variables.

Fix an atom of a sigma-algebra in ${\mathcal{F}}_n$ with positive probability, corresponding to the dyadic interval $[u,u+\delta )$, with $\delta =2^{-n}$. By the uniform distribution, each half has conditional probability $1/2$. The conditional expectation of $Z_{n+1}$ on that atom is thereforeThe middle values cancel. On the zero-probability atom the conditional expectation can be chosen as zero, agreeing with our version of $Z_n$. Henceso $(Z_n)$ is a martingale. This is the dyadic slope martingale associated with the Lipschitz function $f$.