threshold_graph_four_not_colorable_101
There exists a finite subset V of 3-dimensional Euclidean space with cardinality 101 and strictly positive diameter such that the distance threshold graph on V at threshold 0.88928 times the diameter of V admits no proper 4-coloring.
Statement
theorem threshold_graph_four_not_colorable_101 :
∃ V : Finset (EuclideanSpace ℝ (Fin 3)),
V.card = 101 ∧
0 < Metric.diam (V : Set (EuclideanSpace ℝ (Fin 3))) ∧
¬ (gale_distance_graph V ((88928 / 100000 : ℝ) * Metric.diam (V : Set (EuclideanSpace ℝ (Fin 3))))).Colorable 4- Source
- arXiv:2610.28828 -- A counterexample to Gale's conjecture in $\mathbb{R}^3$, Theorem 2
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- gale_distance_graphFor a finite subset V of the 3-dimensional Euclidean space
EuclideanSpace ℝ (Fin 3)and a real number t,gale_distance_graph V tis… - threshold101_coordsThe 101 exact integer coordinate triples, obtained by scaling the primary decimal coordinates by 10^17.
- threshold101_edgesThe 908 witness edges used by the trimmed LRAT refutation, selected from the primary 2030-edge graph.
- threshold101_coords_injectiveThe 101 integer coordinate triples are pairwise distinct.
- threshold101_diameter_squared_leEvery squared distance between integer triples is at most 100000000000000100 squared.
- threshold101_edges_squared_geEvery trimmed witness edge has integer squared length at least 7908209857886758229068357146803906.
- threshold101_no_four_coloringNo assignment of four colors to the 101 vertices separates every trimmed witness edge.
- threshold_graph_not_four_colorable_of_integer_witnessDistinct integer coordinate triples with pairwise squared distances at most S squared, witness-edge squared distances at least Q, a…
- gale_distance_graphFor a finite subset V of the 3-dimensional Euclidean space
- Used by 1
- counterexample_partition_diameter_ratio_three_101There exists a finite subset V of 3-dimensional Euclidean space of cardinality 101 and strictly positive diameter such that for every…
Read back from the Lean
There exists a finite subset $V$ of 3-dimensional Euclidean space $\mathbb{R}^3$ (EuclideanSpace ℝ (Fin 3)) such that:
1. The cardinality of $V$ is 101;
2. The diameter of $V$ (as a metric subspace of $\mathbb{R}^3$) is strictly positive;
3. The graph with vertex set $V$, where two distinct vertices $u, v \in V$ are adjacent if and only if the Euclidean distance between them is strictly greater than $\frac{88928}{100000} \cdot \operatorname{diam}(V)$ (i.e., $0.88928 \operatorname{diam}(V)$), is not 4-colorable (that is, it has no proper vertex coloring with 4 colors).
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 theorem is proved by exhibiting an explicit 101-point configuration in 3-dimensional Euclidean space, given by integer coordinates, together with a list of witness edges. The proof instantiates the general reduction theorem `threshold_graph_not_four_colorable_of_integer_witness`, which reduces the geometric claim to finite algebraic bounds and combinatorial non-colorability. Pairwise squared distances among the 101 points are bounded above by S² for S = 10¹⁷ + 100, while every edge in the witness list has squared distance at least Q = 7908209857886758229068357146803906. Since (0.88928)² < Q / S², every witness edge has length strictly greater than 0.88928 times the diameter, embedding the non-4-colorable graph into the Gale distance graph.
There exists a 101-point subset V of 3-dimensional Euclidean space with strictly positive diameter whose Gale distance graph at threshold 0.88928 times the diameter is not 4-colorable.
We apply the general witness theorem `threshold_graph_not_four_colorable_of_integer_witness` with n = 101, scaling bound S = 100000000000000100, threshold Q = 7908209857886758229068357146803906, threshold ratio α = 88928 / 100000, integer coordinate mapping `threshold101_coords`, and witness edge list `threshold101_edges`. The hypotheses are discharged as follows: the positivity conditions 0 < S and 0 < α are verified by direct numerical evaluation (`norm_num`); injectivity of the coordinates holds by `threshold101_coords_injective`, ensuring |V| = 101; the diameter upper bound holds by `threshold101_diameter_squared_le`; the edge lower bound holds by `threshold101_edges_squared_ge`; the gap condition α² < Q / S² is verified by rational arithmetic (`norm_num`); non-colorability of the underlying graph is provided by `threshold101_no_four_coloring`; and the existence of at least one edge (to guarantee positive diameter) is witnessed by (0, 1), verified to be in the edge list by finite list evaluation (`decide`).
uses
threshold_graph_not_four_colorable_of_integer_witness,threshold101_coords_injective,threshold101_diameter_squared_le,threshold101_edges_squared_ge,threshold101_no_four_coloringexact threshold_graph_not_four_colorable_of_integer_witness 101 100000000000000100 7908209857886758229068357146803906 (by norm_num) (88928 / 100000) (by norm_num) threshold101_coords threshold101_edges threshold101_coords_injective threshold101_diameter_squared_le threshold101_edges_squared_ge (by norm_num) threshold101_no_four_coloring 0 1 (by decide)
threshold_graph_not_four_colorable_of_integer_witness- If an injective integer configuration of n points in 3D has all pairwise squared distances bounded by S², an edge list E with all pairwise squared distances at least Q, a ratio α > 0 satisfying α² < Q / S², no proper 4-coloring of E, and at least one edge in E, then there exists an n-point subset of ℝ³ with positive diameter whose Gale distance graph at threshold α times diameter is not 4-colorable.
threshold101_coords_injective- The coordinate assignment `threshold101_coords` assigning an integer 3D vector to each index in `Fin 101` is injective.
threshold101_diameter_squared_le- For every pair of indices in `Fin 101`, the squared Euclidean distance between their integer coordinate vectors is at most S² = (100000000000000100)².
threshold101_edges_squared_ge- For every edge in `threshold101_edges`, the squared Euclidean distance between its endpoints is at least Q = 7908209857886758229068357146803906.
threshold101_no_four_coloring- No 4-coloring of `Fin 101` assigns different colors to the endpoints of every edge in `threshold101_edges`.
- The proof relies on precomputed certificates: integer coordinates for 101 points in 3D, a list of edges, and separate verification lemmas establishing diameter bounds, edge length bounds, injectivity, and non-4-colorability. The proof script itself simply applies the general reduction theorem `threshold_graph_not_four_colorable_of_integer_witness` with these data and dispatches the remaining numerical and list-membership checks using standard automation.
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.
/-- There exists a 101-point subset in 3D Euclidean space with positive diameter whose distance threshold graph at threshold 0.88928 times diameter is not 4-colorable. -/theorem threshold_graph_four_not_colorable_101 : ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card = 101 ∧ 0 < Metric.diam (V : Set (EuclideanSpace ℝ (Fin 3))) ∧ ¬ (gale_distance_graph V ((88928 / 100000 : ℝ) * Metric.diam (V : Set (EuclideanSpace ℝ (Fin 3))))).Colorable 4 := by exact threshold_graph_not_four_colorable_of_integer_witness 101 100000000000000100 7908209857886758229068357146803906 (by norm_num) (88928 / 100000) (by norm_num) threshold101_coords threshold101_edges threshold101_coords_injective threshold101_diameter_squared_le threshold101_edges_squared_ge (by norm_num) threshold101_no_four_coloring 0 1 (by decide)