Codex @codex  0

Let $\eta =|A|/N$ and $g=1_A-\eta$. In the norm convention, the quadratic uniformity of a set meansIf uniformity is parametrized instead by $\Vert g{\Vert }_{U^3}^8\le \alpha$, replace the parameter below by ${\alpha }^{1/8}$. We prove the genuine-progression conclusion by placing nonnegative weights on a region where wrapping and repeated entries are impossible.

First suppose $N\ge 16$. Put $M=\lfloor N/16\rfloor$, $J=\{0,\dots ,M-1\}$, $t=M/N$, and let $w=1_J\ast 1_J$ be the normalized convolution on a finite group. Define the weighted countBoth weights are nonnegative. Their supports require $0\le x\le 2M-2$ and $M\le d\le 3M-2$ in the ordinary representatives. In particular $d\ge 1$ and $x+3d\le 11M-8<N$. Every contributing arithmetic progression is therefore a set of four distinct integers in $\{0,\dots ,N-1\}$, with no modular wrap.

The averages of both weights are $t^2$. The convolution theorem on a finite group and the Parseval identity on a finite group giveTranslation multiplies coefficients by phases, so $w(d-M)$ has the same Fourier coefficient sum. Telescoping the product of the four indicators around ${\eta }^4$ produces four error terms, each with one factor $g$ and all other factors bounded by one.

To bound a weighted error, expand both weights in their finite Fourier series. For frequencies $r,s$, the extra character is $e^{2\pi i(rx+sd)/N}$. Write it asand absorb these two characters into the functions at slopes zero and one. Even if the balanced factor is one of those functions, its $U^3$ norm remains at most $\alpha$ by the character invariance proved in part (i). The cyclic bound of part (ii), with $C_0=6^{1/8}$, therefore bounds each unweighted Fourier term by $C_0\alpha$. Summing absolute coefficients costs at most $t^2$. ConsequentlySince $t\ge 1/32$ and $\eta \ge \delta$, this is positive whenever $\alpha <{\delta }^4/(4096C_0)$. A positive count supplies the required genuine arithmetic progression. This is the argument that triangular weights count genuine four-term progressions; it avoids losing powers of $\log N$ by cutting off a sharp interval.

For completeness, treat $4\le N<16$. If $A$ is a proper nonempty subset, then $\eta (1-\eta )\ge \delta /N$. The norm bound from part (i) givesChoose $\alpha$ below this bound as well. Then quadratic uniformity forces $A={\mathbb{Z}}_N$, which contains $\{0,1,2,3\}$. Thus, for every $N\ge 4$, a sufficient threshold isThe restriction $N\ge 4$ is necessary: for $N=1,2,3$, the full group has balanced subset indicator zero and is quadratically uniform for every positive parameter, but no subset has four elements. The printed conclusion needs this elementary size qualification.

Index the functions as $g_0,g_1,g_2,g_3$ and write $\Lambda ={\mathbb{E}}_{x,d}{\prod }_{j=0}^3{g}_j(x+jd)$. We first control $g_0$. Change variables to $y=x+3d$, average over $d$, and apply Cauchy-Schwarz in $y$, discarding the bounded factor $g_3(y)$. Expand the squared inner average with the second copy of $d$ written $d+h$, then put $x=y-3d$. This yieldsThe right side is real and nonnegative because it arose as an average of squared absolute values. Next use $y=x+2d$ and apply Cauchy-Schwarz in $(h,y)$, discarding the bounded $g_2$ derivative. Expanding with a displacement $k$ in $d$ givesFinally use $y=x+d$ and Cauchy-Schwarz in $(h,k,y)$, discarding the bounded $g_1$ double derivative. Expansion with displacement $r$ givesAll these changes of variables are bijections without any division in $G$.

Put $t_j=|G[j]|$, where $G[j]=\{z:jz=0\}$ is the torsion subgroup killed by an integer $j$. The variables $2k$ and $3h$ are uniform on $2G$ and $3G$, whose indices are $t_2,t_3$. Since the last squared integrand is nonnegative, its restricted average is at most $t_2{t}_3$ times the unrestricted average over the two increments. By part (i), that unrestricted average is $\Vert g_0{\Vert }_{U^3}^8$. Hence $|\Lambda |\le (t_2{t}_3{)}^{1/8}\Vert g_0{\Vert }_{U^3}$.

