Theorem 2 (companion theorem; not used in the proof of the goal) — fixed-dimensional no-augmentation APTAS
OpenBeyondConvexity.APTAS.Supplement.theorem_2Let be any fixed integer and any fixed class of compact rational polyhedral regions with nonempty connected interiors, given by finite simplicial decompositions of unrestricted complexity. Inputs are finite labeled multisets of normalized class regions, each fitting the exact axis-aligned unit hypercube. Assume the full higher-dimensional uniform rasterizability and representative-roundability interfaces, with Euclidean diameter, maximum coordinate span, Lebesgue volume, arbitrary real phases and scales, and uniform effective rational services.
There is one finite-alphabet machine, a computable natural exponent and a nonnegative integer allowance , chosen for this before the input. For every integer and valid input of complete binary length , it returns an exact rational translation-only packing in unit hypercubes with
Its actual time and the complete output encoding length are at most . The optimum uses arbitrary real translations of the actual input regions. Every occurrence is packed, interiors in a common bin are disjoint and boundary contact is allowed. Empty input is included. No rotation, enlargement, convexity, bounded containment width, fixed shape family or boundary-complexity bound is assumed.
For every real , set . Then and , and the same machine on this index returns such a packing with
with the same polynomial time and output length. The allowance may depend on accuracy, fixed class and fixed dimension, but is independent of the instance, and ; it need not be computable.
This is Theorem 2, a companion to the mission goal Theorem 1, not a step in that goal's proof. Its higher-dimensional extension remains an open Lean proof obligation.
Differences from the source:
- encoding: compact rational polyhedral regions with nonempty connected interiors represented by simplicial decompositions → finite lists of full-dimensional rational closed simplices in EuclideanSpace, with common-face compatibility and IsConnected interior; normalized fitting list occurrences and fixed binary encoders; reason: spells out the Section 7 representation and inherited Section 2 conventions; every admissible shape and arbitrary finite input complexity remain allowed
- encoding: higher dimensional versions of uniform rasterizability and uniform representative roundability → explicit hypercubic grid and Lebesgue-volume rasterization, real-parameter/real-scale rounding guarantees, plus one finite rational-input rounding machine with computable parameter bounds and fully charged input data; reason: expands Definitions 2-5 dimensionally, separating analytic real quantifiers from encoded computational queries without assuming an APTAS or any proof lemma
- encoding: APTAS for every real accuracy with rational translations, polynomial encoding length, computable parameter-dependent polynomial time and an instance-independent integer allowance → one finite-alphabet machine on integer accuracy indices k, a computable exponent g(k), an integer allowance delta(k), and the explicit bridge k=ceil(1/epsilon)+1 for all real 0<epsilon<1; reason: Section 3 permits smaller rational accuracy and the uniform construction supplies one program; for L>=2 parameter-only coefficients are absorbed in the exponent; all guarantees describe the same returned packing
import Definitions.Def_BeyondConvexity_APTAS_Supplement_UniformRasterizable import Definitions.Def_BeyondConvexity_APTAS_Supplement_UniformRepresentativeRoundable import Definitions.Def_BeyondConvexity_APTAS_Supplement_APTASScheme
namespace BeyondConvexity.APTAS.Supplement
/-- Silva, Dell'Arriva, Miyazawa, STOC 2027 submission #890 (October 2026),
Theorem 2, printed p.16 / PDF p.17. Every fixed d >= 2, without convexity,
boundary-complexity or containment-width restrictions. Definitions 2--5 are
interpreted dimensionally with Euclidean diameter and Lebesgue d-volume.
The conclusion includes all real accuracies, exact unit hypercubes, rational
translations, polynomial output length, computable bit-time exponents, and
instance-independent nonnegative integer additive allowances. -/
theorem theorem_2 (d : ℕ) (hd : 2 ≤ d) (P : Set (PolyhedralRegion d))
(hRaster : UniformRasterizable P) (hRound : UniformRepresentativeRoundable P) :
APTASScheme P := by sorry
end BeyondConvexity.APTAS.Supplement