performeduserinit

A.
HowtoGetStartedwithCoCoANokeyboardpresent.
HitF1tocontinue.
(DOSErrorMessage)A.
1GettingCoCoAThecomputeralgebrasystemCoCoAisavailablefreeofchargeviatheinter-net.
YoumaydownloaditfromtheWWWpageftp://cocoa.
dima.
unige.
it/cocoa/index.
htmlChoosethelecorrespondingtoyourmachineandoperatingsystem,anddonotforgettogetacopyofthemanualfromthedirectory/doc.
Thendecompresstheleendingin.
zip,or.
tgz,or.
hqx.
Dependingonyoursystem,youwillhavetouseacommandlikeunziportar-zxvf,orthegraphicalinterfaceofadecompressiontoollikeWinzip.
Asaresultyoushouldhaveanappropriatelynameddirectoryorfolder,forinstance/usr/local/cocoa/,whichcontainstheexecutableleoftheprogram(calledcocoaorcocoa.
exe),alenameduserinit.
coc,andasubdirectorycalledlib.
If,instead,youndhundredsoflesinyourfolder,youforgottouncompressinsuchawaythatallpathsarerestored!
A.
2StartingCoCoANowletustrytheprogram.
Youcanstartitbysimplytypingcocoawhileyouareinthefoldercontainingtheexecutablele.
Or,ifyouhaveagraphicaloperatingsystem,youcanalsoclickonitsicon.
Andifthereisnoicon,createalinkorshortcuttotheexecutablelerst.
ThenthecurrentversionofCoCoAstartsupanddisplaysascreenlike276A.
HowtoGetStartedwithCoCoA--Version:4.
7----OnlineHelp:typeorkeyword----Website:http://cocoa.
dima.
unige.
it----ThecurrentringisR::=Q[x,y,z];Belowweshallexplainhowyoucanentercommandsbygoingwithyouthroughasamplesession.
Butrst,letusshowyouhowyoucanexittheprogram.
SimplytypeQuit;hit,andthat'sit!
Ormaybenot.
IfyouareusingthegraphicalinterfaceofCoCoAunderUnixorWindows,youcaneithersendalinetoCoCoAbytypingattheendoftheline,oryoucanselectalineoragroupoflinesandsendittoCoCoAusing.
AndifyouareusingCoCoAonMacintosh,youshouldmakesureyouhitthekey,nottheonemarked.
Andif,byanychance,youareinamediterraneanmood,youcanalsoleaveCoCoAwithacordialCiao;A.
3UsingCoCoAInteractivelyInfact,whenyoutypedQuit;above,youenteredyourrstCoCoAcommand.
ACoCoAcommandhastwonotablefeatures:itstartswithacapitalletter,anditendswithasemicolon.
Ifyouwanttodeneanewobject,youhavetogiveitanamestartingwithacapitalletter.
Thenyoucanassignitavaluebyusing:=asinthefollowingexample.
F:=x^2+y^2-1;ThiscommanddenesanewpolynomialFinthecurrentringwhichhasthevaluex2+y21.
(Wewillbetalkingaboutringslater,butforthemomentweassumethatyoujuststartedCoCoAandthatthecurrentringisthedefaultringR=Q[x,y,z].
)ThevalueofthenewpolynomialFisx^2+y^2-1.
Asyoucansee,theindeterminatesofapolynomialringinCoCoAhavelower-caselettersasnamesandareraisedtopowersusingthe^key.
SometimestheyA.
HowtoGetStartedwithCoCoA277carryindiceslikex[1],x[2],x[3].
AllothernamesofobjectsandfunctionsinCoCoAstartwithacapitalletter.
NowletusprintoutthevalueofourpolynomialF.
ForthiswecouldtypePrint(F);orsimplyF;ThenCoCoAanswersx^2+y^2-1Wecouldalsoperformsomecalculationbeforetypingitsresult,e.
g.
F^2-F+1;yieldstheoutputx^4+2x^2y^2+y^4-3x^2-3y^2+3Nextweapplyoneofthebuilt-inCoCoAfunctions.
Factor(F-2xy+1);CoCoAreplies[[x-y,2]]whichmeansF2xy+1=(xy)2.
A.
4GettingHelpAmomentagowesawanexampleoftheuseoftheCoCoAfunctionFactor().
Ifyouwanttoknowmoreaboutthisfunction,typeMan('Factor');andCoCoAwilldisplaythepageofitson-linemanualdescribingthefunctionFactor().
Inthiscase,youmayeventypeMan('fac');SincefacisnotthenameofaCoCoAcommand,CoCoAlooksforalltopicsinitson-linemanualcontainingthatstring.
Formoreextensiveinformationabouthowtousethemanual,typeMan();278A.
HowtoGetStartedwithCoCoAAfterthat,yougetalistofpossiblecommandsforgettinghelp.
Forinstance,H.
Toc();willgiveyouthetableofcontentsoftheonlinemanual,H.
Tips();willgiveyoutipsforusingtheonlinemanual,andH.
Commands('Topic');summarizesallcommandsassociatedwith'Topic'(thequotesareneededtomarkastring).
ThereareseveralotherwaystoaccesstheCoCoAmanual.
Inthedirectorydocontheftp-servermentionedinSectionA.
1youwillndanhtml-versionforreadingwithaninternetbrowser,andapostscript-versionforprinting.
Finally,ifyouusethegraphicalinterfaceofCoCoAunderWindows,youcanalsoaccessthemanualthroughtheWindowshelpsystem.
SincethisintroductiontoCoCoAhastobelimitedinspaceandscope,westronglyurgeyoutolookupallthetopicswediscussinthemanual.
Thereyouwillndmoreextensiveandmoredetailedinformation.
Moreover,thereisasectionofthemanualcalled"Tutorial"whichcomplementstheseappendicesandshouldbestudiedaswell.
A.
5DataTypesLetusgetbacktoourexamplesession.
Supposewenowwanttodeneapolynomialideal.
Usingthemanual,wendthatthecorrectcommandisIdeal()andwecantypeI:=Ideal(F,x-y);J:=Ideal(x,y,z)^2;Intersection(I,J);CoCoAwillnotreplytothersttwolines,sincetheyareassignments.
ButitreactstothelastlinebyprintingIdeal(xz-yz,xy-y^2,y^2z^2-1/2z^2,y^3z-1/2yz,y^4-1/2y^2,x^2-y^2)whichmeansthattheintersectionoftheidealsIandJhasbeencomputed.
SometimesitmaybeadvisabletousethecommandSetIndentation;be-foretypingoutalistoranideal.
Inourcase,we'dgetIdeal(xz-yz,xy-y^2,y^2z^2-1/2z^2,y^3z-1/2yz,y^4-1/2y^2,x^2-y^2)A.
HowtoGetStartedwithCoCoA279Naturally,thisbehaviourcanbereversedbyenteringUnsetIndentation;ManyCoCoAobjectslikepolynomials,ideals,andmodulesaredenedoverabasering.
ThecommandCurrentRing();tellsyouthevalueofthecurrentring.
E.
g.
inourexamplesessionwewouldgettheanswerQ[x,y,z].
AnewringcanbedenedbyacommandlikeUseS::=Z/(5)[x,y,z];Here::=istheinstructiontocreateanewring,Sisitsname,Z/(5)isitseldofcoecients,andx,y,zareitsindeterminates.
AfteryouhavedenedthenewringS,youarealsomakingitthecurrentbaseringbyinvokingthecommandUse;YoucanswitchbacktoyourinitialringwiththecommandUseR;andifyoutypeRingEnvs();yougetalistofallthebaseringsdenedsofar.
Wheneveryoucreateanewpolynomial,ideal,ormodule,itisdenedoverthecurrentring.
Toseealistofallobjectsintheworkingmemory,youcantypeMemory();andtoseealsothevaluesofthoseobjectsyoucanuseDescribeMemory();Atthispointyoumaygetalistofdescriptionsofobjectsofdierenttypes.
SomeofthemostcommondatatypesinCoCoAareINT,RATarbitrarilylargeintegersresp.
rationalnumbersZMODelementsofaniteeldZ/(p)wherepisaprimenumberPOLYpolynomialsIDEALpolynomialidealsRINGpolynomialringsVECTORvectorswhoseentriesarepolynomialsMODULEsubmodulesofnitefreemodulesoverpolynomialringsLISTListsofobjectsoftheform[Object1,Object2,Object3]MATmatricesofpolynomialsSTRINGstrings(sequencesofcharacters)BOOLBooleanvariables(i.
e.
theirvalueiseitherTRUEorFALSE)InCoCoA,youusuallydonothavetospecifythedatatypesoftheobjectsyoucreate.
Mostsensibledatatypeconversionsaredoneautomatically.
ThecommandType(Object)displaysthedatatypeofanObject.
Ifnecessary,youcanalsoforcetypeconversionsusingCast()e.
g.
L:=[x,y,z];Type(L);showsthatLisoftypeLIST,whereasCast(L,IDEAL);leadstotheanswerIdeal(x,y,z)280A.
HowtoGetStartedwithCoCoAForspecialtypeconversions,therearefrequentlyindividualcommands,e.
g.
theaboveconversioncouldhavebeendonebytypingI:=Ideal(L);ThentheidealIcanbeconvertedbacktoalistbyusingGens(I);whichbringsustoournexttopic:WhatisalistA.
6ListsInCoCoA,alistisasequenceofobjects,separatedbycommasandenclosedinsquarebrackets.
ListsareverycommonandusefulobjectsinCoCoA.
Exam-plesoflistsareforinstance[1,2,3]and[x,y,z].
Thedierentcomponentsofalistdonotnecessarilyhavetohavethesamedatatype,e.
g.
asinthelist[1,TRUE,x].
GivenalistL:=[x,y,z];youcanaccessitssecondcomponentbytypingL[2];whichyieldstheresulty.
AnotherwaytoachievethesameresultistotypeComp(L,2);ThisisespeciallyconvenientifthelistLisnotdirectlygivenbyitsnamebuttheresultofsomeotherevaluation,e.
g.
asinComp(Gens(I),1);whereIisanideal.
Besideslistingalltheelements,thereareotherwaystocreatealist.
TwosimpleonesaretherangeoperatorandtheCartesianproduct.
TherangeoperatorN.
.
McreatesthelistofallintegersbetweenNandM.
Forinstance,1.
.
5;createsthelist[1,2,3,4,5]Therangeoperatorcanalsocreatealistofindeterminatesofthecurrentring(inthecurrenttermordering),e.
g.
ifthecurrentringisQ[x,y,z],thenx.
.
zcreatesthelist[x,y,z],andifthecurrentringisQ[x[1.
.
8]],thenx[1].
.
x[4]createsthelist[x[1],x[2],x[3],x[4]].
TheCartesianproductoftwolistsisthelistofallpairs,e.
g.
theproduct[1,2,3]>EndDefine;HereFunctionNameisthenamebywhichyoulaterwanttocallyourfunction,Argumentsisthe(possiblyempty)listofargumentsittakes,anddenotesagroupofCoCoAcommands.
Letuslookatanexample.
Wewanttowriteafunctionwhichcomputestheidealgeneratedbythepthpowersofthegeneratorsagivenideal,wheretheprimenumberpisthecharacteristicofthebaseeld.
DefineFrobenius(I)P:=Characteristic();L:=Gens(I);ForN:=1ToLen(L)DoL[N]:=L[N]^P;EndFor;ReturnIdeal(L);EndDefine;NotethatinordertoenterthisfunctiondenitiononaversionofCoCoAhavingagraphicalinterface,youshouldhighlightalllinesusingthemouse284B.
HowtoProgramCoCoAandthenevaluatethisselection.
Afterwardswecanuseournewfunctionlikeanybuilt-inCoCoAfunction.
Forinstance,wecantypeUseS::=Z/(5)[x,y,z];I:=Ideal(xy,yz,x-y);Frobenius(I);andwegettheanswerIdeal(x^5y^5,y^5z^5,x^5-y^5)Aftertheexecutionofthisfunction,youroriginalidealIisunchanged,al-thoughithasbeentamperedwithinsidethefunction!
ThereasonforthisisthattheidealIinsidethefunctionFrobenius(I)isjusta"local"ob-jecttowhichCoCoApassedthevalueofyouroriginalidealI.
Instead,ifyouwantthefunctiontooperatedirectlyontheoriginalideal,youshouldtypeDefineFrobenius(VarI)intherstlineofthefunctiondenition.
B.
2ProgramDevelopmentAssoonasyoustarttowriteCoCoAfunctionsmorefrequently,youwillfeeltheneedtodevelopsometechniquesfordoingthis.
Sincetheavailablemethodsvaryconsiderablyfromoneoperatingsystemtoanother,andsincealmosteveryCoCoAprogrammerhashisownfavouriteprocedures,weshallrestrictourselvestopointingoutthemostcommonways.
ManyCoCoAusersworkwithatext-basedCoCoAinterfaceinsideagraph-icaloperatingsystemenvironment,e.
g.
insideX-WindowsorWindows.
Inthiscasewerecommendthe"CopyandPaste"techniqueforcreatingCoCoAfunctions:Opentwowindows,oneforCoCoAandoneforatexteditor.
TheeditorshouldbeabletosavepureASCIIles.
CreatetheCoCoAfunctioninsidetheeditor.
Use"Copy"and"Paste"totransferthedenitiontoCoCoA,sothatCoCoAcancheckitforsyntaxerrors.
Repeatthepreviousstepsuntiltheprogramiscorrect.
Thenyoucansaveitusingtheeditorinalewhoselenameextensioniscustomarilytakentobe.
coc.
AnotherpossibilityforUnixusersistorunCoCoAinashellofasuitableeditorprogramlikeEmacs.
(SomeusefullesfordoingthisareontheCoCoAwebsite.
)Ifyourunatext-basedversionofCoCoAunderatext-basedoper-atingsystemlikeDOS,youwillhavetoreverttoamoreprimitivetechnique:B.
HowtoProgramCoCoA285Createthefunctionusingatexteditorandsaveitinale,e.
g.
inmyfile.
coc.
Modifytheleuserinit.
coctoincludeasourcecommandwhichreadsyourleatstartup,i.
e.
includetheline+.
Whenyouarecontentwithyourfunction,youcanthensaveittoale.
Anddon'tforgettowritesomedocumentationforyourfunctions,orelseyouwillsoonbeunabletoreusethem!
B.
3InputandOutputInSectionB.
1wesawanexampleofhowaCoCoAfunctioncanpasstheresultofitscomputationsbacktothesystem.
ThecommandReturn;exitsthefunctionandreturnsthevalueoftotheplacefromwherethefunctionwascalled.
PassingobjectstoaCoCoAfunctionisobviouslyachievedthroughitsargumentorlistofarguments.
Noticethatthenamewhichyougivetoafunctionargumentinthefunctiondenitiondoesnothavetoagreewiththenameoftheobjectonwhichyoucallthefunction.
Moreover,theargumentnameinthefunctiondenitiondenotesavariableforwhichyoudonothavetospecifyadatatypeandwhichislocaltothefunction,i.
e.
itmayagreewiththenameofanobjectelsewhereanditwillbedeletedafterthefunctionhasbeenexecuted.
Finally,itisimportanttorememberthatobjectsoutsidetheCoCoAfunctionwhicharenotpassedtoitthroughthelistofargumentsarenotknowninsidethefunction.
Forinstance,ifwehaveI:=Ideal(x^2,y^2);DefineIdealSquare(J)I:=J^2;ReturnI;EndDefine;286B.
HowtoProgramCoCoAthentheidealI:=Ideal(x^2,y^2);isnotdestroyedorchangedduringtheexecutionofIdealSquare(Ideal(z));andwecancallIdealSquare(I);withoutgettingintotrouble.
AnotherwayofobtainingfeedbackfromaCoCoAfunction,forinstanceduringitsexecution,istohaveitwriteoutputonthescreen.
ThiscanbeachievedbyusingthecommandsPrint,.
.
.
,;PrintLn,.
.
.
,;Therstcommandisusedtoprintasequenceofobjectstothescreen,andthesecondonedoesthesamethingbutaddsalinebreakafterwards.
Forexample,toprintoutthevalueofF:=x^2+y^2-1,wecouldwritePrint'ThevalueofFisF=',F;ThevalueofFisF=x^2+y^2-1Finally,usingCoCoAyoucanalsowritedatatolesandreadthemagain.
WehavealreadymentionedthesourcecommandEndFor;HereIisthenameofanintegervariablewhichisinitiallyone,isincreasedbyoneeachtimethehavebeenexecuted,andisN(oranexpressionhavinganintegervalue)whentheloopends.
Forinstance,thefollowingfunctioncreatesarandomvectoroverthebaseeldwhoselengthisthenumberofindeterminatesofthebasering.
DefineRandomVector()N:=NumIndets();L:=NewList(N);ForI:=1ToNDoB.
HowtoProgramCoCoA287L[I]:=Rand();EndFor;ReturnVector(L);EndDefine;AnotherwaytocreatealoopisprovidedbythecommandForEachMInLDoEndForEach;whereMisanobjectnamewhichyoucanchooseandLisalist.
Heretheareexecutedforeachelementofthelist(whoseelementsareexaminedintheobviousorder),andduringthatexecutiontheelementisthevalueofthe"read-only"objectM.
ThisloopconstructionisparticularlyusefulifyoudonotknowbeforehandhowmanyelementsLisgoingtohave,i.
e.
howoftenthehavetobeperformed.
Forexample,thefunctionDefineTermProduct(D)L:=Support(DensePoly(D));Result:=1;ForEachMInLDoResult:=Result*M;EndForEach;ReturnResult;EndDefine;computestheproductofalltermsofdegreeDinthecurrentring.
Evenmorecommonisthesituationthataloophastoberepeateduntilacertainlogicalconditionissatised.
ThiscanbeachievedbyusingWhileDoEndWhile;HeretheissomeexpressionwhichevaluatestoaBooleanvalue.
IfthisBooleanvalueisTRUE,thentheareexe-cuted,otherwisetheloopends.
Forinstance,thefollowingexamplecomputesthelargestpoweroftwodividingagivennaturalnumber.
DefineMaxPower(N)I:=1;WhileMod(N,2)=0DoI:=I*2;N:=N/2;EndWhile;ReturnI;EndDefine;288B.
HowtoProgramCoCoAFinally,CoCoAalsoprovidesmethodsforexecutingonesequenceofcom-mandsoranother,dependingonthevalueofsomelogicalcondition.
ThetwomostfrequentlyusedmethodsareIfThenEndIf;IfThenElseEndIf;Intherstcase,theareexecutedonlyifevaluatestoTRUE.
Otherwisetheyareskippedandprogramexecutioncontin-uesaftertheEndIf;Inthesecondcase,thecommandsareexecutediftheisTRUE,andthecommandsareexe-cutedifitisFALSE.
Forinstance,thefunctionDefineMaxOdd(N)IfMod(N,2)=1ThenReturnN;ElseM:=MaxPower(N)EndIf;ReturnN/M;EndDefine;computesthelargestodddivisorofanaturalnumberN.
NoticethatthecommandReturnN;leadstoanimmediateterminationofthisfunctionifitisencountered.
Shouldthesehintsbenotsucienttosolveyourspecicprogramowcontrolproblem,orshouldyouintendtogetthe"CoCoAbug",weinviteyoutostudytheCoCoAmanualwhichcontainsseveralmorepossibilitiesandahostofexamples.
B.
5ListConstructionsThecreatorsofCoCoAspentalotofeorttomakethesystemasuser-friendlyaspossible.
Inparticular,CoCoAallowsyoudenelistsofobjectsinwayswhichareverysimilartotheusualmathematicaldenitionofsetsinbooksorontheblackboard.
Thislistconstructioncantakeanumberofdierentforms,themostimportantofwhichare[|XIn][|XInAnd][XIn|]Intherstform,isaCoCoAexpressionwhichusuallydependsonthevariableXandevaluatestoaCoCoAobject.
ThusthisformconstructsthelistofallsuchobjectssuchthatXisanelementofthe.
Thesecondformdoesessentiallythesamething,exceptthatonlythoseelementsXofareusedtoconstructobjectsforwhichtheB.
HowtoProgramCoCoA289evaluatestoTRUE.
ThethirdformcreatesthesublistofconsistingofallofitselementsXforwhichtheisTRUE.
Letusseesomeexamplesoflistconstructions.
TherstfunctionreturnsalistofNrandomlinearformsinthecurrentring,whereNisaspeciednaturalnumber.
DefineRandomLinear(N)L:=[Randomized(DensePoly(1))|IIn1.
.
N];ReturnL;EndDefine;NoticethatinthiscaseIisnotusedinthedenitionofthecreatedlistelements,andobservetheuseoftherangeoperator1.
.
Nwhichgeneratesthelist[1,2,3,.
.
.
,N].
AnexampleforthesecondformoflistconstructionsisDefineEvenIntegers(N)L:=[I|IIn1.
.
NAndMod(I,2)=0];ReturnL;EndDefine;afunctionwhichreturnsthelistofevenintegersbetween1andN.
Finally,thefunctionDefineIrrePolys(L)Irre:=[FInL|Len(Factor(F))=1];Irre:=[FInIrre|Comp(Factor(F),1,2)=1];ReturnIrreEndDefine;computesthesublistofagivenlistofmonicpolynomialsconsistingoftheirreducibleones.
Maybeyouhavealsonoticedthatinthisexampleprogramwehaveacommandwhichdoesnotendinasemicolon,apparentlycontradictingwhatwesaidinAppendixA.
Withoutfallingintotheabyssofcomputerjargon,letusjustsaythatyoucandropthesemicolonifitimmediatelyprecedestheEnd;ofsomecommand.
B.
6RecursiveProgrammingNextweshowyoutheperfectwayforcreatingCoCoAprogramswhichrunintoaninniteloop.
Moreseriously,CoCoAallowsafunctiontocallitself.
Ofcourse,ifyouusethisfeatureyouhavetomakesurethattheprocesstermi-nateseventually.
Forexample,acompactimplementationofthecomputationofthefactorialofanaturalnumberis290B.
HowtoProgramCoCoADefineFactorial(N)IfN=0ThenReturn1;ElseReturnN*Factorial(N-1);EndIf;EndDefine;InthisexamplenitenessisachievedbycheckingwhetherN=0beforetherecursivefunctioncallwhichappliestoasmallerintegerN-1.
Clearly,recur-sivefunctioncallsarebothpowerfulanddangerous.
Letusgiveonemoreexample.
Thefollowingfunctionrecursivelycomputesthenondecreasinglistofprimefactorsofanaturalnumber.
DefineFactorList(N)IfN=1ThenReturn[];EndIf;I:=2;WhileMod(N,I)0DoI:=I+1;EndWhile;L:=FactorList(N/I);ReturnConcat([I],L);EndDefine;Andnowotoyourownexperiments!
B.
7ImprovingYourProgramsToendourwhirlwindtourofCoCoA,letusshowyousomewaystoimproveandmanageyourCoCoAprograms.
ThecommandSetTimer;turnsonanautomatictimingmechanism.
Everytimeyouenteracommand,CoCoAdisplaystheCPUtimethatwasconsumedforitsexecution,e.
g.
SetTimer;Factor(x^233-3x^223+x^222-7x^12+x^11+21x^2-10x+1);[[x^11-3x+1,1],[x^222-7x+1,1]]Cputime=1.
81,Usertime=1Youcanusethisfeaturetotestvariousversionsofyourprogramsandopti-mizethemforfastestperformance.
Ifyougetsickofthosetimingmessages,B.
HowtoProgramCoCoA291youcanturnthemoagainbytyping(guesswhat)UnsetTimer;Totimeasinglecommand,youcanalsouseTime;Forinstance,abovewecouldhavewrittenTimeL:=Factor(x^233-3x^223+x^222-7x^12+x^11+21x^2-10x+1);Afterawhile,youwillhaveanumberofCoCoAfunctions,andifyoudonotusethemregularly,youwillforgettheirexactnames,syntax,etc.
Tondtheirnamesagainafteryouloadedthelecontainingthem,youcanusetheCoCoAcommandStarting();ItdisplaysalistofthenamesofallCoCoAfunctionsstartingwith,includingyouowncreations.
Donotforgettoenclosethestringinquotes,though!
Andifyouhaveahardtimerememberingthesyntaxofthefunctionsyouwrote,wesuggestthatyouwriteahelpfunctionforeachofthem.
IfthefunctioniscalledMyFunction(),youshouldcreateanewfunctionlikeDefineHelp_MyFunction()EndDefine;ThenthisfunctionisexecutedeverytimeyoutypeHelp('MyFunction');Ofcourse,theitcontainswillusuallybecommandstoprintsomehelptext.
Afteranotherlongwhile,youwillhavesomanyCoCoAfunctionsthatitbecomesdiculttokeeptrackofalltheirnames,etc.
Ifyoucomethisfar,youcangetoutoftroublebycollectingyourfunctionsinpackages.
ACoCoApackageisalecontainingalotofCoCoAfunctions.
Usuallyithasanameendingwith.
pkg.
ItscontentisoftheshapePackageEndPackage;Lateryoucanshareyourpackagewithothers,e.
g.
peopleintheCoCoAUserGrouporotherstudentsinyourclasssweatingoverthesamehomework.
AsthisisagainaveryadvancedwayofusingCoCoA,wesuggestthatyoulookatMan('Package');fordetails.
Inthenextappendixyoucanseesomeexamplesinwhichtheprevioushintsareapplied.
Ifyouneedmorepreciseinformation,wesuggestthatyoulookcarefullyattheCoCoAmanualmentionedinAppendixA.
Andifallelsefails,youmaywriteane-mailtococoa@dima.
unige.
itButforthetimebeing,wewishyougoodluckandsayCiao;--ByeC.
APotpourriofCoCoAProgramsBugscomeinthroughopenWindows.
(Anonymous)C.
1SomeHintsforTutorial1InthisappendixweshallfrequentlyseethatthesamealgorithmcanbeturnedintoCoCoAfunctionsinmanyways.
Parta)ofTutorial1isacaseinpoint.
Forabeginningprogrammer,thefollowingsolutionshouldnotbetoodiculttond.
DefineReprUniv(F,X)L:=NewList(Deg(F)+1);ForI:=0ToDeg(F)DoL[I+1]:=CoeffOfTerm(X^I,F);EndFor;ReturnL;EndDefine;Inthesecondline,wedeneanewlistLoftheappropriatelength.
ThenaFor-loopisusedtollthatlistwiththecoecientsofthegivenpolynomial.
TheidentierXholdsthenameoftheindeterminatewithrespecttowhichthepolynomialFisunivariate.
Noticehowwehadtochangetheindices,sinceinCoCoAtheelementsofalistarenumberedstartingwith"1".
AnelegantsolutionisbasedontheCoCoAfunctionCoefficients(.
.
.
).
DefineReprUniv(F,X)ReturnReversed(Coefficients(F,X));EndDefine;AsforthefunctionListToPoly(weonlygiveyouthesolutionin-volvingthelistconstruction,inordertomakeyoufeelmorecomfortablewiththisstyleofprogramming.
(WetrustyoucandotheFor-loopbynow,can'tyou)DefineListToPoly(L)ReturnSum([L[I]x^(I-1)|IIn1.
.
Len(L)]);EndDefine;294C.
APotpourriofCoCoAProgramsForpartc),weleavetheimplementationofAddUniv(.
.
.
)toyou.
Averyexplicitanddown-to-earthsolutionforthemultiplicationcouldlookasfollows.
DefineMultUniv(L,M)D:=Len(L)+Len(M)-2;ForI:=Len(L)+1ToD+1DoAppend(L,0);EndFor;ForI:=Len(M)+1ToD+1DoAppend(M,0);EndFor;N:=NewList(D+1,0);ForI:=0ToDDoN[I+1]:=Sum([L[J+1]*M[I+1-J]|JIn0.
.
I]);EndFor;ReturnN;EndDefine;Inthesecondline,wedeterminethedegreeDoftheproduct.
ThenweappendzerostothelistsLandMuntilbothofthemhavelengthD+1.
Finally,weconstructanotherlistNwhichwillcontainthenalresult.
Itsentriesarecomputedusingtheformulaforthecoecientsoftheproductgiveninthehint.
Thelistconstructioncreatesthelistofallajbij.
ThefollowingCoCoAprogramremovesthetrailingzerosofalist.
Itmaybeusefulforsolvingpartd)ofthetutorial.
NoticehowwewereabletoexploittheWhile-loop.
DefineShorten(L)N:=Len(L);WhileL[N]=0DoN:=N-1;EndWhile;ReturnFirst(L,N);EndDefine;Thereisalsoanelegantsolutiontopartd)basedonCoefficients(.
.
.
)andthelistconstruction.
Althoughwedonotexpectyoutobeabletowritesuchprograms(yet!
),itiswellworthstudying.
DefineReprPoly(F)Return[Reversed(Coefficients(G,x))|GInReversed(Coefficients(F,y))];EndDefine;Bynow,youshouldbegintoseethepictureofhowtheotherpartsofthetutorialcanbesolved.
Forinstance,forthefunctionAddPoly(.
.
.
)youshouldC.
APotpourriofCoCoAPrograms295againswitchthesummandssuchthattheonewiththehighery-degreecomesrst,andthenaddthesecondoneontotherstoneusingAddUniv(AndbythetimeyouaredoingMultPoly(youwillndthatthehardestpartofprogrammingisusuallytogetyourmathematicsright.
WeendthesehintswithamastersolutionofthePolyToListconversioninthegeneralcase.
DefinePolyToList(F)ReturnRecPolyToList(F,1);EndDefine;DefineRecPolyToList(F,N)IfN=NumIndets()ThenReturnReversed(Coefficients(F,Indet(N)));EndIf;Return[RecPolyToList(G,N+1)|GInReversed(Coefficients(F,Indet(N)))];EndDefine;C.
2DierentStylesofCoCoAProgrammingComputersarenotintelligent.
Theyonlythinktheyare.
(Anonymous)Letusshowyousomedierentprogrammingstylesusingaveryelemen-taryexample.
Wewanttocreateann*n-matrixwhoseentriesarerandomintegersbetween0and100.
Aquicklookattheon-linemanual,andyoushouldbeabletolocatethefunctionRand(0,100)whichgeneratessucharandominteger.
AveryexplicitrstwaytosolveourtaskistocreateanewmatrixofthedesiredsizeandthentollitusingadoubleFor-loop.
DefineRandomMatrix(N)M:=NewMat(N,N);ForI:=1ToNDoForJ:=1ToNDoM[I,J]:=Rand(0,100);EndFor;EndFor;ReturnM;EndDefine;AnotherpossibilitywhichissometimespreferredbybeginnersistocreatethenecessarylistsbystartingwithanemptylistandusingtheAppend(.
.
.
)command,forinstance296C.
APotpourriofCoCoAProgramsDefineRandomMatrix(N)M:=[];ForI:=1ToNDoL:=[];ForJ:=1ToNDoAppend(L,Rand(0,100));EndFor;Append(M,L);EndFor;ReturnMat(M);EndDefine;Bothofthesedoubleloopstendtoberatherslowinpractice.
TryRandomMatrix(100)!
AmoreecientwayistousethelistconstructionsadvertisedinAppendixB.
6.
Inourexample,wecouldwriteDefineRandomMatrix(N)M:=[[Rand(0,100)|IIn1.
.
N]|JIn1.
.
N];ReturnMat(M);EndDefine;Thiswouldproducethesameresult.
Evenmorecompressedcodecanbegeneratedusingtheshortformfordeningone-linefunctions.
RandomMatrix(N):=Mat[[Rand(0,100)|IIn1.
.
N]|JIn1.
.
N];Butdon'toverdoit!
Wewouldconsiderthisbadprogrammingstyle.
Ifyousqueezetoomuchintothoselistconstructions,yourprogramcodebecomesdiculttoread.
Andtheonewhohastosuermostbecauseofthisisusuallyyourself,whenyouwanttoreuseyourcode(orpartsofit)atalaterstage.
C.
3.
HintsforOtherTutorialsinChapter1Whenallelsefails,readtheinstructions.
(Anonymous)InordertomakethetutorialsaccessibletoinexperiencedCoCoApro-grammers,wenowprovidesomeadditionalhintsforselectedtutorialsinChapter1.
Westronglyurgeyoutorsttrythosetutorialsonyourown.
Ifallelsefails,youmaylookforsomeinspirationhere.
ButkeepinmindthatCoCoAprogrammingisonly10%inspirationand90%perspiration.
InTutorial2youshouldnothavesevereproblemstoconvertthegivenstepsintoworkableCoCoAprograms.
ButforPolyExtEuclid(letusshowyouhowtoimplementthecrucialstep4).
Wesupposethatthetuple(c0,d0,e0)isstoredinT0and(c1,d1,e1)inT1.
C.
APotpourriofCoCoAPrograms297WhileT1[3]0DoQ:=DivAlg(T0[3],[T1[3]]);Q1:=Comp(Q.
Quotients,1);T:=T0-Q1*T1;T0:=T1;T1:=T;EndWhile;Thefollowingprogramcomputesallmonicunivariatepolynomialsofaspecieddegreeoveraniteeld.
DefineMonicPoly(D)IfD=0ThenReturn[1];EndIf;IfD=1ThenReturn[x+N|NIn0.
.
(Characteristic()-1)];EndIf;Pre:=MonicPoly(D-1);ReturnConcatLists([[x*F+N|NIn0.
.
(Characteristic()-1)]|FInPre]);EndDefine;YoucanuseitinTutorial3forwritingthefunctionIrredPoly(Loopthroughallmonicpolynomialsofsomedegreeandcheckwhethertheyaredivisiblebyanyirreduciblepolynomialofsmallerdegree.
TheremainderofthedivisionofFbyGcanbefoundbycallingNR(F,[G]).
Clearly,thefunctionGaussFactor(.
.
.
)inTutorial4isatoughnuttocrack.
So,letushelpyou.
SupposeaGauiannumberz=a+ib∈Z[i]isrepresentedinCoCoAbythelist[a,b].
UsingthefunctionSqrt(.
.
.
)fromAppendixC.
5,wecancreatealistofpossibledivisorsofz=a+ibasfollows.
DefinePossibleDivisors(Z)Norm:=Z[1]^2+Z[2]^2;N:=Sqrt(Norm,0);L:=Diff((-N.
.
N)>0DoQ[I]:=Q[I]+LPP(M)/LPP(G[I]);300C.
APotpourriofCoCoAProgramsM:=M-LPP(M)/LPP(G[I])*G[I];I:=Reducer(M,G);EndWhile;Return[Q,M];EndDefine;Finally,inTutorial16noprogrammingisrequired.
Whatapity,wewerejustgettingtheknackofit!
C.
4OptimizingCoCoAFunctionsHowdoyoumakeWindowsfasterThrowitharder.
(Anonymous)WhenyoustarttowritemorecomplicatedCoCoAprograms,youwillsoondiscovercaseswheretheexecutionoftheprogramseemstobeundulyslow.
Thereisasimplerule-of-thumbwhichsaysthatmostcomputerprogramsspendmorethan90%oftheexecutiontimeinlessthen10%oftheprogramcode.
Hence,ifyouwanttoimprovetheperformanceofyourCoCoAprograms,youhavetondthelinescorrespondingtothose10%ofthecode,andtooptimizethemcarefully.
Letusexplainthisprocessusingaveryeasyexample.
InAppendixB.
6weshowedyoutheprogramFactorList(N)whichusesrecursiveprogrammingandcomputesthelistofprimenumbersdividingagivenintegerN.
Firstwemeasurethetimeitneedstofactorizeafewnumbers.
TimeFactorList(123456789);[3,3,3607,3803]Cputime=7.
31,Usertime=7TimeFactorList(1111111);[239,4649]Cputime=4.
51,Usertime=5Theseanswersmeanthat,onamodestcomputer,ittook7.
3and4.
5secondstofactorthetwonumbers.
Ifwelookatthesourcecodeofourprogram,itisclearthatthemosttimeconsumingpartistheWhile-loop.
Ifwedidn'tknowthat,wecouldputaTimecommandinfrontofeverysuspiciouslineoftheprogram.
Forthemoment,letusjustputaTimecommandinfrontoftheWhile-loop.
(WealsoaddedaPrintLn;commandbeforeReturn[];inordertoimprovetheappearanceoftheoutput.
)C.
APotpourriofCoCoAPrograms301FactorList(123456789);Cputime=0.
00,Usertime=0Cputime=0.
00,Usertime=0Cputime=3.
35,Usertime=3Cputime=3.
57,Usertime=4[3,3,3607,3803]FactorList(1111111);Cputime=0.
22,Usertime=0Cputime=4.
34,Usertime=4[239,4649]Thedataconrmthatalmostallofthetimeisspentsearchingforthelargeprimedivisors.
Forthistask,severalobviousimprovementsareathand.
Forinstance,wecanstartthesearchforanewdivisorwiththelastone,andafterwehavereducedNtoanoddnumberwecanlookforodddivisorsonly.
Thefollowingfunctionincorporatestheseoptimizations.
DefineFactorList2(N)IfN=1ThenReturn[];EndIf;IfMod(N,2)=0ThenReturnConcat([2],FactorList2(N/2));EndIf;L:=[];I:=1;WhileIS;Append(L,N);ReturnL;EndDefine;Thistimethefactorizationofthemoredicultexampleaboveisfoundinasplitsecond!
C.
APotpourriofCoCoAPrograms303TimeFactorList3(111111111);[3,3,37,333667]Cputime=0.
17,Usertime=0C.
5HowToDoCalculusUsingCoCoAAsknotwhatyourcountrycandoforyou.
Askwhatyoucandoforyourcountry.
(JohnF.
Kennedy)Mostcomputeralgebrasystemshavebeendesignedanddevelopedbypeoplewhohadcertainapplicationsorfunctionalitiesinmind.
Thuseachofthemhasitsstrengthsanditsweaknesses.
Asauser,youwillsoonerorlaterdiscoverthatyourfavouritecomputeralgebrasystemwasnotdesignedtodopreciselywhatyouwantittodo.
ShouldyouthenswitchtoanotheroneMaybe.
Butfrequentlyitisjustasusefulandinstructivetoteachyourolddoganewtrick.
Forinstance,CoCoAwasclearlynotdesignedforapplicationsincalculus.
Inthecurrentversion,therearenooatingpointnumbersavailable,andnotasingletranscendentalfunction(sin,log,exp,.
.
.
)isimplemented.
Nevertheless,inseveralsituationsaboveweneededanapproximationforthesquarerootofarationalnumber.
LetusshowyouhowyoucanextendthescopeofCoCoAtoincludesuchafunction.
Firstweneedthepossibilitytoroundarationalnumbertoagivennumberofdigitsafterthedecimalpoint.
(Ourfunctionalwaysroundsthenumberdownwards.
Weleaveittoyoutondtheappropriatechangeinordertogettheusualrule.
)DefineRound(XRat,N)XR:=Cast(XRat*10^N,RAT);ReturnDiv(XR.
Num,XR.
Den)/10^N;EndDefine;Next,wescoursomecalculusbooksandcomeupwithanalgorithmforcomputingsquareroots.
ItisbasedonthemethodusedbytheancientBaby-lonians.
Namely,givenarealnumberr>0,thesequencex0=randxi=12(xi1+rxi1)fori≥1convergesto√r.
DefineBabylon(XRat,N)Last:=XRat;New:=(XRat+1)/2;WhileAbs(New-Last)>(0.
1)^(N+1)DoLast:=New;New:=(Last+XRat/Last)/2;EndWhile;ReturnRound(New,N);EndDefine;304C.
APotpourriofCoCoAProgramsUnfortunately,thismethodconvergestooslowlyifwestartwithalargenum-ber.
Henceournalfunctionrstreducestheproblemtoanumberr/10iτt2.
Exercise2.
3.
7.
Toshowa),useTheorem2.
3.
7.
b.
Exercise2.
4.
8.
UseProposition1.
3.
11.
Exercise2.
5.
5.
Showthateveryreductionsteptransformsabinomialintoabinomial.
Exercise2.
6.
1.
Supposethereexistsi∈{1,n}suchthatm∩K[xi]=(0).
ThenshowthatthereexistsaK-algebrahomomorphismK[xi]→P/mwhichisinjective.
D.
3HintsforExercisesinChapter3Exercise3.
1.
1.
UsethefactthatPisafactorialdomain.
Exercise3.
1.
3.
WehaveΣ={σ12,σ13,σ23},whereσ12=xε1yε2,whereσ13=xε1zε3,andwhereσ23=yε2zε3=σ13σ12.
ThenconsiderthesetB={(1,2),(1,3)}.
Exercise3.
2.
9.
Toproveb)a),usethefactthatab(c,d)=bc(a,b).
Exercise3.
3.
4.
Toshowa),usethefactthatfx+gy=(fy)x+(g+x)y.
Exercise3.
4.
6.
Showthat{g1,gn}isaGr¨obnerbasiswithrespecttoasuitablemoduletermordering.
Exercise3.
4.
7.
ProvethatB=P/(I∩P).
Exercise3.
4.
11.
UseProposition3.
4.
6.
Exercise3.
5.
2.
ConsidertheidealpRS.
Exercise3.
5.
4.
ProvethatthereisanisomorphismbetweenPSandPf.
308D.
HintsforSelectedExercisesExercise3.
5.
7.
Tondanexamplewiththerequiredproperty,youmayconsiderthepolynomialringK[x]andthefollowingexactsequenceofP-modules.
0→Px→P→P/(x)P→0Exercise3.
5.
9.
Ifyoudonotndaproof,useCoCoAtoshowthatd21,d22∈JinthecaseK=Q.
Thenverifythattherepresentationsofd21andd22obtainedwithCoCoAarevalidforeveryeldK.
Exercise3.
6.
4.
ConsidertheK-algebrahomomorphism:K[x1,xs]→Rwhichisdenedby(xi)=fi+Ifori=1,s.
Exercise3.
6.
9.
ProvethattheJacobiandeterminantofthecompositionoftwoK-algebrahomomorphismsfromPtoPistheproductofthetwoJacobiande-terminants.
Exercise3.
7.
1.
OneimportantstepintheproofistoshowthatifKisnotaperfecteld,thenthereexistsasquarefreepolynomialfsuchthatgcd(f,f)=1.
Leta∈KbesuchthatithasnopthrootinK.
Thenshowthatf=xpaisirreducible.
Todothis,youmayconsiderfasanelementofK[x].
Ichhabefertig.
(GiovanniTrapattoni)Notation1.
SpecialSetsNsetofnaturalnumbers,N={0,1,2,.
.
.
}ZsetofintegersQsetofrationalnumbersQ>0setofpositiverationalnumbersQsetofalgebraicnumbersRsetofrealnumbersCsetofcomplexnumbersFqniteeldwithqelementsZ[i]ringofGauiannumbersIsetofirrationalnumbers,I=R\QSnsymmetricgrouponnelementsAnKn-dimensionalanespaceoveraeldKBsetofpairsB={(i,j)|1≤ie.
thesetofallteisuchthatt∈Tnand1≤i≤rS(C)setofallC-splinesP(V)projectivespaceassociatedtoavectorspaceVPnKprojectivespaceassociatedtoKn+1Ensetofextendedtermsxα11···xαnn,whereα1,αn∈Z2.
SetsandMapsABsetAisa(notnecessarilyproper)subsetofsetBABsetAisapropersubsetofsetBA\BsetdierenceofAandB,i.
e.
thesetofallelementsofAwhicharenotcontainedinB#AnumberofelementsofanitesetAψcompositionoftwomaps:A→Bandψ:B→CIm()imageofamap:A→BKer()kernelofahomomorphism:A→B310NotationCoker()cokernelofahomomorphism:A→B,i.
e.
Coker()=B/Im()idAidentitymaponasetAABasurjectivemapA→BA→BaninjectivemapA→Bˇdualofalinearmap0→A→Bψ→C→0exactsequenceofhomomorphisms,i.
e.
ase-quencesuchthatisinjective,ψissurjective,andIm()=Ker(ψ)LM:Pr→PrmapdenedbyLM(m)=LMσ(m)form=0andLM(0)=0LF:Ps→PsmapdenedbyLF(m)=LFσ,G(m)form=0andLF(0)=0ZL(f)setofzerosofapolynomialZL(I)setofzerosofanidealp1p2linethroughtwopointsp1andp2(p0pn)pointinann-dimensionalprojectivespaceHyp(PnK)setofhyperplanesinPnKLin(PnK)setoflinesinPnK(PnK)ˇdualprojectivespaceGrassm(PnK)Gramannianofm-dimensionalsubspacesofPnK3.
Orderings≥σmonoidorderingormoduleorderingLexlexicographictermorderingDegLexdegree-lexicographictermorderingDegRevLexdegree-reverse-lexicographictermorderingRevLexreverse-lexicographicorderingElim(L)eliminationorderingforLOrd(V)orderingassociatedtothematrixV4.
PolynomialsandVectorsdeg(f)degreeofapolynomialSupp(v)supportofavectorofpolynomialsgcd(f1,fm)greatestcommondivisoroff1,fmlcm(f1,fm)leastcommonmultipleoff1,fmsqfree(f)squarefreepartoffcont(f)contentofaunivariatepolynomialffderivativeofaunivariatepolynomialfNewton(f)Newtonpolytopeofapolynomial[v1v2]linesegmentfromv1tov2Notation311LTσ(v)leadingtermofavectorofpolynomialsLCσ(v)leadingcoecientofavectorofpolynomialsLMσ(v)equalsLCσ(v)·LTσ(v)NRσ,G(v)normalremainderofavectorLMσ(G)denedbyLMσ(G)=(LMσ(g1)LMσ(gs))foratupleG=(g1,gs)degσ,G(v)σ-degreeofavectorLFσ,G(v)σ-leadingformofavectortijdenedbytij=lcm(ti,tj)tifortermsti,tjσijfundamentalsyzygy,σij=LCσ(gi)1tijεiLCσ(gj)1tjiεjSijS-vectorofgiandgj,denedbySij=LCσ(gi)1tijgiLCσ(gj)1tjigjNFσ,M(v)normalformofavectorw.
r.
t.
asubmoduledet(fixj)Jacobiandeterminantofasystemofpolynomials5.
RingsandFieldschar(K)characteristicoftheeldKQ(R)eldoffractionsofanintegraldomainRK[x1,xn]polynomialringintheindeterminatesx1,xnoverKK(x1,xn)eldofrationalfunctionsintheindeterminatesx1,xnoverKK[[x]]powerseriesringinoneindeterminateK[x1,xn,x11x1n]LaurentpolynomialringK[x1,xn]GringofinvariantsofGni=1RidirectproductoftheringsR1,Rn6.
IdealsandModulesrk(M)rankofafreemodule{e1,er}canonicalbasisofanitelygeneratedfreemoduleM1M2directsumoftwogroupsormodulesI·MsubmoduleofMgeneratedbyproductsfm,wheref∈Iandm∈Mv+MresidueclassofavectorvmoduloMmλ|λ∈Λmodulegeneratedbytheset{mλ|λ∈Λ}(fλ|λ∈Λ)ideal(ormonoideal)generatedbytheset{fλ|λ∈Λ}LTσ(M)leadingtermmoduleofMLTσ{M}monomoduleoftermsinMSyzR(G)syzygymoduleofatupleG√IradicalofanidealI(S)vanishingidealofasetofpointsAnnR(M)annihilatorofamodule312NotationN:RMcolonidealofNbyMN:MIcolonmoduleofNbyIinMHomR(M,N)Hom-moduleoflinearmaps:M→NExtiR(R/I,M)ithExt-moduleofR/IwithvaluesinMMSlocalizationofamoduleMatamultiplicativelyclosedsetSMflocalizationofamoduleatanelementfN:MI∞saturationofamoduleNbyanidealIinMILlatticeidealassociatedtoL7.
MatricesMatn(R)setofn*n-matricesoverRMatm,n(R)setofm*n-matricesoverRGLn(R)setofinvertiblen*n-matricesoverRAtrtransposedmatrixofAIsidentitymatrixofsizes*sAmatrixassociatedtoalinearmapΛr,shomomorphismmappingalinearmaptoitsassociatedmatrixFls,ratteningisomorphismΦr,sisomorphismdenedbyΦr,s=Fls,rΛr,sABtensorproductofAandB8.
MathematicalOperatorsdimK(V)dimensionofaK-vectorspaceVlog(t)logarithmofaterm,log(xα11···xαnn)=(α1,αn)conv(S)convexhullofasetVert(P)setofverticesofapolytopemaxσ(A)maximumofthesetAw.
r.
t.
therelationσinf(A)inmumofasetAofrealnumberssup(A)supremumofasetAofrealnumbersg→reductionstepusinganelementgG→rewriterelationdenedbyasetofvectorsG←→equivalencerelationdenedbyG→TopK,LrelativeZariskitopologydepthI(M)I-depthofamoduleIP(A,b,C)integerprogrammingproblemGReynoldsoperatorofG(f)numberoftermsinthesupportofapolynomialfE(X)expectedvalueofarandomvariableXVar(X)varianceofarandomvariableXσ(X)standarddeviationofarandomvariableXCov(X,Y)covarianceoftworandomvariablesX,Y(X,Y)correlationcoecientoftworandomvariablesX,YBibliography[AL94]W.
AdamsandP.
Loustaunau,AnintroductiontoGr¨obnerbases,GraduateStudiesinMath.
3,Amer.
Math.
Soc.
,Providence1994[BW93]T.
BeckerandV.
Weispfenning,Gr¨obnerbases,Springer,NewYork1993[Bu65]B.
Buchberger,Onndingavectorspacebasisoftheresidueclassringmoduloazerodimensionalpolynomialideal(inGerman),PhDThesis,Universit¨atInnsbruck,Innsbruck1965[BW98]B.
BuchbergerandF.
Winkler,Gr¨obnerbasesandapplications,LondonMath.
Soc.
Lect.
NoteSer.
251,CambridgeUniversityPress,Cambridge1998[CLS92]D.
Cox,J.
Little,andD.
O'Shea,Ideals,varieties,andalgorithms,Springer,NewYork1992[Ei95]D.
Eisenbud,Commutativealgebrawithaviewtowardalgebraicgeometry,Springer,NewYork1995[Fr97]R.
Fr¨oberg,AnintroductiontoGr¨obnerbases,JohnWiley&Sons,Chichester1997[Ku80]E.
Kunz,Introductiontocommutativealgebraandalgebraicgeometry,Birkh¨auser,Boston1985[La70]S.
Lang,Algebra,Addison-Wesley,Reading1970[Mi93]B.
Mishra,Algorithmicalgebra,Springer,NewYork1993[Va98]W.
Vasconcelos,Computationalmethodsincommutativealgebraandalgebraicgeometry,AlgorithmsandComputationinMath.
2,Springer,Berlin1998[Wi96]F.
Winkler,Polynomialalgorithmsincomputeralgebra,Springer,Wien1996Indexane–algebra,134–set,144–space,144–variety,138,144algebra,18–ane,134–automorphism,231–nitelygenerated,23–fundamentaltheoremof,137–presentation,23algebraicclosureofaeld,137algebraicelement,227algebraicrelation,23,227algebraicallyclosedeld,137algorithm–Berlekamp,38–Buchberger,123–division,71–Euclidean,26–extendedBuchberger,125–extendedEuclidean,27–forsolvingsystemseectively,257–normalremainder,75alternatinggroup,237annihilator,166–computation,167–ofacyclicmodule,167–ofamodule,166antisymmetry,50,54associated–elements,31–matrix,182–prime,175–projectivespace,204–toricideal,222automorphism–ofapolynomialring,232–ofanalgebra,231basis–canonical,20–ofamodule,19Berlekampalgorithm,38binomial,127–ideal,127Buchbergertriple,131Buchberger'salgorithm,123–extendedversion,125–optimization,124,131Buchberger'scriterion,122,128CoCoA,11–introduction,275–programming,283cancellationlaw,42–left,42–right,42canonicalbasis,20Cauchy-Schwarzinequality,269characterization–ofGr¨obnerbases,111,122–ofhomogeneousprimeideals,80–ofNoetherianmodules,112–ofNoetherianmonoids,42–ofDegRevLex,65–ofLex,63–ofRevLex,64Chineseremaindertheorem,39,245coecient,22–leading,60cogenerator,47colonideal,48,166–computation,167,175,204colonmodule,169–computation,170,175–usingelimination,199comaximalideals,245commutativemonoid,17completerelation,50complexoflinearmaps,194316Indexcomponentelimination–module,202–ordering,202conuentrewriterelation,95content,33contravariantHom-functor,182convex–hull,67–set,67coprimeelements,31correlationcoecient,268costcompatibletermordering,210costfunction,209covariance,268covariantHom-functor,182cyclic–group,236–module,19decomposition–intohomogeneouscomponents,77degree–compatibletermordering,52–inTne1,er-gradedmodules,102–ofapolynomial,22–ofaspline,157–ofaterm,22–shifting,78degree-lexicographictermordering,51degree-reverse-lexicographictermordering,51densepolynomial,262depthofamodule,193dihedralgroup,237Diophantinesystem,207disconnectedset,142divisionalgorithm,71–implementation,74domain–Euclidean,36–factorial,30–integral,18–principalideal,19dual–map,190–projectivespace,205–sequence,190eectivepthroots,248ecient–frontier,269–portfolio,269element–algebraic,227–associated,31–coprime,31–denesarewriterule,92–homogeneous,76–irreducible,29–prime,29–reducestoanotherelement,92–reducible,29–squarefreepart,31–transcendental,227elementarysymmetricpolynomial,66elimination–computation,197,202–ideal,196–module,48,196,202–ofmodulecomponents,202–ordering,52,196,202Ennepersurface,233Euclideanalgorithm,26–extended,27Euclideandomain,36evaluation,23–homomorphism,23exactsequence–deningsyzygies,100–ofHom-modules,185expectedreturn,268explicitmembership,152Ext-module,194extendeddivision,214,220extendedterm,208factorialdomain,30factorization,29ber,234eld,17–algebraicclosure,137–algebraicallyclosed,137–nite,27–graded,82–havingeectivepthroots,248–ofalgebraicnumbers,98–ofdenition,116–offractions,212–perfect,37,247nitenesscriterion,243atteningisomorphism,182foliumofDescartes,201form,77Frobeniusmap,37functorialityoftheHom-module,182Index317fundamentaldiagram–ofHom-modules,187–ofsyzygymodules,103,121fundamentalproperty–oftermorderings,56fundamentaltheorem–ofalgebra,137Gauian–elimination,119–numbers,36,80generallineargroup,236generationofleadingtermmodules,88Gr¨obnerbasis,111–characterization,111–computation,129–existence,112–homogeneous,120–invarianceundereldextension,116–minimal,118–reduced,115,120Gramannian,206graded–eld,82–freemodule,78–module,77–residueclassmodule,79–residueclassring,79–ring,76–submodule,79grading–byTn,77–byTne1,er,78–onsyzygymodule,101–standard,77graph,235–colouring,143greatestcommondivisor,31–computation,165group,17–alternating,237–cyclic,236–dihedral,237–generallinear,236–ofmatrices,236–ofpermutations,237–ofreections,237–ofrotations,237Heron'sformula,196Hilbert'sbasistheorem,113Hilbert'sNullstellensatz,140–eld-theoreticversion,136–strongversion,140–weakversion,139Hilbert'ssyzygytheorem,159Hom-functor–contravariant,182–covariant,182–exactnessproperties,185Hom-module,181–computation,186homogeneous–component,77–element,76–form,77–Gr¨obnerbasis,120–ideal,79–linearmap,78–polynomial,77,83–primeideal,80–systemofgenerators,79homogenization,172homomorphism–algebra,18–characteristic,18–evaluation,23–Frobenius,37–module,18–ofgradedmodules,78–ofgradedrings,78–ring,18–structural,18–substitution,23,226hyperplane,204ideal,18–binomial,127–colon,48–comaximal,245–elimination,196–homogeneous,79–irreducible,264–lattice,223–maximal,19–membershiptest,114–monomial,44–ofalgebraicrelations,23,227–primary,264–prime,19–principal,19–radical,48,139–stable,119–toric,222–vanishing,140–zero-dimensional,244318Indexidealquotient,166image–ofalinearmap,178–ofamorphism,235–ofanalgebrahomomorphism,228implicitization,227increasinglyorderedtuple,118integerprogramming,207,222integraldomain,18interreducedtuple,118intersection–computation,174,203–ofseveralsubmodules,164–oftwosubmodules,162–usingelimination,199invariantpolynomial,237invarianttheory,236irrationalnumbers,42irreducible–element,29–ideal,264–w.
r.
t.
arewriterelation,92irredundantsystemofgenerators,154Jacobian–conjecture,233–determinant,233kernel–computation,191,227–ofalinearmap,178–ofanalgebrahomomorphism,227Kleinfourgroup,236Kroneckerproduct,184Krull-Azumayalemma,76Lagrangeinterpolation,156Lagrangemultipliers,270lattice,223–ideal,223Laurentpolynomial,208leading–coecient,60–form,102–position,60–powerproduct,60–term,60–termideal,62––ofasquare,123–termmodule,61leastcommonmultiple,31–computation,165left-cancellationlaw,42lemma–ofDickson,43–ofGau,33–ofKrull-Azumaya,76–ofNakayama,81–ofSeidenberg,250lexicographictermordering,51lifting–computation,109,180–existence,106,180–ofalinearmap,180–ofsyzygies,106,109line,144–inprojectivespace,204–segment,67linearalgebra,119,178linearmap,18–homogeneous,78localization,213logarithm,22Macaulay'sbasistheorem,62,115matrix–associatedtoalinearmap,182–group,236–notation,147maximalideal,19–structuretheorem,137,141MEL-rule,272methodoftagvariables,196minimalGr¨obnerbasis,118minimalpolynomial,227–ofanalgebraicnumber,89,98minimalriskportfolio,270modernportfoliotheory,267modularlaw,173module,18–annihilator,166–basis,19–colon,169–cyclic,19–denedoveraeld,116–depth,193–elimination,48,196–nitelygenerated,19–free,19–graded,77–gradedfree,78–monomial,44–Noetherian,112–offractions,213–ofhomomorphisms,181–ofsyzygies,100Index319–ordering,54–projective,191–rank,19–termordering,54Molien'stheorem,238monic–polynomial,60–tuple,118monoid,17,41–commutative,17–ideal,41–module,41–Noetherian,42–ordering,50–withcancellationlaw,42monoideal,41monomialideal,44monomialmodule,44–structuretheorem,44monomodule,41–Noetherian,46morphismofanespaces,234multiplicativelyclosedset,212Nakayama'slemma,81naturalspline,158Newtonpolytope,67Newton'sidentities,239nilpotentelement,18Noetherian–module,112–monoid,42–monomodule,46non-zerodivisor,18–foramodule,171,176normal–xi-position,254–form,73,113–remainder,73,75–remainderalgorithm,75–selectionstrategy,124Nullstellensatz–eld-theoreticversion,136–strongversion,140–weakversion,139numbereld–algebraicclosure,98–Gauian,36–quadratic,24ordering–RevLex,52–compatible,55–inducedbyatuple,149–ofamonoid,50–ofamonomodule,54–ofterms,50–representedbyamatrix,52,57–reverse-lexicographic,52outerproduct,184palindromicverse,241parametricallydenedspacecurve,196perfecteld,37,247permutationgroup,237Pl¨uckerrelations,207point,137–inprojectivespace,204polynomial,20–binomial,127–content,33–dense,262–derivative,35–elementarysymmetric,66–homogeneous,77,83–invariant,237–Lagrangeinterpolation,156–Laurent,208–map,234–minimal,89,227–monic,28,60–multivariate,20–primitive,33–representation,24,60,66–squarefreepart,37–strange,261–symmetric,66,129,230–univariate,20–zero,137polynomialring,20–factoriality,33–surjectivehomomorphism,230–univariate,20polytope,67–Newton,67–vertex,67portfolio,268powerproduct,22preimagecomputation,162presentation–ofamodule,164–ofasubquotient,164–ofanalgebra,23–oftheimage,178,228–ofthekernel,178–viageneratorsandrelations,164320Indexprimary–decomposition,264–ideal,264prime–associated,175–element,29–ideal,19primitiveelementtheorem,256primitivepolynomial,33principalidealdomain,19projection,235projective–hyperplane,204–line,204–module,191–point,204–space,204pullback,191–universalproperty,192Pythagoreantriple,173–fundamental,173–positive,173radical,139–ideal,48,139–membershiptest,219–ofazero-dimensionalideal,247––computation,251rank,19reducedGr¨obnerbasis,115,120reducesinonestep,92reducible–element,29–ideal,142–topologicalspace,142reductionstep,92reectiongroup,237reexivity,50,54regularsequence,171–inanideal,193–test,172relation,50–algebraic,23–complete,50–rewrite,92relativelyprimeelements,31reverse-lexicographicordering,52rewriterelation,92–conuent,95rewriterule,92Reynoldsoperator,238right-cancellationlaw,42ring,17–graded,76–homomorphism,18–ofinvariants,238–polynomial,20–uniquefactorization,30rotationgroup,237runningexample,100S-polynomial,122S-vector,122saturation,215–andlocalization,216–computation,215,217,220–exactnessproperties,220scalarmultiplication,18Seidenberg'slemma,250set–ane,144–convex,67–disconnected,142–multiplicativelyclosed,212–ofzeros,138shapelemma,257shiftingdegrees,78specialgenerationofsubmodules,87spline,155–degree,157–function,156–natural,158squarefreepart,31–computation,249stableideal,119standarddeviation,268standardgrading,77stronglawoflargenumbers,271subalgebra–membershiptest,230–ofafunctioneld,240submodule,18–membershiptest,114submonomodule,41substitutionhomomorphism,23,226support,22symmetric–group,66–polynomial,66,129,230system–ofDiophantineequations,207–ofDiophantineinequalities,207–ofpolynomialequations,241Index321systemofgenerators–homogeneous,79–irredundant,154–minimalhomogeneous,81–minimalmonomial,45–ofamodule,19–ofamonoideal,41–ofamonomodule,42–ofanalgebra,23–ofleadingtermmodule,88–special,87syzygy,100–ofterms,104–trivial,125syzygymodule,100–computation,152,203–ofaGr¨obnerbasis,151–ofelementsofamonomialmodule,104,108syzygytheoremofHilbert,159Taylorexpansion,272tensorproduct,184term,22–extended,208–leading,60–ofamodule,22termordering,50–DegLex,51–DegRevLex,51–Elim(L),52–Lex,51–Ord(V),52–PosTo,55–ToPos,55–classication,58–compatible,55–costcompatible,210–degreecompatible,52–degree-lexicographic,51–degree-reverse-lexicographic,51–elimination,52,196–inducedbyatuple,149–lexicographic,51–module,54–representedbyamatrix,52theorem–Chineseremainder,39,245–ofHilbert,113,159–ofMacaulay,62,115–ofMolien,238–primitiveelement,256toricideal,222totalreturn,267transcendentalelement,227transitiveclosure,92transitivity,50,54trivialreduction,92trivialsyzygy,125twistedcubiccurve,201–tangentsurface,233uniquefactorizationdomain,30universalproperty–oflocalization,219–ofpolynomialrings,23–ofthepullback,192vanishingideal,140variance,268Veronesesurface,235vertex,67well-ordering,55Whitney'sumbrella,235Zariskiclosure,144Zariskitopology,144zero,137–set,138,144zero-dimensionalideal,244