Pith. sign in

REVIEW 4 minor 7 references

Adding a vertex to a 3-D polytope can increase its pyramidal width by 41 percent, an exact counterexample shows.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-03 04:40 UTC pith:GNHIISQP

load-bearing objection A small, exact, and believable counterexample to a 2015 monotonicity conjecture; the real risk is the unverified δ=PWidth bridge.

arxiv 2607.29555 v1 pith:GNHIISQP submitted 2026-07-31 cs.LG

Pyramidal Width Can Increase Under Vertex Insertion

Jinze Zhao This is my paper
classification cs.LG
keywords pyramidal widthfacial distancevertex insertionpolyhedral combinatoricspolytope conditioningexact rational verificationcounterexampleinteger points
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper targets a conjecture from the optimization literature: that the geometric quantity called pyramidal width, used to control convergence rates of projection-free methods, should never increase when a vertex is added to a polytope, as long as all old vertices remain extreme. The paper disproves this conjecture with an explicit pair of polytopes in three dimensions, both built from integer points. The smaller polytope has five vertices; after a sixth is inserted, all five old vertices remain vertices, yet the squared width rises from 48/353 to 36/133, a ratio of about 1.41. The proof reduces width to a finite list of face-to-vertex distances and computes every one by exact rational arithmetic, accompanied by a dependency-free verifier. If correct, this settles a longstanding open question and invalidates any reasoning that freely transfers width lower bounds from a containing polytope to a vertex subset.

Core claim

The central claim is that vertex-addition monotonicity for pyramidal width is false. Theorem 3.1 constructs six explicit integer points in R^3, defining P as the convex hull of five of them and Q as the convex hull of all six. Every vertex of P remains a vertex of Q, but PWidth(P)^2 = 48/353 while PWidth(Q)^2 = 36/133, so PWidth(Q)/PWidth(P) = sqrt(1059/532) > 1. The proof recasts pyramidal width as facial distance, certifies the complete face lattices by integer supporting hyperplanes, and evaluates every nonempty proper face's distance via exact rational calculation, eliminating any dependence on numerical rounding.

What carries the argument

The key is the exact identity equating pyramidal width with facial distance: the minimum Euclidean distance between a nonempty proper face and the convex hull of the polytope's remaining vertices. This identity turns the nested directional optimization that defines pyramidal width into finitely many convex-hull distance problems. For each face, the distance is computed exactly by enumerating affinely independent subsets of at most four difference vectors and solving rational linear systems; the face lattices themselves are certified by integer supporting hyperplanes, so the entire counterexample can be verified without floating-point arithmetic.

Load-bearing premise

The conclusion rests on the imported equivalence between pyramidal width and facial distance; if that equivalence fails for the paper's definition of pyramidal width, the counterexample would not refute the monotonicity conjecture.

What would settle it

Run the supplied exact verifier or independently recompute the squared facial distance for edge (1,4) of P and edge (2,5) of Q; any value differing from 48/353 or 36/133 respectively, or any supporting-hyperplane certificate that fails, would invalidate the claim. A direct numerical optimization over all directions in the original pyramidal-width definition could also confirm whether the reported ratio holds.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Lower bounds on pyramidal width cannot be freely transferred from a containing polytope to a vertex subset by inserting missing vertices; the general transfer rule is refuted.
  • The conditional route that derived pyramidal-width lower bounds for combinatorial strategy polytopes from this monotonicity principle now requires a separate geometric argument.
  • Established convergence theorems for projection-free methods remain unaffected, since they use the actual fixed width of the feasible polytope rather than the monotonicity principle.
  • The counterexample is not a 0/1-polytope and does not contradict known facial-distance bounds for structured families.
  • Monotonicity may still hold under additional hypotheses on the inserted vertex or for restricted polytope classes; the paper leaves those questions open.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The counterexample suggests that pyramidal width can oscillate along a chain of vertex insertions, so geometric conditioning of a polytope is not monotone in its vertex set even in low dimension; this could complicate incremental or online analyses that assume gradual improvement.
  • Because the construction uses only integer coordinates, a search for smaller or 0/1 counterexamples is a natural next test; a 0/1 vertex example, if found, would extend the failure to combinatorial polytopes.
  • The exact rational verifier is a reusable template for certifying finite polytope-conditioning computations without numerical error, offering a model for checking other geometric optimization constants.
  • The result leaves open whether an alternative geometric condition number, possibly based on a different normalization of width, has the hereditary property that pyramidal width was conjectured to have.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 4 minor

