Pith. sign in

REVIEW 3 major objections 5 minor 24 references

Guessing sequences of eigenvectors for LMPs defining spectrahedral relaxations of Eulerian rigidly convex sets

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper establishes that a chosen linearizing vector makes the multivariate spectrahedral relaxation beat the univariate bound by a gap growing like $\frac{3}{8}(\frac{9}{8})^m$ for even $n=2m$, reversing a previously vanishing…

desk verdict A real but narrow asymptotic improvement, with the load-bearing proof resting on hand-checked cancellations that need independent verification before I'd stake anything on it. read the letter →

arxiv 2507.18434 v1 pith:JLC7LGGV submitted 2025-07-24 math.CO cs.NAmath.NAmath.OC

Alejandro González Nevado This is my paper · ORCID
classification math.COcs.NAmath.NAmath.OC MSC 05A1514P1026C1090C22
keywords Eulerianpolynomialsspectrahedralrelaxationrigidlyconvexsetsrealzerolinearmatrixgeneralizedeigenvaluesdescenttopasymptoticrootbounds
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that adding variables helps in a specific, measurable way: a spectrahedral relaxation built from multivariate Eulerian polynomials—an outer approximation of a convex set by linear matrix inequalities—can certify a bound on the extreme roots of the univariate Eulerian polynomials (the polynomials counting permutations by descents) that is exponentially better than the best univariate bound. Earlier work had already shown an improvement, but the certified gap between the multivariate and univariate bounds shrank to zero as the degree grew, at the rate $(\frac12)(\frac34)^n$. By feeding the relaxation a carefully guessed sequence of vectors, the paper proves that for even $n=2m$ the gap grows like $\frac38(\frac98)^m$, i.e. it diverges exponentially. If correct, this turns “more variables help” from a negligible correction into a decisive asymptotic effect, and it gives a template for extracting accurate root bounds from linearizations of spectrahedra.

What carries the argument

The machinery is the linear matrix polynomial (LMP) produced by the spectrahedral relaxation of the real-zero multivariate Eulerian polynomial, restricted to the diagonal $x_1=\cdots=x_n=x$. For any vector $v$, the quadratic form $v^T(M_{n,0}+xM_{n,\mathrm{sum}})v=D+xN$ is nonnegative on the spectrahedron, so whenever $N>0$ it yields the bound $x\ge -D/N$. The work of the paper is choosing $v$: the entries $(-2^{m-i})_{i=3}^m$, the single $0$ and $\tfrac12$, and the tail of ones are a numerical guess at the shape of the true generalized eigenvector. The asymptotic estimate of $N/D$ is carried out by conjugation, rewriting $c-\sqrt{b}$ as $(c^2-b)/(c+\sqrt{b})$ so that surviving terms below the leading order are not discarded; the surviving term is $\frac38(\frac98)^m$.

What would settle it

Evaluate the exact closed-form expressions from Proposition 12.1 and Lemma 9.1 at even $n=2m$ using exact rational arithmetic and check whether $\mathrm{mult}_v(n)-\mathrm{un}(n)$ divided by $(\frac98)^m$ tends to $\frac38$; any drift or different constant would show that a surviving term was missed in the conjugation chain.

Watch

Extended reading notes

Core claim

The central result is a comparison of two bounds for the leftmost root of the $n$-th univariate Eulerian polynomial. The univariate relaxation gives a bound $\mathrm{un}(n)$; the multivariate relaxation, linearized with the vector $v=(y,(-2^{m-i})_{i=3}^m,0,\tfrac12,(1)_{i=1}^m)$ where $n=2m$, gives a bound $\mathrm{mult}_v(n)$. Lemma 13.2 states that $\mathrm{mult}_v(n)-\mathrm{un}(n)\sim \frac38(\frac98)^m$ along even indices. Since $(\frac98)^m\to\infty$, the certified advantage of the multivariate relaxation no longer vanishes; it grows exponentially. The proof writes the diagonal linear matrix polynomial as $D+xN$, uses $x\ge -D/N$ for any vector, and then computes the asymptotics of $N/D$ by repeated conjugation to remove radicals, after the leading candidate terms cancel exactly.

Load-bearing premise

The whole claim of exponential improvement rests on the manual asymptotic bookkeeping in the proof of Lemma 13.2: after repeated conjugation, every surviving term has been identified correctly, and no neglected subdominant term changes the first growth term.

Editorial extensions

