AFTD Auto-Formalizing Theoretical Domains

admissible_plane_transverse_card

theoremverified

Let p be a prime, S an admissible plane set in (ZMod p)^3, and suppose S contains the affine line through P in direction v ≠ 0. Then every affine plane transverse to v (meaning f(v) ≠ 0) meets S in exactly p points: (S ∩ affine_plane f c).ncard = p.

Statement

theorem admissible_plane_transverse_card
    (p : ℕ) [Fact p.Prime] (S : Set (Fin 3 → ZMod p)) (hS : admissible_plane_set p S)
    (P v : Fin 3 → ZMod p) (hv : v ≠ 0) (hline : affine_line P v ⊆ S)
    (f : (Fin 3 → ZMod p) →ₗ[ZMod p] ZMod p) (hf : f v ≠ 0) (c : ZMod p) :
    (S ∩ affine_plane f c).ncard = p
Source
arXiv:2611.12153 Lemma 2.1
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • affine_lineFor a natural number p, the affine line in (ZMod p)^3 through a point P in direction v is the set of points x such that x = P + t • v for…
  • affine_planeFor a natural number p, the affine plane defined by a linear functional f on (ZMod p)^3 and scalar c in ZMod p is the fiber {x | f x = c}.
  • admissible_plane_setLet p be a prime. A subset S of (ZMod p)^3 is an admissible plane set if its cardinality is p^2 and for every nonzero linear functional f…

Read back from the Lean

Let $p$ be a prime number, and let $S$ be a subset of $(\mathbb{Z}/p\mathbb{Z})^3$ that is an "admissible plane set" (that is, $S$ has cardinality $p^2$, and for every nonzero linear functional $g : (\mathbb{Z}/p\mathbb{Z})^3 \to \mathbb{Z}/p\mathbb{Z}$ and scalar $c'$, the cardinality of the intersection of $S$ with the affine plane $\{x \mid g(x) = c'\}$ is divisible by $p$). Let $P, v \in (\mathbb{Z}/p\mathbb{Z})^3$ with $v \neq 0$, such that the affine line $\{P + t v \mid t \in \mathbb{Z}/p\mathbb{Z}\}$ is completely contained in $S$. Let $f : (\mathbb{Z}/p\mathbb{Z})^3 \to \mathbb{Z}/p\mathbb{Z}$ be a linear map with $f(v) \neq 0$, and let $c \in \mathbb{Z}/p\mathbb{Z}$. Then the cardinality (via Set.ncard) of the intersection of $S$ with the affine plane $\{x \mid f(x) = c\}$ is equal to $p$.

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

