Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Checked fraction-free Gram-Schmidt refinement foundations

Definition
LARLLL_GramSchmidtRefinement

by BoomShaKaLaaaKa · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-algebralllnative-algorithmsregev

The original Bareiss and Gram-Schmidt refinement data and their proof-carrying auxiliary invariants used to connect the concrete integer LLL state to rational orthogonalization.

Definition code
import Definitions.Def_LARLLL_KernelTransport

section
/-
Copyright (c) 2026 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Kim Morrison
-/






set_option autoImplicit true



section

/-!
No-pivot Bareiss loop invariant for `hex-matrix-theory`.

This module proves the recursive bordered-minor invariant of the no-pivot
Bareiss recurrence: after `k` regular Bareiss steps, the trailing entries of
the working matrix agree with the corresponding bordered-minor determinants of
the source matrix, and the previous pivot agrees with the determinant of the
leading prefix of size `k`. As an immediate corollary, when all leading-prefix
determinants are nonzero (`NonzeroBareissPivots`), the loop never takes the
singular branch.

The invariant proof composes the bordered-minor `stepMatrix` update lemma
(`Hex.Matrix.stepMatrixWith_borderedMinor_update`) with the bordered-minor
specialization of Desnanot-Jacobi (`desnanot_jacobi_borderedMinor` in the
parent module) and the exact-division equation
(`bareissExactDiv_borderedMinor_of_mul_eq`).
-/

namespace HexMatrixTheory

universe u

variable {R : Type u} [CommRing R] [DecidableEq R] {n : Nat}
variable {quot : R → R → R}
variable {hquot : ∀ a b : R, b ≠ 0 → quot (a * b) b = a}

/-- An exact quotient makes a nontrivial commutative ring an integral domain. -/
theorem isDomain_of_quot (quot : R → R → R)
    (hquot : ∀ a b : R, b ≠ 0 → quot (a * b) b = a)
    (h1 : (1 : R) ≠ 0) : IsDomain R := by
  let _ : Div R := ⟨quot⟩
  have _ : Hex.ExactDivLaws R := ⟨hquot⟩
  let _ : Nontrivial R := ⟨⟨1, 0, h1⟩⟩
  let _ : NoZeroDivisors R := ⟨by
    intro a b hab
    by_cases ha : a = 0
    · exact Or.inl ha
    by_cases hb : b = 0
    · exact Or.inr hb
    exact (Hex.ExactDivLaws.mul_ne_zero ha hb hab).elim⟩
  exact NoZeroDivisors.to_isDomain R

/-- The `k`-bordered minor of `M` at the corner row/column `⟨k, hk⟩` is exactly
the `(k + 1)`-leading prefix of `M`. This identifies the trailing-corner entry
under the no-pivot Bareiss invariant with a leading-prefix determinant. -/
theorem borderedMinor_corner_eq_principalSubmatrix {R : Type u}
    (M : Hex.Matrix R n n) (k : Nat) (hk : k < n) :
    Hex.Matrix.borderedMinor M k hk ⟨k, hk⟩ ⟨k, hk⟩ =
      Hex.Matrix.principalSubmatrix M (k + 1) (Nat.succ_le_of_lt hk) := by
  apply Hex.Matrix.ext_getElem
  intro r c
  rw [Hex.Matrix.getElem_principalSubmatrix]
  simp only [Hex.Matrix.borderedMinor]
  rw [Hex.Matrix.getElem_ofFn]
  simp only [Hex.Matrix.getElem_pair_eq_nested]
  have hr1 := r.isLt
  have hc1 := c.isLt
  have hrr : (if hr : r.val < k then (⟨r.val, Nat.lt_trans hr hk⟩ : Fin n) else ⟨k, hk⟩) =
      (⟨r.val, Nat.lt_of_lt_of_le r.isLt (Nat.succ_le_of_lt hk)⟩ : Fin n) := by
    split
    · rfl
    · simp only [Fin.mk.injEq]; omega
  have hcc : (if hc : c.val < k then (⟨c.val, Nat.lt_trans hc hk⟩ : Fin n) else ⟨k, hk⟩) =
      (⟨c.val, Nat.lt_of_lt_of_le c.isLt (Nat.succ_le_of_lt hk)⟩ : Fin n) := by
    split
    · rfl
    · simp only [Fin.mk.injEq]; omega
  rw [hrr, hcc]



/-- Bordered-minor invariant of the no-pivot Bareiss recurrence:
- `singularStep` is `none` (no pivot has been zero yet);
- the previous pivot equals the determinant of the leading prefix of size
  `state.step` (which is `1` for `state.step = 0`);
