raw Math
RAW Math Algebra Polynomials

Polynomial Square Roots

Robert Eisele

Taking the square root of a polynomial does not mean solving a polynomial equation. The roots of a polynomial are the values at which it vanishes; a polynomial square root is another polynomial whose square reproduces the entire original polynomial. Given

\[ f(x)=a_{2n}x^{2n}+a_{2n-1}x^{2n-1}+\cdots+a_1x+a_0, \]

the question is whether there is a polynomial

\[ g(x)=b_nx^n+b_{n-1}x^{n-1}+\cdots+b_1x+b_0 \]

such that

\[ \boxed{g(x)^2=f(x)}. \]

For example,

\[ 9x^2-30x+25=(3x-5)^2, \]

so both \(3x-5\) and its negative \(-3x+5\) are square roots. By contrast, \(x^2+1\) has no polynomial square root over \(\mathbb{R}\), even though it is positive for every real \(x\). Pointwise nonnegativity is necessary for a real polynomial square, but it is not sufficient.

When Does a Polynomial Square Root Exist?

Let \(K\) be a field and factor a nonzero polynomial in \(K[x]\) into monic irreducible factors:

\[ f(x)=a\,p_1(x)^{e_1}p_2(x)^{e_2}\cdots p_r(x)^{e_r}, \qquad a\in K\setminus\{0\}. \]

Because \(K[x]\) is a unique factorization domain, \(f\) is a square in \(K[x]\) if and only if both of the following conditions hold:

  1. The scalar \(a\) is a square in \(K\).
  2. Every factor exponent \(e_1,e_2,\ldots,e_r\) is even.

If \(a=c^2\) and \(e_j=2m_j\), then the square root is obtained immediately:

\[ g(x)=c\,p_1(x)^{m_1}p_2(x)^{m_2}\cdots p_r(x)^{m_r}. \]

Conversely, squaring any factorization doubles every irreducible-factor multiplicity, so odd exponents cannot occur in a square. Over \(\mathbb{C}\), all irreducible factors are linear, and the criterion says that every zero of \(f\) must have even multiplicity. Over \(\mathbb{R}\), irreducible quadratic factors must also occur an even number of times. Thus \(x^2+1\) is not a square in \(\mathbb{R}[x]\), whereas \((x^2+1)^2\) plainly is.

Root multiplicities in a perfect-square polynomial Three roots of g become roots of f equals g squared with twice their original multiplicities. g(x) f(x)=g(x)² multiplicity m₁ multiplicity m₂ multiplicity m₃ multiplicity 2m₁ multiplicity 2m₂ multiplicity 2m₃

The factorization criterion is conceptually complete, but factoring a polynomial can be much more work than extracting a square root. A direct coefficient algorithm decides the same question without first finding any zeros or irreducible factors.

Immediate Consequences

Several inexpensive tests reject impossible inputs before any coefficient extraction begins.

The Degree Must Be Even

For nonzero polynomials over a field, degrees add under multiplication:

\[ \deg(g^2)=2\deg g. \]

Therefore every nonzero polynomial square has even degree. If \(\deg f\) is odd, no polynomial square root exists. The zero polynomial is the one exceptional input: its square root is the zero polynomial.

The Leading Coefficient Must Be a Square

If \(\deg f=2n\), comparison of the leading terms gives

\[ b_n^2=a_{2n}. \]

Over \(\mathbb{R}\), this requires \(a_{2n}>0\). Over \(\mathbb{Q}\), its numerator and denominator must both be perfect squares after reduction. Over \(\mathbb{C}\), every nonzero leading coefficient has two square roots. A chosen scalar square-root convention, such as the positive real or principal complex root, fixes the sign of \(b_n\).

There Are Only Two Choices

In an integral domain of characteristic different from \(2\), if \(g^2=f=h^2\), then

\[ 0=g^2-h^2=(g-h)(g+h). \]

Since there are no zero divisors, either \(g=h\) or \(g=-h\). Choosing the leading coefficient therefore determines every remaining coefficient uniquely. This is why a deterministic algorithm can return one canonical root; applying negation gives the other.

