7 Lower bounds of polynomials
Every leaf test reduces to a statement of the form “the polynomial \(p\) is at least \(m\) on \([-1,1]^5\)”, where \(p\) has integer coefficients and degree at most \(2\) in each variable (degree at most \(4\) in \(t_0, t_1\) for one family of orbit tests). This chapter gives the two lower bounds that are used, and the integer encoding that lets the kernel compute them quickly.
A polynomial expression is a term built from integer constants, the variables \(t_0, \dots , t_4\), addition, subtraction and multiplication. It can be evaluated in any commutative ring. Its norm is computed by replacing every constant by its absolute value and evaluating at \(t = (1, \dots , 1)\); it bounds the sum of the absolute values of the coefficients of the polynomial.
The leaf tests are written once, generically in the arithmetic: the same definition, instantiated with integers, is the checker; instantiated with polynomial expressions it produces \(p\); instantiated with reals it gives the geometric quantity. Maps that commute with the ring operations commute with the generic definitions, which relates the three instances.
7.1 The coefficient bound
Let \(p = \sum _m c_m t^m\). For \(t \in [-1,1]^5\),
For \(|t_i| \le 1\) every monomial lies in \([-1, 1]\), and a monomial with only even exponents lies in \([0, 1]\).
7.2 The Bernstein bound
On \([-1, 1]\) a quadratic \(a_0 + a_1 t + a_2 t^2\) equals \(b_0 \beta _0(t) + b_1 \beta _1(t) + b_2 \beta _2(t)\) with
The \(\beta _\kappa \) are nonnegative on \([-1, 1]\) and sum to \(1\).
The Bernstein coefficients of a polynomial of degree at most \(2\) in each of five variables are obtained by applying the transformation \((a_0, a_1, a_2) \mapsto (b_0, b_1, b_2)\) along each variable in turn. There are \(3^5 = 243\) of them.
If every Bernstein coefficient of \(p\) is at least \(m\), then \(p(t) \ge m\) for all \(t \in [-1,1]^5\).
\(p(t) = \sum _\kappa b_\kappa \prod _i \beta _{\kappa _i}(t_i)\), a convex combination of the Bernstein coefficients.
Neither bound dominates the other (for \(p = t^2\) the coefficient bound is \(0\) and the Bernstein bound is \(-1\)), but on the gap polynomials the Bernstein bound is usually much sharper; using it in addition halved the number of leaves in the certificate. It costs more to compute, so the checker tries the coefficient bound first.
7.3 Kronecker packing
The kernel evaluates arithmetic on natural numbers with GMP, but each step of a recursive function is comparatively expensive. The checker therefore represents a polynomial by a single large integer.
A layout assigns to every exponent vector \(m\) with \(m_i {\lt} r_i\) the slot \(\mathrm{idx}(m) = \sum _i m_i s_i\), where \(s_i = \prod _{i' {\lt} i} r_{i'}\). For a slot width \(W\), the Kronecker point is \(t_i = 2^{W s_i}\).
If the exponents of \(p\) fit the layout, then \(p\) evaluated at the Kronecker point is \(\sum _j c_j 2^{W j}\), where \(c_j\) is the coefficient in slot \(j\). If moreover \(|c_j| {\lt} 2^{W-1}\) for all \(j\), then adding \(2^{W-1}\) to every slot gives a natural number whose \(j\)-th base-\(2^W\) digit is \(c_j + 2^{W-1}\).
Evaluation at the Kronecker point is a ring homomorphism, and the mixed-radix indexing is injective on the exponents that fit.
Since evaluation is a ring homomorphism, the checker computes \(p\) at the Kronecker point with a handful of big-integer additions and multiplications. Every coefficient is then available as a digit: the top bit of each offset digit is its sign, a bitwise and with a mask selects a set of slots, and the sum of a set of digits is a remainder modulo \(2^W - 1\).
If the coefficient norm of \(p\) is below the bound fixed by the slot width, then the checker’s mask computations applied to \(p\) at the Kronecker point return exactly the coefficient bound of Theorem 49, and its packed Bernstein transform returns the packed Bernstein coefficients. A Bernstein test that passes therefore certifies that every Bernstein coefficient is at least \(m\).
Digit-by-digit arithmetic on packed numbers (Lemma 55). The Bernstein transform along variable \(i\) separates the slots by their digit \(i\) with masks, shifts them to a common position, and recombines them.
Let \(\mathrm{pack}(d) = \sum _{j {\lt} n} d_j 2^{W j}\) with every digit \(d_j {\lt} 2^W\). Bitwise and, digit-wise sums and differences (when no digit over- or underflows), the extraction of the top bit of every digit, and the sum of all digits (via the remainder modulo \(2^W - 1\), when that sum is below \(2^W - 1\)) all act digit by digit.
Induction on \(n\).
The checker uses slot width \(W = 400\) and requires coefficient norms below \(2^{390}\), which leaves room for the Bernstein transform.
If a gap leaf’s box has scale \(2^K\) with \(K \le 16\) and its direction has \(|w_0|, |w_1| \le 1024\), then every polynomial the leaf decodes has coefficient norm below \(2^{390}\).
The norm bounds are computed by the same formulas as the polynomials, with each operation acting on norms; this only adds and multiplies, so it is monotone in the magnitudes of the inputs. Every box of the walk has \(|c_i| + |h_i| \le 2 \cdot 2^K\) and the vertex coordinates are below \(2^{161}\), so the norms are at most those of the worst box (scale \(2^{16}\), all centres and radii \(2^{17}\)), which are below \(2^{390}\) by direct computation.