AFTD Auto-Formalizing Theoretical Domains

good_slopes_two_row_fiber_rigidity_conditional

theoremverified

Let k be nonzero and let X be a finite set of size 3k whose input coordinates in Z/3 and Z/k form an injective pair. Suppose there are L units modulo k and 0 < d with 2d < L. Assume every k-point fiber with a bad unit direction has at most L-d good unit directions, and every such fiber whose points have a three-coloring that makes the first coordinate and every unit-direction form injective within each color has at most L-2d good unit directions. For any two fixed first-coordinate slopes, if the numbers of unit second-coordinate slopes giving injective coordinate maps sum to more than 2L-2d, then all unit second-coordinate slopes give injective maps in both rows.

Statement

theorem good_slopes_two_row_fiber_rigidity_conditional (k L d : ℕ) [NeZero k] {X : Type*} [Fintype X] [DecidableEq X] [Nonempty X] (x3 y3 : X → ZMod 3) (xk yk : X → ZMod k) (a a' : ZMod 3) (hcard : Fintype.card X = 3*k) (hx : Function.Injective (fun x => (x3 x, xk x))) (hL : ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b).card = L) (hd : 0 < d) (hLd : 2*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)) (c : (ZMod k × ZMod k) → Fin 3), S.card = k → (∀ p ∈ S, ∀ q ∈ S, c p = c q → p.1 = q.1 → p = q) → (∀ b : ZMod k, IsUnit b → ∀ p ∈ S, ∀ q ∈ S, c p = c 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-2*d) (hlarge : ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b ∧ Function.Injective (fun x => (y3 x + a*x3 x, yk x + b*xk x))).card + ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b ∧ Function.Injective (fun x => (y3 x + a'*x3 x, yk x + b*xk x))).card > 2*L-2*d) : (∀ b : ZMod k, IsUnit b → Function.Injective (fun x => (y3 x + a*x3 x, yk x + b*xk x))) ∧ (∀ b : ZMod k, IsUnit b → Function.Injective (fun x => (y3 x + a'*x3 x, yk x + b*xk x)))
Source
Conditional CRT fiber reduction for OP-1027, generalizing the proved modulus-35 two-row reduction.
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

The proof, explained

The theorem is proved by contradiction using two transfer principles from point sets to fibers of the affine coordinate maps. If a row has an anchor bijection and a bad unit slope, its good slopes embed into the directions of a bad fiber, so the uncolored gap hypothesis bounds its good slopes by L - d. If the other row is completely injective, the fiber points can be 3-colored by their ZMod 3 coordinates, satisfying the colored gap hypotheses and sharpening the bound to L - 2d. Since the sum of good slopes across the two rows exceeds 2L - 2d, both rows have anchors, and if either row had a bad slope, the other would be complete, forcing the sum of good slopes to be at most (L - 2d) + L = 2L - 2d, a contradiction.

  1. If row q has a bad unit slope b, then there is some fiber S of row q for which b is not a good direction.

    Since |X| = 3k = |ZMod 3| * |ZMod k| and row q has a bijective anchor map at slope b₀, the product fiber transfer theorem good_slopes_product_fiber_transfer applies. Suppose, for contradiction, that b were a good direction for every fiber of row q; then the transfer theorem would imply that the global coordinate map at slope b is injective on X, contradicting the assumption that b is bad. Hence b must fail to be a good direction on at least one fiber.

    lines 13–27

    uses good_slopes_product_fiber_transfer

      have hcard' : Fintype.card X = Fintype.card (ZMod 3) * Fintype.card (ZMod k) := by
        simp [hcard]
      have htransfer := good_slopes_product_fiber_transfer x3 y3 xk yk q b₀ hcard' hanchor
      rcases hbad with ⟨b, hb, hbinj⟩
      have ht_bad : ∃ t : ZMod 3, b ∉ good_slopes_point_directions k (good_slopes_product_fiber_set x3 y3 xk yk q t) := by
        by_contra h
        simp only [not_exists, not_not] at h
        have hall : ∀ t : ZMod 3, Set.InjOn (fun p : ZMod k × ZMod k => p.2 + b * p.1) (good_slopes_product_fiber_set x3 y3 xk yk q t) := by
          intro t
          have ht := h t
          unfold good_slopes_point_directions at ht
          simp only [mem_filter, mem_univ, true_and] at ht
          exact ht.2
        exact hbinj (htransfer.2.2 b hall)
      obtain ⟨t, ht⟩ := ht_bad
  2. The fiber S has size k and at most L - d good directions.

    By the transfer theorem, the fiber S has cardinality |ZMod k| = k. Because b is a unit direction that is bad for S, the uncolored gap hypothesis hgap applies directly to S, showing that S has at most L - d good unit directions.

    lines 28–34

    uses ZMod.card

      set S := good_slopes_product_fiber_set x3 y3 xk yk q t
      have hScard : S.card = k := by
        have h1 := htransfer.1 t
        rw [ZMod.card] at h1
        exact h1
      have hgap_S : (good_slopes_point_directions k S).card ≤ L - d :=
        hgap S hScard ⟨b, hb, ht⟩
  3. Row q has at most L - d good unit slopes.

    Every unit slope that gives an injective coordinate map on X restricts to an injective direction on the fiber S by good_slopes_product_fiber_transfer. The set of good unit slopes in row q is therefore a subset of the good directions of S, so by Finset.card_le_card its cardinality is at most L - d.

    lines 35–41

    uses Finset.card_le_card

      have hsub : ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b ∧ Function.Injective (fun x => (y3 x + q*x3 x, yk x + b*xk x))) ⊆ good_slopes_point_directions k S := by
        intro b' hb'
        simp only [mem_filter, mem_univ, true_and] at hb'
        unfold good_slopes_point_directions
        simp only [mem_filter, mem_univ, true_and]
        refine ⟨hb'.1, htransfer.2.1 t b' hb'.2⟩
      exact (Finset.card_le_card hsub).trans hgap_S
  4. There is a fiber S of row q of size k for which the bad slope b is not a good direction.

    Under the hypotheses of the colored transfer lemma, the product transfer theorem good_slopes_product_fiber_transfer again shows that each fiber has size k, and the existence of a bad unit slope b on X forces b to be bad on some fiber S.

    lines 42–77

    uses good_slopes_product_fiber_transfer, ZMod.card

    lemma good_slopes_two_row_fiber_rigidity_conditional_colored_transfer
        (k L d : ℕ) [NeZero k] {X : Type*} [Fintype X] [DecidableEq X] [Nonempty X]
        (x3 y3 : X → ZMod 3) (xk yk : X → ZMod k) (q q' : ZMod 3) (b₀ : ZMod k)
        (hcard : Fintype.card X = 3 * k)
        (hx : Function.Injective (fun x => (x3 x, xk x)))
        (hcolored : ∀ (S : Finset (ZMod k × ZMod k)) (c : (ZMod k × ZMod k) → Fin 3),
          S.card = k →
          (∀ p ∈ S, ∀ q ∈ S, c p = c q → p.1 = q.1 → p = q) →
          (∀ b : ZMod k, IsUnit b → ∀ p ∈ S, ∀ q ∈ S, c p = c 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 - 2*d)
        (hanchor : Function.Bijective (fun x => (y3 x + q*x3 x, yk x + b₀*xk x)))
        (hcomplete : ∀ b : ZMod k, IsUnit b → Function.Injective (fun x => (y3 x + q'*x3 x, yk x + b*xk x)))
        (hbad : ∃ b : ZMod k, IsUnit b ∧ ¬ Function.Injective (fun x => (y3 x + q*x3 x, yk x + b*xk x))) :
        ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b ∧ Function.Injective (fun x => (y3 x + q*x3 x, yk x + b*xk x))).card ≤ L - 2*d := by
      have hcard' : Fintype.card X = Fintype.card (ZMod 3) * Fintype.card (ZMod k) := by
        simp [hcard]
      have htransfer := good_slopes_product_fiber_transfer x3 y3 xk yk q b₀ hcard' hanchor
      rcases hbad with ⟨b, hb, hbinj⟩
      have ht_bad : ∃ t : ZMod 3, b ∉ good_slopes_point_directions k (good_slopes_product_fiber_set x3 y3 xk yk q t) := by
        by_contra h
        simp only [not_exists, not_not] at h
        have hall : ∀ t : ZMod 3, Set.InjOn (fun p : ZMod k × ZMod k => p.2 + b * p.1) (good_slopes_product_fiber_set x3 y3 xk yk q t) := by
          intro t
          have ht := h t
          unfold good_slopes_point_directions at ht
          simp only [mem_filter, mem_univ, true_and] at ht
          exact ht.2
        exact hbinj (htransfer.2.2 b hall)
      obtain ⟨t, ht⟩ := ht_bad
      set S := good_slopes_product_fiber_set x3 y3 xk yk q t
      have hScard : S.card = k := by
        have h1 := htransfer.1 t
        rw [ZMod.card] at h1
        exact h1
  5. Each point of S can be represented by a point in X, inducing a 3-coloring c(p) = x₃(rep(p)).

    Every point p in the fiber S is the image of some x in X satisfying y₃(x) + q*x₃(x) = t and (x_k(x), y_k(x)) = p. Choosing a representative rep(p) in X for each point p, we define a 3-coloring c(p) by the value of x₃(rep(p)) in Fin 3, which is well-defined by ZMod.val_lt.

    lines 78–88

    uses Finset.mem_image.mp, Finset.mem_filter, ZMod.val_lt

      have h_rep : ∀ p : ZMod k × ZMod k, ∃ x : X, p ∈ S → y3 x + q * x3 x = t ∧ (xk x, yk x) = p := by
        intro p
        by_cases hp : p ∈ S
        · obtain ⟨x, hx, rfl⟩ : ∃ x ∈ univ.filter (fun x => y3 x + q * x3 x = t), (xk x, yk x) = p := by
            exact Finset.mem_image.mp hp
          rw [Finset.mem_filter] at hx
          exact ⟨x, fun _ => ⟨hx.2, rfl⟩⟩
        · obtain ⟨x0⟩ := ‹Nonempty X›
          exact ⟨x0, fun hp' => (hp hp').elim⟩
      choose rep hrep using h_rep
      let c : (ZMod k × ZMod k) → Fin 3 := fun p => ⟨(x3 (rep p)).val, ZMod.val_lt _⟩
  6. Within each color class on S, the first coordinate is injective.

    If two points p and q_pt in S have the same color and the same first coordinate, then x₃(rep(p)) = x₃(rep(q_pt)) by ZMod.val_injective and x_k(rep(p)) = x_k(rep(q_pt)). By the assumed injectivity of (x₃, x_k) on X, rep(p) = rep(q_pt), so p = q_pt.

    lines 89–102

    uses ZMod.val_injective, Prod.ext

      have hcolor1 : ∀ p ∈ S, ∀ q ∈ S, c p = c q → p.1 = q.1 → p = q := by
        intro p hp q_pt hq_pt hc hp1
        obtain ⟨_, hp_eq⟩ := hrep p hp
        obtain ⟨_, hq_eq⟩ := hrep q_pt hq_pt
        have hc_val : (x3 (rep p)).val = (x3 (rep q_pt)).val := by
          injection hc
        have hc_eq : x3 (rep p) = x3 (rep q_pt) := ZMod.val_injective 3 hc_val
        have hxk_eq : xk (rep p) = xk (rep q_pt) := by
          rw [← hp_eq, ← hq_eq] at hp1
          exact hp1
        have hrep_eq : rep p = rep q_pt := by
          apply hx
          exact Prod.ext hc_eq hxk_eq
        rw [← hp_eq, ← hq_eq, hrep_eq]
  7. Within each color class on S, the linear form p ↦ p.2 + b'*p.1 is injective for every unit b'.

    If two points p and q_pt in S have the same color and satisfy p.2 + b'*p.1 = q_pt.2 + b'*q_pt.1, then their representatives have equal x₃ values. Since both lie on the fiber y₃ + q*x₃ = t, their y₃ values also agree, which means y₃ + q'*x₃ agrees on both. Combining this with the assumption on the second coordinate shows that both representatives evaluate to the same pair in row q' at slope b'. Because row q' is complete (injective across all unit slopes), the representatives must coincide, implying p = q_pt.

    lines 103–128

    uses ZMod.val_injective, Prod.ext

      have hcolor2 : ∀ b' : ZMod k, IsUnit b' → ∀ p ∈ S, ∀ q ∈ S, c p = c q → p.2 + b'*p.1 = q.2 + b'*q.1 → p = q := by
        intro b' hb' p hp q_pt hq_pt hc hform
        obtain ⟨ht_p, hp_eq⟩ := hrep p hp
        obtain ⟨ht_q, hq_eq⟩ := hrep q_pt hq_pt
        have hc_val : (x3 (rep p)).val = (x3 (rep q_pt)).val := by
          injection hc
        have hc_eq : x3 (rep p) = x3 (rep q_pt) := ZMod.val_injective 3 hc_val
        have hy3_eq : y3 (rep p) = y3 (rep q_pt) := by
          calc y3 (rep p) = (y3 (rep p) + q * x3 (rep p)) - q * x3 (rep p) := by ring
          _ = t - q * x3 (rep p) := by rw [ht_p]
          _ = t - q * x3 (rep q_pt) := by rw [hc_eq]
          _ = (y3 (rep q_pt) + q * x3 (rep q_pt)) - q * x3 (rep q_pt) := by rw [ht_q]
          _ = y3 (rep q_pt) := by ring
        have hrow3 : y3 (rep p) + q' * x3 (rep p) = y3 (rep q_pt) + q' * x3 (rep q_pt) := by
          rw [hy3_eq, hc_eq]
        have hp1 : p.1 = xk (rep p) := congr_arg Prod.fst hp_eq.symm
        have hp2 : p.2 = yk (rep p) := congr_arg Prod.snd hp_eq.symm
        have hq1 : q_pt.1 = xk (rep q_pt) := congr_arg Prod.fst hq_eq.symm
        have hq2 : q_pt.2 = yk (rep q_pt) := congr_arg Prod.snd hq_eq.symm
        have hrowk : yk (rep p) + b' * xk (rep p) = yk (rep q_pt) + b' * xk (rep q_pt) := by
          linear_combination hform - hp2 - b' * hp1 + hq2 + b' * hq1
        have hpair : (y3 (rep p) + q' * x3 (rep p), yk (rep p) + b' * xk (rep p)) =
                     (y3 (rep q_pt) + q' * x3 (rep q_pt), yk (rep q_pt) + b' * xk (rep q_pt)) :=
          Prod.ext hrow3 hrowk
        have hrep_eq : rep p = rep q_pt := hcomplete b' hb' hpair
        rw [← hp_eq, ← hq_eq, hrep_eq]
  8. Row q has at most L - 2d good unit slopes.

    With both coloring conditions verified on S and c, the colored fiber gap hypothesis hcolored gives that S has at most L - 2d good unit directions. Since the good unit slopes for row q embed into the good directions of S, row q has at most L - 2d good unit slopes by Finset.card_le_card.

    lines 129–137

    uses Finset.card_le_card

      have hcolored_S : (good_slopes_point_directions k S).card ≤ L - 2*d :=
        hcolored S c hScard hcolor1 hcolor2 ⟨b, hb, ht⟩
      have hsub : ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b ∧ Function.Injective (fun x => (y3 x + q*x3 x, yk x + b*xk x))) ⊆ good_slopes_point_directions k S := by
        intro b' hb'
        simp only [mem_filter, mem_univ, true_and] at hb'
        unfold good_slopes_point_directions
        simp only [mem_filter, mem_univ, true_and]
        refine ⟨hb'.1, htransfer.2.1 t b' hb'.2⟩
      exact (Finset.card_le_card hsub).trans hcolored_S
  9. For any row q, the number of good unit slopes |R(q)| is at most L.

    The set R(q) of good unit slopes in row q is a subset of all units in ZMod k, whose total number is L. Thus |R(q)| ≤ L by Finset.card_le_card and linear arithmetic.

    lines 138–149

    uses Finset.card_le_card

    theorem good_slopes_two_row_fiber_rigidity_conditional (k L d : ℕ) [NeZero k] {X : Type*} [Fintype X] [DecidableEq X] [Nonempty X] (x3 y3 : X → ZMod 3) (xk yk : X → ZMod k) (a a' : ZMod 3) (hcard : Fintype.card X = 3*k) (hx : Function.Injective (fun x => (x3 x, xk x))) (hL : ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b).card = L) (hd : 0 < d) (hLd : 2*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)) (c : (ZMod k × ZMod k) → Fin 3), S.card = k → (∀ p ∈ S, ∀ q ∈ S, c p = c q → p.1 = q.1 → p = q) → (∀ b : ZMod k, IsUnit b → ∀ p ∈ S, ∀ q ∈ S, c p = c 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-2*d) (hlarge : ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b ∧ Function.Injective (fun x => (y3 x + a*x3 x, yk x + b*xk x))).card + ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b ∧ Function.Injective (fun x => (y3 x + a'*x3 x, yk x + b*xk x))).card > 2*L-2*d) : (∀ b : ZMod k, IsUnit b → Function.Injective (fun x => (y3 x + a*x3 x, yk x + b*xk x))) ∧ (∀ b : ZMod k, IsUnit b → Function.Injective (fun x => (y3 x + a'*x3 x, yk x + b*xk x))) := by
      classical
      let R : ZMod 3 → Finset (ZMod k) := fun q => univ.filter fun b => IsUnit b ∧ Function.Injective (fun x => (y3 x + q*x3 x, yk x + b*xk x))
      have hlarge' : 2*L - 2*d < (R a).card + (R a').card := hlarge
      have hbound (q : ZMod 3) : (R q).card ≤ L := by
        have hsub : R q ⊆ univ.filter (fun b : ZMod k => IsUnit b) := by
          intro b hb
          simp only [R, mem_filter, mem_univ, true_and] at hb ⊢
          exact hb.1
        have h := Finset.card_le_card hsub
        omega
  10. Both row a and row a' have strictly positive good slopes, and each admits a bijective anchor slope.

    Since |R(a)| + |R(a')| > 2L - 2d and each row has size at most L with 2d < L, linear arithmetic implies both |R(a)| > 0 and |R(a')| > 0. Any good unit slope gives an injective map from X to ZMod 3 × ZMod k; because both sets have cardinality 3k, Fintype.bijective_iff_injective_and_card ensures that this map is bijective, providing anchor slopes b₀ and b₁.

    lines 150–159

    uses Finset.card_pos.mp, Fintype.bijective_iff_injective_and_card, Fintype.card_prod, ZMod.card

      have ha : 0 < (R a).card := by have := hbound a'; omega
      have ha' : 0 < (R a').card := by have := hbound a; omega
      have anchor (q : ZMod 3) (h : 0 < (R q).card) : ∃ b : ZMod k,
          Function.Bijective (fun x => (y3 x + q*x3 x, yk x + b*xk x)) := by
        obtain ⟨b, hb⟩ := Finset.card_pos.mp h
        simp only [R, mem_filter, mem_univ, true_and] at hb
        refine ⟨b, (Fintype.bijective_iff_injective_and_card _).2 ⟨hb.2, ?_⟩⟩
        rw [Fintype.card_prod, ZMod.card, ZMod.card, hcard]
      obtain ⟨b0, hb0⟩ := anchor a ha
      obtain ⟨b1, hb1⟩ := anchor a' ha'
  11. For any two rows q and q' with anchors whose good slopes sum to more than 2L - 2d, every unit slope in row q is injective.

    Suppose, for contradiction, that row q has a bad unit slope. By the uncolored transfer lemma, |R(q)| ≤ L - d. If row q' also had a bad unit slope, uncolored transfer would give |R(q')| ≤ L - d, leading to |R(q)| + |R(q')| ≤ 2L - 2d, a contradiction; hence row q' must be complete. But with row q' complete, the colored transfer lemma applies to row q, yielding |R(q)| ≤ L - 2d. Then |R(q)| + |R(q')| ≤ (L - 2d) + L = 2L - 2d, contradicting |R(q)| + |R(q')| > 2L - 2d. Thus row q cannot have any bad unit slope.

    lines 160–178

    uses good_slopes_two_row_fiber_rigidity_conditional_uncolored_transfer, good_slopes_two_row_fiber_rigidity_conditional_colored_transfer

      have key (q q' : ZMod 3) (c0 c1 : ZMod k)
          (hc0 : Function.Bijective (fun x => (y3 x + q*x3 x, yk x + c0*xk x)))
          (hc1 : Function.Bijective (fun x => (y3 x + q'*x3 x, yk x + c1*xk x)))
          (hl : 2*L - 2*d < (R q).card + (R q').card) :
          ∀ b : ZMod k, IsUnit b → Function.Injective (fun x => (y3 x + q*x3 x, yk x + b*xk x)) := by
        intro b hb
        by_contra hbad
        have hLd_q : (R q).card ≤ L - d :=
          good_slopes_two_row_fiber_rigidity_conditional_uncolored_transfer k L d x3 y3 xk yk q c0 hcard hgap hc0 ⟨b, hb, hbad⟩
        have hfull : ∀ d' : ZMod k, IsUnit d' → Function.Injective (fun x => (y3 x + q'*x3 x, yk x + d'*xk x)) := by
          intro d' hd'
          by_contra hbad'
          have hLd_q' : (R q').card ≤ L - d :=
            good_slopes_two_row_fiber_rigidity_conditional_uncolored_transfer k L d x3 y3 xk yk q' c1 hcard hgap hc1 ⟨d', hd', hbad'⟩
          omega
        have hL2d : (R q).card ≤ L - 2*d :=
          good_slopes_two_row_fiber_rigidity_conditional_colored_transfer k L d x3 y3 xk yk q q' c0 hcard hx hcolored hc0 hfull ⟨b, hb, hbad⟩
        have := hbound q'
        omega
  12. All unit slopes give injective coordinate maps in both row a and row a'.

    Applying the key rigidity property to (a, a') proves that all unit slopes in row a are injective, and applying it symmetrically to (a', a) proves that all unit slopes in row a' are injective.

    line 179

      exact ⟨key a a' b0 b1 hb0 hb1 hlarge', key a' a b1 b0 hb1 hb0 (by omega)⟩
good_slopes_product_fiber_transfer
For product-like coordinate maps with an anchor bijection, fiber sets have size |Z|, global injectivity implies fiber injectivity, and fiber injectivity across all fibers implies global injectivity.
ZMod.card
The cardinality of ZMod n is n for any positive integer n.
Finset.card_le_card
If s is a subset of t for finite sets s and t, then the cardinality of s is at most that of t.
Finset.mem_image.mp
An element is in the image of a set under f if and only if it is the image of some element in that set.
Finset.mem_filter
An element belongs to a filtered finset if and only if it is in the original set and satisfies the filter predicate.
ZMod.val_lt
The representative value of an element of ZMod n is strictly less than n.
ZMod.val_injective
The canonical mapping from ZMod n to the natural numbers is injective.
Prod.ext
Two ordered pairs are equal if and only if their first components are equal and their second components are equal.
Finset.card_pos.mp
A finite set has strictly positive cardinality if and only if it is nonempty.
Fintype.bijective_iff_injective_and_card
A map between two finite types of equal cardinality is bijective if and only if it is injective.
Fintype.card_prod
The cardinality of a Cartesian product is the product of the cardinalities of the two factors.
good_slopes_two_row_fiber_rigidity_conditional_uncolored_transfer
If a row has an anchor bijection and a bad unit slope, then it has at most L - d good unit slopes.
good_slopes_two_row_fiber_rigidity_conditional_colored_transfer
If a row has an anchor bijection and a bad unit slope, and another row has all unit slopes injective, then the first row has at most L - 2d good unit slopes.

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 Finsetlemma good_slopes_two_row_fiber_rigidity_conditional_uncolored_transfer    (k L d : ℕ) [NeZero k] {X : Type*} [Fintype X] [DecidableEq X]    (x3 y3 : X → ZMod 3) (xk yk : X → ZMod k) (q : ZMod 3) (b₀ : ZMod k)    (hcard : Fintype.card X = 3 * 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 => (y3 x + q*x3 x, yk x + b₀*xk x)))    (hbad : ∃ b : ZMod k, IsUnit b ∧ ¬ Function.Injective (fun x => (y3 x + q*x3 x, yk x + b*xk x))) :    ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b ∧ Function.Injective (fun x => (y3 x + q*x3 x, yk x + b*xk x))).card ≤ L - d := by  have hcard' : Fintype.card X = Fintype.card (ZMod 3) * Fintype.card (ZMod k) := by    simp [hcard]  have htransfer := good_slopes_product_fiber_transfer x3 y3 xk yk q b₀ hcard' hanchor  rcases hbad with ⟨b, hb, hbinj⟩  have ht_bad : ∃ t : ZMod 3, b ∉ good_slopes_point_directions k (good_slopes_product_fiber_set x3 y3 xk yk q t) := by    by_contra h    simp only [not_exists, not_not] at h    have hall : ∀ t : ZMod 3, Set.InjOn (fun p : ZMod k × ZMod k => p.2 + b * p.1) (good_slopes_product_fiber_set x3 y3 xk yk q t) := by      intro t      have ht := h t      unfold good_slopes_point_directions at ht      simp only [mem_filter, mem_univ, true_and] at ht      exact ht.2    exact hbinj (htransfer.2.2 b hall)  obtain ⟨t, ht⟩ := ht_bad  set S := good_slopes_product_fiber_set x3 y3 xk yk q t  have hScard : S.card = k := by    have h1 := htransfer.1 t    rw [ZMod.card] at h1    exact h1  have hgap_S : (good_slopes_point_directions k S).card ≤ L - d :=    hgap S hScard ⟨b, hb, ht⟩  have hsub : ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b ∧ Function.Injective (fun x => (y3 x + q*x3 x, yk x + b*xk x))) ⊆ good_slopes_point_directions k S := by    intro b' hb'    simp only [mem_filter, mem_univ, true_and] at hb'    unfold good_slopes_point_directions    simp only [mem_filter, mem_univ, true_and]    refine ⟨hb'.1, htransfer.2.1 t b' hb'.2⟩  exact (Finset.card_le_card hsub).trans hgap_Slemma good_slopes_two_row_fiber_rigidity_conditional_colored_transfer    (k L d : ℕ) [NeZero k] {X : Type*} [Fintype X] [DecidableEq X] [Nonempty X]    (x3 y3 : X → ZMod 3) (xk yk : X → ZMod k) (q q' : ZMod 3) (b₀ : ZMod k)    (hcard : Fintype.card X = 3 * k)    (hx : Function.Injective (fun x => (x3 x, xk x)))    (hcolored : ∀ (S : Finset (ZMod k × ZMod k)) (c : (ZMod k × ZMod k) → Fin 3),      S.card = k →      (∀ p ∈ S, ∀ q ∈ S, c p = c q → p.1 = q.1 → p = q) →      (∀ b : ZMod k, IsUnit b → ∀ p ∈ S, ∀ q ∈ S, c p = c 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 - 2*d)    (hanchor : Function.Bijective (fun x => (y3 x + q*x3 x, yk x + b₀*xk x)))    (hcomplete : ∀ b : ZMod k, IsUnit b → Function.Injective (fun x => (y3 x + q'*x3 x, yk x + b*xk x)))    (hbad : ∃ b : ZMod k, IsUnit b ∧ ¬ Function.Injective (fun x => (y3 x + q*x3 x, yk x + b*xk x))) :    ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b ∧ Function.Injective (fun x => (y3 x + q*x3 x, yk x + b*xk x))).card ≤ L - 2*d := by  have hcard' : Fintype.card X = Fintype.card (ZMod 3) * Fintype.card (ZMod k) := by    simp [hcard]  have htransfer := good_slopes_product_fiber_transfer x3 y3 xk yk q b₀ hcard' hanchor  rcases hbad with ⟨b, hb, hbinj⟩  have ht_bad : ∃ t : ZMod 3, b ∉ good_slopes_point_directions k (good_slopes_product_fiber_set x3 y3 xk yk q t) := by    by_contra h    simp only [not_exists, not_not] at h    have hall : ∀ t : ZMod 3, Set.InjOn (fun p : ZMod k × ZMod k => p.2 + b * p.1) (good_slopes_product_fiber_set x3 y3 xk yk q t) := by      intro t      have ht := h t      unfold good_slopes_point_directions at ht      simp only [mem_filter, mem_univ, true_and] at ht      exact ht.2    exact hbinj (htransfer.2.2 b hall)  obtain ⟨t, ht⟩ := ht_bad  set S := good_slopes_product_fiber_set x3 y3 xk yk q t  have hScard : S.card = k := by    have h1 := htransfer.1 t    rw [ZMod.card] at h1    exact h1  have h_rep : ∀ p : ZMod k × ZMod k, ∃ x : X, p ∈ S → y3 x + q * x3 x = t ∧ (xk x, yk x) = p := by    intro p    by_cases hp : p ∈ S    · obtain ⟨x, hx, rfl⟩ : ∃ x ∈ univ.filter (fun x => y3 x + q * x3 x = t), (xk x, yk x) = p := by        exact Finset.mem_image.mp hp      rw [Finset.mem_filter] at hx      exact ⟨x, fun _ => ⟨hx.2, rfl⟩⟩    · obtain ⟨x0⟩ := ‹Nonempty X›      exact ⟨x0, fun hp' => (hp hp').elim⟩  choose rep hrep using h_rep  let c : (ZMod k × ZMod k) → Fin 3 := fun p => ⟨(x3 (rep p)).val, ZMod.val_lt _⟩  have hcolor1 : ∀ p ∈ S, ∀ q ∈ S, c p = c q → p.1 = q.1 → p = q := by    intro p hp q_pt hq_pt hc hp1    obtain ⟨_, hp_eq⟩ := hrep p hp    obtain ⟨_, hq_eq⟩ := hrep q_pt hq_pt    have hc_val : (x3 (rep p)).val = (x3 (rep q_pt)).val := by      injection hc    have hc_eq : x3 (rep p) = x3 (rep q_pt) := ZMod.val_injective 3 hc_val    have hxk_eq : xk (rep p) = xk (rep q_pt) := by      rw [← hp_eq, ← hq_eq] at hp1      exact hp1    have hrep_eq : rep p = rep q_pt := by      apply hx      exact Prod.ext hc_eq hxk_eq    rw [← hp_eq, ← hq_eq, hrep_eq]  have hcolor2 : ∀ b' : ZMod k, IsUnit b' → ∀ p ∈ S, ∀ q ∈ S, c p = c q → p.2 + b'*p.1 = q.2 + b'*q.1 → p = q := by    intro b' hb' p hp q_pt hq_pt hc hform    obtain ⟨ht_p, hp_eq⟩ := hrep p hp    obtain ⟨ht_q, hq_eq⟩ := hrep q_pt hq_pt    have hc_val : (x3 (rep p)).val = (x3 (rep q_pt)).val := by      injection hc    have hc_eq : x3 (rep p) = x3 (rep q_pt) := ZMod.val_injective 3 hc_val    have hy3_eq : y3 (rep p) = y3 (rep q_pt) := by      calc y3 (rep p) = (y3 (rep p) + q * x3 (rep p)) - q * x3 (rep p) := by ring      _ = t - q * x3 (rep p) := by rw [ht_p]      _ = t - q * x3 (rep q_pt) := by rw [hc_eq]      _ = (y3 (rep q_pt) + q * x3 (rep q_pt)) - q * x3 (rep q_pt) := by rw [ht_q]      _ = y3 (rep q_pt) := by ring    have hrow3 : y3 (rep p) + q' * x3 (rep p) = y3 (rep q_pt) + q' * x3 (rep q_pt) := by      rw [hy3_eq, hc_eq]    have hp1 : p.1 = xk (rep p) := congr_arg Prod.fst hp_eq.symm    have hp2 : p.2 = yk (rep p) := congr_arg Prod.snd hp_eq.symm    have hq1 : q_pt.1 = xk (rep q_pt) := congr_arg Prod.fst hq_eq.symm    have hq2 : q_pt.2 = yk (rep q_pt) := congr_arg Prod.snd hq_eq.symm    have hrowk : yk (rep p) + b' * xk (rep p) = yk (rep q_pt) + b' * xk (rep q_pt) := by      linear_combination hform - hp2 - b' * hp1 + hq2 + b' * hq1    have hpair : (y3 (rep p) + q' * x3 (rep p), yk (rep p) + b' * xk (rep p)) =                 (y3 (rep q_pt) + q' * x3 (rep q_pt), yk (rep q_pt) + b' * xk (rep q_pt)) :=      Prod.ext hrow3 hrowk    have hrep_eq : rep p = rep q_pt := hcomplete b' hb' hpair    rw [← hp_eq, ← hq_eq, hrep_eq]  have hcolored_S : (good_slopes_point_directions k S).card ≤ L - 2*d :=    hcolored S c hScard hcolor1 hcolor2 ⟨b, hb, ht⟩  have hsub : ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b ∧ Function.Injective (fun x => (y3 x + q*x3 x, yk x + b*xk x))) ⊆ good_slopes_point_directions k S := by    intro b' hb'    simp only [mem_filter, mem_univ, true_and] at hb'    unfold good_slopes_point_directions    simp only [mem_filter, mem_univ, true_and]    refine ⟨hb'.1, htransfer.2.1 t b' hb'.2⟩  exact (Finset.card_le_card hsub).trans hcolored_Stheorem good_slopes_two_row_fiber_rigidity_conditional (k L d : ℕ) [NeZero k] {X : Type*} [Fintype X] [DecidableEq X] [Nonempty X] (x3 y3 : X → ZMod 3) (xk yk : X → ZMod k) (a a' : ZMod 3) (hcard : Fintype.card X = 3*k) (hx : Function.Injective (fun x => (x3 x, xk x))) (hL : ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b).card = L) (hd : 0 < d) (hLd : 2*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)) (c : (ZMod k × ZMod k) → Fin 3), S.card = k → (∀ p ∈ S, ∀ q ∈ S, c p = c q → p.1 = q.1 → p = q) → (∀ b : ZMod k, IsUnit b → ∀ p ∈ S, ∀ q ∈ S, c p = c 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-2*d) (hlarge : ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b ∧ Function.Injective (fun x => (y3 x + a*x3 x, yk x + b*xk x))).card + ((Finset.univ : Finset (ZMod k)).filter fun b => IsUnit b ∧ Function.Injective (fun x => (y3 x + a'*x3 x, yk x + b*xk x))).card > 2*L-2*d) : (∀ b : ZMod k, IsUnit b → Function.Injective (fun x => (y3 x + a*x3 x, yk x + b*xk x))) ∧ (∀ b : ZMod k, IsUnit b → Function.Injective (fun x => (y3 x + a'*x3 x, yk x + b*xk x))) := by  classical  let R : ZMod 3 → Finset (ZMod k) := fun q => univ.filter fun b => IsUnit b ∧ Function.Injective (fun x => (y3 x + q*x3 x, yk x + b*xk x))  have hlarge' : 2*L - 2*d < (R a).card + (R a').card := hlarge  have hbound (q : ZMod 3) : (R q).card ≤ L := by    have hsub : R q ⊆ univ.filter (fun b : ZMod k => IsUnit b) := by      intro b hb      simp only [R, mem_filter, mem_univ, true_and] at hb ⊢      exact hb.1    have h := Finset.card_le_card hsub    omega  have ha : 0 < (R a).card := by have := hbound a'; omega  have ha' : 0 < (R a').card := by have := hbound a; omega  have anchor (q : ZMod 3) (h : 0 < (R q).card) : ∃ b : ZMod k,      Function.Bijective (fun x => (y3 x + q*x3 x, yk x + b*xk x)) := by    obtain ⟨b, hb⟩ := Finset.card_pos.mp h    simp only [R, mem_filter, mem_univ, true_and] at hb    refine ⟨b, (Fintype.bijective_iff_injective_and_card _).2 ⟨hb.2, ?_⟩⟩    rw [Fintype.card_prod, ZMod.card, ZMod.card, hcard]  obtain ⟨b0, hb0⟩ := anchor a ha  obtain ⟨b1, hb1⟩ := anchor a' ha'  have key (q q' : ZMod 3) (c0 c1 : ZMod k)      (hc0 : Function.Bijective (fun x => (y3 x + q*x3 x, yk x + c0*xk x)))      (hc1 : Function.Bijective (fun x => (y3 x + q'*x3 x, yk x + c1*xk x)))      (hl : 2*L - 2*d < (R q).card + (R q').card) :      ∀ b : ZMod k, IsUnit b → Function.Injective (fun x => (y3 x + q*x3 x, yk x + b*xk x)) := by    intro b hb    by_contra hbad    have hLd_q : (R q).card ≤ L - d :=      good_slopes_two_row_fiber_rigidity_conditional_uncolored_transfer k L d x3 y3 xk yk q c0 hcard hgap hc0 ⟨b, hb, hbad⟩    have hfull : ∀ d' : ZMod k, IsUnit d' → Function.Injective (fun x => (y3 x + q'*x3 x, yk x + d'*xk x)) := by      intro d' hd'      by_contra hbad'      have hLd_q' : (R q').card ≤ L - d :=        good_slopes_two_row_fiber_rigidity_conditional_uncolored_transfer k L d x3 y3 xk yk q' c1 hcard hgap hc1 ⟨d', hd', hbad'⟩      omega    have hL2d : (R q).card ≤ L - 2*d :=      good_slopes_two_row_fiber_rigidity_conditional_colored_transfer k L d x3 y3 xk yk q q' c0 hcard hx hcolored hc0 hfull ⟨b, hb, hbad⟩    have := hbound q'    omega  exact ⟨key a a' b0 b1 hb0 hb1 hlarge', key a' a b1 b0 hb1 hb0 (by omega)⟩
See it in the graphDiscuss this resultChallenge it