random_deletion_inequality_k_ap
Let π and π be families in Finset (Finset (Fin n)) such that π is an up-set, π is a down-set, and for every A β π and C β π, the difference A \ C contains a k-term arithmetic progression in Fin n. For each X : Finset (Fin n), let p X : Finset (Fin n) β β be a probability distribution supported on subsets Z β X with β Z β X.powerset, p X Z = 1. Define W X = β Z β X.powerset, p X Z * (if X \ Z β π then 1 else 0). If W X > 0 for all X, then ((π.card : β) / 2 ^ n) * ((π.card : β) / 2 ^ n) β€ (1 / (2 ^ n : β)) * β X : Finset (Fin n), (((π.card : β) / 2 ^ n) / W X) * β Z β X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0).
Statement
open scoped BigOperators Classical in theorem random_deletion_inequality_k_ap (n k : β) (π π : Finset (Finset (Fin n))) (hA_upper : IsUpperSet (π : Set (Finset (Fin n)))) (hC_lower : IsLowerSet (π : Set (Finset (Fin n)))) (h_cross : β A β π, β C β π, finset_contains_k_ap n k (A \ C)) (p : Finset (Fin n) β Finset (Fin n) β β) (hp_nonneg : β X Z, 0 β€ p X Z) (hp_supp : β X Z, p X Z β 0 β Z β X) (hp_sum : β X, β Z β X.powerset, p X Z = 1) (W : Finset (Fin n) β β) (hW : β X, W X = β Z β X.powerset, p X Z * (if X \ Z β π then 1 else 0)) (hW_pos : β X, 0 < W X) : ((π.card : β) / 2 ^ n) * ((π.card : β) / 2 ^ n) β€ (1 / (2 ^ n : β)) * β X : Finset (Fin n), (((π.card : β) / 2 ^ n) / W X) * β Z β X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0)
- Formalizes
- arXiv:2610.26243 Lemma 2.2 -- Families that intersect in an arithmetic progression
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- finset_contains_k_apA subset s of Fin n contains a k-term arithmetic progression if there exist a and d with 1 β€ d such that a + i * d is in s for all 0 β€ i <β¦
Read back from the Lean
For any natural numbers $n$ and $k$, let $\mathcal{A}$ and $\mathcal{C}$ be families (finsets) of subsets of $\mathrm{Fin}(n)$. Assume:
1. $\mathcal{A}$ is an upper set under inclusion (if $A \in \mathcal{A}$ and $A \subseteq B \subseteq \mathrm{Fin}(n)$, then $B \in \mathcal{A}$).
2. $\mathcal{C}$ is a lower set under inclusion (if $C \in \mathcal{C}$ and $B \subseteq C$, then $B \in \mathcal{C}$).
3. For every $A \in \mathcal{A}$ and $C \in \mathcal{C}$, the set difference $A \setminus C$ contains a $k$-term arithmetic progression (in the sense of finset_contains_k_ap).
4. $p : \mathcal{P}(\mathrm{Fin}(n)) \to \mathcal{P}(\mathrm{Fin}(n)) \to \mathbb{R}$ is a function such that:
- $p(X, Z) \ge 0$ for all $X, Z$,
- if $p(X, Z) \neq 0$, then $Z \subseteq X$,
- for every $X$, $\sum_{Z \subseteq X} p(X, Z) = 1$.
5. $W : \mathcal{P}(\mathrm{Fin}(n)) \to \mathbb{R}$ satisfies $W(X) = \sum_{Z \subseteq X} p(X, Z) \cdot \mathbf{1}_{X \setminus Z \in \mathcal{C}}$ for all $X$.
6. $W(X) > 0$ for all $X$.
Then:
$$\frac{|\mathcal{A}|}{2^n} \cdot \frac{|\mathcal{C}|}{2^n} \le \frac{1}{2^n} \sum_{X \subseteq \mathrm{Fin}(n)} \left( \frac{|\mathcal{C}| / 2^n}{W(X)} \sum_{Z \subseteq X} p(X, Z) \cdot \mathbf{1}_{Z \text{ contains a } k\text{-AP}} \right)$$
where $\mathbf{1}_P$ is $1$ if $P$ holds and $0$ otherwise.
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 bounds the product density (|π| / 2^n) * (|π| / 2^n) via a double-counting indicator argument. For any set X and subset Z β X, whenever X β π and X \ Z β π, the cross-intersection hypothesis implies that Z = X \ (X \ Z) contains a k-term arithmetic progression. Weighting by p X Z, summing over Z β X, and dividing by W X yields a bound on the indicator 1_{X β π}. Multiplying by |π| / 2^n and summing over all X evaluates the total indicator weight as |π|, after which multiplying by 1 / 2^n produces the final inequality.
For any X and Z β X, the indicator product satisfies 1_{X β π} Β· (p X Z Β· 1_{X \ Z β π}) β€ p X Z Β· 1_{finset_contains_k_ap n k Z}.
Fix X and Z β X. When X β π and X \ Z β π, the cross-intersection hypothesis `h_cross` guarantees that the set difference X \ (X \ Z) contains a k-term arithmetic progression. Because Z β X (`Finset.mem_powerset.mp`), the double difference X \ (X \ Z) is equal to Z (`Finset.sdiff_sdiff_eq_self`), so Z contains a k-AP. Thus the product of indicators 1_{X β π} Β· 1_{X \ Z β π} is at most 1_{Z contains a k-AP}. In all other cases, at least one indicator is 0, so the product is 0 and the inequality holds trivially. Multiplying both sides by the non-negative weight p X Z (`mul_le_mul_of_nonneg_left`) yields the pointwise bound.
uses
Finset.mem_powerset.mp,Finset.sdiff_sdiff_eq_self,mul_le_mul_of_nonneg_lefthave h_le_Z : β (X Z : Finset (Fin n)), Z β X.powerset β (if X β π then (1 : β) else 0) * (p X Z * (if X \ Z β π then 1 else 0)) β€ p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := by intro X Z hZ have hZ_sub : Z β X := Finset.mem_powerset.mp hZ have h_ineq : (if X β π then (1 : β) else 0) * (if X \ Z β π then 1 else 0) β€ (if finset_contains_k_ap n k Z then 1 else 0) := by by_cases hX : X β π Β· by_cases hC : X \ Z β π Β· have h_ap : finset_contains_k_ap n k Z := by have := h_cross X hX (X \ Z) hC rwa [Finset.sdiff_sdiff_eq_self hZ_sub] at this simp [hX, hC, h_ap] Β· simp only [hX, hC, βreduceIte, mul_zero] split_ifs <;> linarith Β· simp only [hX, βreduceIte, zero_mul] split_ifs <;> linarith have hp := hp_nonneg X Z calc (if X β π then (1 : β) else 0) * (p X Z * (if X \ Z β π then 1 else 0)) _ = p X Z * ((if X β π then (1 : β) else 0) * (if X \ Z β π then 1 else 0)) := by ring _ β€ p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := mul_le_mul_of_nonneg_left h_ineq hp
For each X, 1_{X β π} Β· (|π| / 2^n) β€ ((|π| / 2^n) / W X) * β Z β X.powerset, p X Z * 1_{finset_contains_k_ap n k Z}.
Summing the pointwise inequality over all Z β X and distributing the indicator factor (`Finset.mul_sum`, `Finset.sum_le_sum`) gives 1_{X β π} Β· W X β€ β Z β X.powerset, p X Z * 1_{finset_contains_k_ap n k Z}. Since W X > 0 (`hW_pos`), dividing by W X preserves the inequality (`le_div_iffβ`), isolating 1_{X β π}. Multiplying both sides by the non-negative scalar |π| / 2^n (`mul_le_mul_of_nonneg_right`) and rearranging algebraically yields the desired bound for each X.
uses
Finset.mul_sum,Finset.sum_le_sum,le_div_iffβ,mul_le_mul_of_nonneg_righthave h_le_X : β X : Finset (Fin n), (if X β π then (1 : β) else 0) * ((π.card : β) / 2 ^ n) β€ (((π.card : β) / 2 ^ n) / W X) * β Z β X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := by intro X have h_sum_le : (if X β π then (1 : β) else 0) * W X β€ β Z β X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := by rw [hW X, Finset.mul_sum] exact Finset.sum_le_sum (h_le_Z X) have hW_pos_X := hW_pos X have h_div : (if X β π then (1 : β) else 0) β€ (β Z β X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0)) / W X := by rw [le_div_iffβ hW_pos_X] linarith have hC_nonneg : 0 β€ (π.card : β) / 2 ^ n := by positivity have := mul_le_mul_of_nonneg_right h_div hC_nonneg calc (if X β π then (1 : β) else 0) * ((π.card : β) / 2 ^ n) _ β€ ((β Z β X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0)) / W X) * ((π.card : β) / 2 ^ n) := this _ = (((π.card : β) / 2 ^ n) / W X) * β Z β X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := by ring
Summing over all X, |π| * (|π| / 2^n) β€ β X, ((|π| / 2^n) / W X) * β Z β X.powerset, p X Z * 1_{finset_contains_k_ap n k Z}.
Summing the inequality for each X over all X : Finset (Fin n) (`Finset.sum_le_sum`), the left-hand side is β X, 1_{X β π} * (|π| / 2^n). Factoring out the constant |π| / 2^n (`Finset.sum_mul`) leaves β X, 1_{X β π}, which equals |π| by rewriting the indicator sum as a cardinality sum (`Finset.sum_filter`).
uses
Finset.sum_le_sum,Finset.sum_mul,Finset.sum_filterhave h_sum_all : β X : Finset (Fin n), (if X β π then (1 : β) else 0) * ((π.card : β) / 2 ^ n) β€ β X : Finset (Fin n), (((π.card : β) / 2 ^ n) / W X) * β Z β X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := Finset.sum_le_sum (fun X _ => h_le_X X) rw [β Finset.sum_mul] at h_sum_all have h_sum_A : β X : Finset (Fin n), (if X β π then (1 : β) else 0) = (π.card : β) := by rw [β Finset.sum_filter] simp rw [h_sum_A] at h_sum_all
(|π| / 2^n) * (|π| / 2^n) β€ (1 / 2^n) * β X, ((|π| / 2^n) / W X) * β Z β X.powerset, p X Z * 1_{finset_contains_k_ap n k Z}.
Since 1 / 2^n β₯ 0, multiplying both sides of the summed inequality by 1 / 2^n on the left preserves the inequality (`mul_le_mul_of_nonneg_left`). Ring arithmetic then rewrites (1 / 2^n) * (|π| * (|π| / 2^n)) as (|π| / 2^n) * (|π| / 2^n), matching the theorem conclusion.
uses
mul_le_mul_of_nonneg_lefthave h_pow_pos : 0 β€ (1 : β) / 2 ^ n := by positivity have h_final := mul_le_mul_of_nonneg_left h_sum_all h_pow_pos calc ((π.card : β) / 2 ^ n) * ((π.card : β) / 2 ^ n) _ = (1 / (2 ^ n : β)) * ((π.card : β) * ((π.card : β) / 2 ^ n)) := by ring _ β€ (1 / (2 ^ n : β)) * β X : Finset (Fin n), (((π.card : β) / 2 ^ n) / W X) * β Z β X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := h_final
Finset.mem_powerset.mp- An element belongs to the power set of X if and only if it is a subset of X.
Finset.sdiff_sdiff_eq_self- For a subset t β s, the double relative complement s \ (s \ t) equals t.
mul_le_mul_of_nonneg_left- Multiplying both sides of an inequality b β€ c on the left by a non-negative element a β₯ 0 preserves the inequality: a * b β€ a * c.
Finset.mul_sum- Multiplication on the left distributes over a finite sum: a * β i β s, f i = β i β s, a * f i.
Finset.sum_le_sum- If f i β€ g i for all i in a finite set s, then β i β s, f i β€ β i β s, g i.
le_div_iffβ- For c > 0, the inequality a β€ b / c is equivalent to a * c β€ b.
mul_le_mul_of_nonneg_right- Multiplying both sides of an inequality b β€ c on the right by a non-negative element a β₯ 0 preserves the inequality: b * a β€ c * a.
Finset.sum_mul- Multiplication on the right distributes over a finite sum: (β i β s, f i) * a = β i β s, (f i * a).
Finset.sum_filter- Summing f a over elements satisfying predicate p equals summing the indicator term `if p a then f a else 0` over the whole set.
- The hypotheses `hA_upper` (π is an upper set), `hC_lower` (π is a lower set), `hp_supp` (support condition on p), and `hp_sum` (p sums to 1) are present in the theorem statement following Lemma 2.2 of arXiv:2610.26243, but the algebraic inequality proved here requires only the cross-intersection property `h_cross`, non-negativity `hp_nonneg`, and positivity `hW_pos`.
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 BigOperators Classical in/-- Random-deletion inequality for the product density of k-AP cross-intersecting families (arXiv:2610.26243, Lemma 2.2). -/theorem random_deletion_inequality_k_ap (n k : β) (π π : Finset (Finset (Fin n))) (hA_upper : IsUpperSet (π : Set (Finset (Fin n)))) (hC_lower : IsLowerSet (π : Set (Finset (Fin n)))) (h_cross : β A β π, β C β π, finset_contains_k_ap n k (A \ C)) (p : Finset (Fin n) β Finset (Fin n) β β) (hp_nonneg : β X Z, 0 β€ p X Z) (hp_supp : β X Z, p X Z β 0 β Z β X) (hp_sum : β X, β Z β X.powerset, p X Z = 1) (W : Finset (Fin n) β β) (hW : β X, W X = β Z β X.powerset, p X Z * (if X \ Z β π then 1 else 0)) (hW_pos : β X, 0 < W X) : ((π.card : β) / 2 ^ n) * ((π.card : β) / 2 ^ n) β€ (1 / (2 ^ n : β)) * β X : Finset (Fin n), (((π.card : β) / 2 ^ n) / W X) * β Z β X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := by have h_le_Z : β (X Z : Finset (Fin n)), Z β X.powerset β (if X β π then (1 : β) else 0) * (p X Z * (if X \ Z β π then 1 else 0)) β€ p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := by intro X Z hZ have hZ_sub : Z β X := Finset.mem_powerset.mp hZ have h_ineq : (if X β π then (1 : β) else 0) * (if X \ Z β π then 1 else 0) β€ (if finset_contains_k_ap n k Z then 1 else 0) := by by_cases hX : X β π Β· by_cases hC : X \ Z β π Β· have h_ap : finset_contains_k_ap n k Z := by have := h_cross X hX (X \ Z) hC rwa [Finset.sdiff_sdiff_eq_self hZ_sub] at this simp [hX, hC, h_ap] Β· simp only [hX, hC, βreduceIte, mul_zero] split_ifs <;> linarith Β· simp only [hX, βreduceIte, zero_mul] split_ifs <;> linarith have hp := hp_nonneg X Z calc (if X β π then (1 : β) else 0) * (p X Z * (if X \ Z β π then 1 else 0)) _ = p X Z * ((if X β π then (1 : β) else 0) * (if X \ Z β π then 1 else 0)) := by ring _ β€ p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := mul_le_mul_of_nonneg_left h_ineq hp have h_le_X : β X : Finset (Fin n), (if X β π then (1 : β) else 0) * ((π.card : β) / 2 ^ n) β€ (((π.card : β) / 2 ^ n) / W X) * β Z β X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := by intro X have h_sum_le : (if X β π then (1 : β) else 0) * W X β€ β Z β X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := by rw [hW X, Finset.mul_sum] exact Finset.sum_le_sum (h_le_Z X) have hW_pos_X := hW_pos X have h_div : (if X β π then (1 : β) else 0) β€ (β Z β X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0)) / W X := by rw [le_div_iffβ hW_pos_X] linarith have hC_nonneg : 0 β€ (π.card : β) / 2 ^ n := by positivity have := mul_le_mul_of_nonneg_right h_div hC_nonneg calc (if X β π then (1 : β) else 0) * ((π.card : β) / 2 ^ n) _ β€ ((β Z β X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0)) / W X) * ((π.card : β) / 2 ^ n) := this _ = (((π.card : β) / 2 ^ n) / W X) * β Z β X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := by ring have h_sum_all : β X : Finset (Fin n), (if X β π then (1 : β) else 0) * ((π.card : β) / 2 ^ n) β€ β X : Finset (Fin n), (((π.card : β) / 2 ^ n) / W X) * β Z β X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := Finset.sum_le_sum (fun X _ => h_le_X X) rw [β Finset.sum_mul] at h_sum_all have h_sum_A : β X : Finset (Fin n), (if X β π then (1 : β) else 0) = (π.card : β) := by rw [β Finset.sum_filter] simp rw [h_sum_A] at h_sum_all have h_pow_pos : 0 β€ (1 : β) / 2 ^ n := by positivity have h_final := mul_le_mul_of_nonneg_left h_sum_all h_pow_pos calc ((π.card : β) / 2 ^ n) * ((π.card : β) / 2 ^ n) _ = (1 / (2 ^ n : β)) * ((π.card : β) * ((π.card : β) / 2 ^ n)) := by ring _ β€ (1 / (2 ^ n : β)) * β X : Finset (Fin n), (((π.card : β) / 2 ^ n) / W X) * β Z β X.powerset, p X Z * (if finset_contains_k_ap n k Z then 1 else 0) := h_final