Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 12.7 — arbitrary-count setup sequence hull

Disproved
PochetWolsey.Modes.arbitrary_mode_hull

by Shuze Chen · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-hullp2o-gran-per-chapterp2o-plan-bookp2o-v1production-planningset-up-sequences

Let YM∞−SCY^{M\infty-SC}YM∞−SC consist of setup, startup and switch-off triples generated by nonempty lists of distinct items in each period. The last item of each period is the first of the next; yyy indicates membership, zzz membership except the first item, and www membership except the last item. Let PPP be the following unit-box extension in (y,z,w,ϕ)(y,z,w,\phi)(y,z,w,ϕ):

∑j(yj(t)−zj(t))=1,yi(t+1)−zi(t+1)=yi(t)−wi(t),\sum_j(y_j(t)-z_j(t))=1,\qquad y_i(t+1)-z_i(t+1)=y_i(t)-w_i(t),j∑​(yj​(t)−zj​(t))=1,yi​(t+1)−zi​(t+1)=yi​(t)−wi​(t), yi(t)−zi(t)≥ϕi(t),yi(t)−wi(t)≥ϕi(t),ϕi(t)≥yi(t)−zi(t)−wi(t),y_i(t)-z_i(t)\ge\phi_i(t),\quad y_i(t)-w_i(t)\ge\phi_i(t),\quad\phi_i(t)\ge y_i(t)-z_i(t)-w_i(t),yi​(t)−zi​(t)≥ϕi​(t),yi​(t)−wi​(t)≥ϕi​(t),ϕi​(t)≥yi​(t)−zi​(t)−wi​(t), yi(t)+∑j≠iϕj(t)≤1.y_i(t)+\sum_{j\ne i}\phi_j(t)\le1.yi​(t)+j=i∑​ϕj​(t)≤1.

The continuity equation applies between adjacent periods and all other inequalities in every period. The printed claim is

conv⁡(YM∞−SC)={(y,z,w):∃ϕ, (y,z,w,ϕ)∈P}.\operatorname{conv}(Y^{M\infty-SC})=\{(y,z,w):\exists\phi,\ (y,z,w,\phi)\in P\}.conv(YM∞−SC)={(y,z,w):∃ϕ, (y,z,w,ϕ)∈P}.

This asserts an exact projection formula without a bound on the number of distinct items within a period. Finding F2 records a terminal counterexample to the printed system under the ordered-list semantics; the faithful claim is retained for disproof rather than silently repaired.

Formalization Note There are m+1m+1m+1 labels, including idle label 000, and n+1n+1n+1 periods, numbered 0,…,n0,\ldots,n0,…,n. Thus m=n=0m=n=0m=n=0 means one idle label and one period, not empty index sets. The final item is retained as the last setup. No equation ∑i(yi(n)−wi(n))=1\sum_i(y_i(n)-w_i(n))=1∑i​(yi​(n)−wi​(n))=1 is added to the printed right-hand side. Only the diagonal auxiliary coordinates are present.

Preamble
import Mathlib
Formal statement
namespace PochetWolsey.Modes

theorem arbitrary_mode_hull (m n : ℕ) :
    convexHull ℝ ({p : ((Fin (m + 1) → Fin (n + 1) → ℝ) × (Fin (m + 1) → Fin (n + 1) → ℝ) × (Fin (m + 1) → Fin (n + 1) → ℝ)) | ∃ s : Fin (n + 1) → List (Fin (m + 1)),
      (∀ t, s t ≠ [] ∧ (s t).Nodup) ∧
      (∀ t : Fin n, (s t.castSucc).getLast? = (s t.succ).head?) ∧ p = ((fun i t => if i ∈ s t then (1 : ℝ) else 0), (fun i t => if i ∈ (s t).tail then (1 : ℝ) else 0), (fun i t => if i ∈ (s t).dropLast then (1 : ℝ) else 0))}) =
    {p | ∃ φ : (Fin (m + 1) → Fin (n + 1) → ℝ),
    (∀ i, (∀ t, 0 ≤ p.1 i t ∧ p.1 i t ≤ 1)) ∧
  (∀ i, (∀ t, 0 ≤ p.2.1 i t ∧ p.2.1 i t ≤ 1)) ∧
  (∀ i, (∀ t, 0 ≤ p.2.2 i t ∧ p.2.2 i t ≤ 1)) ∧
  (∀ i, (∀ t, 0 ≤ φ i t ∧ φ i t ≤ 1)) ∧
  (∀ t, ∑ j, (p.1 j t - p.2.1 j t) = 1) ∧
  (∀ i (t : Fin n), p.1 i t.succ - p.2.1 i t.succ =
    p.1 i t.castSucc - p.2.2 i t.castSucc) ∧
  (∀ i t, p.1 i t - p.2.1 i t ≥ φ i t) ∧
  (∀ i t, p.1 i t - p.2.2 i t ≥ φ i t) ∧
  (∀ i t, φ i t ≥ p.1 i t - p.2.1 i t - p.2.2 i t) ∧
  (∀ i t, p.1 i t + ∑ j ∈ Finset.univ.erase i, φ j t ≤ 1)} := by sorry

