Threshold matrices

Matrices whose rows have entries $x$ before a threshold and $1$ after it, with weakly increasing thresholds and a compatibility condition on the markers, preserve interlacing sequences.

Results

An interlacing sequence is a list of nonzero real-rooted polynomials with nonnegative coefficients in which each polynomial interlaces every later one. In a weak interlacing sequence zero polynomials are allowed.

A threshold row with threshold $t$ and marker $\alpha$ has entry $x$ in the columns before $t$, the marker $\alpha$ in column $t$, and $1$ after it. Applied to $(f_j)$ it gives $x\sum_{j<t}f_j+\alpha f_t+\sum_{j>t}f_j$.

Theorem (row-threshold matrices). Let $G$ be an $m\times n$ matrix whose entries are linear forms $a+bx$ with $a,b\ge0$. Assume that row $i$ has a threshold $p_i$: the coefficient of $x$ is positive only in columns before $p_i$, and the constant coefficient is positive only from column $p_i$ on. Assume $p_1\le\dots\le p_m$, and that for rows $i_1\le i_2$ and columns $j_1\le j_2$, with $a=G_{i_1j_1}$, $b=G_{i_1j_2}$, $c=G_{i_2j_1}$, $d=G_{i_2j_2}$, the polynomial $(sx+t)b+d$ interlaces $(sx+t)a+c$ for all $s,t>0$. Then $G$ maps an interlacing sequence of length $n$ to an interlacing sequence. If this condition holds with zero polynomials allowed, $G$ maps an interlacing sequence to a weak interlacing sequence of nonnegative polynomials, and discarding the zero polynomials leaves an interlacing sequence. This specializes the matrix criterion [Bra15, Thm. 7.8.5] of the matrix interlacing page.

Theorem (Haglund–Zhang). [HZ19] Let $G$ be a threshold matrix whose markers are $1$ or $1+x$, whose thresholds weakly increase down the rows, and in which, among rows with equal threshold, a marker $1+x$ is never followed by the marker $1$. Then $G$ maps an interlacing sequence to a weak interlacing sequence of nonnegative polynomials. Consequently the binomial Eulerian polynomials, defined by the Haglund–Zhang recursion on refined vectors (marker $1+x$ at threshold $0$ and $1$ at every later threshold), are real-rooted, which confirms a conjecture of Ma, Ma and Yeh [MMY17].

Theorem (Gustafsson–Solus, Lemma 3.4). [GS20, Lemma 3.4] Let each row have entries $x$ before its threshold $\varphi_i$, entry $1$ or $0$ in column $\varphi_i$ (a dropped pivot), and $1$ after it. If the thresholds weakly increase and, among rows with equal threshold, a dropped pivot is never followed by a row with an undropped pivot, then the matrix maps an interlacing sequence to a weak interlacing sequence of nonnegative polynomials.

Use

Gustafsson and Solus use the last theorem to prove that the box polynomials of $s$-lecture hall simplices, which generalize the derangement polynomials, are real-rooted. The binomial Eulerian polynomials, with the row $1$ prepended, are the rows of OEIS A046802, the $h$-polynomials of the stellohedra. The binomial Eulerian real-rootedness assertion on symmetricfunctions.com is an application of the Haglund–Zhang theorem.

References

