Canonical form

A canonical form is a representation chosen so that expressions that are mathematically equal have the same representation^[3]^[2]. With canonical forms, deciding whether two expressions are equal is a structural comparison rather than a search for a proof, equal expressions hash to the same value, and results can be cached reliably. The most important consequence is the zero test: almost every algorithm in computer algebra branches on whether some quantity is zero, a pivot in elimination, a leading coefficient in division, a remainder in a gcd, and it can do so only if zero is recognizable. A normal form is the weaker requirement that everything equal to zero is represented by 0; for classes closed under subtraction the two notions coincide, since $a = b$ exactly when $a - b$ is zero^[3]. Canonical forms exist for polynomials and rational functions, and for polynomials modulo an ideal via Gröbner bases, but Richardson's theorem shows that for sufficiently rich classes of expressions no algorithm can even decide equality with zero^[1].

§ 01

Definitions

Let $E$ be a class of expressions and $\sim$ the relation of denoting the same function or value. A canonical simplifier is a computable map $S : E \to E$ with $S (e) \sim e$ and

e_{1} \sim e_{2} ⟹ S (e_{1}) = S (e_{2})

where the equality on the right is syntactic identity. A normal simplifier only guarantees $e \sim 0 \Rightarrow S (e) = 0$ . Caviness formalized both notions in 1970^[3], and Moses surveyed the choices a computer algebra system faces between aggressive and conservative simplification^[4].

A canonical simplifier sends every expression of a class of equivalent ones to the same representative: expanded polynomials with sorted terms, and rational functions reduced to lowest terms with a normalized denominator.

§ 02

Polynomials and rational functions

For polynomials over a field or the integers, the expanded form with like terms collected and terms sorted by a fixed monomial order is canonical. For rational functions, the quotient of two such polynomials with their gcd cancelled and the denominator normalized, for instance monic or with positive leading coefficient, is canonical. Expressions containing other functions are handled by treating their non-polynomial parts, such as $sin x$ , as new variables, called kernels.

Four ways of writing one polynomial, as expression trees and in canonical form.

open Expr
 
(* Four ways of writing the same polynomial, and their canonical forms. *)

Running it.

(x + y)^2          tree (x + y)^2                    canonical x^2 + 2·x·y + y^2
x^2 + 2xy + y^2    tree (x^2 + 2*x*y + y^2)          canonical x^2 + 2·x·y + y^2
(y + x)(x + y)     tree (y + x)*(x + y)              canonical x^2 + 2·x·y + y^2
x(x + 2y) + y^2    tree (x*(x + 2*y) + y^2)          canonical x^2 + 2·x·y + y^2
all canonical forms equal: true

The trees differ; the canonical forms are identical. The price of this canonical form is expansion, which can be exponentially larger than the input: $(x_{1} + y_{1}) \dots (x_{n} + y_{n})$ expands into $2^{n}$ terms.

§ 03

Relations between kernels

Treating $sin x$ and $cos x$ as independent variables makes the polynomial form canonical as a polynomial in them, but not as a function of $x$ : it does not know that $sin^{2} x + cos^{2} x = 1$ . When the relations between kernels form a polynomial ideal, the remainder modulo a Gröbner basis of that ideal is canonical for the quotient ring^[9].

Reducing polynomials in s = sin x and c = cos x modulo s² + c² − 1.

(* With s = sin x and c = cos x as independent kernels, the polynomial
   form does not know that s^2 + c^2 = 1. Reducing modulo that relation,
   a Gröbner basis of one element, gives a canonical form that does. *)
open Mpoly

Running it.

s^2 + c^2 - 1                polynomial form: s^2 + c^2 - 1              modulo s^2 + c^2 = 1: 0
s^2 + 2sc + c^2 - 2sc - 1    polynomial form: s^2 + c^2 - 1              modulo s^2 + c^2 = 1: 0
s^4 - c^4                    polynomial form: s^4 - c^4                  modulo s^2 + c^2 = 1: -2c^2 + 1
s^2 - c^2                    polynomial form: s^2 - c^2                  modulo s^2 + c^2 = 1: -2c^2 + 1
s^3 + sc^2                   polynomial form: s^3 + sc^2                 modulo s^2 + c^2 = 1: s

