(* Content-type: application/mathematica *) (*** Wolfram Notebook File ***) (* http://www.wolfram.com/nb *) (* CreatedBy='Mathematica 6.0' *) (*CacheID: 234*) (* Internal cache information: NotebookFileLineBreakTest NotebookFileLineBreakTest NotebookDataPosition[ 145, 7] NotebookDataLength[ 244491, 6501] NotebookOptionsPosition[ 215628, 5726] NotebookOutlinePosition[ 233841, 6189] CellTagsIndexPosition[ 232771, 6156] WindowFrame->Normal*) (* Beginning of Notebook Content *) Notebook[{ Cell[" ", "Text", CellChangeTimes->{3.4925313707585697`*^9}], Cell[CellGroupData[{ Cell["\<\ Exact Computation Using Approximate Gr\[ODoubleDot]bner Bases\ \>", "Title", CellChangeTimes->{{3.407166903767702*^9, 3.407166948062443*^9}, 3.407175662380329*^9, {3.419874960786378*^9, 3.419874968397167*^9}, 3.423585774713799*^9}], Cell["\[ThinSpace]Daniel Lichtblau", "Author"], Cell[TextData[{ "Wolfram", StyleBox[" ", FontFamily->"Utopia"], "Research, Inc.\n100 Trade Center Dr.\nChampaign IL 61820" }], "Address", CellChangeTimes->{{3.442279272415884*^9, 3.4422792744776697`*^9}}], Cell["danl@wolfram.com", "Address"], Cell[CellGroupData[{ Cell[TextData[{ StyleBox["ABSTRACT", FontWeight->"Bold"], ". We discuss computation of approximate Gr\[ODoubleDot]bner bases at high \ but finite precision. We show how this can be used to deduce exact results \ for various applications. Examples include implicitizing surfaces, finding \ multivariate polynomial greatest common divisors and factorizations over the \ rational and complex number fields." }], "Abstract", CellChangeTimes->{ 3.407167031516175*^9, {3.407167383675258*^9, 3.407167570417365*^9}, { 3.40717004029304*^9, 3.407170093516818*^9}, {3.419874991484359*^9, 3.419875025712582*^9}, 3.425126760605563*^9, 3.442279303106863*^9, { 3.442279961786182*^9, 3.442279977364141*^9}, {3.4427787366026993`*^9, 3.442778775768538*^9}, {3.443212172672296*^9, 3.443212177175172*^9}, { 3.500821599920124*^9, 3.500821599945284*^9}}], Cell["\<\ This is an extended version of a paper for SYNASC 2010, titled \ \[OpenCurlyDoubleQuote]Polynomial GCD and Factorization Via Approximate Gr\ \[ODoubleDot]bner Bases\[CloseCurlyDoubleQuote], to appear in IEEE conference \ proceedings.\ \>", "Abstract", CellChangeTimes->{{3.50082160211195*^9, 3.500821645410315*^9}, { 3.5008232545597467`*^9, 3.500823266123743*^9}}] }, Open ]], Cell[CellGroupData[{ Cell["Categories and Subject Descriptors", "Subsubsection"], Cell[TextData[{ "G.1.0 [", StyleBox["Numerical", FontWeight->"Bold"], " ", StyleBox["Analysis", FontWeight->"Bold"], "]: General--- Multiple precision arithmetic; Numerical algorithms; I.1.2 \ [", StyleBox["Symbolic and Algebraic Manipulation", FontWeight->"Bold"], "]: Algorithms\[Hyphen]\[Hyphen]\[Hyphen] Algebraic Algorithms; " }], "Text", CellChangeTimes->{ 3.407166968667043*^9, {3.407179393002147*^9, 3.407179425523344*^9}, { 3.407179718988773*^9, 3.40717977659405*^9}, {3.407179810397416*^9, 3.407179848053621*^9}, {3.407179891744576*^9, 3.407179936128926*^9}, { 3.419875351915796*^9, 3.419875352654539*^9}}] }, Open ]], Cell[CellGroupData[{ Cell["General Terms", "Subsubsection", CellChangeTimes->{{3.425078274545281*^9, 3.425078311388019*^9}, { 3.425078886467639*^9, 3.4250788869424*^9}}], Cell[" Algorithms", "Text", CellChangeTimes->{{3.407166989198426*^9, 3.407166989590187*^9}}] }, Open ]], Cell[CellGroupData[{ Cell["Keywords", "Subsubsection"], Cell["\<\ Gr\[ODoubleDot]bner basis, polynomial gcd, hybrid symbolic\[Hyphen]numeric \ computation\ \>", "Text", CellChangeTimes->{{3.407166999875376*^9, 3.407167025088742*^9}, { 3.419875363918324*^9, 3.419875368643406*^9}}] }, Open ]], Cell[CellGroupData[{ Cell[TextData[{ Cell[TextData[{ StyleBox[ CounterBox["Section"], "SectionNumber"], StyleBox[". ", "SectionNumber"] }], "SectionDingbat"], "INTRODUCTION" }], "Section", CellChangeTimes->{3.407168713699685*^9}], Cell[TextData[{ "Since their introduction more than 40 years ago, usage of \ Gr\[ODoubleDot]bner bases has become pervasive in the realm of computational \ algebra. As is well known, most common applications are in algebraic \ manipulation of polynomial ideals. Less known is that they also can be used \ in the setting of classical polynomial algebra, specifically in finding \ multivariate polynomial greatest common divisors and factorizations. Some \ approaches are presented in [", CounterBox["Reference", "Adams Loustaunau"], ", ", CounterBox["Reference", "Becker Weispfenning Kredel"], ", ", CounterBox["Reference", "Buchberger"], ", ", CounterBox["Reference", "Cox Little OShea"], "] but they are not regarded as being competitive with more commonly used \ methods. The primary aim of this paper is to offer alternative methods to the \ classical polynomial algebra algorithms, building them on simple Gr\ \[ODoubleDot]bner basis computations. The methods we will describe and \ demonstrate seem to be more efficient, in practice, than those that have \ appeared in past." }], "Text", CellChangeTimes->{{3.407167898369321*^9, 3.407167929588924*^9}, { 3.407168127730449*^9, 3.407168326499555*^9}, {3.407168530167865*^9, 3.407168686227365*^9}, {3.407168717361224*^9, 3.407168717723925*^9}, 3.407168794907965*^9, {3.410281370273795*^9, 3.410281401029837*^9}, 3.410281521734266*^9, {3.41028156695866*^9, 3.410281567127708*^9}, { 3.410281602267764*^9, 3.41028160618067*^9}, {3.410281677049135*^9, 3.410281685351004*^9}, {3.410281761098505*^9, 3.410281770105746*^9}, { 3.411498665435155*^9, 3.411498680202542*^9}, {3.419875442853736*^9, 3.419875541715543*^9}, {3.419875706913429*^9, 3.419875711154128*^9}, 3.419875771785725*^9, {3.419875982810755*^9, 3.419876151720862*^9}, { 3.419876262302169*^9, 3.419876309222164*^9}, {3.419966452302943*^9, 3.419966480125779*^9}, 3.419966524560271*^9, {3.419966570065356*^9, 3.419966598351923*^9}, {3.419966647136623*^9, 3.419966658793807*^9}, { 3.44208628404126*^9, 3.4420862973541718`*^9}, {3.4420863543842697`*^9, 3.442086388363172*^9}, {3.4420864580465603`*^9, 3.442086467644051*^9}, 3.4420865318934193`*^9, {3.442091459317094*^9, 3.442091460654052*^9}, { 3.442429029724208*^9, 3.442429108250907*^9}, {3.442429174008993*^9, 3.442429222856267*^9}, {3.442429257864884*^9, 3.442429329448059*^9}, { 3.4424293652910557`*^9, 3.442429366970038*^9}, 3.44321171645715*^9, { 3.443211748136735*^9, 3.443211866696439*^9}, {3.443211896947612*^9, 3.443211917702895*^9}, {3.44321347808946*^9, 3.4432134815715714`*^9}, { 3.443213511911742*^9, 3.443213542420693*^9}}], Cell[TextData[{ "A relatively more recent thread in the literature on Gr\[ODoubleDot]bner \ bases involves computation using approximate coefficients. This gives rise to \ an important issue, recognition of cancellation, without which the algorithm \ might either give poor results or even fail to terminate. Shirayanagi [", CounterBox["Reference", "Shirayanagi"], "] gave the first indication of how to handle this. Since that time several \ other approaches have appeared [", CounterBox["Reference", "KondratyevStetterWinkler"], ", ", CounterBox["Reference", "Lichtblau 2"], ", ", CounterBox["Reference", "Sasaki Kako"], ", ", CounterBox["Reference", "Traverso Zanoni"], "]. In [", CounterBox["Reference", "Lichtblau 2"], "] there is discussed an implementation, parts of which have been in ", StyleBox["Mathematica", FontSlant->"Italic"], " since 1996 [", CounterBox["Reference", "Lichtblau 1"], "]. In contrast to [", CounterBox["Reference", "Lichtblau 2"], "], the present article uses approximation at high precision, as a means for \ later recovering exact results." }], "Text", CellChangeTimes->{{3.407167898369321*^9, 3.407167929588924*^9}, { 3.407168127730449*^9, 3.407168326499555*^9}, {3.407168530167865*^9, 3.407168686227365*^9}, {3.407168717361224*^9, 3.407168717723925*^9}, 3.407168794907965*^9, {3.410281370273795*^9, 3.410281401029837*^9}, 3.410281521734266*^9, {3.41028156695866*^9, 3.410281567127708*^9}, { 3.410281602267764*^9, 3.41028160618067*^9}, {3.410281677049135*^9, 3.410281685351004*^9}, {3.410281761098505*^9, 3.410281770105746*^9}, { 3.411498665435155*^9, 3.411498680202542*^9}, {3.419875442853736*^9, 3.419875541715543*^9}, {3.419875706913429*^9, 3.419875711154128*^9}, 3.419875771785725*^9, {3.419875982810755*^9, 3.419876151720862*^9}, { 3.419876262302169*^9, 3.419876306879478*^9}, {3.41994868440772*^9, 3.41994881969967*^9}, {3.419966710935862*^9, 3.419966721117066*^9}, { 3.423404308655832*^9, 3.42340432368334*^9}, 3.423404413379158*^9, 3.423404471799825*^9, {3.423859886120952*^9, 3.423859888296715*^9}, { 3.4420864809345016`*^9, 3.4420864813086042`*^9}, 3.442086514390204*^9, 3.44209135700525*^9, {3.442342950274111*^9, 3.4423430070054197`*^9}, { 3.44242923748909*^9, 3.442429240944994*^9}, {3.443211939962228*^9, 3.443211986816277*^9}, {3.492534115625637*^9, 3.492534128316785*^9}, { 3.492534187911688*^9, 3.492534195395588*^9}, {3.492534269046356*^9, 3.492534272533483*^9}, {3.492534303124372*^9, 3.4925344058587723`*^9}, { 3.492908527917877*^9, 3.492908538616053*^9}, 3.492908569080529*^9}], Cell["\<\ One point of the present work is to illustrate known methods for recovering \ rational or algebraic results from good approximations for \ Gr\[ODoubleDot]bner bases. For this we rely on results in section 2 that \ allow us to conclude such approximations can be attained. We give simple \ examples in section 3. Our main application will be in polynomial algebra, \ specifically, finding greatest common divisors and factorization. Sections 4 \ and 5 provide the relevant theory. They cover how to recover common divisors \ or factors from certain Gr\[ODoubleDot]bner bases that use substitution \ homomorphisms. For factorization, we remark that there is no step involving \ combination of factor images in this approach.\ \>", "Text", CellChangeTimes->{{3.423859889418461*^9, 3.423860011680296*^9}, { 3.4420865238571587`*^9, 3.442086525487526*^9}, {3.442091393278633*^9, 3.442091431644711*^9}, {3.442342703804311*^9, 3.442342774384451*^9}, { 3.442343090894607*^9, 3.442343106990357*^9}, {3.442343204085258*^9, 3.4423432582403316`*^9}, {3.4423473507882757`*^9, 3.4423473972184343`*^9}, { 3.4424293828653383`*^9, 3.442429446665578*^9}, {3.442429494994421*^9, 3.4424295405384083`*^9}, {3.443212043327918*^9, 3.4432120588554*^9}}], Cell["\<\ Typical experience is that classical methods for computing common divisors or \ factorizations are much faster than those methods that rely on \ Gr\[ODoubleDot]bner bases. This, however, is predicated on usage of exact Gr\ \[ODoubleDot]bner basis computations. We will propose methods involving \ approximate basis computation that seem to be more competitive, due to \ avoidance of both coefficient swell and explicit algebraic numbers. We \ illustrate in this setting with several examples in section 6. Specifically, \ we use approximate bases to obtain exact results. We then discuss failure \ modes. Last we summarize and indicate a number of useful directions for \ further work.\ \>", "Text", CellChangeTimes->{{3.407168727604052*^9, 3.407169025230042*^9}, { 3.407169059104*^9, 3.407169202698055*^9}, {3.407169542489715*^9, 3.407169885779486*^9}, {3.40717064999362*^9, 3.407170867423192*^9}, { 3.407170977897279*^9, 3.407171058117182*^9}, {3.407191873481437*^9, 3.407191983594821*^9}, {3.407192052076711*^9, 3.407192192024165*^9}, { 3.410281787683096*^9, 3.410281942682465*^9}, {3.410282461119084*^9, 3.410282489095974*^9}, {3.410282521407896*^9, 3.410282554529211*^9}, { 3.41028359641828*^9, 3.410283683903691*^9}, {3.410291502230341*^9, 3.410291596875603*^9}, {3.410810182944022*^9, 3.410810183997867*^9}, { 3.411494330206781*^9, 3.411494330470632*^9}, {3.411498711984083*^9, 3.411498743326022*^9}, {3.411753598279182*^9, 3.411753603924727*^9}, { 3.41175366163641*^9, 3.411753673468778*^9}, 3.419875916153521*^9, { 3.419876327540757*^9, 3.419876453754741*^9}, {3.419947529467083*^9, 3.419947580122249*^9}, {3.423860017923295*^9, 3.423860042005528*^9}, { 3.424532607916827*^9, 3.42453262416946*^9}, {3.442086560816271*^9, 3.4420865619011374`*^9}, {3.44234282099081*^9, 3.442342869003715*^9}, { 3.442343155134789*^9, 3.442343172366316*^9}, {3.442429562043435*^9, 3.442429562683386*^9}, {3.443212095057026*^9, 3.4432121081218367`*^9}, { 3.492909051815613*^9, 3.492909051834095*^9}, {3.492977126404317*^9, 3.492977126788414*^9}}], Cell[CellGroupData[{ Cell["Acknowledgements", "Subsection", CellChangeTimes->{{3.4441390284695053`*^9, 3.44413903537996*^9}}], Cell["\<\ I thank Ilias Kotsireas for inviting me to present an early version of this \ work at ACA 2008 (Linz) in the session Gr\[ODoubleDot]bner Bases and their \ Applications. I also thank him and the other two session organizers, \ Elizabeth Arnold and Markus Rosenkranz, and honorary Session Chair Bruno \ Buchberger, for all the hard work that went into their session. I thank the \ anonymous referees of the conference version of this work for their many \ useful comments and questions. I also thank a referee of an earlier version \ of this paper for pointing out some typographical errors.\ \>", "Text", CellChangeTimes->{{3.44413910086989*^9, 3.44413927437493*^9}, { 3.4441394182185183`*^9, 3.4441394386048937`*^9}, {3.444139615230733*^9, 3.444139679194779*^9}, {3.4925357339843388`*^9, 3.492535745889317*^9}}] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[TextData[{ Cell[TextData[{ StyleBox[ CounterBox["Section"], "SectionNumber"], StyleBox[". ", "SectionNumber"] }], "SectionDingbat"], "COMPUTATION OF APPROXIMATE GR\[CapitalODoubleDot]BNER BASES" }], "Section", CellChangeTimes->{ 3.407168713699685*^9, {3.407169932065388*^9, 3.407170004592401*^9}, { 3.419949965639491*^9, 3.419949986972019*^9}}], Cell[TextData[{ "We briefly summarize the model of computation we use in this paper. In \ contrast to empirical polynomials (as encountered e.g. in [", CounterBox["Reference", "Corless Giesbrecht van Hoeij Kotsireas Watt"], ", ", CounterBox["Reference", "Lichtblau 2"], "]), we assume inputs are known exactly. We also assume that we can do \ coefficient arithmetic at arbitrary finite precision (in practice, this might \ involve several hundred digits)." }], "Text", CellChangeTimes->{{3.407168727604052*^9, 3.407169025230042*^9}, { 3.407169059104*^9, 3.407169202698055*^9}, {3.407169542489715*^9, 3.407169885779486*^9}, {3.40717064999362*^9, 3.407170867423192*^9}, { 3.407170977897279*^9, 3.407171058117182*^9}, {3.407191997017315*^9, 3.407192038503354*^9}, {3.410282581990838*^9, 3.410282635733234*^9}, { 3.410282839398126*^9, 3.410282885770069*^9}, {3.411494428618641*^9, 3.411494439551387*^9}, {3.419950026304425*^9, 3.419950242995264*^9}, { 3.419950276948453*^9, 3.419950349319269*^9}, {3.419950514848295*^9, 3.419950515510954*^9}, {3.442087634134789*^9, 3.4420876763593817`*^9}, 3.442087724436473*^9, {3.4420879019290733`*^9, 3.442087966841799*^9}}], Cell[TextData[{ "The model used for coefficients, and operations thereon, is significance \ arithmetic, as described in [", CounterBox["Reference", "Keiper"], ", ", CounterBox["Reference", "Sofroniou Spaletta"], "]. In brief, numbers have a value and also an approximation of their \ maximal error. Standard arithmetic such as addition and multiplication of \ such numbers propagates the error via first order approximations. At low \ precision this tends not to be reliable. The (unknown) contributions to error \ from higher order terms (e.g. the product of the errors, if doing \ multiplication) can simply overwhelm the error estimate. At high precision, \ however, this model tends to be quite robust and in practice it is reliable. \ See [", CounterBox["Reference", "Sofroniou Spaletta"], "] for further details. In this paper we will typically work at precisions \ of dozens to hundreds of digits. This suffices to make the computations \ reliable, while not being so large as to detract from the efficiency offered \ by using finite precision arithmetic. " }], "Text", CellChangeTimes->{{3.407168727604052*^9, 3.407169025230042*^9}, { 3.407169059104*^9, 3.407169202698055*^9}, {3.407169542489715*^9, 3.407169885779486*^9}, {3.40717064999362*^9, 3.407170867423192*^9}, { 3.407170977897279*^9, 3.407171058117182*^9}, {3.407191997017315*^9, 3.407192038503354*^9}, {3.410282581990838*^9, 3.410282635733234*^9}, { 3.410282839398126*^9, 3.410282885770069*^9}, {3.411494428618641*^9, 3.411494439551387*^9}, {3.419950026304425*^9, 3.419950242995264*^9}, { 3.419950276948453*^9, 3.419950349319269*^9}, {3.419950514848295*^9, 3.419950526638479*^9}, {3.423860049667238*^9, 3.42386005084385*^9}, { 3.442086697992079*^9, 3.442086704429717*^9}, {3.469802586983279*^9, 3.4698025933767767`*^9}, {3.49253628365259*^9, 3.4925362876043243`*^9}, { 3.492536324595694*^9, 3.492536388722144*^9}, {3.492542735512601*^9, 3.4925428944801702`*^9}, {3.492542929263764*^9, 3.4925430700922937`*^9}, 3.49297411831726*^9}], Cell["\<\ Recall that in computing Gr\[ODoubleDot]bner bases, it is of paramount \ importance in polynomial reduction to recognize when sums of like terms \ cancel, as this is how we obtain new leading coefficients. In our model of \ arithmetic we regard a sum as zero when there is full cancellation of all \ digits, that is, the result is less than the approximated error interval.\ \>", "Text", CellChangeTimes->CompressedData[" 1:eJxTTMoPSmViYGAQBmIQnRryedaKpJeOjTHqB0D0j+DkIyC6PCzsGojev/o8 w0og3ftxhzaI3nPavhtEn+rKXQaim7bZbAHRX/Y77wPRN3oXfN8MpKukL/wB 0Z+27OeamfHScXlZuSCILt77RgtEZyzZYQCiX5yefPhF1kvHb0s+HgHRN/d6 VnJWv3Q0uRk/BUTvipw3A0SXmK9aCKJtVKO3geicvCvbQTRLlOmquqaXjpcY osG0zH77VKelLx3tDvCmgWi28vhu+VsvHfv4dHpANMujkt/VrK8cF4R9BtNv +Scz1ADpc9LTOUC0VfoHxXogzeLDoQSiY3qnpmmIvHL8lPwiE0QDAAIfnHQ= "]], Cell["\<\ When using significance arithmetic, over the course of many operations there \ will be a (typically gradual) erosion of precision. In practical usage one \ simply starts with a finite approximation of exact input that is sufficiently \ high as to allow the algorithm to run to completion without encountering loss \ of too much precision. What this means will be explained in more detail \ below. First we state a result that has appeared before in various forms. We \ tailor it to the needs of our arithmetic model.\ \>", "Text", CellChangeTimes->{{3.407168727604052*^9, 3.407169025230042*^9}, { 3.407169059104*^9, 3.407169202698055*^9}, {3.407169542489715*^9, 3.407169911580855*^9}, {3.407170913449708*^9, 3.407170960809034*^9}, { 3.411494404848379*^9, 3.411494407920436*^9}, {3.419950553307618*^9, 3.419950683013836*^9}, {3.419951207496538*^9, 3.419951242232705*^9}, { 3.419952425507184*^9, 3.419952450783206*^9}, {3.424532570253746*^9, 3.424532571671026*^9}, 3.50022955012046*^9}], Cell["\<\ Theorem 1. We are given a set F of polynomials in some set of indeterminates \ over the rationals, a term order, and an outcome precision s. Also we assume \ we use a specific algorithm to compute its reduced, minimal \ Gr\[ODoubleDot]bner basis (Buchberger's algorithm, say), and we call that \ basis G. Then there exists a finite precision r such that if we use that \ algorithm to compute a Gr\[ODoubleDot]bner basis for F, begin with r or more \ digits, and use finite precision significance arithmetic on coefficient sums, \ products, and reciprocals, then the result will agree with G to s digits in \ all coefficients.\ \>", "Text", FontSlant->"Italic"], Cell[TextData[{ "Proof. In running the algorithm to obtain ", Cell[BoxData[ FormBox["G", TraditionalForm]]], " from ", Cell[BoxData[ FormBox["F", TraditionalForm]]], ", there will occur a maximal integer coefficient size M. Moreover there \ occurs a certain number ", Cell[BoxData[ FormBox["A", TraditionalForm]]], " of arithmetic operations on coefficients, and a maximal cancellation ", Cell[BoxData[ FormBox["K", TraditionalForm]]], " of digits in operations that do not yield zero (this cancellation is what \ causes loss of precision when repeating the process in finite precision; \ clearly ", Cell[BoxData[ FormBox[ RowBox[{"K", "\[LessEqual]", "M"}], TraditionalForm]]], "). Given these parameters, and a desired precision ", Cell[BoxData[ FormBox["s", TraditionalForm]]], " for the outcome, we assert the following. One can find a start precision, \ and repeat the algorithm using significance arithmetic, with all steps having \ the following properties." }], "Text", CellChangeTimes->{{3.419951750918614*^9, 3.419952006885355*^9}, { 3.419952069986237*^9, 3.419952169278338*^9}, {3.419952211244706*^9, 3.419952224746297*^9}, {3.419952306664479*^9, 3.419952312232621*^9}, { 3.419952600681791*^9, 3.419952600825304*^9}, 3.419961215520205*^9, { 3.423404894019077*^9, 3.423404909743052*^9}, {3.423405004454334*^9, 3.423405040164771*^9}, {3.423405597632197*^9, 3.423405626129953*^9}, 3.423405861201586*^9, {3.423677044613312*^9, 3.423677065680014*^9}, { 3.423913672485847*^9, 3.423913675683997*^9}, 3.424555981954256*^9, { 3.4420867316447163`*^9, 3.442086756671822*^9}}], Cell[TextData[{ "(i) The precision of intermediate values is always larger than ", Cell[BoxData[ FormBox["s", TraditionalForm]]], "." }], "Text", CellChangeTimes->{{3.419951750918614*^9, 3.4199520281203*^9}, { 3.41995219943947*^9, 3.419952246283062*^9}, {3.419952671626348*^9, 3.419952674022882*^9}}], Cell[TextData[{ "(ii) Cancellations of more than ", Cell[BoxData[ FormBox["K", TraditionalForm]]], " digits will correctly be regarded as resulting in zero. Smaller \ cancellations will retain significant digits and hence not be regarded as \ zero." }], "Text", CellChangeTimes->{{3.419952047414708*^9, 3.419952048238058*^9}, { 3.419952251329708*^9, 3.419952273858376*^9}, {3.41995267604871*^9, 3.419952677111945*^9}, 3.419966820122476*^9, {3.423677119682868*^9, 3.423677137936889*^9}}], Cell[TextData[{ "To see that this assertion is correct, we first observe that \ multiplications lose at most ", Cell[BoxData[ FormBox[ RowBox[{"M", "+", "1"}], TraditionalForm]]], " digits of precision, and additions at most ", Cell[BoxData[ FormBox[ RowBox[{"K", "+", "1"}], TraditionalForm]]], " (1 from roundoff and ", Cell[BoxData[ FormBox["K", TraditionalForm]]], ", by assumption, from cancellation). See [", CounterBox["Reference", "Sofroniou Spaletta"], "] for details on how this loss of precision is modelled to first order in \ significance arithmetic. The salient point is that we have a means to \ recognize when a full cancellation has taken place, that is, when two terms \ sum to zero. It happens precisely when there is cancellation of all \ significant digits. We need only guarantee that the initial precision be \ sufficiently high in order to deduce such cancellation (that is, recognize \ zero) correctly. This in turn implies that the finite precision algorithm, if \ given sufficient precision of input, will correctly emulate the exact case. \ From the preceding remarks we see that a starting precision of ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"A", " ", RowBox[{"(", RowBox[{"M", "+", "1"}], ")"}]}], "+", "s"}], TraditionalForm]]], " digits suffices. \[EmptySquare]" }], "Text", CellChangeTimes->{{3.419951750918614*^9, 3.419952007008801*^9}, 3.419952284260972*^9, {3.419952327572219*^9, 3.419952372671828*^9}, { 3.419952622717848*^9, 3.419952802233736*^9}, {3.419961149263741*^9, 3.419961154621858*^9}, {3.41996121871882*^9, 3.419961218735632*^9}, { 3.420051225675932*^9, 3.420051225676162*^9}, {3.423405082051562*^9, 3.423405095588233*^9}, {3.423405764160611*^9, 3.423405780223365*^9}, { 3.423677189546436*^9, 3.423677359457497*^9}, {3.423677396651699*^9, 3.423677433847508*^9}, {3.423677475948234*^9, 3.423677580680977*^9}, { 3.423677613548998*^9, 3.423677647645633*^9}, {3.423677740478002*^9, 3.42367774141387*^9}, {3.423677786261633*^9, 3.423677786279596*^9}, { 3.423677904937309*^9, 3.423678085066544*^9}, {3.423678123844863*^9, 3.423678255309651*^9}, {3.423678296988508*^9, 3.423678387785755*^9}, { 3.423678448477958*^9, 3.423678461135422*^9}, 3.423678527321344*^9, { 3.423678601084093*^9, 3.423678608916365*^9}, {3.423678640631503*^9, 3.423678667933959*^9}, {3.423860061642207*^9, 3.423860062155572*^9}, { 3.424531584266597*^9, 3.424531587731757*^9}, {3.424531638435457*^9, 3.424531652375174*^9}, {3.492536531057724*^9, 3.492536540261758*^9}, 3.492536608477131*^9}], Cell["\<\ We remark that the sufficient initial precision of the above theorem is \ generally far larger than necessary (and also cannot be computed a priori, \ since it depends on information specific to running the code in exact \ arithmetic). While the proposition sheds no light on what will be a realistic \ precision in which to begin a computation, we will show examples that might \ be regarded as typical of actual practice.\ \>", "Text", CellChangeTimes->{{3.419961220405634*^9, 3.419961293357094*^9}, { 3.423678550259794*^9, 3.423678567000079*^9}, {3.423678671311298*^9, 3.42367868423312*^9}, {3.423860064929484*^9, 3.423860065442613*^9}, { 3.442086784653145*^9, 3.44208682969304*^9}, 3.4695532522696457`*^9, { 3.492536632798793*^9, 3.492536703929891*^9}}] }, Open ]], Cell[CellGroupData[{ Cell[TextData[{ Cell[TextData[{ StyleBox[ CounterBox["Section"], "SectionNumber"], StyleBox[". ", "SectionNumber"] }], "SectionDingbat"], "EXACT RESULTS FROM APPROXIMATE GR\[CapitalODoubleDot]BNER BASES" }], "Section", CellChangeTimes->{ 3.407168713699685*^9, {3.407169932065388*^9, 3.407170004592401*^9}, { 3.419949965639491*^9, 3.419949986972019*^9}, {3.423857062664536*^9, 3.42385706664992*^9}, {3.423859429492527*^9, 3.423859431509681*^9}}], Cell["\<\ Given a set of polynomials with rational coefficients, we might find an \ approximate Gr\[ODoubleDot]bner basis to high precision and then attempt to \ recover the exact basis from the approximation. The point of such an endeavor \ is that it can be faster to do this, and validate the result, than to compute \ the exact basis by exact methods.\ \>", "Text", CellChangeTimes->{{3.423857083336346*^9, 3.423857234987534*^9}, { 3.42385726909194*^9, 3.423857270153346*^9}, {3.423860069242439*^9, 3.423860069826904*^9}}], Cell[TextData[{ "At this point it is helpful to see an actual example where use of \ approximate numbers gives a substantial improvement over exact computation. \ This example is mentioned in [", CounterBox["Reference", "Tran"], "]. It is an implicitization of a polynomial parametric surface. To find the \ implicit form we compute a Gr\[ODoubleDot]bner basis using a term ordering \ that eliminates the parameters [", CounterBox["Reference", "Cox Little OShea"], "]. The timing shown is in seconds; an exact computation of the implicit \ form took several hours. Here we do the computation at 500 digits; this will \ suffice to recover the exact form." }], "Text", CellChangeTimes->{{3.420051339043014*^9, 3.420051407616785*^9}, { 3.420051473042005*^9, 3.420051502575081*^9}, {3.420051548724146*^9, 3.420051575443606*^9}, {3.420051662643262*^9, 3.420051854001899*^9}, { 3.423679418755192*^9, 3.423679420316345*^9}, 3.423857707803926*^9, 3.4420880171805*^9, {3.442088195081121*^9, 3.4420882074050303`*^9}, { 3.44258406071068*^9, 3.442584072670854*^9}, {3.443211119878125*^9, 3.44321113350325*^9}}], Cell[CellGroupData[{ Cell[TextData[StyleBox["Example 1", FontSlant->"Italic"]], "Subsubsection", CellChangeTimes->{3.424448768627185*^9, 3.424523588311299*^9}], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{ RowBox[{"surfacePolys", "=", RowBox[{"{", RowBox[{ RowBox[{ RowBox[{"-", "17"}], "-", RowBox[{"27", " ", "s"}], "+", RowBox[{"36", " ", SuperscriptBox["s", "2"]}], "-", RowBox[{"19", " ", SuperscriptBox["s", "3"]}], "-", RowBox[{"45", " ", "s", " ", SuperscriptBox["t", "2"]}], "+", RowBox[{"81", " ", SuperscriptBox["s", "2"], " ", SuperscriptBox["t", "2"]}], "-", RowBox[{"54", " ", SuperscriptBox["s", "3"], " ", SuperscriptBox["t", "2"]}], "+", RowBox[{"30", " ", "s", " ", SuperscriptBox["t", "3"]}], "-", RowBox[{"54", " ", SuperscriptBox["s", "2"], " ", SuperscriptBox["t", "3"]}], "+", RowBox[{"36", " ", SuperscriptBox["s", "3"], " ", SuperscriptBox["t", "3"]}], "+", RowBox[{"10", " ", "x"}]}], ",", RowBox[{ RowBox[{"198", " ", "s"}], "-", RowBox[{"369", " ", SuperscriptBox["s", "2"], " ", "t"}], "+", RowBox[{"246", " ", SuperscriptBox["s", "3"], " ", "t"}], "-", RowBox[{"198", " ", SuperscriptBox["t", "2"]}], "+", RowBox[{"369", " ", SuperscriptBox["s", "2"], " ", SuperscriptBox["t", "2"]}], "-", RowBox[{"246", " ", SuperscriptBox["s", "3"], " ", SuperscriptBox["t", "2"]}], "+", RowBox[{"100", " ", "y"}]}], ",", RowBox[{ RowBox[{"-", "57"}], "-", RowBox[{"81", " ", SuperscriptBox["s", "2"]}], "+", RowBox[{"42", " ", SuperscriptBox["s", "3"]}], "+", RowBox[{"99", " ", SuperscriptBox["t", "2"]}], "-", RowBox[{"81", " ", "s", " ", SuperscriptBox["t", "2"]}], "-", RowBox[{"108", " ", SuperscriptBox["s", "2"], " ", SuperscriptBox["t", "2"]}], "+", RowBox[{"90", " ", SuperscriptBox["s", "3"], " ", SuperscriptBox["t", "2"]}], "-", RowBox[{"66", " ", SuperscriptBox["t", "3"]}], "+", RowBox[{"54", " ", "s", " ", SuperscriptBox["t", "3"]}], "+", RowBox[{"72", " ", SuperscriptBox["s", "2"], " ", SuperscriptBox["t", "3"]}], "-", RowBox[{"60", " ", SuperscriptBox["s", "3"], " ", SuperscriptBox["t", "3"]}], "+", RowBox[{"40", " ", "z"}]}]}], "}"}]}], ";"}], "\n", RowBox[{ RowBox[{"elims", "=", RowBox[{"{", RowBox[{"s", ",", "t"}], "}"}]}], ";"}], "\n", RowBox[{ RowBox[{"vars", "=", RowBox[{"{", RowBox[{"x", ",", "y", ",", "z"}], "}"}]}], ";"}], "\n", RowBox[{"Timing", "[", RowBox[{ RowBox[{"gbapprox", "=", RowBox[{"GroebnerBasis", "[", RowBox[{"surfacePolys", ",", "vars", ",", "elims", ",", RowBox[{"MonomialOrder", "\[Rule]", "EliminationOrder"}], ",", RowBox[{"CoefficientDomain", "\[Rule]", RowBox[{"InexactNumbers", "[", "500", "]"}]}], ",", RowBox[{"Method", "\[Rule]", RowBox[{"{", RowBox[{"\"\\"", ",", RowBox[{"\"\\"", "\[Rule]", "True"}]}], "}"}]}]}], "]"}]}], ";"}], "]"}]}], "Input", CellChangeTimes->{{3.390315900675643*^9, 3.390315924465936*^9}, { 3.390315978180542*^9, 3.390315995228193*^9}, {3.420051624889842*^9, 3.420051626690774*^9}, {3.420051927303539*^9, 3.420051927742103*^9}, 3.442087766699901*^9, 3.4422791515329*^9, 3.470070215459237*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{"168.23942399999999`", ",", "Null"}], "}"}]], "Output", CellChangeTimes->{3.443212465534774*^9, 3.4432135885134172`*^9, 3.470070906774622*^9, 3.470071089538163*^9}] }, Open ]], Cell["\<\ We recover the exact form simply by rationalizing the approximate values. \ This well known technique uses continued fraction approximation. Since it \ might fail to find rationals sufficiently \[OpenCurlyDoubleQuote]close\ \[CloseCurlyDoubleQuote] to the approximate numbers, we will verify \ explicitly that we indeed obtained rational values.\ \>", "Text", CellChangeTimes->{{3.42005230758955*^9, 3.420052462266498*^9}, 3.423405168685851*^9, {3.442088039850998*^9, 3.442088046698278*^9}, { 3.470071103848094*^9, 3.4700711149355717`*^9}, 3.49253586709372*^9}], Cell[BoxData[ RowBox[{"Timing", "[", RowBox[{ RowBox[{"implicit", "=", RowBox[{"Rationalize", "[", RowBox[{"gbapprox", "[", RowBox[{"[", "1", "]"}], "]"}], "]"}]}], ";", RowBox[{"Precision", "[", "implicit", "]"}]}], "]"}]], "Input", CellGroupingRules->{GroupTogetherGrouping, 10001.}, CellChangeTimes->{{3.39056475340897*^9, 3.390564786357652*^9}, { 3.390564823641611*^9, 3.39056483872438*^9}, 3.390565427527744*^9, { 3.420052299330795*^9, 3.420052304135398*^9}, {3.443211091334167*^9, 3.443211099073094*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{"0.3469470000000001`", ",", "\[Infinity]"}], "}"}]], "Output", CellChangeTimes->{3.443213792621008*^9}], Cell["\<\ One also should verify that the polynomial obtained is the correct one. This \ is straightforward (plug the parametric values for the variables into the \ implicit polynomial, and check that it expands to zero); we omit the details.\ \ \>", "Text", CellChangeTimes->{{3.420052475527497*^9, 3.420052506098779*^9}, { 3.420052555446423*^9, 3.420052637847045*^9}, {3.423860077425404*^9, 3.423860077908083*^9}, {3.442088025851666*^9, 3.442088029289997*^9}}], Cell["\<\ Using similar methods we can implicitize the four difficult patches of the \ iconic Newell teapot (these four cover its spout). To the best of my \ knowledge this is the only way in which their implicit forms have been found \ using Gr\[ODoubleDot]bner bases. (The remaining 28 patches can all readily be \ handled via Gr\[ODoubleDot]bner bases using exact computation; the timings \ vary from a fraction of a second to a few seconds).\ \>", "Text", CellChangeTimes->{{3.420051953093212*^9, 3.420052071462396*^9}, { 3.42340518868035*^9, 3.423405189781891*^9}, {3.423678755477419*^9, 3.423678771301282*^9}, {3.4420880731155777`*^9, 3.442088096926777*^9}, { 3.492535891872143*^9, 3.49253589330905*^9}}], Cell[TextData[{ "One can do more than just recover rational numbers. Suppose, for example, \ we have a system of polynomial equations over the rationals, and seek exact \ solutions. We know from general theory that these solutions will be algebraic \ numbers. One approach to obtaining them is to find numeric approximations to \ high precision, and then deduce the algebraic numbers using, say, an \ algorithm based on PSLQ or lattice reduction [", CounterBox["Reference", "Ferguson Bailey Arno"], ", ", CounterBox["Reference", "Lenstra"], "]. Unfortunately, preliminary results in this direction are not promising, \ except in cases of low degree algebraic numbers. This is because typical \ solutions require large integers in the algebraics, and so a tactic of \ recovering exact from approximate tends to be slower than a direct \ computation using exact methods (that possibly use approximate arithmetic in \ the process of computing a Gr\[ODoubleDot]bner basis, as was done above). But \ such methods of algebraic recovery will be useful to us in the context of \ factorization, as will be seen in a later example." }], "Text", CellChangeTimes->{ 3.44243001289248*^9, {3.5002263977836246`*^9, 3.500226401238055*^9}}] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[TextData[{ Cell[TextData[{ StyleBox[ CounterBox["Section"], "SectionNumber"], StyleBox[". ", "SectionNumber"] }], "SectionDingbat"], "BIVARIATE POLYNOMIAL GCD COMPUTATION" }], "Section", CellChangeTimes->{{3.407171809947496*^9, 3.407171844310016*^9}, { 3.407172024813134*^9, 3.407172040605009*^9}, {3.40717902284139*^9, 3.407179040891735*^9}, {3.419964899502602*^9, 3.419964901274152*^9}, { 3.424523707949821*^9, 3.424523726754684*^9}, 3.42452456603162*^9}], Cell[TextData[{ "For simplicity we restrict our attention to bivariate polynomials. \ Generalizing to the multivariate case is straightforward (though making it \ computationally efficient might pose a serious challenge). We will use a \ result related to material in [", CounterBox["Reference", "Gianni Trager"], "]. We develop the relevant theory in a series of propositions." }], "Text", CellChangeTimes->{{3.424527270903172*^9, 3.4245273445854*^9}, 3.424527407852921*^9, {3.442089786173399*^9, 3.4420898306540813`*^9}, 3.492539599025169*^9}], Cell[TextData[{ StyleBox["Proposition 1. Suppose we have ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["f", "1"], "=", RowBox[{"g", " ", "h"}]}], TraditionalForm]], FontSlant->"Italic"], StyleBox[" and ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["f", "2"], "=", RowBox[{"g", " ", "k"}]}], TraditionalForm]], FontSlant->"Italic"], StyleBox[" with ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"g", ",", "h", ",", "k"}], TraditionalForm]], FontSlant->"Italic"], StyleBox[" bivariate polynomials in ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"\[DoubleStruckCapitalQ]", "[", RowBox[{"x", ",", "y"}], "]"}], TraditionalForm]], FontSlant->"Italic"], ", ", StyleBox["and ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"h", ",", "k"}], TraditionalForm]], FontSlant->"Italic"], StyleBox[" relatively prime. Suppose ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["y", "0"], "\[Element]", "\[DoubleStruckCapitalQ]"}], TraditionalForm]], FontSlant->"Italic"], StyleBox[" is a generic value. For our purposes of genericity we require the \ following conditions.", FontSlant->"Italic"] }], "Text", CellChangeTimes->{{3.424527425152877*^9, 3.424527429780294*^9}, { 3.42452746751133*^9, 3.424527527259339*^9}, {3.424527561578621*^9, 3.424527682890602*^9}, {3.424527847773325*^9, 3.424528103706303*^9}, { 3.424529118433184*^9, 3.424529124448483*^9}, {3.424555943474176*^9, 3.424555943641459*^9}, {3.424556203185572*^9, 3.424556222420025*^9}, { 3.42460281921152*^9, 3.424602889482788*^9}, {3.424602927039293*^9, 3.42460295218322*^9}, {3.424602984761418*^9, 3.424603025562836*^9}, { 3.42460307683003*^9, 3.424603109862694*^9}, {3.424603228222109*^9, 3.424603246590967*^9}, {3.424715659714237*^9, 3.424715698088626*^9}, 3.42472723038267*^9, 3.424728278889862*^9, 3.44208994257382*^9, { 3.442582004572591*^9, 3.4425820118497467`*^9}}], Cell[TextData[{ StyleBox["(1) ", "Text"], StyleBox[Cell[BoxData[ FormBox["g", TraditionalForm]], "Text"], "Text"], StyleBox[" ", "Text"], StyleBox["and ", "Text", FontSlant->"Italic"], StyleBox[Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], TraditionalForm]], "Text"], "Text"], StyleBox[" are relatively prime (that is, ", "Text", FontSlant->"Italic"], StyleBox[Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "\[NotVerticalBar]", "g"}], TraditionalForm]], "Text"], "Text"], StyleBox[")", "Text"] }], "Text", CellChangeTimes->{{3.424527425152877*^9, 3.424527429780294*^9}, { 3.42452746751133*^9, 3.424527527259339*^9}, {3.424527561578621*^9, 3.424527682890602*^9}, {3.424527847773325*^9, 3.424528103706303*^9}, { 3.424529118433184*^9, 3.424529124448483*^9}, {3.424555943474176*^9, 3.424555943641459*^9}, {3.424556203185572*^9, 3.424556222420025*^9}, { 3.42460281921152*^9, 3.424602889482788*^9}, {3.424602927039293*^9, 3.42460295218322*^9}, {3.424602984761418*^9, 3.424603025562836*^9}, { 3.42460307683003*^9, 3.424603109862694*^9}, {3.424603228222109*^9, 3.424603307135596*^9}, 3.424603659677296*^9, {3.4420898828620443`*^9, 3.442089883613665*^9}, {3.4420899716312437`*^9, 3.4420899749745703`*^9}}], Cell[TextData[{ StyleBox["(2) ", "Text"], StyleBox[Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ SubscriptBox["deg", "x"], "(", RowBox[{"g", "(", RowBox[{"x", ",", "y"}], ")"}], ")"}], "=", RowBox[{ SubscriptBox["deg", "x"], "(", RowBox[{"g", "(", RowBox[{"x", ",", SubscriptBox["y", "0"]}], ")"}], ")"}]}], TraditionalForm]], "Text"], "Text"], StyleBox[", ", "Text"], StyleBox["where", "Text", FontSlant->"Italic"], StyleBox[" ", "Text"], Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["deg", "x"], "(", "p", ")"}], TraditionalForm]]], " ", StyleBox["denotes the degree in ", "Text", FontSlant->"Italic"], StyleBox[Cell[BoxData[ FormBox["x", TraditionalForm]], "Text"], "Text"], StyleBox[" ", "Text"], StyleBox["of ", "Text", FontSlant->"Italic"], StyleBox[Cell[BoxData[ FormBox["p", TraditionalForm]], "Text"], "Text"], StyleBox[".", FontSlant->"Italic"] }], "Text", CellChangeTimes->{{3.424603314272706*^9, 3.424603366140388*^9}, { 3.424603405353691*^9, 3.424603487707803*^9}, {3.424603550481414*^9, 3.424603559281789*^9}, {3.424603598421058*^9, 3.424603619383668*^9}, { 3.425134015619159*^9, 3.425134069658031*^9}, {3.442089886686947*^9, 3.442089887390402*^9}}], Cell[TextData[{ StyleBox["(3) The variety ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"V", "(", RowBox[{"h", ",", "k", ",", RowBox[{"y", "-", SubscriptBox["y", "0"]}]}], ")"}], TraditionalForm]], FontSlant->"Italic"], StyleBox[" is empty (this is a generic condition from the hypothesis that ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"gcd", "(", RowBox[{"h", ",", "k"}], ")"}], "=", "1"}], TraditionalForm]], FontSlant->"Italic"], ")", StyleBox[".", FontSlant->"Italic"] }], "Text", CellChangeTimes->{{3.424527425152877*^9, 3.424527429780294*^9}, { 3.42452746751133*^9, 3.424527527259339*^9}, {3.424527561578621*^9, 3.424527682890602*^9}, {3.424527847773325*^9, 3.424528103706303*^9}, { 3.424529118433184*^9, 3.424529124448483*^9}, {3.424555943474176*^9, 3.424555943641459*^9}, {3.424556203185572*^9, 3.424556222420025*^9}, { 3.42460281921152*^9, 3.424602889482788*^9}, {3.424602927039293*^9, 3.42460295218322*^9}, {3.424602984761418*^9, 3.424603025562836*^9}, { 3.42460307683003*^9, 3.424603109862694*^9}, {3.424603228222109*^9, 3.424603303535834*^9}, {3.424603719176294*^9, 3.424603719355436*^9}, { 3.442089889613803*^9, 3.4420898904618073`*^9}}], Cell[TextData[{ StyleBox[" Then for all positive integers ", FontSlant->"Italic"], Cell[BoxData[ FormBox["n", TraditionalForm]], FontSlant->"Italic"], StyleBox[", we have equality of ideals ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"(", RowBox[{ SubscriptBox["f", "1"], ",", SubscriptBox["f", "2"], ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "n"]}], ")"}], "=", RowBox[{"(", RowBox[{"g", ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "n"]}], ")"}]}], TraditionalForm]], FontSlant->"Italic"], StyleBox[". ", FontSlant->"Italic"] }], "Text", CellChangeTimes->{{3.442089955643323*^9, 3.442089955643455*^9}, { 3.442582036536538*^9, 3.442582036536697*^9}, {3.4425820762478333`*^9, 3.442582076247966*^9}}], Cell[TextData[{ "Proof. Set ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["I", "n"], "=", RowBox[{"(", RowBox[{ SubscriptBox["f", "1"], ",", SubscriptBox["f", "2"], ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "n"]}], ")"}]}], TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["J", "n"], "=", RowBox[{"(", RowBox[{"g", ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "n"]}], ")"}]}], TraditionalForm]], FontSlant->"Italic"], ". Since ", Cell[BoxData[ FormBox["g", TraditionalForm]]], " divides both ", Cell[BoxData[ FormBox[ SubscriptBox["f", "1"], TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ SubscriptBox["f", "2"], TraditionalForm]]], ", clearly for all ", Cell[BoxData[ FormBox["n", TraditionalForm]]], " we have ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["I", "n"], "\[Subset]", SubscriptBox["J", "n"]}], TraditionalForm]]], ". For the reverse inclusion we proceed by induction. In the base case, ", Cell[BoxData[ FormBox[ RowBox[{"n", "=", "1"}], TraditionalForm]]], ", we are in the setting of univariate polynomials (since ", Cell[BoxData[ FormBox["y", TraditionalForm]]], " is now equivalent to the constant ", Cell[BoxData[ FormBox[ SubscriptBox["y", "0"], TraditionalForm]], FontSlant->"Italic"], "). Since ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["h", "0"], "=", RowBox[{"h", "(", RowBox[{"x", ",", SubscriptBox["y", "0"]}], ")"}]}], TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["k", "0"], "=", RowBox[{"k", "(", RowBox[{"x", ",", SubscriptBox["y", "0"]}], ")"}]}], TraditionalForm]]], " are univariate and relatively prime, the extended gcd provides cofactors \ ", Cell[BoxData[ FormBox[ RowBox[{"a", "(", "x", ")"}], TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ RowBox[{"b", "(", "x", ")"}], TraditionalForm]]], " with ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ RowBox[{"a", " ", SubscriptBox["h", "0"]}], "+", RowBox[{"b", " ", SubscriptBox["k", "0"]}]}], "=", "1"}], TraditionalForm]]], ". Thus ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ RowBox[{ RowBox[{"a", "(", "x", ")"}], " ", RowBox[{ SubscriptBox["f", "1"], "(", RowBox[{"x", ",", SubscriptBox["y", "0"]}], ")"}]}], "+", RowBox[{"b", " ", RowBox[{"(", "x", ")"}], RowBox[{ SubscriptBox["f", "2"], "(", RowBox[{"x", ",", SubscriptBox["y", "0"]}], ")"}]}]}], "=", RowBox[{"g", "(", RowBox[{"x", ",", SubscriptBox["y", "0"]}], ")"}]}], TraditionalForm]]], ", proving that ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["J", "1"], "\[Subset]", SubscriptBox["I", "1"]}], TraditionalForm]]], "." }], "Text", CellChangeTimes->{{3.42452811913512*^9, 3.424528139608398*^9}, { 3.424528190221381*^9, 3.424528216310694*^9}, {3.424528255009347*^9, 3.424528461275776*^9}, {3.424528502370579*^9, 3.424528526112725*^9}, { 3.424528557628558*^9, 3.424528558504472*^9}, {3.424528590700718*^9, 3.424528693835107*^9}, {3.424528926333666*^9, 3.424529029192378*^9}, { 3.424529063462033*^9, 3.424529102522277*^9}, {3.424529135220736*^9, 3.424529169533254*^9}, {3.424529435888392*^9, 3.42452964091805*^9}, { 3.424529678716751*^9, 3.424529804705935*^9}, {3.424530348822065*^9, 3.424530367781485*^9}, {3.424530560178724*^9, 3.424530575981175*^9}, { 3.424530610241608*^9, 3.424530683080148*^9}, {3.424530758968811*^9, 3.424530793187221*^9}, 3.424530834111071*^9, {3.424530890894031*^9, 3.424530938934945*^9}, {3.424530980830501*^9, 3.424531058138593*^9}, { 3.424531126906092*^9, 3.424531155088753*^9}, {3.424531379879531*^9, 3.424531394599464*^9}, {3.424531454614708*^9, 3.424531576801112*^9}, { 3.424531664783693*^9, 3.424531723307459*^9}, 3.424532008533517*^9, { 3.424555833299421*^9, 3.424555862480799*^9}, 3.424555971389154*^9, 3.424727948426056*^9, {3.442582042114736*^9, 3.44258209358819*^9}, { 3.484062868753871*^9, 3.484062895377632*^9}}], Cell[TextData[{ "Now we assume the result for ", Cell[BoxData[ FormBox["n", TraditionalForm]]], " and look at the case ", Cell[BoxData[ FormBox[ RowBox[{"n", "+", "1"}], TraditionalForm]]], ". Since by assumption ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["I", "n"], "=", SubscriptBox["J", "n"]}], TraditionalForm]]], ", there exist (bivariate) polynomials ", Cell[BoxData[ FormBox[ RowBox[{"s", ",", "t"}], TraditionalForm]]], " with ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ RowBox[{"s", " ", SubscriptBox["f", "1"]}], "+", RowBox[{"t", " ", SubscriptBox["f", "2"]}]}], "\[Congruent]", "g", " "}], TraditionalForm]]], " modulo ", Cell[BoxData[ FormBox[ SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "n"], TraditionalForm]], FontSlant->"Italic"], ". Multiplying through by ", Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], TraditionalForm]], FontSlant->"Italic"], " we see that ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"g", "(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "\[Element]", SubscriptBox["I", RowBox[{"n", "+", "1"}]]}], TraditionalForm]]], ". The extended gcd above implies the existence of ", Cell[BoxData[ FormBox[ RowBox[{"w", "(", RowBox[{"x", ",", "y"}], ")"}], TraditionalForm]]], " such that ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ RowBox[{"a", " ", "h"}], "+", RowBox[{"b", " ", "k"}], "+", RowBox[{"w", " ", RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}]}]}], "=", "1"}], TraditionalForm]]], " (since by construction ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ RowBox[{"a", " ", "h"}], "+", RowBox[{"b", " ", "k"}]}], "=", RowBox[{"1", "+", "p"}]}], TraditionalForm]]], " where ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], StyleBox["\[VerticalBar]", FontSlant->"Plain"], "p"}], TraditionalForm]], FontSlant->"Italic"], "). Thus ", Cell[BoxData[ FormBox[ RowBox[{"g", "=", RowBox[{ RowBox[{"g", " ", RowBox[{"(", RowBox[{ RowBox[{"a", " ", "h"}], "+", RowBox[{"b", " ", "k"}], "+", RowBox[{"w", " ", RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}]}]}], ")"}]}], "=", RowBox[{ RowBox[{ RowBox[{"a", " ", SubscriptBox["f", "1"]}], "+", RowBox[{"b", " ", SubscriptBox["f", "2"]}], "+", RowBox[{ RowBox[{"(", RowBox[{"w", " ", "g"}], ")"}], RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}]}]}], "\[Element]", SubscriptBox["I", RowBox[{"n", "+", "1"}]]}]}]}], TraditionalForm]]], ", showing the inclusion ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["J", RowBox[{"n", "+", "1"}]], "\[Subset]", SubscriptBox["I", RowBox[{"n", "+", "1"}]]}], TraditionalForm]]], ". \[EmptySquare]" }], "Text", CellChangeTimes->{{3.42452811913512*^9, 3.424528139608398*^9}, { 3.424528190221381*^9, 3.424528216310694*^9}, {3.424528255009347*^9, 3.424528461275776*^9}, {3.424528502370579*^9, 3.424528526112725*^9}, { 3.424528557628558*^9, 3.424528558504472*^9}, {3.424528590700718*^9, 3.424528693835107*^9}, {3.424528926333666*^9, 3.424529029192378*^9}, { 3.424529063462033*^9, 3.424529102522277*^9}, {3.424529135220736*^9, 3.424529169533254*^9}, {3.424529435888392*^9, 3.42452964091805*^9}, { 3.424529678716751*^9, 3.424529804705935*^9}, {3.424530348822065*^9, 3.424530367781485*^9}, {3.424530560178724*^9, 3.424530575981175*^9}, { 3.424530610241608*^9, 3.424530683080148*^9}, {3.424530758968811*^9, 3.424530793187221*^9}, 3.424530834111071*^9, {3.424530890894031*^9, 3.424530938934945*^9}, {3.424530980830501*^9, 3.424531058138593*^9}, { 3.424531126906092*^9, 3.424531155088753*^9}, {3.424531379879531*^9, 3.424531394599464*^9}, {3.424531454614708*^9, 3.424531576801112*^9}, { 3.424531664783693*^9, 3.424531723307459*^9}, 3.424532008533517*^9, { 3.424555833299421*^9, 3.424555833611495*^9}, {3.442089993226137*^9, 3.4420899932262897`*^9}, {3.442582100167141*^9, 3.4425821391473083`*^9}, { 3.4840629670496197`*^9, 3.484062967049696*^9}, {3.493147654322953*^9, 3.493147753303751*^9}, {3.493147784111771*^9, 3.493147815388722*^9}, { 3.500230914036881*^9, 3.5002309179995213`*^9}, 3.500231043697209*^9}], Cell[TextData[{ StyleBox["Proposition 2. Suppose ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"g", ",", "h", ",", "k", ",", SubscriptBox["y", "0"]}], TraditionalForm]], FontSlant->"Italic"], StyleBox[" satisfy the same hypotheses as in proposition 1. Suppose moreover \ that ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["deg", "x"], "(", "g", ")"}], TraditionalForm]]], StyleBox[" is ", FontSlant->"Italic"], Cell[BoxData[ FormBox["m", TraditionalForm]]], StyleBox[" and ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"deg", RowBox[{"(", "g", ")"}]}], TraditionalForm]]], StyleBox[" is ", FontSlant->"Italic"], Cell[BoxData[ FormBox["n", TraditionalForm]]], ", ", StyleBox["where", FontSlant->"Italic"], " ", Cell[BoxData[ FormBox[ RowBox[{"deg", "(", "p", ")"}], TraditionalForm]]], StyleBox[" is the total degree of p. Also we now assume the content of ", FontSlant->"Italic"], Cell[BoxData[ FormBox["g", TraditionalForm]]], " ", StyleBox["with respect to", FontSlant->"Italic"], " ", Cell[BoxData[ FormBox["x", TraditionalForm]]], " ", StyleBox["is 1 (that is, ", FontSlant->"Italic"], Cell[BoxData[ FormBox["g", TraditionalForm]]], " ", StyleBox["has no factor in ", FontSlant->"Italic"], Cell[BoxData[ FormBox["y", TraditionalForm]], FontSlant->"Italic"], StyleBox[" alone). For any positive integer ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"r", ">", RowBox[{"\[LeftCeiling]", RowBox[{ SuperscriptBox["n", "2"], "/", "m"}], "\[RightCeiling]"}]}], TraditionalForm]]], ", ", StyleBox["let ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ SubscriptBox["G", "r"], TraditionalForm]], FontSlant->"Italic"], StyleBox[" be a Gr\[ODoubleDot]bner basis for the ideal ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["I", "r"], "=", RowBox[{"(", RowBox[{ SubscriptBox["f", "1"], ",", SubscriptBox["f", "2"], ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "r"]}], ")"}]}], TraditionalForm]], FontSlant->"Italic"], " ", StyleBox["with graded lexicographic term order using variable order ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"x", "\[Succeeds]", "y"}], TraditionalForm]], FontSlant->"Italic"], StyleBox[". Let ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ OverscriptBox["g", "~"], TraditionalForm]], FontSlant->"Italic"], StyleBox[" be the minimal polynomial in ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ SubscriptBox["G", "r"], TraditionalForm]], FontSlant->"Italic"], StyleBox[" with respect to this term order. Then ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ OverscriptBox["g", "~"], TraditionalForm]], FontSlant->"Italic"], StyleBox[" is an associate of ", FontSlant->"Italic"], Cell[BoxData[ FormBox["g", TraditionalForm]], FontSlant->"Italic"], StyleBox[", that is, it is a gcd of ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{ SubscriptBox["f", "1"], ",", SubscriptBox["f", "2"]}], ")"}], TraditionalForm]], FontSlant->"Italic"], StyleBox[".", FontSlant->"Italic"] }], "Text", CellChangeTimes->{{3.424527425152877*^9, 3.424527429780294*^9}, { 3.42452746751133*^9, 3.424527527259339*^9}, {3.424527561578621*^9, 3.424527682890602*^9}, {3.424527847773325*^9, 3.424528103706303*^9}, { 3.424529118433184*^9, 3.424529124448483*^9}, {3.424531845770582*^9, 3.424532221414685*^9}, 3.424532446516041*^9, {3.424555929273253*^9, 3.424555937188304*^9}, {3.424556318473748*^9, 3.424556319639382*^9}, { 3.424556556966494*^9, 3.424556784283341*^9}, {3.424603779173373*^9, 3.424603785000476*^9}, {3.424603876059354*^9, 3.424603975048443*^9}, { 3.424604738924598*^9, 3.424604753412756*^9}, {3.424605059588866*^9, 3.424605088940386*^9}, {3.424728291002764*^9, 3.424728306518486*^9}, { 3.424729689279122*^9, 3.424729703945363*^9}, {3.4425821724843187`*^9, 3.442582203435707*^9}}], Cell[TextData[{ "Note that this simply means ", Cell[BoxData[ FormBox["g", TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ OverscriptBox["g", "~"], TraditionalForm]], FontSlant->"Italic"], " agree up to invertible factor which, in our setting, would be a nonzero \ rational number. The greatest common divisor is of course only unique up to \ such factors." }], "Text", CellChangeTimes->{{3.4245322663717*^9, 3.424532434868787*^9}, { 3.424547960211215*^9, 3.42454796769985*^9}, {3.424555930826845*^9, 3.424555933887556*^9}, {3.442422594368368*^9, 3.442422598766225*^9}}], Cell[TextData[{ "Proof. We adapt an argument from [", CounterBox["Reference", "Noro Yokoyama"], "], based on sizes of certain zero sets. Suppose there is a polynomial ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["g", "2"], "\[Element]", SubscriptBox["G", "r"]}], TraditionalForm]]], " with leading power product strictly smaller than that of ", Cell[BoxData[ FormBox["g", TraditionalForm]]], ". We take ", Cell[BoxData[ FormBox[ SubscriptBox["g", "2"], TraditionalForm]]], " to be of minimal degree. Let ", Cell[BoxData[ FormBox[ SubscriptBox["I", SubscriptBox["g", "2"]], TraditionalForm]]], "denote the ideal ", Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{"g", ",", SubscriptBox["g", "2"]}], ")"}], TraditionalForm]]], ". Let ", Cell[BoxData[ FormBox["\[NumberSign]I", TraditionalForm]]], " denote the cardinality of the zero set, counted by multiplicity, of a \ finite ideal ", Cell[BoxData[ FormBox["I", TraditionalForm]]], "." }], "Text", CellChangeTimes->{{3.42453244935241*^9, 3.424532450365612*^9}, { 3.424547934484839*^9, 3.424548121337901*^9}, {3.424548232945627*^9, 3.4245484894895*^9}, {3.424555964743417*^9, 3.42455596508633*^9}, { 3.424556887815327*^9, 3.424556887833931*^9}, {3.424556918583295*^9, 3.424556920819675*^9}, {3.424557757473202*^9, 3.42455776498383*^9}, { 3.424604044239848*^9, 3.424604082555238*^9}, {3.424604113599456*^9, 3.424604125884527*^9}, {3.424604195148975*^9, 3.424604271800761*^9}, { 3.424604304926089*^9, 3.424604389782183*^9}, 3.424604481507595*^9, { 3.424604525929035*^9, 3.424604703329667*^9}, {3.424604765589402*^9, 3.424604881827567*^9}, {3.42460513750265*^9, 3.424605240343622*^9}, { 3.424607226238463*^9, 3.424607241967336*^9}, {3.424640643969398*^9, 3.424640660193311*^9}, 3.424640719680221*^9, {3.424728347622243*^9, 3.424728490986002*^9}, {3.424729386558318*^9, 3.424729579753125*^9}, { 3.424729621380651*^9, 3.424729634932181*^9}, 3.442090206836206*^9, { 3.442580981001652*^9, 3.4425810583450108`*^9}, {3.4700707240397587`*^9, 3.470070724039912*^9}, {3.4931321095085707`*^9, 3.493132132083379*^9}, { 3.493146595336136*^9, 3.493146625432745*^9}, {3.493146701391367*^9, 3.4931467024693117`*^9}}], Cell[TextData[{ "We first claim we do not have ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["g", "2"], "\[VerticalBar]", "g"}], TraditionalForm]]], ". If that happened we would have ", Cell[BoxData[ FormBox[ RowBox[{"g", "=", RowBox[{ SubscriptBox["g", "2"], " ", SubscriptBox["g", "3"]}]}], TraditionalForm]]], " for some ", Cell[BoxData[ FormBox[ SubscriptBox["g", "3"], TraditionalForm]]], " a nontrivial polynomial in ", Cell[BoxData[ FormBox["x", TraditionalForm]]], " (recall ", Cell[BoxData[ FormBox["g", TraditionalForm]]], " is assumed primitive in ", Cell[BoxData[ FormBox["x", TraditionalForm]]], "). Hence ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"\[NumberSign]", "(", RowBox[{ SubscriptBox["g", "3"], ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "r"]}], ")"}], ">", "0"}], TraditionalForm]]], ", and it follows that ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"\[NumberSign]", "(", RowBox[{ SubscriptBox["g", "2"], ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "r"]}], ")"}], "<", SubscriptBox["\[NumberSign]I", "r"]}], TraditionalForm]]], ". But ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["g", "2"], "\[Element]", SubscriptBox["G", "r"]}], TraditionalForm]]], " implies ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["g", "2"], "\[Element]", SubscriptBox["I", "r"]}], TraditionalForm]]], " and divisibility of ", Cell[BoxData[ FormBox["g", TraditionalForm]]], " by ", Cell[BoxData[ FormBox[ SubscriptBox["g", "2"], TraditionalForm]]], " would further imply ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"(", RowBox[{ SubscriptBox["g", "2"], ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "r"]}], ")"}], "=", RowBox[{ RowBox[{"(", RowBox[{"g", ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "r"]}], ")"}], "=", SubscriptBox["I", "r"]}]}], TraditionalForm]]], ", contradicting the size inequality." }], "Text", CellChangeTimes->{{3.42453244935241*^9, 3.424532450365612*^9}, { 3.424547934484839*^9, 3.424548121337901*^9}, {3.424548232945627*^9, 3.4245484894895*^9}, {3.424555964743417*^9, 3.42455596508633*^9}, { 3.424556887815327*^9, 3.424556887833931*^9}, {3.424556918583295*^9, 3.424556920819675*^9}, {3.424557757473202*^9, 3.42455776498383*^9}, { 3.424604044239848*^9, 3.424604082555238*^9}, {3.424604113599456*^9, 3.424604125884527*^9}, {3.424604195148975*^9, 3.424604271800761*^9}, { 3.424604304926089*^9, 3.424604389782183*^9}, 3.424604481507595*^9, { 3.424604525929035*^9, 3.424604703329667*^9}, {3.424604765589402*^9, 3.424604881827567*^9}, {3.42460513750265*^9, 3.424605240343622*^9}, { 3.424607226238463*^9, 3.424607241967336*^9}, {3.424640643969398*^9, 3.424640660193311*^9}, 3.424640719680221*^9, {3.424728347622243*^9, 3.424728490986002*^9}, {3.424729386558318*^9, 3.424729579753125*^9}, { 3.424729621380651*^9, 3.424729634905682*^9}, {3.424729715589151*^9, 3.424729784046327*^9}, {3.424730023594277*^9, 3.424730101873569*^9}, { 3.424730147666874*^9, 3.42473015242146*^9}, {3.424730194949259*^9, 3.424730234259508*^9}, {3.4420900421050158`*^9, 3.442090065010051*^9}, { 3.442090117889207*^9, 3.44209011931859*^9}, {3.4420902365440493`*^9, 3.4420902606428223`*^9}, {3.442090301899276*^9, 3.442090553635655*^9}, { 3.442090620106933*^9, 3.44209066446741*^9}, {3.442090782937337*^9, 3.442090985335923*^9}, {3.469804978877615*^9, 3.469804978877754*^9}, { 3.469805012733585*^9, 3.4698050127358017`*^9}, {3.4700703606716957`*^9, 3.4700703654438877`*^9}, {3.4700707182495604`*^9, 3.470070729326425*^9}, { 3.493131317129974*^9, 3.493131327536709*^9}}], Cell[TextData[{ "As ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["g", "2"], "\[NotVerticalBar]", "g"}], TraditionalForm]]], ", the gcd of ", Cell[BoxData[ FormBox[ SubscriptBox["g", "2"], TraditionalForm]]], " and ", Cell[BoxData[ FormBox["g", TraditionalForm]]], " (call it ", Cell[BoxData[ FormBox[ SubscriptBox["g", "4"], TraditionalForm]], FontSlant->"Italic"], ") must be of lower degree than ", Cell[BoxData[ FormBox[ SubscriptBox["g", "2"], TraditionalForm]]], ". Replacing ", Cell[BoxData[ FormBox[ RowBox[{"{", RowBox[{ SubscriptBox["f", "1"], ",", SubscriptBox["f", "2"]}], "}"}], TraditionalForm]], FontSlant->"Italic"], " by ", Cell[BoxData[ FormBox[ RowBox[{"{", RowBox[{"g", ",", SubscriptBox["g", "2"]}], "}"}], TraditionalForm]], FontSlant->"Italic"], " in proposition 1, we see that ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["g", "4"], "\[Element]", SubscriptBox["I", "r"]}], TraditionalForm]], FontSlant->"Italic"], ". This contradicts the minimality of leading term of ", Cell[BoxData[ FormBox[ SubscriptBox["g", "2"], TraditionalForm]]], ".", " \[EmptySquare]" }], "Text", CellChangeTimes->{{3.4931318397965193`*^9, 3.49313187575145*^9}, { 3.493131980486526*^9, 3.493132000820858*^9}, {3.493132040372673*^9, 3.4931320406916647`*^9}, {3.493132545099531*^9, 3.4931325462482023`*^9}, { 3.4931328708845654`*^9, 3.493133039373502*^9}, {3.493133076141203*^9, 3.493133121252737*^9}, {3.493133220073196*^9, 3.493133220456458*^9}, { 3.493146356297974*^9, 3.493146502600915*^9}, {3.4931465457619133`*^9, 3.493146568498554*^9}, {3.493146664934207*^9, 3.493146668373661*^9}}], Cell[TextData[{ "Observe that a generic linear change of coordinates (that is, a shear \ transformation of the form ", Cell[BoxData[ FormBox[ RowBox[{"y", "\[Rule]", RowBox[{"y", "+", RowBox[{"a", " ", "x"}]}]}], TraditionalForm]]], ") will make ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ SubscriptBox["deg", "x"], "(", "g", ")"}], "=", "n"}], TraditionalForm]]], ". This means there will be a pure term in ", Cell[BoxData[ FormBox["x", TraditionalForm]]], " of maximal (total) degree. In this situation we can use a \ Gr\[ODoubleDot]bner basis for the ideal ", Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{ SubscriptBox["f", "1"], ",", SubscriptBox["f", "2"], ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], RowBox[{"n", "+", "1"}]]}], ")"}], TraditionalForm]], FontSlant->"Italic"], ", and we can learn the value for ", Cell[BoxData[ FormBox["n", TraditionalForm]]], " from the univariate polynomial ", Cell[BoxData[ FormBox[ RowBox[{"gcd", "(", RowBox[{ RowBox[{ SubscriptBox["f", "1"], "(", RowBox[{"x", ",", SubscriptBox["y", "0"]}], ")"}], ",", RowBox[{ SubscriptBox["f", "2"], "(", RowBox[{"x", ",", SubscriptBox["y", "0"]}], ")"}]}], ")"}], TraditionalForm]]], ". There is now, moreover, a simpler proof of proposition 2. If the leading \ power product of ", Cell[BoxData[ FormBox["g", TraditionalForm]], FontSlant->"Italic"], ", in the specified term order, is ", Cell[BoxData[ FormBox[ SuperscriptBox["x", "n"], TraditionalForm]]], ", then the gcd of the leading power products of ", Cell[BoxData[ FormBox["g", TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], RowBox[{"n", "+", "1"}]], TraditionalForm]]], " is 1. Hence by the Buchberger criterion on independent leading terms, ", Cell[BoxData[ FormBox[ RowBox[{"{", RowBox[{"g", ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], RowBox[{"n", "+", "1"}]]}], "}"}], TraditionalForm]]], " is a Gr\[ODoubleDot]bner basis. As all terms in ", Cell[BoxData[ FormBox["g", TraditionalForm]]], " are of degree no larger than ", Cell[BoxData[ FormBox["n", TraditionalForm]]], ", neither polynomial can be used to reduce the other. Thus this basis is \ reduced." }], "Text", CellChangeTimes->{{3.42453244935241*^9, 3.424532450365612*^9}, { 3.424547934484839*^9, 3.424548121337901*^9}, {3.424548232945627*^9, 3.4245484894895*^9}, {3.424555964743417*^9, 3.42455596508633*^9}, { 3.424556887815327*^9, 3.424556887833931*^9}, {3.424556918583295*^9, 3.424556920819675*^9}, {3.424557757473202*^9, 3.42455776498383*^9}, { 3.424604044239848*^9, 3.424604048898713*^9}, {3.424641106729128*^9, 3.424641190966347*^9}, {3.424641800773697*^9, 3.424641801382815*^9}, { 3.442348670007996*^9, 3.442348670008156*^9}, {3.442582228013094*^9, 3.442582265248191*^9}, {3.443359526129839*^9, 3.443359528608993*^9}, { 3.487427867307548*^9, 3.487427867822646*^9}, {3.487427949324512*^9, 3.487427951932048*^9}, {3.492901361629609*^9, 3.4929014436755466`*^9}, { 3.49313363448872*^9, 3.493133637461791*^9}}], Cell["\<\ These propositions taken together give the results we will use in the sequel. \ We first state the general case.\ \>", "Text", CellChangeTimes->{{3.424555901940466*^9, 3.424555917602568*^9}, { 3.424556412158963*^9, 3.424556422294021*^9}, {3.424556879614915*^9, 3.424556880670506*^9}, 3.424641314293037*^9, {3.4246416509217*^9, 3.424641656744911*^9}, {3.424641804155698*^9, 3.424641805513075*^9}}], Cell[TextData[{ StyleBox["Theorem 2. Suppose we have ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["f", "1"], "=", RowBox[{"g", " ", "h"}]}], TraditionalForm]], FontSlant->"Italic"], StyleBox[" and ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["f", "2"], "=", RowBox[{"g", " ", "k"}]}], TraditionalForm]], FontSlant->"Italic"], StyleBox[" with ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"g", ",", "h", ",", "k"}], TraditionalForm]], FontSlant->"Italic"], StyleBox[" bivariate polynomials in ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"\[DoubleStruckCapitalQ]", "[", RowBox[{"x", ",", "y"}], "]"}], TraditionalForm]], FontSlant->"Italic"], StyleBox[", and ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"h", ",", "k"}], TraditionalForm]], FontSlant->"Italic"], StyleBox[" relatively prime. Suppose ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["y", "0"], "\[Element]", "\[DoubleStruckCapitalQ]"}], TraditionalForm]], FontSlant->"Italic"], StyleBox[" is a value satisfying the three generic conditions from the \ hypotheses of proposition 1. Suppose ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"min", "(", RowBox[{ RowBox[{"deg", "(", SubscriptBox["f", "1"], ")"}], ",", RowBox[{"deg", "(", SubscriptBox["f", "2"], ")"}]}], ")"}], TraditionalForm]]], StyleBox[" is ", FontSlant->"Italic"], Cell[BoxData[ FormBox["n", TraditionalForm]]], ".", StyleBox[" Then the minimal polynomial in the Gr\[ODoubleDot]bner basis for ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{ SubscriptBox["f", "1"], ",", SubscriptBox["f", "2"], ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], RowBox[{ SuperscriptBox["n", "2"], "+", "1"}]]}], ")"}], TraditionalForm]], FontSlant->"Italic"], ", ", StyleBox["computed with respect to", FontSlant->"Italic"], " ", StyleBox["the graded lexicographic term order using variable order ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"x", "\[Succeeds]", "y"}], TraditionalForm]], FontSlant->"Italic"], ", ", StyleBox["is a gcd of the pair ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"{", RowBox[{ RowBox[{ SubscriptBox["f", "1"], "(", RowBox[{"x", ",", "y"}], ")"}], ",", RowBox[{ SubscriptBox["f", "2"], "(", RowBox[{"x", ",", "y"}], ")"}]}], "}"}], TraditionalForm]]], ".", StyleBox[" Letting ", FontSlant->"Italic"], Cell[BoxData[ FormBox["m", TraditionalForm]]], " ", StyleBox["be", FontSlant->"Italic"], " ", StyleBox["the degree in ", FontSlant->"Italic"], Cell[BoxData[ FormBox["x", TraditionalForm]]], " ", StyleBox["of the univariate polynomial ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"gcd", "(", RowBox[{ RowBox[{ SubscriptBox["f", "1"], "(", RowBox[{"x", ",", SubscriptBox["y", "0"]}], ")"}], ",", RowBox[{ SubscriptBox["f", "2"], "(", RowBox[{"x", ",", SubscriptBox["y", "0"]}], ")"}]}], ")"}], TraditionalForm]]], ",", StyleBox[" we can instead use the (in general smaller) exponent ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"\[LeftCeiling]", RowBox[{ SuperscriptBox["n", "2"], "/", "m"}], "\[RightCeiling]"}], "+", "1"}], TraditionalForm]]], "." }], "Text", CellChangeTimes->{{3.424555918856609*^9, 3.424555924848452*^9}, { 3.42455599040479*^9, 3.424556193779849*^9}, {3.424556235583014*^9, 3.424556389624483*^9}, {3.424556447708821*^9, 3.424556480394339*^9}, { 3.424556511499033*^9, 3.424556525397275*^9}, 3.424556728571164*^9, { 3.424556806198687*^9, 3.424556837823098*^9}, {3.424641253042635*^9, 3.424641291293545*^9}, {3.424641612875252*^9, 3.424641615551548*^9}, { 3.424641684820747*^9, 3.424641829227029*^9}, {3.424642024453619*^9, 3.424642045417225*^9}, {3.442581874315033*^9, 3.442581950362061*^9}, { 3.4433595129356327`*^9, 3.443359515026167*^9}, {3.484063384600507*^9, 3.4840634357925177`*^9}}], Cell[TextData[{ "An important special case, immediate from the observation following the \ proof of proposition 2, is that after generic change of coordinates we may \ use the (in general smaller) exponent ", Cell[BoxData[ FormBox[ RowBox[{"n", "+", "1"}], TraditionalForm]]], ". Moreover we can deduce that value from the degree of the univariate \ greatest common divisor obtained by a generic substitution value ", Cell[BoxData[ FormBox[ SubscriptBox["y", "0"], TraditionalForm]], FontSlant->"Italic"], "." }], "Text", CellChangeTimes->{{3.424641847415557*^9, 3.424641889012324*^9}, { 3.424641929876748*^9, 3.424641951216499*^9}, {3.424642070660893*^9, 3.4246420732789*^9}, {3.442091026663473*^9, 3.442091026663631*^9}, { 3.442429787804771*^9, 3.442429853693519*^9}, {3.443359467193069*^9, 3.443359502589859*^9}}], Cell[TextData[{ StyleBox["Theorem 3. Again using the hypotheses of Theorem 2, suppose we \ perform a generic linear change of coordinates. Suppose moreover that the \ degree of (the univariate) ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"gcd", "(", RowBox[{ RowBox[{ SubscriptBox["f", "1"], "(", RowBox[{"x", ",", SubscriptBox["y", "0"]}], ")"}], ",", RowBox[{ SubscriptBox["f", "2"], "(", RowBox[{"x", ",", SubscriptBox["y", "0"]}], ")"}]}], ")"}], TraditionalForm]]], " ", StyleBox["is", FontSlant->"Italic"], " ", Cell[BoxData[ FormBox["n", TraditionalForm]]], ".", StyleBox[" Then the smallest polynomial in the Gr\[ODoubleDot]bner basis for \ ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{ SubscriptBox["f", "1"], ",", SubscriptBox["f", "2"], ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], RowBox[{"n", " ", "+", "1"}]]}], ")"}], TraditionalForm]], FontSlant->"Italic"], StyleBox[", computed with respect to the term order of theorem 2, is a gcd \ of the pair {", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ SubscriptBox["f", "1"], ",", SubscriptBox["f", "2"]}], "}"}], TraditionalForm]]], "." }], "Text", CellChangeTimes->{{3.424555918856609*^9, 3.424555924848452*^9}, { 3.42455599040479*^9, 3.424556193779849*^9}, {3.424556235583014*^9, 3.424556389624483*^9}, {3.424556447708821*^9, 3.424556480394339*^9}, { 3.424556511499033*^9, 3.424556525397275*^9}, 3.424556728571164*^9, { 3.424556806198687*^9, 3.424556837823098*^9}, {3.424641253042635*^9, 3.424641291293545*^9}, {3.424641343386732*^9, 3.424641633137178*^9}, { 3.424641915420931*^9, 3.424641924550025*^9}, {3.442091041222282*^9, 3.442091047400441*^9}, {3.442091116392744*^9, 3.442091116392873*^9}, 3.442341599207653*^9, {3.442581962252267*^9, 3.442581987341358*^9}}], Cell["\<\ It should be mentioned that this generic change is not disasterous for the \ computations. While general experience with Gr\[ODoubleDot]bner bases \ suggests that sets of sparse polynomial are more efficiently handled than \ their dense counterparts, we have two things in our favor. One is that we are \ in a bivariate setting, hence the number of monomials for a given total \ degree grows only quadratically. The other is that we will not suffer from \ explosive coefficient growth (either from the basis change itself, or in the \ process of computing the required Gr\[ODoubleDot]bner basis), since we work \ in finite precision. Nevertheless, it remains to be determined whether the \ benefits of reducing the necessary lifting degree outweighs the possible loss \ of efficiency from making the input dense. Empirical evidence suggests that \ it does, but this is by no means definitive.\ \>", "Text", CellChangeTimes->{{3.492533416680338*^9, 3.492533420644847*^9}, 3.500232244710679*^9, {3.5002322924723253`*^9, 3.5002322926604*^9}}] }, Open ]], Cell[CellGroupData[{ Cell[TextData[{ Cell[TextData[{ StyleBox[ CounterBox["Section"], "SectionNumber"], StyleBox[". ", "SectionNumber"] }], "SectionDingbat"], "BIVARIATE FACTORIZATION" }], "Section", CellChangeTimes->{{3.407171809947496*^9, 3.407171844310016*^9}, { 3.407172024813134*^9, 3.407172040605009*^9}, {3.40717902284139*^9, 3.407179040891735*^9}, {3.419964899502602*^9, 3.419964901274152*^9}, { 3.424523707949821*^9, 3.424523726754684*^9}, 3.42452456603162*^9, { 3.424532550900259*^9, 3.424532554459798*^9}}], Cell[TextData[{ "We use the following setup throughout this section. We are given a square \ free bivariate polynomial ", Cell[BoxData[ FormBox[ RowBox[{"f", "(", RowBox[{"x", ",", "y"}], ")"}], TraditionalForm]]], " over the rationals, and a value ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["y", "0"], "\[Element]", "\[DoubleStruckCapitalQ]"}], TraditionalForm]], FontSlant->"Italic"], " such that ", StyleBox[Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "\[NotVerticalBar]", "f"}], TraditionalForm]], "Text"], "Text"], StyleBox[". We assume ", "Text"], Cell[BoxData[ FormBox["f", TraditionalForm]]], " has no factors in ", Cell[BoxData[ FormBox["y", TraditionalForm]]], " alone.", StyleBox[" Let ", "Text"], Cell[BoxData[ FormBox[ SubscriptBox["x", "0"], TraditionalForm]]], StyleBox[" be ", "Text"], "a root of ", Cell[BoxData[ FormBox[ RowBox[{"f", "(", RowBox[{"x", ",", SubscriptBox["y", "0"]}], ")"}], TraditionalForm]]], ", that is, ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"f", "(", RowBox[{ SubscriptBox["x", "0"], ",", SubscriptBox["y", "0"]}], ")"}], "=", "0"}], TraditionalForm]]], ". Again we assume ", Cell[BoxData[ FormBox[ SubscriptBox["y", "0"], TraditionalForm]]], " is generic, specifically ", Cell[BoxData[ FormBox[ RowBox[{"f", "(", RowBox[{"x", ",", SubscriptBox["y", "0"]}], ")"}], TraditionalForm]]], " has the same degree in ", Cell[BoxData[ FormBox["x", TraditionalForm]]], " as ", Cell[BoxData[ FormBox[ RowBox[{"f", "(", RowBox[{"x", ",", "y"}], ")"}], TraditionalForm]]], ", and it remains square free. We will note other generic requirements as we \ proceed. Let ", Cell[BoxData[ FormBox[ RowBox[{"g", "(", RowBox[{"x", ",", "y"}], ")"}], TraditionalForm]]], " be the irreducible factor of ", Cell[BoxData[ FormBox[ RowBox[{"f", "(", RowBox[{"x", ",", "y"}], ")"}], TraditionalForm]]], " in ", Cell[BoxData[ FormBox[ RowBox[{"\[DoubleStruckCapitalK]", "[", RowBox[{"x", ",", "y"}], "]"}], TraditionalForm]]], " for which ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"g", "(", RowBox[{ SubscriptBox["x", "0"], ",", SubscriptBox["y", "0"]}], ")"}], "=", "0"}], TraditionalForm]]], ". By \[DoubleStruckCapitalK] we allow for working over the rationals ", Cell[BoxData[ FormBox["\[DoubleStruckCapitalQ]", TraditionalForm]]], " or their algebraic closure ", Cell[BoxData[ FormBox[ OverscriptBox["\[DoubleStruckCapitalQ]", "_"], TraditionalForm]]], " or (a numeric approximation to) the complex numbers ", Cell[BoxData[ FormBox["\[DoubleStruckCapitalC]", TraditionalForm]]], ". Let ", Cell[BoxData[ FormBox[ SubscriptBox["g", "0"], TraditionalForm]]], " denote ", Cell[BoxData[ FormBox[ RowBox[{"g", "(", RowBox[{"x", ",", SubscriptBox["y", "0"]}], ")"}], TraditionalForm]]], "; here we impose the generic condition on ", Cell[BoxData[ FormBox[ SubscriptBox["y", "0"], TraditionalForm]]], " that ", Cell[BoxData[ FormBox["g", TraditionalForm]], FormatType->"TraditionalForm"], " and ", Cell[BoxData[ FormBox[ SubscriptBox["g", "0"], TraditionalForm]]], " have the same degree in ", Cell[BoxData[ FormBox["x", TraditionalForm]], FormatType->"TraditionalForm"], ". For each positive integer ", Cell[BoxData[ FormBox["n", TraditionalForm]]], " we define ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["I", "n"], "=", RowBox[{"(", RowBox[{"f", ",", SuperscriptBox[ SubscriptBox["g", "0"], "n"], ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "n"]}], ")"}]}], TraditionalForm]]], Cell[BoxData[Cell[""]], FontSlant->"Italic"], "." }], "Text", CellChangeTimes->{ 3.423860191223595*^9, {3.424527265013681*^9, 3.424527266325133*^9}, { 3.424715036332122*^9, 3.424715067304907*^9}, {3.42471522424516*^9, 3.424715224477611*^9}, {3.424716128916116*^9, 3.424716131134092*^9}, { 3.424716208881272*^9, 3.42471627428341*^9}, {3.424730618561468*^9, 3.424730618561682*^9}, {3.442089741340384*^9, 3.442089752495625*^9}, { 3.44233666363632*^9, 3.442336673353858*^9}, {3.442338521447554*^9, 3.4423385413014812`*^9}, {3.442344126052002*^9, 3.442344141400113*^9}, { 3.442344350778192*^9, 3.4423443520557747`*^9}, {3.442429890637233*^9, 3.442429938904516*^9}, {3.500390842040986*^9, 3.5003908604706697`*^9}, { 3.50039090213006*^9, 3.5003909464092293`*^9}}], Cell[TextData[{ StyleBox["Theorem 4. For all ", FontSlant->"Italic"], Cell[BoxData[ FormBox["n", TraditionalForm]]], " ", StyleBox["we have ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"g", "\[Element]", SubscriptBox["I", "n"]}], TraditionalForm]], FontSlant->"Italic"], StyleBox[".", FontSlant->"Italic"] }], "Text", CellChangeTimes->{ 3.423860191223595*^9, {3.424527265013681*^9, 3.424527266325133*^9}, { 3.424715036332122*^9, 3.424715067304907*^9}, {3.42471522424516*^9, 3.424715224477611*^9}, {3.424716128916116*^9, 3.424716131134092*^9}, { 3.424716208881272*^9, 3.42471627428341*^9}, {3.424730618561468*^9, 3.424730618561682*^9}, {3.442089741340384*^9, 3.442089752495625*^9}, { 3.44233666363632*^9, 3.442336673353858*^9}, {3.442338521447554*^9, 3.4423385413014812`*^9}, {3.442344126052002*^9, 3.442344141400113*^9}, { 3.442344350778192*^9, 3.4423443520557747`*^9}, {3.442429890637233*^9, 3.442429893324353*^9}}], Cell[TextData[{ "Outline of proof: First observe that ", Cell[BoxData[ FormBox["g", TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ SubscriptBox["g", "0"], TraditionalForm]]], " agree up to a term with factor ", Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], TraditionalForm]]], ". That is, ", Cell[BoxData[ FormBox[ RowBox[{"g", "=", RowBox[{ SubscriptBox["g", "0"], "+", RowBox[{"s", " ", RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}]}]}]}], TraditionalForm]]], " for some polynomial ", Cell[BoxData[ FormBox[ RowBox[{"s", "(", RowBox[{"x", ",", "y"}], ")"}], TraditionalForm]]], ". So the result holds for ", Cell[BoxData[ FormBox[ RowBox[{"n", "=", "1"}], TraditionalForm]]], ". It suffices to show that it holds for all powers of 2, since these ideals \ are descending (that is, ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["I", "n"], "\[Superset]", SubscriptBox["I", RowBox[{"n", "+", "k"}]]}], TraditionalForm]], FontSlant->"Italic"], " for ", Cell[BoxData[ FormBox[ RowBox[{"k", ">", "0"}], TraditionalForm]]], "). Moreover we may assume ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["g", "0"], "\[NotEqual]", "g"}], TraditionalForm]]], " since otherwise the result follows from proposition 1." }], "Text", CellChangeTimes->{ 3.423860191223595*^9, {3.424527265013681*^9, 3.424527266325133*^9}, { 3.424715036332122*^9, 3.424715067304907*^9}, {3.42471522424516*^9, 3.42471522446073*^9}, {3.44233674791321*^9, 3.442336962329118*^9}, { 3.442343589111287*^9, 3.442343589938139*^9}, {3.442343620467093*^9, 3.442343624433612*^9}, {3.4423436686260366`*^9, 3.4423437371224813`*^9}, { 3.442346181486032*^9, 3.4423462387557907`*^9}, {3.4426581836759357`*^9, 3.442658185447135*^9}, {3.470073427138775*^9, 3.4700734273222322`*^9}, { 3.487515773929084*^9, 3.487515787859363*^9}, {3.4925398701321697`*^9, 3.492539976783967*^9}, 3.4925400162288837`*^9, {3.500314563125082*^9, 3.5003146057637053`*^9}, {3.500314664594678*^9, 3.500314667330494*^9}, { 3.5003148054274054`*^9, 3.500314805855689*^9}}], Cell[TextData[{ "We proceed by introducing a family of \"conjugate\" factors to powers of ", Cell[BoxData[ FormBox["g", TraditionalForm]]], ". We define ", Cell[BoxData[ FormBox[ RowBox[{ OverscriptBox["g", "_"], "=", RowBox[{"(", RowBox[{ SubscriptBox["g", "0"], "-", RowBox[{"s", " ", RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}]}]}], ")"}]}], TraditionalForm]]], " and next observe that ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"g", OverscriptBox["g", "_"]}], "=", RowBox[{ RowBox[{ SuperscriptBox[ SubscriptBox["g", "0"], "2"], "-", SuperscriptBox[ RowBox[{ SuperscriptBox["s", "2"], "(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "2"]}], "\[Congruent]", SuperscriptBox[ SubscriptBox["g", "0"], "2"]}]}], TraditionalForm]]], " modulo ", Cell[BoxData[ FormBox[ SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "2"], TraditionalForm]]], ". Thus ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"(", RowBox[{"f", ",", SuperscriptBox[ SubscriptBox["g", "0"], "2"], ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "2"]}], ")"}], "=", RowBox[{"(", RowBox[{"f", ",", RowBox[{"g", " ", OverscriptBox["g", "_"]}], ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "2"]}], ")"}]}], TraditionalForm]]], ". Irreducibility of ", Cell[BoxData[ FormBox["g", TraditionalForm]]], " implies it is relatively prime to ", Cell[BoxData[ FormBox[ OverscriptBox["g", "_"], TraditionalForm]]], ". We next claim that ", Cell[BoxData[ FormBox[ OverscriptBox["g", "_"], TraditionalForm]]], " is relatively prime to ", Cell[BoxData[ FormBox["f", TraditionalForm]], FormatType->"TraditionalForm"], " (we show this below). So the greatest common divisor of ", Cell[BoxData[ FormBox["f", TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ RowBox[{"g", " ", OverscriptBox["g", "_"], " "}], TraditionalForm]]], " is ", Cell[BoxData[ FormBox["g", TraditionalForm]]], ". By Proposition 1 we conclude ", Cell[BoxData[ FormBox[ RowBox[{"g", "\[Element]", SubscriptBox["I", "2"]}], TraditionalForm]]], ". (It is here that we impose a further assumption on genericity of ", Cell[BoxData[ FormBox[ SubscriptBox["y", "0"], TraditionalForm]]], ", per requirement (3) of that proposition.)" }], "Text", CellChangeTimes->{ 3.423860191223595*^9, {3.424527265013681*^9, 3.424527266325133*^9}, { 3.424715036332122*^9, 3.424715067304907*^9}, {3.42471522424516*^9, 3.42471522446073*^9}, {3.44233674791321*^9, 3.442336752477248*^9}, { 3.4423369650321302`*^9, 3.442337097041518*^9}, {3.442337180248955*^9, 3.442337198649684*^9}, {3.442337240347471*^9, 3.442337272719119*^9}, { 3.44233818029816*^9, 3.442338364791018*^9}, {3.442338399541444*^9, 3.4423385064692783`*^9}, {3.442338548087411*^9, 3.442338563354788*^9}, { 3.442341546898799*^9, 3.4423415817919073`*^9}, {3.4423416224089527`*^9, 3.442341629721792*^9}, {3.442344258500523*^9, 3.442344287640164*^9}, 3.442658254655472*^9, 3.470073473442335*^9, {3.4700748284136667`*^9, 3.470074835660071*^9}, {3.492540017948682*^9, 3.4925400502245197`*^9}, { 3.500313214884591*^9, 3.500313283426838*^9}, {3.500313319330679*^9, 3.5003133197302427`*^9}}], Cell[TextData[{ "To go from ", Cell[BoxData[ FormBox[ RowBox[{"n", "=", "2"}], TraditionalForm]]], " to ", Cell[BoxData[ FormBox[ RowBox[{"n", "=", "4"}], TraditionalForm]]], " and thence to higher powers of 2, observe that we can repeat this \ multiplication tactic. The last paragraph tells us we can write ", Cell[BoxData[ FormBox[ RowBox[{"g", "=", RowBox[{ RowBox[{"t", " ", SuperscriptBox[ SubscriptBox["g", "0"], "2"]}], "+", RowBox[{"u", " ", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "2"]}], "+", RowBox[{"v", " ", "f"}]}]}], TraditionalForm]]], " for some polynomials ", Cell[BoxData[ FormBox["t", TraditionalForm]]], ", ", Cell[BoxData[ FormBox["u", TraditionalForm]]], ", and ", Cell[BoxData[ FormBox["v", TraditionalForm]], FormatType->"TraditionalForm"], ". This time we take as cofactor ", Cell[BoxData[ FormBox[ RowBox[{ OverscriptBox["g", "_"], "=", RowBox[{ RowBox[{"t", " ", SuperscriptBox[ SubscriptBox["g", "0"], "2"]}], "-", RowBox[{"(", RowBox[{ SuperscriptBox[ RowBox[{"u", "(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "2"], "+", RowBox[{"v", " ", "f"}]}], ")"}]}]}], TraditionalForm]]], " and observe that ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"g", OverscriptBox["g", "_"]}], "\[Congruent]", RowBox[{ SuperscriptBox["t", "2"], " ", SuperscriptBox[ SubscriptBox["g", "0"], "4"]}]}], TraditionalForm]]], " modulo ", Cell[BoxData[ FormBox[ RowBox[{"{", RowBox[{"f", ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "4"]}], "}"}], TraditionalForm]]], ". Thus ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"g", OverscriptBox["g", "_"]}], "\[Element]", SubscriptBox["I", "4"]}], TraditionalForm]]], ". We deduce as before that ", Cell[BoxData[ FormBox[ RowBox[{"g", "\[Element]", SubscriptBox["I", "4"]}], TraditionalForm]], FontSlant->"Italic"], ". We omit the formal induction details." }], "Text", CellChangeTimes->{{3.442340545126062*^9, 3.4423407108119497`*^9}, { 3.442343824217742*^9, 3.442343858805256*^9}, {3.442586407397386*^9, 3.442586424625989*^9}, {3.4700748453989058`*^9, 3.470074846166973*^9}, { 3.470074923488652*^9, 3.470075041658354*^9}, {3.470075072094845*^9, 3.470075101818941*^9}, 3.470075244381575*^9, {3.470075299772287*^9, 3.470075326301203*^9}, 3.470075369968409*^9, {3.487515843816227*^9, 3.487516017884626*^9}, {3.487516351309168*^9, 3.487516353017761*^9}, 3.492975071208662*^9, {3.500313295186181*^9, 3.500313296673048*^9}, { 3.500390973835247*^9, 3.500391131039237*^9}}], Cell[TextData[{ "To complete the proof we need to show that ", Cell[BoxData[ FormBox[ OverscriptBox["g", "_"], TraditionalForm]]], " and ", Cell[BoxData[ FormBox["f", TraditionalForm]]], " are relatively prime. Observe that we may treat ", Cell[BoxData[ FormBox[ SubscriptBox["y", "0"], TraditionalForm]]], " as a variable, and when viewed that way ", Cell[BoxData[ FormBox[ SubscriptBox["g", "0"], TraditionalForm]]], " is an analytic function in ", Cell[BoxData[ FormBox[ SubscriptBox["y", "0"], TraditionalForm]]], ". (It is of course a polynomial in ", Cell[BoxData[ FormBox["x", TraditionalForm]]], ", but if we treat ", Cell[BoxData[ FormBox[ SubscriptBox["y", "0"], TraditionalForm]]], " as a variable then it is well known that the coefficients of this \ polynomial are analytic functions of ", Cell[BoxData[ FormBox[ SubscriptBox["y", "0"], TraditionalForm]]], ".) Since ", Cell[BoxData[ FormBox[ SubscriptBox["g", "0"], TraditionalForm]]], " is not constant in ", Cell[BoxData[ FormBox[ SubscriptBox["y", "0"], TraditionalForm]]], ", whereas ", Cell[BoxData[ FormBox["g", TraditionalForm]]], " is constant (with respect to ", Cell[BoxData[ FormBox[ SubscriptBox["y", "0"], TraditionalForm]]], ") , we see that ", Cell[BoxData[ FormBox[ OverscriptBox["g", "_"], TraditionalForm]]], " is likewise not constant in ", Cell[BoxData[ FormBox[ SubscriptBox["y", "0"], TraditionalForm]]], ". Now suppose that for each ", Cell[BoxData[ FormBox[ SubscriptBox["y", "0"], TraditionalForm]]], " there is a polynomial ", Cell[BoxData[ FormBox[ RowBox[{"h", "(", RowBox[{"x", ",", "y"}], ")"}], TraditionalForm]]], " (a priori with coefficients dependent on ", Cell[BoxData[ FormBox[ SubscriptBox["y", "0"], TraditionalForm]]], ") such that ", Cell[BoxData[ FormBox[ RowBox[{"h", "\[VerticalBar]", "f"}], TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ RowBox[{"h", "\[VerticalBar]", OverscriptBox["g", "_"]}], TraditionalForm]]], ". As ", Cell[BoxData[ FormBox["f", TraditionalForm]]], " has but finitely many factors, it is easy to show that for a dense set of \ values ", Cell[BoxData[ FormBox[ SubscriptBox["y", "0"], TraditionalForm]]], ", ", Cell[BoxData[ FormBox["h", TraditionalForm]]], " is the same factor. In other words, we may assume ", Cell[BoxData[ FormBox["h", TraditionalForm]]], " is also constant with respect to ", Cell[BoxData[ FormBox[ SubscriptBox["y", "0"], TraditionalForm]]], ". Recalling the definition of ", Cell[BoxData[ FormBox[ OverscriptBox["g", "_"], TraditionalForm]]], ", we have ", Cell[BoxData[ FormBox[ RowBox[{"h", "\[VerticalBar]", RowBox[{"(", RowBox[{"g", "-", RowBox[{"2", "s", " ", RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}]}]}], ")"}]}], TraditionalForm]]], " (where ", Cell[BoxData[ FormBox["s", TraditionalForm]]], " is function of ", Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{"x", ",", "y", ",", SubscriptBox["y", "0"]}], ")"}], TraditionalForm]]], "). As this holds for any ", Cell[BoxData[ FormBox[ SubscriptBox["y", "0"], TraditionalForm]]], ", it holds for ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["y", "0"], "=", "y"}], TraditionalForm]]], ", and so ", Cell[BoxData[ FormBox[ RowBox[{"h", "\[VerticalBar]", "g"}], TraditionalForm]]], ". Thus ", Cell[BoxData[ FormBox["h", TraditionalForm]]], " must be constant since ", Cell[BoxData[ FormBox[ OverscriptBox["g", "_"], TraditionalForm]]], " is relatively prime to ", Cell[BoxData[ FormBox["g", TraditionalForm]]], ". This finishes the proof that ", Cell[BoxData[ FormBox[ OverscriptBox["g", "_"], TraditionalForm]]], " is relatively prime to ", Cell[BoxData[ FormBox["f", TraditionalForm]]], ". \[EmptySquare]" }], "Text", CellChangeTimes->{{3.442340545126062*^9, 3.4423407108119497`*^9}, { 3.442343824217742*^9, 3.442343858805256*^9}, {3.442586407397386*^9, 3.442586424625989*^9}, {3.4700748453989058`*^9, 3.470074846166973*^9}, { 3.470074923488652*^9, 3.470075041658354*^9}, {3.470075072094845*^9, 3.470075101818941*^9}, 3.470075244381575*^9, {3.470075299772287*^9, 3.470075326301203*^9}, 3.470075369968409*^9, {3.487515843816227*^9, 3.487516017884626*^9}, {3.487516351309168*^9, 3.487516353017761*^9}, 3.492975071208662*^9, {3.500313295186181*^9, 3.500313342016842*^9}, { 3.500314389720935*^9, 3.500314521542864*^9}, {3.500314685353915*^9, 3.500314783404386*^9}, {3.500315463602016*^9, 3.5003154671844397`*^9}, { 3.500315502425528*^9, 3.500315581853806*^9}, {3.5003166130961037`*^9, 3.5003167696371593`*^9}, {3.500316999876786*^9, 3.500317015312305*^9}, { 3.500317054883712*^9, 3.500317078656739*^9}, {3.500322363552086*^9, 3.500322367173686*^9}, {3.500391675419713*^9, 3.5003916817613487`*^9}, { 3.500392701678686*^9, 3.500392791674925*^9}, {3.5003928220704803`*^9, 3.500392841763835*^9}, {3.500392984384129*^9, 3.500393021525982*^9}, { 3.5003931193471203`*^9, 3.5003931548892193`*^9}, {3.500393364650547*^9, 3.5003933651176987`*^9}, {3.5003955829871902`*^9, 3.500395629769835*^9}, { 3.500395665827159*^9, 3.500395670489562*^9}, {3.5003957605754023`*^9, 3.50039576235883*^9}, {3.5003966047282963`*^9, 3.500396627702943*^9}}], Cell[TextData[{ StyleBox["Corollary 1. If ", FontSlant->"Italic"], " ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ SubscriptBox["deg", "x"], StyleBox["(", FontSlant->"Italic"], StyleBox["g", FontSlant->"Italic"], StyleBox[")", FontSlant->"Italic"]}], StyleBox["=", FontSlant->"Italic"], RowBox[{ RowBox[{ StyleBox["deg", FontSlant->"Plain"], StyleBox["(", FontSlant->"Italic"], StyleBox["g", FontSlant->"Italic"], StyleBox[")", FontSlant->"Italic"]}], StyleBox["=", FontSlant->"Italic"], StyleBox["n", FontSlant->"Italic"]}]}], TraditionalForm]]], " ", StyleBox["then g is the polynomial of minimal degree in ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ SubscriptBox["I", RowBox[{"n", "+", "1"}]], TraditionalForm]], FontSlant->"Italic"], StyleBox[".", FontSlant->"Italic"] }], "Text", CellChangeTimes->{ 3.423860191223595*^9, {3.424527265013681*^9, 3.424527266325133*^9}, { 3.424715036332122*^9, 3.424715067304907*^9}, {3.42471522424516*^9, 3.424715224477611*^9}, {3.424716128916116*^9, 3.424716131134092*^9}, { 3.424716208881272*^9, 3.42471627428341*^9}, {3.424730618561468*^9, 3.424730618561682*^9}, {3.442089741340384*^9, 3.442089752495625*^9}, { 3.44233666363632*^9, 3.442336673353858*^9}, {3.442338521447554*^9, 3.4423385413014812`*^9}, {3.442344126052002*^9, 3.442344141400113*^9}, { 3.442344350778192*^9, 3.4423443520557747`*^9}, {3.442422290254499*^9, 3.4424223341715193`*^9}, {3.442422367997197*^9, 3.442422368667631*^9}, { 3.442422405372882*^9, 3.4424225103666067`*^9}, 3.4424227978754673`*^9, 3.4426582362325373`*^9, {3.443031454816163*^9, 3.443031455150387*^9}}], Cell[TextData[{ "Note that a generic linear change of coordinates guarantees the hypotheses \ of this corollary will be satisfied. We also remark that these ideals in \ effect provide lifts of factors that are correct modulo powers of ", Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], TraditionalForm]]], ". This corollary thus gives an effective lifting bound." }], "Text", CellChangeTimes->{{3.44242251309227*^9, 3.4424225401889963`*^9}, { 3.442586241729673*^9, 3.4425862980817127`*^9}, {3.4425868544887466`*^9, 3.442586855764574*^9}, {3.442586918213833*^9, 3.442586935861087*^9}, { 3.4700711424881268`*^9, 3.47007114935187*^9}, {3.487516069003318*^9, 3.487516071028824*^9}}], Cell[TextData[{ "Proof: This follows from the counting argument of the preceding section for \ greatest common divisiors in certain ideals, coupled with the proof of \ Theorem 4 which shows that we find ", Cell[BoxData[ FormBox["g", TraditionalForm]]], " in exactly that setting. \[EmptySquare]" }], "Text", CellChangeTimes->{{3.4424225447099524`*^9, 3.442422545660944*^9}, { 3.4424226475667963`*^9, 3.442422767231325*^9}, 3.442422810498691*^9, { 3.4425823388996677`*^9, 3.442582341023137*^9}, 3.442668046588552*^9}], Cell[TextData[{ StyleBox["Corollary 2: In the setting of absolute factorization over ", FontSlant->"Italic"], Cell[BoxData[ FormBox["\[DoubleStruckCapitalC]", TraditionalForm]]], ",", StyleBox[" the minimal degree factor of f that vanishes at the point ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{ SubscriptBox["x", "0"], ",", SubscriptBox["y", "0"]}], ")"}], TraditionalForm]], FontSlant->"Italic"], StyleBox[" is in the ideal ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{"f", ",", SuperscriptBox[ RowBox[{"(", RowBox[{"x", "-", SubscriptBox["x", "0"]}], ")"}], "n"], ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "n"]}], ")"}], TraditionalForm]], FontSlant->"Italic"], StyleBox[" for all n.", FontSlant->"Italic"] }], "Text", CellChangeTimes->{{3.442340732907618*^9, 3.442340908730693*^9}, { 3.442422339517864*^9, 3.442422339916904*^9}, 3.442422795269019*^9, { 3.4426582967623043`*^9, 3.442658298650989*^9}, {3.442658328858756*^9, 3.442658357831935*^9}}], Cell[TextData[{ "Proof: Simply note that we can replace ", Cell[BoxData[ FormBox[ SubscriptBox["g", "0"], TraditionalForm]]], " by the irreducible factor of ", Cell[BoxData[ FormBox[ RowBox[{"g", "(", RowBox[{"x", ",", SubscriptBox["y", "0"]}], ")"}], TraditionalForm]], FormatType->"TraditionalForm"], " vanishing at ", Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{ SubscriptBox["x", "0"], ",", SubscriptBox["y", "0"]}], ")"}], TraditionalForm]], FormatType->"TraditionalForm"], " and still have the desired ideal inclusion of theorem 4. Clearly ", Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{"x", "-", SubscriptBox["x", "0"]}], ")"}], TraditionalForm]], FontSlant->"Italic"], " is that factor of ", Cell[BoxData[ FormBox[ SubscriptBox["g", "0"], TraditionalForm]]], ". Now apply Theorem 4. \[EmptySquare]" }], "Text", CellChangeTimes->{{3.442422141060807*^9, 3.442422187550211*^9}, 3.4424228121170692`*^9, {3.469555948806884*^9, 3.469555951267541*^9}, 3.470073554748567*^9, {3.500322443976536*^9, 3.500322598320032*^9}, { 3.500322746955739*^9, 3.500322778979158*^9}, 3.5003968454572277`*^9}], Cell[TextData[{ "Indeed, a minor variation of this corollary holds for base field of \ \[DoubleStruckCapitalQ] as well, but it is of less use in that case due to \ corollary 1, along with the fact that working with ", Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{"x", "-", SubscriptBox["x", "0"]}], ")"}], TraditionalForm]], FontSlant->"Italic"], " entails a need to lift further than if we work with ", Cell[BoxData[ FormBox[ SubscriptBox["g", "0"], TraditionalForm]]], " (which, when the base field is \[DoubleStruckCapitalQ], is a product of ", Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{"x", "-", SubscriptBox["x", "0"]}], ")"}], TraditionalForm]], FontSlant->"Italic"], " and its algebraic conjugates). That is to say, ", Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{"x", "-", SubscriptBox["x", "0"]}], ")"}], TraditionalForm]], FontSlant->"Italic"], " is in general a proper divisor of ", Cell[BoxData[ FormBox[Cell[TextData[Cell[BoxData[ FormBox[ SubscriptBox["g", "0"], TraditionalForm]]]]], TraditionalForm]]], ". We remark that the irreducible factor modulo ", Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], TraditionalForm]]], " of ", Cell[BoxData[ FormBox["g", TraditionalForm]], FormatType->"TraditionalForm"], ", that we obtain computationally, might in principle be a proper factor of ", Cell[BoxData[ FormBox[ SubscriptBox["g", "0"], TraditionalForm]]], ". This does not affect the lifting bounds in our analysis above. We also \ note that for generic ", Cell[BoxData[ FormBox[ SubscriptBox["y", "0"], TraditionalForm]]], " our factor will indeed be ", Cell[BoxData[ FormBox[ SubscriptBox["g", "0"], TraditionalForm]]], " when we work over the rationals. This follows from Hilbert\ \[CloseCurlyQuote]s irreducibility theorem [", CounterBox["Reference", "Zippel"], "]." }], "Text", CellChangeTimes->{{3.442422196103064*^9, 3.442422249819002*^9}, { 3.442422824658155*^9, 3.442422848960494*^9}, {3.442422885652248*^9, 3.442423050710512*^9}, 3.4424262140156813`*^9, {3.442432149650125*^9, 3.4424322418239326`*^9}, {3.4424323064787683`*^9, 3.442432307690466*^9}, { 3.4424325150042467`*^9, 3.442432587214539*^9}, 3.442432623981057*^9, { 3.4425823976439037`*^9, 3.442582429481374*^9}, {3.4425824628336887`*^9, 3.442582479888143*^9}, {3.4425828049974422`*^9, 3.442582894308864*^9}, { 3.442583497773347*^9, 3.442583498216432*^9}, {3.442583711436618*^9, 3.442583727962266*^9}, {3.44265821895545*^9, 3.442658219260607*^9}, 3.444242746741477*^9, {3.469554051572695*^9, 3.469554238595339*^9}, 3.470073628366953*^9, {3.500323136692513*^9, 3.500323266241015*^9}, { 3.50032449021518*^9, 3.500324540579631*^9}, {3.500324692688559*^9, 3.50032473039299*^9}, {3.500397026320828*^9, 3.50039702797745*^9}}], Cell[TextData[{ "From a practical standpoint we get too many low degree polynomials in our \ ideals unless we go to sufficiently high powers of ", Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{"x", "-", SubscriptBox["x", "0"]}], ")"}], TraditionalForm]], FontSlant->"Italic"], " and ", Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], TraditionalForm]], FontSlant->"Italic"], ". One must then ask what degree suffices for lifting. This is provided in \ the next theorem." }], "Text", CellChangeTimes->{{3.442422196103064*^9, 3.442422249819002*^9}, { 3.442422824658155*^9, 3.442422848960494*^9}, {3.442422885652248*^9, 3.442423050710512*^9}, 3.4424262140156813`*^9, {3.442432149650125*^9, 3.4424322418239326`*^9}, {3.4424323064787683`*^9, 3.442432307690466*^9}, { 3.4424325150042467`*^9, 3.442432587214539*^9}, 3.442432623981057*^9, { 3.4425823976439037`*^9, 3.442582429481374*^9}, {3.4425824628336887`*^9, 3.442582479888143*^9}, {3.4425828049974422`*^9, 3.442582894308864*^9}, { 3.442583497773347*^9, 3.442583498216432*^9}, {3.442583711436618*^9, 3.442583727962266*^9}, {3.44265821895545*^9, 3.442658219260607*^9}, 3.444242746741477*^9, {3.469554051572695*^9, 3.469554238595339*^9}, 3.4700737533907423`*^9, 3.500236633109743*^9, {3.500236691975328*^9, 3.500236696668001*^9}}], Cell[TextData[{ StyleBox["Theorem 5. Suppose ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"deg", RowBox[{"(", "f", ")"}]}], "=", "n"}], TraditionalForm]]], ", ", StyleBox["and ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"f", "(", RowBox[{ SubscriptBox["x", "0"], ",", SubscriptBox["y", "0"]}], ")"}], "=", "0"}], TraditionalForm]]], StyleBox[". Let ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"m", "=", RowBox[{ SuperscriptBox["n", "2"], "+", "1"}]}], TraditionalForm]]], ". ", StyleBox["In the setting of factoring over \[DoubleStruckCapitalC], the \ minimal degree factor of f that vanishes at the point ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{ SubscriptBox["x", "0"], ",", SubscriptBox["y", "0"]}], ")"}], TraditionalForm]], FontSlant->"Italic"], " ", StyleBox["is the minimal polynomial in a Gr\[ODoubleDot]bner basis for ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"(", RowBox[{"f", ",", SuperscriptBox[ RowBox[{"(", RowBox[{"x", "-", SubscriptBox["x", "0"]}], ")"}], "m"], ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "m"]}], ")"}], TraditionalForm]], FontSlant->"Italic"], ",", StyleBox[" where the term order is graded reverse lexicographic with ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"x", "\[Succeeds]", "y"}], TraditionalForm]]], "." }], "Text", CellChangeTimes->{{3.442422196103064*^9, 3.442422249819002*^9}, { 3.442422824658155*^9, 3.442422848960494*^9}, {3.442422885652248*^9, 3.442423050710512*^9}, 3.4424262140156813`*^9, {3.442432149650125*^9, 3.4424322418239326`*^9}, {3.4424323064787683`*^9, 3.442432307690466*^9}, { 3.4424325150042467`*^9, 3.442432587214539*^9}, 3.442432623981057*^9, { 3.4425823976439037`*^9, 3.4425824427613287`*^9}, {3.4425825120199738`*^9, 3.4425825264375277`*^9}, {3.442582571638672*^9, 3.442582675951688*^9}, { 3.442582793154027*^9, 3.442582793762329*^9}, {3.442583460925097*^9, 3.442583461126646*^9}, {3.442583500234839*^9, 3.442583695678681*^9}, { 3.442584417224062*^9, 3.4425845078622417`*^9}, {3.4426679593392773`*^9, 3.442667986458529*^9}}], Cell["\<\ This can be proved with a zero set size argument along the lines of the proof \ of Proposition 2. We omit the details.\ \>", "Text", CellChangeTimes->{{3.44266799607972*^9, 3.4426680977030573`*^9}, { 3.470073659501067*^9, 3.470073667355093*^9}, {3.492959329947229*^9, 3.49295932999207*^9}}], Cell[TextData[{ "We point out that there is a large body of literature in the realm of \ absolute factorization. For some of the existing methods see [", CounterBox["Reference", "Cheze"], ", ", CounterBox["Reference", "Cheze Galligo 2005"], ", ", CounterBox["Reference", "Cheze Galligo"], ", ", CounterBox["Reference", "Corless Galligo Kotsireas Watt"], ", ", CounterBox["Reference", "Corless Giesbrecht van Hoeij Kotsireas Watt"], ", ", CounterBox["Reference", "Galligo Watt"], ", ", CounterBox["Reference", "Kaltofen"], ", ", CounterBox["Reference", "Sasaki"], ", ", CounterBox["Reference", "Sasaki Suzuki Kolar Sasaki"], "] and references therein. In particular [", CounterBox["Reference", "Cheze Galligo 2005"], "] provides substantial detail about a few of these methods. We do not claim \ that our approach is as efficient as some of these others. Its main advantage \ is that it requires but little code. Moreover as it rests on fundamental \ technology in symbolic computation (i.e. Gr\[ODoubleDot]bner bases), general \ improvements in that area can have a beneficial impact on our method." }], "Text", CellChangeTimes->{{3.4929593317073193`*^9, 3.492959576325554*^9}, 3.492959635268693*^9, {3.492959718215241*^9, 3.4929598277133913`*^9}, { 3.4929612371090612`*^9, 3.492961263219268*^9}, {3.4929624594800577`*^9, 3.492962553425315*^9}, {3.4929626908950872`*^9, 3.492962697934298*^9}, { 3.492963618827512*^9, 3.492963720820491*^9}, 3.492975408144005*^9, 3.5002367726831017`*^9, {3.500236813692965*^9, 3.500236843833748*^9}}] }, Open ]], Cell[CellGroupData[{ Cell[TextData[{ Cell[TextData[{ StyleBox[ CounterBox["Section"], "SectionNumber"], StyleBox[". ", "SectionNumber"] }], "SectionDingbat"], "BIVARIATE GCD AND FACTORIZATION EXAMPLES" }], "Section", CellChangeTimes->{{3.407171809947496*^9, 3.407171844310016*^9}, { 3.407172024813134*^9, 3.407172040605009*^9}, {3.40717902284139*^9, 3.407179040891735*^9}, 3.419964913143628*^9, {3.424447810209189*^9, 3.424447825320483*^9}}], Cell["\<\ We now show several examples that serve to illustrate the methods. We use \ precisions based on trial and error; this aspect to the methods is not \ automated. For simplicity of exposition we also avail ourselves of a minor \ short cut. To wit, we perform no change of variables. It turns out that all \ the examples either already are of full degree in the unsubstituted variable, \ or still work at degree bounds assumed by that case. One should realize that \ this also confers a slight speed advantage because coefficients remain of \ modest size (thus slightly reducing the precision needed in the approximate \ basis computations), and moreover any sparseness we might have in the \ computations will not be destroyed.\ \>", "Text", CellChangeTimes->{ 3.4424297669941187`*^9, {3.442580885047052*^9, 3.442580943523857*^9}, { 3.442584092893732*^9, 3.442584092904718*^9}}], Cell[TextData[{ "All timings are in seconds. These were run on a 3.2 GHz processor, using \ version 7 of ", StyleBox["Mathematica", FontSlant->"Italic"], " [", CounterBox["Reference", "Wolfram"], "] running under Linux." }], "Text", CellChangeTimes->{{3.44258409322959*^9, 3.442584165040873*^9}, { 3.443359576740597*^9, 3.4433595838223457`*^9}, {3.443459219685305*^9, 3.4434592205409937`*^9}, 3.443459917648013*^9}], Cell[CellGroupData[{ Cell["GCD", "Subsection", CellChangeTimes->{{3.407179026846204*^9, 3.407179042905958*^9}, 3.407192257507445*^9, {3.410284210284495*^9, 3.410284218292108*^9}, { 3.410284632641618*^9, 3.410284634811541*^9}, {3.410809933156109*^9, 3.410809934811783*^9}, {3.419961427338462*^9, 3.419961429315826*^9}, { 3.424444709512464*^9, 3.424444710016304*^9}}], Cell[TextData[{ "We first show an example from [", CounterBox["Reference", "Corless Giesbrecht van Hoeij Kotsireas Watt"], "] that factors over the rationals. We remark that their variant had some \ numerical noise (they were illustrating an approximate factorization method), \ whereas we work with the exact input." }], "Text", CellChangeTimes->{{3.419970041377677*^9, 3.419970081105417*^9}, { 3.423943592373023*^9, 3.423943612033415*^9}, {3.42394366430984*^9, 3.423943750645174*^9}, {3.424444876171219*^9, 3.424444888926471*^9}, { 3.4245580723896*^9, 3.424558085159933*^9}, {3.442425817355618*^9, 3.442425834233388*^9}}], Cell[CellGroupData[{ Cell[TextData[StyleBox["Example 2", FontSlant->"Italic"]], "Subsubsection", CellChangeTimes->{{3.42394375970049*^9, 3.423943761879143*^9}, 3.424523600723841*^9, 3.442089693915386*^9}], Cell[BoxData[{ RowBox[{ RowBox[{"g", "=", RowBox[{ RowBox[{"-", "84"}], "+", RowBox[{"41", " ", "x"}], "+", RowBox[{"23", " ", "y"}], "+", RowBox[{"99", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "5"]}], "-", RowBox[{"61", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "4"]}], "-", RowBox[{"50", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "3"]}], "-", RowBox[{"12", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "2"]}], "-", RowBox[{"18", " ", SuperscriptBox["x", "2"], " ", "y"}], "-", RowBox[{"26", " ", "x", " ", SuperscriptBox["y", "7"]}], "-", RowBox[{"62", " ", "x", " ", SuperscriptBox["y", "6"]}], "+", RowBox[{"x", " ", SuperscriptBox["y", "5"]}], "-", RowBox[{"47", " ", "x", " ", SuperscriptBox["y", "4"]}], "-", RowBox[{"91", " ", "x", " ", SuperscriptBox["y", "3"]}], "-", RowBox[{"47", " ", "x", " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"66", " ", SuperscriptBox["x", "3"], " ", "y"}], "-", RowBox[{"55", " ", SuperscriptBox["x", "7"], " ", "y"}], "-", RowBox[{"35", " ", SuperscriptBox["x", "6"], " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"97", " ", SuperscriptBox["x", "6"], " ", "y"}], "+", RowBox[{"79", " ", SuperscriptBox["x", "5"], " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"56", " ", SuperscriptBox["x", "5"], " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"49", " ", SuperscriptBox["x", "5"], " ", "y"}], "+", RowBox[{"57", " ", SuperscriptBox["x", "4"], " ", SuperscriptBox["y", "4"]}], "-", RowBox[{"59", " ", SuperscriptBox["x", "4"], " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"45", " ", SuperscriptBox["x", "4"], " ", SuperscriptBox["y", "2"]}], "-", RowBox[{"8", " ", SuperscriptBox["x", "4"], " ", "y"}], "+", RowBox[{"92", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "5"]}], "+", RowBox[{"77", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"54", " ", SuperscriptBox["x", "3"]}], "+", RowBox[{"53", " ", SuperscriptBox["y", "6"]}], "+", RowBox[{"31", " ", SuperscriptBox["x", "2"]}], "-", RowBox[{"90", " ", SuperscriptBox["y", "7"]}], "-", RowBox[{"58", " ", SuperscriptBox["y", "8"]}], "-", RowBox[{"85", " ", SuperscriptBox["x", "8"]}], "-", RowBox[{"37", " ", SuperscriptBox["x", "7"]}], "-", RowBox[{"86", " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"50", " ", SuperscriptBox["x", "6"]}], "+", RowBox[{"83", " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"63", " ", SuperscriptBox["x", "5"]}], "+", RowBox[{"94", " ", SuperscriptBox["y", "4"]}], "-", RowBox[{"93", " ", SuperscriptBox["x", "4"]}], "-", SuperscriptBox["y", "5"], "-", RowBox[{"5", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "6"]}], "-", RowBox[{"61", " ", "x", " ", "y"}], "+", RowBox[{"43", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "4"]}], "-", RowBox[{"62", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "3"]}]}]}], ";"}], "\n", RowBox[{ RowBox[{"h", "=", RowBox[{ RowBox[{"-", "76"}], "-", RowBox[{"53", " ", "x"}], "+", RowBox[{"88", " ", "y"}], "+", RowBox[{"66", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "5"]}], "-", RowBox[{"29", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "4"]}], "-", RowBox[{"91", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "3"]}], "-", RowBox[{"53", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "2"]}], "-", RowBox[{"19", " ", SuperscriptBox["x", "2"], " ", "y"}], "+", RowBox[{"68", " ", "x", " ", SuperscriptBox["y", "6"]}], "-", RowBox[{"72", " ", "x", " ", SuperscriptBox["y", "5"]}], "-", RowBox[{"87", " ", "x", " ", SuperscriptBox["y", "4"]}], "+", RowBox[{"79", " ", "x", " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"43", " ", "x", " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"80", " ", SuperscriptBox["x", "3"], " ", "y"}], "-", RowBox[{"50", " ", SuperscriptBox["x", "6"], " ", "y"}], "-", RowBox[{"53", " ", SuperscriptBox["x", "5"], " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"85", " ", SuperscriptBox["x", "5"], " ", "y"}], "+", RowBox[{"78", " ", SuperscriptBox["x", "4"], " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"17", " ", SuperscriptBox["x", "4"], " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"72", " ", SuperscriptBox["x", "4"], " ", "y"}], "+", RowBox[{"30", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"72", " ", SuperscriptBox["x", "3"]}], "-", RowBox[{"23", " ", SuperscriptBox["y", "6"]}], "-", RowBox[{"47", " ", SuperscriptBox["x", "2"]}], "-", RowBox[{"61", " ", SuperscriptBox["y", "7"]}], "+", RowBox[{"19", " ", SuperscriptBox["x", "7"]}], "-", RowBox[{"42", " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"88", " ", SuperscriptBox["x", "6"]}], "-", RowBox[{"34", " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"49", " ", SuperscriptBox["x", "5"]}], "+", RowBox[{"31", " ", SuperscriptBox["y", "4"]}], "-", RowBox[{"99", " ", SuperscriptBox["x", "4"]}], "-", RowBox[{"37", " ", SuperscriptBox["y", "5"]}], "-", RowBox[{"66", " ", "x", " ", "y"}], "-", RowBox[{"85", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "4"]}], "-", RowBox[{"86", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "3"]}]}]}], ";"}], "\n", RowBox[{ RowBox[{"f", "=", RowBox[{"Expand", "[", RowBox[{"g", " ", "h"}], "]"}]}], ";"}]}], "Input", CellChangeTimes->{ 3.423943627833061*^9, {3.423944703622687*^9, 3.42394470443129*^9}, 3.423955248502627*^9, {3.424445426263778*^9, 3.424445440310351*^9}, { 3.424445675459729*^9, 3.42444567869124*^9}, {3.424644052517482*^9, 3.424644066311801*^9}, {3.442089695845709*^9, 3.442089696870481*^9}, { 3.442175731091844*^9, 3.442175743305401*^9}, {3.442176026325995*^9, 3.442176038053171*^9}, 3.442279136589169*^9, 3.470071845984311*^9}, CellID->921679567], Cell[TextData[{ "We begin by forming another polynomial, ", Cell[BoxData[ FormBox["e", TraditionalForm]]], ", as the product of ", Cell[BoxData[ FormBox["g", TraditionalForm]]], " and a random bivariate ", Cell[BoxData[ FormBox["k", TraditionalForm]]], " of similar degree." }], "Text", CellChangeTimes->{{3.42444490048859*^9, 3.424444974829459*^9}, { 3.424445475874672*^9, 3.42444548678931*^9}, {3.424445691605536*^9, 3.424445717522089*^9}, {3.442089706349793*^9, 3.4420897160339193`*^9}}], Cell[BoxData[ RowBox[{ RowBox[{"randomPoly", "[", RowBox[{"deg_", ",", "vars_"}], "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"n", "=", RowBox[{"Length", "[", "vars", "]"}]}], ",", "t", ",", "poly", ",", "terms"}], "}"}], ",", RowBox[{ RowBox[{"poly", "=", RowBox[{ RowBox[{"RandomInteger", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"-", "10"}], ",", "10"}], "}"}], ",", RowBox[{"{", RowBox[{"deg", "+", "1"}], "}"}]}], "]"}], ".", RowBox[{"t", "^", RowBox[{"Range", "[", RowBox[{"0", ",", "deg"}], "]"}]}]}]}], ";", "\[IndentingNewLine]", RowBox[{"Expand", "[", RowBox[{"poly", "/.", RowBox[{ RowBox[{"t", "^", "j_."}], "\[RuleDelayed]", RowBox[{ RowBox[{"(", RowBox[{ RowBox[{"RandomInteger", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"-", "5"}], ",", "5"}], "}"}], ",", RowBox[{"{", RowBox[{"Length", "[", "vars", "]"}], "}"}]}], "]"}], ".", "vars"}], ")"}], "^", "j"}]}]}], "]"}]}]}], "]"}]}]], "Input", CellChangeTimes->{ 3.423943627833061*^9, {3.423944703622687*^9, 3.42394470443129*^9}, 3.423955248502627*^9, {3.424444919726411*^9, 3.424444922021776*^9}}], Cell[BoxData[{ RowBox[{ RowBox[{"SeedRandom", "[", "1111", "]"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"k", " ", "=", " ", RowBox[{"randomPoly", "[", RowBox[{"7", ",", RowBox[{"{", RowBox[{"x", ",", "y"}], "}"}]}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"e", "=", RowBox[{"Expand", "[", RowBox[{"g", " ", "k"}], "]"}]}], ";"}]}], "Input", CellChangeTimes->{{3.423944716899667*^9, 3.423944742353739*^9}, { 3.424445238114566*^9, 3.424445244001056*^9}, {3.42444549347383*^9, 3.424445503054329*^9}, {3.424445727671468*^9, 3.424445730529927*^9}, { 3.424644072613778*^9, 3.424644083415881*^9}, {3.4421764088275967`*^9, 3.4421764093540993`*^9}}], Cell[TextData[{ "We now compute an approximate Gr\[ODoubleDot]bner basis for the ideal \ consisting of ", Cell[BoxData[ FormBox[ RowBox[{"{", RowBox[{"f", ",", "e", ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", SubscriptBox["y", "0"]}], ")"}], "d"]}], "}"}], TraditionalForm]], FontSlant->"Italic"], " for a randomly selected ", Cell[BoxData[ FormBox[ SubscriptBox["y", "0"], TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ RowBox[{"d", "=", RowBox[{ RowBox[{"min", "(", RowBox[{ RowBox[{"deg", "(", "f", StyleBox[")", FontSlant->"Plain"]}], StyleBox[",", FontSlant->"Plain"], RowBox[{ StyleBox["deg", FontSlant->"Plain"], StyleBox["(", FontSlant->"Plain"], "e", StyleBox[")", FontSlant->"Italic"]}]}], StyleBox[")", FontSlant->"Plain"]}], StyleBox["+", FontSlant->"Plain"], StyleBox["1", FontSlant->"Plain"]}]}], TraditionalForm]]], ". Shown below is the timing, in seconds." }], "Text", CellChangeTimes->{{3.424444995063963*^9, 3.424445175433435*^9}, { 3.424445277131688*^9, 3.424445288026057*^9}, {3.424445523905499*^9, 3.42444554982913*^9}, {3.424446146524438*^9, 3.424446174723019*^9}, { 3.424558115234287*^9, 3.424558148172828*^9}, {3.424644087293021*^9, 3.424644106355268*^9}, {3.442346740340383*^9, 3.442346751103681*^9}, 3.442426010207468*^9}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"First", "[", RowBox[{"Timing", "[", RowBox[{ RowBox[{"gby", "=", RowBox[{"GroebnerBasis", "[", RowBox[{ RowBox[{"{", RowBox[{"f", ",", "e", ",", RowBox[{ RowBox[{"(", RowBox[{"y", "-", RowBox[{"RandomInteger", "[", RowBox[{"{", RowBox[{"20", ",", "40"}], "}"}], "]"}]}], ")"}], "^", "9"}]}], "}"}], ",", RowBox[{"{", RowBox[{"x", ",", "y"}], "}"}], ",", RowBox[{"MonomialOrder", "\[Rule]", "DegreeReverseLexicographic"}], ",", RowBox[{"CoefficientDomain", "\[Rule]", RowBox[{"InexactNumbers", "[", "200", "]"}]}]}], "]"}]}], ";"}], "]"}], "]"}]], "Input", CellChangeTimes->{{3.423949423617372*^9, 3.423949499322186*^9}, { 3.423949613170854*^9, 3.423949615099675*^9}, {3.423949675315714*^9, 3.42394967772781*^9}, {3.423949809024014*^9, 3.423949812309054*^9}, { 3.423950682487056*^9, 3.42395068680904*^9}, 3.423950796456921*^9, { 3.423950828293471*^9, 3.423950839747877*^9}, 3.423951222542645*^9, { 3.423951291036366*^9, 3.423951295649012*^9}, 3.42395276052938*^9, 3.423952822707028*^9, {3.423953257028109*^9, 3.423953281947107*^9}, { 3.423955012979049*^9, 3.423955018477136*^9}, {3.423955128926648*^9, 3.423955235030738*^9}, {3.423955282782749*^9, 3.423955288418829*^9}, { 3.42395934004902*^9, 3.423959360959064*^9}, {3.424005578563731*^9, 3.424005581309204*^9}, {3.424445272097615*^9, 3.424445272579924*^9}, { 3.424445555964514*^9, 3.424445563549028*^9}, 3.424642381798488*^9, { 3.424644110815849*^9, 3.424644113530875*^9}}], Cell[BoxData["0.1689749999995911`"], "Output", CellChangeTimes->{3.442428620257413*^9}] }, Open ]], Cell[TextData[{ "We check that the recovered common factor agrees with ", Cell[BoxData[ FormBox["g", TraditionalForm]]], " up to multiplicative factor." }], "Text", CellChangeTimes->{{3.42444534066995*^9, 3.424445391452894*^9}, { 3.424642138377809*^9, 3.424642201968708*^9}, {3.424642317945987*^9, 3.42464236396799*^9}, {3.4420896717250957`*^9, 3.442089672308103*^9}, { 3.442346731247035*^9, 3.4423467326210947`*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Together", "[", RowBox[{ RowBox[{"Numerator", "[", RowBox[{"Together", "[", RowBox[{"Rationalize", "[", RowBox[{"First", "[", "gby", "]"}], "]"}], "]"}], "]"}], "/", "g"}], "]"}]], "Input", CellChangeTimes->{{3.423949515072626*^9, 3.423949573078856*^9}, { 3.423949735176392*^9, 3.423949752631773*^9}, {3.42394985429829*^9, 3.423949869524541*^9}, 3.423950017940822*^9, {3.423950738720271*^9, 3.423950785839913*^9}, {3.42395086451419*^9, 3.423950880653033*^9}, { 3.423951340463748*^9, 3.423951420518228*^9}, {3.423951489030195*^9, 3.423951503979588*^9}, 3.423952808243286*^9, {3.423955070683811*^9, 3.423955072191892*^9}, {3.424005593201078*^9, 3.424005599236129*^9}, { 3.424445313764402*^9, 3.42444533732947*^9}, {3.424445569413735*^9, 3.424445572417965*^9}, 3.424644122935476*^9}], Cell[BoxData[ RowBox[{"-", "1"}]], "Output", CellChangeTimes->{ 3.42400560450545*^9, {3.424445308923047*^9, 3.424445337901453*^9}, 3.424445593099804*^9, 3.424642388890287*^9, 3.424644138619872*^9}] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Factorization", "Subsection", CellChangeTimes->{{3.424445599099152*^9, 3.424445612756225*^9}}], Cell["\<\ The code below is based on the theory presented for bivariate factorization \ over the rationals. For efficiency we use quadratic lifting rather than \ trying to do the full lift in one step. We do this by squaring polynomials in \ the preceding basis and augmenting with the polynomial whose factorization we \ seek. In practice this makes a tremendous difference in speed. Moreover it \ allows us to work with lower initial precision than would otherwise be the \ case, because overall precision loss is less when done in quadratic stages \ rather than all at once.\ \>", "Text", CellChangeTimes->{{3.424447676652825*^9, 3.424447804626465*^9}, { 3.424448847796184*^9, 3.424448873338029*^9}, {3.424448969515401*^9, 3.424448969612071*^9}, 3.424643727228276*^9, {3.42464386162307*^9, 3.424643861623309*^9}, {3.424644155443707*^9, 3.424644155443935*^9}, { 3.424644653764803*^9, 3.42464465560721*^9}, {3.424644704093477*^9, 3.424644751428603*^9}, {3.424644833948628*^9, 3.424644986042672*^9}, { 3.424645068939964*^9, 3.424645110388279*^9}, {3.424645240268294*^9, 3.424645341494244*^9}, {3.424645464925226*^9, 3.42464551379624*^9}, { 3.424645820947066*^9, 3.424645840788631*^9}, {3.424645871274953*^9, 3.424645875112933*^9}, {3.424647361961068*^9, 3.424647362082656*^9}, { 3.424694595514853*^9, 3.424694702119979*^9}, {3.424695155154779*^9, 3.424695160355473*^9}, {3.442430055775509*^9, 3.442430171615254*^9}, { 3.442658394281928*^9, 3.442658394630836*^9}, {3.500232721381336*^9, 3.500232725657147*^9}, {3.500232852037891*^9, 3.50023289061033*^9}}], Cell["\<\ At each step we print the time in seconds it took for the Gr\[ODoubleDot]bner \ basis computation of that lift, and the precision of the result. We give up \ if the initial precision is insufficient to obtain the approximate numeric \ bases for the full number of lifting steps required for this task. In this \ case we use the best result we have prior to this failure, in the hope that \ it might have been sufficiently lifted to form a correct factor. An \ improvement we do not implement would be to perform trial division tests \ along the way.\ \>", "Text", CellChangeTimes->{{3.424447676652825*^9, 3.424447804626465*^9}, { 3.424448847796184*^9, 3.424448873338029*^9}, {3.424448969515401*^9, 3.424448969612071*^9}, 3.424643727228276*^9, {3.42464386162307*^9, 3.424643861623309*^9}, {3.424644155443707*^9, 3.424644155443935*^9}, { 3.424644653764803*^9, 3.42464465560721*^9}, {3.424644704093477*^9, 3.424644751428603*^9}, {3.424644833948628*^9, 3.424644986042672*^9}, { 3.424645068939964*^9, 3.424645110388279*^9}, {3.424645240268294*^9, 3.424645341494244*^9}, {3.424645464925226*^9, 3.42464551379624*^9}, { 3.424645820947066*^9, 3.424645840788631*^9}, {3.424645871274953*^9, 3.424645875112933*^9}, {3.424647361961068*^9, 3.424647362082656*^9}, { 3.424694595514853*^9, 3.424694702096277*^9}, {3.442089623214961*^9, 3.442089646331827*^9}}], Cell[BoxData[ RowBox[{ RowBox[{"factorBivariate", "[", RowBox[{"f_", ",", "x_", ",", "y_", ",", "y0_", ",", "prec_"}], "]"}], ":=", RowBox[{"Catch", "[", RowBox[{"Module", "[", "\[IndentingNewLine]", RowBox[{ RowBox[{"{", RowBox[{"rts", ",", "gb", ",", "n", ",", "fax", ",", "fac"}], "}"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"fax", "=", RowBox[{"Select", "[", RowBox[{ RowBox[{"FactorList", "[", RowBox[{"f", "/.", RowBox[{"y", "\[Rule]", "y0"}]}], "]"}], ",", RowBox[{ RowBox[{"!", RowBox[{"NumberQ", "[", RowBox[{"#", "[", RowBox[{"[", "1", "]"}], "]"}], "]"}]}], "&"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"fac", "=", RowBox[{"fax", "[", RowBox[{"[", RowBox[{"1", ",", "1"}], "]"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{ RowBox[{"gb", "[", "0", "]"}], "=", RowBox[{"N", "[", RowBox[{ RowBox[{"{", RowBox[{"fac", ",", RowBox[{"y", "-", "y0"}]}], "}"}], ",", "prec"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"n", "=", RowBox[{"Ceiling", "[", RowBox[{"Log", "[", RowBox[{"2", ",", RowBox[{ RowBox[{"Exponent", "[", RowBox[{"fac", ",", "x"}], "]"}], "+", "1"}]}], "]"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"Print", "[", RowBox[{"\"\\"", ",", "n", ",", " ", "\"\< times\>\""}], "]"}], ";", "\[IndentingNewLine]", RowBox[{"Do", "[", RowBox[{ RowBox[{ RowBox[{"Print", "[", RowBox[{"{", RowBox[{ RowBox[{"First", "[", RowBox[{"Timing", "[", RowBox[{ RowBox[{ RowBox[{"gb", "[", "j", "]"}], "=", "\[IndentingNewLine]", RowBox[{"GroebnerBasis", "[", RowBox[{ RowBox[{"Flatten", "[", RowBox[{"{", RowBox[{"f", ",", RowBox[{ RowBox[{"gb", "[", RowBox[{"j", "-", "1"}], "]"}], "^", "2"}]}], "}"}], "]"}], ",", RowBox[{"{", RowBox[{"x", ",", "y"}], "}"}], ",", RowBox[{ "MonomialOrder", "\[Rule]", "DegreeReverseLexicographic"}], ",", RowBox[{ "CoefficientDomain", "\[Rule]", "InexactNumbers"}]}], "]"}]}], ";"}], "]"}], "]"}], ",", RowBox[{"Precision", "[", RowBox[{"gb", "[", "j", "]"}], "]"}]}], "}"}], "]"}], ";", "\[IndentingNewLine]", RowBox[{"If", "[", RowBox[{ RowBox[{ RowBox[{"Head", "[", RowBox[{"gb", "[", "j", "]"}], "]"}], "===", "GroebnerBasis"}], ",", RowBox[{"Throw", "[", RowBox[{"Numerator", "[", RowBox[{"Together", "[", RowBox[{"Rationalize", "[", RowBox[{"First", "[", RowBox[{"gb", "[", RowBox[{"j", "-", "1"}], "]"}], "]"}], "]"}], "]"}], "]"}], "]"}]}], "]"}], ";"}], "\[IndentingNewLine]", ",", RowBox[{"{", RowBox[{"j", ",", "n"}], "}"}]}], "]"}], ";", "\[IndentingNewLine]", RowBox[{"fac", "=", RowBox[{"First", "[", RowBox[{"gb", "[", "n", "]"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"Clear", "[", "gb", "]"}], ";", "\[IndentingNewLine]", RowBox[{"Numerator", "[", RowBox[{"Together", "[", RowBox[{"Rationalize", "[", "fac", "]"}], "]"}], "]"}]}]}], "]"}], "]"}]}]], "Input", CellChangeTimes->{{3.424694281499802*^9, 3.424694399670914*^9}, { 3.424694555848073*^9, 3.424694560769644*^9}, {3.4424238134280777`*^9, 3.4424238844789677`*^9}, {3.442423930881761*^9, 3.442423931088629*^9}, { 3.442424761877297*^9, 3.442424791651732*^9}, {3.4424277250124197`*^9, 3.442427725281933*^9}, {3.442427760307571*^9, 3.442427760465969*^9}, { 3.443031569636365*^9, 3.443031569935584*^9}, {3.443457675472705*^9, 3.443457755742372*^9}, {3.4434577968376207`*^9, 3.443457816694559*^9}, { 3.443457889832274*^9, 3.443457895646749*^9}, {3.47007156404838*^9, 3.470071577321434*^9}}], Cell[CellGroupData[{ Cell[TextData[StyleBox["Example 3", FontSlant->"Italic"]], "Subsubsection", CellChangeTimes->{{3.424447845039378*^9, 3.424447848844479*^9}, 3.424523605767339*^9, 3.442089605274166*^9}], Cell[TextData[{ "We will continue with the previous example, this time factoring ", Cell[BoxData[ FormBox["f", TraditionalForm]]], ". We first find roots in ", Cell[BoxData[ FormBox["x", TraditionalForm]]], " upon setting ", Cell[BoxData[ FormBox["y", TraditionalForm]]], " to a fixed value (we use 5 in this case). We will work with the first such \ root to develop a full bivariate factor. We begin with 500 digits ", StyleBox["of precision", FontFamily->"Utopia"], "." }], "Text", CellChangeTimes->{ 3.442423445480896*^9, {3.442429987533843*^9, 3.44242998900462*^9}, 3.470070844931855*^9}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Timing", "[", RowBox[{"factor", "=", RowBox[{"factorBivariate", "[", RowBox[{"f", ",", "x", ",", "y", ",", "5", ",", "500"}], "]"}]}], "]"}]], "Input", CellChangeTimes->{ 3.4424213958144093`*^9, 3.442421512793701*^9, {3.442421628826882*^9, 3.4424216334805737`*^9}, 3.4424217018993*^9, 3.442421791340681*^9, 3.4424237183486958`*^9, 3.442424803286069*^9}], Cell[BoxData[{ InterpretationBox[ RowBox[{"\<\"lift \"\>", "\[InvisibleSpace]", "3", "\[InvisibleSpace]", "\<\" times\"\>"}], SequenceForm["lift ", 3, " times"], Editable->False], "\n", RowBox[{"{", RowBox[{"0.01699700000062876`", ",", "469.76299843955235`"}], "}"}], "\n", RowBox[{"{", RowBox[{"0.05299199999990378`", ",", "421.6159203455828`"}], "}"}], "\n", RowBox[{"{", RowBox[{"0.21296799999981886`", ",", "331.52531185335033`"}], "}"}]}], "Output", GeneratedCell->False, CellAutoOverwrite->False, CellChangeTimes->{ 3.442424945076792*^9, {3.4424277543301783`*^9, 3.442427772393786*^9}, 3.44321119000889*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{"0.28895600000032573`", ",", RowBox[{ RowBox[{"-", "76"}], "-", RowBox[{"53", " ", "x"}], "-", RowBox[{"47", " ", SuperscriptBox["x", "2"]}], "+", RowBox[{"72", " ", SuperscriptBox["x", "3"]}], "-", RowBox[{"99", " ", SuperscriptBox["x", "4"]}], "+", RowBox[{"49", " ", SuperscriptBox["x", "5"]}], "+", RowBox[{"88", " ", SuperscriptBox["x", "6"]}], "+", RowBox[{"19", " ", SuperscriptBox["x", "7"]}], "+", RowBox[{"88", " ", "y"}], "-", RowBox[{"66", " ", "x", " ", "y"}], "-", RowBox[{"19", " ", SuperscriptBox["x", "2"], " ", "y"}], "+", RowBox[{"80", " ", SuperscriptBox["x", "3"], " ", "y"}], "+", RowBox[{"72", " ", SuperscriptBox["x", "4"], " ", "y"}], "+", RowBox[{"85", " ", SuperscriptBox["x", "5"], " ", "y"}], "-", RowBox[{"50", " ", SuperscriptBox["x", "6"], " ", "y"}], "-", RowBox[{"42", " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"43", " ", "x", " ", SuperscriptBox["y", "2"]}], "-", RowBox[{"53", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"30", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"17", " ", SuperscriptBox["x", "4"], " ", SuperscriptBox["y", "2"]}], "-", RowBox[{"53", " ", SuperscriptBox["x", "5"], " ", SuperscriptBox["y", "2"]}], "-", RowBox[{"34", " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"79", " ", "x", " ", SuperscriptBox["y", "3"]}], "-", RowBox[{"91", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "3"]}], "-", RowBox[{"86", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"78", " ", SuperscriptBox["x", "4"], " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"31", " ", SuperscriptBox["y", "4"]}], "-", RowBox[{"87", " ", "x", " ", SuperscriptBox["y", "4"]}], "-", RowBox[{"29", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "4"]}], "-", RowBox[{"85", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "4"]}], "-", RowBox[{"37", " ", SuperscriptBox["y", "5"]}], "-", RowBox[{"72", " ", "x", " ", SuperscriptBox["y", "5"]}], "+", RowBox[{"66", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "5"]}], "-", RowBox[{"23", " ", SuperscriptBox["y", "6"]}], "+", RowBox[{"68", " ", "x", " ", SuperscriptBox["y", "6"]}], "-", RowBox[{"61", " ", SuperscriptBox["y", "7"]}]}]}], "}"}]], "Output", CellChangeTimes->{ 3.44242494537488*^9, {3.442427755039508*^9, 3.442427772717779*^9}}] }, Open ]], Cell[TextData[{ "Observe that we indeed recovered a correct factor, specifically ", Cell[BoxData[ FormBox[ RowBox[{"h", "(", RowBox[{"x", ",", "y"}], ")"}], TraditionalForm]]], "." }], "Text", CellChangeTimes->{{3.424644776608273*^9, 3.424644802342336*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Together", "[", RowBox[{"factor", "/", "h"}], "]"}]], "Input", CellChangeTimes->{{3.424644594830079*^9, 3.424644616605443*^9}}], Cell[BoxData["1"], "Output", CellChangeTimes->{{3.424644604409857*^9, 3.424644617364637*^9}, 3.424644648772782*^9, 3.424644698027306*^9, 3.424644774412294*^9, 3.424645204243268*^9, 3.44227957211452*^9}] }, Open ]], Cell[TextData[{ "In the code above we use yet another short cut, which is to assume the \ univariate factor lifts to a multivariate factor (that is, no recombination \ is needed). That this is reasonable is due to Hilbert's irreducibility \ theorem, which shows that most integer substitutions for one variable \ preserve irreducibility over the rationals [", CounterBox["Reference", "Zippel"], "]. Were our factor not to lift in such a way, the algorithm would still \ work except we might need to lift to a higher degree; this is the same \ situation as that described in the remark following Corollary 2 in the \ previous section. An alternative would be to lift to half the total degree of \ the input, and be willing to try all univariate factors of degree less or \ equal to that. The point of either short cut is to reduce the lifting degree, \ as the higher ones clearly make for more strenuous Gr\[ODoubleDot]bner basis \ computations both in terms of polynomial degree and likelihood of \ encountering inadequate precision (the raising of which would incur a time \ penalty on all steps)." }], "Text", CellChangeTimes->{{3.42452346348579*^9, 3.424523469326948*^9}, 3.424523518751624*^9, {3.442429978317419*^9, 3.442429979955305*^9}, { 3.442658418342785*^9, 3.442658419641189*^9}}], Cell[TextData[{ "The next example is from [", CounterBox["Reference", "Galligo Watt"], "]." }], "Text", CellChangeTimes->{{3.42452346348579*^9, 3.424523469326948*^9}, 3.424523518751624*^9, {3.442429978317419*^9, 3.442429979932733*^9}}] }, Open ]], Cell[CellGroupData[{ Cell[TextData[StyleBox["Example 4", FontSlant->"Italic"]], "Subsubsection", CellChangeTimes->{{3.424523448833721*^9, 3.424523460007138*^9}, 3.424523611384472*^9, 3.442089563162039*^9, 3.442176075811708*^9}], Cell[BoxData[{ RowBox[{ RowBox[{"p1", "=", RowBox[{ RowBox[{"48", " ", "x", " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"12", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"11", " ", SuperscriptBox["x", "2"]}], "+", RowBox[{"6", " ", SuperscriptBox["x", "3"]}], "-", RowBox[{"11", " ", SuperscriptBox["x", "7"], " ", SuperscriptBox["y", "2"]}], "-", RowBox[{"63", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"54", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "3"]}], "-", RowBox[{"23", " ", SuperscriptBox["x", "10"], " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"58", " ", SuperscriptBox["x", "4"], " ", SuperscriptBox["y", "4"]}], "+", RowBox[{"18", " ", SuperscriptBox["x", "9"], " ", SuperscriptBox["y", "2"]}], "-", RowBox[{"42", " ", SuperscriptBox["x", "5"], " ", SuperscriptBox["y", "5"]}], "-", RowBox[{"80", " ", SuperscriptBox["x", "11"], " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"10", " ", SuperscriptBox["y", "10"], " ", SuperscriptBox["x", "4"]}], "+", RowBox[{"14", " ", SuperscriptBox["x", "4"], " ", "y"}], "+", RowBox[{"47", " ", SuperscriptBox["y", "15"]}], "+", RowBox[{"18", " ", SuperscriptBox["x", "12"], " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"36", " ", SuperscriptBox["y", "13"]}], "-", RowBox[{"23", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "12"]}], "-", RowBox[{"68", " ", SuperscriptBox["x", "8"], " ", SuperscriptBox["y", "3"]}], "-", RowBox[{"41", " ", SuperscriptBox["x", "4"], " ", SuperscriptBox["y", "7"]}], "+", RowBox[{"72", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "11"]}], "+", RowBox[{"22", " ", "x", " ", SuperscriptBox["y", "13"]}], "-", RowBox[{"76", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "13"]}], "-", RowBox[{"54", " ", SuperscriptBox["y", "10"]}], "-", RowBox[{"18", " ", SuperscriptBox["y", "9"]}], "+", RowBox[{"79", " ", SuperscriptBox["x", "7"], " ", SuperscriptBox["y", "3"]}], "-", RowBox[{"49", " ", SuperscriptBox["x", "7"], " ", SuperscriptBox["y", "4"]}], "+", RowBox[{"9", " ", SuperscriptBox["x", "5"]}], "-", RowBox[{"75", " ", SuperscriptBox["x", "6"], " ", "y"}], "-", RowBox[{"46", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "5"]}], "-", RowBox[{"17", " ", SuperscriptBox["x", "4"], " ", SuperscriptBox["y", "5"]}], "+", RowBox[{"3", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "7"]}], "+", RowBox[{"21", " ", SuperscriptBox["y", "5"]}]}]}], ";"}], "\n", RowBox[{ RowBox[{"p2", "=", RowBox[{ RowBox[{ RowBox[{"-", "40"}], " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"55", " ", "x", " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"36", " ", SuperscriptBox["x", "3"], " ", "y"}], "-", RowBox[{"82", " ", SuperscriptBox["x", "6"], " ", SuperscriptBox["y", "2"]}], "-", RowBox[{"73", " ", SuperscriptBox["x", "9"], " ", "y"}], "-", RowBox[{"27", " ", SuperscriptBox["x", "5"], " ", SuperscriptBox["y", "5"]}], "+", RowBox[{"18", " ", SuperscriptBox["x", "7"], " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"31", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"54", " ", SuperscriptBox["y", "7"], " ", SuperscriptBox["y", "3"]}], "-", RowBox[{"16", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "5"]}], "-", RowBox[{"96", " ", SuperscriptBox["y", "4"]}], "+", RowBox[{"13", " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"40", " ", SuperscriptBox["x", "2"]}], "-", RowBox[{"99", " ", SuperscriptBox["y", "2"]}], "-", RowBox[{"20", " ", SuperscriptBox["y", "6"]}], "+", RowBox[{"44", " ", SuperscriptBox["x", "9"]}], "-", RowBox[{"65", " ", SuperscriptBox["y", "10"]}], "+", RowBox[{"39", " ", SuperscriptBox["x", "6"]}], "+", RowBox[{"66", " ", "x", " ", SuperscriptBox["y", "5"]}], "-", RowBox[{"34", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"99", " ", SuperscriptBox["x", "6"], " ", SuperscriptBox["y", "4"]}], "-", RowBox[{"9", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "4"]}], "-", RowBox[{"83", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "7"]}], "+", RowBox[{"76", " ", SuperscriptBox["x", "4"], " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"28", " ", SuperscriptBox["x", "8"]}], "-", RowBox[{"89", " ", SuperscriptBox["y", "8"]}], "+", RowBox[{"71", " ", "x", " ", SuperscriptBox["y", "8"]}], "+", RowBox[{"38", " ", "x", " ", SuperscriptBox["y", "9"]}], "-", RowBox[{"40", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "6"]}], "-", RowBox[{"12", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "5"]}]}]}], ";"}], "\n", RowBox[{ RowBox[{"prod", "=", RowBox[{"Expand", "[", RowBox[{"p1", " ", "p2"}], "]"}]}], ";"}]}], "Input", CellChangeTimes->{{3.424028978585585*^9, 3.42402927923998*^9}, 3.424694529026559*^9, 3.424694717543546*^9, {3.424694941334028*^9, 3.42469494625271*^9}, {3.44217607965455*^9, 3.442176080965329*^9}, { 3.442279581554222*^9, 3.442279582576495*^9}, 3.470071830223*^9}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Timing", "[", RowBox[{"factor", " ", "=", " ", RowBox[{"factorBivariate", "[", RowBox[{"prod", ",", " ", "x", ",", " ", "y", ",", " ", "2", ",", "600"}], "]"}]}], "]"}]], "Input", CellChangeTimes->{ 3.442424379491349*^9, {3.442424415667178*^9, 3.442424424673634*^9}, { 3.4424244632684183`*^9, 3.442424485941079*^9}, {3.442424530595236*^9, 3.442424547732726*^9}, 3.442424681926049*^9, {3.442424830470777*^9, 3.442424843446025*^9}, 3.443359645383445*^9}], Cell[BoxData[{ InterpretationBox[ RowBox[{"\<\"lift \"\>", "\[InvisibleSpace]", "4", "\[InvisibleSpace]", "\<\" times\"\>"}], SequenceForm["lift ", 4, " times"], Editable->False], "\n", RowBox[{"{", RowBox[{"0.034994000000000025`", ",", "539.5078355690675`"}], "}"}], "\n", RowBox[{"{", RowBox[{"0.1039850000000001`", ",", "470.6587971147544`"}], "}"}], "\n", RowBox[{"{", RowBox[{"0.5379169999999998`", ",", "359.2849701421794`"}], "}"}], "\n", RowBox[{"{", RowBox[{"2.50162`", ",", "128.57172429100962`"}], "}"}]}], "Print", GeneratedCell->False, CellAutoOverwrite->False, CellChangeTimes->{ 3.443457657118554*^9, 3.443457712663455*^9, 3.4434577708742037`*^9, 3.443457826680985*^9, 3.470071376845099*^9, {3.470071591852972*^9, 3.4700716096307173`*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{"3.191515`", ",", RowBox[{ RowBox[{ RowBox[{"-", "40"}], " ", SuperscriptBox["x", "2"]}], "-", RowBox[{"39", " ", SuperscriptBox["x", "6"]}], "-", RowBox[{"28", " ", SuperscriptBox["x", "8"]}], "-", RowBox[{"44", " ", SuperscriptBox["x", "9"]}], "-", RowBox[{"36", " ", SuperscriptBox["x", "3"], " ", "y"}], "+", RowBox[{"73", " ", SuperscriptBox["x", "9"], " ", "y"}], "+", RowBox[{"99", " ", SuperscriptBox["y", "2"]}], "-", RowBox[{"55", " ", "x", " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"40", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"82", " ", SuperscriptBox["x", "6"], " ", SuperscriptBox["y", "2"]}], "-", RowBox[{"18", " ", SuperscriptBox["x", "7"], " ", SuperscriptBox["y", "2"]}], "-", RowBox[{"13", " ", SuperscriptBox["y", "3"]}], "-", RowBox[{"31", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"34", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "3"]}], "-", RowBox[{"76", " ", SuperscriptBox["x", "4"], " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"96", " ", SuperscriptBox["y", "4"]}], "+", RowBox[{"9", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "4"]}], "-", RowBox[{"99", " ", SuperscriptBox["x", "6"], " ", SuperscriptBox["y", "4"]}], "-", RowBox[{"66", " ", "x", " ", SuperscriptBox["y", "5"]}], "+", RowBox[{"12", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "5"]}], "+", RowBox[{"16", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "5"]}], "+", RowBox[{"27", " ", SuperscriptBox["x", "5"], " ", SuperscriptBox["y", "5"]}], "+", RowBox[{"20", " ", SuperscriptBox["y", "6"]}], "+", RowBox[{"40", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "6"]}], "+", RowBox[{"83", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "7"]}], "+", RowBox[{"89", " ", SuperscriptBox["y", "8"]}], "-", RowBox[{"71", " ", "x", " ", SuperscriptBox["y", "8"]}], "-", RowBox[{"38", " ", "x", " ", SuperscriptBox["y", "9"]}], "+", RowBox[{"11", " ", SuperscriptBox["y", "10"]}]}]}], "}"}]], "Output", CellChangeTimes->{3.4700713807137613`*^9, 3.47007159514634*^9}] }, Open ]], Cell[TextData[{ "We see that this recovers (up to sign) the factor ", Cell[BoxData[ FormBox[ StyleBox["p2", FontSlant->"Italic"], TraditionalForm]]], "." }], "Text", CellChangeTimes->{{3.42469489623906*^9, 3.424694914482002*^9}, { 3.44242472189854*^9, 3.442424721898663*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Together", "[", RowBox[{"factor", "/", "p2"}], "]"}]], "Input", CellChangeTimes->{{3.424694855162957*^9, 3.424694862890804*^9}, 3.442424717908841*^9}], Cell[BoxData[ RowBox[{"-", "1"}]], "Output", CellChangeTimes->{3.424694869060989*^9, 3.470071636238285*^9}] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Example 5", "Subsubsection", CellChangeTimes->{{3.42452357768865*^9, 3.42452358058054*^9}, 3.442089399913357*^9}], Cell[TextData[{ "Our final example is a modification of one appearing in [", CounterBox["Reference", "Corless Galligo Kotsireas Watt"], "]. The goal is to find the absolute factorization of a certain bivariate \ polynomial. Our modification subtracts ", Cell[BoxData[ FormBox[ StyleBox[ RowBox[{ RowBox[{ SuperscriptBox["x", "5"], " ", "y"}], "+", SuperscriptBox["x", "4"], "+", SuperscriptBox["x", "3"]}], FontWeight->"Plain"], TraditionalForm]], "Input"], " from the polynomial in the reference, so that it will factor nontrivially \ over some extension field (which is to be determined in the process)." }], "Text", CellChangeTimes->{{3.419961433152384*^9, 3.419961441480724*^9}, { 3.419962492175418*^9, 3.419962511792269*^9}, {3.419963044121213*^9, 3.419963061757833*^9}, {3.419964044561373*^9, 3.419964118236864*^9}, { 3.419964175398194*^9, 3.419964273787803*^9}, {3.419966783972707*^9, 3.419966802238256*^9}, {3.423943755986007*^9, 3.423943756871584*^9}, { 3.424523620636912*^9, 3.424523621369289*^9}, {3.42464601713436*^9, 3.424646032083743*^9}, {3.424715208340566*^9, 3.42471520871757*^9}, { 3.433705907861396*^9, 3.433705910228187*^9}, {3.469557353633595*^9, 3.469557363358553*^9}}], Cell[BoxData[ RowBox[{ RowBox[{"poly", "=", RowBox[{ RowBox[{"-", "3"}], "-", RowBox[{"16", " ", "x"}], "-", RowBox[{"20", " ", SuperscriptBox["x", "2"]}], "-", RowBox[{"11", " ", SuperscriptBox["x", "3"]}], "-", RowBox[{"2", " ", SuperscriptBox["x", "4"]}], "-", RowBox[{"4", " ", SuperscriptBox["x", "5"]}], "-", RowBox[{"8", " ", SuperscriptBox["x", "7"]}], "-", RowBox[{"3", " ", SuperscriptBox["x", "9"]}], "+", RowBox[{"7", " ", "y"}], "-", RowBox[{"16", " ", SuperscriptBox["x", "2"], " ", "y"}], "-", RowBox[{"16", " ", SuperscriptBox["x", "3"], " ", "y"}], "+", RowBox[{"5", " ", SuperscriptBox["x", "4"], " ", "y"}], "-", RowBox[{"4", " ", SuperscriptBox["x", "5"], " ", "y"}], "+", RowBox[{"8", " ", SuperscriptBox["x", "6"], " ", "y"}], "-", RowBox[{"4", " ", SuperscriptBox["x", "7"], " ", "y"}], "+", RowBox[{"3", " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"4", " ", "x", " ", SuperscriptBox["y", "2"]}], "-", RowBox[{ SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "2"]}], "-", RowBox[{"11", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"3", " ", SuperscriptBox["x", "4"], " ", SuperscriptBox["y", "2"]}], "-", RowBox[{ SuperscriptBox["x", "5"], " ", SuperscriptBox["y", "2"]}], "+", RowBox[{"8", " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"8", " ", "x", " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"5", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "3"]}], "-", RowBox[{"5", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"6", " ", SuperscriptBox["x", "4"], " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"8", " ", SuperscriptBox["x", "6"], " ", SuperscriptBox["y", "3"]}], "+", RowBox[{"6", " ", SuperscriptBox["y", "4"]}], "+", RowBox[{"4", " ", "x", " ", SuperscriptBox["y", "4"]}], "+", RowBox[{"4", " ", SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "4"]}], "-", RowBox[{"10", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "4"]}], "+", RowBox[{"3", " ", SuperscriptBox["x", "4"], " ", SuperscriptBox["y", "4"]}], "+", RowBox[{"3", " ", SuperscriptBox["y", "5"]}], "+", RowBox[{ SuperscriptBox["x", "2"], " ", SuperscriptBox["y", "5"]}], "+", RowBox[{"3", " ", SuperscriptBox["y", "6"]}], "-", RowBox[{"5", " ", SuperscriptBox["x", "3"], " ", SuperscriptBox["y", "6"]}], "+", RowBox[{"3", " ", SuperscriptBox["y", "7"]}], "+", SuperscriptBox["y", "9"]}]}], ";"}]], "Input", CellChangeTimes->{{3.4199624310563*^9, 3.419962461574352*^9}, { 3.419964021795374*^9, 3.419964034426834*^9}}], Cell[TextData[{ "One can check that this polynomial is irreducible over the rationals. To \ proceed with the absolute factorization, we first substitute a value for one \ variable (we use ", Cell[BoxData[ FormBox["x", TraditionalForm]]], "), and solve numerically to high precision for the roots of the resulting \ univariate. We show a low precision approximation to the first root in the \ list." }], "Text", CellChangeTimes->{{3.419962514912355*^9, 3.419962546542741*^9}, 3.419962585454476*^9, {3.41996306489844*^9, 3.419963093524773*^9}, { 3.424696707507976*^9, 3.424696721860613*^9}, {3.424696767165758*^9, 3.424696767166011*^9}}], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{ RowBox[{"x0", "=", RowBox[{"11", "/", "7"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"roots", " ", "=", " ", RowBox[{"y", " ", "/.", " ", RowBox[{"NSolve", "[", RowBox[{ RowBox[{"poly", "/.", RowBox[{"x", "\[Rule]", "x0"}]}], ",", " ", RowBox[{"WorkingPrecision", "\[Rule]", "400"}]}], "]"}]}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"root1", "=", RowBox[{"First", "[", "roots", "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"N", "[", "root1", "]"}]}], "Input", CellChangeTimes->{{3.419962579105199*^9, 3.419962579714497*^9}, { 3.419962683360663*^9, 3.419962693380582*^9}, 3.419963111909213*^9, { 3.419963330279119*^9, 3.419963348937636*^9}, 3.419963517294877*^9, 3.419963564484946*^9, {3.419963616454569*^9, 3.419963640183817*^9}, 3.419963777086793*^9, {3.419964039695279*^9, 3.41996404101098*^9}, 3.419964288525845*^9, {3.424696687086677*^9, 3.42469669875752*^9}, { 3.424696786599792*^9, 3.424696808900109*^9}, {3.424785685385727*^9, 3.424785685897247*^9}}], Cell[BoxData[ RowBox[{ RowBox[{"-", "1.3138553614216648`"}], "-", RowBox[{"1.393382650887247`", " ", "\[ImaginaryI]"}]}]], "Output", CellChangeTimes->{{3.424696687691439*^9, 3.424696700101511*^9}, 3.424696821651*^9, {3.42478567923773*^9, 3.424785687289581*^9}, 3.4426584777609777`*^9, 3.443211616913352*^9}] }, Open ]], Cell[TextData[{ "We now attempt to reconstruct the factor containing the first of our roots. \ We will just do a direct lift to degree 10, that is, modulo ", Cell[BoxData[ FormBox[ RowBox[{"{", RowBox[{ SuperscriptBox[ RowBox[{"(", RowBox[{"x", " ", "-", " ", StyleBox["x0", FontSlant->"Italic"]}], ")"}], "10"], ",", SuperscriptBox[ RowBox[{"(", RowBox[{"y", "-", StyleBox["root1", FontSlant->"Italic"]}], ")"}], "10"]}], "}"}], TraditionalForm]]], ". This suffices because any nontrivial factor must have a degree that \ divides 9 (since it gives the full polynomial when multiplied by its equal\ \[Hyphen]degree conjugates). The only candidates are 1 and 3, so by prior \ theory a lift to degree ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ SuperscriptBox["3", "2"], "+", "1"}], "=", "10"}], TraditionalForm]]], " suffices." }], "Text", CellChangeTimes->{{3.419962623651703*^9, 3.419962643972025*^9}, { 3.424696733108111*^9, 3.424696748459803*^9}, {3.42469683583296*^9, 3.424696838837621*^9}, {3.424696886594337*^9, 3.424696934474478*^9}, { 3.424708354312494*^9, 3.424708368499168*^9}, {3.442658530203519*^9, 3.442658632393579*^9}, {3.443359681273094*^9, 3.4433596915723763`*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Timing", "[", RowBox[{ RowBox[{"fac", " ", "=", RowBox[{"First", "[", " ", RowBox[{"GroebnerBasis", "[", RowBox[{ RowBox[{"{", RowBox[{"poly", ",", RowBox[{ RowBox[{"(", RowBox[{"y", "-", "root1"}], ")"}], "^", "10"}], ",", RowBox[{ RowBox[{"(", RowBox[{"x", "-", "x0"}], ")"}], "^", "10"}]}], "}"}], ",", " ", RowBox[{"{", RowBox[{"y", ",", "x"}], "}"}], ",", "\n", " ", RowBox[{"MonomialOrder", "->", "DegreeReverseLexicographic"}], ",", "\n", " ", RowBox[{"CoefficientDomain", "->", "InexactNumbers"}]}], "]"}], "]"}]}], ";"}], "]"}]], "Input", CellChangeTimes->{ 3.419962657972157*^9, {3.419962699329601*^9, 3.419962732570492*^9}, { 3.419962985725486*^9, 3.41996300595665*^9}, {3.419963115542775*^9, 3.419963117652846*^9}, {3.419963192028843*^9, 3.419963196797733*^9}, { 3.419963271760453*^9, 3.419963278112954*^9}, {3.419963340183303*^9, 3.419963367950157*^9}, {3.419963412572343*^9, 3.41996341635718*^9}, { 3.419963453864148*^9, 3.419963455193256*^9}, {3.419963487234689*^9, 3.41996348883903*^9}, {3.41996352209402*^9, 3.419963524600712*^9}, { 3.41996368842728*^9, 3.419963690387732*^9}, {3.419964293118622*^9, 3.419964343652585*^9}, {3.424696818702605*^9, 3.424696819213897*^9}, { 3.424708254136156*^9, 3.424708257895658*^9}, {3.424708298089527*^9, 3.424708331498553*^9}, {3.4426584879371967`*^9, 3.442658492701015*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{"0.5429169999997612`", ",", "Null"}], "}"}]], "Output", CellChangeTimes->{3.442658495006734*^9}] }, Open ]], Cell["\<\ Here is a low precision version of our candidate factor.\ \>", "Text", CellChangeTimes->{{3.41996442278666*^9, 3.41996443610738*^9}, { 3.500233239664679*^9, 3.500233241178033*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Chop", "[", RowBox[{"N", "[", "fac", "]"}], "]"}]], "Input", CellChangeTimes->{{3.419963660623048*^9, 3.419963663701991*^9}, { 3.419964361562846*^9, 3.419964363492479*^9}, {3.419964407035714*^9, 3.419964419058991*^9}}], Cell[BoxData[ RowBox[{ RowBox[{"(", RowBox[{"1.6823278038280194`", "\[InvisibleSpace]", "+", RowBox[{"2.323082799994504`", " ", "\[ImaginaryI]"}]}], ")"}], "+", RowBox[{ RowBox[{"(", RowBox[{"0.6823278038280193`", "\[InvisibleSpace]", "+", RowBox[{"2.323082799994504`", " ", "\[ImaginaryI]"}]}], ")"}], " ", "x"}], "-", RowBox[{ RowBox[{"(", RowBox[{"2.232785615938384`", "\[InvisibleSpace]", "-", RowBox[{"0.7925519925154478`", " ", "\[ImaginaryI]"}]}], ")"}], " ", SuperscriptBox["x", "3"]}], "+", RowBox[{"1.`", " ", "y"}], "+", RowBox[{ RowBox[{"(", RowBox[{"0.34116390191400964`", "\[InvisibleSpace]", "+", RowBox[{"1.161541399997252`", " ", "\[ImaginaryI]"}]}], ")"}], " ", "x", " ", "y"}], "+", RowBox[{"1.`", " ", SuperscriptBox["y", "3"]}]}]], "Output", CellChangeTimes->{ 3.419963670661464*^9, 3.419963708685989*^9, 3.419963799463645*^9, { 3.41996432325982*^9, 3.419964365143134*^9}, {3.419964411298472*^9, 3.419964419634342*^9}, 3.424696957533668*^9, 3.42470833597793*^9, 3.443211631253848*^9}] }, Open ]], Cell[TextData[{ "Before we proceed to deduce the exact form of this result, we should check \ that it is a viable candidate factor. Specifically, it must divide our \ polynomial. We may verify this using generalized division. In ", StyleBox["Mathematica", FontSlant->"Italic"], " this is accomplished with ", StyleBox["PolynomialReduce", "Program"], "." }], "Text", CellChangeTimes->{3.4424299642227287`*^9}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{ RowBox[{"PolynomialReduce", "[", RowBox[{"poly", ",", " ", "fac", ",", " ", RowBox[{"{", RowBox[{"y", ",", "x"}], "}"}], ",", "\n", " ", RowBox[{"CoefficientDomain", "->", "InexactNumbers"}], ",", "\n", " ", RowBox[{"MonomialOrder", "->", "DegreeReverseLexicographic"}]}], "]"}], "[", RowBox[{"[", "2", "]"}], "]"}]], "Input", CellChangeTimes->{ 3.419963251495571*^9, {3.41996328151596*^9, 3.419963281912008*^9}, 3.419964501723733*^9}], Cell[BoxData["0"], "Output", CellChangeTimes->{3.419964350663022*^9, 3.424696976156467*^9, 3.424708343153309*^9, 3.424785727984533*^9, 3.443211636015881*^9}] }, Open ]], Cell[TextData[{ "This is promising. We now take the numeric coefficients of our factor and \ attempt to recast them as algebraic numbers. For this we use ", StyleBox["RootApproximant", "Program"], " along with a small amount of code to convert representations to all use a \ common algebraic number (", StyleBox["RootApproximant", "Program"], " uses functionality based on [", CounterBox["Reference", "Ferguson Bailey Arno"], ", ", CounterBox["Reference", "Lenstra"], "]). We show the timing in seconds." }], "Text", CellChangeTimes->{{3.419969912595063*^9, 3.419969914973153*^9}, { 3.419970087251986*^9, 3.419970087618288*^9}, {3.424708502264014*^9, 3.424708556541169*^9}, {3.42471383681278*^9, 3.424713918632905*^9}, { 3.443359706341626*^9, 3.4433597159353*^9}, {3.492976440150208*^9, 3.492976459537758*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Timing", "[", "\[IndentingNewLine]", RowBox[{ RowBox[{"dtl", "=", RowBox[{"Chop", "[", RowBox[{"GroebnerBasis`DistributedTermsList", "[", RowBox[{"fac", ",", " ", RowBox[{"{", RowBox[{"y", ",", "x"}], "}"}]}], "]"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"newdtl", "=", RowBox[{"MapAt", "[", RowBox[{"RootApproximant", ",", "dtl", ",", RowBox[{"Thread", "[", RowBox[{"{", RowBox[{"1", ",", RowBox[{"Range", "[", RowBox[{"Length", "[", RowBox[{"dtl", "[", RowBox[{"[", "1", "]"}], "]"}], "]"}], "]"}], ",", "2"}], "}"}], "]"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"rtlist", "=", RowBox[{"Cases", "[", RowBox[{"newdtl", ",", RowBox[{"Root", "[", "__", "]"}], ",", "Infinity"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"firstrt", "=", RowBox[{"First", "[", "rtlist", "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"newroots", "=", RowBox[{"Join", "[", RowBox[{ RowBox[{"{", "firstrt", "}"}], ",", RowBox[{"ToNumberField", "[", RowBox[{ RowBox[{"Rest", "[", "rtlist", "]"}], ",", "firstrt"}], "]"}]}], "]"}]}], ";", RowBox[{"newroots", "=", RowBox[{"newroots", "/.", RowBox[{ RowBox[{"AlgebraicNumber", "[", RowBox[{"aa_", ",", "bb_"}], "]"}], ":>", RowBox[{"AlgebraicNumberPolynomial", "[", RowBox[{ RowBox[{"AlgebraicNumber", "[", RowBox[{"aa", ",", "bb"}], "]"}], ",", "aa"}], "]"}]}]}]}], ";", "\[IndentingNewLine]", RowBox[{"newdtl", "=", RowBox[{"newdtl", "/.", RowBox[{"Thread", "[", RowBox[{"rtlist", "\[Rule]", "newroots"}], "]"}]}]}], ";", "\[IndentingNewLine]", RowBox[{"algfactor", "=", RowBox[{ "GroebnerBasis`FromDistributedTermsList", "[", "newdtl", "]"}]}]}], "]"}]], "Input", CellChangeTimes->{{3.424708607664979*^9, 3.424708649086983*^9}, { 3.424708686508173*^9, 3.424708740823603*^9}, 3.424708796365032*^9, { 3.424708886415894*^9, 3.424708924924965*^9}, {3.424712547076937*^9, 3.424712577394154*^9}, {3.424712636654807*^9, 3.424712680832861*^9}, { 3.424712714921679*^9, 3.424712716539969*^9}, {3.424712794381326*^9, 3.42471284064143*^9}, {3.424712976248217*^9, 3.424713087335569*^9}, { 3.424713167231809*^9, 3.424713170466292*^9}, {3.424713230364194*^9, 3.424713255702268*^9}, {3.424713308587223*^9, 3.424713415598121*^9}, 3.424713452067959*^9, {3.424713636491051*^9, 3.4247137096596*^9}, { 3.424713741833964*^9, 3.424713759343393*^9}, {3.424713821633946*^9, 3.42471382555716*^9}, {3.443211245462888*^9, 3.44321129221154*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{"0.38894100000015897`", ",", RowBox[{"1", "+", "y", "+", SuperscriptBox["y", "3"], "+", RowBox[{"2", " ", RowBox[{"Root", "[", RowBox[{ RowBox[{ RowBox[{"1", "+", "#1", "+", SuperscriptBox["#1", "3"]}], "&"}], ",", "3"}], "]"}]}], "+", RowBox[{"2", " ", "x", " ", RowBox[{"Root", "[", RowBox[{ RowBox[{ RowBox[{"1", "+", "#1", "+", SuperscriptBox["#1", "3"]}], "&"}], ",", "3"}], "]"}]}], "+", RowBox[{"x", " ", "y", " ", RowBox[{"Root", "[", RowBox[{ RowBox[{ RowBox[{"1", "+", "#1", "+", SuperscriptBox["#1", "3"]}], "&"}], ",", "3"}], "]"}]}], "+", RowBox[{ SuperscriptBox["x", "3"], " ", RowBox[{"(", RowBox[{ RowBox[{"-", "1"}], "+", SuperscriptBox[ RowBox[{"Root", "[", RowBox[{ RowBox[{ RowBox[{"1", "+", "#1", "+", SuperscriptBox["#1", "3"]}], "&"}], ",", "3"}], "]"}], "2"]}], ")"}]}]}]}], "}"}]], "Output", CellChangeTimes->{3.443211642861096*^9}] }, Open ]], Cell[TextData[{ "We can check the result as follows. Irreducibility of ", Cell[BoxData[ FormBox[ StyleBox["poly", "Text", FontSlant->"Italic"], TraditionalForm]]], " over the rationals implies that all algebraic factors are conjugates of \ one another. We can explicitly form the product of these conjugates, then \ check that their product recovers the polynomial up to an invertible (that \ is, rational) factor. We show this below." }], "Text", CellChangeTimes->{ 3.424713671001556*^9, {3.424786088432359*^9, 3.424786117510675*^9}, { 3.424786154765065*^9, 3.4247862386186*^9}, 3.442089333576706*^9}, CellID->466588476], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"algprod", "=", RowBox[{"Product", "[", RowBox[{ RowBox[{"algfactor", "/.", RowBox[{ RowBox[{"Root", "[", RowBox[{"a_", ",", "3", ",", "b___"}], "]"}], "\[RuleDelayed]", RowBox[{"Root", "[", RowBox[{"a", ",", "j", ",", "b"}], "]"}]}]}], ",", RowBox[{"{", RowBox[{"j", ",", "3"}], "}"}]}], "]"}]}]], "Input", CellChangeTimes->{{3.424785584562861*^9, 3.424785660731918*^9}, { 3.424785779973779*^9, 3.424785836113583*^9}, {3.424785881640322*^9, 3.424785935804898*^9}, {3.424785984131725*^9, 3.424786076940716*^9}, { 3.424786244219413*^9, 3.424786274009976*^9}}], Cell[BoxData[ RowBox[{ RowBox[{"(", RowBox[{"1", "+", "y", "+", SuperscriptBox["y", "3"], "+", RowBox[{"2", " ", RowBox[{"Root", "[", RowBox[{ RowBox[{ RowBox[{"1", "+", "#1", "+", SuperscriptBox["#1", "3"]}], "&"}], ",", "1"}], "]"}]}], "+", RowBox[{"2", " ", "x", " ", RowBox[{"Root", "[", RowBox[{ RowBox[{ RowBox[{"1", "+", "#1", "+", SuperscriptBox["#1", "3"]}], "&"}], ",", "1"}], "]"}]}], "+", RowBox[{"x", " ", "y", " ", RowBox[{"Root", "[", RowBox[{ RowBox[{ RowBox[{"1", "+", "#1", "+", SuperscriptBox["#1", "3"]}], "&"}], ",", "1"}], "]"}]}], "+", RowBox[{ SuperscriptBox["x", "3"], " ", RowBox[{"(", RowBox[{ RowBox[{"-", "1"}], "+", SuperscriptBox[ RowBox[{"Root", "[", RowBox[{ RowBox[{ RowBox[{"1", "+", "#1", "+", SuperscriptBox["#1", "3"]}], "&"}], ",", "1"}], "]"}], "2"]}], ")"}]}]}], ")"}], " ", RowBox[{"(", RowBox[{"1", "+", "y", "+", SuperscriptBox["y", "3"], "+", RowBox[{"2", " ", RowBox[{"Root", "[", RowBox[{ RowBox[{ RowBox[{"1", "+", "#1", "+", SuperscriptBox["#1", "3"]}], "&"}], ",", "2"}], "]"}]}], "+", RowBox[{"2", " ", "x", " ", RowBox[{"Root", "[", RowBox[{ RowBox[{ RowBox[{"1", "+", "#1", "+", SuperscriptBox["#1", "3"]}], "&"}], ",", "2"}], "]"}]}], "+", RowBox[{"x", " ", "y", " ", RowBox[{"Root", "[", RowBox[{ RowBox[{ RowBox[{"1", "+", "#1", "+", SuperscriptBox["#1", "3"]}], "&"}], ",", "2"}], "]"}]}], "+", RowBox[{ SuperscriptBox["x", "3"], " ", RowBox[{"(", RowBox[{ RowBox[{"-", "1"}], "+", SuperscriptBox[ RowBox[{"Root", "[", RowBox[{ RowBox[{ RowBox[{"1", "+", "#1", "+", SuperscriptBox["#1", "3"]}], "&"}], ",", "2"}], "]"}], "2"]}], ")"}]}]}], ")"}], " ", RowBox[{"(", RowBox[{"1", "+", "y", "+", SuperscriptBox["y", "3"], "+", RowBox[{"2", " ", RowBox[{"Root", "[", RowBox[{ RowBox[{ RowBox[{"1", "+", "#1", "+", SuperscriptBox["#1", "3"]}], "&"}], ",", "3"}], "]"}]}], "+", RowBox[{"2", " ", "x", " ", RowBox[{"Root", "[", RowBox[{ RowBox[{ RowBox[{"1", "+", "#1", "+", SuperscriptBox["#1", "3"]}], "&"}], ",", "3"}], "]"}]}], "+", RowBox[{"x", " ", "y", " ", RowBox[{"Root", "[", RowBox[{ RowBox[{ RowBox[{"1", "+", "#1", "+", SuperscriptBox["#1", "3"]}], "&"}], ",", "3"}], "]"}]}], "+", RowBox[{ SuperscriptBox["x", "3"], " ", RowBox[{"(", RowBox[{ RowBox[{"-", "1"}], "+", SuperscriptBox[ RowBox[{"Root", "[", RowBox[{ RowBox[{ RowBox[{"1", "+", "#1", "+", SuperscriptBox["#1", "3"]}], "&"}], ",", "3"}], "]"}], "2"]}], ")"}]}]}], ")"}]}]], "Output", CellChangeTimes->{3.443211668421419*^9}] }, Open ]], Cell[TextData[{ "Next we collect all terms in the polynomial, operating on the coefficients \ to obtain reduced forms. These will be algebraics of minimal degree; what we \ hope to get for all coefficients are rationals. We do, because the result \ cancels perfectly with ", Cell[BoxData[ FormBox[ StyleBox["poly", FontSlant->"Italic"], TraditionalForm]]], "." }], "Text", CellChangeTimes->{{3.424786278501592*^9, 3.424786400440122*^9}, { 3.424788066492686*^9, 3.424788067394939*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Together", "[", RowBox[{ RowBox[{"Expand", "[", RowBox[{"RootReduce", "[", RowBox[{"Collect", "[", RowBox[{ RowBox[{"Expand", "[", "algprod", "]"}], ",", RowBox[{"{", RowBox[{"x", ",", "y"}], "}"}]}], "]"}], "]"}], "]"}], "/", "poly"}], "]"}]], "Input", CellChangeTimes->{{3.424785584562861*^9, 3.424785660731918*^9}, { 3.424785779973779*^9, 3.424785836113583*^9}, {3.424785881640322*^9, 3.424785935804898*^9}, {3.424785984131725*^9, 3.424786076940716*^9}, { 3.424786244219413*^9, 3.424786274009976*^9}}], Cell[BoxData["1"], "Output", CellChangeTimes->{ 3.424785667720977*^9, 3.424785758141034*^9, {3.424785807865632*^9, 3.424785837636998*^9}, {3.424785884546019*^9, 3.424785950266703*^9}, { 3.424786011482529*^9, 3.424786027175207*^9}, {3.424786065650513*^9, 3.424786077513757*^9}, 3.424786244787181*^9, 3.424786412711212*^9}] }, Open ]], Cell[TextData[{ "We remark that there are other good ways to recover exact algebraic \ coefficients, if one first finds the set of all approximate factors. One such \ is presented in [", CounterBox["Reference", "Cheze Galligo"], "], where an analysis of needed precision is also provided." }], "Text", CellChangeTimes->{{3.424786654054166*^9, 3.424786687475497*^9}, { 3.424787193134121*^9, 3.424787242487332*^9}, {3.424788080352679*^9, 3.424788118839517*^9}, {3.443210011239924*^9, 3.443210163797393*^9}, { 3.443359749414366*^9, 3.443359788623958*^9}, {3.469819727683869*^9, 3.469819728641983*^9}}], Cell[TextData[{ "We also observe that the method shown above, while perhaps not as efficient \ as those of [", CounterBox["Reference", "Cheze"], ", ", CounterBox["Reference", "Sasaki"], "], is nonetheless faster than ", StyleBox["Mathematica", FontSlant->"Italic"], "'s current built in capabilities. Moreover these latter require that one \ know in advance the extension field. We show this explicitly below (the \ method will only split off one full factor, but that suffices to recover its \ conjugates)." }], "Text", CellChangeTimes->{{3.492900899224433*^9, 3.492900937301169*^9}, { 3.492901026661091*^9, 3.49290111824572*^9}, {3.492909352001597*^9, 3.492909357757594*^9}, {3.4929095312555513`*^9, 3.4929095472140503`*^9}, { 3.500233349915572*^9, 3.500233351032187*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Timing", "[", RowBox[{ RowBox[{"fax", "=", RowBox[{"FactorList", "[", RowBox[{"poly", ",", RowBox[{"Extension", "\[Rule]", RowBox[{"Root", "[", RowBox[{ RowBox[{ RowBox[{"1", "+", "#1", "+", SuperscriptBox["#1", "3"]}], "&"}], ",", "3"}], "]"}]}]}], "]"}]}], ";"}], "]"}]], "Input", CellChangeTimes->{{3.4929007727188807`*^9, 3.492900811967454*^9}, { 3.492900846222557*^9, 3.4929008576278133`*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{"0.6788960000000017`", ",", "Null"}], "}"}]], "Output", CellChangeTimes->{3.492901013391803*^9}] }, Open ]], Cell[TextData[{ "We also note that while this might not provide a multivariate absolute \ factorization method that scales well as the number of variables grows, it \ can at least quickly determine irreducibility (with high probability). This \ would be effected simply by deciding whether there are numeric approximate \ factors after substitution for all but two variables. Lifting of all \ variables and exact recovery of nontrivial factors, if any, would not be \ needed in such a scenario; we only need lift in one variable, and that only \ approximately, in order to determine whether a given input is irreducible. A \ practical, nontrivial example from constraint geometry may be found in [", CounterBox["Reference", "Lichtblau 3"], "]. The polynomial in question is trivariate, of total degree 16 and with \ all exponents even. It is dense subject to those constraints, and has \ coefficients ranging from two to ten digits in size." }], "Text", CellChangeTimes->{{3.424786654054166*^9, 3.424786687475497*^9}, { 3.424787193134121*^9, 3.424787242487332*^9}, {3.424788080352679*^9, 3.424788118839517*^9}, {3.443210011239924*^9, 3.443210163797393*^9}, { 3.443359749414366*^9, 3.443359788623958*^9}, {3.4695550014500732`*^9, 3.469555144811253*^9}, {3.46955631069446*^9, 3.46955631811679*^9}, { 3.4840549072978277`*^9, 3.484054907426037*^9}, {3.484055272539089*^9, 3.484055407414412*^9}, {3.484055458711378*^9, 3.4840554754929*^9}, 3.48405550678402*^9, {3.4874280019019737`*^9, 3.487428007264773*^9}, { 3.487516211879551*^9, 3.487516214726458*^9}, {3.492539262213152*^9, 3.492539268688922*^9}, 3.492539306786995*^9, {3.500233481118359*^9, 3.500233499284988*^9}}] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[TextData[{ Cell[TextData[{ StyleBox[ CounterBox["Section"], "SectionNumber"], StyleBox[". ", "SectionNumber"] }], "SectionDingbat"], "FAILURE MODES AND VERIFICATION OF RESULTS" }], "Section", CellChangeTimes->{{3.424647121579646*^9, 3.424647131056958*^9}, { 3.469558825213174*^9, 3.469558826090227*^9}, {3.4698013639694223`*^9, 3.469801424452478*^9}, {3.492965073047927*^9, 3.4929650884037437`*^9}, { 3.492968781107544*^9, 3.492968784093655*^9}, {3.492969988468239*^9, 3.492970011457622*^9}}], Cell["\<\ There are three failure modes for our use of finite precision. One is to run \ out of precision in the Gr\[ODoubleDot]bner basis phase, and abort \ computation. Another is to compute a Gr\[ODoubleDot]bner basis that has the \ wrong structure, and thus either fail to find an approximately correct factor \ or else find a putative factor that is entirely wrong. A last type of failure \ is to find a factor that is approximately correct, but does not have \ sufficient precision from which to recover an exact form thereof.\ \>", "Text", CellChangeTimes->{{3.4929650915886374`*^9, 3.492965255721242*^9}, { 3.492965543725233*^9, 3.492965585305006*^9}, {3.492966254907694*^9, 3.492966298074429*^9}, {3.492976632673571*^9, 3.492976636196012*^9}, { 3.500233651442655*^9, 3.5002336728649*^9}}], Cell["\<\ The first form of failure is typically handled by increasing the initial \ precision a few times, until either we obtain a result or else reach some \ upper bound. In this case we have a \"do not know the result\" situation, \ which is at least preferable to an incorrect result.\ \>", "Text", CellChangeTimes->{{3.492965599766348*^9, 3.492965684964566*^9}}], Cell["\<\ Now suppose we have obtained a putative approximate factor or gcd. A first \ question is to decide whether it is in fact a viable approximation to an \ exact one. This determination can typically be made by polynomial division, \ checking that coefficients in any remainder are suitably small. If we have a \ reasonable approximation, we can often improve it by local numerical \ optimization methods. One uses the coefficients of the approximated factor as \ a starting point in order to improve the precision. The objective function \ could be, for example, a sum of squares of coefficients in the remainder on \ division.\ \>", "Text", CellChangeTimes->{{3.49296534703365*^9, 3.492965436285948*^9}, { 3.492965484571392*^9, 3.492965515708469*^9}, {3.492965691478239*^9, 3.492965724436919*^9}}], Cell[TextData[{ "If we have an approximate factor or gcd that, on division, is clearly seen \ to be not viable, this also can be treated as an inconclusive case. We now \ remark on how this case can arise. In the process of computing an approximate \ Gr\[ODoubleDot]bner basis, we might err in a cancellation of terms, such that \ we decide a leading coefficient is zero. This is the only way to get a result \ that is structurally incorrect, that is, has the wrong polynomial skeleton. \ We do not have a theoretical argument to quantify how rare this might be. We \ can, however, say a bit about practical experience. In over a decade of \ operation, the numeric Gr\[ODoubleDot]bner basis capabilities of ", StyleBox["Mathematica", FontSlant->"Italic"], "'s ", StyleBox["NSolve", "Program"], " have never shown this type of failure in problems that arise \ in\[Hyphen]house, from users of the software, or from testing done on \ benchmark problems from the literature." }], "Text", CellChangeTimes->{{3.492966090938696*^9, 3.4929662368077927`*^9}, { 3.492966312694338*^9, 3.492966345189138*^9}, {3.492966375894434*^9, 3.4929666832012463`*^9}, {3.4929680575413713`*^9, 3.49296816798114*^9}, { 3.49296934307718*^9, 3.492969475138275*^9}, {3.500233810706901*^9, 3.5002338191982107`*^9}, {3.5002338949572487`*^9, 3.500233897148494*^9}}], Cell["\<\ As with any numeric method one can likely create a problem for which it will \ fail if run at too low precision. It seems that such problems do not arise \ with any frequency in practice. We can offer a tentative explanation for \ this. Recall theorem 1: For a give problem and a given output precision, \ there exists an input precision such that computing a Gr\[ODoubleDot]bner \ basis at that initial precision, using significance arithmetic, will give a \ result that is correct to the specified output precision. While it is \ impractically high for realistic problems it seems that a more modest \ precision typically suffices. And when it does not suffice we almost always \ lose too much precision and abort. In order to obtain a skeletally incorrect \ result we would have to have a catastrophic cancellation. This means that \ what should be a nonzero term (e.g. in an exact or at least sufficiently high \ precision computation) appeared to be zero. In order for cancellation at all \ significant places to occur we effectively require polynomials with \ coefficients that are commensurately far apart in scale. When the precision \ is in, say, the hundreds of digits, we simply do not see such polynomials in \ practical settings. As precision in the computation degrades it is of course \ more likely that we might encounter such a scale difference. But there is \ only a narrow window for this error to manifest as an incorrect cancellation; \ at sufficiently low precision (a few digits, say) the algorithm will go into \ the first mentioned failure mode, and abort. The conclusion is that we are \ much more likely to abort than to give an incorrect result.\ \>", "Text", CellChangeTimes->{{3.492966090938696*^9, 3.4929662368077927`*^9}, { 3.492966312694338*^9, 3.492966345189138*^9}, {3.492966375894434*^9, 3.4929666832012463`*^9}, {3.4929680575413713`*^9, 3.4929687515029488`*^9}, { 3.492969477982212*^9, 3.492969478051527*^9}, {3.500233979460566*^9, 3.500233983002287*^9}, {3.500234089914997*^9, 3.5002340915279512`*^9}, { 3.5002341574657917`*^9, 3.5002341676864967`*^9}, {3.500234273450857*^9, 3.50023427582689*^9}, {3.5008226926540127`*^9, 3.500822796341796*^9}}], Cell["\<\ We also observe that, should such a problematic case arise, the most likely \ manifestation in our setting would be a nontrivial result that is \ demonstrably wrong. This is because a leading term catastrophic cancellation \ is more likely to yield polynomials in the result that are too small\[Dash] \ in term order\[Dash] rather than too large. Hence we obtain a nontrivial \ putative result that fails to verify, rather than a claim that there is no \ nontrivial result.\ \>", "Text", CellChangeTimes->{{3.4929694783389673`*^9, 3.492969676012108*^9}, { 3.500235711525959*^9, 3.500235841824194*^9}}], Cell["\<\ These various observations support the view that an unverifiable wrong result \ (say, a proper divisor that is not greatest, or a factorization that is \ further factorizable) will be quite rare.\ \>", "Text", CellChangeTimes->{{3.492969676985386*^9, 3.4929697733198233`*^9}}] }, Open ]], Cell[CellGroupData[{ Cell[TextData[{ Cell[TextData[{ StyleBox[ CounterBox["Section"], "SectionNumber"], StyleBox[". ", "SectionNumber"] }], "SectionDingbat"], "SUMMARY AND FURTHER DIRECTIONS" }], "Section", CellChangeTimes->{{3.424647121579646*^9, 3.424647131056958*^9}, { 3.469558855550365*^9, 3.469558856378442*^9}}], Cell["\<\ We have indicated several ways in which approximate Gr\[ODoubleDot]bner bases \ might be used to advantage to obtain exact, verifiable results to problems in \ computational algebra. Applications include finding polynomial greatest \ common divisors and multivariate polynomial factorization. For this latter we \ indicate how to proceed both for ordinary factorization over the rationals, \ and for absolute factorization over the algebraic closure of the rationals.\ \>", "Text", CellChangeTimes->{{3.424646329721912*^9, 3.424646426189604*^9}, { 3.424647138763288*^9, 3.424647172102672*^9}, {3.44242704447322*^9, 3.4424270731085243`*^9}, {3.442427440953641*^9, 3.442427488551951*^9}, { 3.4424275237054453`*^9, 3.442427545768177*^9}, {3.442427576619418*^9, 3.442427576793275*^9}, {3.442580244351721*^9, 3.442580265181527*^9}, { 3.443359804807889*^9, 3.443359807638672*^9}, {3.4929003913645678`*^9, 3.492900529515429*^9}, {3.49290117664572*^9, 3.492901248447955*^9}, { 3.49290247651995*^9, 3.492902476746776*^9}}], Cell[TextData[{ "While our methods seem to be slower than those of e.g. [", CounterBox["Reference", "Cheze"], ", ", CounterBox["Reference", "Cheze Galligo"], "] and subsequent refinements thereof, they are still useful in practice. An \ added advantage is that they are straightforward to implement. Indeed, the ", StyleBox["Mathematica", FontSlant->"Italic"], " code used for the examples was, in total, but a few dozen a few lines. The \ quadratic lifting time seems to approximately double with each step. This is \ in accord with what one might expect using standard lift methods. There are \ at least two caveats. One is that we have no proof that the lifting \ complexity will behave this way in general. Another is that use of finite \ precision and significance arithmetic means our approach can fail and abort \ computation should we lose too much precision." }], "Text", CellChangeTimes->{{3.424646329721912*^9, 3.424646426189604*^9}, { 3.424647138763288*^9, 3.424647172102672*^9}, {3.44242704447322*^9, 3.4424270731085243`*^9}, {3.442427440953641*^9, 3.442427488551951*^9}, { 3.4424275237054453`*^9, 3.442427545768177*^9}, {3.442427576619418*^9, 3.442427576793275*^9}, {3.442580244351721*^9, 3.442580265181527*^9}, { 3.443359804807889*^9, 3.443359807638672*^9}, {3.4929003913645678`*^9, 3.492900529515429*^9}, {3.49290117664572*^9, 3.492901248447955*^9}, { 3.49290247651995*^9, 3.4929027017746983`*^9}, {3.492908426592605*^9, 3.492908432059978*^9}, 3.492976886126607*^9, {3.500822831255121*^9, 3.500822865683939*^9}}], Cell["\<\ There are many open areas that seem worthy of further investigation. We \ indicate several and also mention some preliminary findings.\ \>", "Text", CellChangeTimes->{{3.424646329721912*^9, 3.424646426189604*^9}, { 3.424647138763288*^9, 3.424647207391582*^9}, {3.492900538479844*^9, 3.492900541742872*^9}, {3.492901269171756*^9, 3.492901304572668*^9}, 3.500234562960019*^9}], Cell[CellGroupData[{ Cell["\<\ Automate selection of precision or at least develop some useful heuristic to \ assess in advance an amount that will likely succeed for the computation at \ hand. This is currently a wide open topic.\ \>", "Item1", CellChangeTimes->{{3.424646438927874*^9, 3.424646474849724*^9}, 3.424785156476327*^9, {3.4433598231094723`*^9, 3.443359824288253*^9}, 3.492905407875996*^9, {3.49290664724079*^9, 3.492906653223946*^9}, 3.4929070765990067`*^9}], Cell[TextData[{ "Modify these methods so that they might be used to tackle problems of an \ approximate nature. Inputs might only be known to a few digits, and we seek \ solutions to \[OpenCurlyDoubleQuote]nearby\[CloseCurlyDoubleQuote] problems \ that have nontrivial results (e.g. common divisors larger than 1, or more \ than one factor). Methods such as those shown in [", CounterBox["Reference", "Lichtblau 2"], "] can find approximate gcds in this setting. But they tend to be slower \ than the methods of this paper and they rely on heuristic choices of \ tolerance. A small amount of testing to date has indicated that some of the \ approximate Gr\[ODoubleDot]bner basis ideas from [", CounterBox["Reference", "Lichtblau 2"], "] might carry over to the setting of the present work. This is a topic that \ needs further experimentation." }], "Item1", CellChangeTimes->{{3.424646478749864*^9, 3.424646561308798*^9}, { 3.42464664513423*^9, 3.424646790722919*^9}, {3.44335938845713*^9, 3.443359391228922*^9}, {3.443359826325499*^9, 3.443359827072228*^9}, { 3.4700711953060226`*^9, 3.470071209962595*^9}, 3.4925348692150917`*^9, 3.492905410797295*^9, {3.492906664925475*^9, 3.4929067354802027`*^9}, 3.500822899780167*^9}], Cell["\<\ Apply these methods to the setting of finite fields, in such a way that they \ remain reasonably fast even when the characteristic is small. The problem, in \ this case, is that one might need to work in an algebraic extension. This can \ be costly for Gr\[ODoubleDot]bner basis computations. When such an extension \ is needed it is by no means clear that this approach can be made practical \ (it involves another variable and another polynomial, and this will typically \ make the computation of the needed Gr\[ODoubleDot]bner bases slower). In \ cases where no extension is required (that is to say, hypotheses of theorems \ can be satisfied with appropriate substitutions from the finite field \ itself), one would expect behavior better than that indicated in this paper. \ The reason is that the coefficient arithmetic is now bounded by the modulus \ size and moreover there is no possibility of loss of precision.\ \>", "Item1", CellChangeTimes->{{3.424646567277162*^9, 3.424646638860203*^9}, { 3.424646803281187*^9, 3.424646803492804*^9}, {3.424647213212137*^9, 3.424647213228585*^9}, {3.443359829446759*^9, 3.443359830193426*^9}, 3.4925355390235662`*^9, {3.492902999094823*^9, 3.4929029991115503`*^9}, 3.4929054143840218`*^9, {3.500234679376843*^9, 3.5002347022981443`*^9}, { 3.500234746827497*^9, 3.5002347480089483`*^9}, {3.50082291400299*^9, 3.500822921589161*^9}}], Cell["\<\ In the reverse direction, it might be possible to work over a large finite \ field and then lift to a result over the rationals. This would allow one to \ avoid approximate arithmetic although there is then the issue of avoiding \ primes that are unlucky for the given input.\ \>", "Item1", CellChangeTimes->{{3.494031090686062*^9, 3.4940311638849163`*^9}, { 3.500822935812139*^9, 3.5008229422426767`*^9}}], Cell["\<\ During lifting steps many of the Gr\[ODoubleDot]bner basis inputs seem to be \ close, in some sense, to bases with respect to a lexicographic term order. It \ would be interesting to see if conversion methods such as the \ Gr\[ODoubleDot]bner walk are effective for the computation that takes us to \ the desired term order. Preliminary tests show that the walk can be faster \ than what we did in our examples, but that it is subject to more extreme loss \ of precision. This, presumably, is from the conversion steps that occur at \ each cone traversal during the walk. It is an open problem to determine if \ this loss of precision can be avoided or at least curtailed.\ \>", "Item1", CellChangeTimes->{{3.492903000260784*^9, 3.4929030009164553`*^9}, { 3.4929034787626343`*^9, 3.492903559385901*^9}, {3.492904256476355*^9, 3.492904494998811*^9}, 3.492905416826481*^9, {3.49290564801447*^9, 3.4929056480351477`*^9}, {3.494031198228464*^9, 3.494031205715674*^9}, { 3.500234914560912*^9, 3.5002349146601963`*^9}, {3.500822955605455*^9, 3.500822999585703*^9}}], Cell["\<\ One possibility for alleviating precision loss in intermediate lift steps is \ to recompute, from the approximate bases, their exact counterparts. When \ precision is sufficient for this task, we might then numericize anew at the \ original precision. Our preliminary finding is that this tactic does help, \ but only to a small extent when using the Gr\[ODoubleDot]bner walk. All the \ same, this provides some improvement in that it allows for a lower initial \ precision, regardless of what method is used to compute the \ Gr\[ODoubleDot]bner bases for the lifting steps. Also one could try \ heuristics that gauge the precision loss at a given lifting step, and ratchet \ to accordingly higher precision in preparing for the next step. We must also \ observe that this tactic is far more likely to succeed when working over \ rationals than when doing absolute factorization. The reason is as follows. \ Given the same initial input, one will typically require far less precision \ to recover rationals for the bases produced in lift steps, than that which \ would be needed for algebraic number recovery.\ \>", "Item1", CellChangeTimes->{{3.492905649406221*^9, 3.4929057123331337`*^9}, { 3.492905989352932*^9, 3.492906021590479*^9}, {3.492906302929305*^9, 3.4929063626384697`*^9}, {3.492906398499193*^9, 3.4929064297946444`*^9}, { 3.492906460574304*^9, 3.492906517007103*^9}, {3.4929067853563433`*^9, 3.492906972081867*^9}, {3.492959018692259*^9, 3.492959018715576*^9}, 3.500234990262751*^9, {3.500235043509201*^9, 3.500235044065999*^9}}], Cell["\<\ As a referee observed, using a shear transformation to obtain a monic \ polynomial will destroy sparsity of input. We can avoid such transformations, \ in some of the algorithms presented above, at the cost of requiring higher \ degrees for lifting. It would be useful to understand the tradeoffs in \ efficiency between retaining sparsity vs. having lower lift bounds. It would \ be particularly useful to find ways to avoid the linear coordinate change and \ still have optimal lifting degree bounds.\ \>", "Item1", CellChangeTimes->{{3.492959019923182*^9, 3.4929592375830383`*^9}}], Cell["\<\ We discussed various modes of failure. It would be useful, though probably \ quite difficult, to have a better theoretical understanding of the interplay \ between initial precision and erroneous results.\ \>", "Item1", CellChangeTimes->{{3.492969786775723*^9, 3.492969892629135*^9}, { 3.492969925301478*^9, 3.492969925508524*^9}}], Cell["\<\ The examples of this paper, together with their timings, provide a proof of \ concept that the methods presented are viable. It would of course be nice to \ further improve on speed (above and beyond ideas noted in the preceding \ items). A recent line of inquiry, in regard to the absolute irreducibility \ testing discussed in the previous section, is to understand situations in \ which we might have an early termination during the quadratic lift process. \ This is under current investigation.\ \>", "Item1", CellChangeTimes->{{3.424647214545064*^9, 3.424647304226933*^9}, { 3.424694965714943*^9, 3.424694974402301*^9}, {3.424695114801455*^9, 3.42469511667925*^9}, {3.443359832037533*^9, 3.443359832784321*^9}, { 3.470071223608486*^9, 3.4700712324706993`*^9}, {3.492538663054255*^9, 3.492538731452286*^9}, {3.492538764412278*^9, 3.492538786043612*^9}, { 3.492538954532749*^9, 3.4925389745195093`*^9}, {3.492900353732088*^9, 3.4929003652359324`*^9}, 3.492902966934929*^9, 3.492903004504401*^9, 3.492905421941786*^9, {3.492906573592538*^9, 3.4929066282170467`*^9}, { 3.500235176518078*^9, 3.500235180703364*^9}}] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[TextData[{ Cell[TextData[{ StyleBox[ CounterBox["Section"], "SectionNumber"], StyleBox[". ", "SectionNumber"] }], "SectionDingbat"], "REFERENCES" }], "Section"], Cell[CellGroupData[{ Cell[TextData[{ "W. Adams and P. Loustaunau (1994). ", "An Introduction to Gr\[ODoubleDot]bner Bases", StyleBox[". ", FontSlant->"Italic"], "Graduate Studies in Mathematics Vol. 3. American Mathematical Society." }], "Reference", CellChangeTimes->{{3.410296837509955*^9, 3.410296863891146*^9}}, CellTags->"Adams Loustaunau"], Cell["\<\ T. Becker, W. Weispfenning, and H. Kredel (1993). Gr\[ODoubleDot]bner Bases: \ A Computational Approach to Computer Algebra. Graduate Texts in Mathematics \ 141. Springer\[Hyphen]Verlag.\ \>", "Reference", CellChangeTimes->{3.492975912962986*^9}, CellTags->"Becker Weispfenning Kredel"], Cell["\<\ B. Buchberger (1985). Gr\[ODoubleDot]bner bases: An algorithmic method in \ polynomial ideal theory. Multidimensional Systems Theory, chapter 6. N. K. \ Bose, ed. D. Reidel Publishing Company.\ \>", "Reference", CellChangeTimes->{{3.411745701260964*^9, 3.411745701746767*^9}, { 3.424786882168785*^9, 3.424786912302102*^9}, {3.424786964214607*^9, 3.424786968831112*^9}, 3.492899525639112*^9}, CellTags->"Buchberger"], Cell["\<\ G. Ch\[EGrave]ze (2004). Absolute polynomial factorization in two variables \ and the knapsack problem. Proceedings of the 2004 International Symposium on \ Symbolic and Algebraic Computation (ISSAC 2004), 87\[Hyphen]94. J. Gutierrez, \ editor. ACM Press.\ \>", "Reference", CellChangeTimes->{{3.411745701260964*^9, 3.411745701746767*^9}, { 3.424786758260487*^9, 3.42478677646048*^9}, {3.424786961880907*^9, 3.424787060311494*^9}, {3.424787107667513*^9, 3.424787111469686*^9}, { 3.492899913263082*^9, 3.492900029133794*^9}, {3.492900156888564*^9, 3.492900158314685*^9}, {3.492963580983614*^9, 3.492963582279298*^9}}, CellTags->"Cheze"], Cell["\<\ G. Ch\[EGrave]ze and A. Galligo (2005). Four lectures on polynomial absolute \ factorization. Solving Polynomial Equations, Volume 14 of Algorithms and \ Computation in Mathematics, pp. 339\[Hyphen]392. Springer Berlin Heidelberg.\ \>", "Reference", CellChangeTimes->{{3.411745701260964*^9, 3.411745701746767*^9}, { 3.424786758260487*^9, 3.42478677646048*^9}, {3.424786961880907*^9, 3.424787060311494*^9}, {3.424787107667513*^9, 3.424787111469686*^9}, { 3.492963286895946*^9, 3.492963332109178*^9}, {3.492963372427446*^9, 3.492963375744853*^9}, {3.4929634063625298`*^9, 3.492963429930251*^9}, { 3.49296349542334*^9, 3.492963519789454*^9}, {3.492963562808187*^9, 3.492963569095356*^9}, 3.492975847395206*^9}, CellTags->"Cheze Galligo 2005"], Cell["\<\ G. Ch\[EGrave]ze and A. Galligo (2006). From an approximate to an exact \ absolute polynomial factorization. Journal of Symbolic Computation 41:682\ \[Hyphen]696.\ \>", "Reference", CellChangeTimes->{{3.411745701260964*^9, 3.411745701746767*^9}, { 3.424786758260487*^9, 3.42478677646048*^9}, {3.424786961880907*^9, 3.424787060311494*^9}, {3.424787107667513*^9, 3.424787111469686*^9}}, CellTags->"Cheze Galligo"], Cell["\<\ R. Corless, A. Galligo, I. Kotsireas, and S. Watt (2002). A \ geometric\[Hyphen]numeric algorithm for absolute factorization of \ multivariate polynomials. Proceedings of the 2002 International Symposium on \ Symbolic and Algebraic Computation (ISSAC 2002), 37\[Hyphen]45. T. Mora, \ editor. ACM Press.\ \>", "Reference", CellChangeTimes->{{3.410280026295279*^9, 3.410280050568012*^9}, { 3.410280520865755*^9, 3.410280521807359*^9}, {3.411745778546031*^9, 3.411745781690407*^9}, {3.419961463474993*^9, 3.419961490718516*^9}, { 3.419961525313073*^9, 3.419961533251348*^9}, {3.419962019096603*^9, 3.419962078803739*^9}, 3.423943228385486*^9, {3.423943473793672*^9, 3.423943474816136*^9}, 3.424104977288517*^9, 3.492899537178529*^9}, CellTags->"Corless Galligo Kotsireas Watt"], Cell["\<\ R. Corless, A. Giesbrecht, M. van Hoeij, I. Kotsireas, and S. Watt (2001). \ Towards factoring bivariate approximate polynomials. Proceedings of the 2001 \ International Symposium on Symbolic and Algebraic Computation (ISSAC 2001), \ 85\[Hyphen]92. B. Mourrain, editor. ACM Press.\ \>", "Reference", CellChangeTimes->{{3.410280026295279*^9, 3.410280050568012*^9}, { 3.410280520865755*^9, 3.410280521807359*^9}, {3.411745778546031*^9, 3.411745781690407*^9}, {3.419961463474993*^9, 3.419961490718516*^9}, { 3.419961525313073*^9, 3.419961533251348*^9}, {3.419962019096603*^9, 3.419962078803739*^9}, 3.423943228385486*^9, {3.42394337293003*^9, 3.423943490752755*^9}, {3.423943547909527*^9, 3.423943555163205*^9}, { 3.424005086512848*^9, 3.424005090831079*^9}, {3.424012505253345*^9, 3.424012505792171*^9}, 3.424104968249555*^9, {3.49289953196032*^9, 3.492899532118553*^9}}, CellTags->"Corless Giesbrecht van Hoeij Kotsireas Watt"], Cell["\<\ D. Cox, J. Little, and D. O'Shea (1992). Ideals, Varieties, and Algorithms: \ An Introduction to Computational Algebraic Geometry and Computer Algebra. \ Undergraduate Texts in Mathematics. Springer\[Hyphen]Verlag.\ \>", "Reference", CellTags->"Cox Little OShea"], Cell[TextData[{ "H. Ferguson, D. Bailey, and S. Arno (1999). Analysis of PSLQ, an integer \ relation finding algorithm.", StyleBox[" ", FontSlant->"Italic"], "Mathematics of Computation", StyleBox[" ", FontSlant->"Italic"], "68(225):351\[Hyphen]369." }], "Reference", PageBreakAbove->Automatic, CellChangeTimes->{{3.423859530797029*^9, 3.423859547448133*^9}}, CellTags->"Ferguson Bailey Arno"], Cell["\<\ A. Galligo and S. Watt (1997). A numerical absolute primality test for \ bivariate polynomials. Proceedings of the 1997 International Symposium on \ Symbolic and Algebraic Computation (ISSAC 1997), 217\[Hyphen]224. W. K\ \[UDoubleDot]chlin, editor. ACM Press.\ \>", "Reference", CellChangeTimes->{{3.410280026295279*^9, 3.410280050568012*^9}, { 3.410280520865755*^9, 3.410280521807359*^9}, {3.411745778546031*^9, 3.411745781690407*^9}, {3.419961463474993*^9, 3.419961490718516*^9}, { 3.419961525313073*^9, 3.419961533251348*^9}, {3.419962019096603*^9, 3.419962078803739*^9}, 3.423943228385486*^9, {3.423943473793672*^9, 3.423943474816136*^9}, {3.424083907697776*^9, 3.424083923500045*^9}, { 3.424083954506739*^9, 3.424084028022032*^9}, {3.442338624154993*^9, 3.442338624439619*^9}, 3.4928995017371387`*^9}, CellTags->"Galligo Watt"], Cell["\<\ P. Gianni and B. Trager (1985). Gcd's and factoring multivariate polynomials \ using Gr\[ODoubleDot]bner bases. Proceedings of the 1985 European Conference \ on Computer Algebra (EUROCAL 1985), B. Caviness, editor. Lecture Notes in \ Computer Science 204, 409\[Hyphen]410. Springer\[Hyphen]Verlag.\ \>", "Reference", CellChangeTimes->{{3.411498574026191*^9, 3.411498574203623*^9}, { 3.424011948700364*^9, 3.424012007828006*^9}, {3.424012302881031*^9, 3.424012511413348*^9}, 3.424012749636833*^9, 3.492899497865727*^9}, CellTags->"Gianni Trager"], Cell["\<\ E. Kaltofen (1990). Computing the irreducible real factors and components of \ an algebraic curve. Applicable Algebra in Engineering, Communication and \ Computing 1:135\[Hyphen]148.\ \>", "Reference", CellChangeTimes->{{3.424012563024198*^9, 3.424012567663899*^9}, 3.4698084620924387`*^9, 3.469809260937213*^9, {3.49296108670654*^9, 3.4929611867036057`*^9}}, CellTags->"Kaltofen"], Cell[TextData[{ "J. Keiper (1992). Numerical computation with ", StyleBox["Mathematica", FontSlant->"Italic"], " (tutorial notes).\n\ http://library.wolfram.com/infocenter/Conferences/4687/" }], "Reference", CellChangeTimes->{{3.424012563024198*^9, 3.424012567663899*^9}, 3.4698084620924387`*^9, 3.469809260937213*^9}, CellTags->"Keiper"], Cell["\<\ A. Kondratyev, H. Stetter, and F. Winkler (2004). Numerical computation of Gr\ \[ODoubleDot]bner bases. Proceedings of the 7th Workshop on Computer Algebra \ in Scientific Computing (CASC 2004), St.Petersburg, 295\[Hyphen]306, V. G. \ Ghanza, E. W. Mayr, E. V. Vorozhtov (eds.), Technische Univ. \ M\[UDoubleDot]nchen.\ \>", "Reference", CellChangeTimes->{{3.41028213524393*^9, 3.410282205853657*^9}, { 3.410282242999431*^9, 3.410282288174188*^9}, {3.469970518015078*^9, 3.46997056353234*^9}, {3.4699706311819477`*^9, 3.469970703965412*^9}, 3.492899492809375*^9}, CellTags->"KondratyevStetterWinkler"], Cell[TextData[{ "A. K. Lenstra (1984). Polynomial factorization by root approximation. \ Proceedings of the International Symposium on Symbolic and Algebraic \ Computation", StyleBox[" ", FontSlant->"Italic"], "(EUROSAM 1984), J. Fitch, editor. Lecture Notes in Computer Science 174, \ 272\[Hyphen]276, Springer\[Hyphen]Verlag." }], "Reference", PageBreakAbove->Automatic, CellChangeTimes->{{3.423859648981507*^9, 3.423859674071924*^9}, { 3.424012521459718*^9, 3.42401253633951*^9}, {3.424012801547821*^9, 3.424012804443721*^9}, 3.492899488681587*^9}, CellTags->"Lenstra"], Cell[TextData[{ "D. Lichtblau (1996). ", StyleBox["Gr\[ODoubleDot]bner bases in Mathematica 3.0.", FontVariations->{"CompatibilityType"->0}], " ", "The Mathematica Journal", " ", StyleBox["6", FontWeight->"Bold"], "(4): 81\[Hyphen]88.\nhttp://library.wolfram.com/infocenter/Articles/2179/" }], "Reference", CellChangeTimes->{{3.469809245688706*^9, 3.469809255704648*^9}}, CellTags->"Lichtblau 1"], Cell["\<\ D. Lichtblau (2008). Approximate Gr\[ODoubleDot]bner bases and overdetermined \ algebraic systems. Manuscript. http://library.wolfram.com/infocenter/Conferences/7536/\ \>", "Reference", PageBreakAbove->Automatic, CellChangeTimes->{{3.36061960847548*^9, 3.36061962152984*^9}, 3.360619905143*^9, {3.410279813751004*^9, 3.410279817791669*^9}, 3.410280276795676*^9, {3.41987580649082*^9, 3.419875836044427*^9}, { 3.419966432693112*^9, 3.419966437897646*^9}, {3.442427246311117*^9, 3.442427247941475*^9}, {3.469809219004264*^9, 3.4698092428082333`*^9}}, CellTags->"Lichtblau 2"], Cell["\<\ D. Lichtblau (2010). Midpoint locus of a triangle in a corner. ADG 2010, \ Munich. http://lsiit.u-strasbg.fr/adg2010/upload/2/29/ADG2010_Daniel_TiC_talk.pdf\ \>", "Reference", PageBreakAbove->Automatic, CellChangeTimes->{{3.36061960847548*^9, 3.36061962152984*^9}, 3.360619905143*^9, {3.410279813751004*^9, 3.410279817791669*^9}, 3.410280276795676*^9, {3.41987580649082*^9, 3.419875836044427*^9}, { 3.419966432693112*^9, 3.419966437897646*^9}, {3.442427246311117*^9, 3.442427247941475*^9}, {3.469809219004264*^9, 3.4698092428082333`*^9}, { 3.4840549396183662`*^9, 3.484054940465785*^9}, {3.484055060388164*^9, 3.4840550915817337`*^9}, {3.492532297229751*^9, 3.4925322998219223`*^9}, { 3.492902835435236*^9, 3.492902877799808*^9}}, CellTags->"Lichtblau 3"], Cell["\<\ M. Noro and K. Yokoyama (2002). Yet another practical implementation of \ polynomial factorization over finite fields. Proceedings of the 2002 \ International Symposium on Symbolic and Algebraic Computation (ISSAC 2002), \ 200\[Hyphen]206. T. Mora, editor. ACM Press.\ \>", "Reference", CellChangeTimes->{{3.424012657112564*^9, 3.42401265758146*^9}, { 3.424104901505757*^9, 3.424104949345943*^9}, {3.424104986817781*^9, 3.424105006734696*^9}, 3.4928994860107*^9}, CellTags->"Noro Yokoyama"], Cell["\<\ T. Sasaki (2001). Approximate multivariate polynomial factorization based on \ zero\[Hyphen]sum relations. Proceedings of the 2001 International Symposium \ on Symbolic and Algebraic Computation (ISSAC 2001), 284\[Hyphen]291. B. \ Mourrain, editor. ACM Press.\ \>", "Reference", PageBreakAbove->Automatic, CellChangeTimes->{{3.410280354193676*^9, 3.410280389514519*^9}, { 3.410280452070131*^9, 3.410280470692164*^9}, {3.410280554325035*^9, 3.410280586358127*^9}, {3.492899287580037*^9, 3.49289932775632*^9}, { 3.492899455431396*^9, 3.492899465017797*^9}, {3.492899568871379*^9, 3.492899569013805*^9}, {3.492900065549243*^9, 3.49290007102234*^9}}, CellTags->"Sasaki"], Cell["\<\ T. Sasaki and F. Kako (2007). Computing floating\[Hyphen]point \ Gr\[ODoubleDot]bner bases stably. Proceedings of the 2007 International \ Workshop on Symbolic-numeric Computation (SNC 07), 180\[Hyphen]189. ACM Press.\ \>", "Reference", PageBreakAbove->Automatic, CellChangeTimes->{{3.410280354193676*^9, 3.410280389514519*^9}, { 3.410280452070131*^9, 3.410280470692164*^9}, {3.410280554325035*^9, 3.410280586358127*^9}}, CellTags->"Sasaki Kako"], Cell[TextData[{ "T. Sasaki, M. Suzuki, M. Kol\[AAcute]", Cell[BoxData[ FormBox[ OverscriptBox[ StyleBox["r", FontSlant->"Plain"], "\[Hacek]"], TraditionalForm]]], ", and M. Sasaki (1991). Approximate factorization of multivariate \ polynomials and absolute irreducibility testing. Japan Journal of Industrial \ and Applied Mathematics 8(3):357\[Hyphen]375." }], "Reference", PageBreakAbove->Automatic, CellChangeTimes->{{3.410280354193676*^9, 3.410280389514519*^9}, { 3.410280452070131*^9, 3.410280470692164*^9}, {3.410280554325035*^9, 3.410280586358127*^9}, {3.492899287580037*^9, 3.49289932775632*^9}, { 3.492899455431396*^9, 3.492899465017797*^9}, {3.492899568871379*^9, 3.492899569013805*^9}, {3.492900065549243*^9, 3.49290007102234*^9}, { 3.492958543168446*^9, 3.492958562815048*^9}, {3.4929586968775263`*^9, 3.49295877929077*^9}, 3.4929756765207863`*^9, {3.493139429711685*^9, 3.49313943018819*^9}, {3.4931398837871532`*^9, 3.4931398865467*^9}, 3.493139934647938*^9}, CellTags->"Sasaki Suzuki Kolar Sasaki"], Cell["\<\ K. Shirayanagi (1996). Floating point Gr\[ODoubleDot]bner bases. Mathematics \ and Computers in Simulation 42:509\[Hyphen]528. Elsevier Science Ltd.\ \>", "Reference", CellChangeTimes->{{3.424012657112564*^9, 3.42401265758146*^9}, { 3.4698097248152657`*^9, 3.46980972766378*^9}, 3.469810292149201*^9, 3.4929757001504107`*^9}, CellTags->"Shirayanagi"], Cell["\<\ M. Sofroniou and G. Spaletta (2005). Precise numerical computation. Journal \ of Logic and Algebraic Programming 64(1):113\[Hyphen]134.\ \>", "Reference", CellChangeTimes->{{3.410279878127811*^9, 3.410279927736319*^9}}, CellTags->"Sofroniou Spaletta"], Cell[TextData[{ "Q-N Tran (2007). A new class of term orders for elimination. ", "Journal of Symbolic Computation", " ", StyleBox["42", FontWeight->"Bold"], ":533\[Hyphen]548." }], "Reference", CellChangeTimes->{{3.410279878127811*^9, 3.410279927736319*^9}, { 3.420051165466143*^9, 3.420051179261096*^9}, {3.442427237655224*^9, 3.442427242278232*^9}}, CellTags->"Tran"], Cell["\<\ C. Traverso and A. Zanoni (2002). Numerical stability and stabilization of \ Groebner basis computation. Proceedings of the 2002 International Symposium \ on Symbolic and Algebraic Computation (ISSAC 02), 262\[Hyphen]269. T. Mora, \ editor. ACM Press.\ \>", "Reference", CellChangeTimes->{{3.410280694826224*^9, 3.410280761876285*^9}, { 3.411745352937758*^9, 3.411745357177305*^9}, {3.411745430983623*^9, 3.411745432221751*^9}}, CellTags->"Traverso Zanoni"], Cell[TextData[{ "Wolfram Research, Inc. (2008). Champaign, Illinois. ", StyleBox["Mathematica", FontSlant->"Italic"], " 7. http://www.wolfram.com" }], "Reference", CellChangeTimes->{{3.410279878127811*^9, 3.410279927736319*^9}, { 3.420051165466143*^9, 3.420051179261096*^9}, {3.442427237655224*^9, 3.442427242278232*^9}, {3.443459260374168*^9, 3.44345929345883*^9}, { 3.443869700518795*^9, 3.4438697441652527`*^9}}, CellTags->"Wolfram"], Cell["\<\ R. Zippel (1993). Effective Polynomial Computation. Kluwer Academic \ Publishers.\ \>", "Reference", CellChangeTimes->{{3.410279878127811*^9, 3.410279927736319*^9}, { 3.420051165466143*^9, 3.420051179261096*^9}, {3.4424271540094957`*^9, 3.442427227093532*^9}}, CellTags->"Zippel"] }, Open ]] }, Open ]] }, Open ]] }, AutoGeneratedPackage->None, WindowSize->{960, 681}, WindowMargins->{{151, Automatic}, {Automatic, 17}}, PrintingPageRange->{Automatic, Automatic}, PageHeaders->{{None, None, None}, {None, None, None}}, PageFooters->{{None, Cell[ TextData[ CounterBox["Page"]], "Footer"], None}, {None, Cell[ TextData[ CounterBox["Page"]], "Footer"], None}}, PageHeaderLines->{False, False}, PageFooterLines->{False, False}, PrintingOptions->{"CellBackgroundHalftoneAngle"->Automatic, "CellBackgroundHalftoneDensity"->Automatic, "FacingPages"->False, "FirstPageFace"->Right, "FirstPageFooter"->True, "FirstPageHeader"->False, "GraphicsPrintingFormat"->"Automatic", "IncludePostScriptResourceDirectives"->False, "IncludeSpecialFonts"->True, "Magnification"->1., "PageFooterMargins"->{Automatic, Automatic}, "PageHeaderMargins"->{Automatic, Automatic}, "PageSize"->{Automatic, Automatic}, "PaperOrientation"->"Portrait", "PaperSize"->{611.28, 789.57}, "PostScriptOutputFile"->"/home/usr2/danl/Notebooks/print.pdf", "PrintCellBrackets"->False, "PrintMultipleHorizontalPages"->False, "PrintRegistrationMarks"->False, "PrintSelectionHighlighting"->False, "PrintingMargins"->79.2, "RasterizationResolution"->"Automatic", "RestPagesFooter"->True, "RestPagesHeader"->True, "UnixShellPrintingCommand"->"lpr -Padmin", "UsePostScriptOutputFile"->False, "UseUnixShellPrintingCommand"->True}, GridBoxOptions->{GridBoxSpacings->{"Columns" -> { Offset[0.27999999999999997`], { Offset[0.5599999999999999]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> { Offset[0.2], { Offset[0.08]}, Offset[0.2]}, "RowsIndexed" -> {}}}, FrontEndVersion->"8.0 for Linux x86 (64-bit) (November 14, 2010)", StyleDefinitions->Notebook[{ Cell[ StyleData[ StyleDefinitions -> FrontEnd`FileName[{"Article"}, "Preprint.nb", CharacterEncoding -> "iso8859-1"]]], Cell[ CellGroupData[{ Cell["Unique Styles", "Section"], Cell[ CellGroupData[{ Cell[ StyleData["Author"], CellMargins -> {{-10, Inherited}, {2, 14}}, CellGroupingRules -> {"TitleGrouping", 20}, PageBreakBelow -> False, TextAlignment -> Center, CounterAssignments -> {{"Section", 0}, {"Equation", 0}, { "Figure", 0}}, FontSize -> 14, FontWeight -> "Bold"], Cell[ StyleData["Author", "Printout"], CellMargins -> {{-14, Inherited}, {2, 10}}, FontSize -> 12]}, Open]], Cell[ CellGroupData[{ Cell[ StyleData["Address"], CellMargins -> {{-10, Inherited}, {2, 18}}, CellGroupingRules -> {"TitleGrouping", 30}, PageBreakBelow -> False, TextAlignment -> Center, LineSpacing -> {1, 1}, CounterAssignments -> {{"Section", 0}, {"Equation", 0}, { "Figure", 0}}, FontSize -> 12], Cell[ StyleData["Address", "Printout"], CellMargins -> {{-14, Inherited}, {2, 4}}, FontSize -> 10]}, Open]], Cell[ CellGroupData[{ Cell["References", "Subsection"], Cell[ CellGroupData[{ Cell[ StyleData["ReferenceSection"], CellFrame -> {{0, 0}, {0.5, 0}}, CellMargins -> {{27, Inherited}, {8, 34}}, DefaultNewCellStyle -> "Reference", MenuSortingValue -> 2250, FontSize -> 20], Cell[ StyleData["ReferenceSection", "Printout"], CellMargins -> {{2, 0}, {7, 22}}, FontSize -> 14]}, Open]], Cell[ CellGroupData[{ Cell[ StyleData["Reference"], CellMargins -> {{60, 10}, {0, 4}}, CellFrameLabels -> {{ Cell[ TextData[{"[", CounterBox["Reference"], "] "}], "Reference", CellBaseline -> Baseline], None}, {None, None}}, ParagraphIndent -> -18, CounterIncrements -> "Reference", MenuSortingValue -> 2260, CounterStyleMenuListing -> Automatic], Cell[ StyleData["Reference", "Printout"], CellMargins -> {{16, Inherited}, {0, 2}}, ParagraphIndent -> -12]}, Open]]}, Open]]}, Open]], Cell[ CellGroupData[{ Cell["Styles for Input and Output Cells", "Section"], Cell[ "The cells in this section define styles used for input and output to \ the kernel. Be careful when modifying, renaming, or removing these styles, \ because the front end associates special meanings with these style names. \ Some attributes for these styles are actually set in FormatType Styles (in \ the last section of this stylesheet). ", "Text"], Cell[ CellGroupData[{ Cell[ StyleData["Input"], ReturnCreatesNewCell -> False, MenuSortingValue -> 1650, MenuCommandKey -> "9"], Cell[ StyleData["Input", "Printout"], CellMargins -> {{39, 0}, {1, 1}}, ShowCellLabel -> False]}, Open]], Cell[ StyleData["InputOnly"], ReturnCreatesNewCell -> False], Cell[ StyleData["Code"], ReturnCreatesNewCell -> False, MenuSortingValue -> 1600, MenuCommandKey -> "8"], Cell[ CellGroupData[{ Cell[ StyleData["Output"], ReturnCreatesNewCell -> False, MenuSortingValue -> 1700], Cell[ StyleData["Output", "Printout"], CellMargins -> {{39, 0}, {2, 0.5}}, ShowCellLabel -> False]}, Open]]}, Open]], Cell[ CellGroupData[{ Cell["Styles for Title and Section Cells", "Section"], Cell[ CellGroupData[{ Cell[ StyleData["Section"], CellFrame -> None, CellMargins -> {{27, Inherited}, {8, 34}}, MenuSortingValue -> 1200, MenuCommandKey -> "1", FontSize -> 20], Cell[ StyleData["Section", "Printout"], CellMargins -> {{2, 0}, {7, 14}}, FontSize -> 14]}, Open]], Cell[ CellGroupData[{ Cell[ StyleData["Subsection"], CellDingbat -> None, MenuSortingValue -> 1250, MenuCommandKey -> "2"], Cell[ StyleData["Subsection", "Printout"], CellMargins -> {{9, 0}, {4, 8}}, FontSize -> 12]}, Open]], Cell[ CellGroupData[{ Cell[ StyleData["Subsubsection"], CellDingbat -> None, CellChangeTimes -> {3.4433599668646603`*^9}], Cell[ StyleData["Subsubsection", "Printout"], CellMargins -> {{9, 0}, {2, 4}}, CellChangeTimes -> {3.4433599668653507`*^9}, FontSize -> 11]}, Open]]}, Open]], Cell[ CellGroupData[{ Cell["Styles for Body Text", "Section"], Cell[ CellGroupData[{ Cell[ StyleData["Text"], MenuSortingValue -> 1500, MenuCommandKey -> "7"], Cell[ StyleData["Text", "Printout"], CellMargins -> {{2, 2}, {5, 5}}, TextJustification -> 0.9, Hyphenation -> True]}, Open]], Cell[ CellGroupData[{ Cell["Display", "Subsubsection"], Cell[ CellGroupData[{ Cell["Lists", "Subsubsubsection"], Cell[ CellGroupData[{ Cell["Bulleted", "Subsubsubsubsection"], Cell[ CellGroupData[{ Cell[ StyleData["Item1"], CellMargins -> {{60, Inherited}, {Inherited, Inherited}}, CellGroupingRules -> { "GroupTogetherNestedGrouping", 15000}, MenuSortingValue -> 1710, FontSize -> 12], Cell[ StyleData["Item1", "Printout"], CellMargins -> {{16, Inherited}, {Inherited, Inherited}}]}, Open]], Cell[ CellGroupData[{ Cell[ StyleData["Item2"], CellMargins -> {{84, Inherited}, {Inherited, Inherited}}, CellGroupingRules -> { "GroupTogetherNestedGrouping", 15100}, MenuSortingValue -> 1720], Cell[ StyleData["Item2", "Printout"], CellMargins -> {{40, Inherited}, {Inherited, Inherited}}]}, Closed]], Cell[ CellGroupData[{ Cell[ StyleData["Item3"], CellMargins -> {{108, Inherited}, {Inherited, Inherited}}, CellGroupingRules -> { "GroupTogetherNestedGrouping", 15200}, MenuSortingValue -> 1730], Cell[ StyleData["Item3", "Printout"], CellMargins -> {{64, Inherited}, {Inherited, Inherited}}]}, Closed]]}, Open]], Cell[ CellGroupData[{ Cell[ "Numbered Lists", "Subsubsubsubsection", StyleMenuListing -> None], Cell[ CellGroupData[{ Cell[ StyleData["Item1Numbered"], CellMargins -> {{60, Inherited}, {Inherited, Inherited}}, CellGroupingRules -> { "GroupTogetherNestedGrouping", 15000}, CellFrameLabels -> {{ Cell[ TextData[{ CounterBox["Item1Numbered"], "."}], "Item1NumberedLabel", CellBaseline -> Baseline, TextAlignment -> Right], Inherited}, {Inherited, Inherited}}, CellFrameLabelMargins -> 4, MenuSortingValue -> 1740], Cell[ StyleData["Item1Numbered", "Printout"], CellMargins -> {{16, Inherited}, {Inherited, Inherited}}]}, Closed]], Cell[ CellGroupData[{ Cell[ StyleData["Item2Numbered"], CellMargins -> {{84, Inherited}, {Inherited, Inherited}}, CellGroupingRules -> { "GroupTogetherNestedGrouping", 15100}, CellFrameLabels -> {{ Cell[ TextData[{"(", CounterBox["Item2Numbered", CounterFunction :> (Part[ CharacterRange["a", "z"], #]& )], ")"}], "Item2NumberedLabel", CellBaseline -> Baseline, TextAlignment -> Right], Inherited}, { Inherited, Inherited}}, MenuSortingValue -> 1750, CounterBoxOptions -> {CounterFunction :> Identity}], Cell[ StyleData["Item2Numbered", "Printout"], CellMargins -> {{40, Inherited}, {Inherited, Inherited}}]}, Closed]], Cell[ CellGroupData[{ Cell[ StyleData["Item3Numbered"], CellMargins -> {{108, Inherited}, {Inherited, Inherited}}, CellGroupingRules -> { "GroupTogetherNestedGrouping", 15200}, CellFrameLabels -> {{ Cell[ TextData[{ CounterBox[ "Item3Numbered", CounterFunction :> RomanNumeral], "."}], "Item3NumberedLabel", CellBaseline -> Baseline, TextAlignment -> Right], Inherited}, { Inherited, Inherited}}, MenuSortingValue -> 1760, CounterBoxOptions -> {CounterFunction :> Identity}], Cell[ StyleData["Item3Numbered", "Printout"], CellMargins -> {{64, Inherited}, {Inherited, Inherited}}]}, Closed]]}, Closed]], Cell[ CellGroupData[{ Cell["Continuation Paragraphs", "Subsubsubsubsection"], Cell[ CellGroupData[{ Cell[ StyleData["Item1Paragraph"], CellMargins -> {{82, Inherited}, {Inherited, Inherited}}, CellGroupingRules -> { "GroupTogetherNestedGrouping", 15010}, MenuSortingValue -> 1770], Cell[ StyleData["Item1Paragraph", "Printout"], CellMargins -> {{38, Inherited}, {Inherited, Inherited}}]}, Closed]], Cell[ CellGroupData[{ Cell[ StyleData["Item2Paragraph"], CellMargins -> {{106, Inherited}, {Inherited, Inherited}}, CellGroupingRules -> { "GroupTogetherNestedGrouping", 15110}, MenuSortingValue -> 1780], Cell[ StyleData["Item2Paragraph", "Printout"], CellMargins -> {{62, Inherited}, {Inherited, Inherited}}]}, Closed]], Cell[ CellGroupData[{ Cell[ StyleData["Item3Paragraph"], CellMargins -> {{130, Inherited}, {Inherited, Inherited}}, CellGroupingRules -> { "GroupTogetherNestedGrouping", 15210}, MenuSortingValue -> 1790], Cell[ StyleData["Item3Paragraph", "Printout"], CellMargins -> {{86, Inherited}, {Inherited, Inherited}}]}, Closed]]}, Closed]]}, Open]]}, Open]]}, Open]]}, Visible -> False, FrontEndVersion -> "8.0 for Linux x86 (64-bit) (November 14, 2010)", StyleDefinitions -> "PrivateStylesheetFormatting.nb"] ] (* End of Notebook Content *) (* Internal cache information *) (*CellTagsOutline CellTagsIndex->{ "Adams Loustaunau"->{ Cell[199976, 5366, 332, 8, 22, "Reference", CellTags->"Adams Loustaunau"]}, "Becker Weispfenning Kredel"->{ Cell[200311, 5376, 298, 6, 42, "Reference", CellTags->"Becker Weispfenning Kredel"]}, "Buchberger"->{ Cell[200612, 5384, 434, 8, 42, "Reference", CellTags->"Buchberger"]}, "Cheze"->{ Cell[201049, 5394, 657, 11, 42, "Reference", CellTags->"Cheze"]}, "Cheze Galligo 2005"->{ Cell[201709, 5407, 772, 12, 42, "Reference", CellTags->"Cheze Galligo 2005"]}, "Cheze Galligo"->{ Cell[202484, 5421, 428, 8, 42, "Reference", CellTags->"Cheze Galligo"]}, "Corless Galligo Kotsireas Watt"->{ Cell[202915, 5431, 804, 13, 42, "Reference", CellTags->"Corless Galligo Kotsireas Watt"]}, "Corless Giesbrecht van Hoeij Kotsireas Watt"->{ Cell[203722, 5446, 967, 15, 42, "Reference", CellTags->"Corless Giesbrecht van Hoeij Kotsireas Watt"]}, "Cox Little OShea"->{ Cell[204692, 5463, 274, 5, 42, "Reference", CellTags->"Cox Little OShea"]}, "Ferguson Bailey Arno"->{ Cell[204969, 5470, 405, 12, 42, "Reference", PageBreakAbove->Automatic, CellTags->"Ferguson Bailey Arno"]}, "Galligo Watt"->{ Cell[205377, 5484, 869, 14, 42, "Reference", CellTags->"Galligo Watt"]}, "Gianni Trager"->{ Cell[206249, 5500, 564, 9, 42, "Reference", CellTags->"Gianni Trager"]}, "Kaltofen"->{ Cell[206816, 5511, 401, 8, 42, "Reference", CellTags->"Kaltofen"]}, "Keiper"->{ Cell[207220, 5521, 349, 9, 42, "Reference", CellTags->"Keiper"]}, "KondratyevStetterWinkler"->{ Cell[207572, 5532, 624, 11, 62, "Reference", CellTags->"KondratyevStetterWinkler"]}, "Lenstra"->{ Cell[208199, 5545, 587, 13, 42, "Reference", PageBreakAbove->Automatic, CellTags->"Lenstra"]}, "Lichtblau 1"->{ Cell[208789, 5560, 409, 12, 42, "Reference", CellTags->"Lichtblau 1"]}, "Lichtblau 2"->{ Cell[209201, 5574, 601, 11, 42, "Reference", PageBreakAbove->Automatic, CellTags->"Lichtblau 2"]}, "Lichtblau 3"->{ Cell[209805, 5587, 793, 14, 42, "Reference", PageBreakAbove->Automatic, CellTags->"Lichtblau 3"]}, "Noro Yokoyama"->{ Cell[210601, 5603, 509, 9, 42, "Reference", CellTags->"Noro Yokoyama"]}, "Sasaki"->{ Cell[211113, 5614, 689, 12, 42, "Reference", PageBreakAbove->Automatic, CellTags->"Sasaki"]}, "Sasaki Kako"->{ Cell[211805, 5628, 464, 9, 42, "Reference", PageBreakAbove->Automatic, CellTags->"Sasaki Kako"]}, "Sasaki Suzuki Kolar Sasaki"->{ Cell[212272, 5639, 1062, 21, 42, "Reference", PageBreakAbove->Automatic, CellTags->"Sasaki Suzuki Kolar Sasaki"]}, "Shirayanagi"->{ Cell[213337, 5662, 369, 7, 22, "Reference", CellTags->"Shirayanagi"]}, "Sofroniou Spaletta"->{ Cell[213709, 5671, 263, 5, 22, "Reference", CellTags->"Sofroniou Spaletta"]}, "Tran"->{ Cell[213975, 5678, 383, 11, 22, "Reference", CellTags->"Tran"]}, "Traverso Zanoni"->{ Cell[214361, 5691, 474, 9, 42, "Reference", CellTags->"Traverso Zanoni"]}, "Wolfram"->{ Cell[214838, 5702, 450, 10, 22, "Reference", CellTags->"Wolfram"]}, "Zippel"->{ Cell[215291, 5714, 297, 7, 22, "Reference", CellTags->"Zippel"]} } *) (*CellTagsIndex CellTagsIndex->{ {"Adams Loustaunau", 229623, 6059}, {"Becker Weispfenning Kredel", 229737, 6062}, {"Buchberger", 229845, 6065}, {"Cheze", 229932, 6068}, {"Cheze Galligo 2005", 230028, 6071}, {"Cheze Galligo", 230132, 6074}, {"Corless Galligo Kotsireas Watt", 230247, 6077}, {"Corless Giesbrecht van Hoeij Kotsireas Watt", 230393, 6080}, {"Cox Little OShea", 230525, 6083}, {"Ferguson Bailey Arno", 230633, 6086}, {"Galligo Watt", 230768, 6090}, {"Gianni Trager", 230866, 6093}, {"Kaltofen", 230959, 6096}, {"Keiper", 231045, 6099}, {"KondratyevStetterWinkler", 231147, 6102}, {"Lenstra", 231251, 6105}, {"Lichtblau 1", 231372, 6109}, {"Lichtblau 2", 231467, 6112}, {"Lichtblau 3", 231592, 6116}, {"Noro Yokoyama", 231719, 6120}, {"Sasaki", 231810, 6123}, {"Sasaki Kako", 231930, 6127}, {"Sasaki Suzuki Kolar Sasaki", 232069, 6131}, {"Shirayanagi", 232210, 6135}, {"Sofroniou Spaletta", 232311, 6138}, {"Tran", 232405, 6141}, {"Traverso Zanoni", 232497, 6144}, {"Wolfram", 232591, 6147}, {"Zippel", 232677, 6150} } *) (*NotebookFileOutline Notebook[{ Cell[545, 20, 61, 1, 32, "Text"], Cell[CellGroupData[{ Cell[631, 25, 250, 5, 137, "Title"], Cell[884, 32, 46, 0, 33, "Author"], Cell[933, 34, 210, 6, 76, "Address"], Cell[1146, 42, 35, 0, 38, "Address"], Cell[CellGroupData[{ Cell[1206, 46, 856, 15, 66, "Abstract"], Cell[2065, 63, 377, 7, 46, "Abstract"] }, Open ]], Cell[CellGroupData[{ Cell[2479, 75, 59, 0, 28, "Subsubsection"], Cell[2541, 77, 642, 17, 53, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[3220, 99, 151, 2, 28, "Subsubsection"], Cell[3374, 103, 93, 1, 32, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[3504, 109, 33, 0, 28, "Subsubsection"], Cell[3540, 111, 227, 5, 32, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[3804, 121, 218, 8, 67, "Section"], Cell[4025, 131, 2686, 47, 137, "Text"], Cell[6714, 180, 2641, 55, 116, "Text"], Cell[9358, 237, 1254, 18, 116, "Text"], Cell[10615, 257, 2111, 31, 116, "Text"], Cell[CellGroupData[{ Cell[12751, 292, 105, 1, 37, "Subsection"], Cell[12859, 295, 827, 12, 95, "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[13735, 313, 364, 10, 67, "Section"], Cell[14102, 325, 1199, 21, 74, "Text"], Cell[15304, 348, 2058, 36, 137, "Text"], Cell[17365, 386, 807, 15, 74, "Text"], Cell[18175, 403, 1016, 15, 95, "Text"], Cell[19194, 420, 671, 11, 105, "Text"], Cell[19868, 433, 1631, 35, 98, "Text"], Cell[21502, 470, 311, 8, 25, "Text"], Cell[21816, 480, 503, 11, 40, "Text"], Cell[22322, 493, 2614, 50, 138, "Text"], Cell[24939, 545, 781, 12, 74, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[25757, 562, 463, 11, 67, "Section"], Cell[26223, 575, 532, 9, 74, "Text"], Cell[26758, 586, 1129, 21, 95, "Text"], Cell[CellGroupData[{ Cell[27912, 611, 140, 2, 28, "Subsubsection"], Cell[CellGroupData[{ Cell[28077, 617, 3464, 95, 168, "Input"], Cell[31544, 714, 207, 4, 30, "Output"] }, Open ]], Cell[31766, 721, 579, 9, 53, "Text"], Cell[32348, 732, 551, 12, 30, "Input", CellGroupingRules->{GroupTogetherGrouping, 10001.}], Cell[32902, 746, 143, 3, 30, "Output"], Cell[33048, 751, 468, 8, 53, "Text"], Cell[33519, 761, 718, 11, 74, "Text"], Cell[34240, 774, 1235, 22, 174, "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[35524, 802, 482, 11, 38, "Section"], Cell[36009, 815, 559, 11, 57, "Text"], Cell[36571, 828, 2055, 59, 57, "Text"], Cell[38629, 889, 1377, 32, 25, "Text"], Cell[40009, 923, 1264, 40, 26, "Text"], Cell[41276, 965, 1260, 31, 26, "Text"], Cell[42539, 998, 931, 31, 26, "Text"], Cell[43473, 1031, 4339, 138, 97, "Text"], Cell[47815, 1171, 4677, 143, 98, "Text"], Cell[52495, 1316, 4162, 141, 103, "Text"], Cell[56660, 1459, 594, 15, 54, "Text"], Cell[57257, 1476, 2277, 54, 82, "Text"], Cell[59537, 1532, 4043, 113, 80, "Text"], Cell[63583, 1647, 1718, 57, 56, "Text"], Cell[65304, 1706, 3380, 97, 149, "Text"], Cell[68687, 1805, 418, 7, 32, "Text"], Cell[69108, 1814, 4299, 147, 130, "Text"], Cell[73410, 1963, 844, 19, 74, "Text"], Cell[74257, 1984, 2014, 58, 77, "Text"], Cell[76274, 2044, 1054, 15, 137, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[77365, 2064, 519, 12, 67, "Section"], Cell[77887, 2078, 4661, 157, 141, "Text"], Cell[82551, 2237, 984, 25, 33, "Text"], Cell[83538, 2264, 2230, 64, 75, "Text"], Cell[85771, 2330, 3593, 111, 101, "Text"], Cell[89367, 2443, 2847, 92, 81, "Text"], Cell[92217, 2537, 5420, 169, 165, "Text"], Cell[97640, 2708, 1788, 53, 34, "Text"], Cell[99431, 2763, 747, 15, 53, "Text"], Cell[100181, 2780, 528, 10, 54, "Text"], Cell[100712, 2792, 1166, 36, 50, "Text"], Cell[101881, 2830, 1184, 36, 53, "Text"], Cell[103068, 2868, 2913, 74, 117, "Text"], Cell[105984, 2944, 1393, 30, 53, "Text"], Cell[107380, 2976, 2359, 70, 77, "Text"], Cell[109742, 3048, 306, 6, 32, "Text"], Cell[110051, 3056, 1592, 43, 95, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[111680, 3104, 441, 11, 67, "Section"], Cell[112124, 3117, 891, 14, 116, "Text"], Cell[113018, 3133, 432, 12, 32, "Text"], Cell[CellGroupData[{ Cell[113475, 3149, 359, 5, 37, "Subsection"], Cell[113837, 3156, 639, 12, 53, "Text"], Cell[CellGroupData[{ Cell[114501, 3172, 189, 3, 28, "Subsubsection"], Cell[114693, 3177, 6711, 196, 164, "Input", CellID->921679567], Cell[121407, 3375, 509, 14, 33, "Text"], Cell[121919, 3391, 1427, 41, 69, "Input"], Cell[123349, 3434, 718, 17, 69, "Input"], Cell[124070, 3453, 1496, 48, 56, "Text"], Cell[CellGroupData[{ Cell[125591, 3505, 1666, 35, 88, "Input"], Cell[127260, 3542, 88, 1, 30, "Output"] }, Open ]], Cell[127363, 3546, 430, 9, 33, "Text"], Cell[CellGroupData[{ Cell[127818, 3559, 861, 16, 30, "Input"], Cell[128682, 3577, 205, 4, 30, "Output"] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[128948, 3588, 101, 1, 37, "Subsection"], Cell[129052, 3591, 1601, 23, 95, "Text"], Cell[130656, 3616, 1392, 21, 95, "Text"], Cell[132051, 3639, 4495, 111, 297, "Input"], Cell[CellGroupData[{ Cell[136571, 3754, 190, 3, 28, "Subsubsection"], Cell[136764, 3759, 616, 18, 54, "Text"], Cell[CellGroupData[{ Cell[137405, 3781, 403, 9, 30, "Input"], Cell[137811, 3792, 651, 17, 88, "Output"], Cell[138465, 3811, 2821, 83, 73, "Output"] }, Open ]], Cell[141301, 3897, 271, 8, 32, "Text"], Cell[CellGroupData[{ Cell[141597, 3909, 155, 3, 30, "Input"], Cell[141755, 3914, 211, 3, 30, "Output"] }, Open ]], Cell[141981, 3920, 1303, 21, 158, "Text"], Cell[143287, 3943, 245, 7, 32, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[143569, 3955, 212, 3, 28, "Subsubsection"], Cell[143784, 3960, 5914, 176, 145, "Input"], Cell[CellGroupData[{ Cell[149723, 4140, 507, 10, 30, "Input"], Cell[150233, 4152, 798, 19, 100, "Print"], Cell[151034, 4173, 2539, 76, 73, "Output"] }, Open ]], Cell[153588, 4252, 290, 9, 34, "Text"], Cell[CellGroupData[{ Cell[153903, 4265, 182, 4, 30, "Input"], Cell[154088, 4271, 109, 2, 30, "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[154246, 4279, 124, 2, 28, "Subsubsection"], Cell[154373, 4283, 1255, 26, 74, "Text"], Cell[155631, 4311, 2979, 90, 69, "Input"], Cell[158613, 4403, 652, 13, 75, "Text"], Cell[CellGroupData[{ Cell[159290, 4420, 1089, 24, 88, "Input"], Cell[160382, 4446, 322, 6, 30, "Output"] }, Open ]], Cell[160719, 4455, 1297, 32, 77, "Text"], Cell[CellGroupData[{ Cell[162041, 4491, 1542, 32, 69, "Input"], Cell[163586, 4525, 136, 3, 30, "Output"] }, Open ]], Cell[163737, 4531, 193, 4, 32, "Text"], Cell[CellGroupData[{ Cell[163955, 4539, 251, 5, 30, "Input"], Cell[164209, 4546, 1104, 27, 30, "Output"] }, Open ]], Cell[165328, 4576, 416, 10, 53, "Text"], Cell[CellGroupData[{ Cell[165769, 4590, 501, 12, 69, "Input"], Cell[166273, 4604, 161, 2, 30, "Output"] }, Open ]], Cell[166449, 4609, 834, 19, 74, "Text"], Cell[CellGroupData[{ Cell[167308, 4632, 2753, 65, 202, "Input"], Cell[170064, 4699, 1132, 35, 56, "Output"] }, Open ]], Cell[171211, 4737, 640, 14, 76, "Text", CellID->466588476], Cell[CellGroupData[{ Cell[171876, 4755, 646, 15, 30, "Input"], Cell[172525, 4772, 3165, 101, 124, "Output"] }, Open ]], Cell[175705, 4876, 499, 12, 55, "Text"], Cell[CellGroupData[{ Cell[176229, 4892, 587, 14, 30, "Input"], Cell[176819, 4908, 335, 5, 30, "Output"] }, Open ]], Cell[177169, 4916, 614, 12, 53, "Text"], Cell[177786, 4930, 795, 19, 74, "Text"], Cell[CellGroupData[{ Cell[178606, 4953, 501, 14, 33, "Input"], Cell[179110, 4969, 136, 3, 30, "Output"] }, Open ]], Cell[179261, 4975, 1707, 26, 137, "Text"] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[181029, 5008, 517, 12, 67, "Section"], Cell[181549, 5022, 805, 12, 95, "Text"], Cell[182357, 5036, 369, 6, 53, "Text"], Cell[182729, 5044, 811, 13, 116, "Text"], Cell[183543, 5059, 1352, 22, 137, "Text"], Cell[184898, 5083, 2210, 30, 242, "Text"], Cell[187111, 5115, 614, 10, 74, "Text"], Cell[187728, 5127, 287, 5, 53, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[188052, 5137, 309, 9, 67, "Section"], Cell[188364, 5148, 1041, 15, 74, "Text"], Cell[189408, 5165, 1574, 28, 116, "Text"], Cell[190985, 5195, 396, 7, 32, "Text"], Cell[CellGroupData[{ Cell[191406, 5206, 463, 8, 45, "Item1"], Cell[191872, 5216, 1252, 22, 102, "Item1"], Cell[193127, 5240, 1411, 20, 121, "Item1"], Cell[194541, 5262, 419, 7, 45, "Item1"], Cell[194963, 5271, 1088, 16, 102, "Item1"], Cell[196054, 5289, 1572, 22, 140, "Item1"], Cell[197629, 5313, 595, 9, 83, "Item1"], Cell[198227, 5324, 344, 6, 45, "Item1"], Cell[198574, 5332, 1154, 17, 83, "Item1"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[199777, 5355, 174, 7, 67, "Section"], Cell[CellGroupData[{ Cell[199976, 5366, 332, 8, 22, "Reference", CellTags->"Adams Loustaunau"], Cell[200311, 5376, 298, 6, 42, "Reference", CellTags->"Becker Weispfenning Kredel"], Cell[200612, 5384, 434, 8, 42, "Reference", CellTags->"Buchberger"], Cell[201049, 5394, 657, 11, 42, "Reference", CellTags->"Cheze"], Cell[201709, 5407, 772, 12, 42, "Reference", CellTags->"Cheze Galligo 2005"], Cell[202484, 5421, 428, 8, 42, "Reference", CellTags->"Cheze Galligo"], Cell[202915, 5431, 804, 13, 42, "Reference", CellTags->"Corless Galligo Kotsireas Watt"], Cell[203722, 5446, 967, 15, 42, "Reference", CellTags->"Corless Giesbrecht van Hoeij Kotsireas Watt"], Cell[204692, 5463, 274, 5, 42, "Reference", CellTags->"Cox Little OShea"], Cell[204969, 5470, 405, 12, 42, "Reference", PageBreakAbove->Automatic, CellTags->"Ferguson Bailey Arno"], Cell[205377, 5484, 869, 14, 42, "Reference", CellTags->"Galligo Watt"], Cell[206249, 5500, 564, 9, 42, "Reference", CellTags->"Gianni Trager"], Cell[206816, 5511, 401, 8, 42, "Reference", CellTags->"Kaltofen"], Cell[207220, 5521, 349, 9, 42, "Reference", CellTags->"Keiper"], Cell[207572, 5532, 624, 11, 62, "Reference", CellTags->"KondratyevStetterWinkler"], Cell[208199, 5545, 587, 13, 42, "Reference", PageBreakAbove->Automatic, CellTags->"Lenstra"], Cell[208789, 5560, 409, 12, 42, "Reference", CellTags->"Lichtblau 1"], Cell[209201, 5574, 601, 11, 42, "Reference", PageBreakAbove->Automatic, CellTags->"Lichtblau 2"], Cell[209805, 5587, 793, 14, 42, "Reference", PageBreakAbove->Automatic, CellTags->"Lichtblau 3"], Cell[210601, 5603, 509, 9, 42, "Reference", CellTags->"Noro Yokoyama"], Cell[211113, 5614, 689, 12, 42, "Reference", PageBreakAbove->Automatic, CellTags->"Sasaki"], Cell[211805, 5628, 464, 9, 42, "Reference", PageBreakAbove->Automatic, CellTags->"Sasaki Kako"], Cell[212272, 5639, 1062, 21, 42, "Reference", PageBreakAbove->Automatic, CellTags->"Sasaki Suzuki Kolar Sasaki"], Cell[213337, 5662, 369, 7, 22, "Reference", CellTags->"Shirayanagi"], Cell[213709, 5671, 263, 5, 22, "Reference", CellTags->"Sofroniou Spaletta"], Cell[213975, 5678, 383, 11, 22, "Reference", CellTags->"Tran"], Cell[214361, 5691, 474, 9, 42, "Reference", CellTags->"Traverso Zanoni"], Cell[214838, 5702, 450, 10, 22, "Reference", CellTags->"Wolfram"], Cell[215291, 5714, 297, 7, 22, "Reference", CellTags->"Zippel"] }, Open ]] }, Open ]] }, Open ]] } ] *) (* End of internal cache information *)