Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Checked integer Gram-Schmidt data and fraction-free invariants

Definition
LARLLL_IntegerGramSchmidt

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

linear-algebralllnative-algorithmsregev

The original integer Gram-Schmidt arrays, scaled coefficients, canonical fraction-free updates, and the proof-carrying invariant data needed by the concrete LLL state.

Definition code
import Definitions.Def_LARLLL_BareissProgram

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

/-!
Executable array/loop machinery for the integer scaled Gram-Schmidt pass in
`hex-gram-schmidt`.

This module defines the integer-determinant surface (`gramDet` and
`independent`, the leading Gram matrices (`leadingGramMatrixInt`/`Rat`),
`scaledCoeffMatrix`, lattice membership `memLattice`, and the no-pivot Bareiss
determinant reader `gramDetVecEntry`) together with the mutable row-major array
kernel that computes the scaled coefficients fraction-free. The kernel includes the
nested-array storage (`gramRows`, `zeroRows`, `getArrayEntry`/`setArrayEntry`,
`rowsToMatrix`), the Bareiss-style elimination sweep `stepScaledRows` and
column-writer `writeScaledColumn`, the driver `scaledCoeffArrayLoop`, the two
formulations `scaledCoeffRows` (reference) and `scaledCoeffRowsSchur` (live
per-row Schur recurrence, with `schurSigma`/`schurScaledCoeffEntry`), and a
large body of frame/size bookkeeping lemmas plus the per-step correspondence
`rowsToMatrix_stepScaledRows_eq` between the array update and `Matrix.stepMatrix`.
-/
namespace Hex

namespace GramSchmidt

/-- Promote an index into a shorter prefix to the ambient matrix height. -/
@[expose]
def liftFinLE (i : Fin k) (hk : k ≤ n) : Fin n :=
  ⟨i.val, Nat.lt_of_lt_of_le i.isLt hk⟩

/-- Leading principal Gram matrix of the first `k` rows of an integer basis. -/
@[expose]
def leadingGramMatrixInt (b : Matrix Int n m) (k : Nat) (hk : k ≤ n) : Matrix Int k k :=
  Matrix.ofFn fun i j =>
    (b.row (liftFinLE i hk)).dotProduct (b.row (liftFinLE j hk))





