Documentation

LeanPool.MovingSofa.GerverSofa.KernelOnly.Core.Bundle001

Gerver sofa: related certificate and semantic modules #

Gerver sofa dependency batch #

Basic planar geometry for the moving-sofa problem #

This file fixes the exact hallway convention used by the manuscript. The inner quadrant is open, so contact with an inner wall is allowed.

@[reducible, inline]

Cartesian coordinates for the hallway and sofa geometry.

Equations
Instances For

    Horizontal unit-width arm (-∞,1] × [0,1].

    Equations
    Instances For

      Vertical unit-width arm [0,1] × (-∞,1].

      Equations
      Instances For

        Closed outer quarter-plane (-∞,1]².

        Equations
        Instances For

          Open inner quarter-plane (-∞,0)².

          Equations
          Instances For

            The standard unit right-angled hallway.

            Equations
            Instances For

              Quarter-plane presentation of the standard hallway.

              @[simp]
              @[simp]
              theorem GerverSofa.mem_verticalArm (p : Point) :
              p ∈ verticalArm ↔ 0 ≤ p.1 ∧ p.1 ≤ 1 ∧ p.2 ≤ 1
              @[simp]
              @[simp]

              Specification boundary for interval/Krawczyk certification #

              The records below make the logical target explicit. A completed numerical formalisation must construct these records from exact interval operations, Taylor bounds for sin/cos, a certified interval Jacobian and the general Krawczyk theorem. No global axiom is introduced here.

              structure GerverSofa.CertifiedUniqueSolution {α : Type u_1} (P : α → Prop) (X : Set α) :
              Type u_1

              A unique solution of a predicate inside an explicit set.

              • solution : α

                The certified point satisfying the predicate in the specified domain.

              • solution_mem : self.solution ∈ X
              • satisfies : P self.solution
              • unique_iff (y : α) : y ∈ X → (P y ↔ y = self.solution)
              Instances For
                theorem GerverSofa.CertifiedUniqueSolution.unique {α : Type u_1} {P : α → Prop} {X : Set α} (c : CertifiedUniqueSolution P X) (y : α) (hy : y ∈ X) (hP : P y) :

                Any other solution in the certified domain equals the recorded solution.

                @[reducible, inline]
                abbrev GerverSofa.Vec (n : ℕ) :

                Real coordinate vectors indexed by a finite type.

                Equations
                Instances For
                  def GerverSofa.CertifiedUniqueZero {n : ℕ} (F : Vec n → Vec n) (X : Set (Vec n)) :

                  A unique zero of a vector-valued function in a set.

                  Equations
                  Instances For

                    Exact rational intervals #

                    This module is intentionally small. It provides the decidable relations used to audit the published output manifest. It does not assert that a particular transcendental expression is enclosed; that analytic soundness is a distinct proof obligation.

                    Rational endpoints used by exact interval computations; no ordering is assumed.

                    • lo : ℚ

                      Lower endpoint of the interval.

                    • hi : ℚ

                      Upper endpoint of the interval.

                    Instances For
                      Equations
                      • One or more equations did not get rendered due to their size.
                      Instances For
                        Equations
                        Instances For

                          Strict inclusion in the interior of another interval.

                          Equations
                          Instances For

                            Point interval.

                            Equations
                            Instances For

                              Exact interval addition.

                              Equations
                              Instances For

                                Exact interval negation.

                                Equations
                                Instances For

                                  Exact interval subtraction.

                                  Equations
                                  Instances For

                                    Product hull of two rational intervals.

                                    Equations
                                    Instances For

                                      Real semantics #

                                      Semantic membership of a real number in a rational interval.

                                      Equations
                                      Instances For
                                        @[simp]
                                        theorem GerverSofa.RatInterval.contains_add {a b : RatInterval} {x y : ℝ} (hx : a.Contains x) (hy : b.Contains y) :
                                        (a.add b).Contains (x + y)

                                        Exact interval addition is sound over the reals.

                                        Exact interval negation is sound over the reals.

                                        theorem GerverSofa.RatInterval.contains_sub {a b : RatInterval} {x y : ℝ} (hx : a.Contains x) (hy : b.Contains y) :
                                        (a.sub b).Contains (x - y)

                                        Exact interval subtraction is sound over the reals.

                                        theorem GerverSofa.RatInterval.contains_of_subset {x outer : RatInterval} {r : ℝ} (hsub : outer.lo ≤ x.lo ∧ x.hi ≤ outer.hi) (hr : x.Contains r) :
                                        outer.Contains r

                                        Closed interval inclusion transports semantic membership.

                                        Multiplicative soundness #

                                        theorem GerverSofa.RatInterval.contains_mul {a b : RatInterval} {x y : ℝ} (hx : a.Contains x) (hy : b.Contains y) :
                                        (a.mul b).Contains (x * y)

                                        The four-corner product hull contains every real product of members.

                                        theorem GerverSofa.RatInterval.contains_scale {a : ℚ} {z : RatInterval} {x : ℝ} (hx : z.Contains x) :
                                        ((point a).mul z).Contains (↑a * x)

                                        Rational scaling is a special case of sound interval multiplication.

                                        theorem GerverSofa.RatInterval.valid_of_contains {z : RatInterval} {x : ℝ} (hx : z.Contains x) :
                                        ↑z.lo ≤ ↑z.hi

                                        Semantic validity follows from the existence of a contained real point.

                                        theorem GerverSofa.RatInterval.contains_of_strictInsideB {x outer : RatInterval} {r : ℝ} (hstrict : x.strictInsideB outer = true) (hr : x.Contains r) :
                                        outer.Contains r

                                        A strict Boolean inclusion is, in particular, a closed semantic inclusion.

                                        Exact rational audit of the published certificate manifest #

                                        This file contains no floating-point literals. Every value is emitted as an integer numerator and a positive integer denominator from the deterministic Python Fraction replay. kernel reduction therefore checks the strict box inclusions and every published rational margin in the Lean kernel/runtime.

                                        This manifest audit deliberately does not by itself prove the analytic soundness of the sine/cosine enclosures or the Krawczyk existence theorem; those proof obligations are represented separately in KrawczykSpec.lean and GerverCertificate.lean.

                                        Reconstruct a natural number from base-10³⁵ chunks to share decimal elaboration.

                                        Equations
                                        Instances For

                                          Construct an exact rational number from its integer numerator and natural denominator.

                                          Equations
                                          Instances For

                                            The frozen rational enclosure of π used by the certificate manifest.

                                            Equations
                                            • One or more equations did not get rendered due to their size.
                                            Instances For

                                              The frozen interval obtained from the manifest’s Machin-formula computation.

                                              Equations
                                              • One or more equations did not get rendered due to their size.
                                              Instances For

                                                The four rational intervals specifying the reduced parameter box.

                                                Equations
                                                • One or more equations did not get rendered due to their size.
                                                Instances For

                                                  The twenty-two rational intervals specifying the full Romik parameter box.

                                                  Equations
                                                  • One or more equations did not get rendered due to their size.
                                                  Instances For

                                                    Small kernel-checkable chunks of the frozen rational certificate.

                                                    The previous one-shot package asked the kernel to normalize the whole executable replay in one enormous decide +kernel. That is logically sound but can take hours. Here the proof path uses the already frozen rational certificate and checks it in bounded, independent chunks. The expensive executable replay is still retained in ExactReplay.lean as a diagnostic cross-check, but it is not recomputed while building the trusted certificate.

                                                    Equations
                                                    Instances For

                                                      Executable exact-rational replay of the 4D and 22D Krawczyk inclusions #

                                                      This is a direct, floating-point-free transcription of the companion Python algorithm. It computes with ℚ, interval automatic differentiation and the frozen rational preconditioners. The analytic theorem saying that the Taylor intervals enclose the real sin and cos, and the abstract Krawczyk theorem, remain separate proof obligations; the arithmetic replay itself is decidable.

                                                      def GerverSofa.ExactReplay.q (n : ℤ) (d : ℕ := 1) :

                                                      Construct an exact rational number from its integer numerator and natural denominator.

                                                      Equations
                                                      Instances For

                                                        The singleton rational interval at zero.

                                                        Equations
                                                        Instances For

                                                          The singleton rational interval at one.

                                                          Equations
                                                          Instances For

                                                            Multiply an interval by a rational singleton using exact interval arithmetic.

                                                            Equations
                                                            Instances For

                                                              A factorial interpreted as an exact rational number.

                                                              Equations
                                                              Instances For
                                                                def GerverSofa.ExactReplay.signedTerm (k : ℕ) (x : ℚ) (power : ℕ) :

                                                                An alternating Taylor term with the specified power and factorial denominator.

                                                                Equations
                                                                Instances For

                                                                  The finite odd-power Taylor sum for sine at a rational argument.

                                                                  Equations
                                                                  Instances For

                                                                    The finite even-power Taylor sum for cosine at a rational argument.

                                                                    Equations
                                                                    Instances For

                                                                      The interval between the nineteen- and twenty-term sine Taylor sums.

                                                                      Equations
                                                                      • One or more equations did not get rendered due to their size.
                                                                      Instances For

                                                                        The interval between the nineteen- and twenty-term cosine Taylor sums.

                                                                        Equations
                                                                        • One or more equations did not get rendered due to their size.
                                                                        Instances For

                                                                          The rational π enclosure used for trigonometric argument reduction.

                                                                          Equations
                                                                          • One or more equations did not get rendered due to their size.
                                                                          Instances For

                                                                            A finite alternating rational Taylor sum for arctangent.

                                                                            Equations
                                                                            Instances For
                                                                              def GerverSofa.ExactReplay.atanBound (x : ℚ) (lowTerms highTerms : ℕ) :

                                                                              The interval between two specified arctangent Taylor sums.

                                                                              Equations
                                                                              • One or more equations did not get rendered due to their size.
                                                                              Instances For

                                                                                Evaluate the Machin expression 16 atan(1/5) - 4 atan(1/239) by rational intervals.

                                                                                Equations
                                                                                • One or more equations did not get rendered due to their size.
                                                                                Instances For
                                                                                  def GerverSofa.ExactReplay.floorDecimal (x : ℚ) (digits : ℕ := 60) :

                                                                                  Exact downward rounding to a fixed number of decimal places.

                                                                                  Equations
                                                                                  Instances For
                                                                                    def GerverSofa.ExactReplay.ceilDecimal (x : ℚ) (digits : ℕ := 60) :

                                                                                    Exact upward rounding to a fixed number of decimal places.

                                                                                    Equations
                                                                                    Instances For

                                                                                      The same 60-decimal outward rounding used by the submitted verifier.

                                                                                      Equations
                                                                                      Instances For

                                                                                        Evaluate the small-argument sine enclosure with outward decimal rounding.

                                                                                        Equations
                                                                                        Instances For

                                                                                          Evaluate the small-argument cosine enclosure with outward decimal rounding.

                                                                                          Equations
                                                                                          Instances For

                                                                                            Clamp an interval to the physical angular range used by the Gerver certificate. If x ∈ [0, π/2] and x is enclosed by the input interval, then x is still enclosed after clamping once piI has been proved to contain Real.pi.

                                                                                            Equations
                                                                                            Instances For

                                                                                              A fail-closed enclosure used only when an externally supplied interval is too wide for the small-argument Taylor/range-reduction evaluator. Every certified Gerver call remains in one of the two sharp branches below, so this fallback does not alter the frozen replay.

                                                                                              Equations
                                                                                              Instances For

                                                                                                Complementary interval for the identity sin x = cos (π/2-x) and cos x = sin (π/2-x).

                                                                                                Equations
                                                                                                Instances For

                                                                                                  Evaluate sine by small-argument bounds and complementary-angle reduction.

                                                                                                  Equations
                                                                                                  • One or more equations did not get rendered due to their size.
                                                                                                  Instances For

                                                                                                    Evaluate cosine by small-argument bounds and complementary-angle reduction.

                                                                                                    Equations
                                                                                                    • One or more equations did not get rendered due to their size.
                                                                                                    Instances For

                                                                                                      An interval value together with a list of interval partial derivatives.

                                                                                                      • The interval enclosing the scalar value.

                                                                                                      • Interval enclosures for the coordinate partial derivatives.

                                                                                                      Instances For
                                                                                                        Equations
                                                                                                        • One or more equations did not get rendered due to their size.
                                                                                                        Instances For

                                                                                                          A constant interval with zero partial derivatives in every coordinate.

                                                                                                          Equations
                                                                                                          Instances For

                                                                                                            A rational singleton with zero partial derivatives.

                                                                                                            Equations
                                                                                                            Instances For

                                                                                                              An interval variable with the selected coordinate derivative equal to one.

                                                                                                              Equations
                                                                                                              Instances For

                                                                                                                Addition with interval propagation of all coordinate derivatives.

                                                                                                                Equations
                                                                                                                Instances For

                                                                                                                  Negation with interval propagation of all coordinate derivatives.

                                                                                                                  Equations
                                                                                                                  Instances For

                                                                                                                    Subtraction with interval propagation of all coordinate derivatives.

                                                                                                                    Equations
                                                                                                                    Instances For

                                                                                                                      Multiplication with interval propagation of all coordinate derivatives.

                                                                                                                      Equations
                                                                                                                      Instances For

                                                                                                                        Rational scaling with interval propagation of all coordinate derivatives.

                                                                                                                        Equations
                                                                                                                        Instances For

                                                                                                                          Sine with interval propagation of all coordinate derivatives.

                                                                                                                          Equations
                                                                                                                          Instances For

                                                                                                                            Cosine with interval propagation of all coordinate derivatives.

                                                                                                                            Equations
                                                                                                                            Instances For

                                                                                                                              Read an interval coordinate, returning the zero interval outside the list.

                                                                                                                              Equations
                                                                                                                              Instances For

                                                                                                                                Read a rational coordinate, returning zero outside the list.

                                                                                                                                Equations
                                                                                                                                Instances For

                                                                                                                                  Read a rational matrix row, returning the empty row outside the list.

                                                                                                                                  Equations
                                                                                                                                  Instances For

                                                                                                                                    Reduced 4D system #

                                                                                                                                    Direct 22D Romik system #

                                                                                                                                    Public proof-carrying view and optional executable cross-check #

                                                                                                                                    The full executable Krawczyk/grid replay above is intentionally retained, but normalizing it in one kernel reduction is prohibitively expensive. The trusted proof path therefore consumes the frozen exact-rational certificate emitted by the independent replay and checks that certificate in CertificateManifest. This is the standard proof-carrying-data split: expensive certificate discovery is outside the kernel; small rational certificate verification is inside it.

                                                                                                                                    The executable wrappers prefixed by executable remain available for offline cross-checking and provenance.

                                                                                                                                    The rational interval used internally by the executable replay for Real.pi.

                                                                                                                                    Equations
                                                                                                                                    Instances For

                                                                                                                                      Public wrapper around the executable sine enclosure.

                                                                                                                                      Equations
                                                                                                                                      Instances For

                                                                                                                                        Public wrapper around the executable cosine enclosure.

                                                                                                                                        Equations
                                                                                                                                        Instances For

                                                                                                                                          Frozen reduced input box used by the trusted certificate.

                                                                                                                                          Equations
                                                                                                                                          Instances For

                                                                                                                                            Frozen direct-system input box used by the trusted certificate.

                                                                                                                                            Equations
                                                                                                                                            Instances For