Checked integer Gram-Schmidt data and fraction-free invariants
DefinitionLARLLL_IntegerGramSchmidtlinear-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.