Lemma 5.1 — a realization with large integral optimum
ProvedZhangTangLabelCut.LP2.large_integral_optimumFor each real there exist an integer , a real , and an integer , depending only on , with the following property. For every integer and each orientation there is a permutation realization of the Section 4 construction with and . It is a simple connected graph with finite positive LP optimum. Writing for its actual vertex and edge counts,
This is the large-cut witness needed for the integrality-gap theorem, together with its construction and polynomial size control.
Differences from the source:
- generalization: existence of an appropriate Section 4 realization with the Omega lower bound → the same existence within the integral family delta = beta = D, with explicit polynomial size bounds; reason: choosing integer D ≥ 1/(3epsilon) in the nontrivial range proves the original existential claim and retains every epsilon; these are stronger witness specifications, not restrictions on universal graph inputs
- encoding: Omega with a constant depending only on epsilon → D, C and k0 are chosen before k and the realization; reason: makes dependencies uniform
- encoding: undirected construction, with the directed extension in Section 7 → a Boolean orientation quantified over both cases; reason: both source graph orientations are preserved
- encoding: connected construction instances and the usual fractional optimum → simple connected witnesses with a finite strictly positive extended-real LP value; reason: rules out undefined ratios; LP2 has an attained finite optimum and connected instances have value at least one
import Definitions.Def_ZhangTangLabelCut_LP2_FiniteGraph import Definitions.Def_ZhangTangLabelCut_LP2_CoveringLP import Definitions.Def_ZhangTangLabelCut_LP2_LabelCut import Definitions.Def_ZhangTangLabelCut_LP2_Shutter import Definitions.Def_ZhangTangLabelCut_LP2_Configurations
namespace ZhangTangLabelCut.LP2
theorem large_integral_optimum (ε : ℝ) (hε : 0 < ε) :
∃ D : ℕ, 0 < D ∧ ∃ C : ℝ, 0 < C ∧ ∃ k₀ : ℕ, 2 ≤ k₀ ∧
∀ k : ℕ, k₀ ≤ k → ∀ directed : Bool,
∃ σ : Sample k (32 * k ^ (2 * D)) (k ^ D),
let I := shutterInstance k (32 * k ^ (2 * D)) (k ^ D) directed σ
I.Admissible ∧
C * k * (Fintype.card I.graph.V : ℝ) ^ (1 / 3 - ε) ≤ (I.opt : ℝ) ∧
Fintype.card I.graph.V ≤ 48 * k ^ (2 + 3 * D) ∧
Fintype.card I.graph.E ≤ 64 * k ^ (2 + 3 * D) := by sorry
end ZhangTangLabelCut.LP2
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Hypothesis. , with no upper bound on .
Claim. There exist a natural , a real and a natural such that, for every natural and each choice of directed or undirected, some sample yields an instance with the four properties below. The instance has parameters
(natural-number powers).
The instance . assigns a permutation of to each chain with and . The graph is:
- terminals ;
- per chain, junctions , , , and middles ;
- edges for and , one-way if directed and two-way if not;
- labels in : edges through get , and edges through get .
This gives and .
The four properties of .
- Admissible. The graph is simple, at least one simple – path exists, and the LP value is some real . The LP is: minimise over with for each simple – path , where is 's set of labels.
- Large optimum. , where is the minimum number of labels meeting every simple – path, and the power is a real power.
- Vertex bound. .
- Edge bound. .
Degenerate cases:
- Since and , we have , and , so the real power has a positive base.
- Because is unrestricted above, for the exponent is . Then and property 2 asks only or less.
- may depend on . may depend on and on the directed flag.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.