Summary. The paper gives an explicit nested pair of integer polytopes P⊂Q in R^3, with P=conv{v0,...,v4} and Q=conv{v0,...,v5}, all old vertices remaining extreme in Q, and shows that PWidth(P)^2=48/353 while PWidth(Q)^2=36/133. Thus the pyramidal width increases by the factor sqrt(1059/532)≈1.4109 upon vertex insertion, contradicting the Lacoste-Julien–Jaggi monotonicity conjecture stated as Eq. (4). The proof uses the facial-distance identity δ=PWidth from Peña and Rodríguez, certifies the two face lattices by explicit integer supporting hyperplanes, and evaluates all 46 facial distances by exact rational arithmetic. A companion verifier is said to check the combinatorics, the facial-distance tables, and the final strict inequality.

Significance. If the result stands, it settles a 2015 conjecture in the negative with a small, fully explicit, machine-checkable counterexample. The paper is unusually careful about exactness: integer supporting hyperplanes, rational facial-distance tables, and a verifier are concrete reproducibility assets. The result does not affect Frank–Wolfe convergence theorems that use the actual pyramidal width of a fixed polytope, but it removes the general vertex-addition monotonicity principle as a valid lower-bound transfer tool. The main mathematical dependency is the external identity δ=PWidth; that is a published theorem, and I do not see a circularity or parameter-fitting issue in the manuscript.

minor comments (4)
  1. [§2, Eq. (3)] The paper's central PWidth claims rest entirely on the identity δ(R)=PWidth(R) imported from [6]. Please state the exact theorem from [6] that is being used and confirm explicitly that the conventions in Eq. (1) — especially the meaning of 'proper convex combination' and the treatment of the case where x is a vertex and S_x is empty — match the definition in [4] and the hypotheses of [6]. This is the one step I could not verify from the manuscript alone.
  2. [Abstract and §6] The phrase 'dependency-free exact verifier' is accurate about software dependencies, but the verifier actually checks the facial-distance computations and then applies Eq. (3) to reach PWidth values. Consider rephrasing to 'dependency-free exact verification of the facial-distance computations and of the derived PWidth values under identity (3)', so that the external status of Eq. (3) is not obscured.
  3. [§2, Eq. (2)] The notation V(R)\F, where F is a face rather than a subset of the vertex set, is clarified in prose but could be defined directly after Eq. (2) to avoid ambiguity: 'V(R)\F means the set of vertices of R that do not lie in F.'
  4. [§6, Reproducibility] The verifier is referenced as an accompanying file, but no code listing or checksum is included. For a paper whose reproducibility claim is central, please ensure the link is stable and, ideally, include the verifier or a full transcript of its output as supplementary material.

Circularity Check

0 steps flagged

No circularity: the counterexample is computed directly from definitions, with only an external theorem (Peña-Rodríguez) as the bridge.

full rationale

The paper's derivation chain is: define pyramidal width in Eq. (1); import the exact identity δ(R) = PWidth(R) from Peña and Rodríguez [6] in Eq. (3); compute all facial distances δ(P) and δ(Q) by finite rational enumeration; and thereby obtain the claimed PWidth values. The only load-bearing imported result is Eq. (3), which is an external theorem by different authors, not a self-citation and not an ansatz smuggled in by the present author. The facial-distance computations themselves are performed directly from the definitions, with exact integer supporting hyperplanes, affine determinants, and rational closest-point calculations, and they are exhaustively checked by the accompanying verifier. Nothing is fitted, no parameter is tuned to a subset of data, and no quantity is renamed as a prediction. The skeptic's concern that the verifier checks δ rather than PWidth is a correctness-risk point about reliance on [6], not circularity: the external theorem is stated as an assumption and is independent of the target counterexample. Since no step reduces by construction to its own inputs and no self-citation is load-bearing, the paper is free of circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

No new entities or free parameters; the proof is an explicit finite computation. The central external dependency is the distance equivalence [6].

axioms (3)
  • domain assumption Definition of pyramidal width PWidth(A) as in Eq. (1) matches Lacoste-Julien and Jaggi [4].
    This is the standard definition in the literature; the paper does not re-derive it but it is the definition to which the conjecture applies.
  • domain assumption External identity δ(R) = PWidth(R) from [6], Eq. (3).
    The proof relies on replacing pyramidal width with facial distance; cited from [6], not re-proved in this paper.
  • standard math Euler's relation for simplicial 3-polytopes (f2 = 2 f0 - 4) used in Proposition 3.2.
    Used to conclude the listed facets are complete; standard combinatorial topology.

pith-pipeline@v1.3.0-daily-deepseek · 5608 in / 4827 out tokens · 38186 ms · 2026-08-03T04:40:23.044934+00:00 · methodology

0 comments
read the original abstract