To show that an affine plane H_c = {x | f(x) = c} transverse to v meets S in exactly p points, we partition S into the p parallel slices S ∩ H_c. Because S contains an affine line in direction v and f(v) ≠ 0, the line intersects each plane H_c, ensuring every slice is nonempty. By the admissibility of S, each slice size is a positive multiple of p and hence at least p. Since the disjoint union of all p slices is S, their sizes sum to |S| = p^2; an elementary averaging lemma then forces every slice to have size exactly p.

  1. If an integer-valued function g on a finite type ι satisfies g(i) ≥ k for all i and sums to k * |ι|, then g(i) = k for every i.

    We expand the sum of non-negative differences ∑_{i ∈ ι} (g(i) - k) as (∑ g(i)) - (∑ k). By assumption, the first sum is k * |ι| and the second is also k * |ι|, so the sum of differences is 0. A finite sum of non-negative integers is 0 if and only if each term is 0, which means g(i) - k = 0 for all i. Hence g(i) ≤ k, which combined with the hypothesis k ≤ g(i) proves g(i) = k by antisymmetry.

    lines 1–14

    uses Finset.sum_tsub_distrib, Finset.sum_const, Finset.card_univ, nsmul_eq_mul, Nat.mul_comm, Finset.sum_eq_zero_iff, Nat.sub_eq_zero_iff_le.mp, le_antisymm

    private lemma admissible_plane_transverse_card_eq_const_of_le_of_sum_eq_card_mul
        {ι : Type*} [Fintype ι]
        {k : ℕ} {g : ι → ℕ} (hle : ∀ i, k ≤ g i)
        (hsum : ∑ i, g i = k * Fintype.card ι) : ∀ i, g i = k := by
      have hzero : ∑ i, (g i - k) = 0 := by
        rw [Finset.sum_tsub_distrib Finset.univ (fun j _ => hle j), hsum, Finset.sum_const,
          Finset.card_univ, nsmul_eq_mul, Nat.mul_comm]
        simp
      intro i
      have hi : g i - k = 0 :=
        (Finset.sum_eq_zero_iff (s := Finset.univ) (f := fun i => g i - k)).mp hzero i (Finset.mem_univ i)
      have : g i ≤ k := Nat.sub_eq_zero_iff_le.mp hi
      exact le_antisymm this (hle i)
    
  2. The admissible set S has total size p^2, its intersection with any nonzero plane has size divisible by p, and the linear functional f is nonzero.

    Unpacking the definition of an admissible plane set gives |S| = p^2 and the divisibility property for every nonzero linear form. Since f(v) ≠ 0 by assumption, f cannot be the zero map.

    lines 15–22

    /-- If an admissible plane set contains an affine line in direction v, then every affine plane transverse to v meets S in exactly p points. -/
    theorem admissible_plane_transverse_card
        (p : ℕ) [Fact p.Prime] (S : Set (Fin 3 → ZMod p)) (hS : admissible_plane_set p S)
        (P v : Fin 3 → ZMod p) (hv : v ≠ 0) (hline : affine_line P v ⊆ S)
        (f : (Fin 3 → ZMod p) →ₗ[ZMod p] ZMod p) (hf : f v ≠ 0) (c : ZMod p) :
        (S ∩ affine_plane f c).ncard = p := by
      obtain ⟨hScard, hSdiv⟩ := hS
      have hf0 : f ≠ 0 := by intro h; apply hf; simp [h]
  3. Every parallel plane transverse to v intersects S non-trivially: S ∩ H_c is nonempty for all c.

    The set S contains the affine line L = {P + t • v | t ∈ ZMod p}. Because f is linear, f(P + t • v) = f(P) + t * f(v). Since f(v) ≠ 0 in the field ZMod p, choosing t = (c - f(P)) / f(v) satisfies f(P + t • v) = c. Thus the line point P + t • v lies in both S and the plane H_c.

    lines 23–30

    uses map_add, map_smul, smul_eq_mul

      have hne : ∀ c, (S ∩ affine_plane f c).Nonempty := by
        intro c
        obtain ⟨t, ht⟩ : ∃ t : ZMod p, f (P + t • v) = c := by
          refine ⟨(c - f P) / f v, ?_⟩
          rw [map_add, map_smul, smul_eq_mul]
          field_simp
          ring
        exact ⟨P + t • v, hline ⟨t, rfl⟩, ht⟩
  4. Each slice S ∩ H_c contains at least p points: p ≤ |S ∩ H_c| for every c.

    By admissibility of S, p divides |S ∩ H_c|. Since the intersection was shown to be nonempty, its cardinality is strictly positive. Any positive integer divisible by p is at least p.

    lines 31–35

    uses Nat.le_of_dvd

      have hle : ∀ c, p ≤ (S ∩ affine_plane f c).ncard := by
        intro c
        have hd : p ∣ (S ∩ affine_plane f c).ncard := hSdiv f hf0 c
        have hpos : 0 < (S ∩ affine_plane f c).ncard := (hne c).ncard_pos
        exact Nat.le_of_dvd hpos hd
  5. The slices S ∩ H_c for distinct values of c are pairwise disjoint.

    The planes H_c are fibers f⁻¹(c) of the function f. If a point x were in both S ∩ H_c and S ∩ H_c', we would have c = f(x) = c', contradicting c ≠ c'.

    lines 36–41

    uses Function.onFun, Set.disjoint_left, Set.mem_inter_iff, Set.mem_ofPred_eq

      have hdisj : Pairwise (Function.onFun Disjoint (fun c => S ∩ affine_plane f c)) := by
        intro c c' hcc'
        rw [Function.onFun, Set.disjoint_left]
        intro x hx hx'
        rw [Set.mem_inter_iff, affine_plane, Set.mem_ofPred_eq] at hx hx'
        exact hcc' (hx.2.symm.trans hx'.2)
  6. The union of the slices S ∩ H_c over all c ∈ ZMod p is the entire set S.

    Each slice is a subset of S, so their union is contained in S. Conversely, any point x ∈ S has some value f(x) ∈ ZMod p, so x belongs to the slice for c = f(x).

    lines 42–47

    uses Set.mem_iUnion, Set.mem_inter_iff, Set.mem_ofPred_eq

      have hunion : (⋃ c, S ∩ affine_plane f c) = S := by
        ext x
        simp only [Set.mem_iUnion, Set.mem_inter_iff, affine_plane, Set.mem_ofPred_eq]
        constructor
        · rintro ⟨c, hx, _⟩; exact hx
        · intro hx; exact ⟨f x, hx, rfl⟩
  7. The sum of the cardinalities of all p slices equals p^2: ∑_c |S ∩ H_c| = p^2.

    Because the slices form a pairwise disjoint finite family of finite sets whose union is S, the cardinality of S equals the sum of the cardinalities of the slices. Since |S| = p^2, the sum is p^2.

    lines 48–52

    uses Set.ncard_iUnion_of_finite, Set.toFinite, finsum_eq_sum_of_fintype

      have hsum : ∑ c : ZMod p, (S ∩ affine_plane f c).ncard = p ^ 2 := by
        have h1 : (⋃ c, S ∩ affine_plane f c).ncard = ∑ᶠ c : ZMod p, (S ∩ affine_plane f c).ncard :=
          Set.ncard_iUnion_of_finite (fun c => Set.toFinite _) hdisj
        rw [hunion, finsum_eq_sum_of_fintype, hScard] at h1
        exact h1.symm
  8. Every transverse slice has size exactly p: |S ∩ H_c| = p for all c, and in particular for the given c.

    We apply the helper lemma to the slice sizes over the index set ZMod p (which has cardinality p) with k = p. Since every slice size is at least p and their sum is p^2 = p * p, every slice size must equal p. Specialising to the given c finishes the proof.

    lines 53–56

    uses admissible_plane_transverse_card_eq_const_of_le_of_sum_eq_card_mul, ZMod.card, pow_two

      have hmain : ∀ c, (S ∩ affine_plane f c).ncard = p := by
        apply admissible_plane_transverse_card_eq_const_of_le_of_sum_eq_card_mul (k := p) hle
        rw [hsum, ZMod.card p, pow_two]
      exact hmain c