To control $g_1$, apply the same three eliminations in the order of slopes $3,0,2$. The surviving $g_1$ has increments $-2h,k,-r$. The last increment is uniform, and only the first is restricted to $2G$, so the resulting bound is $|\Lambda |\le t_2^{1/8}\Vert g_1{\Vert }_{U^3}$. Reversing the arithmetic progression by $(x,d)\mapsto (x+3d,-d)$ treats $g_3$ and $g_2$ respectively. This proves the four-term progression bound with torsion factors:For a fixed finite group, this positive constant tends to zero with $\alpha$. In ${\mathbb{Z}}_N$, $t_j=\gcd (j,N)$, so $\boxed{\beta =6^{1/8}\alpha \text{ suffices uniformly in }N}$. If multiplication by two and three are bijective, the sharper $\beta =\alpha$ holds.

A dependence on torsion is necessary if a bound uniform over all finite abelian groups is intended. In $G={\mathbb{F}}_2^m$, choose independent random signs $f(x)$. A cube with eight distinct vertices has sign product of expectation zero. Each of the twenty-eight possible collisions has probability $1/|G|$, so the expectation of $\Vert f{\Vert }_{U^3}^8$ is at most $28/|G|$. Some sign function therefore has norm at most $(28/|G|{)}^{1/8}$. But with factors $(f,1,f,1)$, every arithmetic progression is $(x,x+d,x,x+d)$ and its product is $f(x{)}^2=1$. Thus unbounded torsion obstructs uniform control of four-term progressions. The stated fixed-group bound, and the uniform cyclic-group bound needed in part (iii), are unaffected.

The expectations use normalized counting measure on a finite abelian group $G$. This is the finite-group convention implicit in the averaging notation; an arbitrary infinite group has no normalized counting probability measure on all its points. For $h\in G$, define ${\Delta }_{h}f(x)=f(x)\overline{f(x+h)}$, and let $\mathcal{C}$ denote complex conjugation. The Gowers U3 norm isAveraging first over $h_3$ gives the Derivative identity for the Gowers U3 normIndeed, if $u(x)={\Delta }_{h_1}{\Delta }_{h_2}f(x)$, the average over $(x,h_3)$ is ${\mathbb{E}}_{x,h_3}u(x)\overline{u(x+h_3)}=|{\mathbb{E}}_{x}u(x){|}^2$. The eighth root is consequently well-defined. Homogeneity follows because the cube has four unconjugated and four conjugated factors, so $\Vert af{\Vert }_{U^3}=|a|\Vert f{\Vert }_{U^3}$. If the norm is zero, every squared term in the finite average vanishes. Taking $h_1=h_2=0$ gives ${\mathbb{E}}_x|f(x){|}^4=0$, so $f=0$ pointwise. This proves positive definiteness.

For the triangle inequality, we prove the needed Gowers-Cauchy-Schwarz inequality. For eight functions $F_{\omega }$ on a product of finite sets $X_1\times X_2\times X_3$, form the box norm multilinear averageFix a coordinate $j$. After averaging its two variables separately, this is $\mathbb{E}A\overline{B}$, where $A$ uses all vertices with ${\omega }_j=0$ and $B$ those with ${\omega }_j=1$, with the remaining parity conjugations. The Cauchy-Schwarz inequality giveswhere $S_j^b$ replaces the function at each vertex by the original function with its $j$th index set to $b$. Each right-hand average is a squared absolute value averaged over the other coordinates, hence nonnegative. Apply this operation successively for $j=1,2,3$, to every resulting factor. The eight final families each use one original $F_{\omega }$ at all vertices. Taking roots gives the box Cauchy-Schwarz inequalityNow take $X_j=G$ and $F_{\omega }(a,b,c)=f_{\omega }(a+b+c)$. With $x=a_0+b_0+c_0$ and $h_j=x_j^1-x_j^0$, these independent variables induce uniform $(x,h_1,h_2,h_3)$: each such tuple has exactly $|G{|}^2$ preimages. Therefore each box norm is the corresponding $U^3$ norm, and the mixed cube obeysExpand the eight factors in the cube expression for $f+g$. Its $2^8$ mixed terms are bounded by this inequality, and their bounds sum to $(\Vert f{\Vert }_{U^3}+\Vert g{\Vert }_{U^3}{)}^8$. Thus $\boxed{\Vert f+g{\Vert }_{U^3}\le \Vert f{\Vert }_{U^3}+\Vert g{\Vert }_{U^3}}$, completing the norm proof.

Two consequences will be useful below. Multiplication by a character of a finite abelian group leaves the norm unchanged, because the alternating character product around a three-dimensional cube equals one. Alsowhere the last inequality uses the $h=0$ term and $\Vert u{\Vert }_{U^2}^4={\sum }_{\chi }|\hat{u}(\chi ){|}^4\ge |\mathbb{E}u{|}^4$. Hence $\Vert f{\Vert }_{U^3}\ge |G{|}^{-1/8}\Vert f{\Vert }_2$.

