Veronese sections

Veronese sections of a real-rooted polynomial with nonnegative coefficients are real-rooted or zero. A difference equation recognizes the polynomial sequences that are Veronese sections of products of linear factors, so their rows are real-rooted, and Veronese sections of constant-coefficient recurrences again satisfy a constant-coefficient recurrence.

Results

The $k$th $r$-Veronese section of $p=\sum_i p_i x^i$ is $\sum_{n\geq0}p_{k+rn}x^n$: it keeps the coefficients whose indices are congruent to $k$ modulo $r$ and re-indexes them by $n=(i-k)/r$.

Theorem (Veronese sections). Let $0 \leq k < r$. If a polynomial with nonnegative coefficients splits over $\mathbb R$, then its $k$th $r$-Veronese section is zero or splits over $\mathbb R$.

Fix $r \geq 1$ and real sequences $a_n$, $b_n$ with every $b_n \neq 0$. For a polynomial sequence $P = (P_n)$ put $(\Delta P)_n = (P_{n+1} - a_n P_n)/b_n$. For a polynomial $H$, the seed, the product parent is $Q_n(H) = H(x)\prod_{i<n}(a_i + b_i x)$, and $R_n(H)$ denotes its $(r-1)$st $r$-Veronese section.

Theorem (recognition). $\Delta^r P = x P$ if and only if there is a unique polynomial $H$ with $R_n(H) = P_n$ for all $n$; the $i$th $r$-Veronese section of $H$ is $(\Delta^{r-1-i} P)_0$ for $0 \leq i < r$. For $\beta \neq 0$, $\Delta^r P = (\alpha + \beta x) P$ if and only if there is a unique seed $H$ with $P_n(x) = R_n(H)(\alpha + \beta x)$ for all $n$. If $a_n \geq 0$, $b_n > 0$, and the seed has nonnegative coefficients and splits over $\mathbb R$, then every $P_n$ is zero or splits over $\mathbb R$, in the affine case for $\beta>0$.

For example, if $B \neq 0$ and $P_{n+2} = A P_{n+1} + (Bx + c) P_n$ for all $n$, then there is a unique seed $H$ such that $P_n$ is the odd Veronese section ($r = 2$) of $H\,(x + A/2)^n$, evaluated at $c + A^2/4 + Bx$.

Theorem (sections of recurrences). Let $A$ be a commutative ring, $r \geq 1$, and let $P(x,t)$ be monic in $t$ of degree $d$ with coefficients in $A[x]$. Put $y=x^r$ and let $D(y,t)$ be the determinant of multiplication by $P(x,t)$ on $A[y,t]$ in the basis $1,x,\dotsc,x^{r-1}$. If a sequence of polynomials in $A[x]$ satisfies the recurrence with characteristic polynomial $P$, then every residue section of every solution satisfies the recurrence with characteristic polynomial $D$, which is monic in $t$ of degree $rd$ when $A$ is nontrivial. If the source recurrence first determines row $N \geq d$, the section recurrence first determines row $N+(r-1)d$. Over $\mathbb R$, if every source row has nonnegative coefficients and splits, then every section row is zero or splits.

For binomial rows with $r=2$, Fibonacci tiling rows with $r=3$, and Delannoy triangle rows with $r=2$, the section recurrences have orders two, six and four.

Proof

Real-rootedness of Veronese sections follows from the Pólya frequency characterization of real-rooted polynomials with nonnegative coefficients and total nonnegativity of an associated matrix. For recurrences, the adjugate of the section multiplication matrix writes $D$ as a multiple of $P$, so the shift operator $D$ annihilates every source solution, and taking a section gives the section recurrence.

References

[AW24], where the Veronese-section convention and its linear-factor recurrences appear together with a stronger interlacing statement. See also Veronese sections on symmetricfunctions.com.

  1. [AW24] Christos A. Athanasiadis & David G. Wagner. Veronese sections and interlacing matrices of polynomials and formal power series. arXiv e-prints, 2024.
    BibTeX
    @article{AthanasiadisWagner2024x,
      author = {Christos A. Athanasiadis and David G. Wagner},
      title = {Veronese sections and interlacing matrices of polynomials and formal power series},
      journal = {arXiv e-prints},
      year = {2024},
      eprint = {2404.12989},
      doi = {10.48550/arXiv.2404.12989}
    }