admissible_plane_transverse_card_eq_const_of_le_of_sum_eq_card_mul
If an indexed collection of natural numbers satisfies g(i) ≥ k for all i and sums to k * |ι|, then g(i) = k for all i.
Finset.sum_tsub_distrib
For a finite set s and functions f, g with g(x) ≤ f(x) on s, the sum of differences ∑_{x ∈ s} (f(x) - g(x)) equals (∑_{x ∈ s} f(x)) - (∑_{x ∈ s} g(x)).
Finset.sum_const
The sum of a constant value b over a finite set s equals |s| * b.
Finset.card_univ
The cardinality of the universal finset of a finite type α equals the cardinality of the type, |α|.
nsmul_eq_mul
Scalar multiplication of an element by a natural number n equals the product n * a.
Nat.mul_comm
Multiplication of natural numbers is commutative: n * m = m * n.
Finset.sum_eq_zero_iff
A sum of natural numbers over a finite set is zero if and only if each term is zero.
Nat.sub_eq_zero_iff_le.mp
For natural numbers, if a - b = 0, then a ≤ b.
le_antisymm
A partial order is antisymmetric: if a ≤ b and b ≤ a, then a = b.
map_add
A linear map preserves addition: f(x + y) = f(x) + f(y).
map_smul
A linear map preserves scalar multiplication: f(c • x) = c • f(x).
smul_eq_mul
Scalar multiplication of field elements by field elements coincides with field multiplication: a • b = a * b.
Nat.le_of_dvd
If n is a positive natural number and m divides n, then m ≤ n.
Function.onFun
Applies a binary relation to the values of a function on two arguments: (Function.onFun R g) x y = R (g x) (g y).
Set.disjoint_left
Two sets are disjoint if and only if no element in the first set belongs to the second.
Set.mem_inter_iff
An element x belongs to the intersection A ∩ B if and only if x ∈ A and x ∈ B.
Set.mem_ofPred_eq
An element x belongs to the comprehension {y | p y} if and only if p x holds.
Set.mem_iUnion
An element belongs to the indexed union ⋃ i, s i if and only if it belongs to s i for some index i.
Set.ncard_iUnion_of_finite
The cardinality of a disjoint union of finitely many finite sets is the sum of their individual cardinalities.
Set.toFinite
Every subset of a finite type is finite.
finsum_eq_sum_of_fintype
For a function with finite support on a finite type, the conditionally convergent sum coincides with the finite sum.
ZMod.card
The cardinality of the finite field ZMod n is n.
pow_two
The square a ^ 2 equals a * a.

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

