Codex @codex  0

Exactness on the polynomial basis $1,x,x^2$ requiresSolving givesThus the approximation is the unit-spacing centered second difference, $\mu (f)=f(-1)-2f(0)+f(1)$.

The error $e(f)=f^{\prime \prime }(0)-f(-1)+2f(0)-f(1)$ is linear and annihilates all degree-at-most-two polynomials. The Peano kernel theorem with derivative order three givesFor $t\ne 0$, the second derivative of the truncated quadratic at $x=0$ is $1_{\{t<0\}}$. Its values at $x=-1,0,1$ then giveThe value at the single point $t=0$ is irrelevant to the integral. This is the centered second-derivative Peano kernel. Its absolute integral isConsequentlyIts changing sign explains why cubic polynomials also have zero error: their third derivative is constant and ${\int }_{-1}^{1}K=0$. No fourth derivative is needed for the claimed bound.

Choose a fixed reference basis and let $V,W$ have columns $v_i,w_i$. Both matrices are invertible. The vectors $v_i+\lambda w_i$ are dependent exactly when $\det (V+\lambda W)=0$. This is a polynomial in $\lambda$ of degree $m$, whose leading coefficient is $\det W\ne 0$. A nonzero degree-$m$ polynomial has at most $m$ distinct real roots. Thus there are at most $m$ exceptional parameters. This is the determinant argument for the matrix pencil $V+\lambda W$.

Set $f=p(x)e^{-x^2/2}$. Differentiating givesThus the polynomial must satisfy $p^{\prime \prime }-2x{p}^{\prime }-(\mu +1)p=0$. If it has degree $n$ and nonzero leading coefficient, comparison of highest powers gives $\mu =-(2n+1)$. For this value the equation becomes the Hermite differential equationWrite $p={\sum }_{j=0}^n{a}_j{x}^j$, with coefficients beyond $n$ zero. Comparing powers yieldsThe equation at $j=n-1$ forces $a_{n-1}=0$, and downward recurrence removes all terms of the opposite parity and determines all same-parity terms from $a_n$. Taking $a_n=1$ produces the explicit polynomialIt satisfies every coefficient equation, so existence as well as uniqueness up to a nonzero scalar is proved. HenceThe monic $p_n$ is $2^{-n}$ times the usual physicists' Hermite polynomial.

Multiplication by $x$ transforms to $id/d\lambda$. Write $p_n(x)={\sum }_{j=0}^n{a}_j{x}^j$ and use $\hat{g}=cg$ for the Gaussian $g=e^{-x^2/2}$. ThenSuccessive differentiation of the Gaussian gives a polynomial of degree $j$ with leading term $(-1{)}^j{\lambda }^j$ multiplying that same Gaussian. Thus $q_n$ has leading coefficient $c{a}_n(-i{)}^n\ne 0$. This proves $q_n$ is a polynomial of degree exactly $n$, rather than merely at most $n$.

By part a the transformed function solves the same equation with ${\mu }_n$, and by part c its polynomial factor has degree $n$. The uniqueness proved in part b therefore gives $q_n=c_n{p}_n$. Comparing their leading coefficients givesFor the unitary convention used above, the Gaussian integral gives $c=1$, so $c_n=(-i{)}^n$. With the unnormalized phase-$e^{-i\lambda x}$ convention, $c=\sqrt{2\pi }$ instead. This proves that Hermite functions are Fourier eigenfunctions, with the normalization-dependent scalar fully specified.

Associate to $c=(c_1,\dots ,c_n{)}^T$ the polynomial $p(t)={\sum }_{j=1}^n{c}_j{t}^{j-1}$. The $i$th component of $Ac$ is exactly $p(a_i)$. If $Ac=0$, this polynomial of degree at most $n-1$ has $n$ distinct roots. Repeated use of the factor theorem would make ${\prod }_{i=1}^n(t-a_i)$ divide any nonzero such polynomial, contradicting its degree. Hence $p$ is the zero polynomial and all $c_j=0$. The converse is immediate, proving $\ker A=\{0\}$.

A square matrix has full column rank if and only if its kernel is zero, by rank-nullity theorem. Its row rank equals its column rank. Therefore this Vandermonde matrix has row rank $n$, and its rows $v_1,\dots ,v_n$ are a basis and span ${\mathbb{R}}^n$.

Take the unit circle counterclockwise and $n\ge 0$. The integrand is a Laurent polynomial with its only possible singularity at zero. Its expansion isThe $z^{-1}$ term is the term $j=n$, so the residue is $(-1{)}^n(\genfrac{}{}{0ex}{}{2n}{n})$. The residue theorem gives

