AFTD Auto-Formalizing Theoretical Domains

threshold_graph_four_not_colorable_101

theoremverified

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
Used by 1

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.

  1. 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`).

    lines 7–10

    uses threshold_graph_not_four_colorable_of_integer_witness, threshold101_coords_injective, threshold101_diameter_squared_le, threshold101_edges_squared_ge, threshold101_no_four_coloring

      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)
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`.

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

/-- 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)
See it in the graphDiscuss this resultChallenge it