§1: canonical basis computation and equality test
OpenQAlgorithms.Papers.Independent.Intakethird100.P03.canonical_basisLet be a full-rank integer column basis. There is a unique matrix generating the same subgroup and satisfying
A single classical polynomial-time procedure maps the signed binary encoding of to that of , with output length polynomial in the actual input length. Another single polynomial-time procedure decides whether two such bases generate the same subgroup. Both procedures work for all dimensions.
Consequently, arbitrary-basis output and canonical-basis output are polynomially equivalent: normalize in one direction and retain the canonical basis in the other.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P03
noncomputable section
open scoped Matrix ComplexConjugate Kronecker
namespace QAlgorithms.Papers.Independent.Intakethird100.P03
open QAlgorithms.Papers.Independent.Renew46.P01 (cleanVector)
attribute [local instance] Classical.propDecidable
/-- PDF p.4: canonicalization, efficient equality testing, and the polynomial equivalence
of arbitrary-basis and canonical-basis output. Runtime is measured in the input's actual bit
length. Polynomial-time computability refers to a halting multi-stack Turing machine. -/
theorem canonical_basis :
∃ (normalize equal : List Bool → List Bool) (p : Polynomial ℕ),
QAlgorithms.Complexity.PolyTimeComputable normalize ∧
QAlgorithms.Complexity.PolyTimeComputable equal ∧
∀ (k : ℕ) (B : Matrix (Fin k) (Fin k) ℤ), IsLatticeBasis B →
IsCanonicalBasis B (canonicalBasis B) ∧
(∀ C, IsCanonicalBasis B C → C = canonicalBasis B) ∧
normalize (encodeBasis B) = encodeBasis (canonicalBasis B) ∧
(encodeBasis (canonicalBasis B)).length ≤ p.eval (encodeBasis B).length ∧
∀ C : Matrix (Fin k) (Fin k) ℤ, IsLatticeBasis C →
equal (encodeBasis B ++ encodeBasis C) =
[decide (columnLattice B = columnLattice C)] := by sorry
end QAlgorithms.Papers.Independent.Intakethird100.P03
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
There exist two functions from finite Boolean lists to finite Boolean lists, both Turing-machine computable in polynomial time with identity input and output encodings, and a polynomial with natural-number coefficients, such that the following holds for every natural number and integer matrix for which is injective on . Write for the matrix chosen by the preceding definition, which chooses a qualifying matrix if one exists and otherwise returns zero. Then has injective multiplication, the same integer column span as , zero entries below the diagonal, positive diagonal entries, and for every ; every matrix with these same properties relative to equals ; ; and . Moreover, for every integer matrix whose multiplication map is injective, is the singleton Boolean list whose bit is true exactly when . Here denotes list concatenation, and encodes followed by the entries of column by column, with increasing row indices within each column. To encode a natural number , list the binary digits of from least significant to most significant, prefixing them by as many true bits as their length and then one false bit; to encode an integer , prepend the bit indicating to the natural-number encoding of . The assertions include . No behavior is prescribed for either function on other inputs.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.