What was already known
Ahn, Medarametla and Potechin gave nearly tight separator-based polynomial bounds with polylogarithmic slack.
AI involvement
Diar Heidary directed the project. Codex agents developed the arguments and Lean proof, and a Claude critique corrected an earlier conjecture. No independent human proof check or explanation of the full classification mechanism is documented.
The source explicitly credits agents with developing the mathematical arguments, beyond proof transcription, under Heidary’s direction.
Importance
Identifies the polynomial and logarithmic norm exponents in a fixed dense-sign graph-matrix model.
Limitations
The result does not cover growing graph shapes, growing p or leading constants. A later Xu–Fu–Qiao–Tao paper appears to overlap; exact theorem correspondence and priority remain unresolved.
Technical verification
The source reports a successful local Lean build and complete endpoint axiom audit for the three selected declarations. Comparator/NanoDa had not completed in this snapshot; Formal rests on the Lean check of the exact conditional-free theorem, not on an independent replay.
Formal checking
Lean 4/Mathlib build and all-theorem axiom audit
- Checker
- Lean 4 kernel
- Scope
- GraphMatrices.Classification.full_dense_sign_classification and its two selected consequences
- Basis
- Reported by the linked checker
Checking a formal statement does not establish that it matches the original problem.
Human understanding
No named human explanation of the separator/floating-component proof mechanism is documented; agent reviews are not human understanding evidence.
Correction and publication history
Identifies the polynomial and logarithmic norm exponents in a fixed dense-sign graph-matrix model.
Read this published revision