- the previous pivot is nonzero (so the next step's exact division is valid);
- every trailing entry `(i, j)` with `state.step ≤ i.val` and
  `state.step ≤ j.val` agrees with the determinant of the
  `state.step`-bordered minor with trailing row `i` and column `j`.

The implication on diagonal entries (`state.matrix[k][k]` agrees with the
leading-prefix determinant of size `k + 1`) follows from `trailing_eq` taken
at `i = j = ⟨k, _⟩` together with `borderedMinor_corner_eq_principalSubmatrix`. -/
structure BareissNoPivotInvariant
    (source : Hex.Matrix R n n) (state : Hex.Matrix.BareissState R n) : Prop where
  singular_none : state.singularStep = none
  step_le : state.step ≤ n
  prevPivot_eq :
    state.prevPivot =
      Hex.Matrix.det (Hex.Matrix.principalSubmatrix source state.step step_le)
  prevPivot_ne : state.prevPivot ≠ 0
  trailing_eq :
    ∀ (h : state.step < n) (i j : Fin n)
        (_ : state.step ≤ i.val) (_ : state.step ≤ j.val),
      state.matrix[i][j] =
        Hex.Matrix.det (Hex.Matrix.borderedMinor source state.step h i j)

/-- The initial Bareiss no-pivot state satisfies the bordered-minor invariant:
the matrix is the source itself, and the previous-pivot convention is
`det (principalSubmatrix _ 0 _) = 1`. -/
theorem bareissNoPivotInvariant_initialWith {R : Type u} [CommRing R]
    (M : Hex.Matrix R n n) (h1 : (1 : R) ≠ 0) :
    BareissNoPivotInvariant M (Hex.Matrix.noPivotInitialState M) where
  singular_none := rfl
  step_le := Nat.zero_le _
  prevPivot_eq := by
    show (1 : R) = Hex.Matrix.det (Hex.Matrix.principalSubmatrix M 0 (Nat.zero_le n))
    simp
  prevPivot_ne := by
    show (1 : R) ≠ 0
    exact h1
  trailing_eq := by
    intro h i j _hi _hj
    have h0 : 0 < n := by omega
    -- For `state.step = 0`, the bordered minor is the `1 × 1` block with the
    -- single entry `M[i][j]`.
    show M[i][j] = Hex.Matrix.det (Hex.Matrix.borderedMinor M 0 h0 i j)
    rw [Hex.Matrix.det_one_by_one]
    show M[i][j] =
        (Hex.Matrix.borderedMinor M 0 h0 i j)[(Fin.last 0)][(Fin.last 0)]
    rw [Hex.Matrix.borderedMinor_entry_last_last]

/-- Integer compatibility form of `bareissNoPivotInvariant_initialWith`. -/
theorem bareissNoPivotInvariant_initial (M : Hex.Matrix Int n n) :
    BareissNoPivotInvariant M (Hex.Matrix.noPivotInitialState M) :=
  bareissNoPivotInvariant_initialWith M (by omega)

/-- One regular no-pivot Bareiss step preserves the bordered-minor invariant.
Given a state satisfying the invariant with `state.step + 1 < n` and a nonzero
diagonal pivot, the state produced by one `noPivotLoop` iteration also
satisfies the invariant. -/
 theorem _root_.HexMatrixTheory.bareissNoPivotInvariant_step
    {R : Type u} [CommRing R]
    (quot : R → R → R)
    (hquot : ∀ a b : R, b ≠ 0 → quot (a * b) b = a)
    (source : Hex.Matrix R n n) (state : Hex.Matrix.BareissState R n)
    (hinv : BareissNoPivotInvariant source state)
    (hDone : state.step + 1 < n)
    (hp : state.matrix[(⟨state.step, Nat.lt_of_succ_lt hDone⟩ : Fin n)][
        (⟨state.step, Nat.lt_of_succ_lt hDone⟩ : Fin n)] ≠ 0) :
    BareissNoPivotInvariant source
      { step := state.step + 1
        matrix := Hex.Matrix.stepMatrixWith quot state.matrix state.step
          (state.matrix[(⟨state.step, Nat.lt_of_succ_lt hDone⟩ : Fin n)][
            (⟨state.step, Nat.lt_of_succ_lt hDone⟩ : Fin n)]) state.prevPivot
        prevPivot := state.matrix[(⟨state.step, Nat.lt_of_succ_lt hDone⟩ : Fin n)][
          (⟨state.step, Nat.lt_of_succ_lt hDone⟩ : Fin n)]
        rowSwaps := state.rowSwaps
        singularStep := none } where
  singular_none := rfl
  step_le := Nat.le_of_lt hDone
  prevPivot_eq := by
    -- Pivot at step k equals det (principalSubmatrix source (k + 1) _), via
    -- trailing_eq @ (i = j = ⟨k, _⟩) and borderedMinor_corner_eq_principalSubmatrix.
    have hk : state.step < n := Nat.lt_of_succ_lt hDone
    have hkk :
        state.matrix[(⟨state.step, hk⟩ : Fin n)][(⟨state.step, hk⟩ : Fin n)] =
          Hex.Matrix.det
            (Hex.Matrix.borderedMinor source state.step hk
              (⟨state.step, hk⟩ : Fin n) (⟨state.step, hk⟩ : Fin n)) :=
      hinv.trailing_eq hk ⟨state.step, hk⟩ ⟨state.step, hk⟩
        (Nat.le_refl _) (Nat.le_refl _)
    show state.matrix[(⟨state.step, hk⟩ : Fin n)][(⟨state.step, hk⟩ : Fin n)] = _
    rw [hkk, borderedMinor_corner_eq_principalSubmatrix source state.step hk]
  prevPivot_ne := hp
  trailing_eq := by
    intro hnext i j hi hj
    -- Unfold the structure projection so omega can see through it.
    change state.step + 1 ≤ i.val at hi
    change state.step + 1 ≤ j.val at hj
    have hk : state.step < n := Nat.lt_of_succ_lt hDone
    have hi' : state.step < i.val := hi
    have hj' : state.step < j.val := hj
    -- The pivot for the borderedMinor update is the `(k, k)` entry of
    -- `state.matrix`, which by `trailing_eq` equals
    -- `det (borderedMinor source state.step _ ⟨k, _⟩ ⟨k, _⟩)`.
    have hpivot_eq :
        state.matrix[(⟨state.step, hk⟩ : Fin n)][(⟨state.step, hk⟩ : Fin n)] =
          Hex.Matrix.det
            (Hex.Matrix.borderedMinor source state.step hk
              (⟨state.step, Nat.lt_trans hj' j.isLt⟩ : Fin n)
              (⟨state.step, Nat.lt_trans hi' i.isLt⟩ : Fin n)) :=
      hinv.trailing_eq hk ⟨state.step, hk⟩ ⟨state.step, hk⟩
        (Nat.le_refl _) (Nat.le_refl _)
    -- `current[i][j]` agrees with the bordered minor at (i, j), via trailing_eq.
    have hentry :
        state.matrix[i][j] =
          Hex.Matrix.det (Hex.Matrix.borderedMinor source state.step hk i j) :=
      hinv.trailing_eq hk i j (Nat.le_of_lt hi') (Nat.le_of_lt hj')
    -- `current[i][⟨k, _⟩]` agrees with the bordered minor at (i, ⟨k, _⟩).
    have hleft :
        state.matrix[i][(⟨state.step, Nat.lt_trans hi' i.isLt⟩ : Fin n)] =
          Hex.Matrix.det
            (Hex.Matrix.borderedMinor source state.step hk i
              (⟨state.step, Nat.lt_trans hi' i.isLt⟩ : Fin n)) :=
      hinv.trailing_eq hk i ⟨state.step, Nat.lt_trans hi' i.isLt⟩
        (Nat.le_of_lt hi') (Nat.le_refl _)
    -- `current[⟨k, _⟩][j]` agrees with the bordered minor at (⟨k, _⟩, j).
    have htop :
        state.matrix[(⟨state.step, Nat.lt_trans hj' j.isLt⟩ : Fin n)][j] =
          Hex.Matrix.det
            (Hex.Matrix.borderedMinor source state.step hk
              (⟨state.step, Nat.lt_trans hj' j.isLt⟩ : Fin n) j) :=
      hinv.trailing_eq hk ⟨state.step, Nat.lt_trans hj' j.isLt⟩ j
        (Nat.le_refl _) (Nat.le_of_lt hj')
    -- Desnanot-Jacobi gives the exact-division premise.
    have hdesnanot :
        Hex.Matrix.det (Hex.Matrix.borderedMinor source (state.step + 1) hnext i j) *
            state.prevPivot =
          Hex.Matrix.det (Hex.Matrix.borderedMinor source state.step hk
              (⟨state.step, Nat.lt_trans hj' j.isLt⟩ : Fin n)
              (⟨state.step, Nat.lt_trans hi' i.isLt⟩ : Fin n)) *
            Hex.Matrix.det (Hex.Matrix.borderedMinor source state.step hk i j) -
            Hex.Matrix.det (Hex.Matrix.borderedMinor source state.step hk
              i (⟨state.step, Nat.lt_trans hi' i.isLt⟩ : Fin n)) *
            Hex.Matrix.det (Hex.Matrix.borderedMinor source state.step hk
              (⟨state.step, Nat.lt_trans hj' j.isLt⟩ : Fin n) j) := by
      rw [hinv.prevPivot_eq]
      exact desnanot_jacobi_borderedMinor source state.step hk hnext i j hi' hj'
    have hexact :
        quot
            (Hex.Matrix.det (Hex.Matrix.borderedMinor source state.step hk
              (⟨state.step, Nat.lt_trans hj' j.isLt⟩ : Fin n)
              (⟨state.step, Nat.lt_trans hi' i.isLt⟩ : Fin n)) *
              Hex.Matrix.det (Hex.Matrix.borderedMinor source state.step hk i j) -
              Hex.Matrix.det (Hex.Matrix.borderedMinor source state.step hk
                i (⟨state.step, Nat.lt_trans hi' i.isLt⟩ : Fin n)) *
              Hex.Matrix.det (Hex.Matrix.borderedMinor source state.step hk
                (⟨state.step, Nat.lt_trans hj' j.isLt⟩ : Fin n) j))
            state.prevPivot =
          Hex.Matrix.det (Hex.Matrix.borderedMinor source (state.step + 1) hnext i j) :=
      Hex.Matrix.exactQuot_borderedMinor_of_mul_eq quot hquot source state.step hk hnext i j
        hi' hj' state.prevPivot hinv.prevPivot_ne hdesnanot
    -- Apply `stepMatrix_borderedMinor_update` to obtain the updated entry.
    show (Hex.Matrix.stepMatrixWith quot state.matrix state.step
        (state.matrix[(⟨state.step, hk⟩ : Fin n)][(⟨state.step, hk⟩ : Fin n)])
        state.prevPivot)[i][j] =
      Hex.Matrix.det (Hex.Matrix.borderedMinor source (state.step + 1) hnext i j)
    exact Hex.Matrix.stepMatrixWith_borderedMinor_update quot source state.matrix
      state.step hk hnext i j hi' hj'
      (state.matrix[(⟨state.step, hk⟩ : Fin n)][(⟨state.step, hk⟩ : Fin n)])
      state.prevPivot hpivot_eq hentry hleft htop hexact





























/-- Sign contributed by the row swaps recorded in a Bareiss state. -/
@[expose]
def bareissStateSign (state : Hex.Matrix.BareissState R n) : R :=
  if state.rowSwaps % 2 = 0 then 1 else -1

/-- Row-pivoted Bareiss invariant. The current working state is interpreted as
a no-pivot Bareiss state for a logical source obtained from the original source
by the row swaps already performed; the sign field records the determinant
relation back to the original source. -/
@[expose]
def BareissPivotInvariant
    (source : Hex.Matrix R n n) (state : Hex.Matrix.BareissState R n) : Prop :=
  ∃ logicalSource : Hex.Matrix R n n,
    Hex.Matrix.det source = bareissStateSign state * Hex.Matrix.det logicalSource ∧
      BareissNoPivotInvariant logicalSource state





















/-- Outcome-driven companion of `noPivotLoop_invariant`: if the no-pivot
Bareiss loop run from a valid invariant state does NOT record a singular step
during its `fuel` iterations, the invariant continues to hold afterward. The
non-singular outcome guarantees every visited pivot was nonzero, which is the
hypothesis the inductive step needs.

This is the no-pivot analog of `pivotLoop_invariant_of_singularStep_eq_none`. -/
theorem noPivotLoopWith_invariant_of_singularStep_eq_none
    (hquot : ∀ a b : R, b ≠ 0 → quot (a * b) b = a)
    (source : Hex.Matrix R n n)
    (fuel : Nat) (state : Hex.Matrix.BareissState R n)
    (hinv : BareissNoPivotInvariant source state)
    (hregular : (Hex.Matrix.noPivotLoopWith quot fuel state).singularStep = none) :
    BareissNoPivotInvariant source (Hex.Matrix.noPivotLoopWith quot fuel state) := by
  induction fuel generalizing state with
  | zero =>
      simpa only [Hex.Matrix.noPivotLoopWith_zero_fuel (quot := quot)] using hinv
  | succ fuel ih =>
      by_cases hDone : state.step + 1 < n
      · by_cases hp0 :
            state.matrix[(⟨state.step, Nat.lt_of_succ_lt hDone⟩ : Fin n)][
              (⟨state.step, Nat.lt_of_succ_lt hDone⟩ : Fin n)] = 0
        · rw [Hex.Matrix.noPivotLoopWith_of_singular (quot := quot) fuel state hDone hp0] at hregular
          simp at hregular
        · rw [Hex.Matrix.noPivotLoopWith_of_regular (quot := quot) fuel state hDone hp0]
          apply ih
          · exact _root_.HexMatrixTheory.bareissNoPivotInvariant_step quot hquot source state hinv hDone hp0
          · simpa [Hex.Matrix.noPivotLoopWith_of_regular (quot := quot) fuel state hDone hp0]
              using hregular
      · simpa [Hex.Matrix.noPivotLoopWith_done (quot := quot) fuel state hDone] using hinv

/-- Integer compatibility form of
`noPivotLoopWith_invariant_of_singularStep_eq_none`. -/
theorem noPivotLoop_invariant_of_singularStep_eq_none
    (source : Hex.Matrix Int n n)
    (fuel : Nat) (state : Hex.Matrix.BareissState Int n)
    (hinv : BareissNoPivotInvariant source state)
    (hregular : (Hex.Matrix.noPivotLoop fuel state).singularStep = none) :
    BareissNoPivotInvariant source (Hex.Matrix.noPivotLoop fuel state) :=
  noPivotLoopWith_invariant_of_singularStep_eq_none Int.mul_ediv_cancel
    source fuel state hinv hregular















/-! # Failed Bareiss column dependence

Helper for the row-pivoted singular Bareiss branch: if the pivot search at
level `k` fails (the entire `k`-bordered trailing column is zero) and the
preceding leading-prefix determinant is nonzero, then there is an explicit
linear combination of the columns of `source` — with coefficients given by the
signed `k × k` cofactors of the leading prefix augmented with column `k` —
that vanishes at every row. The coefficient on column `k` is
`Hex.Matrix.det (Hex.Matrix.principalSubmatrix source k _)`, which is nonzero by
hypothesis. -/

/-- The `k × (k+1)` top block used to define the failed-pivot column
dependence: leading `k` rows of `source`, restricted to columns `0..k-1`
followed by column `k`. -/
@[expose]
def failedBareissTopBlock
    (source : Hex.Matrix R n n) (k : Nat) (hk : k < n) :
    Matrix (Fin k) (Fin (k + 1)) R :=
  fun s c =>
    if hc : c.val < k then
      matrixEquiv source (⟨s.val, Nat.lt_trans s.isLt hk⟩ : Fin n)
        (⟨c.val, Nat.lt_trans hc hk⟩ : Fin n)
    else
      matrixEquiv source (⟨s.val, Nat.lt_trans s.isLt hk⟩ : Fin n) ⟨k, hk⟩

/-- Coefficient function for the failed-pivot column dependence. The value at
`c` is `(-1)^(k + c.val) * det(failedBareissTopBlock with column c removed)` for
`c.val ≤ k` and `0` otherwise. The coefficient on column `k` is
`det (principalSubmatrix source k _)`; see `failedBareissColumn_at_pivot`. -/
@[expose]
noncomputable def failedBareissColumn
    (source : Hex.Matrix R n n) (k : Nat) (hk : k < n) :
    Fin n → R :=
  fun c =>
    if hc : c.val ≤ k then
      (-1) ^ (k + c.val) *
        Matrix.det
          ((failedBareissTopBlock source k hk).submatrix id
            (⟨c.val, Nat.lt_succ_of_le hc⟩ : Fin (k + 1)).succAbove)
    else 0





















































end HexMatrixTheory

/- Modified compatibility port (2026-11-15): imports namespaced under
Solutions.RegevBridgeNativeLLLVendor; pure Lean portability changes and removal
of native runtime hooks are recorded in MODIFICATIONS.json and the provenance
receipt. Original copyright/author notices and Apache-2.0 license are retained. -/

end

end

section
/-
Copyright (c) 2026 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Kim Morrison
-/






set_option autoImplicit true



section

/-!
Mathlib-side determinantal theory for the integer Gram-Schmidt surface of
`hex-gram-schmidt`.

This module relates the executable leading integer Gram determinant `gramDet`
to products of squared norms of the orthogonal Gram-Schmidt basis rows.  Its
spine is a rational column-operation reduction from `leadingGramMatrixInt`
(via the interpolating `progressMatrix`, the triangular `auxMatrix`, and the
`Int → Rat` cast law `det_intCast`) to the diagonal norm-squared matrix,
giving `gramDet_succ_rat` and `leadingGramMatrixInt_det_nonneg`.  Along the
way it builds the Cramer machinery (`scaledCoeffMatrix` solved through the
chosen `originalProjectionCoords`) that the sibling module uses to read off
the Gram-Schmidt coefficients `coeffs`.
-/

namespace Hex
namespace GramSchmidt
namespace Int







/-! # Gram determinant as a squared-norm product

The remaining theorems below build the rational column-operation reduction
from the leading Gram matrix to the diagonal Gram-Schmidt norm-squared
matrix, plus the integer→rational cast law for `det`. -/







/-- The cast of an Int matrix to a Rat matrix by entry-wise Int.cast. -/
 def _root_.Hex.GramSchmidt.Int.castIntDetMatrix {k : Nat} (M : Matrix Int k k) : Matrix Rat k k :=
  Matrix.ofFn fun i j => ((M[(i, j)] : Int) : Rat)



























/-- Cast an Int matrix row to a Rat row by entry-wise `Int.cast`. -/
 def _root_.Hex.GramSchmidt.Int.castIntRow (b : Matrix Int n m) (i : Fin n) : Vector Rat m :=
  Vector.map (fun x : Int => (x : Rat)) (b.row i)

/-- Cast an Int matrix to the Rat matrix whose rows are `castIntRow`. -/
 def _root_.Hex.GramSchmidt.Int.castIntMatrixRat (b : Matrix Int n m) : Matrix Rat n m :=
  Hex.Matrix.ofRows (b.rows.map (fun row => row.map (fun x : Int => (x : Rat))))





/-- Coefficients of the projection of row `i` onto the Gram-Schmidt prefix
`0, ..., j`, indexed by that prefix. -/
 noncomputable def _root_.Hex.GramSchmidt.Int.projectionCoeffPrefix
    (b : Matrix Int n m) (i j : Nat) (hi : i < n) (hj : j < n) :
    Vector Rat (j + 1) :=
  Vector.ofFn fun q =>
    GramSchmidt.entry (coeffs b) ⟨i, hi⟩
      ⟨q.val, Nat.lt_of_lt_of_le q.isLt (Nat.succ_le_of_lt hj)⟩

/-- The Gram-Schmidt prefix projection of row `i` onto rows `0, ..., j`, still
written in the orthogonal basis rows. -/
 noncomputable def _root_.Hex.GramSchmidt.Int.basisPrefixProjection
    (b : Matrix Int n m) (i j : Nat) (hi : i < n) (hj : j < n) :
    Vector Rat m :=
  Matrix.vecMul (_root_.Hex.GramSchmidt.Int.projectionCoeffPrefix b i j hi hj) (GramSchmidt.prefixRows (basis b) j hj)

 theorem _root_.Hex.GramSchmidt.Int.basisPrefixProjection_mem_basisSpan
    (b : Matrix Int n m) (i j : Nat) (hi : i < n) (hj : j < n) :
    GramSchmidt.prefixSpan (basis b) j hj
      (_root_.Hex.GramSchmidt.Int.basisPrefixProjection b i j hi hj) := by
  exact ⟨_root_.Hex.GramSchmidt.Int.projectionCoeffPrefix b i j hi hj, rfl⟩

 theorem _root_.Hex.GramSchmidt.Int.basisPrefixProjection_mem_originalSpan
    (b : Matrix Int n m) (i j : Nat) (hi : i < n) (hj : j < n) :
    GramSchmidt.prefixSpan (_root_.Hex.GramSchmidt.Int.castIntMatrixRat b) j hj
      (_root_.Hex.GramSchmidt.Int.basisPrefixProjection b i j hi hj) := by
  have key := ((basis_span b j hj (_root_.Hex.GramSchmidt.Int.basisPrefixProjection b i j hi hj)).mp
      (_root_.Hex.GramSchmidt.Int.basisPrefixProjection_mem_basisSpan b i j hi hj))
  simp only [_root_.Hex.GramSchmidt.Int.castIntMatrixRat, Hex.GramSchmidt.castIntMatrix] at key ⊢
  exact key

/-- Original-row coordinates for the projection of row `i` onto the row prefix
`0, ..., j`. The coordinates are chosen through the proved span equivalence
between original rows and Gram-Schmidt rows. -/
 noncomputable def _root_.Hex.GramSchmidt.Int.originalProjectionCoords
    (b : Matrix Int n m) (i j : Nat) (hi : i < n) (hj : j < n) :
    Vector Rat (j + 1) :=
  Classical.choose (_root_.Hex.GramSchmidt.Int.basisPrefixProjection_mem_originalSpan b i j hi hj)









/-- Auxiliary matrix `M_final` whose `(i, j)` entry is the rational inner
product `⟨b_i, b*_j⟩` between the cast integer row `b_i` and the
Gram-Schmidt orthogonal basis row `b*_j`. -/
 noncomputable def _root_.Hex.GramSchmidt.Int.auxMatrix (b : Matrix Int n m) (k : Nat) (hk : k ≤ n) :
    Matrix Rat k k :=
  Matrix.ofFn fun i j =>
    (_root_.Hex.GramSchmidt.Int.castIntRow b (GramSchmidt.liftFinLE i hk)).dotProduct
      ((basis b).row (GramSchmidt.liftFinLE j hk))











/-- Interpolating matrix between `leadingGramMatrixRat (castIntMatrix b)` (at
`s = 0`) and `auxMatrix b k hk` (at `s = k`). Columns with index `< s` have
already been replaced by basis-row dot products; columns with index `≥ s`
still hold the original `b`-row dot products. -/
 noncomputable def _root_.Hex.GramSchmidt.Int.progressMatrix (b : Matrix Int n m) (k : Nat)
    (hk : k ≤ n) (s : Nat) : Matrix Rat k k :=
  Matrix.ofFn fun i j =>
    if j.val < s then
      (_root_.Hex.GramSchmidt.Int.castIntRow b (GramSchmidt.liftFinLE i hk)).dotProduct
        ((basis b).row (GramSchmidt.liftFinLE j hk))
    else
      (_root_.Hex.GramSchmidt.Int.castIntRow b (GramSchmidt.liftFinLE i hk)).dotProduct
        (_root_.Hex.GramSchmidt.Int.castIntRow b (GramSchmidt.liftFinLE j hk))







/-- The col-op coefficient list for the `s`-th transition step: indices
`p : Fin s` lifted into `Fin k`. -/
 def _root_.Hex.GramSchmidt.Int.progressMatrixSources (k : Nat) (s : Nat) (hs : s < k) :
    List (Fin k) :=
  (List.finRange s).map fun p => ⟨p.val, Nat.lt_of_lt_of_le p.isLt (Nat.le_of_lt hs)⟩



/-- The col-op coefficient for source `src : Fin k`: equals
`-(coeffs b)[s][src.val]`. -/
 noncomputable def _root_.Hex.GramSchmidt.Int.progressMatrixCoeff (b : Matrix Int n m) (k : Nat)
    (hk : k ≤ n) (s : Nat) (hs : s < k) (src : Fin k) : Rat :=
  -(GramSchmidt.entry (coeffs b)
    ⟨s, Nat.lt_of_lt_of_le hs hk⟩
    ⟨src.val, Nat.lt_of_lt_of_le src.isLt hk⟩)



































end Int
end GramSchmidt
end Hex

/- Modified compatibility port (2026-11-15): imports namespaced under
Solutions.RegevBridgeNativeLLLVendor; pure Lean portability changes and removal
of native runtime hooks are recorded in MODIFICATIONS.json and the provenance
receipt. Original copyright/author notices and Apache-2.0 license are retained. -/

end

end

section
/-
Copyright (c) 2026 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Kim Morrison
-/






set_option autoImplicit true



section

/-!
Mathlib-side determinantal identification of the canonical Bareiss
Gram-Schmidt coefficients for `hex-gram-schmidt`.

This module finishes the Cramer identity
`scaledCoeffMatrix_det_eq_gramDet_mul_coeffs`, expressing the scaled
coefficient determinant as `gramDet (j+1) * coeffs[i][j]`.  Its second half
introduces the augmented `(n+1) × (n+1)` matrix `augmentedGram`, whose upper
block is `gramMatrix b` and whose trailing column carries a standard basis
vector, and proves `noPivotLoop_augmentedGram_invariant`: the no-pivot Bareiss
pass on the augmented matrix mirrors the pass on `gramMatrix b` while its
trailing column tracks `bareissGramCanonicalCoeff`.  This yields
`bareissGramCanonicalCoeff_eq_augmentedGram_entry` and its bordered-minor
form, identifying the canonical row coefficients with a Bareiss minor
determinant.
-/

namespace Hex
namespace GramSchmidt
namespace Int


/-- Substitution helper for the diagonal `(i, i)` matrix entry under a Fin
equality. Folded out of `subst`/`rfl` so callers can rewrite the index without
dragging the dependent proof component through the motive. -/
 theorem _root_.InfoLossLAR.NativeLLL.Shared.h74bc156927f74ab6 {n : Nat} (M : Matrix Int n n)
    {i j : Fin n} (h : i = j) :
    M[i][i] = M[j][j] := by
  subst h; rfl

/-- If the `s`-fueled no-pivot Bareiss prefix already recorded a singular step,
that step persists into any longer pass. The longer pass's recorded singular
index therefore matches the earlier one. -/
 theorem _root_.InfoLossLAR.NativeLLL.Shared.h590e675636c058f5
    {n : Nat} (state : Matrix.BareissState Int n) (a b : Nat) (k : Fin n)
    (h_sing_a : (Matrix.noPivotLoop a state).singularStep = some k.val)
    (h_step_a : (Matrix.noPivotLoop a state).step = k.val)
    (h_zero_a :
      (Matrix.noPivotLoop a state).matrix[k][k] = 0)
    (hk : k.val + 1 < n) :
    Matrix.noPivotLoop (a + b) state = Matrix.noPivotLoop a state := by
  rw [Matrix.noPivotLoop_add a b state]
  set S := Matrix.noPivotLoop a state with hS_def
  have hDone : S.step + 1 < n := by rw [h_step_a]; exact hk
  have hp_zero :
      S.matrix[(⟨S.step, Nat.lt_of_succ_lt hDone⟩ : Fin n)][
        (⟨S.step, Nat.lt_of_succ_lt hDone⟩ : Fin n)] = 0 := by
    have h_fin :
        (⟨S.step, Nat.lt_of_succ_lt hDone⟩ : Fin n) = k :=
      Fin.ext h_step_a
    exact (_root_.InfoLossLAR.NativeLLL.Shared.h74bc156927f74ab6 S.matrix h_fin).trans h_zero_a
  have h_sing_step : S.singularStep = some S.step := by
    rw [h_sing_a, h_step_a]
  exact Matrix.noPivotLoop_id_at_singular_fixedpoint (n := n) b S hDone hp_zero h_sing_step

/-! # Augmented Gram matrix for determinantal identification of
`bareissGramCanonicalCoeff`

The canonical row-coefficient vector of the initial no-pivot Bareiss trajectory
on `gramMatrix b` is identified with a trailing-column entry of the no-pivot
Bareiss pass on an `(n + 1) × (n + 1)` augmented matrix.  The upper `n × n`
block of the augmented matrix is `gramMatrix b`; the trailing column at upper
rows carries the standard basis vector `δ_a` at the chosen coefficient slot
`a`; the trailing row is structurally zero.

Because the trailing row is zero and the no-pivot Bareiss update at slot
`(i, j)` with `i, j < n` only consults the upper block, the upper-block
trajectory on the augmented matrix exactly mirrors the trajectory on
`gramMatrix b`.  Because the trailing-column update at row `i < n` and step
`k < i.val` mirrors the canonical-coefficient Bareiss step, the trailing
column at upper rows tracks `bareissGramCanonicalCoeff b fuel i` at slot `a`.
-/

/-- Augmented `(n + 1) × (n + 1)` matrix used to identify
`bareissGramCanonicalCoeff b fuel i [a]` with a trailing-column entry of the
no-pivot Bareiss pass.  Upper block is `gramMatrix b`; trailing column at
upper rows is the standard basis vector `δ_a`; trailing row is zero. -/
@[expose]
def augmentedGram (b : Matrix Int n m) (a : Fin n) :
    Hex.Matrix Int (n + 1) (n + 1) :=
  Matrix.ofFn fun i j : Fin (n + 1) =>
    if hi : i.val < n then
      if hj : j.val < n then
        (Matrix.gramMatrix b)[((⟨i.val, hi⟩ : Fin n), (⟨j.val, hj⟩ : Fin n))]
      else
        if i.val = a.val then (1 : Int) else 0
    else
      0

/-- Upper-block entry of `augmentedGram b a` agrees with `gramMatrix b`. -/
theorem augmentedGram_upper_block
    (b : Matrix Int n m) (a : Fin n) (i j : Fin n) :
    (augmentedGram b a)[(⟨i.val, Nat.lt_succ_of_lt i.isLt⟩ : Fin (n + 1))][
        (⟨j.val, Nat.lt_succ_of_lt j.isLt⟩ : Fin (n + 1))] =
      (Matrix.gramMatrix b)[i][j] := by
  unfold augmentedGram
  rw [Matrix.getElem_ofFn]
  simp [i.isLt, j.isLt]

/-- Trailing-column entry of `augmentedGram b a` at an upper row `i : Fin n`
is `1` when `i = a` and `0` otherwise. -/
theorem augmentedGram_trailing_col
    (b : Matrix Int n m) (a : Fin n) (i : Fin n) :
    (augmentedGram b a)[(⟨i.val, Nat.lt_succ_of_lt i.isLt⟩ : Fin (n + 1))][
        Fin.last n] =
      (if i = a then (1 : Int) else 0) := by
  unfold augmentedGram
  rw [Matrix.getElem_ofFn]
  have h_iff : (i.val = a.val) ↔ (i = a) := ⟨Fin.ext, fun h => by rw [h]⟩
  simp [i.isLt, h_iff]



/-- Substitution helper: matrix entries agree when Fin indices are equal.
Used to reindex matrix-entry equalities across propositionally-equal Fin
indices without provoking motive issues from `rw`. -/
 theorem _root_.Hex.GramSchmidt.Int.matrix_entry_eq_of_eq {n m : Nat} (M : Hex.Matrix Int n m)
    {i i' : Fin n} {j j' : Fin m} (hi : i = i') (hj : j = j') :
    M[i][j] = M[i'][j'] := by
  subst hi; subst hj; rfl

/-- Local copy of `HexMatrixTheory.trailing_eq_at_step` (private there):
re-state `BareissNoPivotInvariant.trailing_eq` with the step value supplied
externally so the dependent bordered-minor type matches the desired
`s = state.step` substitution cleanly. -/
theorem trailing_eq_at_step_local
    {n' : Nat} {M : Hex.Matrix Int n' n'} {state : Matrix.BareissState Int n'}
    (hinv : HexMatrixTheory.BareissNoPivotInvariant M state)
    (s : Nat) (hs : s < n') (hstep : s = state.step)
    (a c : Fin n') (hsa : s ≤ a.val) (hsc : s ≤ c.val) :
    state.matrix[a][c] =
      Hex.Matrix.det (Hex.Matrix.borderedMinor M s hs a c) := by
  subst hstep
  exact hinv.trailing_eq hs a c hsa hsc

/-- Auxiliary monotonicity: if a no-pivot Bareiss state reaches
`fuel + 1` iterations from `noPivotInitialState M` without recording a singular
step, then the prefix at `fuel` iterations is also non-singular.  Singular
states are fixed points of further iteration, so a non-singular outcome at
`fuel + 1` forces a non-singular prefix. -/
 theorem _root_.Hex.GramSchmidt.Int.noPivotLoop_singularStep_none_of_succ
    {n : Nat} (M : Matrix Int n n) (fuel : Nat)
    (h_no_sing :
      (Matrix.noPivotLoop (fuel + 1)
          (Matrix.noPivotInitialState M)).singularStep = none) :
    (Matrix.noPivotLoop fuel (Matrix.noPivotInitialState M)).singularStep = none := by
  set init := Matrix.noPivotInitialState M with hinit
  have h_init : init.singularStep = none := rfl
  rcases noPivotLoop_singular_inv (n := n) fuel init h_init with hnone | ⟨k, hsing, hstep, hzero, hklt⟩
  · exact hnone
  · -- Singular at fuel persists to fuel + 1, contradicting h_no_sing.
    exfalso
    have hpersist : Matrix.noPivotLoop (fuel + 1) init = Matrix.noPivotLoop fuel init :=
      _root_.InfoLossLAR.NativeLLL.Shared.h590e675636c058f5 init fuel 1 k hsing hstep hzero hklt
    rw [hpersist, hsing] at h_no_sing
    nomatch h_no_sing

-- Encapsulation makes the nested entry reads and the canonical-coefficient
-- rewrites over the recursive `noPivotLoop` term defeq-heavy here; a modest
-- bump (down from the original 1000000) covers it.
set_option maxHeartbeats 400000 in
/-- Combined invariant relating the no-pivot Bareiss trajectory on the
augmented matrix to the trajectory on `gramMatrix b`.  Under `fuel + 1 ≤ n`
and a non-singular prefix on the Gram side, the augmented loop tracks the
Gram loop on (i) `step`, (ii) `prevPivot`, (iii) the upper `n × n` block,
and (iv) carries the canonical row coefficient in its trailing column. -/
theorem noPivotLoop_augmentedGram_invariant
    (b : Matrix Int n m) (a : Fin n) (fuel : Nat) :
    fuel + 1 ≤ n →
      (Matrix.noPivotLoop fuel
          (Matrix.noPivotInitialState (Matrix.gramMatrix b))).singularStep = none →
      (Matrix.noPivotLoop fuel
          (Matrix.noPivotInitialState (augmentedGram b a))).step =
        (Matrix.noPivotLoop fuel
          (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step ∧
      (Matrix.noPivotLoop fuel
          (Matrix.noPivotInitialState (augmentedGram b a))).prevPivot =
        (Matrix.noPivotLoop fuel
          (Matrix.noPivotInitialState (Matrix.gramMatrix b))).prevPivot ∧
      (Matrix.noPivotLoop fuel
          (Matrix.noPivotInitialState (augmentedGram b a))).singularStep = none ∧
      (∀ i j : Fin n,
        (Matrix.noPivotLoop fuel
            (Matrix.noPivotInitialState (augmentedGram b a))).matrix[
          (⟨i.val, Nat.lt_succ_of_lt i.isLt⟩ : Fin (n + 1))][
          (⟨j.val, Nat.lt_succ_of_lt j.isLt⟩ : Fin (n + 1))] =
          (Matrix.noPivotLoop fuel
            (Matrix.noPivotInitialState (Matrix.gramMatrix b))).matrix[i][j]) ∧
      (∀ i : Fin n,
        (Matrix.noPivotLoop fuel
            (Matrix.noPivotInitialState (augmentedGram b a))).matrix[
          (⟨i.val, Nat.lt_succ_of_lt i.isLt⟩ : Fin (n + 1))][Fin.last n] =
          (bareissGramCanonicalCoeff b fuel i)[a]) := by
  induction fuel with
  | zero =>
      intro _ _
      refine ⟨rfl, rfl, rfl, ?_, ?_⟩
      · intro i j
        change (augmentedGram b a)[(⟨i.val, Nat.lt_succ_of_lt i.isLt⟩ : Fin (n + 1))][
            (⟨j.val, Nat.lt_succ_of_lt j.isLt⟩ : Fin (n + 1))] =
          (Matrix.gramMatrix b)[i][j]
        exact augmentedGram_upper_block b a i j
      · intro i
        change (augmentedGram b a)[(⟨i.val, Nat.lt_succ_of_lt i.isLt⟩ : Fin (n + 1))][
            Fin.last n] =
          (Vector.ofFn fun k : Fin n => if i = k then (1 : Int) else 0)[a]
        rw [augmentedGram_trailing_col]
        simp
  | succ fuel ih =>
      intro hfuel h_no_sing
      -- Pull the previous-fuel invariant out of the inductive hypothesis.
      have hfuel_prev : fuel + 1 ≤ n := by omega
      have h_no_sing_prev :
          (Matrix.noPivotLoop fuel
              (Matrix.noPivotInitialState (Matrix.gramMatrix b))).singularStep = none :=
        _root_.Hex.GramSchmidt.Int.noPivotLoop_singularStep_none_of_succ (Matrix.gramMatrix b) fuel h_no_sing
      obtain ⟨h_step_prev, h_prev_prev, h_sing_aug_prev, h_block_prev, h_trail_prev⟩ :=
        ih hfuel_prev h_no_sing_prev
      -- Set up shorthand for the previous-fuel states.
      set stateG := Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b)) with hstateG
      set stateA := Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (augmentedGram b a)) with hstateA
      -- Gram side has not finished and pivot is nonzero (else singular at fuel + 1).
      have h_step_G_fuel : stateG.step = fuel := by
        have h := Matrix.noPivotLoop_step_eq_add_of_singularStep_none fuel
          (Matrix.noPivotInitialState (Matrix.gramMatrix b)) rfl (by
            show 0 + fuel + 1 ≤ n; omega) h_no_sing_prev
        simp only [Matrix.noPivotInitialState, Nat.zero_add] at h
        rw [hstateG]
        exact h
      have hDone_G : stateG.step + 1 < n := by rw [h_step_G_fuel]; omega
      have hk_G_lt : stateG.step < n := Nat.lt_of_succ_lt hDone_G
      -- Pivot non-zero on the Gram side.
      have h_pivot_G_ne :
          stateG.matrix[(⟨stateG.step, hk_G_lt⟩ : Fin n)][
              (⟨stateG.step, hk_G_lt⟩ : Fin n)] ≠ 0 := by
        intro hzero
        -- Singular branch at fuel + 1 would record a singular step,
        -- contradicting `h_no_sing`.
        have h_sing_branch : Matrix.noPivotLoop 1 stateG
            = { stateG with singularStep := some stateG.step } :=
          Matrix.noPivotLoop_of_singular 0 stateG hDone_G hzero
        have h_succ_eq :
            Matrix.noPivotLoop (fuel + 1)
              (Matrix.noPivotInitialState (Matrix.gramMatrix b)) =
            Matrix.noPivotLoop 1 stateG := by
          rw [Matrix.noPivotLoop_add fuel 1]
        rw [h_succ_eq, h_sing_branch] at h_no_sing
        simp at h_no_sing
      -- Augmented side: step matches, so it has not finished either.
      have h_step_A_fuel : stateA.step = fuel := h_step_prev.trans h_step_G_fuel
      have hDone_A : stateA.step + 1 < n + 1 := by rw [h_step_A_fuel]; omega
      have hk_A_lt : stateA.step < n + 1 := Nat.lt_of_succ_lt hDone_A
      -- Pivot at the lifted index on the augmented side equals the Gram pivot.
      have h_pivot_A_eq :
          stateA.matrix[(⟨stateA.step, hk_A_lt⟩ : Fin (n + 1))][
              (⟨stateA.step, hk_A_lt⟩ : Fin (n + 1))] =
            stateG.matrix[(⟨stateG.step, hk_G_lt⟩ : Fin n)][
              (⟨stateG.step, hk_G_lt⟩ : Fin n)] := by
        have h_idx :
            (⟨stateA.step, hk_A_lt⟩ : Fin (n + 1)) =
              (⟨(⟨stateG.step, hk_G_lt⟩ : Fin n).val,
                Nat.lt_succ_of_lt (⟨stateG.step, hk_G_lt⟩ : Fin n).isLt⟩ :
                  Fin (n + 1)) := Fin.ext h_step_prev
        calc stateA.matrix[(⟨stateA.step, hk_A_lt⟩ : Fin (n + 1))][
              (⟨stateA.step, hk_A_lt⟩ : Fin (n + 1))]
            = stateA.matrix[(⟨(⟨stateG.step, hk_G_lt⟩ : Fin n).val,
                Nat.lt_succ_of_lt (⟨stateG.step, hk_G_lt⟩ : Fin n).isLt⟩ :
                  Fin (n + 1))][(⟨(⟨stateG.step, hk_G_lt⟩ : Fin n).val,
                Nat.lt_succ_of_lt (⟨stateG.step, hk_G_lt⟩ : Fin n).isLt⟩ :
                  Fin (n + 1))] := _root_.Hex.GramSchmidt.Int.matrix_entry_eq_of_eq _ h_idx h_idx
          _ = stateG.matrix[(⟨stateG.step, hk_G_lt⟩ : Fin n)][
                (⟨stateG.step, hk_G_lt⟩ : Fin n)] :=
              h_block_prev ⟨stateG.step, hk_G_lt⟩ ⟨stateG.step, hk_G_lt⟩
      have h_pivot_A_ne :
          stateA.matrix[(⟨stateA.step, hk_A_lt⟩ : Fin (n + 1))][
              (⟨stateA.step, hk_A_lt⟩ : Fin (n + 1))] ≠ 0 := by
        rw [h_pivot_A_eq]; exact h_pivot_G_ne
      -- Peel off the last iteration on both sides.
      have h_G_succ :
          Matrix.noPivotLoop (fuel + 1)
              (Matrix.noPivotInitialState (Matrix.gramMatrix b)) =
            Matrix.noPivotLoop 0
              { step := stateG.step + 1
                matrix := Matrix.stepMatrix stateG.matrix stateG.step
                  stateG.matrix[(⟨stateG.step, hk_G_lt⟩ : Fin n)][
                    (⟨stateG.step, hk_G_lt⟩ : Fin n)] stateG.prevPivot
                prevPivot := stateG.matrix[(⟨stateG.step, hk_G_lt⟩ : Fin n)][
                  (⟨stateG.step, hk_G_lt⟩ : Fin n)]
                rowSwaps := stateG.rowSwaps
                singularStep := none } := by
        rw [Matrix.noPivotLoop_add fuel 1]
        exact Matrix.noPivotLoop_of_regular 0 stateG hDone_G h_pivot_G_ne
      have h_A_succ :
          Matrix.noPivotLoop (fuel + 1)
              (Matrix.noPivotInitialState (augmentedGram b a)) =
            Matrix.noPivotLoop 0
              { step := stateA.step + 1
                matrix := Matrix.stepMatrix stateA.matrix stateA.step
                  stateA.matrix[(⟨stateA.step, hk_A_lt⟩ : Fin (n + 1))][
                    (⟨stateA.step, hk_A_lt⟩ : Fin (n + 1))] stateA.prevPivot
                prevPivot := stateA.matrix[(⟨stateA.step, hk_A_lt⟩ : Fin (n + 1))][
                  (⟨stateA.step, hk_A_lt⟩ : Fin (n + 1))]
                rowSwaps := stateA.rowSwaps
                singularStep := none } := by
        rw [Matrix.noPivotLoop_add fuel 1]
        exact Matrix.noPivotLoop_of_regular 0 stateA hDone_A h_pivot_A_ne
      -- Both peeled states are zero-fuel, so the loop returns them unchanged.
      rw [h_G_succ, h_A_succ, Matrix.noPivotLoop_zero_fuel, Matrix.noPivotLoop_zero_fuel]
      -- Now project each component of the invariant.
      refine ⟨?_, ?_, ?_, ?_, ?_⟩
      · -- Step equality.
        show stateA.step + 1 = stateG.step + 1
        exact congrArg (· + 1) h_step_prev
      · -- prevPivot equality.
        show stateA.matrix[(⟨stateA.step, hk_A_lt⟩ : Fin (n + 1))][
              (⟨stateA.step, hk_A_lt⟩ : Fin (n + 1))] =
            stateG.matrix[(⟨stateG.step, hk_G_lt⟩ : Fin n)][
              (⟨stateG.step, hk_G_lt⟩ : Fin n)]
        exact h_pivot_A_eq
      · -- singularStep = none.
        rfl
      · -- Upper-block invariant.
        intro i j
        -- Set up the lifted indices and `k` index used in `stepMatrix`.
        set iA : Fin (n + 1) := ⟨i.val, Nat.lt_succ_of_lt i.isLt⟩ with hiA
        set jA : Fin (n + 1) := ⟨j.val, Nat.lt_succ_of_lt j.isLt⟩ with hjA
        -- Case-split on whether step `fuel = stateG.step` updates this entry.
        by_cases hi_lt : stateG.step < i.val
        · by_cases hj_lt : stateG.step < j.val
          · -- Trailing block: Bareiss update fires on both sides.
            have hi_lt_A : stateA.step < iA.val := by
              show stateA.step < i.val
              rw [h_step_prev]; exact hi_lt
            have hj_lt_A : stateA.step < jA.val := by
              show stateA.step < j.val
              rw [h_step_prev]; exact hj_lt
            rw [Matrix.stepMatrix_update_eq stateA.matrix stateA.step _ _ iA jA
              hi_lt_A hj_lt_A]
            rw [Matrix.stepMatrix_update_eq stateG.matrix stateG.step _ _ i j
              hi_lt hj_lt]
            dsimp only []
            -- Rewrite the four matrix entries on the LHS using the block IH.
            have h_ij_A : stateA.matrix[iA][jA] = stateG.matrix[i][j] :=
              h_block_prev i j
            -- (colK : Fin (n+1)) for aug, (colK_G : Fin n) for gram.
            -- These have step.val = stateG.step (by h_step_prev) and we use
            -- the IH at row=i, col=⟨stateG.step, hk_G_lt⟩, and so on.
            have h_step_lift_eq :
                (⟨stateA.step, Nat.lt_trans hi_lt_A iA.isLt⟩ : Fin (n + 1)) =
                  (⟨(⟨stateG.step, hk_G_lt⟩ : Fin n).val,
                    Nat.lt_succ_of_lt (⟨stateG.step, hk_G_lt⟩ : Fin n).isLt⟩ :
                      Fin (n + 1)) := by
              apply Fin.ext
              show stateA.step = stateG.step
              exact h_step_prev
            have h_iL_A :
                stateA.matrix[iA][(⟨stateA.step, Nat.lt_trans hi_lt_A iA.isLt⟩ :
                    Fin (n + 1))] =
                  stateG.matrix[i][(⟨stateG.step, hk_G_lt⟩ : Fin n)] := by
              calc stateA.matrix[iA][(⟨stateA.step, Nat.lt_trans hi_lt_A iA.isLt⟩ :
                      Fin (n + 1))]
                  = stateA.matrix[(⟨i.val, Nat.lt_succ_of_lt i.isLt⟩ : Fin (n + 1))][
                      (⟨(⟨stateG.step, hk_G_lt⟩ : Fin n).val,
                        Nat.lt_succ_of_lt (⟨stateG.step, hk_G_lt⟩ : Fin n).isLt⟩ :
                          Fin (n + 1))] := _root_.Hex.GramSchmidt.Int.matrix_entry_eq_of_eq _ rfl h_step_lift_eq
                _ = stateG.matrix[i][(⟨stateG.step, hk_G_lt⟩ : Fin n)] :=
                    h_block_prev i ⟨stateG.step, hk_G_lt⟩
            have h_kJ_A :
                stateA.matrix[(⟨stateA.step, Nat.lt_trans hj_lt_A jA.isLt⟩ :
                    Fin (n + 1))][jA] =
                  stateG.matrix[(⟨stateG.step, hk_G_lt⟩ : Fin n)][j] := by
              calc stateA.matrix[(⟨stateA.step, Nat.lt_trans hj_lt_A jA.isLt⟩ :
                      Fin (n + 1))][jA]
                  = stateA.matrix[(⟨(⟨stateG.step, hk_G_lt⟩ : Fin n).val,
                      Nat.lt_succ_of_lt (⟨stateG.step, hk_G_lt⟩ : Fin n).isLt⟩ :
                        Fin (n + 1))][(⟨j.val, Nat.lt_succ_of_lt j.isLt⟩ : Fin (n + 1))] :=
                    _root_.Hex.GramSchmidt.Int.matrix_entry_eq_of_eq _ h_step_lift_eq rfl
                _ = stateG.matrix[(⟨stateG.step, hk_G_lt⟩ : Fin n)][j] :=
                    h_block_prev ⟨stateG.step, hk_G_lt⟩ j
            rw [h_ij_A, h_iL_A, h_kJ_A, h_pivot_A_eq, h_prev_prev]
          · -- Trailing row, but column ≤ step. Then both sides preserve the entry.
            -- On aug, the `stepMatrix` update condition `k < i ∧ k < j` fails because `j ≤ k`.
            -- Could be `j.val < k` (no update) or `j.val = k` (clear pivot col below;
            -- value 0, which matches Gram side since both are 0 below pivot).
            by_cases hj_eq : j.val = stateG.step
            · -- Clear pivot column below: both sides set to 0.
              have hj_eq_A : jA.val = stateA.step := by
                show j.val = stateA.step
                rw [h_step_prev]; exact hj_eq
              have hi_lt_A : stateA.step < iA.val := by
                show stateA.step < i.val
                rw [h_step_prev]; exact hi_lt
              rw [Matrix.stepMatrix_pivot_col_below stateA.matrix stateA.step _ _ iA jA
                hi_lt_A hj_eq_A]
              rw [Matrix.stepMatrix_pivot_col_below stateG.matrix stateG.step _ _ i j
                hi_lt hj_eq]
            · -- Column strictly below pivot: both sides preserve their value.
              have hj_lt_step : j.val < stateG.step := by omega
              have hj_lt_step_A : jA.val < stateA.step := by
                show j.val < stateA.step
                rw [h_step_prev]; exact hj_lt_step
              have h_not_update_A : ¬ (stateA.step < iA.val ∧ stateA.step < jA.val) := by
                intro ⟨_, h⟩; omega
              have h_not_col_A : ¬ (stateA.step < iA.val ∧ jA.val = stateA.step) := by
                intro ⟨_, h⟩; omega
              have h_not_update_G : ¬ (stateG.step < i.val ∧ stateG.step < j.val) := by
                intro ⟨_, h⟩; omega
              have h_not_col_G : ¬ (stateG.step < i.val ∧ j.val = stateG.step) := by
                intro ⟨_, h⟩; omega
              rw [Matrix.stepMatrix_eq_of_not_update stateA.matrix stateA.step _ _ iA jA
                h_not_update_A h_not_col_A]
              rw [Matrix.stepMatrix_eq_of_not_update stateG.matrix stateG.step _ _ i j
                h_not_update_G h_not_col_G]
              exact h_block_prev i j
        · -- Row ≤ step: no update on either side.
          have hi_le_step : i.val ≤ stateG.step := Nat.le_of_not_lt hi_lt
          have hi_le_step_A : iA.val ≤ stateA.step := by
            show i.val ≤ stateA.step
            rw [h_step_prev]; exact hi_le_step
          have h_not_update_A : ¬ (stateA.step < iA.val ∧ stateA.step < jA.val) := by
            intro ⟨h, _⟩; exact Nat.not_lt_of_ge hi_le_step_A h
          have h_not_col_A : ¬ (stateA.step < iA.val ∧ jA.val = stateA.step) := by
            intro ⟨h, _⟩; exact Nat.not_lt_of_ge hi_le_step_A h
          have h_not_update_G : ¬ (stateG.step < i.val ∧ stateG.step < j.val) := by
            intro ⟨h, _⟩; exact Nat.not_lt_of_ge hi_le_step h
          have h_not_col_G : ¬ (stateG.step < i.val ∧ j.val = stateG.step) := by
            intro ⟨h, _⟩; exact Nat.not_lt_of_ge hi_le_step h
          rw [Matrix.stepMatrix_eq_of_not_update stateA.matrix stateA.step _ _ iA jA
            h_not_update_A h_not_col_A]
          rw [Matrix.stepMatrix_eq_of_not_update stateG.matrix stateG.step _ _ i j
            h_not_update_G h_not_col_G]
          exact h_block_prev i j
      · -- Trailing-column invariant.
        intro i
        set iA : Fin (n + 1) := ⟨i.val, Nat.lt_succ_of_lt i.isLt⟩ with hiA
        set L : Fin (n + 1) := Fin.last n with hL
        have hL_lt : stateA.step < L.val := by
          show stateA.step < n
          rw [h_step_prev]; exact hk_G_lt
        by_cases hi_lt : stateG.step < i.val
        · -- Active row: both sides apply the Bareiss update.
          have hi_lt_A : stateA.step < iA.val := by
            show stateA.step < i.val
            rw [h_step_prev]; exact hi_lt
          rw [Matrix.stepMatrix_update_eq stateA.matrix stateA.step _ _ iA L
            hi_lt_A hL_lt]
          dsimp only []
          -- Match the four entries on the LHS via the IH:
          -- - the trailing-column entry at row i: by trailing IH.
          -- - the entry (i, step↑): by block IH after reindexing.
          -- - the entry (step↑, last n): by trailing IH at row k.
          -- The pivot at (step↑, step↑) is `h_pivot_A_eq`.
          have h_iL_A : stateA.matrix[iA][L] = (bareissGramCanonicalCoeff b fuel i)[a] :=
            h_trail_prev i
          have h_step_lift_eq :
              (⟨stateA.step, Nat.lt_trans hi_lt_A iA.isLt⟩ : Fin (n + 1)) =
                (⟨(⟨stateG.step, hk_G_lt⟩ : Fin n).val,
                  Nat.lt_succ_of_lt (⟨stateG.step, hk_G_lt⟩ : Fin n).isLt⟩ :
                    Fin (n + 1)) := by
            apply Fin.ext
            show stateA.step = stateG.step
            exact h_step_prev
          have h_iK_A :
              stateA.matrix[iA][(⟨stateA.step, Nat.lt_trans hi_lt_A iA.isLt⟩ :
                  Fin (n + 1))] =
                stateG.matrix[i][(⟨stateG.step, hk_G_lt⟩ : Fin n)] := by
            calc stateA.matrix[iA][(⟨stateA.step, Nat.lt_trans hi_lt_A iA.isLt⟩ :
                    Fin (n + 1))]
                = stateA.matrix[(⟨i.val, Nat.lt_succ_of_lt i.isLt⟩ : Fin (n + 1))][
                    (⟨(⟨stateG.step, hk_G_lt⟩ : Fin n).val,
                      Nat.lt_succ_of_lt (⟨stateG.step, hk_G_lt⟩ : Fin n).isLt⟩ :
                        Fin (n + 1))] := _root_.Hex.GramSchmidt.Int.matrix_entry_eq_of_eq _ rfl h_step_lift_eq
              _ = stateG.matrix[i][(⟨stateG.step, hk_G_lt⟩ : Fin n)] :=
                  h_block_prev i ⟨stateG.step, hk_G_lt⟩
          have h_kL_A :
              stateA.matrix[(⟨stateA.step, Nat.lt_trans hL_lt L.isLt⟩ : Fin (n + 1))][L] =
                (bareissGramCanonicalCoeff b fuel ⟨stateG.step, hk_G_lt⟩)[a] := by
            calc stateA.matrix[(⟨stateA.step, Nat.lt_trans hL_lt L.isLt⟩ :
                    Fin (n + 1))][L]
                = stateA.matrix[(⟨(⟨stateG.step, hk_G_lt⟩ : Fin n).val,
                    Nat.lt_succ_of_lt (⟨stateG.step, hk_G_lt⟩ : Fin n).isLt⟩ :
                      Fin (n + 1))][Fin.last n] :=
                  _root_.Hex.GramSchmidt.Int.matrix_entry_eq_of_eq _ h_step_lift_eq rfl
              _ = (bareissGramCanonicalCoeff b fuel
                    (⟨stateG.step, hk_G_lt⟩ : Fin n))[a] :=
                  h_trail_prev ⟨stateG.step, hk_G_lt⟩
          rw [h_iL_A, h_iK_A, h_kL_A, h_pivot_A_eq, h_prev_prev]
          -- The RHS is the canonical-coefficient recursion at active row.
          have hp_canon :
              (Matrix.noPivotLoop fuel
                  (Matrix.noPivotInitialState (Matrix.gramMatrix b))).matrix[
                (Matrix.noPivotLoop fuel
                  (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step][
                (Matrix.noPivotLoop fuel
                  (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step] ≠ 0 := by
            show stateG.matrix[stateG.step][stateG.step] ≠ 0
            -- Lower the Fin index proof.
            intro hzero
            apply h_pivot_G_ne
            exact hzero
          have hnext_canon :
              (Matrix.noPivotLoop fuel
                  (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 < n := by
            show stateG.step + 1 < n; exact hDone_G
          have hi_lt_canon :
              (Matrix.noPivotLoop fuel
                  (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 ≤ i.val := by
            show stateG.step + 1 ≤ i.val; exact hi_lt
          rw [bareissGramCanonicalCoeff_succ_regular b fuel i hnext_canon hp_canon hi_lt_canon]
          conv_rhs => rw [show ∀ f : Fin n → Int, (Vector.ofFn f)[a] = f a from
            fun f => by simp]
        · -- Processed row (i.val ≤ step): both sides preserve the value.
          have hi_le_step : i.val ≤ stateG.step := Nat.le_of_not_lt hi_lt
          have hi_le_step_A : iA.val ≤ stateA.step := by
            show i.val ≤ stateA.step
            rw [h_step_prev]; exact hi_le_step
          have h_not_update_A : ¬ (stateA.step < iA.val ∧ stateA.step < L.val) := by
            intro ⟨h, _⟩; exact Nat.not_lt_of_ge hi_le_step_A h
          have h_not_col_A : ¬ (stateA.step < iA.val ∧ L.val = stateA.step) := by
            intro ⟨h, _⟩; exact Nat.not_lt_of_ge hi_le_step_A h
          rw [Matrix.stepMatrix_eq_of_not_update stateA.matrix stateA.step _ _ iA L
            h_not_update_A h_not_col_A]
          -- Canon in processed-row case: stays at fuel-value.
          have hnext_canon :
              (Matrix.noPivotLoop fuel
                  (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 < n := by
            show stateG.step + 1 < n; exact hDone_G
          have hp_canon :
              (Matrix.noPivotLoop fuel
                  (Matrix.noPivotInitialState (Matrix.gramMatrix b))).matrix[
                (Matrix.noPivotLoop fuel
                  (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step][
                (Matrix.noPivotLoop fuel
                  (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step] ≠ 0 := by
            show stateG.matrix[stateG.step][stateG.step] ≠ 0
            intro hzero
            apply h_pivot_G_ne; exact hzero
          have h_not_active :
              ¬ (Matrix.noPivotLoop fuel
                  (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 ≤ i.val := by
            show ¬ stateG.step + 1 ≤ i.val; omega
          rw [bareissGramCanonicalCoeff_succ_processed b fuel i hnext_canon hp_canon
            h_not_active]
          exact h_trail_prev i

/-- Determinantal identification of the canonical row-coefficient vector
`bareissGramCanonicalCoeff b fuel i` at slot `a` as the trailing-column entry
of the no-pivot Bareiss pass on the augmented `(n + 1) × (n + 1)` matrix
`augmentedGram b a`.  The hypothesis `fuel ≤ i.val` ensures the comparison
covers both the active-row and processed-row branches of the canonical
recursion. -/
theorem bareissGramCanonicalCoeff_eq_augmentedGram_entry
    (b : Matrix Int n m) (fuel : Nat) (i : Fin n) (a : Fin n)
    (hfuel : fuel ≤ i.val)
    (h_no_sing :
      (Matrix.noPivotLoop fuel
          (Matrix.noPivotInitialState (Matrix.gramMatrix b))).singularStep = none) :
    (bareissGramCanonicalCoeff b fuel i)[a] =
      (Matrix.noPivotLoop fuel
          (Matrix.noPivotInitialState (augmentedGram b a))).matrix[
        (⟨i.val, Nat.lt_succ_of_lt i.isLt⟩ : Fin (n + 1))][Fin.last n] := by
  have hfuel_n : fuel + 1 ≤ n := by
    have : i.val < n := i.isLt
    omega
  obtain ⟨_, _, _, _, h_trail⟩ :=
    noPivotLoop_augmentedGram_invariant b a fuel hfuel_n h_no_sing
  exact (h_trail i).symm

/-- Direct bordered-minor form: the canonical row-coefficient vector at slot
`a` equals the determinant of the `(fuel + 1) × (fuel + 1)` bordered minor of
the augmented Gram matrix.  Composes
`bareissGramCanonicalCoeff_eq_augmentedGram_entry` with the Bareiss
no-pivot invariant `trailing_eq`. -/
theorem bareissGramCanonicalCoeff_eq_borderedMinor_aug
    (b : Matrix Int n m) (fuel : Nat) (i : Fin n) (a : Fin n)
    (hfuel : fuel ≤ i.val)
    (h_no_sing :
      (Matrix.noPivotLoop fuel
          (Matrix.noPivotInitialState (Matrix.gramMatrix b))).singularStep = none) :
    (bareissGramCanonicalCoeff b fuel i)[a] =
      Matrix.det (Matrix.borderedMinor (augmentedGram b a) fuel
        (by have : i.val < n := i.isLt; omega : fuel < n + 1)
        (⟨i.val, Nat.lt_succ_of_lt i.isLt⟩ : Fin (n + 1)) (Fin.last n)) := by
  rw [bareissGramCanonicalCoeff_eq_augmentedGram_entry b fuel i a hfuel h_no_sing]
  -- Set up the Bareiss invariant on the augmented loop.
  have hfuel_n : fuel + 1 ≤ n := by
    have : i.val < n := i.isLt; omega
  obtain ⟨_, _, h_sing_aug, _, _⟩ :=
    noPivotLoop_augmentedGram_invariant b a fuel hfuel_n h_no_sing
  have h_step_aug_eq_fuel :
      (Matrix.noPivotLoop fuel
          (Matrix.noPivotInitialState (augmentedGram b a))).step = fuel := by
    have h := Matrix.noPivotLoop_step_eq_add_of_singularStep_none fuel
      (Matrix.noPivotInitialState (augmentedGram b a)) rfl (by
        show 0 + fuel + 1 ≤ n + 1; omega) h_sing_aug
    simpa [Matrix.noPivotInitialState] using h
  have h_inv : HexMatrixTheory.BareissNoPivotInvariant (augmentedGram b a)
      (Matrix.noPivotLoop fuel (Matrix.noPivotInitialState (augmentedGram b a))) :=
    HexMatrixTheory.noPivotLoop_invariant_of_singularStep_eq_none
      (augmentedGram b a) fuel
      (Matrix.noPivotInitialState (augmentedGram b a))
      (HexMatrixTheory.bareissNoPivotInvariant_initial (augmentedGram b a)) h_sing_aug
  -- Apply trailing_eq_at_step with `s := fuel` and `hstep := h_step_aug_eq_fuel.symm`.
  have h_step_lt : fuel < n + 1 := by omega
  have h_step_le_i : fuel ≤ (⟨i.val, Nat.lt_succ_of_lt i.isLt⟩ : Fin (n + 1)).val := hfuel
  have h_step_le_last : fuel ≤ (Fin.last n).val := by show fuel ≤ n; omega
  exact trailing_eq_at_step_local h_inv fuel h_step_lt h_step_aug_eq_fuel.symm
    (⟨i.val, Nat.lt_succ_of_lt i.isLt⟩ : Fin (n + 1)) (Fin.last n)
    h_step_le_i h_step_le_last

/-- Under a non-singular no-pivot Bareiss prefix that has not yet reached the
terminal step, the loop on the initial state of `M` consumed exactly `fuel`
regular iterations: the resulting step equals `fuel`, and `fuel + 1 ≤ n'`. -/
theorem noPivotLoop_initial_step_eq_and_fuel_succ_le
    {n' : Nat} (M : Hex.Matrix Int n' n') (fuel : Nat)
    (h_no_sing :
      (Matrix.noPivotLoop fuel (Matrix.noPivotInitialState M)).singularStep = none)
    (hnext :
      (Matrix.noPivotLoop fuel (Matrix.noPivotInitialState M)).step + 1 < n') :
    (Matrix.noPivotLoop fuel (Matrix.noPivotInitialState M)).step = fuel ∧
      fuel + 1 ≤ n' := by
  induction fuel with
  | zero =>
    have h_init_step : (Matrix.noPivotInitialState M).step = 0 := rfl
    refine ⟨rfl, ?_⟩
    have h0 := hnext
    rw [Matrix.noPivotLoop_zero_fuel, h_init_step] at h0
    omega
  | succ fuel ih =>
    have h_no_sing_prev := _root_.Hex.GramSchmidt.Int.noPivotLoop_singularStep_none_of_succ M fuel h_no_sing
    set state' := Matrix.noPivotLoop fuel (Matrix.noPivotInitialState M) with hstate'
    by_cases hDone : state'.step + 1 < n'
    · by_cases hp : state'.matrix[state'.step][state'.step] = 0
      · exfalso
        rw [Matrix.noPivotLoop_add fuel 1, ← hstate',
            Matrix.noPivotLoop_of_singular 0 state' hDone hp] at h_no_sing
        simp at h_no_sing
      · -- Regular branch: peel the last iteration.
        obtain ⟨h_step_prev, h_fuel_prev⟩ := ih h_no_sing_prev hDone
        refine ⟨?_, by omega⟩
        rw [Matrix.noPivotLoop_add fuel 1, ← hstate',
            Matrix.noPivotLoop_of_regular 0 state' hDone hp,
            Matrix.noPivotLoop_zero_fuel]
        show state'.step + 1 = fuel + 1
        rw [h_step_prev]
    · exfalso
      rw [Matrix.noPivotLoop_add fuel 1, ← hstate',
          Matrix.noPivotLoop_done 0 state' hDone] at hnext
      exact hDone hnext

/-- Companion to `trailing_eq_at_step_local`: rewrite
`BareissNoPivotInvariant.prevPivot_eq` with the step value supplied externally
so the dependent `principalSubmatrix` type matches the desired `s = state.step`
substitution cleanly. -/
theorem prevPivot_eq_at_step_local
    {n' : Nat} {M : Hex.Matrix Int n' n'} {state : Matrix.BareissState Int n'}
    (hinv : HexMatrixTheory.BareissNoPivotInvariant M state)
    (s : Nat) (hs : s ≤ n') (hstep : s = state.step) :
    state.prevPivot = Hex.Matrix.det (Hex.Matrix.principalSubmatrix M s hs) := by
  subst hstep
  exact hinv.prevPivot_eq

/-- Concrete bridge-side instance of `StepWitness` for any integer basis.

The witness quotient at slot `a` is the next iteration's canonical row
coefficient `(bareissGramCanonicalCoeff b (fuel + 1) i)[a]`.  Integrality of
this quotient comes from the Bareiss-Desnanot identity applied to the
augmented `(n + 1) × (n + 1)` matrix `augmentedGram b a`: the canonical
coefficients identify with trailing-column entries of the augmented no-pivot
Bareiss pass (`bareissGramCanonicalCoeff_eq_borderedMinor_aug`), and the
Bareiss step recurrence on the augmented matrix supplies the exact-division
multiplicative identity. -/
@[expose]
def StepWitness.ofGram (b : Matrix Int n m) :
    Hex.GramSchmidt.Int.StepWitness b := by
  intro fuel hinv h_canon h_prefix_none hnext hp i hi
  -- Prepare bound facts and the step equality before refining.
  set state := Matrix.noPivotLoop fuel
    (Matrix.noPivotInitialState (Matrix.gramMatrix b)) with hstate
  obtain ⟨h_step_eq_fuel, hfuel_n_le⟩ :=
    noPivotLoop_initial_step_eq_and_fuel_succ_le (Matrix.gramMatrix b)
      fuel h_prefix_none hnext
  have hfuel_lt_n : fuel < n := by omega
  have hfuel_lt_naug : fuel < n + 1 := by omega
  have hfuel_succ_lt_naug : fuel + 1 < n + 1 := by omega
  have hfuel_le_naug : fuel ≤ n + 1 := by omega
  -- The prefix at `fuel + 1` is also non-singular (one more regular step).
  have h_prefix_none_succ :
      (Matrix.noPivotLoop (fuel + 1)
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).singularStep = none := by
    rw [Matrix.noPivotLoop_add fuel 1, ← hstate,
        Matrix.noPivotLoop_of_regular 0 state hnext hp,
        Matrix.noPivotLoop_zero_fuel]
  have h_fuel_succ_le_i : fuel + 1 ≤ i.val := by rw [← h_step_eq_fuel]; exact hi
  refine ⟨fun a => (Hex.GramSchmidt.Int.bareissGramCanonicalCoeff b (fuel + 1) i)[a], ?_⟩
  -- The structure field has an outer `let k := ⟨state.step, _⟩` binder before
  -- the `∀ a`, so two intros are needed.
  intro k_let a
  -- Augmented invariants at fuel and fuel + 1, both at slot `a`.
  obtain ⟨h_step_A, h_prev_A, h_sing_A, h_block_A, h_trail_A⟩ :=
    noPivotLoop_augmentedGram_invariant b a fuel hfuel_n_le h_prefix_none
  set stateA := Matrix.noPivotLoop fuel
    (Matrix.noPivotInitialState (augmentedGram b a)) with hstateA
  -- The lifted Fin (n + 1) indices used throughout.
  set iA : Fin (n + 1) := ⟨i.val, Nat.lt_succ_of_lt i.isLt⟩ with hiA_def
  set kA : Fin (n + 1) := ⟨k_let.val, Nat.lt_succ_of_lt k_let.isLt⟩ with hkA_def
  set L : Fin (n + 1) := Fin.last n with hL_def
  -- `k_let.val = state.step = fuel`, so `kA.val = fuel`.
  have h_kA_val : kA.val = fuel := h_step_eq_fuel
  have h_fuel_le_kA : fuel ≤ kA.val := Nat.le_of_eq h_kA_val.symm
  have h_fuel_lt_iA : fuel < iA.val := by show fuel < i.val; omega
  have h_fuel_lt_L : fuel < L.val := by show fuel < n; omega
  have h_fuel_le_iA : fuel ≤ iA.val := Nat.le_of_lt h_fuel_lt_iA
  have h_fuel_le_L : fuel ≤ L.val := Nat.le_of_lt h_fuel_lt_L
  -- Substitute the row-invariant's coefficients by canonical via h_canon.
  rw [h_canon i, h_canon k_let]
  -- Bridge state.matrix entries to stateA entries via the upper-block bridge.
  simp only [Hex.Matrix.getElem_pair_eq_nested]
  rw [show state.matrix[k_let][k_let] = stateA.matrix[kA][kA] from
      (h_block_A k_let k_let).symm]
  rw [show state.matrix[i][k_let] = stateA.matrix[iA][kA] from
      (h_block_A i k_let).symm]
  -- Bridge canonical coefficients to stateA trailing-column entries.
  rw [show (bareissGramCanonicalCoeff b fuel i)[a] = stateA.matrix[iA][L] from
      (h_trail_A i).symm]
  rw [show (bareissGramCanonicalCoeff b fuel k_let)[a] = stateA.matrix[kA][L] from
      (h_trail_A k_let).symm]
  -- Bridge state.prevPivot to stateA.prevPivot (h_prev_A goes the other way).
  rw [← h_prev_A]
  -- Bareiss invariant on the augmented loop at fuel.
  have h_inv : HexMatrixTheory.BareissNoPivotInvariant (augmentedGram b a) stateA :=
    HexMatrixTheory.noPivotLoop_invariant_of_singularStep_eq_none
      (augmentedGram b a) fuel _
      (HexMatrixTheory.bareissNoPivotInvariant_initial (augmentedGram b a))
      h_sing_A
  have h_stateA_step : stateA.step = fuel := h_step_A.trans h_step_eq_fuel
  -- Rewrite each stateA entry and the prevPivot as bordered-minor determinants.
  rw [trailing_eq_at_step_local h_inv fuel hfuel_lt_naug h_stateA_step.symm kA kA
        h_fuel_le_kA h_fuel_le_kA]
  rw [trailing_eq_at_step_local h_inv fuel hfuel_lt_naug h_stateA_step.symm iA L
        h_fuel_le_iA h_fuel_le_L]
  rw [trailing_eq_at_step_local h_inv fuel hfuel_lt_naug h_stateA_step.symm iA kA
        h_fuel_le_iA h_fuel_le_kA]
  rw [trailing_eq_at_step_local h_inv fuel hfuel_lt_naug h_stateA_step.symm kA L
        h_fuel_le_kA h_fuel_le_L]
  rw [prevPivot_eq_at_step_local h_inv fuel hfuel_le_naug h_stateA_step.symm]
  -- Beta-reduce the explicit `q a` on the RHS so the next rewrite matches.
  show ((augmentedGram b a).borderedMinor fuel hfuel_lt_naug kA kA).det *
        ((augmentedGram b a).borderedMinor fuel hfuel_lt_naug iA L).det -
      ((augmentedGram b a).borderedMinor fuel hfuel_lt_naug iA kA).det *
        ((augmentedGram b a).borderedMinor fuel hfuel_lt_naug kA L).det =
    (bareissGramCanonicalCoeff b (fuel + 1) i)[a] *
      ((augmentedGram b a).principalSubmatrix fuel hfuel_le_naug).det
  rw [bareissGramCanonicalCoeff_eq_borderedMinor_aug b (fuel + 1) i a
        h_fuel_succ_le_i h_prefix_none_succ]
  -- Desnanot-Jacobi on the augmented matrix at level `fuel`.
  have hdj :=
    HexMatrixTheory.desnanot_jacobi_borderedMinor (augmentedGram b a) fuel
      hfuel_lt_naug hfuel_succ_lt_naug iA L h_fuel_lt_iA h_fuel_lt_L
  -- The K positions in hdj are `⟨fuel, _⟩ : Fin (n + 1)`; via Fin.ext they
  -- equal `kA` (whose value is `state.step = fuel`).
  have hK : ∀ (h : fuel < n + 1), (⟨fuel, h⟩ : Fin (n + 1)) = kA := fun _ =>
    Fin.ext h_kA_val.symm
  simp_rw [hK] at hdj
  exact hdj.symm









end Int
end GramSchmidt
end Hex

/- Modified compatibility port (2026-11-15): imports namespaced under
Solutions.RegevBridgeNativeLLLVendor; pure Lean portability changes and removal
of native runtime hooks are recorded in MODIFICATIONS.json and the provenance
receipt. Original copyright/author notices and Apache-2.0 license are retained. -/

end

end

section
/-
Copyright (c) 2026 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Kim Morrison
-/






set_option autoImplicit true



section

namespace Hex
namespace GramSchmidt
namespace Int
/-! # Adjacent-swap pivot Gram-determinant product

Swapping adjacent rows `km1, k` (with `km1 + 1 = k`) of `b` changes only the
leading `k × k` Gram determinant within `0 ≤ t ≤ k + 1`. The new pivot Gram
determinant `gramDet (rowSwap b km1 k) k` satisfies the integer product
identity

    gramDet b' k · gramDet b k = gramDet b (k+1) · gramDet b km1 + B²

where `B = (scaledCoeffs b)[k][km1]`. This is the fraction-free form of the
standard rational adjacent-swap update used by integer LLL. -/



















/-- All-zero foldl: when every term in the foldl is zero, the result equals
the initial accumulator. -/
 theorem _root_.Hex.GramSchmidt.Int.foldl_add_zero_of_all_zero_rat {α : Type}
    (f : α → Rat) (xs : List α) (h : ∀ x ∈ xs, f x = 0) (acc : Rat) :
    xs.foldl (fun acc' x => acc' + f x) acc = acc := by
  induction xs generalizing acc with
  | nil => rfl
  | cons x xs ih =>
      simp only [List.foldl_cons]
      have hx : f x = 0 := h x (by simp)
      rw [hx, Rat.add_zero]
      exact ih (fun y hy => h y (by simp [hy])) acc

/-- Foldl isolation: when every term except the `j`-th vanishes, the foldl
over `List.finRange i` collapses to `f ⟨j, hj⟩`. -/
 theorem _root_.Hex.GramSchmidt.Int.foldl_finRange_isolate_rat :
    ∀ (i : Nat) (j : Nat) (hj : j < i) (f : Fin i → Rat),
      (∀ q : Fin i, q.val ≠ j → f q = 0) →
      (List.finRange i).foldl (fun acc q => acc + f q) 0 = f ⟨j, hj⟩
  | 0, _, hj, _, _ => absurd hj (Nat.not_lt_zero _)
  | i + 1, j, hj, f, h_zero => by
      rw [List.finRange_succ_last, List.foldl_append, List.foldl_map]
      simp only [List.foldl_cons, List.foldl_nil]
      by_cases hj_eq : j = i
      · -- j = i: the `Fin.last i` term contributes `f ⟨j, hj⟩`.
        subst hj_eq
        have hzero_pre : ∀ q : Fin j, f (Fin.castSucc q) = 0 := by
          intro q
          apply h_zero
          have : (Fin.castSucc q).val = q.val := rfl
          rw [this]
          exact Nat.ne_of_lt q.isLt
        have hmem_zero : ∀ q ∈ List.finRange j, f (Fin.castSucc q) = 0 := by
          intro q _
          exact hzero_pre q
        have hfold_zero :
            (List.finRange j).foldl
                (fun (acc : Rat) (q : Fin j) => acc + f (Fin.castSucc q)) 0 = 0 :=
          _root_.Hex.GramSchmidt.Int.foldl_add_zero_of_all_zero_rat (fun q => f (Fin.castSucc q))
            (List.finRange j) hmem_zero 0
        rw [hfold_zero, Rat.zero_add]
        rfl
      · -- j < i: recurse on the smaller range.
        have hjlt : j < i := by omega
        have hlast_zero : f (Fin.last i) = 0 := by
          apply h_zero
          have : (Fin.last i).val = i := rfl
          rw [this]
          omega
        rw [hlast_zero, Rat.add_zero]
        have hzero_pre : ∀ q : Fin i, q.val ≠ j → f (Fin.castSucc q) = 0 := by
          intro q hq_ne
          apply h_zero
          have : (Fin.castSucc q).val = q.val := rfl
          rw [this]
          exact hq_ne
        have hih := foldl_finRange_isolate_rat i j hjlt
          (fun q => f (Fin.castSucc q)) hzero_pre
        rw [hih]
        rfl





















end Int
end GramSchmidt
end Hex

/- Modified compatibility port (2026-11-15): imports namespaced under
Solutions.RegevBridgeNativeLLLVendor; pure Lean portability changes and removal
of native runtime hooks are recorded in MODIFICATIONS.json and the provenance
receipt. Original copyright/author notices and Apache-2.0 license are retained. -/

end

end
Source
Apache-2.0 leanprover/hex source and the already checked native LLL adapters. Exact original module locations and SHA-256 values are recorded in the validation receipt. Whole original declaration commands were retained using the official Lean declaration/sketch and structural syntax oracles, with original notices, checked computational definitions, and csimp proof logic preserved. All retained declaration types and safe non-theorem values were compared to the original environment using kernel-checked reflexivity after expanding safe generated implementation helpers. Source SHA-256: f5095a3d8b343d6a3eca95a915fc474e873f84892da6c31870e2bed303981673.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me