WARNING: Summaries are generated by a large language model and may be inaccurate. We suggest that you use the synopsis, short and long summaries only as a loose guide to the topics discussed. The model may attribute to the speaker or other participants views that they do not in fact hold. It may also attribute to the speaker views expressed by other participants, or vice versa. The raw transcript (see the bottom of the page) is likely to be a more accurate representation of the seminar content, except for errors at the level of individual words during transcription.

Polynomial division is a method used to calculate quotients and bound functions. It involves dividing a polynomial by two divisors and using the division algorithm to find q1 to qs and a remainder, r. The leading terms of the divisor and polynomial are checked and if they divide, the coefficient is added to the quotient. Monomial orders, Hilbert basis theorem and Grabner bases are used to guarantee the inequality and ensure a bounded function. This video explains the process and provides examples of polynomial division.

Polynomial division is a technique used to calculate quotients and bound functions. Monomial orders are total orders on sets of indices, which are n-tuples of non-negative integers. These orders satisfy two properties, and common examples include lexicographic order, where an index is greater if the first non-zero component of alpha minus theta is positive, and degree-lexicographic order, where an index is greater if the sum of the components of alpha is greater than theta. Hilbert basis theorem and Grabner bases are used to guarantee the inequality and ensure a bounded function.

Polynomial division is a method of breaking down a polynomial into a linear combination of other polynomials. It is similar to the division algorithm for integers, where a polynomial, p, is divided by a set of divisors, f1 to fs, to find q1 to qs and a remainder, r, such that q1f1 + q2f2 + ... + qsfs + r = p. The division algorithm is used to divide a polynomial by two divisors, and the polynomials must be written in descending order with the leading terms first. The leading term of the divisor is checked against the leading term of the polynomial, and if it divides, the coefficient is added to the quotient and multiplied out. The process is repeated until the leading terms no longer divide, and the remainder is the result of the division. The polynomial can then be written as the first quotient times the first divisor plus the second quotient times the second divisor plus the remainder.

Polynomial division is a technique used to calculate quotients which can be used to bound a function. This is done by using a monomial order to determine which monomials are bigger or smaller than others. A monomial is a product of variables taken to different powers, such as x1 to the alpha 1 times x2 to the alpha 2. Hilbert basis theorem and Grabner bases are used to guarantee the inequality and ensure a bounded function.

A monomial order is a total order on the set of indices, which are n-tuples of non-negative integers. This ordering satisfies two properties: if alpha is less than theta, then adding any other index to this tuple preserves the inequality; and zero is less than or equal to all other indices. Common examples of monomial orders are lexicographic order, where an index alpha is greater than theta if the first non-zero component of alpha minus theta is positive, and degree-lexicographic order, where an index alpha is greater than theta if the sum of the components of alpha is greater than the sum of the components of theta.

Polynomial division is a method of breaking down a polynomial into a linear combination of other polynomials. It is similar to the division algorithm for integers. Given a polynomial, p, and a set of divisors, f1 to fs, the algorithm finds q1 to qs and a remainder, r, such that q1f1 + q2f2 + ... + qsfs + r = p. The leading term of p is the largest monomial according to the chosen monomial order. Graded lexicographical order takes into account the total degree of a monomial.

Division algorithm is used to divide a polynomial by two divisors. The remainder should not contain any monomials that are divisible by the leading terms of the divisors, and the leading term of the polynomial being divided should be greater than or equal to the leading term of the quotient times divisor. An example is given of a polynomial, p, being divided by two divisors, f1 and f2, using graded lexicographic order. The polynomials must be written out in descending order, with the leading terms first.

Polynomial division is a process similar to long division for integers. The two divisors are written out and the thing being divided is written underneath. The leading term of the divisor is checked against the leading term of the polynomial, and if it divides, the coefficient is added to the quotient and multiplied out. This process is repeated until the leading terms no longer divide, and the remainder is the result of the division. The polynomial can then be written as the first quotient times the first divisor plus the second quotient times the second divisor plus the remainder.

Division algorithm might not output an expression of the form p = q1f1 + q2f2 + ... + r, where r is the remainder and q1, q2, ... are the quotients, even though such an expression might exist. This poses a problem for calculations that require specific values of the quotients. An example of this is given, where none of the leading terms of the divisors divide the polynomial, so the whole thing goes into the remainder. To fix this issue, Grover bases are introduced in the next talk.

