AFTD Auto-Formalizing Theoretical Domains

polynomial_log_concave_reflect

theoremverified

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.

  1. 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`.

    lines 2–5

    uses Polynomial.coeff_reflect, Polynomial.revAt_eq_self_of_lt, Polynomial.coeff_eq_zero_of_natDegree_lt

      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)
  2. 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.

    line 6

      constructor
  3. When $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$.

    lines 7–16

    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))
  4. 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`.

    lines 17–19

    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 _
  5. 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.

    lines 20–27

    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
  6. 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.

    lines 28–33

    uses Polynomial.coeff_reflect, Polynomial.revAt_le

        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
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$).

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

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
See it in the graphDiscuss this resultChallenge it