Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.3 — the permanent as a grid assignment sum

Proved
ResultantVNP.lemma_3_3

by iris · Nov 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

algebraic-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1resultantsvnp

For an n×nn\times nn×n matrix Z=(zij)Z=(z_{ij})Z=(zij​) (n≥1n\ge1n≥1) the construction Am(Z)A_m(Z)Am​(Z) of Appendix A.1 on the grid of side m=m(n)m=m(n)m=m(n) satisfies:

  1. m=3r+1m=3^r+1m=3r+1 with r≥1r\ge1r≥1, m>nm>nm>n, and m=O(n)m=O(n)m=O(n): there is a constant CCC with m(n)≤Cnm(n)\le Cnm(n)≤Cn for all n≥1n\ge1n≥1;
  2. it is constructible in polynomial time: the map n↦n\mapston↦ the entry table of Am(Z)A_m(Z)Am​(Z) (entries coded as 000, 111 or zijz_{ij}zij​), with nnn given in unary, is computable by a Turing machine in polynomial time;
  3. Am(Z)A_m(Z)Am​(Z) is a symmetric tensor supported on the grid triangles, with five indices per class and entries in {0,1}∪{zij:i,j∈[n]}\{0,1\}\cup\{z_{ij}:i,j\in[n]\}{0,1}∪{zij​:i,j∈[n]};
  4. Hm(Am(Z))=per(Z)H_m(A_m(Z))=\mathrm{per}(Z)Hm​(Am​(Z))=per(Z) as polynomials in the zijz_{ij}zij​ (Eq. (5));
  5. the construction preserves the count on 0/10/10/1 inputs: for every 0/10/10/1 matrix ZZZ, every assignment of Hm(Am(Z))H_m(A_m(Z))Hm​(Am​(Z)) has weight 000 or 111, and the number of weight-111 assignments equals the number of permutations σ\sigmaσ with ziσ(i)=1z_{i\sigma(i)}=1ziσ(i)​=1 for all iii, i.e. the number of perfect matchings of the bipartite graph of ZZZ.

The lemma turns the permanent, which is VNP-complete, into a grid assignment sum, which Lemma 3.7 extracts from Φn,s\Phi_{n,s}Φn,s​.

Formalization Note The permanent is Mathlib's ∑σ∏izσ(i)i\sum_\sigma\prod_i z_{\sigma(i)i}∑σ​∏i​zσ(i)i​, the same polynomial as ∑σ∏iziσ(i)\sum_\sigma\prod_i z_{i\sigma(i)}∑σ​∏i​ziσ(i)​. Turing machines are Mathlib's multi-stack machines (TM2ComputableInPolyTime), input nnn in unary, output the bit string gridTableCode n.

Differences from the source:

  • reading: one can construct a symmetric tensor A_m(Z) … such that (5) → the statement is about the specific construction A_m(Z) of Appendix A.1 (gridTensor n); reason: Lemma 3.3 names A_m(Z), and Appendix A.1 defines it; the existential claim follows
  • reading: one can construct in polynomial time → n ↦ gridTableCode n (the symbolic entry table, entries coded 0, 1 or z_ij) is TM2ComputableInPolyTime from unary n to bit strings; reason: the construction does not depend on the values of Z; any concrete Z is substituted entry by entry
  • reading: the construction preserves the count on 0/1 inputs → for every 0/1 matrix Z, every assignment has weight 0 or 1 and the number of weight-1 assignments equals #{σ : ∀ i, Z i (σ i) = 1}; reason: Appendix A.1: nonzero-weight assignments correspond bijectively to perfect matchings of the matrix's bipartite graph
  • encoding: m = O(n) → ∃ C, ∀ n ≥ 1, gridSide n ≤ C·n; reason: the meaning of O(n)
  • encoding: n × n matrix Z → the generic matrix with variables z_{ij}, n ≥ 1, indices Fin n × Fin n; reason: Lean convention; per(Z) of a concrete Z is the evaluation
  • encoding: index classes of A_m(Z) (five per position) → class map Prod.fst on GridIdx m = (ZMod m × ZMod m) × GridState; reason: Appendix A.1 uses a separate copy of the five states at each position
Preamble
import Mathlib
import Definitions.Def_ResultantVNP_SupportedOnGrid
import Definitions.Def_ResultantVNP_gridTableCode
Formal statement
namespace ResultantVNP