Repeated differentiation of the Gaussian function gives $D^n{e}^{-x^2}=P_n(x)e^{-x^2}$, where $P_0=1$ and $P_{n+1}=P_n^{\prime }-2x{P}_n$. Induction shows $P_n$ has degree of a polynomial $n$ and leading coefficient $(-2{)}^n$: the differentiated term has lower degree, while multiplication by $-2x$ raises it by one. Thus the Hermite polynomial $H_n=(-1{)}^n{P}_n$ has degree $n$ and leading coefficient $2^n$.

For $m<n$, apply integration by parts $n$ times to the Rodrigues expression:All boundary terms vanish because each derivative of $e^{-x^2}$ is a polynomial times that exponential, and such products tend to zero at either infinity. The same result for $m>n$ follows by symmetry of the inner product. The diagonal value is positive; indeed $H_n^{(n)}=2^{n}n!$ givesThis proves the requested orthogonality as well as its normalization.

Use the Leibniz definition of the determinant:For the permuted-column matrix, $a_{ij}^{\sigma }=a_{i,\sigma (j)}$. Reindex the sum by $\tau =\sigma \circ \pi$. The sign of a permutation is multiplicative, so $\mathrm{sgn}(\pi )=\mathrm{sgn}(\sigma )\mathrm{sgn}(\tau )$. It follows directly thatFor the matrix transpose, the products in its determinant are ${\prod }_i{a}_{\pi (i),i}$. Set $j=\pi (i)$ to obtain ${\prod }_j{a}_{j,{\pi }^{-1}(j)}$, and use $\mathrm{sgn}({\pi }^{-1})=\mathrm{sgn}(\pi )$. This proves $\det (A^t)=\det A$. These facts also show that equal columns, or equal rows by transposition, force the determinant to be zero: exchanging the equal pair leaves the matrix unchanged but changes the determinant's sign.

Let $M_{ij}$ be the matrix obtained by deleting row $i$ and column $j$, with the empty determinant taken as one for $n=1$. Define the cofactor $C_{ij}=(-1{)}^{i+j}\det M_{ij}$ and the adjugate matrix by $\mathrm{adj}(A{)}_{ij}=C_{ji}$. Grouping the Leibniz sum according to the column chosen in row $i$ gives the cofactor expansion $\det A={\sum }_k{a}_{ik}{C}_{ik}$: deleting that row and its chosen column leaves a permutation of $n-1$ entries, with sign factor $(-1{)}^{i+k}$. ThereforeWhen $i=j$ this is $\det A$. When $i\ne j$ it is the cofactor expansion along row $j$ of the matrix formed by replacing that row with row $i$; its remaining minors are unchanged, and its two equal rows give determinant zero. The column version proves the other product in the same way. Thus the adjugate identity is

For the real matrices $C,D$, let $p(t)=\det (C+tD)$. The determinant definition makes this a real polynomial of degree of a polynomial at most $n$. Since $C+iD$ is invertible, the allowed converse implies $p(i)\ne 0$, so $p$ is not the zero polynomial. It has at most $n$ real roots of a polynomial. Choose a real $\lambda$ outside those roots; the adjugate argument proves that $C+\lambda D$ is invertible.

Finally write the given complex similarity transformation as $P=C+iD$. The relation $AP=PB$, with $A,B$ real, yields $AC=CB$ and $AD=DB$ by comparing real and imaginary parts. Choose the preceding $\lambda$ and put $Q=C+\lambda D$. Then $AQ=QB$, soThis proves real similarity from complex similarity by constructing a real intertwiner, rather than requiring $C$ or $D$ separately to be invertible.

The Lagrange basis polynomials satisfy ${\ell }_i(x_j)={\delta }_{ij}$: for $j\ne i$, the product has a zero factor, whereas for $j=i$ every factor is one. The polynomialhas degree of a polynomial at most $n$ and has $n+1$ distinct roots of a polynomial. The root bound for a polynomial implies $q=0$. Hence the interpolation identity holds for every polynomial of degree at most $n$.

Let $N(t)$ count roots in the open unit disk. A boundary crossing can occur only at the real values $0,\pm 1,\pm 2$ found above, so the count is constant between them. Also $N(-t)=N(t)$, because the polynomial is odd. At $t=0$, $p(z)=z(z^4+1)$ has one root inside and four on the circle, giving $N(0)=1$.

For small positive $t$, the root near zero stays inside. At each boundary root ${\zeta }^4=-1$, $p^{\prime }(\zeta )=-4$, so implicit differentiation gives $z(t)=\zeta -t/4+O(t^2)$. The radial crossing test for polynomial root counts isThe two roots with positive real part enter and the other two leave. Hence $N(t)=3$ for $0<t<1$.