Definitions

  • Veronese section

    RealRooted.veroneseSectionPolynomialsource
    def veroneseSectionPolynomial (r k : ℕ) (p : ℝ[X]) : ℝ[X] :=
      if hr0 : r = 0 then 0 else
        Polynomial.ofFinsupp <|
          ⟨Finsupp.onFinset (Finset.range (p.natDegree + 1))
            (fun n => p.coeff (k + r * n))
            (by
              intro n hn
              have hrpos : 0 < r := Nat.pos_of_ne_zero hr0
              by_contra hmem
              have hnotlt : ¬ n < p.natDegree + 1 := by simp_all
              have hle : p.natDegree + 1 ≤ n := Nat.le_of_not_gt hnotlt
              have hpn : p.natDegree < n := Nat.lt_of_succ_le hle
              have hn_le_mul : n ≤ r * n := by
                simpa [one_mul] using
                  Nat.mul_le_mul_right n (Nat.succ_le_of_lt hrpos)
              have hn_le : n ≤ k + r * n :=
                Nat.le_trans hn_le_mul (Nat.le_add_left (r * n) k)
              exact hn <|
                Polynomial.coeff_eq_zero_of_natDegree_lt (lt_of_lt_of_le hpn hn_le))⟩
  • Explicit section-matrix determinant in the coefficient variable

    Polynomial.veroneseNormsource
    def veroneseNorm (r : ℕ) (p : A[X][X]) : A[X][X] :=
      (veroneseMatrix r p).det
  • Common recurrence for all Veronese sections of a polynomial sequence

    LinearRecurrence.veronesesource
    def veronese (r : ℕ) (E : LinearRecurrence A[X]) : LinearRecurrence A[X] where
      order := r * E.order
      coeffs i := -(veroneseNorm r E.charPoly).coeff i
  • Normalized difference operator on a polynomial sequence

    RealRooted.sequenceDeltasource
    @[expose] def sequenceDelta (a b : ℕ → ℝ) (P : ℕ → ℝ[X]) : ℕ → ℝ[X] :=
      fun n ↦ C (b n)⁻¹ * (P (n + 1) - C (a n) * P n)
  • Scalar product parent with seed H

    RealRooted.veroneseProductParentsource
    @[expose] def veroneseProductParent (a b : ℕ → ℝ) (H : ℝ[X])
        (n : ℕ) : ℝ[X] :=
      H * ∏ i ∈ Finset.range n, (C (a i) + C (b i) * X)
  • Residue row of a scalar product parent

    RealRooted.veroneseProductRowsource
    @[expose] def veroneseProductRow (r j : ℕ) (a b : ℕ → ℝ)
        (H : ℝ[X]) (n : ℕ) : ℝ[X] :=
      veroneseSectionPolynomial r j (veroneseProductParent a b H n)
  • Seed reconstructed from the first r differences

    RealRooted.reconstructedVeroneseParentsource
    @[expose] def reconstructedVeroneseParent (r : ℕ) (a b : ℕ → ℝ)
        (P : ℕ → ℝ[X]) (n : ℕ) : ℝ[X] :=
      ∑ j ∈ Finset.range r,
        veroneseResidueTerm r j (((sequenceDelta a b)^[r - 1 - j] P) n)

