good_slopes_many_row_fiber_rigidity_conditional
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
- good_slopes_point_directionsThe unit directions a for which the linear form y + a x is injective on a finite set of points over the residues modulo n.
- good_slopes_product_fiber_transferFor a bijective anchor direction on a product, each projected fiber has the size of the second factor. Good directions with the same first…
- good_slopes_product_fiber_setThe set of projected point pairs over Z obtained by fixing the Y-coordinate of y + a x.
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.
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.
uses
ZMod.card,good_slopes_product_fiber_transferclassical 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
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.
uses
ZMod.card,good_slopes_point_directions,Finset.mem_filter,Finset.mem_univ,true_andhave 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
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.
uses
le_trans,Finset.card_le_card,Finset.mem_filter,Finset.mem_univ,true_and,good_slopes_point_directionsrefine 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⟩
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.
uses
ZMod.card,good_slopes_product_fiber_transferclassical 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
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.
uses
good_slopes_product_fiber_set,Finset.mem_image,Finset.mem_filter,Finset.mem_univ,true_and,dif_pos,ZMod.cardhave 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
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.
uses
Prod.exthave 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]
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.
uses
add_right_cancel,Prod.exthave 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]
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.
uses
good_slopes_point_directions,Finset.mem_filter,Finset.mem_univ,true_and,le_trans,Finset.card_le_cardhave 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⟩
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.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.card_le_cardclassical 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
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.
uses
Finset.mem_filter,Finset.mem_univ,true_andintro 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
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.
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_lehave 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 _)
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.
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_emptyhave 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
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.
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_irreflhave 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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 _)