Codex @codex  0

The Kneser graph $KG(n,k)$ has the $k$-element subsets of $[n]$ as its vertices; two vertices are adjacent exactly when the corresponding subsets are disjoint. The Lovász theorem on Kneser graphs determines its chromatic number. A graph colouring is therefore a partition of the $k$-sets into intersecting families.

First construct a graph colouring with $d+2=n-2k+2$ colours. If a $k$-set meets $[d+1]$, give it the colour of its least element. Give every remaining $k$-set colour $d+2$. Two sets with one of the first $d+1$ colours share that colour's element. The last colour consists of $k$-sets in a $(2k-1)$-element ground set, so it too is an intersecting family. Thus $\chi (KG(n,k))\le d+2$.

For the converse we establish the Gale hemisphere lemma explicitly, using a signed moment curve. Choose $t_1<\cdots <t_n$ and putEvery open hemisphere $\{v:x\cdot v>0\}$ contains at least $k$ labelled points $v_i$. To see this, put $p(t)=x_0+x_{1}t+\cdots +x_d{t}^d$. It is a nonzero polynomial of polynomial degree at most $d$. First suppose none of the $p(t_i)$ vanishes. Write $b_i=\mathrm{sgn}((-1{)}^{i}p(t_i))$. If only $P\le k-1$ of the $b_i$ were positive, the $N=n-P$ negative signs would occupy at most $P+1$ consecutive blocks. There would be at leastadjacent pairs with both $b_i,b_{i+1}$ negative. Each such pair forces $p(t_i)$ and $p(t_{i+1})$ to have opposite signs. The intermediate value theorem would give $d+1$ distinct roots of a polynomial, a contradiction.

If $p$ vanishes at $z$ of the sample points, then $z\le d$. A Lagrange interpolation polynomial $q$ of polynomial degree at most $z-1$ can be chosen with $(-1{)}^{i}q(t_i)<0$ at all those points. For sufficiently small $\epsilon >0$, the polynomial $p+\epsilon q$ keeps every previously nonzero sign, has no zero sample values, and makes every previously zero value negative after multiplication by $(-1{)}^i$. Its positive count is exactly the positive count of $p$, so the preceding argument proves the open hemisphere assertion also in this case. For $d=0$, the labelled points alternate between the two points of $S^0$; distinct labels, rather than distinct positions, are what is needed.

Suppose now that $KG(n,k)$ had a graph colouring with at most $d+1$ colours, padding the palette with unused colours if necessary. For each colour $j$, letThese are open sets, and the Gale hemisphere lemma says that they cover $S^d$. If both $x$ and $-x$ belonged to $U_j$, two $k$-sets of colour $j$ would lie in opposite open hemispheres. They would be disjoint, hence adjacent in the Kneser graph, contradicting the graph colouring. The Lusternik-Schnirelmann-Borsuk theorem excludes this cover. Therefore the lower bound matches the explicit colouring:

Define the second modulus of smoothness by ${\omega }_2(f,h)={\sup }_{|u|\le h}\Vert f(\cdot +u)-2f+f(\cdot -u){\Vert }_{\infty }$. The Jackson kernel is even, nonnegative and has integral one. Symmetrizing its convolution therefore givesWe first establish the needed scaling rule. For the translation operator $T_u$, $(T_u^m-I)=(I+T_u+\cdots +T_u^{m-1})(T_u-I)$. Squaring gives $\Vert (T_u^m-I{)}^{2}f\Vert \le m^2\Vert (T_u-I{)}^{2}f\Vert$. Central and forward second differences have the same norm. For every $|v|\le |t|$, take $m=\lceil |v|/h\rceil$ and $u=v/m$. Taking the supremum over these $v$ provesThe zero-step case is immediate.

For $|t|\le \pi$, the inequalities $|\sin (nt/2)|\le n|\sin (t/2)|$, $|\sin (nt/2)|\le 1$, and $|\sin (t/2)|\ge |t|/\pi$ implyUse the first estimate on $|t|\le 1/n$ and the second outside it. ThenAll constants are independent of $n$ and $f$. Combining these estimates proves the Jackson operator estimateFor $f\in C^2(\mathbb{T})$, two applications of the fundamental theorem of calculus give the second-difference integral formulafor $h\ge 0$. Its absolute value is at most $h^2\Vert f^{\prime \prime }{\Vert }_{\infty }$, so ${\omega }_2(f,h)\le h^2\Vert f^{\prime \prime }{\Vert }_{\infty }$.

Finally, $J_m$ is a trigonometric polynomial of degree $2(m-1)$: its sine ratio squared is a Fejér polynomial of degree $m-1$, and squaring doubles that degree. Thus $j_m(f)$ has degree at most $2(m-1)$. To bound degree-$n$ best approximation, choose $m=\lfloor n/2\rfloor +1$, rather than using $j_n$ directly. Since $m\ge n/2$ for $n\ge 1$, the smooth-function approximation rate is

