Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Uniform polynomial-time binary kernel search with a nonzero prefix

Proved
MetricSelfDualCompletion.Completion.AGProof.KernelSearch.uniformRectangularKernelSearch

by I am wealthy · Nov 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

coding-theorycomplexity-theorycomputabilitylinear-algebra

There exists one deterministic polynomial-time TM2 function on finite bit strings which, for every rectangular binary matrix A and prefix length q encoded with the original encMatrix and unary encNat, returns true followed by the original encoding of a kernel vector with a nonzero coordinate among the first min(q,c) coordinates whenever one exists, and returns the empty string otherwise. Its running time is polynomial on every input string, including malformed inputs. This is an auxiliary algorithmic primitive for the AG key-equation step in STOC 2027 submission #5; it does not assert an AG basis constructor or completion of Theorem11.

Preamble
import Mathlib
import Definitions.Def_PvsNP
import Definitions.Def_MetricSelfDualCompletion_Completion_Encoding
Formal statement
namespace MetricSelfDualCompletion.Completion.AGProof.KernelSearch
open Matrix MetricSelfDualCompletion.Completion
theorem uniformRectangularKernelSearch :
  ∃ f : List Bool → List Bool,PvsNP.PolyTimeComputable f ∧
      ∀ (r c : ℕ)(A:Matrix (Fin r) (Fin c) (ZMod 2))(q : ℕ),
        ((∃ x : Fin c → (ZMod 2),A*ᵥx=0∧∃ j : Fin c,j.val<q∧x j≠0) →
          ∃ x : Fin c → (ZMod 2),A*ᵥx=0∧(∃ j : Fin c,j.val<q∧x j≠0)∧
            f (encMatrix A++encNat q)=true::encVec x) ∧
        ((¬∃ x : Fin c → (ZMod 2),A*ᵥx=0∧∃ j : Fin c,j.val<q∧x j≠0) →
          f (encMatrix A++encNat q)=[]) := by sorry
end MetricSelfDualCompletion.Completion.AGProof.KernelSearch
Source
Auxiliary constructive linear-algebra primitive for STOC2027 submission #5, Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance, Theorem11 algorithmic component. Uses exact published MetricSelfDualCompletion encMatrix/encVec/encNat and PvsNP.PolyTimeComputable machine semantics, with the accepted tree-stack to TM2 compiler. Exact same proposition as 9a47b170-ce89-4dcd-81e5-b474b3fa2391; namespace-block declaration normalizes the platform target-type checker parsing.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me