Keyboard shortcuts

Press ← or → to navigate between chapters

Press ? to show this help

Press Esc to hide this help

ReservoirSchur

Abstract

ReservoirSchur 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 (kernelEmbedding).

Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.kernelEmbedding (✓ std3).

Source. Repository-derived.

Commentary.

kernelEmbedding places one alternating anti-diagonal vector in each short-long block and is zero on the other blocks; kernel_coordinates shows that these vectors parametrize the entire same-depth width-two kernel.

Theorem 1.2 (kernelEmbedding_injective).

Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.kernelEmbedding_injective (✓ std3). ∎

Source. Repository-derived.

Commentary.

The anti-diagonal kernel coordinates determine their embedded vector uniquely; kernelEmbedding_range combines this injectivity with the kernel dimension to identify the entire kernel.

Theorem 1.3 (kernel_coordinates).

Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.kernel_coordinates (✓ std3). ∎

Source. Repository-derived.

Commentary.

Every vector annihilated by the same-depth widthTwoMatrix is an image of kernelEmbedding; LongReservoir.single_update_injective uses this parametrization to reduce the added-slice equation to the kernel coordinates.

Definition 1.4 (cokernelEmbedding).

Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.cokernelEmbedding (✓ std3).

Source. Repository-derived.

Commentary.

cokernelEmbedding places transposed alternating anti-diagonal vectors in the long-short output blocks; cokernelMatrix_mul_widthTwo shows that the associated coordinate projection annihilates the width-two matrix.

Theorem 1.5 (kernelMatrix_mulVec).

Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.kernelMatrix_mulVec (✓ std3). ∎

Source. Repository-derived.

Commentary.

Multiplying by the matrix of kernelEmbedding gives the embedded kernel vector; LongReservoir.single_update_injective uses this to apply the kernel sampling identity to its parametrized input.

Theorem 1.6 (cokernelMatrix_mul_widthTwo).

Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.cokernelMatrix_mul_widthTwo (✓ std3). ∎

Source. Repository-derived.

Commentary.

The transpose of the matrix of cokernelEmbedding annihilates widthTwoMatrix; short_reservoir_injective uses this projection to remove the original width-two term from the augmented flow equation.

Definition 1.7 (kernelSample).

Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.kernelSample (✓ std3).

Source. Repository-derived.

Commentary.

kernelSample chooses coordinates zero and p in each short-long input block; kernel_sample_identity shows that sampling at these positions recovers the kernel coefficients.

Definition 1.8 (cokernelSample).

Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.cokernelSample (✓ std3).

Source. Repository-derived.

Commentary.

cokernelSample chooses coordinates p and zero in each long-short output block; cokernel_sample_identity shows that insertion at these positions is a right inverse of the cokernel projection.

Theorem 1.9 (kernel_sample_identity).

Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.kernel_sample_identity (✓ std3). ∎

Source. Repository-derived.

Commentary.

Sampling an embedded anti-diagonal kernel vector returns its coefficient vector; LongReservoir.single_update_injective uses this identity to reduce the added slice to a map on the kernel coefficients.

Theorem 1.10 (cokernel_sample_identity).

Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.cokernel_sample_identity (✓ std3). ∎

Source. Repository-derived.

Commentary.

Inserting a vector at the cokernel sample positions and then applying the cokernel projection returns that vector; LongReservoir.single_update_injective uses this to read the added slice in cokernel coordinates.

Definition 1.11 (singleCross).

Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.singleCross (✓ std3).

Source. Repository-derived.

Commentary.

singleCross inserts the Kronecker map BM⊗DM between the kernel sample positions and the cokernel sample positions; LongReservoir.single_update_injective uses this map to remove the width-two kernel.

Theorem 1.12 (inclusion_prod).

Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.inclusion_prod (✓ std3). ∎

Source. Repository-derived.

Commentary.

Coordinate insertion along a product of two maps is the Kronecker product of their insertion matrices; singleCross_kronecker uses this factorization to express the added matrix as one tensor slice.

Definition 1.13 (shortZeroCol).

Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.shortZeroCol (✓ std3).

Source. Repository-derived.

