What is a Gröbner basis and how to make one

Read first: Hilbert’s basis theorem

In this post we define the notion of a Gröbner basis of a polynomial ideal, which is an ideal basis possessing favourable properties related to multivariate polynomial division. It is a notion of central importance in algebraic geometry. Good reading material is this book¹ and this thesis².

Gröbner bases

Definitions

A Gröbner basis is a “good” basis of a polynomial ideal and it helps give a solution to the ideal membership problem, which is stated as follows:

Ideal membership problem: Given an ideal $I$ and a polynomial $f$, we need to tell whether $f\in I$ (in a computationally tractable manner).

Let us give the definition of a Gröbner basis:

A Gröbner basis exists as we saw in the proof of Hilbert’s basis theorem (and it is a basis of $I$; see Lemma 1 below).

Recall that in general, for $g_1, \ldots, g_t\in I$,

$$\langle \mathrm{lt}(g_1), \ldots, \mathrm{lt}(g_s)\rangle \subseteq \langle \mathrm{lt}(I)\rangle.$$

Let's show that a Gröbner basis is indeed a basis.

Proof. Let $G=\{g_1, \ldots, g_t\}$ be a Gröbner basis. Evidently, since $G\subseteq I$, $\langle G\rangle \subseteq I$. Pick an $f\in I$. By the multivariate division algorithm,

$$f = a_1g_1 + \ldots + a_tg_t + r,$$

for some $a_i\in k[x_1, \ldots, x_n]$ and no monomials of $r$ are divisible by the leading terms of any $g_i$. Suppose $r\neq 0$. Then, $r = f - a_1g_1 - \ldots - a_tg_t,$ so $r\in I$. This means that

$$\mathrm{lt}(r) \in \mathrm{lt}(I)\subseteq \langle \mathrm{lt}(I)\rangle = \langle G\rangle,$$

where the last equality is because $G$ is a Gröbner basis. The key here is that $\langle G\rangle$ is a monomial ideal and the monomial ideal membership problem is easy to decide according to this proposition!

Let's see what we have: we know that the monomial $\mathrm{lt}(r)$ belongs to the monomial ideal $\langle G\rangle$, which means that a monomial of $\langle G\rangle$ divides it. This is impossible! $\Box$

Exercises

These are exercises from¹.

Solution. Using the lex ordering, the leading terms of $g_1, g_2, g_3$ are $\mathrm{lt}(g_1)=xy^2$, $\mathrm{lt}(g_2)=xy$, and $\mathrm{lt}(g_3)=x$. We need to come up with a $g\in I$ such that the monomial $\mathrm{lt}(g)$ is not divisible by any of $\mathrm{lt}(g_1), \mathrm{lt}(g_2), \mathrm{lt}(g_3)$. Actually, it suffices that $\mathrm{lt}(g)$ be not a polynomial in $x$. To pick a $g\in I$ we do

$$g = a_1g_1 + a_2 g_2 + a_3g_3.$$

If we choose $a_1=1$, $a_2 = -y$ and $a_3=z$ we have $g = - yz^5 + yz^2 + y$ and $\mathrm{lt}(g) = - yz^5$, which is not divisibly by $xy^2$, $xy$, or $x$.

This can be confirmed by the following MATLAB code using our MATLAB algebraic geometry toolbox

ord = @(s1, s2) lex(s1, s2);

[x, y, z] = polysymbols({'x', 'y', 'z'}, ord);

g1 = x*y^2 - x*z + y;
g2 = x*y - z^2;
g3 = x - y*z^4;

g = g1 - y*g2 + z*g3;
lt_g = g.leadTermAsPolynomial
lt_gi  = {...
    g1.leadTermAsPolynomial, ...
    g2.leadTermAsPolynomial, ...
    g3.leadTermAsPolynomial};

[q, r] = lt_g.euclideanDivision(lt_gi);

The nonzero remainder of $r=-yz^5$ proves that $g$ is such a polynomial. $\bullet$