If this is right

  • For every even $n=2m$ large enough, the multivariate spectrahedral relaxation gives a strictly better extreme-root bound than the univariate one, with the gap growing like $\frac38(\frac98)^m$.
  • The previously established vanishing improvement is an artifact of the simple vector $(y,1,-1)$; structured vectors can certify that multivariability changes the asymptotic accuracy of the relaxation.
  • Because univariate Eulerian polynomials are palindromic, the same exponentially growing gap also translates into an exponentially improved bound for the rightmost root.
  • The bound is proven with the $y$ optimized for the earlier vector; the author leaves as an exercise the optimization of $y$ for this new vector, which should only increase the certified gap.
  • The success of this guessed vector suggests a concrete design principle for future linearizations: mimic the observed shape of the actual generalized eigenvector instead of using a generic constant tail.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same guessing strategy could be tested on other real-stable multivariate liftings, such as W-Eulerian polynomials, to see whether their spectrahedral relaxations also certify exponentially growing gaps rather than vanishing ones.
  • Because the difference between bounds is measured along the diagonal, the exponential gap likely reflects genuinely deeper asymptotic terms of the extreme roots; an inner bound from a dual construction would sandwich the roots and expose those terms.
  • A concrete extension is to build the analogous vector for odd $n$; the paper says the odd case follows similarly, but does not compute the base of the exponential growth, so the exact rate for odd $n$ remains open.
  • The vector's entry profile (powers of $-2$ up to a $0,\tfrac12$ step, then a tail of ones) may correspond to a weighting of descent-top statistics; if so, the optimal vector could be derived combinatorially rather than guessed numerically.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies spectrahedral relaxations of Eulerian rigidly convex sets, building on the author's earlier work [7]. The main new claim is that, for even n=2m, the bound obtained by linearizing the multivariate spectrahedral relaxation along the vector (y,(-2^{m-i})_{i=3}^m,0,1/2,(1)_{i=1}^m) satisfies mult_v(n)-un(n) ~ (3/8)(9/8)^m. This would show that the certified advantage of the multivariate relaxation over the univariate bound grows exponentially, in contrast to the vanishing improvement obtained in [7]. The paper constructs the vector through numerical experiments, derives the form of the bound in Proposition 12.1, and computes the asymptotic difference in Lemma 13.2 by a hand-managed chain of conjugations.

Significance. If Lemma 13.2 is correct, the result is significant: it provides the first certificate that the multivariate spectrahedral relaxation of [21] yields an exponentially growing diagonal accuracy improvement over the univariate relaxation, thereby substantially strengthening the main quantitative claim of [7]. The paper also gives a transparent and honest account of the numerical guessing procedure and explicitly warns about the fragility of the chained-conjugation computation (Warning 11.8). However, the central asymptotic claim rests on a lengthy hand-verified computation that is not independently checked, so the significance is conditional on verification.

major comments (3)
  1. [Lemma 13.2 (and Warning 11.8)] The proof of Lemma 13.2 is the load-bearing step: it asserts that after writing mult_v-un=(k+v+u+w)/(s(gamma+delta sqrt(g))) the dominant terms k, v, u, w all grow like 2^{22m+19}3^{2m+1}m^4 and annihilate, then asserts the subdominant terms survive with the claimed leading growth. None of these orders is derived in the text; the steps are described as 'as happened in [7]' and 'computing we can see'. The paper itself, in Warning 11.8, states that a mistake in the chained conjugations could cause one to ignore asymptotic growth terms that actually survive and 'may significantly and wrongly alter the whole computation'. Since the entire (9/8)^m improvement is the first growth term of this difference, this is exactly the risk. I request an independent verification of the cancellation and of the surviving terms, ideally by (a) writing out the explicit asymptotic expansions of each of k, u, v, w after the first conjugation, and (b) providing a reproducible symbolic or numeric check of the final limit mult_v-un over (9/8)^m -> 3/8.
  2. [Proposition 12.1] The proof of Proposition 12.1 consists solely of displaying the sums for D and N and concluding 'Computing these last expressions finishes the proof.' The resulting closed forms for D and N are extremely long, and they are the input to Lemma 13.2. Without an indication of how the sums over the L_p entries (using Computation 6.4) are simplified, or a machine-checked derivation, the reader cannot verify that the displayed D and N are free of transcription errors. Please provide the intermediate summation steps or a verifiable computer algebra script, and state explicitly the indexing correspondence between the vector entries and the variables x_i (the expressions use x_{i-2} and x_m, but the vector is written as (y,(-2^{m-i})_{i=3}^m,(0,1/2),(1)_{i=1}^m); this indexing should be spelled out).
  3. [Proposition 13.1] The proof that the chosen y from [7] gives N>0 and D>0 is outlined only for N, and for D it says 'the result is immediate' after referring to [7]. Since the positivity of D is used to identify the bound as -D/N (equivalently N/D), this step should be expanded or replaced by a direct computation, especially because y contains a radical and the asymptotic argument for N involves comparing 6^{n+1} terms against 8^{n+1} terms. This is less central than Lemma 13.2, but it is still part of the chain establishing the bound.
