Coefficients and Roots of Peak Polynomials

Sara C. Billey, Matthew Fahrbach, Alan TalmageExp. Math 2016 · OpenReview

TL;DR

This paper investigates "peak polynomials," which encode the number of permutations with specific "peak sets." The authors develop new formulas and analyze the roots of these polynomials, revealing connections to combinatorics and number theory, and proving that a conjecture about the positivity of coefficients is a consequence of a stronger conjecture about root locations.

What Problem Does This Paper Address?

The paper delves into the study of permutations and their "peak sets." A peak in a permutation $\pi = \pi_1\pi_2\dots\pi_n$ is an index $i$ where $\pi_{i-1} < \pi_i > \pi_{i+1}$. The "peak set" of a permutation is the collection of all such peak indices. A central question in this field is to count the number of permutations in the symmetric group $S_n$ that have a specific peak set $S$. This count is denoted by $|P_S(n)|$. It has been shown that for a fixed peak set $S$ and sufficiently large $n$, $|P_S(n)|$ can be expressed as $p_S(n) 2^{n-|S|-1}$, where $p_S(x)$ is a polynomial in $x$ called the "peak polynomial."

The problem addressed here is to understand the properties of these peak polynomials, particularly their coefficients and roots. Specifically, the authors investigate a conjecture by Billey, Burdzy, and Sagan which states that certain coefficients of these polynomials, when expanded in a specific basis, are all positive. They also explore the location of the roots of these polynomials, hypothesizing that they lie within a particular region of the complex plane.

Methods

The paper employs a combination of theoretical and computational approaches. Key methods include:

  • Algebraic Manipulation of Polynomials: The authors derive explicit formulas for peak polynomials, particularly in binomial bases centered at 0 and $m$ (the maximum element in the peak set). This involves techniques like induction and the use of recurrence relations.
  • Combinatorial Arguments: They connect peak polynomials to the counting of permutations with specific peak sets, utilizing concepts like alternating permutations and the inclusion-exclusion principle.
  • Theorems from Polynomial Theory: The Gauss-Lucas theorem is used to relate the roots of a polynomial to the roots of its derivatives, which is crucial for bounding root locations.
  • Computational Verification: The authors mention using SageMath to verify conjectures for smaller peak sets, providing empirical evidence for their theoretical results.

Datasets

Not discussed in the paper. The paper focuses on theoretical results and uses computational verification for smaller cases rather than large-scale datasets.

Key Insights and Ideas

  • Positivity Conjecture as a Consequence of Root Location: The paper demonstrates that a conjecture about the positivity of coefficients of peak polynomials is a direct consequence of a stronger conjecture about the location of their complex roots. This reframes the problem and suggests a path for proving the positivity conjecture.
  • Structure of Roots: The authors identify specific integer roots of peak polynomials and explore how the structure of the peak set $S$ influences the roots. For instance, they show that if $S$ has a "gap of three," the polynomial's roots exhibit a form of independence from the peaks to the left of the gap.
  • Explicit Formulas for Peak Polynomials: New, explicit formulas for peak polynomials are derived, particularly for cases with specific structures of peak sets (e.g., those with "gaps of three" or arithmetic progressions). These formulas are crucial for analyzing roots and coefficients.
  • Connection to Alternating Permutations: The paper establishes a link between peak polynomials and alternating permutations, using tangent numbers to enumerate permutations with given peak sets. This provides an alternative combinatorial interpretation and computational tool.

Key Results

  • Conjecture 1.6 Implies Positivity Conjecture: The paper proves that Conjecture 1.6 (regarding the location of complex roots of $p_S(z)$) implies Conjecture 1.5 (regarding the positivity of coefficients in a specific binomial basis expansion).
  • Explicit Formulas for $p_S(x)$: The paper provides explicit formulas for $p_S(x)$ in the binomial basis centered at 0, particularly for cases with no odd gaps and for sets with specific "gap of three" structures.
  • Identification of Integer Roots: Several theorems and corollaries identify specific integer roots of $p_S(x)$, such as $0, 1, \dots, i_r$ when $S$ has an odd gap, and $i \in S$ for all $i$.
  • Gap of Three Independence: Theorem 3.15 shows that if a peak set $S$ has a gap of three, the corresponding peak polynomial $p_S(x)$ is independent of the peaks to the left of the gap (up to a constant), and its roots depend only on the peaks to the right of the gap.

Limitations and Future Work

  • Conjecture 1.6 is Unproven: While the paper shows that Conjecture 1.6 implies Conjecture 1.5, Conjecture 1.6 itself (bounding the complex roots of $p_S(z)$) remains a conjecture.
  • Conjecture 6.5 (Real Roots): The paper presents Conjecture 6.5, which characterizes peak sets $S$ for which $p_S(x)$ has only real roots. This is stated as a conjecture, not a proven theorem.
  • Conjecture 6.6 (Root Location): Conjecture 6.6, related to the location of real roots, is partially proven for integers but not for all real numbers.
  • Question 6.7: The paper poses a question about what $p_S(n)$ counts for $n > \max(S)$, suggesting an area for future exploration.
  • Generalization of Root Properties: While specific root properties are identified, a complete characterization of the roots of $p_S(x)$ for arbitrary $S$ is still an open problem.

Summary updated

BibTeX
@inproceedings{billey2016coefficients,
  author = {Sara C. Billey and Matthew Fahrbach and Alan Talmage},
  title = {{Coefficients and Roots of Peak Polynomials}},
  booktitle = {Exp. Math},
  year = {2016},
  url = {https://openreview.net/forum?id=CDsOgX-KJB8},
}
Figure