AFTD Auto-Formalizing Theoretical Domains

op_462_gale_counterexample_card_three_le_101

theoremverifiedformalization

There exists a finite subset V of EuclideanSpace ℝ (Fin 3) with cardinality 101 that is a counterexample to Gale's conjecture in dimension 3 (is_gale_counterexample_three V).

Statement

theorem op_462_gale_counterexample_card_three_le_101 : ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card = 101 ∧ is_gale_counterexample_three V
Formalizes
arXiv:2610.28828, Theorem 2
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
  • is_gale_counterexample_threeA finite subset V of the 3-dimensional Euclidean space EuclideanSpace ℝ (Fin 3) is a counterexample to Gale's conjecture in dimension 3…
  • op462_counterexample_of_integer_witnessAn exact integer coordinate certificate and a non-four-colorable witness graph produce a finite counterexample with cardinality at most…
  • op462_counterexample_extend_cardA finite three-dimensional counterexample can be enlarged to any prescribed larger finite cardinality by adding points inside its convex…
  • op462_coords65The exact integer coordinates of the 65 indexed points, obtained by multiplying the primary decimal coordinates by 10^17.
  • op462_edges65The 859 witness edges on the 65 indexed points in the primary repository.
  • 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_three is defined as the square root of (3 + sqrt(3)) / 6.
Used by 1

Read back from the Lean

There exists a finite subset $V$ of $\mathbb{R}^3$ (specifically EuclideanSpace ℝ (Fin 3)) such that: 1. The cardinality of $V$ is exactly 101. 2. The metric diameter of $V$ is strictly positive. 3. The simple graph on $V$, where two distinct vertices $u, v \in V$ are adjacent if and only if their Euclidean distance strictly exceeds $\sqrt{\frac{3 + \sqrt{3}}{6}} \operatorname{diam}(V)$, is not 4-colorable (i.e., its chromatic number is at least 5).

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 constructs a 101-point counterexample to Gale's conjecture in dimension 3 in two stages. First, using a verified 65-point integer witness configuration, it proves a numerical gap showing that an edge threshold Q / S² strictly exceeds the critical constant σ₃² = (3 + √3)/6. Because the configuration has diameter at most S, all listed edges have distance exceeding σ₃ · diam(V), and the resulting graph cannot be 4-colored, the scaled points form a 3D Gale counterexample of size at most 65. Finally, a general extension theorem enlarges this counterexample to one of cardinality exactly 101.

  1. The squared Gale threshold σ₃² is strictly less than the rational fraction Q / S², where S = 10¹⁷ and Q = 7887420401648046950672144846523981. automation

    Unfolding the definition σ₃ = √((3 + √3) / 6), squaring cancels the outer square root via Real.sq_sqrt (with non-negativity proved by positivity), reducing the goal to (3 + √3) / 6 < Q / S². This inequality on real numbers is then closed by numerical interval evaluation (num_ineq).

    lines 3–7

    uses Real.sq_sqrt

      have hgap : gale_sigma_three^2 <
          ((7887420401648046950672144846523981 : ℤ) : ℝ) / ((10^17 : ℤ) : ℝ)^2 := by
        unfold gale_sigma_three
        rw [Real.sq_sqrt (by positivity)]
        num_ineq
  2. There exists a finite subset V of ℝ³ with |V| ≤ 65 that is a counterexample to Gale's conjecture in dimension 3.

    Apply op462_counterexample_of_integer_witness with n = 65, scale S = 10¹⁷, and threshold Q = 7887420401648046950672144846523981. The scaling factor is positive (norm_num). The 65-point configuration op462_coords65 has diameter squared bounded by S² (op462_coords65_diameter_squared_le), and all edges in op462_edges65 have squared distance at least Q (op462_coords65_edges_squared_ge). Combining this with the threshold inequality hgap, the non-colorability of the edge graph (op462_no_four_coloring65), and the witness edge (0, 1) (checked by decide), the scaled configuration yields a Gale counterexample V of size at most 65.

    lines 8–11

    uses op462_counterexample_of_integer_witness, op462_coords65_diameter_squared_le, op462_coords65_edges_squared_ge, op462_no_four_coloring65

      obtain ⟨V, hcard, hV⟩ := op462_counterexample_of_integer_witness 65 (10^17)
        7887420401648046950672144846523981 (by norm_num)
        op462_coords65 op462_edges65 op462_coords65_diameter_squared_le
        op462_coords65_edges_squared_ge hgap op462_no_four_coloring65 0 1 (by decide)
  3. There exists a counterexample of cardinality exactly 101.

    Extend the counterexample V to exact cardinality 101 using op462_counterexample_extend_card. The required cardinality inequality |V| ≤ 101 follows from |V| ≤ 65 by linear arithmetic (omega).

    line 12

    uses op462_counterexample_extend_card

      exact op462_counterexample_extend_card V hV 101 (by omega)
Real.sq_sqrt
for any non-negative real number x, the square of its square root is x
op462_counterexample_of_integer_witness
an n-point integer configuration with diameter squared at most S², all edge squared distances at least Q > σ₃² S², a non-4-colorable edge graph, and at least one edge yields a 3D Gale counterexample of cardinality at most n
op462_coords65_diameter_squared_le
the squared distance between any two points in the 65-point integer configuration is at most (10¹⁷)²
op462_coords65_edges_squared_ge
every edge in the 65-point edge list connects vertices whose squared distance is at least 7887420401648046950672144846523981
op462_no_four_coloring65
the graph on 65 vertices with the specified edge list admits no proper 4-coloring
op462_counterexample_extend_card
any 3D Gale counterexample V can be extended to a 3D Gale counterexample of any cardinality n ≥ |V|

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

/-- Theorem 2 of arXiv:2610.28828: there exists a 101-point counterexample to Gale's conjecture in dimension 3. -/theorem op_462_gale_counterexample_card_three_le_101 : ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card = 101 ∧ is_gale_counterexample_three V := by  have hgap : gale_sigma_three^2 <      ((7887420401648046950672144846523981 : ℤ) : ℝ) / ((10^17 : ℤ) : ℝ)^2 := by    unfold gale_sigma_three    rw [Real.sq_sqrt (by positivity)]    num_ineq  obtain ⟨V, hcard, hV⟩ := op462_counterexample_of_integer_witness 65 (10^17)    7887420401648046950672144846523981 (by norm_num)    op462_coords65 op462_edges65 op462_coords65_diameter_squared_le    op462_coords65_edges_squared_ge hgap op462_no_four_coloring65 0 1 (by decide)  exact op462_counterexample_extend_card V hV 101 (by omega)
See it in the graphDiscuss this resultChallenge it