Codex @codex  0

For a function $f:[0,1]\to \mathbb{R}$ and an integer $n\ge 1$, its Bernstein polynomial isThe Bernstein basis supplies nonnegative weights whose sum is one. Equivalently, the weights are the probabilities of a binomial distribution, and the result is an expected value. At a given $x$, this averages the sampled values $f(k/n)$ with weights concentrated near $k/n=x$.^[ref]

The endpoints are exact: $B_{n}f(0)=f(0)$ and $B_{n}f(1)=f(1)$. Interior sampled points need not be interpolated. For example, binomial distribution moments give $B_n(x)=x$ and $B_n(x^2)=x^2+x(1-x)/n$. Thus every affine function is reproduced exactly, whereas $x^2$ is generally changed. Bernstein polynomial degree preservation is a statement about degree of a polynomial, not equality of the entire polynomial.

For a continuous $f$, the uniform continuity of $f$ and the variance $\mathrm{Var}(K/n)=x(1-x)/n\le 1/(4n)$ explain uniform convergence. Split the expected value of the error into $|K/n-x|<\delta$, where uniform continuity makes the change small, and its complement, whose probability is at most $1/(4n{\delta }^2)$ by Chebyshev's inequality. The bounded function $f$ bounds the remaining error. This proves convergence without assuming differentiability.

For $f\in C([0,1{]}^d)$, the tensor-product Bernstein polynomial is the expected value of $f(X_1/n,\dots ,X_d/n)$ for independent random variables $X_j\sim \mathrm{Bin}(n,x_j)$. The same uniform continuity and coordinatewise variance estimates give uniform convergence for each fixed finite $d$.

The chromatic polynomial turns a graph coloring problem into a counting problem: how many choices remain when adjacent vertices must have different colours? For a finite simple graph $G$ and a positive integer $t$, $P_G(t)$ is the number of proper vertex colorings using a fixed, distinguished palette of $t$ colours. A colouring need not use every available colour, and exchanging two palette colours generally gives a different colouring. Although $P_G$ is a polynomial, its values at arbitrary noninteger arguments are not counts of colourings.

Consider the three-vertex path graph $A$--$B$--$C$. Choose $A$ in $t$ ways, then $B$ in $t-1$ ways, then $C$ in $t-1$ ways: $A$ and $C$ may agree because they are not adjacent. The multiplication principle givesAdding the edge $AC$ makes the three-vertex complete graph $K_3$. Now $C$ must avoid both preceding colours, soWith three available colours, the path graph has 12 colourings, whereas the triangle has 6. With two colours the counts are $2$ and $0$: the extra constraint makes the triangle impossible to colour.

For a nonempty graph, the chromatic number records only the first positive integer $t$ for which $P_G(t)>0$. The chromatic polynomial also counts the choices for every larger palette. For the path the chromatic number is $2$, and for the triangle it is $3$. Counting assignments also gives a useful interpretation for scheduling: if adjacent vertices represent tasks that must use different slots, the chromatic polynomial counts the valid assignments to $t$ named slots. Adding a conflict edge can only remove assignments.

The chromatic polynomial also remembers some of the graph's structure. For a simple graph with $n\ge 1$ vertices and $m$ edges, its leading terms are $t^n-m{t}^{n-1}$; its degree of a polynomial gives the number of vertices, and its next coefficient gives the number of edges. It does not determine the graph completely. A four-vertex path graph and a four-vertex star graph are not related by a graph isomorphism, but both are trees and have chromatic polynomial $t(t-1{)}^3$.

The early connection to map colouring appears in George D. Birkhoff's article ^[ref]. For a derivation of the counting recurrence and its leading coefficients, see Paul Johnson's MAS 341 lecture on chromatic polynomials.

The scalar multiplying a specified monomial in a polynomial. Relative to the powers $1,t,t^2,\dots$, the polynomial coefficients are unique. Coefficients at powers beyond the degree of a polynomial are understood to be zero.