[Bra15, Thm. 7.8.5]; [HZ19]; [GS20]; [MMY17].

  1. [Bra15] Petter Brändén. Unimodality, Log-Concavity, Real-Rootedness and Beyond. Handbook of enumerative combinatorics, 437-483, 2015.
    BibTeX
    @incollection{Branden2015,
      doi = {10.1201/b18255-10},
      year = {2015},
      month = mar,
      publisher = {Chapman and Hall/{CRC}},
      pages = {437--483},
      author = {Petter Br{\"{a}}nd{\'{e}}n},
      title = {Unimodality, Log-Concavity, Real-Rootedness and Beyond},
      booktitle = {Handbook of Enumerative Combinatorics}
    }
  2. [HZ19] James Haglund & Philip B. Zhang. Real-rootedness of variations of Eulerian polynomials. Advances in Applied Mathematics, 109, 38-54, 2019.
    BibTeX
    @article{HaglundZhang2019,
      doi = {10.1016/j.aam.2019.05.001},
      url = {https://doi.org/10.1016/j.aam.2019.05.001},
      year = {2019},
      month = aug,
      publisher = {Elsevier {BV}},
      volume = {109},
      pages = {38--54},
      author = {James Haglund and Philip B. Zhang},
      title = {Real-rootedness of variations of {E}ulerian polynomials},
      journal = {Advances in Applied Mathematics}
    }
  3. [GS20] Nils Gustafsson & Liam Solus. Derangements, Ehrhart theory, and local h-polynomials. Advances in Mathematics, 369, 107169, 2020.
    BibTeX
    @article{GustafssonSolus2020,
      doi = {10.1016/j.aim.2020.107169},
      url2 = {https://doi.org/10.1016/j.aim.2020.107169},
      year = {2020},
      month = aug,
      publisher = {Elsevier {BV}},
      volume = {369},
      pages = {107169},
      author = {Nils Gustafsson and Liam Solus},
      title = {Derangements,  {E}hrhart theory,  and local h-polynomials},
      journal = {Advances in Mathematics}
    }
  4. [MMY17] Jun Ma, Shi-Mei Ma, & Yeong-Nan Yeh. Recurrence relations for binomial-Eulerian polynomials. arXiv e-prints, 2017.
    BibTeX
    @article{MaMaYeh2017x,
      author = {Jun Ma and Shi-Mei Ma and Yeong-Nan Yeh},
      title = {Recurrence relations for binomial-{E}ulerian polynomials},
      year = {2017},
      eprint = {1711.09016v2},
      url = {https://arxiv.org/abs/1711.09016v2},
      journal = {arXiv e-prints}
    }

Definitions

  • Threshold entry: x before the threshold, a marker at it, 1 after it

    RealRooted.thresholdEntrysource
    def thresholdEntry (t : ℕ) (α : ℝ[X]) (j : ℕ) : ℝ[X] :=
      if j < t then X else if j = t then α else 1
  • Binomial Eulerian polynomial, via the Haglund–Zhang recursion

    RealRooted.HaglundZhang.binomialEulerianPolynomialsource
    def binomialEulerianPolynomial (n : ℕ) : ℝ[X] :=
      terminalPolynomial (n + 1) (binomialRefined n)
  • Row-threshold matrix of nonnegative linear forms

    RealRooted.HasRowThresholdLinearStructuresource
    def HasRowThresholdLinearStructure (G : List (List ℝ[X])) : Prop :=
      ∃ p : Fin G.length → ℕ,
        (∀ i, HasRowThreshold (G.get i) (p i)) ∧
        ∀ ⦃i j : Fin G.length⦄, i ≤ j → p i ≤ p j

Theorems

  • Haglund–Zhang threshold matrices preserve interlacing sequences

    RealRooted.HaglundZhang.isInterlacingSeq0Nonneg_matPolyActionsource
    theorem isInterlacingSeq0Nonneg_matPolyAction
        {q : ℕ} (rows : List (ℕ × ℝ[X])) (hrows : RowData rows)
        (fs : List ℝ[X]) (hfs_len : fs.length = q)
        (hfs : IsInterlacingSeqNonneg fs) :
        IsInterlacingSeq0Nonneg (matPolyAction (matrix q rows) fs)
  • Haglund–Zhang: binomial Eulerian polynomials are real-rooted

    RealRooted.HaglundZhang.binomialEulerianPolynomial_splitssource
    theorem binomialEulerianPolynomial_splits (n : ℕ) :
        (binomialEulerianPolynomial n).Splits
  • The refined binomial Eulerian vectors form interlacing sequences

    RealRooted.HaglundZhang.binomialRefined_interlacessource
    theorem binomialRefined_interlaces (n : ℕ) :
        IsInterlacingSeq0Nonneg (binomialRefined n)
  • Brändén: row-threshold matrices of linear forms preserve interlacing sequences

    RealRooted.IsInterlacingSeqNonneg.matPolyAction_of_rowThresholdsource
    theorem IsInterlacingSeqNonneg.matPolyAction_of_rowThreshold
        (hn : 0 < n)
        (G : List (List ℝ[X]))
        (hG_rect : ∀ row ∈ G, row.length = n)
        (hG_threshold : HasRowThresholdLinearStructure G)
        (hG_affine : ∀ (i₁ i₂ : Fin G.length) (j₁ j₂ : Fin n),
          i₁ ≤ i₂ → j₁ ≤ j₂ →
          Has2x2InterlacingProperty
            ((G.get i₁).get ⟨j₁, by simp_all⟩)
            ((G.get i₁).get ⟨j₂, by simp_all⟩)
            ((G.get i₂).get ⟨j₁, by simp_all⟩)
            ((G.get i₂).get ⟨j₂, by simp_all⟩))
        (fs : List ℝ[X]) (hfs_len : fs.length = n)
        (hfs : IsInterlacingSeqNonneg fs) :
        IsInterlacingSeqNonneg (matPolyAction G fs)
  • Zero-aware row-threshold preservation of interlacing sequencesMain result

    RealRooted.IsInterlacingSeq0Nonneg.matPolyAction_of_rowThresholdsource
    theorem IsInterlacingSeq0Nonneg.matPolyAction_of_rowThreshold
        (G : List (List ℝ[X]))
        (hG_rect : ∀ row ∈ G, row.length = n)
        (hG_threshold : HasRowThresholdLinearStructure G)
        (hG_affine : ∀ (i₁ i₂ : Fin G.length) (j₁ j₂ : Fin n),
          i₁ ≤ i₂ → j₁ ≤ j₂ →
          Has2x2InterlacingProperty0
            ((G.get i₁).get ⟨j₁, by simp_all⟩)
            ((G.get i₁).get ⟨j₂, by simp_all⟩)
            ((G.get i₂).get ⟨j₁, by simp_all⟩)
            ((G.get i₂).get ⟨j₂, by simp_all⟩))
        (fs : List ℝ[X]) (hfs_len : fs.length = n)
        (hfs : IsInterlacingSeqNonneg fs) :
        IsInterlacingSeq0Nonneg (matPolyAction G fs)
  • Row-threshold matrices give a strict interlacing sequence after discarding zeros

    RealRooted.rowThreshold_interlacingSeq_filter_ne_zero_of_2x2source
    theorem rowThreshold_interlacingSeq_filter_ne_zero_of_2x2
        (G : List (List ℝ[X]))
        (hG_rect : ∀ row ∈ G, row.length = n)
        (hG_threshold : HasRowThresholdLinearStructure G)
        (hG_affine : ∀ (i₁ i₂ : Fin G.length) (j₁ j₂ : Fin n),
          i₁ ≤ i₂ → j₁ ≤ j₂ →
          Has2x2InterlacingProperty0
            ((G.get i₁).get ⟨j₁, by simp_all⟩)
            ((G.get i₁).get ⟨j₂, by simp_all⟩)
            ((G.get i₂).get ⟨j₁, by simp_all⟩)
            ((G.get i₂).get ⟨j₂, by simp_all⟩))
        (fs : List ℝ[X]) (hfs_len : fs.length = n)
        (hfs : IsInterlacingSeqNonneg fs) :
        IsInterlacingSeqNonneg ((matPolyAction G fs).filter (· ≠ 0))
  • Gustafsson–Solus Lemma 3.4: row-threshold matrices preserve interlacing

    RealRooted.isInterlacingSeq0Nonneg_gustafssonSolusActionsource
    theorem isInterlacingSeq0Nonneg_gustafssonSolusAction :
        ∀ {m n : ℕ} (phi : Fin m → Fin n) (dropPivot : Fin m → Bool),
          GustafssonSolusWeaklyIncreasing phi →
          GustafssonSolusNoSwitchAfterDrop phi dropPivot →
          ∀ fs : List ℝ[X], fs.length = n → IsInterlacingSeqNonneg fs →
            IsInterlacingSeq0Nonneg (gustafssonSolusAction phi dropPivot fs)

Lean source RealRooted/Challenges/Matrices/ThresholdMatrices.lean at revision d6670742. Formalized 2026-10-06.