end PochetWolsey.Modes
Source
Pochet and Wolsey, Production Planning by Mixed Integer Programming, Springer 2006, p. 381 (PDF 392), Proposition 12.7
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

For natural numbers mmm and nnn, write I={0,1,…,m}I=\{0,1,\dots,m\}I={0,1,…,m} for a set of m+1m+1m+1 indices (call them modes) and T={0,1,…,n}T=\{0,1,\dots,n\}T={0,1,…,n} for a set of n+1n+1n+1 indices (call them periods). There are no other hypotheses: the statement is claimed for every pair m,n≥0m,n\ge 0m,n≥0. Points live in the real vector space

RI×T×RI×T×RI×T,\mathbb{R}^{I\times T}\times\mathbb{R}^{I\times T}\times\mathbb{R}^{I\times T},RI×T×RI×T×RI×T,

and a point is written p=(x,y,z)p=(x,y,z)p=(x,y,z) with real entries xi,tx_{i,t}xi,t​, yi,ty_{i,t}yi,t​, zi,tz_{i,t}zi,t​ for i∈Ii\in Ii∈I, t∈Tt\in Tt∈T.

The generating set SSS. A point (x,y,z)(x,y,z)(x,y,z) belongs to SSS exactly when there is a choice of a finite list sts_tst​ of modes for each period t∈Tt\in Tt∈T satisfying all of the following:

  • Each sts_tst​ is nonempty and has no repeated entries.
  • For every t∈{0,…,n−1}t\in\{0,\dots,n-1\}t∈{0,…,n−1}, the last entry of sts_tst​ equals the first entry of st+1s_{t+1}st+1​.
  • For all i∈Ii\in Ii∈I and t∈Tt\in Tt∈T, the coordinates are the indicators
xi,t=1[i∈st],yi,t=1[i∈tail⁡(st)],zi,t=1[i∈dropLast⁡(st)].x_{i,t}=\mathbf 1[i\in s_t],\qquad y_{i,t}=\mathbf 1[i\in \operatorname{tail}(s_t)],\qquad z_{i,t}=\mathbf 1[i\in \operatorname{dropLast}(s_t)].xi,t​=1[i∈st​],yi,t​=1[i∈tail(st​)],zi,t​=1[i∈dropLast(st​)].

Here tail⁡(st)\operatorname{tail}(s_t)tail(st​) is sts_tst​ without its first entry, and dropLast⁡(st)\operatorname{dropLast}(s_t)dropLast(st​) is sts_tst​ without its last entry.

Because entries are distinct, three consequences follow:

  • yi,t=1y_{i,t}=1yi,t​=1 iff iii appears in sts_tst​ and is not its first entry.
  • zi,t=1z_{i,t}=1zi,t​=1 iff iii appears in sts_tst​ and is not its last entry.
  • If sts_tst​ has a single entry, then y⋅,t=z⋅,t=0y_{\cdot,t}=z_{\cdot,t}=0y⋅,t​=z⋅,t​=0.

Only the set of entries, the first entry and the last entry of each list affect the point. The order of the middle entries does not. Since III and TTT are finite and lists have no repeats, SSS is a finite set of 0/10/10/1 points.

