AFTD Auto-Formalizing Theoretical Domains

op_462_min_gale_counterexample_card_three_lt_101

theoremverifiedformalization

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

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.

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

    lines 5–8

    uses op462_lt101_of_integer_witness, op462_coords65_diameter_squared_le, op462_coords65_edges_squared_ge, op462_no_four_coloring65

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

    lines 9–10

    uses Real.sq_sqrt

      unfold gale_sigma_three
      rw [Real.sq_sqrt (by positivity)]
  3. 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.

    line 11

      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.

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

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