Cartesian-product slack matrices: complexity-six polygon products
Recorded by the registry's curators from GitHub; the authors did not submit it here.
Sidney Holden
For convex polygons $P,Q$ with $\operatorname{xc}(P)=\operatorname{xc}(Q)=6$,
the note proves $\operatorname{xc}(P\times Q)=12$ by a finite,
certificate-based support argument. Every such polygon has between six and
nine vertices. A hypothetical eleven-term nonnegative factorization of the
complete product slack matrix must satisfy explicit row-degree, vertex-slice,
edge-slice, pure-column and coverage conditions. These give ten Boolean
formulas, one for each unordered pair of polygon sizes, and each has a
deletion-free LRAT refutation, checked by separate Python and C++
implementations and by a hint-free unit-propagation check. Together with
proofs from the author's preceding notes, the result gives additivity for
every pair of polytopes with extension complexities at most six. The note
also gives an integer octagon of complexity six with an exact twelve-term
factorization of its square, and a higher-complexity support pattern that
admits no numerical weights.
Claims
Files and sources
- Paper
- OpenProblemsInNLA @ eb7c9d6, NR-02/report.pdf ↗
- Posted on GitHub
- 14 September 2026
No verification run is on record for this version.