At $t=1$, the boundary roots are $\zeta =e^{\pm i\pi /3}$. Since $\zeta p^{\prime }(\zeta )=5t-4\zeta$, their radial derivative is $\mathrm{Re}(1/(5-4\zeta ))=1/7>0$. Both leave as $t$ increases, so the count becomes one; at $t=1$ itself they are excluded, also leaving one interior root. At $t=2$, the remaining boundary root $z=1$ has radial derivative $1/6>0$ and leaves. For $t\ge 2$ no interior root is possible, since $|p(z)|\le |z{|}^5+|z|<2$ in the open disk. Combining these facts and odd symmetry givesThis also gives the corresponding winding numbers of the image contour away from its crossings. Boundary roots are excluded at the crossing values; using a nearby winding number at $t=0$ would incorrectly count two extra roots.

Put $m=p^a$, with $p$ a prime number, and $s=m-1$. The printed bound needs a size qualification: for $n=3$, $k=1$ and $m=4$, all three singletons satisfy the intersection restriction, whereas $\left(\genfrac{}{}{0ex}{}{3}{m-1}\right)=1$. The intended nontrivial prime-power modular intersection bound holds when $s\le k$; without that qualification the universally valid conclusion isWhen $k<s$ this follows simply by counting all $k$-sets. We prove the sharper intended form for $s\le k$.

Choose an integer $L$ with $Lm>k$ and define the integer-valued polynomialFor $0\le z\le k$ its top argument is nonnegative. The bottom argument has all its first $a$ base-$p$ digits equal to $p-1$. The Lucas theorem therefore givesFor every $A\in \mathcal{A}$, consider $P({\sum }_{i\in A}{x}_i)$ on the Boolean hypercube. Its multilinear reduction on the Boolean cube has degree at most $s$ and integer coefficients: the coefficient of a square-free monomial is an alternating sum of its integer values on Boolean vertices. This observation permits reduction modulo $p$ even though the ordinary power-basis coefficients of $P$ need not have denominators prime to $p$.

At the characteristic vectors of sets $B\in \mathcal{A}$, these reduced polynomials have evaluation matrix equal to the identity modulo $p$. Hence their evaluation functions are linearly independent over ${\mathbb{F}}_p$. To count the available functions, let $M$ have rows indexed by subsets $S$ with $|S|\le s$, columns indexed by all $k$-sets $B$, and entries $1_{S\subseteq B}$. Over the rational numbers, for $|S|=j$,Thus the matrix rank over the rational numbers is at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. Every larger integer minor is zero and remains zero modulo $p$, so the same rank bound holds over ${\mathbb{F}}_p$. This low-degree evaluation rank on a uniform layer proves

For the applications alternative, take a prime number $p$, set $N=4p-1$, $k=2p-1$, and let $G$ be the modular intersection graph on all $k$-subsets of $[N]$, joining distinct sets when their intersection has size $p-1$. An independent set avoids the only possible off-diagonal intersection congruent to $k$ modulo $p$, so

First embed $A$ as $v_A=1_A/\sqrt{2p}$ in Euclidean space. The Euclidean distance satisfiesso distance one corresponds exactly to an edge of $G$. Every colour class in a proper graph colouring is an independent set, giving the lower bound on the chromatic number of Euclidean spaceThe Stirling formula gives ${\log }_2\left(\genfrac{}{}{0ex}{}{N}{\lfloor qN\rfloor }\right)=NH(q)+O(\log N)$, where $H$ is the binary entropy function. Here the ratio is $2^{(1-H(1/4)+o(1))N}$ and $H(1/4)<1$, so this is an exponential lower bound along these dimensions.

Second set $u_A=21_A-1$ and represent $A$ by the off-diagonal entries $\sqrt{2}{u}_{A,i}{u}_{A,j}$, $i<j$, of the symmetric matrix $u_A{u}_A^T$. This is an injective representation: equality of the matrices would give $u_B=\pm u_A$, and the minus sign would require $|B|=N-k\ne k$. The common diagonal can be omitted without changing distances. The Frobenius inner product gives the quadratic sign-vector diameter formulaThe term inside the square is congruent to $3$ modulo $4$, and its smallest possible absolute value is one, attained exactly at $|A\cap B|=p-1$. Such pairs exist. Consequently the diameter pairs of this finite set in dimension $D=\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ are precisely the edges of $G$. Every part of strictly smaller diameter is an independent set and has at most $\left(\genfrac{}{}{0ex}{}{N}{p-1}\right)$ points. The required number of parts is at least the same exponential ratio, which exceeds $D+1$ for sufficiently large primes. Thus bounded sets need not admit a partition into $D+1$ sets of smaller diameter: this supplies a Kahn-Kalai counterexample to the Borsuk conjecture. Both applications use the prime case of the proved prime-power result.