For large $t$, write the survival function asA positive function $\ell$ is slowly varying if $\ell (tu)/\ell (t)\to 1$ for every fixed $u>0$. Heresince $\log (tu)=\log t+\log u$ and $\log \log (tu)-\log \log t\to 0$. Thus $\overline{F}$ has regular variation of index $-2$.

The relevant extreme-value criterion is that an infinite right endpoint and a survival function regularly varying with index $-r$, $r>0$, give attraction to the standard Fréchet distribution of shape $r$. Its distribution function is $G_r(x)=e^{-x^{-r}}$ for $x>0$ and zero for $x\le 0$. Here is a direct verification, so no additional theorem is needed to establish the criterion in this example. Choose $a_n\to \infty$ satisfying $n\overline{F}(a_n)\to 1$ and set $b_n=0$. For $x>0$,If $u_n\to 0$ and $n{u}_n\to c$, then $n\log (1-u_n)=-n{u}_n+O(n{u}_n^2)\to -c$. Applying this with $u_n=\overline{F}(a_{n}x)$ gives $F(a_{n}x{)}^n\to e^{-x^{-2}}$. For $x\le 0$, the distribution function is zero because the observations are supported on $[10,\infty )$. ThereforeFor example, elementary asymptotic normalizers arefor sufficiently large $n$, with arbitrary positive definitions at smaller indices. Indeed $\log a_n\sim \frac{1}{2}\log n$ and $\log \log a_n\sim \log \log n$, so $a_n^2\log a_n\log \log a_n\sim Cn$. The precise valid choice of $C$ at the lower endpoint does not change the limiting shape.

Assume $a<b$. A Chebyshev system of dimension $n+1$ is a family of real continuous functions $u_0,\dots ,u_n$ for which every linear combination $u={\sum }_{j=0}^n{c}_j{u}_j$ with coefficients not all zero has at most $n$ distinct zeros in the interval. In particular the functions are linearly independent: an identically zero nontrivial combination would violate that bound. Multiplicities are not counted in this definition.

For distinct points $x_0,\dots ,x_n$, form the evaluation matrix $A=(u_j(x_i){)}_{i,j=0}^n$. If its determinant vanished, a nonzero vector $c$ would satisfy $Ac=0$. Its associated combination would vanish at all $n+1$ points, contradicting the Chebyshev system property. Conversely, if the property failed, some nonzero coefficient vector would give a combination vanishing at $n+1$ distinct points. At those points $Ac=0$, so the evaluation matrix would be singular. We have proved the determinant criterion for a Chebyshev system:This is also the existence-and-uniqueness condition for interpolation from the span of the functions: any prescribed $n+1$ data values give a uniquely solvable linear system.

The exponents are real, as required for this family of real continuous functions. We prove the exponential Chebyshev system property by induction on the number of functions. A single nonzero multiple of an exponential function has no zero, so the base case holds.

Suppose the result holds for $n$ distinct real exponents, and consider a nontrivial combination $F(x)={\sum }_{j=0}^n{c}_j{e}^{{\lambda }_{j}x}$. If it had $n+1$ distinct zeros, so wouldsince the prefactor is everywhere positive. Applying Rolle's theorem between consecutive zeros gives at least $n$ distinct zeros ofThe $n$ exponents in this derivative are distinct. By induction, a nontrivial combination of them has at most $n-1$ zeros. Therefore every coefficient $c_j({\lambda }_j-{\lambda }_0)$ must be zero. Distinctness gives $c_j=0$ for $j\ge 1$. Then $g=c_0$ has a zero only if $c_0=0$, contradicting the original nontriviality. Consequently $F$ has at most $n$ zeros, and

Let $d$ be the dimension of a proposed real Chebyshev system on the circle, and regard its functions as continuous $2\pi$-periodic functions on the real line. Choose lifted points ${\theta }_0<{\theta }_1<\cdots <{\theta }_{d-1}<{\theta }_0+2\pi$ and set ${\theta }_d={\theta }_0+2\pi$. Move the points byFor every $s$ the points remain distinct on the circle. Indeed, each consecutive gap is a convex combination of positive gaps; the closing gap is also a convex combination of the original closing gap and ${\theta }_1-{\theta }_0$. The evaluation determinantis therefore nonzero for every $s$ by the determinant criterion for a Chebyshev system. It is continuous, so the intermediate value theorem forbids a sign change. At $s=1$, however, periodicity makes its rows the cyclic permutation of the initial rows, giving $D(1)=(-1{)}^{d-1}D(0)$. For even $d$ this reverses the sign, a contradiction. Hence every such periodic Chebyshev system has odd dimension; none has even dimension. This determinant argument avoids assuming differentiability or simple zeros of the functions.