Commentary.

shortZeroCol selects column zero in each short block; singleThirdLeft uses these columns to read the kernel sample coordinates.

Definition 1.14 (longLastRow).

Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.longLastRow (✓ std3).

Source. Repository-derived.

Commentary.

longLastRow selects row p in each long block; singleThirdLeft uses these rows to insert the transformed coefficients into the cokernel sample positions.

Definition 1.15 (singleThirdLeft).

Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.singleThirdLeft (✓ std3).

Source. Repository-derived.

Commentary.

singleThirdLeft applies BM from the zero columns of the short blocks to the final rows of the long blocks; singleCross_kronecker uses it as the left factor of the third tensor slice.

Definition 1.16 (singleThirdRight).

Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.singleThirdRight (✓ std3).

Source. Repository-derived.

Commentary.

singleThirdRight applies DM from the final rows of the long blocks to the zero columns of the short blocks in the second factor; singleCross_kronecker uses it as the right factor of the third tensor slice.

Theorem 1.17 (singleCross_kronecker).

Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.singleCross_kronecker (✓ std3). ∎

Source. Repository-derived.

Commentary.

The update singleCross is the Kronecker product of singleThirdLeft and singleThirdRight; LongReservoir.single_reversal_injective_witness uses this equality to realize the kernel-removing update as a third bond slice.

Definition 1.18 (localSource).

Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.localSource (✓ std3).

Source. Repository-derived.

Commentary.

localSource restricts the input vector to one pair of shift blocks; widthTwo_mulVec_block uses this restriction to express each block equation as a rectangular pencil equation.

Theorem 1.19 (widthTwo_mulVec_block).

Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.widthTwo_mulVec_block (✓ std3). ∎

Source. Repository-derived.

Commentary.

On any pair of blocks, multiplication by widthTwoMatrix equals pencil multiplication on localSource; sourceSL_kernel_of_updated_zero uses this to isolate the short-long kernel equations.

Definition 1.20 (sourceSL).

Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.sourceSL (✓ std3).

Source. Repository-derived.

Commentary.

sourceSL keeps the short-long input blocks and sets all other blocks to zero; sourceSL_kernelEmbedding shows that this projection fixes every vector in the parametrized kernel.

Definition 1.21 (slLine).

Formalization. D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.slLine (✓ std3).

Source. Repository-derived.

Commentary.

slLine reads the short-long input blocks at the coordinate pair (p-r,p-t); slLine_kernelEmbedding computes this array for an embedded anti-diagonal vector.

Theorem 1.22 (cokernel_mulVec_formula).

Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.cokernel_mulVec_formula (✓ std3). ∎

Source. Repository-derived.

Commentary.

The cokernel projection is the displayed alternating sum along each long-short anti-diagonal; cokernel_reservoir_kernel uses this formula to compute the reservoir contribution in cokernel coordinates.

Theorem 1.23 (slLine_kernelEmbedding).

Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.slLine_kernelEmbedding (✓ std3). ∎

Source. Repository-derived.

Commentary.

For an embedded kernel vector, slLine vanishes unless r+t=p and otherwise equals the coefficient vector multiplied by the displayed sign; cokernel_reservoir_kernel uses this to compute the projected added slice.

Theorem 1.24 (sourceSL_kernelEmbedding).

Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.sourceSL_kernelEmbedding (✓ std3). ∎

Source. Repository-derived.

Commentary.

The short-long block projection fixes every image of kernelEmbedding; short_reservoir_injective uses this identity to recover the full kernel vector from the vanishing short-long component.

Theorem 1.25 (short_short_witness).

Proof. Machine-checked in Lean as D5/S3/Quantum/TensorNetworks/BridgeGraph/ReservoirSchur.short_short_witness (✓ std3). ∎

Source. Repository-derived.

Commentary.

For p > 0, 0 < beta ≤ alpha and 0 < delta ≤ gamma, the short reservoir construction yields rational three-slice matrices attaining the outer cut by eliminating the kernel through its Schur complement. LongReservoir.parameterized_base_witness applies this in the equal-depth case with these multiplicity orderings.

References