Dependencies

\(\| C_1 \| = 1\), \({98 \over 100} {\lt} \| C_2 \| {\lt} {99 \over 100}\), and \({98 \over 100} {\lt} \| C_3 \| {\lt} {99 \over 100}\).

A point \(X\) of a box is bad if, with \(r\) the Cayley vector of \(X\) (Definition 36), the tuple \((X_0, X_1, j, r)\) is reduced and \(\bigl(s(X_0, X_1),\ s(X_0, X_1)\, Q_j(r)\bigr)\) is a Rupert pair. A box is covered if none of its points with \(X_0^2 + X_1^2 \le 1\) and \(|r_i| \le 2\) is bad.

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.

A box consists of a chart \(j \in \{ 0, \dots , 4\} \), a face \(f \in \{ 0, \dots , 5\} \) (used only in charts 0 and 4), a scale \(K \in \operatorname{\mathbb {N}}\), and integer centres \(c_i\) and radii \(h_i \ge 0\) for \(i = 0, \dots , 4\). The point of the box at normalized coordinates \(t \in [-1,1]^5\) is \(X(t)\) with \(X_i = (c_i + h_i t_i) / 2^K\).

For \(r = (x, y, z) \in \operatorname{\mathbb {R}}^3\) let \(D(r) = 1 + x^2 + y^2 + z^2\) and

The Cayley rotation of \(r\) is \(\mathrm{Cay}(r) = N(r) / D(r)\). It is the rotation by the unit quaternion proportional to \((1, x, y, z)\).

The chart bases are \(B_0 = I\), \(B_1 = \mathrm{diag}(1, -1, -1)\), \(B_2 = \mathrm{diag}(-1, 1, -1)\), \(B_3 = \mathrm{diag}(-1, -1, 1)\) (the Klein four-group) and \(B_4 = \tau \). In chart \(j\) the relative rotation with coordinates \(r \in \operatorname{\mathbb {R}}^3\) is \(Q_j(r) = B_j\, \mathrm{Cay}(r)\).

A domain leaf names one condition of Definition 34 that fails on the whole box:

1. (disk) \(u^2 + v^2 {\gt} 1\), tested at the lower corner of the box;

2. (wedge) \(v {\gt} \frac{57}{128} u\), tested at the corners of the box;

3. (chart \(k\)) \(\operatorname{\mathrm{tr}}(B_j^T Q_j(r)) {\lt} \operatorname{\mathrm{tr}}(B_k^T Q_j(r))\), a polynomial inequality after clearing \(D_r\);

4. (orbit \(e, g, a\)) \(F(Q_j(r)) {\lt} F(H^e Q_j(r) g_g)\), established through the term \(\operatorname{\mathrm{tr}}(B_a^T H^e Q_j(r) g_g) - [a = 4]\, \frac18\) with \(a \in \{ 0, 4\} \), again a polynomial inequality after clearing denominators, with the tabulated \(\hat g_g\) in place of \(g_g\) and an explicit error allowance.

The main statement: there is a finite set \(V \subseteq \operatorname{\mathbb {R}}^3\) whose convex hull has nonempty interior and which is not Rupert.

For a face index \(f \in \{ 0, \dots , 5\} \) and \((s_0, s_1) \in [-1,1]^2\), \(c_f(s_0, s_1)\) is the point of face \(f\) of \([-1,1]^3\) with free coordinates \((s_0, s_1)\). A point of a blown-up chart has coordinates \(X = (u, v, s_0, s_1, \rho )\) and Cayley vector \(r = \rho \, c_f(s_0, s_1)\); a point of charts 1–3 has coordinates \(X = (u, v, r_0, r_1, r_2)\).

A gap leaf names an inner vertex \(S\) and a direction \((w_0, w_1) \ne 0\). It passes if the coefficients of the polynomials involved are small enough for the packed arithmetic of Chapter 7, and for every one of the 90 outer vertices \(T\) one of the following succeeds:

1. the quick test: a lower bound of \(A - \sum _k T_k E_k\) built from the constant terms and coefficient sums of \(A\) and the \(E_k\), evaluated for all 90 vertices at once;

2. the full test: the coefficient lower bound or the Bernstein lower bound of the polynomial \(A - \sum _k \hat T_k E_k\) is at least \(\mathrm{err}\);

3. for the paired vertex \(T = \sigma (S)\) in charts 0 and 4: the coefficient or Bernstein lower bound of \(2L\) is at least \(\mathrm{err}\) (or \(\rho {\gt} 0\) on the whole box and the full test succeeds).

A certificate tree has internal nodes that split a box in half along one coordinate, and leaves that are gap leaves or domain leaves. A tree is accepted on a box if every leaf passes on its sub-box.

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}\).

The Noperthedron \(\operatorname{\mathbf{NOP}}\) is the convex polyhedron given by the vertex set

The orbit score of a matrix \(X\) is \(F(X) = \max \bigl(\operatorname{\mathrm{tr}}X,\ \operatorname{\mathrm{tr}}(\tau ^T X) - \tfrac 18\bigr)\).

For \((u, v) \in \operatorname{\mathbb {R}}^2\) let \(s(u, v) = \mathrm{Cay}(v, -u, 0)\).

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.

A set \(S \subseteq \operatorname{\mathbb {R}}^3\) is point-symmetric if \(x \in S\) implies \(-x \in S\).

A tuple \((u, v, j, r)\) with \(j \in \{ 0, \dots , 4\} \) is reduced if

1. (wedge and disk) \(u \ge 0\), \(0 \le v \le \frac{57}{128} u\), \(u^2 + v^2 \le 1\);

2. (chart) \(\operatorname{\mathrm{tr}}(B_k^T Q_j(r)) \le \operatorname{\mathrm{tr}}(B_j^T Q_j(r))\) for all \(k \le 4\);

3. (orbit) \(F(H^e Q_j(r) g_k) \le F(Q_j(r))\) for all \(e \in \{ 0,1\} \) and \(k\), where \(H = s(u,v)^T R_z(\pi ) s(u,v)\);

4. (bounds) \(|r_i| \le 1\) if \(j \le 3\) and \(|r_i| \le 2\) if \(j = 4\).

There are 15 root boxes, all with \((u, v) \in [0, 1] \times [0, \frac12]\):

• charts \(1, 2, 3\) with \(r \in [-1, 1]^3\);

• chart \(0\), one box for each face \(f\), with \((s_0, s_1) \in [-1,1]^2\) and \(\rho \in [0, 1]\);

• chart \(4\), one box for each face \(f\), with \((s_0, s_1) \in [-1,1]^2\) and \(\rho \in [0, 2]\).

A convex polyhedron with vertex set \(V\) is Rupert if there are rotations \(R_i, R_o \in SO(3)\) and an offset \(o \in \operatorname{\mathbb {R}}^2\) such that

The shadow of a \(3 \times 3\) matrix \(R\) is \(\mathrm{Sh}(R) = \pi (R\, \operatorname{\mathbf{P}})\). A pair of matrices \((R_o, R_i)\) is a Rupert pair if \(\overline{\mathrm{Sh}(R_i)} \subseteq \operatorname {int} \mathrm{Sh}(R_o)\).

Let \((x, y)\) be the first two coordinates of \(C_3\). The matrix

is minus the reflection in the vertical plane through \(C_3\); it is a half-turn about a horizontal axis, and it has rational entries.

Every \(A \in SO(3)\) is a rotation by some angle \(\gamma \in (-\pi , \pi ]\) about some unit axis \(a\): \(A v - v = \sin \gamma \; a \times v + (1 - \cos \gamma )\; a \times (a \times v)\). Its trace is \(1 + 2\cos \gamma \).

