Equation (1.2.4): padded orbit membership equals affine projection of
ProvedGCT.dc_padded_iff_affineFor all , the padded permanent is the determinant of an matrix of homogeneous linear forms in if and only if is an affine linear projection of , i.e. there are affine-linear functions , , with . This is the equivalence
used throughout GCT to pass between Valiant's affine-projection definition of determinantal complexity and the homogeneous orbit picture inside ; the passage is by homogenizing with in one direction and setting in the other.
import Definitions.Def_GCT_determinantal_complexity
namespace GCT
theorem dc_padded_iff_affine (m n : ℕ) (hmn : m ≤ n) :
HasLinearDetRep n (paddedPerm m n) ↔ HasAffineDetRep n (permPoly m) := by sorry
end GCTRead-back
What the Lean code literally says, in plain math · Aristotle (Harmonic)
Provenance note — this read-back is NOT blind and NOT independent. It was written by the same agent that drafted the Lean statement it describes, at the explicit instruction of the human who owns this proposal, and not by a separate auditor with a fresh context. It is therefore self-testimony: any misreading made while drafting the statement may be repeated here. Reviewers should not treat it as independent confirmation that the formalization is faithful to the source.
The statement is phrased in terms of the following notions.
For a natural number , the permanent polynomial is the element of the polynomial ring in commuting indeterminates given by
the sum running over all permutations of the -element index set (for the conventions give ).
A second copy of the permanent is taken in the larger variable set consisting of the variables together with one extra variable ; in that ring the padded permanent of size is
where is truncated natural-number subtraction: if the exponent is and the padded permanent is just .
For a polynomial in any variable set:
- has a linear determinantal representation of size when there exists an matrix of polynomials such that every entry is homogeneous of degree (the zero polynomial counts as homogeneous of degree , so entries may vanish, but nonzero constants are not allowed) and .
- has a border linear determinantal representation of size when there is a sequence , , of matrices all of whose entries are homogeneous of degree , such that for every monomial exponent vector the scalars converge in , as , to . Convergence is required coefficientwise, for each exponent vector separately; no uniformity across exponents is required.
- has an affine determinantal representation of size when there is an matrix of polynomials with for all (constants permitted) and .
Finally,
each the least element of a set of natural numbers. This is a total function: if the set is empty the value is by convention, so every assertion below also speaks about that junk value whenever the relevant set happens to be empty.
Let and be natural numbers with (this hypothesis is assumed; nothing is claimed when ). The assertion is an equivalence of two existential statements:
- There exists an matrix with entries in , each entry homogeneous of degree (possibly zero), such that , the permanent being taken in the variables of that same ring.
- There exists an matrix with entries in — the ring without the variable — each of total degree at most (constants permitted), such that .
Both determinants are the usual signed determinant over a commutative ring. The equivalence is asserted for every such pair , including the degenerate cases (padding exponent ) and (both sides then concern the constant polynomial ).