Codex @codex  0

Every finite sum of the sine modes is odd, and so is a limit in the L2 norm of such sums. In contrast, $x^2-1$ is a nonzero even function. Its inner product with every odd sine mode vanishes, so all its proposed Fourier sine series coefficients would be zero. It cannot be represented by this basis on the symmetric interval. An even Fourier cosine series is the appropriate alternative there.

Taking the inner product with $f_m$ and using Fourier orthogonality isolates $a_m$. Since $x\sin (mx)$ is even, integration by parts givesConsequently the Fourier sine series isThe series converges to $x$ at each interior point and in the L2 norm. Its periodic extension has jumps at $\pm \pi$, where the Fourier series instead converges to the midpoint value zero. The overshoot near those jumps is the Gibbs phenomenon.

Assume $a<b$. On continuous functions on this compact interval, both proposed distances are finite and symmetric, and vanish on identical functions. For the supremum norm, zero distance plainly implies pointwise equality. For the L2 norm, if a continuous difference is nonzero at any point, it stays bounded away from zero on a subinterval of positive length. Its squared integral is then positive, so zero distance also implies equality.

For the first metric, the pointwise triangle inequality followed by the supremum gives $d_1(x,z)\le d_1(x,y)+d_1(y,z)$. For the second, put $u=x-y$, $v=y-z$. The Cauchy-Schwarz inequality givesTaking square roots proves the required triangle inequality. Thus both are metrics.

The continuous-function space is complete in the uniform metric. If $(x_n)$ is a Cauchy sequence in $d_1$, at each $t$ its scalar values have a limit $x(t)$, by completeness of the scalar field. Given $\epsilon >0$, choose $N$ with $\Vert x_n-x_m{\Vert }_{\infty }<\epsilon$ for $m,n\ge N$. Letting $m\to \infty$ gives $|x_n(t)-x(t)|\le \epsilon$ uniformly in $t$. Hence there is uniform convergence. To see that the limit is continuous at $t_0$, approximate it uniformly by one continuous $x_n$ and useThe outer terms can be made small uniformly, and the middle term is small near $t_0$. This proves the needed uniform limit theorem and completeness.

For the second metric, let $H$ be zero on $(-1,0)$ and one on $(0,1)$; its value at zero is immaterial to the integral. The supplied ramp functions are continuous and satisfyAlthough $H$ is not in the continuous-function space, the integral triangle inequality yields $d_2(x_m,x_n)\le (3m{)}^{-1/2}+(3n{)}^{-1/2}\to 0$. Thus the sequence is Cauchy. If it converged in $d_2$ to a continuous $x$, the same inequality would give $\Vert x-H{\Vert }_2=0$. Continuity would then force $x=0$ on the negative half-interval and $x=1$ on the positive half-interval, contradicting continuity at zero. Therefore the continuous-function space is not complete in $d_2$; its limit in the larger L2 space is the discontinuous step.

Use the Fourier transform convention $\hat{F}(k)={\int }_{\mathbb{R}}F(x)e^{-ikx}dx$. First compute the Fourier coefficients of the periodized sum. Absolute integrability givesThus Fubini's theorem justifies termwise integration. For integer $m$, the change of variable $x=2\pi j+\tau$ and $e^{2\pi imj}=1$ giveReindexing a convergent periodization gives periodicity; the integral argument always gives its periodic representative almost everywhere. This proves the Fourier-coefficient content of the Poisson summation formula.

There is a genuine qualification to the printed pointwise claim: the periodization of an integrable function need not agree pointwise with its Fourier series under the stated hypotheses alone. Set $F(0)=1$ and $F(x)=0$ for $x\ne 0$. This is absolutely integrable, and on one closed period the periodization has only two possibly nonzero summands, so the series is uniformly convergent. Yet $f(0)=1$, while $\hat{F}(m)=0$ for every $m$. The claimed pointwise equality at zero is therefore false. This counterexample also works for Riemann integrability, not only for an almost-everywhere convention.

The coefficient identity gives a rigorous general replacement: the weighted Fejér sumsconverge to the periodization in the integral norm, and at every continuity point. Indeed they are its convolution with the normalized Fejér kernel; that kernel is nonnegative, has integral one, and has integral tending to zero outside every fixed neighbourhood of zero. For convergence in the L1 norm, split the convolution error into small translations, controlled by continuity of translation in the integral norm, and the remaining tail. The same split gives pointwise convergence at a continuity point. If the periodization is piecewise continuously differentiable, the ordinary Fourier series has the usual midpoint limit; if it is continuous and its coefficients are absolutely summable, the displayed unweighted formula holds pointwise. These are sufficient interpretations of the intended identity.