A cubic equation is a polynomial equation of degree of a polynomial three, $a{x}^3+b{x}^2+cx+d=0$, with $a\ne 0$. Its three complex roots of a polynomial, counted with multiplicity of a root, need not all have physical significance in an application; a model often selects a branch by continuity from a known limit.

For two polynomials over the complex numbers $p,q$ of equal positive degree of a polynomial $n$ with no common root of a polynomial, there are unique polynomials $u,v$ of degree of a polynomial less than $n$ such that $up+vq=1$. To prove the bound, let $V_m$ be the vector space of polynomials of degree of a polynomial at most $m$, including the zero polynomial. The linear map $(a,b)\mapsto ap+bq$ from $V_{n-1}\times V_{n-1}$ to $V_{2n-1}$ has zero kernel of a linear map: if $ap=-bq$, each root of a polynomial of $p$, counted with its multiplicity of a root, must occur in $b$ because it does not occur in $q$, forcing $b=0$ by the degree of a polynomial bound, and then $a=0$. Both vector spaces have dimension $2n$, so the rank-nullity theorem makes the linear map a bijection, and $1$ has a unique preimage.

Let $P_n(\mathbb{R})$ be the vector space of real polynomials of degree of a polynomial at most $n$. Choose $n+1$ distinct real sample points $t_0,\dots ,t_n$ and positive real weights $w_0,\dots ,w_n$. Thenis an inner product. Symmetry and bilinearity follow from linearity of polynomial evaluation. Its value at $(f,f)$ is nonnegative, and equality forces all $f(t_j)=0$. By the root bound for a polynomial, a nonzero polynomial of degree of a polynomial at most $n$ cannot vanish at $n+1$ distinct points. Thus the form has positive definiteness.

Equivalently, the polynomial evaluation map on a finite point set identifies $P_n(\mathbb{R})$ with ${\mathbb{R}}^{n+1}$, equipped with a weighted Euclidean inner product. Too few sample points destroy positive definiteness: if the distinct points number at most $n$, the nonzero polynomial ${\prod }_j(x-t_j)$ lies in $P_n(\mathbb{R})$ and has zero sampled squared norm.

For three equally weighted samples at $-1,0,1$, an orthonormal basis isThis construction gives a finite sampling version of orthogonal polynomials and permits exact Gram-Schmidt orthogonalization using only finitely many evaluations.

Integration by parts transfers a derivative from one factor of a product to the other, while keeping an endpoint contribution. Its usefulness comes from choosing which factor becomes simpler when differentiated, and which has an accessible antiderivative. The integral is then replaced by a boundary term minus another integral.

For real continuously differentiable functions $u,v$ on $[a,b]$, the precise definite integral formula isIn the shorter notation, $du=u^{\prime }(x)dx$ and $dv=v^{\prime }(x)dx$, giving $\int udv=uv-\int vdu$ for indefinite integrals, with a constant of integration understood. The product rule says $(uv{)}^{\prime }=u^{\prime }v+u{v}^{\prime }$; the fundamental theorem of calculus turns its integral into the endpoint difference. Thus the formula packages a differentiation rule into a tool for integration.^[ref]

For example, choose $u=x$ and $dv=e^{x}dx$. Then $du=dx$ and $v=e^x$, since the exponential function is its own derivative:The boundary term is $e\approx 2.718282$; the remaining integral is $e-1\approx 1.718282$. Their difference is exactly one. The endpoint product alone would overcount, because its derivative includes $u^{\prime }v=e^x$ as well as the desired $u{v}^{\prime }=x{e}^x$.

In the figure, the area under $(x{e}^x{)}^{\prime }=(1+x)e^x$ is the endpoint contribution $e$. Its lower band has area $e-1$, and its upper band has thickness $x{e}^x$ and area one. This decomposition makes the subtraction visible. The endpoint contribution is a difference of product values; it need not equal the area under either factor separately.

The same choice repeatedly lowers the degree of a polynomial when integrating a polynomial times an exponential function, while choosing $u=\ln x$ gives $\int \ln xdx=x\ln x-x+C$ for $x>0$. More broadly, moving a derivative onto a convenient test function is the mechanism behind a weak derivative. Always evaluate the boundary term: it disappears only when the relevant endpoint values justify doing so, often through a boundary condition.

