GT predecessor and one-based matrix indexing
ProvedQAlgorithms.Papers.Independent.Renew46.P15.gtPattern_predecessor_indexFix and a normalized dominant integral top row . Let be all integral GT-patterns with this top row, with unnormalized lower rows satisfying betweenness. Its cardinality is . Order positions from the top row to the bottom row and from left to right inside each row; use this position order for lexicographic comparison of patterns. Define
The partial predecessor is absent at the minimal pattern. Otherwise find the last lower-row entry , decrease it by one, retain all earlier entries and the top row, and reset every later entry to its new upper neighbor . This yields the immediate preceding valid pattern. Moreover is nonempty, is injective, its image is exactly , and it preserves and reflects strict order. The endpoint patterns satisfy
There are exactly successful predecessor steps before the predecessor is absent. This supplies matrix indices with the mathematical one-based convention, including the one-pattern trivial irrep.
import Definitions.Def_QAlgorithms_Papers_Independent_Renew46_P15
noncomputable section
open scoped BigOperators Matrix
namespace QAlgorithms.Papers.Independent.Renew46.P15
attribute [local instance] Classical.propDecidable
/-- Appendix C.2, (C7)-(C9), PDF pp.17-18: predecessor validity, immediate
precedence, inclusive one-based enumeration and the extreme patterns. Q is one
plus the number of successful predecessor steps, correcting the omitted initial
pattern in the prose according to (C7), Table V and the endpoint sentence. -/
theorem gtPattern_predecessor_index {n : ℕ} (s : GTTopRow n) :
0 < Fintype.card (Pattern s) ∧
Function.Injective (patternRank (s := s)) ∧
(∀ q : ℕ, (∃ m : Pattern s, patternRank m = q) ↔
1 ≤ q ∧ q ≤ Fintype.card (Pattern s)) ∧
(∀ a b : Pattern s, patternLt a b ↔ patternRank a < patternRank b) ∧
(∀ m : Pattern s,
(patternRank m = 1 ↔ ∀ (l k : Fin (n + 2)) (hkl : k ≤ l),
patternGrid m l k = s.val ⟨k.val + (n + 1 - l.val), by
have hl := l.isLt
have hklNat : k.val ≤ l.val := hkl
omega⟩) ∧
(patternRank m = Fintype.card (Pattern s) ↔
∀ l k : Fin (n + 2), k ≤ l → patternGrid m l k = s.val k) ∧
(match patternPredecessor m with
| none => patternRank m = 1
| some raw => ∃ p : Pattern s, patternGrid p = raw ∧
patternRank m = patternRank p + 1 ∧
∀ q : Pattern s, patternLt q m → q = p ∨ patternLt q p) ∧
HasPredecessorChain (patternRank m - 1) m ∧
∀ steps, HasPredecessorChain steps m → steps + 1 = patternRank m) := by sorry
end QAlgorithms.Papers.Independent.Renew46.P15
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be any natural number, including zero, and let be any nonincreasing sequence of natural numbers with . Let be the finite set of arrays with natural entries at most , top row , entries for , and inequalities for and . Extend array entries by zero outside the index range. Order the triangular positions , , by decreasing and, within each row, increasing . Write if there exists a triangular position at which has a smaller entry than , while their entries agree at every earlier triangular position in this order, and set . Define a possibly absent raw predecessor as follows. Search the triangular positions in the reverse order, namely increasing row index and decreasing column index within each row, for the first position satisfying and . If there is no such position, is absent. Otherwise, for all natural , define , and, putting , define
where is subtraction truncated at zero; is then present with raw array for . Define the property recursively: means that is absent, and means that there exists such that is present with raw array exactly , and holds. Then, writing , one has ; is injective; for every natural , there exists with if and only if ; and, for every , if and only if . Moreover, for every , if and only if for every triangular position , and if and only if for every triangular position. If is absent, then ; if is present with raw array , then there exists whose array equals , such that and every with satisfies or . Finally, holds, and for every natural number , implies .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.