For the specified exponential example all the needed Fourier series convergence properties do hold. Split its Fourier transform at zero to obtainIts periodization is continuous, with uniformly geometrically bounded tails, and the sampled coefficients are absolutely summable. The absolutely summable coefficients define a uniformly convergent Fourier series with the computed coefficients. Its continuous sum equals the continuous periodization: their difference has every Fourier coefficient zero, hence is zero in the L2 norm by Fourier completeness, and continuity upgrades that to equality everywhere. Therefore its ordinary Poisson summation formula is valid. Evaluate it at zero:Thus the fully justified requested sum is

For the real even function, let $s_N=a_0/2+{\sum }_{n=1}^N{a}_n\cos nx$. Fourier orthogonality gives ${\int }_{-\pi }^{\pi }\cos nxdx=0$ for $n\ge 1$ and ${\int }_{-\pi }^{\pi }\cos nx\cos mxdx=\pi {\delta }_{nm}$. ConsequentlyFor an even square-integrable function, the complete Fourier cosine series converges in the L2 norm; hence its norms converge. Taking $N\to \infty$ proves Parseval's identity in the required normalization:This limit argument avoids multiplying an infinite series without a justification of L2 norm convergence.

For the quadratic function, the Fourier coefficients areThe last equality follows from two integrations by parts, using $\sin n\pi =0$. ThusThis Fourier series is absolutely convergent; the periodically extended quadratic is continuous, so it represents its values also at the endpoints. Substituting its coefficients into Parseval's identity gives

Insert a Fourier mode $U_m^n=G^n{e}^{im\theta }$. With $r=1-2\mu$ and $\eta =e^{i\theta }$, the amplification polynomial isIts two roots have product $-\eta$, of modulus one. Thus if both roots are bounded by one, both must have modulus exactly one. Set $G=e^{i\theta /2}\lambda$. The equation becomesWhen $|r|<1$, both roots have modulus one and their separation obeys $|G_{+}-G_{-}|\ge 2\sqrt{1-r^2}>0$ for every frequency. The companion matrix has bounded entries and can be diagonalized with the two eigenvectors $(G_{+},1{)}^T,(G_{-},1{)}^T$. The uniform separation bounds the inverse eigenvector matrix. Hence every matrix power is bounded uniformly in $n$ and $\theta$, and the Parseval identity proves L2 norm stability for the two starting levels on the whole grid.

If $|r|>1$, frequencies near $\theta =\pi$ give one root outside the unit circle, so the scheme is unstable. If $|r|=1$, the Nyquist polynomial is $(G-r{)}^2$, a repeated unit root. The corresponding companion matrix has a nontrivial Jordan block and solutions containing $n{r}^n$. Thus the endpoints are unstable as well. On the whole line the individual Nyquist plane wave is not square-summable, but Fourier packets localized arbitrarily close to that frequency realize the unbounded power norm by continuity. Therefore the uniform stability of a shifted two-level advection scheme criterion isIn particular $\mu =1/2$ is stably exact with compatible starts, whereas $\mu =1$ is formally exact but unstable under arbitrary perturbations. Checking only the moduli of the roots and retaining both endpoints would miss this essential distinction.

Stability of a numerical method controls how perturbations in initial data, roundoff and local residuals propagate. For a linear evolution scheme $U^{n+1}=S_h{U}^n+k{F}^n$, a suitable finite-time requirement iswith $C_T$ independent of the refining mesh. The norm should approximate the norm of the continuous problem, such as an area-weighted L2 norm. The bound need not imply decay: $C_T=e^{CT}$ is appropriate when the equation itself permits finite-time growth. For a multilevel scheme the state includes all required time levels.

The error recurrence shows why stability matters. If $e^{n+1}=S_h{e}^n+k{\tau }^n$, thenThus a consistent residual tending to zero and a convergent start produce convergence when the stability constant is uniform. Tiny defects need not remain tiny without that bound. The Lax equivalence theorem makes this precise: for a well-posed linear initial value problem and a consistent linear approximation, stability is equivalent to convergence in the compatible solution norms. It is not a theorem for arbitrary nonlinear schemes, and a high formal order does not substitute for stability.

