Mathematical problems for the next century

MathematicalProblemsfortheNextCentury1SteveSmaleDepartmentofMathematicsCityUniversityofHongKongKowloon,HongKongAugust7,1998SecondVersionIntroduction.V.I.Arnold,onbehalfoftheInternationalMathematicalUnionhaswrittentoanumberofmathematicianswithasuggestionthattheydescribesomegreatproblemsforthenextcentury.Thisreportismyresponse.Arnold’sinvitationisinspiredinpartbyHilbert’slistof1900(seee.g.(Browder,1976))andIhaveusedthatlisttohelpdesignthisessay.Ihavelisted18problems,chosenwiththesecriteria:1.Simplestatement.Alsopreferablymathematicallyprecise,andbestevenwithayesornoanswer.2.Personalacquaintancewiththeproblem.Ihavenotfounditeasy.3.Abeliefthatthequestion,itssolution,partialresultsorevenattemptsatitssolutionarelikelytohavegreatimportanceformathematicsanditsdevelopmentinthenextcentury.Someoftheseproblemsarewellknown.Infact,includedarewhatIbelievetobethethreegreatestopenproblemsofmathematics:theRiemannHypothesis,Poincar´eConjecture,and“DoesP=NP?”BesidestheRiemannHypothesis,onebelowisonHilbert’slist(Hilbert’s1LecturegivenontheoccasionofArnold’s60thbirthdayattheFieldsInstitute,Toronto,June1997.OriginalversionappearedintheMathematicalIntelligencerVol20,(Spring1998)pp7-15116thProblem).Thereisacertainoverlapwithmyearlierpaper“Dynamicsretrospective,greatproblems,attemptsthatfailed”(Smale,1991).Letusbegin.Problem1:TheRiemannHypothesis.ArethosezerosoftheRiemannzetafunction,definedbyanalyticcontinuationfromζ(s)=∞Xn=11ns,Re(s)1whichareinthecriticalstrip0≤Re(s)≤1,allonthelineRe(s)=12?Thiswasproblem#8onHilbert’slist.TherearemanyfinebooksonthezetafunctionandtheRiemannhypothesiswhichareeasytolocate.Ileavethematteratthis.Problem2:ThePoincar´eConjecture.Supposethatacompactconnected3-dimensionalmanifoldhasthepropertythateverycircleinitcanbedeformedtoapoint.Thenmustitbehomeomorphictothe3-sphere?Then-sphereisthespace{x∈Rn+1|kxk=1},kxk2=n+1Xi=1x2i.Acompactn-dimensionalmanifoldcanbethoughtofasaclosedboundedn-dimensionalsurface(differentiableandnon-singular)insomeEuclideanspace.Then-dimensionalPoincar´econjectureassertsthatacompactn-dimensionalmanifoldMhavingthepropertythateverymapf:Sk→M,kn(orequivalently,k≤n/2)canbedeformedtoapoint,mustbehomeomorphictoSn.HenriPoincar´estudiedtheseproblemsinhispioneeringpapersintopology.Poincar´ein1900(seePoincar´e,1953,pp338–370)announcedaproofofthegeneraln-dimensionalcase.Subsequently(in1904)hefoundacounter-exampletohisfirstversionofthestatement(Poincar´e1953,pp435–498).Inthesecondpaperhelimitshimselfton=3,andstatesthe3-dimensionalcaseastheproblemabove(notactuallyasa“conjecture”).Myownrelationshipwiththisproblemisdescribedinthestory(Smale,1990a).ThereIwrote2IfirstheardofthePoincar´econjecturein1955inAnnArboratthetimeIwaswritingathesisonaproblemoftopology.Justashorttimelater,IfeltthatIhadfoundaproof(3dimensions).HansSamelsonwasinhisoffice,andveryexcitedlyIsketchedmyideastohim....Afterleavingtheoffice,Irealizedthatmy“proof”hadn’tusedanyhypothesisonthe3-manifold.In1960,“onthebeachesofRio”,Igaveanaffirmativeanswertothen-dimensionalPoincar´econjectureforn4.In1982,MikeFreedmangaveanaffirmativeanswerforn=4.(Note:forn4,IprovedthestrongerresultthatMwasthesmoothunionoftwoballs,M=Dn∪Dn;thatresultisunprovedforn=4,today.)Forbackgroundonthesematters,besidestheabovereferences,see(Smale,1963).ManyothermathematiciansafterPoincar´ehaveclaimedproofsofthe3-dimensionalcase.See(Taubes,1987)foranaccountofsomeoftheseattempts.AreasonthatPoincar´e’sconjectureisfundamentalinthehistoryofmathematicsisthatithelpedgivefocustoamanifoldasanobjectofstudyinitsownright.Inthisway,Poincar´einfluencedmuchof20thcenturymathematicswithitsattentiontogeometricobjectsincludingeventuallyalgebraicvarieties,Riemannianmanifolds,etc.Iholdtheconvictionthatthereisacomparablephenomenontodayinthenotionofa“polynomialtimealgorithm”.Algorithmsarebecomingworthyofanalysisintheirownright,notmerelyasameanstosolveotherproblems.ThusIamsuggestingthatasthestudyofthesetofsolutionsofanequation(e.g.amanifold)playedsuchanimportantrolein20thcenturymathematics,thestudyoffindingthesolutions(e.g.analgorithm)mayplayanequallyimportantroleinthenextcentury.Problem3:DoesP=NP?Isometimesconsiderthisproblemasagifttomathematicsfromcomputerscience.Itmaybeusefultoputitintoaformwhichlooksmoreliketraditionalmathematics.TowardsthisendfirstconsidertheHilbertNullstellensatzoverthecomplexnumbers.Thusletf1,...,fkbecomplexpolynomialsinnvariables;weareaskedtodecideiftheyhaveacommonzeroζ∈Cn.TheNullstellensatzassertsthatthisisnotthecaseifandonlyiftherearecomplexpolynomialsg1,...,gkinnvariablessatisfyingkX1gifi=1(1)asanidentityofpolynomials.3TheeffectiveNullstellensatzasestablishedbyBrownawell(1987)andothers,statesthatin(1),thedegreesofthegimaybeassumedtosatisfydeggi≤max(3,D)n,D=maxdegfi.Withthisdegreeboundthedecidabilityproblembecomesoneoflinearalgebra.Giventhecoefficientsofthefionecancheckif(1)hasasolutionwhoseunknownsarethecoefficientsofthegi.ThusonehasanalgorithmtodecidetheNullstellensatz.Thenumberofarithmeticstepsrequiredgrowsexponentiallyinthenumberofcoefficientsofthefi(theinputsize).Conjecture(overC).There