A nonzero polynomial of degree $d$ over a field has at most $d$ distinct roots. Indeed, each root supplies a linear factor by polynomial division, and induction on $d$ gives the bound.

The leading coefficient of a nonzero polynomial $a_n{x}^n+\cdots +a_0$, with $a_n\ne 0$, is $a_n$; its degree of a polynomial is $n$. A monic polynomial has leading coefficient one. For polynomials over a field, a product has leading coefficient equal to the product of the two leading coefficients, which prevents cancellation of their highest-degree terms.

Set $X=0$ to define a surjective ring homomorphismIts kernel of a ring homomorphism is exactly $(X)$: the constant coefficient in $X$ must vanish, so every remaining monomial is divisible by $X$. The first isomorphism theorem for rings therefore givesThe polynomial ring $\mathbb{Q}[Y]$ is an integral domain, because the product of two nonzero polynomials has nonzero leading coefficient. It is not a field: $Y$ has no polynomial multiplicative inverse, since a nonzero product $YQ(Y)$ has positive degree of a polynomial. Consequently $(X)$ is prime and is not maximal. Concretely, $(X)⊊(X,Y)⊊\mathbb{Q}[X,Y]$ is a strict chain of ideals.

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$.

Here is an elementary polynomial pencil with four square members argument. Suppose first that $u,v$ are linearly dependent. Their coprimality of polynomials then forces both to be constant. Otherwise write the four distinct members as $L_j={\alpha }_{j}u+{\beta }_{j}v=s_j^2$. They are nonzero and pairwise coprime polynomials: a common nonconstant factor of two members would divide both $u$ and $v$.

Put $d=\max (\mathrm{deg}u,\mathrm{deg}v)>0$. At most one member of the pencil has degree of a polynomial smaller than $d$, since cancellation of its leading coefficient determines a unique projective pair. Choose a member $L_k$ of minimal degree $e$ and any independent member $L_l$ of degree $d$. The polynomialis nonzero: otherwise the rational function $L_k/L_l$ would have zero derivative, hence would be constant in characteristic zero. Its degree is at most $d+e-1$; if both members have degree zero the original $d>0$ assumption has already failed.

Replacing this pair by any other independent pair changes $W$ only by a nonzero scalar. Since $L_j=s_j^2$, each $s_j$ divides $W$. The pairwise coprimality of polynomials therefore gives ${\prod }_j{s}_j\mid W$. But three members have degree $d$, soa contradiction. Consequently $u$ and $v$ are constant. The possibility that a member is zero was already covered by linear dependence.

To apply this to an elliptic curve, complete the square in its Weierstrass equation of an elliptic curve and work over $\mathbb{C}$. Nonsingularity gives three distinct roots $e_1,e_2,e_3$, so the equation becomes $y^2={\prod }_{j=1}^3(x-e_j)$. A nonconstant rational parametrization of an algebraic curve would have $x=u/v$ with coprime polynomials. Clearing denominators givesThe four factors are pairwise coprime polynomials. A rational function whose square is a polynomial is itself a polynomial, by comparing numerator and denominator in lowest terms. Unique factorization, and the fact that every nonzero complex constant has a square root, make each of these four factors a square in $\mathbb{C}[t]$. They correspond to four distinct projective pairs. The result just proved forces $u,v$ to be constant, and the equation then forces $y$ to be constant as well. This proves the nonparametrizability of an elliptic curve.

A sequence of real orthogonal polynomials consists of real polynomials $p_n$ with degree of a polynomial $n$ andOrthogonality is relative to the specified inner product, rather than to the ordinary coefficients. A monic polynomial has leading coefficient one, so a monic orthogonal polynomial has the form $p_n(x)=x^n+\text{terms of lower degree}$. In particular, the monic degree-zero polynomial is $p_0=1$.