Deriving the Coefficient Recurrence

Expanding \(g(x)^2\) turns polynomial multiplication into a convolution:

\[ a_k=\sum_{i+j=k}b_i b_j. \]

Start with \(b_n=\sqrt{a_{2n}}\). Suppose \(b_n,b_{n-1},\ldots,b_{r+1}\) are already known. The coefficient of \(x^{n+r}\) contains exactly two terms involving the next unknown \(b_r\), namely \(b_nb_r\) and \(b_rb_n\). In a commutative field they combine to \(2b_nb_r\); all other terms involve coefficients already determined:

\[ a_{n+r} =2b_nb_r+\sum_{i=r+1}^{n-1}b_i b_{n+r-i}. \]

Solving for \(b_r\) gives the extraction formula

\[ \boxed{ b_r= \frac{ a_{n+r}-\displaystyle\sum_{i=r+1}^{n-1}b_i b_{n+r-i} }{2b_n} }, \qquad r=n-1,n-2,\ldots,0. \]

This is the polynomial analogue of the traditional digit-by-digit square-root algorithm. Each step removes the contribution of terms already found, then divides the remainder by twice the leading term of the root. The division requires \(2b_n\neq0\), so characteristic \(2\) needs a separate rule.

A Complete Extraction

Consider

\[ f(x)=9x^4+6x^3-11x^2-4x+4. \]

Its degree is \(4=2\cdot2\), so write \(g(x)=b_2x^2+b_1x+b_0\). The leading term gives

\[ b_2=\sqrt9=3. \]

The coefficient of \(x^3\) determines \(b_1\):

\[ 6=2b_2b_1=6b_1 \qquad\Longrightarrow\qquad b_1=1. \]

The coefficient of \(x^2\) then determines \(b_0\):

\[ -11=b_1^2+2b_2b_0=1+6b_0 \qquad\Longrightarrow\qquad b_0=-2. \]

The candidate is therefore

\[ g(x)=3x^2+x-2. \]

Squaring it verifies every coefficient, including the two lower coefficients not used to construct it:

\[ (3x^2+x-2)^2 =9x^4+6x^3-11x^2-4x+4=f(x). \]

A second example shows why zero coefficients must not be skipped. For

\[ f(x)=x^6-2x^5-x^4+0x^3+3x^2+2x+1, \]

the recurrence yields \(b_3=1\), \(b_2=-1\), \(b_1=-1\), and \(b_0=-1\). Hence

\[ \sqrt{f(x)}=\pm(x^3-x^2-x-1). \]

Why Verification Is Essential

The recurrence uses the coefficients from degrees \(2n\) down to \(n\) to construct \(n+1\) unknowns. It does not use the remaining coefficients \(a_{n-1},\ldots,a_0\). Those lower coefficients decide whether the candidate is a genuine square root.

For example, applying the first steps to

\[ f(x)=x^2+1 \]

produces the candidate \(g(x)=x\) from the coefficients of \(x^2\) and \(x\). But \(g(x)^2=x^2\), whose constant coefficient is \(0\), not \(1\). The final comparison correctly rejects the candidate.

Verification also protects an implementation from arithmetic mistakes, unsupported coefficient operations, and accumulated floating-point error. A successful routine should never return a polynomial merely because the upper half of its coefficients fit.

Field-Generic Algorithm

The following TypeScript implementation applies when the field characteristic is not \(2\). It stores coefficients in ascending order, so a[k] is the coefficient of \(x^k\). The field object supplies the arithmetic and the scalar square root. Returning null distinguishes a polynomial that is not a square from malformed input or an unsupported field. 

interface Field<T> {
  zero: T;
  add(left: T, right: T): T;
  sub(left: T, right: T): T;
  mul(left: T, right: T): T;
  div(left: T, right: T): T;
  sqrt(value: T): T | null;
  equals(left: T, right: T): boolean;
  fromInteger(value: number): T;
}

