HYPERSURFACES WITH DEGENERATE DUALS AND THE GEOMETRIC COMPLEXITY THEORY PROGRAM

Description

Niveau: Supérieur, Doctorat, Bac+8
HYPERSURFACES WITH DEGENERATE DUALS AND THE GEOMETRIC COMPLEXITY THEORY PROGRAM J.M. LANDSBERG, LAURENT MANIVEL AND NICOLAS RESSAYRE Abstract. We determine set-theoretic defining equations for the variety Dualk,d,N ? P(SdCN ) of hypersurfaces of degree d in CN that have dual variety of dimension at most k. We apply these equations to the Mulmuley-Sohoni variety GLn2 · [detn] ? P(S nCn 2 ), showing it is an irreducible component of the variety of hypersurfaces of degree n in Cn 2 with dual of dimension at most 2n ? 2. We also establish other geometric properties of the Mulmuley-Sohoni variety and prove a quadratic lower bound for the determinental border-complexity of the permanent. 1. Introduction A classical problem in linear algebra is to determine or bound the smallest integer n such that the permanent of an m ?m matrix may be realized as a linear projection of the determinant of an n ? n matrix. L. Valiant [7] proposed using this problem as an algebraic analog of the problem of comparing the complexity classes P and NP. Call this value of n, dc(permm). He conjectured that dc(permm) grows faster than any polynomial in m. The best known lower bound is dc(permm) ≥ m2 2 , which was proved in [3].

• sdw ?


• dual variety


• degenerate duals


• been chosen


• ?1 z


• variety has


• such subspace


• projective automorphisms

Sujets

• Landsberg
• Valiant

Informations

• Publié par: mijec
• Nombre de lectures: 31
• Langue: English

Extrait

HYPERSURFACES WITH DEGENERATE DUALS AND THE GEOMETRIC COMPLEXITY THEORY PROGRAM

J.M. LANDSBERG, LAURENT MANIVEL AND NICOLAS RESSAYRE

d N Abstract.We determine set-theoretic defining equations for the varietyDual k,d,N ⊂P(SC) N of hypersurfaces of degreedinCthat have dual variety of dimension at mostkapply. We 2 n n these equations to the Mulmuley-Sohoni varietyGL n 2 ∙[det n ]⊂P(SC), showing it is an 2 n irreducible component of the variety of hypersurfaces of degreeninCwith dual of dimension at most 2n−2. We also establish other geometric properties of the Mulmuley-Sohoni variety and prove a quadratic lower bound for the determinental border-complexity of the permanent.

1.Introduction A classical problem in linear algebra is to determine or bound the smallest integernsuch that the permanent of anm×mmatrix may be realized as a linear projection of the determinant of ann×nmatrix. L. Valiant [7] proposed using this problem as an algebraic analog of the problem of comparing the complexity classesPandNPthis value of. Call n,dc(perm ). He m conjectured thatdc(perm ) grows faster than any polynomial inm. The best known lower m 2 m bound isdc(perm )≥, which was proved in [3]. m 2 The definition ofdcmay be rephrased as follows: let(perm ) `be a linear coordinate onC, m letC⊕M m (C)⊂M n (C), be any linear inclusion, whereM n (C) denotes the space of complex n−m ) is the smallestnsuch that`perm∈End(M n×nmatrices; thendc(perm m m n (C))∙det n . Hereu∈End(M n (C)) acts by (u∙det n )(M) := det n (u(M)). K. Mulmuley and M. Sohoni [4, 5], have proposed to study the functiondc(perm ), which m n−m is the smallestnsuch that [`perm ] is contained in the orbit closureGL 2 ∙[det n ]⊂ m n n∗ P(S(M n (C)) ). The best known lower bound on this function had been linear. Note that dc(perm )≤dc(perm ), the potential difference being the added flexibility of limiting polyno- m m mials inGL n ∙[det n ] that are not inEnd(M n (C))∙[det n ]. Our main result aboutdc(perm ) is 2 m the following quadratic bound.

2 m Theorem 1.0.1.dc(perm )≥. m 2

n∗ Consider the idealI n of regular functions onS(M n (C) )3det n that are zero onGL 2 ∙[det n ]. n We construct an explicit sub-GL n -moduleV n inI n which has the following properties. 2

Theorem 1.0.2.(1)TheGL n -moduleV n is irreducible of dominant weightn(n−1)(n− 2 2 2)ω 1 + (2n−4n−1)ω 2 + 2ω 2n+1 and its elements have degreen(n−1). (2)The varietyGL n ∙[det n ]is an irreducible component of the zero locusD n ofV n . 2

Date: April 2010. Landsberg supported by NSF grant DMS-0805782. NR supported by the French National Research Agency (ANR-09-JCJC-0102-01). 1