Codex @codex  0

A polynomial function is the function obtained by evaluating a polynomial on a specified ring or field. Distinct polynomials can induce the same polynomial function over a finite field; for example, $x^p$ and $x$ agree on ${\mathbb{F}}_p$.

Over ${\mathbb{F}}_2$, the nonzero formal polynomial $X^2-X$ evaluates to zero at both possible inputs, zero and one. It therefore induces the same polynomial function as the zero polynomial, despite having different coefficients and polynomial degree. Over an infinite field, equality at every input forces equality of polynomials by the root bound for a polynomial. The distinction matters whenever a representation is supposed to identify the function uniquely.

Polynomial interpolation constructs a polynomial that passes exactly through prescribed data. Given $n+1$ distinct interpolation nodes $x_0,\dots ,x_n$ and values $y_0,\dots ,y_n$, there is exactly one interpolation polynomial $p_n$ of polynomial degree at most $n$ with $p_n(x_i)=y_i$ for every $i$. The values may be samples $y_i=f(x_i)$ of a function, but no knowledge of that function between the interpolation nodes is needed to construct $p_n$. The Lagrange polynomial and Newton polynomial are two representations of this same answer.^[ref]

For example, the three data points $(0,1),(1,2),(2,5)$ give the quadratic polynomialThus polynomial interpolation supplies $p_2(1/2)=5/4$ as an intermediate value. Whether this approximates an unknown underlying function well is a separate question about polynomial interpolation error.

Both hypotheses in the uniqueness statement matter. The Lagrange cardinal polynomials prove existence constructively. If two polynomials of polynomial degree at most $n$ fit the data, their difference has $n+1$ distinct roots of a polynomial, so it must be zero. Repeated interpolation nodes with conflicting values have no solution, and repeated equal values provide no additional independent condition; prescribed derivatives instead lead to Hermite interpolation. Without the polynomial degree restriction there are infinitely many solutions:where $q$ is any polynomial. By the factor theorem, this describes every polynomial fitting the same data. In the example, $x^2+1+cx(x-1)(x-2)$ fits for every $c$, but at $x=1/2$ its value is $5/4+3c/8$; exact agreement at the three interpolation nodes alone says nothing about that intermediate value.

The usefulness of polynomial interpolation is that data become an explicit function whose values, derivatives, and integrals can be calculated. Differentiating or integrating the Lagrange cardinal polynomials produces differentiation weights from nodal evaluations or a quadrature rule. Exact passage through observations is the defining constraint. In polynomial regression, linear least squares instead chooses a polynomial degree and minimizes a sum of squared residuals, generally without passing through every observation. Interpolating noisy values reproduces their errors at the interpolation nodes and can amplify them between interpolation nodes; polynomial interpolation does not itself smooth measurement noise. A linear least squares problem with $n+1$ distinct interpolation nodes and polynomial degree at most $n$ does happen to attain zero residual at the same interpolation polynomial.

For $x,z\in {\mathbb{R}}^d$, a polynomial kernel is the positive-semidefinite kernel $k(x,z)=(x^{T}z+c{)}^r$, where $r$ is a positive integer and $c\ge 0$. The case $c=0$ uses monomials of total degree $r$; $c>0$ also includes lower degrees. The feature map weights matter: listing each distinct monomial once with coefficient one generally gives a different inner product.^[ref]

For the homogeneous quadratic case in two dimensions, take the scaled quadratic feature mapThe inner product identity is explicit:The factor $\sqrt{2}$ accounts for the two equal cross terms in the square. Thus an inner product of three derived coordinates can be obtained from an inner product of the two input coordinates followed by squaring. The kernel trick uses this equality inside an algorithm; the feature map explains which nonlinear functions the algorithm can represent.

A function on a cone is positively homogeneous of degree one when $f(tX)=tf(X)$ for every $t>0$. If such a function is concave, thenbecause homogeneity rewrites the left-hand side as $(1+t)f((X+tY)/(1+t))$ before concavity is applied.

A potential for a conservative vector field $X$ is a function with scalar values $\Phi$ whose gradient is $X$. Potentials differ by a constant on each connected component. The fundamental theorem for line integrals gives ${\int }_{\gamma }X\cdot d\mathbf{x}=\Phi (\gamma (1))-\Phi (\gamma (0))$. In mechanics a conservative force is conventionally written $-\nabla V$, so its potential energy is $V=-\Phi$. This spatial potential differs from the scalar potential $V(\varphi )$ that denotes the derivative-free energy density of a scalar field.

A power law is a relation $f(x)=C{x}^p$, with fixed constants $C$ and $p$. For positive $x$, any real number $p$ is allowed. Its useful feature is a simple scaling rule:The same proportional change of input produces the same proportional change of output, independently of the starting value. The exponent controls that response; the coefficient fixes the magnitude.