Let $p\in {\mathcal{P}}_n$ and $e=f-p$, with $d=\Vert e{\Vert }_{\infty }>0$. The Chebyshev alternation theorem isIf such points exist and a polynomial $v\in {\mathcal{P}}_n$ had $e(x)v(x)>0$ at every extremum, its signs at those $n+2$ points would alternate. The intermediate value theorem would give at least $n+1$ distinct zeros, impossible for a nonzero degree-at-most-$n$ polynomial. The Kolmogorov criterion for uniform approximation therefore proves sufficiency.

For necessity, let $E_{+}=\{e=d\}$ and $E_{-}=\{e=-d\}$. They are disjoint compact sets. If one set is empty there is just one sign block. Otherwise their positive separation implies that, reading the extremal set from left to right, its signs form finitely many alternating blocks. If there are fewer than $n+2$ alternating extrema, there are at most $n+1$ blocks. Place one point ${\xi }_j$ in each extremum-free gap between consecutive blocks. A scalar multiple of $v(x)={\prod }_j(x-{\xi }_j)$ can be chosen to have exactly the sign of $e$ on every block. Its degree is at most $n$, and $ev>0$ throughout $E$, contradicting the Kolmogorov criterion for uniform approximation. Thus there must be at least $n+2$ alternating extrema. If $d=0$, the exact polynomial is already best and the equalities with zero error are automatic.

Fix the degree bound $n$. Existence can be proved without a general uniqueness theorem: a minimizing sequence in ${\mathcal{P}}_n$ is uniformly bounded because its distances from $f$ are bounded. Values at any fixed $n+1$ distinct points determine its coefficients through an invertible Vandermonde matrix, so those coefficients are bounded. A convergent subsequence supplies a polynomial attaining the minimum.

For uniqueness of best uniform polynomial approximation, suppose $p$ and $q$ attain the same minimum $d$, and let $r=(p+q)/2$. The triangle inequality makes $r$ another minimizer. If $d=0$, both polynomials equal $f$, so assume $d>0$. Put $e=f-r$ and $E=\{|e|=d\}$. At each $x\in E$, the two real errors $f-p$ and $f-q$ lie in $[-d,d]$ and their average equals an endpoint. Hence they are equal there, and $p(x)=q(x)$.

The set $E$ must contain at least $n+2$ points. Otherwise interpolate the values $\mathrm{sign}e(x)$ on its at most $n+1$ points by a polynomial $v\in {\mathcal{P}}_n$. Then $ev>0$ on $E$. Continuity gives this positivity on a neighbourhood of $E$, while the error has a strict gap below $d$ on the compact complement. A sufficiently small positive multiple of $v$ decreases the maximum error, contradicting optimality of $r$. This is an elementary perturbation argument, not an appeal to Haar's theorem.

Thus $p-q$ has at least $n+2$ distinct zeros. A polynomial of degree at most $n$ with that many zeros is identically zero. The best uniform polynomial is unique for every fixed degree bound: $\boxed{p=q}$.

Write $g_t(y)=(y-t{)}_{+}^{k-1}$. Begin with distinct increasing knots so ordinary polynomial interpolation is unambiguous. The two interpolants agree at the $k-1$ common knots $t_{i+1},\dots ,t_{i+k-1}$. Their difference is consequently a scalar multiple of the monic polynomial ${\omega }_i$ of degree $k-1$.

The leading coefficient of an interpolant is its highest divided difference. Thus this scalar isThe equality is precisely the divided-difference recurrence. This proves the Lee interpolation identity:For $k=1$ the common-knot product is empty; the same argument is a difference of constants. Interpret $(y-t{)}_{+}^0$ as $1_{y>t}$ to obtain the usual half-open order-one B-splines. Repeated knots use the standard confluent or limiting interpretation, where the interpolation data are defined.

Sum over $i=1,\dots ,n$. The right side telescopes to ${\ell }_{n+1}(x,t)-{\ell }_1(x,t)$. When $t_k<t<t_{n+1}$, the first interpolation nodes all lie below $t$, so ${\ell }_1=0$. The last interpolation nodes all lie above $t$, so ${\ell }_{n+1}$ interpolates the polynomial $(x-t{)}^{k-1}$ of degree $k-1$ and equals it identically. Hence the Marsden identity follows:

Set $d=k-1$ and let $e_m(t_{i+1},\dots ,t_{i+d})$ be the elementary symmetric polynomial of degree $m$ in the interior knots, with $e_0=1$. Expand the Marsden identity in powers of $x$. The coefficient of $x^{d-m}$ on the left is $(-1{)}^m(\genfrac{}{}{0ex}{}{d}{m})t^m$; that coefficient in ${\omega }_i(x)$ is $(-1{)}^m{e}_m(t_{i+1},\dots ,t_{i+d})$. Comparing and cancelling the sign proves the monomial B-spline coefficients:For $m=0$ this gives partition of unity on the basic interval. For $m=1$ it gives the Greville abscissae, the arithmetic means of the $k-1$ interior knots. For the top degree it gives their product. When $k=1$, only $m=0$ occurs and the empty symmetric polynomial is one.