all right so today i'm gonna be talking about uh a bit of background for next week's talk um and but everything's not continuing um from where i got to last week so the topic of the talk is polynomial division and um and grabner bases so again uh just by reminding everyone where we uh got to at the end of the last talk so we were we had the um callback libra divergence for some models kfw and we were trying to down that by a polynomial um so we first found conditions that let us found that by a infinite series of polynomials and those polynomials came from some sort of series um and then so the next step was to try and find uh a finite uh sum of those polynomials which also worked as an upper bound um and the we found some conditions which guaranteed this inequality here um and the argument uh boiled down to using the hilbert basis theorem and writing each of those infinitely many polynomials in terms of the first um say capital j generators which come from the albert basis theorem so we found that there exists these polynomials called the quotients which are written as these a's with the subscripts and superscripts zero and they let us write each of the infinitely many polynomials uh in terms of just the first capital j of them and then the argument we had for um guaranteeing and this upper bound was if um you could take all these quotients and uh square them and sum up their squares and get a bounded function and so to actually check that for any examples you need to really have specific values of what these quotients are and so to calculate these questions uh that's where we use polynomial division and also growth bases will come up [Laughter] so in this talk i'll introduce the polynomial division algorithm and also correlate bases um but before i do that there's a few uh definitions which i need to introduce first um and so the first definition is monomial orders and so a monomial order is basically a choice of how you determine which monomials are bigger or smaller than other ones and then once you've made this choice the division algorithm runs using that so i'll just write some notation so we'll write for the variables which will be used in all the polynomials as x which will be a we'll just write all the components in one thing as x with an underline and so a monomial will be a product of those variables taken to different powers so x1 to the alpha 1 times x2 to the alpha 2. uh and so on until you get to the last variable where each alpha i is a non-negative integer so you could we the

notation we use to simplify that is x to the alpha where alpha is a n-tuple of um non-negative integers so you write that as being an element of this sets those are non-negative integers uh and and with n components um okay uh i'm gonna move over to the next board to introduce the actual definition of monomial orders so a monomial order which we indicate using the just the greater the or western symbol is a total order uh which i'll explain what that means on the set of on the set of indices which was that set of n tables of non-negative integers uh so it's an ordering on that set satisfying two properties so the first is that if alpha is less than theta see if you have two indices and according to this order one smaller than the other then if you add any other index to this runway if you add any other index that preserves the inequality and the other property is that zero so just the index with zeros in all the components is less than or equal to all other indices um so what a total ordering means is just that you can compare any two indices so if you just take any index alpha and any other index theta either alpha is less than or equal to beta or um beta is less than alpha ah so that's uh i guess yeah different to a partial order where you might not be able to compare any two given elements of the set um and so having this ordering on all the indices gives an ordering on the monomials and that's just by associating the index alpha with the monomial x to the alpha so i'll talk about a couple examples um so there's lots of different examples of monomial orders which satisfy those conditions and there's ways of constructing new ones um but the two of the most common ones are so the first one is lexicographic order which is basically always the name suggests um like alphabetical order so in lexicographic order we say that um an index alpha one up to alpha n uh which we write as alpha is greater than theta uh if the first component sorry the first um if the uh let's see like that click the eraser okay i'll just write down that if we first non-negative non zero sorry if the first non-zero component of alpha minus theta is positive so another way of looking at it is you look at the first component of alpha and the first component of beta and if the component of alpha is larger than that of beta you say alpha's greater than beta if they're equal you then move going along each of the components until you find a difference um so move over to the next board to introduce the third

sorry the second example of the monomial order um and this is the one that will this is the one that we'll be using um in the top next week and so that's graded lexicographical order which is essentially the same as lexicographic order but it also takes into account the total degree of a monomial so we write the magnitude of alpha as just the sum of all its components and so in greater lexicographic order we say that alpha is greater than theta uh if i if either the magnitude of alpha so the sum of all its components is greater than the one for beta or if those two magnitudes are equal so the monomials have the same total degree uh then we compare them using the [Music] lexicographic conditions so we then just look at the first component and see which one's bigger and if they're the same we move on to the second component and so on um so then using the uh one so from now i'm gonna assume that we've just chosen a monomial order and we're just going to use that monomial water for everything that follows so i guess yeah for this example calculations i do i'll just be using this creative mexico graphic holder so um given a polynomial p um the leading term the reading term sorry my drawing table has gone a bit weird uh okay the leading term of p which we write as lt with p uh so p is a polynomial so it's the sum of also linear combination of several monomials so the leading term is the term which has is largest according to the chosen monomial order um so for example uh for example if p is three x squared y plus x y squared if we're using uh lexicographic order we can see that uh since this um x squared y monomial uh the power of x is larger and in the second term we have that the leading term of p is three x squared y and that's the same also in graded lexicographic order because both terms have the same degree okay so now i'm able to introduce the polynomial division algorithm so the point of the polynomial division algorithm is i guess somewhat similar fairly similar to the uh division algorithm for integers um so you take a polynomial and a divisor or set of divisors and try and write the your chosen polynomial in terms of those divisors so given a polynomial p and a collection of divisors uh which we'll write as f1 to fs so these are also all polynomials uh we want to we want to find questions uh q1 up to qs and remainder r which is another polynomial so that um q1 f1 plus q2 f2 adding up to qs times the final divisor plus the remainder equals p um and there's so