minor comments (5)
  1. [Section 3, Remark 3.1] The phrase 'because of the following three seasons' should be 'three reasons'.
  2. [Experiment 10.5 and Figure 1] The text refers to 'the Figure 10.5' but the caption reads 'Figure 1'; renumber the cross-reference.
  3. [Notation, Sections 10-13] The vector v is written as (y,(-2^{m-i})_{i=3}^m,(0,1/2),(1)_{i=1}^m) but the sums in Proposition 12.1 use indices i-2 and m, which suggests an offset between the two notations. Clarify the indexing consistently: for example, state that the entries correspond to variables (x_1,x_2,...,x_n) with x_1 mapped to y, x_2 to 0, x_3 to 1/2, etc.
  4. [Section 9 and Lemma 9.1] The univariate bound un(n) is used throughout Sections 13 and 14 but is not defined in this paper; a formal definition or reference to the exact statement in [7] would improve readability.
  5. [Abstract and Section 17] The abstract and conclusion state the exponential improvement without always specifying that it is proven only for even n=2m; since the odd case is only claimed to follow 'similarly', state this restriction more prominently in the abstract.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the new bound is a consequence of the relaxation and a fixed guessed vector, not of the result it claims; the main risk is unverified hand computation.

full rationale

The central claim, Lemma 13.2, is not circular. mult_v(n) is obtained by evaluating v^T(M_{n,0}+xM_{n,sum})v for the fixed vector v=(y,(-2^{m-i}),0,1/2,1); once v is fixed, a+xb>=0 is a valid consequence of the PSD relaxation (Procedure 7.3), and the difference mult_v-un is then computed, not assumed. The vector v is found by numerical experiments (Experiment 10.5), but it is not fitted to the final difference; the proof in Section 13 is an explicit, though hand-checked, asymptotic expansion of the two bounds. The reuse of the optimal y from the author's earlier paper [7] is a self-citation, but that y is a concrete algebraic quantity with a stated asymptotic that is an input to the current vector, not a quantity defined in terms of mult_v-un; it is therefore not the target result and does not force the claimed (9/8)^m growth by construction. The paper's own Warnings 11.3 and 11.8 identify the real risk that chained-conjugation cancellations were computed incorrectly; that risk concerns the correctness of the hand checks, not circularity. No equation in the paper is equivalent to its input by definition; the strongest legitimate concern is verification risk, which belongs in a correctness assessment, not in the circularity score. The score of 2 reflects only the repeated reliance on the author's prior work [7] for the y value and for the method, not a circular derivation.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The paper's central comparison rests on the RZ property of the multivariate Eulerian polynomials, the relaxation theorem of Schweighofer, the L-form values, and the imported asymptotic behavior of y from [7]. The new vector entries are chosen by hand from numerics; the first entry y is carried over from [7] and is not optimal for the new vector. No invented physical entities are introduced.

free parameters (2)
  • y = y = (b + sqrt(b^2 - 4ac))/(2a) with a,b,c from Lemma 9.1, n = 2m; y ~ -3^{n+1}/(2^{n+1} n)
    The first entry of every guessing vector; chosen from the optimization in [7], not re-optimized for the new vector. The bound in Lemma 13.2 depends on this choice, and the paper leaves the optimal y as Exercise 14.3.
  • vector entries (-2^{m-i}, 0, 1/2, 1) = Entries of v as given in Notation 10.4
    Chosen by hand after numerical experiments on small generalized eigenvalue problems (Experiment 10.5); the central claim's bound is obtained with this fixed structure, not with an optimized vector.
