difference_squares_avoiding_gp3_bounds
Let $p \ge 7$ be a prime and let $A \subset \mathbb{F}_p$ be nonempty. If the set of squared differences $(A - A)^2$ contains no nondegenerate three-term geometric progression, then $|A|^3 \le p^2$, $|A - A| \ge |A|^{5/4}$, and for every $t \in \mathbb{F}_p^\times$ with $t^4 \neq 1$ and every $s \in \mathbb{F}_p$, $|\{(a, b) \in A^2 : b - t a = s\}| \le p / |A|$.
Statement
open scoped Pointwise in theorem difference_squares_avoiding_gp3_bounds (p : ℕ) [Fact p.Prime] (hp : 7 ≤ p) (A : Finset (ZMod p)) (hA : A.Nonempty) (hGP : ¬ has_nondegenerate_gp3 (diff_squares A : Set (ZMod p))) : A.card ^ 3 ≤ p ^ 2 ∧ (A.card : ℝ) ^ (5 / 4 : ℝ) ≤ ((A - A).card : ℝ) ∧ ∀ (t : ZMod p), t ≠ 0 → t ^ 4 ≠ 1 → ∀ (s : ZMod p), (((A ×ˢ A).filter (fun (a, b) => b - t * a = s)).card : ℝ) ≤ (p : ℝ) / (A.card : ℝ)
- Formalizes
- arXiv:2610.34758 Lemma 3.1
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- has_nondegenerate_gp3A set $D$ in a commutative ring contains a nondegenerate three-term geometric progression if there exist $x, r$ with $x \neq 0$,…
- diff_squaresThe set of squared differences of a finite subset $A$ in a commutative ring is $(A - A)^2 = \{(a - b)^2 : a, b \in A\}$.
- two_pow_four_ne_one_of_prime_ge_sevenFor every prime $p \ge 7$, $2^4 \ne 1$ in $\mathbb{Z}/p\mathbb{Z}$.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
Read back from the Lean
For any prime number $p \ge 7$ and any nonempty finite subset $A \subseteq \mathbb{Z}/p\mathbb{Z}$, if the set of squared differences of elements of $A$ contains no nondegenerate 3-term geometric progression (that is, there do not exist $x, r \in \mathbb{Z}/p\mathbb{Z}$ with $x \ne 0$, $r \ne 0$, and $r^2 \ne 1$ such that $x$, $x r$, and $x r^2$ are all in $\{(a - b)^2 \mid a, b \in A\}$), then: 1. $|A|^3 \le p^2$ (as natural numbers); 2. $|A|^{5/4} \le |A - A|$ (as real numbers, where $A - A = \{a - b \mid a \in A, b \in A\}$ is the pointwise difference set); and 3. For all $t \in \mathbb{Z}/p\mathbb{Z}$ with $t \ne 0$ and $t^4 \ne 1$, and for all $s \in \mathbb{Z}/p\mathbb{Z}$, the number of pairs $(a, b) \in A \times A$ satisfying $b - t a = s$ is at most $p / |A|$ (as real numbers).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
Let p >= 7 be prime and A a subset of F_p whose difference squares avoid nondegenerate 3-term geometric progressions. The map (a,b,c) to (b - ta, c - tb) is injective for t != 0 and t^4 != 1, since equal images would produce a 3-term GP of ratio t^2 in (A - A)^2. Setting t = 2 gives |A|^3 <= p^2 by mapping A^3 to F_p^2, and combining this injectivity on A x X^2 with the Plunnecke-Petridis inequality gives |A|^(5/4) <= |A - A|. Finally, fixing b - ta = s makes c to c - tb injective, yielding the line intersection bound.
2 is nonzero in ZMod p for p at least 7 automation
If 2 = 0 in ZMod p, then p divides 2, so p <= 2, contradicting p >= 7.
uses
ZMod.natCast_eq_zero_iff,Nat.le_of_dvdintro h have h1 : ((2 : ℕ) : ZMod p) = 0 := h rw [ZMod.natCast_eq_zero_iff] at h1 have : p ≤ 2 := Nat.le_of_dvd (by norm_num) h1 omega
ZMod.natCast_eq_zero_iff- In ZMod n, the cast of a natural number a is zero iff n divides a
Nat.le_of_dvd- If m divides a positive integer n, then m is at most n
- Unresolved check: no step explains line(s) 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36 -- every tactic of the proof has to belong to some step
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.
lemma difference_squares_avoiding_gp3_two_ne_zero (p : ℕ) [Fact p.Prime] (hp : 7 ≤ p) : (2 : ZMod p) ≠ 0 := by intro h have h1 : ((2 : ℕ) : ZMod p) = 0 := h rw [ZMod.natCast_eq_zero_iff] at h1 have : p ≤ 2 := Nat.le_of_dvd (by norm_num) h1 omegalemma difference_squares_avoiding_gp3_phi_inj {p : ℕ} [Fact p.Prime] {A : Finset (ZMod p)} (hGP : ¬ has_nondegenerate_gp3 (diff_squares A : Set (ZMod p))) {t : ZMod p} (ht0 : t ≠ 0) (ht4 : t ^ 4 ≠ 1) {a b c a' b' c' : ZMod p} (ha : a ∈ A) (hb : b ∈ A) (hc : c ∈ A) (ha' : a' ∈ A) (hb' : b' ∈ A) (hc' : c' ∈ A) (h1 : b - t * a = b' - t * a') (h2 : c - t * b = c' - t * b') : a = a' ∧ b = b' ∧ c = c' := by have hbb : b - b' = t * (a - a') := by linear_combination h1 have hcc : c - c' = t ^ 2 * (a - a') := by calc c - c' = t * (b - b') := by linear_combination h2 _ = t * (t * (a - a')) := by rw [hbb] _ = t ^ 2 * (a - a') := by ring by_cases haa : a = a' · subst haa have hb_eq : b = b' := by have : b - b' = 0 := by rw [hbb, sub_self, mul_zero] exact sub_eq_zero.mp this subst hb_eq have hc_eq : c = c' := by have : c - c' = 0 := by rw [hcc, sub_self, mul_zero] exact sub_eq_zero.mp this exact ⟨rfl, rfl, hc_eq⟩ · exfalso apply hGP refine ⟨(a - a') ^ 2, t ^ 2, ?_, ?_, ?_, ?_, ?_, ?_⟩ · intro h0 have : a - a' = 0 := sq_eq_zero_iff.mp h0 exact haa (sub_eq_zero.mp this) · intro ht2 apply ht0 exact sq_eq_zero_iff.mp ht2 · intro hr2 apply ht4 calc t ^ 4 = (t ^ 2) ^ 2 := by ring _ = 1 := hr2 · rw [diff_squares, Finset.mem_coe, Finset.mem_image] exact ⟨(a, a'), Finset.mem_product.mpr ⟨ha, ha'⟩, rfl⟩ · rw [diff_squares, Finset.mem_coe, Finset.mem_image] refine ⟨(b, b'), Finset.mem_product.mpr ⟨hb, hb'⟩, ?_⟩ dsimp rw [hbb] ring · rw [diff_squares, Finset.mem_coe, Finset.mem_image] refine ⟨(c, c'), Finset.mem_product.mpr ⟨hc, hc'⟩, ?_⟩ dsimp rw [hcc] ringopen scoped Pointwise inlemma difference_squares_avoiding_gp3_pluennecke_petridis {G : Type*} [DecidableEq G] [AddCommGroup G] {A : Finset G} (hA : A.Nonempty) : ∃ X : Finset G, X.Nonempty ∧ X ⊆ A ∧ (X - A - A).card * A.card ^ 2 ≤ (A - A).card ^ 2 * X.card := by have hA' : A ∈ A.powerset.erase ∅ := Finset.mem_erase_of_ne_of_mem hA.ne_empty (Finset.mem_powerset_self _) obtain ⟨X, hXmem, hXmin⟩ := Finset.exists_min_image (A.powerset.erase ∅) (fun C ↦ ((C + (-A)).card : ℚ≥0) / C.card) ⟨A, hA'⟩ rw [Finset.mem_erase, Finset.mem_powerset, ← Finset.nonempty_iff_ne_empty] at hXmem obtain ⟨hXnonempty, hXA⟩ := hXmem refine ⟨X, hXnonempty, hXA, ?_⟩ have hXratio : ∀ X' ⊆ X, (X + -A).card * X'.card ≤ (X' + -A).card * X.card := by intro X' hX'X by_cases hX'empty : X' = ∅ · rw [hX'empty, Finset.card_empty, mul_zero] exact Nat.zero_le _ · have hX'mem : X' ∈ A.powerset.erase ∅ := by rw [Finset.mem_erase, Finset.mem_powerset] exact ⟨hX'empty, hX'X.trans hXA⟩ have hle := hXmin X' hX'mem have hX_pos : (0 : ℚ≥0) < X.card := Nat.cast_pos.mpr (Finset.card_pos.mpr hXnonempty) have hX'_pos : (0 : ℚ≥0) < X'.card := Nat.cast_pos.mpr (Finset.card_pos.mpr (Finset.nonempty_iff_ne_empty.mpr hX'empty)) rw [div_le_div_iff₀ hX_pos hX'_pos] at hle exact_mod_cast hle have h_pp := Finset.pluennecke_petridis_inequality_add (-A) hXratio have h_min_A := hXmin A hA' have hX_pos : (0 : ℚ≥0) < X.card := Nat.cast_pos.mpr (Finset.card_pos.mpr hXnonempty) have hA_pos : (0 : ℚ≥0) < A.card := Nat.cast_pos.mpr (Finset.card_pos.mpr hA) rw [div_le_div_iff₀ hX_pos hA_pos] at h_min_A have h_bound : (X + -A).card * A.card ≤ (A + -A).card * X.card := by exact_mod_cast h_min_A have h_rew : -A + X + -A = X - A - A := by rw [add_comm (-A) X, ← sub_eq_add_neg, ← sub_eq_add_neg] have h_rew2 : -A + X = X - A := by rw [add_comm, ← sub_eq_add_neg] have h_rew3 : X + -A = X - A := by rw [← sub_eq_add_neg] have h_rew4 : A + -A = A - A := by rw [← sub_eq_add_neg] rw [h_rew, h_rew2, h_rew3] at h_pp rw [h_rew3, h_rew4] at h_bound have hXcard_pos : 0 < X.card := Finset.card_pos.mpr hXnonempty have h1 : (X - A - A).card * X.card * A.card ^ 2 ≤ (X - A).card ^ 2 * A.card ^ 2 := by calc (X - A - A).card * X.card * A.card ^ 2 _ = ((X - A - A).card * X.card) * A.card ^ 2 := by ring _ ≤ ((X - A).card * (X - A).card) * A.card ^ 2 := by gcongr _ = (X - A).card ^ 2 * A.card ^ 2 := by ring have h2 : (X - A).card ^ 2 * A.card ^ 2 = ((X - A).card * A.card) ^ 2 := by ring have h3 : ((X - A).card * A.card) ^ 2 ≤ ((A - A).card * X.card) ^ 2 := by exact Nat.pow_le_pow_left h_bound 2 have h4 : ((A - A).card * X.card) ^ 2 = (A - A).card ^ 2 * X.card * X.card := by ring have h5 : (X - A - A).card * A.card ^ 2 * X.card ≤ (A - A).card ^ 2 * X.card * X.card := by calc (X - A - A).card * A.card ^ 2 * X.card _ = (X - A - A).card * X.card * A.card ^ 2 := by ring _ ≤ (X - A).card ^ 2 * A.card ^ 2 := h1 _ = ((X - A).card * A.card) ^ 2 := h2 _ ≤ ((A - A).card * X.card) ^ 2 := h3 _ = (A - A).card ^ 2 * X.card * X.card := h4 exact Nat.le_of_mul_le_mul_right h5 hXcard_poslemma difference_squares_avoiding_gp3_real_pow {a b : ℕ} (h : a ^ 5 ≤ b ^ 4) : (a : ℝ) ^ (5 / 4 : ℝ) ≤ (b : ℝ) := by have ha : 0 ≤ (a : ℝ) := Nat.cast_nonneg a have hb : 0 ≤ (b : ℝ) := Nat.cast_nonneg b by_cases ha0 : a = 0 · subst ha0 simp have h_cast : (a : ℝ) ^ 5 ≤ (b : ℝ) ^ 4 := by exact_mod_cast h have h_cast' : (a : ℝ) ^ ((5 : ℕ) : ℝ) ≤ (b : ℝ) ^ ((4 : ℕ) : ℝ) := by rw [Real.rpow_natCast, Real.rpow_natCast] exact h_cast have h1 : ((a : ℝ) ^ ((5 : ℕ) : ℝ)) ^ ((1 : ℝ) / 4) ≤ ((b : ℝ) ^ ((4 : ℕ) : ℝ)) ^ ((1 : ℝ) / 4) := by exact Real.rpow_le_rpow (by positivity) h_cast' (by norm_num) rw [← Real.rpow_mul ha, ← Real.rpow_mul hb] at h1 have h5 : ((5 : ℕ) : ℝ) * (1 / 4) = 5 / 4 := by norm_num have h4 : ((4 : ℕ) : ℝ) * (1 / 4) = 1 := by norm_num rw [h5, h4, Real.rpow_one] at h1 exact h1open scoped Pointwise in/-- Injectivity and size bounds for sets avoiding geometric progressions in difference squares (Lemma 3.1). -/theorem difference_squares_avoiding_gp3_bounds (p : ℕ) [Fact p.Prime] (hp : 7 ≤ p) (A : Finset (ZMod p)) (hA : A.Nonempty) (hGP : ¬ has_nondegenerate_gp3 (diff_squares A : Set (ZMod p))) : A.card ^ 3 ≤ p ^ 2 ∧ (A.card : ℝ) ^ (5 / 4 : ℝ) ≤ ((A - A).card : ℝ) ∧ ∀ (t : ZMod p), t ≠ 0 → t ^ 4 ≠ 1 → ∀ (s : ZMod p), (((A ×ˢ A).filter (fun (a, b) => b - t * a = s)).card : ℝ) ≤ (p : ℝ) / (A.card : ℝ) := by have ht0 : (2 : ZMod p) ≠ 0 := difference_squares_avoiding_gp3_two_ne_zero p hp have ht4 : (2 : ZMod p) ^ 4 ≠ 1 := two_pow_four_ne_one_of_prime_ge_seven p hp refine ⟨?_, ?_, ?_⟩ · let f : (ZMod p × (ZMod p × ZMod p)) → ZMod p × ZMod p := fun ⟨a, b, c⟩ => (b - 2 * a, c - 2 * b) have h_inj : Set.InjOn f ((A ×ˢ (A ×ˢ A) : Finset _) : Set _) := by rintro ⟨a, b, c⟩ hx ⟨a', b', c'⟩ hy heq rw [Finset.coe_product, Finset.coe_product, Set.mem_prod, Set.mem_prod] at hx hy obtain ⟨ha, hb, hc⟩ := hx obtain ⟨ha', hb', hc'⟩ := hy rw [Finset.mem_coe] at ha hb hc ha' hb' hc' injection heq with h1 h2 obtain ⟨rfl, rfl, rfl⟩ := difference_squares_avoiding_gp3_phi_inj hGP ht0 ht4 ha hb hc ha' hb' hc' h1 h2 rfl have h_maps : Set.MapsTo f ((A ×ˢ (A ×ˢ A) : Finset _) : Set _) ↑(Finset.univ : Finset (ZMod p × ZMod p)) := by intro x _ simp have h_card := Finset.card_le_card_of_injOn f h_maps h_inj rw [Finset.card_product, Finset.card_product] at h_card have h_univ : (Finset.univ : Finset (ZMod p × ZMod p)).card = p ^ 2 := by simp [sq] rw [h_univ] at h_card calc A.card ^ 3 = A.card * (A.card * A.card) := by ring _ ≤ p ^ 2 := h_card · obtain ⟨X, hXnonempty, hXA, h_pp⟩ := difference_squares_avoiding_gp3_pluennecke_petridis hA let f : (ZMod p × (ZMod p × ZMod p)) → ZMod p × ZMod p := fun ⟨a, b, c⟩ => (b - 2 * a, c - 2 * b) let S := A ×ˢ (X ×ˢ X) let T := (X - A - A) ×ˢ (X - A - A) have h_maps : Set.MapsTo f (S : Set _) (T : Set _) := by rintro ⟨a, x1, x2⟩ h rw [Finset.coe_product, Finset.coe_product, Set.mem_prod, Set.mem_prod] at h obtain ⟨ha, hx1, hx2⟩ := h rw [Finset.mem_coe] at ha hx1 hx2 rw [Finset.coe_product, Set.mem_prod, Finset.mem_coe, Finset.mem_coe] have h1 : x1 - 2 * a ∈ X - A - A := by have : 2 * a = a + a := by ring rw [this, ← sub_sub] exact Finset.sub_mem_sub (Finset.sub_mem_sub hx1 ha) ha have h2 : x2 - 2 * x1 ∈ X - A - A := by have : 2 * x1 = x1 + x1 := by ring rw [this, ← sub_sub] exact Finset.sub_mem_sub (Finset.sub_mem_sub hx2 (hXA hx1)) (hXA hx1) exact ⟨h1, h2⟩ have h_inj : Set.InjOn f (S : Set _) := by rintro ⟨a, b, c⟩ hx ⟨a', b', c'⟩ hy heq rw [Finset.coe_product, Finset.coe_product, Set.mem_prod, Set.mem_prod] at hx hy obtain ⟨ha, hb, hc⟩ := hx obtain ⟨ha', hb', hc'⟩ := hy rw [Finset.mem_coe] at ha hb hc ha' hb' hc' injection heq with h1 h2 obtain ⟨rfl, rfl, rfl⟩ := difference_squares_avoiding_gp3_phi_inj hGP ht0 ht4 ha (hXA hb) (hXA hc) ha' (hXA hb') (hXA hc') h1 h2 rfl have h_card := Finset.card_le_card_of_injOn f h_maps h_inj rw [Finset.card_product, Finset.card_product, Finset.card_product] at h_card have h_inj_bound : A.card * X.card ^ 2 ≤ (X - A - A).card ^ 2 := by calc A.card * X.card ^ 2 _ = A.card * (X.card * X.card) := by ring _ ≤ (X - A - A).card * (X - A - A).card := h_card _ = (X - A - A).card ^ 2 := by ring have hX_pos : 0 < X.card := Finset.card_pos.mpr hXnonempty have hX2_pos : 0 < X.card ^ 2 := Nat.pos_of_ne_zero (pow_ne_zero 2 (ne_of_gt hX_pos)) have h1 : A.card ^ 5 * X.card ^ 2 ≤ (X - A - A).card ^ 2 * A.card ^ 4 := by calc A.card ^ 5 * X.card ^ 2 _ = (A.card * X.card ^ 2) * A.card ^ 4 := by ring _ ≤ (X - A - A).card ^ 2 * A.card ^ 4 := Nat.mul_le_mul_right (A.card ^ 4) h_inj_bound have h2 : (X - A - A).card ^ 2 * A.card ^ 4 = ((X - A - A).card * A.card ^ 2) ^ 2 := by ring have h3 : ((X - A - A).card * A.card ^ 2) ^ 2 ≤ ((A - A).card ^ 2 * X.card) ^ 2 := by exact Nat.pow_le_pow_left h_pp 2 have h4 : ((A - A).card ^ 2 * X.card) ^ 2 = (A - A).card ^ 4 * X.card ^ 2 := by rw [mul_pow, ← pow_mul] have h5 : A.card ^ 5 * X.card ^ 2 ≤ (A - A).card ^ 4 * X.card ^ 2 := by calc A.card ^ 5 * X.card ^ 2 _ ≤ (X - A - A).card ^ 2 * A.card ^ 4 := h1 _ = ((X - A - A).card * A.card ^ 2) ^ 2 := h2 _ ≤ ((A - A).card ^ 2 * X.card) ^ 2 := h3 _ = (A - A).card ^ 4 * X.card ^ 2 := h4 have h_pow : A.card ^ 5 ≤ (A - A).card ^ 4 := Nat.le_of_mul_le_mul_right h5 hX2_pos exact difference_squares_avoiding_gp3_real_pow h_pow · intro t ht0 ht4 s let Fs := (A ×ˢ A).filter (fun (a, b) => b - t * a = s) let g : (ZMod p × ZMod p) × ZMod p → ZMod p := fun ⟨⟨a, b⟩, c⟩ => c - t * b have h_inj : Set.InjOn g ((Fs ×ˢ A : Finset _) : Set _) := by rintro ⟨⟨a, b⟩, c⟩ hx ⟨⟨a', b'⟩, c'⟩ hy heq rw [Finset.coe_product, Set.mem_prod, Finset.mem_coe, Finset.mem_filter, Finset.mem_product] at hx hy obtain ⟨⟨⟨ha, hb⟩, hs⟩, hc⟩ := hx obtain ⟨⟨⟨ha', hb'⟩, hs'⟩, hc'⟩ := hy dsimp [g] at heq have h1 : b - t * a = b' - t * a' := by rw [hs, hs'] obtain ⟨rfl, rfl, rfl⟩ := difference_squares_avoiding_gp3_phi_inj hGP ht0 ht4 ha hb hc ha' hb' hc' h1 heq rfl have h_maps : Set.MapsTo g ((Fs ×ˢ A : Finset _) : Set _) ↑(Finset.univ : Finset (ZMod p)) := by intro x _ simp have h_card := Finset.card_le_card_of_injOn g h_maps h_inj rw [Finset.card_product] at h_card have h_univ : (Finset.univ : Finset (ZMod p)).card = p := ZMod.card p rw [h_univ] at h_card have hA_pos : 0 < (A.card : ℝ) := Nat.cast_pos.mpr (Finset.card_pos.mpr hA) have h_cast : (Fs.card : ℝ) * (A.card : ℝ) ≤ (p : ℝ) := by exact_mod_cast h_card exact (le_div_iff₀ hA_pos).mpr h_cast