Since $x{p}_n-p_{n+1}$ has degree of a polynomial at most $n$, expand it in the basis $p_0,\dots ,p_n$. Multiplication by $x$ is self-adjoint for this weighted inner product: $⟨xp,q⟩=⟨p,xq⟩$. For $k\le n-2$, the polynomial $x{p}_k$ has degree at most $n-1$, soOnly the $p_n$ and $p_{n-1}$ coefficients remain. Taking their inner products gives the three-term recurrenceFor the second formula, $x{p}_{n-1}=p_n+$ a polynomial of lower degree, hence $⟨x{p}_n,p_{n-1}⟩=⟨p_n,x{p}_{n-1}⟩=⟨p_n,p_n⟩$. At $n=0$, take $p_{-1}=0$, ${\beta }_0=0$ and the same formula for ${\alpha }_0$. Positivity of the weight ensures that all the squared norms in the denominators are nonzero.

For a basis $v_1,\dots ,v_d$ of the real vector space $V$, the Gram-Schmidt process constructs an orthonormal basis successively:The inner product makes $w_j$ orthogonal to all earlier $e_i$. Moreover $w_j\ne 0$, since otherwise $v_j$ would be a linear combination of its predecessors, contrary to linear independence. Induction gives $\mathrm{span}(e_1,\dots ,e_j)=\mathrm{span}(v_1,\dots ,v_j)$. Starting with a basis of a linear subspace $U$ and extending it to a basis of $V$ gives the same construction with the first $r=\dim U$ vectors spanning $U$.

The orthogonal complement is $U^{\perp }=\{v\in V:⟨v,u⟩=0\text{ for every }u\in U\}$. For every $v\in V$, set $u={\sum }_{i=1}^r⟨v,e_i⟩e_i$. Then $u\in U$ and $v-u\in U^{\perp }$. If $w\in U\cap U^{\perp }$, then $⟨w,w⟩=0$, so $w=0$ by definiteness of the inner product. Thus the direct sum isThis also covers $U=0$ and $U=V$.

For the polynomial space, the form is immediately a symmetric bilinear form, and $(f,f)=f(1{)}^2+f(2{)}^2+f(3{)}^2\ge 0$. A nonzero polynomial of degree of a polynomial at most two cannot have three distinct roots of a polynomial, so this form is an inner product for $n=1,2$. For $n\ge 3$, the nonzero polynomial $(x-1)(x-2)(x-3)$ has $(f,f)=0$. Therefore, among the stipulated positive integers,

The original PDF contains this subpart; the local TeX has omitted it. Write $a_n$ for the leading coefficient of $P_n$. The Legendre polynomial recurrence relation and the starting polynomials give $a_0=a_1=1$, and induction givesIndeed, $x{P}_n$ has degree of a polynomial $n+1$, while $P_{n-1}$ has smaller degree of a polynomial and cannot cancel its leading term. HenceAt $x=1$, the same linear recurrence relation gives $(n+1)P_{n+1}(1)=(2n+1)P_n(1)-n{P}_{n-1}(1)$. Starting from $P_0(1)=P_1(1)=1$, induction yields

Suppose $X=f_1\cdots f_s$ were a product of irreducible elements of $R$. Since degree of a polynomial is additive under products, exactly one factor has positive degree and all the others are constant. By the preceding classification, the positive-degree factor has constant term $\pm 1$, while every constant irreducible is $\pm p$ for a prime $p$. Their product therefore has a nonzero constant term, contradicting $X(0)=0$.

Thus $X$ is not a product of irreducibles, so this integral domain is not an atomic domain and in particular is not a unique factorization domain.

Let the smooth projective curve be the projective completion of $f(x,y)=0$, of degree $d$, and suppose after interchanging $x$ and $y$ if necessary that $f_y=\partial f/\partial y$ is nonzero. A basis of its holomorphic differential forms isEquivalently one may use $-x^i{y}^{j}dy/f_x$. These expressions agree on their common domain because differentiating $f(x,y)=0$ gives $f_{x}dx+f_{y}dy=0$. The allowed monomials are precisely the homogeneous polynomials of degree at most $d-3$, in accordance with the adjunction formula $K_C\cong {\mathcal{O}}_C(d-3)$.