assumptions (4)
  • domain assumption Dehomogenized multivariate Eulerian polynomials A_n(x,1) are RZ (real zero)
    Needed to apply the spectrahedral relaxation. Justified via real stability from Borcea-Branden theory, cited to [8,23,7] and Propositions 5.1 and 5.2.
  • domain assumption Spectrahedral relaxation theorem: rcs(p) subset S(p) for RZ p
    Quoted as [21, Theorem 3.35]; the whole bounding procedure relies on this inclusion.
  • standard math L-form values in Computation 6.4 are correct
    They are derived from the counting formula Corollary 6.2 and [21, Example 3.5]; all subsequent D and N expressions in Proposition 12.1 rest on these values.
  • domain assumption Asymptotics of y from [7]: y ~ -3^{n+1}/(2^{n+1} n)
    Used in Proposition 13.1 and Lemma 13.2 to identify the dominant terms. Stated without proof in this paper and imported from [7].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Guessing sequences of eigenvectors for LMPs defining spectrahedral relaxations of Eulerian rigidly convex sets." pith.science (2026). https://pith.science/paper/JLC7LGGV

@misc{pith2026250718434,
  author       = {Pith},
  title        = {Pith review of: Guessing sequences of eigenvectors for LMPs defining spectrahedral relaxations of Eulerian rigidly convex sets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JLC7LGGV}},
  note         = {Machine review of arXiv:2507.18434}
}
abstract

Stable multivariate Eulerian polynomials were introduced by Br\"and\'en. Particularizing some variables, it is possible to extract real zero multivariate Eulerian polynomials from them. These real zero multivariate Eulerian polynomials can be fed into constructions of spectrahedral relaxations providing therefore approximations to the (Eulerian) rigidly convex sets defined by these polynomials. The accuracy of these approximations is measured through the behaviour in the diagonal, where the usual univariate Eulerian polynomials sit. In particular, in this sense, the accuracy of the global spectrahedral approximation produced by the spectrahedral relaxation can be measured in terms of bounds for the extreme roots of univariate Eulerian polynomials. The bounds thus obtained beat the previous bounds found in the literature. However, the bound explicitly studied and obtained before beat the previously known bounds by a quantity going to $0$ when $n$ goes to infinity. Here we use numerical experiments to construct a sequence of vectors providing a (linearized) bound whose difference with the previous known bounds is a growing exponential function (going therefore fast to infinity when $n$ grows). This allows us to establish a better (diagonal) measure of accuracy for the spectrahedral relaxation of the Eulerian rigidly convex sets. In particular, we will achieve this by linearizing through the sequence of vectors $\{(y,(-2^{m-i})_{i=3}^{m},(0,\frac{1}{2}),(1)_{i=1}^{m})\in\mathbb{R}^{n+1}\}_{n=1}^{\infty}$ for even $n=2m$.

Figures

Figures reproduced from arXiv: 2507.18434 by the authors.