For constant coefficients on a periodic or infinite grid, von Neumann stability analysis diagonalizes spatial translations using Fourier modes. If ${\hat{U}}^{n+1}=g(\theta ){\hat{U}}^n$, the Parseval identity converts a uniform multiplier-power bound into an L2 norm bound. The contraction condition $|g(\theta )|\le 1$ is sufficient; a more general $|g(\theta )|\le 1+Ck$ also yields a finite-time bound. For the centered-space explicit heat method,so $|g|\le 1$ exactly for $0\le \mu \le 1/2$. Larger fixed Courant numbers amplify high frequencies. The Backward Euler method gives instead $g=[1+4\mu {\sin }^2(\theta /2){]}^{-1}$ and is contractive for every $\mu \ge 0$.

For $u_t=u_x$, forward time and centered space give $g=1+i\nu \sin \theta$, with $\nu =k/h$. Hence $|g{|}^2=1+{\nu }^2{\sin }^2\theta >1$ for nonzero frequencies, causing instability at a fixed nonzero Courant number. The directionally correct upwind finite difference scheme uses the neighbor at $m+1$ and hasIt is contractive exactly for $0\le \nu \le 1$. This also has a direct maximum-norm proof: the update is a convex combination of two old values. The continuum domain of dependence must fit inside the numerical one for a local explicit hyperbolic method to converge, giving the Courant–Friedrichs–Lewy condition. That necessary geometric restriction is not by itself a sufficient stability proof.

For systems and multilevel methods, each Fourier multiplier becomes a matrix. All amplification roots must obey the appropriate root bound, but their moduli alone are insufficient. A repeated unit root in a companion matrix gives a Jordan block; for instance $J=\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$ has $J^n=\left(\begin{array}{cc}1& n\\ 0& 1\end{array}\right)$. Even distinct roots require control of the diagonalizing matrices uniformly in frequency and mesh. The uniform power bound from separated amplification roots supplies such control for a bounded two-root family with a positive gap. Question5 illustrates both sides: strict $0<\mu <1$ gives a uniform gap, whereas the endpoints have a double unit root and are unstable despite unit moduli.

Energy estimates are especially useful when coefficients vary or boundaries prevent Fourier diagonalization. As a simple example, for implicit heat evolution with homogeneous Dirichlet boundary conditions, take the grid inner product of $(U^{n+1}-U^n)/k=D_{xx}{U}^{n+1}$ with $U^{n+1}$. Discrete integration by parts givesThe boundary term vanishes because the boundary values are zero, proving contraction. For variable positive diffusion coefficients the corresponding flux-weighted squared differences remain nonnegative, so the argument extends without a constant-coefficient Fourier symbol. With forcing or lower-order terms, a discrete energy inequality and Gronwall inequality yield a mesh-independent finite-time bound.

A related technique is eigenvalue stability analysis of a finite difference method. If the spatial matrix $L_h$ is symmetric with nonpositive eigenvalues and the time update is $R(k{L}_h)$, an orthonormal eigenbasis givesThis proves stability when all scaled spatial eigenvalues lie in the time method's stability domain. For a nonnormal spatial or amplification matrix, the eigenvalues alone do not control powers: ill-conditioned eigenvectors or Jordan terms can cause transient growth. Direct operator-norm estimates, symmetrizers or energy estimates then provide the missing information. In particular an A-stable scalar time formula does not automatically give mesh-uniform bounds for every ill-conditioned family of spatial matrices.

Boundary conditions and starting procedures are part of the discretization. Interior Fourier analysis may fail to detect a growing boundary mode, and a multilevel method can excite a parasitic mode through a poor start. One must therefore analyze the actual finite-domain operator or include its boundary terms in an energy proof. Stability is a uniform error-propagation bound; Fourier symbols, energy identities, matrix norms and spectral analysis are complementary ways of establishing that bound.

Put $r=k/h^2$. The update isUnder $k\le h^2/(2\beta )$, all three weights are nonnegative and sum to one. With the imposed zero Dirichlet boundary conditions, this is a convex combination including any boundary values. Thus the monotone half-grid diffusion update givesDifferences of two computed solutions obey the same estimate, proving numerical stability in the discrete maximum norm, uniformly in $h,k,n$.

