closed_network_am_gm_product_bound
For any integer n ≥ 1 and any non-negative tuples x, y : Fin n → ℝ satisfying x i + y i ≤ 1 for all i, (∏ i, x i) ^ (1 / n) + (∏ i, y i) ^ (1 / n) ≤ 1.
Statement
theorem closed_network_am_gm_product_bound
(n : ℕ) (hn : 1 ≤ n) (x y : Fin n → ℝ)
(hx : ∀ i, 0 ≤ x i) (hy : ∀ i, 0 ≤ y i)
(hxy : ∀ i, x i + y i ≤ 1) :
(∏ i : Fin n, x i) ^ (1 / (n : ℝ)) +
(∏ i : Fin n, y i) ^ (1 / (n : ℝ)) ≤ 1- Source
- arXiv:2610.35838 Eq. 31-32
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- closed_network_bound_of_product_boundsFor any integer n ≥ 1, real correlator values I, J, and non-negative tuples x, y : Fin n → ℝ satisfying x i + y i ≤ 1 for all i, if |I| ≤…
Read back from the Lean
For any natural number $n$ with $1 \le n$ and any families of real numbers $x, y : \mathrm{Fin}\ n \to \mathbb{R}$, if $x(i) \ge 0$, $y(i) \ge 0$, and $x(i) + y(i) \le 1$ for all $i \in \mathrm{Fin}\ n$, then $$\left(\prod_{i \in \mathrm{Fin}\ n} x(i)\right)^{1/n} + \left(\prod_{i \in \mathrm{Fin}\ n} y(i)\right)^{1/n} \le 1.$$
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 applies the unweighted arithmetic mean - geometric mean (AM-GM) inequality to each of the two tuples, bounding each geometric mean by its corresponding arithmetic mean: $(\prod x_i)^{1/n} ≤ \frac{1}{n} \sum x_i$ and $(\prod y_i)^{1/n} ≤ \frac{1}{n} \sum y_i$. Summing the pointwise hypothesis $x_i + y_i ≤ 1$ across all $n$ components gives $\sum (x_i + y_i) ≤ n$, meaning the sum of the two arithmetic means is at most 1. Chaining these inequalities immediately yields the desired bound $(\prod x_i)^{1/n} + (\prod y_i)^{1/n} ≤ 1$.
For any $n ≥ 1$ and non-negative tuple $z$, the unweighted geometric mean is at most the arithmetic mean: $(\prod_i z_i)^{1/n} ≤ \frac{1}{n} \sum_i z_i$.
Since $1 ≤ n$, we have $n > 0$ as both a natural number and a real number. We instantiate the general weighted AM-GM inequality (`Real.geom_mean_le_arith_mean`) on the index set `Fin n` with uniform weights $w_i = 1$. The weights are non-negative, their sum is $n > 0$, and each $z_i ≥ 0$. Simplifying the powers and denominators in the weighted inequality yields the unweighted AM-GM inequality.
uses
Real.geom_mean_le_arith_meanhave hn0 : (0:ℕ) < n := hn have hn0' : (0:ℝ) < (n:ℝ) := by exact_mod_cast hn0 have h := Real.geom_mean_le_arith_mean (Finset.univ : Finset (Fin n)) (fun _ => (1:ℝ)) z (by intro i _; norm_num) (by simpa using hn0') (by intro i _; exact hz i) simpa using h
The geometric means of $x$ and $y$ are bounded by their respective arithmetic means: $(\prod_i x_i)^{1/n} ≤ \frac{1}{n} \sum_i x_i$ and $(\prod_i y_i)^{1/n} ≤ \frac{1}{n} \sum_i y_i$.
Casting $1 ≤ n$ establishes $0 < (n : ℝ)$. Applying the helper lemma `closed_network_am_gm_product_bound_geom` to $x$ and to $y$, using the given non-negativity hypotheses, yields the arithmetic-geometric mean bound for each tuple.
uses
closed_network_am_gm_product_bound_geomhave hn0 : (0:ℕ) < n := hn have hn0' : (0:ℝ) < (n:ℝ) := by exact_mod_cast hn0 have h1 := closed_network_am_gm_product_bound_geom n hn x hx have h2 := closed_network_am_gm_product_bound_geom n hn y hy
The total sum of all components is at most $n$: $\sum_i x_i + \sum_i y_i ≤ n$.
Summing the pointwise hypothesis $x_i + y_i ≤ 1$ over all $i \in \text{Fin } n$ using `Finset.sum_le_sum` gives $\sum_i (x_i + y_i) ≤ \sum_i 1 = n$. Distributing the sum on the left via `Finset.sum_add_distrib` yields $\sum_i x_i + \sum_i y_i ≤ n$.
uses
Finset.sum_le_sum,Finset.sum_add_distribhave hsum : (∑ i : Fin n, x i) + (∑ i : Fin n, y i) ≤ n := by have : (∑ i : Fin n, (x i + y i)) ≤ ∑ i : Fin n, (1:ℝ) := Finset.sum_le_sum (fun i _ => hxy i) rw [Finset.sum_add_distrib] at this simpa using this
The sum of the arithmetic means is at most 1, which bounds the sum of the geometric means by 1: $(\prod_i x_i)^{1/n} + (\prod_i y_i)^{1/n} ≤ 1$.
Combining fractions via `add_div` and clearing the positive divisor $n$ using `div_le_iff₀` reduces the inequality $\frac{1}{n}\sum_i x_i + \frac{1}{n}\sum_i y_i ≤ 1$ to $\sum_i x_i + \sum_i y_i ≤ n$, which was established in the previous step. Finally, linear arithmetic (`linarith`) adds the two AM-GM bounds for $x$ and $y$ to this bound on the arithmetic means to conclude the theorem.
uses
add_div,div_le_iff₀have hsum' : (∑ i : Fin n, x i) / n + (∑ i : Fin n, y i) / n ≤ 1 := by rw [← add_div] rw [div_le_iff₀ hn0'] linarith linarith
Real.geom_mean_le_arith_mean- For any finite set of non-negative weights with positive sum and any non-negative values, the weighted geometric mean is at most the weighted arithmetic mean.
closed_network_am_gm_product_bound_geom- For any integer $n ≥ 1$ and non-negative $n$-tuple $z$, the unweighted geometric mean $(\prod_i z_i)^{1/n}$ is at most the arithmetic mean $\frac{1}{n} \sum_i z_i$.
Finset.sum_le_sum- If $f(i) ≤ g(i)$ for all elements $i$ in a finite set, then the sum of $f$ over that set is at most the sum of $g$.
Finset.sum_add_distrib- The sum of a pointwise sum of two functions over a finite set equals the sum of the individual sums: $\sum_i (f(i) + g(i)) = \sum_i f(i) + \sum_i g(i)$.
add_div- Division distributes over addition from the right: $(a + b) / c = a / c + b / c$.
div_le_iff₀- For a positive divisor $c > 0$, $b / c ≤ a$ if and only if $b ≤ a \cdot c$.
- Lean distinguishes the natural number $n$ from the real number $n$, requiring an explicit cast (`exact_mod_cast`) to deduce $0 < (n : ℝ)$ from $1 ≤ n$.
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.
private lemma closed_network_am_gm_product_bound_geom (n : ℕ) (hn : 1 ≤ n) (z : Fin n → ℝ) (hz : ∀ i, 0 ≤ z i) : (∏ i : Fin n, z i) ^ (1 / (n : ℝ)) ≤ (∑ i : Fin n, z i) / n := by have hn0 : (0:ℕ) < n := hn have hn0' : (0:ℝ) < (n:ℝ) := by exact_mod_cast hn0 have h := Real.geom_mean_le_arith_mean (Finset.univ : Finset (Fin n)) (fun _ => (1:ℝ)) z (by intro i _; norm_num) (by simpa using hn0') (by intro i _; exact hz i) simpa using h/-- AM-GM inequality applied to products of normalized responses in an n-local network. -/theorem closed_network_am_gm_product_bound (n : ℕ) (hn : 1 ≤ n) (x y : Fin n → ℝ) (hx : ∀ i, 0 ≤ x i) (hy : ∀ i, 0 ≤ y i) (hxy : ∀ i, x i + y i ≤ 1) : (∏ i : Fin n, x i) ^ (1 / (n : ℝ)) + (∏ i : Fin n, y i) ^ (1 / (n : ℝ)) ≤ 1 := by have hn0 : (0:ℕ) < n := hn have hn0' : (0:ℝ) < (n:ℝ) := by exact_mod_cast hn0 have h1 := closed_network_am_gm_product_bound_geom n hn x hx have h2 := closed_network_am_gm_product_bound_geom n hn y hy have hsum : (∑ i : Fin n, x i) + (∑ i : Fin n, y i) ≤ n := by have : (∑ i : Fin n, (x i + y i)) ≤ ∑ i : Fin n, (1:ℝ) := Finset.sum_le_sum (fun i _ => hxy i) rw [Finset.sum_add_distrib] at this simpa using this have hsum' : (∑ i : Fin n, x i) / n + (∑ i : Fin n, y i) / n ≤ 1 := by rw [← add_div] rw [div_le_iff₀ hn0'] linarith linarith