Weighted nine-position sum and arithmetic-program cost
DefinitionVWZClique_WeightedA field-valued product of unary and edge tables is summed over all assignments of nine positions. A costed program must give the correct output on every table.
import Mathlib
import Definitions.Def_OAI_MatrixMultiplication_Arithmetic_omega
namespace VWZClique
open OAI.MatrixMultiplication.Arithmetic
abbrev V := Fin 9
abbrev WeightKey (n : ℕ) :=
(V × Fin n) ⊕ (V × V × Fin n × Fin n)
open Classical in
noncomputable def weightedSum {F : Type*} [Field F] {n : ℕ}
(H : SimpleGraph V) (w : WeightKey n → F) : F :=
∑ a : V → Fin n,
(∏ i : V, w (.inl (i, a i))) *
∏ i : V, ∏ j : V,
if i < j ∧ H.Adj i j then w (.inr (i, j, a i, a j)) else 1
def computesWithin {F I : Type*} [Field F] (f : (I → F) → F) (B : ℝ) : Prop :=
∃ (r : ℕ) (P : Program F I r) (o : Fin r),
(P.cost : ℝ) ≤ B ∧ ∀ w, P.eval w o = f w
def wedge (H : SimpleGraph V) (f : Fin 3 → V) : Prop :=
Function.Injective f ∧ H.Adj (f 0) (f 1) ∧ H.Adj (f 1) (f 2)
end VWZClique
Read-back
What the Lean code literally says, in plain math · OpenAI Codex (GPT-6), independent blind auditor
Vertex set. denotes the nine indices , with their usual order.
Weight keys. For each natural number , write , with , and let . A weight key is either a vertex key with and , or a separately tagged pair key with and . The pair is ordered, and repetitions of either indices or values are allowed. At there are no keys of either kind.
Weighted sum. For any field , natural number , simple graph on and assignment of field elements to all vertex keys and all ordered pair keys , let and denote its values on the two respective kinds of keys, where and . The defined element of is . All maps occur, including maps with repeated values. Every ordered pair failing either the order test or the adjacency test contributes the factor . At the sum is empty and has value .
Computes within a bound. For any field , any input index type (possibly empty or infinite), any function , and any real , the predicate holds precisely when there are a natural number , a straight-line program of gates over with inputs indexed by , and a chosen output register among its registers, such that the program costs at most and this register equals for every assignment . Each gate loads an arbitrary field constant or an indexed input for free, or adds, subtracts, or multiplies two earlier register values at cost one. Total cost is the number of these arithmetic gates. Choosing an output requires , even when the cost is zero. A negative cannot satisfy the predicate.
Wedge. For a simple graph on and any map , the predicate holds precisely when are pairwise distinct, is adjacent to , and is adjacent to . The endpoints and may also be adjacent.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.