there'll also be some technical restrictions on what the remainder should be because and the obvious way to write an expression of this form is just to set all the quotients to zero and the remainder to equal p but that doesn't tell us very much um unfortunately i won't be able to go into too much details about those restrictions but it's to do with the i guess yeah so all the terms in the remainder shouldn't be divisible by the reading terms of uh the divisors i guess that's it's vaguely similar to in the division algorithm for integers the remainder should be [Music] smaller than the size of the divisor i think it's probably pretty important to write down those conditions otherwise it's not clear yeah actually it means sure i'll put that on the next part okay so uh yeah the conditions should be that uh is a sum or winning a combination of monomials uh none of which are divisible by the leading terms of any of the devices so in the case in the single variable case the leading term is the largest power of x so that says exactly that r has degree strictly less than those of the thing you're dividing into it which in that case would be just f right that's right uh yep and there's one other condition i think which is that the uh if one of the quotients times the divisor isn't zero then the leading term of the polynomial you're dividing should be greater than or equal to the leading term of that quotient times divisor um i'm not too sure of the reason for that condition but i think it's something to do with at least the division algorithm shouldn't inadvertently make almost bigger things that then have to be canceled i think something maybe like that um so then yeah so to actually explain how the division algorithm runs uh i think it's easier to just uh explain it through an example rather than um writing it as a sort of abstract algorithm um and so hopefully the example show sort of all the different steps involved so um so in this example we're going to take the polynomial p equals 5 x cubed y minus x x squared y plus x y and we're going to try and divide it by two divisors which are f one equals x squared y plus x y and the second is f two which is x plus y and we're going to use graded lexicographic order uh so the important thing is to have all each of these polynomials written out um with their leading term first and then all the other terms in descending order so for example with p the first term has total degree four and the second has degrees three and that is degree two so

that's already in the sending order um and so the way the algorithm runs is very similar to i guess pretty similar to um just doing long division or integers uh i might just go over to the next floor just to make sure i have space to fit it on one cloth okay um so the way we set it up is again yeah similar to long division so you write the two quotient the two divisors out the front let's give myself a bit more space so that was x squared y plus x y and the second was just x plus y and we use this symbol and write the thing we're dividing underneath let's find x cubed y minus x squared y plus x y and then because we're dividing by two divisors we need space for two equations so what you do is you just look at the leading term of p and go look first at the leading term of f1 and check ask whether the leading term of f1 divides that leading time of p ah in this case it does so 5x cubed y is equal to x times x squared y so then you just put um that five x in the space of the first quotient and then like you do for long division you multiply out that 5x by all of f1 and write the result underneath so that gives us 5 x cubed y plus 5 x squared y and again with like in just integer long division you subtract those two lines to get um minus 6 x squared y plus xy and then you repeat the same process looking at the leading term of what's left which is minus 6x squared y you go first to f1 and again in this case the leading term x squared y divides minus 6 x squared y and so we we just add minus 6 to the quotient and multiply it out again and six x y and so that gives us when we subtract minus seven sorry n minus seven uh positive seven x y um then in this case the leading term of f1 uh x squared y doesn't divide 7xy so then uh when that fails you go and look at the leading term of the second divisor in this case is which is x and does divide 7xy so we just add 7y to the second quotient which gives 7xy um plus seven y squared um we subtract again to get minus seven y squared now at this stage uh what's left isn't divisible by either of the waiting terms of um the divisors uh and so what's left just goes into the remainder so what this process has resulted in is that we can write a polynomial p five x cubed y minus x squared y plus x y as uh the first quotient times the first divisor plus the second quotient which is 7y times the second divisor plus the remainder which is minus seven y squared um and so that's the polynomial division algorithm um and so it turns out if it's guaranteed

like the result by those comments before i think that's requirement about um they're being made up of monomials none of which are divisible by the leading terms of the devices is just guaranteed by uh well everything that's that is divisible by the leading terms of the devices gets cancelled out during the algorithm um but there are a there is one big problem with the division algorithm or a couple problems with the division algorithm as it stands uh the first i'll go to the next board to talk about the first problem um which makes it at least as it is it makes it not that useful for the the uh the purpose that we're using it for um and with the singular learning theory problem so the issue with the division algorithm is that it might be true that you can write your the polynomial that you're devising as a combination of the divisors with no remainder but the algorithm might not output an expression of that form the algorithm a output um instead an expression like p equals q one f one and so on q s f s plus a non-zero remainder uh and so that's uh that's a bit of an issue oh especially for us because we for the calculations are doing we need specific values of these quotients that and we already know that the expressions of this form exist um just by the hilbert basis theorem and so if we were to just straightaway use the division algorithm as uh described it might not actually give us anything we can work with um so just as an example of how this could happen is if we take f1 equals xy plus z so we have three variables now and f2 equals x plus y and then the polynomial we're dividing as minus y z plus z um no way i've written that sorry not mine i've written that wrong um uh it's meant to be minus what um y squared plus that's risk spencer we're gonna have to wrap up a minute or so because the code session starts oh finish whatever comment you were making okay yeah sure uh yeah so i just finished this example um [Music] so it's true that p equals f 1 minus y f 2 but if we do the division algorithm with these divisors and that polynomial um neither if we're using a graded lexicographic order neither of the leading terms divide either of these terms of the polynomial so the whole thing just goes into the remainder and so the division algorithm outputs p equals zero f1 plus zero f2 plus p um which isn't very helpful so yeah i'll wrap it up there i'll mention so i guess yeah in the talk next week i'll introduce grover bases which are just defined to essentially fix this problem