Polynomial Division, Descartes' Rule of Signs & Transformations

1. The Division Algorithm for Polynomials

For any polynomial dividend $P(x)$ and non-zero divisor $D(x)$, there exist unique quotient $Q(x)$ and remainder $R(x)$ such that: $$\mathbf{P(x) = D(x) Q(x) + R(x), \quad \text{where } \deg(R) < \deg(D) \text{ or } R(x) = 0}$$ Remainder Theorem: When divided by a linear factor $(x - c)$, the remainder is the constant $R = P(c)$.
Factor Theorem: A linear binomial $(x - c)$ is a factor of $P(x)$ if and only if $P(c) = 0$.

2. Horner’s Synthetic Division Algorithm

William George Horner formalized a streamlined algorithm for dividing a polynomial $P(x) = a_n x^n + \dots + a_0$ by $(x - c)$ using only $n$ multiplications and $n$ additions: $$\begin{array}{c|cccccc} c & a_n & a_{n-1} & a_{n-2} & \dots & a_1 & a_0 \\ & & c b_{n-1} & c b_{n-2} & \dots & c b_1 & c b_0 \\ \hline & b_{n-1} & b_{n-2} & b_{n-3} & \dots & b_0 & R \end{array}$$ where the recurrence is initialized by $b_{n-1} = a_n$ and generated by: $$\mathbf{b_{k-1} = a_k + c \, b_k, \quad \text{with remainder } R = P(c) = a_0 + c \, b_0}$$ The quotient polynomial is $Q(x) = b_{n-1} x^{n-1} + b_{n-2} x^{n-2} + \dots + b_0$.

1. Statement of Descartes’ Theorem

René Descartes established an analytical bound on the real roots of a real polynomial $P(x) = a_n x^n + \dots + a_0$:

• Let $V$ denote the number of sign variations between consecutive non-zero coefficients of $P(x)$.
• The number of positive real roots $N_+$ of $P(x)$ is either equal to $V$ or less than $V$ by an even non-negative integer: $$\mathbf{N_+ = V - 2k, \quad k \in \{0, 1, 2, \dots\}, \quad N_+ \le V}$$
• The number of negative real roots $N_-$ of $P(x)$ is bounded similarly by the sign variations $V_-$ in the polynomial $P(-x)$: $$\mathbf{N_- = V_- - 2m, \quad m \in \{0, 1, 2, \dots\}, \quad N_- \le V_-}$$

2. Proof Outline & Bounding Imaginary Roots

Multiplying a polynomial by $(x - r)$ where $r > 0$ increases the number of sign variations by at least 1 and always by an odd number. Since non-real complex roots of real polynomials occur strictly in conjugate pairs (contributing in multiples of 2), the discrepancy between $V$ and $N_+$ must be an even integer. Lower Bound on Non-Real Complex Roots: Since the total number of complex roots is $n$, the number of non-real roots $N_c$ satisfies: $$\mathbf{N_c = n - (N_+ + N_-) \ge n - (V + V_-)}$$

1. Definition and Derivative Criteria

A root $c$ of $P(x)$ has multiplicity $m \ge 1$ if $(x - c)^m$ divides $P(x)$ but $(x - c)^{m+1}$ does not, so $P(x) = (x - c)^m g(x)$ with $g(c) \ne 0$.
Theorem: A number $c$ is a root of $P(x)$ of multiplicity $m$ if and only if: $$\mathbf{P(c) = P'(c) = P''(c) = \dots = P^{(m-1)}(c) = 0 \quad \text{and} \quad P^{(m)}(c) \ne 0}$$ Proof: Differentiating $P(x) = (x - c)^m g(x)$ by the Product Rule: $$P'(x) = m(x - c)^{m-1} g(x) + (x - c)^m g'(x) = (x - c)^{m-1} [m g(x) + (x - c) g'(x)]$$ At $x = c$, $(x - c)^{m-1}$ is a factor, so $P'(c) = 0$ for $m \ge 2$. Repeated differentiation continues until order $m-1$. $\blacksquare$

2. Square-Free Factorization via Greatest Common Divisor

The greatest common divisor of $P(x)$ and its derivative $P'(x)$ isolates all repeated roots: $$\mathbf{\gcd(P(x), P'(x)) = \prod_{i=1}^k (x - c_i)^{m_i - 1}}$$ The square-free part $P_{\text{red}}(x) = \frac{P(x)}{\gcd(P(x), P'(x))}$ has identical roots to $P(x)$ but with all multiplicities reduced to 1, allowing Euclidean algorithm polynomial GCD routines to isolate repeated roots without numerical root-finding!

1. Shifting Roots by a Constant $h$

To transform an equation $P(x) = 0$ into an equation whose roots are diminished by $h$ (i.e., $y = x - h \implies x = y + h$): $$P(y + h) = A_n y^n + A_{n-1} y^{n-1} + \dots + A_1 y + A_0 = 0$$ The transformed coefficients $A_k$ are determined efficiently by performing $n$ successive synthetic divisions by $h$: $$A_k = \frac{P^{(k)}(h)}{k!}$$

2. Scaling and Reciprocal Transformations

• Multiplying Roots by $m$ ($y = mx \implies x = y/m$): $$a_n \left(\frac{y}{m}\right)^n + a_{n-1}\left(\frac{y}{m}\right)^{n-1} + \dots + a_0 = 0 \iff a_n y^n + m a_{n-1} y^{n-1} + m^2 a_{n-2} y^{n-2} + \dots + m^n a_0 = 0$$
• Reciprocal Roots ($y = 1/x \implies x = 1/y$): $$a_n \left(\frac{1}{y}\right)^n + \dots + a_0 = 0 \iff a_0 y^n + a_1 y^{n-1} + \dots + a_{n-1} y + a_n = 0$$ This simply reverses the order of the original coefficients!

1. Eliminating the Second Term (Tschirnhaus Shift)

Given $a_0 x^n + a_1 x^{n-1} + \dots + a_n = 0$, shifting roots by $x = y + h$: $$a_0 (y + h)^n + a_1 (y + h)^{n-1} + \dots = a_0 [y^n + n h y^{n-1} + \dots] + a_1 [y^{n-1} + \dots] = 0$$ The coefficient of $y^{n-1}$ is $n a_0 h + a_1$. Setting this to zero yields: $$\mathbf{h = -\frac{a_1}{n a_0}}$$ This canonical shift removes the degree $n-1$ term, reducing any general cubic $a x^3 + b x^2 + c x + d = 0$ to the depressed cubic $y^3 + p y + q = 0$!

2. Reciprocal Equations of First and Second Class

An equation is reciprocal if substituting $x \to 1/x$ leaves the equation unchanged: $$a_k = a_{n-k} \quad (\text{Standard Class}) \qquad \text{or} \qquad a_k = -a_{n-k} \quad (\text{Second Class})$$ Solution Strategy:

• If degree $n$ is odd, $x = -1$ (Class 1) or $x = 1$ (Class 2) is always a root. Factoring out $(x \pm 1)$ reduces the equation to an even-degree reciprocal equation.
• For an even degree reciprocal equation $a x^4 + b x^3 + c x^2 + b x + a = 0$, divide by $x^2$: $$a\left(x^2 + \frac{1}{x^2}\right) + b\left(x + \frac{1}{x}\right) + c = 0$$ Substituting $z = x + \frac{1}{x} \implies x^2 + \frac{1}{x^2} = z^2 - 2$ reduces the quartic to a quadratic in $z$: $$\mathbf{a(z^2 - 2) + bz + c = 0}$$ Solving for $z$ and then solving $x^2 - zx + 1 = 0$ yields all roots!