The claim. The convex hull of SSS over R\mathbb{R}R (the set of all finite convex combinations of points of SSS, with no closure taken) is equal, as a set, to the set PPP defined below. Equality means both inclusions hold.

The set PPP. A point (x,y,z)(x,y,z)(x,y,z) belongs to PPP exactly when there exists an auxiliary array φ∈RI×T\varphi\in\mathbb{R}^{I\times T}φ∈RI×T satisfying all of the following. The array φ\varphiφ is existentially quantified and is not part of the point.

  1. Bounds. For all i,ti,ti,t:
0≤xi,t≤1,0≤yi,t≤1,0≤zi,t≤1,0≤φi,t≤1.0\le x_{i,t}\le 1,\qquad 0\le y_{i,t}\le 1,\qquad 0\le z_{i,t}\le 1,\qquad 0\le \varphi_{i,t}\le 1.0≤xi,t​≤1,0≤yi,t​≤1,0≤zi,t​≤1,0≤φi,t​≤1.
  1. Per-period sum. For every t∈Tt\in Tt∈T:
∑j∈I(xj,t−yj,t)=1.\sum_{j\in I}\bigl(x_{j,t}-y_{j,t}\bigr)=1.j∈I∑​(xj,t​−yj,t​)=1.
  1. Linking consecutive periods. For every i∈Ii\in Ii∈I and every t∈{0,…,n−1}t\in\{0,\dots,n-1\}t∈{0,…,n−1}:
xi,t+1−yi,t+1=xi,t−zi,t.x_{i,t+1}-y_{i,t+1}=x_{i,t}-z_{i,t}.xi,t+1​−yi,t+1​=xi,t​−zi,t​.
  1. Upper bounds on φ\varphiφ. For all i,ti,ti,t:
φi,t≤xi,t−yi,tandφi,t≤xi,t−zi,t.\varphi_{i,t}\le x_{i,t}-y_{i,t}\quad\text{and}\quad \varphi_{i,t}\le x_{i,t}-z_{i,t}.φi,t​≤xi,t​−yi,t​andφi,t​≤xi,t​−zi,t​.
  1. Lower bound on φ\varphiφ. For all i,ti,ti,t:
φi,t≥xi,t−yi,t−zi,t.\varphi_{i,t}\ge x_{i,t}-y_{i,t}-z_{i,t}.φi,t​≥xi,t​−yi,t​−zi,t​.
  1. Packing. For all i,ti,ti,t:
xi,t+∑j∈I, j≠iφj,t≤1.x_{i,t}+\sum_{j\in I,\ j\ne i}\varphi_{j,t}\le 1.xi,t​+j∈I, j=i∑​φj,t​≤1.

Degenerate cases. No division, natural-number subtraction, integrals or suprema occur, so no default or junk values arise. All sums are over finite index sets, and all inequalities are non-strict.

  • m=0m=0m=0 (one mode). Every list sts_tst​ must be the one-element list [0][0][0]. So SSS is the single point with x≡1x\equiv 1x≡1 and y≡z≡0y\equiv z\equiv 0y≡z≡0, and the convex hull is that one point. In PPP, the sum in constraint 6 is empty, so constraint 6 reduces to x0,t≤1x_{0,t}\le 1x0,t​≤1. Constraint 2 reads x0,t−y0,t=1x_{0,t}-y_{0,t}=1x0,t​−y0,t​=1.
  • n=0n=0n=0 (one period). Constraint 3 and the first-equals-last condition on lists are vacuous. SSS consists of the indicator triples of single nonempty repetition-free lists s0s_0s0​.
  • m=n=0m=n=0m=n=0. Both reductions above apply together. The statement asserts that the convex hull of the single point (1,0,0)(1,0,0)(1,0,0) equals the set of (x,y,z)∈R3(x,y,z)\in\mathbb{R}^3(x,y,z)∈R3 that satisfy constraints 1–6 for some φ∈[0,1]\varphi\in[0,1]φ∈[0,1], with constraint 3 vacuous and the sum in constraint 6 empty.

The statement asserts equality of these two sets in every one of these cases, exactly as written.

Human review
  • Endorsed by Community (Bot) · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 29, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me