/-- Determinant matrix used by the integral `scaledCoeffs` entry formula:
take the leading `j + 1` Gram matrix and replace its last column by the inner
products with row `i`. -/
@[expose]
def scaledCoeffMatrix (b : Matrix Int n m) (i j : Fin n) (hji : j.val < i.val) :
    Matrix Int (j.val + 1) (j.val + 1) :=
  let hk : j.val + 1 ≤ n := Nat.succ_le_of_lt (Nat.lt_trans hji i.isLt)
  Matrix.ofFn fun p q =>
    let p' := liftFinLE p hk
    if q.val = j.val then
      (b.row p').dotProduct (b.row i)
    else
      let q' := liftFinLE q hk
      (b.row p').dotProduct (b.row q')

end GramSchmidt

namespace GramSchmidt.Int



/-- The `k`-th Gram determinant: the determinant of the `k × k` leading
principal Gram matrix of the integer input.

The bound `hk : k ≤ n` defaults to `by omega`, so callers with a concrete `k`
and `n` (as in `#guard`s and examples) can omit it. -/
@[expose]
def gramDet (b : Matrix Int n m) (k : Nat) (hk : k ≤ n := by omega) : Nat :=
  (Matrix.bareiss (GramSchmidt.leadingGramMatrixInt b k hk)).toNat

/-- Linear independence of the row prefix determinants used by the
Gram-Schmidt theorem surface, stated over the Mathlib-free executable
`gramDet` data. -/
@[expose]
def independent (b : Matrix Int n m) : Prop :=
  ∀ k : Fin n, 0 < gramDet b (k.val + 1) (Nat.succ_le_of_lt k.isLt)

/-- `independent` is decidable: it is a bounded conjunction of `Nat` positivity
tests on the leading Gram determinants. When *evaluated* (compiled) this is
efficient — each determinant is computed fraction-free (Bareiss) in cubic time.
Note it is not reducible by `decide` in the kernel, since `gramDet` runs through
Bareiss's well-founded recursion; use it for runtime tests, not kernel proofs. -/
instance _root_.Hex.GramSchmidt.Int.instDecidableIndependent (b : Matrix Int n m) : Decidable (independent b) := by
  unfold independent; infer_instance

/-- Product of the squared Gram-Schmidt basis norms along the first `k` rows. -/
@[expose]
noncomputable def gramSchmidtNormProduct (b : Matrix Int n m) (k : Nat) (hk : k ≤ n) :
    Rat :=
  Fin.foldl k
    (fun acc j =>
      let jn : Fin n := ⟨j.val, Nat.lt_of_lt_of_le j.isLt hk⟩
      acc * ((basis b).row jn).normSq)
    1

/-- Read a diagonal entry from a Bareiss elimination matrix as a natural
determinant value. -/
@[expose]
def bareissDiagNat (data : Matrix.BareissData Int n) (r : Nat) (hr : r < n) : Nat :=
  let i : Fin n := ⟨r, hr⟩
  (data.matrix[(i, i)]).toNat

/-- Read the `k`-th leading-principal determinant from one no-pivot Bareiss
elimination pass over the full Gram matrix. This helper is only used for Gram
matrices: once a leading row prefix is singular, every larger leading prefix is
also singular, so all later leading determinants are zero. -/
@[expose]
def gramDetVecEntry (data : Matrix.BareissData Int n) (k : Fin (n + 1)) : Nat :=
  match hk : k.val with
  | 0 => 1
  | r + 1 =>
      have hrSucc : r + 1 < n + 1 := by
        simpa [hk] using k.isLt
      have hr : r < n := Nat.succ_lt_succ_iff.mp hrSucc
      match data.singularStep with
      | some s => if s < r + 1 then 0 else
          bareissDiagNat data r hr
      | none => bareissDiagNat data r hr





/-- Mutable loop state for the integer scaled Gram-Schmidt pass: the current
step, the working matrix and coefficient arrays, and the previous Bareiss
pivot. -/
structure ScaledCoeffArrayState where
  step : Nat
  matrix : Array (Array Int)
  coeffs : Array (Array Int)
  prevPivot : Int

/-- Read entry `(row, col)` from a row-major nested array as `rows[row]![col]!`. -/
@[inline] def getArrayEntry (rows : Array (Array Int)) (row col : Nat) : Int :=
  rows[row]![col]!

/-- An `n × n` row-major nested array initialised to all zeros. -/
@[expose]
def zeroRows (n : Nat) : Array (Array Int) :=
  Array.replicate n (Array.replicate n 0)

/-- The Gram matrix of `b` packaged as a row-major nested integer array. -/
@[expose]
def gramRows (b : Matrix Int n m) : Array (Array Int) :=
  Array.ofFn fun i : Fin n =>
    Array.ofFn fun j : Fin n =>
      (b.row i).dotProduct (b.row j)

/-- Symmetry-aware implementation of integer Gram rows. The upper triangle is
computed once, then the lower triangle is filled by reading its transpose. -/
@[expose]
def gramRowsImpl (b : Matrix Int n m) : Array (Array Int) :=
  let upper : Vector (Vector Int n) n :=
    Vector.ofFn fun i =>
      Vector.ofFn fun j =>
        if i.val ≤ j.val then
          (b.row i).dotProduct (b.row j)
        else
          0
  Array.ofFn fun i : Fin n =>
    Array.ofFn fun j : Fin n =>
      if i.val ≤ j.val then upper[i][j] else upper[j][i]

/-- Compiled integer Gram-row construction uses symmetry while `gramRows`
remains the direct reference definition used by proofs. -/
@[csimp] theorem gramRows_eq_impl : @gramRows = @gramRowsImpl := by
  funext n m b
  apply Array.ext
  · simp [gramRows, gramRowsImpl]
  · intro i hi href
    apply Array.ext
    · simp [gramRows, gramRowsImpl]
    · intro j hj hrefj
      simp only [gramRows, gramRowsImpl, Array.getElem_ofFn,
        Vector.getElem_ofFn, Fin.getElem_fin]
      split <;> rename_i hij
      · rfl
      · have hji : j ≤ i := by omega
        rw [if_pos hji]
        exact Vector.dotProduct_comm (R := Int) _ _



/-- Reconstruct an `n × n` integer matrix from a row-major nested array, reading
entry `(i, j)` as `rows[i]![j]!` (`getArrayEntry`). This converts the executable
array passes back to the `Matrix` API; for the Gram rows it inverts `gramRows`,
so `rowsToMatrix (gramRows b) n = gramMatrix b`. -/
@[expose]
def rowsToMatrix (rows : Array (Array Int)) (n : Nat) : Matrix Int n n :=
  Matrix.ofFn fun i j => getArrayEntry rows i.val j.val



/-- Write `value` into entry `(row, col)` of a row-major nested array. -/
@[expose]
def setArrayEntry (rows : Array (Array Int)) (row col : Nat) (value : Int) :
    Array (Array Int) :=
  rows.set! row (rows[row]!.set! col value)













































/-- Write column `k` of the coefficient array, copying the matrix-column values
from row `k` downward. -/
@[expose]
def writeScaledColumn (coeffs rows : Array (Array Int)) (n k : Nat) :
    Array (Array Int) :=
  Id.run do
    let mut next := setArrayEntry coeffs k k (getArrayEntry rows k k)
    for i in [k + 1:n] do
      next := setArrayEntry next i k (getArrayEntry rows i k)
    return next



















@[expose]
def stepScaledRows (rows : Array (Array Int)) (n k : Nat)
    (pivot prevPivot : Int) : Array (Array Int) :=
  Id.run do
    let mut next := rows
    let pivotRow := rows[k]!
    for i in [k + 1:n] do
      next := next.modify i fun sourceRow =>
        let entryIK := sourceRow[k]!
        Id.run do
          let mut nextRow := sourceRow.set! k 0
          for j in [k + 1:n] do
            let value :=
              Matrix.exactDiv
                (pivot * nextRow[j]! - entryIK * pivotRow[j]!) prevPivot
            nextRow := nextRow.set! j value
          return nextRow
    return next

section StepScaledRowsBookkeeping



















end StepScaledRowsBookkeeping

@[expose]
def scaledCoeffArrayLoop (n fuel : Nat) (state : ScaledCoeffArrayState) :
    ScaledCoeffArrayState :=
  match fuel with
  | 0 => state
  | fuel + 1 =>
      if state.step < n then
        let k := state.step
        let coeffs := writeScaledColumn state.coeffs state.matrix n k
        let pivot := getArrayEntry state.matrix k k
        if k + 1 < n then
          if pivot = 0 then
            { state with coeffs := coeffs }
          else
            let next : ScaledCoeffArrayState :=
              { step := state.step + 1
                matrix := stepScaledRows state.matrix n k pivot state.prevPivot
                coeffs := coeffs
                prevPivot := pivot }
            scaledCoeffArrayLoop n fuel next
        else
          { state with step := state.step + 1, coeffs := coeffs }
      else
        state















/-- Run one no-pivot fraction-free Gram elimination and record each scaled
coefficient column immediately before the elimination step zeroes it.

This is the **reference formulation** of the scaled-coefficient matrix, kept
for proofs rather than execution. The live algorithm runs `scaledCoeffRowsSchur`
(the per-row Schur recurrence below); `getArrayEntry_scaledCoeffRowsSchur_eq`
proves the two agree entry-for-entry, and that bridge is what connects
`scaledCoeffRowsSchur` to `gramDet` / `scaledCoeffs`. Do not remove this
formulation as "unused": deleting it breaks the correctness proof of the live
path. -/
@[expose]
def scaledCoeffRows (b : Matrix Int n m) : Array (Array Int) :=
  let state :=
    scaledCoeffArrayLoop n n
      { step := 0
        matrix := gramRows b
        coeffs := zeroRows n
        prevPivot := 1 }
  state.coeffs

/-- Schur-complement σ-chain for the fraction-free scaled Gram-Schmidt
recurrence. Each step divides by the previous diagonal pivot `rows[p-1][p-1]`
via `Matrix.exactDiv`; that division is **exact** — the fraction-free Bareiss
invariant guarantees the numerator is divisible by the pivot, so `sigma` stays
an integer bounded by a minor determinant rather than growing as an unreduced
fraction. -/
@[expose]
def schurSigma (rows : Array (Array Int)) (i j : Nat) : Int :=
  Id.run do
    let mut sigma := getArrayEntry rows i 0 * getArrayEntry rows j 0
    for p in [1:j] do
      sigma :=
        Matrix.exactDiv
          (getArrayEntry rows p p * sigma +
            getArrayEntry rows i p * getArrayEntry rows j p)
          (getArrayEntry rows (p - 1) (p - 1))
    return sigma

@[expose]
def schurScaledCoeffEntry
    (rows gram : Array (Array Int)) (i j : Nat) : Int :=
  if j = 0 then
    getArrayEntry gram i 0
  else
    getArrayEntry rows (j - 1) (j - 1) * getArrayEntry gram i j -
      schurSigma rows i j

/-- Per-row Schur-complement scaled Gram-Schmidt coefficient kernel.

Rows are filled from top to bottom; within row `i`, entries `0..i` are written
left to right.  For `j < i` this writes the scaled coefficient `ν[i][j]`; for
`j = i` the same recurrence writes the diagonal Gram determinant `d_{i+1}`. -/
@[expose]
def scaledCoeffRowsSchur (b : Matrix Int n m) : Array (Array Int) :=
  Id.run do
    let gram := gramRows b
    let mut rows := zeroRows n
    for i in [0:n] do
      for j in [0:i + 1] do
        rows := setArrayEntry rows i j (schurScaledCoeffEntry rows gram i j)
    return rows





























end GramSchmidt.Int
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

/-!
Scaled-coefficient and Gram-determinant surface for `hex-gram-schmidt`.

This module packages the executable scaled Gram-Schmidt output: the `Data`
record bundling the leading Gram determinant vector `d` with the scaled
coefficient matrix `ν`, produced by `data` from a single
`scaledCoeffRowsSchur` pass, and exposed as the public `gramDetVec` and
`scaledCoeffs`. It proves the per-row Schur kernel agrees with the reference
`scaledCoeffRows` formulation (`schurSigma_congr` and the column/boundary
frame lemmas), and develops the Bareiss commutation infrastructure the
determinant correspondence rests on: a `Matrix.stepMatrix` step commutes with
taking a `principalSubmatrix` and with taking a trailing `borderedMinor`
(`principalSubmatrix_stepMatrix_eq`, `borderedMinor_stepMatrix_eq`), the no-pivot
loop stays synchronized across a matrix and its bordered minor
(`noPivotLoop_full_eq_borderedMinor_at_trailing`), it preserves trailing-block
symmetry, and its `step`/`singularStep` bookkeeping is monotone and stable
under prefixing.
-/
namespace Hex
namespace GramSchmidt.Int






/-- Integral scaled Gram-Schmidt coefficients. For `j < i`, the entry is the
determinant formula corresponding to `d_{j+1} * μ_{i,j}`; on the diagonal we
store `d_{j+1}`, and entries above the diagonal are zero. -/
structure Data (n : Nat) where
  d : Vector Nat (n + 1)
  ν : Matrix Int n n

@[expose]
def gramDetVecFromScaledCoeffRows (rows : Array (Array Int)) :
    Vector Nat (n + 1) :=
  Vector.ofFn fun k =>
    match hk : k.val with
    | 0 => 1
    | r + 1 =>
        have hrSucc : r + 1 < n + 1 := by
          simpa [hk] using k.isLt
        have _hr : r < n := Nat.succ_lt_succ_iff.mp hrSucc
        (getArrayEntry rows r r).toNat

/-- Run the per-row Schur scaled-coefficient kernel once and package both the
leading Gram determinant vector and the scaled Gram-Schmidt coefficient matrix. -/
@[expose]
def data (b : Matrix Int n m) : Data n :=
  let rows := scaledCoeffRowsSchur b
  { d := gramDetVecFromScaledCoeffRows rows
    ν := rowsToMatrix rows n }

/-- All leading Gram determinants, starting with the empty-prefix value
`d₀ = 1`. -/
@[expose]
def gramDetVec (b : Matrix Int n m) : Vector Nat (n + 1) :=
  (data b).d

/-- Integral scaled Gram-Schmidt coefficients. For `j < i`, the entry is the
determinant formula corresponding to `d_{j+1} * μ_{i,j}`; on the diagonal we
store `d_{j+1}`, and entries above the diagonal are zero. -/
@[expose]
def scaledCoeffs (b : Matrix Int n m) : Matrix Int n n :=
  (data b).ν







/-- Promote a bordered-minor coordinate to its lifted index in `Fin n`. -/
 def _root_.Hex.GramSchmidt.Int.liftBorderedIdx {n k : Nat} (hk : k < n) (anchor : Fin n) (x : Fin (k + 1)) :
    Fin n :=
  if h : x.val < k then ⟨x.val, Nat.lt_trans h hk⟩ else anchor























/-- Once the no-pivot Bareiss loop has reached the boundary
(`state.step + 1 ≥ n`), any further fuel is a no-op. -/
 theorem _root_.Hex.GramSchmidt.Int.noPivotLoop_id_at_done
    {n : Nat} (fuel : Nat) (state : Matrix.BareissState Int n)
    (hDone : ¬ state.step + 1 < n) :
    Matrix.noPivotLoop fuel state = state := by
  induction fuel with
  | zero => rfl
  | succ f _ih => exact Matrix.noPivotLoop_done f state hDone

/-- Once the no-pivot Bareiss loop has marked the current step singular
(`state.singularStep = some state.step` with a zero pivot at that step),
any further fuel is a no-op. -/
theorem noPivotLoop_id_at_singular_fixedpoint
    {n : Nat} (fuel : Nat) (state : Matrix.BareissState Int n)
    (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)
    (hsing : state.singularStep = some state.step) :
    Matrix.noPivotLoop fuel state = state := by
  induction fuel with
  | zero => rfl
  | succ f _ih =>
      rw [Matrix.noPivotLoop_of_singular f state hDone hp]
      -- Goal: {state with singularStep := some state.step} = state.
      cases state with
      | mk step matrix prevPivot rowSwaps singularStep =>
        simp only at hsing
        subst hsing
        rfl

/-- Fuel composition for the no-pivot Bareiss loop: running `a + b` units of
fuel from `state` equals running `b` more units after `a` initial units. -/
theorem noPivotLoop_add
    {n : Nat} (a b : Nat) (state : Matrix.BareissState Int n) :
    Matrix.noPivotLoop (a + b) state =
      Matrix.noPivotLoop b (Matrix.noPivotLoop a state) := by
  induction a generalizing state with
  | zero =>
      show Matrix.noPivotLoop (0 + b) state = Matrix.noPivotLoop b state
      simp
  | succ a' ih =>
      by_cases hDone : state.step + 1 < n
      · let k : Fin n :=
          ⟨state.step, Nat.lt_trans (Nat.lt_succ_self state.step) hDone⟩
        by_cases hp : state.matrix[k][k] = 0
        · -- Singular: both sides collapse to `{state with singularStep := some state.step}`.
          have h_lhs :
              Matrix.noPivotLoop (a' + 1 + b) state =
                {state with singularStep := some state.step} := by
            have : a' + 1 + b = (a' + b) + 1 := by omega
            rw [this]
            exact Matrix.noPivotLoop_of_singular (a' + b) state hDone hp
          have h_rhs_inner :
              Matrix.noPivotLoop (a' + 1) state =
                {state with singularStep := some state.step} :=
            Matrix.noPivotLoop_of_singular a' state hDone hp
          rw [h_lhs, h_rhs_inner]
          symm
          -- Now show: noPivotLoop b {state with singularStep := some state.step} = that.
          let s' : Matrix.BareissState Int n :=
            {state with singularStep := some state.step}
          have hDone_s' : s'.step + 1 < n := hDone
          have hp_s' : s'.matrix[(⟨s'.step, Nat.lt_of_succ_lt hDone_s'⟩ : Fin n)][(⟨s'.step, Nat.lt_of_succ_lt hDone_s'⟩ : Fin n)] = 0 := hp
          have hsing_s' : s'.singularStep = some s'.step := rfl
          exact noPivotLoop_id_at_singular_fixedpoint b s' hDone_s' hp_s' hsing_s'
        · -- Regular: both sides do one step then recurse on `next`.
          have h_lhs :
              Matrix.noPivotLoop (a' + 1 + b) state =
                Matrix.noPivotLoop (a' + b)
                  { step := state.step + 1
                    matrix := Matrix.stepMatrix state.matrix state.step
                      state.matrix[k][k] state.prevPivot
                    prevPivot := state.matrix[k][k]
                    rowSwaps := state.rowSwaps
                    singularStep := none } := by
            have : a' + 1 + b = (a' + b) + 1 := by omega
            rw [this]
            exact Matrix.noPivotLoop_of_regular (a' + b) state hDone hp
          have h_rhs_inner :
              Matrix.noPivotLoop (a' + 1) state =
                Matrix.noPivotLoop a'
                  { step := state.step + 1
                    matrix := Matrix.stepMatrix state.matrix state.step
                      state.matrix[k][k] state.prevPivot
                    prevPivot := state.matrix[k][k]
                    rowSwaps := state.rowSwaps
                    singularStep := none } :=
            Matrix.noPivotLoop_of_regular a' state hDone hp
          rw [h_lhs, h_rhs_inner]
          exact ih _
      · -- Boundary: both sides return `state` unchanged.
        rw [_root_.Hex.GramSchmidt.Int.noPivotLoop_id_at_done (a' + 1 + b) state hDone,
          _root_.Hex.GramSchmidt.Int.noPivotLoop_id_at_done (a' + 1) state hDone]
        exact (_root_.Hex.GramSchmidt.Int.noPivotLoop_id_at_done b state hDone).symm

/-- After running `noPivotLoop` from a state without a recorded singular
step, the result has either no singular step, or it has a singular step
that matches the current `step` field together with a zero pivot at that
position. -/
theorem noPivotLoop_singular_inv
    {n : Nat} (fuel : Nat) (state : Matrix.BareissState Int n)
    (h_init : state.singularStep = none) :
    (Matrix.noPivotLoop fuel state).singularStep = none ∨
    ∃ k : Fin n,
      (Matrix.noPivotLoop fuel state).singularStep = some k.val ∧
      (Matrix.noPivotLoop fuel state).step = k.val ∧
      (Matrix.noPivotLoop fuel state).matrix[k][k] = 0 ∧
      k.val + 1 < n := by
  induction fuel generalizing state with
  | zero =>
      left
      change state.singularStep = none
      exact h_init
  | succ f ih =>
      by_cases hDone : state.step + 1 < n
      · let k : Fin n := ⟨state.step, Nat.lt_of_succ_lt hDone⟩
        by_cases hp : state.matrix[k][k] = 0
        · -- Singular branch: result = {state with singularStep := some state.step}.
          right
          refine ⟨k, ?_, ?_, ?_, hDone⟩
          · rw [Matrix.noPivotLoop_of_singular f state hDone hp]
          · rw [Matrix.noPivotLoop_of_singular f state hDone hp]
          · rw [Matrix.noPivotLoop_of_singular f state hDone hp]
            exact hp
        · -- Regular branch
          rw [Matrix.noPivotLoop_of_regular f state hDone hp]
          exact ih _ rfl
      · -- Boundary
        rw [Matrix.noPivotLoop_done f state hDone]
        left; exact h_init





/-- A no-pivot Bareiss pass that never records a singular step preserves the
nonzero status of the previous pivot. Regular branches replace `prevPivot` by
the current nonzero pivot; singular branches contradict the final
`singularStep = none` hypothesis. -/
 theorem _root_.Hex.GramSchmidt.Int.noPivotLoop_prevPivot_ne_zero
    {n : Nat} (fuel : Nat) (state : Matrix.BareissState Int n)
    (hprev : state.prevPivot ≠ 0)
    (h_no_sing : (Matrix.noPivotLoop fuel state).singularStep = none) :
    (Matrix.noPivotLoop fuel state).prevPivot ≠ 0 := by
  induction fuel generalizing state with
  | zero =>
      simpa [Matrix.noPivotLoop_zero_fuel] using hprev
  | succ f ih =>
      by_cases hDone : state.step + 1 < n
      · by_cases hp : state.matrix[state.step][state.step] = 0
        · rw [Matrix.noPivotLoop_of_singular f state hDone hp] at h_no_sing
          simp at h_no_sing
        · rw [Matrix.noPivotLoop_of_regular f state hDone hp] at h_no_sing
          rw [Matrix.noPivotLoop_of_regular f state hDone hp]
          exact ih
            { step := state.step + 1
              matrix := Matrix.stepMatrix state.matrix state.step
                state.matrix[state.step][state.step] state.prevPivot
              prevPivot := state.matrix[state.step][state.step]
              rowSwaps := state.rowSwaps
              singularStep := none }
            hp h_no_sing
      · rw [Matrix.noPivotLoop_done f state hDone] at h_no_sing ⊢
        exact hprev













end GramSchmidt.Int
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.Int
/-! # Gram row-span invariant for no-pivot Bareiss -/

/-- Row-vector interpretation of the trailing block during a no-pivot Bareiss
pass over a Gram matrix.  Each active trailing row carries an explicit integer
coefficient vector `coeff i` such that the represented row is
`Matrix.vecMul (coeff i) b`, supported at coordinates `≤ i.val`, and
each matrix entry in that trailing row is its inner product against the
corresponding original row. -/
structure BareissGramRowInvariant (b : Matrix Int n m)
    (state : Matrix.BareissState Int n) where
  coeff : Fin n → Vector Int n
  coeff_supp : ∀ i k : Fin n, state.step ≤ i.val → i.val < k.val →
    (coeff i)[k] = 0
  entry_eq_dot : ∀ i j : Fin n, state.step ≤ i.val →
    state.matrix[i][j] =
      (Matrix.vecMul (coeff i) b).dotProduct (b.row j)

/-- The initial no-pivot Gram state satisfies the row-coefficient invariant
with each row represented by the standard basis vector `eᵢ`. -/
@[expose]
def bareissGramRowInvariant_initial (b : Matrix Int n m) :
    BareissGramRowInvariant b
      (Matrix.noPivotInitialState (Matrix.gramMatrix b)) := by
  refine
    { coeff := fun i => Vector.ofFn fun k : Fin n => if i = k then 1 else 0
      coeff_supp := ?_
      entry_eq_dot := ?_ }
  · intro i k _hi hik
    by_cases h : i = k
    · subst k
      omega
    · simp [h]
  · intro i j _hi
    have hsingle :
        Matrix.vecMul (Vector.ofFn fun k : Fin n => if i = k then (1 : Int) else 0) b =
          b.row i :=
      Matrix.IsRowReduced.vecMul_single (M := b) i
    rw [hsingle]
    simp only [Matrix.noPivotInitialState]
    rw [Matrix.getElem_gramMatrix]

/-- `foldl_sum_bareiss_row_update` pulls a Bareiss left row-update through a folded sum for later dot-product identities. -/
 theorem _root_.Hex.GramSchmidt.Int.foldl_sum_bareiss_row_update
    {α : Type u} (xs : List α) (x y : Int) (u v w : α → Int)
    (accU accV : Int) :
    xs.foldl
        (fun acc a => acc + ((x * u a - y * v a) * w a))
        (x * accU - y * accV) =
      x * xs.foldl (fun acc a => acc + u a * w a) accU -
        y * xs.foldl (fun acc a => acc + v a * w a) accV := by
  induction xs generalizing accU accV with
  | nil =>
      simp
  | cons a xs ih =>
      simp only [List.foldl_cons]
      have hstep :
          x * accU - y * accV + ((x * u a - y * v a) * w a) =
            x * (accU + u a * w a) - y * (accV + v a * w a) := by
        grind
      rw [hstep]
      exact ih (accU + u a * w a) (accV + v a * w a)

/-- `dot_bareiss_row_update_left` expands the dot product of a Bareiss-updated left vector as the corresponding linear combination of dots. -/
 theorem _root_.Hex.GramSchmidt.Int.dot_bareiss_row_update_left
    (x y : Int) (u v w : Vector Int m) :
    (Vector.ofFn fun a : Fin m => x * u[a] - y * v[a]).dotProduct w =
      x * u.dotProduct w - y * v.dotProduct w := by
  unfold Vector.dotProduct
  simpa [Fin.foldl_eq_finRange_foldl] using
    _root_.Hex.GramSchmidt.Int.foldl_sum_bareiss_row_update
      (xs := List.finRange m) x y
      (fun a : Fin m => u[a])
      (fun a : Fin m => v[a])
      (fun a : Fin m => w[a])
      0 0

/-- `foldl_sum_bareiss_row_update_right` pulls a Bareiss right row-update through a folded sum for the symmetric dot-product identity. -/
 theorem _root_.Hex.GramSchmidt.Int.foldl_sum_bareiss_row_update_right
    {α : Type u} (xs : List α) (x y : Int) (u v w : α → Int)
    (accU accV : Int) :
    xs.foldl
        (fun acc a => acc + (w a * (x * u a - y * v a)))
        (x * accU - y * accV) =
      x * xs.foldl (fun acc a => acc + w a * u a) accU -
        y * xs.foldl (fun acc a => acc + w a * v a) accV := by
  induction xs generalizing accU accV with
  | nil =>
      simp
  | cons a xs ih =>
      simp only [List.foldl_cons]
      have hstep :
          x * accU - y * accV + (w a * (x * u a - y * v a)) =
            x * (accU + w a * u a) - y * (accV + w a * v a) := by
        grind
      rw [hstep]
      exact ih (accU + w a * u a) (accV + w a * v a)

/-- `dot_bareiss_row_update_right` expands the dot product with a Bareiss-updated right vector as the corresponding linear combination of dots. -/
 theorem _root_.Hex.GramSchmidt.Int.dot_bareiss_row_update_right
    (x y : Int) (w u v : Vector Int m) :
    w.dotProduct (Vector.ofFn fun a : Fin m => x * u[a] - y * v[a]) =
      x * w.dotProduct u - y * w.dotProduct v := by
  unfold Vector.dotProduct
  simpa [Fin.foldl_eq_finRange_foldl] using
    _root_.Hex.GramSchmidt.Int.foldl_sum_bareiss_row_update_right
      (xs := List.finRange m) x y
      (fun a : Fin m => u[a])
      (fun a : Fin m => v[a])
      (fun a : Fin m => w[a])
      0 0

/-- `vecMul_bareiss_coeff_update` shows that row combinations respect the Bareiss coefficient update used by the Gram-row invariant. -/
 theorem _root_.Hex.GramSchmidt.Int.vecMul_bareiss_coeff_update
    (M : Matrix Int n m) (x y : Int) (c d : Vector Int n) :
    Matrix.vecMul (Vector.ofFn fun a : Fin n => x * c[a] - y * d[a]) M =
      Vector.ofFn fun j : Fin m =>
        x * (Matrix.vecMul c M)[j] - y * (Matrix.vecMul d M)[j] := by
  apply Vector.ext
  intro j hj
  let jf : Fin m := ⟨j, hj⟩
  show
      (Matrix.vecMul (Vector.ofFn fun a : Fin n => x * c[a] - y * d[a]) M)[jf] =
        (Vector.ofFn fun j : Fin m =>
          x * (Matrix.vecMul c M)[j] - y * (Matrix.vecMul d M)[j])[jf]
  unfold Matrix.vecMul
  have h_rhs :
      (Vector.ofFn fun j : Fin m => x * (M.transpose * c)[j] - y * (M.transpose * d)[j])[jf] =
        x * (M.transpose * c)[jf] - y * (M.transpose * d)[jf] := by
    simp
  rw [h_rhs]
  repeat rw [Matrix.getElem_mulVec]
  exact _root_.Hex.GramSchmidt.Int.dot_bareiss_row_update_right x y ((Matrix.transpose M).row jf) c d

/-- `exactDiv_eq_of_eq_mul_right` recovers the right quotient when the exact-division numerator is a quotient times the nonzero denominator. -/
 theorem _root_.Hex.GramSchmidt.Int.exactDiv_eq_of_eq_mul_right
    {num denom q : Int} (hdenom : denom ≠ 0) (hnum : num = q * denom) :
  Matrix.exactDiv num denom = q := by
  have hnum' : num = denom * q := by
    grind
  have hdvd : denom ∣ num := by
    refine ⟨q, ?_⟩
    exact hnum'
  rw [Matrix.exactDiv_eq_divExact hdvd, Int.divExact_eq_ediv hdvd]
  exact Int.ediv_eq_of_eq_mul_left hdenom hnum













/-- Coefficient witness produced by one regular Bareiss step on the row at
index `i`.  The functional shape mirrors the row update on the matrix side. -/
@[expose]
def bareissGramRowInvariantStepCoeff
    {b : Matrix Int n m} {state : Matrix.BareissState Int n}
    (hinv : BareissGramRowInvariant b state)
    (hnext : state.step + 1 < n) (i : Fin n) (_hi : state.step + 1 ≤ i.val) :
    Vector Int n :=
  let k : Fin n := ⟨state.step, Nat.lt_trans (Nat.lt_succ_self state.step) hnext⟩
  Vector.ofFn fun a : Fin n =>
    Matrix.exactDiv
      (state.matrix[(k, k)] * (hinv.coeff i)[a] -
        state.matrix[(i, k)] * (hinv.coeff k)[a])
      state.prevPivot

/-- Coefficient-level exact-division provenance for one regular Gram-row
Bareiss step.  The quotient vector is kept separate from
`bareissGramRowInvariantStepCoeff` so later row-entry proofs can consume the
integer divisibility witness before projecting back to the existing exact-div
coefficient API. -/
structure BareissGramRegularStepQuotient
    {b : Matrix Int n m} {state : Matrix.BareissState Int n}
    (hinv : BareissGramRowInvariant b state)
    (hnext : state.step + 1 < n) (i : Fin n) (_hi : state.step + 1 ≤ i.val) where
  q : Fin n → Int
  coeff_num_eq_mul :
    let k : Fin n := ⟨state.step, Nat.lt_trans (Nat.lt_succ_self state.step) hnext⟩
    ∀ a : Fin n,
      state.matrix[(k, k)] * (hinv.coeff i)[a] -
        state.matrix[(i, k)] * (hinv.coeff k)[a] =
          q a * state.prevPivot

 theorem _root_.Hex.GramSchmidt.Int.bareissGramRegularStepQuotient_stepCoeff_get
    {b : Matrix Int n m} {state : Matrix.BareissState Int n}
    {hinv : BareissGramRowInvariant b state}
    {hnext : state.step + 1 < n} {i : Fin n} {hi : state.step + 1 ≤ i.val}
    (hprev : state.prevPivot ≠ 0)
    (hq : BareissGramRegularStepQuotient hinv hnext i hi) (a : Fin n) :
    (bareissGramRowInvariantStepCoeff hinv hnext i hi)[a] = hq.q a := by
  dsimp [bareissGramRowInvariantStepCoeff]
  rw [Vector.getElem_ofFn]
  exact _root_.Hex.GramSchmidt.Int.exactDiv_eq_of_eq_mul_right hprev (hq.coeff_num_eq_mul a)

 theorem _root_.Hex.GramSchmidt.Int.bareissGramRegularStepQuotient_stepCoeff_eq
    {b : Matrix Int n m} {state : Matrix.BareissState Int n}
    {hinv : BareissGramRowInvariant b state}
    {hnext : state.step + 1 < n} {i : Fin n} {hi : state.step + 1 ≤ i.val}
    (hprev : state.prevPivot ≠ 0)
    (hq : BareissGramRegularStepQuotient hinv hnext i hi) :
    bareissGramRowInvariantStepCoeff hinv hnext i hi = Vector.ofFn hq.q := by
  apply Vector.ext
  intro a ha
  let af : Fin n := ⟨a, ha⟩
  simpa [af] using
    _root_.Hex.GramSchmidt.Int.bareissGramRegularStepQuotient_stepCoeff_get
      (hinv := hinv) (hnext := hnext) (i := i) (hi := hi) hprev hq af

 theorem _root_.Hex.GramSchmidt.Int.vecMul_bareissGramRegularStepQuotient
    {b : Matrix Int n m} {state : Matrix.BareissState Int n}
    {hinv : BareissGramRowInvariant b state}
    {hnext : state.step + 1 < n} {i : Fin n} {hi : state.step + 1 ≤ i.val}
    (hprev : state.prevPivot ≠ 0)
    (hq : BareissGramRegularStepQuotient hinv hnext i hi) :
    Matrix.vecMul (bareissGramRowInvariantStepCoeff hinv hnext i hi) b =
      Matrix.vecMul (Vector.ofFn hq.q) b := by
  rw [_root_.Hex.GramSchmidt.Int.bareissGramRegularStepQuotient_stepCoeff_eq hprev hq]

theorem bareissGramRowInvariantStepCoeff_support
    {b : Matrix Int n m} {state : Matrix.BareissState Int n}
    (hinv : BareissGramRowInvariant b state)
    (hnext : state.step + 1 < n) (i : Fin n) (hi : state.step + 1 ≤ i.val) :
    ∀ a : Fin n, i.val < a.val →
      (bareissGramRowInvariantStepCoeff hinv hnext i hi)[a] = 0 := by
  intro a hia
  dsimp [bareissGramRowInvariantStepCoeff]
  rw [Vector.getElem_ofFn]
  let k : Fin n := ⟨state.step, Nat.lt_trans (Nat.lt_succ_self state.step) hnext⟩
  have h_i : state.step ≤ i.val := Nat.le_trans (Nat.le_succ state.step) hi
  have h_k : state.step ≤ k.val := Nat.le_refl _
  have hci : (hinv.coeff i)[a] = 0 := hinv.coeff_supp i a h_i hia
  have hk_lt_i : k.val < i.val := by
    dsimp [k]
    omega
  have hka : k.val < a.val := Nat.lt_trans hk_lt_i hia
  have hck : (hinv.coeff k)[a] = 0 := hinv.coeff_supp k a h_k hka
  have hciNat : (hinv.coeff i)[a.val] = 0 := by simpa using hci
  have hckNat :
      (hinv.coeff
        (⟨state.step, Nat.lt_trans (Nat.lt_succ_self state.step) hnext⟩ : Fin n))[a.val] = 0 := by
    simpa [k] using hck
  simp [hciNat, hckNat, Matrix.exactDiv]

/-! # Canonical coefficient vector and canonicity predicate -/

/-- Canonical row-coefficient vector for the initial no-pivot Gram trajectory.

Base case: each row carries the standard basis vector `e_i`. Inductive step
(regular branch, active row): apply the fraction-free Bareiss row update via
`exactDiv`. Processed rows, singular branches, and done branches preserve the
previous vector unchanged — mirroring the row-invariant evolution in
`bareissGramRowInvariant_noPivotLoop_initialAux`.

Defined as a pure function of `b` and `fuel` (no `BareissGramRowInvariant`
argument), so the canonical coefficient is fixed by the matrix and step
count alone. Non-canonical row-coefficient witnesses are ruled out by the
`IsCanonicalAt` predicate consumed by `StepWitness`. -/
@[expose]
def bareissGramCanonicalCoeff (b : Matrix Int n m) :
    Nat → Fin n → Vector Int n
  | 0, i => Vector.ofFn fun k : Fin n => if i = k then 1 else 0
  | fuel + 1, i =>
    let state := Matrix.noPivotLoop fuel
      (Matrix.noPivotInitialState (Matrix.gramMatrix b))
    if hnext : state.step + 1 < n then
      if state.matrix[(state.step, state.step)] = 0 then
        bareissGramCanonicalCoeff b fuel i
      else if state.step + 1 ≤ i.val then
        let k : Fin n :=
          ⟨state.step, Nat.lt_trans (Nat.lt_succ_self state.step) hnext⟩
        Vector.ofFn fun a : Fin n =>
          Matrix.exactDiv
            (state.matrix[(k, k)] * (bareissGramCanonicalCoeff b fuel i)[a] -
              state.matrix[(i, k)] * (bareissGramCanonicalCoeff b fuel k)[a])
            state.prevPivot
      else
        bareissGramCanonicalCoeff b fuel i
    else
      bareissGramCanonicalCoeff b fuel i



/-- Recursion equation: regular-branch active-row case. With the branch
hypotheses in context, `simp [*]`/`simp_all` rewrites `bareissGramCanonicalCoeff`
at `fuel + 1` to its explicit Bareiss exact-division update. -/
@[simp, grind =] theorem bareissGramCanonicalCoeff_succ_regular
    (b : Matrix Int n m) (fuel : Nat) (i : Fin n)
    (hnext :
      (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 < n)
    (hp :
      (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)
    (hi :
      (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 ≤ i.val) :
    bareissGramCanonicalCoeff b (fuel + 1) i =
      (let state := Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))
       let k : Fin n :=
         ⟨state.step, Nat.lt_trans (Nat.lt_succ_self state.step) hnext⟩
       Vector.ofFn fun a : Fin n =>
         Matrix.exactDiv
           (state.matrix[k][k] * (bareissGramCanonicalCoeff b fuel i)[a] -
             state.matrix[i][k] * (bareissGramCanonicalCoeff b fuel k)[a])
           state.prevPivot) := by
  simp [bareissGramCanonicalCoeff, dif_pos hnext, if_pos hi]
  intro hc
  simp only [Matrix.getElem_nat_eq_getRow] at hp
  exact absurd hc hp

/-- Recursion equation: regular-branch processed-row case. An already-processed
row (`i ≤ step`) keeps its previous coefficient vector, so the canonical
coefficient at `fuel + 1` collapses to the one at `fuel`. -/
@[simp, grind =] theorem bareissGramCanonicalCoeff_succ_processed
    (b : Matrix Int n m) (fuel : Nat) (i : Fin n)
    (hnext :
      (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 < n)
    (_hp :
      (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)
    (hi : ¬ (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 ≤ i.val) :
    bareissGramCanonicalCoeff b (fuel + 1) i =
      bareissGramCanonicalCoeff b fuel i := by
  simp [bareissGramCanonicalCoeff, dif_pos hnext, if_neg hi]

/-- Recursion equation: singular branch (zero diagonal). A zero pivot skips the
update, so the canonical coefficient at `fuel + 1` collapses to the one at
`fuel`. -/
@[simp, grind =] theorem bareissGramCanonicalCoeff_succ_singular
    (b : Matrix Int n m) (fuel : Nat) (i : Fin n)
    (hnext :
      (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 < n)
    (hp :
      (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) :
    bareissGramCanonicalCoeff b (fuel + 1) i =
      bareissGramCanonicalCoeff b fuel i := by
  simp [bareissGramCanonicalCoeff, dif_pos hnext]
  intro hc
  simp only [Matrix.getElem_nat_eq_getRow] at hp
  exact absurd hp hc

/-- Recursion equation: done branch (no further work possible). Once the loop can
take no further step (`¬ step + 1 < n`), the canonical coefficient at `fuel + 1`
collapses to the one at `fuel`. -/
@[simp, grind =] theorem bareissGramCanonicalCoeff_succ_done
    (b : Matrix Int n m) (fuel : Nat) (i : Fin n)
    (hDone : ¬ (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 < n) :
    bareissGramCanonicalCoeff b (fuel + 1) i =
      bareissGramCanonicalCoeff b fuel i := by
  simp only [bareissGramCanonicalCoeff, dif_neg hDone]

/-- A `BareissGramRowInvariant` on `noPivotLoop fuel (noPivotInitialState …)`
is *canonical at `fuel`* when every row's coefficient vector matches
`bareissGramCanonicalCoeff`. This is the soundness gate consumed by
`StepWitness`: non-canonical witnesses (which can shift coefficients by a
kernel vector while keeping `entry_eq_dot` satisfied) cannot invoke the
witness's quotient identity.

The rows `(1,1), (1,0), (-1,-1)` produce two
distinct `BareissGramRowInvariant` instances at the same loop state whose
coefficient vectors differ by the kernel vector. Both satisfy `entry_eq_dot`,
but only one (the canonical one) yields an integer Bareiss-step quotient. -/
@[expose]
def IsCanonicalAt (b : Matrix Int n m) (fuel : Nat)
    (hinv : BareissGramRowInvariant b
      (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b)))) : Prop :=
  ∀ i : Fin n, hinv.coeff i = bareissGramCanonicalCoeff b fuel i

/-- The base-case row invariant at `fuel = 0` carries the standard basis vectors
and is therefore canonical. -/
theorem isCanonicalAt_initial (b : Matrix Int n m) :
    IsCanonicalAt b 0 (bareissGramRowInvariant_initial b) := by
  intro i
  rfl

/-- Transport along an equation of `BareissState`s preserves the `coeff` field
of a `BareissGramRowInvariant`. The field's type `Fin n → Vector Int n` does
not depend on the state index, so transport is the identity at that
projection. Used to discharge canonicity proofs after transporting an explicit
intermediate state back to the `noPivotLoop fuel initial` form. -/
theorem bareissGramRowInvariant_coeff_transport
    {b : Matrix Int n m} {st1 st2 : Matrix.BareissState Int n}
    (h : st1 = st2) (x : BareissGramRowInvariant b st2) (i : Fin n) :
    (h ▸ x).coeff i = x.coeff i := by
  cases h
  rfl

/-- Right-scalar linearity of the dot product against a `vecMul` whose
coefficient vector is multiplied pointwise by a constant on the right.  Used
to factor the Bareiss exact-division denominator out of a quotient-backed row
combination. -/
 theorem _root_.Hex.GramSchmidt.Int.dot_vecMul_mul_right_int
    (b : Matrix Int n m) (f : Fin n → Int) (s : Int) (w : Vector Int m) :
    Vector.dotProduct
        (Matrix.vecMul (Vector.ofFn fun a : Fin n => f a * s) b) w =
      (Matrix.vecMul (Vector.ofFn f) b).dotProduct w * s := by
  have h_eq_input :
      (Vector.ofFn fun a : Fin n => f a * s) =
        Vector.ofFn fun a : Fin n =>
          s * (Vector.ofFn f)[a] - 0 * (Vector.ofFn f)[a] := by
    apply Vector.ext
    intro a ha
    simp only [Vector.getElem_ofFn]
    grind
  rw [h_eq_input, _root_.Hex.GramSchmidt.Int.vecMul_bareiss_coeff_update b s 0 (Vector.ofFn f) (Vector.ofFn f)]
  rw [_root_.Hex.GramSchmidt.Int.dot_bareiss_row_update_left s 0
    (Matrix.vecMul (Vector.ofFn f) b)
    (Matrix.vecMul (Vector.ofFn f) b) w]
  grind

/-- Row-entry algebra for one regular Gram-row Bareiss step.  Consuming the
quotient-coefficient package `BareissGramRegularStepQuotient` together with a
nonzero `prevPivot` and the already-processed-column zero entries gives the
exact row-entry relation for `Matrix.stepMatrix` at row `i` and any column
`j`.  Covers the three column regimes: `j.val < state.step` (already-cleared
column, both sides zero), `j.val = state.step` (pivot column below the pivot,
both sides zero), and `state.step < j.val` (trailing block, `exactDiv` of the
Bareiss numerator). -/
 theorem _root_.Hex.GramSchmidt.Int.bareissGramRegularStep_entry_eq_dot
    {b : Matrix Int n m} {state : Matrix.BareissState Int n}
    {hinv : BareissGramRowInvariant b state}
    {hnext : state.step + 1 < n} {i : Fin n} {hi : state.step + 1 ≤ i.val}
    (hprev : state.prevPivot ≠ 0)
    (hq : BareissGramRegularStepQuotient hinv hnext i hi)
    (h_processed : ∀ i' : Fin n, state.step ≤ i'.val →
      ∀ j' : Fin n, j'.val < state.step → state.matrix[i'][j'] = 0)
    (j : Fin n) :
    (Matrix.stepMatrix state.matrix state.step
        state.matrix[state.step][state.step] state.prevPivot)[i][j] =
      Vector.dotProduct
        (Matrix.vecMul (bareissGramRowInvariantStepCoeff hinv hnext i hi) b)
        (b.row j) := by
  let k : Fin n := ⟨state.step, Nat.lt_trans (Nat.lt_succ_self state.step) hnext⟩
  have hk_val : k.val = state.step := rfl
  have h_step_le_i : state.step ≤ i.val := Nat.le_trans (Nat.le_succ _) hi
  have h_step_lt_i : state.step < i.val := hi
  have h_step_le_k : state.step ≤ k.val := Nat.le_refl _
  let lhsNum : Int :=
    state.matrix[k][k] * state.matrix[i][j] - state.matrix[i][k] * state.matrix[k][j]
  have hLHS_num : lhsNum =
      state.matrix[k][k] * state.matrix[i][j] -
        state.matrix[i][k] * state.matrix[k][j] := rfl
  -- Claim A: the dot product of the "numerator-side" row combination is lhsNum.
  have h_dot_num :
      Vector.dotProduct
          (Matrix.vecMul (Vector.ofFn fun a : Fin n =>
              state.matrix[k][k] * (hinv.coeff i)[a] -
                state.matrix[i][k] * (hinv.coeff k)[a]) b)
          (b.row j) = lhsNum := by
    rw [_root_.Hex.GramSchmidt.Int.vecMul_bareiss_coeff_update b
      state.matrix[k][k] state.matrix[i][k] (hinv.coeff i) (hinv.coeff k)]
    rw [_root_.Hex.GramSchmidt.Int.dot_bareiss_row_update_left
      state.matrix[k][k] state.matrix[i][k]
      (Matrix.vecMul (hinv.coeff i) b)
      (Matrix.vecMul (hinv.coeff k) b)
      (b.row j)]
    rw [← hinv.entry_eq_dot i j h_step_le_i,
        ← hinv.entry_eq_dot k j h_step_le_k]
  -- Claim B: the dot product of the step coefficient row combination equals
  -- `exactDiv lhsNum prevPivot`.
  have h_dot_step :
      Vector.dotProduct
          (Matrix.vecMul (bareissGramRowInvariantStepCoeff hinv hnext i hi) b)
          (b.row j) = Matrix.exactDiv lhsNum state.prevPivot := by
    rw [_root_.Hex.GramSchmidt.Int.vecMul_bareissGramRegularStepQuotient hprev hq]
    refine (_root_.Hex.GramSchmidt.Int.exactDiv_eq_of_eq_mul_right hprev ?_).symm
    have h_dot_mul :=
      _root_.Hex.GramSchmidt.Int.dot_vecMul_mul_right_int b hq.q state.prevPivot (b.row j)
    rw [← h_dot_mul]
    have h_q_eq_num :
        (Vector.ofFn fun a : Fin n => hq.q a * state.prevPivot) =
          (Vector.ofFn fun a : Fin n =>
            state.matrix[k][k] * (hinv.coeff i)[a] -
              state.matrix[i][k] * (hinv.coeff k)[a]) := by
      apply Vector.ext
      intro a ha
      rw [Vector.getElem_ofFn, Vector.getElem_ofFn]
      have h := (hq.coeff_num_eq_mul ⟨a, ha⟩).symm
      simp only [Matrix.getElem_pair_eq_nested] at h
      exact h
    rw [h_q_eq_num]
    exact h_dot_num.symm
  -- Case split on `j.val` against `state.step`.
  by_cases hjk : state.step < j.val
  · -- Trailing block: stepMatrix is the Bareiss exactDiv update.
    rw [Matrix.stepMatrix_update_eq state.matrix state.step
      state.matrix[state.step][state.step] state.prevPivot i j h_step_lt_i hjk]
    rw [h_dot_step]
    rfl
  · by_cases hjeq : j.val = state.step
    · -- Pivot column, below the pivot: stepMatrix entry is 0, and `lhsNum = 0`.
      rw [Matrix.stepMatrix_pivot_col_below state.matrix state.step
        state.matrix[state.step][state.step] state.prevPivot i j h_step_lt_i hjeq]
      rw [h_dot_step]
      have h_j_eq_k : j = k := Fin.ext (by rw [hjeq, hk_val])
      have h_lhs_num_zero : lhsNum = 0 := by
        rw [hLHS_num, h_j_eq_k]; grind
      rw [h_lhs_num_zero]
      symm
      exact _root_.Hex.GramSchmidt.Int.exactDiv_eq_of_eq_mul_right hprev
        (by grind : (0 : Int) = 0 * state.prevPivot)
    · -- Already-processed column: stepMatrix carries over, both sides zero.
      have hj_lt : j.val < state.step :=
        Nat.lt_of_le_of_ne (Nat.le_of_not_lt hjk) hjeq
      have h_not_trail : ¬ (state.step < i.val ∧ state.step < j.val) := by
        intro ⟨_, h2⟩; exact absurd h2 (Nat.not_lt_of_le (Nat.le_of_lt hj_lt))
      have h_not_col : ¬ (state.step < i.val ∧ j.val = state.step) := by
        intro ⟨_, h2⟩; exact hjeq h2
      rw [Matrix.stepMatrix_eq_of_not_update state.matrix state.step
        state.matrix[state.step][state.step] state.prevPivot i j h_not_trail h_not_col]
      have h_i_j_zero : state.matrix[i][j] = 0 := h_processed i h_step_le_i j hj_lt
      have h_k_j_zero : state.matrix[k][j] = 0 := h_processed k h_step_le_k j hj_lt
      have h_lhs_num_zero : lhsNum = 0 := by
        rw [hLHS_num, h_i_j_zero, h_k_j_zero]; grind
      rw [h_dot_step, h_lhs_num_zero, h_i_j_zero]
      symm
      exact _root_.Hex.GramSchmidt.Int.exactDiv_eq_of_eq_mul_right hprev
        (by grind : (0 : Int) = 0 * state.prevPivot)

/-- One regular no-pivot Bareiss step preserves the Gram row-coefficient
invariant, provided the later loop proof supplies the exact-division entry
relation for the fraction-free updated row combinations. -/
@[expose]
def bareissGramRowInvariant_regular_step
    {b : Matrix Int n m} {state : Matrix.BareissState Int n}
    (hnext : state.step + 1 < n)
    (_hp : state.matrix[state.step][state.step] ≠ 0)
    (hinv : BareissGramRowInvariant b state)
    (hentry :
      ∀ i j : Fin n, (hi : state.step + 1 ≤ i.val) →
        (Matrix.stepMatrix state.matrix state.step
            state.matrix[state.step][state.step] state.prevPivot)[i][j] =
          Vector.dotProduct
            (Matrix.vecMul (bareissGramRowInvariantStepCoeff hinv hnext i hi) b)
            (b.row j)) :
    BareissGramRowInvariant b
      { step := state.step + 1
        matrix := Matrix.stepMatrix state.matrix state.step
          state.matrix[state.step][state.step] state.prevPivot
        prevPivot := state.matrix[state.step][state.step]
        rowSwaps := state.rowSwaps
        singularStep := none } := by
  refine
    { coeff := fun i =>
        if hi : state.step + 1 ≤ i.val then
          bareissGramRowInvariantStepCoeff hinv hnext i hi
        else
          hinv.coeff i
      coeff_supp := ?_
      entry_eq_dot := ?_ }
  · intro i k hi hik
    have hi' : state.step + 1 ≤ i.val := hi
    simp [hi', bareissGramRowInvariantStepCoeff_support hinv hnext i hi' k hik]
  · intro i j hi
    have hi' : state.step + 1 ≤ i.val := hi
    simpa [hi'] using hentry i j hi'

/-- The coefficient vectors produced by `bareissGramRowInvariant_regular_step`
from a canonical input invariant match `bareissGramCanonicalCoeff` at the
next-step fuel index. Used to propagate canonicity through one regular Bareiss
step inside `bareissGramRowInvariant_noPivotLoop_initialAux`. -/
theorem bareissGramRowInvariant_regular_step_coeff_canonical
    (b : Matrix Int n m) (elapsed : Nat)
    (hinv : BareissGramRowInvariant b
      (Matrix.noPivotLoop elapsed
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))))
    (h_canon : IsCanonicalAt b elapsed hinv)
    (hnext :
      (Matrix.noPivotLoop elapsed
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 < n)
    (hp :
      (Matrix.noPivotLoop elapsed
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).matrix[
          (Matrix.noPivotLoop elapsed
            (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step][
          (Matrix.noPivotLoop elapsed
            (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step] ≠ 0)
    (hentry :
      ∀ i j : Fin n,
        (hi : (Matrix.noPivotLoop elapsed
          (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 ≤ i.val) →
        (Matrix.stepMatrix
          (Matrix.noPivotLoop elapsed
            (Matrix.noPivotInitialState (Matrix.gramMatrix b))).matrix
          (Matrix.noPivotLoop elapsed
            (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step
          (Matrix.noPivotLoop elapsed
            (Matrix.noPivotInitialState (Matrix.gramMatrix b))).matrix[
              (Matrix.noPivotLoop elapsed
                (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step][
              (Matrix.noPivotLoop elapsed
                (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step]
          (Matrix.noPivotLoop elapsed
            (Matrix.noPivotInitialState (Matrix.gramMatrix b))).prevPivot)[i][j] =
          Vector.dotProduct
            (Matrix.vecMul (bareissGramRowInvariantStepCoeff hinv hnext i hi) b)
            (b.row j))
    (i : Fin n) :
    (bareissGramRowInvariant_regular_step hnext hp hinv hentry).coeff i =
      bareissGramCanonicalCoeff b (elapsed + 1) i := by
  -- The regular_step constructor produces `if step+1 ≤ i.val then stepCoeff else hinv.coeff i`.
  by_cases hi : (Matrix.noPivotLoop elapsed
      (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 ≤ i.val
  · have hLHS :
        (bareissGramRowInvariant_regular_step hnext hp hinv hentry).coeff i =
          bareissGramRowInvariantStepCoeff hinv hnext i hi := by
      show (if hi : _ then _ else _) = _
      rw [dif_pos hi]
    rw [hLHS, bareissGramCanonicalCoeff_succ_regular b elapsed i hnext hp hi]
    show Vector.ofFn (fun a : Fin n =>
        Matrix.exactDiv
          (_ * (hinv.coeff i)[a] - _ * (hinv.coeff _)[a])
          _) = _
    rw [h_canon i,
        h_canon ⟨(Matrix.noPivotLoop elapsed
          (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step,
          Nat.lt_trans (Nat.lt_succ_self _) hnext⟩]
    simp only [Hex.Matrix.getElem_pair_eq_nested]
  · have hLHS :
        (bareissGramRowInvariant_regular_step hnext hp hinv hentry).coeff i =
          hinv.coeff i := by
      show (if hi : _ then _ else _) = _
      rw [dif_neg hi]
    rw [hLHS, bareissGramCanonicalCoeff_succ_processed b elapsed i hnext hp hi]
    exact h_canon i



/-- On a nonsingular initial no-pivot Gram trajectory, any current state that is
ready for a regular next step has a nonzero previous pivot. -/
 theorem _root_.Hex.GramSchmidt.Int.noPivotLoop_initial_gram_prevPivot_ne_zero
    (b : Matrix Int n m) (fuel : Nat)
    (h_prefix_none :
      (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).singularStep = none)
    (_hnext :
      (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 < n)
    (_hp :
      (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) :
    (Matrix.noPivotLoop fuel
      (Matrix.noPivotInitialState (Matrix.gramMatrix b))).prevPivot ≠ 0 := by
  apply _root_.Hex.GramSchmidt.Int.noPivotLoop_prevPivot_ne_zero
  · simp [Matrix.noPivotInitialState]
  · exact h_prefix_none



/-- After running `noPivotLoop fuel` from a state with `singularStep = none`, if
the result also has `singularStep = none`, then every column strictly between
the initial step and the final step is zero below the pivot in the final
matrix. Each such column was processed by a regular Bareiss step that cleared
its sub-diagonal entries, and no later iteration touches them. -/
 theorem _root_.Hex.GramSchmidt.Int.noPivotLoop_matrix_processed_col_eq_zero {n : Nat} (fuel : Nat) :
    ∀ (state : Matrix.BareissState Int n),
      (Matrix.noPivotLoop fuel state).singularStep = none →
      ∀ (k : Nat), state.step ≤ k →
        k < (Matrix.noPivotLoop fuel state).step →
        ∀ (kFin : Fin n), kFin.val = k →
        ∀ (i : Fin n), k < i.val →
          (Matrix.noPivotLoop fuel state).matrix[i][kFin] = 0 := by
  induction fuel with
  | zero =>
      intros state _h_result k hk_ge hk_lt _kFin _hkFin i _hki
      simp [Matrix.noPivotLoop_zero_fuel] at hk_lt
      omega
  | succ f ih =>
      intros state h_result_none k hk_ge hk_lt kFin hkFin i hki
      by_cases hDone : state.step + 1 < n
      · by_cases hp : state.matrix[state.step][state.step] = 0
        · -- Singular branch contradicts h_result_none.
          rw [Matrix.noPivotLoop_of_singular f state hDone hp] at h_result_none
          simp at h_result_none
        · -- Regular branch.
          let next : Matrix.BareissState Int n :=
            { step := state.step + 1
              matrix := Matrix.stepMatrix state.matrix state.step
                state.matrix[state.step][state.step] state.prevPivot
              prevPivot := state.matrix[state.step][state.step]
              rowSwaps := state.rowSwaps
              singularStep := none }
          have h_eq_next : Matrix.noPivotLoop (f + 1) state =
              Matrix.noPivotLoop f next :=
            Matrix.noPivotLoop_of_regular f state hDone hp
          rw [h_eq_next] at h_result_none hk_lt ⊢
          by_cases hk_eq : k = state.step
          · -- k just got processed: column k was zeroed by stepMatrix.
            have hi_lt : state.step < i.val := hk_eq ▸ hki
            have hkFin_eq : kFin.val = state.step := hk_eq ▸ hkFin
            have h_next_zero : next.matrix[i][kFin] = 0 :=
              Matrix.stepMatrix_pivot_col_below state.matrix state.step
                state.matrix[state.step][state.step] state.prevPivot i kFin hi_lt hkFin_eq
            have h_fixed : kFin.val < next.step := by
              change kFin.val < state.step + 1
              omega
            have h_eq :=
              Matrix.noPivotLoop_matrix_entry_of_row_le_or_col_lt f next i kFin
                (Or.inr h_fixed)
            rw [h_eq]
            exact h_next_zero
          · -- k was processed at a later step inside `next`.
            have hk_ge_next : next.step ≤ k := by
              change state.step + 1 ≤ k
              omega
            exact ih next h_result_none k hk_ge_next hk_lt kFin hkFin i hki
      · -- Done branch: state.step unchanged, so hk_lt collapses.
        have h_eq_state : Matrix.noPivotLoop (f + 1) state = state :=
          Matrix.noPivotLoop_done f state hDone
        rw [h_eq_state] at h_result_none hk_lt ⊢
        omega

/-- Initial no-pivot Gram trajectory specialization of the regular row-entry
algebra.  The quotient package supplies the coefficient-side divisibility
provenance; the initial trajectory supplies nonzero `prevPivot` and the
already-processed column zeros needed by the one-step algebra. -/
 theorem _root_.Hex.GramSchmidt.Int.bareissGramInitialRegularStep_entry_eq_dot
    (b : Matrix Int n m) (fuel : Nat)
    (hinv : BareissGramRowInvariant b
      (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))))
    (h_prefix_none :
      (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).singularStep = none)
    (hnext :
      (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 < n)
    (hp :
      (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)
    (i j : Fin n)
    (hi :
      (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 ≤ i.val)
    (hq : BareissGramRegularStepQuotient hinv hnext i hi) :
    (Matrix.stepMatrix
        (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))).matrix[
            (Matrix.noPivotLoop fuel
              (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step][
            (Matrix.noPivotLoop fuel
              (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step]
        (Matrix.noPivotLoop fuel
          (Matrix.noPivotInitialState (Matrix.gramMatrix b))).prevPivot)[i][j] =
      Vector.dotProduct
        (Matrix.vecMul (bareissGramRowInvariantStepCoeff hinv hnext i hi) b)
        (b.row j) := by
  let state :=
    Matrix.noPivotLoop fuel
      (Matrix.noPivotInitialState (Matrix.gramMatrix b))
  have hprev : state.prevPivot ≠ 0 :=
    _root_.Hex.GramSchmidt.Int.noPivotLoop_initial_gram_prevPivot_ne_zero
      b fuel h_prefix_none hnext hp
  have h_processed :
      ∀ i' : Fin n, state.step ≤ i'.val →
        ∀ j' : Fin n, j'.val < state.step → state.matrix[i'][j'] = 0 := by
    intro i' hi' j' hj'
    exact _root_.Hex.GramSchmidt.Int.noPivotLoop_matrix_processed_col_eq_zero fuel
      (Matrix.noPivotInitialState (Matrix.gramMatrix b)) h_prefix_none
      j'.val (by simp [Matrix.noPivotInitialState]) hj' j' rfl i'
      (Nat.lt_of_lt_of_le hj' hi')
  exact _root_.Hex.GramSchmidt.Int.bareissGramRegularStep_entry_eq_dot hprev hq h_processed j

/-- Per-step quotient package for the initial no-pivot Gram trajectory,
restricted to *canonical* row-coefficient witnesses via `IsCanonicalAt`.

`StepWitness.Cell` is an alias for `BareissGramRegularStepQuotient` whose
canonicity gate (`h_canon`) prevents non-canonical `BareissGramRowInvariant`
witnesses — which can shift coefficients by a kernel vector while still
satisfying `entry_eq_dot` — from supplying integer quotients. The kernel-shift
counterexample with rows `(1,1), (1,0), (-1,-1)` at row 2 step 1
shows the restriction is necessary: distinct non-canonical witnesses produce
numerators differing by `1`, which is not divisible by `prevPivot = 2`. -/
abbrev StepWitness.Cell
    (b : Matrix Int n m) (fuel : Nat)
    (hinv : BareissGramRowInvariant b
      (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))))
    (_h_canon : IsCanonicalAt b fuel hinv)
    (hnext :
      (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 < n)
    (i : Fin n)
    (hi :
      (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 ≤ i.val) :
    Type :=
  BareissGramRegularStepQuotient hinv hnext i hi

/-- Quotient provenance for the initial no-pivot Gram trajectory, restricted
to canonical `BareissGramRowInvariant` witnesses via `IsCanonicalAt`. The
provider supplies, at every reachable regular Bareiss step, an integer
quotient `q : Fin n → Int` realising the Bareiss-row-update divisibility on
the canonical coefficient vectors.

Concrete providers are constructed in `HexGramSchmidtTheory`, where the
Bareiss-Desnanot proof infrastructure on PSD Gram minors is available; the
Mathlib-free layer only consumes this abstraction. -/
abbrev StepWitness (b : Matrix Int n m) : Type :=
  ∀ (fuel : Nat)
    (hinv : BareissGramRowInvariant b
      (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))))
    (h_canon : IsCanonicalAt b fuel hinv)
    (h_prefix_none :
      (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).singularStep = none)
    (hnext :
      (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 < n)
    (_hp :
      (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)
    (i : Fin n)
    (hi :
      (Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 ≤ i.val),
      StepWitness.Cell b fuel hinv h_canon hnext i hi

/-- Canonical row-coefficients are unchanged once the no-pivot Bareiss loop
has reached the boundary `state.step + 1 = n`. Used to propagate canonicity
through the done branch of `bareissGramRowInvariant_noPivotLoop_initialAux`. -/
 theorem _root_.Hex.GramSchmidt.Int.bareissGramCanonicalCoeff_eq_of_done
    {n m : Nat} (b : Matrix Int n m) (elapsed j : Nat) (i : Fin n)
    (hDone :
      ¬ (Matrix.noPivotLoop elapsed
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 < n) :
    bareissGramCanonicalCoeff b (elapsed + j) i =
      bareissGramCanonicalCoeff b elapsed i := by
  induction j with
  | zero => rfl
  | succ j ih =>
      have h_state_eq :
          Matrix.noPivotLoop (elapsed + j)
            (Matrix.noPivotInitialState (Matrix.gramMatrix b)) =
          Matrix.noPivotLoop elapsed
            (Matrix.noPivotInitialState (Matrix.gramMatrix b)) := by
        rw [noPivotLoop_add elapsed j]
        exact _root_.Hex.GramSchmidt.Int.noPivotLoop_id_at_done j _ hDone
      have hDone' :
          ¬ (Matrix.noPivotLoop (elapsed + j)
            (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 < n := by
        rw [h_state_eq]; exact hDone
      rw [show elapsed + (j + 1) = (elapsed + j) + 1 from by omega,
          bareissGramCanonicalCoeff_succ_done b (elapsed + j) i hDone']
      exact ih

/-- State-equation variant of `bareissGramCanonicalCoeff_succ_singular`: when
the no-pivot Bareiss state at `fuel` is propositionally equal to some `s`, the
singular hypothesis on `s` propagates to the canonical-coefficient identity at
`fuel + 1`. Used by `bareissGramCanonicalCoeff_eq_of_singular` to apply the
succ-singular equation at the singular fixed-point without rewriting through
dependent matrix-access proofs. -/
 theorem _root_.Hex.GramSchmidt.Int.bareissGramCanonicalCoeff_succ_singular_of_state_eq
    {n m : Nat} (b : Matrix Int n m) (fuel : Nat) (i : Fin n)
    {s : Matrix.BareissState Int n}
    (h_state : Matrix.noPivotLoop fuel
        (Matrix.noPivotInitialState (Matrix.gramMatrix b)) = s)
    (hDone : s.step + 1 < n)
    (hp : s.matrix[s.step][s.step] = 0) :
    bareissGramCanonicalCoeff b (fuel + 1) i =
      bareissGramCanonicalCoeff b fuel i := by
  subst h_state
  exact bareissGramCanonicalCoeff_succ_singular b fuel i hDone hp

/-- Canonical row-coefficients are unchanged by extending the no-pivot Bareiss
loop past a singular step. Used to propagate canonicity through the singular
branch of `bareissGramRowInvariant_noPivotLoop_initialAux`. -/
 theorem _root_.Hex.GramSchmidt.Int.bareissGramCanonicalCoeff_eq_of_singular
    {n m : Nat} (b : Matrix Int n m) (elapsed j : Nat) (i : Fin n)
    (hDone :
      (Matrix.noPivotLoop elapsed
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step + 1 < n)
    (hp :
      (Matrix.noPivotLoop elapsed
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).matrix[
          (Matrix.noPivotLoop elapsed
            (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step][
          (Matrix.noPivotLoop elapsed
            (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step] = 0) :
    bareissGramCanonicalCoeff b (elapsed + 1 + j) i =
      bareissGramCanonicalCoeff b elapsed i := by
  induction j with
  | zero =>
      exact bareissGramCanonicalCoeff_succ_singular b elapsed i hDone hp
  | succ j ih =>
      have h_one :
          Matrix.noPivotLoop (elapsed + 1)
            (Matrix.noPivotInitialState (Matrix.gramMatrix b)) =
          { (Matrix.noPivotLoop elapsed
              (Matrix.noPivotInitialState (Matrix.gramMatrix b))) with
            singularStep := some (Matrix.noPivotLoop elapsed
              (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step } := by
        rw [noPivotLoop_add elapsed 1]
        exact Matrix.noPivotLoop_of_singular 0 _ hDone hp
      have h_state_eq :
          Matrix.noPivotLoop (elapsed + 1 + j)
            (Matrix.noPivotInitialState (Matrix.gramMatrix b)) =
          { (Matrix.noPivotLoop elapsed
              (Matrix.noPivotInitialState (Matrix.gramMatrix b))) with
            singularStep := some (Matrix.noPivotLoop elapsed
              (Matrix.noPivotInitialState (Matrix.gramMatrix b))).step } := by
        rw [noPivotLoop_add (elapsed + 1) j, h_one]
        exact noPivotLoop_id_at_singular_fixedpoint j _ hDone hp rfl
      rw [show elapsed + 1 + (j + 1) = (elapsed + 1 + j) + 1 from by omega,
          _root_.Hex.GramSchmidt.Int.bareissGramCanonicalCoeff_succ_singular_of_state_eq
            b (elapsed + 1 + j) i h_state_eq hDone hp]
      exact ih

end GramSchmidt.Int
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

/-!
Bareiss row-invariant proofs for the no-pivot Gram pass in `hex-gram-schmidt`.

This module establishes that the no-pivot Bareiss elimination over a Gram
matrix carries the `BareissGramRowInvariant` row-coefficient invariant and
that its coefficients stay canonical (matching `bareissGramCanonicalCoeff`),
threading the `StepWitness`/`IsCanonicalAt` quotient gate through the
recursion. It proves the supporting fraction-free divisibility and
singular-step facts (exact divisibility of each Bareiss step, propagation of
the first singular step, and that a singular leading Gram prefix forces the
later leading determinants to zero), the integer dot-product degeneracy
lemmas, and the row-combination expansion of inner products. It also supplies
the `scaledCoeffArrayLoop` branch/size lemmas (singular, regular, last-step,
done, and current-column-written) that the correspondence proofs unfold.
-/
namespace Hex
namespace GramSchmidt.Int
/-- Initial no-pivot Gram specialization indexed by elapsed fuel.  The regular
branch no longer asks callers for a row-entry equation; it obtains the
reachable row-entry relation from `bareissGramInitialRegularStep_entry_eq_dot`
using the supplied quotient provenance.

Threads `IsCanonicalAt` through the recursion so that the canonicity gate of
`StepWitness` can be discharged at every regular step. The return type packages
the row invariant together with the proof that its coefficients match
`bareissGramCanonicalCoeff` at the elapsed-plus-fuel index. -/
 def _root_.Hex.GramSchmidt.Int.bareissGramRowInvariant_noPivotLoop_initialAux
    (b : Matrix Int n m) (elapsed fuel : Nat)
    (hinv : BareissGramRowInvariant b
      (Matrix.noPivotLoop elapsed
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))))
    (h_canon : IsCanonicalAt b elapsed hinv)
    (h_prefix_none :
      (Matrix.noPivotLoop elapsed
        (Matrix.noPivotInitialState (Matrix.gramMatrix b))).singularStep = none)
    (hquot : StepWitness b) :
    { hinv' : BareissGramRowInvariant b
        (Matrix.noPivotLoop fuel
          (Matrix.noPivotLoop elapsed
            (Matrix.noPivotInitialState (Matrix.gramMatrix b)))) //
      ∀ i : Fin n,
        hinv'.coeff i = bareissGramCanonicalCoeff b (elapsed + fuel) i } := by
  induction fuel generalizing elapsed with
  | zero =>
      exact ⟨hinv, h_canon⟩
  | succ fuel ih =>
      let state :=
        Matrix.noPivotLoop elapsed
          (Matrix.noPivotInitialState (Matrix.gramMatrix b))
      by_cases hDone : state.step + 1 < n
      · by_cases hp0 : state.matrix[(state.step, state.step)] = 0
        · have hp : state.matrix[state.step][state.step] = 0 := by
            rw [Matrix.getElem_nat_eq_getRow]
            simpa using hp0
          rw [Matrix.noPivotLoop_of_singular fuel state hDone hp]
          refine ⟨{ coeff := hinv.coeff
                    coeff_supp := ?_
                    entry_eq_dot := ?_ }, ?_⟩
          · simpa using hinv.coeff_supp
          · simpa using hinv.entry_eq_dot
          · intro i
            show hinv.coeff i = bareissGramCanonicalCoeff b (elapsed + (fuel + 1)) i
            rw [h_canon i,
                show elapsed + (fuel + 1) = elapsed + 1 + fuel from by omega]
            exact (_root_.Hex.GramSchmidt.Int.bareissGramCanonicalCoeff_eq_of_singular
              b elapsed fuel i hDone hp).symm
        · have hp : state.matrix[state.step][state.step] ≠ 0 := by
            rw [Matrix.getElem_nat_eq_getRow]
            simpa using hp0
          rw [Matrix.noPivotLoop_of_regular fuel state hDone hp]
          have hstep :
              Matrix.noPivotLoop (elapsed + 1)
                  (Matrix.noPivotInitialState (Matrix.gramMatrix b)) =
                ({ step := state.step + 1
                   matrix := Matrix.stepMatrix state.matrix state.step
                     state.matrix[state.step][state.step] state.prevPivot
                   prevPivot := state.matrix[state.step][state.step]
                   rowSwaps := state.rowSwaps
                   singularStep := none } : Matrix.BareissState Int n) := by
            rw [noPivotLoop_add elapsed 1
              (Matrix.noPivotInitialState (Matrix.gramMatrix b))]
            rw [Matrix.noPivotLoop_of_regular 0 state hDone hp]
            simp [Matrix.noPivotLoop_zero_fuel]
          have hentry := fun i j hi =>
            _root_.Hex.GramSchmidt.Int.bareissGramInitialRegularStep_entry_eq_dot
              (b := b) elapsed hinv h_prefix_none hDone hp i j hi
              (hquot elapsed hinv h_canon h_prefix_none hDone hp i hi)
          let hinv_next := bareissGramRowInvariant_regular_step hDone hp hinv hentry
          have h_canon_next_pre :
              ∀ i : Fin n,
                hinv_next.coeff i = bareissGramCanonicalCoeff b (elapsed + 1) i := fun i =>
            bareissGramRowInvariant_regular_step_coeff_canonical
              b elapsed hinv h_canon hDone hp hentry i
          rw [← hstep]
          have h_canon_next :
              IsCanonicalAt b (elapsed + 1) (hstep ▸ hinv_next) := by
            intro i
            show (hstep ▸ hinv_next).coeff i = bareissGramCanonicalCoeff b (elapsed + 1) i
            rw [bareissGramRowInvariant_coeff_transport hstep hinv_next i]
            exact h_canon_next_pre i
          have h_prefix_next :
              (Matrix.noPivotLoop (elapsed + 1)
                (Matrix.noPivotInitialState (Matrix.gramMatrix b))).singularStep = none := by
            rw [hstep]
          let ih_result :=
            ih (elapsed := elapsed + 1) (hstep ▸ hinv_next) h_canon_next h_prefix_next
          refine ⟨ih_result.1, ?_⟩
          intro i
          rw [show elapsed + (fuel + 1) = (elapsed + 1) + fuel from by omega]
          exact ih_result.2 i
      · rw [Matrix.noPivotLoop_done fuel state hDone]
        refine ⟨hinv, ?_⟩
        intro i
        rw [h_canon i]
        exact (_root_.Hex.GramSchmidt.Int.bareissGramCanonicalCoeff_eq_of_done b elapsed (fuel + 1) i hDone).symm

/-- Initial-state specialization of the row invariant for the no-pivot pass
over a Gram matrix.  Callers supply only quotient provenance for reachable
regular branches; the row-entry equation is derived internally. -/
 def _root_.Hex.GramSchmidt.Int.bareissGramRowInvariant_noPivotLoop_initial
    (b : Matrix Int n m) (fuel : Nat)
    (hquot : StepWitness b) :
    BareissGramRowInvariant b
      (Matrix.noPivotLoop fuel (Matrix.noPivotInitialState (Matrix.gramMatrix b))) :=
  (_root_.Hex.GramSchmidt.Int.bareissGramRowInvariant_noPivotLoop_initialAux
    (b := b) 0 fuel (bareissGramRowInvariant_initial b)
    (isCanonicalAt_initial b) rfl hquot).1





























































end GramSchmidt.Int
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: 226f3f6fca7d7b750c2bdd22f5953617942804a57503ad94626e3ae3fe9b43a7.

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