Pyramidal Width Can Increase Under Vertex Insertion Jinze Zhao University of California, San Diego [email protected] Abstract Lacoste-Julien and Jaggi [4] 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 R3 . For
arXiv:2607.29555v1 [cs.LG] 31 Jul 2026
P = conv{v0 , . . . , v4 }, where
Q = conv{v0 , . . . , v5 },
v0 = (−1, −3, −1),
v1 = (3, 2, −2),
v2 = (0, 2, 1),
v3 = (−1, −3, 3),
v4 = (−2, 0, 1),
v5 = (−1, 0, −2),
all five vertices of P remain vertices of Q, but PWidth(P )2 =
48 353
and
PWidth(Q)2 =
36 . 133
p Thus vertex insertion increases pyramidal width by the factor 1059/532 ≈ 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. Keywords: Frank–Wolfe method; pyramidal width; facial distance; polytope conditioning; exact counterexample.
1
Introduction
The Frank–Wolfe method minimizes a differentiable convex function over a compact convex set using only linear optimization subproblems [2, 3]. For polytopal feasible regions, away-step, pairwise, and fully corrective variants can converge linearly. The rate bounds of Lacoste-Julien and Jaggi [4] separate analytic conditioning of the objective from geometric conditioning of the feasible polytope. Their geometric quantity is the pyramidal width. In Section 3.1, footnote 7 of that work, Lacoste-Julien and Jaggi conjectured that pyramidal width is non-increasing when another vertex is added, as long as the old points remain vertices. Such a rule would be useful because it could transfer lower bounds from a simple containing polytope to a complicated vertex subset. The conjecture was subsequently invoked as a conditional route to a pyramidal-width lower bound for combinatorial strategy polytopes [5]. The conjecture is false. This paper makes three contributions. (i) We give a six-vertex integer counterexample in dimension three. Adding one vertex increases pyramidal width by approximately 41.1%. (ii) We give an exact proof. Integer supporting planes certify the complete face lattices, and rational arithmetic evaluates the facial distance of every nonempty proper face. 1
(iii) We provide a short dependency-free verifier that independently checks the combinatorics, all 46 facial-distance values, and the strict inequality. The counterexample does not challenge the established convergence theorems that use pyramidal width as a positive geometric constant. It invalidates only the proposed general monotonicity principle and deductions that rely on that principle without additional structure. The remainder of the paper is organized as follows. Section 2 records the definitions and the facial-distance equivalence of Peña and Rodríguez [6]. Section 3 states the counterexample and certifies its face lattices. Section 4 gives the exact finite distance method, and Section 5 applies it. Full rational tables and supporting certificates appear in the appendix.
2
Pyramidal width and facial distance
Throughout, all distances and inner products are Euclidean. For a finite set A ⊂ Rd and a nonzero direction r, define r ,s − v . dirW(A, r) := max s,v∈A ∥r∥ Let M = conv(A). If x ∈ M , let Sx be the collection of subsets S ⊆ A for which x is a proper convex combination of the points in S, and choose s(A, r) ∈ arg max⟨r, v⟩. v∈A
The pyramidal directional width is
PdirW(A, r, x) := min dirW S ∪ {s(A, r)}, r . S∈Sx
Following Lacoste-Julien and Jaggi [4, Section 3], the pyramidal width is PWidth(A) :=
min
K a face of M, x∈K, 0̸=r∈cone(K−x)
PdirW(K ∩ A, r, x).
(1)
The minimization over feasible directions in all faces prevents ordinary width from degenerating along a lower-dimensional face. For a polytope R, write V (R) for its vertex set and abbreviate PWidth(R) := PWidth(V (R)). Define its facial distance by δ(R) :=
min
F a nonempty proper face of R
dist F, conv V (R) \ F
.
(2)
Here V (R) \ F means the vertices of R that are not contained in F . Theorems 1 and 2 of Peña and Rodríguez [6] imply the exact identity δ(R) = PWidth(R).
(3)
This equivalence is the key to the proof: it replaces the nested directional optimization in Equation (1) by finitely many distances between convex hulls. The vertex-insertion conjecture of Lacoste-Julien and Jaggi [4, Section 3.1, footnote 7] can now be written as follows. If A = V (conv A) and all points of A remain vertices of conv(A ∪ {v}), then PWidth(A ∪ {v}) ≤ PWidth(A). We disprove Equation (4) in dimension three. 2
(4)
3
The counterexample and its combinatorics
Consider the six points in Table 1 and the nested polytopes P := conv{v0 , v1 , v2 , v3 , v4 },
Q := conv{v0 , v1 , v2 , v3 , v4 , v5 }.
(5)
Table 1: Integer vertices of the counterexample. Vertex v0 v1 v2 v3 v4 v5
First coordinate
Second coordinate
Third coordinate
−1 3 0 −1 −2 −1
−3 2 2 −3 0 0
−1 −2 1 3 1 −2
Theorem 3.1 (Failure of vertex-insertion monotonicity). Every point v0 , . . . , v4 is a vertex of both P and Q, while 48 36 PWidth(P )2 = and PWidth(Q)2 = . (6) 353 133 Consequently, r PWidth(Q) 1059 = ≈ 1.410886779 > 1. PWidth(P ) 532 We first certify the combinatorial part of the theorem. A string such as 013 denotes the triangle conv{v0 , v1 , v3 }. Proposition 3.2 (Exact face lattices). The facets of P are 013, 014, 034, 123, 124, 234,
(7)
013, 015, 034, 045, 123, 125, 234, 245.
(8)
and the facets of Q are In particular, P and Q have f -vectors (5, 9, 6) and (6, 12, 8), respectively, and every old vertex remains a vertex after v5 is inserted. Proof. For each triangle in Equations (7) and (8), Table 2 gives integers a, b such that every relevant vertex satisfies a⊤ x ≤ b, with equality precisely at the three named vertices. Thus every listed triangle is a facet. The 15 affine determinants in Table 3 are nonzero. Hence the points are in general affine position, both polytopes are full-dimensional, and every facet is triangular. Each input point occurs in at least one listed supporting triangle, so each is extreme. A simplicial three-polytope with f0 vertices has f2 = 2f0 − 4 facets by Euler’s relation [7]. The lists contain exactly 6 = 2 · 5 − 4 and 8 = 2 · 6 − 4 facets, respectively, so no facets are omitted. Their two-element subsets give the asserted edge counts.
3
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 ⊂ R3 , write conv(A) − conv(B) := {x − y : x ∈ conv(A), y ∈ conv(B)} for their Minkowski difference. Lemma 4.1 (Finite exact distance calculation). Let D(A, B) := {a − b : a ∈ A, b ∈ B}. Then dist conv(A), conv(B)
2
=
min
∥z∥2 .
z∈conv D(A,B)
(9)
If A and B have rational coordinates, the value in Equation (9) can be obtained by enumerating affinely independent subsets of D(A, B) of size at most four and solving rational linear systems. Proof. First, conv(A) − conv(B) = conv D(A, B).
(10)
Indeed, if x = i αi ai and y = j βj bj , then x − y = i,j αi βj (ai − bj ). Conversely, the row and column marginals of any convex combination of the differences produce points x ∈ conv(A) and y ∈ conv(B). Equation (9) follows immediately. By Caratheodory’s theorem in R3 , a minimizer z has an affinely independent representation using k ≤ 4 difference vectors d1 , . . . , dk . For a proposed support, let D = [d1 · · · dk ] and G = D⊤ D. The stationary point of ∥Dλ∥2 on 1⊤ λ = 1 is obtained from P
P
P
"
G 1 1⊤ 0
#" #
" #
λ 0 = . µ 1
4
(11)
For an affinely independent support, the bordered matrix is nonsingular. The candidate is retained when λ ≥ 0. For completeness, singular supports may be skipped because every point of the convex hull has an affinely independent Caratheodory representation. If the affine projection for a support has a negative barycentric coordinate, the minimum over that simplex lies on a proper face, which is covered by a smaller support. Thus enumeration of all affinely independent supports of size at most four is exhaustive. Rational inputs make Equation (11), its solution, and the resulting squared norm rational.
5
Evaluation of the two polytopes
For each nonempty proper face F of P and Q, apply Theorem 4.1 with B = V (R) \ F.
A = V (F ),
There are 5 + 9 + 6 = 20 such faces for P and 6 + 12 + 8 = 26 for Q. The complete tables are Tables 4 and 5; every entry is a squared distance. For P , the unique minimum is attained at the edge F = 14: δ(P )2 =
48 . 353
(12)
The next smallest table entry is 432/233, so the minimum is strict. Exact closest points are p=
104v1 + 249v4 1 = (−186, 208, 41), 353 353
q=
110v0 + 243v2 1 = (−110, 156, 133). 353 353
(13)
Their difference is
1 48 (−76, 52, −92), ∥r∥2 = . 353 353 The positive coefficients in Equation (13) place p in edge 14 and q in conv{v0 , v2 , v3 }. Moreover, r =p−q =
⟨r, v1 − p⟩ = ⟨r, v4 − p⟩ = 0,
⟨r, v0 − q⟩ = ⟨r, v2 − q⟩ = 0,
⟨r, v3 − q⟩ = −
368 < 0. 353
These are the first-order closest-pair inequalities; the exhaustive table supplies the global lower bound. For Q, the unique minimum is attained at edge F = 25: δ(Q)2 =
36 . 133
(14)
The next smallest value is 144/475. Exact closest points are p′ =
76v2 + 57v5 1 = (−3, 8, −2), 133 7
q′ =
Thus
49v1 + 84v4 1 = (−3, 14, −2). 133 19
(15)
1 36 (−36, 54, −24), ∥r′ ∥2 = . 133 133 The active vertices again have zero first-order margins, while the two inactive complement vertices satisfy 150 246 ⟨r′ , v0 − q ′ ⟩ = − < 0, ⟨r′ , v3 − q ′ ⟩ = − < 0. 133 133 r′ = p′ − q ′ =
5
Combining Equations (3), (12) and (14) gives PWidth(P )2 =
48 , 353
PWidth(Q)2 =
36 . 133
Finally, 36 48 6324 − = > 0, 133 353 46949 which proves Theorem 3.1.
6
Consequences, scope, and reproducibility
What the example resolves. The construction disproves the general vertex-addition inequality Equation (4). In particular, a pyramidal-width lower bound for a vertex subset cannot be inferred only by inserting its missing vertices into a better understood containing polytope. The conditional use of that route in Nakamura et al. [5] therefore requires a separate geometric argument. What the example does not resolve. The example is not a 0/1-polytope and does not invalidate independently proved facial-distance bounds for structured families; see, for example, Chakrabarti et al. [1]. It also does not contradict the positivity of pyramidal width for a fixed finite vertex set or any Frank–Wolfe convergence theorem expressed directly in terms of the actual width. A monotonicity result for adding redundant atoms while keeping the convex hull fixed is a different statement: here v5 is a new extreme point and changes the polytope. Reproducibility. The accompanying file code/verify_pyramidal_counterexample.js shared via the link uses only Node.js and exact BigInt rational arithmetic. It independently: (i) enumerates and certifies all supporting facets and affine determinants; (ii) reconstructs all vertices, edges, and facets; (iii) enumerates the Caratheodory supports in Theorem 4.1; (iv) checks every entry of Tables 4 and 5; and (v) asserts the unique minima and their strict ratio. Run it from the source directory with node code/verify_pyramidal_counterexample.js. Priority. To the best of our knowledge, this is the first counterexample to the vertex-addition monotonicity conjecture of Lacoste-Julien and Jaggi [4]. Targeted exact-phrase, citation, and specialist-literature searches through July 31, 2026 found no prior proof or counterexample. This statement is a literature-search report, not a substitute for peer review or a formal priority determination.
6
7
Conclusion
Pyramidal width is not monotone under vertex insertion, even for full-dimensional simplicial polytopes in R3 with integer coordinates. The explicit pair P ⊂ Q satisfies PWidth(P )2 =
48 36 < = PWidth(Q)2 . 353 133
The proof is finite and exact: it reduces pyramidal width to facial distance, certifies every face, and solves only rational quadratic programs of dimension at most four. The example leaves useful structured questions open. Monotonicity may still hold under additional hypotheses on the inserted vertex or for restricted families, and alternative geometric condition numbers may have better hereditary behavior. Independently proved bounds for special families, such as the structured facial-distance bounds of Chakrabarti et al. [1], are unaffected. Any lower bound derived solely from the general vertex-insertion conjecture, however, requires a separate proof.
8
Disclosure
The proof strategy and counterexample were produced by OpenAI’s GPT-5.6 Sol Ultra through Codex in response to prompts from Jinze Zhao. Codex was also used to revise the exposition and prepare the LaTeX manuscript. The author selected the problem, directed the interactions and revisions, and is the sole named author. The AI system is acknowledged as a reasoning and writing tool, not as an author. This disclosure is not a substitute for independent expert mathematical review.
References [1] Darshan Chakrabarti, Gabriele Farina, and Christian Kroer. Efficient learning in polyhedral games via best-response oracles. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 9564–9572, 2024. doi: 10.1609/aaai.v38i9.28812. [2] 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. [3] Martin Jaggi. Revisiting Frank–Wolfe: Projection-free sparse convex optimization. In Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 427–435, 2013. URL https://proceedings.mlr.press/v28/jaggi13. html. [4] Simon Lacoste-Julien and Martin Jaggi. On the global linear convergence of Frank– Wolfe optimization variants. In Advances in Neural Information Processing Systems 28, pages 496–504, 2015. URL https://proceedings.neurips.cc/paper/2015/hash/ c058f544c737782deacefa532d9add4c-Abstract.html. [5] 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
[6] 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. [7] Günter M. Ziegler. Lectures on Polytopes, volume 152 of Graduate 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 that a⊤ vi = b exactly for the indices in the facet column and that all other relevant vertices satisfy a strict inequality. Table 2: Supporting inequalities a⊤ x ≤ b. Polytope
Facet
a
b
P, Q P, Q P, Q P, Q
013 034 123 234
(5, −4, 0) (−3, −1, 0) (5, 1, 5) (−1, 1, 2)
7 6 7 4
P P
014 124
(−13, 7, −17) (−1, 1, −1)
9 1
Q Q Q Q
015 045 125 245
(1, −2, −6) (−9, −1, −3) (−1, 2, −1) (−3, 3, −1)
11 15 3 5
For i < j < k < ℓ, define
∆ijkℓ := det vj − vi vk − vi vℓ − vi . The exact values in Table 3 show that no four of the six points are coplanar. Table 3: All four-point affine determinants. Indices
∆
Indices
∆
Indices
∆
0123 0134 0234 0345 1245
60 −68 −32 −12 −12
0124 0135 0235 1234 1345
−12 −48 −12 −36 46
0125 0145 0245 1235 2345
−42 −38 −20 −66 28
8
B
Complete facial-distance tables
Each value below is dR (F )2 := dist F, conv V (R) \ F
2
.
Faces are written as vertex-index strings. The tables contain every nonempty proper face from Theorem 3.2. Table 4: All squared facial distances for P . Face F
dP (F )2
Face F
dP (F )2
0 2 4
Vertices 4624/483 1 54/19 3 32/13
177/10 80/7
01 04 13 23 34
Edges 4624/419 03 16/5 12 3600/1619 14 432/233 24 16/5
10 8 48/353 108/17
013 034 124
Facets 108/17 014 8 123 10 234
432/233 16/5 4624/419
Table 5: All squared facial distances for Q. Face F
dQ (F )2
Face F
dQ (F )2
0 2 4
Vertices 72/17 1 54/19 3 784/395 5
108/7 80/7 1444/507
01 04 12 15 24 34
Edges 576/257 03 144/475 05 38/5 13 441/101 23 115/34 25 16/5 45
91/10 92/19 3600/1619 432/233 36/133 16/11
013 034 123 234
Facets 1764/467 015 16/3 045 16/5 125 100/11 245
100/11 16/5 16/3 1764/467
9
C
Machine-checkable certificate
The verifier represents a rational number as a normalized pair of arbitrary precision integers. Gaussian elimination solves Equation (11) without rounding. Its expected terminal summary is PWidth(P)^2 = 48/353 at face 14 PWidth(Q)^2 = 36/133 at face 25 squared ratio = 1059/532 All exact dependency-free checks passed, including every table entry. The script also asserts each intermediate value, so this summary is printed only after all combinatorial and distance certificates have passed.
10