function polynomialSquareRoot<T>(
  input: readonly T[],
  field: Field<T>
): T[] | null {
  let degree = input.length - 1;
  while (degree >= 0 && field.equals(input[degree], field.zero)) {
    degree--;
  }

  if (degree < 0) {
    return [];
  }
  if (degree % 2 !== 0) {
    return null;
  }

  const rootDegree = degree / 2;
  const leadingRoot = field.sqrt(input[degree]);
  if (leadingRoot === null) {
    return null;
  }

  const root = Array.from(
    { length: rootDegree + 1 },
    () => field.fromInteger(0)
  );
  root[rootDegree] = leadingRoot;

  for (let r = rootDegree - 1; r >= 0; r--) {
    const sourceDegree = rootDegree + r;
    let remainder = input[sourceDegree] ?? field.zero;

    for (let i = r + 1; i < rootDegree; i++) {
      remainder = field.sub(
        remainder,
        field.mul(root[i], root[sourceDegree - i])
      );
    }

    root[r] = field.div(
      remainder,
      field.mul(field.fromInteger(2), leadingRoot)
    );
  }

  const square = Array.from(
    { length: degree + 1 },
    () => field.fromInteger(0)
  );
  for (let i = 0; i < root.length; i++) {
    for (let j = 0; j < root.length; j++) {
      square[i + j] = field.add(square[i + j], field.mul(root[i], root[j]));
    }
  }

  for (let k = 0; k <= degree; k++) {
    if (!field.equals(square[k], input[k] ?? field.zero)) {
      return null;
    }
  }
  return root;
}

The extraction performs \(O(n^2)\) field operations in the straightforward implementation, and the final multiplication costs another \(O(n^2)\). Factoring \(f\) first gives a beautiful existence proof, but direct extraction is usually the simpler computational route when the only question is whether \(f\) is a perfect square.

Using Polynomial.js

Polynomial.js implements the same recurrence through its sqrt() method. It returns the root with the principal leading coefficient, or null when no polynomial root exists. The returned polynomial is verified by squaring before it leaves the method. 

import Polynomial from "polynomial";

const f = new Polynomial("9x^4+6x^3-11x^2-4x+4");
const g = f.sqrt();

if (g !== null) {
  console.log(g.toString());            // 3x^2+x-2
  console.log(g.mul(g).toString());     // 9x^4+6x^3-11x^2-4x+4
  console.log(g.neg().toString());      // -3x^2-x+2
}

Exact coefficient arithmetic matters. Rational and finite-field calculations can compare coefficients exactly. Real and complex floating-point arithmetic instead needs a small scale-aware tolerance during final verification; otherwise a mathematically exact square may be rejected because a computed coefficient differs by one rounding unit.

Characteristic Two

The division by \(2b_n\) in the recurrence is impossible in characteristic \(2\), where \(2=0\). Fortunately, squaring becomes simpler. The cross terms vanish because every pair occurs twice:

\[ \left(\sum_{i=0}^n b_ix^i\right)^2 =\sum_{i=0}^n b_i^2x^{2i}. \]

Thus a polynomial over a perfect field of characteristic \(2\) is a square exactly when every odd-degree coefficient is zero and every even-degree coefficient has a square root in the coefficient field. Over \(\mathbb{F}_2\), scalar squaring is the identity, so extraction simply halves every exponent:

\[ x^4+x^2+1=(x^2+x+1)^2 \qquad\text{in }\mathbb{F}_2[x]. \]

Polynomial Roots Versus Power-Series Roots

Failing the final verification does not always end the story. A polynomial that is not a square polynomial may still have a square root as an infinite formal power series. For instance, \(1+x\) is not a square in \(\mathbb{Q}[x]\), but its binomial series begins

\[ \sqrt{1+x} =1+\frac12x-\frac18x^2+\frac1{16}x^3-\frac5{128}x^4+\cdots. \]

