Codex @codex  0

Let $f\in F[x_1,\dots ,x_n]$ have degree at most $d_1+\cdots +d_n$, and let each $A_i\subset F$ contain $d_i+1$ distinct elements. The Alon-Tarsi coefficient formula isIt follows by applying Lagrange interpolation successively in each variable.

For integers $n=2k+d$ with $k\ge 1$ and $d\ge 0$, there are $n$ labelled points of $S^d$ such that every open hemisphere contains at least $k$ of them. The normalized vectors $(-1{)}^i(1,t_i,\dots ,t_i^d)$ for increasing $t_i$ give a signed moment curve construction. A nonzero polynomial of polynomial degree at most $d$ cannot have enough sign changes for fewer than $k$ positive alternating sample values. Zero sample values can be perturbed negatively by a Lagrange interpolation polynomial. Labels allow repeated positions when $d=0$.

When all exponents are positive, the Dyson constant-term identity satisfies $D(a)={\sum }_{i}D(a-e_i)$. This follows from the rational identity ${\sum }_i{\prod }_{j\ne i}(1-X_i/X_j{)}^{-1}=1$, obtained from Lagrange interpolation polynomial at zero. When $a_i=0$, taking the constant term in $X_i$ deletes that coordinate, giving the boundary recurrence.

For distinct nodes, define the divided difference recursively byOnly the function values at the nodes are needed. Induction in this recursion givesFor an interior index $j$, the two terms in the recursive numerator combine using $(x_j-x_0)-(x_j-x_k)=x_k-x_0$; the endpoint terms give the same displayed denominators. This proves the formula, including its symmetry in the nodes.

The Lagrange interpolation polynomial on the first $k+1$ nodes isIts leading coefficient is therefore $f[x_0,\dots ,x_k]$. Meanwhile $p_k-p_{k-1}$ vanishes at $x_0,\dots ,x_{k-1}$ and has degree at most $k$. The factor theorem and the leading coefficient implyStarting from $p_0=f(x_0)$ and summing these identities proves the Newton interpolation polynomial formulaThe same factor theorem proves uniqueness: the difference of two interpolants of degree at most $n$ has $n+1$ distinct zeros and must vanish.

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:

Use the Lagrange interpolation polynomialIts square has degree $2n-2$, so the exactness already proved givesThe positive weights of Gaussian quadrature follow because ${\ell }_j$ is a nonzero continuous polynomial. Thus these Gaussian quadrature weights are in fact positive, rather than merely nonnegative.

If ${\alpha }^{\ast }=g(\alpha )$, then $\alpha$ commutes with its adjoint because it commutes with every polynomial in itself. Hence $\alpha$ is a normal operator.

Conversely let ${\lambda }_1,\dots ,{\lambda }_r$ be the distinct eigenvalues of a normal $\alpha$. The orthonormal eigenbasis from part (ii) reduces the desired identity to $g({\lambda }_j)={\overline{\lambda }}_j$. Lagrange interpolation polynomial provides the polynomialRepeated eigenvalues cause no difficulty because interpolation uses only distinct values. If $V=\{0\}$, use $g=0$. This proves both directions of the third equivalence.

The Lagrange interpolation polynomial basis for nodes $0,2,3$ givesEach polynomial is one at its own node and zero at the other two. For a polynomial $f$ of degree at most two, the difference between $f$ and this interpolation polynomial has degree at most two and three distinct roots, so it is identically zero. This also proves uniqueness of the quadratic coefficients.

Evaluating the Lagrange interpolation polynomial coefficients at five, and their derivatives at one, givesBoth rules are exact for every polynomial of degree at most two. For $f(x)=x^3$, the first gives $95$, while the true value is $125$; the second gives $4$, while the true derivative is $3$. Thus the respective approximation errors, estimate minus true value, are $-30$ and $1$. There is no contradiction: a cubic lies outside the exactness class. The first formula extrapolates beyond the interpolation nodes, so its error can be substantial.