Agrawal–Biswas primality test Created 2026-09-24 Updated 2026-11-05
The Agrawal–Biswas primality test tests a formal polynomial identity in :For , the identity holds exactly when is a prime number. Testing a formal polynomial is stronger than evaluating it at residues.
The randomized algorithm first handles prime numbers at most thirteen, divisibility by them, and perfect powers. For remaining , choose a monic polynomial of polynomial degree , with independent uniform lower coefficients modulo . Compute the remainder of modulo using exponentiation by squaring. A nonzero remainder proves compositeness. The monic polynomial permits division even when the coefficient ring has zero divisors.
Every prime number passes. After preprocessing, a composite number is rejected with probability at least per trial, so independent trials give error at most . Keeping remainders below polynomial degree makes the computation polynomial time in the bit length of .[ref]
Algebraic integer Created 2026-09-24 Updated 2026-10-13
An algebraic number is an algebraic integer if it is a polynomial root of a monic polynomial with integer coefficients:Equivalently, its algebraic minimal polynomial over has integer coefficients. The requirement that the leading coefficient be one matters: satisfies and is an algebraic number, but is not an algebraic integer. In fact the rational numbers that are algebraic integers are exactly the integers.[ref]
Some useful computed examples are:
- satisfies .
- satisfies .
- satisfies , although its displayed coefficients in the basis are not integers.
- has algebraic minimal polynomial , so it is not an algebraic integer even though it satisfies .
Algebraic integers are closed under addition, subtraction, and multiplication. Thus they provide an arithmetic ring, while division is allowed only when the result is again an algebraic integer. The algebraic integer module criterion explains this closure without having to find a new polynomial for every sum and product.
BCH code Created 2026-09-24 Updated 2026-11-05
Let be a finite field, let be coprime to , and choose an element of multiplicative order in an field extension. A BCH code of length , starting exponent , and design distance is the cyclic code whose generator polynomial of a cyclic code iswhere is the algebraic minimal polynomial of over . Equivalently, is the least-degree monic polynomial over the base finite field vanishing at consecutive powers. This least-degree condition distinguishes the BCH code from its proper cyclic code subcodes with additional zeros. The BCH bound gives minimum Hamming distance at least .
For example, over the field with two elements, let and let be a polynomial root of . The roots and have the same algebraic minimal polynomial, so and give , a Hamming code of length seven.[ref]
Shift-Register Synthesis and BCH Decoding by James L. Massey. Sections IV–V: BCH codes and synthesis-based decoding
Characteristic polynomial of a companion matrix Created 2026-10-31 Updated 2026-11-05
For a monic polynomial , use the companion matrix convention with ones on the subdiagonal and last column . In , the cofactors of the last-column entries, from top to bottom, are . This follows by expanding their bidiagonal minors: the subdiagonal factors cancel the cofactor signs. Laplace expansion along that column therefore gives . The degree-one case is the same identity for the one-by-one matrix .
Chebyshev polynomial Created 2026-09-24 Updated 2026-10-18
The first-kind Chebyshev polynomial converts a multiple-angle cosine into a polynomial:The cosine addition formula gives the recurrence relationThis constructs polynomials valid for every real , including outside , where the real-angle description is unavailable. For example,For , has polynomial degree and leading coefficient . On its uniform norm is one, even as its oscillations become more numerous.[ref]
https://dlmf.nist.gov/18.5#i. T. H. Koornwinder and collaborators, NIST Digital Library of Mathematical Functions, §18.5(i), equation 18.5.1: trigonometric representation
[ref]https://dlmf.nist.gov/18.9#i. Koornwinder and collaborators, NIST DLMF, §18.9(i), Table 18.9.1: recurrence coefficients
The polynomial roots of are especially simple:They correspond to equally spaced angles, but their locations in cluster near and . For , the polynomial roots are . For , the positive polynomial roots are approximately , with their negatives completing the set. The distance from the right endpoint to the nearest polynomial root is ; central neighboring polynomial roots are separated on the larger scale . The small change of cosine near angles zero and explains the clustering.
Analytical illustration of the eight roots of T8: equally spaced angles on a semicircle project to endpoint-clustered interpolation nodes
. Details. These polynomial roots supply interpolation nodes for a polynomial interpolation of polynomial degree at most . They differ from the Chebyshev-Lobatto nodes , which include both endpoints. This choice of polynomial roots has nodal polynomialThe monic Chebyshev extremal polynomial minimizes the uniform norm of this product among monic polynomials of polynomial degree on . Consequently, if has continuous derivatives, the usual polynomial interpolation error gives the useful boundThis optimizes the nodal factor in that bound, not the actual error for every function. Endpoint clustering helps control the large endpoint oscillations of equally spaced interpolation associated with Runge's phenomenon. The two node conventions and their geometric construction are discussed in Trefethen's authored text.[ref]
https://people.maths.ox.ac.uk/trefethen/ATAP/ATAPfirst6chapters.pdf. Lloyd N. Trefethen, Approximation Theory and Approximation Practice, Chapters 2–3 and Exercise 2.4: endpoint clustering, first-kind roots and polynomials
The same cosine substitution for polynomial approximation explains the weighted orthogonality:The endpoint singularities of the weight are integrable. Thus the Chebyshev polynomials are orthogonal polynomials for this weight, making coefficients in a least-squares polynomial in an orthogonal-polynomial basis separate cleanly. Their polynomial roots also give Chebyshev–Gauss quadrature, connecting polynomial interpolation to Gaussian quadrature.[ref]
Accuracy still depends on the target function. The absolute value function has a corner at zero, so the hypothesis requiring continuous derivatives in the displayed polynomial interpolation error bound fails. Endpoint clustering cannot remove that corner. A jump poses a stronger obstruction: polynomials are continuous functions, so they cannot converge in the uniform norm to a discontinuous function on the whole interval. Chebfun's documented examples show persistent overshoot for such jumps; these are a limitation of global polynomial interpolation, not a universal promise of rapid accuracy from Chebyshev polynomials.[ref]
https://www.chebfun.org/docs/guide/guide04.html#4.3. Chebfun development team, Chebfun Guide, §4.3: polynomial interpolation of discontinuous functions
Companion matrix Created 2026-09-24 Updated 2026-11-05
For a monic polynomial , its companion matrix represents multiplication by on the quotient module in the basis . With column vectors it has ones on the subdiagonal and last column . For example, . Transposing this matrix gives another common convention, so the subdiagonal convention should be specified when giving entries.
Completing the square Created 2026-09-28 Updated 2026-10-18
Completing the square rewrites a quadratic polynomial so that its minimum or maximum and its roots of a polynomial become easy to read. The linear term is absorbed into a shift of the variable; the resulting polynomial identity changes the description, rather than the values of the polynomial.
For coefficients in the real numbers, with ,First factor out the leading coefficient from , then add and subtract inside the bracket. The cross term in is , exactly the term needed. Multiplication by restores . Thus the half-coefficient is , rather than unless the quadratic polynomial is a monic polynomial. Expanding the right-hand side verifies the polynomial identity directly.[ref]
For an original example,For every in the real numbers, , with equality only at . The minimum is therefore , reached at ; no calculus is needed, and there are no roots of a polynomial in the real numbers. The expanded coefficients conceal these conclusions more effectively than the completed square does.
Conjugacy-class generating function for finite general linear groups Created 2026-10-14 Updated 2026-11-05
If counts conjugacy classes in , then . Associate a partition to each irreducible polynomial other than t. The Euler product over those polynomials counts monic polynomials with nonzero constant term and is .
CRC generator polynomial Created 2026-10-31 Updated 2026-11-05
The CRC generator polynomial is the agreed divisor used in a cyclic redundancy check. In the basic binary convention it is a monic polynomial of polynomial degree with . A nonzero error polynomial goes undetected exactly when .
This algebra gives useful detection guarantees. A single changed bit has and cannot be divisible by when . More generally, suppose the first and last changed bits span at most consecutive positions. Write with and . Since and are coprime polynomials, would imply , contradicting the polynomial degree bound. Every such error pattern is therefore detected.
If divides , every error changing an odd number of bits is also detected: its error polynomial satisfies , whereas every multiple of has value zero at .
Cyclic redundancy check Created 2026-10-31 Updated 2026-11-05
A cyclic redundancy check represents a bit string as a polynomial over the field with two elements and uses a polynomial remainder as checking information. Agree on a monic polynomial of polynomial degree with constant term . Under the basic systematic convention, a message polynomial producesHere , and addition equals subtraction over the field with two elements, so divides the transmitted polynomial . The receiver tests the polynomial remainder on division by the same CRC generator polynomial.
For example, and give and . If an error polynomial changes to , the error is undetected exactly when divides . Thus the CRC generator polynomial controls which bit-error patterns the cyclic redundancy check detects. This basic convention fixes the mathematics; implementations can additionally specify initial register contents and bit-order conventions.
Cyclotomic factorization Created 2026-09-24 Updated 2026-11-05
Partitioning the roots of by their exact orders givesInductively, the product over proper divisors is a monic polynomial in . Division of by this monic polynomial stays in and has zero remainder, proving that .
Cyclotomic polynomial Created 2026-09-24 Updated 2026-11-05
is the monic polynomial whose roots are the primitive th roots of unity. It belongs to and is irreducible over .
Eisenstein polynomial Created 2026-09-24 Updated 2026-11-05
For a discrete valuation ring with uniformizer , an Eisenstein polynomial is a monic polynomial whose nonleading coefficients are divisible by and whose constant coefficient is not divisible by . It is irreducible, and adjoining one of its roots gives a totally ramified extension.
Elementary symmetric polynomial Created 2026-09-24 Updated 2026-10-18
The th elementary symmetric polynomial adds every product obtained by choosing distinct positions from :The conventions are and for . The positions must be distinct, but their values may coincide. Each permutation of the variables merely rearranges the summands, so this is a symmetric polynomial.
For , , , we obtain , , and . Expanding the product givesIn general, . Thus the coefficients of a monic polynomial collect elementary symmetric polynomials of its roots of a polynomial, with alternating signs. These are the Vieta formulas.[ref]
Feedback-polynomial parity condition for maximal period Created 2026-09-24 Updated 2026-11-05
For a binary linear-feedback shift register of length , a feedback polynomial with maximal period cannot have as a polynomial root. A root at would make the nonzero all-one state fixed, whereas maximal period requires all nonzero states to lie in one cycle of length greater than one.
Writing the monic polynomial as , this givesOver the field with two elements, an even number of the feedback coefficients must therefore equal one, and has an odd number of nonzero coefficients. This is a necessary condition, not a sufficient test for a primitive polynomial. The restriction matters: for , has maximal nonzero-state period despite having as a polynomial root.
Finite-module criterion for integrality 2026-10-07
An element of an -algebra is an integral element precisely when is a finite -module. More generally, a finite -submodule containing one and stable under multiplication by proves integrality by the determinant trick. Conversely a monic polynomial equation reduces all powers of to finitely many generators.
Finite residue-field theorem for Gaussian integer orders Created 2026-10-05 Updated 2026-11-05
If is a Gaussian integer and is a nonzero prime ideal of , then is a finite field. Complex conjugation preserves , so a nonzero gives the positive integer . Primality supplies a rational prime . Since satisfies the monic polynomial , the ring is a quotient of and has at most elements. It is a finite integral domain, hence a field. The proof does not require to be a principal ideal domain.
Gaussian quadrature Created 2026-09-24 Updated 2026-10-14
Gaussian quadrature is a quadrature rule that chooses both sample locations and coefficients to achieve unusually high polynomial exactness. For a finite interval with , assume the integration weight is integrable and positive almost everywhere. DefineLet be the monic orthogonal polynomial of polynomial degree for the inner product : it satisfies for every polynomial of polynomial degree below . The polynomial roots of are distinct and inside ; take them as the nodes . Integrate the Lagrange cardinal polynomials to obtain . These coefficients are positive, andThe integration weight and the discrete coefficients play different roles: specifies the integral being approximated, while tell us how much each sample contributes.[ref]
https://dlmf.nist.gov/3.5#v. Nico M. Temme, NIST Digital Library of Mathematical Functions, §3.5(v), Gauss quadrature: nodes, coefficients and exactness
A proof outline explains the gain over simply integrating an arbitrary polynomial interpolation. Use polynomial division to write , with and . Orthogonality makes , and sampling at the polynomial roots of makes . The Lagrange cardinal polynomials recover exactly, so both expressions agree. Also , since has polynomial degree . This is the mechanism behind positive weights of Gaussian quadrature.
For a concrete two-node example, set on . The Legendre polynomial has polynomial roots . Its monic polynomial version has zero integral against both and , as required. Symmetry and exactness for the constant polynomial give . Thus the Gauss–Legendre instance of Gaussian quadrature isDirect evaluation on gives , exactly their integrals. For the polynomial , two samples therefore give exactly. But for the rule gives , whereas the integral is : the error is .
Analytical illustration of two-node Gauss–Legendre sampling: exact monomial integrals through degree three and failure at degree four
. Details. The ceiling is sharp for distinct real nodes under the positive-weight assumptions. Their squared nodal polynomial has polynomial degree , is zero at every sample, and has a strictly positive weighted integral. Thus no such quadrature rule integrates every polynomial of polynomial degree exactly. Nor does Gaussian quadrature integrate every nonpolynomial function exactly: the same two-node example gives , while .
Gaussian quadrature is useful when evaluations are costly and a modest polynomial captures the integrand well. More precisely, for a continuous function and any polynomial of polynomial degree at most , positivity and constant exactness giveThe uniform norm on measures the approximation between samples. This bound connects quadrature rule accuracy to uniform approximation, rather than promising an error from sample count alone. Corners, sharp unresolved features and roundoff error require their own assessment; the absolute value function example already shows why polynomial exactness is a qualified guarantee.
Integral element Created 2026-09-24 Updated 2026-11-05
An element of an -algebra is integral over when it satisfies a monic polynomial with coefficients in .
Irreducibility by degree-preserving reduction modulo a prime Created 2026-10-31 Updated 2026-11-05
Let be primitive polynomial and let be a prime number not dividing its leading coefficient. If its coefficientwise reduction is irreducible in , then is irreducible in . Indeed, a rational factorization would give an integer factorization by Gauss's lemma. The leading coefficients of both factors remain nonzero modulo , so reduction preserves their positive degrees, contradicting irreducibility of the reduction. For monic polynomials the leading-coefficient condition is automatic.