Lacoste-Julien and Jaggi conjectured in 2015 that the pyramidal width of a polytope cannot increase when a vertex is added, provided that every old point remains a vertex. We give an exact counterexample with six integer points in $\R^3$. For \[ P=\conv\{v_0,\ldots,v_4\},\qquad Q=\conv\{v_0,\ldots,v_5\}, \] where \[ \begin{aligned} v_0&=(-1,-3,-1), & v_1&=(3,2,-2), & v_2&=(0,2,1),\\ v_3&=(-1,-3,3), & v_4&=(-2,0,1), & v_5&=(-1,0,-2), \end{aligned} \] all five vertices of $P$ remain vertices of $Q$, but \[ \PWidth(P)^2=\frac{48}{353} \quad\text{and}\quad \PWidth(Q)^2=\frac{36}{133}. \] Thus vertex insertion increases pyramidal width by the factor $\sqrt{1059/532}\approx 1.410886779$. The proof uses the equivalence between pyramidal width and facial distance, certifies both face lattices by integer supporting hyperplanes, and evaluates every facial distance by a finite rational calculation. A dependency-free exact verifier accompanies the paper.

Figures

Figures reproduced from arXiv: 2607.29555 by Jinze Zhao.

Figure 1
Figure 1. Figure 1: Orthographic visualization of P (left) and Q (right). The minimizing face is highlighted in red: edge 14 for P and edge 25 for Q. The dashed segment joins the exact closest points used in Section 5. The drawing is illustrative and is not used in the proof. 4 Exact facial-distance certification This section describes a finite rational method for evaluating every term in Equation (2). For finite sets A, B ⊂ … view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

7 extracted references · 2 canonical work pages

  1. [1]

    Efficient learning in polyhedral games via best-response oracles

    Darshan Chakrabarti, Gabriele Farina, and Christian Kroer. Efficient learning in polyhedral games via best-response oracles. InProceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 9564–9572, 2024. doi: 10.1609/aaai.v38i9.28812

    work page doi:10.1609/aaai.v38i9.28812 2024

  2. [2]

    An algorithm for quadratic programming.Naval Research Logistics Quarterly, 3(1–2):95–110, 1956

    Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming.Naval Research Logistics Quarterly, 3(1–2):95–110, 1956. doi: 10.1002/nav.3800030109

    doi:10.1002/nav.3800030109 1956

  3. [3]

    Revisiting Frank–Wolfe: Projection-free sparse convex optimization

    Martin Jaggi. Revisiting Frank–Wolfe: Projection-free sparse convex optimization. InProceedings of the 30th International Conference on Machine Learning, volume 28 ofProceedings of Machine Learning Research, pages 427–435, 2013. URLhttps://proceedings.mlr.press/v28/jaggi13. html

    2013

  4. [4]

    On the global linear convergence of Frank– Wolfe optimization variants

    Simon Lacoste-Julien and Martin Jaggi. On the global linear convergence of Frank– Wolfe optimization variants. InAdvances in Neural Information Processing Systems 28, pages 496–504, 2015. URL https://proceedings.neurips.cc/paper/2015/hash/ c058f544c737782deacefa532d9add4c-Abstract.html

    2015

  5. [5]

    Practical Frank–Wolfe method with decision diagrams for computing wardrop equilibrium of combinatorial congestion games

    Kengo Nakamura, Shinsaku Sakaue, and Norihito Yasuda. Practical Frank–Wolfe method with decision diagrams for computing wardrop equilibrium of combinatorial congestion games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2200–2209, 2020. doi: 10.1609/aaai.v34i02.5596. 7

    work page doi:10.1609/aaai.v34i02.5596 2020

  6. [6]

    Polytope conditioning and linear convergence of the Frank– Wolfe algorithm.Mathematics of Operations Research, 44(1):1–18, 2019

    Javier Peña and Daniel Rodríguez. Polytope conditioning and linear convergence of the Frank– Wolfe algorithm.Mathematics of Operations Research, 44(1):1–18, 2019. doi: 10.1287/moor. 2017.0910

    arXiv 2019

  7. [7]

    Ziegler.Lectures on Polytopes, volume 152 ofGraduate Texts in Mathematics

    Günter M. Ziegler.Lectures on Polytopes, volume 152 ofGraduate Texts in Mathematics. Springer, New York, 1995. doi: 10.1007/978-1-4613-8431-1. A Supporting and affine certificates Table 2 gives primitive integer supporting inequalities for all facets used in Theorem 3.2. Direct substitution verifies thata⊤vi =b exactly for the indices in the facet column ...

    doi:10.1007/978-1-4613-8431-1 1995