HYPERSURFACES WITH DEGENERATE DUALS AND THE GEOMETRIC COMPLEXITY THEORY PROGRAM

English
11 Pages
Read an excerpt
Gain access to the library to view online
Learn more

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


Subjects

Informations

Published by
Reads 31
Language English
Report a problem
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 varietyDualk,d,NP(SC) N of hypersurfaces of degreedinCthat have dual variety of dimension at mostkapply. We 2 n n these equations to the Mulmuley-Sohoni varietyGLn2[detn]P(SC), showing it is an 2 n irreducible component of the variety of hypersurfaces of degreeninCwith dual of dimension at most 2n2. 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 letCMm(C)Mn(C), be any linear inclusion, whereMn(C) denotes the space of complex nm ) is the smallestnsuch that`permEnd(M n×nmatrices; thendc(permm m n(C))detn. HereuEnd(Mn(C)) acts by (udetn)(M) := detn(u(M)). K. Mulmuley and M. Sohoni [4, 5], have proposed to study the functiondc(perm ), which m nm is the smallestnsuch that [`perm ] is contained in the orbit closureGL2[detn]m n nP(S(Mn(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 inGLn[detn] that are not inEnd(Mn(C))[detn]. Our main result aboutdc(perm ) is 2 m the following quadratic bound.
2 m Theorem 1.0.1.dc(perm ). m 2
nConsider the idealInof regular functions onS(Mn(C) )3detnthat are zero onGL2[detn]. n We construct an explicit sub-GLn-moduleVninInwhich has the following properties. 2
Theorem 1.0.2.(1)TheGLn-moduleVnis irreducible of dominant weightn(n1)(n2 2 2)ω1+ (2n4n1)ω2+ 2ω2n+1and its elements have degreen(n1). (2)The varietyGLn[detn]is an irreducible component of the zero locusDnofVn. 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