In charts 0 and 4, with \(r = \rho \, c\),

For every \(S \in \operatorname{\mathbb {R}}^3\),

Equivalently \(\mathrm{Cay}(r) S - S = \frac{2}{D(r)} \bigl(r \times S + r \times (r \times S)\bigr)\).

\(D(r) {\gt} 0\) and \(\mathrm{Cay}(r) \in SO(3)\) for every \(r \in \operatorname{\mathbb {R}}^3\).

\(\operatorname{\mathrm{tr}}\mathrm{Cay}(r) = (3 - |r|^2) / (1 + |r|^2)\).

Every reduced \((u, v, j, r)\) is a point of one of the root boxes of chart \(j\).

Every \(r\) with \(|r_i| \le R\) for all \(i\) is \(\rho \, c_f(s_0, s_1)\) for some face \(f\), some \(0 \le \rho \le R\) and some \(|s_0|, |s_1| \le 1\).

If \(\operatorname{\mathbf{P}}\) is Rupert, then there is a Rupert pair \((R_o, R_i)\) with \(R_o, R_i \in SO(3)\).

where \(N_o\) is the numerator of \(s(u, v)\). As a function of the normalized coordinates \(t\), this is (up to a fixed power of two) a polynomial with integer coefficients of degree at most \(2\) in each variable. Writing \(\alpha _k = w_0 (N_o)_{0k} + w_1 (N_o)_{1k}\), it equals \(A - \sum _k T_k E_k\) with \(A = \sum _k \alpha _k (M_j N(r) S)_k\) and \(E_k = \alpha _k \kappa _j D_r\), which do not depend on \(T\).

Every entry of every tabulated rotation \(\hat g_k\) is within \(2^{-60}\) of the corresponding entry of \(g_k = R_z(2\pi k/15)\).

\(\sum _{k=0}^{3} \operatorname{\mathrm{tr}}(B_k^T X) = 0\) for every \(3 \times 3\) matrix \(X\), and

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}\).

If \((R_o, R_i)\) is a Rupert pair, then so is \((R_o, R_z(\pi ) R_i)\).

Let \(L \in SO(3)\) with \(L e_z = \pm e_z\). If \((R_o, R_i)\) is a Rupert pair, then so is \((L R_o, L R_i)\). In particular this holds for \(L = R_z(\gamma )\) and for the half-turn \(L = R_x(\pi )\).

If \((R_o, R_i)\) is a Rupert pair, then so are \((R_o g_k, R_i)\) and \((R_o, R_i g_k)\).

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}\).

If \(R \in SO(3)\) has the same third row as \(s(u, v)\), then \(R = R_z(\gamma )\, s(u, v)\) for some \(\gamma \).

The third row of \(s(u, v)\), the view \(s(u,v)^T e_z\), is the inverse stereographic image

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\).

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.

Suppose \(A \ge c_0 - \mathrm{sl}\) and \(|E_k - e_k| \le a_k\) on the box, where \(c_0\), \(e_k\) are constant terms and \(\mathrm{sl}\), \(a_k\) are coefficient sums. If

then \(\mathrm{err} \le A - \sum _k T_k E_k\) on the box.

If the skeleton is accepted on a root box when holes count as passing, its holes are exactly the boxes of the listed subtrees, and every listed subtree is accepted on its box, then the root box is covered.

\(\sin (2\pi /15) \le \frac{57}{128} \cos (2\pi /15)\).

Every point of a box is a point of one of its two halves.

Let \(Q \in SO(3)\) and let \(j\) maximize \(\operatorname{\mathrm{tr}}(B_k^T Q)\) over \(k \in \{ 0, \dots , 4\} \). Then \(Q = Q_j(r)\) for some \(r\) with \(|r_i| \le 1\) (if \(j \le 3\)) or \(|r_i| \le 2\) (if \(j = 4\)).