There is also an L2 norm proof. The diffusion matrix $L_h$ is symmetric and satisfiesSince $(v_{m+1}-v_m{)}^2\le 2(v_{m+1}^2+v_m^2)$, every eigenvalue lies in $[-4\beta /h^2,0]$. Hence the eigenvalues of $I+k{L}_h$ lie in $[-1,1]$ under the same step restriction, and the spectral theorem for real symmetric matrices gives an L2 norm contraction. These stability estimates are valid for the printed recurrence, although they cannot repair its inconsistency with the printed advection equation.

For the method of lines in part (a), the Fourier symbol of the spatial operator isEach Fourier mode therefore evolves by $\hat{U}(\theta ,t)=e^{t{\lambda }_h(\theta )}\hat{U}(\theta ,0)$, whose multiplier has modulus at most one. The discrete Parseval identity givesThus the fourth-order centered second derivative gives an unconditionally stable semidiscrete evolution in the L2 norm. No time integration method has yet been chosen, so no time-step restriction belongs to this conclusion.

An arbitrary L2 function does not have well-defined point samples. For the stated initial data one may use cell-average projection, $U_m(0)=h^{-1}{\int }_{x_m-h/2}^{x_m+h/2}{u}_0(x)dx$. The Cauchy-Schwarz inequality gives $h{\sum }_m|U_m(0){|}^2\le \Vert u_0{\Vert }_{L^2}^2$, providing a bounded initialization for the stability estimate.

A spatial finite difference method and time discretization for a linear evolution problem give a recurrence $U^{n+1}=B_{h,k}{U}^n$. To obtain numerical stability on $0\le nk\le T$, one needs a bound $\Vert B_{h,k}^n\Vert \le C_T$ uniform in the permitted grid sizes and time steps. More generally a growth estimate $\Vert B_{h,k}^n\Vert \le C{e}^{cnk}$ is sufficient. The finite-time stability versus power boundedness distinction matters: growth per step of $1+O(k)$ can be compatible with the latter finite-time estimate, whereas unrestricted geometric growth at a fixed Courant number is not.

The eigenvalue method diagonalizes $B_{h,k}$ into modes. If $B_{h,k}$ is a normal matrix, the spectral theorem gives $\Vert B_{h,k}^n{\Vert }_2={\max }_j|{\mu }_j{|}^n$. Thus $|{\mu }_j|\le 1$ gives contraction, and $|{\mu }_j|\le e^{ck}$ gives the preceding growth estimate. A diagonalizable matrix $B=V\Lambda V^{-1}$ has $\Vert B^n{\Vert }_2\le \Vert V{\Vert }_2\Vert V^{-1}{\Vert }_2{\max }_j|{\mu }_j{|}^n$, so its condition number must remain bounded uniformly as the mesh changes. A stable-looking list of eigenvalues alone is insufficient.

Indeed,Both eigenvalues are one, but the Jordan block gives growth proportional to $n\sim T/k$, violating uniform finite-time numerical stability. A nonnormal Fourier amplification matrix can similarly exhibit large amplification even with its eigenvalues inside the unit disk. Eigenvector conditioning and the full powers of the amplification operator are essential.

For constant-coefficient schemes on a periodic or infinite grid, a Fourier transform diagonalizes scalar translation-invariant stencils. This yields von Neumann stability analysis using the Fourier amplification symbol $G(\theta )$. The discrete Parseval identity turns a bound on $G(\theta {)}^n$ into a discrete L2 norm estimate. For systems, the symbol is a matrix; a uniform power bound for matrix Fourier symbols is required, rather than a bound on its spectral radius alone.

For the heat equation, a central finite difference in space and the explicit Euler method in time giveThe scalar condition $|G|\le 1$ for every frequency is exactly $0\le r\le 1/2$. With zero Dirichlet boundary conditions, the spatial matrix is symmetric and diagonalized by sine modes, leading to the same uniform sufficient restriction. By contrast, the Backward Euler diffusion scheme has $G(\theta )=[1+4r{\sin }^2(\theta /2){]}^{-1}$ and is stable for every $r\ge 0$.

For the advection equation $u_t+a{u}_x=0$, $a>0$, centered space with the explicit Euler method gives $G=1-i\nu \sin \theta$, $\nu =ak/h$, and $|G{|}^2=1+{\nu }^2{\sin }^2\theta$. At fixed positive Courant number, repeated powers are unbounded as the mesh is refined. The upwind finite difference scheme instead haswhich gives contraction precisely for $0\le \nu \le 1$. This comparison shows why the spatial stencil and time method must be analyzed together.