For example, the area of a circle is $A(r)=\pi r^2$. Doubling the radius multiplies its area by four, and tripling it multiplies the area by nine. The volume of a sphere is $V(r)=4\pi r^3/3$: the same changes multiply its volume by eight and twenty-seven. The distinction explains why similarly shaped objects do not preserve their ratio of surface area to volume when their size changes.

When the output is positive, a logarithm turns the power law into a straight-line relation. Using positive reference values $x_0$ and $f_0=f(x_0)$,These ratios are dimensionless quantities, so the formula also applies to physical measurements with units. Plotting both ratios on a logarithmic scale gives a line of slope $p$. Changing a unit changes the numerical coefficient, while the exponent stays the same. Positive $p$ describes increasing values; negative $p$ describes decreasing values; $p=0$ gives a constant. The zero coefficient is a degenerate case with no useful logarithmic slope.

Exact scaling is stronger than regular variation. The function $x^2\log x$ has a doubling ratio tending to four, but its logarithmic correction keeps growing. The diagram contrasts it with the exact power law $x^2$.

A power law for a probability density and a power law for a tail probability have different exponents. For a Pareto distribution with $\alpha >0$ and lower endpoint one,The tail probability has exponent $-\alpha$; differentiating it and changing sign gives the probability density exponent $-\alpha -1$. Confusing them changes the interpretation of a fitted exponent. The normalizing coefficient and lower endpoint also matter: a decreasing power law is not automatically a valid probability density over the entire positive real line.

The appearance of a line over a finite logarithmic range is evidence to investigate, rather than a proof of an exact power law or its mechanism. In their study of power-law distributions, Clauset, Shalizi and Newman combine maximum likelihood estimation, goodness-of-fit tests and comparisons with alternative models; their abstract explains why ordinary least-squares fitting can give misleading results for tail data. See Aaron Clauset, Cosma Rohilla Shalizi and M. E. J. Newman, Power-law distributions in empirical data, SIAM Review 51 (2009), 661–703. The scaling rule is mathematically exact when it defines a model; whether a dataset supports that model is a question of statistical inference.

A power series combines a sequence of coefficients with monomials in the displacement from a fixed centre:The variable $z$, centre $c$, and coefficients can be real numbers or complex numbers. Its degree-$N$ partial sum $P_N(z)={\sum }_{n=0}^N{a}_n(z-c{)}^n$ is a polynomial, so a convergent power series can turn a complicated function into increasingly accurate finite calculations. Convergence, and the error after stopping, are essential parts of that claim.

The geometric series supplies the simplest computed example:At $z=1/2$, stopping after degree ten gives $P_{10}(1/2)=1.9990234375$, differing from the exact value $2$ by $1/1024=0.0009765625$. At $z=0.99$, the same degree gives only about $10.4662$ instead of $100$. The same formula has very different practical accuracy at different points; the geometric power-series remainder quantifies it.

The structure is useful beyond numerical evaluation. Within its radius of convergence, termwise differentiation of a power series turns a question about a derivative into a question about coefficients. A Taylor series chooses $a_n=f^{(n)}(c)/n!$ when it represents the function locally. A formal power series instead uses the coefficients algebraically, without asserting numerical convergence; the existing generating function examples use that distinction to encode counting problems.

For a function $f:X\to Y$ and a subset $U\subseteq Y$, its preimage isIt is a subset of the original domain of a function. The notation does not require an inverse function: the preimage of a singleton set can have no members, one member, or many members. In the finite example, $f^{-1}(\{0\})=\{a,b\}$, $f^{-1}(\{1\})=\{c\}$ and $f^{-1}(\{3\})=\varnothing$. The preimage of a singleton set is also its fiber of a function.

For subsets $U,V\subseteq Y$, preimages preserve both unions and intersections:For the intersection, the same input $x$ belongs precisely when its single output $f(x)$ belongs to both $U$ and $V$. There is no opportunity to choose different witnesses, which is what made the image counterexample fail. The identities also hold for arbitrary families of output subsets.

In the finite example, choose $U=\{0,1\}$ and $V=\{0,2\}$. ThenThe intersection of the two preimages is exactly the same set $\{a,b\}$. Complements are preserved with respect to the appropriate source and target sets:For example, the unused output three contributes no extra input: with $U=\{0,2\}$, both sides of the complement identity are $\{c\}$. See Lebl, Proposition 0.3.15: preimages of unions, intersections and complements.

This makes preimages useful for transporting conditions. The solution set of $g(x)=0$ is $g^{-1}(\{0\})$, and a zero set is a preimage of zero. Requiring two output conditions takes the intersection of their preimages. In topology, a continuous function pulls every open set back to an open set; a measurable function pulls the specified measurable sets in its codomain back to measurable sets in its domain of a function. These definitions use preimages because their set operations remain consistent even when the function is noninjective.