The remainder eliminates every power of $s$ beyond the first, and $s^{4} - c^{4}$ and $s^{2} - c^{2}$ are recognized as equal. Rewriting systems give normal forms in the same way when they are terminating and confluent, which the Knuth–Bendix completion procedure tries to achieve^[10].

§ 04

Richardson's theorem

Richardson proved in 1968 that there is no algorithm to decide whether an expression built from $x$ , rational numbers, $π$ , $ln 2$ , addition, multiplication, composition, $sin$ , $exp$ and $∣ \cdot ∣$ is identically zero^[1]. The proof encodes Hilbert's tenth problem, whether a polynomial with integer coefficients has an integer root, into such expressions, using $sin^{2} (π x)$ to force variables to be integers. Consequently no canonical or even normal simplifier exists for such a class, and practical systems keep canonical forms for well-behaved fragments, polynomials, rational functions and some algebraic and exponential extensions, and use heuristics outside them.

§ 05

Randomized identity testing

When expansion is too expensive or no canonical form is available, an identity can be tested by evaluating both sides at random points. For polynomials, the Schwartz–Zippel lemma bounds the error: a nonzero polynomial of total degree $d$ vanishes at a point chosen uniformly from $S^{n}$ with probability at most $d /∣ S ∣$ ^[5]^[6]^[7].

Checking that the Vandermonde determinant is the product of differences, and rejecting a subtly wrong version, by evaluation at random points modulo a large prime.

(* Testing a polynomial identity by evaluation at random points modulo a
   prime: the Vandermonde determinant equals the product of differences.
   A wrong identity is caught with probability at least 1 - d/p. *)
let p = 1_000_000_007
 
let det m =                                  (* Gaussian elimination mod p *)
  let n = Array.length m and m = Array.map Array.copy m and d = ref 1 in
  (try for k = 0 to n - 1 do
       let piv = match List.find_opt (fun i -> m.(i).(k) <> 0) (List.init (n - k) (fun i -> k + i)) with
         | Some i -> i | None -> raise Exit in
       if piv <> k then (let t = m.(piv) in m.(piv) <- m.(k); m.(k) <- t; d := p - !d);
       d := !d * m.(k).(k) mod p;
       let inv = Modp.inv p m.(k).(k) in
       for i = k + 1 to n - 1 do
         let f = m.(i).(k) * inv mod p in
         for j = k to n - 1 do m.(i).(j) <- Modp.md p (m.(i).(j) - f * m.(k).(j)) done
       done
     done with Exit -> d := 0);
  !d

Running it.

det = prod (x_j - x_i), 20 random points: true
det = (x_1 + x_0) prod over the other pairs: agreed at 0 of 20 random points
the expanded determinant has 12! = 479001600 terms

The determinant has degree 66, so each evaluation modulo a prime near $1 0^{9}$ misses a wrong identity with probability below $1 0^{- 7}$ , while the expanded determinant would have nearly half a billion terms. Whether such tests can be derandomized is a central open problem of complexity theory, tied to lower bounds for arithmetic circuits^[8].

§ 06

History

Early formula manipulation systems of the 1960s struggled with simplification, and the distinction between canonical and normal forms was clarified by Caviness in 1970^[3] and discussed by Moses in 1971^[4]. Richardson's undecidability theorem of 1968 marked the limits^[1]. Buchberger's Gröbner bases and the Knuth–Bendix procedure supplied canonical forms modulo relations^[10], and Buchberger and Loos surveyed algebraic simplification in 1982^[2]. Probabilistic identity testing was introduced by DeMillo and Lipton, Zippel and Schwartz between 1978 and 1980^[7]^[6]^[5].