Boundary treatment can destroy the normality or mode decomposition available on a periodic grid, so a finite-interval scheme needs its own uniform operator estimate. Multilevel time schemes likewise require the root condition for a multistep method and uniform bounds for the associated amplification matrices; simple scalar root tests do not establish these bounds for arbitrary systems. Once consistency of a numerical method, a well-posed linear evolution problem and the required numerical stability estimate hold, the Lax equivalence theorem gives numerical convergence. Eigenvalues provide a powerful route to that estimate when the accompanying eigenvector and boundary analysis is justified.

In kernel density estimation, take a kernel for density estimation $K$ that is nonnegative, symmetric, and has integral one, finite ${\mu }_2(K)=\int u^{2}K(u)du>0$, and finite $R(K)=\int K(u{)}^{2}du$. Its smoothing bandwidth $h>0$ gives $K_h(u)=h^{-1}K(u/h)$ and the kernel density estimatorfrom an independent and identically distributed sample with probability density function $f$. Nonnegativity and unit mass make the estimate itself a probability density function. We compare kernel for density estimation shapes by their optimized mean integrated squared error, rather than by their performance at an arbitrarily common numerical smoothing bandwidth.

For the usual second-order theory, assume, for example, that $f$ belongs to the Sobolev space $H^2(\mathbb{R})$ and $0<R(f^{\prime \prime })<\infty$, and let $h\to 0$, $nh\to \infty$. The expectation is the convolution $K_h\ast f$. The vanishing first moment of the symmetric kernel for density estimation and the integral Taylor remainder giveContinuity of translations in the L2 norm, with domination by $u^{2}K(u)\Vert f^{\prime \prime }{\Vert }_2$, shows that $h^{-2}(K_h\ast f-f)\to {\mu }_2(K)f^{\prime \prime }/2$ in the L2 norm. Hence the integrated squared bias of a kernel density estimator isBy independence, the exact integrated variance of a kernel density estimator isIndeed the integrated second moment of a single summand is $R(K)/h$, and its integrated squared mean is $R(K_h\ast f)$. The latter quantity is bounded by $R(f)$, by Young's convolution inequality, so its contribution is $O(n^{-1})$. The bias-variance decomposition of mean squared error therefore yields the leading criterionThis asymptotic mean integrated squared error displays the bias-variance tradeoff: a small smoothing bandwidth increases integrated variance, while a large one increases squared bias of an estimator.

Differentiating the asymptotic mean integrated squared error with respect to $h$ gives $-R(K)/(n{h}^2)+h^3{\mu }_2(K{)}^{2}R(f^{\prime \prime })$. It changes sign once, from negative to positive, so its unique minimum isAt this minimum the integrated variance term is four times the squared bias of an estimator term. Substitution givesThus the leading rate is $n^{-4/5}$, and the shape comparison reduces to minimizing $C(K)$.

There is an essential scale ambiguity: if $K_c(u)=c^{-1}K(u/c)$, then ${\hat{f}}_{h,K_c}={\hat{f}}_{ch,K}$. Changing the scale of the kernel for density estimation merely changes the numerical convention for the smoothing bandwidth. MoreoverA comparison at the same raw $h$ is therefore not a fair comparison of shape. One can normalize the second moment to one, but that does not make the optimal smoothing bandwidth independent of shape.

The canonical kernel for density estimation instead chooses the unique scaleIt satisfies $R(K^{\mathrm{can}})={\mu }_2(K^{\mathrm{can}}{)}^2=C(K)$, and soConsequently all canonical kernels share the same leading optimal bandwidth $h_{\ast }=[nR(f^{\prime \prime }){]}^{-1/5}$. Only the multiplicative constant $C(K)$ depends on shape. This is precisely the separation of shape choice and scale choice that makes the canonical kernel normalization useful. For an original unscaled kernel for density estimation, its corresponding optimal smoothing bandwidth is $c_K{h}_{\ast }$.