Theorems

  • Veronese sections preserve real-rootednessMain result

    RealRooted.veroneseSectionPolynomial_eq_zero_or_splitssourcestatement on symmetricfunctions.com
    theorem veroneseSectionPolynomial_eq_zero_or_splits {r k : ℕ} (hk : k < r)
        {p : ℝ[X]} (hp : HasNonnegCoeffs p) (hsplits : p.Splits) :
        veroneseSectionPolynomial r k p = 0 ∨ (veroneseSectionPolynomial r k p).Splits
  • Δ^r P = X P holds exactly for rows of Veronese product parents

    RealRooted.iterate_sequenceDelta_eq_X_mul_iff_existsUnique_seedsource
    theorem iterate_sequenceDelta_eq_X_mul_iff_existsUnique_seed
        {r : ℕ} (hr : 0 < r) {a b : ℕ → ℝ} (hb : ∀ n, b n ≠ 0)
        (P : ℕ → ℝ[X]) :
        (∀ n, ((sequenceDelta a b)^[r] P) n = X * P n) ↔
          ∃! H : ℝ[X], ∀ n,
            veroneseProductRow r (r - 1) a b H n = P n
  • Affine recognition of Veronese product parents

    RealRooted.iterate_sequenceDelta_eq_affine_mul_iff_existsUnique_seedsource
    theorem iterate_sequenceDelta_eq_affine_mul_iff_existsUnique_seed
        {r : ℕ} (hr : 0 < r) {a b : ℕ → ℝ} (hb : ∀ n, b n ≠ 0)
        {α β : ℝ} (hβ : β ≠ 0) (P : ℕ → ℝ[X]) :
        (∀ n, ((sequenceDelta a b)^[r] P) n =
          (C α + C β * X) * P n) ↔
          ∃! H : ℝ[X], ∀ n,
            affineVeroneseProductRow r (r - 1) α β a b H n = P n
  • Recognized rows are zero or real-rooted when the seed is nonnegative and splits

    RealRooted.sequenceDelta_row_eq_zero_or_splitssource
    theorem sequenceDelta_row_eq_zero_or_splits {r : ℕ} (hr : 0 < r)
        {a b : ℕ → ℝ} (ha : ∀ n, 0 ≤ a n) (hb : ∀ n, 0 < b n)
        {P : ℕ → ℝ[X]}
        (hcycle : ∀ n, ((sequenceDelta a b)^[r] P) n = X * P n)
        (hseednn : HasNonnegCoeffs (reconstructedVeroneseParent r a b P 0))
        (hseedsplits : (reconstructedVeroneseParent r a b P 0).Splits) (n : ℕ) :
        P n = 0 ∨ (P n).Splits
  • Constant second-order recurrences have a unique affine Veronese parent

    RealRooted.existsUnique_affineVeroneseProductRow_of_orderTwo_recurrencesource
    theorem existsUnique_affineVeroneseProductRow_of_orderTwo_recurrence
        (A B c : ℝ) (hB : B ≠ 0) (P : ℕ → ℝ[X])
        (hrec : ∀ n, P (n + 2) = C A * P (n + 1) +
          (C B * X + C c) * P n) :
        ∃! H : ℝ[X], ∀ n,
          affineVeroneseProductRow 2 1 (c + A ^ 2 / 4) B
            (fun _ ↦ A / 2) (fun _ ↦ 1) H n = P n
  • Sections of an order-d recurrence share a recurrence of order rd

    LinearRecurrence.exists_veroneseSectionsource
    theorem exists_veroneseSection (E : LinearRecurrence A[X]) {r : ℕ} (hr : 0 < r) :
        ∃ T : LinearRecurrence A[X], T.order = r * E.order ∧
          T.charPoly = veroneseNorm r E.charPoly ∧
          ∀ (R : ℕ → A[X]), E.IsSolution R → ∀ i, i < r →
            T.IsSolution (fun n => (R n).veroneseSection r i)
  • Eventual recurrences pass to every Veronese section

    LinearRecurrence.veronese_recurrence_of_eventuallysource
    theorem veronese_recurrence_of_eventually (E : LinearRecurrence A[X])
        {r : ℕ} (hr : 0 < r) {R : ℕ → A[X]} {s : ℕ}
        (hR : ∀ n, s ≤ n → R (n + E.order) = ∑ j, E.coeffs j * R (n + j))
        {i : ℕ} (hi : i < r) {n : ℕ} (hn : s ≤ n) :
        (R (n + r * E.order)).veroneseSection r i =
          ∑ j : Fin (r * E.order), (E.veronese r).coeffs j *
            (R (n + j)).veroneseSection r i
  • Nonnegative real-rooted solutions give real-rooted section solutions

    RealRooted.isSolution_and_eq_zero_or_splits_veroneseSectionPolynomialsource
    theorem isSolution_and_eq_zero_or_splits_veroneseSectionPolynomial
        (E : LinearRecurrence ℝ[X]) {R : ℕ → ℝ[X]} (hR : E.IsSolution R)
        (hnn : ∀ n, HasNonnegCoeffs (R n)) (hs : ∀ n, (R n).Splits)
        {r i : ℕ} (hr : 0 < r) (hi : i < r) :
        (E.veronese r).IsSolution (fun n => veroneseSectionPolynomial r i (R n)) ∧
          ∀ n, veroneseSectionPolynomial r i (R n) = 0 ∨
            (veroneseSectionPolynomial r i (R n)).Splits

Lean source RealRooted/Challenges/PolyaFrequency/VeroneseSections.lean at revision d6670742. Formalized 2026-10-05.