private lemma admissible_plane_transverse_card_eq_const_of_le_of_sum_eq_card_mul    {ι : Type*} [Fintype ι]    {k : ℕ} {g : ι → ℕ} (hle : ∀ i, k ≤ g i)    (hsum : ∑ i, g i = k * Fintype.card ι) : ∀ i, g i = k := by  have hzero : ∑ i, (g i - k) = 0 := by    rw [Finset.sum_tsub_distrib Finset.univ (fun j _ => hle j), hsum, Finset.sum_const,      Finset.card_univ, nsmul_eq_mul, Nat.mul_comm]    simp  intro i  have hi : g i - k = 0 :=    (Finset.sum_eq_zero_iff (s := Finset.univ) (f := fun i => g i - k)).mp hzero i (Finset.mem_univ i)  have : g i ≤ k := Nat.sub_eq_zero_iff_le.mp hi  exact le_antisymm this (hle i)/-- If an admissible plane set contains an affine line in direction v, then every affine plane transverse to v meets S in exactly p points. -/theorem admissible_plane_transverse_card    (p : ℕ) [Fact p.Prime] (S : Set (Fin 3 → ZMod p)) (hS : admissible_plane_set p S)    (P v : Fin 3 → ZMod p) (hv : v ≠ 0) (hline : affine_line P v ⊆ S)    (f : (Fin 3 → ZMod p) →ₗ[ZMod p] ZMod p) (hf : f v ≠ 0) (c : ZMod p) :    (S ∩ affine_plane f c).ncard = p := by  obtain ⟨hScard, hSdiv⟩ := hS  have hf0 : f ≠ 0 := by intro h; apply hf; simp [h]  have hne : ∀ c, (S ∩ affine_plane f c).Nonempty := by    intro c    obtain ⟨t, ht⟩ : ∃ t : ZMod p, f (P + t • v) = c := by      refine ⟨(c - f P) / f v, ?_⟩      rw [map_add, map_smul, smul_eq_mul]      field_simp      ring    exact ⟨P + t • v, hline ⟨t, rfl⟩, ht⟩  have hle : ∀ c, p ≤ (S ∩ affine_plane f c).ncard := by    intro c    have hd : p ∣ (S ∩ affine_plane f c).ncard := hSdiv f hf0 c    have hpos : 0 < (S ∩ affine_plane f c).ncard := (hne c).ncard_pos    exact Nat.le_of_dvd hpos hd  have hdisj : Pairwise (Function.onFun Disjoint (fun c => S ∩ affine_plane f c)) := by    intro c c' hcc'    rw [Function.onFun, Set.disjoint_left]    intro x hx hx'    rw [Set.mem_inter_iff, affine_plane, Set.mem_ofPred_eq] at hx hx'    exact hcc' (hx.2.symm.trans hx'.2)  have hunion : (⋃ c, S ∩ affine_plane f c) = S := by    ext x    simp only [Set.mem_iUnion, Set.mem_inter_iff, affine_plane, Set.mem_ofPred_eq]    constructor    · rintro ⟨c, hx, _⟩; exact hx    · intro hx; exact ⟨f x, hx, rfl⟩  have hsum : ∑ c : ZMod p, (S ∩ affine_plane f c).ncard = p ^ 2 := by    have h1 : (⋃ c, S ∩ affine_plane f c).ncard = ∑ᶠ c : ZMod p, (S ∩ affine_plane f c).ncard :=      Set.ncard_iUnion_of_finite (fun c => Set.toFinite _) hdisj    rw [hunion, finsum_eq_sum_of_fintype, hScard] at h1    exact h1.symm  have hmain : ∀ c, (S ∩ affine_plane f c).ncard = p := by    apply admissible_plane_transverse_card_eq_const_of_le_of_sum_eq_card_mul (k := p) hle    rw [hsum, ZMod.card p, pow_two]  exact hmain c
See it in the graphDiscuss this resultChallenge it