Connectivity of permissible box paths
OpenQAlgorithms.Papers.Independent.Intakenext100.P41.boxPathConnectivityLet , , and . A permissible signature is a weakly decreasing integral -tuple with largest-minus-smallest entry at most . Fix signatures and two length- paths from to , each step adding one box to one row and every intermediate signature permissible. Two paths are adjacent when exactly one interior signature changes. Then
All paths in the chain have the same endpoints and length. Signatures are kept unnormalized until any final common-shift equivalence; at the chain can have length zero.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P41
noncomputable section
open scoped BigOperators
open MeasureTheory Set
namespace QAlgorithms.Papers.Independent.Intakenext100.P41
/-- §32, final combinatorial argument, PDF p.42: paths with the same endpoints
and length are connected by single-intermediate-signature changes. All vertices
are actual permissible signatures, not independently normalized representatives. -/
theorem boxPathConnectivity (N ell k : ℕ) (hN : 2 ≤ N) (hell : 1 ≤ ell)
(hk : 1 ≤ k) (hkN : k ≤ N) (f g : IntegerSignature N)
(P Q : BoxPath ell k f g) :
Relation.ReflTransGen AdjacentPaths P Q := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P41
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For all natural numbers satisfying , , and , all integer vectors indexed by , and all paths from to having steps, the following holds. Here each path has vertices, every vertex satisfies whenever and for every , and each step increases exactly one coordinate by . There exists a finite sequence of such paths from to in which consecutive paths differ at exactly one vertex with index strictly between and , agreeing at every other vertex. The sequence may have zero transitions, in which case . For , adjacency is impossible, so the conclusion requires ; for endpoints admitting no such paths, the universal assertion about is vacuous.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.