“> David Renshaw recently gave a formal proof in Lean that the triakis tetrahedron does have Rupert's property That's me! This result appears to be significantly harder to formalize. Steininger and Yurkevich's proof certificate is a 2.5GB tree that partitions the state space into 18 million cells and takes 30 hours to validate in SageMath. Formalizing …”
Formal Verification of the Empty Hexagon Number
A recent breakthrough in computer-assisted mathematics showed that every set of $30$ points in the plane in general position (i.e., without three on a common line) contains an empty convex hexagon, thus closing a line of research dating back to the 1930s. Through a combination of geometric insights and automated reasoning techniques, Heule and Scheucher constructed a CNF formula $φ_n$, with $O(n^4)$ clauses, whose unsatisfiability implies that no set of $n$ points in general position can avoid an empty convex hexagon. An unsatisfiability proof for n = 30 was then found with a SAT solver using 17300 CPU hours of parallel computation, thus implying that the empty hexagon number h(6) is equal to 30. In this paper, we formalize and verify this result in the Lean theorem prover. Our formalization covers discrete computational geometry ideas and SAT encoding techniques that have been successfully applied to similar Erdős-Szekeres-type problems. In particular, our framework provides tools to connect standard mathematical objects to propositional assignments, which represents a key step towards the formal verification of other SAT-based mathematical results. Overall, we hope that this work sets a new standard for verification when extensive computation is used for discrete geometry problems, and that it increases the trust the mathematical community has in computer-assisted proofs in this area.
候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“Hi! One of the authors here. Whether checking the LLM-generated Lean statements/definitions is easy or not depends heavily on the area of mathematics and the concrete definitions at play. In this case it was remarkably easy. As you can see in the repository, the definition of a countermodel is easy to parse, and the statement corresponding to their nonexi…”