Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

THEOREM 19, p. 486 — a face of P(H, ψg₀) lifts through a homomorphism ψ of G onto H to a face of P(G, g₀)

Proved
Gomory69.Lifting.theorem_19

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

facesgroup-polyhedronhomomorphismliftingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let G\mathcal GG and H\mathcal HH be finite Abelian groups and ψ\psiψ a homomorphism of G\mathcal GG onto H\mathcal HH with kernel K\mathcal KK, and let g0∈Gg_0\in\mathcal Gg0​∈G with g0∉Kg_0\notin\mathcal Kg0​∈/K. Let (π′,π0)(\pi',\pi_0)(π′,π0​) be a face of the master polyhedron P(H,ψg0)P(\mathcal H,\psi g_0)P(H,ψg0​) with π0>0\pi_0>0π0​>0. Define π\piπ on G+\mathcal G^+G+ by

π(g)=π′(ψg),with π′(0ˉ)=0, so π(g)=0 for g∈K.\pi(g)=\pi'(\psi g),\qquad\text{with }\pi'(\bar 0)=0,\ \text{so }\pi(g)=0\text{ for }g\in\mathcal K .π(g)=π′(ψg),with π′(0ˉ)=0, so π(g)=0 for g∈K.

Then (π,π0)(\pi,\pi_0)(π,π0​) is a face of P(G,g0)P(\mathcal G,g_0)P(G,g0​).

Faces of the master polyhedron of a small group thus produce faces of the master polyhedra of all groups mapping onto it. For example, the face t1≥1t_1\ge 1t1​≥1 of P(G2,(1))P(\mathcal G_2,(1))P(G2​,(1)) lifts through reduction mod 222 to the face t1+0t2+t3+0t4+t5≥1t_1+0t_2+t_3+0t_4+t_5\ge 1t1​+0t2​+t3​+0t4​+t5​≥1 of P(G6,(5))P(\mathcal G_6,(5))P(G6​,(5)) (p. 488). THEOREM 20 gives the converse for faces with a zero coefficient.

Formalization Note The hypothesis π0>0\pi_0>0π0​>0 is added: the page does not state it, and without it the theorem is false under the paper's own definition of face. With G=Z6\mathcal G=\mathbb Z_6G=Z6​, H=Z3\mathcal H=\mathbb Z_3H=Z3​, ψ\psiψ reduction mod 3 and g0=1g_0=1g0​=1, the inequality t(1)≥0t(1)\ge 0t(1)≥0 is a face of P(Z3,(1))P(\mathbb Z_3,(1))P(Z3​,(1)) (THEOREM 16), but its lift t(1)+t(4)≥0t(1)+t(4)\ge 0t(1)+t(4)≥0 is not a face of P(Z6,(1))P(\mathbb Z_6,(1))P(Z6​,(1)): its tight solutions all have t(1)=t(4)=0t(1)=t(4)=0t(1)=t(4)=0 and span only a 3-dimensional subspace of the 4-dimensional hyperplane. The proof's "∣H∣−1|\mathcal H|-1∣H∣−1 independent minimal paths" (p. 487) requires π0>0\pi_0>0π0​>0. Surjectivity is the page's "onto"; g0∉Kg_0\notin\mathcal Kg0​∈/K is written ψg0≠0ˉ\psi g_0\neq\bar 0ψg0​=0ˉ.

Preamble
import Mathlib
import Definitions.Def_Gomory69_Lifting_GroupPolyhedron
import Definitions.Def_Gomory69_Lifting_Lift
Formal statement
namespace Gomory69.Lifting

theorem theorem_19 {G H : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G]
    [AddCommGroup H] [Fintype H] [DecidableEq H]
    (ψ : G →+ H) (hψ : Function.Surjective ψ) (g₀ : G) (hg₀ : ψ g₀ ≠ 0)
    (π' : Plus H → ℝ) (π₀ : ℝ) (hπ₀ : 0 < π₀) (hface : IsFace H (ψ g₀) π' π₀) :
    IsFace G g₀ (liftCoeff ψ π') π₀ := by sorry

end Gomory69.Lifting
Source
Gomory, Some polyhedra related to combinatorial problems, Linear Algebra Appl. 2 (1969), p. 486, THEOREM 19 (proof pp. 486–488)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 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