Polynomial division Created 2026-09-24 Updated 2026-10-18
Polynomial division separates a polynomial into a multiple of a chosen divisor and a smaller polynomial remainder. Given over a field , with , there are unique polynomials satisfyingHere is the polynomial quotient. The bound concerns polynomial degree, rather than the sizes of the coefficients.[ref]
Fields and Galois Theory by James S. Milne. Fields and Galois Theory, version 5.10, Chapter 1, p. 10, §1.6: division algorithm, zero remainder alternative and uniqueness
For an original example over the rational numbers, takePolynomial long division first cancels by subtracting :Subtracting one more copy of cancels :ThusThe final polynomial remainder has polynomial degree one, below the divisor's polynomial degree two. Multiplying out the last identity checks every coefficient, including the constant term .
The polynomial degree bound makes this decomposition useful: it replaces a potentially long polynomial with a short polynomial remainder whenever multiples of can be discarded. At any root of a polynomial of , those multiples vanish under polynomial evaluation. Repeated polynomial division also drives the Euclidean algorithm for finding a greatest common divisor of polynomials.
The coefficient setting matters. Over a commutative ring, the same existence and uniqueness hold when the divisor's leading coefficient is a unit in a ring. A monic polynomial therefore works over the integers, even though they do not form a field; monic polynomial division over a ring explains why zero divisors cause no difficulty in that case.[ref]
Chapter 3 Ring theory. Abstract Algebra, Chapter 3 Ring theory, §3.9, Theorem 3.9.1: division with a unit leading coefficient
A nonzero divisor alone is insufficient over the integers. Dividing by with an integer polynomial quotient and a constant polynomial remainder would require for an integer , which is impossible. Over the rational numbers the division instead givesThe obstruction is the nonunit leading coefficient . This example separates existence from uniqueness: over an integral domain, the polynomial degree argument still makes any admissible pair unique, if it exists.
Polynomial function Created 2026-10-03 Updated 2026-10-14
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, and agree on .
Over , the nonzero formal polynomial 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 identity testing Created 2026-09-24 Updated 2026-10-18
Polynomial identity testing asks whether a polynomial represented implicitly, such as by an arithmetic circuit or a remainder computation, is the zero polynomial.
Here zero means that every coefficient vanishes after collecting equal monomials in the polynomial ring. Testing equality of two polynomials amounts to testing for zero. An arithmetic circuit can permit cheap polynomial evaluation even when expanding all monomials is expensive. The random evaluation test for a polynomial identity exploits this: one nonzero value disproves the polynomial identity, while a known total degree limits how often a nonzero polynomial can evade detection.[ref]
Lecture 9: Polynomial Identity Testing by the Schwartz-Zippel Lemma. CPSC 536N: Randomized Algorithms; Lecture 9: Polynomial Identity Testing by the Schwartz-Zippel Lemma, §1: formal zero means all coefficients vanish; representations and evaluation access
For example, for an integer , has distinct monomials, one for each subset of the variables. Its factored expression needs only additions and multiplications for one polynomial evaluation. Evaluating the compact expression avoids creating its expanded list of coefficients. The saving is especially attractive in many variables; it does not make a zero result into a proof of identity.
Work in the finite field , using modular arithmetic modulo five. Consider the two original polynomial examplesThe distributive property gives , so all coefficients of cancel: is identically zero. In contrast, in this finite field, with nonzero leading coefficient. Its roots of a polynomial are exactly one and two: a product in a field is zero only if a factor is zero.
The complete polynomial evaluations, displayed as representatives modulo five, areIn particular, is a nonzero witness, which disproves identity without examining other points. At one or two, a zero value fails to reveal that is nonzero. A random variable with a uniform distribution on a finite set hits those two polynomial roots with probability .
A crucial limit appears with . Its coefficients make it a nonzero polynomial of polynomial degree five in , yet direct polynomial evaluation gives zero at all five field elements: the values before reduction are , all divisible by five. Thus induces the same polynomial function as the zero polynomial. Any number of trials restricted to will falsely accept this identity. This is compatible with the Schwartz-Zippel lemma: the ratio of polynomial degree to sampling-set size is , which gives no useful guarantee.
When a polynomial's representation permits polynomial evaluation over a larger field extension, a larger sampling set can restore the useful degree ratio. Access only to the induced polynomial function on the original finite field cannot distinguish from zero.[ref]
Lecture 9: Polynomial Identity Testing by the Schwartz-Zippel Lemma. CPSC 536N: Randomized Algorithms; Lecture 9: Polynomial Identity Testing by the Schwartz-Zippel Lemma, §1.4: formal nonzero polynomials can vanish everywhere on a finite field; extension-field evaluations need a suitable representation
Positive lacunary trigonometric series 2026-10-14
For an odd integer and positive summable coefficients , the Weierstrass M-test makes continuous. Its partial sum over is the unique best uniform approximation by degree-at-most- trigonometric polynomials, for . If is the first omitted frequency, at every omitted cosine equals because all frequency ratios are odd. Thus the tail attains alternating extrema equal to its coefficient sum at points. The trigonometric Chebyshev alternation theorem proves the formula. For , , the largest decay exponent is .
Power series Created 2026-09-24 Updated 2026-10-14
A power series combines a sequence of coefficients with monomials in the displacement from a fixed centre:The variable , centre , and coefficients can be real numbers or complex numbers. Its degree- partial sum 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 , stopping after degree ten gives , differing from the exact value by . At , the same degree gives only about instead of . 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 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.
Prime-power contraction in a formal group 2026-10-31
Let be the valuation ring of a complete non-Archimedean valued field whose residue field has characteristic , and let . For a one-dimensional formal group law over , repeated addition gives with . Hence . The series converges for because its coefficients are bounded and .
For and , choose . The values remain in the ball , so . Associativity identifies . The argument also works in equal characteristic , where the linear coefficient vanishes, and does not require a discrete valuation. It proves contraction of prime-power multiplication near the formal identity without assuming a characteristic-zero formal logarithm.
For prime , a graph with edges and maximum degree at most contains a nonempty -regular subgraph. Over , apply the Combinatorial Nullstellensatz on the Boolean edge-variable cube toIts full squarefree coefficient is nonzero because the first product has degree below . A nonzero value cannot occur at the zero vector; at any other Boolean vector the second product vanishes, and the first forces all selected degrees to be multiples of . The maximum-degree condition makes every positive selected degree exactly .
Probability generating function of an independent random sum Created 2026-10-18 Updated 2026-10-25
Let be a nonnegative integer-valued random variable, and let be nonnegative integer-valued independent and identically distributed random variables, with common probability generating function . Require the whole sequence to be independent of , so are jointly independent. Set the random sumwith the empty sum equal to zero. Given , the probability generating function of an independent sum yields the conditional expectation . By the law of total expectation,The composition is valid because . Merely making the independent of each other does not preserve their conditional laws when depends on them. This is the probability generating function version of transform composition for an independent random sum.
For a Poisson distribution count with mean , substitution into gives a compound Poisson distribution withIf the jumps have finite second moment, conditioning also gives mean and variance . The extra spread comes from randomness in the count as well as randomness in the jumps.[ref]
Random: Probability, Mathematical Statistics, Stochastic Processes by Kyle Siegrist. The Poisson Process, Compound Poisson Processes, Definition; Properties: mean, variance, and generating-function conditioning proof; Compound Poisson Distributions: count independent of the sequence
For an original example, choose and jumps taking values one and two with equal probability. Keep the independence assumptions above. ThenHere , , and . The law of total expectation and law of total variance giveThus the aggregate is not itself a Poisson distribution, whose mean and variance would coincide.
To recover the probability mass function without repeated differentiation, use and compare coefficients:For example, . As an independent check, expanding gives
The plotted probability masses stop at 20, although the support of a probability distribution is unbounded. The omitted tail probability isThis model has bounded jumps and an unbounded count. Its entire probability generating function does give a finite moment-generating function at every real argument, but the general random sum composition only guarantees the stated domain.
For nonnegative integer-valued independent random variables , factor the expected value of a product:The Cauchy product explains what this means for individual probability masses:Every way of splitting the total contributes once. This is convolution of independent random variables; multiplying probability generating functions performs the bookkeeping automatically.
For an original example, take independent and , using the Bernoulli distribution and binomial distribution. ThensoDirect enumeration of the six pairs gives the same probability masses. For example, total one collects and , with contributions . The coefficients sum to one. The expected value is ; since , the variance is , agreeing with .
Uncorrelated random variables are insufficient for the product identity. For a concrete counterexample, let be uniform on and set , . Then , but , whereas . Zero covariance controls one mixed moment, not the full joint probability mass function.
QR decomposition Created 2026-09-24 Updated 2026-10-14
A reduced QR decomposition of an matrix over the real numbers with full column rank, , writes , where is with orthonormal columns and is a upper triangular matrix with positive diagonal. Applying the Gram-Schmidt process to the columns of constructs and records the coefficientsThis last column identity is exactly the matrix multiplication . The upper triangular matrix records that the th input uses only the first new directions, while its positive diagonal records the norms of the nonzero orthogonal projection residuals. Since , one also has ; denotes the transpose and the identity matrix. Over the complex numbers, use the conjugate transpose in these identities.
For the three-dimensional Gram-Schmidt process example, the exact matrices areFor example, the last column reconstructs asThe diagonal entries are approximately . Each is a norm of the new direction before it was scaled to length one.
The computed QR factorization: input matrix , orthonormal columns of , and the upper triangular matrix of orthogonal projection coefficients
. Details. For a linear least-squares problem, the orthogonal projection of onto the column space of is . Hence the minimizing coefficients solve the linear system by back substitution. Let consist of the first two columns of the example; its reduced factors are and the leading block of . For , the linear system isThus , agreeing with the orthogonal projection computed above, and the minimum Euclidean norm of is . The QR decomposition separates building an orthonormal basis from recovering coefficients in the original basis.[ref]
https://ocw.mit.edu/courses/18-065-matrix-methods-in-data-analysis-signal-processing-and-machine-learning-spring-2018/resources/lecture-9-four-ways-to-solve-least-squares-problems/. Strang, MIT 18.065, Lecture 9: Four Ways to Solve Least Squares Problems
QR decomposition by Givens rotations Created 2026-09-24 Updated 2026-10-14
Successive Givens rotations eliminate entries below the diagonal of a matrix. For an matrix with , process columns ; within column , rotate rows for each whose entry needs elimination. Apply each Givens row-pair update to columns . Both rows are zero in earlier columns, so these operations preserve earlier eliminations. No assumption of full column rank is needed to perform the eliminations.
For a concrete example, takeFirst use , then :The entry in position was already zero, so its elimination was skipped. The second Givens rotation combines the remaining pair in column two. This yields the full QR decompositionThe first two columns of and first two rows of give the reduced QR decomposition. Direct multiplication verifies both and . For these displayed factors evaluated in binary64 floating-point arithmetic, the Frobenius norms and are both below ; these measure reconstruction and loss of orthogonality separately.
More generally, if the chronological rotations are , thenEach factor is an orthogonal matrix, so is too. For a rectangular matrix, has zeros below its diagonal; its leading block is an upper triangular matrix. With full column rank, retaining the first columns of gives orthonormal columns. To impose a positive diagonal when necessary, flip matching columns of and rows of , preserving their product.
For a linear least-squares problem, apply the same chronological Givens rotations to the right-hand side , obtaining , without explicitly constructing . Since the Euclidean norm is preserved, solve the leading upper triangular matrix system by back substitution when has full column rank; the remaining entries of give the minimum residual norm. In the example, gives , , and minimum residual Euclidean norm .
The locality is useful for a sparse matrix or an existing QR decomposition needing an extra row: only two rows change at each step, and the new row can be eliminated against the stored upper triangular matrix. For an factor, this extra-row procedure takes rotations and arithmetic operations. Locality does not guarantee preservation of sparsity: mixing rows can create nonzeros wherever either row had one. For a fully populated input, the straightforward elimination uses rotations, each touching columns, giving work. Storage layout, zero patterns and implementation affect speed; this count alone establishes no universal advantage over other QR decomposition algorithms.
The Euclidean norm preservation explains the appeal for numerical stability: exact rotations do not amplify a perturbation's length. Rounded coefficients and Givens row-pair updates still introduce roundoff error. Small reconstruction and orthogonality residuals check the computed factors, while the condition number of the original problem still controls how accurately a linear least-squares problem determines its solution.
For the displayed nonlinear diffusion equation, a quadratic ansatz reduces the partial differential equation exactly toIndeed , and equality of the constant and quadratic coefficients proves the reduction. For nonzero curvature, integration gives . On , the remaining linear ordinary differential equation is , whose integrating factor is . Thus, including spatial translation,All three constants are arbitrary, on a domain with . When the quadratic coefficient vanishes, the more general affine ansatz gives .
A narrower ansatz fixes two coefficients together and permits exactly or . The zero value of is a valid spatially constant branch, not an algebraic exception to discard. These finite-parameter families are exact solutions; they are not the complete general solution of the nonlinear partial differential equation, and their sums need not be solutions.
Radius of convergence Created 2026-09-24 Updated 2026-10-14
The radius of convergence of is the unique separating interior absolute convergence from exterior divergence. It converges absolutely when and diverges when . At the centre it always has the finite value , since all positive powers vanish. The boundary convergence of a power series is a separate question.
For , the interior is a disk in the complex plane and an open interval on the real line. A power series converges uniformly on every smaller closed disk . This gives stable polynomial approximation over a whole compact region, rather than a separate limiting calculation at each point. See Jiří Lebl, Basic Analysis, §11.3.2: convergence of power series.
Four examples reveal what measures:
- has , since its coefficients have constant magnitude one.
- also has : a factor changes boundary behaviour without changing the limiting coefficient-root growth.
- has . The ratio test gives successive term ratio for every fixed , producing the exponential function.
- has . For any , successive term magnitudes have ratio , so the terms do not tend to zero.
The Cauchy-Hadamard theorem computes directly from the coefficients. The attractive feature is that one growth statistic decides convergence throughout the interior and exterior, including sparse series with many zero coefficients. Finite changes to the coefficients do not alter the radius, though they can change the sum.
Rank-one spectral-factor Gram matrix 2026-10-06
For coefficient column , is a Hermitian matrix and a positive semidefinite matrix because . Expanding on the unit circle gives coefficient . Thus has matrix rank one when and zero otherwise. General feasible Gram matrices need not have matrix rank one.
Rational homotopy group Created 2026-09-24 Updated 2026-11-05
For , the rational homotopy group of a based topological space is the vector spaceHere is an abelian group, so this tensor product is defined. For a finitely generated abelian group with finite, the result is : finite-order classes disappear and the free generators acquire rational coefficients. More generally every torsion element maps to zero, since implies for .
For example, gives , whereas becomes zero. The general tensor product definition also handles groups that are not finitely generated: for an Eilenberg–MacLane space , its degree- rational homotopy group is still .
For a simply connected CW complex, these vector spaces are the homotopy groups of its rationalization of a topological space. An arbitrary nonabelian fundamental group cannot be tensored with by this abelian group formula; the nilpotent-group localization used more generally in rational homotopy theory is a separate construction.
Reciprocal-conjugate root pairing 2026-10-06
For a nonzero real-on-the-circle trigonometric polynomial of actual order , the polynomial satisfies . Its constant term is the nonzero conjugate of its leading coefficient. Hence its nonzero roots of a polynomial occur in pairs with the same multiplicity of a root. The coefficient reversal and complex conjugation preserve the exponents of the paired factors. Fixed roots of a polynomial on the unit circle require nonnegativity, rather than this symmetry alone, to have even multiplicity.
Redistribution of polynomial factors for dice Created 2026-10-14 Updated 2026-11-05
Encode a fair die with face labels by . Its probability generating function is . Two independent dice with polynomials have the same sum probability distribution as another pair if and all four dice have faces. Redistributing polynomial factors can construct unexpected examples, but each resulting polynomial must have nonnegative integer coefficients, no constant term if labels must be positive, and value at . For example, reallocating from one copy of to the other gives face labels and .
Repeated roots in Vieta's formulas 2026-10-18
For the polynomial , the root list is , not . Its elementary symmetric polynomials areThe zero coefficient of is accounted for by the cancellation in . Omitting one occurrence of the double root of a polynomial loses both the polynomial degree and the correct coefficients. Multiplicity of a root is part of the root data.
Suppose in . Put and , and choose of size . Let . If the restricted sumset fits in a set of size , then vanishes on . Its coefficient of isAll factorial arguments are below and . The Combinatorial Nullstellensatz gives a contradiction. Since , this includes the saturated case as well as the small-set case.





