For a positive integer , let be the permutation group on . The permanent of a matrix of independent variables is . For a complex polynomial in variables, an affine determinant representation of size is an identity with . Its determinantal complexity is the least positive size of such a representation. Its border determinantal complexity is the least positive for which is a coefficientwise limit of determinants of affine-linear matrices of size . An affine-linear algebraic branching program computes the sum of products of affine-linear edge labels along all directed paths from a source to a sink in a finite acyclic graph. The permanent versus determinant problem asks how and grow with .
Mignon and Ressayre proved the characteristic-zero bound . Landsberg, Manivel and Ressayre proved the unrestricted complex border bound .
The preprint proves for every . The preprint also derives a lower bound of for the fixed vertex budget in any coefficientwise approximation of by affine-linear algebraic branching programs.
The Lean library Determinantal formalizes the determinant lower bounds and the coefficient and plane-curve results supporting them. For a nonzero homogeneous complex form of degree in variables, the Lean library proves under the hypothesis that the only common zero of and all its first partial derivatives is the origin. Lean has checked every result of the Lean library, so the Lean library is the reference for these pages. Each page states the Lean library’s result and links to the corresponding declaration. Where the preprint gives a different statement, its statement appears beside the Lean library’s. The preprint serves only as a guide to the order and names of the results.
Determinantal is a Lean library: 30 items, in nine groups. Each has a page written by OctoInform, listed below.
No item matches.