Theorem 1.1 — Exact counting of large cliques
ProvedVWZClique.count_large_cliquesFor every sufficiently large fixed clique size, exact clique counting on adjacency-matrix inputs admits a word-RAM algorithm with running time for an absolute .
import Definitions.Def_VWZClique_Count import Definitions.Def_OAI_MatrixMultiplication_Arithmetic_omega
theorem VWZClique.count_large_cliques :
∃ δ : ℝ, 0 < δ ∧ ∃ K₀ : ℕ, ∀ k ≥ K₀,
VWZClique.countsWithin k
((OAI.MatrixMultiplication.Arithmetic.omega ℂ - δ) * (k : ℝ) / 3) := by sorryRead-back
What the Lean code literally says, in plain math · OpenAI Codex (GPT-6), independent blind auditor
There exist a positive real number and a natural number such that for every natural number there are a finite word-RAM program , a positive natural number , and a positive real number , all allowed to depend on , with the following property. For every natural number and every simple undirected graph on , there is a natural number such that accepts within instructions, including the accepting instruction, and the signed word in cell upon acceptance equals the number of -element vertex subsets whose distinct members are pairwise adjacent. This includes output zero when , and output one for if . The program starts at instruction with word width exactly . Initially cell holds , the next cells hold the zero-one adjacency matrix in row-major order, and all other integer-addressed cells hold zero, with values reduced to the word width. The instructions allow writing one, word addition, subtraction and multiplication modulo two to the word width, indirect loads and stores with signed addresses, branching on a negative signed word, acceptance and rejection. Falling past the program rejects. Other final cells are unrestricted. Here is the real infimum of the real numbers such that for every real there exists a real for which every integer size admits a straight-line program computing the product of every pair of complex matrices with arithmetic cost at most . Each gate stores an arbitrary complex constant or an input entry at zero cost, or adds, subtracts or multiplies two preceding gate values at cost one. A designated final register supplies each product entry. The arithmetic program may vary with the size and the slack.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.