Squaring the infinite series gives \(1+x\), but no finite truncation does so exactly. A polynomial square-root algorithm must therefore stop after its finite candidate and return failure rather than silently returning a truncated Taylor series.

Practical Checklist

  1. Treat the zero polynomial separately.
  2. Reject every nonzero polynomial of odd degree.
  3. Check that the leading coefficient has a square root in the coefficient field.
  4. Extract coefficients from highest degree to lowest using the recurrence.
  5. Use the characteristic-two rule instead when \(2=0\).
  6. Square the complete candidate and compare every coefficient with the input.
  7. Return one canonical sign and obtain the other root by negation.

These steps separate necessary conditions from the decisive test. Even degree and a square leading coefficient make a root possible; only the final identity \(g^2=f\) proves that the polynomial is a perfect square.

References

Related Stuff

raw / Algebra
06 Aug
·
Robert Eisele

Introduction to Polynomials

This chapter builds the general theory of one-variable polynomials that the quadratic and cubic equation chapters specialize from. It covers evaluation and Horner's method (linking to Landau notation for the running-time comparison), coefficient-wise addition and convolution-based multiplication with the resulting degree rules, the polynomial division algorithm and synthetic division, the Factor Theorem, root multiplicity via derivatives and its geometric meaning (crossing versus touching the x-axis), the Fundamental Theorem of Algebra and conjugate-pair factorization for real coefficients, the existence of a real root for every odd-degree real polynomial, Vieta's formulas relating coefficients to elementary symmetric functions of the roots, and the Abel-Ruffini theorem explaining why radical solution formulas exist only up to degree four.
raw / Algebra
28 Sep
·
Robert Eisele

Introduction to Complex Numbers

Complex numbers extend the real number system with the imaginary unit and form a complete metric field. The discussion develops Cartesian and polar representation, arithmetic, conjugation, modulus, argument rules, triangle inequalities, and convergence. Euler's formula leads to the complex exponential, Euler's identity, De Moivre's formula, complex logarithms, branch choices, general powers, principal roots, and roots of unity. The fundamental theorem of algebra is accompanied by the conjugate-root theorem for real polynomials. Complex trigonometric and hyperbolic functions are defined through the exponential and then specialized to their familiar real forms, identities, addition theorems, and inverses.
raw / Linear Algebra
08 May
·
Robert Eisele

Introduction to Eigenvalues and Eigenvectors

This introduces eigenvalues and eigenvectors as invariant directions of linear transformations. It derives the characteristic polynomial (including the alternate det(lambda I - A) sign convention), works through a full numerical example of a symmetric matrix with a repeated eigenvalue to show the characteristic polynomial, row reduction, and eigenspace computation concretely, explains eigenspaces and multiplicity including a defective, non-diagonalisable counter-example and why real symmetric matrices can never be defective, proves the trace/determinant formulas and the linear independence of eigenvectors for distinct eigenvalues, states Cauchy's interlacing theorem for the eigenvalues of a principal submatrix and the Perron-Frobenius theorem for nonnegative matrices, studies orthogonal matrices (proving every eigenvalue has absolute value 1), rotation matrices with complex eigenvalues and the degrees-of-freedom argument behind them, reflection matrices with real +-1 eigenvalues and a diagram of the mirror line and an eigenvector's invariant direction, and three-dimensional rotations via Euler's rotation theorem and the trace-angle relation, presents the eigenvalue decomposition, extends it to arbitrary real matrix powers and the symmetric square root, derives Gram factors, whitening transforms, and their use in generating correlated random vectors, derives the Rayleigh quotient and its variational characterization of the extreme eigenvalues, shows how repeated application of a matrix is governed by its dominant eigenvalue via power iteration, illustrated with an interactive diagram of successive normalized directions spiraling onto the dominant eigenvector and with the Fibonacci sequence and Binet's formula, proves the Cayley-Hamilton theorem (with a common false-proof pitfall explained) and uses it to derive the determinant of a matrix directly from traces of its powers via Newton's identities, and lists typical applications in linear algebra and engineering, including spectral graph theory and PageRank.
All Math