polynomial_log_concave_reflect
Reflecting a natural polynomial through degree N at least its degree preserves log-concavity and interval support.
Statement
theorem polynomial_log_concave_reflect (p : Polynomial ℕ) (N : ℕ) (hdeg : p.natDegree ≤ N) (hlc : ∀ k : ℕ, p.coeff k * p.coeff (k + 2) ≤ p.coeff (k + 1) * p.coeff (k + 1)) (hint : ∀ i j k : ℕ, i ≤ j → j ≤ k → 0 < p.coeff i → 0 < p.coeff k → 0 < p.coeff j) : (∀ k : ℕ, (p.reflect N).coeff k * (p.reflect N).coeff (k + 2) ≤ (p.reflect N).coeff (k + 1) * (p.reflect N).coeff (k + 1)) ∧ (∀ i j k : ℕ, i ≤ j → j ≤ k → 0 < (p.reflect N).coeff i → 0 < (p.reflect N).coeff k → 0 < (p.reflect N).coeff j)- Source
- Algebraic helper for the leaf-rich graph case of OP-1399.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem proves that reflecting a polynomial $p$ with natural coefficients across degree $N \ge \deg(p)$ preserves log-concavity and interval support. The proof first establishes a helper lemma showing that reflected coefficients at indices beyond $N$ vanish. For log-concavity at index $k$, it splits into two cases: if $k+2 \le N$, reversing the indices reduces the condition to the log-concavity of $p$ at $N-(k+2)$; if $k+2 > N$, the coefficient at $k+2$ is zero and the inequality holds trivially. For interval support, non-vanishing boundary coefficients force all relevant indices to be at most $N$, reversing the order of the indices so the interval support of $p$ applies directly.
All coefficients of the reflected polynomial at indices strictly greater than $N$ are zero.
For an index $m > N$, `Polynomial.revAt_eq_self_of_lt` reduces the reflection index to $m$ itself. Because the degree of $p$ is at most $N < m$, the coefficient $p.coeff\ m$ vanishes by `Polynomial.coeff_eq_zero_of_natDegree_lt`.
uses
Polynomial.coeff_reflect,Polynomial.revAt_eq_self_of_lt,Polynomial.coeff_eq_zero_of_natDegree_lthave hzero : ∀ {m : ℕ}, N < m → (p.reflect N).coeff m = 0 := by intro m hm rw [Polynomial.coeff_reflect, Polynomial.revAt_eq_self_of_lt hm] exact Polynomial.coeff_eq_zero_of_natDegree_lt (hdeg.trans_lt hm)
It suffices to establish log-concavity and interval support separately for the reflected polynomial.
We split the conjunction into two independent subgoals: showing that the coefficients of the reflected polynomial satisfy the log-concavity inequality, and showing that they satisfy the interval support property.
constructorWhen $k + 2 \le N$, the log-concavity inequality holds at index $k$ for the reflected polynomial.
Since $k+2 \le N$, all three indices $k$, $k+1$, and $k+2$ are at most $N$. Using `Polynomial.coeff_reflect` and `Polynomial.revAt_le`, the coefficients of `p.reflect N` at these indices become the coefficients of $p$ at $N-k$, $N-(k+1)$, and $N-(k+2)$. Setting $m = N - (k+2)$, these correspond to indices $m+2$, $m+1$, and $m$. Commuting the factors on the left via `mul_comm` transforms the inequality into $p.coeff(m) \cdot p.coeff(m+2) \le p.coeff(m+1)^2$, which holds by the assumed log-concavity `hlc` of $p$ at $m$.
uses
Polynomial.coeff_reflect,Polynomial.revAt_le,mul_comm· intro k by_cases hk : k + 2 ≤ N · have hk0 : k ≤ N := by omega have hk1 : k + 1 ≤ N := by omega rw [Polynomial.coeff_reflect, Polynomial.coeff_reflect, Polynomial.coeff_reflect] rw [Polynomial.revAt_le hk0, Polynomial.revAt_le hk1, Polynomial.revAt_le hk] have h1 : N - (k + 1) = (N - (k + 2)) + 1 := by omega have h2 : N - k = (N - (k + 2)) + 2 := by omega rw [h1, h2, mul_comm (p.coeff _)] exact hlc (N - (k + 2))
When $k + 2 > N$, the log-concavity inequality holds trivially at index $k$ for the reflected polynomial.
If $k + 2 > N$, the preliminary lemma `hzero` implies that the coefficient at $k + 2$ is zero. Multiplying by zero gives zero on the left-hand side by `mul_zero`, which is at most the non-negative right-hand side by `Nat.zero_le`.
uses
Nat.not_le.mp,mul_zero,Nat.zero_le· have hlt : N < k + 2 := Nat.not_le.mp hk rw [hzero hlt, mul_zero] exact Nat.zero_le _
For indices $i \le j \le k$ with non-zero reflected coefficients at $i$ and $k$, all three indices satisfy $i \le j \le k \le N$.
If $k > N$, then by `hzero` the $k$-th reflected coefficient would be zero, contradicting the assumption that it is positive. Hence $k \le N$, which together with $i \le j \le k$ forces $j \le N$ and $i \le N$ by linear arithmetic.
uses
Nat.not_le.mp· intro i j k hij hjk hi hk have hk_le : k ≤ N := by by_contra h have hlt : N < k := Nat.not_le.mp h have hz : (p.reflect N).coeff k = 0 := hzero hlt omega have hj_le : j ≤ N := by omega have hi_le : i ≤ N := by omega
The $j$-th coefficient of the reflected polynomial is strictly positive.
Since $i, j, k \le N$, rewriting with `Polynomial.coeff_reflect` and `Polynomial.revAt_le` shows that the hypotheses mean $0 < p.coeff(N - i)$ and $0 < p.coeff(N - k)$. Reversing the order gives $N - k \le N - j \le N - i$. Applying the interval support hypothesis `hint` for $p$ to these reversed indices shows that $p.coeff(N - j) > 0$, which is precisely the $j$-th coefficient of the reflected polynomial.
uses
Polynomial.coeff_reflect,Polynomial.revAt_lerw [Polynomial.coeff_reflect, Polynomial.revAt_le hj_le] rw [Polynomial.coeff_reflect, Polynomial.revAt_le hi_le] at hi rw [Polynomial.coeff_reflect, Polynomial.revAt_le hk_le] at hk have h1 : N - k ≤ N - j := by omega have h2 : N - j ≤ N - i := by omega exact hint (N - k) (N - j) (N - i) h1 h2 hk hi
Polynomial.coeff_reflect- The $i$-th coefficient of a polynomial reflected at degree $N$ is the original polynomial's coefficient at $\text{revAt}(N, i)$.
Polynomial.revAt_eq_self_of_lt- Reversing an index $i$ with respect to degree $N$ leaves $i$ unchanged if $N < i$.
Polynomial.coeff_eq_zero_of_natDegree_lt- Any coefficient of a polynomial at an index strictly greater than its degree is zero.
Polynomial.revAt_le- Reversing an index $i \le N$ with respect to degree $N$ gives $N - i$.
mul_comm- Multiplication in a commutative structure satisfies $a \cdot b = b \cdot a$.
Nat.not_le.mp- For natural numbers, if $a \le b$ is false, then $b < a$.
mul_zero- Multiplying any element by zero on the right yields zero ($a \cdot 0 = 0$).
Nat.zero_le- Zero is less than or equal to every natural number ($0 \le n$).
- The operation `p.reflect N` relies on `Polynomial.revAt N i`, which is formally defined to yield $N - i$ when $i \le N$ and the identity $i$ when $i > 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.
theorem polynomial_log_concave_reflect (p : Polynomial ℕ) (N : ℕ) (hdeg : p.natDegree ≤ N) (hlc : ∀ k : ℕ, p.coeff k * p.coeff (k + 2) ≤ p.coeff (k + 1) * p.coeff (k + 1)) (hint : ∀ i j k : ℕ, i ≤ j → j ≤ k → 0 < p.coeff i → 0 < p.coeff k → 0 < p.coeff j) : (∀ k : ℕ, (p.reflect N).coeff k * (p.reflect N).coeff (k + 2) ≤ (p.reflect N).coeff (k + 1) * (p.reflect N).coeff (k + 1)) ∧ (∀ i j k : ℕ, i ≤ j → j ≤ k → 0 < (p.reflect N).coeff i → 0 < (p.reflect N).coeff k → 0 < (p.reflect N).coeff j) := by have hzero : ∀ {m : ℕ}, N < m → (p.reflect N).coeff m = 0 := by intro m hm rw [Polynomial.coeff_reflect, Polynomial.revAt_eq_self_of_lt hm] exact Polynomial.coeff_eq_zero_of_natDegree_lt (hdeg.trans_lt hm) constructor · intro k by_cases hk : k + 2 ≤ N · have hk0 : k ≤ N := by omega have hk1 : k + 1 ≤ N := by omega rw [Polynomial.coeff_reflect, Polynomial.coeff_reflect, Polynomial.coeff_reflect] rw [Polynomial.revAt_le hk0, Polynomial.revAt_le hk1, Polynomial.revAt_le hk] have h1 : N - (k + 1) = (N - (k + 2)) + 1 := by omega have h2 : N - k = (N - (k + 2)) + 2 := by omega rw [h1, h2, mul_comm (p.coeff _)] exact hlc (N - (k + 2)) · have hlt : N < k + 2 := Nat.not_le.mp hk rw [hzero hlt, mul_zero] exact Nat.zero_le _ · intro i j k hij hjk hi hk have hk_le : k ≤ N := by by_contra h have hlt : N < k := Nat.not_le.mp h have hz : (p.reflect N).coeff k = 0 := hzero hlt omega have hj_le : j ≤ N := by omega have hi_le : i ≤ N := by omega rw [Polynomial.coeff_reflect, Polynomial.revAt_le hj_le] rw [Polynomial.coeff_reflect, Polynomial.revAt_le hi_le] at hi rw [Polynomial.coeff_reflect, Polynomial.revAt_le hk_le] at hk have h1 : N - k ≤ N - j := by omega have h2 : N - j ≤ N - i := by omega exact hint (N - k) (N - j) (N - i) h1 h2 hk hi