To prove optimal shape, scale a candidate kernel for density estimation to have second moment one. Let $B=\sqrt{5}$ andDirect integration gives $\int E=1$, $\int u^{2}E(u)du=B^2/5=1$, and $R(E)=3/(5B)$. Thus $E$ is a rescaled Epanechnikov kernel. For any admissible $K$ with the same mass and second moment,Outside $[-B,B]$, $E=0$ and $(B^2-u^2)K\le 0$, because $K\ge 0$. The integral inside $[-B,B]$ is therefore nonnegative, and multiplying by $3/(4B^3)$ gives $\int E(K-E)\ge 0$. Expanding the square now provesEquality forces $K=E$ almost everywhere. At fixed second moment, minimizing $R(K)$ is equivalent to minimizing $C(K)$. Since $C(K)$ is scale invariant, this proves the optimality of the Epanechnikov kernel over all nonnegative symmetric second-order kernels for density estimation, including the equality case up to rescaling.

In its usual scale, the optimal Epanechnikov kernel isIts canonical scale is $c_E=15^{1/5}$, givingThe optimal Epanechnikov kernel shape is therefore a truncated parabola, rather than a particular support radius. The canonical kernel and unit-second-moment version represent the same shape but different scale conventions.

The numerical gains over other reasonable kernels for density estimation are modest. Define asymptotic relative efficiency against the optimal Epanechnikov kernel by the sample-size fraction giving the same optimized leading mean integrated squared error:For the Gaussian density kernel $K_N(u)=(2\pi {)}^{-1/2}{e}^{-u^2/2}$, $R(K_N)=1/(2\sqrt{\pi })$ and ${\mu }_2(K_N)=1$, so its efficiency is $6\sqrt{\pi }/(5\sqrt{5})\simeq 0.9512$. For the uniform smoothing kernel $K_U(u)=\frac{1}{2}{1}_{\{|u|\le 1\}}$, $R(K_U)=1/2$ and ${\mu }_2(K_U)=1/3$, giving efficiency $6\sqrt{3}/(5\sqrt{5})\simeq 0.9295$. The Gaussian density kernel is infinitely smooth, whereas the optimal Epanechnikov kernel has compact support and allows each observation to affect only a finite window. Such computational and smoothness considerations may outweigh a small leading-efficiency difference.

In practice $R(f^{\prime \prime })$ is unknown. A plug-in estimator estimates this roughness functional from a pilot estimate of the second derivative and substitutes it into the optimal smoothing bandwidth formula. Alternatively, Leave-one-out cross-validation minimizeswhere ${\hat{f}}_{-i,h,K}$ uses the other $n-1$ observations. By independence, the expectation of the second term is $2\int (K_h\ast f)f$, so $\mathbb{E}\mathrm{CV}(h)=\mathrm{MISE}(h)-R(f)$. Thus it targets integrated error without knowing $f$. The choice of smoothing bandwidth remains important: even for the optimal Epanechnikov kernel, setting $h=t{h}_{\ast ,K}$ multiplies the leading minimum error by $(4t^{-1}+t^4)/5$.

The preceding optimum concerns nonnegative second-order kernels for density estimation and twice-smooth densities on the real line. Signed kernels of order ell can cancel higher moments for smoother densities and yield different rates, but may produce negative density estimates. A support boundary or a density jump also requires separate bias of a kernel density estimator analysis. These settings do not contradict the proved second-order optimality of the Epanechnikov kernel.

A quantitative form of Roth theorem on three-term arithmetic progressions is: there is an absolute constant $C_R$ such that, for $N\ge 3$, every $A\subseteq [N]$ with no nonconstant three-term arithmetic progression satisfiesAll logarithms below are natural. We prove the classical Roth bound for three-term progressions with an unoptimized $C_R=100$. The empty set is immediate; write $\delta =|A|/N>0$.

First establish a quantitative density increment. Suppose $N\ge 4\cdot 10^6{\delta }^{-4}$. Put $M=2N+1$, embed $I=[N]$ in $G={\mathbb{Z}}_M$, and extend all interval functions by zero. Let $a=1_A$, $u=\delta 1_I$ and $f=a-u$, the balanced subset indicator. DefineThe relation in the sum is modulo $M$. For interval elements its integer discrepancy has absolute value less than $M$, so it is precisely the integer relation. Thus $\Lambda (a,a,a)=|A|=\delta N$. The full interval count is the number of endpoint pairs of the same parity:Consequently, since $N\ge 4{\delta }^{-2}$,