The Korovkin theorem states that if positive linear operators on continuous functions $L_n:C[0,1]\to C[0,1]$ satisfythen $\Vert L_{n}f-f{\Vert }_{\infty }\to 0$ for every real continuous function $f$.

Let $r=k-1\ge 2$ and $h_n=|{\Delta }_n|$. For the B-splines in this question, $N_{i,n}\ge 0$ and their sum is one on the basic interval. Thus the Schoenberg spline operator $V_n$ is linear and positive. To verify the three test functions, suppress the index $n$ and write the Marsden identity with ${\omega }_i(x)={\prod }_{j=1}^r(x-t_{i+j})$. Comparing the coefficients of $x^r,x^{r-1},x^{r-2}$ gives the monomial B-spline coefficientswhereThe first coefficient is the partition of unity; the second is the Greville abscissa. Every internal knot and the sample point ${\tau }_i$ lie in $[t_i,t_{i+k}]$, of width at most $k{h}_n$. Consequently $|{\tau }_i-{\xi }_i|\le k{h}_n$. Since all these numbers lie in $[0,1]$, for any two internal knots $u,v$ we also haveAveraging gives $|{\tau }_i^2-q_i|\le 2k{h}_n$. Nonnegative weights of sum one now yieldHere the spline order $k$ is fixed, so all three errors tend to zero. The Korovkin theorem therefore provesNo special selection such as the Greville abscissae is required for the sample points. In fact the local-support error bound for a Schoenberg spline operator also gives $\Vert V_{n}f-f{\Vert }_{\infty }\le \omega (f,k{h}_n)$. Under the usual continuous-spline convention the operators have the codomain required by the stated theorem. If the permissive knot notation is taken to allow full interior multiplicities and hence discontinuous splines, the same conclusion in the uniform norm still follows from this direct bound, although each approximant need not then be continuous.

A nontrivial example is $f_n=T_{n+1}$, the Chebyshev polynomial characterized by $T_{n+1}(\cos \theta )=\cos ((n+1)\theta )$. Its supremum norm is one. At the $n+2$ points $\cos (j\pi /(n+1))$, $0\le j\le n+1$, its values alternate between $1$ and $-1$; reversing their order gives increasing nodes with the same alternation.

The zero polynomial therefore satisfies the Chebyshev alternation theorem for degree at most $n$, so $E_n(f_n)=1$. Since the smaller polynomial space is contained in the larger one, $E_{n-1}(f_n)\ge 1$; the zero polynomial is feasible in the smaller space as well, giving the reverse inequality. HenceA constant function would also give equality with both errors zero, but this example shows that equality can occur at a positive approximation error.

For a function on an interval, the modulus of continuity is $\omega (f,t)={\sup }_{|x-y|\le t}|f(x)-f(y)|$, with the pair restricted to that interval. For a periodic function the equivalent definition is ${\sup }_{\theta ,|h|\le t}|g(\theta +h)-g(\theta )|$. The mean value theorem and $|\sin \theta |\le 1$ giveBoth cosine values lie in $[-1,1]$. Hence for $|h|\le t$,Taking the supremum provesIf the periodic modulus of continuity is defined using circular distance instead, choose lifts at that shortest distance and apply the same argument. The cosine substitution for polynomial approximation therefore does not enlarge this modulus.

The first Jackson theorem for periodic approximation states that an absolute constant $C_J$ exists such that, for every continuous $2\pi$-periodic function $g$ and integer $n\ge 1$, there is a trigonometric polynomial $q_n$ of degree at most $n$ satisfyingApply it to the continuous periodic function $g(\theta )=f(\cos \theta )$, which is even. Replace the approximant by its even partSince $g(-\theta )=g(\theta )$, the triangle inequality gives $\Vert g-q_n^{\mathrm{ev}}{\Vert }_{\infty }\le \Vert g-q_n{\Vert }_{\infty }$. This symmetrization cancels all sine terms, so $q_n^{\mathrm{ev}}={\sum }_{j=0}^n{\alpha }_j\cos (j\theta )$. The Chebyshev polynomials satisfy $T_j(\cos \theta )=\cos (j\theta )$ and have degree $j$; the latter follows inductively from $T_0=1$, $T_1=x$ and $T_{j+1}=2x{T}_j-T_{j-1}$. Thereforeis an algebraic polynomial of degree at most $n$, and $p_n(\cos \theta )=q_n^{\mathrm{ev}}(\theta )$. Because cosine maps onto $[-1,1]$, the supremum norms agree exactly:Finally, the definition of the best error, periodic Jackson approximation, and part (a) give the successive boundsThusNeither the constant nor the choice of approximation space depends on $f$. The cosine substitution for polynomial approximation and even symmetrization are what preserve the required degree bound.