AFTD Auto-Formalizing Theoretical Domains

good_slopes_many_row_fiber_rigidity_conditional

theoremverified

Let K be a finite field with r nonzero elements and let k be nonzero. Let X have |K|·k elements and input coordinates in K×Z/kZ that form an injective pair. Suppose there are L units modulo k, d is positive and r·d<L. Assume that every k-point set with a bad unit direction has at most L−d good unit directions, and that a set with a bad direction and a K-coloring that makes the input coordinate and all unit direction forms injective within colors has at most L−r·d good unit directions. If the total number of good unit directions across all nonzero K-coordinate rows is greater than rL−rd, then every row is full.

Statement

theorem good_slopes_many_row_fiber_rigidity_conditional (K : Type*) [Field K] [Fintype K] [DecidableEq K] (k L r d : ℕ) [NeZero k] {X : Type*} [Fintype X] [DecidableEq X] [Nonempty X] (xK yK : X → K) (xk yk : X → ZMod k) (hcard : Fintype.card X = Fintype.card K * k) (hx : Function.Injective (fun x => (xK x, xk x))) (hL : ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b).card = L) (hR : ((Finset.univ : Finset K).filter fun a => IsUnit a).card = r) (hr : 0 < r) (hd : 0 < d) (hLd : r*d < L) (hgap : ∀ S : Finset (ZMod k × ZMod k), S.card = k → (∃ b : ZMod k, IsUnit b ∧ b ∉ good_slopes_point_directions k S) → (good_slopes_point_directions k S).card ≤ L-d) (hcolored : ∀ (S : Finset (ZMod k × ZMod k)) (color : (ZMod k × ZMod k) → K), S.card = k → (∀ p ∈ S, ∀ q ∈ S, color p = color q → p.1 = q.1 → p = q) → (∀ b : ZMod k, IsUnit b → ∀ p ∈ S, ∀ q ∈ S, color p = color q → p.2 + b*p.1 = q.2 + b*q.1 → p = q) → (∃ b : ZMod k, IsUnit b ∧ b ∉ good_slopes_point_directions k S) → (good_slopes_point_directions k S).card ≤ L-r*d) (hlarge : ((Finset.univ : Finset K).filter fun a => IsUnit a).sum (fun a => ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b ∧ Function.Injective (fun x => (yK x + a*xK x, yk x + b*xk x))).card) > r*L-r*d) : ∀ a : K, IsUnit a → ∀ b : ZMod k, IsUnit b → Function.Injective (fun x => (yK x + a*xK x, yk x + b*xk x))
Source
Conditional many-row product-fiber reduction for OP-1027, generalizing good_slopes_two_row_fiber_rigidity_conditional.
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The theorem is proved by contradiction: assuming some row a ∈ K^× has a bad unit direction b ∈ (ℤ/kℤ)^×, we show that the sum of good unit directions across all r nonzero rows cannot exceed rL - rd, contradicting the hypothesis. First, if no row were completely full (having all L good directions), every row would have at most L - d good directions by an uncolored fiber rigidity lemma, forcing the sum to be at most r(L - d) = rL - rd. This guarantees the existence of at least one full row a₁, which allows us to color the fiber of the bad row a and apply a colored fiber rigidity lemma to bound |R(a)| ≤ L - rd. Bounding row a by L - rd and the remaining r - 1 rows by L gives a total sum of at most (r - 1)L + (L - rd) = rL - rd, yielding the final contradiction.

  1. In the uncolored helper lemma, failure of global injectivity in direction b implies failure of injectivity on some fiber S_t.

    Using the cardinality condition |X| = |K|·|ℤ/kℤ| via ZMod.card, the transfer lemma good_slopes_product_fiber_transfer establishes that global injectivity of an affine direction form is equivalent to injectivity on every fiber S_t = {(x_k(x), y_k(x)) | y_K(x) + a·x_K(x) = t}. Because direction b is assumed globally non-injective, it cannot be injective on every fiber; hence there exists some fiber t ∈ K on which p ↦ p₂ + b·p₁ fails to be injective on S_t.

    lines 12–21

    uses ZMod.card, good_slopes_product_fiber_transfer

      classical
      have hcard' : Fintype.card X = Fintype.card K * Fintype.card (ZMod k) := by
        rw [ZMod.card]; exact hcard
      have htransfer := good_slopes_product_fiber_transfer xK yK xk yk a b₀ hcard' hanchor
      obtain ⟨b, hbunit, hbinj⟩ := hbad
      have hnotall : ¬ ∀ t : K, Set.InjOn (fun p : ZMod k × ZMod k => p.2 + b*p.1) ↑(good_slopes_product_fiber_set xK yK xk yk a t) := by
        intro hall
        exact hbinj (htransfer.2.2 b hall)
      push_neg at hnotall
      obtain ⟨t, ht⟩ := hnotall
  2. The fiber set S_t has size k and has b as a bad unit direction, so it has at most L - d good unit directions.

    The transfer lemma shows that S_t has cardinality |ℤ/kℤ| = k. Since b is a unit and fails to be injective on S_t, b is not a good direction for S_t. Applying the uncolored gap assumption (hgap) to S_t, the number of good unit directions on S_t is at most L - d.

    lines 22–29

    uses ZMod.card, good_slopes_point_directions, Finset.mem_filter, Finset.mem_univ, true_and

      have hScard : (good_slopes_product_fiber_set xK yK xk yk a t).card = k := by
        have := htransfer.1 t
        rwa [ZMod.card] at this
      have hSbad : ∃ b' : ZMod k, IsUnit b' ∧ b' ∉ good_slopes_point_directions k (good_slopes_product_fiber_set xK yK xk yk a t) := by
        refine ⟨b, hbunit, fun hmem => ?_⟩
        simp only [good_slopes_point_directions, Finset.mem_filter, Finset.mem_univ, true_and] at hmem
        exact ht hmem.2
      have hgapS := hgap _ hScard hSbad
  3. The number of good unit directions for row a is at most L - d.

    Any unit direction b' that is globally injective for row a must, by the transfer lemma, be injective on the fiber S_t, meaning it is a good unit direction for S_t. Because the globally good unit directions for row a embed into the good unit directions of S_t, their number is bounded by the cardinality of the latter, which is at most L - d.

    lines 30–34

    uses le_trans, Finset.card_le_card, Finset.mem_filter, Finset.mem_univ, true_and, good_slopes_point_directions

      refine le_trans ?_ hgapS
      apply Finset.card_le_card
      intro b' hb'
      simp only [Finset.mem_filter, Finset.mem_univ, true_and, good_slopes_point_directions] at hb' ⊢
      exact ⟨hb'.1, htransfer.2.1 t b' hb'.2⟩
  4. In the colored helper lemma, there exists a fiber S_t on which direction b fails to be injective.

    As in the uncolored setting, we rewrite the cardinality using ZMod.card and invoke good_slopes_product_fiber_transfer. Since direction b is globally non-injective, there must be a fiber t ∈ K on which the direction form p ↦ p₂ + b·p₁ is not injective on S_t.

    lines 51–60

    uses ZMod.card, good_slopes_product_fiber_transfer

      classical
      have hcard' : Fintype.card X = Fintype.card K * Fintype.card (ZMod k) := by
        rw [ZMod.card]; exact hcard
      have htransfer := good_slopes_product_fiber_transfer xK yK xk yk a b₀ hcard' hanchor
      obtain ⟨b, hbunit, hbinj⟩ := hbad
      have hnotall : ¬ ∀ t : K, Set.InjOn (fun p : ZMod k × ZMod k => p.2 + b*p.1) ↑(good_slopes_product_fiber_set xK yK xk yk a t) := by
        intro hall
        exact hbinj (htransfer.2.2 b hall)
      push_neg at hnotall
      obtain ⟨t, ht⟩ := hnotall
  5. Each point of S_t has a representative in X and a K-coloring c(p) = x_K(rep(p)), with |S_t| = k.

    Points of S_t are characterized as images of points in X satisfying y_K + a·x_K = t. For each point p, we choose a representative in X (using dif_pos when p ∈ S_t) and define the color c(p) ∈ K to be the x_K-coordinate of this representative. By the transfer lemma, S_t has cardinality k.

    lines 61–73

    uses good_slopes_product_fiber_set, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and, dif_pos, ZMod.card

      have hmem_img : ∀ p : ZMod k × ZMod k, p ∈ good_slopes_product_fiber_set xK yK xk yk a t ↔ ∃ x : X, yK x + a*xK x = t ∧ (xk x, yk x) = p := by
        intro p
        simp only [good_slopes_product_fiber_set, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and]
      let rep : (ZMod k × ZMod k) → X := fun p =>
        if hp : ∃ x : X, yK x + a*xK x = t ∧ (xk x, yk x) = p then hp.choose else Classical.arbitrary X
      have hrep_spec : ∀ p, (∃ x : X, yK x + a*xK x = t ∧ (xk x, yk x) = p) → yK (rep p) + a*xK (rep p) = t ∧ (xk (rep p), yk (rep p)) = p := by
        intro p hp
        simp only [rep, dif_pos hp]
        exact hp.choose_spec
      let c : (ZMod k × ZMod k) → K := fun p => xK (rep p)
      have hScard : (good_slopes_product_fiber_set xK yK xk yk a t).card = k := by
        have := htransfer.1 t
        rwa [ZMod.card] at this
  6. The coloring c makes the first coordinate map injective on S_t within each color class.

    If two points p, q ∈ S_t have the same color c(p) = c(q) and equal first coordinates p.1 = q.1, their representatives in X have identical x_K and x_k coordinates. Since the map x ↦ (x_K(x), x_k(x)) is assumed injective, the representatives coincide, which forces p = q.

    lines 74–85

    uses Prod.ext

      have hcolor1 : ∀ p ∈ good_slopes_product_fiber_set xK yK xk yk a t, ∀ q ∈ good_slopes_product_fiber_set xK yK xk yk a t, c p = c q → p.1 = q.1 → p = q := by
        intro p hp q hq hc h1
        have hp' := (hmem_img p).mp hp
        have hq' := (hmem_img q).mp hq
        obtain ⟨hpf, hpe⟩ := hrep_spec p hp'
        obtain ⟨hqf, hqe⟩ := hrep_spec q hq'
        have hxKeq : xK (rep p) = xK (rep q) := hc
        have hxkeq : xk (rep p) = xk (rep q) := by
          rw [← hpe, ← hqe] at h1
          exact h1
        have : rep p = rep q := hx (Prod.ext hxKeq hxkeq)
        rw [← hpe, ← hqe, this]
  7. The coloring c makes every unit direction form injective on S_t within each color class.

    Suppose c(p) = c(q) and p₂ + b'·p₁ = q₂ + b'·q₁ for a unit b'. Color equality gives x_K(rep(p)) = x_K(rep(q)). Since both representatives lie on fiber t, y_K(rep(p)) + a·x_K(rep(p)) = y_K(rep(q)) + a·x_K(rep(q)), so cancelling a·x_K via add_right_cancel gives y_K(rep(p)) = y_K(rep(q)). Thus the representatives agree on the first coordinate for the full row a₁: y_K + a₁·x_K. Since they also agree on the b'-direction form, injectivity of row a₁ at unit b' implies that the representatives are equal, so p = q.

    lines 86–102

    uses add_right_cancel, Prod.ext

      have hcolor2 : ∀ b' : ZMod k, IsUnit b' → ∀ p ∈ good_slopes_product_fiber_set xK yK xk yk a t, ∀ q ∈ good_slopes_product_fiber_set xK yK xk yk a t, c p = c q → p.2 + b'*p.1 = q.2 + b'*q.1 → p = q := by
        intro b' hb' p hp q hq hc hform
        have hp' := (hmem_img p).mp hp
        have hq' := (hmem_img q).mp hq
        obtain ⟨hpf, hpe⟩ := hrep_spec p hp'
        obtain ⟨hqf, hqe⟩ := hrep_spec q hq'
        have hxKeq : xK (rep p) = xK (rep q) := hc
        have hyKeq : yK (rep p) = yK (rep q) := by
          have h1 : yK (rep p) + a*xK (rep p) = yK (rep q) + a*xK (rep q) := by rw [hpf, hqf]
          rw [hxKeq] at h1
          exact add_right_cancel h1
        have hform' : yk (rep p) + b'*xk (rep p) = yk (rep q) + b'*xk (rep q) := by
          rw [← hpe, ← hqe] at hform
          exact hform
        have hfirst : yK (rep p) + a1*xK (rep p) = yK (rep q) + a1*xK (rep q) := by rw [hyKeq, hxKeq]
        have := hfull b' hb' (Prod.ext hfirst hform')
        rw [← hpe, ← hqe, this]
  8. The number of good unit directions for row a is at most L - r·d.

    The fiber set S_t has size k and bad unit direction b. Because the coloring c satisfies both within-color injectivity hypotheses, the colored gap assumption (hcolored) implies that S_t has at most L - r·d good unit directions. Every globally good unit direction for row a restricts to a good direction on S_t, so row a has at most L - r·d good unit directions.

    lines 103–112

    uses good_slopes_point_directions, Finset.mem_filter, Finset.mem_univ, true_and, le_trans, Finset.card_le_card

      have hSbad : ∃ b' : ZMod k, IsUnit b' ∧ b' ∉ good_slopes_point_directions k (good_slopes_product_fiber_set xK yK xk yk a t) := by
        refine ⟨b, hbunit, fun hmem => ?_⟩
        simp only [good_slopes_point_directions, Finset.mem_filter, Finset.mem_univ, true_and] at hmem
        exact ht hmem.2
      have hgapS := hcolored _ c hScard hcolor1 hcolor2 hSbad
      refine le_trans ?_ hgapS
      apply Finset.card_le_card
      intro b' hb'
      simp only [Finset.mem_filter, Finset.mem_univ, true_and, good_slopes_point_directions] at hb' ⊢
      exact ⟨hb'.1, htransfer.2.1 t b' hb'.2⟩
  9. In the main theorem, define D = K^× of size r and R(a) as the set of good unit directions for row a, with each |R(a)| ≤ L.

    Let D be the set of r nonzero elements (units) of K, and for each a ∈ K, let R(a) be the set of unit directions b modulo k that make row a injective. Since R(a) is a subset of the L units modulo k, its cardinality is at most L.

    lines 115–128

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.card_le_card

      classical
      let D : Finset K := (Finset.univ : Finset K).filter (fun a => IsUnit a)
      let R : K → Finset (ZMod k) := fun a => (Finset.univ : Finset (ZMod k)).filter (fun b => IsUnit b ∧ Function.Injective (fun x => (yK x + a*xK x, yk x + b*xk x)))
      have hDcard : D.card = r := hR
      have hlarge' : r*L - r*d < D.sum (fun a => (R a).card) := hlarge
      have hbound : ∀ a, (R a).card ≤ L := by
        intro a
        have hsub : R a ⊆ (Finset.univ : Finset (ZMod k)).filter (fun b => IsUnit b) := by
          intro c hc
          simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at hc ⊢
          exact hc.1
        have := Finset.card_le_card hsub
        rw [hL] at this
        exact this
  10. Assume for contradiction that some row a in D and unit b fail injectivity.

    We introduce a row a ∈ D and a unit direction b, and suppose for contradiction that the affine form x ↦ (y_K(x) + a·x_K(x), y_k(x) + b·x_k(x)) is not injective.

    lines 129–135

    uses Finset.mem_filter, Finset.mem_univ, true_and

      intro a ha b hb
      by_contra hcon
      have haD : a ∈ D := by simp only [D, Finset.mem_filter, Finset.mem_univ, true_and]; exact ha
      have hRsubD : R a ⊆ (Finset.univ : Finset (ZMod k)).filter (fun b => IsUnit b) := by
        intro c hc
        simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at hc ⊢
        exact hc.1
  11. There exists at least one full row a₁ in D with |R(a₁)| = L.

    Suppose for contradiction that no row in D is full, so |R(a')| < L for all a' ∈ D. Then every row a' has a bad unit direction. If R(a') is empty, its size is 0 ≤ L - d. If R(a') is non-empty, any element provides an anchor direction (injective maps between finite sets of equal cardinality are bijective by Fintype.bijective_iff_injective_and_card), and the uncolored rigidity lemma good_slopes_many_row_fiber_rigidity_conditional_uncolored gives |R(a')| ≤ L - d. Summing over all r rows in D yields ∑ |R(a')| ≤ r(L - d) = rL - rd, which contradicts the hypothesis that the sum strictly exceeds rL - rd. Thus, at least one full row a₁ ∈ D exists.

    lines 136–172

    uses Finset.mem_filter, Finset.mem_univ, true_and, lt_of_le_of_ne, Finset.ssubset_iff_subset_ne, lt_irrefl, Finset.exists_of_ssubset, Fintype.bijective_iff_injective_and_card, Fintype.card_prod, ZMod.card, good_slopes_many_row_fiber_rigidity_conditional_uncolored, Finset.not_nonempty_iff_eq_empty, Finset.sum_le_sum, Nat.mul_sub, lt_of_lt_of_le

      have hfull_exists : ∃ a1 ∈ D, (R a1).card = L := by
        by_contra hcon2
        have hle : ∀ a' ∈ D, (R a').card ≤ L - d := by
          intro a' ha'
          have hne : (R a').card ≠ L := fun heq => hcon2 ⟨a', ha', heq⟩
          have hbad' : ∃ c : ZMod k, IsUnit c ∧ ¬ Function.Injective (fun x => (yK x + a'*xK x, yk x + c*xk x)) := by
            have hsub : R a' ⊆ (Finset.univ : Finset (ZMod k)).filter (fun b => IsUnit b) := by
              intro c hc
              simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at hc ⊢
              exact hc.1
            have hcardlt : (R a').card < ((Finset.univ : Finset (ZMod k)).filter (fun b => IsUnit b)).card := by
              rw [hL]; exact lt_of_le_of_ne (hbound a') hne
            have hssub : R a' ⊂ (Finset.univ : Finset (ZMod k)).filter (fun b => IsUnit b) := by
              rw [Finset.ssubset_iff_subset_ne]
              exact ⟨hsub, fun heq => by rw [heq] at hcardlt; exact lt_irrefl _ hcardlt⟩
            obtain ⟨c, hc, hcn⟩ := Finset.exists_of_ssubset hssub
            simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hc
            refine ⟨c, hc, fun hinj => hcn ?_⟩
            simp only [R, Finset.mem_filter, Finset.mem_univ, true_and]
            exact ⟨hc, hinj⟩
          by_cases hemp : (R a').Nonempty
          · obtain ⟨b0, hb0⟩ := hemp
            have hanchor : Function.Bijective (fun x => (yK x + a'*xK x, yk x + b0*xk x)) := by
              refine (Fintype.bijective_iff_injective_and_card _).2 ⟨?_, ?_⟩
              · simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at hb0; exact hb0.2
              · simp only [Fintype.card_prod, ZMod.card]; exact hcard
            exact good_slopes_many_row_fiber_rigidity_conditional_uncolored K k L d xK yK xk yk a' b0 hcard hgap hanchor hbad'
          · rw [Finset.not_nonempty_iff_eq_empty] at hemp
            rw [hemp]
            simp
        have hsumle : D.sum (fun a' => (R a').card) ≤ r*(L-d) := by
          calc D.sum (fun a' => (R a').card) ≤ D.sum (fun _ => L-d) := Finset.sum_le_sum hle
            _ = D.card * (L-d) := by simp
            _ = r*(L-d) := by rw [hDcard]
        have hmul : r*(L-d) = r*L - r*d := Nat.mul_sub r L d
        rw [hmul] at hsumle
        exact absurd (lt_of_lt_of_le hlarge' hsumle) (lt_irrefl _)
  12. The bad row a has at most L - r·d good unit directions.

    If R(a) is empty, its cardinality is 0, which is at most L - r·d because r·d < L. If R(a) is non-empty, any element gives an anchor direction. Having established the existence of a full row a₁, all hypotheses of good_slopes_many_row_fiber_rigidity_conditional_colored are satisfied, proving that |R(a)| ≤ L - r·d.

    lines 173–196

    uses Fintype.bijective_iff_injective_and_card, Finset.mem_filter, Finset.mem_univ, true_and, Fintype.card_prod, ZMod.card, Finset.eq_of_subset_of_card_le, good_slopes_many_row_fiber_rigidity_conditional_colored, Finset.not_nonempty_iff_eq_empty, Finset.card_empty

      have hAcard : (R a).card ≤ L - r*d := by
        by_cases hemp : (R a).Nonempty
        · obtain ⟨b0, hb0⟩ := hemp
          have hanchor : Function.Bijective (fun x => (yK x + a*xK x, yk x + b0*xk x)) := by
            refine (Fintype.bijective_iff_injective_and_card _).2 ⟨?_, ?_⟩
            · simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at hb0; exact hb0.2
            · simp only [Fintype.card_prod, ZMod.card]; exact hcard
          obtain ⟨a1, ha1D, ha1full⟩ := hfull_exists
          have hRequal : R a1 = (Finset.univ : Finset (ZMod k)).filter (fun b => IsUnit b) := by
            apply Finset.eq_of_subset_of_card_le
            · intro c hc
              simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at hc ⊢
              exact hc.1
            · rw [hL, ha1full]
          have hfull : ∀ c : ZMod k, IsUnit c → Function.Injective (fun x => (yK x + a1*xK x, yk x + c*xk x)) := by
            intro c hc
            have hmem : c ∈ R a1 := by rw [hRequal]; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; exact hc
            simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at hmem
            exact hmem.2
          exact good_slopes_many_row_fiber_rigidity_conditional_colored K k L r d xK yK xk yk a a1 b0 hcard hx hcolored hanchor hfull ⟨b, hb, hcon⟩
        · rw [Finset.not_nonempty_iff_eq_empty] at hemp
          rw [hemp]
          simp only [Finset.card_empty]
          omega
  13. Summing over all rows yields at most rL - rd, reaching a contradiction.

    We split the sum into row a and the remaining r - 1 rows: ∑_{a' ∈ D} |R(a')| = ∑_{a' ∈ D \ {a}} |R(a')| + |R(a)|. Each of the other r - 1 rows contributes at most L, so their sum is at most (r - 1)L. Combined with |R(a)| ≤ L - r·d, the total sum is at most (r - 1)L + L - r·d = rL - rd. This contradicts the assumption that the sum strictly exceeds rL - rd, completing the proof.

    lines 197–214

    uses Finset.sum_erase_add, Finset.card_erase_of_mem, Finset.sum_le_sum, add_le_add, Nat.succ_mul, Nat.add_sub_assoc, le_of_lt, lt_of_lt_of_le, le_trans, lt_irrefl

      have hsplit : D.sum (fun a' => (R a').card) = (D.erase a).sum (fun a' => (R a').card) + (R a).card :=
        (Finset.sum_erase_add D (fun a' => (R a').card) haD).symm
      have herase_card : (D.erase a).card = r - 1 := by
        rw [Finset.card_erase_of_mem haD, hDcard]
      have herase_le : (D.erase a).sum (fun a' => (R a').card) ≤ (r-1)*L := by
        calc (D.erase a).sum (fun a' => (R a').card) ≤ (D.erase a).sum (fun _ => L) := Finset.sum_le_sum (fun a' _ => hbound a')
          _ = (D.erase a).card * L := by simp
          _ = (r-1)*L := by rw [herase_card]
      have hsum_le : D.sum (fun a' => (R a').card) ≤ (r-1)*L + (L - r*d) := by
        rw [hsplit]
        exact add_le_add herase_le hAcard
      have hfin : (r-1)*L + (L - r*d) ≤ r*L - r*d := by
        have hr1 : (r-1)*L + L = r*L := by
          cases r with
          | zero => omega
          | succ s => simp [Nat.succ_mul]
        rw [← hr1, Nat.add_sub_assoc (le_of_lt hLd)]
      exact absurd (lt_of_lt_of_le hlarge' (le_trans hsum_le hfin)) (lt_irrefl _)
ZMod.card
The cardinality of ℤ/nℤ is n.
good_slopes_product_fiber_transfer
Given an anchor direction that makes an affine form bijective, each fiber set has size equal to the second factor, and global injectivity of an affine direction is equivalent to injectivity on every fiber.
good_slopes_point_directions
The set of unit directions a modulo n such that the direction form p ↦ p₂ + a·p₁ is injective on a set S.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal finset.
true_and
The conjunction of True with a proposition p simplifies to p.
le_trans
If a ≤ b and b ≤ c, then a ≤ c.
Finset.card_le_card
If s ⊆ t, then |s| ≤ |t|.
good_slopes_product_fiber_set
The projection to the second coordinate factor of the fiber {x ∈ X | y_Y(x) + a·x_Y(x) = t}.
Finset.mem_image
An element y is in the image of a finset under f if and only if y = f(x) for some x in the finset.
dif_pos
A dependent conditional expression with condition c evaluates to its then-branch when c is true.
Prod.ext
Two ordered pairs are equal if and only if their first coordinates are equal and their second coordinates are equal.
add_right_cancel
In an additive structure with right cancellation, a + b = c + b implies a = c.
lt_of_le_of_ne
If a ≤ b and a ≠ b, then a < b.
Finset.ssubset_iff_subset_ne
A finset s is a strict subset of t if and only if s ⊆ t and s ≠ t.
lt_irrefl
Strict order is irreflexive: a < a is false for all a.
Finset.exists_of_ssubset
If s₁ is a strict subset of s₂, there exists an element in s₂ that does not belong to s₁.
Fintype.bijective_iff_injective_and_card
A map between finite types of the same cardinality is bijective if and only if it is injective.
Fintype.card_prod
The cardinality of the Cartesian product of two finite types is the product of their cardinalities.
good_slopes_many_row_fiber_rigidity_conditional_uncolored
If a row has an anchor direction and a bad unit direction, the number of good unit directions on that row is at most L - d.
Finset.not_nonempty_iff_eq_empty
A finset is not non-empty if and only if it is the empty set.
Finset.sum_le_sum
If f(i) ≤ g(i) for all i in a finite set, then the sum of f over that set is at most the sum of g.
Nat.mul_sub
Multiplication distributes over subtraction in ℕ: n·(m - k) = n·m - n·k.
lt_of_lt_of_le
If a < b and b ≤ c, then a < c.
Finset.eq_of_subset_of_card_le
If s ⊆ t and |t| ≤ |s| for finsets s and t, then s = t.
good_slopes_many_row_fiber_rigidity_conditional_colored
If a row has an anchor, a bad unit direction, and another row that is completely full, then the number of good unit directions on that row is at most L - r·d.
Finset.card_empty
The cardinality of the empty finset is 0.
Finset.sum_erase_add
Summing over a finset with an element removed and adding back that element's term equals the sum over the entire set.
Finset.card_erase_of_mem
Removing an element from a finset decreases its cardinality by 1.
add_le_add
If a ≤ b and c ≤ d, then a + c ≤ b + d.
Nat.succ_mul
For natural numbers, (n + 1)·m = n·m + m.
Nat.add_sub_assoc
If k ≤ m in ℕ, then n + m - k = n + (m - k).
le_of_lt
If a < b, then a ≤ b.

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 good_slopes_many_row_fiber_rigidity_conditional_uncolored    (K : Type*) [Field K] [Fintype K] [DecidableEq K] (k L d : ℕ) [NeZero k]    {X : Type*} [Fintype X] [DecidableEq X]    (xK yK : X → K) (xk yk : X → ZMod k) (a : K) (b₀ : ZMod k)    (hcard : Fintype.card X = Fintype.card K * k)    (hgap : ∀ S : Finset (ZMod k × ZMod k), S.card = k →      (∃ b : ZMod k, IsUnit b ∧ b ∉ good_slopes_point_directions k S) →      (good_slopes_point_directions k S).card ≤ L-d)    (hanchor : Function.Bijective (fun x => (yK x + a*xK x, yk x + b₀*xk x)))    (hbad : ∃ b : ZMod k, IsUnit b ∧ ¬ Function.Injective (fun x => (yK x + a*xK x, yk x + b*xk x))) :    ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b ∧ Function.Injective (fun x => (yK x + a*xK x, yk x + b*xk x))).card ≤ L - d := by  classical  have hcard' : Fintype.card X = Fintype.card K * Fintype.card (ZMod k) := by    rw [ZMod.card]; exact hcard  have htransfer := good_slopes_product_fiber_transfer xK yK xk yk a b₀ hcard' hanchor  obtain ⟨b, hbunit, hbinj⟩ := hbad  have hnotall : ¬ ∀ t : K, Set.InjOn (fun p : ZMod k × ZMod k => p.2 + b*p.1) ↑(good_slopes_product_fiber_set xK yK xk yk a t) := by    intro hall    exact hbinj (htransfer.2.2 b hall)  push_neg at hnotall  obtain ⟨t, ht⟩ := hnotall  have hScard : (good_slopes_product_fiber_set xK yK xk yk a t).card = k := by    have := htransfer.1 t    rwa [ZMod.card] at this  have hSbad : ∃ b' : ZMod k, IsUnit b' ∧ b' ∉ good_slopes_point_directions k (good_slopes_product_fiber_set xK yK xk yk a t) := by    refine ⟨b, hbunit, fun hmem => ?_⟩    simp only [good_slopes_point_directions, Finset.mem_filter, Finset.mem_univ, true_and] at hmem    exact ht hmem.2  have hgapS := hgap _ hScard hSbad  refine le_trans ?_ hgapS  apply Finset.card_le_card  intro b' hb'  simp only [Finset.mem_filter, Finset.mem_univ, true_and, good_slopes_point_directions] at hb' ⊢  exact ⟨hb'.1, htransfer.2.1 t b' hb'.2⟩theorem good_slopes_many_row_fiber_rigidity_conditional_colored    (K : Type*) [Field K] [Fintype K] [DecidableEq K] (k L r d : ℕ) [NeZero k]    {X : Type*} [Fintype X] [DecidableEq X] [Nonempty X]    (xK yK : X → K) (xk yk : X → ZMod k) (a a1 : K) (b₀ : ZMod k)    (hcard : Fintype.card X = Fintype.card K * k)    (hx : Function.Injective (fun x => (xK x, xk x)))    (hcolored : ∀ (S : Finset (ZMod k × ZMod k)) (color : (ZMod k × ZMod k) → K), S.card = k →      (∀ p ∈ S, ∀ q ∈ S, color p = color q → p.1 = q.1 → p = q) →      (∀ b : ZMod k, IsUnit b → ∀ p ∈ S, ∀ q ∈ S, color p = color q → p.2 + b*p.1 = q.2 + b*q.1 → p = q) →      (∃ b : ZMod k, IsUnit b ∧ b ∉ good_slopes_point_directions k S) →      (good_slopes_point_directions k S).card ≤ L-r*d)    (hanchor : Function.Bijective (fun x => (yK x + a*xK x, yk x + b₀*xk x)))    (hfull : ∀ b : ZMod k, IsUnit b → Function.Injective (fun x => (yK x + a1*xK x, yk x + b*xk x)))    (hbad : ∃ b : ZMod k, IsUnit b ∧ ¬ Function.Injective (fun x => (yK x + a*xK x, yk x + b*xk x))) :    ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b ∧ Function.Injective (fun x => (yK x + a*xK x, yk x + b*xk x))).card ≤ L - r*d := by  classical  have hcard' : Fintype.card X = Fintype.card K * Fintype.card (ZMod k) := by    rw [ZMod.card]; exact hcard  have htransfer := good_slopes_product_fiber_transfer xK yK xk yk a b₀ hcard' hanchor  obtain ⟨b, hbunit, hbinj⟩ := hbad  have hnotall : ¬ ∀ t : K, Set.InjOn (fun p : ZMod k × ZMod k => p.2 + b*p.1) ↑(good_slopes_product_fiber_set xK yK xk yk a t) := by    intro hall    exact hbinj (htransfer.2.2 b hall)  push_neg at hnotall  obtain ⟨t, ht⟩ := hnotall  have hmem_img : ∀ p : ZMod k × ZMod k, p ∈ good_slopes_product_fiber_set xK yK xk yk a t ↔ ∃ x : X, yK x + a*xK x = t ∧ (xk x, yk x) = p := by    intro p    simp only [good_slopes_product_fiber_set, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and]  let rep : (ZMod k × ZMod k) → X := fun p =>    if hp : ∃ x : X, yK x + a*xK x = t ∧ (xk x, yk x) = p then hp.choose else Classical.arbitrary X  have hrep_spec : ∀ p, (∃ x : X, yK x + a*xK x = t ∧ (xk x, yk x) = p) → yK (rep p) + a*xK (rep p) = t ∧ (xk (rep p), yk (rep p)) = p := by    intro p hp    simp only [rep, dif_pos hp]    exact hp.choose_spec  let c : (ZMod k × ZMod k) → K := fun p => xK (rep p)  have hScard : (good_slopes_product_fiber_set xK yK xk yk a t).card = k := by    have := htransfer.1 t    rwa [ZMod.card] at this  have hcolor1 : ∀ p ∈ good_slopes_product_fiber_set xK yK xk yk a t, ∀ q ∈ good_slopes_product_fiber_set xK yK xk yk a t, c p = c q → p.1 = q.1 → p = q := by    intro p hp q hq hc h1    have hp' := (hmem_img p).mp hp    have hq' := (hmem_img q).mp hq    obtain ⟨hpf, hpe⟩ := hrep_spec p hp'    obtain ⟨hqf, hqe⟩ := hrep_spec q hq'    have hxKeq : xK (rep p) = xK (rep q) := hc    have hxkeq : xk (rep p) = xk (rep q) := by      rw [← hpe, ← hqe] at h1      exact h1    have : rep p = rep q := hx (Prod.ext hxKeq hxkeq)    rw [← hpe, ← hqe, this]  have hcolor2 : ∀ b' : ZMod k, IsUnit b' → ∀ p ∈ good_slopes_product_fiber_set xK yK xk yk a t, ∀ q ∈ good_slopes_product_fiber_set xK yK xk yk a t, c p = c q → p.2 + b'*p.1 = q.2 + b'*q.1 → p = q := by    intro b' hb' p hp q hq hc hform    have hp' := (hmem_img p).mp hp    have hq' := (hmem_img q).mp hq    obtain ⟨hpf, hpe⟩ := hrep_spec p hp'    obtain ⟨hqf, hqe⟩ := hrep_spec q hq'    have hxKeq : xK (rep p) = xK (rep q) := hc    have hyKeq : yK (rep p) = yK (rep q) := by      have h1 : yK (rep p) + a*xK (rep p) = yK (rep q) + a*xK (rep q) := by rw [hpf, hqf]      rw [hxKeq] at h1      exact add_right_cancel h1    have hform' : yk (rep p) + b'*xk (rep p) = yk (rep q) + b'*xk (rep q) := by      rw [← hpe, ← hqe] at hform      exact hform    have hfirst : yK (rep p) + a1*xK (rep p) = yK (rep q) + a1*xK (rep q) := by rw [hyKeq, hxKeq]    have := hfull b' hb' (Prod.ext hfirst hform')    rw [← hpe, ← hqe, this]  have hSbad : ∃ b' : ZMod k, IsUnit b' ∧ b' ∉ good_slopes_point_directions k (good_slopes_product_fiber_set xK yK xk yk a t) := by    refine ⟨b, hbunit, fun hmem => ?_⟩    simp only [good_slopes_point_directions, Finset.mem_filter, Finset.mem_univ, true_and] at hmem    exact ht hmem.2  have hgapS := hcolored _ c hScard hcolor1 hcolor2 hSbad  refine le_trans ?_ hgapS  apply Finset.card_le_card  intro b' hb'  simp only [Finset.mem_filter, Finset.mem_univ, true_and, good_slopes_point_directions] at hb' ⊢  exact ⟨hb'.1, htransfer.2.1 t b' hb'.2⟩theorem good_slopes_many_row_fiber_rigidity_conditional (K : Type*) [Field K] [Fintype K] [DecidableEq K] (k L r d : ℕ) [NeZero k] {X : Type*} [Fintype X] [DecidableEq X] [Nonempty X] (xK yK : X → K) (xk yk : X → ZMod k) (hcard : Fintype.card X = Fintype.card K * k) (hx : Function.Injective (fun x => (xK x, xk x))) (hL : ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b).card = L) (hR : ((Finset.univ : Finset K).filter fun a => IsUnit a).card = r) (hr : 0 < r) (hd : 0 < d) (hLd : r*d < L) (hgap : ∀ S : Finset (ZMod k × ZMod k), S.card = k → (∃ b : ZMod k, IsUnit b ∧ b ∉ good_slopes_point_directions k S) → (good_slopes_point_directions k S).card ≤ L-d) (hcolored : ∀ (S : Finset (ZMod k × ZMod k)) (color : (ZMod k × ZMod k) → K), S.card = k → (∀ p ∈ S, ∀ q ∈ S, color p = color q → p.1 = q.1 → p = q) → (∀ b : ZMod k, IsUnit b → ∀ p ∈ S, ∀ q ∈ S, color p = color q → p.2 + b*p.1 = q.2 + b*q.1 → p = q) → (∃ b : ZMod k, IsUnit b ∧ b ∉ good_slopes_point_directions k S) → (good_slopes_point_directions k S).card ≤ L-r*d) (hlarge : ((Finset.univ : Finset K).filter fun a => IsUnit a).sum (fun a => ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b ∧ Function.Injective (fun x => (yK x + a*xK x, yk x + b*xk x))).card) > r*L-r*d) : ∀ a : K, IsUnit a → ∀ b : ZMod k, IsUnit b → Function.Injective (fun x => (yK x + a*xK x, yk x + b*xk x)) := by  classical  let D : Finset K := (Finset.univ : Finset K).filter (fun a => IsUnit a)  let R : K → Finset (ZMod k) := fun a => (Finset.univ : Finset (ZMod k)).filter (fun b => IsUnit b ∧ Function.Injective (fun x => (yK x + a*xK x, yk x + b*xk x)))  have hDcard : D.card = r := hR  have hlarge' : r*L - r*d < D.sum (fun a => (R a).card) := hlarge  have hbound : ∀ a, (R a).card ≤ L := by    intro a    have hsub : R a ⊆ (Finset.univ : Finset (ZMod k)).filter (fun b => IsUnit b) := by      intro c hc      simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at hc ⊢      exact hc.1    have := Finset.card_le_card hsub    rw [hL] at this    exact this  intro a ha b hb  by_contra hcon  have haD : a ∈ D := by simp only [D, Finset.mem_filter, Finset.mem_univ, true_and]; exact ha  have hRsubD : R a ⊆ (Finset.univ : Finset (ZMod k)).filter (fun b => IsUnit b) := by    intro c hc    simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at hc ⊢    exact hc.1  have hfull_exists : ∃ a1 ∈ D, (R a1).card = L := by    by_contra hcon2    have hle : ∀ a' ∈ D, (R a').card ≤ L - d := by      intro a' ha'      have hne : (R a').card ≠ L := fun heq => hcon2 ⟨a', ha', heq⟩      have hbad' : ∃ c : ZMod k, IsUnit c ∧ ¬ Function.Injective (fun x => (yK x + a'*xK x, yk x + c*xk x)) := by        have hsub : R a' ⊆ (Finset.univ : Finset (ZMod k)).filter (fun b => IsUnit b) := by          intro c hc          simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at hc ⊢          exact hc.1        have hcardlt : (R a').card < ((Finset.univ : Finset (ZMod k)).filter (fun b => IsUnit b)).card := by          rw [hL]; exact lt_of_le_of_ne (hbound a') hne        have hssub : R a' ⊂ (Finset.univ : Finset (ZMod k)).filter (fun b => IsUnit b) := by          rw [Finset.ssubset_iff_subset_ne]          exact ⟨hsub, fun heq => by rw [heq] at hcardlt; exact lt_irrefl _ hcardlt⟩        obtain ⟨c, hc, hcn⟩ := Finset.exists_of_ssubset hssub        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hc        refine ⟨c, hc, fun hinj => hcn ?_⟩        simp only [R, Finset.mem_filter, Finset.mem_univ, true_and]        exact ⟨hc, hinj⟩      by_cases hemp : (R a').Nonempty      · obtain ⟨b0, hb0⟩ := hemp        have hanchor : Function.Bijective (fun x => (yK x + a'*xK x, yk x + b0*xk x)) := by          refine (Fintype.bijective_iff_injective_and_card _).2 ⟨?_, ?_⟩          · simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at hb0; exact hb0.2          · simp only [Fintype.card_prod, ZMod.card]; exact hcard        exact good_slopes_many_row_fiber_rigidity_conditional_uncolored K k L d xK yK xk yk a' b0 hcard hgap hanchor hbad'      · rw [Finset.not_nonempty_iff_eq_empty] at hemp        rw [hemp]        simp    have hsumle : D.sum (fun a' => (R a').card) ≤ r*(L-d) := by      calc D.sum (fun a' => (R a').card) ≤ D.sum (fun _ => L-d) := Finset.sum_le_sum hle        _ = D.card * (L-d) := by simp        _ = r*(L-d) := by rw [hDcard]    have hmul : r*(L-d) = r*L - r*d := Nat.mul_sub r L d    rw [hmul] at hsumle    exact absurd (lt_of_lt_of_le hlarge' hsumle) (lt_irrefl _)  have hAcard : (R a).card ≤ L - r*d := by    by_cases hemp : (R a).Nonempty    · obtain ⟨b0, hb0⟩ := hemp      have hanchor : Function.Bijective (fun x => (yK x + a*xK x, yk x + b0*xk x)) := by        refine (Fintype.bijective_iff_injective_and_card _).2 ⟨?_, ?_⟩        · simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at hb0; exact hb0.2        · simp only [Fintype.card_prod, ZMod.card]; exact hcard      obtain ⟨a1, ha1D, ha1full⟩ := hfull_exists      have hRequal : R a1 = (Finset.univ : Finset (ZMod k)).filter (fun b => IsUnit b) := by        apply Finset.eq_of_subset_of_card_le        · intro c hc          simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at hc ⊢          exact hc.1        · rw [hL, ha1full]      have hfull : ∀ c : ZMod k, IsUnit c → Function.Injective (fun x => (yK x + a1*xK x, yk x + c*xk x)) := by        intro c hc        have hmem : c ∈ R a1 := by rw [hRequal]; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; exact hc        simp only [R, Finset.mem_filter, Finset.mem_univ, true_and] at hmem        exact hmem.2      exact good_slopes_many_row_fiber_rigidity_conditional_colored K k L r d xK yK xk yk a a1 b0 hcard hx hcolored hanchor hfull ⟨b, hb, hcon⟩    · rw [Finset.not_nonempty_iff_eq_empty] at hemp      rw [hemp]      simp only [Finset.card_empty]      omega  have hsplit : D.sum (fun a' => (R a').card) = (D.erase a).sum (fun a' => (R a').card) + (R a).card :=    (Finset.sum_erase_add D (fun a' => (R a').card) haD).symm  have herase_card : (D.erase a).card = r - 1 := by    rw [Finset.card_erase_of_mem haD, hDcard]  have herase_le : (D.erase a).sum (fun a' => (R a').card) ≤ (r-1)*L := by    calc (D.erase a).sum (fun a' => (R a').card) ≤ (D.erase a).sum (fun _ => L) := Finset.sum_le_sum (fun a' _ => hbound a')      _ = (D.erase a).card * L := by simp      _ = (r-1)*L := by rw [herase_card]  have hsum_le : D.sum (fun a' => (R a').card) ≤ (r-1)*L + (L - r*d) := by    rw [hsplit]    exact add_le_add herase_le hAcard  have hfin : (r-1)*L + (L - r*d) ≤ r*L - r*d := by    have hr1 : (r-1)*L + L = r*L := by      cases r with      | zero => omega      | succ s => simp [Nat.succ_mul]    rw [← hr1, Nat.add_sub_assoc (le_of_lt hLd)]  exact absurd (lt_of_lt_of_le hlarge' (le_trans hsum_le hfin)) (lt_irrefl _)
See it in the graphDiscuss this resultChallenge it