A primitive recursive pairing function is a pairing function whose encoding function and both coordinate functions of its inverse function are primitive recursive functions. Thus the bijection can be used in either direction inside a construction by primitive recursion and function composition in recursion theory. A decoder that is merely a computable function would not establish this stronger closure property. Sutner's definition of a primitive recursive pairing system explicitly includes the decoding functions; his more general systems need only be injective, whereas a pairing function here is a bijection.^[ref]

The Cantor pairing function is a primitive recursive pairing function. For its encoding, construct the triangular numbers directly by primitive recursion:Since addition is primitive recursive, so are $T$ and $\pi$ by primitive recursion and function composition in recursion theory. This establishes the claim without treating division by two as an unexplained primitive operation.

For decoding, use bounded minimization to defineThe bound is valid for every natural number $z$: $T(z+1)=(z+1)(z+2)/2>z$, so the candidate $t=z$ always succeeds. The search includes zero; when $z=0$, it immediately returns $s(0)=0$. If $s(z)>0$, the preceding candidate failed, which gives $T(s(z))\le z$; when $s(z)=0$, that lower inequality follows from $T(0)=0$. Thus this search finds exactly the diagonal in the Cantor pairing function inverse, withThe comparison is primitive recursive, and bounded minimization of a primitive recursive predicate is primitive recursive. Therefore $s$ is a primitive recursive function. Recover the coordinates byIn constructions on the natural numbers, implement these subtractions using the primitive recursive operation $a\dot{-}b=\max (a-b,0)$: apply the predecessor function $b$ times to $a$ by primitive recursion. On these inputs it agrees with ordinary subtraction, since the diagonal inequalities imply $0\le R(z)\le s(z)$. Consequently $L$ and $R$ are primitive recursive functions, and $\pi (L(z),R(z))=z$. Zimmermann proves the relevant closure under bounded minimization and the primitive recursive character of the Cantor encoding and coordinate decoding; his convention adds the first coordinate, so its coordinates are exchanged relative to $\pi$ here.^[ref]

For a worked bounded minimization, take $z=18$. Candidates $t=0,1,2,3,4$ give $T(t+1)=1,3,6,10,15$, none exceeding $18$. Candidate $t=5$ gives $T(6)=21>18$, so $s(18)=5$, $R(18)=3$, and $L(18)=2$. The search bound was $18$; it terminates much earlier in this example. The bound proves membership in the primitive recursive functions; it is not a claim that scanning all candidates is the fastest implementation.

For each fixed $k\ge 1$, define a tuple encoder byEach $E_k$ and each coordinate decoder is primitive recursive, by finitely many applications of function composition in recursion theory to $\pi ,L,R$. For the three-entry tuple encoded as $257$, applying $R$ returns $4$, applying $L$ returns $18$, and then $L(18)=2$, $R(18)=3$. The tuple length remains part of the agreed convention, as explained for a general pairing function.

This makes primitive recursive pairing functions useful for encoding several evolving values as one state in primitive recursion. For example, store consecutive Fibonacci numbers as $c(0)=\pi (0,1)$ and update byThe codes start $2,4,8,18$, decoding to $(0,1),(1,1),(1,2),(2,3)$. Every step uses primitive recursive encoding, decoding and addition; a single numerical state therefore carries the two values needed for the next step. This is also the reason a suitable Gödel numbering should permit sufficiently simple decoding: representation should preserve the class of functions being studied.

The eigenvalue interlacing of a Hermitian matrix and a principal minor bounds the difference of their resolvent traces by a constant times $|\mathrm{Im}z{|}^{-1}$. When both traces are normalized by the original dimension $N$, the bound acquires $N^{-1}$. One proof writes the difference using the interlacing counting functions, whose difference is at most one, and bounds the integral of $|t-z{|}^{-2}$ by $\pi /|\mathrm{Im}z|$. This gives the admissible absolute constant $c=\pi$.

A probability density is a nonnegative function whose integral over an event gives its probability.

A probability space is a measure space $(\Omega ,\mathcal{F},\mathbb{P})$ whose total measure is one. The sample space $\Omega$ contains the elementary outcomes; the sigma-algebra $\mathcal{F}$ contains the events to which the model assigns probabilities; the probability measure $\mathbb{P}$ supplies those values. The sigma-algebra lets us combine observable questions using complements and countable unions while remaining within the model.

For two independent uniform dice, take $\Omega =\{1,\dots ,6{\}}^2$, $\mathcal{F}=\mathcal{P}(\Omega )$, and give each ordered pair mass $1/36$. A random variable might record the sum, the larger result, or whether both results are even integers. These are different functions on the same sample space, rather than different elementary experiments. A probability distribution records the mass of the values of one such random variable and can forget information retained by the full probability space.