isotropic_intersection_size_bound
Let A ⊂ ℝ^d be a finite, non-empty set in isotropic position (so that ∑_{a ∈ A} a = 0 and ∑_{a ∈ A} (a · u)^2 = |A| ‖u‖^2 for all u ∈ ℝ^d), and let v ∈ ℝ^d be non-zero. Then |A ∩ (v + A)| ≤ 2|A| / ‖v‖^2.
Statement
open scoped Pointwise in theorem isotropic_intersection_size_bound (d : ℕ) (A : Finset (EuclideanSpace ℝ (Fin d))) (h_nonempty : A.Nonempty) (h_mean : ∑ a ∈ A, a = 0) (h_cov : ∀ u : EuclideanSpace ℝ (Fin d), ∑ a ∈ A, (inner (𝕜 := ℝ) a u) ^ 2 = (A.card : ℝ) * ‖u‖ ^ 2) (v : EuclideanSpace ℝ (Fin d)) (hv : v ≠ 0) : ((A ∩ (v +ᵥ A)).card : ℝ) ≤ 2 * (A.card : ℝ) / ‖v‖ ^ 2
- Formalizes
- arXiv:2611.04644 Lemma A.4 -- Additive energy, Freiman's lemma, and an edge-isoperimetric problem on the boolean cube
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- is_isotropic_positionA finite, nonempty subset A of ℝ^d is in isotropic position if (1/|A|) ∑_{a ∈ A} a = 0 and (1/|A|) ∑_{a ∈ A} (a · v)^2 = ‖v‖^2 for all v ∈…
- sum_range_sq_add_geFor any natural number m and any real number t, the sum of (t + k)^2 for k from 0 to m - 1 is at least (1/12) m (m^2 - 1).
- isotropic_chain_cubic_ineqFor every natural number m, m - 1 ≤ (1/6) m (m^2 - 1).
Read back from the Lean
For any natural number $d$ and any finite subset $A$ of the Euclidean space $\mathbb{R}^d$ (formalized as EuclideanSpace ℝ (Fin d)), assuming:
1. $A$ is non-empty (A.Nonempty),
2. the sum of all elements in $A$ is the zero vector ($\sum_{a \in A} a = 0$),
3. $A$ is in isotropic position, in the sense that for every vector $u \in \mathbb{R}^d$, $\sum_{a \in A} \langle a, u \rangle^2 = |A| \, \|u\|^2$, and
4. $v \in \mathbb{R}^d$ is a non-zero vector ($v \neq 0$),
the cardinality of the intersection $A \cap (v + A)$ (where $v + A = \{v + a \mid a \in A\}$) is at most $\frac{2 |A|}{\|v\|^2}$.
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
The proof decomposes the finite set A into maximal arithmetic progressions (chains) with common difference v, each starting at a representative r where r - v ∉ A. For a chain of length M + 1, exactly M points shift back into A upon subtracting v, so the intersection size |A ∩ (v + A)| equals the sum of chain lengths ∑ M. Along each chain, the sum of squared inner products with v is bounded below by (1/2) M ‖v‖⁴ using the discrete variance inequality for arithmetic progressions. Summing over all chains and applying the isotropic covariance assumption ∑_{a ∈ A} ⟨a, v⟩² = |A| ‖v‖² yields (1/2) ‖v‖⁴ |A ∩ (v + A)| ≤ |A| ‖v‖², which simplifies to |A ∩ (v + A)| ≤ 2|A| / ‖v‖² upon dividing by ‖v‖².
Subtracting r • v and then s • v equals subtracting (r + s) • v
Distribute the scalar multiplication over addition using add_smul and simplify with abelian group normalization (abel).
uses
add_smulrw [add_smul]; abelMultiples of a non-zero vector by distinct natural numbers are distinct: if i • v = j • v then i = j
Rewriting the equality as (i - j) • v = 0 with sub_smul, the fact that v ≠ 0 forces the real scalar i - j to be zero. Injectivity of the cast from ℕ to ℝ (Nat.cast_injective) then gives i = j.
uses
sub_smul,Nat.cast_injectivehave h3 : (((i : ℝ)) - ((j : ℝ))) • v = 0 := by rw [sub_smul]; exact sub_eq_zero.mpr h rcases smul_eq_zero.mp h3 with h4 | h4 · have h5 : (i : ℝ) = (j : ℝ) := by linarith exact Nat.cast_injective h5 · exact absurd h4 hv
Repeatedly subtracting v from any element a ∈ A eventually leaves the finite set A
Assuming the contrary, every point a - (k+1) • v for k ∈ ℕ would belong to A. The map k ↦ a - (k+1) • v is injective because v ≠ 0, producing an infinite subset inside the finite set A, which is a contradiction.
uses
sub_eq_add_neg,add_left_cancel,neg_injective,sub_smul,Nat.cast_injective,Set.Infinite.mono,Set.infinite_range_of_injectiveby_contra hcon simp only [not_exists, not_not] at hcon have hinj : Function.Injective (fun k : ℕ => a - ((k : ℝ) + 1) • v) := by intro k l hkl have hkl' : a - ((k : ℝ) + 1) • v = a - ((l : ℝ) + 1) • v := hkl have h1 : -(((k : ℝ) + 1) • v) = -(((l : ℝ) + 1) • v) := by rw [sub_eq_add_neg, sub_eq_add_neg] at hkl' exact add_left_cancel hkl' have h2 : ((k : ℝ) + 1) • v = ((l : ℝ) + 1) • v := neg_injective h1 have h3 : (((k : ℝ) + 1) - ((l : ℝ) + 1)) • v = 0 := by rw [sub_smul] exact sub_eq_zero.mpr h2 rcases smul_eq_zero.mp h3 with h4 | h4 · have h5 : (k : ℝ) = (l : ℝ) := by linarith exact Nat.cast_injective h5 · exact absurd h4 hv have hsub : Set.range (fun k : ℕ => a - ((k : ℝ) + 1) • v) ⊆ (A : Set V) := by rintro x ⟨k, rfl⟩ exact hcon k exact (Set.Infinite.mono hsub (Set.infinite_range_of_injective hinj)) A.finite_toSet
Define the chain step count, base representative, chain fibers, and the set of chain starts
For each a ∈ A, define chainK(a) as the minimal natural number k such that a - (k+1) • v ∉ A using Nat.find, and chainRep(a) = a - chainK(a) • v as the starting point of its chain. A chain is defined as the fiber of points sharing the same representative, and chainStarts is the set of all such base points.
uses
Nat.findclassical exact if h : ∃ k : ℕ, a - ((k : ℝ) + 1) • v ∉ A then Nat.find h else 0 /-- The first point of the `v`-chain through `a`. -/ noncomputable def isotropic_intersection_size_bound_chainRep (A : Finset V) (v : V) (a : V) : V := by classical exact a - (isotropic_intersection_size_bound_chainK A v a : ℝ) • v /-- The `v`-chain of `A` starting at `r`. -/ noncomputable def isotropic_intersection_size_bound_chain (A : Finset V) (v : V) (r : V) : Finset V := by classical exact A.filter (fun b => isotropic_intersection_size_bound_chainRep A v b = r) /-- The index of the top point of the chain starting at `r`. -/ noncomputable def isotropic_intersection_size_bound_chainLen (A : Finset V) (v : V) (r : V) : ℕ := (isotropic_intersection_size_bound_chain A v r).sup (isotropic_intersection_size_bound_chainK A v) /-- The set of chain starts of `A` in direction `v`. -/ noncomputable def isotropic_intersection_size_bound_chainStarts (A : Finset V) (v : V) : Finset V := by classical exact A.image (isotropic_intersection_size_bound_chainRep A v)
Characterize chainK(a) as the boundary index where stepping backwards along v leaves A
By the properties of Nat.find, a - (chainK(a) + 1) • v ∉ A, while any strictly smaller step count stays in A (Nat.find_min). Moreover, any index whose backward step leaves A must be at least chainK(a) (Nat.find_min').
uses
isotropic_intersection_size_bound_back_exists,dif_pos,Nat.find_spec,Nat.find_min,Nat.find_min'classical simp [isotropic_intersection_size_bound_chain] lemma isotropic_intersection_size_bound_chainK_spec (hv : v ≠ 0) (a : V) (ha : a ∈ A) : a - ((isotropic_intersection_size_bound_chainK A v a : ℝ) + 1) • v ∉ A := by classical have h := isotropic_intersection_size_bound_back_exists A v hv a ha have hfind : isotropic_intersection_size_bound_chainK A v a = Nat.find h := dif_pos h rw [hfind] exact Nat.find_spec h lemma isotropic_intersection_size_bound_chainK_min (hv : v ≠ 0) {a : V} (ha : a ∈ A) {j : ℕ} (hj : j < isotropic_intersection_size_bound_chainK A v a) : a - ((j : ℝ) + 1) • v ∈ A := by classical by_contra hmem have h := isotropic_intersection_size_bound_back_exists A v hv a ha have hfind : isotropic_intersection_size_bound_chainK A v a = Nat.find h := dif_pos h exact (Nat.find_min h (hfind ▸ hj)) hmem lemma isotropic_intersection_size_bound_chainK_le (hv : v ≠ 0) {a : V} (ha : a ∈ A) {j : ℕ} (hj : a - ((j : ℝ) + 1) • v ∉ A) : isotropic_intersection_size_bound_chainK A v a ≤ j := by classical have h := isotropic_intersection_size_bound_back_exists A v hv a ha have hfind : isotropic_intersection_size_bound_chainK A v a = Nat.find h := dif_pos h rw [hfind] exact Nat.find_min' h hj
Points along the backward chain stay in A, with chainRep(a) ∈ A but chainRep(a) - v ∉ A
By induction on l ≤ chainK(a), the minimality of chainK ensures that a - l • v ∈ A. In particular, the representative chainRep(a) = a - chainK(a) • v belongs to A, while subtracting one further step of v leaves A by the definition of chainK.
uses
isotropic_intersection_size_bound_chainK_min,sub_add_cancel,isotropic_intersection_size_bound_mem_of_le,le_rfl,isotropic_intersection_size_bound_chainK_spec,add_smul,one_smulintro l hl match l with | 0 => simpa using ha | (j + 1) => have hlt : j < isotropic_intersection_size_bound_chainK A v a := by omega have hmem := isotropic_intersection_size_bound_chainK_min A v hv ha hlt simpa [Nat.cast_add, Nat.cast_one] using hmem lemma isotropic_intersection_size_bound_chainRep_eq_add (a : V) : isotropic_intersection_size_bound_chainRep A v a + (isotropic_intersection_size_bound_chainK A v a : ℝ) • v = a := by simp [isotropic_intersection_size_bound_chainRep, sub_add_cancel] lemma isotropic_intersection_size_bound_chainRep_mem (hv : v ≠ 0) {a : V} (ha : a ∈ A) : isotropic_intersection_size_bound_chainRep A v a ∈ A := by have h := isotropic_intersection_size_bound_mem_of_le A v hv ha (isotropic_intersection_size_bound_chainK A v a) le_rfl rw [isotropic_intersection_size_bound_chainRep] exact h lemma isotropic_intersection_size_bound_chainRep_sub_v (hv : v ≠ 0) {a : V} (ha : a ∈ A) : isotropic_intersection_size_bound_chainRep A v a - v ∉ A := by have h := isotropic_intersection_size_bound_chainK_spec A v hv a ha have hEq : isotropic_intersection_size_bound_chainRep A v a - v = a - ((isotropic_intersection_size_bound_chainK A v a : ℝ) + 1) • v := by rw [isotropic_intersection_size_bound_chainRep, add_smul, one_smul] abel rwa [hEq]
The step count shifts as chainK(a - l • v) = chainK(a) - l, so the representative is constant along the chain and idempotent
Stepping backwards by l ≤ chainK(a) reduces the remaining distance to the boundary by exactly l, establishing chainK(a - l • v) = chainK(a) - l via antisymmetry. Consequently, chainRep(a - l • v) = chainRep(a), which specializes at l = chainK(a) to chainK(chainRep(a)) = 0 and chainRep(chainRep(a)) = chainRep(a).
uses
isotropic_intersection_size_bound_mem_of_le,isotropic_intersection_size_bound_chainK_le,Nat.cast_sub,isotropic_intersection_size_bound_sub_smul_sub,isotropic_intersection_size_bound_chainK_spec,Nat.le_of_not_lt,le_antisymm,isotropic_intersection_size_bound_chainK_index,Nat.sub_self,isotropic_intersection_size_bound_chainRep_indexclassical have hmem : a - (l : ℝ) • v ∈ A := isotropic_intersection_size_bound_mem_of_le A v hv ha l hl have hupper : isotropic_intersection_size_bound_chainK A v (a - (l : ℝ) • v) ≤ isotropic_intersection_size_bound_chainK A v a - l := by apply isotropic_intersection_size_bound_chainK_le A v hv hmem have hs : ((l : ℝ) + (((isotropic_intersection_size_bound_chainK A v a - l : ℕ) : ℝ) + 1)) = ((isotropic_intersection_size_bound_chainK A v a : ℝ) + 1) := by rw [Nat.cast_sub hl]; ring have hEq : a - (l : ℝ) • v - (((isotropic_intersection_size_bound_chainK A v a - l : ℕ) : ℝ) + 1) • v = a - ((isotropic_intersection_size_bound_chainK A v a : ℝ) + 1) • v := by rw [isotropic_intersection_size_bound_sub_smul_sub, hs] rw [hEq] exact isotropic_intersection_size_bound_chainK_spec A v hv a ha have hlower : isotropic_intersection_size_bound_chainK A v a - l ≤ isotropic_intersection_size_bound_chainK A v (a - (l : ℝ) • v) := by refine Nat.le_of_not_lt (fun hlt => ?_) have hnotmem : a - (l : ℝ) • v - ((isotropic_intersection_size_bound_chainK A v (a - (l : ℝ) • v) : ℝ) + 1) • v ∉ A := isotropic_intersection_size_bound_chainK_spec A v hv (a - (l : ℝ) • v) hmem apply hnotmem have hEq : a - (l : ℝ) • v - ((isotropic_intersection_size_bound_chainK A v (a - (l : ℝ) • v) : ℝ) + 1) • v = a - ((l + isotropic_intersection_size_bound_chainK A v (a - (l : ℝ) • v) + 1 : ℕ) : ℝ) • v := by have hs : ((l : ℝ) + ((isotropic_intersection_size_bound_chainK A v (a - (l : ℝ) • v) : ℝ) + 1)) = ((l + isotropic_intersection_size_bound_chainK A v (a - (l : ℝ) • v) + 1 : ℕ) : ℝ) := by push_cast; ring rw [isotropic_intersection_size_bound_sub_smul_sub, hs] rw [hEq] exact isotropic_intersection_size_bound_mem_of_le A v hv ha _ (by omega) exact le_antisymm hupper hlower lemma isotropic_intersection_size_bound_chainRep_index (hv : v ≠ 0) {a : V} (ha : a ∈ A) {l : ℕ} (hl : l ≤ isotropic_intersection_size_bound_chainK A v a) : isotropic_intersection_size_bound_chainRep A v (a - (l : ℝ) • v) = isotropic_intersection_size_bound_chainRep A v a := by have hh := isotropic_intersection_size_bound_chainK_index A v hv ha hl simp only [isotropic_intersection_size_bound_chainRep, hh] have hs : ((l : ℝ) + (((isotropic_intersection_size_bound_chainK A v a) - l : ℕ) : ℝ)) = (isotropic_intersection_size_bound_chainK A v a : ℝ) := by rw [Nat.cast_sub hl]; ring rw [isotropic_intersection_size_bound_sub_smul_sub, hs] lemma isotropic_intersection_size_bound_chainK_chainRep (hv : v ≠ 0) {a : V} (ha : a ∈ A) : isotropic_intersection_size_bound_chainK A v (isotropic_intersection_size_bound_chainRep A v a) = 0 := by have h := isotropic_intersection_size_bound_chainK_index A v hv ha (l := isotropic_intersection_size_bound_chainK A v a) le_rfl have hEq : isotropic_intersection_size_bound_chainRep A v a = a - (isotropic_intersection_size_bound_chainK A v a : ℝ) • v := rfl rw [hEq, h, Nat.sub_self] lemma isotropic_intersection_size_bound_chainRep_fix (hv : v ≠ 0) {a : V} (ha : a ∈ A) : isotropic_intersection_size_bound_chainRep A v (isotropic_intersection_size_bound_chainRep A v a) = isotropic_intersection_size_bound_chainRep A v a := by have h := isotropic_intersection_size_bound_chainRep_index A v hv ha (l := isotropic_intersection_size_bound_chainK A v a) le_rfl have hEq : isotropic_intersection_size_bound_chainRep A v a = a - (isotropic_intersection_size_bound_chainK A v a : ℝ) • v := rfl rw [hEq] at h exact h
Each chain is an arithmetic progression r + i • v for 0 ≤ i ≤ M of size M + 1, where M = chainLen(r)
Any element b in the chain of r has b = r + chainK(b) • v with chainK(b) ≤ M. Conversely, taking the top element c achieving the maximum length M, every intermediate point r + i • v = c - (M - i) • v belongs to A with representative r. The progression map is injective, so the chain has cardinality M + 1.
uses
isotropic_intersection_size_bound_mem_chain,Finset.le_sup,isotropic_intersection_size_bound_chainRep_eq_add,Finset.exists_mem_eq_sup,isotropic_intersection_size_bound_mem_of_le,isotropic_intersection_size_bound_chainRep_index,Nat.cast_sub,sub_smul,isotropic_intersection_size_bound_nat_smul_inj,add_left_cancel,isotropic_intersection_size_bound_chain_image,Finset.card_image_of_injOn,isotropic_intersection_size_bound_chain_inj,Finset.card_rangeclassical have hne : (isotropic_intersection_size_bound_chain A v r).Nonempty := ⟨r, (isotropic_intersection_size_bound_mem_chain A v).mpr ⟨hr, hfix⟩⟩ ext b constructor · intro hb obtain ⟨hbA, hbr⟩ := (isotropic_intersection_size_bound_mem_chain A v).mp hb have hle : isotropic_intersection_size_bound_chainK A v b ≤ isotropic_intersection_size_bound_chainLen A v r := by simpa [isotropic_intersection_size_bound_chainLen] using Finset.le_sup (f := isotropic_intersection_size_bound_chainK A v) hb refine Finset.mem_image.mpr ⟨isotropic_intersection_size_bound_chainK A v b, Finset.mem_range.mpr (by omega), ?_⟩ have h := isotropic_intersection_size_bound_chainRep_eq_add A v b rw [hbr] at h exact h · intro hb obtain ⟨i, hi, rfl⟩ := Finset.mem_image.mp hb simp only [Finset.mem_range] at hi obtain ⟨c, hc, hcm⟩ := Finset.exists_mem_eq_sup (isotropic_intersection_size_bound_chain A v r) hne (isotropic_intersection_size_bound_chainK A v) obtain ⟨hcA, hcr⟩ := (isotropic_intersection_size_bound_mem_chain A v).mp hc have hcm' : isotropic_intersection_size_bound_chainK A v c = isotropic_intersection_size_bound_chainLen A v r := hcm.symm have hile : i ≤ isotropic_intersection_size_bound_chainLen A v r := by omega have hmemc : c - ((isotropic_intersection_size_bound_chainLen A v r - i : ℕ) : ℝ) • v ∈ A := isotropic_intersection_size_bound_mem_of_le A v hv hcA _ (by omega) have hrep : isotropic_intersection_size_bound_chainRep A v (c - ((isotropic_intersection_size_bound_chainLen A v r - i : ℕ) : ℝ) • v) = r := by rw [isotropic_intersection_size_bound_chainRep_index A v hv hcA (l := isotropic_intersection_size_bound_chainLen A v r - i) (by omega), hcr] have hceq : c = r + (isotropic_intersection_size_bound_chainLen A v r : ℝ) • v := by have h := isotropic_intersection_size_bound_chainRep_eq_add A v c rw [hcr, hcm'] at h exact h.symm have heq : r + (i : ℝ) • v = c - ((isotropic_intersection_size_bound_chainLen A v r - i : ℕ) : ℝ) • v := by rw [hceq] have hsc : ((isotropic_intersection_size_bound_chainLen A v r : ℝ) - ((isotropic_intersection_size_bound_chainLen A v r - i : ℕ) : ℝ)) = (i : ℝ) := by rw [Nat.cast_sub hile]; ring rw [← hsc, sub_smul] abel rw [heq] exact (isotropic_intersection_size_bound_mem_chain A v).mpr ⟨hmemc, hrep⟩ lemma isotropic_intersection_size_bound_chain_inj (hv : v ≠ 0) {r : V} : Set.InjOn (fun i : ℕ => r + (i : ℝ) • v) ↑(Finset.range (isotropic_intersection_size_bound_chainLen A v r + 1)) := by intro i _ j _ hij exact isotropic_intersection_size_bound_nat_smul_inj hv (add_left_cancel hij) lemma isotropic_intersection_size_bound_chain_card {r : V} (hv : v ≠ 0) (hr : r ∈ A) (hfix : isotropic_intersection_size_bound_chainRep A v r = r) : (isotropic_intersection_size_bound_chain A v r).card = isotropic_intersection_size_bound_chainLen A v r + 1 := by classical rw [isotropic_intersection_size_bound_chain_image A v hv hr hfix, Finset.card_image_of_injOn (isotropic_intersection_size_bound_chain_inj A v hv), Finset.card_range]
The quadratic energy of a chain of length M + 1 in direction v is at least (1/2) M ‖v‖⁴
Along the progression r + i • v for i < n = M + 1, the inner products expand to ‖v‖⁴ ∑ (t + i)² where t = ⟨r, v⟩ / ‖v‖². Applying sum_range_sq_add_ge bounds this by (1/12) n (n² - 1) ‖v‖⁴, and the cubic inequality isotropic_chain_cubic_ineq yields (1/12) n (n² - 1) ≥ (1/2)(n - 1) = (1/2) M.
uses
isotropic_intersection_size_bound_chain_image,isotropic_intersection_size_bound_chain_inj,sum_range_sq_add_ge,isotropic_chain_cubic_ineqclassical set n := isotropic_intersection_size_bound_chainLen A v r + 1 with hn set s := ‖v‖ ^ 2 with hs have hs_pos : 0 < s := by have hvpos : 0 < ‖v‖ := norm_pos_iff.mpr hv rw [hs]; positivity have hncast : ((n : ℝ) - 1) = (isotropic_intersection_size_bound_chainLen A v r : ℝ) := by rw [hn]; push_cast; ring have h4 : ‖v‖ ^ 4 = s ^ 2 := by rw [hs]; ring have himg : isotropic_intersection_size_bound_chain A v r = (Finset.range n).image (fun i : ℕ => r + (i : ℝ) • v) := by rw [isotropic_intersection_size_bound_chain_image A v hv hr hfix, hn] have hinj : Set.InjOn (fun i : ℕ => r + (i : ℝ) • v) ↑(Finset.range n) := by rw [hn]; exact isotropic_intersection_size_bound_chain_inj A v hv have hsum1 : ∑ b ∈ isotropic_intersection_size_bound_chain A v r, (inner (𝕜 := ℝ) b v) ^ 2 = ∑ i ∈ Finset.range n, (inner (𝕜 := ℝ) r v + (i : ℝ) * s) ^ 2 := by rw [himg, Finset.sum_image hinj] apply Finset.sum_congr rfl intro i hi rw [inner_add_left, real_inner_smul_left, real_inner_self_eq_norm_sq, ← hs] have hsplit : ∑ i ∈ Finset.range n, (inner (𝕜 := ℝ) r v + (i : ℝ) * s) ^ 2 = s ^ 2 * ∑ i ∈ Finset.range n, (inner (𝕜 := ℝ) r v / s + (i : ℝ)) ^ 2 := by rw [Finset.mul_sum] apply Finset.sum_congr rfl intro i hi have h1 : inner (𝕜 := ℝ) r v + (i : ℝ) * s = s * (inner (𝕜 := ℝ) r v / s + (i : ℝ)) := by field_simp rw [h1]; ring have hT : (1 / 12) * (n : ℝ) * ((n : ℝ) ^ 2 - 1) ≤ ∑ i ∈ Finset.range n, (inner (𝕜 := ℝ) r v / s + (i : ℝ)) ^ 2 := sum_range_sq_add_ge n (inner (𝕜 := ℝ) r v / s) have hcub : (1 / 2) * ((n : ℝ) - 1) ≤ (1 / 12) * (n : ℝ) * ((n : ℝ) ^ 2 - 1) := by have := isotropic_chain_cubic_ineq n linarith have hstep1 : (1 / 2) * (isotropic_intersection_size_bound_chainLen A v r : ℝ) * ‖v‖ ^ 4 = ((1 / 2) * ((n : ℝ) - 1)) * s ^ 2 := by rw [← hncast, h4] rw [hstep1, hsum1, hsplit] calc ((1 / 2) * ((n : ℝ) - 1)) * s ^ 2 ≤ ((1 / 12) * (n : ℝ) * ((n : ℝ) ^ 2 - 1)) * s ^ 2 := mul_le_mul_of_nonneg_right hcub (sq_nonneg s) _ ≤ (∑ i ∈ Finset.range n, (inner (𝕜 := ℝ) r v / s + (i : ℝ)) ^ 2) * s ^ 2 := mul_le_mul_of_nonneg_right hT (sq_nonneg s) _ = s ^ 2 * ∑ i ∈ Finset.range n, (inner (𝕜 := ℝ) r v / s + (i : ℝ)) ^ 2 := mul_comm (∑ i ∈ Finset.range n, (inner (𝕜 := ℝ) r v / s + (i : ℝ)) ^ 2) (s ^ 2)
A chain of length M + 1 contributes exactly M points to the intersection A ∩ (v + A)
In the progression r + i • v, the base point r has r - v ∉ A (contributing 0 to the indicator), while each subsequent point r + (k+1) • v for k < M shifts back to r + k • v ∈ A (contributing 1). Summing these indicators over the chain yields exactly M = chainLen(r).
uses
isotropic_intersection_size_bound_chain_image,isotropic_intersection_size_bound_chain_inj,isotropic_intersection_size_bound_chainRep_sub_v,add_smul,one_smul,isotropic_intersection_size_bound_mem_chainclassical have himg : isotropic_intersection_size_bound_chain A v r = (Finset.range (isotropic_intersection_size_bound_chainLen A v r + 1)).image (fun i : ℕ => r + (i : ℝ) • v) := isotropic_intersection_size_bound_chain_image A v hv hr hfix have hinj : Set.InjOn (fun i : ℕ => r + (i : ℝ) • v) ↑(Finset.range (isotropic_intersection_size_bound_chainLen A v r + 1)) := isotropic_intersection_size_bound_chain_inj A v hv rw [himg, Finset.sum_image hinj, Finset.sum_range_succ'] have h0 : (if (r + ((0 : ℕ) : ℝ) • v) - v ∈ A then (1 : ℝ) else 0) = 0 := by have hnot : r - v ∉ A := by rw [← hfix] exact isotropic_intersection_size_bound_chainRep_sub_v A v hv hr have heq : r + ((0 : ℕ) : ℝ) • v - v = r - v := by simp rw [heq] simp [hnot] rw [h0, add_zero] have hk : ∀ k ∈ Finset.range (isotropic_intersection_size_bound_chainLen A v r), (if (r + (((k + 1 : ℕ)) : ℝ) • v) - v ∈ A then (1 : ℝ) else 0) = 1 := by intro k hk have hk' : k < isotropic_intersection_size_bound_chainLen A v r := Finset.mem_range.mp hk have heq : r + (((k + 1 : ℕ)) : ℝ) • v - v = r + (k : ℝ) • v := by push_cast rw [add_smul, one_smul] abel have hmem : r + (k : ℝ) • v ∈ A := by have h1 : r + (k : ℝ) • v ∈ (Finset.range (isotropic_intersection_size_bound_chainLen A v r + 1)).image (fun i : ℕ => r + (i : ℝ) • v) := Finset.mem_image.mpr ⟨k, Finset.mem_range.mpr (by omega), rfl⟩ rw [← himg] at h1 exact ((isotropic_intersection_size_bound_mem_chain A v).mp h1).1 rw [heq] simp [hmem] rw [Finset.sum_congr rfl hk] simp
Express the intersection cardinality |A ∩ (v + A)| as the indicator sum ∑_{a ∈ A} 𝟙_{a - v ∈ A}
The intersection A ∩ (v + A) consists of points a ∈ A such that a - v ∈ A. Writing the size of this filtered set as a sum of booleans (Finset.sum_boole) gives the indicator representation.
uses
Finset.sum_booleclassical have hInter : A ∩ (v +ᵥ A) = A.filter (fun a => a - v ∈ A) := by ext a simp only [Finset.mem_inter, Finset.mem_filter, Finset.mem_vadd_finset, vadd_eq_add] constructor · rintro ⟨ha, y, hy, hya⟩ refine ⟨ha, ?_⟩ rw [← hya] have h : v + y - v = y := by abel rw [h] exact hy · rintro ⟨ha, hav⟩ exact ⟨ha, a - v, hav, by abel⟩ have hN : ((A ∩ (v +ᵥ A)).card : ℝ) = ∑ a ∈ A, (if a - v ∈ A then (1 : ℝ) else 0) := by rw [hInter] exact (Finset.sum_boole (fun a => a - v ∈ A) A).symm
Fiberwise summation decomposes the intersection size into the sum of chain lengths ∑_r M_r
Grouping the sum over a ∈ A by the fibers of the representative map a ↦ chainRep(a) via Finset.sum_fiberwise_of_maps_to, each fiber is a chain contributing its length M_r by isotropic_intersection_size_bound_chain_count, giving |A ∩ (v + A)| = ∑_r M_r.
uses
Finset.mem_image_of_mem,isotropic_intersection_size_bound_chainRep_fix,isotropic_intersection_size_bound_chainRep_mem,Finset.sum_fiberwise_of_maps_to,isotropic_intersection_size_bound_chain_counthave hmaps : ∀ a ∈ A, isotropic_intersection_size_bound_chainRep A v a ∈ isotropic_intersection_size_bound_chainStarts A v := by intro a ha exact Finset.mem_image_of_mem _ ha have hfib : ∀ r ∈ isotropic_intersection_size_bound_chainStarts A v, isotropic_intersection_size_bound_chainRep A v r = r ∧ r ∈ A := by intro r hr obtain ⟨a, ha, rfl⟩ := Finset.mem_image.mp hr exact ⟨isotropic_intersection_size_bound_chainRep_fix A v hv ha, isotropic_intersection_size_bound_chainRep_mem A v hv ha⟩ have hcount : ((A ∩ (v +ᵥ A)).card : ℝ) = ∑ r ∈ isotropic_intersection_size_bound_chainStarts A v, (isotropic_intersection_size_bound_chainLen A v r : ℝ) := by rw [hN, ← Finset.sum_fiberwise_of_maps_to hmaps (fun a : EuclideanSpace ℝ (Fin d) => if a - v ∈ A then (1 : ℝ) else 0)] exact Finset.sum_congr rfl (fun r hr => isotropic_intersection_size_bound_chain_count A v hv (hfib r hr).2 (hfib r hr).1)
The total quadratic energy ∑_{a ∈ A} ⟨a, v⟩² is bounded below by (1/2) ‖v‖⁴ ∑_r M_r
Summing fiberwise over the chains partitions the total energy into a sum of chain energies. Applying the single-chain energy lower bound to each chain yields (1/2) ‖v‖⁴ ∑_r M_r ≤ ∑_{a ∈ A} ⟨a, v⟩².
uses
Finset.sum_fiberwise_of_maps_to,Finset.sum_le_sum,isotropic_intersection_size_bound_chain_energyhave hsplit_energy : ∑ r ∈ isotropic_intersection_size_bound_chainStarts A v, ∑ b ∈ isotropic_intersection_size_bound_chain A v r, (inner (𝕜 := ℝ) b v) ^ 2 = ∑ a ∈ A, (inner (𝕜 := ℝ) a v) ^ 2 := Finset.sum_fiberwise_of_maps_to hmaps _ have henergy : ∑ r ∈ isotropic_intersection_size_bound_chainStarts A v, (1 / 2) * (isotropic_intersection_size_bound_chainLen A v r : ℝ) * ‖v‖ ^ 4 ≤ ∑ a ∈ A, (inner (𝕜 := ℝ) a v) ^ 2 := by rw [← hsplit_energy] exact Finset.sum_le_sum (fun r hr => isotropic_intersection_size_bound_chain_energy A v hv (hfib r hr).2 (hfib r hr).1)
Connect the energy lower bound to the isotropic covariance condition: (1/2) ‖v‖⁴ |A ∩ (v + A)| ≤ |A| ‖v‖²
Factoring out (1/2) ‖v‖⁴ from the sum of chain lengths converts it to (1/2) ‖v‖⁴ |A ∩ (v + A)|. By the isotropic assumption with u = v, the total quadratic energy equals |A| ‖v‖², giving the inequality.
uses
Finset.mul_sum,le_of_eqhave hmain : (1 / 2) * ‖v‖ ^ 4 * ((A ∩ (v +ᵥ A)).card : ℝ) ≤ (A.card : ℝ) * ‖v‖ ^ 2 := by rw [hcount] have hfac : (1 / 2) * ‖v‖ ^ 4 * ∑ r ∈ isotropic_intersection_size_bound_chainStarts A v, (isotropic_intersection_size_bound_chainLen A v r : ℝ) = ∑ r ∈ isotropic_intersection_size_bound_chainStarts A v, (1 / 2) * (isotropic_intersection_size_bound_chainLen A v r : ℝ) * ‖v‖ ^ 4 := by rw [Finset.mul_sum] exact Finset.sum_congr rfl (fun r _ => by ring) rw [hfac] exact henergy.trans (le_of_eq (h_cov v))
Divide by ‖v‖² to conclude |A ∩ (v + A)| ≤ 2|A| / ‖v‖²
Since v ≠ 0, ‖v‖² > 0. Cancelling one factor of ‖v‖² and multiplying by 2 yields ‖v‖² |A ∩ (v + A)| ≤ 2|A|, and dividing by ‖v‖² gives the desired bound.
uses
le_of_mul_le_mul_left,le_div_iff₀have hvpos : (0 : ℝ) < ‖v‖ ^ 2 := by have h1 : 0 < ‖v‖ := norm_pos_iff.mpr hv positivity have hkey : ‖v‖ ^ 2 * ((A ∩ (v +ᵥ A)).card : ℝ) ≤ 2 * (A.card : ℝ) := by have h2 : ‖v‖ ^ 4 * ((A ∩ (v +ᵥ A)).card : ℝ) ≤ 2 * ((A.card : ℝ) * ‖v‖ ^ 2) := by nlinarith [hmain] have h4 : ‖v‖ ^ 4 = ‖v‖ ^ 2 * ‖v‖ ^ 2 := by ring have h3 : ‖v‖ ^ 2 * (‖v‖ ^ 2 * ((A ∩ (v +ᵥ A)).card : ℝ)) ≤ ‖v‖ ^ 2 * (2 * (A.card : ℝ)) := by nlinarith [h2, h4] exact le_of_mul_le_mul_left h3 hvpos rw [le_div_iff₀ hvpos] calc ((A ∩ (v +ᵥ A)).card : ℝ) * ‖v‖ ^ 2 = ‖v‖ ^ 2 * ((A ∩ (v +ᵥ A)).card : ℝ) := by ring _ ≤ 2 * (A.card : ℝ) := hkey
add_smul- Distributivity of scalar multiplication over scalar addition: (r + s) • x = r • x + s • x
sub_smul- Distributivity of scalar multiplication over scalar subtraction: (r - s) • y = r • y - s • y
Nat.cast_injective- The natural cast into an additive monoid with characteristic zero is injective: if (i : ℝ) = (j : ℝ) then i = j
sub_eq_add_neg- Subtraction is addition of the negative: a - b = a + -b
add_left_cancel- Left cancellation in an additive group: a + b = a + c implies b = c
neg_injective- Negation is an injective function
Set.Infinite.mono- A superset of an infinite set is infinite
Set.infinite_range_of_injective- The image of an infinite type under an injective function is an infinite set
Nat.find- The least natural number satisfying a decidable predicate
isotropic_intersection_size_bound_back_exists- Repeatedly subtracting a non-zero vector v from a point of a finite set A eventually leaves A
dif_pos- Evaluates a dependent if-then-else to the positive branch when the condition holds
Nat.find_spec- The number returned by Nat.find satisfies the predicate
Nat.find_min- Any natural number strictly smaller than Nat.find does not satisfy the predicate
Nat.find_min'- Nat.find is bounded above by any witness satisfying the predicate
isotropic_intersection_size_bound_chainK_min- Any step count strictly less than chainK keeps the backward point inside A
sub_add_cancel- Adding the subtracted element cancels subtraction: a - b + b = a
isotropic_intersection_size_bound_mem_of_le- All backward steps up to chainK stay inside A
le_rfl- Reflexivity of preorder: a ≤ a
isotropic_intersection_size_bound_chainK_spec- Stepping chainK + 1 times backwards along v leaves A
one_smul- Scalar multiplication by 1 is the identity: 1 • b = b
isotropic_intersection_size_bound_chainK_le- If stepping j + 1 times backwards along v leaves A, then chainK ≤ j
Nat.cast_sub- The cast of a natural difference m - n into an additive group with one equals ↑m - ↑n when n ≤ m
isotropic_intersection_size_bound_sub_smul_sub- Distributing differences of scalar multiples: a - r • v - s • v = a - (r + s) • v
Nat.le_of_not_lt- If a natural number is not strictly less than another, then the inequality holds in the other direction
le_antisymm- Antisymmetry of partial orders: a ≤ b and b ≤ a implies a = b
isotropic_intersection_size_bound_chainK_index- The chain step count shifts linearly under backward steps: chainK(a - l • v) = chainK(a) - l
Nat.sub_self- A natural number minus itself is zero: n - n = 0
isotropic_intersection_size_bound_chainRep_index- The chain representative is invariant under backward steps: chainRep(a - l • v) = chainRep(a)
isotropic_intersection_size_bound_mem_chain- Membership in a chain: b ∈ chain A v r if and only if b ∈ A and chainRep(b) = r
Finset.le_sup- An element's value under f is bounded above by the supremum over the finite set: f b ≤ s.sup f
isotropic_intersection_size_bound_chainRep_eq_add- A point equals its chain representative shifted forward by chainK steps: chainRep(a) + chainK(a) • v = a
Finset.exists_mem_eq_sup- On a non-empty finite set, the supremum of a function is attained at some element
isotropic_intersection_size_bound_nat_smul_inj- Multiples of a non-zero vector by distinct natural numbers are distinct: i • v = j • v implies i = j
isotropic_intersection_size_bound_chain_image- The chain starting at r is the image of the range under i ↦ r + i • v
Finset.card_image_of_injOn- The cardinality of an image under an injective map equals the cardinality of the domain
isotropic_intersection_size_bound_chain_inj- The progression map i ↦ r + i • v is injective on indices
Finset.card_range- The cardinality of Finset.range n is n
sum_range_sq_add_ge- The sum of squares of an arithmetic progression shifted by t is bounded below by (1/12) m (m² - 1)
isotropic_chain_cubic_ineq- Cubic inequality for chains: m - 1 ≤ (1/6) m (m² - 1)
isotropic_intersection_size_bound_chainRep_sub_v- Stepping backwards by v from a chain representative leaves A: chainRep(a) - v ∉ A
Finset.sum_boole- The sum of a boolean indicator over a finite set equals the cardinality of the filtered subset
Finset.mem_image_of_mem- An element's image under f belongs to the image of the set: f a ∈ Finset.image f s
isotropic_intersection_size_bound_chainRep_fix- The chain representative operation is idempotent: chainRep(chainRep(a)) = chainRep(a)
isotropic_intersection_size_bound_chainRep_mem- The chain representative of any element of A belongs to A
Finset.sum_fiberwise_of_maps_to- Fubini / fiberwise summation formula: grouping a sum over s by the fibers of a map g
isotropic_intersection_size_bound_chain_count- A chain of length M + 1 contains exactly M points b such that b - v ∈ A
Finset.sum_le_sum- Monotonicity of finite sums: if f i ≤ g i for all i ∈ s, then ∑ i ∈ s, f i ≤ ∑ i ∈ s, g i
isotropic_intersection_size_bound_chain_energy- The quadratic energy of a chain of length M + 1 in direction v is at least (1/2) M ‖v‖⁴
Finset.mul_sum- Distributing multiplication over a finite sum: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i
le_of_eq- An equality implies a weak inequality: a = b implies a ≤ b
le_of_mul_le_mul_left- Cancelling a positive factor on the left preserves inequality: a * b ≤ a * c with 0 < a implies b ≤ c
le_div_iff₀- Division by a positive quantity preserves inequality: a ≤ b / c ↔ a * c ≤ b for 0 < c
- The proof decomposes the finite set into one-dimensional chains (arithmetic progressions in direction v) and applies discrete variance estimates to each chain.
- In the energy bound for a single chain, minimizing the discrete quadratic sum uses the helper inequality sum_range_sq_add_ge and the cubic inequality isotropic_chain_cubic_ineq.
- Linear and non-linear arithmetic automation (linarith, nlinarith, omega, positivity) is used throughout to close intermediate inequalities.
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 scoped Pointwisesection IsotropicIntersectionBoundHelpersvariable {V : Type*} [NormedAddCommGroup V] [InnerProductSpace ℝ V] [DecidableEq V]/-- Distributing a difference of scalar multiples. -/lemma isotropic_intersection_size_bound_sub_smul_sub (a v : V) (r s : ℝ) : a - r • v - s • v = a - (r + s) • v := by rw [add_smul]; abel/-- Multiples of a nonzero vector by distinct naturals are distinct. -/lemma isotropic_intersection_size_bound_nat_smul_inj {v : V} (hv : v ≠ 0) {i j : ℕ} (h : (i : ℝ) • v = (j : ℝ) • v) : i = j := by have h3 : (((i : ℝ)) - ((j : ℝ))) • v = 0 := by rw [sub_smul]; exact sub_eq_zero.mpr h rcases smul_eq_zero.mp h3 with h4 | h4 · have h5 : (i : ℝ) = (j : ℝ) := by linarith exact Nat.cast_injective h5 · exact absurd h4 hv/-- Walking backwards along `v` from a point of a finite set eventually leaves it. -/lemma isotropic_intersection_size_bound_back_exists (A : Finset V) (v : V) (hv : v ≠ 0) (a : V) (ha : a ∈ A) : ∃ k : ℕ, a - ((k : ℝ) + 1) • v ∉ A := by by_contra hcon simp only [not_exists, not_not] at hcon have hinj : Function.Injective (fun k : ℕ => a - ((k : ℝ) + 1) • v) := by intro k l hkl have hkl' : a - ((k : ℝ) + 1) • v = a - ((l : ℝ) + 1) • v := hkl have h1 : -(((k : ℝ) + 1) • v) = -(((l : ℝ) + 1) • v) := by rw [sub_eq_add_neg, sub_eq_add_neg] at hkl' exact add_left_cancel hkl' have h2 : ((k : ℝ) + 1) • v = ((l : ℝ) + 1) • v := neg_injective h1 have h3 : (((k : ℝ) + 1) - ((l : ℝ) + 1)) • v = 0 := by rw [sub_smul] exact sub_eq_zero.mpr h2 rcases smul_eq_zero.mp h3 with h4 | h4 · have h5 : (k : ℝ) = (l : ℝ) := by linarith exact Nat.cast_injective h5 · exact absurd h4 hv have hsub : Set.range (fun k : ℕ => a - ((k : ℝ) + 1) • v) ⊆ (A : Set V) := by rintro x ⟨k, rfl⟩ exact hcon k exact (Set.Infinite.mono hsub (Set.infinite_range_of_injective hinj)) A.finite_toSet/-- The number of backward steps along `v` from a point before leaving `A`. -/noncomputable def isotropic_intersection_size_bound_chainK (A : Finset V) (v : V) (a : V) : ℕ := by classical exact if h : ∃ k : ℕ, a - ((k : ℝ) + 1) • v ∉ A then Nat.find h else 0/-- The first point of the `v`-chain through `a`. -/noncomputable def isotropic_intersection_size_bound_chainRep (A : Finset V) (v : V) (a : V) : V := by classical exact a - (isotropic_intersection_size_bound_chainK A v a : ℝ) • v/-- The `v`-chain of `A` starting at `r`. -/noncomputable def isotropic_intersection_size_bound_chain (A : Finset V) (v : V) (r : V) : Finset V := by classical exact A.filter (fun b => isotropic_intersection_size_bound_chainRep A v b = r)/-- The index of the top point of the chain starting at `r`. -/noncomputable def isotropic_intersection_size_bound_chainLen (A : Finset V) (v : V) (r : V) : ℕ := (isotropic_intersection_size_bound_chain A v r).sup (isotropic_intersection_size_bound_chainK A v)/-- The set of chain starts of `A` in direction `v`. -/noncomputable def isotropic_intersection_size_bound_chainStarts (A : Finset V) (v : V) : Finset V := by classical exact A.image (isotropic_intersection_size_bound_chainRep A v)variable (A : Finset V) (v : V)lemma isotropic_intersection_size_bound_mem_chain {r b : V} : b ∈ isotropic_intersection_size_bound_chain A v r ↔ b ∈ A ∧ isotropic_intersection_size_bound_chainRep A v b = r := by classical simp [isotropic_intersection_size_bound_chain]lemma isotropic_intersection_size_bound_chainK_spec (hv : v ≠ 0) (a : V) (ha : a ∈ A) : a - ((isotropic_intersection_size_bound_chainK A v a : ℝ) + 1) • v ∉ A := by classical have h := isotropic_intersection_size_bound_back_exists A v hv a ha have hfind : isotropic_intersection_size_bound_chainK A v a = Nat.find h := dif_pos h rw [hfind] exact Nat.find_spec hlemma isotropic_intersection_size_bound_chainK_min (hv : v ≠ 0) {a : V} (ha : a ∈ A) {j : ℕ} (hj : j < isotropic_intersection_size_bound_chainK A v a) : a - ((j : ℝ) + 1) • v ∈ A := by classical by_contra hmem have h := isotropic_intersection_size_bound_back_exists A v hv a ha have hfind : isotropic_intersection_size_bound_chainK A v a = Nat.find h := dif_pos h exact (Nat.find_min h (hfind ▸ hj)) hmemlemma isotropic_intersection_size_bound_chainK_le (hv : v ≠ 0) {a : V} (ha : a ∈ A) {j : ℕ} (hj : a - ((j : ℝ) + 1) • v ∉ A) : isotropic_intersection_size_bound_chainK A v a ≤ j := by classical have h := isotropic_intersection_size_bound_back_exists A v hv a ha have hfind : isotropic_intersection_size_bound_chainK A v a = Nat.find h := dif_pos h rw [hfind] exact Nat.find_min' h hjlemma isotropic_intersection_size_bound_mem_of_le (hv : v ≠ 0) {a : V} (ha : a ∈ A) : ∀ l : ℕ, l ≤ isotropic_intersection_size_bound_chainK A v a → a - (l : ℝ) • v ∈ A := by intro l hl match l with | 0 => simpa using ha | (j + 1) => have hlt : j < isotropic_intersection_size_bound_chainK A v a := by omega have hmem := isotropic_intersection_size_bound_chainK_min A v hv ha hlt simpa [Nat.cast_add, Nat.cast_one] using hmemlemma isotropic_intersection_size_bound_chainRep_eq_add (a : V) : isotropic_intersection_size_bound_chainRep A v a + (isotropic_intersection_size_bound_chainK A v a : ℝ) • v = a := by simp [isotropic_intersection_size_bound_chainRep, sub_add_cancel]lemma isotropic_intersection_size_bound_chainRep_mem (hv : v ≠ 0) {a : V} (ha : a ∈ A) : isotropic_intersection_size_bound_chainRep A v a ∈ A := by have h := isotropic_intersection_size_bound_mem_of_le A v hv ha (isotropic_intersection_size_bound_chainK A v a) le_rfl rw [isotropic_intersection_size_bound_chainRep] exact hlemma isotropic_intersection_size_bound_chainRep_sub_v (hv : v ≠ 0) {a : V} (ha : a ∈ A) : isotropic_intersection_size_bound_chainRep A v a - v ∉ A := by have h := isotropic_intersection_size_bound_chainK_spec A v hv a ha have hEq : isotropic_intersection_size_bound_chainRep A v a - v = a - ((isotropic_intersection_size_bound_chainK A v a : ℝ) + 1) • v := by rw [isotropic_intersection_size_bound_chainRep, add_smul, one_smul] abel rwa [hEq]lemma isotropic_intersection_size_bound_chainK_index (hv : v ≠ 0) {a : V} (ha : a ∈ A) {l : ℕ} (hl : l ≤ isotropic_intersection_size_bound_chainK A v a) : isotropic_intersection_size_bound_chainK A v (a - (l : ℝ) • v) = isotropic_intersection_size_bound_chainK A v a - l := by classical have hmem : a - (l : ℝ) • v ∈ A := isotropic_intersection_size_bound_mem_of_le A v hv ha l hl have hupper : isotropic_intersection_size_bound_chainK A v (a - (l : ℝ) • v) ≤ isotropic_intersection_size_bound_chainK A v a - l := by apply isotropic_intersection_size_bound_chainK_le A v hv hmem have hs : ((l : ℝ) + (((isotropic_intersection_size_bound_chainK A v a - l : ℕ) : ℝ) + 1)) = ((isotropic_intersection_size_bound_chainK A v a : ℝ) + 1) := by rw [Nat.cast_sub hl]; ring have hEq : a - (l : ℝ) • v - (((isotropic_intersection_size_bound_chainK A v a - l : ℕ) : ℝ) + 1) • v = a - ((isotropic_intersection_size_bound_chainK A v a : ℝ) + 1) • v := by rw [isotropic_intersection_size_bound_sub_smul_sub, hs] rw [hEq] exact isotropic_intersection_size_bound_chainK_spec A v hv a ha have hlower : isotropic_intersection_size_bound_chainK A v a - l ≤ isotropic_intersection_size_bound_chainK A v (a - (l : ℝ) • v) := by refine Nat.le_of_not_lt (fun hlt => ?_) have hnotmem : a - (l : ℝ) • v - ((isotropic_intersection_size_bound_chainK A v (a - (l : ℝ) • v) : ℝ) + 1) • v ∉ A := isotropic_intersection_size_bound_chainK_spec A v hv (a - (l : ℝ) • v) hmem apply hnotmem have hEq : a - (l : ℝ) • v - ((isotropic_intersection_size_bound_chainK A v (a - (l : ℝ) • v) : ℝ) + 1) • v = a - ((l + isotropic_intersection_size_bound_chainK A v (a - (l : ℝ) • v) + 1 : ℕ) : ℝ) • v := by have hs : ((l : ℝ) + ((isotropic_intersection_size_bound_chainK A v (a - (l : ℝ) • v) : ℝ) + 1)) = ((l + isotropic_intersection_size_bound_chainK A v (a - (l : ℝ) • v) + 1 : ℕ) : ℝ) := by push_cast; ring rw [isotropic_intersection_size_bound_sub_smul_sub, hs] rw [hEq] exact isotropic_intersection_size_bound_mem_of_le A v hv ha _ (by omega) exact le_antisymm hupper hlowerlemma isotropic_intersection_size_bound_chainRep_index (hv : v ≠ 0) {a : V} (ha : a ∈ A) {l : ℕ} (hl : l ≤ isotropic_intersection_size_bound_chainK A v a) : isotropic_intersection_size_bound_chainRep A v (a - (l : ℝ) • v) = isotropic_intersection_size_bound_chainRep A v a := by have hh := isotropic_intersection_size_bound_chainK_index A v hv ha hl simp only [isotropic_intersection_size_bound_chainRep, hh] have hs : ((l : ℝ) + (((isotropic_intersection_size_bound_chainK A v a) - l : ℕ) : ℝ)) = (isotropic_intersection_size_bound_chainK A v a : ℝ) := by rw [Nat.cast_sub hl]; ring rw [isotropic_intersection_size_bound_sub_smul_sub, hs]lemma isotropic_intersection_size_bound_chainK_chainRep (hv : v ≠ 0) {a : V} (ha : a ∈ A) : isotropic_intersection_size_bound_chainK A v (isotropic_intersection_size_bound_chainRep A v a) = 0 := by have h := isotropic_intersection_size_bound_chainK_index A v hv ha (l := isotropic_intersection_size_bound_chainK A v a) le_rfl have hEq : isotropic_intersection_size_bound_chainRep A v a = a - (isotropic_intersection_size_bound_chainK A v a : ℝ) • v := rfl rw [hEq, h, Nat.sub_self]lemma isotropic_intersection_size_bound_chainRep_fix (hv : v ≠ 0) {a : V} (ha : a ∈ A) : isotropic_intersection_size_bound_chainRep A v (isotropic_intersection_size_bound_chainRep A v a) = isotropic_intersection_size_bound_chainRep A v a := by have h := isotropic_intersection_size_bound_chainRep_index A v hv ha (l := isotropic_intersection_size_bound_chainK A v a) le_rfl have hEq : isotropic_intersection_size_bound_chainRep A v a = a - (isotropic_intersection_size_bound_chainK A v a : ℝ) • v := rfl rw [hEq] at h exact h/-- The chain starting at `r` is the affine progression `r + i • v`, `i ≤ chainLen`. -/lemma isotropic_intersection_size_bound_chain_image {r : V} (hv : v ≠ 0) (hr : r ∈ A) (hfix : isotropic_intersection_size_bound_chainRep A v r = r) : isotropic_intersection_size_bound_chain A v r = (Finset.range (isotropic_intersection_size_bound_chainLen A v r + 1)).image (fun i : ℕ => r + (i : ℝ) • v) := by classical have hne : (isotropic_intersection_size_bound_chain A v r).Nonempty := ⟨r, (isotropic_intersection_size_bound_mem_chain A v).mpr ⟨hr, hfix⟩⟩ ext b constructor · intro hb obtain ⟨hbA, hbr⟩ := (isotropic_intersection_size_bound_mem_chain A v).mp hb have hle : isotropic_intersection_size_bound_chainK A v b ≤ isotropic_intersection_size_bound_chainLen A v r := by simpa [isotropic_intersection_size_bound_chainLen] using Finset.le_sup (f := isotropic_intersection_size_bound_chainK A v) hb refine Finset.mem_image.mpr ⟨isotropic_intersection_size_bound_chainK A v b, Finset.mem_range.mpr (by omega), ?_⟩ have h := isotropic_intersection_size_bound_chainRep_eq_add A v b rw [hbr] at h exact h · intro hb obtain ⟨i, hi, rfl⟩ := Finset.mem_image.mp hb simp only [Finset.mem_range] at hi obtain ⟨c, hc, hcm⟩ := Finset.exists_mem_eq_sup (isotropic_intersection_size_bound_chain A v r) hne (isotropic_intersection_size_bound_chainK A v) obtain ⟨hcA, hcr⟩ := (isotropic_intersection_size_bound_mem_chain A v).mp hc have hcm' : isotropic_intersection_size_bound_chainK A v c = isotropic_intersection_size_bound_chainLen A v r := hcm.symm have hile : i ≤ isotropic_intersection_size_bound_chainLen A v r := by omega have hmemc : c - ((isotropic_intersection_size_bound_chainLen A v r - i : ℕ) : ℝ) • v ∈ A := isotropic_intersection_size_bound_mem_of_le A v hv hcA _ (by omega) have hrep : isotropic_intersection_size_bound_chainRep A v (c - ((isotropic_intersection_size_bound_chainLen A v r - i : ℕ) : ℝ) • v) = r := by rw [isotropic_intersection_size_bound_chainRep_index A v hv hcA (l := isotropic_intersection_size_bound_chainLen A v r - i) (by omega), hcr] have hceq : c = r + (isotropic_intersection_size_bound_chainLen A v r : ℝ) • v := by have h := isotropic_intersection_size_bound_chainRep_eq_add A v c rw [hcr, hcm'] at h exact h.symm have heq : r + (i : ℝ) • v = c - ((isotropic_intersection_size_bound_chainLen A v r - i : ℕ) : ℝ) • v := by rw [hceq] have hsc : ((isotropic_intersection_size_bound_chainLen A v r : ℝ) - ((isotropic_intersection_size_bound_chainLen A v r - i : ℕ) : ℝ)) = (i : ℝ) := by rw [Nat.cast_sub hile]; ring rw [← hsc, sub_smul] abel rw [heq] exact (isotropic_intersection_size_bound_mem_chain A v).mpr ⟨hmemc, hrep⟩lemma isotropic_intersection_size_bound_chain_inj (hv : v ≠ 0) {r : V} : Set.InjOn (fun i : ℕ => r + (i : ℝ) • v) ↑(Finset.range (isotropic_intersection_size_bound_chainLen A v r + 1)) := by intro i _ j _ hij exact isotropic_intersection_size_bound_nat_smul_inj hv (add_left_cancel hij)lemma isotropic_intersection_size_bound_chain_card {r : V} (hv : v ≠ 0) (hr : r ∈ A) (hfix : isotropic_intersection_size_bound_chainRep A v r = r) : (isotropic_intersection_size_bound_chain A v r).card = isotropic_intersection_size_bound_chainLen A v r + 1 := by classical rw [isotropic_intersection_size_bound_chain_image A v hv hr hfix, Finset.card_image_of_injOn (isotropic_intersection_size_bound_chain_inj A v hv), Finset.card_range]/-- Quadratic energy of a single chain is at least `(1/2)·chainLen·‖v‖⁴`. -/lemma isotropic_intersection_size_bound_chain_energy {r : V} (hv : v ≠ 0) (hr : r ∈ A) (hfix : isotropic_intersection_size_bound_chainRep A v r = r) : (1 / 2) * (isotropic_intersection_size_bound_chainLen A v r : ℝ) * ‖v‖ ^ 4 ≤ ∑ b ∈ isotropic_intersection_size_bound_chain A v r, (inner (𝕜 := ℝ) b v) ^ 2 := by classical set n := isotropic_intersection_size_bound_chainLen A v r + 1 with hn set s := ‖v‖ ^ 2 with hs have hs_pos : 0 < s := by have hvpos : 0 < ‖v‖ := norm_pos_iff.mpr hv rw [hs]; positivity have hncast : ((n : ℝ) - 1) = (isotropic_intersection_size_bound_chainLen A v r : ℝ) := by rw [hn]; push_cast; ring have h4 : ‖v‖ ^ 4 = s ^ 2 := by rw [hs]; ring have himg : isotropic_intersection_size_bound_chain A v r = (Finset.range n).image (fun i : ℕ => r + (i : ℝ) • v) := by rw [isotropic_intersection_size_bound_chain_image A v hv hr hfix, hn] have hinj : Set.InjOn (fun i : ℕ => r + (i : ℝ) • v) ↑(Finset.range n) := by rw [hn]; exact isotropic_intersection_size_bound_chain_inj A v hv have hsum1 : ∑ b ∈ isotropic_intersection_size_bound_chain A v r, (inner (𝕜 := ℝ) b v) ^ 2 = ∑ i ∈ Finset.range n, (inner (𝕜 := ℝ) r v + (i : ℝ) * s) ^ 2 := by rw [himg, Finset.sum_image hinj] apply Finset.sum_congr rfl intro i hi rw [inner_add_left, real_inner_smul_left, real_inner_self_eq_norm_sq, ← hs] have hsplit : ∑ i ∈ Finset.range n, (inner (𝕜 := ℝ) r v + (i : ℝ) * s) ^ 2 = s ^ 2 * ∑ i ∈ Finset.range n, (inner (𝕜 := ℝ) r v / s + (i : ℝ)) ^ 2 := by rw [Finset.mul_sum] apply Finset.sum_congr rfl intro i hi have h1 : inner (𝕜 := ℝ) r v + (i : ℝ) * s = s * (inner (𝕜 := ℝ) r v / s + (i : ℝ)) := by field_simp rw [h1]; ring have hT : (1 / 12) * (n : ℝ) * ((n : ℝ) ^ 2 - 1) ≤ ∑ i ∈ Finset.range n, (inner (𝕜 := ℝ) r v / s + (i : ℝ)) ^ 2 := sum_range_sq_add_ge n (inner (𝕜 := ℝ) r v / s) have hcub : (1 / 2) * ((n : ℝ) - 1) ≤ (1 / 12) * (n : ℝ) * ((n : ℝ) ^ 2 - 1) := by have := isotropic_chain_cubic_ineq n linarith have hstep1 : (1 / 2) * (isotropic_intersection_size_bound_chainLen A v r : ℝ) * ‖v‖ ^ 4 = ((1 / 2) * ((n : ℝ) - 1)) * s ^ 2 := by rw [← hncast, h4] rw [hstep1, hsum1, hsplit] calc ((1 / 2) * ((n : ℝ) - 1)) * s ^ 2 ≤ ((1 / 12) * (n : ℝ) * ((n : ℝ) ^ 2 - 1)) * s ^ 2 := mul_le_mul_of_nonneg_right hcub (sq_nonneg s) _ ≤ (∑ i ∈ Finset.range n, (inner (𝕜 := ℝ) r v / s + (i : ℝ)) ^ 2) * s ^ 2 := mul_le_mul_of_nonneg_right hT (sq_nonneg s) _ = s ^ 2 * ∑ i ∈ Finset.range n, (inner (𝕜 := ℝ) r v / s + (i : ℝ)) ^ 2 := mul_comm (∑ i ∈ Finset.range n, (inner (𝕜 := ℝ) r v / s + (i : ℝ)) ^ 2) (s ^ 2)/-- A chain of length `M + 1` contributes exactly `M` points to `v + A`. -/lemma isotropic_intersection_size_bound_chain_count {r : V} (hv : v ≠ 0) (hr : r ∈ A) (hfix : isotropic_intersection_size_bound_chainRep A v r = r) : ∑ b ∈ isotropic_intersection_size_bound_chain A v r, (if b - v ∈ A then (1 : ℝ) else 0) = (isotropic_intersection_size_bound_chainLen A v r : ℝ) := by classical have himg : isotropic_intersection_size_bound_chain A v r = (Finset.range (isotropic_intersection_size_bound_chainLen A v r + 1)).image (fun i : ℕ => r + (i : ℝ) • v) := isotropic_intersection_size_bound_chain_image A v hv hr hfix have hinj : Set.InjOn (fun i : ℕ => r + (i : ℝ) • v) ↑(Finset.range (isotropic_intersection_size_bound_chainLen A v r + 1)) := isotropic_intersection_size_bound_chain_inj A v hv rw [himg, Finset.sum_image hinj, Finset.sum_range_succ'] have h0 : (if (r + ((0 : ℕ) : ℝ) • v) - v ∈ A then (1 : ℝ) else 0) = 0 := by have hnot : r - v ∉ A := by rw [← hfix] exact isotropic_intersection_size_bound_chainRep_sub_v A v hv hr have heq : r + ((0 : ℕ) : ℝ) • v - v = r - v := by simp rw [heq] simp [hnot] rw [h0, add_zero] have hk : ∀ k ∈ Finset.range (isotropic_intersection_size_bound_chainLen A v r), (if (r + (((k + 1 : ℕ)) : ℝ) • v) - v ∈ A then (1 : ℝ) else 0) = 1 := by intro k hk have hk' : k < isotropic_intersection_size_bound_chainLen A v r := Finset.mem_range.mp hk have heq : r + (((k + 1 : ℕ)) : ℝ) • v - v = r + (k : ℝ) • v := by push_cast rw [add_smul, one_smul] abel have hmem : r + (k : ℝ) • v ∈ A := by have h1 : r + (k : ℝ) • v ∈ (Finset.range (isotropic_intersection_size_bound_chainLen A v r + 1)).image (fun i : ℕ => r + (i : ℝ) • v) := Finset.mem_image.mpr ⟨k, Finset.mem_range.mpr (by omega), rfl⟩ rw [← himg] at h1 exact ((isotropic_intersection_size_bound_mem_chain A v).mp h1).1 rw [heq] simp [hmem] rw [Finset.sum_congr rfl hk] simpend IsotropicIntersectionBoundHelpersopen scoped Pointwise in/-- Intersection size bound for sets in isotropic position (arXiv:2611.04644 Lemma A.4). -/theorem isotropic_intersection_size_bound (d : ℕ) (A : Finset (EuclideanSpace ℝ (Fin d))) (h_nonempty : A.Nonempty) (h_mean : ∑ a ∈ A, a = 0) (h_cov : ∀ u : EuclideanSpace ℝ (Fin d), ∑ a ∈ A, (inner (𝕜 := ℝ) a u) ^ 2 = (A.card : ℝ) * ‖u‖ ^ 2) (v : EuclideanSpace ℝ (Fin d)) (hv : v ≠ 0) : ((A ∩ (v +ᵥ A)).card : ℝ) ≤ 2 * (A.card : ℝ) / ‖v‖ ^ 2 := by classical have hInter : A ∩ (v +ᵥ A) = A.filter (fun a => a - v ∈ A) := by ext a simp only [Finset.mem_inter, Finset.mem_filter, Finset.mem_vadd_finset, vadd_eq_add] constructor · rintro ⟨ha, y, hy, hya⟩ refine ⟨ha, ?_⟩ rw [← hya] have h : v + y - v = y := by abel rw [h] exact hy · rintro ⟨ha, hav⟩ exact ⟨ha, a - v, hav, by abel⟩ have hN : ((A ∩ (v +ᵥ A)).card : ℝ) = ∑ a ∈ A, (if a - v ∈ A then (1 : ℝ) else 0) := by rw [hInter] exact (Finset.sum_boole (fun a => a - v ∈ A) A).symm have hmaps : ∀ a ∈ A, isotropic_intersection_size_bound_chainRep A v a ∈ isotropic_intersection_size_bound_chainStarts A v := by intro a ha exact Finset.mem_image_of_mem _ ha have hfib : ∀ r ∈ isotropic_intersection_size_bound_chainStarts A v, isotropic_intersection_size_bound_chainRep A v r = r ∧ r ∈ A := by intro r hr obtain ⟨a, ha, rfl⟩ := Finset.mem_image.mp hr exact ⟨isotropic_intersection_size_bound_chainRep_fix A v hv ha, isotropic_intersection_size_bound_chainRep_mem A v hv ha⟩ have hcount : ((A ∩ (v +ᵥ A)).card : ℝ) = ∑ r ∈ isotropic_intersection_size_bound_chainStarts A v, (isotropic_intersection_size_bound_chainLen A v r : ℝ) := by rw [hN, ← Finset.sum_fiberwise_of_maps_to hmaps (fun a : EuclideanSpace ℝ (Fin d) => if a - v ∈ A then (1 : ℝ) else 0)] exact Finset.sum_congr rfl (fun r hr => isotropic_intersection_size_bound_chain_count A v hv (hfib r hr).2 (hfib r hr).1) have hsplit_energy : ∑ r ∈ isotropic_intersection_size_bound_chainStarts A v, ∑ b ∈ isotropic_intersection_size_bound_chain A v r, (inner (𝕜 := ℝ) b v) ^ 2 = ∑ a ∈ A, (inner (𝕜 := ℝ) a v) ^ 2 := Finset.sum_fiberwise_of_maps_to hmaps _ have henergy : ∑ r ∈ isotropic_intersection_size_bound_chainStarts A v, (1 / 2) * (isotropic_intersection_size_bound_chainLen A v r : ℝ) * ‖v‖ ^ 4 ≤ ∑ a ∈ A, (inner (𝕜 := ℝ) a v) ^ 2 := by rw [← hsplit_energy] exact Finset.sum_le_sum (fun r hr => isotropic_intersection_size_bound_chain_energy A v hv (hfib r hr).2 (hfib r hr).1) have hmain : (1 / 2) * ‖v‖ ^ 4 * ((A ∩ (v +ᵥ A)).card : ℝ) ≤ (A.card : ℝ) * ‖v‖ ^ 2 := by rw [hcount] have hfac : (1 / 2) * ‖v‖ ^ 4 * ∑ r ∈ isotropic_intersection_size_bound_chainStarts A v, (isotropic_intersection_size_bound_chainLen A v r : ℝ) = ∑ r ∈ isotropic_intersection_size_bound_chainStarts A v, (1 / 2) * (isotropic_intersection_size_bound_chainLen A v r : ℝ) * ‖v‖ ^ 4 := by rw [Finset.mul_sum] exact Finset.sum_congr rfl (fun r _ => by ring) rw [hfac] exact henergy.trans (le_of_eq (h_cov v)) have hvpos : (0 : ℝ) < ‖v‖ ^ 2 := by have h1 : 0 < ‖v‖ := norm_pos_iff.mpr hv positivity have hkey : ‖v‖ ^ 2 * ((A ∩ (v +ᵥ A)).card : ℝ) ≤ 2 * (A.card : ℝ) := by have h2 : ‖v‖ ^ 4 * ((A ∩ (v +ᵥ A)).card : ℝ) ≤ 2 * ((A.card : ℝ) * ‖v‖ ^ 2) := by nlinarith [hmain] have h4 : ‖v‖ ^ 4 = ‖v‖ ^ 2 * ‖v‖ ^ 2 := by ring have h3 : ‖v‖ ^ 2 * (‖v‖ ^ 2 * ((A ∩ (v +ᵥ A)).card : ℝ)) ≤ ‖v‖ ^ 2 * (2 * (A.card : ℝ)) := by nlinarith [h2, h4] exact le_of_mul_le_mul_left h3 hvpos rw [le_div_iff₀ hvpos] calc ((A ∩ (v +ᵥ A)).card : ℝ) * ‖v‖ ^ 2 = ‖v‖ ^ 2 * ((A ∩ (v +ᵥ A)).card : ℝ) := by ring _ ≤ 2 * (A.card : ℝ) := hkey