Solution. There is an $f\in I$ such that $$\mathrm{lt}(f) \notin \langle \mathrm{lt}(f_1), \ldots, \mathrm{lt}(f_s)\rangle,$$ and note that $\mathrm{lt}(f)$ is a monomial and $\langle \mathrm{lt}(f_1), \ldots, \mathrm{lt}(f_s)\rangle$ is a monomial ideal. From this proposition, we conclude that $\mathrm{lt}(f)$ is not divisible by any of $\mathrm{lt}(f_1), \ldots, \mathrm{lt}(f_s)$, so from the multivariate division algorithm the remainder of the division of $f$ by $f_1, \ldots, f_s$ is nonzero. $\bullet$

Solution. If $I=\langle g_1, \ldots, g_t\rangle$ and $\{g_1, \ldots, g_t\}$ is a Gröbner basis, then we can tell whether $f\in I$ by performing a multivariate division by the generating polynomials. If the remainder is zero, then $f\in I$. $\bullet$

Solution. This is because

$$\begin{aligned} & f \in \langle \mathrm{lt}(g); g\in I\setminus \{0\}\rangle \\ \Rightarrow{} & f = \sum_{i=1}^{m}a_i \mathrm{lt}(g_i), a_i\in k[x_1,\ldots, x_n], g_i\in I \\ \Rightarrow{} & f = \sum_{i=1}^{m}a_i \operatorname{lc}(g_i)\operatorname{lm}(g_i) = \sum_{i=1}^{m}\tilde{a}_i \operatorname{lm}(g_i), \end{aligned}$$

where $\tilde{a}_i = a_i \operatorname{lc}(g_i)$, so

$$f\in \langle \operatorname{lm}(g); g\in I\setminus \{0\}\rangle.$$

The converse is also simple. $\bullet$

Solution. (1) Suppose that $G=\{g_1, \ldots, g_t\}$ is a Gröbner basis of $I$ and $f\in I$. I want to show that $\mathrm{lt}(f)$ is divisible by one of $\mathrm{lt}(g_i)$. The fact that $\{g_1, \ldots, g_t\}$ is a Gröbner basis implies that

$$\mathrm{lt}(f) = a_1 \mathrm{lt}(g_1) + \ldots + a_t \mathrm{lt}(g_t),$$

Let us divide by each of $\mathrm{lt}(g_i)$ separately. This means that $\mathrm{lt}(f) \in \langle \mathrm{lt}(g_1), \ldots, \mathrm{lt}(g_t)\rangle$ and the latter is a monomial ideal, so from this proposition it is divisible by one of $\mathrm{lt}(g_i)$.

(2) For the converse, suppose that for every $f\in I$, $\mathrm{lt}(f)$ is divisible by an $\mathrm{lt}(g_i)$.

To show that $G$ is a Gröbner basis, we need to show that $\langle \mathrm{lt}(I)\rangle = \langle \mathrm{lt}(g_1), \ldots, \mathrm{lt}(g_t)\rangle$. It suffices to show that $\langle \mathrm{lt}(I)\rangle \subseteq \langle \mathrm{lt}(g_1), \ldots, \mathrm{lt}(g_t)\rangle$.

Let $f$ be such that $\mathrm{lt}(f)\in \langle \mathrm{lt}(I)\rangle$. This means

$$\begin{aligned} \mathrm{lt}(f) ={}& a_1 \mathrm{lt}(f_1) + \ldots + a_m \mathrm{lt}(f_m) \\ ={}& a_1h_1\mathrm{lt}(g_1) + \ldots + a_m h_m \mathrm{lt}(g_m) \\ {}\in{}& \langle \mathrm{lt}(g_1), \ldots, \mathrm{lt}(g_m)\rangle \end{aligned}$$

This completes the proof. $\Box$

Properties

First and foremost, a Gröbner basis for an ideal, $G=\{g_1, \ldots, g_t\}$, behaves nicely as a divisor: when we divide a polynomial $f$ by $(g_1, \ldots, g_t)$ the remainder is the same regardless of the order of the $g_i$.

Proof. If we divide $f$ by $(g_1, \ldots, g_t)$ we get

$$f = a_1g_1 + \ldots + a_tg_t + r,$$

where none of the monomials of $r$ is divisible by any of $\mathrm{lt}(g_1), \ldots, \mathrm{lt}(g_t)$. Let $g = a_1g_1 + \ldots + a_tg_t\in I$. Then, $f = g + r$.

It remains to prove that $r$ is unique: Suppose that $f = g + r = g' + r'$ such that condition (1) is satisfied. Then, $r-r' = g' - g \in I$. Suppose $r\neq r'$. Then,

