Border complexity via elementary symmetric polynomials

Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, Vladimir LysikovarXiv 2022 · DOI · arXiv

TL;DR

This paper connects two measures of polynomial complexity: Waring rank and Kumar complexity. They introduce a new model called "product-plus-power" and use it to prove a converse to Kumar's theorem, showing that polynomials with small border Waring rank are essentially products of linear forms. This work has implications for understanding the complexity of matrix multiplication and the power of geometric complexity theory.

What Problem Does This Paper Address?

Understanding the computational complexity of polynomials is a fundamental problem in computer science. Two key measures are Waring rank (WR) and Kumar complexity (Kc). WR relates to representing a polynomial as a sum of powers of linear forms, while Kc involves a specific type of approximation using linear forms and roots of unity. While there are known relationships between these measures, particularly that Kc is bounded by WR, the authors explore the converse and the nuances of their "border" versions. The border versions account for polynomials that can be approximated by sequences of polynomials with lower complexity. This paper aims to establish a tighter connection between border Waring rank and border Kumar complexity, particularly for the "product-plus-power" polynomial, and to leverage this understanding for geometric complexity theory.

Methods

The paper introduces a new computational model called the "product-plus-power" model, which is a degeneration of a specific polynomial. They then prove "debordering" results for this model, showing that polynomials within this model don't gain significantly more complexity when considering their border versions. A key technique is the use of Newton's identities, which relate elementary symmetric polynomials and power sums. The authors also employ geometric complexity theory (GCT) tools, specifically representation theory and group actions, to derive multiplicity obstructions. These obstructions are used to prove that certain polynomials are not degenerations of others, providing lower bounds on their complexity. The paper also delves into the stabilizer of polynomials under group actions, which is crucial for GCT.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Converse to Kumar's Theorem: The paper establishes a converse to a result by Kumar, showing that if a homogeneous polynomial has a small border Kumar complexity, it must be a product of linear forms. This is a significant insight into the structure of polynomials with low complexity.
  • Product-Plus-Power Model: The introduction of this model provides a new framework for studying polynomial complexity and its relationship to existing measures.
  • Debordering Results: The paper demonstrates that the product-plus-power model does not significantly increase complexity when considering border versions, suggesting that the underlying structure is well-captured by non-border measures.
  • GCT for Product-Plus-Power: The authors apply GCT techniques to the product-plus-power polynomial, yielding new multiplicity obstructions based on symmetries. This showcases the power of GCT for proving lower bounds.
  • Connection to Matrix Multiplication: The work has implications for understanding the exponent of matrix multiplication, a fundamental constant in computer science, by relating it to the Kumar complexity of specific polynomials.

Key Results

  • Theorem 1.1 (Converse of Kumar's Theorem): For a homogeneous polynomial $f$, either $WR(f) < Kc(f)$ or $f$ is a product of linear forms.
  • Corollary 1.2: The exponent of matrix multiplication $\omega$ is characterized as $\omega = \lim_{n\to\infty} \log_n K_c(\text{trace}(X_n))$.
  • Theorem 1.3 (Debordering Product-Plus-Power): If $f$ is a degeneration of the product-plus-power polynomial $P_{1,1}^{[d]}$, then either $f$ is also a degeneration of $P_{1,1}^{[d]}$ or $WR(f) \le O(d^5)$.
  • Theorem 1.4 (New Obstructions): For $d > 3$, new representation theoretic multiplicity obstructions are established, showing that $x_1^d + \dots + x_{d+1}^d$ is not a degeneration of $P_{1,1}^{[d]}$.

Limitations and Future Work

The paper acknowledges that it is an open question to what extent the product-plus-power model is stronger than Kumar's model. Future work could involve further exploring this relationship and finding tighter lower bounds for Kumar's complexity. The paper also mentions that the potential of multiplicity obstructions in GCT is still being explored, suggesting that further applications of these techniques could lead to significant breakthroughs in complexity theory. The connection to the Alon-Tarsi conjecture is also highlighted, indicating potential avenues for future research in combinatorics and theoretical computer science.

Summary updated

BibTeX
@misc{dutta2022border,
  author = {Pranjal Dutta and Fulvio Gesmundo and Christian Ikenmeyer and Gorav Jindal and Vladimir Lysikov},
  title = {{Border complexity via elementary symmetric polynomials}},
  year = {2022},
  eprint = {2211.07055},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2211.07055},
}

Loading related content...

Figure