FloorSelectorCycles
Abstract
FloorSelectorCycles supplies the width-three bridge max-flow proof.
Formulas retain the Lean parameter types and all hypotheses. HDiv.hDiv and HMod.hMod are displayed infix: on natural and integer carriers they mean the respective Lean integer division and remainder operations; on rational carriers division is field division. Coe.coe denotes the coercion determined by the displayed target type. Finite and dependent-pair constructors omit proof fields, which do not change their values. A dash in a match pattern is an anonymous wildcard. CoeFun.coe and CoeSort.coe retain coercions to functions and types. All dimensions use ℕ, all construction coefficients use ℚ, and max-flow uses ℂ.
Definition 1.1 (jump).
Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.jump (✓ std3).
Source. Repository-derived.
Commentary.
jump is the difference between consecutive ceilings of n*ρ; jump_zero_or_one bounds its values for slopes between zero and one, allowing it to represent selector events.
Theorem 1.2 (jump_zero_or_one).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.jump_zero_or_one (✓ std3). ∎
Source. Repository-derived.
Commentary.
For 0 ≤ ρ ≤ 1, every ceiling increment is zero or one; CyclicResolvent.forward_supported_zero applies this to the input and output slopes in the balanced-cycle recurrence.
Theorem 1.3 (opposite_direction_excess).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.opposite_direction_excess (✓ std3). ∎
Source. Repository-derived.
Commentary.
When ρI ≤ ρO, the input ceiling increments along a forward interval exceed the output increments along a backward interval by at most one; CyclicResolvent.forward_supported_zero uses this as the interval balance inequality.
Theorem 1.4 (jump_one_iff_fin_selector).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.jump_one_iff_fin_selector (✓ std3). ∎
Source. Repository-derived.
Commentary.
For 0 < B ≤ A, a ceiling increment at n in Fin A equals one exactly when n is one of the positions floor(k*A/B) with k in Fin B; CyclicResolvent.forward_supported_zero uses this equivalence to express coordinate support as selector events.
Theorem 1.5 (monodromy_forces_zero).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.monodromy_forces_zero (✓ std3). ∎
Source. Repository-derived.
Commentary.
A rational value fixed by multiplication by μ < 1 must vanish; balanced_cycle_zero applies this after propagating a coordinate around a full period.
Theorem 1.6 (half_pow_lt_one).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.half_pow_lt_one (✓ std3). ∎
Source. Repository-derived.
Commentary.
Every positive power of the rational number 1/2 is strictly below one; tensor_edge_product_lt_one uses this to bound the product of weights around the tensor cycle.
Theorem 1.7 (recurrence_product_bounded).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.recurrence_product_bounded (✓ std3). ∎
Source. Repository-derived.
Commentary.
Iterating a multiplicative recurrence over L steps multiplies the initial value by the product of its L factors; balanced_cycle_zero uses this identity to compare a coordinate with its value one period later.
Theorem 1.8 (balanced_cycle_zero).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.balanced_cycle_zero (✓ std3). ∎
Source. Repository-derived.
Commentary.
Under the displayed recurrence and zero conditions, binary input and output sequences with interval excess at most one and nonpositive full-period excess force every periodic coordinate to vanish when each period product is below one. CyclicResolvent.shifted_recurrence_zero applies this to the supported reservoir equations.
Theorem 1.9 (common_node_product_bound).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.common_node_product_bound (✓ std3). ∎
Source. Repository-derived.
Commentary.
For κ > 0 and positive weights, inserting a factor κ/(κ+1) at output events cannot increase the product of weights; CyclicResolvent.shifted_recurrence_zero uses this to preserve the strict period-product bound.
Definition 1.10 (backward).
Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.backward (✓ std3).
Source. Repository-derived.
Commentary.
backward is the unweighted cyclic shift obtained by rotating the rows of the identity matrix; tensor_mulVec_orbit uses it to decrease the first orbit coordinate by one.
Theorem 1.11 (backward_apply).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.backward_apply (✓ std3). ∎
Source. Repository-derived.
Commentary.
The entry of backward at (i,j) is one exactly when j is the cyclic successor of i and is zero otherwise; tensor_mulVec_orbit uses this entry formula to isolate the preceding orbit position.
Definition 1.12 (forwardHalf).
Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.forwardHalf (✓ std3).
Source. Repository-derived.
Commentary.
forwardHalf is the opposite cyclic shift with weight 1/2 at row zero and weight one elsewhere; tensor_mulVec_orbit uses this weight to describe propagation in the second coordinate.
Theorem 1.13 (forwardHalf_apply).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.forwardHalf_apply (✓ std3). ∎
Source. Repository-derived.
Commentary.
The entry of forwardHalf at (i,j) is nonzero only when j is the cyclic predecessor of i, with weight 1/2 at i=0 and one elsewhere; tensor_mulVec_orbit uses this formula to obtain the factor edge.
Definition 1.14 (rowSelector).
Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.rowSelector (✓ std3).
Source. Repository-derived.
Commentary.
rowSelector samples positions floor(k*A/B) from an A-coordinate vector into B coordinates; CyclicResolvent.input_matrix and output_matrix express the tensor input and output maps using these selectors.
Definition 1.15 (reservoir).
Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.reservoir (✓ std3).
Source. Repository-derived.
Commentary.
reservoir is the identity minus the Kronecker product of the two oppositely directed cyclic shifts; CyclicResolvent.reservoir_isUnit proves its invertibility by propagating its homogeneous equation around each orbit.
Definition 1.16 (schurMap).
Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.schurMap (✓ std3).
Source. Repository-derived.
Commentary.
schurMap restricts κ times the identity plus the inverse reservoir to the selected input and output coordinates; CyclicResolvent.schur_eq_restricted expresses this restriction through coordinate-insertion matrices.
Definition 1.17 (CyclicResolventLemma).
Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.CyclicResolventLemma (✓ std3).
Source. Repository-derived.
Commentary.
CyclicResolventLemma states invertibility of the reservoir and injectivity or surjectivity of schurMap according to the ordering of AD and BG, for positive ordered selector dimensions and κ > 0; CyclicResolvent.cyclic_resolvent_lemma proves these assertions.
Definition 1.18 (index).
Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.index (✓ std3).
Source. Repository-derived.
Commentary.
For a positive modulus N, index maps an integer to its remainder in Fin N; orbit uses it to follow both cyclic coordinates for arbitrary integer steps.
Theorem 1.19 (index_val_int).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.index_val_int (✓ std3). ∎
Source. Repository-derived.
Commentary.
The integer value of index is the integer remainder modulo N; index_nat uses this equality to recover an index already in Fin N.
Theorem 1.20 (index_nat).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.index_nat (✓ std3). ∎
Source. Repository-derived.
Commentary.
Reducing the value of an element of Fin N modulo N returns that element; CyclicResolvent.succ_pred_relation uses this to translate cyclic successor and predecessor equations into integer shifts.
Theorem 1.21 (index_add_multiple).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.index_add_multiple (✓ std3). ∎
Source. Repository-derived.
Commentary.
Adding any integer multiple of N leaves index unchanged; orbit_period applies this in both coordinates to obtain a period of A*G.
Theorem 1.22 (index_add_one).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.index_add_one (✓ std3). ∎
Source. Repository-derived.
Commentary.
Increasing the integer argument of index by one advances its value by one modulo N; tensor_mulVec_orbit uses this to identify the first-coordinate shift.
Theorem 1.23 (index_sub_one).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.index_sub_one (✓ std3). ∎
Source. Repository-derived.
Commentary.
Decreasing the integer argument of index by one gives its cyclic predecessor; tensor_mulVec_orbit uses this to identify the second-coordinate shift.
Definition 1.24 (orbit).
Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.orbit (✓ std3).
Source. Repository-derived.
Commentary.
orbit follows the positions (a-s modulo A,b+s modulo G), with the two coordinates moving in opposite directions; CyclicResolvent.reservoir_mulVec_orbit expresses the reservoir equation along this orbit.
Definition 1.25 (edge).
Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.edge (✓ std3).
Source. Repository-derived.
Commentary.
edge assigns weight 1/2 at positions divisible by G and one at all other positions; tensor_mulVec_orbit identifies it as the coefficient relating successive orbit coordinates.
Theorem 1.26 (orbit_period).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.orbit_period (✓ std3). ∎
Source. Repository-derived.
Commentary.
For positive A and G, shifting the orbit parameter by A*G returns the same pair of coordinates; CyclicResolvent.reservoir_isUnit uses this periodicity to close the homogeneous recurrence.
Theorem 1.27 (edge_pos).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.edge_pos (✓ std3). ∎
Source. Repository-derived.
Commentary.
Every edge weight is strictly positive; CyclicResolvent.forward_supported_zero uses this to satisfy the nonzero propagation condition in the balanced-cycle argument.
Theorem 1.28 (tensor_mulVec_orbit).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.tensor_mulVec_orbit (✓ std3). ∎
Source. Repository-derived.
Commentary.
The Kronecker shift sends the value at an orbit position to edge times the value at the preceding position; CyclicResolvent.reservoir_mulVec_orbit subtracts this contribution from the identity term.
Theorem 1.29 (whole_tensor_excess).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.whole_tensor_excess (✓ std3). ∎
Source. Repository-derived.
Commentary.
Over AG steps with A,G > 0, the difference between the input and output event counts is exactly AD-G*B; CyclicResolvent.forward_supported_zero uses the dimension ordering to make this full-period excess nonpositive.
Theorem 1.30 (jump_index).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.jump_index (✓ std3). ∎
Source. Repository-derived.
Commentary.
For positive A, reducing an integer modulo A does not change the ceiling increment of slope B/A; CyclicResolvent.forward_supported_zero uses this to identify selector events along integer orbit parameters.
Theorem 1.31 (edge_product).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.edge_product (✓ std3). ∎
Source. Repository-derived.
Commentary.
Over M*G consecutive positions with G > 0, the product of edge weights is (1/2)^M, independently of the starting phase; tensor_edge_product_lt_one uses this formula over a tensor period.
Theorem 1.32 (tensor_edge_product_lt_one).
Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.tensor_edge_product_lt_one (✓ std3). ∎
Source. Repository-derived.
Commentary.
For positive A and G, the product of edge weights over A*G consecutive orbit steps is strictly below one; CyclicResolvent.reservoir_isUnit uses this contraction to force its homogeneous kernel to vanish.
References
- Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.CyclicResolventLemma - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.backward - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.backward_apply - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.balanced_cycle_zero - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.common_node_product_bound - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.edge - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.edge_pos - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.edge_product - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.forwardHalf - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.forwardHalf_apply - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.half_pow_lt_one - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.index - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.index_add_multiple - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.index_add_one - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.index_nat - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.index_sub_one - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.index_val_int - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.jump - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.jump_index - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.jump_one_iff_fin_selector - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.jump_zero_or_one - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.monodromy_forces_zero - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.opposite_direction_excess - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.orbit - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.orbit_period - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.recurrence_product_bounded - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.reservoir - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.rowSelector - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.schurMap - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.tensor_edge_product_lt_one - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.tensor_mulVec_orbit - Truth anchor:
D5/S3/Quantum/TensorNetworks/BridgeGraph/FloorSelectorCycles.whole_tensor_excess