$$\mathrm{lt}(r-r') \in \mathrm{lt}(I) \in \langle \mathrm{lt}(I) \rangle = \langle \mathrm{lt}(g_1), \ldots, \mathrm{lt}(g_t)\rangle.$$

By this proposition, $\mathrm{lt}(r-r')$ is divisible by at least one of $\mathrm{lt}(g_i)$. This is a contradiction, as neither none of the terms of $r$ nor $r'$ are divisible by any of $\mathrm{lt}(g_i)$ — see also this clarification. $\Box$

Note: Non-uniqueness of quotients. Although the remainder, $r$, is unique as we showed in Theorem 2, the quotients, $a_1, \ldots, a_t$, depend on the order of division.

Example: Consider the polynomial ideal $I=\langle f_1, f_2\rangle$ of ${\rm I\!R}[x, y]$ where $f_1 = x - y^4$ and $f_2 = xy - yx^2$ and the lex monomial ordering. A Gröbner basis for this ideal is $G = \{g_1, g_2, g_3\}$ with $g_1 = x - y^4$, $g_2 = x^2y - xy$, and $g_3 = y^9 - y^5$. Take the polymomial $f = x^2 - xy^4 + xy^2 + x - x^2y^2$ (chosen arbitrarily). The remainder of the division of $f$ by $G$ (in any order) is $r=y^4$. However, if we divide by $(g_1, g_2, g_3)$ we get

$$f = (- xy^2 + x - y^6 + y^2 + 1)g_1 + 0g_2 + (-y)g_3 + r,$$

whereas if we divide by $(g_2, g_3, g_1)$ we get

$$f = (-y)g_2 + 0g_3 + (x + 1)g_1 + r.$$

Here is a code snippet in MATLAB using our algebraic geometry toolbox:

ord = @(s1, s2) lex(s1, s2);
vars = {'x', 'y'};
[x, y] = polysymbols(vars, ord);
id = MultivariatePolynomial.id(vars, ord);

f1 = x - y^4; f2 = x*y - y*x^2;

I = PolynomialIdeal({f1, f2});
I.grobnerBasis(true);
G = I.grobner;

f = x^2 - x*y^4 + x*y^2 + x - x^2*y^2;
[q, r] = f.euclideanDivision({G{[1 2 3]}}) ;

Gröbner bases solve the ideal membership problem. Let us state this as a theorem.

Proof. If the remainder is zero, then $f=a_1g_1 + \ldots + a_tg_t$, so, evidently, $f\in I$. Conversely, if $f\in I$ then $f=f+0$ satisfies the conditions of Theorem 2, and due to the uniqueness of the remainder, zero is the remainder. $\Box$

Here is an example using our MATLAB algebraic geometry toolbox:

ord = @(s1, s2) lex(s1, s2);
vars = {'x', 'y'};
[x, y] = polysymbols(vars, ord);
id = MultivariatePolynomial.id(vars, ord);

f1 = x - y^4; f2 = x*y - y*x^2;

I = PolynomialIdeal({f1, f2});

f = (x^2 + y^2 + 3*id) * f1 + x*y*f2;
is_member = I.ismember(f) % is true

The ideal membership problem is decided by dividing $f$ by a Gröbner basis of $I$ (computed internally).

More Exercises

Exercise 1 is a generalisation of Theorem 2:

Solution. Let $g$ and $r$ be as in Theorem 2 where we showed that the terms of $r$ are not divisible by any of $\mathrm{lt}(g_1), \ldots, \mathrm{lt}(g_t)$. We claim that the same $g$ and $r$ satisfy the conditions stated here.

Suppose $r_0$ is a term of $r$ (a monomial term). Aiming at a contradiction, suppose $r_0$ is divisible by an element of $\mathrm{lt}(I)$, i.e., $r_0 = b \mathrm{lt}(h)$ for some $h\in I$ and some polynomial $b\in k[x_1, \ldots, x_n]$. Note that

$$\begin{aligned} \mathrm{lt}(f) \in \langle \mathrm{lt}(I)\rangle = \langle \mathrm{lt}(g_1), \ldots, \mathrm{lt}(g_t)\rangle, \end{aligned}$$

therefore,

$$r_0 \in \langle \mathrm{lt}(I)\rangle = \langle \mathrm{lt}(g_1), \ldots, \mathrm{lt}(g_t)\rangle.$$

From this proposition, $r_0$ is divisible by one of $\mathrm{lt}(g_i)$, which is a contradiction.

Note that we limited our search to decompositions of the form $f = g+r$ where $r$ satisfies the conditions of Theorem 2; this is necessary because we're trying to prove something stronger. $\bullet$

Solution. We'll show this building up on Exercise 1a, although uniqueness is already implied by Theorem 2. Suppose $f=g+r=g'+r'$ where the pairs $(g, r)$ and $(g', r')$ satisfy the conditions of Exercise 1a. Then $r-r' = g'-g\in I$, so $\mathrm{lt}(r-r')\in \mathrm{lt}(I)\subseteq \langle \mathrm{lt}(I)\rangle$, which is a monomial ideal; see again the definition of $\mathrm{lt}(I)$ here. From this proposition, this means that $\mathrm{lt}(q)$ divides $\mathrm{lt}(r-r')$ for some $q\in I$, which is impossible because $\mathrm{lt}(q)$ cannot divide any of the terms of $r$ or $r'$. $\bullet$

We will see now a proof that the definition is independent of the choice of Gröbner basis.

Solution. From Exercise 1a and Exercise 1b we can write $f=g+r$ where $g\in I$ and $r$ is the unique polynomial whose terms are not divisible by any of the monomials of $\mathrm{lt}(I)$. Note here that if $m$ is a monomial in $\langle \mathrm{lt}(I)\rangle$ then $m$ is divisible by an $\mathrm{lt}(\phi)$, $\phi\in I$. We conclude that the terms of $r$ are not divisible by any element of $\langle \mathrm{lt}(I)\rangle$. Note that

$$\langle \mathrm{lt}(I)\rangle = \langle \mathrm{lt}(g_1), \ldots, \mathrm{lt}(g_t)\rangle = \langle \mathrm{lt}(g_1'), \ldots, \mathrm{lt}(g_s')\rangle,$$

so $r$ is not divisible by any of $\mathrm{lt}(g_1), \ldots, \mathrm{lt}(g_t)$ or $\mathrm{lt}(g_1'), \ldots, \mathrm{lt}(g_s')$ and since it is unique, it is the same remainder regardless of the choice of Gröbner basis. $\Box$

Conclusion: We can talk about the remainder of the division of $f\in k[x_1, \ldots, x_n]$ by an ideal $I$; what we’ll mean by this is that if $G$ is a Gröbner basis of $I$, $$\overline{f}^I = \overline{f}^G.$$ As we saw in Exercise 4, the remainder is independent of the choice of Gröbner basis.

Solution. From Exercise 1a, we can write $f = q_f + \overline{f}^G$ and $g = q_g + \overline{g}^G$, where $q_f, q_g\in I$. If we subtract by parts we get $$f - g = (q_f - q_g) + (\overline{f}^G - \overline{g}^G).\tag{1}$$ Firstly, suppose that $\overline{f}^G = \overline{g}^G$. Then, from Equation (1) $f-g=q_f-q_g\in I$.

For the converse, suppose that $f-g\in I$. Then, from Equation (1) we see that $\overline{f}^G - \overline{g}^G = (f-g) - (q_f - q_g)$ and since $f-g\in I$ and $q_f, q_g\in I$ we conclude $\overline{f}^G - \overline{g}^G\in I$. Now $\overline{f}^G - \overline{g}^G$ must be equal to zero and here is why: firstly,

$$\overline{f}^G - \overline{g}^G\in I \Rightarrow \mathrm{lt}(\overline{f}^G - \overline{g}^G) \in \mathrm{lt}(I).\tag{2}$$

From Exercise 1a, none of the terms of $\overline{f}^G$ and $\overline{g}^G$ are divisible by any of the elements of $\mathrm{lt}(I)$, therefore, similar to our argument in Theorem 2, it must be $\overline{f}^G - \overline{g}^G = 0$.

Let us clarify this argument:

Clarification: Suppose $p, q\in k[x_1, \ldots, x_n]$ are polynomials and they have the form $$p = \sum_{i\in \mathcal{I}}a_ix^i, q = \sum_{j\in \mathcal{J}}b_j x^j.$$ Then, the terms of $p\pm q$ are some of the terms ${x^\iota}_{\iota \in I\cup J}$ and $\mathrm{lt}(p\pm q)$ is one of these. As a result, if $s\in k[x_1, \ldots, x_n]$ is such that $\mathrm{lt}(s)$ does not divide any of these terms, it does not divide $\mathrm{lt}(p \pm q)$. This is the argument we made above.

This completes the proof. $\bullet$

Solution. Suppose $f+g = q + r$ with $q\in I$ and no terms of $r$ are divisible by any element of $\mathrm{lt}(I)$. Likewise, $f = q_f + r_f$, $g = q_g + r_g$ and no terms of $r_f$ or $r_g$ are divisible by an element of $\mathrm{lt}(I)$. We have

$$q_f +q_g + r_f + r_g = q + r \Rightarrow r - (r_f + r_g) \in I,$$

and this implies that

$$\mathrm{lt}(r - r_f - r_g) \in \mathrm{lt}(I),$$

so as we did before, we conclude that $r = r_f + r_g$. $\bullet$

Solution. Here is a neat proof: Let $f = q_f + r_f$ and $g = q_g + r_g$. Then, $$fg = (q_f + r_f)(q_g + r_g) \in r_f r_g + I,$$ so $fg - r_f r_g \in I$, so from Exercise 13a $\overline{fg}^G = \overline{r_fr_g}^G$, which completes the proof. $\Box$

Buchberger’s criterion

Buchberger’s criterion allows us to tell whether a given basis is a Gröbner basis. Before we can state the criterion, we need to introduce a few definitions.

Good references for this topic are¹ and³.

Note that if $F$ is a Gröbner basis then the order of the elements of $F$ is not important, so we can treat $F$ as a set.

The remainder, $\overline{f}^F$ is also called the normal form of $f$.

We have shown that if $G$ is a Gröbner basis for $I$ then $f\in I$ iff $\overline{f}^G = 0$.

Note the the definition of lcm is with respect to an (implied) monomial ordering.

S-polynomials

Next, we define the $S$-polynomial of $f$ and $g$.

Again, the $S$-polynomial implies a monomial ordering.

Also note that $\mathrm{lt}(f) = \operatorname{lc}(f) x^\alpha$, so

$$\frac{x^\gamma}{\mathrm{lt}(f)} = \frac{x^\gamma}{\operatorname{lc}(f) x^\alpha} = \operatorname{lc}(f)^{-1}x^{\gamma - \alpha},$$

and given that $\gamma \geq \alpha$ (element-wise), $\gamma - \alpha$ is a multiindex.

Let's see what the $S$-polynomial looks like.

Example 1. In $\mathbb{Q}[x, y, z]$ take $f=x^2y+2z$ and $g=5xy + 7y^3z$. Using lex, $\mathrm{lt}(f)=x^2y$, $\mathrm{lt}(g)=5xy$, so $\alpha=(2, 1, 0)$ and $\beta=(1, 1, 0)$, so $\gamma=(2,1,0)$ and

$$\begin{aligned} S(f, g) {}={}& \frac{x^2y}{x^2y}f - \frac{x^2y}{5xy}g \\ {}={}& f - \frac{x}{5}g \\ {}={}& \cancel{x^2y}+2z -\cancel{x^2y} - \tfrac{7}{5}xy^3z = 2z - \tfrac{7}{5}xy^3z, \end{aligned}$$

This can be computed using our MATLAB algebraic geometry toolbox:

[x, y, z] = polysymbols({'x', 'y', 'z'}); % lex order is default

f = x^2 * y + 2*z; g = 5*x*y + 7*y^3*z;
sfg = f.spoly(g)

Let us make an observation about the terms involved in $S$: it is $$\frac{x^\gamma}{\mathrm{lt}(f)}f = \operatorname{lc}(f)^{-1}x^{\gamma - \alpha}f,$$ so $\operatorname{multideg}\left[\frac{x^\gamma}{\mathrm{lt}(f)}f\right] = \gamma$ and $\operatorname{multideg}\left[-\frac{x^\gamma}{\mathrm{lt}(g)}g\right] = \gamma$. This can be confirmed in Example 1.

The criterion

When we add these two polynomials, the leading terms cancel out. We now ask the "converse" question: if we have two polynomials $p_1$ and $p_2$ with the same multidegree (same as the two terms in $S$) and the leading terms cancel out, is it possible to describe $p_1 + p_2$ in terms of $S$-polynomials? The following lemma gives an affirmative answer.

The proof can be found in¹.

The lemma implies that if $\operatorname{multidegree}p_i=\delta$, then

$$\sum_i p_i = \sum_{j,l} c_{j,l}S(p_j, p_l).$$

As Cox et al.¹ put it, in the RHS “all cancellation can be accounted for by $S$-polynomials.”

This brings us to Buchberger's criterion:

Example 2. In $\mathbb{Q}[x, y, z]$ with lex we will show that $G={x^5 + 2y, xy^2, y^3}$ is a Gröbner basis. We have $$S(x^5 + 2y, xy^2) = 2y^3,$$ which is clearly in $I = \langle G\rangle$. Likewise, $$S(x^5 + 2y, y^3) = 2y^4 = 2y (y^3)\in I.$$ Lastly, $$S(xy^2, y^3) = 0 \in I.$$ We conclude that $G$ is a Gröbner basis. $\bullet$

Buchberger’s algorithm

Buchberger's algorithm allows us to construct a Gröbner basis of an ideal $I$.

In Buchberger's criterion we saw that if $G=\{g_1, \ldots, g_t\}$ is a Gröbner basis of an ideal $I$ then

$$\overline{S(g_i, g_j)}^G = 0,$$

for all $i\neq j$.

Suppose $I = \langle f_1, \ldots, f_s\rangle$ and $F=(f_1, \ldots, f_s)$ is not a Gröbner basis. Buchberger's algorithm extends $F$ — it adds more polynomials (from $I$) until we obtain a Gröbner basis. In particular, every time we have $\overline{S(g_i, g_j)}^G \neq 0$, the remainder $\overline{S(g_i, g_j)}^G$ is included into the basis.

To see how this works, let us compute some Gröbner bases¹:

Solution. We can do this with our MATLAB algebraic geometry toolbox:

ord = @(s1, s2) lex(s1, s2);

[x, y] = polysymbols({'x', 'y'}, ord);
id = MultivariatePolynomial([0 0 1], ord);
f1 = x^2*y - id;
f2 = x*y^2 - x;

F = {f1, f2};
I = PolynomialIdeal(F);
I.grobnerBasis();
G = I.grobner;

When using lex we end up with a Gröbner basis with 4 polynomials. This is

$$G_{\rm lex} = \{x^2y - 1, xy^2 - x, x^2 - y, y^2 - 1\}.$$

When using grlex we obtain the same Gröbner basis. $\bullet$

Solution. Again, using our MATLAB algebraic geometry toolbox, we have

ord = @(s1, s2) lex(s1, s2);

vars = {'x', 'y', 'z'};
[x, y] = polysymbols(vars, ord);
id = MultivariatePolynomial.id(vars, ord);

f1 = x^2 + y;
f2 = x^4 + 2*x^2*y+y^2+3*id;

F = {f1, f2};
I = PolynomialIdeal(F);
I.grobnerBasis();
G = I.grobner;

We find that regardless of the monomial ordering, it is

$$G = \{x^2+y, x^4+2x^2y+y^2+3, -3\},$$

and we see that a constant term has sneaked into $G$ which means that $I=\mathbb{Q}[x, y]$, so $\mathbf{V}(I) = \emptyset$. $\bullet$

Solution. Interestingly, using lex this is a Gröbner basis, but using grlex the generated Gröbner basis is

$$G_{\rm grlex}=\{- z^4 + x, - z^5 + y, - xz + y, yz^3 - x^2, - y^2z^2 + x^3, x^4 - y^3z\},$$

which involves six polynomials. $\bullet$

The algorithm

Buchberger’s algorithms is as follows:

Input: $F=\{f_1, \ldots, f_s\}$
Output: Gröbner basis $G=\{g_1, \ldots, g_t\} \supseteq F$ for $I$
1. $G\gets F$
2. Do
2.1. $G' \gets G$
2.2. For each $f,f'\in G$, compute $r = \overline{S(f_i, f_j)}^{G'}$; if $r\neq 0$ insert $r$ into $G'$
3. until $G'=G$.
4. return G

The algorithm creates an ascending chain of ideals, $\langle \mathrm{lt}(G')\rangle$, which is known to saturate.