Figure 1
Figure 1. Representation of the entries of the eigenvectors in the interval [0 [PITH_FULL_IMAGE:figures/full_fig_p024_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [7]

    Spectrahedral relaxations of Eulerian rigidly convex sets

    A. Gonz´ alez Nevado,Spectrahedral relaxations of Eulerian rigidly convex sets, arXiv preprint arXiv:2507.03800, 2025

    work page Pith review arXiv 2025

  2. [21]

    Markus Schweighofer, Spectrahedral relaxations of hyperbolicity cones , arXiv preprint arXiv:1907.13611, 2023

    work page Pith review arXiv 1907

  3. [1]

    Real-rootedness of rook-Eulerian polynomials

    P. Alexandersson, A. Jal, M. Quemener, Real-rootedness of rook- Eulerian polynomials, arXiv preprint arXiv:2502.05939, 2025

    work page Pith review arXiv 2025

  4. [2]

    Barry, On integer-sequence-based constructions of generalized Pascal triangles, J

    P. Barry, On integer-sequence-based constructions of generalized Pascal triangles, J. Integer Seq., 9 (2006), Article 06.2.4

    work page 2006

  5. [3]

    Wag- ner, Proof of the monotone column permanent conjecture , in *Notions of Positivity and the Geometry of Polynomials*, Pages 63–78, Springer, 2011

    Petter Br¨ and´ en, James Haglund, Mirk´ o Visontai, and David G. Wag- ner, Proof of the monotone column permanent conjecture , in *Notions of Positivity and the Geometry of Polynomials*, Pages 63–78, Springer, 2011

    work page 2011

  6. [4]

    Demidenko and Vladimir L

    Gennadii V. Demidenko and Vladimir L. Vaskevich, Selected works of S.L. Sobolev, Springer, 2006

    work page 2006

  7. [5]

    Euler, Methodus universalis series summandi ulterius promota , Com- mentarii Acad

    L. Euler, Methodus universalis series summandi ulterius promota , Com- mentarii Acad. Scientiarum Imperialis Petropolitanae, Vol. 8, 1736, pp. 147–158

    work page

  8. [6]

    J.-B. J. Fourier, Solution d’une question particuli` ere du calcul des in´ egalit´ es, Nouveau Bulletin des Sciences par la Soci´ et´ e philomatique de Paris, vol. 99, 1826, pp. 100

    work page

Show all 24 references
  1. [8]

    James Haglund and Mirk´ o Visontai,Stable multivariate Eulerian polyno- mials and generalized Stirling permutations , European Journal of Com- binatorics, Volume 33, Number 4, Pages 477–487, Elsevier, 2012. 49

    2012

  2. [9]

    Haglund, P

    J. Haglund, P. B. Zhang, Real-rootedness of variations of Eulerian poly- nomials, Advances in Applied Mathematics, vol. 109, 2019, pp. 38–54

    2019

  3. [10]

    Eric Katz and Max Kutler, Matroidal mixed Eulerian numbers , Alge- braic Combinatorics, Volume 7, Number 5, Pages 1479–1506, 2024

    2024

  4. [11]

    Khoshnevisan, Probability, American Mathematical Society, Vol

    D. Khoshnevisan, Probability, American Mathematical Society, Vol. 80, 2007

    2007

  5. [12]

    Greg Knese, Determinantal representations of semihyperbolic polyno- mials, Michigan Mathematical Journal, Volume 65, Number 3, Pages 473–487, University of Michigan, Department of Mathematics, 2016

    2016

  6. [13]

    Mario Kummer, Daniel Plaumann, and Cynthia Vinzant, Hyperbolic polynomials, interlacers, and sums of squares , Mathematical Program- ming, Volume 153, Pages 223–245, Springer, 2015

    2015

  7. [14]

    John Michael MacNamee and Victor Yakovlevich Pan, Numerical Meth- ods for Roots of Polynomials – Parts I and II , Studies in Computational Mathematics, Volumes 14 and 16, Elsevier

  8. [15]

    Istv´ an Mez˝ o,Combinatorics and number theory of counting sequences , Chapman and Hall/CRC, 2019

    2019

  9. [16]

    R. B. Paris, D. Kaminski, Asymptotics and Mellin-Barnes Integrals , Cambridge University Press, Vol. 85, 2001

    2001

  10. [17]

    Robin Pemantle, Hyperbolicity and stable polynomials in combinatorics and probability, arXiv preprint arXiv:1210.3231, 2012

    2012 arXiv

  11. [18]

    Goldman, Some geometric results in semidefinite programming, Journal of Global Optimization, Volume 7, Number 1, Pages 33–50, Citeseer, 1995

    Motakuri Ramana and Alan J. Goldman, Some geometric results in semidefinite programming, Journal of Global Optimization, Volume 7, Number 1, Pages 33–50, Citeseer, 1995

    1995

  12. [19]

    C. D. Savage, M. Visontai, Eulerian polynomials of type D have only real roots, Discrete Mathematics & Theoretical Computer Science, Proc., 2013, Episciences.org

    2013

  13. [20]

    Savage, M

    C. Savage, M. Visontai, The s-Eulerian polynomials have only real roots, Transactions of the American Mathematical Society, vol. 367, no. 2, 2015, pp. 1441–1466. 50

    2015

  14. [22]

    Stump, Explicit forms for the roots of Eulerian polynomials , Math- Overflow, https://mathoverflow.net/q/287547

    C. Stump, Explicit forms for the roots of Eulerian polynomials , Math- Overflow, https://mathoverflow.net/q/287547

  15. [23]

    Mirk´ o Visontai and Nathan Williams, Stable multivariate W-Eulerian polynomials, Journal of Combinatorial Theory, Series A, Volume 120, Number 7, Pages 1929–1945, Elsevier, 2013

    1929

  16. [24]

    A. L. B. Yang, P. B. Zhang, The real-rootedness of Eulerian polynomials via the Hermite–Biehler theorem , Discrete Mathematics & Theoretical Computer Science, Proc., 2015, Episciences.org. 51

    2015

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.