good_slopes_two_row_fiber_rigidity_conditional
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
- 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.
- Used by 1
- good_slopes_gap_three_coprime_from_fiber_boundsLet k be a nonzero natural number coprime to 3 and let f be a non-extremal permutation modulo 3k. Suppose there are L units modulo k and 0…
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.
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.
uses
good_slopes_product_fiber_transferhave 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
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.
uses
ZMod.cardset 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⟩
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.
uses
Finset.card_le_cardhave 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
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.
uses
good_slopes_product_fiber_transfer,ZMod.cardlemma 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
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.
uses
Finset.mem_image.mp,Finset.mem_filter,ZMod.val_lthave 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 _⟩
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.
uses
ZMod.val_injective,Prod.exthave 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]
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.
uses
ZMod.val_injective,Prod.exthave 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]
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.
uses
Finset.card_le_cardhave 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
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.
uses
Finset.card_le_cardtheorem 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
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₁.
uses
Finset.card_pos.mp,Fintype.bijective_iff_injective_and_card,Fintype.card_prod,ZMod.cardhave 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'
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.
uses
good_slopes_two_row_fiber_rigidity_conditional_uncolored_transfer,good_slopes_two_row_fiber_rigidity_conditional_colored_transferhave 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
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.
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.
- The proof is organised into two transfer lemmas (uncolored and colored) connecting fiber directions in (ZMod k)^2 to row slopes on X, followed by the main rigidity theorem. Presburger arithmetic is handled by the `omega` tactic to close cardinality contradictions.
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.
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)⟩