op_462_min_gale_counterexample_card_three_lt_101
Open Problem OP-462: the minimum cardinality min_gale_counterexample_card_three of a finite counterexample to Gale's conjecture in dimension 3 is strictly less than 101.
Statement
theorem op_462_min_gale_counterexample_card_three_lt_101 : min_gale_counterexample_card_three < 101- Formalizes
- Known consequence of the 65-point configuration in https://github.com/vsvor/Gale-conjecture/tree/bd6dc9594c589791f599a0bf4685841bcb5b4486/best_known/3d_65p_088808 accompanying arXiv:2610.28828. Exact-integer geometry and independent non-4-colorability were checked in experiment 4045. This is an upper-bound partial result for Question 2, not the exact minimum.
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- min_gale_counterexample_card_threeThe minimum cardinality
min_gale_counterexample_card_threeof a finite counterexample to Gale's conjecture in dimension 3 is the infimum… - op462_lt101_of_integer_witnessAn integer coordinate certificate on fewer than 101 indexed points, with unit diameter bound, a strict threshold gap and a…
- op462_edges65The 859 witness edges on the 65 indexed points in the primary repository.
- op462_coords65The exact integer coordinates of the 65 indexed points, obtained by multiplying the primary decimal coordinates by 10^17.
- op462_no_four_coloring65No map from the 65 points to four colors separates every witness edge.
- op462_coords65_diameter_squared_leEvery squared distance between the scaled integer points is at most 10^34.
- op462_coords65_edges_squared_geEvery witness edge has scaled squared distance at least 7887420401648046950672144846523981.
- gale_sigma_threeThe real constant
gale_sigma_threeis defined as the square root of (3 + sqrt(3)) / 6.
- min_gale_counterexample_card_threeThe minimum cardinality
Read back from the Lean
The infimum in $\mathbb{N}$ of the set of natural numbers $m$ such that there exists a finite subset $V \subset \mathbb{R}^3$ (with the Euclidean metric) of cardinality $m$ satisfying: 1. $V$ has strictly positive diameter, and 2. the simple graph on vertex set $V$, where two distinct vertices are adjacent if and only if their Euclidean distance strictly exceeds $\sqrt{\frac{3 + \sqrt{3}}{6}} \cdot \operatorname{diam}(V)$, is not 4-colorable, is strictly less than 101.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof establishes that the minimum size of a 3-dimensional counterexample to Gale's conjecture is strictly less than 101 by constructing an explicit 65-vertex counterexample. Using `op462_lt101_of_integer_witness`, the claim reduces to verifying geometric bounds and non-4-colorability on an integer point configuration with 65 vertices, along with an algebraic threshold inequality. The finite graph properties are verified by precomputed certificates, and the remaining inequality comparing the Gale threshold to the configuration's edge length is solved numerically.
The theorem reduces to verifying that gale_sigma_three² < 7887420401648046950672144846523981 / (10¹⁷)².
Apply the reduction theorem `op462_lt101_of_integer_witness` with vertex count n = 65, scale factor S = 10¹⁷, squared distance threshold Q = 7887420401648046950672144846523981, vertex coordinates `op462_coords65`, and edge list `op462_edges65`. The hypotheses 65 < 101, 0 < 10¹⁷, and (0, 1) ∈ op462_edges65 are settled by direct decision procedures (`decide` and `norm_num`). The diameter bound is supplied by `op462_coords65_diameter_squared_le`, the edge distance lower bound by `op462_coords65_edges_squared_ge`, and non-4-colorability by `op462_no_four_coloring65`. Only the separation gap condition remains.
uses
op462_lt101_of_integer_witness,op462_coords65_diameter_squared_le,op462_coords65_edges_squared_ge,op462_no_four_coloring65apply op462_lt101_of_integer_witness 65 (by decide) (10^17) 7887420401648046950672144846523981 (by norm_num) op462_coords65 op462_edges65 op462_coords65_diameter_squared_le op462_coords65_edges_squared_ge ?_ op462_no_four_coloring65 0 1 (by decide)
The goal simplifies to (3 + √3) / 6 < 7887420401648046950672144846523981 / (10¹⁷)².
Unfold the definition of `gale_sigma_three`, which is √((3 + √3) / 6). Then rewrite using `Real.sq_sqrt` to simplify the square of the square root, where non-negativity of (3 + √3) / 6 is checked by the `positivity` tactic.
uses
Real.sq_sqrtunfold gale_sigma_three rw [Real.sq_sqrt (by positivity)]
The numerical inequality holds, completing the proof. automation
The automated tactic `num_ineq` proves the strict numerical inequality between the algebraic number (3 + √3) / 6 ≈ 0.788675 and the rational fraction Q / S² ≈ 0.788742.
num_ineq
op462_lt101_of_integer_witness- If an integer point set of size n < 101 scaled by S > 0 with edge threshold Q has diameter squared at most S², all graph edges have squared length at least Q, the graph has no proper 4-coloring, and gale_sigma_three² < Q / S², then the minimum counterexample cardinality is strictly less than 101.
op462_coords65_diameter_squared_le- The pairwise squared Euclidean distance between any two of the 65 points in op462_coords65 is at most (10¹⁷)².
op462_coords65_edges_squared_ge- Every edge in op462_edges65 connects two points whose squared Euclidean distance is at least 7887420401648046950672144846523981.
op462_no_four_coloring65- The graph with vertex set Fin 65 and edge list op462_edges65 cannot be properly colored with 4 colors.
Real.sq_sqrt- For any real number x ≥ 0, the square of the square root of x equals x.
- The final inequality is closed by the `num_ineq` tactic, an automated procedure for numerical inequalities over real algebraic numbers.
- The geometric and chromatic certificates (`op462_coords65_diameter_squared_le`, `op462_coords65_edges_squared_ge`, and `op462_no_four_coloring65`) encapsulate large finite checks, including non-existence of a 4-coloring on 65 vertices, proven in earlier lemmas.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open scoped BigOperators/-- Open problem OP-462: the minimum cardinality of a counterexample to Gale's conjecture in dimension 3 is strictly less than 101. -/theorem op_462_min_gale_counterexample_card_three_lt_101 : min_gale_counterexample_card_three < 101 := by apply op462_lt101_of_integer_witness 65 (by decide) (10^17) 7887420401648046950672144846523981 (by norm_num) op462_coords65 op462_edges65 op462_coords65_diameter_squared_le op462_coords65_edges_squared_ge ?_ op462_no_four_coloring65 0 1 (by decide) unfold gale_sigma_three rw [Real.sq_sqrt (by positivity)] num_ineq