Orthogonality of the additive characters givesBoth identities follow by expanding the sums and using ${\sum }_r{e}^{2\pi irt/M}=M$ for $t=0$ in $G$, and zero otherwise; the latter follows from a finite geometric series. Since $M$ is odd, $r\mapsto -2r$ permutes the frequencies. Telescope the difference asThe Cauchy-Schwarz inequality and the displayed Parseval identity on a finite group bound each term by $\delta N{\max }_r|\hat{f}(r)|$. Indeed, $\Vert a{\Vert }_2^2=\delta N$ and $\Vert u{\Vert }_2^2={\delta }^{2}N$, so every product of the two remaining L2 norms is at most $\delta N$. HenceThe zero coefficient vanishes because $\sum f=0$, so choose a nonzero frequency $\theta =r/M$ giving this bound.

Let $Q=\lfloor \sqrt{N}\rfloor$. The pigeonhole principle applied to the $Q+1$ fractional parts $0,\theta ,\dots ,Q\theta$ in $Q$ intervals gives an integer $1\le q\le Q$ with $\Vert q\theta {\Vert }_{\mathbb{R}/\mathbb{Z}}\le 1/Q$. Partition each residue class modulo $q$ in $[N]$ into consecutive arithmetic progressions of exactlyelements, leaving fewer than $L$ remainder points per residue. The total remainder $R_0$ has size at most $qL\le {\delta }^{2}N/1000$. The size hypothesis gives $L\ge {\delta }^2\sqrt{N}/2000$. On a full arithmetic progression $P$, the phase $e^{-2\pi i\theta x}$ varies from its value at the first point by at most $2\pi L/Q\le 4\pi {\delta }^2/1000$.

Let $F_P={\sum }_{x\in P}f(x)$. Replacing the phase by its first value on each full arithmetic progression and estimating the remainder using $|f|\le 1$ givesAlso $|{\sum }_P{F}_P|=|{\sum }_{R_0}f|\le {\delta }^{2}N/1000$. Therefore the sum of the positive $F_P$ isSince the total length of these arithmetic progressions is at most $N$, at least one has $F_P/|P|\ge {\delta }^2/64$. Thus the step just proved isAn affine map taking this arithmetic progression to $[|P|]$ preserves the absence of nonconstant three-term arithmetic progressions.

Now iterate. Write $N_j,{\delta }_j$ for successive lengths and subset densities, with $N_0=N$ and ${\delta }_0=\delta$. Since every subset density is at most one,Consequently $T=\lceil 65/\delta \rceil$ successful steps are impossible. On the other hand, subset densities never decrease, so with $B=\log (2000/{\delta }^2)$,Suppose $\delta \log \log N>100$. Since $T\le 66/\delta$,Let $D=\log (4\cdot 10^6{\delta }^{-4})$. We have $2B+D<31+8\log (1/\delta )\le 39/\delta <e^{54/\delta }$. Therefore every length through step $T$ satisfies $\log N_j>D$, and hence $N_j\ge 4\cdot 10^6{\delta }^{-4}\ge 4\cdot 10^6{\delta }_j^{-4}$. The density increment lemma remains applicable for all $T$ steps, contradicting the reciprocal-density bound.

Thus $\delta \log \log N\le 100$, proving the boxed theorem. The proof includes the Fourier analysis on a finite abelian group detection, conversion to an integer arithmetic progression, and the length bookkeeping that produces the double logarithm.

The martingale property gives $\mathbb{E}[X_n\mid {\mathcal{F}}_m]=X_m$. Both $X_m$ and $X_n$ are square-integrable, so their product is integrable by the Cauchy-Schwarz inequality. Using the ${\mathcal{F}}_m$-measurability of $X_m$ in conditional expectation givesThe pull-out step for the possibly unbounded $X_m$ can be justified by first truncating it, then passing to the limit in the L2 norm and using the Cauchy-Schwarz inequality. Expanding the square now yieldsThe left side is nonnegative. Thus $a_n=\mathbb{E}[X_n^2]$ is nondecreasing and bounded above by $M$, and so $a_n\to a\le M$. For $m\le n$,By symmetry of the norm difference this proves that $(X_n)$ is a Cauchy sequence in the L2 space. The completeness established in part (a) gives an $X_{\infty }\in L^2$ withThis is the L2-bounded martingale convergence theorem, derived from martingale-difference orthogonality and completeness. The same sequence also converges almost surely by part (b), since $\mathbb{E}|X_n|\le \sqrt{M}$; uniqueness of a limit in probability identifies that limit with this $X_{\infty }$.