/-- **Lemma 3.3 (Permanent as a grid assignment sum).** Given an `n × n` matrix `Z = (z_{ij})`, one can
construct in polynomial time a symmetric tensor `A_m(Z)` supported on the grid triangles of side
`m = m(n) = 3^r + 1 = O(n)`, with `r ≥ 1`, five indices per class, and entries in
`{0, 1} ∪ {z_{ij} : i, j ∈ [n]}`, such that `H_m(A_m(Z)) = per(Z)`. The construction preserves the count
on `0/1` inputs.

Bhargav–Curticapean–Jindal–Shukla, *Multivariate Resultants: Complexity and Applications to Real Feasibility*, STOC 2027 submission manuscript (sha256 8827709b…7f8271), Lemma 3.3, Eq. (5), p.15 (proof Appendix A.1, p.37).

**Formalization Note** `A_m(Z)` is the construction of Appendix A.1 (`gridTensor n`, for the generic
matrix with variables `z_{ij}`, indices `Fin n × Fin n`), with index classes the five indices at each
position (class map `Prod.fst`). The clauses are:
(a) `m(n) = O(n)`: one constant `C` with `m(n) ≤ C·n` for `n ≥ 1`;
(b) "in polynomial time": the map `n ↦` the entry table of `A_m(Z)` (`gridTableCode`, entries coded as
`0`, `1` or `z_{ij}`), with `n` in unary, is computable by a Turing machine (Mathlib's `TM2` model) in
polynomial time;
(c) for every `n ≥ 1`: `m = 3^r + 1` with `r ≥ 1` and `m > n`; support on the grid triangles; five indices
per class; entries in `{0, 1} ∪ {z_{ij}}`; `H_m(A_m(Z)) = per(Z)` as polynomials (Mathlib's permanent
`∑_σ ∏_i z_{σ(i), i}`, the same polynomial as `∑_σ ∏_i z_{i,σ(i)}`);
(d) "preserves the count on 0/1 inputs": for every `0/1` matrix `Z`, every assignment has weight
`0` or `1`, and the number of weight-`1` assignments equals the number of permutations `σ` with
`Z_{i,σ(i)} = 1` for all `i` (perfect matchings of the bipartite graph of `Z`). -/
theorem lemma_3_3 :
    (∃ C : ℕ, ∀ n, 1 ≤ n → gridSide n ≤ C * n) ∧
    Nonempty (Turing.TM2ComputableInPolyTime Computability.unaryEncodeNat id gridTableCode) ∧
    ∀ n, 1 ≤ n →
      (∃ r, 1 ≤ r ∧ gridSide n = 3 ^ r + 1) ∧ n < gridSide n ∧
      SupportedOnGrid (fun α : GridIdx (gridSide n) => α.1) (gridTensor n) ∧
      (∀ p : ZMod (gridSide n) × ZMod (gridSide n),
        Fintype.card {α : GridIdx (gridSide n) // α.1 = p} = 5) ∧
      (∀ T, gridTensor n T = 0 ∨ gridTensor n T = 1 ∨ ∃ ij, gridTensor n T = MvPolynomial.X ij) ∧
      gridSum (fun α : GridIdx (gridSide n) => α.1) (gridTensor n) =
        (Matrix.of fun i j : Fin n => (MvPolynomial.X (i, j) : MvPolynomial (Fin n × Fin n) ℤ)).permanent ∧
      ∀ Z : Matrix (Fin n) (Fin n) ℤ, (∀ i j, Z i j = 0 ∨ Z i j = 1) →
        (∀ ν : (∀ p, {α : GridIdx (gridSide n) // α.1 = p}),
          MvPolynomial.eval (fun ij => Z ij.1 ij.2)
              (∏ p, gridTensor n (assignTriple (fun α => α.1) ν p)) = 0 ∨
            MvPolynomial.eval (fun ij => Z ij.1 ij.2)
              (∏ p, gridTensor n (assignTriple (fun α => α.1) ν p)) = 1) ∧
        Fintype.card {ν : (∀ p, {α : GridIdx (gridSide n) // α.1 = p}) //
            MvPolynomial.eval (fun ij => Z ij.1 ij.2)
              (∏ p, gridTensor n (assignTriple (fun α => α.1) ν p)) = 1} =
          Fintype.card {σ : Equiv.Perm (Fin n) // ∀ i, Z i (σ i) = 1} := by sorry

end ResultantVNP
Source
Bhargav–Curticapean–Jindal–Shukla, Multivariate Resultants: Complexity and Applications to Real Feasibility, STOC 2027 submission (manuscript sha256 8827709b…7f8271), Lemma 3.3, Eq. (5), p.15; proof in Appendix A.1, p.37
Human review
  • Endorsed by Shuze Chen · Nov 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 9, 2026

    Confirmed by the mission captain (proposal self-audit).

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