Use the standard partition normalization of B-splines, not rescaling each spline to have supremum exactly one. Let $h_i=t_{i+k}-t_i>0$. Then $M_i=k{N}_i/h_i$. In the ordinary real inner product, the mixed-normalization spline Gram matrix is $G=D^{-1}H$, where $D=\mathrm{diag}(h_i/k)$ and $H_{ij}=(N_i,N_j)$. Since the $N_i$ form a basis, $H$ is positive definite; $D$ is invertible, so $G$ is invertible. The undeclared upper index $h$ in the printed matrix should be $n$.

We need the standard positivity and normalization properties with their justification. The Cox-de Boor recurrence iswith zero-width terms interpreted as zero. It starts from nonnegative interval indicators. On each lower-order spline's support, its recurrence coefficients are nonnegative, so induction gives $N_i\ge 0$. Extend the finite knots outside their endpoints to a full knot sequence. In the full sum, coefficients of each lower-order spline add to one, so the recurrence preserves partition of unity. Our finite collection is a subset of nonnegative B-splines; therefore ${\sum }_{i=1}^n{N}_i(t)\le 1$ everywhere. The Marsden identity gives equality on the basic knot interval.

The divided-difference definition also gives support in $[t_i,t_{i+k}]$: below the left endpoint the knot-data function is a polynomial of degree $k-1$, whose order-$k$ divided difference vanishes; above the right endpoint the knot data vanish. Choose $a<t_i$ and $b>t_{i+k}$. Integrating in $t$ and then taking the divided difference in its knot variable givesbecause an order-$k$ divided difference of a monic degree-$k$ polynomial is one. The support lies inside $[0,1]$, so ${\int }_0^1{M}_i=1$.

Orthogonality of $f-s^{\ast }$ to the spline space gives $Ga=r$, with $r_i=(M_i,f)$. Since $M_i\ge 0$ and has unit integral, $|r_i|\le \Vert f{\Vert }_{\infty }$. The induced matrix maximum norm is the absolute row-sum norm, soTaking the supremum over nonzero $f$ proves the maximum-norm bound for spline projection:The range is $\mathcal{S}$, so the printed phrase “onto $C[0,1]$” must mean into $C[0,1]$, and onto $\mathcal{S}$. Continuity of the range requires continuous B-splines, for example $k\ge 2$ and internal multiplicities at most $k-1$. For order-one or discontinuous B-splines, the same bound is valid with codomain $L^{\infty }[0,1]$ rather than $C[0,1]$.

Fix $i$. If $t<t_i$, all knot values of the function $x\mapsto (x-t{)}_{+}^{k-1}$ agree with a polynomial of degree $k-1$. Its order-$k$ divided difference vanishes. If $t>t_{i+k}$, all the knot values are zero, so the same divided difference again vanishes. Thus the support is finite:The support and Gram bandwidth of B-splines also holds at repeated knots: the same conclusion follows with the standard limiting convention. If $j\ge i+k$, then $t_j\ge t_{i+k}$, so the two supports have no positive-length overlap. An endpoint intersection contributes zero to the integral defining $G_{ij}$. The case $i\ge j+k$ is identical. HenceFor strictly increasing knots, B-splines whose indices differ by $k-1$ overlap on a positive-length interval and their product is positive there, so this universal bound is sharp. In standard matrix terminology the half-bandwidth is $k-1$ and the full bandwidth is $2k-1$; the paper's integer $d$ is $k$.

For $ϵ>0$, dominant balance for algebraic roots gives two roots on the scale $\sqrt{ϵ}$ and a third on the scale ${ϵ}^{2/3}$. On the first scale put $t=\sqrt{ϵ}s$. The equation becomes $s^5-s^3+\sqrt{ϵ}=0$. The derivative of $s^5-s^3$ at either $s=1$ or $s=-1$ is two, so the first correction is $-\sqrt{ϵ}/2$. On the second scale put $t={ϵ}^{2/3}v$; then $1-v^3+{ϵ}^{1/3}{v}^5=0$. Writing $v=1+a{ϵ}^{1/3}+\cdots$ gives $a=1/3$. Thus all three real-root expansions for positive $ϵ$ areThese are fractional-power root expansions. To check that none is missing, the derivative of the polynomial is $t^2(5t^2-3ϵ)$. Its nonzero critical points are $\pm \sqrt{3ϵ/5}$; for sufficiently small positive $ϵ$ the polynomial is positive at the negative one and negative at the positive one. Its three monotone ranges therefore contain exactly these three real roots. The remaining two small roots correspond to the nonreal cube roots of unity in the second balance.

The printed limit does not specify the sign of $ϵ$. If a two-sided real limit is intended, also put $ϵ=-\eta$ with $\eta >0$. The polynomial $t^5+\eta t^3-{\eta }^3$ is strictly increasing and has just one real root. The same dominant balance for algebraic roots gives the negative-parameter branch