If \((s, R_i)\) is a Rupert pair with \(R_i \in SO(3)\), then there is a Rupert pair \((s, s\, Q)\) with \(Q \in SO(3)\) and \(F(H^e Q g_k) \le F(Q)\) for all \(e\) and \(k\).

If there is a Rupert pair in \(SO(3)\), then there is one of the form \((s(u, v), R_i)\) with

\(\tau \) maps the 30 points \(\mathcal{C}_{30} \cdot C_3\) onto themselves.

Let \(\theta _1 = 2\pi /15\). Then \(\theta _1 = \pi /3 - \pi /5\), and \(\cos \theta _1\) and \(\sin \theta _1\) are known to \(28\) decimal places.

For \(k = 0, \dots , 14\), the checker’s tables of \(\cos (2\pi k/15)\) and \(\sin (2\pi k/15)\) (dyadic numbers with denominator \(2^{80}\)) are within \(2^{-71}\) of the true values.

Every coordinate of every tabulated vertex is within \(2^{-60}\) of the corresponding coordinate of the true vertex of \(\operatorname{\mathbf{P}}\).

The Noperthedron has nonempty interior.

The noperthedron is point-symmetric.

The norm of any vertex in the Noperthedron is no more than 1.

If every Bernstein coefficient of \(p\) is at least \(m\), then \(p(t) \ge m\) for all \(t \in [-1,1]^5\).

Every \(A \in SO(3)\) with \(\operatorname{\mathrm{tr}}A \ge 0\) is \(\mathrm{Cay}(r)\) for some \(r\) with \(|r|^2 \le 3\).

Let \(p = \sum _m c_m t^m\). For \(t \in [-1,1]^5\),

If a domain leaf passes on a box, then no point of the box with \(u^2 + v^2 \le 1\) and \(|r_i| \le 2\) is reduced.

Let \(X\) be a point of a box in chart \(j\) with \(u^2 + v^2 \le 1\) and \(|r_i| \le 2\), let \(S\) be an inner vertex and \(w \ne 0\). Suppose that for every outer vertex \(T\), either

or \(j \in \{ 0, 4\} \), \(T = \sigma (S)\) and \(\mathrm{err} \le 2 \hat L(X)\), where \(\hat L\) is \(L\) computed with \(\hat S\). Then \(\bigl(s, s\, Q_j(r)\bigr)\) is not a Rupert pair.

If a gap leaf passes on a box, then no point of the box with \(u^2 + v^2 \le 1\) and \(|r_i| \le 2\) gives a Rupert pair \((s, s\, Q_j(r))\).

If each of the 15 root boxes carries an accepted skeleton with accepted subtrees for its holes, then \(\operatorname{\mathbf{P}}\) is not Rupert.

The Noperthedron is not Rupert (Cayley.KProof.noperthedron_not_rupert). Hence there is a convex polyhedron with nonempty interior that is not Rupert (Cayley.KProof.exists_not_rupert).

If \(\operatorname{\mathbf{P}}\) is Rupert, then there is a reduced \((u, v, j, r)\) such that \(\bigl(s(u, v),\ s(u, v)\, Q_j(r)\bigr)\) is a Rupert pair.

The convex polyhedron with vertex set \(V\) is Rupert if and only if the convex hull of \(V\) is a Rupert set, i.e. there is a pose (two rotations and an offset) under which the closure of the inner shadow lies in the interior of the outer shadow.

Let \(S \subseteq \operatorname{\mathbb {R}}^3\) be point-symmetric and convex. If a pose with offset \(o\) passes \(S\) through itself, then so does the same pose with offset \(0\).

Let \(S\) be a vertex of \(\operatorname{\mathbf{P}}\) and \(w \ne 0\). If

for every vertex \(T\) of \(\operatorname{\mathbf{P}}\), then \((R_o, R_i)\) is not a Rupert pair.

If a tree is accepted on a box, then the box is covered.